BI-GRA – Grafové algoritmy a základy teorie složitosti

Cíl předmětu

Studenti získají základní přehled o používání grafových modelů v informatice, se zaměřením především na algoritmické otázky a řešení grafových problémů. Zahrnuta jsou rovněž další témata, která tento přehled doplňují o specifické aplikace nebo postupy (toky v sítích, heuristické hledání, aproximační algoritmy) nebo se týkají obecnější problematiky algoritmické řešitelnosti a složitosti úloh (Turingovy stroje, NP úplné problémy).

Program přednášek

  1. Grafové modely, neorientované grafy, izomorfismus.
  2. Sousednost, souvislost, orientované grafy.
  3. Silná souvislost, acyklické grafy, reprezentace grafů, procházení do šířky.
  4. Procházení do hloubky, topologické uspořádání, silně souvislé komponenty.
  5. Eulerovy grafy, dominující a nezávislé podmnožiny, barevnost, vzdálenost.
  6. Stromy, kostry, kružnice, minimální kostry.
  7. Nejkratší cesty, algoritmy hledání nejkratších cest 1 -> n.
  8. Algoritmy hledání nejkratších cest n -> n, planarita.
  9. Toky v sítích, určení maximálního toku v síti.
  10. Nejlevnější cirkulace, párování, řešení přiřazovací úlohy.
  11. Stavový prostor úloh, prohledávání, heuristické hledání.
  12. Turingovy stroje.
  13. Třídy složitosti, NP-úplné problémy, aproximační algoritmy.

Program cvičení

  1. Indukce, rekurze, rekurence
  2. Druhy stromů a jejich reprezentace, procházení stromů.
  3. Vlastnosti grafů (izomorfismus, souvislost, komponenty, stupně uzlů).
  4. Silná souvislost, rozklad na silné komponenty, topologické uspořádání.
  5. Reprezentace a procházení grafu, použití.
  6. Určení Eulerova tahu, úloha čínského listonoše, zadání semestrální práce.
  7. Určování charakteristik (nezávislost, dominance, barevnost, cyklomatické číslo).
  8. Stromy, kostry a minimální kostry.
  9. Nejkratší cesty.
  10. Nejkratší cesty, planarita, konzultace k semestrální úloze.
  11. Maximální tok v síti, cirkulace, párování.
  12. Algoritmy heuristického hledání.
  13. Turingovy stroje.
  14. Odevzdání semestrální úlohy, zápočet.



Poslední změna: 5.7.2010, 22:28