Algorytmy_Struktury_Danych.pdf

(328 KB) Pobierz
231772321 UNPDF
Algorytmy i Struktury Danych
dr Karol Grudziński
Uniwersytet Kazimierza Wielkiego
i
Wyższa Szkoła Gospodarki
<Zawiera Obszerne Cytaty z Książek. Do użytku wewnętrznego.>
Pojęcia Podstawowe
Komputery stały się narzędziem powszechnego
użytku a ich zastosowania daleko wykraczają
poza pierwotny jedyny cel: obliczenia.
Takie a nie inne możliwości ich zastosowania
wynikają z odpowiedniego ich zaprogramowania.
•
Algorytmy i Struktury Danych to dziedzina o
silnych podstawach teoretycznych, wywodząca
się z matematyki i informatyki.
•
Znajomość fundamentów tej dziedziny jest
niezbędna do sprawnego i wydajnego
programowania.
•
2
•
ALGORYTM: Formalny przepis wykonania
określonej czynności. Ciąg instrukcji służących
wykonaniu jakiegoś zadania.
●
Do zaprogramowania konkretnego zadania
możemy na ogół użyć jednego z wielu algorytmów
– wybór jakiegoś konkretnego decyduje jak
szybko komputer wykona zadanie i ile zasobów
będzie potrzebne.
●
Efektywność rozwiązania danego problemu przy
użyciu danego algorytmu – czy to pod względem
szybkości czy zasobów - jest często nie tylko
cechą samego algorytmu ale i zależy od
konkretnych danych. 3
●
TEORIA ZŁOŻONOŚCI: umożliwia określenie
żarłoczności algorytmu w odniesieniu do różnych
zasobów, z których najważniejszy jest zazwyczaj
czas realizacji i zajętość pamięci.
Dla większości rozwiązywanych problemów
wybór konkretnego algorytmu to sprawa
kompromisu między czasem realizacji a
zajętością pamięci: szybsze algorytmy na ogół
wymagają większych pamięci.
4
●
●
Notacja 'dużego O'
Podstawową miarą efektywności algorytmu jest
zależność czynnika stanowiącego o tej
efektywności (najczęściej czasu wykonania) od
rozmiaru problemu.
Przykład sortowania: mamy dwa algorytmy
sortowania, 1 : sortuje tysiąc liczb w 1s a milion w
10s; 2 : tysiąc w 2s a milion w 5s.
●
Wniosek: wartości bezwzględne czasów
wykonania nie na wiele się zdają przy
porównywaniu obydwu algorytmów – wyższość
któregoś z nich uwarunkowana jest rozmiarem
danych. 5
●
●

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin