Vladan Majerech - NTIN090 Základy složitosti a vyčíslitelnosti
Last Modified: 9.10.2025
Index
Pro získání zápočtu z NTIN090 je potřeba získat 10 bodů (2/3 z možných bodů za domácí úkoly zadávané v průběhu semestru). Úkoly budou zadávány brzy po první verzi středečního cvičení a termín na jejich odevzdání bude u úkolu explicitně uveden (nejspíš čt 15:40). Za domácí úkoly odevzdané po termínu je možno získat nejvýš polovinu z uvedených bodů. Úkoly je možno odevzdávat opakovaně (vylepšené verze), v případě opakování nezlepšené verze by byl mírně snížen maximální získatelný počet bodů.
Na domácí úkoly letos použijeme owl. Pokud jste ode mne nedostali e-mail s linkem, tak mne kontaktujte.
Odkazy na obdobné stránky
Cvičení Petra Kučery, moje loňská.
Cvičení 1
Ve čtvrtek v S6 se nepodařilo zprovoznit kameru, takže bohužel cvičení zůstalo bez nahrávky.
Na prvním cvičení jsme se bavili o Turingových strojích. Zavedli jsme hlavně z důvodu přesnějšího měření prostorové složitosti vícepáskové stroje s rozlišenými možnostmi read/write přístupů k páskám. Zavedli jsme pojmy display, akce, krok, konfigurace. Definovali jsme i nedeterministické stroje. Definovali jsem časovou a prostorovou složitost.
Nejprve jsme se zabývali možností redukce počtu pásek (nejtěžší část při tvorbě univerzálního stroje) jak posouváním evidovaných poloh hlav po simulované široké pásce, tak posouváním obsahu pásek s udržováním simulovaných hlav na místě. Druhý postup bylo možno šikovnou organizací prázdných, poloprázdných a plných bloků exponenciálně rostoucí délky zorganizovat tak, že jeden krok byl odsimulován v amortizovaném čase $O(\log s)$. Kvůli různým definicím prostorové složitosti jsme pak probrali větu o lineární kompresi, následně i větu o lineárním zrychlení (větší abeceda, taneček na získání potřebných informací na provedení r kroků na 3, pozor na vstupní a výstupní pásky, nutná duplikace vstupní pásky vede ke zdržení $(1+\varepsilon)n$).
Také jsme odhadli počty možných konfigurací stroje s omezenou prostorovou složitostí pro pevný vstup (stroje bez výstupních pásek).
Následně jsme zmínili problém jednostranně nekonečné pásky. Na posledním cvičeních jsme se zabývali problémem děrné pásky, resp. situací, kdy na pásku můžeme zapisovat nejvýše jednou. Na všech verzích cvičení jsem zmínil problém líného hardvéráře (kdy jednotlivé kroky mohou ze změny stavu, posunu a přepsání pásky provádět nejýš 2 a později nejvýš jednu podakci), ale nebyl čas se mu věnovat.