Luettelo algoritmeista

Seuraa **luettelo [[Algoritmi|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<br>
* 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<br>
** 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