Algorytmy i struktury danych ...

[ Pobierz całość w formacie PDF ]
Wykład I
1. Pojęcie algorytmu
Definicja nieformalna
Algorytmem
jest pewna ściśle określona procedura obliczeniowa, która dla właściwych
danych wejściowych
„produkuje” żądane
dane wyjściowe
zwane
wynikiem działania
algorytmu
.
Dane
wejściowe
Algorytm
Dane
wyjściowe
Inne definicje:
Algorytm to
−
ciąg kroków
obliczeniowych prowadzących
do przekształcania danych wejściowych w
dane wyjściowe;
skończony
ciąg reguł
, które aplikuje się na skończonej liczbie danych, pozwalający
rozwiązywać zbliżone do siebie klasy problemów;
zespół reguł
charakterystyczny dla pewnych obliczeń lub czynności.
Źródłosłów:
Perski pisarz – matematyk
Abu Jafar Mohammed ibn Musa al-Khowarizmi
( IXw n.e.)
−
podał regułę wyjaśniającą krok po kroku zasady operacji arytmetycznych na liczbach
dziesiętnych;
po łacinie jego nazwisko brzmi:
Algorismus
.
Słowo
algorytm
często jest również kojarzone z greckim matematykiem
Euklidesem
(365-
300 p.n.e.),
który przedstawił m.in. sformalizowane algorytmy:
•
dzielenia kąta na połowy;
badania identyczności dwóch kątów;
obliczania Największego Wspólnego Podzielnika tzw. NWP dwóch liczb
naturalnych.
Algorytmy stworzone przez Euklidesa wykorzystywały w swoich działaniach
elementarne
operacje
, które mogły być wykonane w sposób jednoznaczny, tzn.
−
dla
algorytmów geometrycznych
były to operacje typu
prosta – okrąg
, wykonywane
przy pomocy cyrkla i linijki;
dla
algorytmów obliczeniowych
(numerycznych) były to operacje arytmetyczne:
+, -, *, /
oraz
porównywania
.
Nas interesować będą algorytmy w kontekście
informatycznym
, tzn. przekształcające
efektywnie
dane wejściowe
na
dane wyjściowe
zwane również
wynikiem.
Cechy algorytmu informatycznego:
¦
posiada
dane wejściowe
,
które pochodzą z dokładnie określonego zbioru, np. ze
zbioru liczb naturalnych
N
, ze zbioru liczb rzeczywistych
R
;
¦
produkuje
pewien
wynik
(niekoniecznie numeryczny);
¦
jest
precyzyjnie zdefiniowany
, tzn. każdy jego krok jest jednoznacznie określony i
obejmuje wyłącznie
operacje elementarne
;
¦
jest
skończony
, tzn. w skończonym czasie wyprodukuje wynik, a czas jego działania
powinien być możliwie precyzyjnie określony;
¦
jest
jednoznaczny
( inaczej powtarzalny), tzn. jego wielokrotne wykonywanie dla
identycznych danych wejściowych daje zawsze taki sam wynik;
¦
jest
kompletny
, tzn. uwzględnia wszystkie możliwe przy-padki, jakie mogą wystąpić
podczas jego wykonywania;
¦
jest
uniwersalny
, tzn. umożliwia rozwiązanie całej
klasy zadań
, a nie tylko
pojedynczego, ustalonego zadania.
Formy przedstawiania algorytmu informatycznego
¦
opis słowny
, zazwyczaj z formułami matematycznymi
¦
schemat graficzny
•
schematy blokowe
czyli ciągi znormalizowanych symboli graficznych
połączonych skierowanymi liniami
strukturogramy
czyli graficzne schematy zwarte
¦
specjalne
języki matematyczne
zwane
pseudokodami
¦
języki programowania
wyższego poziomu np. PASCAL, Fortran, C, BASIC, ADA,
Simula, itp.
Schematy blokowy – lista bloków
Tzw. schematy Bohma – Jacopiniego.
początek
Blok
począ
tk
wprowadzić
a,b,c
WE
koniec
Blok
końca
pisz
„Brak danych”
W4
x=x
y
Blok
operacy
Tak
Blok decyzyjny
warunek
Nie
Bloki
łącznikowe
dla i=1 do n
Blok
iteracyj
1
2
Bloki iteracyjne
Powtarzaj
<
ciąg czynności>
dopóki
<
warunek
>
Dopóki
<warunek
>
wykonuj
<ciąg czynności
>
Ciąg czynności
Nie
warunek
Tak
Nie
warunek
Ciąg czynności
Tak
Strukturogramy zwarte
(Diagramy Nassi - Shnaeidermana)
Blok wejścia (klawiatura, plik)
A
Blok wyjścia (monitor, drukarka, plik)
A
Blok operacyjny
Operacja
Warunek
Blok decyzyjny
tak
nie
Blok 1
Blok 2
wyrażenie
Blok wyboru z szeregu możliwości
W1
Blok 1
W2
Blok 2
W3
Inaczej
Blok 3
Blok
i=1,m
Pętla - cykliczne wykonanie bloku dla 1,...,m
Blok - treść pętli
warunek
pętla typu
dopóki <warunek> wykonuj <blok>
blok
blok
pętla typu
powtarzaj <blok> aż do <warunek>
warunek
nazwa algorytmu
blok procedury
(odrębnego, nazwanego fragmentu algorytmu)
Typy algorytmów
Z punktu widzenia organizacji wykonywanych czynności (obliczenia, rysowanie,
porównywanie) rozróżniamy
trzy
podstawowe
typy algorytmów
:
¦
liniowy
(
sekwencyjny
): wszystkie czynności są wykonywane w ściśle określonej
kolejności, jedna za drugą;
¦
z rozgałęzieniami (selekcja
): kolejność i zakres wykonywanych czynności zależy od
warunków, których spełnienie (lub niespełnienie) zależy od danych wejściowych oraz
pewnych wyników pośrednich;
¦
iteracyjny (pętla
): pewien ciąg identycznych czynności (tzw. cykl lub pętla) jest
powtarzalny wielokrotnie dla różnych danych.
Przykłady różnych form przedstawienia algorytmu.
Opis słowny
Problem:
Oblicz wartość funkcji:
f(x)
x
x
R
Wynik:
wartość funkcji
f(x
)
określona jest wzorem:
-1 dla x<0
f(x)=
0 dla x=0
1 dla x>0
Algorytm:
krok 0:
Podaj wartość danej x
krok 1:
Jeśli x>0, to f(x)=1.
Zakończ algorytm
krok2:
Jeśli x=0, to f(x)=0
Dla
x
0
Zakończ algorytm
krok 3:
Mamy f(x)=-1
.
Dla
x
0
Zakończ algorytm
Schemat blokowy
początek
podaj x
TAK
NIE
x<0
TAK
NIE
wynik =
x=0
koniec
wynik = 0
wynik = 1
Koniec
koniec
koniec
Dane
:
dowolna liczba rzeczywista x
wynik=-
1
[ Pobierz całość w formacie PDF ]