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 2019
• Semestr: letní
• E-Kredity: 6
• Rozsah, examinace: letní s.:2/2, Z+Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: nevyučován
• Jazyk výuky: angličtina, čeština
• Způsob výuky: prezenční
• 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

čeština

Poslední úprava: 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č. Předmět nemusí být vyučován každý rok, je vyučován alespoň jednou za dva roky.

angličtina

Poslední úprava: 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.

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

čeština

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