SubjectsSubjects(version: 845)
Course, academic year 2018/2019
   Login via CAS
Optimization and Approximation CSP - NMMB536
Title in English: Optimalizace a aproximace CSP
Guaranteed by: Department of Algebra (32-KA)
Faculty: Faculty of Mathematics and Physics
Actual: from 2018 to 2018
Semester: summer
E-Credits: 6
Hours per week, examination: summer s.:2/2 C+Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: not taught
Language: English, Czech
Teaching methods: full-time
Guarantor: doc. Mgr. Libor Barto, Ph.D.
Class: M Mgr. MMIB
M Mgr. MMIB > Povinně volitelné
Classification: Mathematics > Algebra
Annotation - Czech
Last update: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (14.05.2019)
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č.
Course completion requirements - Czech
Last update: 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.

Literature -
Last update: T_KA (30.04.2015)

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

Requirements to the exam - Czech
Last update: RNDr. Alexandr Kazda, Ph.D. (23.02.2018)

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

Syllabus - Czech
Last update: 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

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html