Teoria obliczeń i złożoność obliczeniowa 2026

Środa 13¹⁵ - 15⁰⁰ C-4/35 wykład

Czwartek 11¹⁵ - 13⁰⁰ C-4/34 ćwiczenia (dr inż. A. Lauks-Dutka)

Literatura

1. Ch.H. Papadimitriou, Złożoność obliczeniowa, WNT, Warszawa 2002 (ISBN 83-204-2659-6)
2. T.A. Sudkamp, Languages and Machines, Pearson, 2006, (ISBN: 978-81-317-1475-1)
3. J.E. Hopcroft, J.D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, WNT, Warszawa 1994 (ISBN 83-01-11298-0)
4. T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, Wprowadzenie do algorytmów, WNT, Warszawa 1997 (ISBN 83-204-2144-6)
5. M. Cygan, F.V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, S. Saurabh, Parameterized Algorithms, Springer Publishing Company 2015

Notatki i listy zadań

• Część 1 (4h) (12-03-2026 zadania 1-5)
• Część 2 (2h) (19-03-2026 zadania 1-5, 26-03-2026 zadania 6-10)
• Część 3 (6h) (1-04-2026 zadania 1-7, 9-04-2026 zadania 8-16)

Tematy wykładów (w przybliżeniu)

1. Maszyna Turinga. Własności różnych modeli maszyny Turinga. (4-03-2026)
2. Uniwersalna maszyna Turinga. Języki rekurencyjne i rekurencyjnie przeliczalne. Nierozstrzygalność problemu stopu. Twierdzenie Rice'a. (05-03-2026)
3. Podstawy złożoności obliczeniowej Relacje między klasami złożoności. Twierdzenia o hierarchii. Metoda osiągalności. (11-03-2026)
4. Redukcje między problemami. P-zupełność. NP-zupełność. (18-03-2026)
5. Przykłady redukcji między problemami NP-zupełnymi. Klasa co-NP. (25-03-2026)

Zasady zaliczenia kursu

Zaliczenie kursu składa się z dwóch części: zaliczenia ćwiczeń i egzaminu końcowego.

Zaliczenie ćwiczeń

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 alternatywne rozwiązania.
3. Podstawą do wystawienia oceny są wyniki krótkich sprawdzianów. Sprawdziany będą polegały na rozwiązaniu jednego zadania i punktowane od 0 do 5. Materiałem obowiązującym na sprawdzianie są 3 poprzednie ćwiczenia. Sprawdziany przeprowadzane są bez uprzedniej zapowiedzi. Nieobecność na sprawdzianie daje 0. Jeden, najsłabszy sprawdzian studenta w semestrze zostanie anulowany.
4. Podstawą do zaliczenia 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ć 6.
5. Ocena nie podlega poprawianiu po zakończeniu zajęć.

Egzamin końcowy

1. Egzamin jest punktowany od 0 do 5.
2. Na egzaminie jedyną dopuszczalną pomocą naukową jest kartka formatu A4 podpisana w ten sposób aby z odległości 2 metrów dało się ustalić jej właściciela. Oprócz tego student nie ma prawa mieć żadnych innych kartek, książek i innych pomocy. Kartki z treścią zadań i miejscem na rozwiązania oraz brudnopisy dostarcza wykładowca.
3. Dodatkowym warunkiem zaliczenia jest oddanie przez studenta w formie pisemnej (PDF) referatu na wyznaczony temat. Referat powinien być napisany dokładnie, w sposób formalny i przejrzysty. Temat wyznacza prowadzący wykład.

Ocena końcowa

Ocena końcowa jest średnią z punktów z ćwiczeń i punktów z egzaminu zaokrąglonej do najbliższej oceny zgodnej z regulaminem studiów (0.00-2.74 - 2, 2.75-3.24 - 3, 3.25-3.74 - 3.5, itd.).