Automaty, języki i złożoność obliczeniowa


Informacje ogólne

Typ:obowiazkowy
Kierunek:Informatyka studia licencjackie
Semestr:3
Wymiar zajęć:30 godzin wykładu, 30 godzin ćwiczeń
Punkty ECTS:6

Założenia i cele przedmiotu

poznanie wstępnych informacji z informatyki teoretycznej

Program

  • Automaty skończone, wyrażenia regularne, automaty niedeterministyczne, twierdzenie o determinizacji, twierdzenie o równoważności automatów skończonych i wyrażeń regularnych, lemat o pompowaniu.
  • Gramatyki Chomsky'ego, gramatyki bezkontekstowe, automaty ze stosem, drzewo wywodu. Parsery. Lemat o pompowaniu dla CF, gramatyki kontekstowe i automaty LBA. Postacie normalne.
  • Maszyny Turinga, języki rekurencyjne i rekurencyjnie przeliczalne, problemy rozstrzygalne i nierozstrzygalne, problem stopu i twierdzenie Rice'a.
  • Klasy P, NP. Problemy NP.-zupełne.

Sposób zaliczenia

Zaliczenie kolokwiów, aktywne uczestnictwo w ćwiczeniach, egzamin

Umiejętności i kompetencje

umiejętność rozróżniania języków z hierarchii Chomsky’ego

Literatura

  • J. Hopcroft, J. Ullman - Wprowadzenie do teorii automatów, języków i obliczeń, PWN 1994.
  • J. Jędrzejowicz, K. Rejniak - Języki, automaty, złożoność obliczeniowa - zbiór zadań, Wyd. UG 1994.
  • J. Jędrzejowicz, A. Szepietowski - Języki, automaty, złożoność obliczeniowa - Wyd. UG 2008.