| Téma: | Aproximační algoritmy pro úlohy řešitelné dynamickým programováním
|
|---|
| Vedoucí: | doc. RNDr. Daniel Průša Ph.D.
|
|---|
| Vypsáno jako: | Diplomová práce,Bakalářská práce,Individuální projekt,Semestrální projekt
|
|---|
| Popis: | Dynamické programování je účinná technika, kterou lze uplatnit při návrhu polynomiálních algoritmů pro celou řadu problémů. Jejich polynomiální složitost nemusí být však dostačující při zpracování velkých vstupních instancí, které se dnes běžně vyskytují v disciplínách jako je strojové učení nebo dobývání znalostí. Efektivnější přístup je nalézt přibližné řešení ve (skoro) linárním čase. Příklady těchto algoritmů nalezneme v [2] (problém optimálního vyhledávacího stromu) nebo v [3] (problému batohu). Cílem práce je studium takovýchto algoritmů, návrh a implementace (Java nebo C++) vlastních pro vybrané úlohy a jejich teoretická a/nebo empirická analýza.
|
|---|
| Literatura: | [1] Algoritmizace (B4B33ALG), slidy k přednáškám o dynamickém programování, https://cw.fel.cvut.cz/wiki/courses/b4b33alg/prednasky
[2] K. Mehlhorn: Nearly optimal binary search trees, https://people.mpi-inf.mpg.de/~mehlhorn/ftp/mehlhorn3.pdf
[3] Knapsack problem: 2-approximation algorithm, section 10.2.1 in https://www.cs.cmu.edu/afs/cs/academic/class/15854-f05/www/scribe/lec10.pdf
|
|---|
| Vypsáno dne: | 22.12.2017
|
|---|