Wykład 5

Algorytmy

Przed programem jest

algorytm

Jeżeli mamy do wykonania jakieś
zadanie,

budujemy

sposób,

przepis realizacji

tego za-dania.

Taki przepis to

algorytm

. Dopiero

po zapisaniu w konkretnym języku
programo-wania algorytm staje
się

programem

. Słowo „algorytm”

pochodzi od nazwiska matema-
tyka Muhammada ibn Musy al-
Chwarizmie-go (IXw.) - jeden z
jego traktatów nadał też nazwę
dziedzinie znanej jako „algebra”.

Który algorytm jest

„dobry”?

Do danego celu prowadzi zwykle
więcej niż jedna droga. Jak więc
oceniać

alternatywne

sposoby

rozwiązania problemu?

Podstawowe parametry algorytmu
to jego

złożoność czasowa

i

złożoność

pamięciowa

.

Oprócz

tego

przy

algorytmach

działających na liczbach trzeba
pamiętać

o

stabilności

nu-

merycznej

.

Który algorytm jest

„dobry”?

Złożoność czasowa

mówi, ile

kroków obli-czeniowych i ile czasu
wymaga zakończenie algorytmu
dla danej porcji danych.

Często

nie jest funkcją liniową!

Złożoność pamięciowa

mówi, jaką

maksy-malnie część danych i
wyników pośrednich trzeba w
ramach

danego

algorytmu

przecho-wywać

w

pamięci

operacyjnej.

Również

i

ten

parametr często nie zachowuje się
liniowo.

Przykład złożoności

czasowej

Na

przyjęciu

dyplomatycznym

bawi się N ambasadorów. Ich
uściski rąk są rejestro-wane przez
fotografa

po kolei

. Ile czasu

zajmie taka sesja zdjęciowa?

Algorytm:

Ambasador 1 podaje

rękę amba-sadorom 2, 3, 4... aż do
N. Ambasador 2 po-daje rękę
ambasadorom 3,4,...,N. W ten spo-
sób dochodzimy do ambasadorów
N-1 i N, którzy jako ostatni
wymieniają uścisk.

Złożoność

czasowa:

N(N-1)/2

jednostek

Stabilność numeryczna

Określa ona

wrażliwość

wyniku

końcowego na

błędy zaokrągleń

w

trakcie

obliczeń

oraz

na

dokładność

danych początkowych

.

Przykłady:

Komputer

wykonuje

operacje

liczbowe

ze

skończoną

precyzją. Może się okazać, że wynik
działania 10 000 000 000 + 1 to dalej
10 000 000 000.

Podobnie, realizacja dzielenia jako
mnożenie przez odwrotność jest mało
stabilna numerycznie dla ar-gumentów
bliskich zeru.

Schematy blokowe

Służą one do zapisu algorytmu w
obrazowy

sposób

podając

kierunek

procesu

obliczeń.

Najważniejsze używane symbole:

BLOK
DECYZYJNY

ODCZYT LUB
ZAPIS
DANYCH

START,
STOP

PROCES
(CZYNNOŚ
Ć)

START

Wprowadź liczby X i Y. Wyzeruj licznik

L (L := 0)

Odejmij Y od X (X := X - Y)

x<0 ?

Zwiększ licznik L o 1 (L :=

L + 1)

NIE

TAK

Wypisz

L

STOP

START

Wprowadź liczbę naturalną X.

Ustal zmienną W na X (W := X)

Zmniejsz X o 1 (X := X - 1)

X=0 ?

Pomnóż W przez X (W := W

* X)

NIE

TAK

Wypisz

W

STOP

START

Wprowadź liczbę naturalną X.

Ustal zmienną W na 1 (W := 1)

Wypisz

W

STOP

Zmniejsz X o 1 (X := X - 1)

Pomnóż W przez X (W := W

* X)

Wykonaj X razy:

START

Wczytaj zbiór N danych,

{x

i

}

i := 1

X

i

> X

i+1

?

i := i + 1

NIE

TAK

Zamień X

i

i

X

i+1

STOP

i = N ?

NIE

Były zamiany ?

NIE

TAK

TAK

Zeruj licznik zamian

Algorytm

sortowania

bąbelkowego

START

Dana funkcja f(x) oraz

x

1

i x

2

f(x

1

) i f(x

2

) są różnych

znaków

f(x

3

) = 0 ?

x

2

:=

x

3

NIE

TAK

x

3

:= (x

1

+

x

2

)/2

STOP

f(x

1

) i f(x

3

)

mają różne

znaki ?

NIE

TAK

Algorytm

poszukiwania

miejsca zerowego

funkcji

metodą bisekcji

x

1

:=

x

3

Obliczanie wartości

wielomianu

Sprawdźmy

złożoność

obliczeniową operacji wyznaczenia
wartości wielomianu W(x).

Niech

W(x) = 7x

4

+ 3x

3

+ 2x

2

-3x

+5

Klasycznie używamy zwykłego zapisu:

W(x) = 7

*

x

*

x

*

x

*

x

+

3

*

x

*

x

*

x

+

2

*

x

*

x

-

3

*

x

+

5

Użyto

dziesięciu

mnożeń,

czterech

dodawań

W ogólności obliczenie W(x) tym
algorytmem wymaga

n

dodawań oraz

n(n+1)/2

mnożeń,

gdzie

n

jest

stopniem wielomianu.

Obliczanie wartości

wielomianu

Znaczącą

redukcję

kosztów

obliczeń daje

algorytm Hornera

.

Wystarczy inaczej zapisać wielomian:

W(x) = ( ( ( 7

*

x

+

3 )

*

x

+

2 )

*

x

-

3 )

*

x

+

5

Użyto

czterech

mnożeń,

czterech

dodawań

W ogólności algorytm Hornera wymaga

n

mnożeń oraz

n

dodawań. Nie ma

zysku na dodawaniach, ale dla mnożeń
zredukowaliśmy koszt metody z

O(n

2

)

do

O(n)

.

Własność „STOP”

Czy możemy przewidzieć, że dany
program się za-trzyma, czyli czy ma
własność „STOP”?

Nie można

sporządzić schematu, który

zbada

własność

„STOP”

każdego

pomyślanego algorytmu!

Schemat taki musiałby bowiem umieć
sprawdzić

także

poniższy

krótki

algorytm...

1) Sprawdź, czy ten algorytm ma
własność

STOP

2)

Jeśli

TAK,

to

wpadnij

w

nieskończoną

pętlę

3) A jeśli nie, to ZAKOŃCZ

„Cudowne algorytmy”

Omówione

uprzednio

sortowanie

bąbelkowe jest bardzo powolne. Dziś
znamy znacznie szybsze algorytmy
stosowane np. w bazach danych.

Innym słynnym algorytmem jest

Szybka

Transfor-macja Fouriera (FFT, Fast
Fourier Transform)

powstała w latach

60. XX w. Redukuje ona czas obliczeń
transformacji Fouriera z

O(n

2

)

do

O(nlogn)

Wiele metod chemii obliczeniowej
posiada złożoność obliczeniową rzędu

O(n

4

)

i gorszą. Nieustannie pro-jektuje

się algorytmy jak najbardziej zbliżone
do

skalowania liniowego

,

O(n)

.