Ot�zky ke st�tn� zkou�ce z v�po�tov� slo�itosti

1. Z�kladn� pojmy v�po�tov� slo�itosti
   • formalizace pojmu �loha
   • v�po�etn� modely (varianty TS, RAM, Booleovsk� obvody)
   • m��en� slo�itosti
   • vztah rozhodovac�ch a obecn�ch �loh
   • polynomi�ln� ekvivalence v�po�etn�ch model�
2. NP-�plnost
   • t��da NP
   • p-p�evoditelnost a jej� vlastnosti
   • NP-�pln� �lohy
   • SAT je NP-�pln�
   • dal�� NP-�pln� �lohy
3. Efektivn� algoritmy pro varianty NP-�pln�ch �loh
   • probl�m batohu p�i jednotkov�m k�dov�n� vstupu
   • 2-SAT
   • aproxima�n� algoritmus pro
     • probl�m obchodn�ho cestuj�c�ho
     • probl�m vrcholov�ho pokryt�
     • probl�m mno�inov�ho pokryt�
     • probl�m maxim�ln�ho �ezu
4. Obecn� slo�itostn� t��dy
   • Blumova teorie slo�itosti
   • v�ta o d�r�ch
   • v�ta o zrychlen�
   • konstruovateln� funkce
   • v�ty a �asov� a prostorov� hierarchii
5. PSPACE
   • zaveden� PSPACE-�plnosti
   • probl�m KBF
   • hra na grafech
6. Booleovsk� slo�itost
   • DNF, KNF, rozhodovac� stromy
   • odhady slo�itosti konkr�tn�ch funkc�
   • porovn�n� v�po�etn� s�ly uveden�ch model�
7. Kryptografick� syst�my s ve�ejn�m kl��em
   • z�kadn� v�ty z teorie ��sel
   • testy prvo��selnosti
   • RSA
   • Diffie-Hellman�v syst�m distribuce utajen�ho n�hodn�ho kl��e