TIN063 Skripta Ladislava Strojila

Skripta obsahují většinu látky ze Složitosti II.

Errata

Errata jsou vztažena k verzi 1.1.

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 log₂n, ale log₂S(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)

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)