Teorie složitosti

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 a určení vztahů mezi nimi. Ke studiu a určení složitosti těchto problémů definuje výpočetní modely, jako je Turingův stroj nebo RAM, na kterých je simuluje a určuje složitost (typicky časovou a paměťovou). Používají se i další míry složitosti, jako množství komunikace (v komunikační složitosti), počet hradel obvodu (ve složitosti obvodů), počet přístupů do keše (v analýze kešování) a počet procesorů (v paralelním programování). Jeden z cílů teorie složitosti je určit praktické limity toho, co počítače dokážou spočítat a co ne.

V tomto kontextu je výpočetní problém chápán jako úkol, který lze vyřešit na počítači, čímž se myslí mechanickou aplikací postupných kroků pomocí algoritmu. Konkrétní zadání problému je tzv. instance a algoritmus vrátí řešení instance. Příkladem je situace, kdy chceme zjistit, zdali je nějaké přirozené číslo n prvočíslem nebo ne. Jedná se o rozhodovací problém, kde instancí problému jsou přirozená čísla a výsledkem je odpověď ANO/NE.

Problém, například výše zmíněné testování prvočíselnosti, se považuje za těžký, pokud jeho řešení potřebuje značné zdroje bez ohledu na to, jaký algoritmus je použit.

Příbuzné oblasti informatiky jsou analýza algoritmů a teorie vyčíslitelnosti. Hlavním rozdílem mezi analýzou algoritmů a teorií složitosti je, že analýza algoritmů se zabývá množstvím potřebných zdrojů, které potřebuje konkrétní algoritmus, zatímco teorie složitosti zjišťuje obecnější otázky týkající se všech algoritmů, které se dají použít pro řešení určitého problému. Snaží se tedy klasifikovat problémy podle daných omezení na dostupné zdroje. Tedy zavedení omezení na dostupné zdroje odlišuje teorii složitosti od teorie vyčíslitelnosti, které se ptá, jaké problémy lze, v principu, vyřešit algoritmicky.

Výpočetní problémy

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

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, tzv. instanci problému, 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

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čů. Matematické úlohy v oblasti grafů například můžeme zadávat pomocí sousednosti v podobě matic.

Rozhodovací problém a Formální jazyk

Rozhodovací problém je jeden ze základních typů problémů teorie složitosti, který má pouze dva možné výstupy ANO či NE. Případně binárně 0 nebo 1. V jazyku, 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. Algoritmus počítá charakteristickou funkci jazyka.

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

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.

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 rozhodovacího problému je tedy trojice $(a,b,c)$ a odpověď ANO se vrací pouze pro trojice, kde platí $a\cdot b=c$ .

Měření velikosti vstupu

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 funkce ${\mathcal {T}}(n)$ . Například pokud ${\mathcal {T}}(n)$ je polynomiální pak hovoříme o polynomiálním algoritmu. 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.

Měření velikosti (zdrojů)

Zajímá nás spotřebovaný čas (v krocích), paměť (v bitech/bajtech/buňkách), pakety (rámcově v rámcích), cache (např. počet přístupů) ... A to buď pro konkrétní algoritmus anebo pro nějaký problém, čímž se myslí nejlepší algoritmus pro předložený problém. A protože to chceme obecně pro data velikosti n a nikoli pro konkrétní hodnotu vstupu k (velikosti n), navíc pro všechny možné (počtem nekonečné) velikosti, tak složitost odhadujeme a to obvykle asymptoticky.

A ještě obecnější pojem jsou třídy složitosti.

Související články

Externí odkazy

Obrázky, zvuky či videa k tématu teorie složitosti na Wikimedia Commons

Reference

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

Knihy

Sanjeev Arora, Boaz Barak; BARAK, Boaz. Computational Complexity: A Modern Approach. [s.l.]: Cambridge, 2009. Dostupné online. ISBN 978-0-521-42426-4.
DOWNEY, Rod; FELLOWS, M. Parameterized complexity. Berlin, New York: Springer-Verlag, 1999. Dostupné online.
DU, Ding-Zhu, Ko, Ker-I. Theory of Computational Complexity. [s.l.]: John Wiley & Sons, 2000. ISBN 978-0-471-34506-0.
GOLDREICH, Oded. Computational Complexity: A Conceptual Perspective. [s.l.]: Cambridge University Press, 2008. Dostupné online.
edited by Jan van Leeuwen. Vol.A, Algorithms and complexity. Handbook of theoretical computer science (vol. A): algorithms and complexity. Redakce van Leeuwen Jan. [s.l.]: MIT Press, 1990. ISBN 978-0-444-88071-0.
PAPADIMITRIOU, Christos. Computational Complexity. 1st. vyd. [s.l.]: Addison Wesley, 1994. ISBN 0201530821.
SIPSER, Michael. Introduction to the Theory of Computation. 2nd. vyd. USA: Thomson Course Technology, 2006. ISBN 0534950973.

Články

COOK, Stephen. An overview of computational complexity. Commun. ACM. ACM, 1983, s. 400–408. ISSN 0001-0782. DOI 10.1145/358141.358144.
FORTNOW, Lance; HOMER, Steven. A Short History of Computational Complexity. Bulletin of the EATCS. 2003, s. 95–133. Dostupné online.
MERTENS, Stephan. Computational Complexity for Physicists. Computing in Science and Engg.. Piscataway, NJ, USA: IEEE Educational Activities Department, 2002, s. 31–47. ISSN 1521-9615. DOI 10.1109/5992.998639.