Optymalizacja kombinatoryczna, ćwiczenia, semestr letni 2003/2004

• Termin: czwartek, 14:15-15:45.
• Miejsce: sala 3150.

Zaliczenie ćwiczeń

Tematy obowiązujące podczas zaliczenia:

1. Skojarzenia w grafach dwudzielnych
2. Tw. Halla, Tw. Vizinga
3. Kolorowanie krawędziowe (grafy dwudzielne)
4. 4--kolorowanie grafów kubicznych
5. Programowanie liniowe (*opcjonalnie*)
6. Algorytmy aproksymacyjne (Set Cover)
7. Przepływy (Ford Fulkerson, 3 Hindusów, zastosowania)
8. MST (Prim/Kruskal/Boruvka)
9. MST (Yao/Boruvka)
10. MST (Weryfikacja)
11. Trudność aproksymacji

Zalicznie polega na odpowiedzi na dwa zagadnienia (jedno z nich można samemu wybrać).
Termin: 15.06.2004 10-15
Miejsce: MIM UW, pokój 4060
(dokładną godzinę proszę ustalić drogą mailową)