Jerzy Marcinkowski

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

Kurs dla II roku Informatyki, edycja 2019

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), .

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

Pierwsza część egzaminu odbędzie się 27 marca w porze wykładu.

ZmiANA ZMIANA!!!!!: Druga część egzaminu odbędzie się ***18*** czerwca o ***10:00***.

ZmiANA: Trzecia część egzaminu odbędzie się 12 czerwca w porze wykładu.

Wyniki egzaminu będą niewiadomogdzie .

Pewnie niektórzy będą chcieli przyjść na egzamin poprawkowy. Odbędzie się on w poniedziałek 9 września o 10 rano (1 część), we wtorek 10 września o 10 rano (2 część) i we wtorek 10 września o 1 po południu (3 część). Wszystkie części w wielkiej sali dziennikarstwa.

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

 

 

 

 

 

 

Na ćwiczenia 25 lutego obowiązywać będą zadania 1--3, 6, 39--40 ze zbioru.

Na ćwiczenia 4 marca obowiązywać będą zadania 4,8--11, 14, 19--23 ze zbioru.

Na ćwiczenia 11 marca obowiązywać będą zadania 13, 15-17, 27, 46, 48, 74-77 ze zbioru.

Na ćwiczenia 18 marca obowiązywać będą zadania 33--38; 42, 44, 45, 49, 52 ze zbioru.

Na ćwiczenia 25 marca obowiązywać będą zadania 56-- 58, 64--66 68, 69 oraz 70--73 ze zbioru.

Na ćwiczenia 1 kwietnia obowiązywać będą zadania 78--85 ze zbioru.

Na ćwiczenia 8 kwietnia obowiązywać będą zadania 86--89 i 91--96 ze zbioru.

Na ćwiczenia 15 kwietnia obowiązywać będą zadania 97--102 i 105, 106 oraz 122 i 123 ze zbioru.

Na ćwiczenia 29 kwietnia obowiązywać będą zadania 107, 109--113 oraz 125 ze zbioru.

Na ćwiczenia 6 maja obowiązywać będą zadania 114 --118, 124, oraz 130--132 ze zbioru.

Na ćwiczenia 13 maja obowiązywać będą zadania 133 --141 oraz 146 ze zbioru.

Na ćwiczenia 20 maja obowiązywać będą zadania 142--145 oraz 147, 148, 151, 152 i 178 ze zbioru.

Na ćwiczenia 27 maja obowiązywać będą zadania 154--156, 179--184 oraz 186, 187 i ze zbioru.

Na ćwiczenia 4 czerwca obowiązywać będą zadania 161--164 oraz 168, 172, 174, 175, 189 i 196 ze zbioru.

Na ćwiczenia 11 czerwca obowiązywać będą zadania 191--194 oraz 199--201 ze zbioru.

 

 

 

 

 

 

 

 

        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.