Złożoność obliczeniowa 2008
Wtorek 730 - 900 C-11/P.01 wykład
Środa 1515 - 1655 TP/TN C-7/303a ćwiczenia
Kolokwium zaliczeniowe odbędzie się na wykladzie 27
stycznia 2009.
Kolokwium poprawkowe odbędzie się 10 lutego o godz. 1715 w sali D-1/311
Literatura
- Ch.H. Papadimitriou, Złożoność obliczeniowa, WNT, Warszawa 2002
(ISBN 83-204-2659-6)
- 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)
Listy zadań
Zasady zaliczenia kursu
- Zaliczenie kursu następuje przez zaliczenie kolokwium końcowego.
- Zasadniczym celem ćwiczeń jest ułatwienie studentom samodzielnej pracy
nad opanowaniem materiału w czasie całego 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.
- Na każde ćwiczenia jest przygotowywana osobna lista zadań, ogłaszana
co najmniej na trzy dni przed zajęciami. Na ćwiczeniach rozwiązywane są
wybrane zadania z tej listy. Decyzję odnośnie wyboru zadań do rozwiązania
podejmuje prowadzący.
- Dodatkowym warunkiem zaliczenia jest oddanie przez studenta w formie
pisemnej (PDF) wyznaczonych zadań zrobionych na ćwiczeniach. Oddawane
zadanie powinno być rozwiązane dokładnie, w sposób formalny i przejrzysty.
Zadanie wyznacza prowadzący ćwiczenia.
- Kolokwium końcowe jest pisane na ostatnim wykładzie.
- Na kolokwium 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.
- Oceną końcową jest ocena z kolokwium która może być podwyższona za
aktywność na ćwiczeniach.
Tematy wykładów (w przybliżeniu)
- Złożoność obliczeniowa. Relacje między klasami złożoności. (07-10-2008)
- Twierdzenia o Hierarchii. Redukcje między problemami. (14-10-2008)
- P-zupełność. NP-zupełność. (21-10-2008)
- Przykłady redukcji dla problemów NP-zupełnych. (28-10-2008)
- co-NP i problemy funkcyjne. (4-11-2008)
- Obliczenia losowe. (13-11-2008)
- Wykład przełożony z powodu wyjazdu. (18-11-2008)
- Sieci logiczne. (25-11-2008)
- Obliczenia równoległe. Klasa NC. (2-12-2008)
- Aproksymowalność. (9-12-2008)
- Schematy aproksymacyjne. (16-12-2008)
- Pamięć wielomianowa. Problemy PSPACE-zupełne. (6-01-2009)
- Klasa #P. (13-01-2009)
- Podsumowanie. (20-01-2009)
- Kolokwium. (27-01-2009)