Języki, automaty i obliczenia

obowiązkowe

Algorytmy i struktury danych 1000-213bASD
Matematyka dyskretna 1000-212bMD
Podstawy matematyki 1000-211bPM
Wstęp do programowania 1000-211bWPI

Podstawowe modele obliczeń (automaty, gramatyki, maszyna Turinga), związki między trudnością problemów obliczeniowych a strukturalną złożonością modeli obliczeń. Hierarchia Chomsky'ego. Matematyczny sens pojęcia obliczalności oraz jego ograniczenia, a także - w zarysie - podstawowe zagadnienia złożoności obliczeniowej.

Elementy teorii języków formalnych: słowa, języki, wyrażenia regularne.

Automaty skończone i twierdzenie Kleene'go o efektywnej odpowiedniości automatów i wyrażeń.

Konstrukcje optymalizujące automaty - determinizacja, minimalizacja.

Języki bezkontekstowe: gramatyki i ich postaci normalne.

Odpowiedniość gramatyk bezkontekstowych i niedeterministycznych automatów ze stosem.

Kryteria rozróżniania języków regularnych i bezkontekstowych - lematy o pompowaniu.

Zagadnienia algorytmiczne: problem niepustości dla automatów i gramatyk, rozpoznawanie języków bezkontekstowych.

Przykłady zastosowań automatów i gramatyk.

Uniwersalne modele obliczeń: maszyna Turinga i jej warianty.

Granice obliczalności: nierozstrzygalność problemu stopu, przykłady praktycznych problemów nierozstrzygalnych.

Podsumowanie - klasyfikacja gramatyk, modeli obliczeń i języków według hierarchii Chomsky'ego.

Wprowadzenie do zagadnień złożoności obliczeniowej: klasy P i NP.

Twierdzenie Cooka-Levina o NP-zupełności SAT.

Hipoteza P=/=NP i jej praktyczne implikacje, informacja o pozytywnych zastosowaniach problemów trudnych obliczeniowo, np. w kryptografii.

1. J. E. Hopcroft, R. Motwani, J. D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, PWN, Warszawa 2005.

2. Ch. Papadimitriou, Złożoność obliczeniowa, WNT, Warszawa 2002.

Student ma wiedzę o podstawowych problemach i technikach związanych z konstruowaniem automatów i gramatyk, oraz z różnymi modelami obliczeniowymi. Poza tym potrafi względnie precyzyjnie przeprowadzać dowody faktów związanych z tą dziedziną. Umiejętność precyzyjnego dowodzenia poprawności różnego rodzaju konstrukcji informatycznych jest najsłabszą stroną studentów informatyki i jednym z najważniejszych efektów jest polepszenie tej umiejętności. Przedmiot ten się świetnie do tego nadaje ponieważ ma charakter częściowo matematyczny i uczy abstrahowania podstawowych elementów w różnego rodzaju konstrukcjach i modelach obliczeniowych (K_U27, K_W16).

W szczególności student:

1. Ma uporządkowaną wiedzę w zakresie konstrukcji automatów skończonych, ich minimalizacji i równoważności.

2. Zna związki automatów z wyrażeniami regularnymi. Umie udowodnić, że wybrany język formalny nie jest regularny.

3. Ma podstawową wiedzę w zakresie gramatyk bezkontekstowych i zna ich związki z automatami stosowymi.

4. Zna kryteria na to, że język nie jest bezkontekstowy.

5. Zna podstawowe algorytmy sprawdzania przynależności do języka bezkontekstowego.

6. Rozumie, jakie są uniwersalne modele obliczeniowe: maszyna Turinga i jej równoważniki (automaty wielolicznikowe, wielostosowe).

7. Potrafi udowodnić nierozstrzygalność wybranych problemów.

8. Zna definicję NP-zupełności, zna szereg problemów NP-zupełnych.

9. Rozumie pojęcie PSPACE-zupełności.

10. Ma świadomość tego, że istnieją problemy, które są rozstrzygalne ale mają astronomiczna złożoność.

* 4 zadania domowe po 5 pkt każde.

* 8 testów domowych łącznie za 8 pkt.

* egzamin końcowy za ~30 pkt.

* zadania z gwiazdką pozwalające zdobyć dodatkowe punkty.

By być dopuszczonym do egzaminu w pierwszym terminie, wymagane jest przynajmniej 14 pkt (próg ten może zostać opuszczony).

Ostateczna ocena w pierwszym terminie to 1/10 sumy uzyskanych punktów (z zaokrągleniem w dół do 0.5).

Egzamin w drugim terminie będzie skutkował oceną ostateczną (bez wpływu uzyskanych wcześniej punktów j.w.).