Wykład 1 (4.X 2025)
-
Przegląd tematyki.
Alfabety, słowa, języki.
Automaty skończone deterministyczne, niedeterministyczne, z cichymi przejściami.
Wyrażenia regularne. Tw. Kleene'ego (wszystkie powyższe metody definiują tę samą klasę języków). Wykład 2 (18.X 2025)
- Języki regularne, c.d. Operacje na językach regularnych. Lemat o pompowaniu.
- Języki bezkontekstowe i gramatyki. Automaty ze stosami. Operacje na językach bezkontekstowych. Lemat o pompowaniu.
Wykład 3 (25.X 2025)
- Maszyny Turinga. Porównanie maszyn Turinga z innymi klasami automatów. Języki rekurencyjnie przeliczalne i rekurencyjne. Rozstrzygalność. Obliczalność.
Wykład 4 (15.XI 2025)
-
Maszyny Turinga -- determinizacja.
Klasy złożoności czasowej. Wykład 5 (22.XI 2025)
-
Przykłady złożoności czasowej: algorytm CYK, problem spójności grafów, problem SAT.
Problemy NP-zupełne, dowód, że SAT jest NP-zupełny.
SAT solvers. Wykład 6 (6.XII 2025)
- Redukcje problemów, problemy NP-zupełne, 3SAT, kolorowalność, pokrycie wierzchołkowe, ścieżki Hamiltona.
Wykład 7 (13.XII 2025)
- Złożoność pamięciowa. Zawierania różnych klas złożoności.
