{{predmet|Složitost II|Ondřej Čepek|TIN063}}
= Obecné informace o předmětu =
= Zápočet =
Kdo složí zkoušku získá automaticky i zápočet.
= Zkouška =
* Písemka - dokázování inkluzí mezi třídami složitosti.
* Ústní část - teoretická otázka.
== Minulé termíny ==
převzato z http://mff.modry.cz/slozitost/zkousky/zkousky_leto.txt
* [[TIN063_zkouska_2001-05-31 | 31.5.2001]]
* [[TIN063_zkouska_2002-06-19 | 19.6.2002]]
* [[TIN063_zkouska_2002-06-21 | 21.6.2002]]
* [[TIN063_zkouska_2002-06-25 | 25.6.2002]]
== Letní semestr 2004/2005 ==
* [[TIN063_zkouska_2005-05-27 | 25.5.2005 S4 8:00]]
* [[TIN063_zkouska_2005-06-02 | 2.6.2005 S5 9:00]]
* [[TIN063_zkouska_2005-06-14 | 14.6.2005 S5 9:00]]
* [[TIN063_zkouska_2005-06-15 | 15.6.2005 S5 9:00]]
* [[TIN063_zkouska_2005-06-16 | 16.6.2005 S5 9:00]]
* [[TIN063_zkouska_2005-06-22 | 22.6.2005 S3 9:00]]
* [[TIN063_zkouska_2005-06-23 | 23.6.2005 S3 9:00]]
* [[TIN063_zkouska_2005-06-29 | 29.6.2005 S3 9:00]]
= Poznámky =
== Definice potřebných výpočetních modelů ==
=== Turingův stroj ===
[[wen:turing_machine|Definice z Wikipedie]]
* Pro účely přednášky jsme rozuměli turingovým strojem pouze pětici (blank symbol se neuvádí).
=== Časová a prostorová složitost ===
* Prostorová složitost - Nechť M je DTS takový, že <math>\forall w \in \Sigma^* ; |w| = n </math> použije M při výpočtu nad vstupem <math>w</math> nejvýše S(n) buněk na pracovních páskách. Potom říkámě, že M má prostorovou složitost S(n) a že jazyk L(M) má prostorovou složitost S(n).
* Časová složitost - Nechť M je DTS takový, že <math>\forall w \in \Sigma^* ; |w| = n </math> udělá M při výpočtu nad vstupem <math>w</math> nejvýše T(n) kroků než se zastaví. Potom říkámě, že M má časovou složitost T(n) a že jazyk L(M) má časovou složitost T(n).
=== Třídy složitosti ===
* DSPACE(S(n)) - třída jazyků deterministické prostorové složitosti S(n).
* NSPACE(S(n)) - třída jazyků nedeterministické prostorové složitosti S(n).
* DTIME(T(n)) - třída jazyků deterministické časové složitosti T(n).
* NTIME(T(n)) - třída jazyků nedeterministické časové složitosti T(n).
== Věta o lineární prostorové kompresi ==
=== Znění ===
Nechť L je jazyk přijímaný k-páskovým DTS M s prostorovou složitostí S(n). Potom <math>\forall r \in \mathbb{N}^+</math> existuje k-páskový DTS M' s prostorovou složitostí <math>\left \lceil \frac{1}{r} * S(n) \right \rceil</math> přijímajicí jazyk L.
=== Důkaz ===
Popíšeme konstrukci stroje M'.
Každý symbol z <math>\Sigma_{M'}</math> kóduje uspořádanou r-tici z <math>\Sigma_M</math>. Jeden krok stroje M je simulován jedním krokem stroje M'. Přičemž stavy řídící jednotky M' si pamatují na kterém symbolu aktuální r-tice je hlava simulovaného stroje.
a) k = 1. Stroj s jednou vstupní (READ ONLY) a jednou výstupní (WRITE ONLY) páskou.
* Pásková abeceda: uspořádané r-tice páskových symbolu stroje M.
* Stavy: <math>q_i</math> převedeme na <math>q_i^l; \forall 1 \le l \le r</math>.
* Přechodová funkce
** Bez pohybu hlavy: <math>\delta_M(q_i,z,a) \rightarrow (q_j,b,N)</math> převedeme na <math>\delta_{M'}(q_i^l,z,x^l) \rightarrow (q_j^l,y^l,N)</math> <math>\forall l; 1 \le l \le r</math> a <math>\forall (x^l,y^l)</math> kde <math>x^l</math> koduje slovo na jehož l-té pozici je <math>a</math> a <math>y^l</math> kóduje slovo na jehož l-té pozici je b.
** Pohyb hlavy doprava: <math>\delta_M(q_i,z,a) \rightarrow (q_j,b,R)</math> převedeme na
***<math>\delta_{M'}(q_i^l,z,x^l) \rightarrow (q_j^{l+1},y^l,N)</math> <math>\forall l; 1 \le l \le r-1 </math>
***<math>\delta_{M'}(q_i^r,z,x^l) \rightarrow (q_j^1,y^l,R)</math>
** Pohyb hlavy doleva: <math>\delta_M(q_i,z,a) \rightarrow (q_j,b,L)</math> převedeme na
***<math>\delta_{M'}(q_i^l,z,x^l) \rightarrow (q_j^{l-1},y^l,N)</math> <math>\forall l; 2 \le l \le r </math>
***<math>\delta_{M'}(q_i^1,z,x^l) \rightarrow (q_j^r,y^l,L)</math>
b) Pro obecné k.
* Stejná myšlenka jen složitější zápis.
<math>\Box</math>
Stejný důkaz lze zopakovat i pro NTS.
=== Důsledky ===
* <math>\forall r \in \mathbb{N}^+: DSPACE(S(n)) = DSPACE(\left \lceil \frac{1}{r} * S(n) \right \rceil)</math>
== Věta o redukci počtu pásek pro prostorovou složitost ==
=== Znění ===
Nechť L je jazyk přijímaný k-páskovým DTS M s prostorovou složitostí S(n). Potom existuje DTS M' s jednou pracovní páskou a prostorovou složitostí S(n) přijímajicí L.
=== Důkaz ===
Základní myšlenka je, že symboly ze stejné buňky všech pásek se smrsknou do jednoho znaku (k-tice) nové pásky. Ve znaku je také potřeba držet informaci jestli je nad symbolem hlava původního stroje nebo ne. Pak se simulují instrukce původního stroje (postupně pro každou pásku M).
<math>\Box</math>
To samé lze zopakovat pro NTS.
== Věta o lineárním zrychlení ==
=== Znění ===
Část 1: Nechť L je jazyk přijímaný k-páskovým DTS M s časovou složitostí T(n), kde <math>k \ge 2</math> a platí <math>inf_{n \rightarrow \infty} \frac{T(n)}{n} = \infty</math>. Potom <math>\forall c > 0</math> existuje k-páskový DTS M' s časovou složitostí c * T(n) přijímajicí L.
Část 2: Nechť L je jazyk přijímaný k-páskovým DTS M s časovou složitostí c * T(n), kde <math> \ge 2</math> a <math>c > 1</math>. Potom <math>\forall \varepsilon > 0</math> existuje k-páskový DTS M' s časovou složitostí <math>(1 + \varepsilon) * T(n)</math> přijímajicí L.
=== Důkaz ===
Popíšeme činnost stroje M'. Z m políček původní pásky udělám jeden znak (m-tici) nového stroje.
# přepíše vstup m-krát zahuštěný na pracovní pásku, na to potřebujeme <math>n+1</math> kroků.
# odjede na začátek nové pracovní pásky, na to potřebujeme <math>\left \lceil \frac{n}{m} \right \rceil</math> kroků.
# simuluje T(n) kroků stroje M pomocí <math> 8 * \left \lceil \frac {T(n)}{n} \right \rceil</math> kroků.
Celkově tedy <math>n + \left \lceil \frac{n}{m} \right \rceil + 8 * \left \lceil \frac {T(n)}{n} \right \rceil</math> kroků.
* Část 1: Jak určit m aby <math>n + \left \lceil \frac{n}{m} \right \rceil + 8 * \left \lceil \frac {T(n)}{n} \right \rceil \le c * T(n)</math>?
{{TODO|}}
* Část 2: Jak určit m aby <math>n + \left \lceil \frac{n}{m} \right \rceil + 8 * \left \lceil \frac {T(n)}{n} \right \rceil \le (\varepsilon + 1) * n</math>?
{{TODO|}}
<math>\Box</math>
Stejná věta se dá dokázat i pro NTS.
== Věta o redukci počtu pásek pro časovou složitost ==
=== Znění ===
Část 1: Nechť <math>L \in DTIME(T(n))</math> a platí <math>inf_{n \rightarrow \infty} \frac{T(n)}{n} = \infty</math> nebo <math>T(n) = c * n; c > \sqrt{2*k}</math>. Potom existuje jednopáskový DTS s časovou složitostí <math>T((n))^2</math> přijímajicí L.
Část 2: Nechť L je jazyk příjímaný k-páskovým DTS M s časovou složitostí T(n). Potom existuje 2-páskový DTS M' s časovou složitostí <math>T(n) * log_2(T(n))</math> přijímajicí L.
=== Důkaz ===
Část 1:
* Pokud platí <math>inf_{n \rightarrow \infty} \frac{T(n)}{n} = \infty</math> použiji [[Složitost_II#Věta o lineárním zrychlení| větu o lineárním zrychlení]] (část 1) s <math>c = \sqrt{\frac{1}{2k}}</math> a poté redukuji počet pásek stejným způsobem jako v důkazu [[Složitost_II#Věta o redukci počtu pásek pro prostorovou složitost| věty o redukci počtu pásek pro prostorovou složitost]].
* Pokud platí <math>T(n) = c * n; c > \sqrt{2*k}</math> použiji [[Složitost_II#Věta o lineárním zrychlení| větu o lineárním zrychlení]] (část 2) a pak stějně jako v předchozím případě.
Poznámka: Obráceně to dělat nemůžu protože neumíme zrychlovat jednopáskové stroje.
Část 2:
Idea důkazu: Hlavy držím pod sebou a pohybuji daty.
Popíšeme konstrukci stroje M':
* 1. Páska ma 2k stop a je rozdělena na bloky <math>..,B_{-2},B_{-1},B_0,B_1,B_2,...</math> kde:
** <math>B_0</math> obsahuje jedinou buňku.
** <math>\forall i \ge 1; |B_i| = |B_{i-1}| = 2^{i-1}</math>
* 2. Páska je jednostopá a slouží k přesunu dat.
* Invarianty, které platí po simulaci každého kroku stroje:
*# <math>\forall i \ge 1</math> nastává jedna z možností:
*#* <math>B_i</math> má obě stopy plné a <math>B_{-i}</math> má obě stopy prázdné.
*#* <math>B_i</math> má obě stopy prázdné a <math>B_{-i}</math> má obě stopy plné.
*#* <math>B_i,B_{-i}</math> mají dolní stopu prázdnou a horní plnou.
*# <math>\forall i; B_i</math> obsahuje souvislý interval pásky stroje M
*#* pokud i < 0 tak horní stopa (HS) obsahuje symboly vpravo od dolní stopy (DS).
*#* pokud i > 0 tak HS obsahuje symboly vlevo od DS.
*#* pokud i = 0 tak symbol je pouze na DS a na HS je speciální symbol (zarážka).
*# <math>\forall i; B_i</math> obsahuje interval pásky M bezprostředné vlevo od <math>B_{i+1}</math>
Simulace jednoho kroku stroje M:
* Změna symbolu na pásce a změna řídícího stavu jsou zřejmé.
* Pro posun hlavy je třeba posunout data na pásce (BÚNO pohyb doleva):
# Hlava na 1.pásce M' jede od <math>B_0</math> doprava dokud nenajde blok <math>B_i</math> s alespoň jednou stopou prázdnou.
# Hlava jede zpět k <math>B_0</math> a na pomocnou pásku kopíruje obsah bloků <math>B_0,..B_{i-1}</math>. (Přitom každý blok přejedu 3x).
# Hlava jede do prava a z pomocné pásky kopíruje data do stop <math>B_1,..,B_{i-1}</math>
#* do DS pokud <math>B_i</math> měl obě stopy prázdné.
#* do HS pokud <math>B_i</math> měl jednu stopu prázdnou.
# Hlava jede doleva a počíta na pomocnou pásku vzdálenost od pravého kraje <math>B_i</math> do <math>B_0</math>.
# Hlava pokračuje vlevo a pomocí počítadla najde levý okraj bloku <math>B_{-i}</math>.
# Hlava jede v pravo a kopíruje na pomocnou pásku obsah stopy bloku <math>B_{-i}</math> (HS pokud je, jinak DS).
# Hlava pokračuje vpravo a kopíruje data z pomocné pásky do DS bloků <math>B_{-i+1},..,B_0</math>.
Předchozí body označíme jako <math>B_i</math> operace.
* Po ukončení <math>B_i</math> operace platí uvedené invarianty.
* <math>B_i</math> operace trvá <math>m * 2^{i-1}</math> kroků M', pro konstantu m.
* Po provedení <math>B_i</math> operace nemůže být další <math>B_i</math> operace provedena dříve než po <math>2^{i-1}</math> krocích stroje M. Tedy každá <math>B_i</math> operace může být spuštěna maximálně <math>\left \lfloor \frac{T(n)}{2^{i-1}}\right\rfloor</math> krát.
Stroj M' udělá nejvýše <math>T'(n) \le k * \sum_{i=1}^{log_2(T(n))+1}(m * 2^{i-1} * \frac{T(n)}{2^{i-1}}) \le 2*m*k*T(n)*log_2(T(n))</math>. A díky [[Složitost_II#Věta o lineárním zrychlení|větě o lineárním zrychlení]] existuje DTS simulujicí M' v čase <math>T(n) * log_2(T(n))</math>.
=== Důsledky ===
* Část 1: <math>L \in NTIME(T(n))</math> pak existuje jednopáskový NTS s časovou složitostí <math>(T(n))^2</math> přijímajicí L.
* Část 2: Nechť je L přijímán k-páskovým NTS M s časovou složitostí T(n). Potom existuje 2-páskový NTS M' s časovou složitostí <math>T(n) * log_2(T(n))</math> přijímajicí L.
== Konstruovatelnost funkcí ==
Funkce <math>f:\mathbb{N} \rightarrow \mathbb{N}</math> je '''rekurzivní''' pokud existuje DTS M takový, že pro vstup 1<sup>n</sup> vydá výstup 1<sup>F(n)</sup>.
Funkce <math>f:\mathbb{N} \rightarrow \mathbb{N}</math> je '''vyčíslitelná v čase O(f) ''' pokud f je rekurzivní a ∃ c ≥ 1 takové, že příslušný DTS udělá nejvýše c*f(n) kroků než vydá 1<sup>f(n)</sup>.
Funkce <math>f:\mathbb{N} \rightarrow \mathbb{N}</math> je '''vyčíslitelná v prostoru O(f) ''' pokud f je rekurzivní a ∃ c ≥ 1 takové, že příslušný DTS použije při práci prostor nejvýše c*f(n).
Funkce <math>f:\mathbb{N} \rightarrow \mathbb{N}</math> je '''časově konstruovatelná''' pokud existuje DTS M takový, že pro každý vstup délky n zastaví po právě f(n) krocích. (předpokládáme, že f(n) ≥ n + 1).
Funkce <math>f:\mathbb{N} \rightarrow \mathbb{N}</math> je '''prostorově konstruovatelná''' pokud existuje DTS M takový, že pro každý vstup délky n zastaví s právě f(n) páskovými symboly neprázdnými, přičemž žádný jiný prostor na pracovních páskách nebyl v průběhu výpočtu použit.
= Odkazy =
[ftp://barbora.ms.mff.cuni.cz/../VYUKA/CEPEK/SLOZITOST Slajdy z přednášky] [ftp://barbora.ms.mff.cuni.cz//USR/VYUKA/CEPEK/SLOZITOST/ (alt. odkaz)] - Pro ty, kteří mají na barboře účet.
