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 [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: 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.; prof. Mgr. Michal Koucký, Ph.D.
• Vyučující: prof. Mgr. Michal Koucký, Ph.D.; prof. RNDr. Pavel Pudlák, DrSc.
• Třída: Informatika Mgr. - volitelný
• Kategorizace předmětu: Informatika > Teoretická informatika
• Je neslučitelnost pro: NTIN053
• Je záměnnost pro: NTIN053

Anotace

čeština

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/.

Poslední úprava: T_KAM (14.04.2002)

angličtina

Seminar on computational complexity and related combinatorial problems. Recent papers and results of the participants are presented.

Poslední úprava: T_KAM (06.05.2001)

Cíl předmětu

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

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

Podmínky zakončení předmětu

čeština

Zápočet se uděluje za aktivní pravidelnou účast na semináři a alespoň jednu prezentaci na semináři během semestru.

Zápočet nelze opakovat.

Poslední úprava: Koucký Michal, prof. Mgr., Ph.D. (09.10.2017)

angličtina

Credit for the seminar is obtained for regular active participation at the seminar which includes at least one presentation at the seminar during the semester.

There is no make up for getting the credit.

Poslední úprava: Koucký Michal, prof. Mgr., Ph.D. (09.10.2017)

Literatura

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

Poslední úprava: T_KAM (22.04.2003)

Sylabus

čeština

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ů.

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

angličtina

Recent topics include:

• Sublinear algorithms.

• Error-correcting codes and their applications in complexity.

• Low degree polynomials and use of algebraic methods in complexity.

• Boolean complexity, lower bounds for explicit functions, formulas, branching programs.

• Lower bounds for propositional proof systems.

• Communication complexity.

• Combinatorial problems related to complexity. Expanders. Extremal combinatorics of set systems.

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