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:
-
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í. 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é ulici. Úmluva bude v prvním
týdnu semestru na KAM, v rámci hromadné úmluvy na výběrové přednášky KAM.
Kontakt: sgall@math.cas.cz, pudlak@math.cas.cz,
http://www.math.cas.cz/~sgall/,
http://www.math.cas.cz/~pudlak/,
tel. 22090780, 22090721.
28. 3. 2001