11. Výpočetní složitost a Turingův stroj

Question 1

Co je výpočetní složitost a jaké jsou její základní komponenty?

Answer 1

Výpočetní složitost je oblast teoretické informatiky, která zkoumá množství zdrojů potřebných pro vyřešení problému pomocí algoritmu. Zdroje zahrnují čas (počet kroků potřebných k dokončení) a prostor (množství paměti vyžadované algoritmem).

Question 2

Co označují pojmy časová a prostorová složitost v kontextu algoritmů?

Answer 2

• Časová složitost: Vyjadřuje, jak rychle roste počet kroků algoritmu v závislosti na velikosti vstupu, obvykle vyjádřeno pomocí notace Big O, Ω, nebo Θ.
• Prostorová složitost: Vyjadřuje množství paměti potřebné pro zpracování dat algoritmem, také vyjádřeno pomocí notace Big O.

Question 3

Co je Turingův stroj a jaké má základní komponenty?

Answer 3

Turingův stroj je teoretický výpočetní model navržený Alanem Turingem, který je schopen simulovat jakýkoli algoritmický proces. Zahrnuje páskovou jednotku s buňkami obsahujícími symboly, čtecí/zapisovací hlavu pro manipulaci s symboly, a konečný řídící mechanismus, který řídí operace stroje podle přechodové funkce.

Question 4

Jaký vztah má Turingův stroj k výpočetní složitosti?

Answer 4

Turingův stroj poskytuje základ pro definici a analýzu složitosti algoritmů. Pomocí tohoto modelu lze identifikovat a klasifikovat různé třídy složitosti, jako jsou P (polynomiální čas) a NP (nedeterministický polynomiální čas), a zkoumat, které problémy jsou teoreticky řešitelné v rámci těchto tříd.

Question 5

Co znamená, když je problém “Turing řešitelný”?

Answer 5

Problém je “Turing řešitelný”, pokud existuje algoritmus, který ho může vyřešit na Turingově stroji. Toto označení ukazuje, že problém je v principu řešitelný pomocí algoritmického přístupu, bez ohledu na praktická omezení, jako jsou výpočetní zdroje nebo čas.

Question 6

Co přesně vyjadřují notace Big O, Ω a Θ?

Answer 6

• Big O (O(g(n))): Udává horní hranici růstu funkce, tedy nejhorší možný scénář.
• Omega (Ω(g(n))): Udává dolní hranici růstu funkce, tedy nejlepší možný scénář.
• Theta (Θ(g(n))): Udává přesnou asymptotickou hranici, kde funkce roste stejně rychle jako g(n) v nekonečnu.