Témata prací (Výběr práce)Témata prací (Výběr práce)(verze: 384)
Detail práce
   Přihlásit přes CAS
Heuristikou řízené hledání optima v NP-těžkých úlohách
Název práce v češtině: Heuristikou řízené hledání optima v NP-těžkých úlohách
Název v anglickém jazyce: Heuristic-driven methods finding optimum for NP-hard problems
Akademický rok vypsání: 2008/2009
Typ práce: bakalářská práce
Jazyk práce: čeština
Ústav: Katedra aplikované matematiky (32-KAM)
Vedoucí / školitel: RNDr. Martin Pergel, Ph.D.
Řešitel: skrytý - zadáno a potvrzeno stud. odd.
Datum přihlášení: 04.11.2008
Datum zadání: 04.11.2008
Datum a čas obhajoby: 17.09.2010 00:00
Datum odevzdání elektronické podoby:17.09.2010
Datum proběhlé obhajoby: 17.09.2010
Oponenti: doc. RNDr. Pavel Surynek, Ph.D.
 
 
 
Zásady pro vypracování
Uchazeč po dohodě s vedoucím vybere vhodné problémy řesitelné v anotaci uvedenou metodou, implementuje jejich řešení a případně se pokusí metodu modifikovat resp. zobecnit k využití na dalších těžkých problémech.
Seznam odborné literatury
Jiří Ivánek, Jaroslav Morávek: Heuristic improvement of the dynamic programming treatment of the TSP. Ekonomicko-matematický obzor 17, 1981, č. 1, str. 13 - 27.

Stuart J. Russel, Peter Norvig: Artificial Intelligence. A Modern Approach. Second Edition. Prentice Hall, New Jersey 2003.

S. Dasgupta, C. H. Papadimitriou, U. V. Vazirani: Algorithms. Penultimate draft. Berkeley 2006.

G. Gambosi, P. Crescenzi, V. Kann, A. Marchetti-Spaccamela, M. Protasi: Complexity and Approximation. Combinatorial Optimization Problems and Their Approximability Properties. Second corrected printing. Springer-Verlag, Berlin 2003.

Dorit S. Hochbaum (ed.): Approximation Algorithms for NP-hard Problems. PWS Publishing Comp, Boston 1997.

Další dle vlastního uvážení a doporučení vedoucího.
Předběžná náplň práce
Předmětem práce je studium a využití některých heuristických metod založených na algoritmu A* na hledání optimálních řešení vybraných NP-těžkých problémů, analýza, na které problémy je tato metoda vhodná (vysvětlení proč) a zhodnocení úspěšnosti této metody na vybraných (NP-těžkých) problémech.
Předběžná náplň práce v anglickém jazyce
Subject to the thesis is study and use of methods based on A*-algorithm finding optimum solutions for particular NP-hard problems. The thesis includes analysis and explanation for which type of problems this method is suitable. Candidate also comments results reached by this method for particular (suitable) NP-hard problems.
 
Univerzita Karlova | Informační systém UK