Teorie složitosti

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
Informatika
Obory informatiky
Programování
Matematická informatika
Teoretická informatika
Teorie složitosti
Umělá inteligence
Teorie grafů
Teorie informace
Informační technologie
Bioinformatika
Chemoinformatika
Geoinformatika
Lékařská informatika
Neuroinformatika
Sociální informatika
Informatici
Charles Babbage
Alan Turing
Donald Knuth
další...
Dějiny informatiky

Teorie složitosti je odvětvím teorie počítání v informatice a matematice, které se zaměřuje na klasifikaci 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číslem nebo ne. Zadáním tohoto jsou tedy 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 času a finančních prostředků k realizaci řešení. Teorie používá ke studiu těchto problémů 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 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.

S tímto problémem souvisí také analýza algoritmů a teorie vyčíslitelnosti. Hlavním rozdílem mezi analýzou algoritmů a teorií vyčíslitelnosti je že teorie vyčíslitelnosti se zabývá spíše výší finančních prostředků, které mimochodem potřebují samostatný algoritmus, zatímco analýza algoritmů se zabývá možnostmi všech možných použitelných algoritmů. Snaží se tedy klasifikovat problém podle omezenosti dostupných zdrojů. Podle pořadí a omezenosti zdrojů dává tedy odpověď na otázku zda úkol lze řešit algoritmicky či ne.

Výpočetní problémy[editovat | editovat zdroj]

Ukázkovým problémem je problém obchodníka, který musí projít všechna velká německá města znázorněná na obrázku, přičemž každé město navštíví právě jednou. Pokud vezmeme 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í.

Zadání problému[editovat | editovat zdroj]

Výpočetní problém lze chápat jako nekonečnou sbírku příkladů a jejich řešení pro danou situaci. Zadání vstupu nelze zaměňovat s problémem samotným. Problém je třeba řešit bez ohledu na způsob jeho zadání. Například zmíněný test na prvočíslo. Zadáním je číslo a výstupem "ano" nebo "ne". Výstup tedy musí patřičně korespondovat se zadáním.

Možnosti zadávání problému[editovat | editovat zdroj]

Nejzákladnějším způsobem je zadání problému v podobě vyslovené věty. Pokud se jedná o následné řešení počítačem je třeba překládat do jazyka počítačů tedy do binárního kódu. Matematické úlohy v oblasti grafů například můžeme zadávat pomocí sousednosti v podobě matic.

Rozhodovací problém a Formální jazyk[editovat | editovat zdroj]

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ě binárně 0 nebo 1. V 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řijat, jinak odmítnut.

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ě.

Formální jazyky (a problémy nad nimi) jsou nad nějakou abecedou, která nemusí být nutně binární.

Problém funkce[editovat | editovat zdroj]

Problém funkce je výpočetní problém, kde jeden výstup totální funkce platí pro všechny možné vstupy, ale je složitější než výstup rozhodovací funkce, neočekává se pouze výstup ve tvaru ANO nebo NE.

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ě čí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 a \cdot b = c.

Měření velikosti vstupu[editovat | editovat zdroj]

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

Jestliže je vstupem n pak čas potřebný pro výpočet je funkcí \mathcal{T}(n). Například pokud \mathcal{T}(n) je polynomiální pak hovoříme o polynomiálním algoritmu pro všechny vstupy n. Cobhamova teze říká že problém lze vyřešit v polynomiálním čase, pokud pro něj existuje algoritmus, který zpracuje n bitový vstup v čase \mathcal{O}(n^c), kde c je konstanta závisející na problému, nikoliv jeho vstupu.

Související články[editovat | editovat zdroj]

Zdroje[editovat | editovat zdroj]

V tomto článku byl použit překlad textu z článku Computational complexity theory na anglické Wikipedii.


Knihy[editovat | editovat zdroj]

Články[editovat | editovat zdroj]