Teoretyczne podstawy informatyki
Informacje ogólne
Kierunek:informatyka
Semestr:4
Wymiar zajęć:20h wykładu
Punkty ECTS:4
Program
- Automaty skończone, wyrażenia regularne, automaty niedeterministyczne, równoważność wyrażeń regularnych i automatów skończonych. Wyrażenia regularne w językach skryptowych.
- Hierarchia Chomsky'ego. Gramatyki bezkontekstowe, automaty ze stosem, drzewo wywodu, parsery.
- Maszyna Turinga jako model obliczeń. Pojęcie obliczalności.
- Złożoność obliczeniowa.
- Klasa NP. Problemy NP-zupełne.
Sposób zaliczenia
zaliczenieLiteratura
Hopcroft, Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, Wyd. PWN 1994.