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.
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.