Języki, automaty i obliczenia

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.

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ść.