Předmět Kombinatorická optimalizace (KO)

Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu KO - Kombinatorická optimalizace, Vysoká škola báňská - Technická univerzita Ostrava (VŠB-TU).

Materiál	Typ	Datum	Počet stažení

Cíl

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íhoprogramová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

Osnova

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émminimá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 CheckableProofs) 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í úlohlineá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ýchna příslušných přednáškách; osnova cvičení tedy kopíruje osnovu přednášek.Budou využívány standardní volně šiřitelné softwarové nástroje.1. Řešení konkrétních instancí problémů minimální kostry, plánováníúloh na jednom procesoru a dalších problémů, kde funguje hladovýpřístup. Procvičení pojmu matroid a důkazů korektnosti hladovéhopřístupu u váhových funkcí.2. Rozbor složitosti algoritmů pro hledání nejkratší cesty v grafu.Formulace problému jako úlohy lineárního programování.Řešení instancí problémů maximálního toku v sítích a maximálníhopárování. 3. Hledání polynomiálních redukcí prokazujících NP-obtížnost (variant)problému obchodního cestujícího [TSP], grafových problémů, problémůrozvrhování.4. Formulace konkrétních optimalizačních problémů jako jako problémů celočíselného lineárního programování a řešení konkrétních instancí.5. Procvičení principu duality v lineárním programování na konkrétníchpříkladech.6. Řešení konkrétních instancí simplexovou metodou a jejímivariantami.7. Problémy zachycené totálně unimodulárními maticemi.Procvičení metoda větvení a mezí (branch and bound).8. Procvičení dalších metod řešení úloh ILP. Metoda řezů (cutting planes).9. Rozbor vybraných pseudopolynomiálních algoritmů a aproximačních algoritmů.10. Návrh aproximačních algoritmů pro vybrané NP-obtížné optimalizačníproblémy.11. Provedení důkazů špatné aproximovatelnosti vybrané NP-obtížnýchproblémů.12. a 13. Řešení konkrétních instancí problémů plánování arozvrhování, pro jeden procesor i pro více procesorů.14. Zopakování hlavních pojmů a metod, které budou prověřeny zkouškou.

Literatura

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

Požadavky

Žádné

Garant

prof. RNDr. Petr Jančar, CSc.

Vyučující

prof. RNDr. Petr Jančar, CSc.