Algorytmy i algorytmika
Opracował dr Robert Fidytek
Kilka słów o historii algorytmów
Pojęcie algorytm pochodzi od przydomku
al-Chorezmiego (pisany po łacinie przyjął postać
Algorismus) arabskiego matematyka i astronoma
Muhammada ibn Musa, uznawanego za
prekursora metod obliczeniowych w matematyce.
Żył na przełomie VIII i IX wieku i to on
upowszechnił system dziesiętny i stosowanie zera
jako symbolu oznaczającego  nic .
2
Algorytmy wokół nas
Jakie czynności trzeba kolejno wykonać aby:

zaparzyć herbatę,

ugotować jajko,

wysłać e-maila,

uruchomić edytor Word,

wymienić żarówkę,

zatelefonować do kogoś,

poderwać dziewczynę/chłopaka?
3
Parzenie herbaty
Parzenie herbaty
1. Nalej wodę do czajnika.
2. Postaw czajnik na gaz.
3. Włącz gaz.
4. Zagotuj wodę.
5. Wrzuć saszetkę do szklanki.
6. Zalej herbatę.
7. Posłódz
do smaku.
8. Wypij herbatę.
4
Parzenie herbaty
Parzenie herbaty
1. Nalej wodę do czajnika.
Ile wody mam
2. Postaw czajnik na gaz.
nalać?
3. Włącz gaz.
Co mam zrobić,
4. Zagotuj wodę.
gdy czajnik jest
5. Wrzuć saszetkę do szklanki.
elektryczny?
6. Zalej herbatę.
Co to znaczy
7. Posłódz
do smaku.
posłódz
do smaku?
8. Wypij herbatę.
5
Pojęcie algorytmu
Algorytmika  dział informatyki zajmujący się
różnymi aspektami tworzenia i analizowania
algorytmów.
Algorytm  określony zbiór czynności, który w
skończonej liczbie kroków prowadzi do
rozwiązania problemu.
Określoność  zarówno kolejność wykonywania poszczególnych
kroków, jak i zbiór dostępnych instrukcji oraz ich znaczenie
powinny być ściśle zdefiniowane nie zostawiając miejsca na
dowolność interpretacji.
Skończoność  rozwiązuje problem w ograniczonej liczbie kroków,
musi mieć swój koniec. 6
Cechy algorytmów

poprawność (algorytm daje dobre wyniki),

jednoznaczność (daje takie same wyniki przy
takich samych danych),

skończoność (wykonuje się w skończonej ilości
kroków),

sprawność (czasowa - szybkość działania i
pamięciowa - "zasobożerność").
7
Etapy rozwiązywania problemów
1. Sformułowanie zadania.
2. Określenie danych wejściowych.
3. Określenie wyniku (celu).
4. Poszukiwanie metody rozwiązania (algorytmu).
5. Zapis rozwiązania (algorytmu).
6. Analiza poprawności rozwiązania.
7. Testowanie rozwiązania dla różnych danych
i ocena efektywności przyjętej metody.
8
Sposoby zapisu algorytmu

opis słowny,

lista kroków,

schemat blokowy,

zapis z wykorzystaniem jednego z języków
programowania.
9
Przykład: obliczanie NWD
Algorytm Euklidesa (lista kroków):
1. Dane są dwie niezerowe liczby naturalne a i b.
2. Dopóki liczby nie są równe powtarzaj krok 3
w przeciwnym razie przejdz
do kroku 4.
3. Od większej liczby odejmnij mniejszą
i tą większą zastąp otrzymaną różnicą.
4. Wyprowadz
wynik: NWD (największy wspólny
dzielnik) jest równy pierwszej liczbie.
10
Symbole stosowane w
schematach blokowych
11
Przykład: suma trzech liczb
12
Przykład: parzystość liczby
13
PROGRAM  ciąg instrukcji
wykonujący określony
algorytm
14