diplomová práce

Aproximativní a heuristické metody řešení NP-těžkých problémů

Autor práce: Ing. Ivo Bílek

Ak. rok: 2007/2008

Vedoucí: prof. RNDr. Ing. Miloš Šeda, Ph.D.

Oponent: Oponent bude zobrazen po zveřejnění jeho hodnocení.

Abstrakt:

V této práci je rozebrána problematika výpočetní složitosti NP těžkých problémů. Jsou zde uvedeny jednotlivé metody a algoritmy přibližného řešení NP těžkých problémů a dále jsou zde popsány základní aproximativní metody, deterministické a stochastické heuristiky. Dále je v úloze obchodního cestujícího popsán rozbor vybraného problému a jeho implementace spolu s implementací dvou algoritmů pro porovnaní výsledků a časové náročnosti.

Klíčová slova:

Problém , algoritmus, graf, výpočetní složitost, kódování

Termín obhajoby

6.11.2007

Výsledek obhajoby

obhájeno (práce byla úspěšně obhájena)

znakmkaEznamka

Klasifikace

E

Jazyk práce

čeština

Fakulta

Ústav

Studijní obor

Inženýrská informatika a automatizace (N3917-01)

Složení komise

doc. Ing. Čestmír Ondrůšek, CSc. (předseda)
doc. Ing. Arnošt Motyčka, CSc. (místopředseda)
RNDr. Jaroslav Pelikán, Ph.D. (člen)
doc. RNDr. Jindřich Klapka, CSc. (člen)
prof. RNDr. Ing. Jiří Šťastný, CSc. (člen)