Please enable JavaScript.
Coggle requires JavaScript to display documents.
14. Korektnost a složitost (Parciální a totální korektnost (specifikace…
14. Korektnost a složitost
Parciální a totální korektnost
variant cyklu
hodnota daná přirozeným číslem, která se v průběhu alg. stále snižuje - dokud nenabude hodnoty, při které alg. končí --> důkay konvergence
invariant cyklu
tvrzení o alg., které platí vždy těsně před cyklem, po skončení každé jeho iterace a po těsně něm
specifikace
vstupní a výstupní podmínka daného alg.
vstupní podm. (φ)
ze všech možných vstupů do daného alg. vymezí ty, pro které je alg. definován
výstupní podm. (ψ)
pro každý korektní vstup daného alg. určuje tvar korektního výstupu
úplný binární strom
vyvážený a plněný zleva, [n/2] listů
konečnost
alg. skončí v konečném množství kroků
binární strom
uspořádaný 2-ární strom
Korektnost
alg. dá pro každý vstup v konečném množství kroků správný výsledek
parciální korektnost
pokud je splněna vstupní podmínka A alg. skončí, výstup splňuje vstupní podmínku
totální korektnost
pokud je splněna vstupní podmínka, alg. skončí vždy a výstup splňuje vstupní podmínku
binární halda
rozděl a panuj alg.
problém rozdělí na elem. problémy --> snadné řešení (rekurze)
složitost algoritmu
náročnost alg. na různé zdroje (doba výpočtu, velikost paměti, počet procesorů,...)
časová složitost
funkce, pro každou velikost vstupních dat je rovna délce nejdelšího výpočtu na všech možných datech této velikosti
analýza nejhoršího případu
prostorová složitost
funkce, pro každou velikost vstupních dat je rovna velikosti paměti výpočtu zabírajícího největší paměť na všech možných datech této velikosti
analýza nejhoršího případu
složitost problému
složitost optimálního alg. řešícího tento problém
časová složitost problému
časová složitost alg., který daný problém řeší nejrychleji
prostorová složitost problému
prostorová složitost alg., který řeší daný problém v nejmenší paměti
délka výpočtu
počet kroků výpočetního modelu pro korektní alf. a korektní vstup
O-notace
- rychlost růstu fcí
O(f(x)
nejhorší - alg. probíhá asym. = rychle / rychleji než f(x)
Ω(x)
nejlepší - alg. probíhá asym. = rychle / pomaleji než f(x)
Θ(x)
průměrná - alg. probíhá asym. = rychle jako f(x)
je zároveň v O(f(x)) a Ω(f(x))
důkaz korektnosti algoritmu
dá správný výsledek
je konečný
třídy složitosti
O(c) << O(logn logn) << O(logn) << O(nlogn) << O(n^c) << O(c^n) << O(n!) << O(n^n)
Důkazy korektnosti
př. specifikace a totální korektnosti (parc. korektnosti, invariant, konvergence):
funkce power pro čísla z a n počítá z^n
napsat v Javě - cyklus / rekurze
pomocí invariantu
pokud bude mít cyklus od 0, jiný invariant (r=z^i)
specifikace
nalezení vstupní a výstupní podmínky
nalezneme vstupy, pro které je program definován
program počítá z^n - cíl fce a výstupní podmínka
když zadáme okrajové hodnoty - nevyjde správně
vstupní podm. φ(<z, n>)
z != 0 a n >= 0
výstupní podm. ψ(<z, n>, r)
r = z^n
totální korektnost
aby byl alg. totálně korektní, musí být parciálně korektní a konvergentní (skončí + vrátí správnou odpověď)
parciální korektnost - invariant
uvedená fce obsahuje cyklus, musíme najít invariant - pomocí něj dokážeme platnost vstupní a výstupní podmínky
podívám se, co cyklus dělá a že chci dostat r=z^n
postup (...)
kód rozdělíme na 3 části - před cykle, cyklus, po cyklu
z uvedeného dostaneme tvrzení
cyklus v každém kroku počítá r tak, že ji pokaždé vynásobí z
z toho vyplývá, že nemáme dostatečně zadaný invariant (postrádá vyjádření i)
analýza cyklu - i jde k n a cyklus se naposledy provede pro i = n
rozšíření r=z^(i-1) na r=z^(i-1) a i <= n+1 - platí před/v/po
znovu ověříme cesty
funkce je parciálně korektní
pokud výpočet skončí na vstupu splňujícím vstupní podmínku, pak výstup splňuje výstupní podm. - tzn. pokud vrátí odpověď, pak je správná
konvergence
po splnění vstupních podmínek algoritmus skončí vždy (tzn. bez vstupní podmínky nemusí)
jediné, co nám v této fci může zabránit v ukončení, je cyklus
přijdu na: n-i+1
... klesá při každém průchodu o 1 + nikdy záporné --> cyklus skončí
v něm se v každé iteraci i blíží po 1 k n
konvergence - dk.
vytvoříme hodnotící fci δ(n, i) = n-i+1 >= 0
ověření: END < BEGINING
vezmeme cestu cyklu a ukážeme, že při každém průchodu hodnota klesá
platí --> je konvergentní
vše záleží na invariantu (špatná volba - nic nedokážu)
(použ. rekurze) pomocí indukce
specifikace
vstupní a výstupní podmínky
2.. parciální korektnost
pro každý def. vstup správný výsledek
totální korektnost
parc. kor + konv.
konvergence
hledáme variant
rekurze - na první pohled
na každém správném vstupu skončí
obecně
indukcí (funkcioální paradigma/rekurze)
invariant cyklu (imperativní par. bez rekurze)
Asymptotická složitost
pokud máme 2 alg. o slož. O(n) a O(2n) - druhý pustím na 2* rychl. stroji
pokud nejsou ve stejné třídě složitosti, tak nám na srovnání výkonu nepomůže nic (2
tolik dat bude 4
toli času,...)
zařazuje alg. do kategorií - tříd složitosti
lineární, exponenciální, log,...
O-notace
porovnávání efektivity, nezávisle na impl. a platformě
př.
funkce porovnáváme podle rozhodujících členů
Zdůvodnění korektnosti a složitosti základních algoritmů
Řadící algoritmy
př.: counting sort (počítá výskytyú, radix sort (fixní délka řetězců, dle znaků)
ale obv. ne pro všeobecné použití
časová složitost - nejlepší ty, které neporovnávají (O(n))
všeobecné použití: třída O(nlogn)
vybíráme dle
implementační složitost
vhodnost pro datovou strukturu
výkon
stabilita
př.: heapsort, quicksort, mergesort - porovnávají
slouží k setřízení prvků vstupního souboru dle daného pravidla
malá velikost dat - O(n^2) - bubble sort, insertion sort, selection sort - jednoduchá impl.
stabilita
přirozenost
analýza
merge sort
přirozený a stabilní
Θ(nlogn)
princip - slévání 2 seřazených polí pomocí dalšího pole o velikosti n
postup
platí tranzitivita
konvergence - velikost polí
quicksort
v praxi rychlejší než hs a ms, ne real-time
postup
očekávajá složitost (nezaručená): O(nlogn), nejhorší: O(n^2) - špatný pivot
volba pivota
medián první, prostřední a poslední
náhodný
první
ideálně: pole na poloviny O(nlogn)
špatný pivot
NEpřirozený a NEstabilní, velmi rychlý
heapsort
O(nlogn)
porovnávání - jeden z nejefektivnějších
NEpřirozený a NEstabilní
postup
složitost
v každém kroku vybereme levého následníka (log n)
toto pro každý prvek - n-krát
O(nlogn) zaručená --> real-time systémy
--> O(nlogn)
selection sort
O(n^2)
pole řadíme od největšího k nejmenšímu
NEpřirozený a NEstabilní
insertion sort
O(n^2)
vylepšení: shell sort (není stabilní)
přirozený a stabilní
první prvek - seřazený, další - procházíme setřízené a zařadíme
složitost
pro každý z n prvků procházíme zpětně n-1 prvků
téměř seřazené pole - blíží se k O(n) (pouze prochází)
--> často doplněk k RaP
efektivní pro malé vstupy (n<=10)
counting sort
NEpřirozený a stabilní
Θ(n)
pracuje na bázi výčtu výskytů hodnot, ne porovnání
bubble sort
O(n^2)
probublává nejmenší prvek až nakonec - pokud najde po cestě menší, bere ten
přirozený a stabilní
složitost
n-1 cyklů
(n-1)+(n-2)+...+1 (1 je triviálně seřazen)
bereme největší člen - n^2
radix sort
použití: řazení řetězců stejné délky
nad každým znakem od konce řetězce zavolá stabilní řadící alg
Θ(n)
po n-tém průchodu - seřazené dle všech pozic znaků
NEpřirozený a NEstabilní
složitost
O(znaky Alg(n))
vyhledávací algoritmy
Binární vyhledávání
zjišťuje pozici prvku v seřazeném poli
rozpůlí pole - přesune se na správnou stranu
O(logn)
princip
půlení intervalu
složitost půlení int - logn kroků
lineární vyhledávání
triviální, když nevím o datech nic
jeden po druhém
O(n)
interpolační vyhledávání
O(log log(n))
vylepšení binárního
když je pole seřazené + rovnoměrně hodnoty
implementace
teorie
algoritmus
program