Fázové přechody algoritmů
| Název práce: | Fázové přechody algoritmů |
|---|---|
| Autor(ka) práce: | Tejkalová, Natálie |
| Typ práce: | Diplomová práce |
| Vedoucí práce: | Tichý, Vladimír |
| Oponenti práce: | Šalamon, Tomáš |
| Jazyk práce: | Česky |
| Abstrakt: | 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í. |
| Klíčová slova: | fázový přechod; úloha naplňování zásobníku; NP-úplnost |
| Název práce: | Phase Transitions of Algorithms |
|---|---|
| Autor(ka) práce: | Tejkalová, Natálie |
| Typ práce: | Diploma thesis |
| Vedoucí práce: | Tichý, Vladimír |
| Oponenti práce: | Šalamon, Tomáš |
| Jazyk práce: | Česky |
| Abstrakt: | The thesis deals with phase transisions of algorithms for solving NP-hard problems. In this domain, phase transition describes the location where many hard instances of given problem can be found. Phase transition is defined by unique order parameter and its existence should be independent on problem size. For decision problems, both transitions in problem difficulty and in the probability of solution appear together. A hypothesis has been raised that for each NP-hard problem, at least one such phase transition exists. Actually, there are many more open questions concerning phase transitions of algorithms. Our thesis summarizes current state of knowledge in this field and presents a selection of phase transitions that have been described in literature (travelling salesman problem, number partitioning etc). Second part of our thesis focuses on algorithms for the bin packing problem. Some of them were implemented in a program that accompanies this text and used in search for the phase transition of this problem. Final chapter contains a description of difficulty of examined instances. |
| Klíčová slova: | bin packing; NP-completeness; phase transitions |
Informace o studiu
| Studijní program / obor: | Aplikovaná informatika/Znalostní technologie |
|---|---|
| Typ studijního programu: | Magisterský studijní program |
| Přidělovaná hodnost: | Ing. |
| Instituce přidělující hodnost: | Vysoká škola ekonomická v Praze |
| Fakulta: | Fakulta informatiky a statistiky |
| Katedra: | Katedra informačních technologií |
Informace o odevzdání a obhajobě
| Datum zadání práce: | 20. 6. 2012 |
|---|---|
| Datum podání práce: | 26. 6. 2013 |
| Datum obhajoby: | 12. 6. 2013 |
| Identifikátor v systému InSIS: | https://insis.vse.cz/zp/38105/podrobnosti |