Vztah determinismu a nedeterminismu pro lineární čas
| Název práce v jazyce práce (slovenština): | Vztah determinismu a nedeterminismu pro lineární čas |
|---|---|
| Název práce v češtině: | Vztah determinismu a nedeterminismu pro lineární čas |
| Název v anglickém jazyce: | Relation of determinism and non-determinism for linear time |
| Klíčová slova: | vzt'ah determinizmu a nedeterminizmu, alternujuci Turingov stroj, separacia tried zlozitosti |
| Klíčová slova anglicky: | relation of determinism and non-determinism, alternating Turing machine, separation of complexity classes |
| Akademický rok vypsání: | 2010/2011 |
| Typ práce: | diplomová práce |
| Jazyk práce: | slovenština |
| Ústav: | Katedra teoretické informatiky a matematické logiky (32-KTIML) |
| Vedoucí / školitel: | prof. RNDr. Václav Koubek, DrSc. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 22.11.2010 |
| Datum zadání: | 22.11.2010 |
| Datum a čas obhajoby: | 05.09.2011 09:00 |
| Datum odevzdání elektronické podoby: | 02.08.2011 |
| Datum odevzdání tištěné podoby: | 05.08.2011 |
| Datum proběhlé obhajoby: | 05.09.2011 |
| Oponenti: | RNDr. Petr Kučera, Ph.D. |
| Zásady pro vypracování |
| Seznamit se pracemi Paula a spol. o vztahu DLIN a NLIN. Podrobne napsat dukaz, ze linearni nedeterministcke algoritmy nelze
simulovat deterministickymi linearnimi algoritmy. Na zaklade tohoto pokusit se zobecnit uvedeny vysledek. |
| Seznam odborné literatury |
| J. L. Balcazar, J. Diaz, J. Gabarro: Structural complexity II, Springer-Verlag, EATCS Monographs on Theoretical Computer
Science, Volume 22, 1990. W. J. Paul, N. Pippenger, E. Szemeredi, W. T. Trotter: On determinism versus non-determinism and related problems, Proc. 24, FOCS 429--438, 1983. W. J. Paul, R. Reischuk: On time versus space II, J. Comp. Sys. Sci. 22 (10\981), 312-327. |