Algoritmy pro řešení speciálních problémů batohu a jejich výpočetní složitost
| Název práce: | Algoritmy pro řešení speciálních problémů batohu a jejich výpočetní složitost |
|---|---|
| Autor(ka) práce: | Sem, Štěpán |
| Typ práce: | Diplomová práce |
| Vedoucí práce: | Ivánek, Jiří |
| Oponenti práce: | Kalčevová, Jana |
| Jazyk práce: | Česky |
| Abstrakt: | Práce se zabývá variantami problému batohu a možnostmi jejich řešení, dále potom vlivem speciálního tvaru konkrétního zadání (instance) na efektivitu testovaného postupu. Předkládá rovněž možnosti převoditelnosti mezi popsanými úlohami, jakož i jejich spojité rozšíření (spojitou relaxaci). Z řad klasických algoritmů popisuje algoritmus L3 a řešení superklesajícího problému batohu, z řad pravděpodobnostních algoritmů Metodu Monte Carlo, simulované žíhání a genetické algoritmy. Diskutovány jsou i další možnosti. Nedílnou součást práce tvoří doprovodná aplikace, která sloužila k vytvoření podkladů zde uváděných a může být rovněž použita k řešení dalších instancí. |
| Klíčová slova: | algoritmy; problém batohu; výpočetní složitost |
| Název práce: | Algorithms for solving of special knapsack problems and their computational complexity |
|---|---|
| Autor(ka) práce: | Sem, Štěpán |
| Typ práce: | Diploma thesis |
| Vedoucí práce: | Ivánek, Jiří |
| Oponenti práce: | Kalčevová, Jana |
| Jazyk práce: | Česky |
| Abstrakt: | The thesis deals with knapsack problems variants and possibility of their solving, furthermore with the impact of particular task (instance) special structure on the effciency of tested approach. The thesis also proposes conversion possibility between described tasks and their continuous extension (continuous relaxation). It describes L3 algorithm and superdecreasing knapsack problem solving from the common sort of algorithms and Monte Carlo Method, simulated annealing and genetic algorithms from the sort of probability ones. Other possibilities are also discussed. Integral part of this thesis is the accompanying application, which was used to create groundwork used in the text and which can be also used to solve other instances. |
| Klíčová slova: | computational complexity; algorithms; knapsack problems |
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ího a znalostního inženýrství |
Informace o odevzdání a obhajobě
| Datum zadání práce: | 21. 9. 2010 |
|---|---|
| Datum podání práce: | 4. 5. 2012 |
| Datum obhajoby: | 6. 2. 2013 |
| Identifikátor v systému InSIS: | https://insis.vse.cz/zp/27389/podrobnosti |