Třídy složitosti paměťové a časové Flashcards
(8 cards)
Teorie vyčíslitelnosti a složitost
Teorie vyčíslitelnosti zkoumá otázku algoritmické řešitelnosti problému z pohledu řešitelnosti (které problémy LZE/NELZE vyřešit algoritmem), ne časové náročnosti. Vyčíslitelnost je zkoumána pomocí teoretických výpočetních modelů – deterministický a nedeterministický konečný automat, zásobníkový automat, Turingův stroj a další.
Složitost je vztah algoritmu k prostředkům (čas a velikost paměti).
Zabývá se tím, kolik zdrojů (čas, paměť) je potřeba k řešení vyčíslitelného problému. Jinými slovy – i když problém řešit lze, nemusí být prakticky řešitelný. Paměťová složitost je závislost paměťových nároků na vstupních datech, zatímco časová je dána hrubým odhadem počtu kroků, který daný algoritmus musí provést na základě délky vstupních dat. V potaz by se měly brát oba dva typy složitosti, jelikož může nastat situace, kdy lze problém řešit dvěma algoritmy: jedním s malou časovou složitostí a druhým s malou paměťovou. Výběr z těchto složitostí závisí na hardware a situaci použití.
Asymptotická složitost
Asymptotická složitost je klíčový koncept v analýze algoritmů, který nám umožňuje vyjádřit, jak se časová nebo prostorová náročnost algoritmu mění v závislosti na velikosti vstupu. Používají se tři hlavní notace: Ω (Omega), Θ (Theta) a O (Omikron), které popisují různé aspekty chování algoritmu.
Jelikož vždy nelze určit přesnou složitost algoritmu, byla definována asymptotická složitost, která chování funkce aproximuje ze tří pohledů:
– Nejlepší případ Ω (Omega) značí spodní hranici trvání algoritmu.
– Průměrný případ Θ (Theta) odhaduje nejpravděpodobnější dobu trvání algoritmu.
– Nejhorší případ O (Omicron, big-O) značí horní hranici trvání algoritmu. Je nejčastěji používaná.
Polynomiální algoritmy
Polynomiální algoritmus je takový algoritmus, jehož časová (nebo paměťová) složitost roste polynomiálně vzhledem k velikosti vstupu. To znamená, že počet kroků potřebných k vyřešení problému lze zapsat jako polynom v závislosti na délce vstupu n. Při vysokých hodnotách by nepolynomiální algoritmy byly v kryptografii nepoužitelné.
1) Konstantní O(1) Nezávisí na velikosti vstupních dat
2) Logaritmická O(log 𝑛) Náročnost s velikostí logaritmicky klesá.
3) Lineární O(𝑛) Počet operací je závislý na velikosti vstupních dat.
4) Kvazilineární O(𝑛 log 𝑛) Poslední produkčně použitelná náročnost, např. quicksort.
5) Kvadratická O(𝑛^2) 500 prvků → 250 000 operací.
6) Kubická O(𝑛^3) 200 prvků → 8 000 000 operací.
7) Exponenciální O(2^𝑛) - exponenciální růst počtu operací.
9) Faktoriální O(𝑛!) Faktoriální růst počtu operací.
Posouzení složitosti algoritmů - Algoritmy řazení a hledání
Algoritmy řazení
Třídění pomocí algoritmů Bubble Sort, Insert Sort a Select Sort má složitost O(𝑛^2 ). Algoritmus Quick Sort má složitost Θ(𝑛 log 𝑛)/O(𝑛^2 ). Algoritmus Merge Sort má složitost O(𝑛 log 𝑛).
Algoritmy hledání
Dva základní algoritmy pro hledání jsou Binary search a Linear search. Binární funguje lépe než lineární, ale pouze pro větší a seřazené seznamy.
Třídy složitosti
Třídy složitosti skupinují problémy podle toho, jak rychle se dají vyřešit – tedy jaký algoritmus potřebujeme a kolik času nebo paměti k tomu spotřebujeme.
Třída P (polynomial)- Problémy, které lze řešit v polynomiálním čase.
Např. seřazení čísel, nalezení nejkratší cesty v grafu.
Problémy v P jsou „snadno řešitelné“ na běžném počítači.
roblém patří do třídy P, pokud existuje algoritmus, který ho vyřeší v polynomiálním čase O(𝑛^𝑘) pro nějaké pevné 𝑘.
Třída NP (Nondeterministic polynomial) - Problémy, které lze ověřit v polynomiálním čase.
Je možné je provést v polynomiálním čase na nedeterministickém TS (nebyl doposud sestaven). Spadají pod ně i všechny algoritmy z třídy P.
Pokud ti někdo dá správné řešení, dokážeš ho rychle ověřit.
Ale najít to správné řešení může být extrémně těžké.
Problém obchodního cestujícího, sudoku,
P = NP? (dosud nevyřešený problém teoretické informatiky)
Pokud by se ukázalo, že P = NP, všechny problémy, které se nyní zdají těžké, by šly vyřešit rychle! (např. faktorizace velkých čísel → rozbití šifrování RSA)
NP-těžké - přinejmenším tak těžké, jako nejtěžší z NP. Nemusí být vykonatelné pomocí TS.
NP-problémy mají řešení, které lze ověřit v polynomiálním čase.
NP-těžké problémy nemusí mít ani ověřitelné řešení.
Pokud bychom našli algoritmus pro NP-těžký problém, který běží v polynomiálním čase, dokázali bychom tím, že P = NP!
Ale není jasné, zda jsou všechny NP-těžké problémy v NP (nemusí mít ověřitelné řešení).
Turingův stroj - funkce a vztah ke třídám složitosti, druhy
Turingův stroj je matematický model výpočtu, který definuje, co lze spočítat algoritmicky. Slouží jako základ pro teorii složitosti, protože každý algoritmus lze simulovat na Turingově stroji. Turingův stroj je jednoduchý, ale univerzální model počítače, který dokáže simulovat jakýkoli algoritmus.Nedeterministický Turingův stroj (NTS) je hypotetický model, který může v každém kroku „hádat“ správné rozhodnutí.
Třídy složitosti určují, jak efektivně lze problém vyřešit na Turingově stroji – tedy kolik času (počtu kroků) nebo paměti (počtu políček na pásce) je k tomu potřeba.
Každý problém, který lze vyřešit algoritmicky, může být vyřešen na Turingově stroji.
Turingův stroj – nelze měnit program.
– Univerzální Turingův stroj – program lze přepsat; dnešní PC, mobily, atd.
– Nedeterministický Turingův stroj – doposud nesestaven, sestrojení by znamenalo konec asymetrické kryptografie, neví se jestli ho lze vůbec sestrojit (P vs PN).
– Paralelní Turingův stroj - z pohledu vyčíslitelnosti je ekvivalentní s běžným, jen přináší více výkonu.
– Kvantový Turingův stroj – založen na superpozicích stavů, dokáže řešit „exponenciální explozi“ a převést ji na problém se složitostí v polynomiálním čase.
Turingův stroj - složení a funkce
Skládá se ze tří hlavních částí:
1) Páska (infinite tape)
Nekonečný pás, rozdělený na políčka.
Každé políčko obsahuje symbol z konečné abecedy (např. 0, 1 nebo prázdný znak ⬜).
Slouží jako paměť stroje.
2) Čtecí/zapisovací hlava (head)
Hlava čte symboly na pásce.
Může symbol přepsat jiným symbolem.
Může se pohybovat doleva (L) nebo doprava (R).
3) Řídicí jednotka (finite control)
Obsahuje skončený počet stavů.
Na základě aktuálního stavu a přečteného symbolu rozhoduje, co dělat dál.
Turingův stroj pracuje v krocích podle předem definovaných pravidel.
Každý krok obsahuje tři akce:
1) Přečti symbol pod hlavou.
2) Změň stav podle přečteného symbolu.
3) Proveď akci (přepiš symbol, posuň hlavu vlevo/vpravo).
Stroj pokračuje, dokud nedosáhne koncového stavu (halt state), nebo běží nekonečně.
Vztah časové a paměťové složitosti
Většina algoritmů je kompromisem mezi těmito dvěma druhy složitosti. Pokud bychom měli algoritmus s vysokými nároky na časovou složitost (aby byl co nejrychlejší) tak jeho paměťová složitost bude vzrůstat. Většinu algoritmů je nějakým způsobem optimalizovaná nebo ji lze optimalizovat
