Prerekvizity                                                                                                                                                       

Předpokladem jsou znalosti základních technik pro návrh algoritmů (rekurze, dynamické programování, hladové techniky), datových struktur a algoritmů (v rozsahu předmětů IB002 a IV003).

Sylabus
Kurz je volným pokračováním  kurzů IB002 Algoritmy a datové struktury I a IV003 Algoritmy a datové sturktury II. Prezentuje algoritmické koncepty a metody pro těžké výpočetní úlohy. Systematicky vysvětluje a porovnává možné způsoby atakování těžkých problémů. Zkoumá techniky založené  na randomizaci, aproximační techniky, deterministické přístupy a heuristiky,  a jejich vzájomné kombinace.

• Deterministické techniky: pseudopolynomiální algoritmy, parametrizované algoritmy, branch--and--bound, exponenciální  algoritmy.
• Aproximativní přístup: koncept aproximativního algoritmu, klasifikace aproximatívních algoritmů, stabilita aproximatívních algoritmů, neaproximovatelnost. Techniky návrhu aproximatívních algoritmů. Využití principů dynamického programování a hladových techník. Techniky využívající redukci na úlohu lineárního programování. Kombinatorické přístupy.
• Náhodnostní přístup: klasifikace a paradigmata náhodnostních agoritmů. Techniky návrhu náhodnostních algoritmů. Derandomizace. Kombinace aproximativních a náhodnostních technik.
• Heuristiky: lokální  vyhledávání, simulované žíhání, genetické algoritmy.