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

WYJŚCIE PRZEZ DRZWI
1.

Podejdź do drzwi

2.

Jeśli otwarte, to przejdź. KONIEC

3.

Naciśnij klamkę.

4.

Popchnij drzwi.

5.

Jeśli otwarte, to przejdź. KONIEC

6.

Pociągnij drzwi do siebie.

7.

Jeśli otwarte, to przejdź. KONIEC

8.

Drzwi nietypowe lub zamknięte na
klucz

WYJŚCIE PRZEZ DRZWI
1.

Podejdź do drzwi

2.

Jeśli otwarte, to przejdź. KONIEC

3.

Popchnij drzwi.

4.

Naciśnij klamkę.

5.

Jeśli otwarte, to przejdź. KONIEC

6.

Pociągnij drzwi do siebie.

7.

Jeśli otwarte, to przejdź. KONIEC

8.

Drzwi nietypowe lub zamknięte na
klucz

Algorytm przejścia przez drzwi

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).

START

STOP

T

N

Skrzynki graniczne:

Skrzynka warunkowa:

Skrzynka wejścia/wyjścia

Skrzynka operacyjna

Schemat blokowy

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.