{{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 jsem 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 ==
= Odkazy =
[ftp://barbora.ms.mff.cuni.cz/../VYUKA/CEPEK/SLOZITOST Slajdy z přednášky] - Pro ty, kteří mají na barboře účet.
