Języki formalne i złożoność obliczeniowa

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. #Przykładowe symulacje pomiędzy różnymi modelami. Definicja Kleene'go. Teza Churcha. (6 godz.)
7. 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.)
8. Nierozstrzygalność problemów Posta i problemu słów w półgrupie. Informacja o nierozstrzygalności arytmetyki. (4 godz.)
9. Czasowa i pamięciowa złożoność obliczeniowa dla modelu maszyny Turinga. #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.)
10. NP-zupełność, sens pojęcia, przykłady, tw. Cooka, redukcje pomiędzy problemami, hipoteza P¹ NP. (6 godz.)
11. 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.)

Literatura

• A.V. Aho, J.E. Hopcroft, J.D. Ullman, Projektowanie i analiza algorytmów komputerowych, PWN, Warszawa 1983.
• J.E. Hopcroft, J.D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, WNT, Warszawa 1994.
• N.D. Jones, Computability and Complexity from a Programming Perspective, w druku.