Jerzy Marcinkowski

"Języki Formalne i Złożoność Obliczeniowa"

Kurs dla II roku Informatyki, edycja 2018

prowadzony, eksperymentalnie, w wymiarze 3h wykładu+ 3h ćwiczeń (plus oczywiście repetytorium, które polecam).  

 


 

Tu jest regulamin ćwiczeń, taki jak zawsze.

Tu będzie lista rankingowa.

Tu będzie zbiór zadań na ćwiczenia (.pdf), z roku na rok grubszy.

Egzamin odbędzie się tradycyjnie w trzech częściach:

Pierwsza część egzaminu odbędzie się w poniedziałek 26 marca w godzinach wykładu w sali wielkiej zachodniej.

Druga część egzaminu odbędzie się 14 maja w porze wykładu.

Trzecia część egzaminu odbędzie się w piątek 15 czerwca o 10:30 rano.

Wyniki egzaminu będą wiadomogdzie .

Pewnie niektórzy będą chcieli przyjść na egzamin poprawkowy. Odbędzie się on 3 września przed południem (część 1), 3 września po południu (część 2) i 4 września przed południem (część 3).

Tradycyjnie, kto będzie zadowolony z wyników niektórych (jednej lub dwóch) tercji z pierwszego teminu, będzie mógł je uznać za wyniki tych tercji w terminie poprawkowym. Decyzję o uznaniu wyniku komunikuje mi się poprzez nieprzystąpienie do tych tercji w terminie poprawkowym. -->

Kto chciałby, abym mu się wpisał do indeksu, nalepiej zrobi zostawiając go na mojej półce. Indeks powinien być wypełniony zgodnie z minimalnymi zasadami grzeczności obowiązującymi w języku polskim.  

 

 

 

 

 

Na ćwiczenia 21 lutego obowiązywać będą zadania 1, 4, 5, 7, 9--12, 21, 22, 27 ze zbioru.

Na ćwiczenia 28 lutego obowiązują zadania 14, 15, 17, 23, 25, 31, 43, 44, 45, 77, 78. Pojęcia pojawiające się w zadaniach 14, 15 i 17 zostaną wyjaśnione na wykładzie w poniedziałek. Zadanie 77 jest oczywiście za jeden punkt (na liście jest błąd wynikający z wcześniejszego zastosowania tego zadania).

Na ćwiczenia 7 marca obowiązują zadania 6, 18--20, 46, 48, 49, 51, 80 -- 83. Narzędzia potrzebne do rozwiązania zadań 6, 48, 49 i 51 zostaną wyjaśnione na wykładzie w poniedziałek.

Na ćwiczenia 14 marca obowiązują zadania 37 -- 42, 53, 54, 62, 63, 79

Na ćwiczenia 21 marca obowiązują zadania 64, 65, 74 -- 76 z pierwszej części kursu i jakieś proste zadania z drugiej części: 84 -- 88.

Na ćwiczenia 28 marca obowiązują zadania 89 -- 93 i 95, 96, 100 -- 102.

Na ćwiczenia 11 kwietnia obowiązują zadania 97, 103--111. Pojęcia potrzebne do rozwiązania zadania 111 pojawią się na wykładzie w poniedziałek.

Na ćwiczenia 18 kwietnia obowiązują zadania 113, 114, 121, 123, 131--133. Zadania 113 i 123 są Bardzo Ważne.

Na ćwiczenia 25 kwietnia obowiązują zadania 117--119, 127, 128, 134, 136 (najlepiej rozwiązywać po wykładzie w poniedziałek), 141, 142.

Na ćwiczenia 9 maja obowiązują zadania 122, 124--126 z części II kursu, i zadania 146 -- 149 z części III.

Na ODRABIANE ćwiczenia 17 maja o godzinie 10:15 obowiązują zadania 143 -- 145, 150-- 152 , 155 -- 157.

Na ćwiczenia 23 maja obowiązują zadania 153, 154, 158, 165-- 169, 171, 191

Na ćwiczenia 30 maja obowiązują zadania 172 -- 174, 179-- 181; 192 -- 195

Na ćwiczenia 7 czerwca obowiązują zadania 196 -- 204

Na ćwiczenia 14 czerwca obowiązują zadania 208 -- 211, 219--221

 

 

 

 

 

 

 

 

        Program przedmiotu.

Program przedmiotu obejmuje zagadnienia związane z teorią języków formalnych (wykłady A1 - A8) w zakresie istotnym z punktu widzenia wykształcenia informatycznego, a także dostatecznym dla stworzenia zasobów naturalnych przykładów dla części B i C. Następnie przechodzi się do zagadnień związanych z pojęciami rozstrzygalności i nierozstrzygalności (wykłady R1 -- R8). Ostatnia część kursu poświęcona jest wybranym, elementarnym zagadnieniom złożoności obliczeniowej.

A1. Deterministyczny automat skończony. Języki regularne. Lemat o pompowaniu. Twierdzenie o indeksie.

A2. Niedeterminizm. Niedeterministyczny automat skończony. Determinizacja automatu.

A3. Wyrażenia regularne. Równoważność automatów skończonych i wyrażeń regularnych. Aspekty algorytmiczne: rozstrzyganie równoważności wyrażeń regularnych jest możliwe ale zagadkowo czasochłonne.

A4. Uwagi o automatach na obiektach innych niż słowa skończone: automaty na drzewach skończonych i na słowach nieskończonych.

A5. Gramatyki bezkontekstowe. Przykłady.

A6. Postać Chomsky'ego, lemat o pompowaniu i jego konsekwencje.

A7. Automaty ze stosem. Postać Greibach gramatyk bezkontekstowych. Równoważnośc gramatyk i automatów ze stosem.

A8. Własności zamkniętości klasy języków bezkontekstowych. Niemożliwość determinizacji.

R1. Zbiory rekurencyjne i rekurencyjnie przeliczalne. Funkcje rekurencyjne - częściowe i całkowite. Numeracja funkcji rekurencyjnych. Nierozstrzygalność problemu stopu.

R2. Pojęcie redukcji. Twierdzenie Rice'a. Uwagi o implikacjach tw. Rice'a dla możliwości automatycznej weryfikacji programów.

R3. Maszyna Turinga. Teza Churcha.

R4. Nierozstrzygalność problemu słów dla semiprocesów Thuego.

R5. Nierozstrzygalność problemu słów dla procesów Thuego (problemu słów w półgrupie).

R6. Nierozstrzygalność problemu odpowiedniości Posta, i przykłady nierozstrzygalnych problemów dotyczących gramatyk.

R7. Nierozstrzygalność teorii pierwszego rzędu liczb naturalnych z dodawaniem i mnożeniem (ewentualnie: z dodawaniem, mnożeniem i potęgowaniem). Uwagi o niemożliwości zaksjomatyzowania arytmetyki. Uwagi o dziesiątym problemie Hilberta.

R8. Nierozstrzygalność rachunku predykatów pierwszego rzędu.

C1. Klasa PTIME i PSPACE. Redukcje wielomianowe. Wielomianowa równoważność 3SAT i 3COL.

C2. Niedeterminizm i klasa NP. Przykłady. Przykłady języków z klasy co-NP, oraz z przecięcia NP i co-NP. Charakteryzacja NP jako klasy języków bedących projekcjami języków z P.

C3. NP zupełność. Twierdzenie Cook'a. Więcej przykładów problemów NP-zupełnych. Uwagi o SAT-solverach.

C4. PSPACE. Tw. Savitcha.

C5. Problemy PSPACE-zupełne: QBF i totalność wyrażeń regularnych. Wyjaśnienie zagadki z wykładu A3.

C6. Funkcje jednostronne. Uwagi o teoriozłożonościowych założeniach kryptografii z kluczem publicznym.

C7. Słaba wersja twierdzenia o hierarchii czasowej: różność EXPTIME i PTIME. Uwagi o sposobach uogólnienia tej słabej wersji.

C8. Problemy wymagające dowodliwie czasu wykładniczego. Pebble games. Totalność wyrażeń regularnych.

C9. Inne niż PTIME formalizacje intuicji ''łatwej obliczalności''. Uwagi o klasie FPT. Zrandomizowane algorytmy testowania pierwszości. Uwagi o komputerach kwantowych.

C10. Przykład problemu rozstrzygalnego ale nieelementarnego: totalność wyrażeń regularnych z dopełnieniem.

Literatura podstawowa

Michael Sipser, Wprowadzenie do teorii obliczen, WNT Warszawa 2009. Literatura dodatkowa

[3] Sanjeev Arora, Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.

Kompetencje. Przedmiot dotyczy jednego z głównych obszarów teorii informatyki. Oczekuje się, że osoba która go zaliczy, będzie miała świadomość wszechobecności, w sytuacjach związanych z praktyką informatyczną/algorytmiczną, podstawowych omawianych pojęć i zagadnień (takich jak automat skończony, problem rozstrzygalności, problem złożoności obliczeniowej, złożoność wielomianowa i złożoność NP, redukcja) a także będzie się umiała w praktyce sprawnie tymi pojęciami posługiwać. Ta zdolność do praktycznego posługiwania się stanowi priorytet, dlatego program przedmiotu nie obejmuje wielu zaawansowanych i specjalistycznych zagadnień, skupiając się na możliwie głębokim rozumieniu zagadnień elementarnych. Ponadto forma, w jakiej prowadzi się ćwiczenia tablicowe (w ramach których studenci prezentują na tablicy przygotowane przez siebie wcześniej rozwiązania zadań), przyczynia się do rozwoju kompetencji komunikacyjnych.