Złożoność obliczeniowa 2007

Środa 7³⁰ - 9⁰⁰ C-7/303a wykład

Czwartek 15¹⁵ - 16⁵⁵ TP C-4/35 ćwiczenia

Kolokwium zaliczeniowe odbędzie się na wykladzie 23 stycznia 2008.

Z powodu wyjazdu prowadzącego na konferencję wykład z 12 grudnia jest przeniesiony na 6 grudnia w sali C-4/35 o godzinie 15¹⁵, a ćwiczenia z 13 grudnia przeniesione na 20 grudnia, pora i sala takie same.

Kolokwium poprawkowe odbędzie się 4 lutego o godz. 17¹⁵ w sali A-1/329

Literatura

1. Ch.H. Papadimitriou, Złożoność obliczeniowa, WNT, Warszawa 2002 (ISBN 83-204-2659-6)
2. J.E. Hopcroft, J.D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, WNT, Warszawa 1994 (ISBN 83-01-11298-0)
3. T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, Wprowadzenie do algorytmów, WNT, Warszawa 1997 (ISBN 83-204-2144-6)

Listy zadań

• Lista nr 1 na 4/11 października
• Lista nr 2 na 18 października
• Lista nr 3 na 15 listopada
• Lista nr 4 na 22 listopada
• Lista nr 5 na 29 listopada
• Lista nr 6 na 20 grudnia (ćwiczenia przeniesione z 13 grudnia)
• Lista nr 7 na 10 stycznia

Zasady zaliczenia kursu

1. Zaliczenie kursu następuje przez zaliczenie kolokwium końcowego.
2. Zasadniczym celem ćwiczeń jest ułatwienie studentom samodzielnej pracy nad opanowaniem materiału w czasie całego semestru.
3. 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.
4. 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.
5. 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.
6. Kolokwium końcowe jest pisane na ostatnim wykładzie.
7. 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.
8. 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)

1. Złożoność obliczeniowa. Relacje między klasami złożoności. (03-10-2007)
2. Twierdzenia o Hierarchii. Redukcje między problemami. (10-10-2007)
3. P-zupełność. NP-zupełność. (17-10-2007)
4. Przykłady redukcji dla problemów NP-zupełnych. (24-10-2007)
5. co-NP. (31-10-2007)
6. Obliczenia losowe. (7-11-2007)
7. Sieci logiczne. (14-11-2007)
8. Aproksymowalność. (21-11-2007)
9. Schematy aproksymacyjne. (28-11-2007)
10. Obliczenia równoległe. Klasa NC. (5-12-2007)
11. Pamięć logarytmiczna. (6-12-2007) (wykład przeniesiony z 12 grudnia)
12. Pamięć wielomianowa. Problemy PSPACE-zupełne. (19-12-2007)
13. Klasa #P. (9-01-2008)
14. Podsumowanie. (16-01-2008)
15. Kolokwium. (23-01-2008)