PředmětyPředměty(verze: 964)
Předmět, akademický rok 2024/2025
   Přihlásit přes CAS
Toky, cesty a řezy - NDMI067
Anglický název: Flows, Paths and Cuts
Zajišťuje: Katedra aplikované matematiky (32-KAM)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2024
Semestr: zimní
E-Kredity: 3
Rozsah, examinace: zimní s.:2/0, Zk [HT]
Počet míst: neomezen
Minimální obsazenost: neomezen
4EU+: ne
Virtuální mobilita / počet míst pro virtuální mobilitu: ne
Stav předmětu: nevyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Garant: doc. Mgr. Petr Kolman, Ph.D.
Třída: Informatika Mgr. - Diskrétní modely a algoritmy
Kategorizace předmětu: Informatika > Diskrétní matematika
Výsledky anket   Termíny zkoušek   Rozvrh   Nástěnka   
Anotace -
Toky více komodit zobecňují přirozeným způsobem klasický tokový problém: místo jediné dvojice zdroj-spotřebič máme takových dvojic několik, ale přitom máme k dispozici stále jen jedinou síť, do které se musí všechny toky poskládat. Toky více komodit a zejména jejich duální řezové problémy hrály v posledním desetiletí významnou úlohu při návrhu aproximačních algoritmů pro celou radu rozmanitých aplikací. Cílem přednášky je představit vybrané výsledky z této oblasti a ukázat na nich několik obecných postupů užitečných při návrhu aproximačních algoritmů. Predmet se uci jednou za dva roky.
Poslední úprava: T_KAM (21.04.2016)
Podmínky zakončení předmětu -

Zkouška je ústní. Požadavky odpovídají sylabu v míře pokryté přednáškami.

Poslední úprava: Kolman Petr, doc. Mgr., Ph.D. (12.10.2017)
Literatura -

[1] D. P. Williamson, D. B. Shmoys: The Design of Approximation Algorithms, http://www.designofapproxalgs.com/book.pdf (dostupne online)

[2] V. Vazirani: Approximation Algorithms

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

Toky více komodit zobecňují přirozeným způsobem klasický tokový problém: místo jediné dvojice zdroj-spotřebič máme takových dvojic několik, ale přitom máme k dispozici stále jen jedinou síť, do které se musí všechny toky poskládat. Toky více komodit a zejména jejich duální řezové problémy hrály v posledním desetiletí významnou úlohu při návrhu aproximačních algoritmů pro celou radu rozmanitých aplikací. Cílem přednášky je představit vybrané výsledky z této oblasti a ukázat na nich několik obecných postupů užitečných při návrhu aproximačních algoritmů.

Poslední úprava: G_I (08.06.2007)
 
Univerzita Karlova | Informační systém UK