Sylabus
1. Optimalizace a aproximace CSP, vCSP 2.Příklady výpočetních problémů, které lze popsat v jazyku vCSP 3.Lineární relaxace vCSP, použití 4.NP-těžká vCSP 5.Algebraická teorie vCSP - Galoisova korespondence mezi váženými relaxačními a algebraickými klony 6.Aproximační algoritmy založené na lineárním a semidefinitním programování 7.Neaproximovatelná CSP - PCP věta, UGC (Unique Games Conjecture) 8.Řešení problémů s extrémně velkým vstupem
Anotace
Diskrétní optimalizační problémy z mnoha oborů lze popsat v jazyku CSP (problém splnitelnosti omezujících podmínek) nebo vCSP (ohodnocené CSP). Předmět se zaměří na výpočetní složitost optimalizace a aproximace vCSP, zejména vCSP s pevnou šablonou. Podíváme se, které problémy umíme řešit rychle, které ne, a proč.
Předmět nemusí být vyučován každý rok, je vyučován alespoň jednou za dva roky.