Sylabus
Základy diskrétní optimalizace:
- Úvod, příklady optimalizačních problémů a optimalizačních technik. Analýza algoritmů, implementace, složitost.
- Eulerovská procházka, hladový algoritmus, nejkratsi cesta a jejich souvislosti.
- Párování a aplikace, souvislost s toky v sítích. Heuristiky a algoritmy, i pravděpodobnostní, na párování. Problém pošťáka.
- Problém obchodního cestujícího (TSP): heuristiky, aplikace a souvislosti
- Porovnání těžkých a polynomiálních problémů: TSP, problém pošťáka, Euler tours, minimální kostra, minimální Steiner tree.
Základy spojité optimalizace:
- Konvexní funkce a množiny
- Konvexní optimalizace
- Kvadratické programování
- Kuželové programování a dualita
- Karush-Kuhn-Tuckerovy podmínky optimality
- Základní metody
- Programování s nepřesnými daty, robustní optimalizace
Anotace
Přehledová přednáška pokrývající základní oblasti optimalizace, včetně výpočetních metod. Na úlohy spadající pod tuto problematiku vede nesčetné množství problémů z téměř všech oborů lidské činnosti. Má velmi široké možnosti použití. Úvod k dalším přednáškám specializovaným na řešení jednotlivých tříd optimalizačních úloh.
Pro absolvování předmětu jsou vhodné (nikoli však nutné) předběžné znalosti lineárního programování, např. z přednášky NOPT048 Lineární programování a kombinatorická optimalizace (dříve Opt. Metody).