Teorie složitosti

Technology

12 hours ago

Author

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. +more 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. +more 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

německá města znázorněná na obrázku, přičemž každé město navštíví právě jednou. +more 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. +more 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čů. +more 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. +more 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. +more 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. +more 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ů) . +more 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.