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

zaliczenie

Literatura

Hopcroft, Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, Wyd. PWN 1994.