PředmětyPředměty(verze: 802)
Předmět, akademický rok 2016/2017
   Přihlásit přes CAS
Seminář z výpočetní složitosti - NTIN050
Anglický název: Seminar on Computational Complexity
Zajišťuje: Katedra aplikované matematiky (32-KAM)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2009
Semestr: oba
E-Kredity: 3
Rozsah, examinace: 0/2 Z [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: čeština
Způsob výuky: prezenční
Další informace: http://www.math.cas.cz/~koucky/complexity/
Poznámka: předmět lze zapsat opakovaně
předmět lze zapsat v ZS i LS
Garant: prof. RNDr. Pavel Pudlák, DrSc.
doc. Mgr. Michal Koucký, Ph.D.
Třída: Informatika Mgr. - volitelný
Kategorizace předmětu: Informatika > Teoretická informatika
Anotace -
Poslední úprava: T_KAM (14.04.2002)

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/.
Cíl předmětu
Poslední úprava: SGALL/MFF.CUNI.CZ (07.04.2008)

Získat přehled o aktuální literatuře a zajímavých výsledcích v teorii složitosti.

Literatura
Poslední úprava: T_KAM (22.04.2003)

Většinou aktuální články v angličtině.

Sylabus -
Poslední úprava: SGALL/MFF.CUNI.CZ (07.04.2008)

Výběr témat se přizpůsobuje zájmům účastníků. V poslední době jsme se zabývali těmito oblastmi:

  • Sublineární algoritmy
  • Kódy a jejich použití v teorii složitosti.
  • Reprezentace pomocí polynomů a použití algebraických metod ve složitosti.
  • Booleovská složitost, dolní odhady výpočetní složitosti explicitních funkcí, formule, branching programy.
  • Dolní odhady pro výrokové kalkuly.
  • Komunikační složitost.
  • Kombinatorické problémy související se složitostí. Expandery. Extremální kombinatorika množinových systémů.

 
Univerzita Karlova | Informační systém UK