Přeskočit na hlavní obsah
Přeskočit hlavičku

Kombinatorická optimalizace

Anotace

Mnohé problémy každodenní (průmyslové) praxe jsou de facto optimalizačními problémy: v množině přípustných řešení (např. přidělení úkolů pracovníkům či procesorům, naplánování vozidel a jejich tras pro zásobování, návrh rozmístění elektronických součástek na desce plošných spojů) hledáme takové řešení, které je z nějakého hlediska (např. ceny, času) optimální. Tyto problémy lze často formulovat jako problémy kombinatorické (nebo též diskrétní) optimalizace, většinou v pojmech grafů a (celočíselných) lineárních nerovnic. Některé problémy lze uspokojivě řešit rychlými polynomiálními algoritmy, u jiných (NP-těžkých) se musíme spokojit s algoritmy, které jen aproximují optimální řešení, či s jinými (heuristickými) algoritmy, které dávají rozumné výsledky, byť jejich kvalita není obecně garantována.
Cílem předmětu je přiblížení oblasti kombinatorické optimalizace, klasifikace problémů, které zde patří, a osvětlení metod používaných k jejich praktickému řešení.

Povinná literatura

- Jon Lee: A first course in combinatorial optimization, Cambridge
University Press, 2004

Doporučená literatura

- Bernhard Korte, Jens Vygen: Combinatorial Optimization (Theory and Algorithms), Springer (5th edition 2012)

- Christos H. Papadimitriou, Kenneth Steiglitz: Combinatorial Optimization:
Algorithms and Complexity, Dover Publications, 1998.

- Malik Ghallab, Dana Nau, Paolo Traverso: Automated Planning: Theory & Practice, Morgan Kaufmann, 2004.

- Alexander Schrijver: Combinatorial Optimization (3 volume, A,B, & C),
Springer, 2003.


Jazyk výuky čeština, angličtina
Kód 460-4091
Zkratka KO
Název předmětu česky Kombinatorická optimalizace
Název předmětu anglicky Combinatorial Optimization
Garantující katedra Katedra informatiky
Garant předmětu doc. Ing. Zdeněk Sawa, Ph.D.