TIN063 Skripta Ladislava Strojila
Z ωικι.matfyz.cz
Skripta obsahují většinu látky ze Složitosti II.
- Domovská stránka
- Stažení: TeX, PostScript, PDF, DVI
Errata[editovat | editovat zdroj]
Errata jsou vztažena k verzi 1.1.
Faktické chyby[editovat | editovat zdroj]
- str. 17, důkaz věty 15, poslední odstavec: místo "potom L ∈ L(M')" má být "w ∈ L(M')" (David Majda)
- str. 19, věta 18 b'): místo "NSPACE" má být nejspíš "DSPACE" (David Majda)
- str. 20, důkaz věty 19: pozice pracovní hlavy není omezena log2n, ale log2S(n) (David Majda)
- str. 20, důkaz věty 19, poslední odstavec: místo "V každý okamžik je na zásobníku O(S(n)) záznamů." má být "V každý okamžik je na zásobníku nejvýše O(S(n)) záznamů." (David Majda)
Překlepy, formátování apod.[editovat | editovat zdroj]
- str. 2, definice turingova stroje: místo "poh" má být "pod" (David Majda)
- str. 3, definice přijímaného jayzka: za svislítkem je 2× "w" (David Majda)
- str. 10, důkaz věty 9: v první větě má být místo "teda" slovo "tedy" (David Majda)