Powrót do strony domowej

Strona wykładu z Języków, automatów i obliczeń

Szymon Toruńczyk – lato 17/18 – środy, g. 12.15, sala 3180

Zasady zaliczania


Lista wykładów
  1. 28.02 – słowa, języki, wyrażenia regularne.
  2. 7.03 – automaty.
  3. 14.03 – równoważność automatów deterministycznych, niedeterministycznych, i wyrażeń regularnych.
  4. 21.03 – algorytmy na automatach. Minimalizacja automatów.
  5. 4.04 – podsumowanie języków regularnych słów. Języki regularne drzew.
  6. 11.04 – języki bezkontekstowe.
  7. 18.04 – własności języków bezkontekstowych, lemat o pompowaniu dla nich.
  8. 25.04 – automaty ze stosem.
  9. 9.05 – kolokwium (treść oraz przykładowe rozwiązania).
  10. 16.05 – algorytmy dla języków bezkontekstowych. Wstęp do maszyn Turinga.
  11. 23.05 – maszyny Turinga i funkcje obliczalne.
  12. 30.05 – języki obliczalne, częściowo obliczalne, rekurencyjnie przeliczalne. Uniwersalna maszyna Turinga.
  13. 6.06 – nierozstrzygalność.
  14. 13.06 – nierozstrzygalność – ciąg dalszy; niedeterminizm, P, NP.
Skrypt do wykładu

Skrypt z minionymi wykładami. Data ostatniej modyfikacji: 01.08.2018 15:26

Zadania domowe
  1. Zadanie 1 – termin 17.04
  2. Zadanie 2 – termin 17.06
Zadania z gwiazdką
  1. Seria 1 – termin 1.06
Egzamin

Materiały

Polecany podręcznik:

Zbiór zadań

Książka 200 Problems in Formal Languages and Automata Theory to zbiór zadań wraz z rozwiązaniami, w języku angielskim. Tu jest strona książki, wraz z próbką. Książka zawiera rozwiązania zadań zebranych przez Damiana Niwińskiego i Wojciecha Ryttera w zbiorku dostępnym po polsku tutaj. Książka będzie dostępna w pierwszej połowie marca w bibliotece wydziałowej, w ilościach umożliwiających jej jednoczesne wypożyczenie przez większość słuchaczy wykładu. Zachęcam do odnajdywania błędów i wpisywania ich do erraty.