Algorytmy i struktury danych 1

[ Pobierz całość w formacie PDF ]
Algorytmy i struktury danych
Wykład01
WitoldKoioki
wkos@ukw.edu.pl
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óblewki, 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. yło:
Algorytmy
, WSiP, Warszawa, 1997
•
[8] M.M. ył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.
[ Pobierz całość w formacie PDF ]