460-4091/01 – Kombinatorická optimalizace (KO)

Garantující katedraKatedra informatikyKredity4
Garant předmětuprof. RNDr. Petr Jančar, CSc.Garant verze předmětuprof. RNDr. Petr Jančar, CSc.
Úroveň studiapregraduální nebo graduálníPovinnostpovinně volitelný
Ročník1Semestrletní
Odkaz na webJazyk výukyčeština
Rok zavedení2015/2016Rok zrušení
Určeno pro fakultyFEIUrčeno pro typy studianavazující magisterské
Výuku zajišťuje
Os. čís.JménoCvičícíPřednášející
JAN59 prof. RNDr. Petr Jančar, CSc.
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Zápočet a zkouška 2+2
kombinovaná Zápočet a zkouška 10+0

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ě)

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.

Způsob průběžné kontroly znalostí během semestru

E-learning

Další požadavky na studenta

Nejsou kladeny další požadavky na studenty.

Minimální znalostní požadavky

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 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ého pří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ího pá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ích příkladech. 6. Řešení konkrétních instancí simplexovou metodou a jejími variantami. 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ých problémů. 12. a 13. Řešení konkrétních instancí problémů plánování a rozvrhování, pro jeden procesor i pro více procesorů. 14. Zopakování hlavních pojmů a metod, které budou prověřeny zkouškou.

Podmínky absolvování předmětu

Prezenční forma (platnost od: 2015/2016 zimní semestr)
Název úlohyTyp úlohyMax. počet bodů
(akt. za podúlohy)
Min. počet bodů
Zápočet a zkouška Zápočet a zkouška 100 (100) 51
        Zápočet Zápočet 45  20
        Zkouška Zkouška 55  6
Rozsah povinné účasti:

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramOborSpec.FormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2017/2018 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 1 volitelný odborný stu. plán
2017/2018 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 1 volitelný odborný stu. plán
2017/2018 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 1 povinně volitelný stu. plán
2017/2018 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 1 povinně volitelný stu. plán
2016/2017 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 1 volitelný odborný stu. plán
2016/2017 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 1 volitelný odborný stu. plán
2016/2017 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 1 povinně volitelný stu. plán
2016/2017 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 1 povinně volitelný stu. plán
2015/2016 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 1 povinně volitelný stu. plán
2015/2016 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 1 volitelný odborný stu. plán
2015/2016 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 1 povinně volitelný stu. plán
2015/2016 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 1 volitelný odborný stu. plán

Výskyt ve speciálních blocích

Název blokuAkademický rokForma studiaJazyk výuky RočníkZLTyp blokuVlastník bloku