Název: Vztah determinismu a nedeterminismu pro lineární čas
Překlad názvu: Relation of determinism and non-determinism for linear time
Autoři: Juračka, Matej ; Koubek, Václav (vedoucí práce) ; Kučera, Petr (oponent)
Typ dokumentu: Diplomové práce
Rok: 2011
Jazyk: slo
Abstrakt: [eng] [cze]
Result of this work is a reconstruction of proof, that non-deterministic linear time is strictly more powerful than deterministic linear time. We focus on completeness and clarity either of proof itself, either of all auxiliary propositions, which lead to this result. Výsledkem práce je rekonstrukce důkazu, že třídy jazyků akceptovaných deterministickým a nedeterministickým strojem v lineárním času jsou různé. Soustředíme se přitom na úplnost a srozumitelnost jak samotného důkazu, tak i všech přípravních tvrzení, které k němu vedou. Výsledkem práce je rekonstrukce důkazu, že třídy jazyků akceptovaných deterministickým a nedeterministickým strojem v lineárním času jsou různé. Soustředíme se přitom na úplnost a srozumitelnost jak samotného důkazu, tak i všech přípravních tvrzení, které k němu vedou. Výsledkem práce je rekonstrukce důkazu, že třídy jazyků akceptovaných deterministickým a nedeterministickým strojem v lineárním času jsou různé. Soustředíme se přitom na úplnost a srozumitelnost jak samotného důkazu, tak i všech přípravních tvrzení, které k němu vedou.
Klíčová slova: alternujuci Turingov stroj; separacia tried zlozitosti; vzt'ah determinizmu a nedeterminizmu; alternating Turing machine; relation of determinism and non-determinism; separation of complexity classes

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/49450

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-313739


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Diplomové práce