Luettelo algoritmeista

Seuraa luettelo algoritmeja kukin yhden rivin kuvauksella.

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

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
    
• 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

Lukuteoreettiset algoritmit

• Eukleideen algoritmi kahden kokonaisluvun suurimman yhteisen tekijän löytämiseksi
• Eratostheneen seula alkulukujen luettelemiseen

Laskennallinen tiede

Maantiede

• Vincenty on kaavat: nopea algoritmi laskea etäisyys kahden leveysaste/pituusaste pistettä ellipsoid

Informaatioteoria ja signaalinkäsittely

Digitaalinen signaalinkäsittely

Signaalinkäsittely

• FFT, nopea Fourier’n muunnos

Katso myös

• Luettelo tietorakenteista
• Heuristiikka