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 a určení vztahů mezi třídami. V tomto kontextu je 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. 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.

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. Teorie složitosti formalizuje tento intuitivní přístup a zavádí výpočetní modely. Na nich se studuje a kvantifikuje množství potřebných zdrojů pro řešení problémů, např. čas a paměť. 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.

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[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, 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[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čů. 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ý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[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.

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[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 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ů)[editovat | editovat 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 nikolivěk 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[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]