Fázové přechody algoritmů - Tejkalová, Natálie; Tichý, Vladimír, 1953-; Šalamon, Tomáš; Vysoká škola ekonomická v Praze. Fakulta informatiky a statistiky (2013)
Práce se zabývá fázovými přechody algoritmů pro řešení NP-těžkých úloh. V této doméně označuje fázový přechod místo, kde nalézáme mnoho těžkých instancí dané úlohy. Fázový přechod je definován s pomocí klíčového parametru a jeho existence by neměla být závislá na velikosti řešeného problému. Pro rozhodovací úlohy nalézáme často zároveň přechod ve složitosti instance i přechod v pravděpodobnosti řešení úloh se stejnými parametry. Byla vznesena hypotéza, že každá NP-těžká úloha má alespoň jeden takový fázový přechod. Otazníků kolem fázových přechodů u algoritmů ovšem existuje více. Naše práce shrnuje dosavadní poznatky na tomto poli a představuje výběr již nalezených fázových přechodů na konkrétních úlohách (úloha obchodního cestujícího, úloha dělení kořisti a další). Druhá část se zaměřuje na algoritmy pro úlohu naplňování zásobníku. Několik z nich bylo implementováno v přiloženém programu a využito ke hledání fázového přechodu na této úloze. Závěrečná kapitola obsahuje popis obtížnosti zkoumaných instancí.
Vedoucí práce: Vladimír Tichý
Diplomová práce (Ing.)—Vysoká škola ekonomická v Praze. Fakulta informatiky a statistiky, 2013
Obsahuje bibliografii
Textový (vysokoškolská kvalifikační práce)
Rok obhajoby 2013
Způsob přístupu: Internet
Keywords: znalostní technologie [obor dipl. práce]; diplomové práce; master's theses