• 1. Nejprve se na tomto odkazu zaregistrujte do online simulátoru.
  2. Poté informujte vyučujícího a bude vám vygenerováno zadání příkladu, které uvidíte na odkazu "Online zápočty"
  3. Zadání vyřešte na offline Turingově stroji, viz "Simulátor Turingova stroje ke stažení"
  4. Následně nahrajte textový soubor s pravidly stroje v online simulátoru přes odkaz "Online zápočty"
  5. Pokud je stroj v pořádku, uvidíte své jméno v seznamu úspěšných řešitelů; v opačném případě opakujte kroky 3 a 4
• Upozornění: při použití vícepáskového stroje musí být vystup i výstup umístěn na první pásce!

Pojem mechanický výpočet označuje proces, který probíhá samočinně podle předem stanovené posloupnosti kroků. Nemusí být nutně prováděn mechanickým strojem, i když první počítače mechanické byly. Vývoj výpočetních strojů ve 20. století vyprovokoval řadu otázek týkajících se limitů jejich schopností.

Původní představy, že počítače mohou vyřešit jakýkoli matematický nebo fyzikální problém, byly vyvráceny už v prvních dekádách 20. století. Pro zodpovězení této otázky vznikla ve 20. století celá řada matematických modelů výpočtu, ovšem ukázalo se, že všechny řeší tutéž třídu úloh, přičemž řada úloh zůstává neřešitelných. Turingova-Churchova teze tvrdí, že třída řešitelných úloh je stejná pro všechny počítače, které můžeme zkonstruovat.

Postupně se pro svou jednoduchost a praktičnost etabloval jako matematický model výpočtu tzv. Turingův stroj. V poslední době sílí snahy o jeho modernizaci nebo nahrazení jiným modelem. Původní představy totiž nepočítaly s propojenými sítěmi typu Internet, které dovolují počítačům nepředvídatelně komunikovat a neustále se vyvíjet. Tyto vlastnosti zvětšují výpočetní potenciál počítačové sítě jako celku.

Turingův stroj se v literatuře vyskytuje v několika variantách, jež se však neliší svou výpočetní silou. Jinými slovy, každá z variant může simulovat kteroukoli jinou, byť někdy za cenu zpomalení nebo větší spotřeby paměti (pásky). Existence více variant je užitečná: když chceme činnost stroje popsat matematicky, je výhodné použít co nejjednodušší variantu. Naopak když ukazujeme, že stroj zvládne jistý algoritmus, je pohodlné použít variantu s mocnějšími operacemi, jako např. vícepáskový stroj.

Univerzální Turingův stroj může simulovat činnost kteréhokoli jiného Turingova stroje. Jeho existence spolu s Turingovou-Churchovou tezí dává důležitý důsledek: je-li počítač schopen simulovat Turingův stroj, pak může simulovat i kterýkoli jiný počítač.

Vstup: 1. páska = n jedniček

Výstup: 2. páska, n! jedniček

Krokujte stroj a všímejte si, jakým způsobem funguje, sledujte dílčí procedury v průběhu výpočtu, jako např. násobení.

d(0, , )=(99, , ,1, )
d(0,1, )=(1, ,R,1, )
d(1, ,1)=(10, , ,1,R)
d(1,1,1)=(2,1, ,x,R)
d(2,1, )=(3,1, ,0,L)
d(2,1,?)=(2,1, ,?,R)
d(3,1,0)=(3,1, ,0,L)
d(3,1,1)=(4,1, ,1,L)
d(4,1,1)=(4,1, ,1,L)
d(4,1,x)=(1,1, ,x,R)
d(3,1,x)=(5,1, ,1,L)
d(5,1,x)=(5,1, ,1,L)
d(5,1, )=(1,0,R, ,R)
d(10, ,1)=(10, , ,1,R)
d(10, ,0)=(10, , ,1,R)
d(10, , )=(11, , , ,L)
d(11, ,1)=(11, , ,1,L)
d(11, , )=(12, ,L, ,R)
d(12, ,1)=(99, , ,1, )
d(12,0,1)=(13,1,L,1, )
d(13,0,1)=(13,1,L,1, )
d(13, ,1)=(13, ,R,1, )
d(13,1,1)=(1, ,R,1, )

Rozhodovací problém je množina otázek (případů) s odpověďmi ANO/NE. Každý rozhodovací problém se dá popsat (charakterizovat) nějakým formálním jazykem. Tento jazyk obsahuje popisy všech případů problému s odpovědí ANO.

Jazyk je rekurzívně spočetný, je-li přijímán nějakým Turingovým strojem (takových strojů může být více). Pokud existuje Turingův stroj, který jazyk přijímá a který se zastaví pro jakýkoli vstup (i tehdy, když nedojde do koncového stavu), nazývá se jazyk rekurzívní. Každý rekurzívní jazyk je i rekurzívně spočetný, obráceně to platit nemusí.

Intuitivně nazveme problém rozhodnutelným, jestliže existuje algoritmus, který umí správně zodpovědět (rozhodnout) každý jeho případ. To je ekvivalentní požadavku, aby jazyk charakterizující problém byl rekurzívní. Proto je pro nás důležité studovat vlastnosti rekurzívních a rekurzívně spočetných jazyků.

Existují jazyky, které nejsou rekurzívně spočetné, dokonce je jich velké množství. Existence aspoň jednoho takového jazyka označeného , který není akceptován žádným Turingovým strojem, se dá dokázat sporem, tzv. diagonalizační metodou. Název metody vychází z použití rovinného grafu s dvěma kolmými osami.  Na jednu osu umístíme všechny Turingovy stroje a na druhou osu jejich vstupní slova. Budeme (mylně) předpokládat, že existuje Turingův stroj přijímající  a na diagonále (úhlopříčce) grafu dojdeme k logickému paradoxu, čili sporu. Tím je předpoklad vyvrácen, tedy jazyk  skutečně není rekurzívně spočetný.

Rozhodovací problém definujeme jako množinu případů, které lze chápat jako otázky s odpovědí ano/ne. Každý případ se musí dát popsat/zakódovat slovem nad nějakou pevně zvolenou abecedou. Problém je potom charakterizován jazykem obsahujícím slova - případy s odpovědí ano. Problém je algoritmicky rozhodnutelný, je-li tento jazyk rekurzívní.

Z výsledků předchozího tématu plyne, že řada problémů je nerozhodnutelných. K důkazu jejich (ne)rozhodnutelnosti není nutno užívat vždy diagonalizační metodu, která může být pracná. Bývá jednodušší použít metodu redukce. Redukce je vlastně zobrazení R jednoho problému do druhého (připomeňme, že problémy jsou množiny případů). Přitom odpověď ano/ne na každý případ x prvního problému musí být shodná jako odpověď na redukovaný případ R(x) druhého problému. Říkáme, že případy x a R(x) jsou ekvivalentní. Potom každý algoritmus rozhodující redukovaný problém vlastně rozhoduje i problém původní.

Riceho věta říká, že když zvolíme jakoukoli netriviální vlastnost, pak je nerozhodnutelné, zda jazyk akceptovaný nějakým Turingovým strojem tuto vlastnost má nebo ne. Poměrně snadno lze pomocí redukce tuto nerozhodnutelnost rozšířit i na jiné aspekty chování Turingových strojů, například zda mohou dojít do určitých konfigurací, vydat na výstup určité hodnoty a podobně. Vzpomeňme, že podle Turingovy-Churchovy teze se dá každý počítač s libovolným programem simulovat Turingovým strojem. Pak z Riceho věty vyplývá, že všechny netriviální aspekty chování počítačů a počítačových programů jsou nerozhodnutelné. To má dalekosáhlé důsledky pro ladění a testování software.

V kapitole 2 (skripta prof. Černá) jsme se seznámili s několika problémy různé složitosti, která je dána časem potřebným k vyřešení problému. Ten je intuitivně dán rychlostí nejrychlejšího sekvenčního algoritmu, který umí problém vyřešit. Který algoritmus je ale ten nejrychlejší? Co když pro některé případy téhož problému je nejrychlejší algoritmus A a pro jiné algoritmus B?

Abychom porovnali rychlost dvou (nebo více algoritmů), budeme brát za rozhodující, jak se budou chovat pro vstupy zvětšujících se délek, tj. případy rostoucí velikosti. Jinými slovy, jak rychle roste čas výpočtu braný jako funkce délky vstupu algoritmu.

Asymptotiky představují matematický nástroj pro porovnávání rychlosti růstu funkcí. Při takovém srovnání dvou funkcí f(n) a g(n) (jejichž definičním oborem jsou přirozená čísla) nás zajímá jejich chování pro hodnoty argumentů n≥n₀, tedy od n₀ do nekonečna. Malé hodnoty argumentu n<n₀ ignorujeme. Přitom hranici n₀ si můžeme zvolit sami. Její význam je v tom, abychom oddělili počáteční část definičního oboru, kde se funkce může chovat atypicky, od zbytku, kde by její růst měl být stabilní. Výsledek srovnání, zjednodušeně řečeno, závisí na tom, jak se vyvíjí poměr f(n)/g(n) pro neomezeně rostoucí argument n: zda klesá k nule, nebo se blíží k nějaké konstantě, nebo zda jde k nekonečnu.

Časová složitost algoritmu je funkce, jejímž argumentem je velikost vstupu (v bitech), a hodnotou funkce je počet kroků algoritmu. Samozřejmě pro různé vstupy téže velikosti může algoritmus pracovat různě dlouho: rozhodující je nejhorší případ, pro který výpočet trvá nejdelší dobu.

Časovou složitost problému pak definujeme jako časovou složitost nejrychlejšího algoritmu (Turingova stroje) schopného tento problém rozhodovat. (Nejrychlejší algoritmus je ten, jehož časová složitost je dána nejpomaleji rostoucí funkcí.) Analogicky je tomu u prostorové složitosti.

Složitostní třída DTIME(f(n)) je množina všech problémů, jejichž časová složitost je nejvýše f(n). (Hm, přísně vzato to není množina, ale v tomto předmětu se nic nestane, když ji budeme za množinu považovat)

Z toho plyne, že jestliže máme dvě třídy DTIME(f(n)) a DTIME(g(n)), a platí, že f(n) ≤ g(n), pak DTIME(f(n)) ⊆
DTIME(g(n)): každý problém, který umíme vyřešit v čase f(n), je možné vyřešit taky v delším čase g(n).

Analogicky pak zavedeme i složitostní třídu pro prostor DSPACE(f(n)). Zde je třeba dát pozor na to, že do spotřeby paměti Turingova stroje se nezapočítává délka vstupu a výstupu na speciální vstupní a výstupní pásce.

Speciální význam má nedeterministický Turingův stroj, který zavádí koncepci nedeterministického výpočtu: stroj může v každém kroku náhodně vybírat z více aplikovatelných pravidel. V důsledku toho mohou některé výpočty s tímtéž vstupem být akceptující a jiné zamítající. Vstup x je strojem akceptován tehdy, jestliže pro něj existuje alespoň jeden akceptující výpočet. Přitom ale spotřebovaný čas není brán jako součet všech možných výpočtů (kterých může být exponenciálně mnoho), ale jako čas nejdelšího z nich. Tím pádem je nedeterministický stroj zvýhodněn oproti deterministickému, který by musel při jeho simulaci projít postupně všechny možné výpočty, a přitom spotřeboval exponenciálně delší čas. Proto platí pro libovolnou funkci f(n):

DTIME(f(n)) ⊆ NTIME(f(n)) ⊆ DTIME(2^f(n))

Deterministický stroj je vlastně speciálním případem nedeterministického, když v každém kroku existuje právě jedno aplikovatelné pravidlo. Přestože v praxi většinou používáme deterministické algoritmy, mají nedeterministické Turingovy stroje v teorii složitosti velký význam. Jen ony dovolují přesně charakterizovat skupinu v praxi velmi důležitých tzv. NP-úplných problémů, pro které se neví, jak rychle je lze řešit deterministickými algoritmy.

Pro určení časové složitosti (času výpočtu v nejhorším případě) běžných počítačových programů si musíme všímat programových konstrukcí jako jsou podmínky, cykly a vzájemné volání funkcí, zejména rekurzívní. Výpočty času u jednoduchých nebo vnořených cyklů se provádějí většinou pomocí (vícenásobných) sum, výpočet často vede na aritmetickou nebo geometrickou řadu. Problémem mohou být cykly while, kde je někdy obtížné určit počet opakování.

U rekurzívních funkcí se čas výpočtu zapíše pomocí speciální soustavy rovnic, tzv. rekurence. K jejímu vyřešení existuje v literatuře (např. Graham, Knuth, Patashnik: Concrete mathematics) řada speciálních metod. Nejjednodušší a často použitelnou metodou je opakované vzájemné dosazování rekurentních rovnic, anebo tzv. Mistrovská metoda (Master method). 

Z praktického hlediska je nejdůležitější identifikovat programy nebo metody, jejichž délka výpočtu roste exponenciálně vzhledem k některému vstupnímu parametru. Takové programy mohou být výpočetně nezvládnutelné už pro poměrně nízké hodnoty parametrů.

Cílem studia složitosti výpočtů je rozdělit úlohy řešené na počítačích do několika kategorií (složitostních tříd) podle jejich časové a paměťové náročnosti. Cesta k tomu vede přes zdánlivě kontra-intuitivní výsledek, že čas výpočtu na Turingově stroji a spotřebu políček pásky je možné urychlit libovolnou konstantou.

Urychlení stroje a komprese pásky se dosahuje rozšířením páskové abecedy, kdy například na jedno políčko umístíme informace ze dvou původních. To v praxi odpovídá rozšíření délky operandů instrukce v mikroprocesoru. Jestliže instrukce pracuje např. s 64-bitovými operandy namísto 32-bitových, lze v jednom kroku zpracovat dvojnásobně více informace.

U prostorové složitosti lze takto neomezeně snižovat spotřebu políček pracovních pásek (když nepočítáme obsah vstupní a výstupní pásky). U časové složitosti požadujeme, aby stroj vždy přečetl celý obsah vstupní pásky, a proto nemůže vykonat méně kroků, než je délka vstupu.

Věta o urychlení nám říká, že například třída DTIME(n^k) je totožná se všemi třídami DTIME(f(n)), kde f(n) je libovolný polynom k-tého stupně. Obdobný vztah platí i pro prostorovou složitost. Vidíme také, že násobení konstantou u složitostních tříd nehrají žádnou roli.

Pro rozdělení problémů na zvládnutelné, tj. řešitelé na počítači v rozumném čase (paměti), a nezvládnutelné budeme považovat za klíčové, zda výpočet probíhá v logaritmickém, polynomiálním či exponenciálním čase (prostoru). Tím dospějeme k definici základních složitostních tříd jako P, NP, LOGSPACE, PSPACE a dalších.

Z praktického hlediska jsou nejdůležitější třídy P, NP, PSPACE. Několik známých problémů z těchto tříd:

• Třída P
• veškeré vyhledávací a třídicí algoritmy (v poli, v souborech a v databázích) 
• řada grafových algoritmů (hledání [nejkratších] cest mezi dvěma vrcholy, souvislost grafu, planarita grafu a další - aplikace v sítích všeho druhu, jízdní řády, doprava...) 
• vyhledávání vzorku v textu s případnými mutacemi (aplikace: antivirová analýza s pomocí virové databáze)
• test na prvočíselnost, nalezení největšího společného dělitele (aplikace: šifrování)
• lineární programování (jednoduché optimalizační problémy s lineární účelovou funkcí a omezujícími podmínkami) 
• příslušnost slova do regulárního nebo bezkontextového jazyka (aplikace: kompilátory)
• LZW kompresní algoritmus a další (aplikace: gzip, rar...)

• Třída NP
• problém obchodního cestujícího a jeho aplikace v dopravních problémech
• mnoho dalších grafových problémů (k-klika, k-nezávislá podmnožina, vrcholové barvení...)
• velká většina optimalizačních problémů (plnění batohu, vytěžování vozidel, optimalizace výroby, problém čínského pošťáka, všechny problémy kvadratického programování...)
• nejdelší společné podslovo v množině slov (aplikace: analýza DNA, proteinů)
• mnohé hry jako sudoku,tetris, Rubikova kostka...
• Třída PSPACE
• splnitelnost výrokové formule s kvantifikátory
• příslušnost slova do kontextového jazyka (aplikace: analýza přirozených jazyků)
• řada problémů automatického plánování a rozvrhování, např. nalezení nejjednoduššího plánu
• řada grafových problémů, např. týkajících se routingu na Internetu
• mnohé hry jako dáma, piškvorky, Super Mario Bros...

Pozoruhodný a v teoretické informatice naprosto ojedinělý fakt je, že v této hierarchii tříd je dodnes mnoho základních problémů otevřených. Neumíme dokázat, zda mezi deterministickými a nedeterministickými časovými třídami (např. P a NP) je měřitelný rozdíl. Obdobná situace je v porovnání času a prostoru (např. P a PSPACE). Na vyřešení těchto problémů jsou vypsány finanční prémie v řádu miliónu dolarů. Pokud by se ukázalo, že P=NP, mělo by to v IT obrovský dopad na řešení výpočetně obtížných problémů.

Redukce je základním nástrojem pro porovnání složitosti dvou problémů. S redukcí jsme se už setkali v souvislosti s vyčíslitelností problémů. Víme, že redukce konstruuje z případů jednoho problému ekvivalentní případy druhého problému. V této kapitole navíc požadujeme, aby tato konstrukce proběhla v polynomiálním čase. Redukce je základem pro definici třídy tzv. C-úplných problémů, kde C je složitostní třída. 

Nejdůležitější fakta k zapamatování (C je některá z tříd P, NP, EXPTIME, NEXPTIME, PSPACE):

• A ≤ B intuitivně znamená, že problém B je nejméně tak těžký jako A
  
• pokud A ≤ B, a problém B patří do třídy C, tak i problém A patří do třídy C
  
• každý C-těžký problém je nejméně tak těžký jako kterýkoli problém ve třídě C
  
• C-těžký problém ale sám do třídy C patřit nemusí (může patřit do větší třídy obsahující C)
• pokud A ≤ B, a A je C-těžký, tak i B je C-těžký
  
• pokud C-těžký problém patří do třídy C, tak je C-úplný
  
• C-úplné problémy jsou ty nejtěžší ve třídě C, a jsou všechny vzájemně redukovatelné
  
• když chceme ukázat o nějakém problému B ze třídy C, že je C-úplný, tak stačí vzít vhodný C-úplný problém A a sestrojit redukci A ≤ B

Největší praktický význam má třída NP-úplných problémů, kam patří velké množství v praxi řešených problémů (optimalizační, dopravní, síťové...). Nejznámějšími reprezentanty jsou problém SAT a HAM (známý též jako problém obchodního cestujícího). Příklady dalších NP-úplných problémů naleznete v tématu "Základní složitostní třídy".

Všechny NP-úplné problémy se v praxi považují za nezvládnutelné - na počítači jsme většinou schopni najít jen jejich přibližná řešení, přesná řešení jsou příliš výpočetně náročná.

Existuje početná skupina problémů (často založených na rekurzi), které vyžadují rozdělit problém na části, a jejich řešení využít pro výpočet celkového řešení. Přitom se často zdá, že množství nutných výpočtů (rekurzívních volání) roste exponenciálně s velikostí zadání, a že tedy problém je NP-těžký. Ve skutečnosti tomu ale tak není: stačí si všimnout, že mnoho částečných řešení se počítá opakovaně, a jejich celkový počet je jen polynomiální. Dynamické programování je obecná strategie, kdy místo rekurzívního algoritmu postupně vypočítáváme řešení podproblémů od nejmenších k větším, a mezivýsledky ukládáme, až se dostaneme k výpočtu původního zadání.

Typickým příkladem je výpočet Fibonacciho posloupnosti, kde je tento princip názorně předveden.