Literatury z poprzednich lat
2010-2012
- Graph Theory
czas: czwartek 16:15-18:00
miejsce: GCh 333
Przedmiot studiujemy na podstawie książki "Graph Theory" autorstwa
Reinharda Diestela.
2009-2010
- Extremal Graph Theory
Przedmiot studiujemy na podstawie książki "Extremal GraphTheory" autorstwa Béla Bollobása.
2008-2009
- Computers and Intractability: A Guide to the Theory of NP-Completeness
czas: wtorek 16:15 - 18:00
miejsce: GG 405/5
Przedmiot studiujemy na podstawie książki "Computers and Intractability: A Guide to the Theory of NP-Completeness" autorstwa Michaela R. Gareya i Davida S. Johnsona. Jest to książka o klasach trudności problemów decyzyjnych i optymalizacyjnych. W książce tej również jest podanych ponad 300 problemów NP-zupełnych. Poniżej znajduje się konspekt tego przedmiotu.
Konspekt (uzupełniany w miarę przerabiania):
1. Problemy wielomianowe, klasa NP oraz problemy NP-zupełne (formalne definicje wykorzystujące maszyny Turinga). Wielomianowa redukcja jednego problemu decyzyjnego do drugiego. Twierdzenie Cooka, czyli twierdzenie mówiące o tym, że problem SAT jest problemem NP-zupełnym (NPC).
2. Wykazanie NP-zupełności następujących problemów: 3-SAT, 3-wymiarowego skojarzenia, podziału zbioru, pokrycia wierzchołkowego, istnienia kliki, istnienia cyklu Hamiltona.
3. Umówienie technik udowadniania NP-zupełności takich jak "ograniczenie", "lokalna zamiana" i "rzeźba totalna" na przykładach.
4. Rozwiązywanie zadań z rozdziału 3.3 metodami z punktu trzeciego.
5. Używanie NP-zupełności do analizy problemów. Badanie NP-zupełności podproblemów danego problemu NP-zupełnego. Udowodnienie, że problem 3-kolorowalności grafu jest NP-zupełny dla grafów o maksymalnym stopniu co najwyżej 4, jak również dla grafów planarnych. Algorytmy pseudo-wielomianowe na przykładzie problemu podziału zbioru.
6. Algorytmy pseudo-wielomianowe - formalna definicja. Problemy numeryczne. NP-zupełność w silnym sensie. Udowodnienie silnej NP-zupełności problemów 4-podziału oraz 3-podziału.
7. Pseudo-wielomianowa transformacja jednego problemu do drugiego. Udowodnienie silnej NP-zupełności problemu szeregowania zadań o ograniczonych czasach oraz problemu poddrzewowego izomorfizmu. Złożoność czasowa jako funkcja naturalnych parametrów.