******Program przedmiotu.**
Program przedmiotu obejmuje zagadnienia związane z teorią językow formalnych
(wykłady A1 - A8) w zakresie istotnym z punktu widzenia wykształcenia
informatycznego, a także dostatecznym dla stworzenia zasobow naturalnych
przykładow 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. Rownoważność automatow skończonych i wyrażeń
regularnych. Aspekty algorytmiczne: rozstrzyganie rownoważ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.
Rownoważnośc gramatyk i automatow ze stosem.
A8. Własności zamkniętości klasy językow 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 programow.
R3. Maszyna Turinga. Teza Churcha.
R4. Nierozstrzygalność problemu słow dla semiprocesow Thuego.
R5. Nierozstrzygalność problemu słow dla procesow Thuego (problemu słow w
połgrupie).
R6. Nierozstrzygalność problemu odpowiedniości Posta, i przykłady
nierozstrzygalnych problemow 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 predykatow pierwszego rzędu.
C1. Klasa PTIME i PSPACE. Redukcje wielomianowe. Wielomianowa rownoważność
3SAT i 3COL.
C2. Niedeterminizm i klasa NP. Przykłady. Przykłady językow z klasy co-NP,
oraz z przecięcia NP i co-NP. Charakteryzacja NP jako klasy językow bedących
projekcjami językow z P.
C3. NP zupełność. Twierdzenie Cook'a. Więcej przykładow problemow 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: rożność EXPTIME i PTIME.
Uwagi o sposobach uogolnienia 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**
[1] Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman, Projektowanie i
analiza algorytmow komputerowych, PWN, Warszawa 1983. [2] 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ł ownych obszarow teorii
informatyki. Oczekuje się, że osoba ktora 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 ktorych studenci prezentują
na tablicy przygotowane przez siebie wcześniej rozwiązania zadań), przyczynia
się do rozwoju kompetencji komunikacyjnych.
**Wymagania:** Logika dla informatyk ow i Matematyka dyskretna
sem. letni 2023/24: piątki, godz. 12.30-13.30, pokój 311, a także konsultacje zdalne za pośrednictwem MSTeams, w piątki, godz. 19.15 - 19.30 i dłużej, jeżeli będą zainteresowani.
Zapraszam też na konsultacje zdalne lub w Instytucie w terminach uzgodnionych ze stosownym wyprzedzeniem np. pocztą elektroniczną.
