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