Algorytmy i struktury danych

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.