Teorie složitosti: Porovnání verzí

'''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č|počítači]]i. Problém tedy spočívá v zadání a jeho řešení. Základním příkladem je situace, kdy chceme zjistit zda-li 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.

Zde nehraje roli samotný [[algoritmus]], ale také například množství potřebného [[čas|času]]u a finančních prostředků k realizaci řešení. Teorie používá ke studiu těchto problémů [[Matematický model|modely]], které hledají potřebné kapacity a zkoumají [[čas]] potřebný pro výpočet. Dalšími prostředky mohou být nástroje určené k sestavování samotného výpočetního systému. Zjišťují tedy možnosti [[Výpočetní cluster|paralelizace]] výpočtů na víceprocesorový systém. Dále je třeba zajistit v jakém rozsahu mohou stroje provádět výpočty, tedy co mohou provádět a co ne.

[[ImageSoubor:TSP Deutschland 3.png|thumb|200px|Ukázkovým problémem je problém obchodníka, který musí projít všechna velká [[Měmecko|německá]] města znázorněná na obrázku, přičemž každé město navštíví právě jednou. Pokud vezmem v úvahu že se v jednom městě nachází a nezáleží na směru další objednávky, pak existuje 14!/2 = 43,589,145,600 dalších možností.]]

Rozhodovací problém je jeden ze základních typů problémů teorie složitosti, který má pouze dva možné výstupní stavy ANO či NE. Případně [[Dvojková soustava|binárně ]] 0 nebo 1. V [[Formální jazyk|jazyku logiky]], kde členy jazyka jsou případy s odpovědí ANO a ostatní členy s odpovědí NE. Je třeba pomocí algoritmu rozhodnout jakým způsobem zadaný vstup s tímto jazykem odpovídá. Jestliže algoritmus vrátí ANO pak je vstup přijmut, jinak odmítnut.

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|bitech]]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.

* {{Citation