Informacje ogólne

Typ:obowiazkowy

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.