Jerzy Marcinkowski

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

Kurs dla II roku Informatyki, edycja 2017

 

 


 

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. Tu jest wersja zbioru przepoczwarzająca się w angielskojęzyczną.

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

Pierwsza część egzaminu odbędzie się we środę 12 kwietnia w porze wykładu.

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

Trzecia część egzaminu odbędzie się we środę 14 czerwca w porze wykładu.

Wyniki egzaminu są wiadomogdzie .

Pewnie niektórzy będą chcieli przyjść na egzamin poprawkowy. Odbędzie się on w piątek 1 września (część 2 i 3) i w poniedziałek 4 września (część 1).

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 23 lutego obowiązywać będą zadania 1, 2, 5, 6, 7, 9 i 10 ze zbioru.

Na ćwiczenia 2 marca obowiązują zadania 11, 12, 37 -- 39, 21 -- 23.

Na ćwiczenia 9 marca obowiązują zadania 14, 15, 17, 27, 30, 43 --45.

Na ćwiczenia 16 marca obowiązują zadania 18 --20, 25, 31, 47 -- 49, 51, 53.

Na ćwiczenia 23 marca obowiązują zadania 40 -- 42, , 81, 82, 84, 85, 86; zad. 42 jest za 2 punkty.

Na ćwiczenia 30 marca obowiązują zadania 77 -- 80, 87 -- 90, 97, 98. Pojęcia do zadań 97 i 98 pojawią się na wykładzie w poniedziałek 27 marca.

Na ćwiczenia 6 kwietnia obowiązują zadania 63, 71-73, 92, 99, 101--103, UWAGA, zmiana 105 .

Na ćwiczenia 13 kwietnia obowiązują zadania 32, 33, 74--76, 104, 106, 127 -- 130

Na ćwiczenia 20 kwietnia obowiązują zadania 100 (za 2 pkt.),110, 115, 116, 118

Na ćwiczenia 27 kwietnia obowiązują zadania 107, 119 -- 122. Pojęcia do zadań 121 i 122 pojawią się na wykładzie 24 kwietnia.

Na ćwiczenia 4 maja maja obowiązują zadania 143 -- 148 i 153.

Na ćwiczenia 18 maja obowiązują zadania 149--152, 154, 155 i 162.

Na ćwiczenia 25 maja obowiązują zadania 138, 165, 175, 182, 188, 189, 192, 194 i 195.

Na ćwiczenia 1 czerwca obowiązują zadania 176--178, 193, 196, 197, 212--214.

Na ćwiczenia 8 czerwca obowiązują zadania 201--205.

 

 

 

 

 

 

 

 

        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.