Zajišťuje: KAM
Vyučující: Pavel Pudlák; Jiří Sgall
Rozsah v ZS: 0/2 Z
Rozsah v LS: 0/2 Z
Třída: I
Anotace
Seminář zaměřený na výpočetní složitost a související kombinatorické problémy.
Referují se zejména aktuální články a výsledky účastníků a hostů semináře.
Je vhodný pro studenty, kteří se chtějí specializovat v této oblasti a
pro doktorandy. Některé referáty budou v angličtině. Aktuální informace
na adrese http://www.math.cas.cz/~sgall/complexity/.
Osnova
Výběr témat se přizpůsobuje zájmům účastníků. V poslední době jsme se zabývali
těmito oblastmi:
-
Exponenciální algoritmy pro NP-úplné problémy
-
Booleovská složitost, dolní odhady výpočetní složitosti explicitních funkcí,
branching programy. Dolní odhady pro výrokové kalkuly.
-
Komunikační složitost. Souvislosti složitosti s algebraickými pojmy: rank,
rigidita matic, vlastnosti řídkých a cirkulantních matic.
-
Kombinatorické problémy související se složitostí. Expandery. Extremální
kombinatorika množinových systémů.
-
Vztahy mezi existencí složitých funkcí a derandomizací pravděpodobnostních
algoritmů.
-
On-line algoritmy.
Základní literatura
Většinou aktuální články v angličtině.
Doplň.popis
Seminář se koná v Matematickém ústavu v Žitné 25, většinou v úterý dopoledne.
Na hromadné úmluvě na
výběrové přednášky KAM lze případně domluvit mírnou změnu termínu.
Kontakt: sgall@math.cas.cz, pudlak@math.cas.cz,
http://www.math.cas.cz/~sgall/,
http://www.math.cas.cz/~pudlak/,
tel. 222 090 780, 222 090 721.
7. 2. 2003