statnice:magistr:b4m01tal

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.

====== Třídy složitosti úloh/jazyků vzhledem k časové složitosti jejich řešení a paměťové složitosti včetně nerozhodnutelných úloh/jazyků. ======

[[https://fel.cvut.cz/en/education/bk/predmety/46/95/p4695106.html|BE4M01TAL]] [[https://moodle.fel.cvut.cz/course/view.php?id=5851|Webové stránky předmětu]]

  * **Asymptotický růst funkcí**, časová a prostorová složitost algoritmů. Správnost algoritmů – varianta a invariant.
  * **Deterministické Turingovy stroje**, vícestopé Turingovy stroje a nedeterministické Turingovy stroje.
  * **Rozhodovací problémy a jazyky.** Třídy složitosti P, NP, co-NP. Redukce a polynomiální redukce, třída NPC. Cookova věta. Heuristiky a aproximační algoritmy pro řešení NP-úplných problémů.
  * **Třídy založené na paměťové složitosti:** PSPACE a NPSPACE. Savitchova věta.
  * **Randomizované algoritmy.** Randomizované Turingovy stroje. Třídy založené na randomizaci: RP, ZPP, co-RP.
  * **Rozhodnutelnost a nerozhodnutelnost.** Rekurzivní a rekurzivně vyčíslitelné jazyky. Diagonální jazyk. Univerzální jazyk a univerzální Turingův stroj.

Trace: • b4m39nur • exams

Search

Navigation

Print/export

Tools

QR Code