Karol Gotfryd

Podstawowe informacje

Kurs ten jest przedmiotem obowiązkowym dla 1. roku (1. semestr) studiów II stopnia na kierunku Informatyka Algorytmiczna. Są to ćwiczenia do wykładu prof. Macieja Gębali.

Zajęcia odbywają się w środy w godzinach 9¹⁵–11⁰⁰ w sali 35 bud. C-4.

Listy zadań, zasady zaliczenia oraz literatura podane są na stronie kursu.

Opis kursu (karta przedmiotu): m-W04INA-SM0012G-pwr.pdf

Zasady zaliczenia ćwiczeń

Na ćwiczeniach obowiązują zasady ustalone przez wykładowcę.

1. Zasadniczym celem ćwiczeń jest ułatwienie samodzielnej pracy nad opanowaniem materiału w czasie całego semestru. Punktacja z ćwiczeń jest oceną jakości i intensywności pracy w czasie semestru.
2. Wykładowca ogłasza z odpowiednim wyprzedzeniem listy zadań do samodzielnego rozwiązania przed zajęciami. Na ćwiczeniach prezentowane są rozwiązania zadań. W trakcie rozwiązywania wyjaśniane są wątpliwości dotyczące rozwiązania oraz przedstawiane są alternatywne rozwiązania.
3. Na ćwiczeniach przeprowadzane będą krótkie sprawdziany. Sprawdziany będą polegały na rozwiązaniu jednego zadania i będą punktowane od 0 do 5. Materiałem obowiązującym na sprawdzianie są tematy omawiane na trzech poprzednich ćwiczeniach. Sprawdziany przeprowadzane są bez uprzedniej zapowiedzi. Nieobecność na sprawdzianie daje 0. Jeden, najsłabszy sprawdzian każdej osoby w semestrze zostanie anulowany.
4. Podstawą do obliczenia końcowej punktacji z ćwiczeń jest średnia ze sprawdzianów. Punktacja może być podwyższona przez prowadzącego w zależności od aktywności na ćwiczeniach, nie może jednak przekroczyć 7.
5. Punktacja nie podlega poprawianiu po zakończeniu zajęć.

Puntky ze sprawdzianów i aktywności

Wyniki sprawdzianów przeprowadzanych na ćwiczeniach oraz informacje o punktach z aktywności będą przekazywane przez platformę MS Teams (zakładka „Oceny”).

UWAGA nr 1.
Z wynikami sprawdzianów można nie zgadzać się osobiście w trakcie konsultacji (preferowany sposób), ewentualnie na czacie w Teamsach, mailowo lub po zakończeniu zajęć. Jeśli będzie taka potrzeba, to na zajęciach po sprawdzeniu zadań będę omawiał za co odejmowałem punkty oraz przekazywał najważniejsze uwagi.

UWAGA nr 2.
Jeśli w Teamsach brakuje jakiś punktów (sprawdziany, aktywność) lub punkty nie zgadzają się ze stanem faktycznym, wszelkie uwagi proszę zgłaszać na czacie w Teamsach, mailowo, po zajęciach lub na konsultacjach.

Literatura i materiały do ćwiczeń

• Ch.H. Papadimitriou, Złożoność obliczeniowa, WNT, Warszawa 2002
• Ch.H. Papadimitriou, Computational Complexity, 1^st Edition, Addison-Wesley, 1994
• T.A. Sudkamp, Languages and Machines: An Introduction to the Theory of Computer Science, 3^rd Edition, Pearson, 2006
• J.E. Hopcroft, R. Motwani, J.D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, WNT, Warszawa 2005
• J.E. Hopcroft, R. Motwani, J.D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3^rd Edition, Pearson, 2007
• Introduction to Automata Theory, Languages, and Computation – Jeffrey Ullman's page with many useful materials and resources (lecture notes, slides, exercises, exams etc.)
• M. Sipser, Wprowadzenie do teorii obliczeń, WNT, Warszawa 2009
• T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 4^th edition, MIT Press, 2022
• T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, C. Stein, Wprowadzenie do algorytmów, Wydawnictwo Naukowe PWN, Warszawa 2013 – polskie wydanie podręcznika
• M. Cygan, F.V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, S. Saurabh,Parameterized Algorithms, Springer, 2015
• M. Cygan et al, Parameterized Algorithms – the book website
• Studia Informatyczne – Języki, automaty i obliczenia – materiały z Ważniaka

Notatki i listy zadań

• Część 1 (4h)
• Część 2 (2h)
• Część 3 (6h)
• Część 4 (4h)
• Część 5 (4h)
• Część 6 (2h)
• Część 7 (4h)

Tematy ćwiczeń i omawiane zagadnienia (w przybliżeniu)

1. zajęcia (05.03.2025.)
   • pierwszy wykład (prof. M. Gębala)
   • omówione zagadnienia:
     • maszyna Turinga
     • własności różnych modeli maszyny Turinga
2. zajęcia (12.03.2025.)
   • zadania 1–5 z części 1. notatek
   • omówione zagadnienia:
     • deterministyczne i niedeterministyczne maszyny Turinga (DTM/NTM) – przypomnienie
     • właściwe funkcje złożoności – definicja, przykłady
3. zajęcia (19.03.2025.)
   • zadania 1–6 z części 2. notatek
   • Kartkówka 1 – konstruowanie jednotaśmowej DTM dla zadanego języka
   • omówione zagadnienia:
     • własności zbiorów rekurencyjnych i rekurencyjnie przeliczalnych
     • rekurencyjne i rekurencyjnie przeliczalne podzbiory zbioru liczb naturalnych \(\mathbb{N}\) oraz \(\mathbb{N}^{2}\)
     • generatory dla języków rekurencyjnych i rekurencyjnie przeliczalnych
     • istnienie generatora języka rozpoznawalnego wypisującego słowa bez powtarzania jakiegokolwiek z nich
     • istnienie generatora języka rozstrzygalnego wypisującego słowa w porządku kanonicznym (rosnąco według długości, a dla tej samej długości leksykograficznie)
     • (nie)rozstrzygalność i (nie)rozpoznawalność języków – wprowadzenie
4. zajęcia (26.03.2025.)
   • zadania 7–10 z części 2. notatek
   • Kartkówka 2 – rekurencyjne i rekurencyjnie przeliczalne podzbiory \(\mathbb{N}\)
   • omówione zagadnienia:
     • (nie)rozstrzygalność i (nie)rozpoznawalność języków
     • dowodzenie, że dany język jest lub nie jest rekurencyjny (rozstrzygalny)
     • dowodzenie, że dany język jest lub nie jest rekurencyjnie przeliczalny (rozpoznawalny)
     • redukcje problemu stopu (i nie tylko) do rozważanych problemów
     • przykład języka nierozpoznawalnego, którego dopełnienie też nie jest rozpoznawalne
5. zajęcia (02.04.2025.)
   • zadania 1–7 z części 3. notatek
   • Kartkówka 3 – (nie)rozstrzygalność i (nie)rozpoznawalność języków
   • omówione zagadnienia:
   • klasy złożoności obliczeniowej
   • równoważność definicji klasy \(NP\) opartej o wielomianową weryfikowalność (relacje wielomianowo zrównoważone i wielomianowe rozstrzygalne)
   • problemy \(P\)-zupełne, \(NP\)-zupełne oraz \(NL\)-zupełne
   • problemy spełnialności formuł logicznych – \(2SAT\), \(HORNSAT\), \(3SAT\)
   • złożoność wariantów problemu \(3SAT\) – \(3SAT_3\), \(3SAT_2\)
   • \(NL\)-zupełność problemu \(2SAT\)
6. zajęcia (09.04.2025.)
   • zadania 8–13 z części 3. notatek
   • Kartkówka 4 – złożoność obliczeniowa problemów spełnialności formuł logicznych
   • omówione zagadnienia:
   • klasy złożoności obliczeniowej – ciąg dalszy
   • \(NP\)-zupełne problemy grafowe
   • redukcja \(3SAT\) do problemów \(DOMINATING\ SET(K)\) i \(CLIQUE(K)\)
   • problemy \(CLIQUE(K)\), \(INDEPENDENT\ SET(K)\), \(VERTEX\ COVER(K)\), \(SET\ COVER(K)\) oraz \(DOMINATING\ SET(K)\) – wybrane własności i redukcje
7. zajęcia (16.04.2025.)
   • zadania 14–16 z części 3. notatek, zadania 1–5 z części 4. notatek
   • omówione zagadnienia:
   • \(NP\)-zupełne problemy grafowe – ciąg dalszy
   • problemy kolorowania grafu – \(3COLORING\) oraz \(K\text{-}COLORING\)
   • problem komiwojażera i problem cyklu Hamiltona
   • aproksymowalność – część 1.
   • problem \(MIN\text{-}VERTEX\text{-}COVER\) – strategia zachłanna, algorytm \(\frac12\)-aproksymacyjny
   • problem plecakowy – strategia zachłanna, algorytmy aproksymacyjne
   • aproksymowalność problemu minimalnego pokolorowania grafu
8. zajęcia (23.04.2025.)
   • zadania 6–11 z części 4. notatek
   • Kartkówka 5 – złożoność obliczeniowa problemów grafowych
   • omówione zagadnienia:
   • aproksymowalność – część 2.
   • problem \(BIN\ PACKING\) – algorytm aproksymacyjny, próg aproksymacyjny
   • metryczny problem komiwojażera (z nierównością trójkąta)
   • algorytmy aproksymacyjne dla problemu komiwojażera z nierównością trójkąta
   • wielomianowe schematy aproksymacyjne, klasa \(FPTAS\)
   • algorytm \(\frac{2}{3}\)-aproksymacyjny dla problemu maksymalnego podgrafu planarnego
9. zajęcia (30.04.2025.)
   • 9. wykład (prof. M. Gębala)
   • zagadnienia do omówienia:
     • kernelizacja
     • iteracyjna kompresja
10. zajęcia (07.05.2025.)
    • zadania 1–5 z części 5. notatek
    • zagadnienia do omówienia:
    • złożoność parametryczna, fixed parameter tractability – część 1.
    • związki pokryć wierzchołkowych ze skojarzeniami w grafach
    • wyznaczanie minimalnego pokrycia wierzchołkowego na podstawie maksymalnego skojarzenia w grafie dwudzielnym
    • algorytmy rozstrzygające istnienie pokrycia wierzchołkowego rozmiaru \(\leq k\) i ich własności – część 1.
    • podstawowy algorytm o złożoności \(O(k|V|^{k+1})\)
    • algorytm typu branch & bound o złożoności \(O(k2^{k}|V|)\)
11. zajęcia (14.05.2025.)
    • zadania 6–10 z części 5. notatek
    • zagadnienia do omówienia:
    • złożoność parametryczna, fixed parameter tractability – część 2.
    • algorytm kernelizacji dla problemu \(VERTEX\ COVER(K)\) o złożoności \(O(k|V| + 2^{k}k^{2})\)
    • algorytmy kernelizacji, reguły upraszczania
    • algorytm z iteracyjną kompresją dla problemu \(VERTEX\ COVER(K)\) o złożoności \(O(|E||V|2^{k+1})\)
    • algorytm FPT dla problemu \(Min2SAT(K)\)
    • algorytmy kernelizacji a problem \(CLIQUE(K)\)
12. zajęcia (21.05.2025.)
    • zadania 1–8 z części 6. notatek
    • zagadnienia do omówienia:
    • wielomianowe klasy losowe
    • klasa \(RP\), \(PP\) i \(BPP\) – podstawowe własności
    • zamkniętość wielomianowych klas losowych na sumy, przekroje i redukcje
    • związki między klasami \(PP\) oraz \(PSPACE\)
    • klasa \(PP\), \(PP_{\varepsilon}\) i ich wybrane własności
    • związki między klasami \(NP\), \(BPP\) i \(RP\)
13. zajęcia (28.05.2025.)
    • zadania 1–4 z części 7. notatek
    • zagadnienia do omówienia:
    • klasa złożoności pamięciowej \(PSPACE\), problemy \(PSPACE\)-zupełne – przykłady
    • problemy dla wyrażeń regularnych – czy \(L(r) = \Sigma^{*}\)
    • \(PSPACE\)-zupełność problemu równoważności wyrażeń regularnych
    • gry na grafie skierowanym, pytania o strategię wygrywającą dla gier dwuosobowych
    • alternujące maszyny Turinga – część 1.
    • związki między klasami \(APSPACE\) i \(EXPTIME\)
14. zajęcia (28.05.2025.)
    • zadania 5–8 z części 7. notatek
    • zagadnienia do omówienia:
    • alternujące maszyny Turinga – część 2.
    • klasy złożoności \(AP\) i \(AL\)
    • \(AP\)-zupełność problemu \(QSAT\)
    • związki między klasami \(AP\) i \(PSPACE\) oraz \(AL\) i \(P\)
    • podliniowe maszyny alternujące i klasa \(ATIME(\log n)\)