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.