Luettelo algoritmeista

Wikimedia-luetteloartikkeli

Seuraa luettelo algoritmeja kukin yhden rivin kuvauksella.

Automatisoitu suunnitteluMuokkaa

Kombinatoriset algoritmitMuokkaa

Yleiset kombinatoriset algoritmitMuokkaa

VerkkoalgoritmitMuokkaa

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

  • Voimiin perustuvat algoritmit: fysiikkaan perustuvia algoritmeja, esim. jousialgoritmit
  • Spektriasettelu (spectral layout)

VerkkoteoriaMuokkaa

  • Verkkoanalyysi
    • Linkkianalyysi
      • Girvan–Newman -algoritmi: tunnistaa yhteisöjä monimutkaisista verkoista, eli tiheästi yhdistettyjä solmujoukkoja
      • Hyperlinkkianalyysi
        • Hyperlink-Induced Topic Search (HITS)
        • PageRank
        • TrustRank
  • Virtausverkot

ReititysMuokkaa

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

VerkkohakuMuokkaa

  • 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

AliverkotMuokkaa

  • 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

JonoalgoritmitMuokkaa

Summittainen jonojen vertailuMuokkaa

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

  • Quickselect
  • Introselect

JonohakuMuokkaa

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

  • Yksinkertainen yhdistämisalgoritmi
  • k-suuntainen yhdistämisalgoritmi
  • Unioni (yhdistäminen tuloksen alkioita toistamatta)

Jonojen permutaatiotMuokkaa

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

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

Pääartikkeli: Lajittelualgoritmi

AlijonotMuokkaa

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

AlimerkkijonotMuokkaa

  • 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

DatavirratMuokkaa

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 matematiikkaMuokkaa

Abstrakti algebraMuokkaa

TietokonealgebraMuokkaa

GeometriaMuokkaa

Lukuteoreettiset algoritmitMuokkaa

Numeerisia algoritmejaMuokkaa

Differentiaaliyhtälön ratkaiseminenMuokkaa

Alkeis- ja erikoisfunktioitaMuokkaa

Geometrisia algoritmejaMuokkaa

Interpolointi ja ekstrapolointiMuokkaa

LineaarialgebraMuokkaa

Monte CarloMuokkaa

Numeerinen integrointiMuokkaa

Juurien etsintäMuokkaa

OptimointialgoritmitMuokkaa

Laskennallinen tiedeMuokkaa

TähtitiedeMuokkaa

BioinformatiikkaMuokkaa

MaantiedeMuokkaa

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

KielitiedeMuokkaa

LääketiedeMuokkaa

FysiikkaMuokkaa

TilastotiedeMuokkaa

TietojenkäsittelytiedeMuokkaa

TietokonearkkitehtuuriMuokkaa

TietokonegrafiikkaMuokkaa

Kryptografia tai salakirjoitusMuokkaa

Digitaalinen logiikkaMuokkaa

Koneoppiminen ja tilastollinen luokitteluMuokkaa

Ohjelmointikielten teoriaMuokkaa

JäsennysMuokkaa

KvanttialgoritmejaMuokkaa

Tietojenkäsittelyteoria ja automaatitMuokkaa

Informaatioteoria ja signaalinkäsittelyMuokkaa

KoodausteoriaMuokkaa

Virheenhavaitseminen ja -korjausMuokkaa

Häviöttömät pakkausalgoritmitMuokkaa

Häviölliset pakkausalgoritmitMuokkaa

Digitaalinen signaalinkäsittelyMuokkaa

SignaalinkäsittelyMuokkaa

  • FFT, nopea Fourier’n muunnos

KuvankäsittelyMuokkaa

OhjelmistotuotantoMuokkaa

Tietokanta-algoritmitMuokkaa

Hajautettujen järjestelmien algoritmitMuokkaa

Muistinhallinta-algoritmitMuokkaa

ViestiliikennealgoritmitMuokkaa

KäyttöjärjestelmäalgoritmitMuokkaa

Prosessien synkronointiMuokkaa

AikataulutusMuokkaa

Kovalevyn aikataulutusMuokkaa

Katso myösMuokkaa