Złożoność obliczeniowa 2009
Wtorek 915 - 1100 A-1/204 wykład
Czwartek 915 - 1100 TP/TN C-4/35 ćwiczenia
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. (06-10-2009)
- Twierdzenia o Hierarchii. Redukcje między problemami. (13-10-2009)
- P-zupełność. NP-zupełność. (20-10-2009)
- Przykłady redukcji dla problemów NP-zupełnych. (27-10-2009)
- co-NP i problemy funkcyjne. (3-11-2009)
- Obliczenia losowe. (17-11-2009)
- Sieci logiczne. (24-11-2009)
- Obliczenia równoległe. Klasa NC. (01-12-2009)
- Aproksymowalność. (8-12-2009)
- Schematy aproksymacyjne. (15-12-2009)
- Pamięć logarytmiczna. (22-12-2009)
- Pamięć wielomianowa. Problemy PSPACE-zupełne. (05-01-2010)
- Klasa #P. (12-01-2010)