{{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 =
= 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ěty ==
=== 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 ===
* Čá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{2k}</math>. Potom existuje jednopáskový DTS s časovou složitostí <math>T((n))^2</math> přijímajicí L.
* Důsledek: <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ť 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ůsledek: 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.
= 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.