PředmětyPředměty(verze: 835)
Předmět, akademický rok 2018/2019
   Přihlásit přes CAS
Optimalizace a aproximace CSP - NMMB536
Anglický název: Optimization and Approximation CSP
Zajišťuje: Katedra algebry (32-KA)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2018
Semestr: letní
E-Kredity: 6
Rozsah, examinace: letní s.:2/2 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: nevyučován
Jazyk výuky: angličtina, čeština
Způsob výuky: prezenční
Garant: doc. Mgr. Libor Barto, Ph.D.
Třída: M Mgr. MMIB
M Mgr. MMIB > Povinně volitelné
Kategorizace předmětu: Matematika > Algebra
Anotace
Poslední úprava: T_KA (30.04.2015)

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č.
Podmínky zakončení předmětu
Poslední úprava: T_KA (30.04.2015)

Zápočet i zkouška se udělují za aktivní účast a řešení problémů během semestru. Charakter zápočtu (průběžná práce) neumožňuje opakování pokusu o získání zápočtu.

Literatura -
Poslední úprava: T_KA (30.04.2015)

S. Živný. The Complexity of Valued Constraint Satisfaction Problem. Springer, 2012.

Požadavky ke zkoušce
Poslední úprava: T_KA (30.04.2015)

Zkouška se uděluje za průběžné řešení problémů během semestru.

Sylabus
Poslední úprava: T_KA (30.04.2015)

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

 
Univerzita Karlova | Informační systém UK