Seznam algoritmů - List of algorithms

Následuje seznam algoritmů spolu s jednořádkovými popisy pro každý z nich.

Automatické plánování

Kombinatorické algoritmy

Obecné kombinatorické algoritmy

• Brentův algoritmus : najde cyklus v iteracích hodnot funkcí pomocí pouze dvou iterátorů
• Floydův algoritmus hledání cyklu : najde cyklus v iteracích hodnot funkcí
• Algoritmus Gale – Shapley : řeší problém stabilního manželství
• Generátory pseudonáhodných čísel (rovnoměrně rozmístěné - viz také Seznam generátorů pseudonáhodných čísel pro jiné PRNG s různým stupněm konvergence a různou statistickou kvalitou):
  • ACORN generátor
  • Blum Blum Shub
  • Zpožděný Fibonacciho generátor
  • Lineární kongruenční generátor
  • Mersenne Twister

Algoritmy grafů

• Algoritmus barvení : Algoritmus barvení grafu.
• Algoritmus Hopcroft – Karp : převeďte bipartitní graf na maximální shodnost
• Maďarský algoritmus : algoritmus pro nalezení dokonalé shody
• Prüferovo kódování : převod mezi označeným stromem a jeho Prüferovou sekvencí
• Tarjanův off-line algoritmus nejnižších společných předků : vypočítá nejnižší společné předky pro páry uzlů ve stromu
• Topologické řazení : vyhledá lineární pořadí uzlů (např. Úloh) na základě jejich závislostí.

Grafická kresba

• Algoritmy založené na síle (známé také jako silové algoritmy nebo pružinové algoritmy)
• Spektrální rozložení

Teorie sítě

• Analýza sítě
  • Analýza odkazů
    • Algoritmus Girvan – Newman : detekuje komunity ve složitých systémech
    • Analýza webových odkazů
      • Hledání témat vyvolané hypertextovým odkazem (HITS) (také známé jako centra a autority )
      • PageRank
      • TrustRank
• Tokové sítě
  • Dinicův algoritmus : je silně polynomický algoritmus pro výpočet maximálního toku v tokové síti .
  • Algoritmus Edmonds – Karp : implementace Ford – Fulkerson
  • Algoritmus Ford – Fulkerson : vypočítá maximální průtok v grafu
  • Kargerův algoritmus : metoda Monte Carlo pro výpočet minimálního řezu připojeného grafu
  • Algoritmus push – relabel : vypočítá maximální tok v grafu

Směrování pro grafy

• Edmondsův algoritmus (také známý jako Chu – Liu/Edmondsův algoritmus): najděte maximální nebo minimální větvení
• Euklidovský minimální překlenovací strom : algoritmy pro výpočet minimálního překlenovacího stromu množiny bodů v rovině
• Euklidovský problém s nejkratší cestou : najděte nejkratší cestu mezi dvěma body, která neprotíná žádnou překážku
• Problém s nejdelší cestou : najděte jednoduchou cestu maximální délky v daném grafu
• Minimální kostra
  • Borůvkův algoritmus
  • Kruskalův algoritmus
  • Primův algoritmus
  • Algoritmus zpětného mazání
• Neblokovací spínač s minimálním rozpětím řekněme pro telefonní ústřednu
• Problém s nejkratší cestou
  • Algoritmus Bellman – Ford : vypočítá nejkratší cesty ve váženém grafu (kde některé z okrajových vah mohou být záporné)
  • Algoritmus Dijkstry: vypočítá nejkratší cesty v grafu s nezápornými váhami hran
  • Algoritmus Floyd – Warshall : řeší problém nejkratší cesty všech párů ve váženém, směrovaném grafu
  • Algoritmus Johnsona : Algoritmus nejkratší cesty všech párů v řídkém váženém orientovaném grafu
• Problém tranzitivního uzavření : najděte tranzitivní uzavření daného binárního vztahu
• Problém obchodního cestujícího
  • Christofidesův algoritmus
  • Algoritmus nejbližšího souseda
• Warnsdorffovo pravidlo : Heuristická metoda pro řešení problému Rytířského turné .

Hledání v grafu

• A* : speciální případ best-first search, který ke zvýšení rychlosti používá heuristiku
• B* : algoritmus pro vyhledávání grafů nejlepší první, který najde cestu s nejnižšími náklady z daného počátečního uzlu do libovolného cílového uzlu (z jednoho nebo více možných cílů)
• Backtracking : upustí od dílčích řešení, pokud zjistí, že nevyhovují úplnému řešení
• Beam search : je heuristický vyhledávací algoritmus, který je optimalizací nejlepšího prvního vyhledávání a snižuje nároky na paměť.
• Hledání svazku paprsků : integruje zpětné vyhledávání s vyhledáváním paprsků
• Nejlepší první vyhledávání : prochází grafem v pořadí pravděpodobné důležitosti pomocí prioritní fronty
• Obousměrné vyhledávání : najděte nejkratší cestu z počátečního vrcholu do vrcholu cíle v nasměrovaném grafu
• Šířka prvního hledání : prochází grafem po úrovni
• Hledání hrubou silou : Vyčerpávající a spolehlivá metoda vyhledávání, ale výpočetně neefektivní v mnoha aplikacích.
• D* : inkrementální heuristický vyhledávací algoritmus
• Hledání do hloubky : prochází grafem větev po větvi
• Algoritmus Dijkstry : Zvláštní případ A*, pro který se nepoužívá žádná heuristická funkce
• General Problem Solver : klíčový algoritmus pro dokazování vět, který má fungovat jako univerzální stroj pro řešení problémů.
• Iterativní prohloubení hloubkového vyhledávání (IDDFS): strategie hledání ve stavovém prostoru
• Hledání bodu skoku : Optimalizace na A*, která může pomocí další heuristiky zkrátit dobu výpočtu o řád.
• Lexikografické vyhledávání do šířky (také známé jako Lex-BFS): lineární časový algoritmus pro uspořádání vrcholů grafu
• Hledání jednotných nákladů : stromové vyhledávání, které najde nejlevnější trasu, kde se náklady liší
• SSS* : prohledávání stavového prostoru procházející herním stromem nejlepším způsobem, který je podobný algoritmu vyhledávání A*
• F* : Speciální algoritmus pro sloučení dvou polí

Podpisy

• Kliky
  • Algoritmus Bron – Kerbosch : technika pro hledání maximálních klik v neorientovaném grafu
  • Algoritmus maximální kliky MaxCliqueDyn : najděte maximální kliku v neorientovaném grafu
• Silně propojené komponenty
  • Algoritmus silných komponent na bázi cesty
  • Kosarajuův algoritmus
  • Algoritmus silně propojených komponent Tarjana
• Problém izomorfismu podgrafu

Sekvenční algoritmy

Přibližná shoda sekvencí

• Algoritmus bitap : fuzzy algoritmus, který určuje, zda jsou řetězce přibližně stejné.
• Fonetické algoritmy
  • Daitch-Mokotoff Soundex : a Soundex zjemnění, který umožňuje sladění slovanské a germánské příjmení
  • Double Metaphone : vylepšení metaphonu
  • Přístup k hodnocení shody : fonetický algoritmus vyvinutý společností Western Airlines
  • Metaphone : algoritmus pro indexování slov podle jejich zvuku, když je vyslovován v angličtině
  • NYSIIS : fonetický algoritmus , vylepšený na Soundexu
  • Soundex : fonetický algoritmus pro indexování jmen podle zvuku, jak je vyslovováno v angličtině
• Metriky řetězců : vypočítá skóre podobnosti nebo odlišnosti (vzdálenosti) mezi dvěma páry textových řetězců
  • Vzdálenost Damerau – Levenshtein : vypočítá míru vzdálenosti mezi dvěma řetězci, zlepší vzdálenost Levenshtein
  • Kockový koeficient (také známý jako koeficient kostky): míra podobnosti související s Jaccardovým indexem
  • Hammingova vzdálenost : součet počtu pozic, které jsou různé
  • Jaro – Winklerova vzdálenost : je mírou podobnosti mezi dvěma řetězci
  • Levenshteinova vzdálenost úprav : vypočítá metriku pro rozdíl mezi dvěma sekvencemi
• Trigram search : hledá text, pokud není přesně známa syntaxe nebo pravopis cílového objektu

Algoritmy výběru

• Rychlý výběr
• Introselect

Sekvenční hledání

• Lineární vyhledávání : vyhledá položku v netříděné sekvenci
• Algoritmus výběru : najde k -tu největší položku v sekvenci
• Ternární vyhledávání : technika pro nalezení minima nebo maxima funkce, která se buď přísně zvyšuje a poté striktně klesá, nebo naopak
• Seřazené seznamy
  • Algoritmus binárního vyhledávání : vyhledá položku v seřazené sekvenci
  • Technika vyhledávání Fibonacci : prohledejte seřazenou sekvenci pomocí algoritmu rozděl a panuj, který zúží možná místa pomocí Fibonacciho čísel
  • Skokové vyhledávání (nebo blokové vyhledávání): lineární vyhledávání v menší podmnožině sekvence
  • Prediktivní vyhledávání : binární vyhledávání, které ovlivňuje velikost hledaného výrazu a vysoké a nízké hodnoty ve vyhledávání. Někdy se nazývá vyhledávání ve slovníku nebo interpolované vyhledávání.
  • Jednotné binární vyhledávání : optimalizace klasického algoritmu binárního vyhledávání

Sekvenční slučování

• Jednoduchý spojovací algoritmus
• Algoritmus sloučení k-way
• Union (sloučení, s prvky na výstupu se neopakují)

Sekvenční permutace

• Fisher -Yates shuffle (také známý jako Knuth shuffle): náhodně zamíchat konečnou sadu
• Algoritmus Schensted : z permutace vytvoří pár mladých tableaux
• Algoritmus Steinhaus – Johnson – Trotter (také známý jako algoritmus Johnson – Trotter): generuje permutace transponováním prvků
• Algoritmus generování permutace haldy : výměna prvků pro generování další permutace

Sekvenční kombinace

Sekvenční zarovnání

• Dynamické časové deformace : měří podobnost mezi dvěma sekvencemi, které se mohou lišit v čase nebo rychlosti
• Hirschbergův algoritmus : najde nejlevnější zarovnání sekvence mezi dvěma sekvencemi, měřeno jejich Levenshteinovou vzdáleností
• Algoritmus Needleman – Wunsch : najděte globální zarovnání mezi dvěma sekvencemi
• Algoritmus Smith – Waterman : vyhledejte zarovnání lokální sekvence

Sekvenční třídění

• Výměnné druhy
  • Řazení podle bublin : u každého páru indexů položky vyměňte, pokud jsou mimo provoz
  • Třídění koktejlových třepaček nebo obousměrné třídění bublin
  • Hřebenové řazení
  • Gnome sort
  • Zvláštní - dokonce i třídit
  • Rychlé řazení : rozdělte seznam na dva, přičemž všechny položky na prvním seznamu budou před všemi položkami na druhém seznamu .; potom seřaďte dva seznamy. Často způsob volby
• Humorné nebo neúčinné
  • Bogosort
  • Třídění loutek
• Hybridní
  • Flashsort
  • Introsort : začněte quicksortem a přepněte na heapsort, když hloubka rekurze překročí určitou úroveň
  • Timsort : adaptivní algoritmus odvozený ze sloučení a vložení. Používá se v Pythonu 2.3 a vyšším a Java SE 7.
• Vkládací druhy
  • Třídění vložení : určete, kam aktuální položka patří v seznamu seřazených, a vložte ji tam
  • Řazení knihovny
  • Třídění trpělivosti
  • Shell sort : pokus o vylepšení řazení vložení
  • Třídění stromů ( třídění binárních stromů): sestavte binární strom a poté jej procházejte a vytvořte seřazený seznam
  • Třídění cyklu : na místě s teoreticky optimálním počtem zápisů
• Sloučit druhy
  • Sloučit řazení : seřaďte samostatně první a druhou polovinu seznamu a poté sloučené seřazené seznamy
  • Zpomaluje
  • Strand sort
• Nesrovnatelné druhy
  • Třídění korálků
  • Kbelíkové řazení
  • Burstsort : Sestavte kompaktní, v mezipaměti efektivní burst trie a poté procházejte, abyste vytvořili tříděný výstup
  • Počítání
  • Druh holubí díry
  • Postman sort : varianta Bucket sort, která využívá výhod hierarchické struktury
  • Radixové řazení : třídí řetězce podle písmene
• Druhy výběru
  • Heapsort : převeďte seznam na hromadu, pokračujte v odstraňování největšího prvku z haldy a přidávejte jej na konec seznamu
  • Třídění výběru : vyberte nejmenší ze zbývajících prvků a přidejte jej na konec seřazeného seznamu
  • Smoothsort
• jiný
  • Bitonický třídič
  • Třídění palačinek
  • Třídění špaget
  • Topologické řazení
• Neznámá třída
  • Samplesort

Následky

• Kadaneův algoritmus : najde maximální dílčí pole libovolné velikosti
• Nejdelší společný problém se subsekvencí : Najděte nejdelší subsekvenci společnou všem sekvencím v sadě sekvencí
• Problém s nejdelší rostoucí subsekvencí: Najděte nejdelší rostoucí subsekvenci dané sekvence
• Nejkratší společný problém se supersekvencí : Najděte nejkratší supersekvenci, která obsahuje dvě nebo více sekvencí jako subsekvencí

Podřetězce

• Nejdelší běžný problém s podřetězcem : najděte nejdelší řetězec (nebo řetězce), který je podřetězcem (nebo jsou podřetězci) dvou nebo více řetězců
• Hledání podřetězců
  • Aho-Corasick řetězec odpovídající algoritmus : trie algoritmu založeného na nalezení všech podřetězec utkání některého z konečné sady strun
  • Algoritmus vyhledávání řetězců Boyer – Moore : amortizovaný lineární ( ve většině případů sublineární ) algoritmus pro vyhledávání podřetězců
  • Algoritmus Boyer – Moore – Horspool : Zjednodušení Boyer – Moore
  • Algoritmus Knuth – Morris – Pratt : vyhledávání podřetězců, které obchází opětovné zkoušení odpovídajících znaků
  • Algoritmus vyhledávání řetězců Rabin – Karp : prohledává efektivně více vzorů
  • Algoritmus shody řetězců Zhu – Takaoka : varianta Boyer – Moore
• Ukkonen algoritmus : a lineární-time , on-line algoritmus pro konstrukci příponu stromů
• Odpovídající zástupné znaky
  • Wild Salz ' wildmat : široce používaný open-source rekurzivní algoritmus
  • Kraussův algoritmus odpovídající zástupným znakům : nerekurzivní algoritmus s otevřeným zdrojovým kódem

Výpočetní matematika

Abstraktní algebra

• Chienovo vyhledávání : rekurzivní algoritmus pro určování kořenů polynomů definovaných přes konečné pole
• Algoritmus Schreier – Sims : výpočet základní a silné generující sady (BSGS) skupiny permutací
• Algoritmus Todd – Coxeter : Postup pro generování kosetů .

Počítačová algebra

• Buchbergerův algoritmus : najde Gröbnerův základ
• Algoritmus Cantor – Zassenhaus : polynomy faktorů nad konečnými poli
• Algoritmus Faugère F4 : najde Gröbnerův základ (zmiňuje také algoritmus F5)
• Gosperův algoritmus : najděte součty hypergeometrických výrazů, které jsou samy hypergeometrickými termíny
• Algoritmus dokončení Knuth – Bendix : pro přepis systémů pravidel
• Algoritmus dělení více proměnných : pro polynomy v několika neurčitých
• Pollardův klokaní algoritmus (také známý jako Pollardův lambda algoritmus): algoritmus pro řešení problému diskrétního logaritmu
• Polynomiální dlouhé dělení : algoritmus pro dělení polynomu jiným polynomem stejného nebo nižšího stupně
• Rischův algoritmus : algoritmus pro početní operace neurčité integrace (tj. Hledání antiderivativ )

Geometrie

• Nejbližší problém dvojice : najděte dvojici bodů (ze sady bodů) s nejmenší vzdáleností mezi nimi
• Algoritmy detekce kolizí : zkontrolujte kolizi nebo průnik dvou daných těles
• Algoritmus kužele : identifikuje povrchové body
• Konvexní obal algoritmy : určení konvexní trup o množiny bodů
  • Grahamův sken
  • Quickhull
  • Algoritmus balení dárků nebo pochod Jarvis
  • Chanův algoritmus
  • Algoritmus Kirkpatrick – Seidel
• Euklidovská transformace vzdálenosti : vypočítá vzdálenost mezi každým bodem v mřížce a diskrétní kolekcí bodů.
• Geometrické hašování : metoda pro efektivní nalezení dvourozměrných objektů reprezentovaných diskrétními body, které prošly afinní transformací
• Algoritmus vzdálenosti Gilbert – Johnson – Keerthi : určení nejmenší vzdálenosti mezi dvěma konvexními tvary.
• Algoritmus Jump-and-Walk : algoritmus pro umístění bodu v triangulacích
• Laplaciánské vyhlazování : algoritmus pro vyhlazení polygonální sítě
• Průsečík úseček: zjištění, zda se čáry protínají, obvykle s algoritmem rozmítání čar
  • Algoritmus Bentley – Ottmann
  • Algoritmus Shamos – Hoey
• Algoritmy minimálního ohraničovacího rámečku : najděte orientovaný minimální ohraničující rámeček uzavírající sadu bodů
• Hledání nejbližšího souseda : vyhledejte nejbližší bod nebo body bodu dotazu
• Bod v polygonových algoritmech: testuje, zda daný bod leží v daném polygonu
• Algoritmy registrace sady bodů : vyhledá transformaci mezi dvěma sadami bodů, aby je optimálně zarovnal.
• Rotující posuvná měřítka : určete všechny antipodální dvojice bodů a vrcholů na konvexním mnohoúhelníku nebo konvexním trupu .
• Algoritmus tkaničky : určete oblast polygonu, jehož vrcholy jsou popsány uspořádanými dvojicemi v rovině
• Triangulace
  • Delaunayova triangulace
    • Ruppertův algoritmus (také známý jako Delaunayovo upřesnění): vytváření kvalitních Delaunayových triangulací
    • Chewův druhý algoritmus : vytvářejí Delaunayovy triangulace omezené kvalitou
  • Pochodující trojúhelníky : rekonstruujte dvojrozměrnou geometrii povrchu z nestrukturovaného mračna bodů
  • Algoritmy triangulace polygonů : rozložte polygon na sadu trojúhelníků
  • Voronoiovy diagramy , geometrické dual of Delaunay triangulace
    • Algoritmus Bowyer – Watson : vytvořte voronoiový diagram v libovolném počtu dimenzí
    • Algoritmus štěstí : vytvořte voronoiový diagram
  • Kvazitriangulace

Algoritmy číselné teorie

• Algoritmus binárních GCD : Efektivní způsob výpočtu GCD.
• Boothův multiplikační algoritmus
• Chakravala metoda : cyklický algoritmus pro řešení neurčitých kvadratických rovnic, včetně Pellovy rovnice
• Diskrétní logaritmus :
  • Baby-step obří krok
  • Algoritmus indexového počtu
  • Pollardův rho algoritmus pro logaritmy
  • Algoritmus Pohlig – Hellman
• Euklidovský algoritmus : vypočítá největšího společného dělitele
• Rozšířený euklidovský algoritmus : Také řeší rovnici ax  +  o  =  c .
• Faktorizace celého čísla: rozdělení celého čísla na jeho hlavní faktory
  • Shoda čtverců
  • Dixonův algoritmus
  • Fermatova faktorizační metoda
  • Obecné síto číselného pole
  • Faktorizace eliptické křivky Lenstra
  • Pollardův  algoritmus p - 1
  • Pollardův rho algoritmus
  • algoritmus primární faktorizace
  • Kvadratické síto
  • Shorův algoritmus
  • Síto pro speciální čísla
  • Zkušební rozdělení
• Algoritmy násobení : rychlé násobení dvou čísel
  • Algoritmus Karatsuba
  • Algoritmus Schönhage – Strassen
  • Násobení Toom – Cook
• Modulární odmocnina : výpočet odmocnin modulo prvočíslo
  • Algoritmus Tonelli – Shanks
  • Cipollův algoritmus
  • Algoritmus Berlekampova kořene
• Algoritmus Odlyzko – Schönhage : vypočítá netriviální nuly funkce Riemann zeta
• Lenstra – Lenstra – Lovászův algoritmus (také známý jako LLL algoritmus): najděte krátký, téměř ortogonální mřížkový základ v polynomiálním čase
• Testy primality : určení, zda je dané číslo prvočíslo
  • Test primality AKS
  • Test primality Baillie – PSW
  • Fermatův test primality
  • Lucasův test primality
  • Miller -Rabinův test primality
  • Atkinovo síto
  • Síto Eratosthenes
  • Síto Sundaram

Numerické algoritmy

Řešení diferenciální rovnice

• Eulerova metoda
• Zpětná Eulerova metoda
• Trapézové pravidlo (diferenciální rovnice)
• Lineární vícestupňové metody
• Metody Runge – Kutta
  • Integrace Euler
• Multigridové metody ( metody MG), skupina algoritmů pro řešení diferenciálních rovnic pomocí hierarchie diskretizací
• Dílčí diferenciální rovnice :
  • Metoda konečných rozdílů
  • Klikově -Nicolsonova metoda pro difúzní rovnice
  • Lax – Wendroff pro vlnové rovnice
• Verlet integrace ( francouzská výslovnost: [vɛʁlɛ] ): integrují Newtonovy pohybové rovnice

Základní a speciální funkce

• Výpočet π :
  • Borweinův algoritmus : algoritmus pro výpočet hodnoty 1/π
  • Algoritmus Gauss – Legendre : vypočítá číslice pí
  • Chudnovského algoritmus : Rychlá metoda pro výpočet číslic π
  • Bailey – Borwein – Plouffeův vzorec : (vzorec BBP) algoritmus čepu pro výpočet n -té binární číslice π
• Algoritmy dělení : pro výpočet kvocientu a/nebo zbytku dvou čísel
  • Dlouhé dělení
  • Obnovování divize
  • Neobnovující se divize
  • Divize SRT
  • Divize Newton – Raphson : používá Newtonovu metodu k nalezení reciproční hodnoty D a vynásobením této reciproční hodnoty N k nalezení konečného kvocientu Q.
  • Goldschmidtova divize
• Hyperbolické a trigonometrické funkce:
  • Algoritmus BKM : vypočítává elementární funkce pomocí tabulky logaritmů
  • CORDIC : vypočítává hyperbolické a goniometrické funkce pomocí tabulky arktangentů
• Umocnění:
  • Zesílení na adiční řetězec : umocnění kladnými celočíselnými mocninami, které vyžaduje minimální počet násobení
  • Umocňování pomocí kvadratury : algoritmus používaný pro rychlý výpočet velkých celých mocnin čísla
• Montgomeryho redukce : algoritmus, který umožňuje efektivní provádění modulární aritmetiky, když je modul velký
• Algoritmy násobení : rychlé násobení dvou čísel
  • Boothův multiplikační algoritmus : multiplikační algoritmus, který znásobí dvě znaménková binární čísla v zápisu komplementu dvou
  • Fürerův algoritmus : celočíselný multiplikační algoritmus pro velmi velká čísla s velmi nízkou asymptotickou složitostí
  • Algoritmus Karatsuba : efektivní postup pro násobení velkých čísel
  • Algoritmus Schönhage – Strassen : asymptoticky rychlý multiplikační algoritmus pro velká celá čísla
  • Násobení Toom – Cook : (Toom3) multiplikační algoritmus pro velká celá čísla
• Multiplikativní inverzní algoritmy : pro výpočet multiplikativní inverzní hodnoty čísla (reciproční).
  • Newtonova metoda
• Zaokrouhlovací funkce : klasické způsoby zaokrouhlování čísel
• Algoritmus čepu : Způsob, jak vypočítat hodnotu matematické konstanty bez znalosti předchozích číslic
• Druhá mocnina a N -tý kořen čísla:
  • Alfa max plus beta min algoritmus : aproximace druhé odmocniny součtu dvou čtverců
  • Metody výpočtu odmocnin
  • n. kořenový algoritmus
  • Algoritmus posouvání n-root : extrakce kořenů číslice po číslici
• Souhrn:
  • Binární dělení : technika rozděl a panuj, která urychluje numerické vyhodnocování mnoha typů sérií s racionálními termíny
  • Algoritmus souhrnu Kahana : přesnější metoda sčítání čísel s plovoucí desetinnou čárkou
• Neomezený algoritmus

Geometrický

• Filtrovaná zpětná projekce : efektivně vypočítá inverzní 2-dimenzionální radonovou transformaci .
• Level set method (LSM): numerická technika pro sledování rozhraní a tvarů

Interpolace a extrapolace

• Birkhoffova interpolace : rozšíření polynomiální interpolace
• Kubická interpolace
• Hermitská interpolace
• Lagrangeova interpolace : interpolace pomocí Lagrangeových polynomů
• Lineární interpolace : metoda přizpůsobení křivky pomocí lineárních polynomů
• Monotónní kubická interpolace : varianta kubické interpolace, která zachovává monotónnost interpolované datové sady.
• Multivariační interpolace
  • Bicubická interpolace , zobecnění kubické interpolace na dvě dimenze
  • Bilineární interpolace : rozšíření lineární interpolace pro interpolační funkce dvou proměnných na pravidelné mřížce
  • Lanczosův převzorkování („Lanzosh“): multivariační interpolační metoda používaná k výpočtu nových hodnot pro všechna digitálně vzorkovaná data
  • Interpolace nejbližších sousedů
  • Tricubická interpolace , zobecnění kubické interpolace na tři dimenze
• Paretova interpolace : metoda odhadu mediánu a dalších vlastností populace, která následuje po Paretově distribuci .
• Polynomická interpolace
  • Nevillův algoritmus
• Interpolace splajnu : Snižuje chyby s Rungeovým fenoménem .
  • Al Boorův algoritmus : B-splajny
  • Algoritmus De Casteljau : Bézierovy křivky
• Trigonometrická interpolace

Lineární algebra

• Algoritmy vlastních čísel
  • Arnoldiova iterace
  • Inverzní iterace
  • Jacobiho metoda
  • Lanczosova iterace
  • Iterace napájení
  • Algoritmus QR
  • Rayleighova kvocientní iterace
• Gram – Schmidtův proces : ortogonalizuje sadu vektorů
• Algoritmy násobení matic
  • Algoritmus děla : distribuovaný algoritmus pro násobení matic, zvláště vhodný pro počítače uspořádané v síti N × N
  • Coppersmith – Winogradův algoritmus : násobení čtvercové matice
  • Freivaldsův algoritmus : randomizovaný algoritmus používaný k ověření násobení matice
  • Strassenův algoritmus : rychlejší multiplikace matice

• Řešení soustav lineárních rovnic
  • Metoda bikonjugátového gradientu : řeší soustavy lineárních rovnic
  • Konjugovaný gradient : algoritmus pro numerické řešení konkrétních soustav lineárních rovnic
  • Gaussova eliminace
  • Eliminace Gauss – Jordan : řeší soustavy lineárních rovnic
  • Gauss – Seidelova metoda : řeší soustavy lineárních rovnic iterativně
  • Levinsonova rekurze : řeší rovnici zahrnující Toeplitzovu matici
  • Stoneova metoda : také známá jako silně implicitní procedura nebo SIP, je algoritmus pro řešení řídkého lineárního systému rovnic
  • Následná nadměrná relaxace (SOR): metoda používaná k urychlení konvergence metody Gauss – Seidel
  • Algoritmus tridiagonální matice (Thomasův algoritmus): řeší systémy tridiagonálních rovnic
• Algoritmy řídké matice
  • Cuthill-McKee algoritmus : snížení šířky pásma o symetrické řídké matice
  • Algoritmus minimálního stupně : permutujte řádky a sloupce symetrické řídké matice před aplikací Choleskyho dekompozice
  • Symbolický Choleskyho rozklad : Efektivní způsob ukládání řídké matice

Monte Carlo

• Gibbsův výběr : generuje posloupnost vzorků ze společného rozdělení pravděpodobnosti dvou nebo více náhodných proměnných
• Hybridní Monte Carlo : generuje sekvenci vzorků pomocí Hamiltonova váženého Markovova řetězce Monte Carlo z rozdělení pravděpodobnosti, které je obtížné přímo odebrat.
• Algoritmus Metropolis – Hastings : používá se ke generování sekvence vzorků z rozdělení pravděpodobnosti jedné nebo více proměnných
• Algoritmus Wang a Landau : rozšíření vzorkování algoritmů Metropolis – Hastings

Numerická integrace

• Algoritmus MISER : Simulace Monte Carlo, numerická integrace

Kořenový nález

• Metoda půlení
• Metoda falešné polohy : aproximuje kořeny funkce
• Metoda ITP : minmax optimální a superlinární konvergence současně
• Newtonova metoda : najde nuly funkcí s kalkulem
• Halleyho metoda : používá první a druhý derivát
• Metoda sečna : 2bodová , jednostranná
• Metoda falešné polohy a metoda Illinois: 2bodová, bracketing
• Ridderova metoda : 3bodové , exponenciální škálování
• Mullerova metoda : 3bodová, kvadratická interpolace

Optimalizační algoritmy

• Prořezávání alfa – beta : vyhledávání za účelem snížení počtu uzlů v algoritmu minimax
• Větev a vázání
• Brussův algoritmus : viz kurzový algoritmus
• Násobení řetězové matice
• Kombinatorická optimalizace : optimalizační problémy, kde je soubor proveditelných řešení diskrétní
  • Greedy randomized adaptive search procedure (GRASP): postupné konstrukce chamtivého randomizovaného řešení a jeho následné iterační vylepšení prostřednictvím lokálního vyhledávání
  • Maďarská metoda : kombinatorický optimalizační algoritmus, který řeší problém přiřazení v polynomiálním čase
• Spokojenost omezení
  • Obecné algoritmy pro uspokojení omezení
    • Algoritmus AC-3
    • Algoritmus rozdílové mapy
    • Algoritmus minimálních konfliktů
  • Algoritmus plev : algoritmus pro řešení instancí booleovského problému uspokojivosti
  • Algoritmus Davis – Putnam : zkontrolujte platnost logického vzorce prvního řádu
  • Davis-Putnam-Logemann-Loveland algoritmus (DPLL): algoritmus pro rozhodování o splnitelnost výrokové logiky vzorce v konjunktivní normální formě , tedy pro řešení CNF-SAT problém
  • Přesný problém s krytem
    • Algoritmus X : nedeterministický algoritmus
    • Dancing Links : efektivní implementace Algoritmu X
• Metoda cross-entropie : obecný přístup Monte Carla ke kombinatorické a kontinuální multiextrémní optimalizaci a vzorkování důležitosti
• Diferenciální evoluce
• Dynamické programování : problémy vykazující vlastnosti překrývajících se podproblémů a optimální substrukturu
• Elipsoidová metoda : je algoritmus pro řešení problémů s konvexní optimalizací
• Evoluční výpočet : optimalizace inspirovaná biologickými mechanismy evoluce
  • Evoluční strategie
  • Programování genových výrazů
  • Genetické algoritmy
    • Poměrný výběr kondice -také známý jako výběr rulety
    • Stochastický univerzální odběr vzorků
    • Výběr zkrácení
    • Výběr turnaje
  • Memetický algoritmus
  • Rojová inteligence
    • Optimalizace kolonie mravenců
    • Algoritmus včel : vyhledávací algoritmus, který napodobuje chování potravních rojů včel
    • Roj částic
• Algoritmus Frank-Wolfe : iterativní optimalizační algoritmus prvního řádu pro omezenou konvexní optimalizaci
• Hledání ve zlaté sekci : algoritmus pro nalezení maxima skutečné funkce
• Sklon klesání
• Vyhledávání v mřížce
• Harmony search (HS): metaheuristický algoritmus napodobující improvizační proces hudebníků
• Metoda vnitřního bodu
• Lineární programování
  • Benson algoritmus : algoritmus pro řešení lineární vektor optimalizačních problémů
  • Dantzig – Wolfeův rozklad : algoritmus pro řešení problémů lineárního programování se speciální strukturou
  • Zpožděné generování sloupců
  • Celočíselné lineární programování : vyřešte problémy s lineárním programováním, kde jsou některé nebo všechny neznámé omezeny na celočíselné hodnoty
    • Větev a řez
    • Metoda řezné roviny
  • Karmarkarův algoritmus : První přiměřeně účinný algoritmus, který řeší problém lineárního programování v polynomiálním čase .
  • Simplex algoritmus : algoritmus pro řešení lineární programování problémy
• Řádkové vyhledávání
• Místní vyhledávání : metaheuristika pro řešení výpočetně náročných optimalizačních problémů
  • Náhodné restartování horolezectví
  • Hledání tabu
• Minimax používaný v programování her
• Hledání nejbližších sousedů (NNS): vyhledejte nejbližší body v metrickém prostoru
  • Best Bin First : najděte přibližné řešení problému hledání nejbližšího souseda ve velmi vysoce dimenzionálních prostorech
• Newtonova metoda v optimalizaci
• Nelineární optimalizace
  • Metoda BFGS : Nelineární optimalizační algoritmus
  • Gauss – Newtonův algoritmus : Algoritmus pro řešení nelineárních úloh nejmenších čtverců .
  • Levenberg – Marquardtův algoritmus : Algoritmus pro řešení nelineárních úloh nejmenších čtverců .
  • Nelder – Meadova metoda (downhill simplex metoda): Nelineární optimalizační algoritmus
• Algoritmus šancí (Brussův algoritmus): Najde optimální strategii pro předpověď poslední konkrétní události v události s náhodnou sekvencí
• Náhodné vyhledávání
• Simulované žíhání
• Stochastické tunelování
• Algoritmus součtu podmnožiny

Výpočetní věda

Astronomie

• Algoritmus Doomsday : den v týdnu
• Zellerova shoda je algoritmus pro výpočet dne v týdnu pro jakékoli datum juliánského nebo gregoriánského kalendáře
• k výpočtu dne Velikonoc se používají různé velikonoční algoritmy

Bioinformatika

• Basic Local Alignment Search Tool také známý jako BLAST: algoritmus pro porovnávání informací o primární biologické sekvenci
• Kabschův algoritmus : vypočítat optimální zarovnání dvou sad bodů za účelem výpočtu střední kvadratické odchylky mezi dvěma proteinovými strukturami.
• Velvet : sada algoritmů manipulujících s de Bruijnovými grafy pro sestavení genomické sekvence
• Řazení podle podepsaných zvratů : algoritmus pro pochopení genomové evoluce.
• Maximální šetrnost (fylogenetika) : algoritmus pro nalezení nejjednoduššího fylogenetického stromu k vysvětlení dané matice znaků.
• UPGMA : fylogenetický stromový algoritmus založený na vzdálenosti.

Geoscience

• Vincentyho vzorce : rychlý algoritmus pro výpočet vzdálenosti mezi dvěma body zeměpisné šířky/délky na elipsoidu
• Geohash : algoritmus veřejné domény, který kóduje desítkovou dvojici zeměpisná šířka/délka jako řetězec hash

Lingvistika

• Algoritmus Lesk : disambiguace smyslu slova
• Stemmingový algoritmus : metoda redukce slov na jejich kmenovou, základnovou nebo kořenovou formu
• Sukhotinův algoritmus : algoritmus statistické klasifikace pro klasifikaci znaků v textu jako samohlásky nebo souhlásky

Lék

• Algoritmus ESC pro diagnostiku srdečního selhání
• Obsazovací kritéria pro syndrom dráždivého tračníku
• Diagnostické algoritmy plicní embolie
• Projekt Texas Medication Algorithm

Fyzika

• Algoritmus omezení : třída algoritmů pro splnění omezení pro těla, která dodržují Newtonovy pohybové rovnice
• Algoritmus démona : metoda Monte Carlo pro efektivní vzorkování členů mikrokanonického souboru s danou energií
• Algoritmus Featherstone : vypočítá účinky sil působících na strukturu spojů a vazeb
• Základní stav aproximace
  • Variační metoda
    • Ritzova metoda
• n -tělesné problémy
  • Simulace Barnes – Hut : Řeší problém n-tělesa přibližným způsobem, který má pořadí O ( n log n ) místo O ( n ² ) jako v simulaci s přímým součtem.
  • Rychlá vícepólová metoda (FMM): zrychluje výpočet sil na dálku
• Algoritmus počítání deště : Redukuje komplexní historii napětí na počet elementárních zvratů napětí pro použití při únavové analýze
• Sweep and prořezávání : široký fázový algoritmus používaný během detekce kolize k omezení počtu párů pevných látek, které je třeba zkontrolovat na kolizi
• Algoritmus VEGAS : metoda pro snížení chyb v simulacích Monte Carlo
• Glauberova dynamika : metoda pro simulaci Isingova modelu na počítači

Statistika

• Algoritmy pro výpočet rozptylu : zamezení nestability a numerického přetečení
• Algoritmus přibližného počítání : Umožňuje počítat velký počet událostí v malém registru
• Bayesovské statistiky
  • Vnořený vzorkovací algoritmus : výpočetní přístup k problému porovnávání modelů v Bayesovské statistice
• Shlukování algoritmů
  • Klastrování průměrných vazeb : jednoduchý aglomerační shlukovací algoritmus
  • Algoritmus shlukování baldachýnů : Algoritmus předběžného shlukování bez dozoru související s algoritmem K-means
  • Cluster s kompletním propojením : jednoduchý aglomerační shlukovací algoritmus
  • DBSCAN : shlukovací algoritmus založený na hustotě
  • Algoritmus maximalizace očekávání
  • Fuzzy shlukování : třída shlukovacích algoritmů, kde každý bod má určitý stupeň příslušnosti ke klastrům
    • Fuzzy c-means
    • Klastrování FLAME (Fuzzy clustering by Local Aproximation of MEmberships): definujte klastry v hustých částech datové sady a provádějte přiřazení klastrů pouze na základě sousedských vztahů mezi objekty
  • Algoritmus klastrování KHOPCA : místní klastrovací algoritmus, který produkuje hierarchické klastry s více přeskoky ve statickém a mobilním prostředí.
  • k-means clustering : klastrové objekty založené na atributech do oddílů
  • k-means ++ : variace tohoto, pomocí modifikovaných náhodných semen
  • k-medoidy : podobné k-means, ale vybírá datové body nebo medoidy jako centra
  • Algoritmus Linde – Buzo – Gray : vektorový kvantovací algoritmus pro odvození dobrého číselníku
  • Lloydův algoritmus (Voronoiova iterace nebo relaxace): seskupení datových bodů do určitého počtu kategorií, oblíbený algoritmus pro klastrování k-means
  • OPTICS : shlukovací algoritmus založený na hustotě s metodou vizuálního hodnocení
  • Klastrování s jedním spojením : jednoduchý aglomerační shlukovací algoritmus
  • SUBCLU : algoritmus shlukování podprostoru
  • Wardova metoda : aglomerační shlukovací algoritmus, rozšířený o obecnější Lance -Williamsovy algoritmy
  • WACA clustering Algoritmus : místní klastrovací algoritmus s potenciálně multi-hop strukturami; pro dynamické sítě
• Teorie odhadu
  • Algoritmus maximalizace očekávání Třída souvisejících algoritmů pro nalezení odhadů maximální pravděpodobnosti parametrů v pravděpodobnostních modelech
    • Maximalizace seřazené podskupiny očekávání (OSEM): používá se v lékařském zobrazování pro pozitronovou emisní tomografii , jednofotonovou emisní počítačovou tomografii a rentgenovou počítačovou tomografii.
  • Algoritmus šancí (Brussův algoritmus) Optimální online vyhledávání rozlišené hodnoty v sekvenčním náhodném vstupu
  • Kalmanův filtr : odhadněte stav lineárního dynamického systému ze série hlučných měření
• Algoritmus falešného nejbližšího souseda (FNN) odhaduje fraktální dimenzi
• Skrytý Markovův model
  • Algoritmus Baum – Welch : vypočítává odhady maximální pravděpodobnosti a odhady pozdějšího režimu pro parametry skrytého Markovova modelu
  • Algoritmus vpřed-vzad : dynamický programovací algoritmus pro výpočet pravděpodobnosti konkrétní sledované sekvence
  • Algoritmus Viterbi : najděte nejpravděpodobnější sekvenci skrytých stavů ve skrytém Markovově modelu
• Částečná regrese nejmenších čtverců : najde lineární model popisující některé predikované proměnné z hlediska jiných pozorovatelných proměnných
• Teorie front
  • Buzenův algoritmus : algoritmus pro výpočet normalizační konstanty G (K) v Gordonově -Newellově větě
• RANSAC (zkratka pro „RANdom SAmple Consensus“): iterační metoda pro odhad parametrů matematického modelu ze sady pozorovaných dat, která obsahuje odlehlé hodnoty
• Algoritmus bodování : je forma Newtonovy metody, která se používá k numerickému řešení rovnic maximální pravděpodobnosti
• Metoda Yamartino : vypočítat aproximaci směrodatné odchylky σθ směru větru θ během jediného průchodu příchozími daty
• Algoritmus Ziggurat : generuje náhodná čísla z nejednotného rozdělení

Počítačová věda

Počítačová architektura

• Algoritmus Tomasulo : umožňuje sekvenční instrukce, které by normálně byly zablokovány kvůli určitým závislostem, provádět nesekvenčně

Počítačová grafika

• Výstřižek
  • Oříznutí čáry
    • Cohen – Sutherland
    • Cyrus – Beck
    • Rychlé ořezávání
    • Liang – Barsky
    • Nicholl – Lee – Nicholl
  • Oříznutí mnohoúhelníku
    • Sutherland – Hodgman
    • Vatti
    • Weiler – Atherton
• Obrysové čáry a rovinné plochy
  • Pochodující kostky : extrahujte polygonální síť izosurface z trojrozměrného skalárního pole (někdy nazývaného voxely)
  • Pochodující čtverce : generuje vrstevnice pro dvourozměrné skalární pole
  • Pochodující čtyřstěny : alternativa k pochodujícím kostkám
• Discrete Green's Theorem : je algoritmus pro výpočet dvojitého integrálu přes generalizovanou obdélníkovou doménu v konstantním čase. Je to přirozené rozšíření algoritmu tabulky součtových oblastí
• Flood fill : vyplní připojenou oblast vícerozměrného pole zadaným symbolem
• Algoritmy globálního osvětlení : Zvažuje přímé osvětlení a odraz od jiných objektů.
  • Ambient occlusion
  • Trasování paprsků
  • Trasování kuželů
  • Osvětlení založené na obrázku
  • Světelná doprava metropole
  • Trasování trasy
  • Mapování fotonů
  • Radiosita
  • Ray tracing
• Odstranění skrytého povrchu nebo Vizuální určení povrchu
  • Newellův algoritmus : eliminace polygonových cyklů při třídění hloubek požadovaných při odstraňování skrytého povrchu
  • Painterův algoritmus : detekuje viditelné části trojrozměrné scenérie
  • Vykreslování skeneru : vytvoří obrázek přesunutím imaginární čáry přes obrázek
  • Algoritmus Warnock
• Kreslení čar : grafický algoritmus pro aproximaci úsečky na diskrétních grafických médiích.
  • Algoritmus Bresenhamovy čáry : vykresluje body 2dimenzionálního pole a vytváří přímku mezi 2 zadanými body (používá rozhodovací proměnné)
  • Algoritmus čáry DDA : vykresluje body 2dimenzionálního pole a vytváří přímku mezi 2 zadanými body (používá matematiku s plovoucí desetinnou čárkou)
  • Algoritmus čáry Xiaolin Wu : algoritmus pro vyhlazování čar.
• Algoritmus středového kruhu : algoritmus používaný k určení bodů potřebných pro kreslení kruhu
• Algoritmus Ramer – Douglas – Peucker : Vzhledem k „křivce“ složené z úseček najít křivku ne příliš nepodobnou, ale která má méně bodů
• Stínování
  • Gouraudovo stínování : algoritmus simulující rozdílné efekty světla a barev na povrchu objektu ve 3D počítačové grafice
  • Phong stínování : algoritmus pro interpolaci normálových vektorů povrchu pro stínování povrchu ve 3D počítačové grafice
• Slerp (sférická lineární interpolace): quaternionová interpolace za účelem animace 3D rotace
• Souhrnná tabulka oblastí (také známá jako integrální obraz): algoritmus pro výpočet součtu hodnot v obdélníkové podmnožině mřížky v konstantním čase

Kryptografie

• Asymetrické šifrování (veřejný klíč) :
  • ElGamal
  • Kryptografie eliptické křivky
  • MAE1
  • NTRUEncrypt
  • RSA
• Digitální podpisy (asymetrické ověřování):
  • DSA a jeho varianty:
    • ECDSA a deterministická ECDSA
    • EdDSA (Ed25519)
  • RSA
• Kryptografické hashovací funkce (viz také část o ověřovacích kódech zpráv):
  • ČERNÁ
  • MD5 - Všimněte si, že nyní existuje způsob generování kolizí pro MD5
  • RIPEMD-160
  • SHA-1 -Všimněte si, že nyní existuje způsob generování kolizí pro 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), obvykle používaný v hašiších tygřích stromů
  • VÍŘIVÁ VANA
• Kryptograficky zabezpečené generátory pseudonáhodných čísel
  • Blum Blum Shub - na základě tvrdosti faktorizace
  • Fortuna , zamýšlený jako vylepšení algoritmu Yarrow
  • Posuvný registr s lineární zpětnou vazbou (poznámka: mnoho algoritmů založených na LFSR je slabých nebo bylo poškozeno)
  • Řebříčkový algoritmus
• Výměna klíčů
  • Výměna klíčů Diffie – Hellman
  • Eliptická křivka Diffie – Hellman (ECDH)
• Funkce odvozování klíčů , často používané pro hašování hesel a roztahování klíčů
  • bcrypt
  • PBKDF2
  • scrypt
  • Argon 2
• Ověřovací kódy zpráv (symetrické ověřovací algoritmy, které jako parametr berou klíč):
  • HMAC : autentizace pomocí klíče hash
  • Poly1305
  • SipHash
• Tajné sdílení , tajné dělení, dělení klíčů, M z N algoritmů
  • Blakeyho schéma
  • Shamirovo schéma
• Symetrické (tajný klíč) šifrování :
  • Advanced Encryption Standard (AES), vítěz soutěže NIST , také známý jako Rijndael
  • Blowfish
  • Dvakrát
  • Tři ryby
  • Data Encryption Standard (DES), někdy DE Algorithm, vítěz výběrové soutěže NBS, pro většinu účelů nahrazen AES
  • IDEA
  • RC4 (šifra)
  • Tiny Encryption Algorithm (TEA)
  • Salsa20 a jeho aktualizovaná varianta ChaCha20
• Postkvantová kryptografie
• Algoritmy důkazu o práci

Digitální logika

• Booleovská minimalizace
  • Algoritmus Quine – McCluskey : Také se nazývá algoritmus QM, programovatelná metoda pro zjednodušení booleovských rovnic.
  • Petrickova metoda : Další algoritmus pro booleovské zjednodušení.
  • Minimalizátor heuristické logiky Espresso : Rychlý algoritmus pro minimalizaci booleovské funkce.

Strojové učení a statistická klasifikace

• ALOPEX : algoritmus strojového učení založený na korelaci
• Učení se pravidlu asociace : objevte zajímavé vztahy mezi proměnnými používanými při dolování dat
  • Apriori algoritmus
  • Algoritmus Eclat
  • Algoritmus růstu FP
  • Pravidlo s jedním atributem
  • Pravidlo nulových atributů
• Boosting (meta-algoritmus) : Ke zvýšení efektivity použijte mnoho slabých studentů
  • AdaBoost : adaptivní posilování
  • BrownBoost : zesilující algoritmus, který může být odolný vůči hlučným datovým sadám
  • LogitBoost : posílení logistické regrese
  • LPBoost : posílení lineárního programování
• Agregace bootstrapu (pytlování): technika ke zlepšení stability a přesnosti klasifikace
• Počítačové vidění
  • Grabcut založený na řezech Graph
• Rozhodovací stromy
  • Algoritmus C4.5 : rozšíření ID3
  • Algoritmus ID3 (Iterativní dichotomizér 3): použijte heuristiku ke generování malých rozhodovacích stromů
• Clustering : třída nekontrolovaných výukových algoritmů pro seskupování a shromažďování souvisejících vstupních vektorů.
  • k-nejbližší sousedé (k-NN): metoda pro klasifikaci objektů na základě nejbližších tréninkových příkladů v prostoru funkcí
• Algoritmus Linde – Buzo – Gray : vektorový kvantovací algoritmus sloužící k odvození dobrého číselníku
• Lokalizované hašování (LSH): metoda provádění pravděpodobnostní redukce dimenzí vysoce dimenzionálních dat
• Nervová síť
  • Zpětná propagace : Metoda učení pod dohledem, která vyžaduje učitele, který zná nebo dokáže vypočítat požadovaný výstup pro jakýkoli daný vstup
  • Hopfield net : Opakující se neuronová síť, ve které jsou všechna připojení symetrická
  • Perceptron : nejjednodušší druh dopředné neuronové sítě: lineární klasifikátor .
  • Pulzně vázané neurální sítě (PCNN): Neurální modely navržené modelováním kočičí zrakové kůry a vyvinuté pro vysoce výkonné biomimetické zpracování obrazu.
  • Síť s radiálními základními funkcemi : umělá neuronová síť, která jako aktivační funkce využívá radiální bazické funkce
  • Samoorganizující se mapa : síť bez dohledu, která produkuje nízko dimenzionální reprezentaci vstupního prostoru tréninkových vzorků
• Random forest : klasifikujte pomocí mnoha rozhodovacích stromů
• Posílení učení :
  • Q-learning : naučí se funkce hodnota akce, která dává očekávanou užitečnost provedení dané akce v daném stavu a následování pevné zásady poté
  • State – Action – Rewards – State – Action (SARSA): osvojte si Markovovu politiku rozhodovacího procesu
  • Časové rozdílové učení
• Relevance-Vector Machine (RVM): podobný SVM, ale poskytuje pravděpodobnostní klasifikaci
• Učení pod dohledem : Učení podle příkladů (označené datové sady rozdělené na tréninkové a testovací)
• Support-Vector Machine (SVM): sada metod, které rozdělují vícerozměrná data nalezením dělící hyperplane s maximálním rozpětím mezi oběma sadami
  • Structured SVM : umožňuje školení klasifikátoru pro obecné strukturované výstupní štítky.
• Algoritmus Winnow : souvisí s perceptronem, ale používá multiplikační schéma aktualizace hmotnosti

Teorie programovacího jazyka

• Linearizace C3 : algoritmus používaný primárně k získání konzistentní linearizace hierarchie vícenásobné dědičnosti v objektově orientovaném programování
• Chaitinův algoritmus : algoritmus přidělování registrů pro barvení registrů zdola nahoru, který jako metriku rozlití používá cenu/stupeň
• Inferenční algoritmus typu Hindley – Milner
• Algoritmus Rete : efektivní algoritmus shody vzorů pro implementaci systémů produkčních pravidel
• Algoritmus Sethi-Ullman : generuje optimální kód pro aritmetické výrazy

Analýza

• Algoritmus CYK : Algoritmus O (n ³ ) pro analýzu bezkontextových gramatik v Chomského normální formě
• Earley parser : Další algoritmus O (n ³ ) pro analýzu jakékoli bezkontextové gramatiky
• GLR parser : Algoritmus pro analýzu jakékoli bezkontextové gramatiky od Masaru Tomita . Je vyladěn pro deterministické gramatiky, na kterých provádí téměř lineární čas a v nejhorším případě O (n ³ ).
• Algoritmus Inside-Out : Algoritmus O (n ³ ) pro opětovné odhadování pravděpodobností produkce v pravděpodobnostních bezkontextových gramatikách
• Analyzátor LL : Relativně jednoduchý algoritmus lineární časové analýzy pro omezenou třídu bezkontextových gramatik
• Analyzátor LR : Složitější algoritmus lineární časové analýzy pro větší třídu bezkontextových gramatik . Varianty:
  • Kanonický analyzátor LR
  • Analyzátor LALR (podívejte se dopředu LR)
  • Analyzátor přednosti operátorů
  • Analyzátor SLR (Simple LR)
  • Jednoduchý analyzátor priorit
• Packrat parser : Lineární algoritmus časové analýzy podporující některé bezkontextové gramatiky a analyzující výrazové gramatiky
• Rekurzivní analyzátor sestupu : analyzátor shora dolů vhodný pro gramatiky LL ( k )
• Algoritmus posunovacích yardů : převeďte matematický výraz s infixovou notací na postfix
• Analyzátor Pratt
• Lexikální analýza

Kvantové algoritmy

• Algoritmus Deutsch – Jozsa : kritérium rovnováhy pro booleovskou funkci
• Groverův algoritmus : poskytuje kvadratické zrychlení mnoha problémů s vyhledáváním
• Shorův algoritmus : poskytuje exponenciální zrychlení (ve srovnání s aktuálně známými nekvantovými algoritmy) pro faktoring čísla
• Simonův algoritmus : poskytuje prokazatelně exponenciální zrychlení (vzhledem k jakémukoli nekvantovému algoritmu) pro problém černé skříňky

Teorie výpočtu a automatů

• Hopcroftův algoritmus , Moorův algoritmus a Brzozowského algoritmus : algoritmy pro minimalizaci počtu stavů v deterministickém konečném automatu
• Konstrukce Powerset : Algoritmus pro převod nedeterministického automatu na deterministický automat .
• Algoritmus Tarski-Kuratowski : nedeterministický algoritmus, který poskytuje horní hranici složitosti vzorců v aritmetické hierarchii a analytické hierarchii

Informační teorie a zpracování signálu

Teorie kódování

Detekce a opravy chyb

• BCH kódy
  • Algoritmus Berlekamp – Massey
  • Algoritmus Peterson – Gorenstein – Zierler
  • Oprava chyby Reed – Solomon
• Algoritmus BCJR : dekódování kódů opravujících chyby definovaných na mřížích (hlavně konvoluční kódy)
• Předat opravu chyb
• Šedý kód
• Hammingovy kódy
  • Hamming (7,4) : Hammingův kód, který kóduje 4 bity dat do 7 bitů přidáním 3 paritních bitů
  • Hammingova vzdálenost : součet počtu pozic, které jsou různé
  • Hammingova váha (počet obyvatel): najděte počet 1 bitů v binárním slově
• Kontroly nadbytečnosti
  • Adler-32
  • Kontrola cyklické redundance
  • Dammův algoritmus
  • Fletcherův kontrolní součet
  • Kontrola podélné redundance (LRC)
  • Luhnův algoritmus : metoda ověřování identifikačních čísel
  • Algoritmus Luhnova mod N : rozšíření Luhna na nečíselné znaky
  • Parita : jednoduchá/rychlá technika detekce chyb
  • Verhoeffův algoritmus

Algoritmy bezeztrátové komprese

• Burrows – Wheelerova transformace : předzpracování užitečné pro zlepšení bezeztrátové komprese
• Váha kontextového stromu
• Kódování Delta : podpora komprese dat, ve kterých se sekvenční data často vyskytují
• Dynamická Markovova komprese : Komprese využívající prediktivní aritmetické kódování
• Slovníkové kodéry
  • Kódování párů bajtů (BPE)
  • Vypusťte
  • Lempel – Ziv
    • LZ77 a LZ78
    • Lempel – Ziv Jeff Bonwick (LZJB)
    • Algoritmus řetězce Lempel – Ziv – Markov (LZMA)
    • Lempel – Ziv – Oberhumer (LZO): orientovaný na rychlost
    • Lempel – Ziv – Stac (LZS)
    • Lempel – Ziv – Storer – Szymanski (LZSS)
    • Lempel – Ziv – Welch (LZW)
    • LZWL : varianta založená na slabikách
    • LZX
    • Lempel – Ziv Ross Williams (LZRW)
• Entropické kódování : kódovací schéma, které přiřazuje kódy symbolům tak, aby odpovídaly délkám kódu s pravděpodobností symbolů
  • Aritmetické kódování : pokročilé kódování entropie
    • Kódování rozsahu : stejné jako aritmetické kódování , ale bylo na něj pohlíženo trochu jiným způsobem
  • Huffmanovo kódování : jednoduchá bezeztrátová komprese využívající výhody relativních znakových frekvencí
    • Adaptivní Huffmanovo kódování : adaptivní kódovací technika založená na Huffmanově kódování
    • Algoritmus sloučení balíčků : Optimalizuje Huffmanovo kódování s výhradou omezení délky řetězců kódu
  • Kódování Shannon – Fano
  • Kódování Shannon – Fano – Elias : předchůdce aritmetického kódování
• Kódování entropie se známými charakteristikami entropie
  • Golombovo kódování : forma entropického kódování, která je optimální pro abecedy po geometrických distribucích
  • Rice coding : forma entropického kódování, která je optimální pro abecedy po geometrických distribucích
  • Zkrácené binární kódování
  • Unární kódování : kód, který představuje číslo n s n jedničkami, za nimiž následuje nula
  • Univerzální kódy : kóduje kladná celá čísla do binárních kódových slov
    • Eliasovo delta , gama a omega kódování
    • Exponenciální-Golombovo kódování
    • Fibonacciho kódování
    • Levenshteinovo kódování
• Fast Efficient & Lossless Image Compression System (FELICS): bezeztrátový algoritmus komprese obrazu
• Inkrementální kódování : delta kódování aplikované na sekvence řetězců
• Predikce částečnou shodou (PPM): adaptivní technika komprese statistických dat založená na kontextovém modelování a predikci
• Kódování za běhu : bezeztrátová komprese dat s využitím řetězců opakujících se znaků
• Algoritmus SEQUITUR : bezeztrátová komprese pomocí inkrementálního odvozování gramatiky na řetězci

Algoritmy ztrátové komprese

• 3Dc : ztrátový algoritmus komprese dat pro normální mapy
• Audio a řeči komprese
  • Algoritmus A-law : standardní kompandovací algoritmus
  • Lineární predikce buzená kódem (CELP): komprese řeči s nízkou bitovou rychlostí
  • Lineární prediktivní kódování (LPC): ztrátová komprese reprezentující spektrální obálku digitálního signálu řeči v komprimované formě
  • Algoritmus Mu-law : standardní analogový kompresní nebo kompandovací algoritmus
  • Pokřivené lineární prediktivní kódování (WLPC)
• Komprese obrazu
  • Block Truncation Coding (BTC): typ techniky ztrátové komprese obrázků pro obrázky ve stupních šedi
  • Vestavěný Zerotree Wavelet (EZW)
  • Algoritmy rychlé kosinové transformace ( algoritmy FCT): efektivně vypočítává diskrétní kosinovou transformaci (DCT)
  • Fraktální komprese : metoda používaná ke kompresi obrázků pomocí fraktálů
  • Nastavit rozdělení na hierarchické stromy (SPIHT)
  • Waveletová komprese : forma komprese dat dobře vhodná pro kompresi obrazu (někdy také komprese videa a komprese zvuku)
• Transformační kódování : typ komprese dat pro „přirozená“ data, jako jsou zvukové signály nebo fotografické obrázky
• Komprese videa
• Vektorová kvantizace : technika často používaná při ztrátové kompresi dat

Zpracování digitálních signálů

• Adaptivně-aditivní algoritmus (AA algoritmus): vyhledejte fázi prostorové frekvence pozorovaného vlnového zdroje
• Diskrétní Fourierova transformace : určuje frekvence obsažené v signálu (segmentu a)
  • Algoritmus FFT společnosti Bluestein
  • Bruunův FFT algoritmus
  • Algoritmus FFT Cooley – Tukey
  • Rychlá Fourierova transformace
  • Algoritmus FFT primárního faktoru
  • Raderův FFT algoritmus
• Algoritmus rychlého skládání : účinný algoritmus pro detekci přibližně periodických událostí v datech časových řad
• Algoritmus Gerchberg – Saxton : Algoritmus získávání fází pro optické roviny
• Algoritmus Goertzel : identifikuje konkrétní frekvenční složku v signálu. Lze použít pro dekódování číslic DTMF .
• Karplus-Silná syntéza strun : Syntéza fyzického modelování pro simulaci zvuku tlouknutého nebo trhaného strun nebo některých typů bicích nástrojů

Zpracování obrazu

• Vylepšení kontrastu
  • Vyrovnání histogramu : použijte histogram ke zlepšení kontrastu obrazu
  • Adaptivní ekvalizace histogramu : ekvalizace histogramu, která se přizpůsobuje lokálním změnám kontrastu
• Označování připojených komponent : vyhledejte a označte nesouvislé oblasti
• Dithering a half-toning
  • Difúze chyb
  • Floyd – Steinberg váhá
  • Nařízeno dithering
  • Riemersma váhá
• Algoritmus rozdílové mapy Elser : vyhledávací algoritmus pro obecné problémy s uspokojením omezení. Původně se používal pro rentgenovou difrakční mikroskopii
• Detekce funkcí
  • Detektor hran Canny : detekuje na obrázcích širokou škálu hran
  • Zobecněná Houghova transformace
  • Tvrdá transformace
  • Marr-Hildreth algoritmus : časné detekci hran algoritmus
  • SIFT (transformace funkce neměnná v měřítku): je algoritmus pro detekci a popis místních funkcí v obrazech.
  • SURF ( Speeded Up Robust Features ) : je robustní lokální detektor funkcí, který poprvé představil Herbert Bay et al. v roce 2006, které lze použít v úlohách počítačového vidění, jako je rozpoznávání objektů nebo 3D rekonstrukce. Je částečně inspirován deskriptorem SIFT. Standardní verze SURF je několikrát rychlejší než SIFT a její autoři tvrdí, že jsou odolnější proti různým transformacím obrazu než SIFT.
• Dekonvoluce Richardson – Lucy : algoritmus pro odstranění rozmazání obrazu
• Slepá dekonvoluce : algoritmus pro rozostření obrazu, když není známa funkce šíření bodů .
• Medián filtrování
• Řezání švů : algoritmus pro změnu velikosti obrazu s vědomím obsahu
• Segmentace : rozdělení digitálního obrazu na dvě nebo více oblastí
  • Algoritmus GrowCut : interaktivní segmentační algoritmus
  • Algoritmus náhodných chodců
  • Region roste
  • Transformace povodí : třída algoritmů založená na analogii povodí

Softwarové inženýrství

• Algoritmy mezipaměti
• Konverze CHS : převod mezi systémy adresování disku
• Double dabble : Převod binárních čísel na BCD
• Funkce hash : převede velké, případně proměnné množství dat na malý datum, obvykle jedno celé číslo, které může sloužit jako index do pole
  • Funkce hash Fowler – Noll – Vo : rychlá s nízkou mírou kolizí
  • Pearson hashing : vypočítá pouze 8bitovou hodnotu, optimalizovanou pro 8bitové počítače
  • Zobrist hashing : používá se při implementaci transpozičních tabulek
• Algoritmus řazení Unicode
• Algoritmus swapu Xor : zaměňuje hodnoty dvou proměnných bez použití vyrovnávací paměti

Algoritmy databáze

• Algoritmy pro obnovu a izolaci využívající sémantiku (ARIES): obnova transakcí
• Připojte se k algoritmům
  • Blokovat vnořenou smyčku
  • Hash připojení
  • Spojení vnořené smyčky
  • Seřadit-Sloučit Připojit

Algoritmy distribuovaných systémů

• Synchronizace hodin
  • Berkeleyův algoritmus
  • Cristianův algoritmus
  • Algoritmus křižovatky
  • Marzullův algoritmus
• Konsensus (počítačová věda) : dohodnutí jedné hodnoty nebo historie mezi nespolehlivými procesory
  • Algoritmus konsensu Chandra – Toueg
  • Paxosův algoritmus
  • Raft (počítačová věda)
• Detekce ukončení procesu
  • Algoritmus Dijkstra-Scholten
  • Huangův algoritmus
• Lamport objednávání : a částečné uspořádání událostí vychází z stalo, před vztahu
• Volba vůdce : metoda pro dynamický výběr koordinátora
  • Bully algoritmus
• Vzájemné vyloučení
  • Distribuovaný algoritmus vzájemného vyloučení společnosti Lamport
  • Naimi-Trehelův log (n) algoritmus
  • Maekawův algoritmus
  • Raymondův algoritmus
  • Algoritmus Ricart – Agrawala
• Algoritmus Snapshot : zaznamenejte konzistentní globální stav pro asynchronní systém
  • Algoritmus Chandy -Lamport
• Vektorové hodiny : generují částečné řazení událostí v distribuovaném systému a zjišťují porušení kauzality

Algoritmy alokace paměti a deallokace

• Přidělení paměti Buddy : Algoritmus pro přidělování paměti tak, aby fragmentace byla menší.
• Popeláři
  • Cheneyho algoritmus : Vylepšení poloprostorového kolektoru
  • Generational garbage collector : Rychlí popeláři, kteří oddělují paměť podle věku
  • Kompaktní algoritmus značek : kombinace algoritmu rozmítání značek a Cheneyho kopírovacího algoritmu
  • Označte a zamete
  • Poloprostorový kolektor : Sběratel raného kopírování
• Počítání referencí

Sítě

• Karnův algoritmus : řeší problém získání přesných odhadů doby zpáteční pro zprávy při použití TCP
• Luleåův ​​algoritmus : technika pro efektivní ukládání a prohledávání směrovacích tabulek internetu
• Přetížení sítě
  • Exponenciální backoff
  • Nagleův algoritmus : zlepšuje efektivitu sítí TCP/IP sdružováním paketů
  • Zkrácené binární exponenciální zpoždění

Algoritmy operačních systémů

• Algoritmus bankéře : Algoritmus používaný pro zamezení zablokování.
• Algoritmy nahrazení stránky : Výběr stránky oběti za podmínek nedostatku paměti.
  • Adaptivní náhradní mezipaměť : lepší výkon než LRU
  • Hodiny s adaptivní výměnou (CAR): je algoritmus pro výměnu stránky, který má výkon srovnatelný s adaptivní náhradní mezipamětí

Synchronizace procesů

• Dekkerův algoritmus
• Algoritmus Lamport's Bakery
• Petersonův algoritmus

Plánování

• Nejdříve termín první plánování
• Plánování spravedlivého sdílení
• Nejméně volné časové plánování
• Plánování seznamu
• Víceúrovňová fronta zpětné vazby
• Hodnotově monotónní plánování
• Plánování každý s každým
• Další nejkratší práce
• Nejkratší zbývající čas
• Algoritmus nejlepších uzlů : správa kalendáře zdrojů

Plánování I/O

Plánování disku

• Algoritmus výtahu : Algoritmus plánování disku, který funguje jako výtah.
• Nejkratší hledání jako první : Algoritmus plánování disku ke zkrácení doby hledání .

Viz také

• Seznam datových struktur
• Seznam algoritmů strojového učení
• Seznam algoritmů pro hledání cesty
• Seznam obecných témat algoritmů
• Seznam termínů týkajících se algoritmů a datových struktur
• Heuristický

Reference