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