Jerzy Marcinkowski

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

Kurs dla II roku Informatyki, edycja 2020

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ę ???

Druga część egzaminu odbędzie się ???

Trzecia część egzaminu odbędzie się ????

Wyniki egzaminu będą niewiadomogdzie .

Pewnie niektórzy będą chcieli przyjść na egzamin poprawkowy. Odbędzie się on ???? września

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 4 marca obowiązują zadania 1--4 i 7--12  

Na ćwiczenia 11 marca obowiązują zadania 21--23, 25, 41--43 oraz 78--81  

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.