Výpočetní složitost I a II

Přednáška se koná na katedře logiky FF UK.

Rozsah: ZS 2/0 Z
LS 2/0 Zk

Sylabus
Otázky ke státnicím
Průběh ZS 2015/2016
Průběh LS 2015/2016
Průběhy předchozích ročníků

Texty ke zkoušce:
      strany jednotlivě       2 strany na 1 list
Výpočetní složitost I vypsl2016zs1.pdf vypsl2016zs2.pdf
Výpočetní složitost II (bez Bool. f.) vypsl2016ls1.pdf vypsl2016ls2.pdf
Reprezentace Booleovských funkcí rbf2011a1.pdf rbf2011a2.pdf

Z textu Reprezentace Booleovských funkcí jsou pro předmět Výpočetní složitost II potřeba sekce 1, 2, 7.1, 7.2, 7.3, tedy především výsledky týkající se DNF, CNF a rozhodovacích stromů.

Zápočet a zkouška

Zápočet po prvním semestru je udělován na základě písemného testu.
Zkouška je za celý rok, tedy za zimní i letní semestr.

Pro stanovení termínu zkoušky nebo zápočtu napište email.

Literatura

Sanjeev Arora and Boaz Barak, Computational Complexity, A Modern Approach.
Cambridge University Press, 2009.

Další odkazy

RSA
Diffie-Hellman

Luca Trevisan, Inapproximability of Combinatorial Optimization Problems

Johan Hastad, Some optimal inapproximability results

vlastnosti MD5 včetně informace o hledání kolizí
pravděpodobnostní test prvočíselnosti