Złożoność obliczeniowa 2006
Poniedziałek 1115 - 1300 C-7/303a
wykład
Czwartek 1515 - 1655 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ń
Kolokwium odbędzie się na wykladzie 22 stycznia 2007.
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. (02-10-2006)
- Twierdzenia o Hierarchii. Redukcje między problemami. (09-10-2006)
- NP-zupełność. Redukcje do problemów NP-zupełnych. (16-10-2006)
- Przykłady redukcji dla problemów NP-zupełnych. (23-10-2006)
- co-NP. (30-10-2006)
- Obliczenia losowe. (6-11-2006)
- Sieci logiczne. (13-11-2006)
- Aproksymowalność. (20-11-2006)
- Schematy aproksymacyjne. (27-11-2006)
- Obliczenia równoległe. Klasa NC. (4-12-2006)
- Pamięć logarytmiczna. (11-12-2006)
- Klasa #P. (18-12-2006)
- Pamięć wielomianowa. Problemy PSPACE-zupełne. (8-01-2007)
- Podsumowanie. (15-01-2007)
- Kolokwium. (22-01-2007)