PředmětyPředměty(verze: 807)
Předmět, akademický rok 2017/2018
   Přihlásit přes CAS
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 2014
Semestr: zimní
E-Kredity: 5
Rozsah, examinace: zimní s.:2/1 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Poznámka: předmět lze zapsat opakovaně
Garant: doc. Mgr. Michal Koucký, Ph.D.
Třída: Informatika Mgr. - Teoretická informatika
Kategorizace předmětu: Informatika > Teoretická informatika
Anotace -
Poslední úprava: T_KTI (12.05.2006)

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.
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: doc. 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.

Požadavky ke zkoušce -
Poslední úprava: doc. 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.

Sylabus -
Poslední úprava: T_KTI (12.05.2006)

  • Náhodnost a pseudonáhodné generátory.
  • Komunikační složitost a interaktivní protokoly.
  • Samoopravné kódy.
  • Dolní odhady.
  • Expandery a jejich použití.

 
Univerzita Karlova | Informační systém UK