grafy

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 15. Szybkie potęgowanie macierzy

 Na wykładzie omówiłem następujące zagadnienia:

  • Jak efektywnie mnożyć macierze? Szybkie potęgowanie macierzy.
  • Wyznaczanie wyrazów (i nie tylko) ciągów zdefiniowanych poprzez rekursję liniową. I jeszcze bonusik: zadanie Liczby Leonarda z ONTAK-a 2008.
  • Wyznaczanie ścieżek długości =n bądź ≤n w grafie.
  • Potęgowanie macierzy jako przyspieszenie rozwiązań opartych na programowaniu dynamicznym.
  • Pokrywanie prostokąta 4 x n za pomocą klocków z Tetrisa.

Wykład poprowadził Tomasz Kulczyński. Lokalizacja: 3130. Termin: 10.03.2009, 16:15-18:00.

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 13. Proste (czyżby?) algorytmy grafowe

Na wykładzie omówiłem różne w sumie podstawowe algorytmy związane z grafami. Przy większości z nich wspomniałem o tym, jak według mojego doświadczenia najlepiej (np. najłatwiej) go zaimplementować, jak najłatwiej uzasadnić jego poprawność i jak go stosować do różnych fajnych rzeczy. Na wykładzie zakładałem raptem... znajomość poniższych algorytmów:).

  • BFS (tak, nawet w zwykłym BFS-ie coś ciekawego siedzi!).
  • Silnie spójne składowe i sortowania topologiczne.
  • Cykl Eulera.
  • Algorytm Dijkstry z moim ulubionym zastosowaniem.
  • Algorytm Floyda-Warshalla i zastosowania do ujemnych cykli w grafie (patrz zadanie Studia z PA 2008).
  • "Dzielenie przez 32" na przykładzie algorytmów grafowych (w tym zliczanie trójkątów w grafie i inne Floydy).

Wykład poprowadził Jakub Radoszewski. Lokalizacja: 3130. Termin: 24.02.2009, 16:00-17:45.

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