Vladan Majerech - NTIN090 Základy složitosti a vyčíslitelnosti
Last Modified: 25.2.2024
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). Úkoly budou zadávány brzy po první verzi cvičení a termín na jejich odevzdání je u úkolu explicitně uveden (vždy 9:00). (Jedná se o počátek cvičení 14 dní po počátku třetí verze cvičení). Vzhledem k rektorskému dni 2.11.2023 se mění číslování cvičení a třetí verze cvičení už nebude páteční, ale čtvrteční. 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ů.
Zápočtové příklady
| kód | Body | Termín odevzdání | Zadání | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| reset | 3 | 27.10.2023 | 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 | 10.11.2023 | 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]\}$. | |||||||||
| size | 3 | 30.11.2023 | Je jazyk $\hbox{Size}=\{\langle M,k\rangle\mid |L(M)|\ge k\}$ rozhodnutelný? Je částečně rozhodnutelný? | |||||||||
| inkluze | 3 | 14.12.2023 |
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 |
|---|---|---|
| b | 3 | reset(3), $\forall\exists$(0), size(0) |
| c | 9 | reset(3), $\forall\exists$(3), size(2), inkluze(0), 3Dvěže(1) |
| l | 6 | reset(1+1/2), $\forall\exists$(3), size(3/2) |
| q | 8.5 | reset(3), $\forall\exists$(0+3/2), size(3), inkluze(4) |
| v | 7 | reset(3), $\forall\exists$(2), size(1), inkluze(1) |
| x | 3 | reset(3), $\forall\exists$(0), size(0) |
| Á | 7.5 | reset(3), $\forall\exists$(1), inkluze(2), size(3/2), 3Dvěže(0) |
| Í | 9 | reset(3), $\forall\exists$(2), size(2), inkluze(2), 3Dvěže(0) |
| Ĺ | 5 | $\forall\exists$(1), size(0), inkluze(4) |
| A | 15 | reset(3), $\forall\exists$(3), size(3), inkluze(6) |
| B | 11 | reset(3), $\forall\exists$(3), size(3), inkluze(2) |
| C | 14 | reset(3), $\forall\exists$(3), size(3), inkluze(5) |
| D | 10 | reset(3), $\forall\exists$(3), size(1), inkluze(4) |
| E | 11 | reset(3), $\forall\exists$(3), size(3), inkluze(2) |
| F | 15 | reset(3), $\forall\exists$(3), size(3), inkluze(6) |
| G | 14 | reset(3), $\forall\exists$(3), size(1+2/2), inkluze(6) |
| H | 14.5 | reset(3), $\forall\exists$(2+1/2), size(3), inkluze(6) |
| I | 11 | reset(3, $\forall\exists$(3), size(3), inkluze(2) |
| J | 13.5 | reset(3), $\forall\exists$(2.5), size(3), inkluze(5) |
| K | 13 | reset(3), $\forall\exists$(3), size(3), inkluze(4) |
| L | 12 | reset(3), $\forall\exists$(3), size(3), inkluze(3) |
| M | 11 | reset(3), $\forall\exists$(3), size(3), inkluze(2) |
| N | 10 | reset(3), $\forall\exists$(3), size(3), inkluze(1) |
| O | 13 | reset(3), $\forall\exists$(3), size(3), inkluze(4) |
| P | 14 | reset(3), $\forall\exists$(3), size(3), inkluze(5) |
| Q | 10.5 | reset(3), $\forall\exists$(3), size(3/2), inkluze(2+2/2) |
| R | 11.5 | reset(3), $\forall\exists$(3), size(2+1/2), inkluze(3) |
| S | 13 | reset(3), $\forall\exists$(3), size(3), inkluze(4) |
| T | 12 | reset(3), $\forall\exists$(3), size(3), inkluze(3) |
| U | 10 | reset(3), $\forall\exists$(1+2/2), size(2), inkluze(3) |
| V | 11 | reset(3), $\forall\exists$(3), size(3), inkluze(2) |
| W | 11 | reset(3), $\forall\exists$(2), size(3), inkluze(3) |
| X | 10 | reset(2+1/2), $\forall\exists$(3), size(3), inkluze(1.5) |
| Y | 12 | reset(3), $\forall\exists$(3), size(3), inkluze(3) |
| Z | 10 | reset(3), $\forall\exists$(1+2/2), size(2), inkluze(3) |
| a | 11 | reset(3), $\forall\exists$(3), size(0+3/2), inkluze(5/2) |
| d | 10 | reset(2), $\forall\exists$(3), size(2), inkluze(3) |
| e | 13 | reset(3), $\forall\exists$(2), size(3), inkluze(5) |
| f | 10.5 | reset(3), $\forall\exists$(2), size(3), inkluze(5/2) |
| g | 10 | reset(3), $\forall\exists$(3), inkluze(4) |
| h | 10 | reset(0+3/2), $\forall\exists$(3), size(1), inkluze(3+3/2) |
| i | 10 | reset(3), $\forall\exists$(3), size(3), inkluze(1) |
| j | 10.5 | reset(3), $\forall\exists$(2+1/2), inkluze(5) |
| k | 10.5 | reset(3), $\forall\exists$(3), inkluze(3), size(3/2) |
| m | 10 | reset(3), size(2), inkluze(2+1/2), $\forall\exists$(3/2), 3Dvěže(1) |
| o | 15 | reset(3), $\forall\exists$(3), size(3), inkluze(6) |
| p | 12 | reset(3), $\forall\exists$(3), size(3), inkluze(3) |
| r | 11 | reset(3), $\forall\exists$(3), size(3), inkluze(2) |
| s | 12 | reset(3), size(3), inkluze(9) |
| t | 10.5 | reset(3), $\forall\exists$(3), size(3), inkluze(3/2) |
| u | 15 | reset(3), $\forall\exists$(3), size(3), inkluze(6) |
| w | 12 | reset(3), $\forall\exists$(1), size(3), inkluze(5) |
| y | 10 | reset(3), $\forall\exists$(2), size(0), inkluze(5) |
| z | 10 | reset(3), $\forall\exists$(2), size(3), inkluze(2) |
| Č | 11 | reset(3), $\forall\exists$(3), size(3), inkluze(2) |
| Ď | 10.5 | reset(3/2), $\forall\exists$(3), size(3), 3Dvěže(3) |
| É | 10.5 | reset(3/2), $\forall\exists$(3), size(2/2), inkluze(5) |
| Ě | 11 | reset(0/2), $\forall\exists$(3), size(1+2/2), inkluze(6) |
Odkazy na obdobné stránky
Cvičení Petra Kučery, moje loňská.
Cvičení 1
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. Odhadli jsme počet možných konfigurací stroje s omezenou prostorovou složitostí pro pevný vstup (stroje bez výstupních pásek).
Kvůli různým definicím prostorové složitosti jsme na druhé a třetí verzi cvičení probrali věty o lineární kompresi a zrychlení (větší abeceda, taneček na získání potřebných informací na provedení r kroků na 6 (resp. 3), pozor na vstupní a výstupní pásky). Na prvním a druhém cvičení jsme se dále 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, ale nezabývali jsme se redukcí abecedy.
Následně jsme se chvíli věnovali problému jednostranně nekonečné pásky. 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 akci), ale nebyl čas se mu věnovat. Na všech cvičeních jsme se 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$ na prvním cvičení jsme nestihli ukázat to, že z $A\leq_m C$ a $B\leq_m C$ plyne $A\oplus B\leq C$, ani jsme nevyřešili co plyne z předpokladu $A\leq_m \overline{A}$ pro rekurzivně spočetný jazyk $A$ a jeho doplněk $\overline{A}$ o rozhodnutelnosti $A$ (je přijímán strojem, který se vždy zastaví).
Cvičení 3
Nejprve jsme dokončili vyčíslitelnost úlohami na převod $L_u\oplus\overline{L_u}$ na $EQ=\{\langle M,N\rangle\mid L_{(M)}=L_{(N)}\}$ a převodem $L_u$ na $\hbox{Inf}=\{M\mid |L_{(M)}|=\omega\}$.
Pak jsme se zabývali třídami složitosti $\mathrm{(N)Time}(f(n))$ a $\mathrm{(N)Space}(f(n))$. Vyslovili jsme metavěty o simulaci jednak prostorově druhak časově omezeného výpočtu (zatajili jsme předpoklad konstruovatelnosti). Ukázali jsme aplikaci časové metavěty na důkaz vnoření $\mathrm{NTime}(f(n))$ do $\mathrm{Space}(f(n))$, ukázali jsme druhou aplikaci časové metavěty k tomu, že existuje nedeterministický univerzální stroj pro simulaci $\mathrm{NTime}(f(n))$ v čase $O(f(n))$. Ukázali jsme aplikaci prostorové metavěty na důkaz vnoření $\mathrm{NSpace}(f(n))$ do $\bigcup_c \mathrm{Time}(2^{c(f(n)+\log n)})$, i do $\mathrm{Space}((f(n)+\log n)^2)$. Kromě toho jsme ukázali aplikaci prostorové metavěty pro důkaz existence nedeterministicého univerzálního stoje pro simulaci $\mathrm{NSpace}(f(n))$, který se pro každý vstup zastaví a potřebuje prostor $O(f(n))$.
Na konci hodiny byl uveden jazyk dokazující věty o hierarchii pro $\mathrm{Time}$, $\mathrm{Space}$ a $\mathrm{NSpace}$. Na příští hodině se k němu vrátíme a budeme se věnovat potřebě konstruovatelnosti funkcí.
Cvičení 4
Nejprve jsme se věnovali důležitosti konstruovatelnosti funkcí včetně dokončení důkazu vět o hierarchii (Žákovu větu jsem nechal pro zájemce k samostudiu, existenci Blumovy věty jsem jen naznačil), ve zbyku hodiny jsme se věnovali NP-úplnosti.
Cvičení 5
Věnovali jsme se NP-úplnosti a aproximčním algoritmům.
Cvičení 6
Věnovali jsme se tak trochu kryptografii. Konkrétně jsme si povídali o testování prvočíselnosti a metodách faktorizace.