Skripta obsahují většinu látky ze [Složitosti II](Složitost%20II).

* [Domovská stránka](http://ladislav.strojil.cz/school.php?sub=1)
* Stažení: [TeX](http://ladislav.strojil.cz/do_download.php?path=documents&file=np&type=tex), [PostScript](http://ladislav.strojil.cz/do_download.php?path=documents&file=np&type=ps), [PDF](http://ladislav.strojil.cz/do_download.php?path=documents&file=np&type=pdf), [DVI](http://ladislav.strojil.cz/do_download.php?path=documents&file=np&type=dvi)

## Errata ##

Errata jsou vztažena k verzi 1.1.

### Faktické chyby ###

* 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<sub>2</sub>*n*, ale log<sub>2</sub>*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*)

### Překlepy, formátování apod. ###

* 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*)