Seznam vyčíslitelných a složitých témat - List of computability and complexity topics
Toto je seznam vyčíslitelnost a složitost témat, stránkou Wikipedie.
Teorie vypočítatelnosti je součástí teorie výpočet která se v zásadě zabývá tím, co lze vypočítat. Teorie výpočetní složitosti pojednává o tom, jak tvrdé výpočty jsou, z kvantitativního hlediska, oba s horními mezemi (algoritmy jejichž složitost v nejhorších případech, jako je použití výpočetních zdrojů, lze odhadnout) a zdola (důkazy o tom, že žádný postup k provedení nějakého úkolu nemůže být velmi rychlý).
Další abstraktní základní záležitosti viz seznam témat matematické logiky. Viz také seznam algoritmů, seznam obecných témat algoritmu.
Výpočet
- Vyhledávací tabulka
- Historie počítačů
- Algoritmus násobení
- Dělení dvěma
- Umocňování čtvercem
- Sčítací řetězec
- Presburgerova aritmetika
Teorie vypočítatelnosti: modely výpočtu
- Aritmetické obvody
- Algoritmus
- Konečný stavový automat
- Pushdown automat
- Büchi automat
- Chomského hierarchie
- Zaregistrujte stroj
- Stohovací stroj
- Petriho síť
- Post stroj
- Přepisování
- Výška hvězdy
- Buněčný automat
- Turingův stroj
- Lambda kalkul
- Kombinovaná logika
- Paralelní výpočty
- Flynnova taxonomie
- Kvantový počítač
- Church-Turingova teze
Problémy s rozhodováním
- Entscheidungsproblem
- Zastavení problému
- Problém s korespondencí
- Rozhodnutelný jazyk
- Slovní úloha pro skupiny
- Wang dlaždice
- Penroseovy obklady
Otázky definovatelnosti
- Vypočítatelné číslo
- Definovatelné číslo
- Pravděpodobnost zastavení
- Algoritmická teorie informací
- Algoritmická pravděpodobnost
- Komprese dat
Teorie složitosti
- Poradenství (složitost)
- Amortizovaná analýza
- Protokol Arthur – Merlin
- Nejlepší a nejhorší případy
- Zaneprázdněný bobr
- Složitost obvodu
- Konstruktivní funkce
- Cookova věta
- Exponenciální čas
- Funkční problém
- Lineární čas
- Věta o lineárním zrychlení
- Přirozený důkaz
- Polynomiální čas
- Polynomiální časová redukce jedna
- Polynomiálně-Turingova redukce
- Savitchova věta
- Věta o vesmírné hierarchii
- Rychlost před
- Věta o zrychlení
- Subkvadratický čas
- Věta o časové hierarchii
Třídy složitosti
Pojmenované problémy
- Clique problém
- Hamiltoniánský cyklus
- Problém hamiltonovské cesty
- Faktorizace celého čísla
- Problém s batohem
- Problém uspokojivosti
- Problém se součtem podmnožiny
- 3SUM
- Problém obchodního cestujícího
- Problém s vrcholovým krytem
- Jednosměrná funkce
- Nastavit problém s krytem
- Problém nezávislé množiny
Rozšíření
- Pravděpodobnostní algoritmus, randomizovaný algoritmus
- Algoritmus Las Vegas
- Nedeterminismus
- Nedeterministický Turingův stroj
- Interaktivní výpočet
- Interaktivní kontrolní systém
- Pravděpodobný Turingův stroj
- Aproximační algoritmus
- Simulované žíhání
- Algoritmus kolonie mravenců
- Sémantika hry
- Zobecněná hra
- Systém více agentů
- Parametrizovaná složitost
- Zpracovat kalkul
- Hyperpočítání
- Skutečný výpočet