PředmětyPředměty(verze: 825)
Předmět, akademický rok 2017/2018
   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 2016 do 2017
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: vyučován
Jazyk výuky: č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: RNDr. Alexandr Kazda, Ph.D. (23.02.2018)

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: RNDr. Alexandr Kazda, Ph.D. (23.02.2018)

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