Co bylo na wykladzie ?

8. 10. 2004.
Wprowadzenie - intuicja pojecia zlozonosci.
Podstawowe pojecia : slowa, jezyki, konkatenacja, operacja gwiazdki, ilorazy.
Jezyki regularne, wyrazenia regularne.
Automaty skonczone - niedeterministyczne i deterministyczne, obliczenia akceptujace.
Przyklady automatow (m.in. badanie podzielnosci).
Twierdzenie Kleene'go. Transformacja wyrazenia regularnego w automat niedetrministyczny o liniowej liczbie stanow.
Transformacja odwrotna przez konstrukcje i rozwiazanie ukladu rownan (niedokonczone).

15.10. 2004.
Dokonczenie tranformacji : automat |--> wyrazenie regularne (rozmiaru wykladniczego).
W dowodzie zastosowanie Lematu Ardena, ze rozwiazaniem rownania X = AX + B jest A* B
(jedynym jesli A nie zawiera slowa pustego).
Lemat o pompowaniu dla jezykow regularnych. Przyklady jezykow nie-regularnych.
Algorytm rozpoznawania, czy tekst zawiera wzorzec zgodny z danym wyrazeniem regularnym.

22.10. 2004.
Algorytm stwierdzania, czy automat skonczony akceptuje jakiekolwiek slowo.
Determinizacja automatu skonczonego. Przyklad na wykladnicza eksplozje zbioru stanow.
Relacja synkaktyczna jezyka. Twierdzenie Myhilla-Nerode'a.
Abstrakcyjna konstrukcja automatu minimalnego z klas abstrakcji relacji syntaktycznej jezyka.

29.10.2004
Konstrukcja automatu minimalnego wychodzaca od dowolnego automatu deterministycznego,
metoda "sklejania stanow", tzn. dzielenia przez relacje kongruencji.
Algorytm minimalizacji Moore'a (n^2) - przyklad, wzmianka o algorytmie Hopcrofta (n log n).
Zastosowania automatow skonczonych : automat rozpoznajacy wzorzec w tekscie,
automat rozpoznajacy podslowa (dokonczenie na nastepnym wykladzie).

5.11.2004
Automat rozpoznajacy podslowa, dokonczenie. Wzmianka o zastosowaniu automatow w weryfikacji.
Wlasnosci domkniecia klasy jezykow regularnych, podsumowanie.
Gramatyki bezkontekstowe, wyprowadzenia i drzewa wyprowadzen.

19.11.2004
Zagadnienie jednoznacznosci gramatyk, przyklady.
Algorytm badania, czy gramatyka generuje jezyk niepusty.
Efektywna eliminacja zmiennych nieosiagalnych, nieproduktywnych, regul epsilonowych i jednostkowych.
Efektywne sprowadzanie gramatyki do postaci normalnej Chomsky'ego.
Algorytm rozpoznawania jezyka bezkontekstowego metoda programowania dynamicznego (CYK).

26.11.2004
Automaty ze stosem - podstawowe definicje i przyklady.
Rownowaznosc akceptacji przez stany i przez pusty stos.
Rownowaznosc niedeterministycznych automatow ze stosem i gramatyk bezkontekstowych.
Podstawowy lemat : eliminacja stanow (sprowadzenie do jednego).

3.12.2004
Lemat o pompowaniu i lemat Ogdena. Ich zastosowania do dowodzenia,
ze jakis jezyk nie jest bezkontekstowy.
Palindromy - jako przyklad jezyka bezkontekstowego nierozpoznawalnego
przez deterministyczny automat ze stosem.

10.12.2004 (Stefan Dziembowski)
Maszyna Turinga - dyskusja wprowadzajaca, definicja, przyklady.
Ogolniejsze warianty maszyny Turinga i ich rownowaznosc z modelem
podstawowym: maszyna z tasma nieskonczona w obie strony, maszyna
z wieloma tasmami lub tasma wielowymiarowa.

17.12.2004
Kodowanie maszyn Turinga, konstrukcja maszyny uniwersalnej.
Jezyk przekatniowy i nierozstrzygalnosc problemu stopu.
Nierozstrzygalnosc problemu niepustosci dla maszyn Turinga.

7.01.2005
Podstawowe pojecia teorii obliczalnosci: zbiory czesciowo i calkowicie
obliczalne. Twierdzenie Rice'a o nieobliczalnosci wlasnosci semantycznych maszyn Turinga.
Przyklady zbiorow nie obliczalnych - problem Posta.

14.01.2005
Gramatyki typu 0 (bez ograniczen) i ich rownowaznosc z maszynami Turinga.
Informacja o jezykach kontekstowych.
Hierarchia gramatyk Chomsky'ego. Wlasnosci domkniecia
poszczegolnych klas Chomsky'ego i wlasnosci rozstrzygalnosci.
Definicje zlozonosci czasowej i pamieciowej. Konstrukcja jezyka
rozpoznawalnego w pamieci wielomianowej, ale nie w pamieci logarytmicznej.

21.01.2005
O pozytkach z teorii zlozonosci - odpieranie potencjalnych zarzutow.
Klasy zlozonosci wielomianowej: P, NP i PSPACE.
Problemy NP-zupelne: definicja, znaczenie poznawcze, przyklady.
Generyczna redukcja dowolnego problemu NP do problemu spelnialnosci ukladow logicznych.
NP-zupelnosc problemow SAT, CNF SAT, 3-CNF SAT.
Redukcja 3-CNF SAT do 3-kolorowania.

Koniec.