Detail of the student project

List
Topic:Aproximační algoritmy pro úlohy řešitelné dynamickým programováním
Department:Katedra kybernetiky
Supervisor:RNDr. Daniel Průša Ph.D.
Announce as:DP,BP,PMI,PRO
Description: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.
Bibliography:[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
Date:22.12.2017
Responsible person: Petr Pošík