Teoretyczne Podstawy Informatyki
tematyka przedmiotu
1. Podstawowe pojęcia z teorii automatów i języków
2. Automaty skończone, zastosowania, rozpoznawanie wzorców, deterministyczny automat
skończony, niedeterministyczny automat skończony, równoważność DAS i NAS,
automaty skończone z �-przejściami
3. Wyrażenia i języki regularne, operatory konstruujące WR, równoważność wyrażeń
regularnych i automatów skończonych, prawa algebraiczne dla wyrażeń regularnych
4. Własności języków regularnych, lemat o pompowaniu dla JR, własności zamkniętości
języków regularnych, minimalizacja i równoważność automatów skończonych
5. Gramatyki i języki bezkontekstowe, wyprowadzenia gramatyk, drzewa wyprowadzenia,
wieloznaczność języków i gramatyk bezkontekstowych
6. Automaty ze stosem, równoważność automatu ze stosem i gramatyki bezkontekstowej,
deterministyczne AZS
7. Własności języków bezkontekstowych, postacie normalne gramatyk bezkontekstowych
(postać normalna Chomsky ego i Greibach), lemat o pompowaniu dla JBK, własności
zamkniętości języków bezkontekstowych
8. Hierarchia Chomsky ego klas języków formalnych, języki kontekstowe i rekurencyjnie
przeliczalne
9. Problemy, których nie potrafią rozwiązywać komputery, nierozstrzygalność, maszyna
Turinga, teza Churcha-Turinga, języki rekurencyjnie przeliczalne, problem drukowania
tekstu, problem stopu, problem odpowiedniości Posta
10. Złożoność obliczeniowa algorytmów (wilomianowa i wykładnicza), problemy niepodatne,
problemy P i NP, redukcje w czasie wielomianowym, problemy NP-zupełne, problem
CNF-spełnialności, problem komiwojażera, problem plecakowy