Teorie algoritmů

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 22. srpna 2021; ověření vyžaduje 1 úpravu .

Teorie algoritmů je odvětví matematiky , které studuje obecné vlastnosti a vzory algoritmů a různé formální modely pro jejich reprezentaci. Mezi úkoly teorie algoritmů patří formální důkaz algoritmické neřešitelnosti problémů, asymptotická analýza složitosti algoritmů , klasifikace algoritmů podle tříd složitosti , vývoj kritérií pro srovnávací hodnocení kvality algoritmů atd. Společně s matematickou logikou tvoří teorie algoritmů teoretický základ výpočetních věd [1] [2] , teorie přenosu informace, informatiky , telekomunikačních systémů a dalších oblastí vědy a techniky.

Historie

Vývoj teorie algoritmů začíná Kurtem Gödelovým důkazem teorémů neúplnosti pro formální systémy zahrnující aritmetiku, z nichž první byl prokázán v roce 1931 . Předpoklad, který v souvislosti s těmito větami vznikl o nemožnosti algoritmického řešení mnoha matematických problémů (zejména problému odvoditelnosti v predikátovém počtu ), vyvolal potřebu standardizovat koncept algoritmu. První standardizované verze tohoto konceptu vyvinuli ve 30. letech 20. století Alan Turing , Emil Post a Alonzo Church . Jejich navrhovaný Turingův stroj , Postův stroj a lambda počet se ukázaly být navzájem ekvivalentní. Na základě práce Gödela představil Stephen Kleene koncept rekurzivní funkce , který se také ukázal jako ekvivalentní výše uvedenému.

Jednou z nejúspěšnějších standardizovaných variant algoritmu je koncept normálního algoritmu představený Andrey Markovem . Byl vyvinut deset let po práci Turinga, Posta, Churche a Kleenea v souvislosti s důkazem algoritmické neřešitelnosti řady algebraických problémů.

V pozdějších letech významně přispěli k teorii algoritmů Donald Knuth , Alfred Aho a Jeffrey Ullman .

Výpočtové modely

Turingův stroj je abstraktní exekutor (abstraktní výpočetní stroj). To bylo navrženo Alanem Turingem v roce 1936 formalizovat koncept algoritmu . Turingův stroj je rozšířením konečného automatu a podle Church-Turingovy teze je schopen napodobit všechny ostatní vykonavatele (nastavením přechodových pravidel), které nějakým způsobem implementují postupný proces výpočtu, ve kterém je každý krok výpočtu docela elementární.
Lambda kalkul - uvažuje se dvojice: λ-výraz a jeho argument, - a výpočet je aplikace nebo aplikace prvního člena dvojice na druhý. To vám umožní oddělit funkci a to, na co se vztahuje. Obecněji se za výpočet považuje řetězec začínající počátečním λ-výrazem následovaným konečnou sekvencí λ-výrazů, z nichž každý je získán z předchozího použitím β-redukce , tedy substitučního pravidla .
Kombinatorická logika - výklad výpočtu je podobný jako u λ-kalkulu, ale jsou zde i důležité rozdíly (např. kombinátor Y s pevnou čárkou má normální tvar v kombinatorické logice, ale ne v λ-kalkulu). Kombinatorická logika byla původně vyvinuta pro studium povahy paradoxů a pro vybudování koncepčně jasného základu pro matematiku a myšlenka proměnné byla zcela vyloučena, což pomohlo objasnit roli a místo proměnných v matematice .
Registrovat stroje , konkrétně stroj RAM , je abstraktní počítač, který simuluje počítač s náhodným přístupem k paměti. Právě tento výpočtový model se nejčastěji používá při analýze algoritmů.

Church-Turingova teze a algoritmicky neřešitelné problémy

Alan Turing se domníval (známý jako " Church-Turingova teze "), že jakýkoli algoritmus - v intuitivním smyslu slova - může být reprezentován ekvivalentním Turingovým strojem . Zpřesnění pojmu vyčíslitelnost na základě konceptu takového stroje (a dalších konceptů jemu ekvivalentních) otevřelo možnost důsledně prokázat algoritmickou neřešitelnost různých hromadných problémů (problémy hledání jednotné metody řešení určité třídy problémů , jehož podmínky se mohou v určitých mezích lišit).

Nejjednodušším příkladem algoritmicky neřešitelného hromadného problému je problém použitelnosti algoritmu, zastavovací problém , který je následující: je třeba najít obecnou metodu, která by umožňovala libovolný Turingův stroj (daný jeho programem) a libovolný počáteční stav pásky tohoto stroje k určení, zda práce stroj ukončí v konečném počtu kroků, nebo bude pokračovat donekonečna?

Během prvního desetiletí historie teorie algoritmů byly neřešitelné hromadné problémy nalezeny pouze samy o sobě (včetně výše popsaného "problému použitelnosti") a v matematické logice ("problém odvoditelnosti" v klasickém predikátovém počtu ). Proto se věřilo, že teorie algoritmů je „cestou“ matematiky, což pro takové klasické sekce jako „ algebra “ nebo „ analýza “ nevadí . Situace se změnila poté , co Andrei Markov a Emil Post v roce 1947 prokázali algoritmickou neřešitelnost známého problému rovnosti v algebře pro konečně generované a konečně definované pologrupy ( Thueův problém ). Následně byla stanovena algoritmická neřešitelnost mnoha dalších "čistě matematických" hromadných problémů, nejznámějším výsledkem v této oblasti je algoritmická neřešitelnost Hilbertova desátého problému dokázaná Jurijem Matiyasevichem .

Pokyny

Teorie algoritmů se vyvíjí především ve třech směrech:

Klasický:
- Formální formulace úkolů;
- Koncept řešení problému ;
- Klasifikace stupňů obtížnosti (" P ", " NP " a další).
Analýza:
- Asymptotické :
  - Odhad intenzity zdrojů a doby provádění (zejména u rekurzivních algoritmů);
  - Odhad růstu požadavků na zdroje (například doby provádění) s nárůstem objemu dat.
- Praktický:
  - Získání „explicitních“ funkcí intenzity práce;
  - Intervalová analýza funkcí;
  - Hledání kritérií kvality;
  - Metodologie racionální volby.

Analýza složitosti algoritmů

Účelem analýzy je najít optimální algoritmus. Kritériem je pracnost (počet elementárních operací, které algoritmus vyžaduje). Funkce vstupu práce je poměr vstupu práce ke vstupním datům.

Složitost může být v různé míře ovlivněna vlastnostmi vstupních dat:

Hlasitost;
hodnoty;
Vstupní příkaz.

Jeden ze zjednodušených typů analýzy nákladů algoritmů je asymptotický s velkým množstvím vstupních dat. Odhadem použité funkce náročnosti práce je „složitost“ algoritmu , která umožňuje určit vztah mezi náročností práce a množstvím dat. Při asymptotické analýze algoritmů se používá zápis používaný v matematické asymptotické analýze. Hlavní hodnocení obtížnosti jsou uvedeny níže.

Hlavní odhad funkce složitosti algoritmu (kde n je množství dat, „délka vstupu“) je : $f(n)$ ${\boldsymbol {\Theta ))$

f(n)={\tučný symbol {\Theta}}(g(n))

jestliže pro g > 0, pro n > 0 existují kladné c 1 , c 2 , n 0 takové, že:

c_{1}\cdot g(n)\leq \;f(n)\leq \;c_{2}\cdot g(n)

v ; jinými slovy, lze najít takové a , že pro dostatečně velké , bude uzavřeno mezi: ${\displaystyle n>n_{0))$ $c_{1}$ $c_{2}$ $n$ $f(n)$

c_{1}\cdot \;g(n)

a .

c_{2}\cdot \;g(n)

V tomto případě také říkají, že funkce je asymptoticky přesný odhad funkce , protože z definice se funkce neliší od funkce až do konstantního faktoru (viz asymptotická rovnost ). Například pro metodu třídění "heapsort" je vstup práce: $g(n)$ $f(n)$ $f(n)$ $g(n)$

f(n)={\boldsymbol {\Theta}}(n\log n)

, to je .

g(n)=n\log n

Od vyplývá . $f(n)={\tučný symbol {\Theta}}(g(n))$ $g(n)={\tučný symbol {\Theta}}(f(n))$

${\boldsymbol {\Theta }}(g(n))$ není funkcí, ale souborem funkcí popisujících růst až po konstantní faktor. udává horní i dolní mez růstu funkce. Často je nutné tyto odhady posuzovat samostatně. Odhad je horní asymptotický odhad složitosti algoritmu. Říkáme, že pokud: $f(n)$ ${\boldsymbol {\Theta ))$ ${\boldsymbol {O}}$ $f(n)={\boldsymbol {O}}(g(n))$

\exists \;c>0,n_{0}>0:0\leq \;f(n)\leq \;cg(n),\forall \;n>n_{0}

Jinými slovy, zápis znamená, že patří do třídy funkcí, které nerostou rychleji než funkce až do konstantního faktoru. $f(n)={\boldsymbol {O}}(g(n))$ $f(n)$ $g(n)$

Odhad specifikuje nižší asymptotický odhad růstu funkce a definuje třídu funkcí, které rostou ne pomaleji než do konstantního faktoru. , pokud: ${\boldsymbol {\Omega ))$ $f(n)$ $g(n)$ $f(n)={\tučný symbol {\Omega}}(g(n))$

{\displaystyle \exists \;c>0,n_{0}>0:0\leq \;c\,g(n)\leq \;f(n),\forall \;n>n_{0))

Zápis například označuje třídu funkcí, které nerostou pomaleji než ; tato třída zahrnuje všechny polynomy se stupněm větším než jedna, stejně jako všechny mocninné funkce se základem větším než jedna. $f(n)={\boldsymbol {\Omega ))(n\,\log n)$ $g(n)=n\,\log n$

Rovnost platí tehdy a jen tehdy, když a . $f(n)={\tučný symbol {\Theta}}(g(n))$ $f(n)={\boldsymbol {O}}(g(n))$ $f(n)={\tučný symbol {\Omega}}(g(n))$

Asymptotická analýza algoritmů má nejen praktický, ale i teoretický význam. Bylo například prokázáno, že všechny třídicí algoritmy založené na párovém porovnávání prvků seřadí n prvků v čase ne méně než . ${\boldsymbol {\Omega }}(n\,\log n)$

Důležitou roli ve vývoji asymptotické analýzy algoritmů sehráli Alfred Aho , Jeffrey Ullman , John Hopcroft .

Třídy obtížnosti

V rámci klasické teorie jsou problémy klasifikovány podle jejich složitosti ( P-těžké , NP-těžké , exponenciálně těžké a další):

"P" - lze řešit v čase, polynomiálně závislém na množství počátečních dat, pomocí deterministického počítače (například " Turingův stroj ");
"NP":
- Úlohy, které lze řešit v polynomiálním čase pomocí nedeterministického počítače (jehož další stav není vždy jednoznačně určen předchozími). Jeho práci lze znázornit jako proces větvení při každé nejednoznačnosti: problém je vyřešen, pokud alespoň jedna větev dosáhne odpovědi;
- Úlohy, jejichž řešení pomocí doplňujících informací o délce polynomu, které nám byly dány shora, můžeme zkontrolovat v polynomiálním čase. Zejména třída "NP" zahrnuje všechny problémy, jejichž řešení lze zkontrolovat v polynomiálním čase.

Třída "P" je obsažena v "NP". Klasickým příkladem problému NP je „ Problém cestujícího obchodníka “.

Protože "P" je obsaženo v "NP", příslušnost problému do třídy "NP" často odráží naše současné chápání toho, jak tento problém vyřešit, a není konečné. V obecném případě není důvod se domnívat, že nelze najít P-řešení pro ten či onen NP-problém. Otázka možné ekvivalence tříd "P" a "NP" (možnost nalezení P-řešení pro jakýkoli NP-problém) je považována za jednu z hlavních v moderní teorii složitosti algoritmů; zatím nebyla nalezena žádná odpověď. Jeho samotná formulace je možná díky zavedení konceptu NP-úplných problémů ; lze na ně zredukovat jakékoli NP-problémy — a pokud je nalezeno P-řešení pro NP-úplný problém, pak bude nalezeno P-řešení pro všechny NP-problémy. Příkladem NP-úplného problému je „ Problém s konjunktivitou “.

Studium složitosti algoritmů umožnilo nově se podívat na řešení mnoha klasických matematických problémů a najít pro některé jejich řady (násobení polynomů a matic, řešení lineárních soustav rovnic a další) řešení, která vyžadují méně zdroje než tradiční.

Matematické aplikace teorie algoritmů

Některé aplikace teorie algoritmů:

výzkum masových problémů;
aplikace do základů matematiky : konstruktivní sémantika ;
aplikace na matematickou logiku : analýza formalizovaných jazyků logiky a aritmetiky ;
vypočitatelná analýza;
číslované struktury;
aplikace v teorii pravděpodobnosti : definice náhodné posloupnosti;
aplikace v teorii informace : algoritmický přístup ke konceptu kvantity informace;
posouzení složitosti řešení jednotlivých problémů;
vliv teorie algoritmů na algoritmickou praxi [3] .

Poznámky

↑ Semjonov A. L. , Uspensky V. A. Matematická logika ve výpočetních vědách a výpočetní praxi. // Bulletin Akademie věd SSSR , č. 7, s. 93-103
↑ Uspenskij V. A. , Semjonov A. L. Řešitelné a neřešitelné algoritmické problémy. // Kvant , 1985, č. 7, s. 9-15
↑ V. A. Uspensky , A. L. Semenov Teorie algoritmů: hlavní objevy a aplikace, M., Nauka , 1987, 288 s.

Literatura

Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmy: konstrukce a analýza = Introduction to Algorithms / Ed. I. V. Krasíková. - 2. vyd. - M. : Williams, 2005. - 1296 s. — ISBN 5-8459-0857-4 .
Donald Knuth . The Art of Computer Programming, díl 1. Základní algoritmy = The Art of Computer Programming, díl 1. Základní algoritmy. - 3. vyd. - M. : Williams, 2006. - 720 s. - ISBN 0-201-89683-4 .
Kolmogorov A. N. Teorie informace a teorie algoritmů. - M. : Nauka, 1987. - 304 s.
Markov A. A., Nagorny N. M. Theory of Algorithms. - 2. vyd. - M .: Fazis, 1996.

Odkazy

Přednášky o teorii složitosti a kombinatorických algoritmech

Slovníky a encyklopedie	Velká Katalánština Velký Rus

Odvětví matematiky

Portál "Věda"

Základy matematiky teorie množin matematická logika algebra logiky

Teorie čísel ( aritmetika )

Algebra
Elementární algebra	Řešení rovnice
Lineární algebra	Vektorový počet matrice Tenzorový počet Multilineární algebra
Obecná algebra	Komutativní algebra Teorie reprezentace Diferenciální algebra Homologická algebra Univerzální algebra Teorie kategorií

Analýza
Klasická analýza	Diferenciální počet Integrální počet
Teorie funkcí	Harmonická analýza Kvaternionová analýza Komplexní analýza teorie míry Teorie funkcí reálné proměnné funkční analýza Variační počet
Diferenciální a integrální rovnice	Dynamické systémy a ergodická teorie Diferenciální rovnice obyčejný v parciálních derivacích Integrální rovnice
Vektorová analýza Globální analýza Teorie katastrofy Vlastní analýza Hladká infinitezimální analýza

Geometrie a topologie
Geometrie	Algebraická geometrie Analytická geometrie Euklidovská geometrie Neeuklidovská geometrie Planimetrie Stereometrie
Topologie	Obecná topologie Algebraická topologie Diferenciální geometrie a topologie

Diskrétní matematika
Kombinatorika teorie grafů

Aplikovaná matematika
Matematická fyzika Matematická chemie matematická biologie Matematické statistiky Matematické modelování Teorie algoritmů Numerické metody matematická ekonomie finanční matematika Teorie pravděpodobnosti Operační výzkum Herní teorie

Portál "Matematika"
Kategorie "Matematika"