To tylko jedna z 29 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
Algorytmy
i struktury danych
Od problemu do jego
rozwiązania
Sformułowanie
problemu
Przykład: Dany
jest ciąg liczb.
Znaleźć
największą z nich.
Rozwiązanie problemu
Niech max ma
wartość równą
pierwszemu
elementowi ciągu.
Porównaj max z
kolejnymi
elementami ciągu i
jeśli spotkasz
wartość większą,
przyjmij ją jako
nową wartość max.
Algorytm to metoda postępowania, która prowadzi do
rozwiązania jakiegoś problemu.
1
Algorytm
skończony, uporządkowany ciąg jasno
zdefiniowanych czynności, koniecznych do
wykonania dowolnego zadania z określonej
klasy zadań.
Słowo "algorytm" pochodzi od nazwiska
Muhammeda Alchwarizmi - matematyka
perskiego z IX wieku.
Badaniem algorytmów zajmuje się algorytmika.
Algorytm może zostać zaimplementowany w
postaci programu komputerowego.
Algorytm – definicja formalna
Oznaczmy przez:
We - zestaw danych wejściowych
Wy - zestaw danych wyjściowych
stan pamięci
przed
wykonaniem
algorytmu
Dane
We
Algorytm
stan
pamięci po
wykonaniu
algorytmu
Wyniki
Wy
Algorytm jest rozumiany jako odwzorowanie O, które
dla określonego zestawu We generuje zestaw Wy:
O: We → Wy,
gdzie liczności zbiorów We i Wy mogą być różne.
2
Przykład algorytmu I
Algorytm wyznaczania pola kwadratu o boku a:
Jako dane wejściowe pobierz wartość długości
boku kwadratu a
Oblicz wartość pola P = a2
Zwróć obliczoną wartość pola kwadratu P
Przykład algorytmu II
Algorytm Euklidesa wyznaczania NWD:
Dopóki x różne od y wykonuj:
Jeżeli xy, to odejmij y od x i wynik podstaw na x;
W przeciwnym przypadku od y odejmij x i wynik
podstaw na y;
koniec dopóki
wynikiem jest y
Dane x =21, y =12.
(x,y) = (21,12)- (9,12)- (9,3)- (6,3)- (3,3)
Wynik 3
3
Cechy algorytmu
Ogólność
Skończoność
Rozwiązanie zadania w skończonej liczbie kroków
Określoność
Rozwiązywanie określonej klasy zadań
Jednoznaczność operacji
Efektywność
Czas wykonania, zapotrzebowanie na pamięć
Sposoby zapisu algorytmu
Język naturalny
Schematy blokowe
Prostota, szeroki zasób słownictwa, mała precyzja
Zapis sformalizowany, brak możliwości
przedstawienia skomplikowanych algorytmów
Języki formalne
Najczęściej używane w praktyce, ścisłość zapisu
4
Schematy blokowe
Proces
uprzednio
zdefiniowany
Zapis/odczyt
danych
Łącznik
stronicowy
Łącznik
międzystronicowy
Algorytm wyznaczania
iloczynu
5
Algorytm wyznaczania
iloczynu
Algorytm wyznaczania
iloczynu
Język Pascal
y := 1;
for i := 1 to n do y := y * x [ i ];
6
Klasyfikacja algorytmów
(wybrane kategorie)
algorytmy proste – rozgałęzione
algorytmy cykliczne – mieszane
algorytmy równoległe – sekwencyjne
algorytmy numeryczne – algorytmy
nienumeryczne
algorytmy rekurencyjne – algorytmy
iteracyjne
Algorytmy proste i
rozgałęzione
7
Algorytmy cykliczne i
mieszane
Algorytm równoległy i
sekwencyjny
8
Algorytm równoległy i
sekwencyjny
Algorytm rekurencyjny i
iteracyjny
9
Rekurencja
Rekurencja albo rekursja - odwoływanie się
np. funkcji lub
(…)
…
Rząd złożoności obliczeniowej
Struktury danych
Struktury są „pojemnikami na dane”, które gromadzą
dane i układają je w odpowiedni sposób
Na strukturach danych operują algorytmy
Podstawowe struktury danych to:
rekord (struktura)
tablica
lista
stos
kolejka
drzewo (drzewo binarne)
graf
22
Rekord
W niektórych językach programowania nazywany
strukturą (ang. structure, struct, record)
Jest to obiekt programistyczny, grupujący dane
różnych typów
Posiada określone elementy (składowe), które mogą
być odczytywane i zmieniane
Odpowiednik rekordu w teorii relacyjnych baz danych
to krotka (wiersz tabeli)
Rekord - przykład
Rekord typu pracownik może zawierać np.:
Nazwisko – element danych typu tekstowego
Imię - element danych typu tekstowego
Data urodzenia - rekord typu data
Data…
… w ogólnie
dostępnym języku
programowania, łatwo
go zrozumieć, liczy
szybko, nie wymaga
dużo miejsca w pamięci
i zawsze daje
poprawne wyniki.
Koszt algorytmu
Miary kosztu:
• Liczba
zmiennych
• ilość miejsca
potrzebna dla
danych
• Liczba instrukcji
• liczba operacji
arytmetycznych
• liczba wywołań
procedury
Ogólnie: wybór miary zależy od typu problemu, rodzaju
rozwiązania.
15
Efektywność algorytmów…
... zobacz całą notatkę
Komentarze użytkowników (0)