Obsahem této přednášky jsou pokročilé partie z výpočetní složitosti. Každý semestr bude věnován jinému tématu. Mezi plánovaná témata patří oblast náhodnosti a pseudonáhodných generátorů, komunikační složitost a interaktivní protokoly, samoopravné kódy a jejich užití ve složitosti, dolní odhady, expandery a jejich použití a další. Přednáška je určena především studentům vyšších ročníků studia a doktorandům. Přednáška předpokládá základní znalosti z výpočetní složitosti, pravděpodobnosti a diskrétní matematiky.
Poslední úprava: T_KTI (12.05.2006)
This course covers advanced topics in computational complexity. Each semester will be devoted to a different topic. Topics will include among others: randomness and pseudorandom generators, communication complexity and interactive protocols, error-correcting codes and their applications in complexity, lower bounds, expanders and their applications. The course is intended to students from upper classes and to graduate students. Prerequisites: understanding of elementary concepts from computational complexity, probability theory and discrete math.
Cíl předmětu
Poslední úprava: T_KTI (23.05.2008)
Naučit vybrané kapitoly z výpočetní složitosti
Podmínky zakončení předmětu -
Poslední úprava: prof. Mgr. Michal Koucký, Ph.D. (09.10.2017)
Zápočet se uděluje po získání dostatečného počtu bodů z domácích úkolů. Je nutné získat alespoň 50% všech možných bodů za příklady a řešit úlohy z alespoň 3/4 zadaných sérií.
Zápočet nelze opakovat.
Zápočet je nutný ke zkoušce.
Poslední úprava: prof. Mgr. Michal Koucký, Ph.D. (09.10.2017)
The credit from tutorials is given based on the number of points obtained from the homework assignments. To get the credit one has to get at least 50% of the total number of points
for the assignments, and one has to solve at least some problem from at least 3/4 of the assignments.
There are no make-up homeworks.
The credit from tutorials has to be obtained before taking an exam.
Požadavky ke zkoušce -
Poslední úprava: prof. Mgr. Michal Koucký, Ph.D. (09.10.2017)
Zkouška je ústní. Zkouší se z probrané látky. Po zadání otázek dostane student čas na přípravu.
Studijní materiály (skripta, učebnice a zápisky z přednášek) ani notebooky, kalkulačky, PDA, atd., nejsou u zkoušky dovoleny.
Poslední úprava: prof. Mgr. Michal Koucký, Ph.D. (09.10.2017)
The exam is oral from the material covered by the lectures. Each student gets reasonable time (at most three hours) for preparation upon receiving the questions.
Study materials (lecture notes, text books, etc.), computers and other electronic devices are not allowed during the exam.
Sylabus -
Poslední úprava: prof. Mgr. Michal Koucký, Ph.D. (01.10.2021)
Náhodnost a pseudonáhodné generátory.
Komunikační složitost a interaktivní protokoly.
Samoopravné kódy.
Dolní odhady.
Expandery a jejich použití.
Upresneni pro rok 2021/22 viz: https://users.math.cas.cz/~talebanfard/mtc.html
Poslední úprava: prof. Mgr. Michal Koucký, Ph.D. (01.10.2021)
Randomness and pseudorandom generators.
Communication complexity and interactive protocols.
Error-correcting codes and their applications in complexity.
Lower bounds.
Expanders and their applications.
For details for 2021/22 see: https://users.math.cas.cz/~talebanfard/mtc.html
