Wykład specjalizujący 1

Specialized lecture 1

2023L

Kod przedmiotu17S1-WYKSPE1
Punkty ECTS 2,5
Typ zajęć Wykład
Przedmioty wprowadzające
Wymagania wstępne
Opis ćwiczeń
Opis wykładów. Alfabety, słowa, języki. Deterministyczne automaty skończone (DFA). Akceptowanie słów i rozpoznawanie języków przez DFA. 2. Operacje regularne na językach. Zamkniętość klasy języków regularnych ze względu na operację sumy. Niedeterministyczne automaty skończone (NFA). 3. Determinizacja. Własności domknięcia klasy języków regularnych ze względu na operacje regularne. Wyrażenia regularne. 4. Równoważność automatów skończonych i wyrażeń regularnych. Uogólnione niedeterministyczne automaty skończone (GNFA). 5. Równoważność deterministycznych automatów skończonych i ich minimalizacja. 6. Języki nieregularne. Lemat o pompowaniu. Kryterium nieregularności. Przykłady języków nieregularnych. 7. Gramatyki bezkontekstowe (CFG). Języki bezkontekstowe. Drzewa wyprowadzeń. Jednoznaczność gramatyk i języków bezkontekstowych. Postać normalna Chomsky'ego. 8. Niedeterministyczne automaty ze stosem (PDA). Równoważność gramatyk bezkontekstowych i automatów ze stosem. 9. Lemat o pompowaniu dla języków bezkontekstowych. Przykłady języków, które nie są bezkontekstowe. Własności domknięcia klasy języków bezkontekstowych. 10. Maszyny Turinga. Konfiguracje. Języki rozpoznawalne i rozstrzygalne w sensie Turinga. Przykłady maszyn Turinga. 11. Warianty maszyn Turinga: wielotaśmowe i niedeterministyczne maszyny Turinga. Enumeratory. Wzmianka o równoważnych modelach obliczeń. Teza Churcha-Turinga. 12. Reprezentowanie problemów w postaci języków. Przykłady problemów rozstrzygalnych: problem akceptacji dla DFA i NFA, problem generowania słowa przez wyrażenie regularne, problem generowania słowa przez gramatykę bezkontekstową, problem pustości dla gramatyk regularnych. 13. Nierozstrzygalność problemu akceptacji dla maszyn Turinga. Rozpoznawalność problemu akceptacji dla maszyn Turinga. Uniwersalna maszyna Turinga. Istnienie języków nierozpoznawalnych w sensie Turinga. Redukowalność. Inne problemy nierozstrzygalne: problem stopu, problem pustości języka rozpoznawanego przez maszynę Turinga, problem regularności. 14. Twierdzenie Rice'a. Nierozstrzygalność problemu równoważności dla maszyn Turinga. 15. Klasa złożoności P. Przykłady problemów z klasy P. Klasa złożoności NP. Przykłady problemów z klasy NP. Problem P versus NP. Problemy NP-zupełne. Przykłady problemów NP-zupełnych.
Cel kształcenia
Literatura podstawowa1) J.E. Hopcroft, J.D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, ., 2003 2) J.E. Hopcroft, R. Montani, J. D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, ., 2005
Literatura uzupełniająca
Uwagi