Karol Gotfryd

Podstawowe informacje

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

Zajęcia odbywają się w czwartki w godzinach 11¹⁵–13⁰⁰ w sali D2.2 bud. C-16.

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 studentom samodzielnej pracy nad opanowaniem materiału w czasie całego semestru. Punktacja z ćwiczeń jest oceną jakości i intensywności pracy studenta w czasie semestru.
2. Wykładowca ogłasza z odpowiednim wyprzedzeniem listy zadań do samodzielnego rozwiązania przed zajęciami. Na ćwiczeniach studenci prezentują 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 studenta 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 studenta 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 się nie zgadzać osobiście w trakcie konsultacji, na czacie w Teamsach, ewentualnie mailowo lub – w szczególnych przypadkach – 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 (preferowany sposób), ewentulanie 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, 3^rd edition, MIT Press, 2009
• 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 (29.02.2024.)
   • pierwszy wykład (prof. M. Gębala)
   • omówione zagadnienia:
   • maszyna Turinga
   • własności różnych modeli maszyny Turinga
2. zajęcia (07.03.2024.)
   • zadania 1–4 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 (14.03.2024.)
   • zadanie 5 z części 1. notatek, zadania 1–3 z części 2. notatek
   • Kartkówka 1 – konstruowanie DTM dla zadanego języka
   • omówione zagadnienia:
   • właściwe funkcje złożoności – przykłady (cd.)
   • własności zbiorów rekurencyjnych i rekurencyjnie przeliczalnych
   • rekurencyjne i rekurencyjnie przeliczalne podzbiory zbioru liczb naturalnych \(\mathbb{N}\) oraz \(\mathbb{N}^{2}\)
4. 21.03.2024 – zamiana (ćwiczenia z Metod Optymalizacji z prof. P. Zielińskim)
4. zajęcia (04.04.2024.)
   • zadania 4–9 z części 2. notatek
   • Kartkówka 2 – rekurencyjne i rekurencyjnie przeliczalne podzbiory \(\mathbb{N}\)
   • omówione zagadnienia:
   • 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
   • 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
5. zajęcia (11.04.2024.)
   • zadanie 10 z części 2. notatek, zadania 1–4, 7 z części 3. notatek
   • Kartkówka 3 – (nie)rozstrzygalność i (nie)rozpoznawalność języków
   • omówione zagadnienia:
   • przykład języka nierozpoznawalnego, którego dopełnienie też nie jest rozpoznawalne
   • 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\)
6. zajęcia (18.04.2024.)
   • zadania 4, 5, 8–13 z części 3. notatek
   • omówione zagadnienia:
   • złożoność wariantów problemu \(3SAT\) – \(3SAT_3\), \(3SAT_2\)
   • \(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 (25.04.2024.)
   • zadania 14–16 z części 3. notatek, zadania 1–3 z części 4. notatek
   • Kartkówka 4 – złożoność obliczeniowa problemów spełnialności formuł logicznych
   • 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
8. zajęcia (29.04.2024.) – zamiana (zaległe zajęcia z dnia 21.03.2024.)
   • zadania 4–9, 11 z części 4. notatek
   • omówione zagadnienia:
   • aproksymowalność – część 2.
   • problem plecakowy (cd.) – algorytmy aproksymacyjne
   • aproksymowalność problemu minimalnego pokolorowania grafu
   • 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
   • algorytm \(\frac{2}{3}\)-aproksymacyjny dla problemu maksymalnego podgrafu planarnego
9. zajęcia (09.05.2024.)
   • zadanie 10 z części 4. notatek, zadania 1–5 z części 5. notatek
   • zagadnienia do omówienia:
   • wielomianowe schematy aproksymacyjne, klasa \(FPTAS\)
   • złożoność parametryczna, fixed parameter tractability – część 1.
   • związki pokryć wierzchołkowych ze skojarzeniami w grafach
   • 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|)\)
10. zajęcia (16.05.2024)
    • zadania 6–10 z części 5. notatek
    • zagadnienia do omówienia:
    • złożoność parametryczna, fixed parameter tractability – część 2.
    • algorytmy kernelizacji, reguły upraszczania
    • algorytm kernelizacji dla problemu \(VERTEX\ COVER(K)\) o złożoności \(O(k|V| + 2^{k}k^{2})\)
    • 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)\)
11. zajęcia (23.05.2024)
    • 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
    • klasa \(PP\), \(PP_{\varepsilon}\) i ich wybrane własności
    • związki między klasami \(PP\) oraz \(PSPACE\)
    • związki między klasami \(NP\), \(BPP\) i \(RP\)
12. zajęcia (06.06.2024)
    • 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^{*}\), równoważność 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\)
13. zajęcia (13.06.2024)
    • 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)\)