Mikołaj Bojańczyk > Języki, Automaty i Obliczenia (wykład 2012)
15 lutego: Wyrażenia regularne
22 lutego: Automaty skończone deterministyczne i niedeterministyczna. Determinizacja.
29 lutego: Dla każdego wyrażenia regularnego istnieje równoważny automat. Lemat o pompowaniu.
7 marca: Dla każdego automatu istnieje równoważne wyrażenie regularne. Minimalizacja automatów skończonych.
14 marca: Zakończenie języków regularnych. Początek gramatyk bezkontekstowych.
21 marca: Gramatyki. Drzewa wyprowadzeń.
28 marca: Automaty ze stosem. Równoważność z gramatykami.
4 kwietnia: Pompowanie języków bezkontekstowych.
11 kwietnia (nie ma wykładu): Ferie Wielkanocne
18 kwietnia: Maszyna Turinga
25 kwietnia: Kolokwium zadania z rozwiązaniami
2 maja Nierozstrzygalność
9 maja: Klasy złożoności: NP
16 maja: Klasy złożoności: PSPACE
23 maja (nie ma wykładu): Wykłady o wykładach.
30 maja: nie wiem
6 czerwca: (bufor, bo wiadomo, że coś się obsunie)
Kolokwium 40% + Egzamin 60%
Będą też zadania z gwiazdką.
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ń”
Za zadania dostaje się punkty, które dodają się do oceny z egzaminu (na przykład dostateczny + 1 punkt = dobry), pod warunkiem zdania egzaminu.
Za każde zadanie rozdzielę 1/2 punktu pomiędzy osoby, które je zrobiły (jeśli na przykład 5 osób zrobiło zadanie bezbłędnie, to każda dostanie 1/10 punktu). Za każde 5 zadań (niekoniecznie z jednej serii) jest bonus w postaci 1 punktu, niezależnie od tego ile innych osób rozwiązało te zadania.
Strony poprzednich moich wykładów z tego przedmiotu: 2010 2009. Można tam znaleźć zadania z kolokwiów i egzaminów. Uwaga, w tym roku będzie więcej maszyn Turinga na egzaminie.