Wikipedie

Teorie složitosti: Porovnání verzí

Interaktivně procházet historii
← Přejít na předchozí porovnáníPřejít na další porovnání →
Smazaný obsah Přidaný obsah
VizuálníWikitext
preklad perexu - soory, jeste opravit
m dokonceni preekladu perexu
Řádek 1:
{{Informatika}}
{{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 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ítestování prvočíselnosti'', se považuje za těžký, pokud jeho řesšenířešení potřebuje značné zdroje bez ohledu na to, jaký algorimtusalgoritmus je použit. Teorie složitosti formalizuje twetnotento intuitivní přístup a zavádí [[v7po4tn9výpočetní modelymodel]]y. Na nich se studuje a kvantifikuje množství potřebných zdtojůzdrojů pro řešení problémů, např. čas a paměť.
PoužívajéPoužívají se i další míry složitoastislož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 [[palalelníchparalelních výpočtech]]). Jeden z cílů teorie složitosti jer určit praktické limity toho, co počítače dokážou sločítatspočítat a co ne.
 
SPříbuzné tímtooblasti problémeminformatiky souvisí takéjsou [[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]]složitosti je, že analýaanalýza algoritmů se zabývá množstvímmpotřebnychmnožstvím potřebných zdrojů, které potřebuje koknrétníkonkrétní algoritmus, zatímco [[teorie vyčíslitelnosti]]složitosti obecnějizjišťuje zjiš´tuje,obecnější jakéotázky všechnytýkající možnése algorimyvšech algoritmů, které se dají použít pro řešení určitého problému. Snaží se tedy klasifikovat problémproblémy podle daných omezení na dostupné zdroje. ...PodleTedy <s>pořadízavedení a</s>omezení omezenostina zdrojůdostupné dávázdroje tedyodlišuje odpověďteorii nasložitosti otázkuod teorie vyčíslitelnosti, zdakteré úkolse ptá, jaké problémy lze, vyřešitv algoritmickyprincipu, čivyřešit nealgoritmicky.▼
<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 analýa algoritmů se zabývá množstvímmpotřebnych zdrojů, které potřebuje koknrétní algoritmus, zatímco [[teorie vyčíslitelnosti]] obecněji zjiš´tuje, jaké všechny možné algorimy se dají použít pro řešení určitého problému. Snaží se tedy klasifikovat problém podle daných omezení na dostupné zdroje. ...Podle <s>pořadí a</s> omezenosti zdrojů dává tedy odpověď na otázku, zda úkol lze vyřešit algoritmicky či ne.
 
== Výpočetní problémy ==
Citováno z „https://cs.wikipedia.org/wiki/Teorie_složitosti“