Matematyczne podstawy informatyki

TREŚCI NAUCZANIA

Pojęcie języka formalnego i gramatyki. Wyrażenia regularne i języki regularne. Automat skończenie stanowy, automat niedeterministyczny, lemat o pompowaniu. Minimalizacja automatu. Język bezkontekstowy, automat ze stosem, algorytm rozpoznawania języka bezkontekstowego. Maszyna Turinga, model obliczania funkcji, model rozpoznawania języka. Języki rozstrzygalne i nierozstrzygalne, problem stopu, inne przykłady problemów nierozstrzygalnych. Złożoność czasowa i obliczeniowa maszyny Turinga. Pojęcie trudności obliczeniowej. Podstawowe klasy złożoności: P, NP, NPC, LOGSPACE, PSPACE. Logiki reprezentacji wiedzy w językach zapytań i odpowiedzi dla baz danych. Metody automatycznego dowodzenia twierdzeń oraz logicznego wspomagania weryfikacji i specyfikacji programów.

LITERATURA PODSTAWOWA

1. J. E. Hopcroft, R. Motwani, J. D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, PWN 2005.
2. M. Sipser, Introduction to the Theory of Computation, Second Edition, PWS Publishing Company, 2005.

LITERATURA UZUPEŁNIAJĄCA

1. C. Papadimitriou, Złożoność obliczeniowa, WNT 2002.