1

OBLICZENIA RÓWNOLEGLE

Temat 1:

Algorytm, zlozonosc - przypomnienie

Prowadz acy:

dr inz. Zbigniew TARAPATA

pok.225A, tel.: 83-94-13

e-mail:

[e-mail]

[e-mail]

http://

tarapata.

tarapata.

strefa

strefa

.pl

.pl

/

/

p_obliczenia_rownolegle

p_obliczenia_rownolegle

/

/

2

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

PLAN REFERATU

n

n

Z

Z

l

l

o

o

z

z

ono

ono

sc

sc

algorytmu

algorytmu

a zlozonosc

problemu

problemu

(zadania);

n

n

Optymalno

Optymalno

sc

sc

algorytmu ze wzgledu na

dok

dok

l

l

adno

adno

sc

sc

,

a optymalnosc ze wzgledu na

z

z

l

l

o

o

z

z

ono

ono

sc

sc

;

n

Zlozonosc

pesymistyczna

pesymistyczna

, zlozonosc

oczekiwana

oczekiwana

,

wra

wra

z

z

liwo

liwo

sc

sc

algorytmów;

n

n

Problem decyzyjny

Problem decyzyjny

a

optymalizacyjny;

optymalizacyjny;

n

n

Klasy z

Klasy z

l

l

o

o

z

z

ono

ono

s

s

ci

ci

obliczeniowej problemów;

n

n

Dowodzenie przynale

Dowodzenie przynale

z

z

no

no

s

s

ci

ci

problemu

do klasy z

do klasy z

l

l

o

o

z

z

ono

ono

s

s

ci

ci

;

n

n

Metody badania

Metody badania

zlozonosci, dokladno sci algorytmów;

2

3

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

ALGORYTM - przypomnienie podstawowych pojec

n

n

Algorytmika

Algorytmika jest dziedzina wiedzy zajmujaca sie badaniem

algorytm

algorytm

ó

ó

w

w

;

n

W informatyce jest ona nieodlacznie zwiazana z algorytmami
przetwarzania

struktur

danych

danych

;

n

Potocznie

algorytm

algorytm jest rozumiany jako pewien przepis na

wykonanie jakiegos zestawu czynno sci, prowadzacych do
osi agniecia oczekiwanego i z góry okreslonego celu;

n

Mówi si e równiez, ze:

n

-

algorytm

jest pewna scisle okreslona procedura obliczeniowa,

która dla zestawu wlasciwych danych wejsciowych wytwarza
zadane dane wyjsciowe;

n

-

algorytm

jest to zbiór regul postepowania umozliwiajacych

rozwiazanie okreslonego zadania w skonczonej liczbie kroków
i w skonczonym czasie.

Termin algorytm wywodzi si

Termin algorytm wywodzi si

e

e

od zlatynizowanej formy

od zlatynizowanej formy

(

(

Algorismus

Algorismus

,

,

Algorithmus

Algorithmus

) nazwiska matematyka arabskiego

) nazwiska matematyka arabskiego

z

z

IX w.,

IX w.,

Al

Al

-

-

Chuwarizmiego

Chuwarizmiego

.

.

4

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

ZLOZONOSC ALGORYTMU

A ZLOZONOSC PROBLEMU (ZADANIA)

n

n

Z

Z

l

l

o

o

z

z

ono

ono

sc

sc

algorytmu

algorytmu

– liczba kroków algorytmu

(czas) potrzebna na rozwiazanie danego
problemu dla najgorszego przypadku danych
ustalonego rozmiaru;

n

Zlozonosc

problemu (zadania)

problemu (zadania)

- zlozonosc

najlepszego algorytmu rozwiazujacego ten
problem;

3

5

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

OPTYMALNOSC W SENSIE ZLOZONOSCI,

OPTYMALNOSC W SENSIE DOKLADNOSCI

n

Algorytm nazywamy

optymalnym ze wzgl

optymalnym ze wzgl

e

e

du na z

du na z

l

l

o

o

z

z

ono

ono

sc

sc

jezeli nie istnieje inny algorytm (dla tego samego problemu)
o zlozonosci lepszej;

n

Algorytm nazywamy

optymalnym ze wzgl

optymalnym ze wzgl

e

e

du na dok

du na dok

l

l

adno

adno

sc

sc

(dla danego problemu, przy posiadanej informacji) jezeli blad
tego algorytmu jest najmniejszy sposród bledów wszystkich
algorytmów rozwiazujacych dany problem;

n

Algorytm A nazywamy

ε

ε

-

-

aproksymacyjnym

aproksymacyjnym

(

ε

ε-

przybli

przybli

z

z

onym

onym

)

(

ε

ε

>1

>1

) jezeli zachodzi nastepujaca zaleznosc:

gdzie S(A(Z)) – wartosc rozwiazania problemu Z przez algorytm

A, S(Z) – wartosc optymalnego rozwiazania problemu Z;

UWAGA!
Optymalnosc algorytmu ze wzgledu na dokladnosc oraz zlozonosc

nie musi sie pokrywac !!!

( ( ))

( )

S A Z

S Z

ε

≤ ⋅

6

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

PESYMISTYCZNA ZLOZONOSC

OBLICZENIOWA

Niech:

D

n

- zbiór danych rozmiaru n dla rozwazanego

problemu;

- liczba operacji podstawowych wykonanych

przez algorytm na danych I

∈D

n

;

Pesymistyczna

zlozonosc

obliczeniowa

W(n)

definiowana jest jako :

( )

I

t

( )

( )

{

}

n

D

I

I

t

n

W

∈

=

:

max

4

7

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

OCZEKIWANA ZLOZONOSC

OBLICZENIOWA

Niech:

-prawdopodobienstwo wystepowania danych I

∈D

n

;

- zmienna losowa o wartosciach

i rozkladzie ;

Oczekiwana zlozonosc obliczeniowa

A(n) definiowana

jest jako :

( )

I

p

n

X

( )

I

t

( )

I

p

( )

( ) ( )

)

(

n

D

I

X

E

I

t

I

p

n

A

n

=

=

∑

∈

8

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

WRAZLIWOSC PESYMISTYCZNA

I OCZEKIWANA ALGORYTMÓW

Wrazliwosc pesymistyczna

:

( )

( ) ( )

{

}

n

D

I

I

I

t

I

t

n

∈

−

=

∆

2

1

2

1

,

:

max

Wrazliwosc oczekiwana

:

( )

( )

( ) ( ) ( )

(

)

2

E

∑

∈

−

⋅

=

=

n

D

I

n

n

X

I

t

I

p

X

Var

n

δ

5

9

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

DEFINICJE RZEDÓW ZLOZONOSCI

OBLICZENIOWEJ

Niech R* =R

+

∪{0}.

Mówimy, ze funkcja

f(x):R*

→R* jest rzedu

O

O

(

(

g(x)

g(x)

)

)

(g(x):R*

→R*), jesli istnieje taka stala c>0 oraz x

0

∈R*,

ze dla kazdego x

≥x

0

zachodzi f(x)

≤c⋅g(x) (f nie rosnie

szybciej niz g).

x

y

x

0

f(x)

cg(x)

f(x)=O(g(x))

10

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

DEFINICJE RZEDÓW ZLOZONOSCI

OBLICZENIOWEJ, c.d.

Niech R* =R

+

∪{0}.

Mówimy, ze

funkcja f(x):R*

→R* jest rzedu

Ω

Ω

(

(

g(x)

g(x)

)

)

(g(x):R*

→R*), jesli istnieje taka stala c>0 oraz x

0

∈R*,

ze dla kazdego x

≥x

0

zachodzi g(x)

≤c⋅f(x) (f nie rosnie

wolniej niz g).

x

y

x

0

cf(x)

g(x)

f

f

(x)=

(x)=

Ω

Ω

(

(

g(x)

g(x)

)

)

6

11

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

Niech R* =R

+

∪{0}.

Mówimy, ze

funkcja f(x):R*

→R* jest rzedu

Θ

Θ

(

(

g(x)

g(x)

)

)

(g(x):R*

→R*), jesli istnieja takie stale c

1

, c

2

>0 oraz

x

0

∈R*,

ze dla kazdego

x

≥x

0

zachodzi

c

1

g(x)

≤f(x)≤c

2

g(x) (f rosnie tak samo jak g).

x

y

x

0

f(x)

c

1

g(x)

c

2

g(x)

f

f

(x)=

(x)=

Θ

Θ

(

(

g(x)

g(x)

)

)

DEFINICJE RZEDÓW ZLOZONOSCI

OBLICZENIOWEJ, c.d.

12

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

KLASY I TYPY FUNKCJI ZLOZONOSCI

OBLICZENIOWEJ

Klasa funkcji

Typ funkcji

Przyklady

stala

(

)

n

e

n

2

sin

−

Θ

,

( )

n

/

1

Θ

subliniowa

polilogarytmiczna

(

)

n

log

log

Θ

,

(

)

n

2

log

Θ

liniowa

( )

n

Θ

,

(

)

(

)

n

n

n

/

1

1

+

Θ

quasi-liniowa

(

)

n

nlog

Θ

,

(

)

n

n

log

log

Θ

wielomianowa

kwadratowa

( )

2

n

Θ

,





















Θ

2

n

superwielomianowa

( )

n

n

lg

Θ

,

( )

n

e

Θ

wykladnicza

( )

n

2

Θ

,

( )

n

n 3

2

Θ

niewielomianowa

superwykladnicza

( )

n

n

2

Θ

,

( )

n

n

Θ

7

13

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

Wplyw wzrostu predkosci komputera na

maksymalny rozmiar zagadnienia, które

mozna rozwiazac w jednostce czasu

Algorytm

Maksymalny rozmiar zagadnienia

Symbol

Zlozonosc

przed wzrostem

predkosci

po 100-krotnym

wzroscie predkosci

5

A

( )

n

Θ

N

5

5

100N

4

A

( )

2

n

Θ

N

4

10 N

4

3

A

( )

3

n

Θ

N

3

4.64 N

3

2

A

( )

5

n

Θ

N

2

3.5 N

2

1

A

( )

n

2

Θ

N

1

6.64+N

1

0

A

(

)

n

n log

Θ

N

0

0

100N dla

1

0

>>

N

h

N

1

2

4

=

,

( )

100

1

2

4

4

⋅

=

h

N

c

⇒

10

100

4

=

=

c

h

N

1

2

1

=

,

100

1

2

1

1

⋅

=

+

h

c

N

⇒

100

2

1

=

c

⇒

c

1

=log

2

100=6.64

14

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

Zwiazek pomiedzy rz edem zlozonosci, stala

proporcjonalnosci, rozmiarem danych i

rzeczywistym czasem obliczen na minikomputerze
i superkomputerze

n

Cray-1

3

3n

[ns]

PENTIUM IV 1.6 GHz

195000n [ns]

10

3 µs

300 µs

100

3 ms

3 ms

1 000

3 s

30 ms

10 000

49 min.

300 ms

1000 000

95 lat

3 s

Mimo ze algorytm szescienny „wystartowal” z wiekszym impetem,

drugi algorytm (liniowy), majacy zlozonosc o 2 rzedy nizsza

(O(n) w stosunku do O(n

3

)),

„dogonil go” i okazal sie szybszy dla

100

>

n

.

8

15

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

SZACOWANIE ZLOZONOSCI

OBLICZENIOWEJ

Metody szacowania zlozonosci algorytmów

Aby oszacowac zlozonosc algorytmu zlicza sie tzw. operacje
podstawowe dla badanego problemu lub klasy rozwazanych
algorytmów, tj. takie, które sa najczesciej wykonywane
(ignorujac pozostale operacje pomocnicze, takie jak
instrukcje inicjalizacji, instrukcje organizacji petli itp.).

Tabela 1 Przyklady operacji podstawowych dla typowych
problemów obliczeniowych

Lp.

Problem

Operacja

1.

2.

3.

4.

Znalezienie x na liscie
nazwisk.

Mnozenie dwóch macierzy
liczb rzeczywistych.


Porzadkowanie liczb.


Wyznaczanie drogi
najkrótszej w grafie zadanym
w postaci listy sasiadów.

Porównanie x z pozycja na
liscie.

Mnozenie dwóch macierzy
liczb typu real (lub mnozenie
i dodawanie).

Porównanie dwóch liczb
(lub porównanie i zamiana).

Operacja na wskazniku listy.

Zalety zliczania operacji

Zalety zliczania operacji

podstawowych:

podstawowych:

-

Uniezale znienie sie od
rodzaju i liczby
procesorów ;

-

Mozliwosc przewidywania
zachowania sie algorytmu
dla róznych danych;

-

Swoboda wyboru operacji
podstawowej;

16

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

SZACOWANIE ZLOZONOSCI OBLICZENIOWEJ

Przyk

Przyk

l

l

ady praktyczne mierzenia z

ady praktyczne mierzenia z

l

l

o

o

z

z

ono

ono

s

s

ci obliczeniowej

ci obliczeniowej

–

–

Przyk

Przyk

l

l

ad 4

ad 4

Przyklad 4: Prosta petla

for (i=sum=0; i<n; i++) sum+=a[i];

Powyzsza petla powtarza sie n razy, podczas kaz dego jej przebiegu
realizuje dwa przypisania: aktualizujace zmienna „sum” i zmiane wartosci
zmiennej „i”. Mamy zatem 2 n przypisan podczas calego wykonania petli;
jej

asymptotyczna z

asymptotyczna z

l

l

o

o

z

z

ono

ono

sc

sc

wynosi O(

wynosi O(

n

n

).

).

Czy mo

Czy mo

z

z

emy zapisa

emy zapisa

c

c

, r

, r

ó

ó

wnie

wnie

z

z

Ω

Ω

(

(

n

n

) ?

) ?

TAK

Zatem mozemy zapisac

Θ(n).

9

17

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

SZACOWANIE ZLOZONOSCI OBLICZENIOWEJ

Przyk

Przyk

l

l

ady praktyczne mierzenia z

ady praktyczne mierzenia z

l

l

o

o

z

z

ono

ono

s

s

ci obliczeniowej

ci obliczeniowej

–

–

Przyk

Przyk

l

l

ad 5

ad 5

Przyklad 5: Petla zagniez dzona

for (i=0; i<n; i++) {

for (j=1, sum=a[0]; j<=i; j++)

sum+=a[j]; }

Na samym poczatku zmiennej „i” nadawana jest wartosc poczatkowa. Petla
zewnetrzna powtarza sie n razy, a w kazdej jej iteracji wykonuje sie wewnetrzna
petla oraz instrukcja przypisania wartosci zmiennym „i”, „ j”, „ sum”. Petla
wewnetrzna wykonuje sie „i” razy dla kazdego i e {1,...,n-1}, a na kazda iteracje
przypadaja dwa przypisania:jedno dla „sum”, jedno dla „j”. Mamy zatem

1 + 3n + 2(1+2+...+n-1) = 1 + 3n + n (n-1) = O(n) + O(n

2

) = O(n

2

)

przypisan wykonywanych w calym programie. Jej

asymptotyczna z

asymptotyczna z

l

l

o

o

z

z

ono

ono

sc

sc

wynosi

wynosi

O(n

O(n

2

2

).

).

Czy mo

Czy mo

z

z

emy zapisa

emy zapisa

c

c

r

r

ó

ó

wnie

wnie

z

z

Ω

Ω

(

(

n

n

2

2

),

),

Θ

Θ

(

(

n

n

2

2

)

)

?

?

P

P

e

e

tle zagnie

tle zagnie

z

z

d

d

z

z

one maj

one maj

a

a

zwykle wi

zwykle wi

e

e

ksz

ksz

a

a

z

z

l

l

o

o

z

z

ono

ono

sc

sc

ni

ni

z

z

pojedyncze, jednak nie musi

pojedyncze, jednak nie musi

tak by

tak by

c

c

zawsze.

zawsze.

TAK

18

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

SZACOWANIE ZLOZONOSCI OBLICZENIOWEJ

Przyk

Przyk

l

l

ady praktyczne mierzenia z

ady praktyczne mierzenia z

l

l

o

o

z

z

ono

ono

s

s

ci obliczeniowej

ci obliczeniowej

–

–

Przyk

Przyk

l

l

ad 6

ad 6

Analiza tych dwóch przypadk ów byla stosunkowo prosta poniewaz liczba
iteracji nie zalezala od wartosci elementów tablicy.
Wyznaczenie zloz onosci asymptotycznej jest trudniejsze jezeli liczba iteracji
nie jest zawsze jednakowa.

Przyklad 6: Znajdz najdluzsza podtablice zawierajac a
liczby uporzadkowane rosnaco.

for (i=0; len=1; i<n-1; i++) {

for (i1=i2=k=i; k<n-1 && a[k]<a[k+1]; k++,i2++);

if(len < i2-i1+1) len=i2-i1+1; }

=> Jesli liczby w tablicy sa uporzadkowane malejaco, to pe tla zewne trzna

wykonuje sie n-1 razy, a w kaz dym jej przebiegu petla wewne trzna
wykona sie tylko raz. Zlozonosc algorytmu wynosi wi ec wtedy

O(n).

O(n).

10

19

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

SZACOWANIE ZLOZONOSCI OBLICZENIOWEJ

Przyk

Przyk

l

l

ady praktyczne mierzenia z

ady praktyczne mierzenia z

l

l

o

o

z

z

ono

ono

s

s

ci obliczeniowej

ci obliczeniowej

–

–

Przyk

Przyk

l

l

ad 6, c.d.

ad 6, c.d.

Analiza tych dwóch przypadk ów byla stosunkowo prosta poniewaz liczba
iteracji nie zalezala od wartosci elementów tablicy.
Wyznaczenie zloz onosci asymptotycznej jest trudniejsze jezeli liczba iteracji
nie jest zawsze jednakowa.

Przyklad 6: Znajdz najdluzsza podtablice zawierajac a
liczby uporzadkowane rosnaco.

for (i=0; len=1; i<n-1; i++) {

for (i1=i2=k=i; k<n-1 && a[k]<a[k+1]; k++,i2++);

if(len < i2-i1+1) len=i2-i1+1; }

=> Jesli liczby w tablicy sa uporzadkowane rosnaco, to petla zewnetrzna

wykonuje sie n-1 razy, a w kaz dym jej przebiegu petla wewne trzna
wykona sie i razy dla i

∈{1,...,n-1}.

Zl ozonosc algorytmu wynosi wi ec wtedy

O(n

O(n

2

2

).

).

Poniewa

Poniewa

z

z

z

z

l

l

o

o

z

z

ono

ono

sc

sc

algorytmu jest mierzona dla przypadku

algorytmu jest mierzona dla przypadku

„

„

najgorszych danych

najgorszych danych

”

”

zatem z

zatem z

l

l

o

o

z

z

ono

ono

sc

sc

algorytmu wynosi

algorytmu wynosi

O(n

O(n

2

2

).

).

20

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

SZACOWANIE ZLOZONOSCI OBLICZENIOWEJ

Przyk

Przyk

l

l

ady praktyczne mierzenia z

ady praktyczne mierzenia z

l

l

o

o

z

z

ono

ono

s

s

ci obliczeniowej

ci obliczeniowej

–

–

Przyk

Przyk

l

l

ad 6, c.d.

ad 6, c.d.

Analiza tych dwóch przypadk ów byla stosunkowo prosta poniewaz liczba
iteracji nie zalezala od wartosci elementów tablicy.
Wyznaczenie zloz onosci asymptotycznej jest trudniejsze jezeli liczba iteracji
nie jest zawsze jednakowa.

Przyklad 6: Znajdz najdluzsza podtablice zawierajac a
liczby uporzadkowane rosnaco.

for (i=0; len=1; i<n-1; i++) {

for (i1=i2=k=i; k<n-1 && a[k]<a[k+1]; k++,i2++);

if(len < i2-i1+1) len=i2-i1+1; }

=> Z reguly dane nie sa uporzadkowane i ocena zloz onosci algorytmu jest

rzecz a nielatwa, ale bardzo istotna. Staramy sie wyznaczy zloz onosc

w „ przypadku optymistycznym”, „ przypadku pesymistycznym” oraz

„ przypadku srednim”. Czesto poslugujemy sie wtedy przyblizeniami

opartymi o notacje „ duze O,

Ω i Θ”.

11

21

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

SZACOWANIE ZLOZONOSCI OBLICZENIOWEJ

Przyk

Przyk

l

l

ady praktyczne mierzenia z

ady praktyczne mierzenia z

l

l

o

o

z

z

ono

ono

s

s

ci obliczeniowej

ci obliczeniowej

–

–

Przyk

Przyk

l

l

ad 7

ad 7

Przyklad 7:

Algorytm sortowania

Insertion-Sort(A)

1. for j:=2 to length[A]

2.

do key:=A[j]

/* Wstaw A [i] w posortowany

ciag A[1..j-1].*/

3.

i:= j-1

4.

while i>0 i A[i] > key

5.

do A[i+1] := A[i]

6.

i:= i-1

7.

A[i+1] := key

Przyklad dzialania algorytmu

5 2 4 6 1 3

2 5 4 6 1 3

2 4 5 6 1 3

2 4 5 6 1 3

1 2 4 5 6 3

1 2 3 4 5 6

22

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

SZACOWANIE ZLOZONOSCI OBLICZENIOWEJ

Przyk

Przyk

l

l

ady praktyczne mierzenia z

ady praktyczne mierzenia z

l

l

o

o

z

z

ono

ono

s

s

ci obliczeniowej

ci obliczeniowej

–

–

Przyk

Przyk

l

l

ad 7, c.d.

ad 7, c.d.

Insertion-Sort(A)

koszt

koszt

liczba wykona

liczba wykona

n

n

1.

for j:=2 to length[A]

c

1

n

2.

do key:=A[i]

c

2

n-1

3.

i:= j-1

c

3

n-1

4.

while i>0 i A[i] > key

c

4

5.

do A[i+1] := A[i]

c

5

6.

i:= i-1

c

6

7.

A[i+1] := key

c

7

n-1

∑

=

n

j

j

t

2

∑

=

−

n

j

j

t

2

)

1

(

∑

=

−

n

j

j

t

2

)

1

(

12

23

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

SZACOWANIE ZLOZONOSCI OBLICZENIOWEJ

Przyk

Przyk

l

l

ady praktyczne mierzenia z

ady praktyczne mierzenia z

l

l

o

o

z

z

ono

ono

s

s

ci obliczeniowej

ci obliczeniowej

–

–

Przyk

Przyk

l

l

ad 7, c.d.

ad 7, c.d.

)

1

(

)

1

(

)

1

(

)

1

(

)

1

(

)

(

7

2

6

2

5

2

4

3

2

1

−

+

−

+

−

+

+

−

+

−

+

=

∑

∑

∑

=

=

=

n

c

t

c

t

c

t

c

n

c

n

c

n

c

n

T

n

j

j

n

j

j

n

j

j

1

2

)

1

(

2

−

+

=

∑

=

n

n

j

n

j

2

)

1

(

)

1

(

2

−

=

−

∑

=

n

n

j

n

j

=

−

+













−

+













−

+













−

+

+

−

+

−

+

=

)

1

(

2

)

1

(

2

)

1

(

1

2

)

1

(

)

1

(

)

1

(

)

(

7

6

5

4

3

2

1

n

c

n

n

c

n

n

c

n

n

c

n

c

n

c

n

c

n

T

)

(

2

2

2

2

2

2

7

4

3

2

7

6

5

4

3

2

1

2

6

5

4

c

c

c

c

n

c

c

c

c

c

c

c

n

c

c

c

+

+

+

−













+

−

−

+

+

+

+













+

+

=

2

2

( )

(

)

T n

an

bn

c

O n

=

+ + =

24

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

SPOSOBY BADANIA OPTYMALNOSCI

ALGORYTMÓW

n

Istnieje pewna granica

zwana

wewnetrzna

zlozonoscia

problemu

(ang. inherent problem

complexity), tzn. minimalna ilosc pracy niezbednej
do wykonania w celu rozwiazania zadania, której
nie mozna przekroczyc, poprawiajac zlozonosc
algorytmu;

n

Aby pokazac, ze

algorytm jest optymalny

algorytm jest optymalny

ze

ze

wzgl

wzgl

e

e

du na z

du na z

l

l

o

o

z

z

ono

ono

sc

sc

najczesciej dowodzi sie, ze

istnieje pewne dolne oszacowanie liczby operacji

podstawowych potrzebnych do rozwiazania
problemu.

13

25

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

Aby zbadac, czy algorytm jest optymalny nalezy:

1. Zaprojektowac

mozliwie najlepszy algorytm,

powiedzmy A. Nastepnie przeanalizowac algorytm
A, otrzymujac zlozonosc najgorszego przypadku

W

.

2. Dla pewnej funkcji

F

udowodnic twierdzenie

mówiace, ze

dla dowolnego algorytmu w rozwa

dla dowolnego algorytmu w rozwa

z

z

anej

anej

klasie istniej

klasie istniej

a

a

dane rozmiaru

dane rozmiaru

n

n

takie,

takie,

z

z

e algorytm

e algorytm

musi wykona

musi wykona

c

c

przynajmniej

przynajmniej

F(n

F(n

)

)

krok

krok

ó

ó

w.

w.

3. Jesli funkcje

W

i

F

sa równe, to algorytm A jest

optymalny (dla najgorszego przypadku).

SPOSOBY BADANIA OPTYMALNOSCI

ALGORYTMÓW

26

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

Przyklad

Problem

: Znajdowanie najwiekszej wsród n liczb.

Klasa algorytmów

: Algorytmy, które porównuja

liczby i przepisuja je.

Operacja podstawowa

: Porównanie dwóch

wielkosci.

SPOSOBY BADANIA OPTYMALNOSCI

ALGORYTMÓW

14

27

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

Algorytm_2

Dane

: L, n, gdzie L jest tablica

n-elementowa .

Wyniki

: max, najwiekszy element

w L.

begin

1.

max:= L[1];

2.

for index:= 2 to n do

3.

if max < L[index] then

max:= L[index]

end;

Oszacowanie g

Oszacowanie g

ó

ó

rne

rne

:

Przypuscmy, ze

liczby zapisane s a w tablicy L. Poró wnania s a
realizowane w linii 3, która jest wykonywana n-1
razy. Zatem n-1 jest g órna granica liczby
porównan koniecznych do znalezienia
maksimum w najgorszym przypadku danych.

Oszacowanie dolne

Oszacowanie dolne

:

:

Przypuscmy, ze nie

ma dwóch jednakowych liczb w L.
Zalo zenie takie jest dopuszczalne,
poniewaz dolne oszacowanie w tym
szczególnym przypadku jest równiez
dolnym oszacowaniem w przypadku
ogólnym. Gdy mamy n róznych liczb, to
n-1 z nich nie sa najwiekszymi. Ale zeby
stwierdzi c, ze jakis element nie jest
maksymalny, trzeba go porównac z
przynajmniej jednym z pozostalych.
Zatem

n-1

elementów musi byc

wyeliminowanych droga porównania z
pozostalymi. Poniewaz

w kazdym

porównaniu biora

udzial

tylko 2

elementy, wiec trzeba wykonac
przynajmniej n-1

porównan. Zatem

F(n)=n-1

jest poszukiwanym dolnym

oszacowaniem i na tej podstawie
wnioskujemy,

ze algorytm_2 jest

optymalny.

SPOSOBY BADANIA OPTYMALNOSCI

ALGORYTMÓW, PRZYKLAD C.D.

28

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

Przyklad

Problem

: Dane sa dwie macierze

rozmiaru

. Obliczyc macierz

.

Klasa algorytmów

: Algorytmy wykonujace

dodawania, odejmowania, mnozenia i dzielenia na
elementach macierzy.

Operacja podstawowa

: Mnozenie.

Oszacowanie górne

: Jak wiadomo, zwykly algorytm

wykonuje n

3

mnozen, zatem n

3

jest oszacowaniem

z góry.

Oszacowanie dolne

: Jak wiadomo, zlozonosc

pamieciowa wynosi 2n

2

, wiec

mnozen jest

niezbednych.

SPOSOBY BADANIA OPTYMALNOSCI

ALGORYTMÓW, PRZYKLAD

ij

A

a

 

=  

ij

B

b

 

=  

n

n

×

B

A

C

×

=

( )

2

n

Ω

15

29

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

n

Wniosek

: Nie ma mozliwosci stwierdzenia na tej

podstawie, czy algorytm klasyczny jest
optymalny, czy nie. Dlatego wlozono wiele
wysilku w poprawienie oszacowania dolnego, jak
dotad bezskutecznie. Z drugiej strony szuka sie
nowych, lepszych algorytmów.

n

Obecnie

najlepszy znany algorytm mno

najlepszy znany algorytm mno

z

z

enia

enia

dw

dw

ó

ó

ch macierzy kwadratowych wykonuje oko

ch macierzy kwadratowych wykonuje oko

l

l

o

o

n

n

2,376

2,376

mno

mno

z

z

e

e

n

n

.

.

n

Czy jest to algorytm optymalny? Nie wiadomo,
ciagle bowiem oszacowanie górne przewyzsza
oszacowanie dolne.

SPOSOBY BADANIA OPTYMALNOSCI

ALGORYTMÓW, PRZYKLAD C.D.

30

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

PRZYKLAD POSTEPU, JAKI DOKONAL SIE

W DZIEDZINIE PROJEKTOWANIA ALGORYTM ÓW

BADAJACYCH PLANARNOSC GRAFU

Algorytm

Rozmiar

analizowanego

grafu

w przypadku

udostepniania

komputera na okres

Symbol

Autor [rok]

Zlozonosc

Czas obliczen

dla

ms

c

10

=

100

=

n

minuty

godziny

1

A

Kuratowski
[1930]

6

cn

325 lat

4

8

2

A

Goldstein
[1963]

3

cn

2.8 godzin

18

71

3

A

Lempel et al.
[1967]

2

cn

100 sekund

77

6 000

4

A

Hopcroft-
Tarjan
[1971]

n

cn

2

log

7 sekund

643

24 673

5

A

Hopcroft-
Tarjan
[1974]

cn

1 sekunda

6 000

4

10

36

⋅

16

31

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

PROBLEM DECYZYJNY

A PROBLEM OPTYMALIZACYJNY

Problem decyzyjny – taki, dla którego odpowiedz brzmi „tak” albo „nie”.

Problem optymalizacyjny – polega na wyznaczaniu takiego elementu

zbioru rozwiazan dopuszczalnych, dla którego funkcja celu osiaga

ekstremum na tym zbiorze.

Przyklad

Optymalizacyjny

problem zaladunku mozna

sformulowac nastepujaco:

wyznaczyc

{ }

{

}

n

1,

j

,

0,1

x

:

E

x

B

S

x

j

n

n

*

=

∈

∈

=

⊂

∈

taki, ze

( )

( )

∑

=

∈

∈

=

=

n

j

j

j

x

c

1

S

x

S

x

*

m

x

c,

m

x

c,

ax

ax

gdzie

















≤

∈

=

∑

=

n

1

j

j

j

n

d

x

a

:

B

x

S

oraz

j

c - wartosc towaru typu

n

1

j

j

,

,

=

,

j

a - objetosc towaru typu

n

1

j

j

,

,

=

,

d - pojemnosc srodka transportu.

Zwiazany z tym problemem

problem decyzyjny

sformulujemy w postaci

b) czy istnieje

n

B

x

∈

spelniajacy ograniczenia

( )

S

x

y,

x

c,

∈

≥

32

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

WIELOMIANOWA

TRANSFORMOWALNOSC

(SPROWADZALNOSC) PROBLEMÓW

Definicja
Problem decyzyjny

Π

1

jest

wielomianowo transformowalny

(sprowadzalny, redukowalny)

do problemu decyzyjnego

Π

2

(co zapisujemy

Π

1

α Π

2

) jesli dla dowolnego lancucha danych x

problemu

Π

1

mozna w wielomianowym czasie (wielomian zalezy

od

x

) zbudowac lancuch y danych problemu

Π

2

taki, ze x jest

lancuchem danych konkretnego problemu

Π

1

z odpowiedzia „tak”

wtedy i tylko wtedy, gdy y jest lancuchem danych konkretnego
problemu

Π

2

z odpowiedzia „tak”.

17

33

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

KLASY ZLOZONOSCI OBLICZENIOWEJ

PROBLEMÓW

Definicja

Klasa P

nazywamy klase wszystkich problemów decyzyjnych, których zlozonosc

obliczeniowa jest wielomianowa tzn. takich, które DTM rozwiazuje w czasie
ograniczonym od góry przez wielomian.

Definicja

Klasa NP

nazywamy klase wszystkich problemów de cyzyjnych, które sa

rozwiazywalne w czasie wielomianowym przez NDTM.

lub równowaznie

Definicja

Mówimy, ze

problem decyzyjny

Π nalezy do NP

jesli istnieje wielomian p(n) od

rozmiaru tego problemu oraz algorytm

α (algorytm weryfikacji potwierdzenia)

takie, ze dla kazdego konkretnego problemu

?

D

z

∈

z odpowiedzia „tak”

i lancuchem danych x(z) istnieje lancuch (potwierdzenie) c(x) symboli alfabetu
wejsciowego

Σ taki, ze:

-

( )

(

)

( )

(

)

z

x

p

z

x

c

≤

,

- algorytm

α po otrzymaniu na wejsciu sekwencji

( )

( )

( )

z

x

c

#

z

x

(# oznacza koniec

danych i poczatek potwierdzenia) dochodzi do odpowiedzi „tak” po nie wiecej
niz

( )

( )

z

x

p

krokach.

NP

P

⊂

34

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

KLASY ZLOZONOSCI OBLICZENIOWEJ

PROBLEMÓW, PRZYKLAD 1

Przyklad

Klika k-elementowa

: dla danego grafu G o zbiorze wierzcholków

V zbadac czy istnieje podgraf pelny o licznosci zbioru
wierzcholków równej k.

Dla rozwiazania tego zadania nalezaloby przejrzec













k

V

podzbiorów zbioru V.
Nie jest znany algorytm wielomianowy dla tego zadania.
Istnieje natomiast dla konkretnego zadania z odpowiedzia „tak”
„potwierdzenie” w postaci kodu zbioru C elementów kliki o
licznosci k, które mozna zweryfikowac w czasie wielomianowym
przy pomocy pewnego algorytmu

α sprawdzajacego:

- czy zbiór C ma licznosc k,
- czy podgraf zawierajacy wierzcholki ze zbioru C jest pelny.

18

35

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

KLASY ZLOZONOSCI OBLICZENIOWEJ

PROBLEMÓW, PRZYKLAD 2

Przyklad

Zadanie komiwojazera

: dla sieci o

V

n

=

wierzcholkach

i odleglosciach miedzy wierzcholkami zadanymi
calkowitoliczbowa macierza

( )

n x n

ij

d

d

=

zbadac czy istnieje cykl

Hamiltona o dlugosci mniejszej lub równej zadanej liczbie L
(calkowitej).
Dla konkretnego zadania z odpowiedzia „tak” wystarczajacym
potwierdzeniem bedzie kod cyklu Hamiltona spelniajacy
wymagana dlugosc.
Przy pomocy algorytmu wielomianowego

α mozna sprawdzic czy:

-

( )

ij

d

d

L,

n,

=

poprawne dane,

- kod przedstawia cykl Hamiltona,
- dlugosc cyklu Hamiltona jest mniejsza lub równa L.

36

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

KLASY ZLOZONOSCI OBLICZENIOWEJ

PROBLEMÓW, PRZYKLAD 3

Przyklad

Problem SPELNIALNOSCI

: czy istnieje wektor

n

B

x

∈

, dla

którego formula alternatywno – koniunkcyjna jest równa 1.
Dla konkretnego zadania z odpowiedzia „tak” dobrym
potwierdzeniem jest wlasnie kod wektora x, dla którego ta
formula przyjmuje wartosc 1.
Algorytm

α w czasie wielomianowym sprawdza czy:

- formula zawiera n zmiennych,
- wyrazenie jest w poprawnej formie,
- formula przyjmuje wartosc 1.

19

37

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

KLASY ZLOZONOSCI OBLICZENIOWEJ

PROBLEMÓW, PROBLEMY NP-ZUPELNE

Wazna podklasa problemów w NP jest klasa problemów

NP – zupelnych

, które maja miedzy innymi taka wlasnosc, ze

j

j

j

e

e

e

s

s

s

l

l

l

i

i

i

k

k

k

t

t

t

ó

ó

ó

r

r

r

y

y

y

k

k

k

o

o

o

l

l

l

w

w

w

i

i

i

e

e

e

k

k

k

z

z

z

n

n

n

i

i

i

c

c

c

h

h

h

m

m

m

i

i

i

a

a

a

l

l

l

b

b

b

y

y

y

w

w

w

i

i

i

e

e

e

l

l

l

o

o

o

m

m

m

i

i

i

a

a

a

n

n

n

o

o

o

w

w

w

y

y

y

(

(

(

n

n

n

a

a

a

D

D

D

T

T

T

M

M

M

)

)

)

a

a

a

l

l

l

g

g

g

o

o

o

r

r

r

y

y

y

t

t

t

m

m

m

r

r

r

o

o

o

z

z

z

w

w

w

i

i

i

a

a

a

z

z

z

a

a

a

n

n

n

i

i

i

a

a

a

,

,

,

t

t

t

o

o

o

i

i

i

s

s

s

t

t

t

n

n

n

i

i

i

a

a

a

l

l

l

b

b

b

y

y

y

w

w

w

i

i

i

e

e

e

l

l

l

o

o

o

m

m

m

i

i

i

a

a

a

n

n

n

o

o

o

w

w

w

y

y

y

a

a

a

l

l

l

g

g

g

o

o

o

r

r

r

y

y

y

t

t

t

m

m

m

d

d

d

l

l

l

a

a

a

k

k

k

a

a

a

z

z

z

d

d

d

e

e

e

g

g

g

o

o

o

p

p

p

r

r

r

o

o

o

b

b

b

l

l

l

e

e

e

m

m

m

u

u

u

n

n

n

a

a

a

l

l

l

e

e

e

z

z

z

a

a

a

c

c

c

e

e

e

g

g

g

o

o

o

d

d

d

o

o

o

N

N

N

P

P

P

.

.

.

Definicja
Problem

NP

?

∈

nazywamy NP – zupelnym jesli dla kazdego

NP

?

∈

′

zachodzi

?

?

∝

′

.

38

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

KLASY ZLOZONOSCI OBLICZENIOWEJ

PROBLEMÓW, PROBLEMY NP-ZUPELNE

Twierdzenie (Cook, 1971)

Problem

SPELNIALNOSCI

jest NP – zupelny.

Dysponujac takim jednym problemem NP – zupelnym mozna
latwiej wykazac NP – zupelnosc innych problemów.

Przyklady problemów NP – zupelnych :

♦

klika k-elementowa,

♦

cykl (droga) Hamiltona,

♦

zadanie komiwojazera.

Znanych jest okolo kilku tysiecy problemów NP – zupelnych.

20

39

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

DOWODZENIE NP-ZUPELNOSCI

PROBLEMÓW

Glówna technika dowodzenia NP-zupelnosci problemów jest technika
ograniczania.

W celu wykazania, ze rozpatrywany problem

NP

?

1

∈

jest

NP-zupelny nalezy zgodnie z ta technika udowodnic, ze zawiera on w
sobie znany NP-zupelny problem

Π

2

jako przypadek szczególny

problemu

Π

1

.

Przyklad (

najdluzsza droga w grafie

)

Dany jest graf

(

)

E

V,

G

=

i liczba naturalna

.

V

k

<

Problem

Π

1

: czy graf G zawiera droge prosta (kazdy wierzcholek

tylko raz moze wystapic) zawierajaca nie mniej niz k galezi.

Przyjmujac

1

−

=

V

k

otrzymujemy jako przypadek szczególny

problem

Π

2

w postaci drogi Hamiltona, który jest NP-zupelny.

Zauwazmy ponadto, ze

NP

?

1

∈

gdyz sprawdzalnym wielomianowo

potwierdzeniem moze byc kod takiej drogi.
Zachodzi równiez

1

2

?

?

∝

co uzyskujemy ograniczajac problem

Π

1

do

tych

1

?

D

z

∈

dla których

1

−

=

V

k

.

40

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

DOWODZENIE NP-ZUPELNOSCI

PROBLEMÓW, c.d.

Przyklad (

konstrukcja niezawodnej sieci

)

Dane sa dwie symetryczne macierze

( )

nxn

ij

d

d

=

- macierz odleglosci miedzy wierzcholkami,

( )

nxn

ij

r

r

=

- macierz wielokrotnosci polaczen miedzy

wierzcholkami .

Problem

Π

1

: czy istnieje siec zawi erajaca n-wierzcholków, w

której suma odleglosci jest nie wieksza od L, taka ze miedzy i-tym
oraz j-tym wierzcholkiem istnieje nie mniej niz r

ij

rozlacznych

wierzcholkowo dróg.

Przyjmujac

2

r

1,

d

n,

L

ij

ij

=

=

=

dla wszystkich

j

r

≠

, jedynym grafem z n

wierzcholkami, w którym miedzy dwoma dowolnymi wierzcholkami
istnieja dwie nie majace wspólnych wierzcholków drogi, jest cykl z n
wierzcholkami. Zatem szczególny przypadek problemu

Π

1

jest problemem

Π

2

sprowadzajacym sie do pytania o istnienie cyklu Hamiltona w sieci

n-wierzcholkowej z

2

r

1,

d

ij

ij

=

=

. Problem

Π

2

jest NP-zupelny. Ponadto

NP

?

1

∈

oraz

1

2

?

?

∝

.

21

41

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

Wsród problemów NP-zupelnych mozemy zaobserwowac takie,
których szczególne przypadki staja sie problemami

„latwymi”

i takie, które pozostaja

„trudne”

równiez dla szczególnych

przypadków.

1

0

. Przypadki „latwe”

Przyklad
Maksymalna klika w grafie planarnym moze miec nie wiecej niz 4
wierzcholki. W takim szczególnym grafie mozna podac algorytm
wyznaczania kliki maksymalnej o zlozonosci

( )

4

V

O

czyli

„planarna klika” nalezy do P.
Do klasy P nalezy równiez zadanie tzw.”2-SPELNIALNOSCI”
tzn. zadanie, w którym kazdy czynnik zawiera tylko 2 literaly

(

)

i

i

x

x

lub

.

WNIOSEK: problem

WNIOSEK: problem

ó

ó

w nie nale

w nie nale

z

z

y formu

y formu

l

l

owa

owa

c

c

zbyt og

zbyt og

ó

ó

lnie, gdy

lnie, gdy

z

z

wtedy jest

wtedy jest

szansa,

szansa,

z

z

e zadanie mo

e zadanie mo

z

z

e mie

e mie

c

c

wielomianowy algorytm rozwi

wielomianowy algorytm rozwi

a

a

zania, mimo

zania, mimo

z

z

e jego uog

e jego uog

ó

ó

lnienie nale

lnienie nale

z

z

y do klasy NP

y do klasy NP

-

-

zupe

zupe

l

l

nych.

nych.

DOWODZENIE NP-ZUPELNOSCI

PROBLEMÓW, c.d.

42

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

OGÓLNY SCHEMAT ROZWIAZYWANIA
PROBLEM ÓW OPTYMALIZACYJNYCH

Problem optymalizacyjny

Problem optymalizacyjny

X

X

wersja decyzyjna

wersja decyzyjna

X

X

d

d

X

X

d

d

∈

∈

P

P

?

?

↔

↔

X

X

d

d

∈

∈

NPC

NPC

?

?

Zbuduj efektywny

Zbuduj efektywny

algorytm dla

algorytm dla

X

X

X

X

d

d

∈

∈

PseudoP

PseudoP

?

?

↔

↔

X

X

d

d

∈

∈

NPC!

NPC!

?

?

Zbuduj dla

Zbuduj dla

X

X

algorytm

algorytm

pseudowielomianowy

pseudowielomianowy

Zadowalaj

Zadowalaj

a

a

nas przybli

nas przybli

z

z

enia?

enia?

Tak

Wielomianowe algorytmy:

Wielomianowe algorytmy:

•

•

przybli

przybli

z

z

one

one

•

•

schematy aproksymacyjne

schematy aproksymacyjne

Nie

Okre

Okre

s

s

l satysfakcjonuj

l satysfakcjonuj

a

a

c

c

a

a

restrykcj

restrykcj

e

e

zagadnienia

zagadnienia

X

X

•

Ma

Ma

l

l

e dane: szukanie wyczerpuj

e dane: szukanie wyczerpuj

a

a

ce (

ce (

branch

branch

&

&

bound

bound

)

)

•

•

Heurystyki: tabu

Heurystyki: tabu

search

search

, algorytmy genetyczne, ...

, algorytmy genetyczne, ...

Brak

22

43

Z.Tarapata, Obliczenia równolegle, wyklad nr 1

Dziekuje za uwage