TIN063 Skripta Ladislava Strojila

Z ωικι.matfyz.cz
Verze z 29. 9. 2008, 17:41, kterou vytvořil Ivokabel (diskuse | příspěvky) (Errata)

(rozdíl) ← Starší verze | zobrazit aktuální verzi (rozdíl) | Novější verze → (rozdíl)
Přejít na: navigace, hledání

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

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 LL(M')" má být "wL(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)