Teoria obliczeń i złożoność obliczeniowa 2023
Czwartek 1515 - 1655 C-3/22 wykład
Czwartek 1115 - 1300 C-3/20 ćwiczenia (dr inż. K. Gotfryd)
Egzamin: 5 luty 2024, 915 - 1045, C-16/D1.1
Egzamin poprawkowy: 12 luty 2024, 915 - 1045, C-16/D1.1.
Literatura
- Ch.H. Papadimitriou, Złożoność obliczeniowa, WNT, Warszawa 2002 (ISBN 83-204-2659-6)
- T.A. Sudkamp, Languages and Machines, Pearson, 2006, (ISBN: 978-81-317-1475-1)
- J.E. Hopcroft, J.D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, WNT, Warszawa 1994 (ISBN 83-01-11298-0)
- T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, Wprowadzenie do algorytmów, WNT, Warszawa 1997 (ISBN 83-204-2144-6)
- 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ń
Lista referatów
Tematy wykładów (w przybliżeniu)
- Maszyna Turinga. Własności różnych modeli maszyny Turinga. (5-10-2023)
- Uniwersalna maszyna Turinga. Języki rekurencyjne i rekurencyjnie przeliczalne. (5-10-2023)
- Nierozstrzygalność problemu stopu. Twierdzenie Rice'a. (12-10-2023)
- Podstawy złożoności obliczeniowej Relacje między klasami złożoności. Twierdzenia o hierarchii. Metoda osiągalności. (19-10-2023)
- Redukcje między problemami. P-zupełność. NP-zupełność. (26-10-2023)
- Przykłady redukcji między problemami NP-zupełnymi. Klasa co-NP. (9-11-2023)
- Aproksymowalność. (16-11-2023)
- Klasy PTAS i FPTAS. (23-11-2023)
- Złożoność parametryczna na przykładzie Vertex Cover. (30-11-2023)
- Kernelizacja i iteracyjna kompresja. (7-12-2023)
- Obliczenia losowe. (14-12-2023)
- Klasa PSPACE. Alternujące maszyny Turinga. (21-12-2023)
- Klasa AP. Klasa AL. Hierarchia wielomianowa. (11-01-2023)
- Sieci logiczne. Obliczenia równoległe. Klasa NC. (18-01-2023)
- Problemy zliczania. (25-01-2023)
Zasady zaliczenia kursu
Zaliczenie kursu składa się z dwóch części: zaliczenia ćwiczeń i egzaminu końcowego.
Zaliczenie ćwiczeń
- 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.
- 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.
- 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.
- 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.
- 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.
- Ocena nie podlega poprawianiu po zakończeniu zajęć.
Egzamin końcowy
- Zdanie egzaminu jest warunkiem koniecznym zaliczenia kursu.
- 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).