Vladan Majerech - NTIN090 Základy složitosti a vyčíslitelnosti
Last Modified: 3.2.2023
Index
zápočtové příklady, odkazy, cvičení 1 , cvičení 2 , cvičení 3 , cvičení 4 , cvičení 5 , cvičení 6
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). Cvičím v pondělí liché i sudé týdny. Úkoly jsou zadávány brzy po prvním cvičení a termín na jejich odevzdání je do počátku cvičení 14 dní po druhém cvičení. Za domácí úkoly vypracované v termínu je možno získat plný počet uvedených bodů. 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ů. Všichni byste měli dostat e-mailem odkaz na Google doc, z nějž by měly být přístupné nahrávky cvičení. Pokud jste jej nedostali, kontaktujte mne e-mailem.
Zápočtové příklady
| kód | Body | Termín odevzdání | Zadání | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| reset | 3 | 26.10.2022 | Ukažte, jak lze libovolný jednopáskový Turingův stroj $M$ převést na Resetovací (jednopáskový) stroj $M'$, který se od Turingova stroje liší tím, že přechodová funkce neumožňuje pohyb doleva o jedno políčko, ale pouze pohyb na začátek (jednostranně nekonečné) pásky. | |||||||||
| $\exists\forall$ | 3 | 9.11.2022 | Ukažte, že jazyk $L$ je rozhodnutelný, právě když existují rozhodnutelné jazyky $A$ a $B$, pro které platí, že $L=\{x\;|\;(\exists y)[\langle x, y\rangle\in A]\}= \{x\;|\;(\forall y)[\langle x, y\rangle\in B]\}$ | |||||||||
| reg | 1 | 23.11.2022 | Nechť $B$ je jazyk přijímaný konečným automatem a nechť $A$ je jazyk pro nějž $A\le_m B$. Je $A$ regulární? Proč? | |||||||||
| size | 2 | 23.11.2022 | Je jazyk $\hbox{Size}=\{\langle M,k\rangle\mid |L(M)|\ge k\}$ rozhodnutelný? Je částečně rozhodnutelný? | |||||||||
| inkluze | 3 | 7.12.2022 |
O kterých inkluzích mezi následujícími dvojicemi tříd jste schopni dokázat,
že platí a o kterých, že neplatí.
Za každý dokázaný vztah je jeden bod
(do požadovaného počtu bodů započítáno za 3).
| |||||||||
| 3Dvěže | 3 | Dokažte, že je NP úplné zjistit, zda je možno do 3D šachovnice $k\times\ell\times m$ umístit $k\cdot\ell$ věží tak, aby se navzájem neohrožovaly. Přitom jsou některá políčka označena kaňkou a na tato políčka je zakázáno umístit věž. Věž na políčku $(x,y,z)$ ohrožuje všechna políčka, která se od $(x,y,z)$ liší právě v jedné souřadnici. |
V následující tabulce je uveden aktuální stav získaných bodů jednotlivých studentů.
| Id studenta | celkem | detail |
|---|---|---|
| A | 13 | reset(3), $\exists\forall$(3), reg(1), size(2), inkluze(4) |
| B | 13 | reset(3), $\exists\forall$(3), reg(1), size(2), inkluze(4) |
| C | 10 | reset(3), $\exists\forall$(3), reg(1), size(1), inkluze(2) |
| D | 3 | reset(3), $\exists\forall$(0) |
| E | 10.5 | reset(3), reg(1) size(2), inkluze(3), $\exists\forall$(3/2) |
| F | 10.75 | reset(3/2), $\exists\forall$(3/2), reg(1), size(1.5+0.5/2), inkluze(5) |
| G | 13 | reset(3), $\exists\forall$(1), reg(1), size(2), inkluze(6) |
| H | 11 | reset(3), $\exists\forall$(2), reg(1), size(2), inkluze(3) |
| B | 9 | reset(3), $\exists\forall$(3), reg(1), size(2) |
| I | 11.5 | reset(3), $\exists\forall$(2+1/2), reg(1), inkluze(5) |
| J | 11.5 | reset(3), $\exists\forall$(3), reg(1), size(2), inkluze(5/2) |
| K | 10.5 | reset(3/2), $\exists\forall$(3), reg(1), inkluze(5) |
Odkazy na obdobné stránky
Cvičení Petra Kučery, Petra Gregora a moje loňská.
Cvičení 1
Na první verzi 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. Definovali jsme i nedeterministické stroje. Na první verzi cvičení jsme se letmo věnovali počáteční konfiguraci, daleko víc nás zajímal průběh výpočtu, ani jsme se nevěnovali tomu, jak je definován konec výpočtu. Definovali jsem časovou a prostorovou složitost. Na druhé verzi cvičení jsme okrajové podmínky zmínili.
Kvůli různým definicím prostorové složitosti jsme probrali věty o lineární kompresi a následně i o lineárním zrychlení (po počátečním zdržení $(1+\varepsilon)n$). Dále jsme se zabývali možností redukce počtu pásek 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)$. Zmínili jsme konstrukci univerzálního stroje.
Následně jsme se chvíli věnovali problému jednostranně nekonečné pásky. Pak na prvním cvičení problému 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 akci). Na prvním cvičení jsme se také zabývali problémem děrné pásky, tedy situací, kdy na pásku můžeme zapisovat nejvýše jednou.
Cvičení 2
Nejprve jsme se zabývali vzájemným vztahem Turingových strojů a RAM. U RAM jsme museli stanovit nekonstantní čas pro jednotlivé operace, abychom mohli RAM simulovat na TS s polynomiálním zpomalením.
Pak jsme si definovali základní pojmy jako abeceda, slovo jazyk, věnovali se určení velikosti příslušných množin. Abeceda je konečná, množina slov je spočetná (ukázali jsme jak očíslovat slova nad abecedou velikosti 2, a obdobně pro jiné velikosti). Následně jsme ukázali, že množina jazyků (nad danou abecedou) je nespočetná (připomněli jsme si Cantorovu diagonalizaci). Pak jsme si ukázali, že množina Turingových strojů je spočetná (každému stroji jsme přiřadili přirozené číslo tak, že z čísla bylo možno stroj rekonstruovat, takže šlo o zobrazení prosté) ve skutečnosti bylo přiřazení takové, že pro každý stroj existuje spočetně mnoho čísel jejichž dekódováním dostaneme stroj který bude pracovat zcela stejně jako původní stroj. Některým číslům neodpovídají funkční stroje. Každé takovéto konstrukci říkáme Goedelovo číslování strojů. Jazyk $i$-tého stroje běžne značíme $L_i$. Následně jsme Goedelovo číslování strojů použili v diagonalizaci prokazující nespočetnost množiny jazyků, abychom definovali jazyk $K=\{w_i\mid w_i\not\in L_i\}$, který není přijímán žádným strojem (není rekurzivně spočetný).
Dále jsme si pro účely cvičení definovali bylo „disjunktní sjednocení“ $\oplus$. Dále jsme pracovali s pojmem $\leq_m$ převeditelnosti. Ukázali jsme si $A\leq_m A\oplus B$ i to, že z $A\leq_m C$ a $B\leq_m C$ plyne $A\oplus B\leq C$. Ke konci jsme si ukázali, že z $A\leq_m \overline{A}$ pro rekurzivně spočetný jazyk $A$ a jeho doplněk $\overline{A}$ plyne jeho rekurzivnost (je přijímán strojem, který se vždy zastaví).
Cvičení 3
Nejprve jsme se věnovali uzavřenosti částečně rekurzivních respektive rekurzivních množin na základní jazykové operace (ale třeba negaci jsme neřešili). Pak jsme se věnovali jazyku $J=L_u\oplus \overline{L_u}$, dále jsme převáděli $L_u$ na $EQ=\{\langle M,N\rangle\mid L_M=L_N\}$ a $Infinite=\{M\mid |L_M|=\omega\}$. Na konci hodiny jsme si připomněli postův korespondenční problém a převáděli jsme $L_u$ na něj.
Cvičení 4
Věnovali jsme se vzájemnou simulací programů s různými omezeními prostředků (N/)(Space/Time). Řekli jsme si metavětu pro simulaci prostorově omezených výpočtů i metavětu pro simulaci (nedeterministických) časově omezených výpočtů. Pak jsme se věnovali především programům na procházení grafů v závislosti na tom, jak máme omezené prostředky. Na konci jsme dokazovali věty o hierarchii (Žákova byla zmíněna, ale ne zformulována).
Cvičení 5
Věnovali jsme se NP-úplnosti. Připomněl jsem techniku převádění na SAT tím, že ukážeme že jsme schopni modelovat booleovské proměnné a jejich negace a jsme schopni vytvářet nezávislé klauzule. Předvedli jsme to na testování tripartitnosti grafu a zjišťování existence hamiltonovské kružnice na orientovaném grafu s velmi omezenými stupni (rovinný, bipartitní, stupně v partitách (in1+out2/in2+out1).
Cvičení 6
Věnovali jsme se především P# a úplnosti problému permanent 01 matice. Zmínil jsem souvislost s pravděpodobnostní třídou PP. Pak jsem ještě ukázal jednu NPC konstrukci.