Powrót do strony domowej

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

Szymon Toruńczyk – wiosna 18/19 – środy, g. 12.15, sala 3180


Ankieta

Anonimowa ankieta dotycząca sposobu prowadzenia wykładu. Państwa uwagi będą dla mnie cenną informacją zwrotną, którą postaram się uwzględnić.

Zasady zaliczania


Lista wykładów
  1. 27.02 – słowa, języki, wyrażenia regularne, automaty.
  2. 6.03 – równoważność automatów niedeterministycznych i wyrażeń regularnych.
  3. 13.03 – własności języków regularnych.
  4. 20.03 – minimalizacja, twierdzenie Myhilla-Nerodego.
  5. 27.03 – regularne języki drzew.
  6. 3.04 – języki bezkontekstowe.
  7. 10.04 – własności języków bezkontekstowych.
  8. 17.04 – automaty ze stosem.
  9. 24.04 – algorytmy dla gramatyk bezkontekstowych.
  10. 8.05 – kolokwium (treść oraz przykładowe rozwiązania).
  11. 15.05 – maszyny Turinga i funkcje obliczalne.
  12. 22.05 – maszyny wielotaśmowe, uniwersalna maszyna Turinga.
  13. 29.05 – nierozstrzygalność.
  14. 5.06 – nierozstrzygalność – ciąg dalszy.
  15. 12.06 – niedeterminizm, klasy P, NP, NP-zupełność.
Skrypt do wykładu

Będę prowadził skrypt do wykładu. Kolejne jego części będą pojawiały się po odpowiednich wykładach. Skrypt z grubsza, lecz niedokładnie, odpowiada wykładowi. Będę bardzo wdzięczny za zgłoszone uwagi i znalezione błędy w skrypcie.

Skrypt z minionymi wykładami. Data ostatniej modyfikacji: 12.06.2019 17:24

Zadania domowe
  1. Zadanie 1 – termin 9.04. Przykładowe rozwiązanie
  2. Zadanie 2 – termin 25.05
  3. Zadanie 3 – termin 22.06
Zadania z gwiazdką
  1. Seria 1 – termin 21.05; Przykładowe rozwiązanie zadania 3
  2. Seria 2 – termin 22.06
Egzamin

Materiały

Polecany podręcznik: John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, "Wprowadzenie do teorii automatów, języków i obliczeń", PWN.

Strony poprzednich edycji tego wykładu:
  • Materiały Damiana Niwińskiego
  • Materiały Wojciecha Ryttera
  • Materiały Mikołaja Bojańczyka
  • Materiały Pawła Urzyczyna
  • Materiały Sławomira Lasoty
  • Materiały Wojciecha Czerwińskiego
  • Strona wykładu z zeszłego roku

  • 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 jest dostępna w bibliotece wydziałowej. Zachęcam do odnajdywania błędów i wpisywania ich do erraty.