Mikołaj Bojańczyk > Języki, Automaty i Obliczenia (wykład 2010)


Języki, Automaty i Obliczenia


Co było?

15 lutego: Definicja automatu

22 lutego: Determinizacja. Wyrażenia regularne.

1 marca: Twierdzenie Kleene'go o równoważności wyrażeń regularnych i automatów.

8 marca: Lemat o pompowaniu. Minimalizacja automatów.

15 marca: Zakończenie języków regularnych. Początek gramatyk bezkontekstowych.

22 marca: Gramatyki. Drzewa wyprowadzeń.

29 marca: Automaty ze stosem. Równoważność z gramatykami.

5 kwietnia: Lany poniedziałek

12 kwietnia: Pompowanie języków bezkontekstowych.

19 kwietnia: Postacie normalne gramatyk. Algorytm CYK. Języki kontekstowe.

26 kwietnia: Maszyna Turinga

3 maja: 3 maja

10 maja: Nierozstrzygalność.

17 maja: Kolokwium. Rozwiązania

24 maja: Nierozstrzygalność problemu Posta.

31 maja: Klasy złożoności: NP.


Zasady zaliczenia

Kolokwium 40% + Egzamin 60%

Zadania z pierwszego terminu egzaminu i ich rozwiązania

Zadania z egzaminu poprawkowego i ich rozwiązania


Materiały

Notatki Pawła Urzyczyna

Notatki Damiana Niwińskiego (oraz inne materiały)

Zbiór zadań Damiana Niwińskiego i Wojciecha Ryttera

Hopcroft John, Ullman Jeffrey (dodatkowo Rajeev Motwani w nowszych wydaniach)   „Wprowadzenie do teorii automatów, języków i obliczeń”