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
- Girvan–Newman -algoritmi: tunnistaa yhteisöjä monimutkaisista verkoista, eli tiheästi yhdistettyjä solmujoukkoja
- Linkkianalyysi
- 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
- Bellman–Ford -algoritmi: löytää lyhimmät polut painotetulle verkolle, erimerkkisille painoille
- 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
- Bron–Kerbosch -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
- Path-based strong component algorithm eli polkuihin perustuva 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
- Damerau–Levenshtein -etäisyys vierekkäisten merkkien vaihdon huomioiva parannus Levenshtein-etäisyyteen
- 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
- Puolitushaku eli binäärihaku: Jos tietoa jakaumasta ei saada, teoreettisesti nopein hakualgoritmi järjestetylle listalle
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
- Pääartikkeli: Lajittelualgoritmi
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
- Aho–Corasick -merkkijonotäsmäysalgoritmi: puuhun perustuva algoritmi, joka löytää kaikki tiettyyn merkkijonojoukkoon täsmäävät alimerkkijonot
- 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