Algorytmy i struktury danych
Wykład 01
Witold Kosioski
[e-mail]
01.03.2011
Literatura podstawowa
" [1] T. H. Cormen, Ch. E. Leiserson, R. L. Rivest, Wprowadzenie do
algorytmów, WNT, 2005
" [2] N. Wirth, Algorytmy + Struktury danych = Programy, WNT, 2004
" [3] A. V. Aho, J. E. Hopcroft, J. D. Ullman, Algorytmy I struktury danych,
Helion, 2003
" [4] P. Wróblewski, Algorytmy struktury danych i techniki programowania,
Helion 1996
" [5] L. Banachowski, K. Diks, W. Rytter, Algorytmy i struktury danych, WNT,
2006
" [6] D. Harel, Rzecz o istocie informatyki  Algorytmika, WNT, 2000
" [7] M.M. Sysło: Algorytmy, WSiP, Warszawa, 1997
" [8] M.M. Sysło, Konstrukcje algorytmiczne, WSiP. ,Warszawa, 1998
" [9] Inni, Zbiór zadań do ASD, Wydawnictwo PJWSTK, Warszawa, 2009
 Teraz kilka definicji:
" Algorytm to opis obiektów łącznie z opisem czynności jednoznacznie prowadzących
do określonego celu. Algorytm musi posiadać początek i koniec.
Chodzi tu o zaznaczenie miejsca, od którego zaczynamy algorytm oraz zaznaczenie miejsca,
w którym kończymy opis czynności danego algorytmu. Liczba kroków potrzebnych
do uzyskania określonego celu musi być skończona.
" Algorytm - to przepis rozwiązania zadania, zawierający opis danych wraz z opisem
czynności, które należy w określonym porządku wykonać z tymi danymi, aby osiągnąć
zamierzony cel.
" Algorytmem na rozwiązanie postawionego problemu nazywa się przepis
podający wszystkie czynności, które należy wykonać, by rozwiązać problem w skończonym
czasie.
" Algorytmika, podstawowy dział informatyki poświęcony poszukiwaniom,
konstruowaniu i badaniom algorytmów, zwłaszcza w kontekście
ich przydatności do rozwiązywania problemów za pomocą komputerów.
 Cechy algorytmu
Algorytm musi być:
Poprawny - tzn., dla każdego zestawu danych, po wykonaniu skończonej liczby
czynności, prowadzi do poprawnych wyników.
Jednoznaczny, tzn., w każdym przypadku jego zastosowania, dla tych samych danych
uzyskamy ten sam wynik.
Szczegółowy - aby wykonawca algorytmu rozumiał opisane czynności i potrafił je
wykonać.
Uniwersalny, aby posłużył do rozwiązywania pewnej grupy zadań, a nie tylko jednego
zadania (np. algorytm jest przepisem na rozwiązanie równania postaci ax+b=0 dla
dowolnych współczynników a i b, a nie - jednego konkretnego równania, np. 2x+3=0.
.
do gór
Etapy rozwiązywania problemów:
Gdzie pojawia się algorytm? Przy rozwiązywaniu problemów
Etapy rozwiązywania problemów:
1. Sformułowanie zadania.
2. Określenie danych wejściowych.
3. Określenie celu, czyli wyniku.
4. Poszukiwanie metody rozwiązania, czyli algorytmu.
5. Przedstawienie algorytmu w postaci:
- opisu słownego
- listy kroków
- schematu blokowego
- jednego z języków programowania
6. Analiza poprawności rozwiązania.
7. Testowanie rozwiązania dla różnych danych - ocena efektywności przyjętej metody.
Kolejnośd działao
Algorytm przejścia przez drzwi
WYJŚCIE PRZEZ DRZWI WYJŚCIE PRZEZ DRZWI
1. Podejdz
do drzwi 1. Podejdz
do drzwi
2. Jeśli otwarte, to przejdz
. KONIEC 2. Jeśli otwarte, to przejdz
. KONIEC
3. Naciśnij klamkę. 3. Popchnij drzwi.
4. Popchnij drzwi. 4. Naciśnij klamkę.
5. Jeśli otwarte, to przejdz
. KONIEC 5. Jeśli otwarte, to przejdz
. KONIEC
6. Pociągnij drzwi do siebie. 6. Pociągnij drzwi do siebie.
7. Jeśli otwarte, to przejdz
. KONIEC 7. Jeśli otwarte, to przejdz
. KONIEC
8. Drzwi nietypowe lub zamknięte na 8. Drzwi nietypowe lub zamknięte na
klucz klucz
Algorytmika jest kluczową dziedziną wszędzie tam, gdzie wykorzystuje się
komputery
Zasady budowy schematu blokowego
(metajęzyk algorytmu):
Każda operacja, relacja lub informacja umieszczona
jest w skrzynce.
Kolejność wykonywania operacji wyznaczają
połączenia między skrzynkami.
Każde połączenie jest zaczepione początkiem do
skrzynki a koniec do innej skrzynki lub innego
połączenia.
Skrzynki przybierają kształty: prostokąta, rombu,
równoległoboku, okręgu (elipsy).
Schemat blokowy
Skrzynki graniczne:
START
STOP
N
T
Skrzynka warunkowa:
Skrzynka wejścia/wyjścia
Skrzynka operacyjna
Schemat blokowy, przykład algorytmu , który wyznacza najmniejszą
wartośd spośród 3 elementów danego zbioru RÓŻNYCH liczb całkowitych
a,b,c.