ALGORYTMY I STRUKTURY DANYCH
POLECANA LITERATURA
L. Banachowski
K. Diks
W Rytter.............................................. Algorytmy i struktury danych WNT Warszawa
T. H. Cormen
Ch. E. Leiserson
R. L. Rivest ......................................... Wprowadzenie do algorytmów WNT Warszawa
P. Wróblewski..................................... Algorytmy, struktury danych i techniki programowania
Helion Warszawa
M. M. Sysło ........................................ Piramidy, szyszki i inne konstrukcje algorytmiczne WSiP Warszawa
M. M. Sysło ........................................ Algorytmy WSiP Warszawa
B. Wojdyło.......................................... Wprowadzenie do informatyki z elementami metodologii
programowania TUTOR Toruń
ALGORYTM
Algorytm jest przepisem opisującym krok po kroku rozwiązanie problemu lub osiągnięcie jakiegoś celu.
SÅ‚owo algorytm pochodzi od brzmienia fragmentu nazwiska: Muhammad ibn Musa Al-Chorezmi, arabskiego
matematyka i astronoma, żyjącego na przełomie VIII i IX wieku. Jest on uznawany za prekursora metod
obliczeniowych w matematyce. Od fragmentu tytułu jego dzieła pochodzi inne słowo, algebra. Upowszechnił on
również stosowanie systemu dziesiętnego i posługiwanie się zerem.
Algorytmika jest nazwą dziedziny zajmującej się algorytmami i ich własnościami. Po raz pierwszy tego terminu
użył Dawid Harel w tytule swojej książki Rzecz o istocie informatyki algorytmika . Powstała ona na kanwie
pogadanek o algorytmach, prowadzonych przez autora w izraelskim radiu.
1
OPRACOWANIE: Grażyna Zawadzka
ETAPY ROZWIZYWANIA ZADAC ZA POMOC KOMPUTERA
1. Matematyczne sformułowanie zadania (in. specyfikacja):
a. dane
b. wyniki
2. Zbadanie istnienia rozwiązania (czy nie jest sprzeczne?) oraz wybór odpowiedniego algorytmu.
3. Przedstawienie algorytmu w postaci:
a. opisu słownego
b. listy kroków
c. schematu blokowego
d. drzewa algorytmu
e. programu i in.
4. Dowód poprawności algorytmu.
5. Obliczenia na komputerze (testowanie rozwiązania dla różnych danych).
6. Analiza wyników (ocena efektywności przyjętego algorytmu, złożoności obliczeniowej czasowej
i pamięciowej).
METODY PROGRAMOWANIA
1. TOP-DOWN (z góry na dół)
2. BOTTOM-UP (z dołu do góry)
CECHY POPRAWNEGO PROGRAMU
1. TOP-DOWN
2. strukturalny
REPREZENTACJE ALGORYTMÓW
1. OPIS ALGORYTMU W POSTACI LISTY KROKÓW
Lista kroków jest jednym z najczęściej stosowanych, dokładnych sposobów opisywania obliczeń oraz ich
kolejności. Poszczególne kroki zawierają opis operacji, które mają być wykonane przez algorytm. Mogą w
nich również wystąpić polecenia związane ze zmianą kolejności wykonywania kroków lub polecenia
zakończenia algorytmu. Przyjmuje się w tym opisie, że kolejność wykonywania poszczególnych kroków
jest zgodna z kolejnością ich wypisania, z wyjątkiem sytuacji, gdy jednym z poleceń jest przejście do
wykonania kroku o podanym numerze. W nawiasach {...} umieszczane są komentarze nie będące częścią
algorytmu, a jedynie komentujÄ…ce jego przebieg.
2
ALGORYTMY I STRUKTURY DANYCH
Przykład 1
Poniżej przedstawiono algorytm w postaci listy kroków obliczający wartość funkcji
ż#
ª#-1, dla x < 0
ª#
f (x) = 0, dla x = 0
¨#
ª#
1, dla x > 0
ª#
©#
(1)
Specyfikacja:
Dane: Dowolna liczba rzeczywista x.
Wynik: Wartość funkcji f(x) określonej powyższym wzorem.
Algorytm w postaci listy kroków:
Krok 0: Wczytaj wartość danej x.
Krok 1: Jeśli x>0, to f(x)=1. Zakończ algorytm.
Krok 2: {W tym przypadku xd"0.} Jeśli x=0, to f(x)=0. Zakończ algorytm.
Krok 3: {W tym przypadku x<0.} Przypisz f(x)=-1. Zakończ algorytm.
Opis algorytmów w postaci listy kroków najdokładniej określa wykonywane w algorytmie działania i ich
kolejność.
2. SCHEMAT BLOKOWY ALGORYTMU
Schemat blokowy jest jednym z najbardziej popularnych, graficznych sposobów przedstawiania
algorytmów.
Schemat blokowy to graf zorientowany składający się z następujących elementów:
START STOP
zapisywanie działań (instrukcji przypisania)
poczÄ…tek i koniec schematu
czytanie danych i drukowanie wyników
zapisywanie pytań (predykatów)
3
OPRACOWANIE: Grażyna Zawadzka
Å‚Ä…cznik (stosowany przy przenoszeniu na
przejścia do strzałek
następną stronę)
Elementy schematu blokowego łączymy w taki sposób, że sklejamy ze sobą strzałki wychodzące z
wchodzącymi . W schemacie nie powinno być strzałek wolnych.
Przykład 2
Poniżej przedstawiono schemat blokowy algorytmu obliczającego wartość funkcji (1):
Specyfikacja:
Dane: Dowolna liczba rzeczywista x.
Wynik: Wartość funkcji f(x) określonej powyższym wzorem.
Schemat blokowy algorytmu:
START
czytaj x
TAK NIE
x>0
pisz 1
NIE
TAK
x=0
pisz -1
pisz 0
STOP
STOP
STOP
(rys. 1)
4
ALGORYTMY I STRUKTURY DANYCH
3. DRZEWO ALGORYTMU
Drzewo algorytmu, nazywane również drzewem obliczeń, jest szczególnym rodzajem schematu blokowego,
który przyjmuje postać drzewa.
Drzewo w opracowaniach informatycznych jest rysowane na ogół do góry nogami, z korzeniem u góry.
Stosowane nazewnictwo elementów drzewa jest wzięte z dendrologii korzeń, wierzchołki końcowe
nazywają się liśćmi, a krawędzie, czyli połączenia w drzewie gałęziami.
Przykład 3
Poniżej przedstawiono przykładowe drzewo algorytmu obliczania wartości funkcji (1), odpowiadające
schematowi blokowemu z rys. 1.
Specyfikacja:
Dane: Dowolna liczba rzeczywista x.
Wynik: Wartość funkcji f(x) określonej powyższym wzorem.
Drzewo algorytmu:
korzeń
x>0
Nie
Tak
wierzchołki pośrednie
f(x)=1 x=0
Tak
Nie
f(x)=0 f(x)=-1
wierzchołki końcowe
(rys. 2)
W drzewie algorytmu można wyróżnić: korzeń wierzchołek, w którym rozpoczynają się działania
algorytmu, wierzchołki pośrednie, w których są umieszczone operacje wykonywane w algorytmie oraz
wierzchołki końcowe (liście), które odpowiadają różnym wynikom zakończenia obliczeń w algorytmie.
5
OPRACOWANIE: Grażyna Zawadzka
METODY PROGRAMOWANIA
LINIOWE lub WARUNKOWE
Rodzaj algorytmu i programu, w którym instrukcje wykonywane są po kolei bez powtórzeń.
Przykładem takiego algorytmu jest omówiony wcześniej algorytm obliczający wartość funkcji (1)
przedstawiony w postaci listy kroków, schematu blokowego (rys. 1) oraz drzewa algorytmu
(rys. 2).
ITERACJA
Rodzaj algorytmu i programu, w którym wielokrotnie wykonuje się pewne instrukcje, dopóki nie
zostanie spełniony warunek.
Przykład 4
Przykładem może być algorytm obliczający sumę n liczb kolejnych całkowitych większych od 0,
który przedstawiony został poniżej.
Specyfikacja:
Dane: n (ilość sumowanych liczb)
Wynik: s (suma n liczb całkowitych większych od 0)
Schemat blokowy algorytmu:
START
czytaj n
s:=0
i:=1
i<=n
s:=s+i
drukuj s
i:=i+1
STOP
6
ALGORYTMY I STRUKTURY DANYCH
Sprawdzenie:
dla n=4
si
01
12
33
64
10 5
REKURENCJA
Mówimy, że ciąg jest zdefiniowany rekurencyjnie, jeśli
a. określony jest pewien skończony zbiór wyrazów ciągu (np. kilka pierwszych lub pierwszy wyraz)
b. pozostałe wyrazy ciągu są zdefiniowane za pomocą poprzednich wyrazów ciągu, wzór definiujący
taki ciąg nazywamy wzorem, równaniem lub zależnością rekurencyjną
Warunek (a) zawiera krok początkowy definicji. Pozostałe wyrazy ciągu są określane za pomocą wzoru (b),
tzn. rekurencyjnie.
Rekurencja w algorytmice i programowaniu to wywołanie procedury lub funkcji wewnątrz jej samej.
Procedury i funkcje rekurencyjne, które dają się zastąpić przez procedury i funkcje iteracyjne nazywamy
pseudorekurencyjnymi.
Przykład 6
Typowym przykładem zastosowania rekurencji jest wyznaczenie n-tego elementu ciągu Fibonacciego,
którego elementy mają następujące wartości:
1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Zależność rekurencyjna przedstawia się następująco:
ż#a = a2 = 1 dla n = 1 i n = 2
ª# 1
¨#
an = an-1 + an-2 dla n > 2
ª#
©#
7
OPRACOWANIE: Grażyna Zawadzka
Poniżej przedstawiono funkcję rekurencyjną obliczającą n-ty element ciągu Fibonacciego oraz analizę jej
wywołań w programie dla n=4:
int FIB (int n)
{
if (n==1 || n==2) return 1;
return FIB(n-1) + FIB(n-2);
}
Poziomy rekurencji: FIB(4)
Wywołania rekurencyjne
1 (odkładanie wartości Powrót
FIB(3) + FIB(2)
na stos) wykonanie
obliczeń
1
FIB(2) + FIB(1)
2 (wstawianie wartości
ze stosu)
1
1
8
Wyszukiwarka
Podobne podstrony:
2009 12 Metaprogramowanie algorytmy wykonywane w czasie kompilacji [Programowanie C C ]248 12Biuletyn 01 12 201412 control statementsRzym 5 w 12,14 CZY WIERZYSZ EWOLUCJI12 2krlFadal Format 2 (AC) B807 12więcej podobnych podstron