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ą)