PředmětyPředměty(verze: 806)
Předmět, akademický rok 2017/2018
   Přihlásit přes CAS
Algoritmy pro specifické třídy grafů - NDMI077
Anglický název: Algorithms for Specific Graph Classes
Zajišťuje: Katedra aplikované matematiky (32-KAM)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2017
Semestr: letní
E-Kredity: 3
Rozsah, examinace: letní s.:2/0 Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: angličtina, čeština
Způsob výuky: prezenční
Garant: doc. RNDr. Jiří Fiala, Ph.D.
Třída: Informatika Mgr. - volitelný
Kategorizace předmětu: Informatika > Diskrétní matematika
Anotace -
Poslední úprava: doc. Mgr. Milan Hladík, Ph.D. (04.05.2015)

Kurz zaměřený na návrh algoritmů pro specifické třídy grafů. Vhodné pro studenty mat. a inf. od 3.r. i pro doktorandy (M a I). Doporučeno absolvování předmětu Grafové minory a stromové rozklady.
Literatura -
Poslední úprava: JUDr. Dana Macharová (14.10.2008)

  • Diestel, R.: Graph Theory, graduate texts in mathematics, vol. 173., Springer Verlag, May 1997.
  • Kloks, T. Treewidth: Computations and approximations, no. 842 in Lecture Notes in Computer Science, Springer Verlag, 1994.
  • Časopisecká literatura podle specifikace přednášejícího.

Sylabus -
Poslední úprava: doc. Mgr. Milan Hladík, Ph.D. (04.05.2015)

Kurz zaměřený na návrh efektivních algoritmů pro specifické třídy grafů, a to pro problémy, které jsou v obecnosti NP-těžké. Jmenovitě pro grafy různých šířek (stromové rozklady - Courcellova věta, klikové rozklady) případně s danou reprezentací (průnikové grafy intervalů, kruhů a dalších geometrických objektů).

 
Univerzita Karlova | Informační systém UK