FI:M015 Grafové algoritmy - Informace o předmětu

M015 Grafové algoritmy

Rozsah

2/1. 3 kr. Doporučované ukončení: zk. Jiná možná ukončení: k, z.

Vyučující

doc. RNDr. Libor Polák, CSc. (přednášející)

Garance

Kontaktní osoba: doc. RNDr. Libor Polák, CSc.

Předpoklady

Doporučeno je absolvovat M010 Kombinatorika a teorie grafů.

Omezení zápisu do předmětu

Předmět je nabízen i studentům mimo mateřské obory.

Mateřské obory/plány

• Informatika (program FI, B-IN)
• Informatika (program FI, M-IN)
• Učitelství výpočetní techniky pro střední školy (program FI, M-IN)
• Učitelství výpočetní techniky pro střední školy (program FI, M-SS)
• Výpočetní technika (program FI, B-IN)

Osnova

• Elementární grafové algoritmy (reprezentace grafů, prohledávání do šířky, prohledávání do hloubky, topologické uspořádání, silně souvislé komponenty).
• Minimální kostry (růst minimální kostry, algoritmy Kruskala a Prima).
• Nejkratší cesty z jediného vrcholu (nejkratší cesty a relaxace, Dijkstrův algoritmus, Bellman--Fordův algoritmus, nejkratší cesty v orientovaných acyklických grafech).
• Nejkratší cesty mezi všemi dvojicemi vrcholů (nejkratší cesty a násobení matic, Floyd--Warshallův algoritmus, Johnsonův algoritmus pro řídké grafy).
• Maximální toky v sítích (sítě, Ford--Fulkersonova metoda, maximální párování v bipartitních grafech).
• Datové struktury pro grafové algoritmy (binární haldy, prioritní fronty, binomiální haldy, Fibonacciho haldy, datové struktury pro systémy disjunktních množin).

• Statistika zápisu (léto 1997, nejnovější)
  
• Permalink: https://is.muni.cz/predmet/fi/leto1997/M015