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

Czwartek 12⁰⁰ - 13³⁰ D-1/215 wykład

Czwartek 15²⁰ - 16⁵⁵ D-1/215 ćwiczenia (dr inż. K. Gotfryd)

Egzamin: 3 luty 2023, 12¹⁵ - 13⁴⁵, D-1/215.
Egzamin poprawkowy: 10 luty 2023, 12¹⁵ - 13⁴⁵, D-1/215.

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. H. Barendregt, E. Barendsen, Introduction to Lambda Calculus, 1994

Notatki i listy zadań

Lista referatów

• Część 1 (4h) (04-10-2022 zadania 1-4, 13-10-2022 zadania 5-8, 20-10-2022 zadania 9-11)
• Część 2 (2h) (27-10-2022 zadania 1-6)
• Część 3 (2h) (03-10-2022 zadania 1-4, 10-12-2022 zadania 5-7)
• Część 4 (6h) (17-11-2022 zadania 1-4, 24-11-2022 zadania 5-8)
• Część 5 (4h) (01-12-2022 zadania 1-4, 08-12-2022 zadania 5-7)
• Część 6 (2h) (15-12-2022 zadania 1-4, 22-13-2022 zadania 5-8)
• Część 7 (4h) (12-01-2023 zadania 1-4, 19-01-2023 zadania 5-8)
• Część 8 (2h) (26-01-2023 zadania 1-3)
• Część 9 (2h)

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

1. Maszyna Turinga. Własności różnych modeli maszyny Turinga. (4-10-2022)
2. Uniwersalna maszyna Turinga. Języki rekurencyjne i rekurencyjnie przeliczalne. (13-10-2022)
3. Nierozstrzygalność problemu stopu. Twierdzenie Rice'a. (20-10-2022)
4. Teza Churcha. Inne modele obliczeń. Maszyna licznikowa. (27-10-2022)
5. Podstawy złożoności obliczeniowej Relacje między klasami złożoności. Twierdzenia o hierarchii. Metoda osiągalności. (03-11-2022)
6. Redukcje między problemami. P-zupełność. NP-zupełność. (10-11-2022)
7. Przykłady redukcji między problemami NP-zupełnymi. Klasa co-NP. (17-11-2022)
8. Aproksymowalność. (24-11-2022)
9. Aproksymowalność. (01-12-2022)
10. Obliczenia losowe. (08-12-2022)
11. Klasa PSPACE. Alternujące maszyny Turinga. (15-12-2022)
12. Klasa AP. Klasa AL. Hierarchia wielomianowa. (22-12-2022)
13. Sieci logiczne. Obliczenia równoległe. Klasa NC. (12-01-2023)
14. Problemy zliczania. (19-01-2023)
15. Podsumowanie wykładu. Omówienie referatów. (26-01-2023)

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. Ocena 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 listy. Sprawdziany przeprowadzane są bez uprzedniej zapowiedzi. Nieobecność na sprawdzianie daje 0. Jeden, najsłabszy sprawdzian studenta w semestrze zostanie anulowany.
4. Podstawą do oceny na zaliczenie jest średnia ze sprawdzianów zaokrąglona w górę do najbliższej oceny. Ocena może być podwyższona przez prowadzącego w zależności od aktywności studenta na ćwiczeniach.
5. 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 ćwiczenia.
6. Ocena nie podlega poprawianiu po zakończeniu zajęć.

Egzamin końcowy

1. Zdanie egzaminu jest warunkiem koniecznym zaliczenia kursu.
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.

Ocena końcowa

Ocena końcowa jest średnią z oceny na zaliczenie i oceny z egzaminu zaokrąglonej w górę do najbliższej oceny (2.5 zaokrągla się jednak do 2.0).