Teorie složitosti: Porovnání verzí
Smazaný obsah Přidaný obsah
m Úprava rozcestníku za pomoci robota: Graf - změna odkazu/ů na Graf (teorie grafů) |
Zpřesnění úvodu, přeformátování, odkaz na rozhodovací problém značky: první editace editace z Vizuálního editoru |
||
Řádek 2:
{{Upravit| Každá věta jiná přednáška, skripta, škola ; nepřesnosti ; nepřesný překlad}}
'''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 a určení vztahů mezi
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í [[Algoritmus|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číslo|prvočíslem]] nebo ne. Jedná se o [[rozhodovací problém]], kde instancí problému jsou [[přirozené číslo|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. Teorie složitosti formalizuje tento intuitivní přístup a zavádí [[výpočetní model]]y. Na nich se studuje a kvantifikuje množství potřebných zdrojů pro řešení problémů, např. čas a paměť.▼
▲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ýza algoritmů|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.
| |||