Fakulta elektrotechnická

MOTTO: SCIENTIA EST POTENTIA

Vyhledávání

Přehled studia | Přehled oborů | Všechny skupiny předmětů | Všechny předměty | Seznam rolí | Vysvětlivky               Návod
A4M35KO Kombinatorická optimalizace Rozsah výuky:3p+2c
Garant:Hanzálek Z. Typ předmětu:P Zakončení:Z,ZK
Vyučující:Hanzálek Z.
Zodpovědná katedra:13135 Kreditů:6 Semestr:L

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

Osnovy 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

Osnovy 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

Literatura:

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/

Požadavky:
Optimalizace, Diskrétní matematika, Logika a grafy Stránky předmětu: https://moodle.dce.fel.cvut.cz/

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

Předmět je zahrnut do těchto studijních plánů:

Plán Obor Role Dop. semestr
MPIB Před zařazením do oboru V Není
MPOI1 Umělá inteligence P 2
MPOI2 Počítačové inženýrství P 2
MPOI3 Počítačové vidění a digitální obraz P 2
MPOI5 Softwarové inženýrství a interakce P 2
MPOI4NEW Počítačová grafika P 2
MPOI5NEW Softwarové inženýrství a interakce P 2
MPOI4 Počítačová grafika P 2
MPKME3 Elektronika V 2
MPKME4 Sítě elektronických komunikací (magisterský) V 2
MPKME1 Bezdrátové komunikace (magisterský) V 2
MPKME2 Multimediální technika (magisterský) V 2
MPEEM2 Elektrické stroje, přístroje a pohony V 2
MPEEM1 Technologické systémy V 2
MPEEM5 Ekonomika a řízení elektrotechniky V 2
MPEEM3 Elektroenergetika V 2
MPEEM4 Ekonomika a řízení energetiky V 2
MPKYR4 Letecké a kosmické systémy V 2
MPKYR2 Senzory a přístrojová technika V 2
MPKYR3 Systémy a řízení V 2
MPKYR1 Robotika V 2

Stránka vytvořena 23. 2. 2012, semestry: L/2009-10, L/2010-1, Z/2008-9, Z/2007-8, Z/2009-10, L/2007-8, L/2011-2, L/2008-9, Z/2011-2, Z/2010-1, připomínky k informační náplni zasílejte správci studijních plánů Návrh a realizace: I. Halaška (K336), J. Novák (K336)