Algorytmy i struktury danych - Sposoby zapisu i cechy

Nasza ocena:

5
Pobrań: 49
Wyświetleń: 1134
Komentarze: 0
Notatek.pl

Pobierz ten dokument za darmo

Podgląd dokumentu
Algorytmy i struktury danych - Sposoby zapisu i cechy - strona 1 Algorytmy i struktury danych - Sposoby zapisu i cechy - strona 2 Algorytmy i struktury danych - Sposoby zapisu i cechy - strona 3

Fragment notatki:

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)

Zaloguj się, aby dodać komentarz