1

Wykład 1

Literatura

Algorytmy

Dane i struktury danych

Klasyfikacja struktur

Wyszukiwanie połówkowe

1. T.H. Cormen, C.E. Leiserson, R.L. Rivest

„Wprowadzenie do algorytmów”

2. N. Wirth

„Algorytmy + struktury danych = programy”

3. K.Balińska

„Projektowanie algorytmów i struktur danych”

4. M.M. Sysło, N.Deo, J.S. Kowalik

„Algorytmy optymalizacji dyskretnej”

5. E.M. Reingold, J. Nievergelt, N. Deo

„Algorytmy kombinatoryczne”

Literatura

Literatura

6. L. Banachowski, K. Diks, W. Rytter

„Algorytmy i struktury danych”

7. P. Wróblewski

„Algorytmy, struktury danych i techniki programowania”

8. A.V. Aho, J.E. Hopcroft, J.D. Ullman

„ Algorytmy i struktury danych”

9. J. Marecki

„Struktury danych”

10. R. Jagielski,

„Tablice rozproszone”

Algorytm

Definicja

Ciąg elementarnych operacji przekształcający dane wejściowe
w wyniki

Środek umożliwiający rozwiązanie konkretnego problemu
obliczeniowego

Przykład: sortowanie

Dane wejściowe: ciąg n liczb a

1

, a

2

, ... a

n

Wynik: permutacja liczb a’

1

, a’

2

, ... a'

n

, taka że a’

1

≤

a’

≤

...

≤

a'

n

Przykład danych wejściowych - instancja problemu

Algorytm jest poprawny jeżeli dla każdej instancji
zatrzymuje się i daje poprawny wynik

Algorytm

Algorytm jako technologia

Współczesne zaawansowane technologie informatyczne:

sprzęt (procesory, karty graficzne)

sieci (lokalne, globalne)

GUI

Czy algorytmy są równie istotne co powyższe technologie?

Algorytm można przedstawić:

w języku naturalnym

w pseudokodzie

w postaci programu

w postaci realizacji sprzętowej

Analiza algorytmów

Analiza algorytmów:

to dział informatyki zajmujący się szukaniem najlepszych
algorytmów dla zadań komputerowych,

odpowiada na pytania:

czy dany problem może być rozwiązany na komputerze
w dostępnym CZASIE i PAMIĘCI?

który algorytm zastosować w danych okolicznościach?

czy jest lepszy algorytm (czy jest on optymalny)?

jak uzasadnić, że algorytm rozwiązuje postawione zadanie?

prowadzona jest w dwóch aspektach: poprawności
semantycznej i złożoności obliczeniowej

uwzględnia: poprawność semantyczną, prostotę, czas
działania, zajętą pamięć, optymalność, okoliczności użycia.

2

Złożoność obliczeniowa

Definiuje się ją jako:

ilość zasobów komputerowych potrzebnych do jego
wykonania (czas procesora, wielkość pamięci).

Wyróżnia się:

złożoność pesymistyczną (ilość zasobów potrzebnych przy
„najgorszych” danych wejściowych o rozmiarze

n

),

złożoność oczekiwaną (ilość zasobów potrzebnych przy
„typowych” danych wejściowych o rozmiarze

n

),

Typowe złożoności

stała

logarytmiczna

liniowa

liniowo logarytmiczna

kwadratowa

sześcienna

wielomianowa

wykładnicza

silnia

Rozmiar

zło

ż

ono

ś

ci

problemu

n

Funkcja

10

20

30

40

50

Złożoność czasowa a czas wykonania

Struktury danych

Dana: zapis informacji na nośniku komputerowym.

Dana prosta: zapis informacji, którego żadna część
nie jest zapisem informacji.

Dana złożona (struktura danych): środek służący
do przechowywania i organizowania danych w celu
ułatwienia dostępu i ich modyfikacji.

Klasyfikacja struktur danych

Ze względu na powiązania elementów struktury:

mnogościowe

liniowe

drzewiaste

grafowe (sieciowe)

Struktury mnogościowe - zbiory

Zbiór.

Operacje proste

:

inicjalizacja nowego zbioru,

sprawdzenie czy zbiór pusty,

sprawdzenie czy element należy do zbioru,

dołączenie elementu do zbioru,

usunięcie elementu ze zbioru.

Operacje złożone

:

suma zbiorów,

iloczyn zbiorów,

różnica zbiorów,

różnica symetryczna zbiorów,

...

Implementacje: bitowa, listowa.

3

Struktury liniowe - tablice

Tablica jest to struktura liniowa o:

dostępie adresowym.

Operacje proste:

odczytywanie zawartości działki,

zmiana zawartości działki.

Operacje złożone:

odszukiwanie elementu,

sortowanie elementów.

Rekordy

Rekord jest to struktura mnogościowa o:

dostępie adresowym (nazwa pola).

Tablica rekordów

Pole kluczowe (jedno z pól w rekordzie):

może decydować o położeniu rekordu w tablicy
(rozmieszczanie rekordów),

może być podstawą odszukiwania.

Rozmieszczanie rekordów w tablicy

Klasyfikacja według gęstości:

luźne,

zwarte.

Klasyfikacje według powiązania z zawartością:

chaotyczne,

sterowane:

monotonicznie (np. niemalejące, nierosnące),

algorytmicznie („haszowanie”).

Tablica - operacje złożone

Dla tablicy chaotycznej (zwartej oraz luźnej):

wprowadzenie rekordu,

odszukiwanie rekordu (sekwencyjne),

rozmieszczanie elementów,

reorganizacja tablicy (np. monotonizacja).

Dla tablicy monotonicznej

dochodzi

:

odszukiwanie: binarne (połówkowe), interpolacyjne.

Dla tablicy z rozmieszczeniem algorytmicznym:

odszukiwanie algorytmiczne,

rozmieszczanie algorytmiczne,

zmiana algorytmu rozmieszczającego.

Wyszukiwanie połówkowe

t : array [1..MAX] of integer;

lewy:= 1;

prawy:= MAX;

found:= false;

repeat

sr:=(lewy+prawy) div 2;

if t[sr]=sz then

found:= true

else if t[sr]<sz then

lewy:= sr+1

else

prawy:= sr-1

until found or (lewy>prawy);

if found then write(sr) else write(’not found’)

Wyszukiwanie połówkowe

t : array [1..MAX] of integer;

lewy:= 1;

prawy:= MAX;

repeat

sr:=(lewy+prawy) div 2;

if t[sr]<sz then

lewy:= sr+1

else

prawy:= sr-1

until lewy>prawy;

if t[lewy]=sz then write(lewy) else write(’not found’)