Informatyka W3

Algorytmy

2009-04-19

Dr inż. Tadeusz BURAK

Metody Numeryczne

ALGORYTMY

2009-04-19

Dr inż. Tadeusz BURAK

Algorytm definicje

Algorytm jest to sposób postępowania podczas
rozwiązywania zadania

Algorytm – mechaniczna procedura
rozwiązywania problemu obliczeniowego

Gdzie:

problem obliczeniowy to zadanie z para-

metrami,

niekoniecznie

matematyczne,

byle

precyzyjnie określone, tzn. jakie parametry są
dopuszczalne,

jakie

warunki

spełniać

rozwiązanie,jakie mają być wyniki.

Parametry to dane wejściowe (INPUT).
Rozwiązanie –dane wyjściowe (OUTPUT).

Algorytmy

2009-04-19

Dr inż. Tadeusz BURAK

Algorytm definicje II

ALGORYTM, dokładny przepis podający
sposób rozwiązania określonego zadania w
skończonej liczbie kroków; zbiór poleceń
odnoszących się do pewnych obiektów, ze
wskazaniem porządku, w jakim mają być
realizowane.

ALGORYTM zapisany przy pomocy
języka programowania jest programem.

Wyróżniamy algorytmy numeryczne

(np.

Euklidesa)

i nienumeryczne operujące na

obiektach nie liczbowych

(np. dokumenty)

2009-04-19

Dr inż. Tadeusz BURAK

Algorytm definicje III

ALGORYTM sekwencyjny
Kolejność czynności jest określona w
sposób jednoznaczny

ALGORYTM niesekwencyjny

Kolejność czynności nie w każdym

przypadku jest jednoznaczna

Np.– Algorytmy równoległe, współbieżne

ALGORYTMY skończone

Algorytmy

2009-04-19

Dr inż. Tadeusz BURAK

Algorytm formy zapisu:

Zapis słowny

(np. zbiór przepisów kulinarnych)

Zapis matematyczny -

wzory

Graficzny -

schemat blokowy

Zapis w języku programowania

2009-04-19

Dr inż. Tadeusz BURAK

Schemat blokowy

Schemat blokowy -- elmenty

elmenty

A,B,C

START

STOP

WEJŚCIE – WYJŚCIE

PRZETWARZANIE - PROCES

DECYZJA

PROCEDURA

(POWTARZALNY FRAGMENT

ZDEFINIOWANY W INNYM MIEJSCU)

PRZENIESIENIE

START

STOP

WARUNEK

Tak

Nie

Algorytmy

2009-04-19

Dr inż. Tadeusz BURAK

Schemat blokowy I (wzór)

)

albo

∆

⋅

−

∆

⋅

Znając parametry a,b,c znajdź miejsce zerowe funkcji:

⋅

∆

−

⋅

∆

−

⋅

−

brak rozwiązania
w dziedzinie liczb

rzeczywistych

2009-04-19

Dr inż. Tadeusz BURAK

Start

STOP

WE:

A,B,C

D = B

--4*A*C

4*A*C

D < 0

X =

X = --B/(2*A)

B/(2*A)

WY:

D > 0

= (

= (--B+sqrt(D))/(2*A)

B+sqrt(D))/(2*A)

X2= (

X2= (--B

B--sqrt(D))/(2*A)

sqrt(D))/(2*A)

WY:

BRAK

ROZWIĄZANIA

WY:

, X

STOP

Tak

Nie

Schemat

Schemat
blokowy II

blokowy II

Algorytmy

dr inż. Tadeusz BURAK

Algorytm Euklidesa

Algorytm Euklidesa to algorytm znajdowania

największego wspólnego dzielnika (NWD) dwóch

liczb naturalnych. Nie wymaga on rozkładania

tych liczb na czynniki pierwsze.

Algorytm

dane są dwie liczby naturalne a i b

jeśli b jest równe zeru, to NWD jest równe a

w przeciwnym wypadku oblicz c jako resztę z
dzielenia a przez b

zastąp a przez b, zaś b przez c i zacznij od
początku.

dr inż. Tadeusz BURAK

Algorytm Euklidesa

Przykład

NWD

NWD liczb 1029 i 42 wynosi 21

obliczany jest następująco:

aaaa

bbbb

cccc

1029

0000

Algorytmy

2009-04-19

Dr inż. Tadeusz BURAK

Pętla

I = I+1

Licznik

Schemat

Schemat
blokowy

blokowy

SUMATOR

Dane:l

, l

,...l

,9999 Oblicz średnią?

STOP

Start

WE: X

I = 0; S=0

X = 9999

S = S+X

WY:

‘Średnia =‘ ;

‘Średnia =‘ ; S

S = S / I

Tak

Sumator

Nie

2009-04-19

Dr inż. Tadeusz BURAK

Pętla

Schemat

Schemat
blokowy

blokowy

SUMATOR II

Dane:N,l

, l

,...l

Oblicz średnią?

Start

WE: X

I = 1; S=0

I = N

Tak

Nie

WE: N

I = I+1

STOP

S = S+X

WY:

‘Średnia =‘ ;

‘Średnia =‘ ; S

Licznik

Sumator

S = S / N

Algorytmy

2009-04-19

Dr inż. Tadeusz BURAK

I=I+1

START

We N, l

,..l

Umieść w Tab A(I)

X= A(1)

I=1

X< A(I)

X= A(I)

I>N

WY X

STOP

Dane: N, l

, l

,..l

Znajdź największą liczbę

A(1)=L

A(2)=L

...

A(N)=L

2009-04-19

Dr inż. Tadeusz BURAK

Procedura zamiany

Dane w tablicy (zmiennej indeksowej):

T(1),T(2),..T(K),..T(L),..T(M)

Zamień wartości T(K) z T(L)

Z = T(K)

PROC.ZAMIEŃ

T(K) =T(L)

T(L) = Z

KONIEC PROC.

Algorytmy

dr inż. Tadeusz BURAK

Sortowanie

metodą przez porównanie sąsiednich elementów

-13

-13

-13

-13

dr inż. Tadeusz BURAK

Sortowanie 2

-13

-13

-13

-13

Algorytmy

dr inż. Tadeusz BURAK

Sortowanie 3

-13

-13

-13

dr inż. Tadeusz BURAK

Sortowanie 4

-13

Wynik

Dane wejściowe

Algorytmy

dr inż. Tadeusz BURAK

Sortowanie schemat blokowy

START

We: N,L

...L

Do tablicy: (1),A(2),…,A(N)

J=2

ZAMIEŃ
A(J-1) z A(J)

J > N - I

I = N -1

A(J-1) > A(J)

J =J + 1

I =I + 1

Tak

Nie

I=1

dr inż. Tadeusz BURAK

Miejsce zerowe funkcji

metoda bisekcji

metoda bisekcji –

– podziału połówkowego

podziału połówkowego

-15

-10

-5

-4

-2

Dana jest następująca funkcja:

Zadaniem jest znalezienie miejsca zerowego

Algorytmy

dr inż. Tadeusz BURAK

Miejsce zerowe funkcji

((

metoda bisekcji)

ALGORYTM 1

Założenia:

•Funkcja jest monotoniczna w założonym przedziale.

•Wartości funkcji na końcach przedziału są różnego znaku.

( F(Xp) * F(Xk) ) < 0

Algorytm:

•znajdujemy wartość funkcji dla połowy długości przedziału

•Jeżeli wartość funkcji na początku i w środku przedziału jest
tego samego znaku to wybieramy jako nowy początek
przedziału punkt środkowy – jeśli znaki się różnią to punkt
ś

rodkowy staje się nowym końcem przedziału.

dr inż. Tadeusz BURAK

Miejsce zerowe funkcji

((

metoda bisekcji)

ALGORYTM 2

Dla danej funkcji:

Przedział początkowy przyjmuje: Xp=1 , Xk=2

I odpowiednio Yp= -1,02 ; Yk=0,498

Wyliczone Xs = 1,5 i odpowiednio Ys = -0,213

-1,5

-1

-0,5

0,5

0,5

1,5

2,5

Algorytmy

dr inż. Tadeusz BURAK

Xp= 1,500

Xs= 1,625

Xk= 1,750

0,250

F(Xp)= -0,21

F(Xs)= -0,026 F(Xk)= 0,155

Miejsce zerowe funkcji

((

metoda

metoda bisekcji

bisekcji))

ALGORYTM 3

Xp= 1,000

Xs= 1,500

Xk= 2,000

1,000

F(Xp)= -1,02 F(Xs)= -0,213 F(Xk)= 0,498

Xp= 1,500

Xs= 1,750

Xk= 2,000

0,500

F(Xp)= -0,21 F(Xs)= 0,155

F(Xk)= 0,498

Xp= 1,630

Xs= 1,688

Xk= 1,750

0,125

F(Xp)

-0,026 F(Xs)

0,065

F(Xk)= 0,155

dr inż. Tadeusz BURAK

Algorytm obliczania całki oznaczonej

Algorytm obliczania całki oznaczonej
metodą prostokątów

metodą prostokątów

a a+h a+2h ....

A+h/

a a+h/2 a+h

F(h/2)