Přístupnostní navigace
E-přihláška
Vyhledávání Vyhledat Zavřít
Detail předmětu
FSI-SHE-AAk. rok: 2024/2025
Kurz je zaměřen na heuristické optimalizační metody jakožto nástroje pro řešení složitých problémů v situacích, kdy nelze použít klasické exaktní metody. Důraz je kladen nejen na pochopení rozdílů mezi exaktními algoritmy, aproximačními metodami a heuristickými algoritmy, ale také na způsob konkrétní programové realizace heuristických algoritmů. Zde je pozornost věnována nejen procedurální stránce, ale také návrhu vhodných datových struktur.
Jazyk výuky
Počet kreditů
Garant předmětu
Zajišťuje ústav
Vstupní znalosti
Kurs předpokládá základní znalost algoritmizace a počítačovou gramotnost.
Pravidla hodnocení a ukončení předmětu
Zápočet: Účast na cvičeních + zpracování zadaných programů v C++ (celkem 2 programy). Zkouška: ústní, diskuse nad zpracovanými projekty s možnými doplňujícími otázkami. Klasifikace je plně v kompetenci vyučujícího podle platných směrnic VUT v Brně.
Přítomnost na přednáškách je doporučená, na cvičeních povinná. Výuka probíhá podle rozvrhu. Stanovení formy náhrady zameškaných cvičení je v kompetenci vyučujícícho.
Učební cíle
Hlavním cílem kursu je pochopení principu a filozofie heuristických algoritmů a jejich aplikace v řešení logistických problémů. Kromě toho je důraz věnován schpnosti efektivní objektové implementace heuristických algoritmů v objektově orientovaných programovacích jazycích, jako je C++ nebo C#.
Po absolvování kurzu budou studenti chápat rozdíly mezi exaktními, aproximačními a heuristickými algoritmy a budou schopni posoudit možnost jejich použití v konkrétních situacích. Budou znát základní klasifikaci metaheristik a typické algoritmy reprezentující jednotlivé kategorie. Absolventi budou schopni praktické implementace heuristických algoritmů v objektově orientovaných jazycích (C++, C#).
Základní literatura
Doporučená literatura
Zařazení předmětu ve studijních plánech
specializace CZS , 1 ročník, zimní semestr, volitelný
Přednáška
Vyučující / Lektor
Osnova
1. Úvod, exaktní algorimy, aproximační algoritmy, heuristické algoritmy. Heuristika, metaheuristika.2. Složitost úloh, časová náročnost hledání řešení.3. Globální a lokální optimum.4. Klasifikace metaheuristik - deterministické/stochastické, založené na jednom řešení/založené na populaci řešení, iterativní/hladové, ...5. Prohledávání stavového prostoru - náhodné prohledávání, neinformované a informované metody6. Aplikace heuristik pro kombinatorické problémy7., 8. Heuristiky založené na lokálním prohledávání (simulované žíhání, tabu search)9., 10. Heuristiky založené na populaci řešení (genetické algoritmy, scatter search)11. Mravenčí kolonie, hejnové algoritmy12., 13.: Efektivní implementace heuristických algoritmů
Cvičení
1. - 13.: Demonstrace látky z přednášek na reálných příkladech, implementace vybraných algoritmů pomocí OOP v jazycích C++ a/nebo C#.