SubjectsSubjects(version: 945)
Course, academic year 2023/2024
   Login via CAS
Optimization and Approximation CSP - NMMB536
Title: Optimalizace a aproximace CSP
Guaranteed by: Department of Algebra (32-KA)
Faculty: Faculty of Mathematics and Physics
Actual: from 2019
Semester: summer
E-Credits: 6
Hours per week, examination: summer s.:2/2, C+Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
4EU+: no
Virtual mobility / capacity: no
State of the course: not taught
Language: English, Czech
Teaching methods: full-time
Teaching methods: full-time
Guarantor: doc. Mgr. Libor Barto, Ph.D.
Class: M Mgr. MMIB
M Mgr. MMIB > Povinně volitelné
Classification: Mathematics > Algebra
Annotation -
Last update: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (14.05.2019)
The course may not be taught every academic year, it will be taught at least once every two years.
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