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.