Phase Transitions of Algorithms
| Thesis title: | Fázové přechody algoritmů |
|---|---|
| Author: | Tejkalová, Natálie |
| Thesis type: | Diplomová práce |
| Supervisor: | Tichý, Vladimír |
| Opponents: | Šalamon, Tomáš |
| Thesis language: | Česky |
| Abstract: | 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í. |
| Keywords: | fázový přechod; úloha naplňování zásobníku; NP-úplnost |
| Thesis title: | Phase Transitions of Algorithms |
|---|---|
| Author: | Tejkalová, Natálie |
| Thesis type: | Diploma thesis |
| Supervisor: | Tichý, Vladimír |
| Opponents: | Šalamon, Tomáš |
| Thesis language: | Česky |
| Abstract: | 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. |
| Keywords: | bin packing; NP-completeness; phase transitions |
Information about study
| Study programme: | Aplikovaná informatika/Znalostní technologie |
|---|---|
| Type of study programme: | Magisterský studijní program |
| Assigned degree: | Ing. |
| Institutions assigning academic degree: | Vysoká škola ekonomická v Praze |
| Faculty: | Faculty of Informatics and Statistics |
| Department: | Department of Information Technologies |
Information on submission and defense
| Date of assignment: | 20. 6. 2012 |
|---|---|
| Date of submission: | 26. 6. 2013 |
| Date of defense: | 12. 6. 2013 |
| Identifier in the InSIS system: | https://insis.vse.cz/zp/38105/podrobnosti |