Vybrané kapitoly z výpočetní složitosti I - NTIN085

• Anglický název: Selected Topics in Computational Complexity I
• Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2024
• Semestr: zimní
• E-Kredity: 4
• Rozsah, examinace: zimní s.:2/1, Z+Zk [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, angličtina
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Poznámka: předmět lze zapsat opakovaně
• Garant: prof. Mgr. Michal Koucký, Ph.D.
• Vyučující: prof. Mgr. Michal Koucký, Ph.D.
• Třída: Informatika Mgr. - Teoretická informatika
• Kategorizace předmětu: Informatika > Teoretická informatika
• Je neslučitelnost pro: NTIX085
• Je záměnnost pro: NTIX085

Anotace

čeština

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)

angličtina

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.

Poslední úprava: T_KTI (12.05.2006)

Cíl předmětu

Naučit vybrané kapitoly z výpočetní složitosti

Poslední úprava: T_KTI (23.05.2008)

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

čeština

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: Koucký Michal, prof. Mgr., Ph.D. (09.10.2017)

angličtina

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.

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

Požadavky ke zkoušce

čeština

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: Koucký Michal, prof. Mgr., Ph.D. (09.10.2017)

angličtina

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.

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

Sylabus

čeština

• 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: Koucký Michal, prof. Mgr., Ph.D. (01.10.2021)

angličtina

• 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

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