Wykłady:
- 25 lutego: Słowa, języki, wyrażenia regularne. [slajdy]
- 4 marca: Automaty. [slajdy]
- 11 marca: Języki regularne a automaty. [slajdy]
- 18 marca: Minimalizacja automatów. [slajdy]
- 25 marca: Języki bezkontekstowe. [slajdy]
- 1 kwietnia: Automaty ze stosem. [slajdy]
- 8 kwietnia: Własności języków bezkontekstowych. [slajdy]
- 15 kwietnia: Obrazy przemienne języków. Automaty dwukierunkowe. [slajdy]
- 22 kwietnia: Maszyny Turinga. [slajdy]
- 29 kwietnia: Obliczalność. [slajdy]
- 13 maja: Nieobliczalność. [slajdy]
- 20 maja: Nieobliczalność c.d. [slajdy]
- 27 maja: Złożoność czasowa i pamięciowa. NP. [slajdy]
- 3 czerwca: NP c.d. PSPACE. Hierarchia Chomsky’ego. [slajdy]
- 10 czerwca: podsumowanie i powtórka.
Literatura:
- D. Niwiński, W. Rytter, 200 problems in formal languages and automata theory, CUP (zbiór zadań z rozwiązaniami).
[treści zadań po angielsku]
[treści zadań po polsku]
- J.E. Hopcroft, R. Motwani, J.D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, PWN.
[wykład oparty na tej książce]
- M. Sipser, Wprowadzenie do teorii obliczeń, PWN.
Materiały dodatkowe: