Mikołaj Bojańczyk > Języki, Automaty i Obliczenia (wykład 2009)
Anonimowa ankieta z ocena na biezaco
4 czerwca: Klasy złożoności: PSPACE.
28 maja: Klasy złożoności: NP.
21 maja: Nierozstrzygalność, ciąg dalszy.
14 maja: Nierozstrzygalność.
7 maja: Początek maszyn Turinga (Dexter Kozen).
30 kwietnia: Kolokwium (Rozwiązania).
23 kwietnia: Postacie normalne gramatyk. Algorytm CYK. Języki kontekstowe.
16 kwietnia: Pompowanie języków bezkontekstowych.
9 kwietnia: Dzień wolny.
2 kwietnia: Automat ze stosem.
26 marca: Gramatyki bezkontekstowe.
19 marca: Minimalizacja automatów.
12 marca: Lemat o pompowaniu.
5 marca: Twierdzenie Kleene'go o równoważności wyrażeń regularnych i automatów.
26 lutego: Formalna definicja automatu. Determinizacja.
19 lutego: Słowa i operacje na słowach. Wyrażenia regularne. Automat.
Kolokwium 40% + Egzamin 60%
Notatki Damiana Niwińskiego (oraz inne materiały)
Zbiór zadań Damiana Niwińskiego i Wojciecha Ryttera
Hopcroft John, Ullman Jeffrey „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). Z jednej serii (będą trzy) można dostać maksymalnie jeden punkt. 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.
Pierwsza seria o językach regularnych. Termin: 29 marca.
Druga seria o językach bezkontekstowych. Termin: 17 maja.