{{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 ===
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:
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>
Důsledek: <math>\forall r \in \mathbb{N}^+: DSPACE(S(n)) = DSPACE(\left \lceil \frac{1}{r} * S(n) \right \rceil)</math>
Stejný důkaz lze zopakovat i pro NTS.
= 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.
