Teorie složitosti: Porovnání verzí
Smazaný obsah Přidaný obsah
→top: BFU překlad; já tušil že to bude v ingličtině v pořádku |
preklad perexu - soory, jeste opravit |
||
Řádek 2:
{{Upravit| Každá věta jiná přednáška, skripta, škola ; nepřesnosti}}
'''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 třídami. 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číslo|prvočíslem]] nebo ne. Zadáním tohoto jsou tedy [[přirozené číslo|přirozená čísla]] a výsledkem je odpověď ANO/NE případně 0 nebo 1.
Problém, například výše zmíněné ''terstování prvočíselnosti'', se považuje za těžký, pokud jeho řesšení potřebuje značné zdroje bez ohledu na to, jaký algorimtus je použit. Teorie složitosti formalizuje twetno intuitivní přístup a zavádí [[v7po4tn9 modely]]. Na nich se studuje a kvantifikuje množství potřebných zdtojů pro řešení problémů, např. čas a paměť.
Zde nehraje roli samotný [[algoritmus]], ale také například množství potřebného [[čas]]u a <s>finančních prostředků{{kdy?}}</s> zdrojů, ''ne prachů,'' k realizaci řešení. Teorie používá ke studiu těchto problémů [[Matematický model|modely]], (že by [[výpočetní model]]), které <u>hledají{{kde?}} potřebné kapacity a</u> 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 [[Výpočetní cluster|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. ''Stroje mohou provádět '''instrukce''' 24 hodin a 7 dní v týdnu.''▼
Používajé se i další míry složitoasti, 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 [[palalelních výpočtech]]). Jeden z cílů teorie složitosti jer určit praktické limity toho, co počítače dokážou sločítat a co ne.
▲<s>Zde nehraje roli samotný [[algoritmus]], ale také například množství potřebného [[čas]]u a <s>finančních prostředků{{kdy?}}</s> zdrojů, ''ne prachů,'' k realizaci řešení. Teorie používá ke studiu těchto problémů [[Matematický model|modely]], (že by [[výpočetní model]]), které <u>hledají{{kde?}} potřebné kapacity a</u> 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 [[Výpočetní cluster|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. ''Stroje mohou provádět '''instrukce''' 24 hodin a 7 dní v týdnu.''</s>
S tímto problémem souvisí také [[analýza algoritmů]] a [[teorie vyčíslitelnosti]]. Hlavním rozdílem mezi [[analýza algoritmů|analýzou algoritmů]] a [[teorie vyčíslitelnosti|teorií vyčíslitelnosti]] je, že <u>teorie vyčíslitelnosti se zabývá spíše výší finančních prostředků</u>, 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 <s>pořadí a</s> omezenosti zdrojů dává tedy odpověď na otázku, zda úkol lze vyřešit algoritmicky či ne.▼
▲S tímto problémem souvisí také [[analýza algoritmů]] a [[teorie vyčíslitelnosti]]. Hlavním rozdílem mezi [[analýza algoritmů|analýzou algoritmů]] a [[teorie vyčíslitelnosti|teorií vyčíslitelnosti]] je, že
== Výpočetní problémy ==
| |||