Lista över algoritmer - List of algorithms

Följande är en lista över algoritmer tillsammans med enradiga beskrivningar för varje.

Automatiserad planering

Kombinerande algoritmer

Allmänna kombinatoriska algoritmer

• Brents algoritm : hittar en cykel i funktionsvärde iterationer med endast två iteratorer
• Floyds cykel-hitta algoritm : hittar en cykel i funktionsvärde iterationer
• Gale – Shapley -algoritm : löser det stabila äktenskapsproblemet
• Pseudoslumpmässiga nummergeneratorer (enhetligt fördelade - se även Lista över pseudoslumpmässiga nummergeneratorer för andra PRNG med olika grad av konvergens och varierande statistisk kvalitet):
  • ACORN generator
  • Blum Blum Shub
  • Lagrad Fibonacci -generator
  • Linjär kongruentiell generator
  • Mersenne Twister

Grafalgoritmer

• Färgalgoritm : Graffärgningsalgoritm.
• Hopcroft – Karp -algoritm : konvertera en bipartitgraf till en maximal kardinalitetsmatchning
• Ungerska algoritmen : algoritm för att hitta en perfekt matchning
• Prüfer -kodning : konvertering mellan ett märkt träd och dess Prüfer -sekvens
• Tarjans off-line lägsta gemensamma förfäder algoritm : beräknar lägsta gemensamma förfäder för par av noder i ett träd
• Topologisk sortering : hittar linjär ordning av noder (t.ex. jobb) baserat på deras beroenden.

Diagramritning

• Kraftbaserade algoritmer (även känd som kraftstyrda algoritmer eller fjäderbaserade algoritmer)
• Spektral layout

Nätverksteori

• Nätverksanalys
  • Länkanalys
    • Girvan – Newman -algoritm : upptäcka samhällen i komplexa system
    • Webblänksanalys
      • Hyperlänkinducerad ämnesökning (HITS) (även känd som nav och myndigheter )
      • Sidrankning
      • TrustRank
• Flödesnätverk
  • Dinics algoritm : är en starkt polynom algoritm för att beräkna det maximala flödet i ett flödesnät .
  • Edmonds – Karp -algoritm : implementering av Ford – Fulkerson
  • Ford – Fulkerson -algoritm : beräknar det maximala flödet i en graf
  • Kargers algoritm : en Monte Carlo -metod för att beräkna minsta snitt av en ansluten graf
  • Push -relabel algoritm : beräknar ett maximalt flöde i en graf

Routing för grafer

• Edmonds algoritm (även känd som Chu – Liu/Edmonds algoritm): hitta maximala eller minsta förgreningar
• Euklidiskt minimumspanträd : algoritmer för att beräkna det minsta spanträdet för en uppsättning punkter i planet
• Euklidiska kortaste vägproblem : hitta den kortaste vägen mellan två punkter som inte skär något hinder
• Längsta sökvägsproblem : hitta en enkel väg med maximal längd i en given graf
• Minsta omfattande träd
  • Borůvkas algoritm
  • Kruskals algoritm
  • Prims algoritm
  • Reverse-delete algoritm
• Icke -blockerande minimal spänningsomkopplare säger, för en telefonväxel
• Kortaste vägproblem
  • Bellman – Ford -algoritm: beräknar kortaste vägar i en vägd graf (där några av kantvikterna kan vara negativa)
  • Dijkstras algoritm : beräknar kortaste vägar i en graf med icke-negativa kantvikter
  • Floyd – Warshall -algoritm : löser alla parens kortaste vägproblem i en vägd, riktad graf
  • Johnsons algoritm : Alla par kortaste banalgoritm i sparsamt vägd riktad graf
• Problem med transitiv stängning : hitta den transitiva stängningen av en given binär relation
• Resande säljare problem
  • Christofides algoritm
  • Närmaste granne algoritm
• Warnsdorffs regel : En heuristisk metod för att lösa Knight's tour -problemet.

Grafsökning

• A* : specialfall av bäst-först-sökning som använder heuristik för att förbättra hastigheten
• B* : en bäst-först-grafsökningsalgoritm som hittar den billigaste vägen från en given initialnod till vilken målnod som helst (av ett eller flera möjliga mål)
• Backtracking : överger partiella lösningar när de befinner sig inte uppfylla en komplett lösning
• Strålsökning : är en heuristisk sökalgoritm som är en optimering av bäst-först-sökning som minskar minneskravet
• Beam stack search : integrerar backtracking med beam search
• Bästa först-sökning : korsar en graf i storleksordningen sannolik betydelse med hjälp av en prioritetskö
• Dubbelriktad sökning : hitta den kortaste vägen från en inledande toppunkt till en målpunkt i en riktad graf
• Bredd-första sökning : korsar en graf nivå för nivå
• Brute-force-sökning : En uttömmande och pålitlig sökmetod, men beräknat ineffektiv i många applikationer.
• D * : en inkrementell heuristisk sökning algoritm
• Djup-första sökning : korsar en graf gren för gren
• Dijkstras algoritm : Ett specialfall av A* för vilket ingen heuristisk funktion används
• Allmän problemlösare : en grundläggande teorem-bevisande algoritm avsedd att fungera som en universell problemlösarmaskin.
• Iterativ fördjupad djup-första sökning (IDDFS): en statlig rymdsökstrategi
• Hoppningspunktsökning : En optimering till A* som kan minska beräkningstiden med en storleksordning med hjälp av ytterligare heuristik.
• Lexikografisk bredd-första sökning (även känd som Lex-BFS): en linjär tidsalgoritm för att ordna hörn i en graf
• Enhetlig kostnadssökning : en trädsökning som hittar den billigaste rutten där kostnaderna varierar
• SSS* : statlig rymdsökning som korsar ett spelträd på bästa sätt som liknar A* sökalgoritmens
• F* : Speciell algoritm för att slå ihop de två matriserna

Delgrafer

• Klickar
  • Bron – Kerbosch -algoritm : en teknik för att hitta maximala klickningar i en oriktad graf
  • MaxCliqueDyn algoritm för maximal klick : hitta en maximal klick i en oriktad graf
• Kraftigt anslutna komponenter
  • Vägbaserad algoritm för stark komponent
  • Kosarajus algoritm
  • Tarjans starkt anslutna komponentalgoritm
• Subgrafisk isomorfismproblem

Sekvensalgoritmer

Ungefärlig sekvensmatchning

• Bitap -algoritm : suddig algoritm som avgör om strängar är ungefär lika.
• Fonetiska algoritmer
  • Daitch – Mokotoff Soundex : en Soundex -förfining som möjliggör matchning av slaviska och germanska efternamn
  • Double Metaphone : en förbättring av Metaphone
  • Match rating -metod : en fonetisk algoritm utvecklad av Western Airlines
  • Metafon : en algoritm för att indexera ord efter deras ljud, när de uttalas på engelska
  • NYSIIS : fonetisk algoritm , förbättrar Soundex
  • Soundex : en fonetisk algoritm för att indexera namn efter ljud, som uttalas på engelska
• Strängmått : beräknar en likhet eller olikhet (avstånd) mellan två par textsträngar
  • Damerau – Levenshtein -avstånd : beräknar ett avståndsmått mellan två strängar, förbättrar Levenshtein -avståndet
  • Tärningskoefficient (även känd som tärningskoefficienten): ett likhetsmått relaterat till Jaccard -index
  • Hammningsavstånd : summan av positioner som är olika
  • Jaro – Winkler -avstånd : är ett mått på likhet mellan två strängar
  • Levenshtein redigera avstånd : beräknar ett mått för skillnaden mellan två sekvenser
• Trigramsökning : sök efter text när den exakta syntaxen eller stavningen för målobjektet inte är exakt känd

Urvalsalgoritmer

• Quickselect
• Introselekt

Sekvenssökning

• Linjär sökning : lokaliserar ett objekt i en osorterad sekvens
• Urvalsalgoritm : hittar det k: e största objektet i en sekvens
• Ternär sökning : en teknik för att hitta minimum eller maximalt för en funktion som antingen strikt ökar och sedan strikt minskar eller tvärtom
• Sorterade listor
  • Binär sökalgoritm : lokaliserar ett objekt i en sorterad sekvens
  • Fibonacci -sökteknik : sök i en sorterad sekvens med en dividera och erövra algoritm som begränsar möjliga platser med hjälp av Fibonacci -nummer
  • Hoppsökning (eller blockeringssökning): linjär sökning på en mindre delmängd av sekvensen
  • Prediktiv sökning : binärliknande sökning som faktorer i söktermens storlek kontra de höga och låga värdena i sökningen. Ibland kallas ordbokssökning eller interpolerad sökning.
  • Uniform binär sökning : en optimering av den klassiska binära sökalgoritmen

Sekvens sammanslagning

• Enkel sammanfogningsalgoritm
• k-way-kopplingsalgoritm
• Union (sammanslagning, med element på utgången upprepas inte)

Sekvenspermutationer

• Fisher – Yates shuffle (även känd som Knuth shuffle): slumpmässigt blanda en ändlig uppsättning
• Schensted -algoritm : konstruerar ett par unga tablåer från en permutation
• Steinhaus – Johnson – Trotter -algoritm (även känd som Johnson – Trotter -algoritmen): genererar permutationer genom att transponera element
• Heaps algoritm för permutationsgenerering : utbyteselement för att generera nästa permutation

Sekvenskombinationer

Sekvensjustering

• Dynamisk tidsförvrängning : mäta likheten mellan två sekvenser som kan variera i tid eller hastighet
• Hirschberg algoritm : finner den minsta kostnaden sekvensinpass mellan två sekvenser, såsom mätt genom deras levenshteinavstånd
• Needleman – Wunsch -algoritm : hitta global anpassning mellan två sekvenser
• Smith – Waterman -algoritm : hitta lokal sekvensjustering

Sekvenssortering

• Utbytesorter
  • Bubblesortering : för varje par index, byt objekten om de är ur funktion
  • Cocktail shaker sort eller dubbelriktad bubblasortering, en bubblasort som passerar listan växelvis framifrån och bakåt och bakåt till framsidan
  • Kamsortering
  • Gnome sort
  • Udda - jämn sort
  • Quicksort : dela listan i två, med alla objekt på den första listan före alla objekt på den andra listan .; sortera sedan de två listorna. Ofta valmetoden
• Humoristiskt eller ineffektivt
  • Bogosort
  • Stooge sort
• Hybrid
  • Flashsort
  • Introsort : börja med kvicksort och växla till högsort när rekursionsdjupet överstiger en viss nivå
  • Timsort : adaptiv algoritm som härrör från sammanslagningssortering och infogningssortering. Används i Python 2.3 och senare och Java SE 7.
• Insättningssorter
  • Infogningssortering : bestäm var det aktuella objektet hör hemma i listan över sorterade och infoga det där
  • Biblioteksortering
  • Tålamodssortering
  • Skalsortering : ett försök att förbättra införingssorteringen
  • Trädsortering (binär trädsortering): bygg binärt träd och korsa sedan det för att skapa sorterad lista
  • Cykelsortering : på plats med teoretiskt optimalt antal skrivningar
• Slå ihop sorter
  • Kopplingssortering : sortera den första och andra halvan av listan separat och slå sedan ihop de sorterade listorna
  • Långsam sortering
  • Strand sortera
• Icke-jämförelse sorter
  • Pärlsortering
  • Bucket sort
  • Burstsort : bygg en kompakt, cache -effektiv burst -trie och korsa den sedan för att skapa sorterad utdata
  • Räknar sortering
  • Duvhålssort
  • Postman sort : variant av Bucket sort som drar fördel av hierarkisk struktur
  • Radix sortera : sorterar strängar bokstav för bokstav
• Urvalssorter
  • Heapsort : konvertera listan till en hög, fortsätt ta bort det största elementet från högen och lägg till den i slutet av listan
  • Urvalssort : välj det minsta av de återstående elementen, lägg till det i slutet av den sorterade listan
  • Smidig sort
• Övrig
  • Bitonisk sorterare
  • Pannkakssortering
  • Spaghettisorter
  • Topologisk sort
• Okänd klass
  • Provsort

Efterföljningar

• Kadanes algoritm : hittar maximal delmatris av valfri storlek
• Längsta vanliga undersekvensproblem : Hitta den längsta undersekvensen som är gemensam för alla sekvenser i en uppsättning sekvenser
• Längsta ökande undersekvensproblem : Hitta den längsta ökande undersekvensen för en given sekvens
• Kortaste vanliga supersekvensproblem : Hitta den kortaste supersekvensen som innehåller två eller flera sekvenser som undersekvenser

Substrings

• Längsta vanliga delsträngsproblem : hitta den längsta strängen (eller strängarna) som är en delsträng (eller är underordnade) på två eller flera strängar
• Substrängsökning
  • Aho – Corasick strängmatchningsalgoritm : triebaserad algoritm för att hitta alla delsträngsmatchningar till någon av en ändlig uppsättning strängar
  • Boyer – Moore strängsökningsalgoritm : amortiserad linjär ( sublinär i de flesta gånger) algoritm för undersökning
  • Boyer – Moore – Horspool algoritm : Förenkling av Boyer – Moore
  • Knuth – Morris – Pratt -algoritm: delsträngssökning som kringgår omprövning av matchade tecken
  • Rabin – Karp strängsökningsalgoritm : söker effektivt efter flera mönster
  • Zhu – Takaoka strängmatchningsalgoritm : en variant av Boyer – Moore
• Ukkonen algoritm : en linjär tid , online-algoritm för att konstruera suffix träd
• Matchande jokertecken
  • Rich Salz ' wildmat : en allmänt använd öppen källkod rekursiva algoritm
  • Krauss matchande jokerteckenalgoritm : en icke-rekursiv algoritm med öppen källkod

Beräkningsmatematik

Abstrakt algebra

• Chiensökning : en rekursiv algoritm för att bestämma rötterna till polynom definierade över ett ändligt fält
• Schreier – Sims -algoritm : beräkning av en bas och stark genereringsuppsättning (BSGS) för en permutationsgrupp
• Todd -Coxeter -algoritm : Procedur för att generera cosets .

Datoralgebra

• Buchbergers algoritm : hittar en Gröbner -grund
• Cantor -Zassenhaus -algoritm : faktorpolynom över ändliga fält
• Faugère F4 -algoritm : hittar en Gröbner -grund (nämner också F5 -algoritmen)
• Gospers algoritm : hitta summor av hypergeometriska termer som själva är hypergeometriska termer
• Knuth – Bendix -kompletteringsalgoritm : för omskrivning av regelsystem
• Multivariat divisionsalgoritm : för polynom i flera obestämda
• Pollards kängururealgoritm (även känd som Pollards lambda -algoritm): en algoritm för att lösa det diskreta logaritmproblemet
• Polynom lång division : en algoritm för att dela ett polynom med ett annat polynom av samma eller lägre grad
• Risch -algoritm : en algoritm för beräkning av obestämd integration (dvs. att hitta antiderivativ )

Geometri

• Närmaste parproblem : hitta poängparet (från en uppsättning punkter) med det minsta avståndet mellan dem
• Kollisionsdetekteringsalgoritmer : kolla efter kollision eller skärningspunkt mellan två givna fasta ämnen
• Kegelalgoritm : identifiera ytpunkter
• Konvexa skrovalgoritmer : bestämning av det konvexa skrovet för en uppsättning punkter
  • Graham -skanning
  • Quickhull
  • Presentförpackningsalgoritm eller Jarvis -marsch
  • Chans algoritm
  • Kirkpatrick – Seidel -algoritm
• Euklidisk avståndstransform : beräknar avståndet mellan varje punkt i ett rutnät och en diskret samling av punkter.
• Geometrisk hash : en metod för att effektivt hitta tvådimensionella objekt representerade av diskreta punkter som har genomgått en affin transformation
• Gilbert – Johnson – Keerthi avståndsalgoritm : bestämma det minsta avståndet mellan två konvexa former.
• Jump-and-Walk-algoritm : en algoritm för punktläge i trianguleringar
• Laplacian smoothing : en algoritm för att jämna ut ett polygonalt nät
• Linjesegmentkorsning : hitta om linjer skär varandra, vanligtvis med en svepslinjealgoritm
  • Bentley -Ottmann -algoritm
  • Shamos – Hoey algoritm
• Minsta begränsningsboxalgoritmer : hitta den orienterade minimigränsrutan som omsluter en uppsättning punkter
• Närmaste grannsökning : hitta den eller de närmaste punkterna till en fråga
• Punkt i polygonalgoritmer : testar om en given punkt ligger inom en given polygon
• Registreringsalgoritmer för punktuppsättningar: hittar transformationen mellan två punktuppsättningar för att anpassa dem optimalt.
• Roterande bromsok : bestäm alla antipodala par av punkter och hörn på en konvex polygon eller konvex skrov .
• Skosnöre -algoritm : bestäm området av en polygon vars hörn beskrivs av ordnade par i planet
• Triangulering
  • Delaunay triangulering
    • Rupperts algoritm (även känd som Delaunay -förfining): skapa kvalitet på Delaunay -trianguleringar
    • Chews andra algoritm : skapa kvalitetsbegränsade Delaunay -trianguleringar
  • Marschande trianglar : rekonstruera tvådimensionell ytgeometri från ett ostrukturerat punktmoln
  • Polygontrianguleringsalgoritmer : bryt ner en polygon i en uppsättning trianglar
  • Voronoi -diagram , geometrisk dubbel av Delaunay triangulering
    • Bowyer – Watson -algoritm: skapa ett voronoi -diagram i valfritt antal dimensioner
    • Fortunes algoritm: skapa voronoi -diagram
  • Kvasitriangulering

Talteoretiska algoritmer

• Binär GCD -algoritm : Effektivt sätt att beräkna GCD.
• Booths multiplikationsalgoritm
• Chakravala -metod : en cyklisk algoritm för att lösa obestämda kvadratiska ekvationer, inklusive Pells ekvation
• Diskret logaritm :
  • Baby-step jätte-steg
  • Indexberäkningsalgoritm
  • Pollards rho -algoritm för logaritmer
  • Pohlig – Hellman -algoritm
• Euklidisk algoritm : beräknar den största gemensamma delaren
• Utökad euklidisk algoritm : Löser också ekvationen ax  +  med  =  c .
• Heltalsfaktorisering : bryta ett heltal i dess främsta faktorer
  • Kongruens av torg
  • Dixons algoritm
  • Fermats faktoriseringsmetod
  • Allmänt sifferfält
  • Lenstra elliptisk kurvfaktorisering
  • Pollards  algoritm p - 1
  • Pollards rho -algoritm
  • primfaktoriseringsalgoritm
  • Kvadratisk sil
  • Shors algoritm
  • Specialnummer fältsikt
  • Försöksindelning
• Multiplikationsalgoritmer : snabb multiplikation av två tal
  • Karatsuba algoritm
  • Schönhage – Strassen -algoritm
  • Toom – Cook multiplikation
• Modulär kvadratrot : beräkning av kvadratrötter modulerar ett primtal
  • Tonelli – Shanks -algoritm
  • Cipollas algoritm
  • Berlekamps rotfyndalgoritm
• Odlyzko – Schönhage -algoritm : beräknar icke -privata nollor för Riemann zeta -funktionen
• Lenstra-Lenstra-Lovasz algoritm (även känd som LLL algoritm): hitta en kort, nästan ortogonala gitterbasis i polynomisk tid
• Primalitetstester : avgör om ett givet tal är primtal
  • AKS -primitetstest
  • Baillie -PSW primitetstest
  • Fermat primitetstest
  • Lucas primitetstest
  • Miller – Rabin primitetstest
  • Sikt av Atkin
  • Sikt av Eratosthenes
  • Sikt av Sundaram

Numeriska algoritmer

Lösning av differentialekvationer

• Euler metod
• Backward Euler -metod
• Trapezformad regel (differentialekvationer)
• Linjära flerstegsmetoder
• Runge – Kutta -metoder
  • Euler -integration
• Multigridmetoder (MG -metoder), en grupp algoritmer för att lösa differentialekvationer med hjälp av en hierarki av diskretiseringar
• Partiell differentialekvation :
  • Slutlig skillnadsmetod
  • Crank – Nicolson -metod för diffusionsekvationer
  • Lax – Wendroff för vågekvationer
• Verlet integration ( fransk pronunciation: [vɛʁlɛ] ): integrera Newtons rörelseekvationer

Elementära och speciella funktioner

• Beräkning av π :
  • Borweins algoritm : en algoritm för att beräkna värdet på 1/π
  • Gauss – Legendre -algoritm: beräknar siffrorna i pi
  • Chudnovsky -algoritm : En snabb metod för att beräkna siffrorna i π
  • Bailey – Borwein – Plouffe -formel : (BBP -formel) en tappalgoritm för beräkning av den n: e binära siffran för π
• Delningsalgoritmer : för beräkning av kvot och/eller resten av två tal
  • Lång division
  • Återställa divisionen
  • Icke-återställande division
  • SRT -division
  • Newton – Raphson division : använder Newtons metod för att hitta det ömsesidiga av D och multiplicera det ömsesidiga med N för att hitta den slutliga kvoten Q.
  • Goldschmidt division
• Hyperboliska och trigonometriska funktioner:
  • BKM -algoritm : beräknar elementära funktioner med hjälp av en tabell med logaritmer
  • CORDIC : beräknar hyperboliska och trigonometriska funktioner med hjälp av en tabell med arktangenter
• Exponentiering:
  • Add-chain exponentiering : exponentiering med positiva heltalskrafter som kräver ett minimalt antal multiplikationer
  • Exponentiering genom kvadrering : en algoritm som används för snabb beräkning av ett heltal med ett heltal
• Montgomery -reduktion : en algoritm som gör att modulär aritmetik kan utföras effektivt när modulen är stor
• Multiplikationsalgoritmer : snabb multiplikation av två tal
  • Booths multiplikationsalgoritm : en multiplikationsalgoritm som multiplicerar två signerade binära tal i tvås komplementnotation
  • Ferrers algoritm : en heltalsmultiplikationsalgoritm för mycket stora tal som har en mycket låg asymptotisk komplexitet
  • Karatsuba -algoritm : ett effektivt förfarande för att multiplicera stora antal
  • Schönhage – Strassen -algoritm : en asymptotiskt snabb multiplikationsalgoritm för stora heltal
  • Toom – Cook multiplikation : (Toom3) en multiplikationsalgoritm för stora heltal
• Multiplikativ invers algoritm : för beräkning av ett tal multiplikativ invers (ömsesidig).
  • Newtons metod
• Avrundningsfunktioner : de klassiska sätten att avrunda siffror
• Spigot -algoritm : Ett sätt att beräkna värdet på en matematisk konstant utan att veta föregående siffror
• Kvadrat och n: a roten av ett tal:
  • Alpha max plus beta min algoritm : en approximation av kvadratroten för summan av två kvadrater
  • Metoder för att beräkna kvadratrötter
  • n : te roten algoritm
  • Skiftande n-rot-algoritm : siffra för siffra rotextraktion
• Summering:
  • Binär delning : en dela och erövra teknik som påskyndar den numeriska utvärderingen av många typer av serier med rationella termer
  • Kahan summeringsalgoritm : en mer exakt metod för att summera flytande tal
• Obegränsad algoritm

Geometrisk

• Filtrerad bakprojektion : beräknar effektivt den inversa 2-dimensionella Radon-transformen .
• Level set method (LSM): en numerisk teknik för att spåra gränssnitt och former

Interpolering och extrapolering

• Birkhoff -interpolering : en förlängning av polynominterpolering
• Kubisk interpolation
• Eremitinterpolering
• Lagrange interpolation : interpolation med hjälp av Lagrange polynom
• Linjär interpolering : en metod för kurvpassning med hjälp av linjära polynom
• Monoton kubisk interpolering : en variant av kubisk interpolering som bevarar monotoniciteten hos den datauppsättning som interpoleras.
• Multivariat interpolation
  • Bikubisk interpolation , en generalisering av kubisk interpolation till två dimensioner
  • Bilinjär interpolation : en förlängning av linjär interpolation för interpoleringsfunktioner av två variabler på ett vanligt rutnät
  • Lanczos resampling ("Lanzosh"): en multivariat interpoleringsmetod som används för att beräkna nya värden för eventuellt digitalt samplade data
  • Närmaste granne interpolering
  • Trikubisk interpolation , en generalisering av kubisk interpolation till tre dimensioner
• Pareto -interpolering : en metod för att uppskatta median och andra egenskaper hos en befolkning som följer en Pareto -fördelning .
• Polynomisk interpolation
  • Nevilles algoritm
• Spline interpolation : Minskar fel med Runges fenomen .
  • De Boor-algoritmen : B-splines
  • De Casteljaus algoritm : Bézier -kurvor
• Trigonometrisk interpolation

Linjär algebra

• Eigenvalue -algoritmer
  • Arnoldi iteration
  • Omvänd iteration
  • Jacobi metod
  • Lanczos iteration
  • Power iteration
  • QR -algoritm
  • Rayleigh -kvotering
• Gram – Schmidt -processen : ortogonaliserar en uppsättning vektorer
• Matrismultiplikationsalgoritmer
  • Cannons algoritm : en distribuerad algoritm för matrismultiplikation speciellt lämplig för datorer som läggs ut i ett N × N -nät
  • Coppersmith-Winograd algoritm : kvadrat matrismultiplikation
  • Freivalds algoritm : en randomiserad algoritm som används för att verifiera matrismultiplikation
  • Strassen -algoritm : snabbare matrismultiplikation

• Lösning av system för linjära ekvationer
  • Biconjugate -gradientmetod : löser system med linjära ekvationer
  • Konjugatgradient : en algoritm för den numeriska lösningen för vissa system av linjära ekvationer
  • Gaussisk eliminering
  • Eliminering av Gauss – Jordanien : löser system av linjära ekvationer
  • Gauss -Seidel -metod : löser system av linjära ekvationer iterativt
  • Levinson rekursion : löser ekvation som involverar en Toeplitz -matris
  • Stones metod : även känd som det starkt implicita förfarandet eller SIP, är en algoritm för att lösa ett gles linjärt ekvationssystem
  • Successiv överavslappning (SOR): metod som används för att påskynda konvergensen mellan Gauss-Seidel-metoden
  • Tridiagonal matrisalgoritm (Thomas algoritm): löser system med tridiagonal ekvationer
• Gles matris algoritmer
  • Cuthill – McKee -algoritm : minska bandbredden för en symmetrisk gles matris
  • Minsta gradalgoritm : permutera raderna och kolumnerna i en symmetrisk gles matris innan du använder Cholesky -sönderdelningen
  • Symbolisk Cholesky -sönderdelning : Effektivt sätt att lagra gles matris

Monte Carlo

• Gibbs -provtagning : genererar en sekvens av prover från den gemensamma sannolikhetsfördelningen av två eller flera slumpmässiga variabler
• Hybrid Monte Carlo : genererar en sekvens av prover med Hamiltonian vägd Markov kedja Monte Carlo , från en sannolikhetsfördelning som är svår att prova direkt.
• Metropolis – Hastings algoritm : används för att generera en sekvens av prover från sannolikhetsfördelningen av en eller flera variabler
• Wang och Landau algoritm : en förlängning av Metropolis-Hastings algoritm sampling

Numerisk integration

• MISER -algoritm : Monte Carlo -simulering, numerisk integration

Rotfynd

• Bisektion metod
• Falsk positionsmetod : approximerar rötterna i en funktion
• ITP -metod : minmax optimal och superlinär konvergens samtidigt
• Newtons metod : hittar nollor av funktioner med kalkyl
• Halleys metod : använder första och andra derivat
• Sekant metod : 2- punkts , ensidig
• Falsk positionsmetod och Illinois-metod: 2-punkts, parentes
• Ridders metod : 3-punkts, exponentiell skalning
• Mullers metod : 3-punkts, kvadratisk interpolation

Optimeringsalgoritmer

• Beskärning av alfa -beta : sök för att minska antalet noder i minimax -algoritmen
• Gren och bunden
• Bruss algoritm : se oddsalgoritm
• Kedjematrismultiplikation
• Kombinatorisk optimering : optimeringsproblem där uppsättningen genomförbara lösningar är diskret
  • Greedy randomized adaptive search procedure (GRASP): successiva konstruktioner av en girig randomiserad lösning och efterföljande iterativa förbättringar av den genom en lokal sökning
  • Ungersk metod : en kombinatorisk optimeringsalgoritm som löser tilldelningsproblemet i polynomtid
• Begränsning av tillfredsställelse
  • Allmänna algoritmer för begränsningstillfredsställelse
    • AC-3-algoritm
    • Skillnadskartalgoritm
    • Min konflikter algoritm
  • Chaff -algoritm : en algoritm för att lösa instanser av det booleska tillfredsställelsesproblemet
  • Davis – Putnam-algoritm : kontrollera giltigheten av en första ordningens logiska formel
  • Davis – Putnam – Logemann – Loveland-algoritm (DPLL): en algoritm för att avgöra om propositionell logikformel är tillfredsställande i konjunktiv normalform , dvs för att lösa CNF-SAT- problemet
  • Exakt täcka problem
    • Algoritm X : en icke -bestämd algoritm
    • Danslänkar : en effektiv implementering av algoritm X
• Cross-entropy-metod : en allmän Monte Carlo-strategi för kombinatorisk och kontinuerlig multi-extremal optimering och viktprovtagning
• Differentialutveckling
• Dynamisk programmering : problem som uppvisar egenskaperna hos överlappande delproblem och optimal understruktur
• Ellipsoidmetod : är en algoritm för att lösa konvexa optimeringsproblem
• Evolutionär beräkning : optimering inspirerad av biologiska evolutionära mekanismer
  • Evolutionstrategi
  • Programmering av genuttryck
  • Genetiska algoritmer
    • Fitness proportionellt urval- även känt som val av roulettehjul
    • Stokastisk universell provtagning
    • Val av stympning
    • Turneringsval
  • Memetisk algoritm
  • Svärm intelligens
    • Optimering av myrkolonin
    • Binalgoritm : en sökalgoritm som efterliknar födosökningsbeteendet hos svärmar av honungsbin
    • Partikelsvärm
• Frank-Wolfe algoritm : en iterativ första ordnings optimeringsalgoritm för begränsad konvex optimering
• Golden-section search : en algoritm för att hitta maximalt för en verklig funktion
• Gradient nedstigning
• Grid Search
• Harmony search (HS): en metaheuristisk algoritm som efterliknar musikerns improvisationsprocess
• Inre punktmetod
• Linjär programmering
  • Bensons algoritm : en algoritm för att lösa problem med linjär vektoroptimering
  • Dantzig – Wolfe sönderdelning : en algoritm för att lösa linjära programmeringsproblem med speciell struktur
  • Försenad kolumngenerering
  • Integer linjär programmering : lösa linjära programmeringsproblem där några eller alla okända är begränsade till heltalsvärden
    • Grena och skär
    • Skärplan-metod
  • Karmarkars algoritm : Den första rimligt effektiva algoritmen som löser det linjära programmeringsproblemet i polynomtid .
  • Simplex algoritm : En algoritm för att lösa linjära programmeringsproblem
• Linjesökning
• Lokal sökning : en meteurist för att lösa beräkningsmässigt hårda optimeringsproblem
  • Slumpmässigt omstart av bergsklättring
  • Tabu -sökning
• Minimax används i spelprogrammering
• Närmaste grannsökning (NNS): hitta närmaste punkter i ett metriskt utrymme
  • Best Bin First : hitta en ungefärlig lösning på det närmaste grannens sökproblem i mycket högdimensionella utrymmen
• Newtons metod för optimering
• Olinjär optimering
  • BFGS metod : En icke-linjär optimering algoritm
  • Gauss – Newton -algoritm : En algoritm för att lösa problem med icke -linjära minst kvadrater .
  • Levenberg – Marquardt -algoritm : En algoritm för att lösa olinjära problem med minst kvadrat .
  • Nelder-Mead metod (nedför simplexmetoden): En icke-linjär optimering algoritm
• Oddsalgoritm (Bruss -algoritm): Hittar den optimala strategin för att förutsäga en sista specifik händelse i en slumpmässig sekvenshändelse
• Slumpmässig sökning
• Simulerad glödgning
• Stokastisk tunnel
• Delmängdssummaalgoritm

Beräkningsvetenskap

Astronomi

• Doomsday -algoritm : veckodag
• Zellers kongruens är en algoritm för att beräkna veckodagen för varje julianskt eller gregorianskt kalenderdatum
• olika påskalgoritmer används för att beräkna påskdagen

Bioinformatik

• Basic Local Alignment Search Tool, även känt som BLAST: en algoritm för att jämföra primär biologisk sekvensinformation
• Kabsch -algoritm : beräkna den optimala inriktningen av två uppsättningar punkter för att beräkna rotmedelskvadratavvikelsen mellan två proteinstrukturer.
• Velvet : en uppsättning algoritmer som manipulerar de Bruijn -grafer för genomisk sekvensmontering
• Sortering efter signerade reverseringar : en algoritm för att förstå genomisk utveckling.
• Maximal parsimon (fylogenetik) : en algoritm för att hitta det enklaste fylogenetiska trädet för att förklara en given teckenmatris.
• UPGMA : en distansbaserad fylogenetisk trädbyggnadsalgoritm.

Geovetenskap

• Vincentys formler : en snabb algoritm för att beräkna avståndet mellan två latitud/longitudpunkter på en ellipsoid
• Geohash : en offentlig domänalgoritm som kodar ett decimal latitud/longitudpar som en hashsträng

Lingvistik

• Lesk -algoritm : ordförnimmelsdisambiguering
• Stammalgoritm : en metod för att reducera ord till deras stam, bas eller rotform
• Sukhotins algoritm : en statistisk klassificeringsalgoritm för att klassificera tecken i en text som vokaler eller konsonanter

Medicin

• ESC -algoritm för diagnos av hjärtsvikt
• Bemanningskriterier för irritabelt tarmsyndrom
• Lungemboli diagnostiska algoritmer
• Texas medicineringsalgoritmprojekt

Fysik

• Begränsningsalgoritm : en klass av algoritmer för att tillfredsställa begränsningar för kroppar som lyder Newtons rörelseekvationer
• Demonalgoritm : en Monte Carlo -metod för att effektivt sampla medlemmar i ett mikrokanoniskt ensemble med en given energi
• Featherstones algoritm : beräknar effekterna av krafter som appliceras på en struktur av leder och länkar
• Marktillstånds -approximation
  • Variationsmetod
    • Ritz -metoden
• n -kroppsproblem
  • Barnes – Hut-simulering : Löser n-kroppsproblemet på ett ungefärligt sätt som har ordningen O ( n log n ) istället för O ( n ² ) som i en direktsummesimulering.
  • Snabb multipolmetod (FMM): påskyndar beräkningen av långsträckta krafter
• Rainflow-räkningsalgoritm : Minskar en komplex spänning historia till en räkning av elementära stressåterför för användning i utmattningsanalys
• Sopa och beskära : en bredfasalgoritm som används vid kollisionsdetektering för att begränsa antalet par fasta ämnen som måste kontrolleras för kollision
• VEGAS -algoritm : en metod för att minska fel i Monte Carlo -simuleringar
• Glauber -dynamik : en metod för att simulera Ising -modellen på en dator

Statistik

• Algoritmer för att beräkna varians : undvika instabilitet och numeriskt överflöd
• Ungefärlig räknaralgoritm : Gör det möjligt att räkna ett stort antal händelser i ett litet register
• Bayesisk statistik
  • Kapslad samplingsalgoritm : en beräkningsmetod för problemet med att jämföra modeller i bayesisk statistik
• Klusteringsalgoritmer
  • Genomsnittlig kopplingsgruppering : en enkel agglomerativ klusteralgoritm
  • Canopy clustering algoritm : en oövervakad pre-clustering algoritm relaterad till K-medel algoritmen
  • Koppling av fullständig koppling : en enkel agglomerativ klusteralgoritm
  • DBSCAN : en densitetsbaserad klusteralgoritm
  • Förväntning-maximering algoritm
  • Fuzzy clustering : en klass av klusteralgoritmer där varje punkt har en viss grad av tillhörighet till kluster
    • Fuzzy c-betyder
    • FLAME clustering (Fuzzy clustering by Local Approximation of MEmberships): definiera kluster i de täta delarna av en datamängd och utför klustilldelning uteslutande baserat på grannskapsrelationerna mellan objekt
  • KHOPCA-klusteralgoritm : en lokal klusteralgoritm som producerar hierarkiska multi-hop-kluster i statiska och mobila miljöer.
  • k-betyder klustering : klusterobjekt baserade på attribut i partitioner
  • k-betyder ++ : en variant av detta, med hjälp av modifierade slumpmässiga frön
  • k-medoids : liknar k-medel, men väljer datapunkter eller medoids som centra
  • Linde – Buzo – Gray -algoritm : en vektorkvantiseringsalgoritm för att härleda en bra kodbok
  • Lloyds algoritm (Voronoi iteration eller avslappning): gruppdatapunkter i ett visst antal kategorier, en populär algoritm för k-medelklustering
  • OPTIK : en densitetsbaserad klusteralgoritm med en visuell utvärderingsmetod
  • Koppling med en länk : en enkel agglomerativ klusteralgoritm
  • SUBCLU : en klusteringsalgoritm för delrum
  • Wards metod : en agglomerativ klusteralgoritm, utökad till mer allmänna Lance – Williams -algoritmer
  • WACA-klusteralgoritm : en lokal klusteralgoritm med potentiellt multi-hop-strukturer; för dynamiska nätverk
• Uppskattningsteori
  • Förväntningsmaximeringsalgoritm En klass av relaterade algoritmer för att hitta maximala sannolikhetsuppskattningar av parametrar i probabilistiska modeller
    • Ordered subset expectation maximization (OSEM): används vid medicinsk avbildning för positronemissionstomografi , en-fotonemissionstomografi och röntgenberäknad tomografi.
  • Oddsalgoritm (Bruss -algoritm) Optimal sökning online efter distinkt värde i sekventiell slumpmässig inmatning
  • Kalman -filter : uppskatta tillståndet för ett linjärt dynamiskt system från en serie bullriga mätningar
• Falsk närmaste granne algoritm (FNN) uppskattar fraktaldimension
• Dold Markov -modell
  • Baum – Welch -algoritm: beräknar maximala sannolikhetsuppskattningar och uppskattningar i bakre läge för parametrarna för en dold Markov -modell
  • Framåt-bakåt-algoritm : en dynamisk programmeringsalgoritm för att beräkna sannolikheten för en viss observationssekvens
  • Viterbi -algoritm : hitta den mest troliga sekvensen av dolda tillstånd i en dold Markov -modell
• Delvis minsta kvadraters regression : hittar en linjär modell som beskriver några förutsagda variabler i termer av andra observerbara variabler
• Köteori
  • Buzens algoritm : en algoritm för att beräkna normaliseringskonstanten G (K) i Gordon – Newell -satsen
• RANSAC (en förkortning för "RANdom SAmple Consensus"): en iterativ metod för att uppskatta parametrar för en matematisk modell från en uppsättning observerade data som innehåller outliers
• Poängalgoritm : är en form av Newtons metod som används för att lösa maximala sannolikhetsekvationer numeriskt
• Yamartino -metod : beräkna en approximation till standardavvikelsen σθ för vindriktningen θ under en enda passage genom inkommande data
• Ziggurat-algoritm : genererar slumptal från en ojämn fördelning

Datavetenskap

Datorarkitektur

• Tomasulo-algoritm : tillåter sekventiella instruktioner som normalt skulle stoppas på grund av vissa beroenden att köra icke-sekventiellt

Datorgrafik

• Klippning
  • Linjeklippning
    • Cohen – Sutherland
    • Cyrus – Beck
    • Snabbklippning
    • Liang – Barsky
    • Nicholl – Lee – Nicholl
  • Polygonklippning
    • Sutherland – Hodgman
    • Vatti
    • Weiler – Atherton
• Konturlinjer och Isosurfaces
  • Marschbitar : extrahera ett polygonalt nät av en isosyta från ett tredimensionellt skalärfält (ibland kallat voxel)
  • Marschrutor : genererar konturlinjer för ett tvådimensionellt skalfält
  • Marscheringstetraeder : ett alternativ till marscherande kuber
• Discrete Greens sats : är en algoritm för att beräkna dubbelintegral över en generaliserad rektangulär domän i konstant tid. Det är en naturlig förlängning till den summerade tabellalgoritmen
• Flood fill : fyller en ansluten region i en flerdimensionell array med en specificerad symbol
• Globala belysningsalgoritmer : Anser direkt belysning och reflektion från andra objekt.
  • Omgivande ocklusion
  • Strålspårning
  • Konspårning
  • Bildbaserad belysning
  • Metropolis lätt transport
  • Sök spårning
  • Fotonkartläggning
  • Radiositet
  • Strålspårning
• Avlägsnande av dold yta eller visuell ytbestämning
  • Newells algoritm : eliminera polygoncykler i den djupsortering som krävs vid borttagning av dold yta
  • Målarens algoritm : detekterar synliga delar av ett tredimensionellt landskap
  • Skanningsvisning : konstruerar en bild genom att flytta en tänkt linje över bilden
  • Warnock -algoritm
• Radritning : grafisk algoritm för att approximera ett linjesegment på diskreta grafiska medier.
  • Bresenhams linjealgoritm : plottar punkter i en tvådimensionell array för att bilda en rak linje mellan 2 angivna punkter (använder beslutsvariabler)
  • DDA-linjealgoritm : plottar punkter i en tvådimensionell array för att bilda en rak linje mellan 2 specificerade punkter (använder flytande matematik)
  • Xiaolin Wus linjealgoritm : algoritm för radialialisering.
• Mittpunktscirkelalgoritm : en algoritm som används för att bestämma de punkter som behövs för att rita en cirkel
• Ramer – Douglas – Peucker -algoritm : Med tanke på en ”kurva” som består av linjesegment för att hitta en kurva som inte är så olik men som har färre punkter
• Skuggning
  • Gouraud -skuggning : en algoritm för att simulera olika effekter av ljus och färg över ytan på ett objekt i 3D -datorgrafik
  • Phong-skuggning : en algoritm för att interpolera ytnormala vektorer för ytskugga i 3D-datorgrafik
• Slerp (sfärisk linjär interpolation): quaternion interpolation i syfte att animera 3D -rotation
• Summed area table (även känd som en integrerad bild): en algoritm för att beräkna summan av värden i en rektangulär delmängd av ett rutnät i konstant tid

Kryptografi

• Asymmetrisk (offentlig nyckel) kryptering :
  • ElGamal
  • Elliptisk kurva kryptografi
  • MAE1
  • NTRUEncrypt
  • RSA
• Digitala signaturer (asymmetrisk autentisering):
  • DSA och dess varianter:
    • ECDSA och Deterministic ECDSA
    • EdDSA (Ed25519)
  • RSA
• Kryptografiska hashfunktioner (se även avsnittet om meddelandeautentiseringskoder):
  • BLAKE
  • MD5 - Observera att det nu finns en metod för att generera kollisioner för MD5
  • RIPEMD-160
  • SHA-1- Observera att det nu finns en metod för att generera kollisioner för SHA-1
  • SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512)
  • SHA-3 (SHA3-224, SHA3-256, SHA3-384, SHA3-512, SHAKE128, SHAKE256)
  • Tiger (TTH), som vanligtvis används i tigerhashar
  • WHIRLPOOL
• Kryptografiskt säkra pseudo-slumpmässiga talgeneratorer
  • Blum Blum Shub - baserat på faktoriseringens hårdhet
  • Fortuna , avsedd som en förbättring av Yarrow -algoritmen
  • Linjärt feedback-skiftregister (notera: många LFSR-baserade algoritmer är svaga eller har brutits)
  • Yarrow algoritm
• Nyckelbyte
  • Nyckelbyte mellan Diffie - Hellman
  • Elliptisk kurva Diffie – Hellman (ECDH)
• Nyckelavledningsfunktioner , som ofta används för lösenordshashning och nyckeltöjning
  • bcrypt
  • PBKDF2
  • kryptera
  • Argon2
• Meddelandeautentiseringskoder (symmetriska autentiseringsalgoritmer, som tar en nyckel som parameter):
  • HMAC : autentisering med nyckel-hash-meddelande
  • Poly1305
  • SipHash
• Hemlig delning , hemlig splittring, nyckelsplitning, M av N -algoritmer
  • Blakeys schema
  • Shamirs schema
• Symmetrisk (hemlig nyckel) kryptering :
  • Advanced Encryption Standard (AES), vinnare av NIST -tävling, även känd som Rijndael
  • blåsfisk
  • Tvåfiskar
  • Trefisk
  • Data Encryption Standard (DES), ibland DE Algoritm, vinnare av NBS urvalstävling, ersatt av AES för de flesta ändamål
  • ANING
  • RC4 (chiffer)
  • Tiny Encryption Algorithm (TEA)
  • Salsa20 , och dess uppdaterade variant ChaCha20
• Postkvantkryptografi
• Arbetsgodkända algoritmer

Digital logik

• Boolsk minimering
  • Quine – McCluskey -algoritm : Kallas även som QM -algoritm, programmerbar metod för att förenkla de booleska ekvationerna.
  • Petricks metod : En annan algoritm för boolsk förenkling.
  • Espresso heuristisk logisk minimizer : Snabb algoritm för boolsk funktionsminimering.

Maskininlärning och statistisk klassificering

• ALOPEX : en korrelationsbaserad algoritm för maskininlärning
• Föreningsregelinlärning : upptäck intressanta relationer mellan variabler, som används vid datamining
  • Apriori algoritm
  • Eclat -algoritm
  • FP-tillväxtalgoritm
  • En-attributregel
  • Nollattributregel
• Boosting (meta-algoritm) : Använd många svaga elever för att öka effektiviteten
  • AdaBoost : adaptiv boost
  • BrownBoost : en förstärkande algoritm som kan vara robust för bullriga datamängder
  • LogitBoost : logistisk regression öka
  • LPBoost : förstärkning av linjär programmering
• Bootstrap aggregating (bagging): teknik för att förbättra stabilitet och klassificeringsnoggrannhet
• Datorsyn
  • Grabcut baserat på grafsnitt
• Beslutsträd
  • C4.5 -algoritm : en förlängning till ID3
  • ID3 -algoritm (Iterative Dichotomiser 3): använd heuristik för att generera små beslutsträd
• Clustering : en klass av oövervakade inlärningsalgoritmer för gruppering och bucketing -relaterad inmatningsvektor.
  • k-närmaste grannar (k-NN): en metod för att klassificera objekt baserat på närmaste träningsexempel i funktionsutrymmet
• Linde – Buzo – Gray -algoritm : en vektorkvantiseringsalgoritm som används för att härleda en bra kodbok
• Lokalitetskänslig hashing (LSH): en metod för att utföra probabilistisk dimensionreduktion av högdimensionell data
• Neuralt nätverk
  • Backpropagation : En övervakad inlärningsmetod som kräver en lärare som känner till eller kan beräkna önskad utmatning för en given input
  • Hopfield net : ett återkommande neuralt nätverk där alla anslutningar är symmetriska
  • Perceptron : den enklaste typen av feedforward neuralt nätverk: en linjär klassificerare .
  • Pulskopplade neurala nätverk (PCNN): Neurala modeller som föreslås genom att modellera en katt visuell cortex och utvecklad för högpresterande biomimetisk bildbehandling.
  • Radialbasfunktionsnätverk : ett artificiellt neuralt nätverk som använder radiella basfunktioner som aktiveringsfunktioner
  • Självorganiserande karta : ett oövervakat nätverk som ger en lågdimensionell representation av inmatningsutrymmet för träningsproverna
• Slumpmässig skog : klassificera med många beslutsträd
• Förstärkningsinlärning :
  • Q-inlärning : lär sig en åtgärdsvärdesfunktion som ger den förväntade nyttan av att vidta en given åtgärd i ett givet tillstånd och därefter följa en fast policy
  • State-Action-Reward-State-Action (Sarsa): lära sig ett Markov beslutsprocess policy
  • Temporal skillnadsinlärning
• Relevans-vektor maskin (RVM): liknar SVM, men ger sannolikhetsklassificering
• Övervakad inlärning : Inlärning genom exempel (märkt datamängd uppdelad i träningsuppsättning och testuppsättning)
• Support-Vector Machine (SVM): en uppsättning metoder som delar upp flerdimensionella data genom att hitta ett delande hyperplan med maximal marginal mellan de två uppsättningarna
  • Strukturerad SVM : möjliggör utbildning av en klassificerare för allmänna strukturerade utskriftsetiketter.
• Winnow-algoritm : relaterad till perceptronen, men använder ett multiplikativt system för viktuppdatering

Programmeringsspråkteori

• C3-linearisering : en algoritm som främst används för att erhålla en konsekvent linearisering av en multipel arvshierarki i objektorienterad programmering
• Chaitins algoritm : en algoritm för tilldelning av registerfärger från botten upp och uppåt som använder kostnad/grad som sin spillmätning
• Inferensalgoritm av typen Hindley – Milner
• Rete algoritm : en effektiv mönstermatchning algoritm för att genomföra produktionsregelsystemen
• Sethi-Ullman-algoritm : genererar optimal kod för aritmetiska uttryck

Analys

• CYK-algoritm : En O (n ³ ) algoritm för att analysera kontextfria grammatiker i Chomsky normal form
• Earley parser : En annan O (n ³ ) algoritm för analys av kontextfri grammatik
• GLR-parser : En algoritm för analys av kontextfri grammatik av Masaru Tomita . Den är inställd för deterministiska grammatiker, på vilken den utför nästan linjär tid och O (n ³ ) i värsta fall.
• Inside-outside algoritm : En O (n ³ ) algoritm för att uppskatta produktionssannolikheter i probabilistiska kontextfria grammatiker
• LL-parser : En relativt enkel linjär tidsanalysalgoritm för en begränsad klass av kontextfria grammatiker
• LR-parser : En mer komplex linjär tidsanalysalgoritm för en större klass av kontextfria grammatiker . Varianter:
  • Canonical LR -parser
  • LALR (blick framåt LR) parser
  • Operatörens företräde analys
  • SLR -analys (enkel LR)
  • Enkel prioritetsparser
• Packrat-parser : En linjär tidsanalysalgoritm som stöder vissa kontextfria grammatiker och analyserande uttrycksgrammatik
• Rekursiv nedstigningsparser : En parser uppifrån och ned lämplig för LL ( k ) grammatik
• Shunting-yard algoritm : konvertera ett infix-notation matematiskt uttryck till postfix
• Pratt parser
• Lexikal analys

Kvantalgoritmer

• Deutsch – Jozsa -algoritm : balanskriterium för booleska funktioner
• Grovers algoritm : ger kvadratisk snabbhet för många sökproblem
• Shors algoritm : tillhandahåller exponentiell hastighet (i förhållande till för närvarande kända icke-kvantalgoritmer) för factoring av ett tal
• Simons algoritm : ger en bevisligen exponentiell hastighet (i förhållande till en icke-kvantalgoritm) för ett problem med black-box

Beräkningsteori och automat

• Hopcrofts algoritm , Moores algoritm och Brzozowskis algoritm : algoritmer för att minimera antalet tillstånd i en deterministisk ändlig automat
• Powerset -konstruktion : Algoritm för att konvertera icke -bestämd automat till deterministisk automat .
• Tarski – Kuratowski-algoritm : en icke-deterministisk algoritm som ger en övre gräns för formelernas komplexitet i den aritmetiska hierarkin och den analytiska hierarkin

Informationsteori och signalbehandling

Kodningsteori

Feldetektering och korrigering

• BCH -koder
  • Berlekamp – Massey -algoritm
  • Peterson – Gorenstein – Zierler -algoritm
  • Reed – Solomon felkorrigering
• BCJR -algoritm : avkodning av felkorrigerande koder definierade på spaljéer (huvudsakligen konvolutionskoder)
• Vidarebefordra felkorrigering
• Grå kod
• Hammarkoder
  • Hammning (7,4) : en Hamming -kod som kodar 4 bitar data till 7 bitar genom att lägga till 3 paritetsbitar
  • Hammningsavstånd : summan av positioner som är olika
  • Hammningsvikt (befolkningsantal): hitta antalet 1 bitar i ett binärt ord
• Redundanskontroller
  • Adler-32
  • Cyklisk redundanskontroll
  • Damm -algoritm
  • Fletchers kontrollsumma
  • Longitudinal redundanskontroll (LRC)
  • Luhn -algoritm : en metod för att validera identifieringsnummer
  • Luhn mod N algoritm : förlängning av Luhn till icke-numeriska tecken
  • Paritet : enkel/snabb feldetekteringsteknik
  • Verhoeff algoritm

Förlustfria komprimeringsalgoritmer

• Burrows – Wheeler -transform : förbearbetning användbar för att förbättra förlustfri komprimering
• Kontext träd viktning
• Delta -kodning : hjälp för komprimering av data där sekventiell data ofta förekommer
• Dynamisk Markov -komprimering : Komprimering med prediktiv aritmetisk kodning
• Ordbokskodare
  • Byte -par -kodning (BPE)
  • Töm ut
  • Lempel – Ziv
    • LZ77 och LZ78
    • Lempel – Ziv Jeff Bonwick (LZJB)
    • Kedjealgoritm för Lempel – Ziv – Markov (LZMA)
    • Lempel – Ziv – Oberhumer (LZO): hastighetsinriktad
    • Lempel – Ziv – Stac (LZS)
    • Lempel – Ziv – Storer – Szymanski (LZSS)
    • Lempel – Ziv – Welch (LZW)
    • LZWL : stavelsesbaserad variant
    • LZX
    • Lempel – Ziv Ross Williams (LZRW)
• Entropykodning : kodningsschema som tilldelar koder till symboler för att matcha kodlängder med symbolernas sannolikheter
  • Aritmetisk kodning : avancerad entropi kodning
    • Områdeskodning : samma som aritmetisk kodning , men sett på ett lite annorlunda sätt
  • Huffman -kodning : enkel förlustfri komprimering med fördel av relativa teckenfrekvenser
    • Adaptiv Huffman -kodning : adaptiv kodningsteknik baserad på Huffman -kodning
    • Paket-sammanfogningsalgoritm : Optimerar Huffman-kodning med förbehåll för en längdbegränsning på kodsträngar
  • Shannon – Fano kodning
  • Shannon – Fano – Elias kodning : föregångare till aritmetisk kodning
• Entropikodning med kända entropikarakteristika
  • Golombkodning : form av entropikodning som är optimal för alfabet efter geometriska fördelningar
  • Riskodning : form av entropikodning som är optimal för alfabet efter geometriska fördelningar
  • Trunkerad binär kodning
  • Unary kodning : kod som representerar ett tal n med n en följt av en nolla
  • Universella koder : kodar positiva heltal till binära kodord
    • Elias delta , gamma och omega kodning
    • Exponential-Golomb kodning
    • Fibonacci -kodning
    • Levenshtein -kodning
• Fast Efficient & Lossless Image Compression System (FELICS): en förlustfri bildkomprimeringsalgoritm
• Inkrementell kodning : delta -kodning applicerad på strängsekvenser
• Prediction by partial matching (PPM): en adaptiv statistisk datakomprimeringsteknik baserad på kontextmodellering och förutsägelse
• Körningslängdskodning : förlustfri datakomprimering med fördelar av strängar med upprepade tecken
• SEQUITUR -algoritm : förlustfri komprimering genom inkrementell grammatikinferens på en sträng

Förlorade komprimeringsalgoritmer

• 3Dc : en förlorad datakomprimeringsalgoritm för vanliga kartor
• Ljud och tal komprimering
  • A-lag algoritm : standard anderingsalgoritm
  • Code-exciterad linjär prediktion (CELP): lågkomprimerad talkomprimering
  • Linjär prediktiv kodning (LPC): förlustaktig komprimering genom att representera spektralhöljet för en digital talsignal i komprimerad form
  • Mu-law algoritm : standard analog signalkomprimering eller companding algoritm
  • Warped Linear Predictive Coding (WLPC)
• Bildkomprimering
  • Block Truncation Coding (BTC): en typ av förlustfri bildkomprimeringsteknik för gråskala bilder
  • Inbäddad Zerotree Wavelet (EZW)
  • Snabba Cosine Transform -algoritmer (FCT -algoritmer): beräknar effektivt Discrete Cosine Transform (DCT) effektivt
  • Fraktalkomprimering : metod som används för att komprimera bilder med hjälp av fraktaler
  • Ange uppdelning i hierarkiska träd (SPIHT)
  • Wavelet -komprimering : form av datakomprimering väl lämpad för bildkomprimering (ibland även videokomprimering och ljudkomprimering)
• Transformkodning : typ av datakomprimering för "naturliga" data som ljudsignaler eller fotografiska bilder
• Videokomprimering
• Vektorkvantisering : teknik som ofta används vid förlust av datakomprimering

Digital signalbehandling

• Adaptiv-additiv algoritm (AA-algoritm): hitta den rumsliga frekvensfasen för en observerad vågkälla
• Diskret Fouriertransform : bestämmer frekvenserna i en (segment av a) signal
  • Bluesteins FFT -algoritm
  • Bruuns FFT -algoritm
  • Cooley – Tukey FFT -algoritm
  • Snabb Fourier -transform
  • Prime-factor FFT-algoritm
  • Raders FFT -algoritm
• Snabbviktningsalgoritm : en effektiv algoritm för detektering av ungefär periodiska händelser inom tidsseriedata
• Gerchberg – Saxton -algoritm : Fashämtningsalgoritm för optiska plan
• Goertzel -algoritm : identifiera en viss frekvenskomponent i en signal. Kan användas för avkodning av DTMF -siffror.
• Karplus-Strong strängsyntes : fysisk modelleringssyntes för att simulera ljudet av en hamrad eller plockad sträng eller vissa typer av slagverk

Bildbehandling

• Kontrastförbättring
  • Histogramutjämning : använd histogram för att förbättra bildkontrasten
  • Adaptiv histogramutjämning : histogramutjämning som anpassar sig till lokala kontrastförändringar
• Märkning av anslutna komponenter : hitta och märka olika områden
• Dithering och halvtoning
  • Fel spridning
  • Floyd – Steinberg dithering
  • Beställde dithering
  • Riemersma dithering
• Elser differens-kart-algoritm : en sökalgoritm för generella problem med tillfredsställelse. Ursprungligen användes för röntgen diffraktion mikroskopi
• Funktionsdetektering
  • Canny edge detector : upptäck ett brett spektrum av kanter i bilder
  • Generaliserad Hough -transform
  • Hough transform
  • Marr-Hildreth algoritm : en tidig kantdetekteringsalgoritm
  • SIFT (Scale-invariant feature transform): är en algoritm för att upptäcka och beskriva lokala funktioner i bilder.
  • SURF ( Speeded Up Robust Features ) : är en robust lokal funktionsdetektor, som först presenterades av Herbert Bay et al. 2006, som kan användas i datorvisionsuppgifter som objektigenkänning eller 3D -rekonstruktion. Det är delvis inspirerat av SIFT -deskriptorn. Standardversionen av SURF är flera gånger snabbare än SIFT och påstås av dess författare vara mer robust mot olika bildomvandlingar än SIFT.
• Richardson – Lucy deconvolution : algoritm för suddig bild
• Blind dekonvolution : algoritm för avbildning av bilder när punktspridningsfunktionen är okänd.
• Medianfiltrering
• Seam carving : innehållsmedveten bildändringsalgoritm
• Segmentering : dela upp en digital bild i två eller flera regioner
  • GrowCut -algoritm : en interaktiv segmenteringsalgoritm
  • Slumpmässig rollator -algoritm
  • Region växer
  • Vattendelstransformation : en klass av algoritmer baserade på vattendelarsanalogin

Mjukvaruutveckling

• Cache -algoritmer
• CHS -konvertering : konvertering mellan diskadresseringssystem
• Double dabble : Konvertera binära tal till BCD
• Hashfunktion : konvertera en stor, möjligen stor mängd data till en liten datum, vanligtvis ett enda heltal som kan fungera som ett index till en array
  • Fowler – Noll – Vo hash -funktion : snabb med låg kollisionshastighet
  • Pearson hashing : beräknar endast 8 bitars värde, optimerat för 8 bitars datorer
  • Zobrist hashing : används vid implementering av transponeringstabeller
• Unicode -samlingsalgoritm
• Xor swap -algoritm : byter värden för två variabler utan att använda en buffert

Databasalgoritmer

• Algoritmer för återhämtning och isolering som utnyttjar semantik (ARIES): återhämtning av transaktioner
• Gå med i algoritmer
  • Blockera kapslad slinga
  • Hash gå med
  • Nested loop join
  • Sort-Merge Join

Distribuerade systemalgoritmer

• Klocksynkronisering
  • Berkeley -algoritm
  • Cristians algoritm
  • Korsningsalgoritm
  • Marzullos algoritm
• Konsensus (datavetenskap) : enas om ett enda värde eller historia bland opålitliga processorer
  • Chandra – Toueg konsensusalgoritm
  • Paxos algoritm
  • Raft (datavetenskap)
• Upptäckt av processavslutning
  • Dijkstra-Scholten-algoritm
  • Huangs algoritm
• Lamport-beställning : en delvis ordning av händelser baserat på förhållandet som inträffade före
• Ledarval : en metod för dynamiskt val av en koordinator
  • Mobbningsalgoritm
• Ömsesidig uteslutning
  • Lamports distribuerade ömsesidiga uteslutningsalgoritm
  • Naimi-Trehels logg (n) Algoritm
  • Maekawas algoritm
  • Raymonds algoritm
  • Ricart – Agrawala algoritm
• Snapshot -algoritm : spela in ett konsekvent globalt tillstånd för ett asynkront system
  • Chandy – Lamport -algoritm
• Vector klockor : generera en partiell beställning av händelser i ett distribuerat system och upptäcka orsaks kränkningar

Minnesallokerings- och deallokationsalgoritmer

• Buddy memory allocation : Algoritm för att allokera minne så att fragmenteringen blir mindre.
• Sopor
  • Cheneys algoritm : En förbättring av Semi-space-samlaren
  • Generationssoplare : Snabba sophämtare som separerar minnet efter ålder
  • Mark-compact-algoritm : en kombination av mark-sweep-algoritmen och Cheneys kopieringsalgoritm
  • Markera och sopa
  • Halvrymtsamlare : En samlare för tidig kopiering
• Referensräkning

Nätverk

• Karn's algoritm : tar upp problemet med att få exakta uppskattningar av rundturstiden för meddelanden vid användning av TCP
• Luleå -algoritm : en teknik för effektiv lagring och sökning av internetdirigeringstabeller
• Trängsel i nätverket
  • Exponentiell backoff
  • Nagles algoritm : förbättra effektiviteten hos TCP/IP -nätverk genom att samla paket
  • Avkortad binär exponentiell backoff

Operativsystems algoritmer

• Bankirens algoritm : Algoritm som används för att undvika dödläge.
• Sidersättningsalgoritmer : Välj offersida under låga minnesförhållanden.
  • Adaptiv ersättningscache : bättre prestanda än LRU
  • Klocka med adaptiv ersättning (CAR): är en sidbytesalgoritm som har prestanda som är jämförbar med adaptiv ersättningscache

Processynkronisering

• Dekkers algoritm
• Lamports bageri -algoritm
• Petersons algoritm

Schemaläggning

• Tidigaste deadline första schemaläggning
• Schemaläggning för rättvis andel
• Minst långsam tidsplanering
• Lista schemaläggning
• Feedbackkö på flera nivåer
• Pris-monoton schemaläggning
• Round-robin schemaläggning
• Kortaste jobbet nästa
• Kortast återstående tid
• Toppnoder algoritm : resurskalenderhantering

I/O -schemaläggning

Schemaläggning av hårddiskar

• Hissalgoritm : Diskplaneringsalgoritm som fungerar som en hiss.
• Kortaste sökning först : Diskplaneringsalgoritm för att minska söktiden .

Se även

• Lista över datastrukturer
• Lista över maskininlärningsalgoritmer
• Lista över sökvägsalgoritmer
• Lista över algoritmens allmänna ämnen
• Lista över termer som rör algoritmer och datastrukturer
• Heuristisk

Referenser