7 (1879)

Q Częściowa oraz pełna 'poprawność algorytmu. Jak dowodzi się dochodzenie obliczeń'^ \ do punktu końcowego (własność stopu)? .

t    -p>Tn^ocx>    . Qfcjl0rr7QjL

Poprawność częściowa jest to udowodnienie poprawności algorytmu według reguł do wodzenia/*'* Poprawność pełna jest to poprawność częściowa algorytmu oraz dowód na skońc2oność wszystkich pętJi algorytmów. Dowód na skończoność algorytmu: a) e>0 w* ciele pętli

bj {e=e^= ... }P4e<eo) po przejściu jednorazowym pętli e musi się zmieniać c) e^O po wyjściu z pętli    .

e - dowolne wyrażenie zazwyczaj zależy od niego wyjście z danej pętli.

Na drugie pytanie niestety nie znam odpowiedzi !1!

+ poktLtac do~6J cito. p<^4<:

.. «n f

°odać definicje pojęć: rozmiar danych, działanie dominujące, złożoność pamięciowa algorytmu. Wymienić typcry/e funkcje określające złożoności obliczeniowe algorytmów. Po co wyznacza się złożoność obliczeń }ową algorytmu

rozmiar danych : jest to ilość danych wejściowych , określa dokładnie ilość pamięci potrzebnej na ich lokację    zjl

b) działanie dominując* obliczeniowej ; jest to

; jest to działanie

operacja zajmująca najwięcej 'umowne przyjmowane przez

•ra>

czasu (działań) nas ; działanie

dla złożoności dzięki któremu

porównujemy różne algorytmy (ich złożoność oblic2e^ow^^^_pc^ j z) złożoność pamięciowa algorytmu : jest to funkcjafiribra uRieśtajak

zrmema się

-poeegg^wyykcmywiint-a algofyrmćw w zależności od rozmiaru danych wejściowych. Jest to funkcja jednej zmiennej. Jest to funkcja niemalejąca.    3 , _K ^

Typowe funkcje określające złożoność obliczeniową algorytmu:    ^    ^ ^3

n, log(n), n log\n), n dla m= {2,3,...} , n! ,

Ol

Ov€ąZ<^tuS>

to samo mniejsza.

Bierzemy pod uwagę zło2oność obliczeniową średnią, ponieważ złożoność pesymistyczna bardzo rzadko występuje pod czas wykonywania algorylinów. Podczas dobom algorytmu bierzemy również pod uwagę złożoność pamięciową] wybieramy rozwiązanie najbardziej nam odpowiadające.

(iQ^)cg rozumiesz przez: zrożoność pesymistyczną algorytmu,

złożoność średnia

algorytmu? Udowodnij, że:

Vf(n) = a„n^m i ... 1 ćijn t u₀ = O(rT) dla n>0. ^w(n) <=ia_Tri!n^CI - ;a-_I1.||n^ro'^: - ja,|n + Jaoi =

= (jaj -*• ia^.jj/n + fa^^t/n² + ...+ |ao}/n“)*n^E <=

^<= (W - |Łji-iI + la™-:! - ... + Ja,h- M)*n^a =

= c‘nⁿ=> W(n)= O (n^m)

fżOs rr>i Ci*

F L"r\U

l<2 nr}

CJ o rro c. rn I O/ru ionOLjCh    | •

CftiA) ó\khno WU) aAo\ó<

jf c Q jź. b'd< donyh D /TĆArfr-)] d nÓOi Jfc²²

zto ro <u p.

cno Z or>S 1psjr C rm

p^Ut^ł ^riei, ’

dLD dou(Lj dl

1^1 ^L    o i?

f ^ru 'O.TŁU7 K^rt!^} 1    .... .^v—'    1

Złożoność pesymistyczna algorytmu jest to maksymalny rząd uośct ( maksymalna ilosc ) wykonanycn

operacji dominujących dla danego algorytmu podczas jednego ,peinego przejścia algorytmu. Tpc^n)^ max (T(d): d należy' do D_n }

D_n- zestaw danvch testowych.    o

Złożoność średnia cil^urylmy:

TfrOi)²* suma dla wszystkich d należących do D_c z( p(d)T(d)) p(d)- prawdopodobieństwo wystąpienia zestawu danych „d*^ł T(u)- złożoność obliczeniowa dla danego zestawu danych wejściowych.

Określa złożoność obliczeniową (pamięciową} potrzebną do porównania różnych algorytmów'.

I {•    ” yŚ.. -p_ |

7