Kombinatorická optimalizace

Podmínkou zápisu předmětu je dřívější úspěšné absolvování předmětů:

Pokročilá algoritmizace (A4M33PAL)

Přednášející:

Zdeněk Hanzálek (gar.)

Cvičící:

Zdeněk Hanzálek (gar.), Zdeněk Bäumelt, Ondřej Nývlt, Demlová Uznáno, Roman Václavík

Předmět zajišťuje:

katedra řídicí techniky

Anotace:

Cílem předmětu je seznámit studenty s problémy a algoritmy

kombinatorické optimalizace (často se nazývá diskrétní optimalizace,

významně se překrývá s pojmem operační výzkum). V návaznosti na

předměty z oblasti lineární algebry, algoritmizace, diskrétní

matematiky a základů optimalizace jsou ukázány techniky založené na

grafech, celočíselném lineárním programování, heuristikách,

aproximačních algoritmech a metodách prohledávání prostoru řešení.

Požadavky:

Optimalizace, Diskrétní matematika, Logika a grafy

Stránky předmětu: https://moodle.dce.fel.cvut.cz/

Osnova přednášek:

1. Uvedení základních pojmů z kombinatorické optimalizace, příklady aplikací.

2. Celočíselné lineární programování - algoritmy.

3. Formulace problémů pomocí celočíselného lineárního programování.

4. Nejkratší cesty. Test I.

5. Toky a řezy v sítích - formulace problémů a algoritmy. Párování v bipartitních grafech.

6. Multi-komoditní toky.

7. Problém batohu, pseudo-polynomiální a aproximační algoritmy.

8. Úloha obchodního cestujícího. Test II.

9. Rozvrhování na jednom procesoru.

10. Paralelní procesory.

11. Rozvrhování projektu s časovými omezeními.

12. Programování s omezujícími podmínkami.

13. Rezerva

Osnova cvičení:

1. Seznámení s experimentálním prostředím a knihovnou pro optimalizaci

2. Celočíselné lineární programování

3. Aplikace celočíselného lineárního programování

4. Samostatná úloha I - zadání a kategorizace

5. Nejkratší cesty

6. Samostatná úloha II - rešerše literatury a prezentace řešení

7. Aplikace toků a řezů v sítích

8. Samostatná úloha III - konzultace

9. Rozvrhování

10. Test III

11. Samostatná úloha IV - odevzdání algoritmu a písemné zprávy

12. Zápočet

13. Rezerva

Cíle studia:

Studijní materiály:

B. H. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms.

Springer, third ed., 2006.

J. Blazevicz, Scheduling Computer and Manufacturing Processes. Springer,

second ed., 2001.

J. Demel, Grafy a jejich aplikace. Academia, second ed., 2002.

TORSCHE http://rtime.felk.cvut.cz/scheduling-toolbox/

Poznámka:

Rozsah výuky v kombinované formě studia: 21p+6c

Rozvrh na zimní semestr 2011/2012:

Rozvrh není připraven

Rozvrh na letní semestr 2011/2012:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
Út	místnost T2:C3-340 Hanzálek Z. 10:00–12:30 (přednášková par. 1) Dejvice Posluchárna
St	místnost KN:E-2 Bäumelt Z. 14:30–16:00 (přednášková par. 1 paralelka 105) Karlovo nám. Laboratoř PCmístnost KN:E-2 Bäumelt Z. 16:15–17:45 (přednášková par. 1 paralelka 106) Karlovo nám. Laboratoř PCmístnost KN:E-2 18:00–19:30 (přednášková par. 1 paralelka 107) Karlovo nám. Laboratoř PC
Čt	místnost KN:E-2 07:30–09:00 (přednášková par. 1 paralelka 101) Karlovo nám. Laboratoř PCmístnost KN:E-2 Václavík R. 09:15–10:45 (přednášková par. 1 paralelka 102) Karlovo nám. Laboratoř PCmístnost KN:E-2 Nývlt O. 11:00–12:30 (přednášková par. 1 paralelka 103) Karlovo nám. Laboratoř PCmístnost KN:E-2 Nývlt O. 12:45–14:15 (přednášková par. 1 paralelka 104) Karlovo nám. Laboratoř PCmístnost KN:E-2 Václavík R. 14:30–16:00 (přednášková par. 1 paralelka 109) Karlovo nám. Laboratoř PCmístnost KN:E-2 Václavík R. 16:15–17:45 (přednášková par. 1 paralelka 108) Karlovo nám. Laboratoř PC
Pá

Předmět je součástí následujících studijních plánů:

• Otevřená informatika - Umělá inteligence (povinný předmět programu)
• Otevřená informatika - Počítačové inženýrství (povinný předmět programu)
• Otevřená informatika - Počítačové vidění a digitální obraz (povinný předmět programu)
• Otevřená informatika - Počítačová grafika a interakce (povinný předmět programu)
• Otevřená informatika - Softwarové inženýrství (povinný předmět programu)