{{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 ===
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.
=== Věta o lineárním zrychlení ===
* Čá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.
* Důsledek: Pokud <math>inf_{n \rightarrow \infty} \frac{T(n)}{n} = \infty</math> pak <math>\forall c>0</math> je <math>DTIME(T(n)) = DTIME(c * T(n))</math>.
* Část 2: Nechť L je jazyk přijímaný k-páskovým DTS M s časovou složitostí c * T(n), kde <math>k \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ůsledek: Pokud T(n) = c * n (pro nějakou konstantu c > 1) pak <math>\forall \varepsilon > 0: DTIME(T(n)) = DTIME((1+\varepsilon)*n)</math>.
Stejná věta platí 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.
