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

Algoritmit
Luettelot matematiikasta