Jadwiga Chudzicka

1

Jadwiga Chudzicka

2

KLASYFIKACJA ALGORYTMÓW



algorytmy numeryczne, operujące na liczbach (np.

algorytm Euklidesa),



algorytmy nienumeryczne, operujące na obiektach

nieliczbowych (np. sortowanie dokumentów).

Inny podział to:



algorytmy sekwencyjne (kolejność czynności jest

jednoznacznie określona),



algorytmy niesekwencyjne (równoległe, w których

współbieżne następstwo miedzy pewnymi operacjami nie

jest ściśle określone).

Jadwiga Chudzicka

3

Metody projektowania

algorytmów



Programowanie strukturalne jest techniką

programowania, w której problem jest

dzielony na mniejsze bloki (moduły),

odpowiedzialne za realizację

poszczególnych jego części. Dotyczy to

głównie dużych projektów, które są zbyt

skomplikowane do opisania w całości. W

programach komputerowych modułami są

najczęściej procedury i/lub funkcje. Możliwe

są przy tym dwa sposoby postępowania:

Jadwiga Chudzicka

4

W pierwszej metodzie zwanej programowaniem

zstępującym (ang. top-down programming),

programista powinien uświadomić sobie, co jest do

zrobienia i starać się wyodrębnić z całości

problemu mniejsze zadania. Może je traktować

tymczasowo jako „czarne skrzynki” o określonych

właściwościach. To samo należy zrobić z „czarnymi

skrzynkami”, tzn. próbować wyodrębnić w nich

jeszcze bardziej szczegółowe zadania. Proces ten

powinien być kontynuowany tak długo, aż osiągnie

się poziom szczegółowości implikowany przez

stosowany język.

Jadwiga Chudzicka

5

W drugiej metodzie zwanej programowaniem

wstępującym (ang. bottom-up programming),

najpierw należy zaprogramować elementarne

struktury, a następnie złożyć z nich program w

logiczną całość; jest to metoda odwrotna do wyżej

opisanej.

Jadwiga Chudzicka

6

Do pisania programów z wykorzystaniem

techniki programowania strukturalnego

nadają się zwłaszcza strukturalne języki

programowania, takie jak:

Pascal

,

C

,

Modula-2

.

Programowanie strukturalne ułatwia

projektowanie, testowanie a także

otrzymanie kodu programu.

Jadwiga Chudzicka

7



Programowanie obiektowe – rodzaj

programowania, w którym dane i wykonywane na

nich operacje są połączone. Ten formalny zabieg

umożliwia szybsze pisanie większych programów

przez „składanie ich” ze wzajemnie powiązanych

obiektów, które odpowiadają za daną funkcję

programu (np. przygotowanie danych, wykonanie

obliczeń, zaprezentowanie wyników). Programując

obiektowo, należy najpierw „wykryć” wszystkie

obiekty w rozważanym problemie. Terminem

obiekt określamy dane i algorytmy na nich

operujące. Dane w językach programowania

nazywane są polami obiektu, natomiast algorytmy

– metodami.

Jadwiga Chudzicka

8

Do najpopularniejszych języków

programowania obiektowego

należą

C++

,

Java

,

Effel

.

Jadwiga Chudzicka

9



programowanie dynamiczne – problem

dzielony jest na kilka zagadnień, ważność każdego

z nich jest oceniana i po pewnym wnioskowaniu

wyniki analizy niektórych prostszych zagadnień

wykorzystuje się do rozwiązania głównego

problemu,



metoda zachłanna – nie analizujemy

podproblemów dokładnie, tylko wybieramy

najbardziej obiecującą w tym momencie drogę

rozwiązania,



programowanie liniowe – oceniamy

rozwiązanie problemu przez pewną funkcję jakości

i szukamy jej minimum,

Jadwiga Chudzicka

10



poszukiwanie i wyliczanie – przeszukujemy

zbiór danych aż do odnalezienia rozwiązania,



probabilistyczne rozwiązanie – algorytm

działa poprawnie z bardzo wysokim

prawdopodobieństwem, ale wynik nie jest

pewny,



heurystyka – człowiek na podstawie swojego

doświadczenia tworzy algorytm, który działa w

najbardziej prawdopodobnych warunkach

(rozwiązanie zawsze jest przybliżone).

Jadwiga Chudzicka

11

ZŁOŻONOŚĆ OBLICZENIOWA

ALGORYTMÓW

Jadwiga Chudzicka

12

Jeżeli dany algorytm da się wykonać na maszynie o

dostępnej mocy obliczeniowej i określonej pojemności

pamięci oraz w akceptowalnym czasie, to mówi się że

jest

obliczalny

.

Jeżeli algorytm dla coraz większego zbioru danych

powoduje wzrost czasu obliczeń szybciej niż to

wynikałoby z funkcji wielomianowej, to mówi się że

nie jest obliczalny

.

Wiąże się z tym pojęcie

złożoności obliczeniowej

(pojęcie to wprowadzili J. Hartmanis i R. E. Stearns):

Jadwiga Chudzicka

13

Złożoność obliczeniowa algorytmu –

ilość zasobów komputera jakiej potrzebuje

dany algorytm.

Najczęściej przez zasób rozumie się czas

oraz pamięć – dlatego też używa się

określeń

złożoność czasowa

i

złożoność

pamięciowa

.

ZŁOŻONOŚĆ CZASOWA I

ZŁOŻONOŚĆ PAMIĘCIOWA

Jadwiga Chudzicka

14

Za jednostkę złożoności pamięciowej przyjmuje

się pojedyncze słowo maszyny (np. bajt).

W przypadku złożoności czasowej nie można

podać bezpośrednio jednostki czasu, np.

milisekundy, ponieważ nie wiadomo na jakiej

maszynie dany algorytm będzie wykonywany.

Dlatego też wyróżnia się - charakterystyczną dla

algorytmu - operację dominującą. Liczba wykonań

tej operacji jest proporcjonalna do wykonań

wszystkich operacji.

Jadwiga Chudzicka

15

Rodzaje złożoności czasowej



złożoność pesymistyczna określa

złożoność w "najgorszym" przypadku.

Jeśli D oznacza zbiór wszystkich

możliwych danych wejściowych, d jeden z

elementów tego zbioru, a f funkcję, która

dla danego d zwraca liczbę operacji, to

złożoność pesymistyczna jest

zdefiniowana jako:

sup{f(d): d

∈

D}

Jadwiga Chudzicka

16



złożoność oczekiwana określa złożoność

średnią czyli

wartość oczekiwaną

zmiennej

losowej f. Jeśli wszystkie dane są

jednakowo prawdopodobne (z

prawdopodobieństwem niezerowym) wtedy

wyraża się ona wzorem:

D

d

f

D

d

∑

∈

)

(

Terminologia

Jadwiga Chudzicka

17

Pojęcie wartości oczekiwanej

W rachunku prawdopodobieństwa wartość

oczekiwana (inaczej wartość przeciętna,

wartość średnia, nadzieja

matematyczna) zmiennej losowej

(dyskretnej) jest sumą iloczynów wartości tej

zmiennej losowej przez prawdopodobieństwa,

z jakimi te wartości są przyjmowane.

C.D.

Jadwiga Chudzicka

18

Pojęcie wartości oczekiwanej c.d.

Formalnie, jeżeli dyskretna zmienna losowa X

przyjmuje wartości x1, x2, ..., z

prawdopodobieństwami odpowiednio: p1, p2, ...,

wówczas wartość oczekiwaną E[X] zmiennej

losowej X definiujemy jako:

∑

∞

=

=

1

]

[

i

i

i

p

x

X

E

Jadwiga Chudzicka

19

Wykorzystywanie złożoności obliczeniowej do

badania jakości algorytmu nie zawsze jest

zalecane, ponieważ operacja dominująca na

jednym komputerze może wykonywać się

bezproblemowo i szybko, na innym zaś musi

być zastąpiona szeregiem instrukcji.

Dlatego też częściej stosuje się złożoność

asymptotyczną, która mówi o tym jak

złożoność kształtuje się dla bardzo dużych,

granicznych rozmiarów danych wejściowych.

Jadwiga Chudzicka

20

Złożoność asymptotyczna

Do opisu złożoności asymptotycznej stosuje się

trzy notacje:

1. Notacja

O

(„omikron” lub „Wielkie O”)

2. Notacja Ω („Wielkie Omega”)

3. Notacja Θ („Teta”)
Przedstawimy opis matematyczny tych notacji,

przyjmując, że dane są funkcje f oraz g, których

dziedziną

jest zbiór liczb naturalnych, natomiast

przeciwdziedziną

zbiór liczb rzeczywistych

dodatnich.

Wyjaśnienie terminów

Jadwiga Chudzicka

21

Definicja funkcji

Funkcja matematyczna przekształcająca zbiór X

w zbiór Y to odwzorowanie (przyporządkowanie),

które każdemu elementowi zbioru X przypisuje

dokładnie jeden element zbioru Y.

Zbiór X nazywamy dziedziną funkcji, jego

elementy argumentami, zaś zbiór Y -

przeciwdziedziną funkcji.

Element

y

zbioru Y, który jest przypisany danemu

elementowi x ze zbioru X nazywamy obrazem x,

albo wartością funkcji dla argumentu x.

Jadwiga Chudzicka

22

Na kolejnych slajdach umieszczone są definicje

poszczególnych trzech notacji.

Służą one do opisu czasu działania algorytmu.

Mówi się wówczas o tzw. rzędzie wielkości

funkcji.

Jadwiga Chudzicka

23

Ad 1) Notacja

O

("omikron” lub

"Wielkie O")

Notacja O określa asymptotyczną granicę górną,

tzn. dla danej funkcji g(n) mówimy, że f jest co

najwyżej rzędu g, gdy istnieją takie stałe n

0

> 0

oraz c > 0, że:

)

(

)

(

0

0

n

cg

n

f

n

n

≤

≤

∀

≥

Ciąg dalszy

Jadwiga Chudzicka

24

Chociaż O(g(n)) jest zbiorem funkcji to

wygodnie jest stosować zapis f(n) =

O(g(n)), gdy chcemy wyrazić, że funkcja

f(n) jest elementem zbioru O(g(n)).

Określenia

"złożoność co najwyżej O(f(n))"

i

"złożoność O(f(n))"

są matematycznie

równoważne.

Jadwiga Chudzicka

25

Graficzny przykład notacji O

c

⋅

g(n)

n

n

0

f(n)

f(n) = O(g(n))

n

0

f(n)

f(n) = O(g(n))

Objaśnienia

Jadwiga Chudzicka

26

Notacja

O

daje górne ograniczenie

funkcji z dokładnością do stałego

czynnika. Piszemy

f(n) = O(g(n))

, jeśli

istnieją dodatnie stałe

n

0

i

c

, takie że na

prawo od

n

0

wartość

f(n)

jest nie

większa niż

cg(n

).

Wartość

n

0

jest minimalną możliwą

wartością; każda większa wartość jest

również dobra.

Jadwiga Chudzicka

27

Ad 2) Notacja Ω ("Wielkie Omega")

Notacja Ω

określa asymptotyczną granicę dolną, tzn.

dla danej funkcji g(n) mówimy, że f jest co najmniej

rzędu g, gdy istnieją takie stałe n

0

> 0 oraz c > 0, że:

)

(

)

(

0

0

n

f

n

cg

n

n

≤

≤

∀

≥

Stosujemy zapis f(n) = Ω(g(n)), gdy funkcja f(n)

jest elementem zbioru Ω(g(n)).

Jadwiga Chudzicka

28

Graficzny przykład notacji Ω:

c

⋅

g(n)

n

n

0

f(n)

f(n) = Ω(g(n))

c

⋅

g(n)

n

n

0

f(n)

f(n) = Ω(g(n))

Objaśnienia

Jadwiga Chudzicka

29

Notacja

Ω

daje dolne ograniczenie funkcji z

dokładnością do stałego czynnika. Piszemy

f(n)

= Ω(g(n))

, jeśli istnieją dodatnie stałe

n

0

i

c

,

takie że na prawo od

n

0

wartość

f(n)

jest nie

mniejsza niż

cg(n

).

Wartość

n

0

jest minimalną możliwą wartością;

każda większa wartość jest również dobra.

Jadwiga Chudzicka

30

Ad 3) Notacja Θ ("Teta")

Notacja Θ ogranicza funkcję asymptotycznie od góry

i od dołu tzn. dla danej funkcji g(n) mówimy, że f

jest dokładnie rzędu g, gdy istnieją takie stałe n

0

> 0 oraz c

1

> 0 i c

2

> 0, że:

)

(

)

(

)

(

0

2

1

0

n

g

c

n

f

n

g

c

n

n

≤

≤

≤

∀

≥

dalej

Jadwiga Chudzicka

31

Stosujemy zapis f(n) = Θ(g(n)), gdy funkcja

f(n) jest elementem zbioru Θ(g(n)).

Można stwierdzić, że f(n) = Θ(g(n)), gdy f(n)

jest jednocześnie rzędu O(g(n)) i Ω(g(n)).

Wartości wymienionych w tych notacjach stałych:

c, c1 i c2 wpływają znacznie na efektywność

algorytmu.

Jadwiga Chudzicka

32

c

1

⋅

g(n)

n

n

0

f(n)

f(n) = Θ(g(n))

c

2

⋅

g(n)

c

1

⋅

g(n)

n

n

0

f(n)

f(n) = Θ(g(n))

c

2

⋅

g(n)

Graficzny przykład notacji Θ

Objaśnienia

Jadwiga Chudzicka

33

Za pomocą notacji

Θ

szacuje się funkcję

z dokładnością do stałego czynnika.

Piszemy

f(n) = Θ(g(n))

, jeśli istnieją

dodatnie stałe

n

0

,

c

1

i c

2

, takie że na

prawo od

n

0

wartość

f(n)

leży zawsze

między

c

1

g(n

) a

c

2

g(n

) .

Wartość

n

0

jest minimalną możliwą

wartością; każda większa wartość jest

również dobra.

Jadwiga Chudzicka

34

Posługując się tymi notacjami można określać

czas działania algorytmów.

Jeśli np. mówimy, że czas działania algorytmu

wynosi Ω(g(n)), należy przez to rozumieć, że

niezależnie od konkretnych danych

wejściowych o rozmiarze n (dla dostatecznie

dużych n) czas działania algorytmu dla tych

danych wynosi co najmniej g(n), pomnożone

przez pewną stałą.

Jadwiga Chudzicka

35

Algorytmy mają zwykle złożoność czasową

proporcjonalną do funkcji.

Najczęściej spotykane rzędy złożoności algorytmu to:



1 (stała);



log

2

n

(logarytmiczna);



n (liniowa);



nlog

2

n (liniowo-

logarytmiczna);



n

2

(kwadratowa);



n

3

(sześcienna);



n

c

(wielomianowa);



c

n

(wykładnicza);



n! (wykładnicza,

ponieważ n!>2

n

już

od n=4