**Program:**
1. Wyrażenia i języki regularne. Automaty skończone, równoważność deterministycznych automatów skończonych, niedeterministycznych automatów skończonych i wyrażeń regularnych. (4 godz.)
2. Lemat o pompowaniu. Twierdzenie Myhilla-Nerode'a i minimalizacja automatu. (4 godz.)
3. Gramatyki i języki bezkontekstowe. Postać normalna Greibach i Chomsky'ego. #Automaty ze stosem. Równoważność gramatyk bezkontekstowych i automatów ze stosem. (10 godz.)
4. Lemat o pompowaniu i lemat Ogdena. (4 godz.)
5. Języki deterministyczne i jednoznaczne. (4 godz.)
6. Teoretyczne modele maszyn obliczających. Modele obliczeń sekwencyjnych: maszyna Turinga i jej modyfikacje, RAM. Niedeterministyczna maszyna Turinga.
7. Przykładowe symulacje pomiędzy różnymi modelami. Definicja Kleene'go. Teza Churcha. (6 godz.)
8. Pojęcie zbioru rekurencyjnego i rekurencyjnie przeliczalnego. Kodowanie i numeracja maszyn Turinga, maszyna uniwersalna. Nierozstrzygalność problemu stopu. Inne przykłady problemów nierozstrzygalnych. Twierdzenie Rice'a. (4 godz.)
9. Nierozstrzygalność problemów Posta i problemu słów w półgrupie. Informacja o nierozstrzygalności arytmetyki. (4 godz.)
10. Czasowa i pamięciowa złożoność obliczeniowa dla modelu maszyny Turinga.
11. Zależności pomiędzy nimi. Pojęcie klasy złożoności i najważniejsze przykłady (LOGSPACE, NLOGSPACE, PTIME, UP, NP, PSPACE, EXPTIME). Przykład problemu wymagającego wykładniczego czasu i pamięci. (8 godz.)
12. NP-zupełność, sens pojęcia, przykłady, tw. Cooka, redukcje pomiędzy problemami, hipoteza P≠ NP. (6 godz.)
13. Zagadnienie złożoności dla modeli równoległych, klasa PSPACE jako pułap złożoności dla obliczeń równoległych w czasie wielomianowym, informacja o klasie NC, jej podklasach i strukturze. (4 godz.)
**Wymagania:** Logika dla informatyków, Matematyka dyskretna oraz Algorytmy i
struktury danych
