Wykłady:
- 26 lutego: Słowa, języki, wyrażenia regularne. [slajdy]
- 5 marca: Automaty. [slajdy]
- 12 marca: Języki regularne a automaty. [slajdy]
- 19 marca: Minimalizacja automatów. [slajdy]
- 26 marca: Języki bezkontekstowe. [slajdy]
- 2 kwietnia: Automaty ze stosem. [slajdy]
- 9 kwietnia: Własności języków bezkontekstowych. [slajdy]
- 16 kwietnia: Obrazy przemienne języków. Automaty dwukierunkowe. [slajdy]
- 23 kwietnia: Maszyny Turinga. [slajdy]
- 30 kwietnia: Obliczalność. [slajdy]
- 14 maja: Nieobliczalność. [slajdy]
- 21 maja: Nieobliczalność c.d. [slajdy]
- 28 maja: Złożoność czasowa i pamięciowa. NP. [slajdy]
- 4 czerwca: NP c.d. PSPACE. Hierarchia Chomsky’ego. [slajdy]
- 11 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: