Luettelo algoritmeista

Seuraa luettelo algoritmeja kukin yhden rivin kuvauksella.

 Automatisoitu suunnittelu 

 Kombinatoriset algoritmit 

 Yleiset kombinatoriset algoritmit 
 Brentin algoritmi: etsii toistojakson funktion arvoista kahdella iteraattorilla
 Floydin syklinetsimisalgoritmi: etsii toistojakson funktion arvoista
 Gale–Shapley -algoritmi: ratkaisee vakaa avioliitto -ongelman
 Näennäissatunnaislukugeneraattorit (tasajakauma):
 Blum Blum Shub
 Viivästetty Fibonacci-generaattori
 Lineaarinen kongruenssigeneraattori
 Mersenne twister

 Verkkoalgoritmit 
 Väritysalgoritmi: Verkonväritysalgoritmi
 Hopcroft–Karpin algoritmi: kaksijakoisen verkon maksimisovitus
 Unkarilainen algoritmi: kaksijakoisen verkon maksimisovitus
 Prüferin listaesitys: muodostaa Prüferin listaesityksen puulle
 Tarjanin viimeisimmät yhteiset esivanhemmat -offline-algoritmi: etsii puusta kahden solmun lähimmän yhteisen esivanhemman
 Topologinen lajittelu: järjestää suunnatun syklittömän verkon (DAG) solmut jonoksi riippuvuuksien mukaan

 Verkkojen piirtäminen 
 Voimiin perustuvat algoritmit: fysiikkaan perustuvia algoritmeja, esim. jousialgoritmit
 Spektriasettelu (spectral layout)

 Verkkoteoria 
 Verkkoanalyysi
 Linkkianalyysi
 Girvan–Newman -algoritmi: tunnistaa yhteisöjä monimutkaisista verkoista, eli tiheästi yhdistettyjä solmujoukkoja
 Hyperlinkkianalyysi
 Hyperlink-Induced Topic Search (HITS)
 PageRank
 TrustRank
 Virtausverkot
 Dinic'n algoritmi: on vahvasti polynominen algoritmi maksimivirtauksen laskemiseen
 Edmonds–Karp -algoritmi: Ford–Fulkerson -algoritmin toteutus
 Ford–Fulkerson -algoritmi: laskee maksimivirtauksen
 Kargerin algoritmi: Monte Carlo-menetelmä verkon pienimmän leikkauksen laskemiseen
 Push-relabel -algoritmi: laskee maksimivirtauksen 

 Reititys 
 Edmondsin algoritmi (tunnetaan myös nimellä Chu Liu/Edmondsin algoritmi): suurin tai pienin haaroitus
 Euklidinen pienin virityspuu: pienin virityspuu pisteille tasossa
 Euklidinen lyhimmän polun ongelma: löytää lyhimmän polun kahden pisteen välillä leikkaamatta mitään estettä
 Pisimmän polun ongelma: löytää pisimmän yksinkertaisen polun
 Pienin virityspuu
 Borůvkan algoritmi
 Kruskalin algoritmi
 Primin algoritmi
 Reverse-delete -algoritmi
 Nonblocking Minimal Spanning Switch yksinkertaisin aina toimiva kytkin esim. puhelinkeskukseen 
 Lyhimmän polun ongelma
 Bellman–Ford -algoritmi: löytää lyhimmät polut painotetulle verkolle, erimerkkisille painoille
 Dijkstran algoritmi: löytää lyhimmät polut painotetusta verkosta, positiivisille painoille
 Floyd–Warshall -algoritmi: ratkaisee kaikki parit, lyhin polku -ongelman painotetulle, suunnattulle verkolle
 Johnsonin algoritmi: Kaikki parit, lyhin polku -algoritmi harvalle, painotetulle, suunnatulle verkolle
 Transitiivinen sulkeuma -ongelma: löytää binäärirelaation transitiivisen sulkeuman
 Kauppamatkustajan ongelma
 Christofides-algoritmi
 Lähin naapuri -algoritmi
 Ratsun kierto: Warndorffin algoritmi - heuristinen menetelmä Ratsun kierto -ongelmaan

 Verkkohaku 
 A*-algoritmi: heuristinen hakualgoritmi. Erikoistapaus paras ensin -hakualgoritmista.
 B*-algoritmi: paras ensin -hakualgoritmi, joka etsii halvimman polun lähtösolmusta mihin tahansa kohdesolmuun
 Backtracking: Peruuttava haku, eli vetäytyminen/luopuminen osittaisesta ratkaisusta havaittaessa, että se ei johda ratkaisuun
 Beam-haku toimii leveyshaun tavoin, paitsi joka kierroksella säilytetään heuristisesti parhaat N solmua ja karsitaan loput
 Beam stack -haku: yhdistää vetäytymisen Beam -hakuun
 Paras ensin -haku: kulkee verkon prioriteettijärjestyksessä käyttäen prioriteettijonoa
 Kaksisuuntainen haku: etsii suunnatun verkon lyhimmän polun lähtösolmusta kohdesolmuun
 Bloom-suodatin: vakioaikainen ja -muistinen joukon jäsenyystarkistus. Voi tuottaa vääriä positiivisia, mutta ei koskaan vääriä negatiivisia.
 Leveyshaku (BFS): kulkee verkon läpi syvyystasoittain
 D*: inkrementaalinen, heuristinen hakualgoritmi. Hyödyntää edellisten hakujen välituloksia, muuten kuin A*-algoritmi.
 Syvyyshaku (DFS): kulkee verkon läpi säteittäin
 Dijkstran algoritmi: A*-algoritmi heuristiikka kytkettynä pois päältä, prioriteettina kaaren lyhyys. Vaihtoehtoisesti etsii lyhimmän polun lähtösolmusta kaikkiin muihin solmuihin.
 General Problem Solver: uraauurtava matemaattisten lauseiden todistusalgoritmi vuodelta 1959, jonka tarkoituksena oli toimia yleisenä ongelmanratkaisukoneena. Verkko muodostetaan aksioomien ja johtopäätösten välille.
 Iteratiivinen syvenevä syvyyshaku (IDDFS): syvyyshakua toistetaan kasvavalla hakusyvyydellä. Eräänlainen kompromissi leveys- ja syvyyshaun välillä. 
 Jump point search: A* lisäheuristiikoilla. Toimii painottamattomissa hiloissa (ruudukko, jossa esteitä).
 Leksikografinen leveyshaku (tunnetaan myös nimellä Lex-BFS): lineaariaikainen algoritmi verkon solmujen järjestämiseen
 Uniform-cost search: alias Dijkstran algoritmille
 SSS*: A*-algoritmin kaltainen tila-avaruushaku (state space search) pelipuulle, esim. shakin siirrot

 Aliverkot 
 Klikit
 Bron–Kerbosch -algoritmi: löytää maksimaaliset klikit suuntaamattomasta verkosta
 MaxCliqueDyn maksimaalinen klikki -algoritmi: löytää maksimaaliset klikit suuntaamattomasta verkosta
 Vahvasti yhtenäiset komponentit
 Path-based strong component algorithm eli polkuihin perustuva vahvasti yhtenäisten komponenttien algoritmi
 Kosarajun algoritmi
 Tarjanin vahvasti yhtenäisten komponenttien algoritmi

 Jonoalgoritmit 

 Summittainen jonojen vertailu 
 Bitap algoritmi: sumea algoritmi, joka määrittää, ovatko merkkijonot suunnilleen samat
 Foneettisia algoritmeja
 Daitch–Mokotoff Soundex: Soundex-parannus, joka mahdollistaa slaavilainen ja germaanisten sukunimien tunnistamisen
 Double Metaphone: parannus Metaphoneen
 Match Rating Approach: Western Airlinesin kehittämä foneettinen algoritmi
 Metaphone: indeksöi englanninkielisiä sanoja
 NYSIIS: Soundex-parannus
 Soundex: indeksöi englanniksi lausuttuja nimiä
 Merkkijonomittarit: merkkijonojen samankaltaisuus tai etäisyys
 Damerau–Levenshtein -etäisyys vierekkäisten merkkien vaihdon huomioiva parannus Levenshtein-etäisyyteen 
 Dicen kerroin (tunnetaan myös nimellä Dice-kerroin): samankaltaisuusmittari joka on sukua Jaccard-indeksille
 Hamming-etäisyys: eroavien alkioiden määrä
 Jaro–Winkler -etäisyys: samankaltaisuusmitta kahden merkkijonon välillä
 Levenshteinin etäisyys: kahden sekvenssin muokkausetäisyys laskettuna merkkien lisäyksillä, poistoilla ja korvauksilla
 Trigram-haku: etsii tekstiä, kun tarkka kirjoitusasu tai kohde ei ole tiedossa

 Valinta-algoritmeja 
 Quickselect
 Introselect

 Jonohaku 
 Peräkkäishaku: Etsii kohteen järjestämättömästä jonosta
 Valinta-algoritmi: Löytää k:nneksi suurimman alkion
 Ternäärihaku:  etsii suurimman alkion taulukossa, jonka alkuosa on nouseva ja loppuosa on laskeva
 Järjestetyt listat
 Puolitushaku eli binäärihaku: Jos tietoa jakaumasta ei saada, teoreettisesti nopein hakualgoritmi järjestetylle listalle
 Fibonacci-hakutekniikka: hajota ja hallitse-algoritmi, hyödyntää hakuavaruuden pilkkomisessa Fibonaccin lukuja
 Hyppyhaku (tai lohkohaku): karkea peräkkäishaku ensin lohkon löytämiseksi ja sitten tarkempi peräkkäishaku löydetyn lohkon sisällä
 Ennakoiva haku: kuten binäärihaku, mutta huomioi hakutermin ja tarkistettujen alkioiden koot. Kutsutaan myös sanakirjahauksi ja interpoloiduksi hauksi.
 Tasainen binäärihaku: optimoitu versio klassisesta puolitushausta arkkitehtuureille, joilla taulukosta lukeminen on nopeampaa kuin bitinshiftaus ja yhteenlasku

 Jonojen yhdistäminen 
 Yksinkertainen yhdistämisalgoritmi
 k-suuntainen yhdistämisalgoritmi
 Unioni (yhdistäminen tuloksen alkioita toistamatta)

 Jonojen permutaatiot 
 Fisher–Yates shuffle (tunnetaan myös nimellä Knuth shuffle): permutoi joukon satunnaisesti ja harhattomasti, toisin sanoen sekoittaa pakan
 Schensted-algoritmi: luo permutaatiota vastaavat Youngin taulut
 Steinhaus–Johnson–Trotter -algoritmi (tunnetaan myös nimellä Johnson–Trotter algoritmi): luo kaikki permutaatiot vaihtamalla vierekkäisten alkioiden paikkoja (transpositio)
 Heapin permutaatiogenerointialgoritmi: vaihtaa elementtien paikkaa permutaatioiden luomiseen

 Jonojen linjaaminen 
 Dynamic time warping: mittaa kahden ajallisesti ja nopeudeltaan vaihtelevan jonon samankaltaisuutta
 Hirschbergin algoritmi: löytää linjauksen joka minimoi jonojen välisen Levenshtein-etäisyyden
 Needleman–Wunsch -algoritmi: optimoi jonojen globaalin linjauksen
 Smith–Waterman -algoritmi: optimoi jonojen paikallisen linjauksen

 Jonojen järjestäminen 

 Alijonot 
 Kadanen algoritmi: etsii alijonon, jonka peräkkäisten alkioiden summa on suurin
 Pisimmän yhteisen alijonon ongelma: Löytää jonojoukon pisimmän kaikille jonoille yhteisen alijonon, jonka ei tarvitse olla yhtenäinen
 Pisimmän kasvavan alijonon ongelma: Löytää pisimmän kasvavan alijonon, jonka ei tarvitse olla yhtenäinen
 Lyhimmän yhteisen ylijonon ongelma: Löytää lyhimmän tietyn alijonojoukon sisältävän ylijonon. Alijonojen ei tarvitse olla ylijonossa yhtenäisiä. 

 Alimerkkijonot 
 Pisimmän yhteisen alimerkkijonon ongelma: etsii pisimmän merkkijonon (tai -jonot), joka on kahden tai useamman muun merkkijonon alimerkkijono
 Alimerkkijonohaku
 Aho–Corasick -merkkijonotäsmäysalgoritmi: puuhun perustuva algoritmi, joka löytää kaikki tiettyyn merkkijonojoukkoon täsmäävät alimerkkijonot
 Boyer–Moore -merkkijonohakualgoritmi: amortisoidusti lineaarinen, yleensä sublineaarinen merkkijonohakualgoritmi
 Boyer–Moore–Horspool -algoritmi: Boyer–Moore -algoritmin yksinkertaistus
 Knuth–Morris–Pratt -algoritmi: merkkijonohaku joka välttää vertaamasta täsmääviä merkkejä toista kertaa
 Rabin–Karp -merkkijonohakualgoritmi: hakee useita merkkijonoja kerralla tehokkaasti
 Zhu–Takaoka -merkkijonotäsmäysalgoritmi variantti Boyer–Moore -algoritmista
 Ukkosen algoritmi: lineaariaikainen online-algoritmi päätepuiden rakentamiseen

 Datavirrat 
Datavirta-algoritmit käsittelevät jonoja tyypillisesti yhdellä läpikäynnillä, rajoitetulla muistilla ja prosessointiajalla

 Boyer–Moore majority vote algorithm, eli enemmistöäänestysalgoritmi - Löytää absoluuttisen enemmistöalkion (jos sellainen on)

 Lossy Count Algorithm, eli häviöllinen lukumääränlaskualgoritmi - Löytää alkiot, joiden suhteellinen osuus ylittää annetun tason, annetulla virhemarginaalilla

 Misra–Gries summary, eli yhteenvetoalgoritmi - Löytää joukon alkioita, jotka yhdessä muodostavat annetun persentiilin datavirrasta

 Laskennallinen matematiikka 

 Abstrakti algebra 

 Tietokonealgebra 

 Geometria 

 Lukuteoreettiset algoritmit 

 Eukleideen algoritmi kahden kokonaisluvun suurimman yhteisen tekijän löytämiseksi
 Eratostheneen seula alkulukujen luettelemiseen

 Numeerisia algoritmeja 

 Differentiaaliyhtälön ratkaiseminen 

 Alkeis- ja erikoisfunktioita 

 Geometrisia algoritmeja 

 Interpolointi ja ekstrapolointi 

 Lineaarialgebra 

 Monte Carlo 

 Numeerinen integrointi 

 Juurien etsintä 

 Optimointialgoritmit 

 Laskennallinen tiede 

 Tähtitiede 

 Bioinformatiikka 

 Maantiede 
 Vincenty on kaavat: nopea algoritmi laskea etäisyys kahden leveysaste/pituusaste pistettä ellipsoid

 Kielitiede 

 Lääketiede 

 Fysiikka 

 Tilastotiede 

 Tietojenkäsittelytiede 

 Tietokonearkkitehtuuri 

 Tietokonegrafiikka 

 Kryptografia tai salakirjoitus 

 Digitaalinen logiikka 

 Koneoppiminen ja tilastollinen luokittelu 

 Ohjelmointikielten teoria 

 Jäsennys 

 Kvanttialgoritmeja 

 Tietojenkäsittelyteoria ja automaatit 

 Informaatioteoria ja signaalinkäsittely 

 Koodausteoria 

 Virheenhavaitseminen ja -korjaus 

 Häviöttömät pakkausalgoritmit 

 Häviölliset pakkausalgoritmit 

 Digitaalinen signaalinkäsittely 

 Signaalinkäsittely 

 FFT, nopea Fourier’n muunnos

 Kuvankäsittely 

 Ohjelmistotuotanto 

 Tietokanta-algoritmit 

 Hajautettujen järjestelmien algoritmit 

 Muistinhallinta-algoritmit 

 Viestiliikennealgoritmit 

 Käyttöjärjestelmäalgoritmit 

 Prosessien synkronointi 

 Aikataulutus 

 Kovalevyn aikataulutus 

 Katso myös 
 Luettelo tietorakenteista
 Heuristiikka

Luokka:Algoritmit
Luokka:Luettelot matematiikasta