460-4063/01 – Kombinatorická optimalizace (KO)
| Garantující katedra | Katedra informatiky | Kredity | 5 |
| Garant předmětu | prof. RNDr. Petr Jančar, CSc. | Garant verze předmětu | prof. RNDr. Petr Jančar, CSc. |
| Úroveň studia | pregraduální nebo graduální | Povinnost | volitelný odborný |
| Ročník | | Semestr | zimní |
| | Jazyk výuky | čeština |
| Rok zavedení | 2014/2015 | Rok zrušení | 2015/2016 |
| Určeno pro fakulty | FEI | Určeno pro typy studia | navazující magisterské |
Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi
Student po úspěšném absolvování předmětu:
- rozumí základním pojmům z oblasti kombinatorické optimalizace (včetně příslušných pojmů teorie grafů, lineárního programování, výpočtové složitosti apod.)
- umí klasifikovat praktické problémy, které se dají vhodně modelovat jako problémy kombinatorické optimalizace
- umí sestavit k praktickým problémům příslušné vhodné modely
- umí u základních problémů rozlišit, které jsou řešitelné polynomiálními algoritmy a které jsou NP-těžké
- má přehled o metodách řešení úloh lineárního programování a celočíselného lineárního programování a umí je používat
- rozumí myšlenkám základních polynomiálních algoritmů
- má přehled o základních aproximačních algoritmech u NP-těžkých problémů a obecně použitelných heuristických přístupech
- umí pracovat se softwarovými nástroji pro řešení úloh kombinatorické optimalizace
Vyučovací metody
Přednášky
Cvičení (v učebně)
Projekt
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:
• Bernhard Korte, Jens Vygen: Combinatorial Optimization (Theory and Algorithms), Springer (5th edition 2012)
Doporučená literatura:
- 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.
Forma způsobu ověření studijních výsledků a další požadavky na studenta
E-learning
Další požadavky na studenta
Každý student během semestru samostatně zpracuje projekt. Bude mít možnost volby mezi aplikačně zaměřeným projektem a teoreticky zaměřeným projektem. V případě aplikačního projektu student dostane zadání konkrétního prakticky motivovaného problému (např. může jít o sestavení optimálního pořadí vrtání děr na desce plošných spojů), k němuž pak sestaví model a navrhne vhodný způsob řešení, který implementuje ve zvoleném softwarovém nástroji.
V případě teoretického projektu půjde o zadání vyžadující např. netriviální důkazy vlastností konkrétních metod a algoritmů řešících optimalizační problémy.
Prerekvizity
Předmět nemá žádné prerekvizity.
Korekvizity
Předmět nemá žádné korekvizity.
Osnova předmětu
Osnova přednášek:
1. Přehled kursu. Obecná definice (diskrétních) optimalizačních problémů. Příklady typických úloh kombinatorické optimalizace, modelovaných v pojmech teorie grafů. Příklady problémů řešitelných "hladovým přístupem" (např. problém minimální kostry). Obecný důkaz korektnosti v pojmech matroidů.
2. Další konkrétní problémy řešitelné rychlými (polynomiálními) algoritmy. Připomenutí problémů nejkratší cesty, maximálního toku v sítích, maximálního párování; myšlenky příslušných algoritmů.
Polynomiální převeditelnost mezi problémy.
3. NP-obtížné problémy (problém SAT a MAX-SAT, problém obchodního cestujícího [TSP], problémy rozvrhování, apod.). Myšlenka Cookovy věty (NP-úplnost problému SAT) a důkazy NP-obtížnosti pomocí polynomiální převeditelnosti.
4. Celočíselné lineární programování (ILP). Formulace problémů kombinatorické optimalizace jako instancí problémů ILP. NP-obtížnost ILP.
5. Lineární programování (tj. "relaxované" ILP). Formulace úloh lineárního programování. Princip duality.
6. Řešení úloh lineárního programování; simplexová metoda. Diskuse polynomiální složitosti lineárního programování.
7. Řešení úloh ILP. Totálně unimodulární matice. Metoda větvení a mezí (branch and bound).
8. Další metody řešení úloh ILP. Metoda řezů (cutting planes).
9. Pseudopolynomiální algoritmy a aproximační algoritmy ilustrované např. na problému batohu (knapsack problem). Zmínka o heuristických přístupech řešení NP-obtížných problémů.
10. Další aproximační algoritmy a přístupy (aproximace problému TSP, metoda simulovaného žíhání).
11. Špatně aproximovatelné problémy. PCP (Probabilistically Checkable
Proofs) teorém a jeho aplikace na problém maximální kliky v grafu.
12. a 13. Různé varianty problémů plánování a rozvrhování a jejich řešení.
(Rozvrhování pro jeden procesor a pro paralelní procesory.)
14. Shrnutí kursu a zopakování hlavních pojmů a myšlenek.
Osnova počítačových cvičení:
Cvičení jsou uvedena jako počítačová, jelikož budou zahrnovat i řešení problémů pomocí softwarových nástrojů (např. k řešení úloh lineárního programování). Významná část cvičení bude ale věnována i řešením problémů u tabule. Půjde o procvičení pojmů a metod probraných na příslušných přednáškách; osnova tedy bude kopírovat osnovu přednášek.
Podmínky absolvování předmětu
Výskyt ve studijních plánech
Výskyt ve speciálních blocích
Hodnocení Výuky
Předmět neobsahuje žádné hodnocení.