Teorie složitosti: Porovnání verzí

{{Informatika}}

'''Teorie složitosti''' je odvětvím [[teorie počítání]] v [[Informatika|informatice]] a [[matematika|matematice]], které se zaměřuje na klasifikaci [[Výpočetní problém|výpočetních problémů]] dle jejich vlastní složitosti. V tomto kontextu je problém chápán jako úkol, který lze zpracovat na [[počítač]]i. Problém tedy spočívá v zadání a jeho řešení. Základním příkladem je situace, kdy chceme zjistit zdali je nějaké přirozené číslo ''n'' [[prvočíslo|prvočíslem]] nebo ne. Zadáním tohoto jsou tedy [[přirozené číslo|přirozená čísla]] a výsledkem je odpověď ANO/NE případně 0 nebo 1.

 

 

Příkladem rozhodovacího problému je [[graf]] a máme rozhodnout zda je to [[souvislý graf]] či ne. Formální jazyk je pak množina všech souvislých grafů a pouze je třeba rozhodnout, jak graf reprezentovat v binární podobě.

 

=== Problém funkce ===

Lze se zamyslet nad tím, že [[problém funkce]] je bohatší na výsledky než [[rozhodovací problém]]. Nicméně [[problém funkce]] lze přepracovat také na rozhodovací problém a to takto: chceme vynásobit dvě [[Číslo|čísla]], vstupem je tedy množina o třech členech a rozhodnutí o tom, zda je třetí člen součástí množiny rozhodne operace <math>a \cdot b = c</math>.

 

Závisí na množství času pro zpracování algoritmem. Tyto dílčí problémy, kterým může být i prostor potřebný pro řešení zpracovává samostatný [[algoritmus]] a vše souvisí také s velikostí vstupu v [[bit]]ech. Teorie složitosti se zajímá mimo jiné o způsob jakým se algoritmus vypořádá s velikostí vstupu. Například pro řešení souvislého grafu o ''n'' hranách v porovnání s grafem o ''2n'' hranách.