Marek Cygan

Wykład 17. Końcówka algorytmów grafowych

 Ostatnie klasyczne algorytmy grafowe, jakie pozostały do dobicia:

  • 2-SAT raz jeszcze.
  • Funkcja low, mosty, punkty artykulacji, dwuspójne składowe.
  • MST (najtańsze drzewo rozpinające), zastosowania (w tym zadanie Aviamachinations z SGU).

Wykład poprowadził Marek Cygan. Lokalizacja: 3130. Termin: 31.03.2009, 16:15-18:00.

Tutaj znajdują się notatki Bartka Nowierskiego na temat mostów, punktów artykulacji i dwuspójnych składowych (Uwaga, znajduje się tam nieprawdziwe stwierdzenie, które mówi że most łączy dwa punkty artykulacji). Załączam również kody Kuby Radoszewskiego powstałe na bazie materiałów z podanej strony: mosty i punkty artykulacji oraz dwuspójne. Jako ćwiczenie polecam rozwiązać następujące zadanie

Dostępne materiały: Nagrania.

Wykład 14. Ciekawsze algorytmy grafowe

 Wykład był kontynuacją poprzedniego; zostały na nim omówione kolejne, tym razem już mniej znane i mniej powszechnie rozumiane algorytmy grafowe:

  • Różne triki w zadaniach na drzewa (+ zadanie domowe).
  • Jak najkrócej napisać rozwiązanie 2SAT-a, czy jak kto woli zadania o Spokojnej komisji z VIII OI, wraz z przykładami zastosowań.

Wykład poprowadził Marek Cygan. Lokalizacja: 3130. Termin: 03.03.2009, 16:15-17:45.

UWAGA: Nagranie zawiera niepoprawne uzasadnienie ostatniego algorytmu. W dodatku sam algorytm też jest niepoprawny, kontrprzykład to (x1 lub x1) i (x1 lub x2) i (nie(x1) lub nie(x2)). Na początku wykładu 17. znajduje się sprostowanie.

Dostępne materiały: Nagrania.

Wykład 8. Skojarzenia i przepływy (część II)

Zagadnienia, które były poruszone na wykładzie (niektóre z nich mogą zostać przeniesione do kolejnego wykładu o tej samej nazwie, jeśli taki się odbędzie):

  • Dokończenie nietrywialnych zastosowań twierdzenia o maksymalnym przepływie i minimalnym przekroju.
  • Skojarzenie: postawienie problemu, algorytm oparty na ścieżkach. powiększających z udoskonaleniem Tomka Idziaszka.
  • Pokrycie wierzchołkowe i maksymalny zbiór niezależny w grafie dwudzielnym.
  • Twierdzenie Mengera (wersja krawędziowa i wierzchołkowa).
  • Maksymalny przepływ o minimalnym koszcie (jeśli zdążymy).

Wykład poprowadził Marek Cygan. Lokalizacja: 3150. Termin: 21.04.2008, 16:15-17:45.

Dostępne materiały: Nagrania.

Wykład 3. Skojarzenia i przepływy (część I)

 Zagadnienia poruszone na wykładzie:

  • Przepływ dla krawędzi jednostkowych - postawienie problemu.
  • Schemat Forda-Fulkersona.
  • Twierdzenie o maksymalnym przepływie i minimalnym przekroju.
  • Uogólnienie problemu maksymalnego przepływu dla krawędzi o dowolnych przepustowościach.
  • Algorytm Edmondsa-Karpa.
  • Zmodyfikowany algorytm Dinica.
  • Przykład zadania które pokazuje nietrywialne zastosowanie maksymalnego przepływu.

Wykład poprowadził Marek Cygan. Lokalizacja: 3150. Termin: 10.03.2008, 16:15-17:45.

Dostępne materiały: Nagrania, Notatki.

Syndicate content