Luettelo algoritmeista
Wikimedia-luetteloartikkeli
Seuraa luettelo algoritmeja kukin yhden rivin kuvauksella.
Automatisoitu suunnittelu muokkaa
Kombinatoriset algoritmit muokkaa
Yleiset kombinatoriset algoritmit muokkaa
- 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 muokkaa
- 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 muokkaa
- Voimiin perustuvat algoritmit: fysiikkaan perustuvia algoritmeja, esim. jousialgoritmit
- Spektriasettelu (spectral layout)
Verkkoteoria muokkaa
- 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 muokkaa
- 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 muokkaa
- 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 muokkaa
- 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 muokkaa
Summittainen jonojen vertailu muokkaa
- 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 muokkaa
- Quickselect
- Introselect
Jonohaku muokkaa
- 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 muokkaa
- Yksinkertainen yhdistämisalgoritmi
- k-suuntainen yhdistämisalgoritmi
- Unioni (yhdistäminen tuloksen alkioita toistamatta)
Jonojen permutaatiot muokkaa
- 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 muokkaa
- 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 muokkaa
- Pääartikkeli: Lajittelualgoritmi
Alijonot muokkaa
- 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 muokkaa
- 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 muokkaa
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 muokkaa
Abstrakti algebra muokkaa
Tietokonealgebra muokkaa
Geometria muokkaa
Lukuteoreettiset algoritmit muokkaa
- Eukleideen algoritmi kahden kokonaisluvun suurimman yhteisen tekijän löytämiseksi
- Eratostheneen seula alkulukujen luettelemiseen
Numeerisia algoritmeja muokkaa
Differentiaaliyhtälön ratkaiseminen muokkaa
Alkeis- ja erikoisfunktioita muokkaa
Geometrisia algoritmeja muokkaa
Interpolointi ja ekstrapolointi muokkaa
Lineaarialgebra muokkaa
Monte Carlo muokkaa
Numeerinen integrointi muokkaa
Juurien etsintä muokkaa
Optimointialgoritmit muokkaa
Laskennallinen tiede muokkaa
Tähtitiede muokkaa
Bioinformatiikka muokkaa
Maantiede muokkaa
- Vincenty on kaavat: nopea algoritmi laskea etäisyys kahden leveysaste/pituusaste pistettä ellipsoid
Kielitiede muokkaa
Lääketiede muokkaa
Fysiikka muokkaa
Tilastotiede muokkaa
Tietojenkäsittelytiede muokkaa
Tietokonearkkitehtuuri muokkaa
Tietokonegrafiikka muokkaa
Kryptografia tai salakirjoitus muokkaa
Digitaalinen logiikka muokkaa
Koneoppiminen ja tilastollinen luokittelu muokkaa
Ohjelmointikielten teoria muokkaa
Jäsennys muokkaa
Kvanttialgoritmeja muokkaa
Tietojenkäsittelyteoria ja automaatit muokkaa
Informaatioteoria ja signaalinkäsittely muokkaa
Koodausteoria muokkaa
Virheenhavaitseminen ja -korjaus muokkaa
Häviöttömät pakkausalgoritmit muokkaa
Häviölliset pakkausalgoritmit muokkaa
Digitaalinen signaalinkäsittely muokkaa
Signaalinkäsittely muokkaa
- FFT, nopea Fourier’n muunnos