A.Szewczyk (Kat.Informatyki AGH)

Przedm.“ASD”, 1999/2000, sem.letni

2000-02

1.Wstęp do przedmiotu

1.1.Nazwa przedmiotu

Nazwa polska: „Algorytmy i struktury danych”

Nazwa angielska: „Data algorithms and structures”

albo: „Data structures and algorithms”

Semantyka: „Struktury i algorytmy dotyczące danych”

Pierszeństwo struktur przed algorytmami

1.2.Pojęcie informacji

(ujęcie obiektowe)

1.3.Dane proste i złożone

Dane: zapisy informacji na nośniku komputerowym

Dana prosta: gdy część zapisu nie jest zapisem informacji

Dana złożona:

1) podłoże danej

2) pokrycie podłoża

3) wyróżnienia działek podłoża

1.4.Podłoże danej złożonej

1) działki („pozycje”) podłoża (zbiór P)

2) powiązania między działkami (zbiory R₁, R₂, ... relacji R_i ⊆ P × P)

1.5.Klasyfikacja danych złożonych

(według struktury podłoża)

Struktury:

mnogościowe

liniowe

pierścieniowe

drzewiaste

sieciowe (grafowe)

1.6.Pokrycie podłoża

Zbiór C danych składowych

Funkcja pokrywająca γ : P → C

Struktury wielowarstwowe

1.7.Ograniczenia pokrycia

Ograniczenia ilościowe równościowe i nierównościowe

Ograniczenia co do typu

Jednorodność pokrycia

1.8.Wyróżnienia działek podłoża

(W₁, W₂, ... ⊆ P)

1.9.Struktury dynamiczne

( = struktury zanurzone w czasie)

Stan struktury dynamicznej

Zdarzenia i procesy

Rozkład procesu na podprocesy

Powiązania między procesami

Operacje proste i złożone

Operacje na wyróżnieniach, na pokryciu i na podłożu

1.10.Plan przedmiotu

Rozdz.1: Wstęp do przedmiotu

Rozdz.2: Struktury mnogościowe

Rozdz.3 - 10: Struktury liniowe (w tym sieci odsyłaczowe i tablice rozproszone)

Rozdz.11: Struktury pierścieniowe

Rozdz.12 - 15: Wprowadzenie do struktur grafowych i struktury drzewiaste

Rozdz.16: Struktury grafowe

Rozdz.17: Dane w pamięci niejednorodnej

Rozdz.18: Kompresja danych

1.11.Zawartość treściowa poszczególnych rozdziałów

Struktura statyczna

Dynamika (operacje proste i złożone; algorytmy operacji złożonych)

Problematyka implementacyjna

Zastosowania

1.12.Literatura w języku polskim

(kolejność chronologiczna odwrócona)

Banachowski L., Diks K., Rytter W.: Algorytmy i struktury danych. WNT, Warszawa, 1996 (podejście nieco odmienne od mojego, zalecam jednak zapoznanie się z tą książką)

Banachowski L., Kreczmar A., Rytter W.: Analiza algorytmów i struktur danych. Warszawa, 1987 (książka przydatna fragmentami)

Reingold E.M., Nievergelt J., Deo N.: Algorytmy kombinatoryczne. PWN, Warszawa, 1985 (nieco odmienny zapis operacji złożonych; bardzo dobre odsyłacze do literatury źródłowej)

Aho A.V., Hopcroft J.E., Ullman J.D.: Projektowanie i analiza algorytmów komputerowych. PWN, Warszawa, 1983 (książka przydatna fragmentami)

Jagielski R.: Tablice rozproszone. WNT, Warszawa, 1982 (bardzo dobre opracowanie, ograniczone jednak do problematyki tablic rozproszonych)

Lipski W.: Kombinatoryka dla programistów. Warszawa, 1982 (książka przydatna w zakresie algorytmów grafowych)

Dembiński P., Małuszyński J.: Matematyczne metody definiowania języków programowania. Warszawa, 1981 (przydatne rozdziały: algebra wielorodzajowa; abstrakcyje typy danych)

Deo N.: Teoria grafów i jej zastosowania w technice i informatyce. Warszawa, 1980 (kompletne opraco-wanie teorii grafów)

Wirth N.: Algorytmy + struktury danych = programy. WNT, Warszawa, 1980 (książka bardzo dobra od strony dydaktycznej, nie obejmuje jednak całego materiału)

Turski M.W.: Struktury danych. WNT, Warszawa, 1971 (pierwsza polska książka ze struktur danych, ukazały się dwa wydania)

1.13.Literatura w języku angielskim

(kolejność chronologiczna odwrócona)

Decker R.: Data Structures. Prentice Hall, Englewood Clffs, 1989 (dostępna w Bibliotece Głównej AGH; omawia m.in. abstrakcyjne typy danych)

Aho A.V., Hopcroft J.E., Ullman J.D.: Data Structures and Algorithms. Addison-Wesley, Reading (MA), 1985 (bardzo dobrzy autorzy, książka raczej trudno dostępna)

Horowitz E., Sahni S.: Fundamentals of Data Structures. Pitman, London, 1977 (książka bardzo dobra od strony dydaktycznej)

Hall P.A.V.: Computational Structures. An Introduction to Non-numerical Computing. London 1975 (interesujące podejście do budowy edytorów tekstowych; istnieje wersja rosyjska)

Lorin H.: Sorting and Sort Systems (1975) (klasyczna monografia metod sortowania; istnieje wersja rosyjska)

Knuth D.: The Art of Computer Programming. Vol.3: Sorting and Searching (1973)

Knuth D.: The Art of Computer Programming. Vol.1: Fundamental Algorithms (1968) (obydwa tomy monografii Knutha zawierają ilościowe wzory dla niektórych algorytmów)

1.14. Pozycja przedmiotu w planie studiów

Przedmioty poprzedzające:

Wstęp do informatyki

Przedmioty poprzedzane (m.in.):

Bazy danych

Systemy informatyczne

Metody obliczeniowe

Sztuczna inteligencja

========

2.Struktury mnogościowe

2.1.Zbiory

2.1.1.Definicja

Struktura mnogościowa dynamiczna

o pokryciu zupełnym różnowartościowym

Termin „element zbioru”

2.1.2.Operacje proste

Sprawdzanie czy zbiór jest niepusty

Dołączanie elementu

Wybór elementu

Usuwanie elementu

2.1.2.Operacje złożone

Sumowanie zbiorów

Iloczyn zbiorów

Różnica zbiorów

Symetryczna różnica zbiorów

2.2.Multizbiory

2.2.1.Definicja

Struktura mnogościowa dynamiczna

o pokryciu zupełnym niekoniecznie różnowartościowym

2.2.2.Operacje proste i złożone

Analogiczne jak dla zbiorów

2.3.Rekordy

2.3.1.Definicja

Struktura mnogościowa dynamiczna:

o podłożu stałym

o dostępie adresowym

2.3.2.Adresacja działek

Zbiór adresów A (adres = "nazwa pola")

Funkcja adresująca α : A → P

2.3.3.Operacje proste

Odczytywanie zawartości działki ( działka = "pole")

Zmiana zawartości działki

2.3.4.Termin „plik”

Terminem tym określana będzie każda struktura o działkach pokrytych przez rekordy

========

3.Struktury liniowe: wprowadzenie

3.1.Podłoże liniowe

Działki początkowa i końcowa

Relacja następstwa i relacja poprzedzania

Relacje osiągalności naprzód i wstecz

Podłoże liniowe puste

Struktura liniowa dynamiczna

3.2.Tablica liniowa

3.2.1.Definicja

Struktura dynamiczna

o podłożu liniowym stałym

o pokryciu jednorodnym

o dostępie adresowym

3.2.2.Pokrycie częściowe

Rozmieszczenie działek niepustych: zwarte lub luźne

3.2.3.Tablica liniowa numerowana (tablica TLN)

Numeracja działek podłoża:

gdy zbiór adresów A jest przedziałem liczb całkowitych

3.2.4.Operacje proste

Odczytywanie zawartości działki

Zmiana zawartości działki

3.2.5.Rozmieszczenie elementów tablicy

Rozmieszczenie zwarte

Rozmieszczenie luźne

Rozmieszczenie przypadkowe

Rozmieszczenie sterowane zawartością działki:

monotoniczne

algorytmiczne

3.2.6.Monotoniczność tablicy

Warunek: porządek liniowy w zbiorze danych pokrywających C

oznaczenie: c₁ ∠ c₂ ( = „c₁ jest wcześniejsze od c₂”)

Monotoniczność zwykła (niemalejąca):

jeżeli dla każdej pary adresów a₁ < a₂

pokrycia c₁ i c₂ działek p₁ = α (a₁) i p₂ = α (a₂)

spełniają warunek c₁ = c₂ albo c₁ ∠ c₂

Monotoniczność odwrócona (nierosnąca):

Jw., tylko z a₁ < a₂ wynika c₁ = c₂ albo c₂ ∠ c₁

3.2.7.Operacje złożone

Rozmieszczanie elementów

Odszukiwanie działki lub działek o zadanym pokryciu:

sekwencyjne; binarne; interpolacyjne; algorytmiczne

Reorganizacja tablicy:

monotonizacja („sortowanie”)

zmiana algorytmu rozmieszczającego

3.3.Plik TLN (tablicowy liniowy numerowany)

3.3.1.Definicja

Tablica TLN

o działkach pokrytych przez rekordy

jednakowego typu

3.3.2.Pole kluczowe rekordu

Zastosowanie:

do rozmieszczania rekordów

do odszukiwania rekordów

do sortowania pliku

3.3.3.Rozmieszczanie rekordów

Rozmieszczanie; zwarte; luźne; przypadkowe; sterowane zawartością rekordu:

monotoniczne; algorytmiczne

3.3.4.Odszukiwanie rekordów

Odszukiwanie sekwencyjne; binarne; algorytmiczne

Zakres stosowalności i ocena czasu

odszukiwania sekwencyjnego i binarnego

3.3.5.Reorganizacja pliku tablicowego

Monotonizacja („sortowanie”)

Zmiana algorytmu rozmieszczającego

3.4.Wstęp do algorytmów sortujących

3.4.1.Rząd złożonościowy algorytmu

Założenie:

funkcje rzeczywiste dodatnie f i g

argumentu naturalnego n

(np. długość pliku n i czas sortowania f(n))

Zapis f(n) ∈ O(g(n)) (czytamy: funkcja f jest rzędu funkcji g,

„O” od słowa „ordo” lub „order” = rząd) oznacza,

że istnieją współczynniki rzeczywiste dodatnie c₁ i c₂

oraz liczba naturalna N takie, że dla kazdego n > N jest

c₁g(n) ≤ f(n) ≤ c₂g(n)

3.4.2.Twierdzenia o rzędzie złożonościowym

1) Zwrotność: f(n) ∈ O(f(n))

2) Symetria: Jezeli f(n) ∈ O(g(n)) to g(n) ∈ O(f(n))

3) Przechodniość: Jezeli f(n) ∈ O(g(n)) oraz g(n) ∈ O(h(n)),

to f(n) ∈O(h(n))

4) Twierdzenie o mnożeniu przez współczynnik:

Jeżeli f(n) jest rzędu g(n), a k jest współczynnikiem rzeczywistym dodatnim,

to kf(n) jest też rzędu g(n).

5) Twierdzenie o sumie: Funkcja f + g jest rzedu max (f, g)

6) Twierdzenie o iloczynie: Jezeli f₁ jest rzedu g₁, a f₂ jest rzedu g₂,

to f₁ f₂ jest rzędu g₁ g₂

7) Wnioski z twierdzeń (4), (5) i (6):

a) Wielomian a₁n^m + a₂n^m-1 + ... jest rzedu n^m

b) O( lg_k n) = O( lg_l n) także dla k ≠ l, zamiast O( lg_k n) czy O( lg_l n)

można więc pisać O( lg n)

3.4.3.Najczęściej występujące rzędy złożonościowe

Stały: O(1); liniowy: O(n); kwadratowy: O(n²); potęgowy: O(n^m); wykładniczy: O(e ⁿ); logarytmiczny: O( lg n); liniowo - logarytmiczny: O( n lg n)

3.4.4.Klasyfikacja algorytmów sortujących

1) Według rodzaju struktury sortowanej

np. tablica; lista; łańcuch odsyłaczowy

2) Według metody sortowania

metody bezpośrednie:

przestawianie rekordów realizowane natychmiast

metody pośrednie:

etap logiczny - zapis informacji o potrzebnych przestawieniach

etap fizyczny - realizacja przestawień

3) Według miejsca sortowania

sortowanie wewnętrzne: w pamięci operacyjnej

sortowanie zewnętrzne: z wykorzystaniem pamięci masowej

4) Według zużycia pamięci pomocniczej

intensywne („in situ”): z małym zapotrzebowaniem na pamięć pomocniczą

ekstensywne: z dużym zapotrzebowaniem

5) Według stabilności

stabilne: bez przestawiania rekordów o jednakowych kluczach

niestabilne: z możliwością przestawiania rekordów o jednakowych kluczach

6) Według wydajności (podział umowny)

metody proste (złożoność kwadratowa lub gorsza)

metody szybkie (złożoność liniowo-logarytmiczna lub lepsza)

7) Według ilości kluczy w rekordzie

z jednym kluczem sortowania

z wieloma kluczami równorzędnymi

z wieloma kluczami zhierarchizowanymi

========

4.Sortowanie tablic: metody proste

4.1.Metoda pęcherzykowa

(„bąbelkowa”; ang. bubblesort)

4.1.1.Ogólna charakterystyka metody

Mała przydatność praktyczna

Podstawa metod Shella

Podstawa metody grzebieniowej

4.1.2.Pęcherzykowa kontrola monotoniczności

Inwersje elementarne i ich kontrola

4.1.3.Podstawowy wariant metody

Sekwencyjne usuwanie inwersji elementarnych

Efekt jednokrotnego przeglądu sekwencyjnego

Podstawowy algorytm pęcherzykowy

Rząd złożonościowy O(n²) z dużym współczynnikiem

4.1.3.Wariant ze zmienną logiczną

Podstawienia bool := false i bool := true

Warunek wyjścia z pętli

Ogólna ocena wariantu

4.1.4.Wariant wahadłowy ze zderzakami

Organizacja pętli zewnętrznej

Warunek wyjścia z pętli

Ogólna ocena wariantu

4.2.Metoda wstawiania

(ang. insertion sort)

4.2.1.Podstawowa koncepcja metody

Część monotoniczna pliku:

pusta

jednoelementowa

seria naturalna

Poszukiwanie miejsca dla nowego rekordu:

sekwencyjne („metoda wstawiania prostego”)

binarne („metoda wstawiania połówkowego”)

warunek stabilności

Wstawianie z przesuwaniem

Poszukiwanie sekwencyjne z jednoczesnym przesuwaniem

4.2.2.Ogólna charakterystyka metody

Rząd złożonościowy O(n²)

Zalecana dla n ≤ 20

4.3.Metoda wyboru

(„metoda prostego wyboru”; „metoda selekcji”; ang. selection sort)

4.3.1.Podstawowa koncepcja metody

Część monotoniczna pliku: pusta

Poszukiwanie minimum

Warunek stabilności

Wariant podstawowy: przestawianie

Wariant stabilny: wstawianie z przesuwaniem

4.3.2.Ogólna charakterystyka metody

Rząd złożonościowy dla poszukiwania minimum: O(n²)

Rząd złożonościowy dla przestawiania: O(n)

Rząd złożonościowy dla przesuwania: O(n²)

Rząd złożonościowy ogólny: O(n²)

Wariant podstawowy zalecany dla n ≤ 50

========

5.Sortowanie tablic: metody szybkie

5.1.Metoda podziałów

(„Quicksort”, autor C.A.R.Hoare, r.1962)

5.1.1.Ogólna charakterystyka metody

Metoda liniowo-logarytmiczna (jedna z najszybszych)

Niebezpieczeństwo „ukwadratowienia”

Brak stabilności

5.1.2.Wariant podstawowy (Wirtha)

1: procedure qs(id, ig);

2: begin i := id; j := ig;

3: kp := k[(id + ig) div 2];

4: repeat

5: while k[i] < kp do i := i + 1; while k[j] > kp do j := j − 1;

6: if i ≤ j then begin R[i] :=: R[j]; i := i + 1; j := j − 1 end

7: until i > j;

8: if j > id then qs(id, j); if i < ig then qs(i, ig)

9: end {qs}

Złożoność przy podziałach korzystnych: O(n log n)

Złożoność przy podziałach niekorzystnych: O(n²)

Złożoność statystyczna

5.1.3.Wariant Horowitza

Klucz kp z początku tablicy

Dla pliku monotonicznego złożoność kwadratowa

5.1.4.Wariant losowy

Nakład obliczeń na losowanie

5.1.5.Wariant z medianą z trzech

Nakład na obliczanie mediany

5.1.6.Wariant iteracyjny

Kolejność sortowania po podziale

5.1.7.Kombinacja z metodą prostą

Np. z metodą wstawiania

5.1.8.Algorytm poszukiwania mediany

Ok. dwa razy szybszy od wariantu podstawowego

5.1.9.Algorytm "Quickersort"

Podział na trzy części

5.2.Metoda scalania

(„metoda łączenia”, ang. mergesort)

5.2.1.Ogólna charakterystyka metody

Ekstensywność metody

Rząd złożonościowy O(n log n)

Metoda charakterystyczna dla list i łańcuchów

oraz dla sortowania zewnętrznego

5.2.2.Scalanie plików monotonicznych

Scalanie dwustrumieniowe

Scalanie wielostrumieniowe

5.2.3.Podstawowy (iteracyjny) wariant metody

Pamięć pomocnicza

Podział na pary elementarne

Algorytm podstawowy

Złożoność algorytmu podstawowego

Rozmieszczenie odcinków resztkowych

5.2.4.Wariant rekurencyjny

Zapis algorytmu rekurencyjnego

Rozmieszczenie odcinków resztkowych

5.2.5.Wariant naturalny

Serie naturalne

Granice między seriami

Efektywność wariantu naturalnego

5.3.Metoda grzebieniowa

(Combsort)

5.3.1.Uwagi wstępne

Opublikowana: „Byte”, kwiecień 1991

Autorzy: S.Lacey (specjalność: medycyna, genetyka);

R.Box (specjalność: geofizyka; matematyka)

Jest rozwinięciem metody pęcherzykowej

5.3.2.Wariant podstawowy

Tablica sortowana: A: array[1..size]

1: begin gap := size;

2: repeat

3: gap := max(trunc(gap/1.3), 1); top := size − gap;

4: swapped := false;

5: for i := 1 to top do begin j := i + gap;

6: if k[i] > k[j] then begin A[i] :=: A[j]; swapped := true end {if}

7: end {for}

8: until (gap = 1) and not swapped

9: end {cs}

5.3.3.Wariant "Combsort 11"

1: begin gap := size;

2: repeat

3: gap := trunc(gap/1.3);

4: case gap of 0: gap := 1; 9, 10: gap := 11 end {case};

5: top := size − gap; swapped := false;

6: for i := 1 to top do begin j := i + gap;

7: if k[i] > k[j] then begin A[i] :=: A[j]; swapped := true end {if}

8: end {for}

9: until (gap = 1) and not swapped

10: end {cs11}

5.3.4.Ogólna charakterystyka sortowania grzebieniowego

Rząd złożonościowy O(n log n)

Złożoność statystyczna: ok. 1,9 qs

Prosty algorytm

========

6.Sieci odsyłaczowe

6.1.Wprowadzenie

6.1.1.Podstawa sieci

Przypadek najczęstszy: plik TLN

Przypadek ogólny: dowolny plik o dostępie adresowym

Pole odsyłaczowe i odsyłacz („wskaźnik”; ang. pointer)

Odsyłacz niewłaściwy („nil”)

Kadłub rekordu ( = rekord bez pól odsyłaczowych)

Trzon rekordu ( = rekord bez pól odsyłaczowych i kluczowych)

6.1.2.Powiązania odsyłaczowe

Relacja następstwa odsyłaczowego

Relacja osiągalności odsyłaczowej

Odsyłacze zewnętrzne

6.1.4. Sieć odsyłaczowa nieswobodna

(B, I, D, R) gdzie:

B - podstawa sieci

I - zbiór odsyłaczy zewnętrznych początkowych

D - zbiór odsyłaczy zewnętrznych wyróżniających

R - zbiór rekordów osiągalnych z I

6.1.5. Sieć odsyłaczowa swobodna

Sieci nieswobodne równoważne

Klasa równoważnościowa sieci nieswobodnych

6.1.4.Operacje proste

Odczytanie zawartości rekordu wyróżnionego

Zmiana zawartości rekordu wyróżnionego

Zmiana wartości odsyłacza zewnętrznego

6.2.Proste przypadki sieci odsyłaczowych

6.2.1.Łańcuch odsyłaczowy jednokierunkowy

6.2.2.Łańcuch odsyłaczowy dwukierunkowy

6.2.3.Pierścień odsyłaczowy jednokierunkowy

6.2.4. Pierścień odsyłaczowy dwukierunkowy

7.Sortowanie tablic: metody pośrednie

7.1.Sortowanie łańcuchowe

7.1.1.Etap logiczny

1) Powiązać rekordy w łańcuch odsyłaczowy w kolejności fizycznej.

2) Posortować łańcuch dowolną metodą.

7.1.2.Etap fizyczny - wariant ekstensywny

Czytając rekordy w kolejności łańcucha odsyłaczowego („logicznej”) przepisywać je do tablicy pomocniczej. Działki tablicy pomocniczej zapełniać w kolejności fizycznej.

7.1.3.Etap fizyczny - wariant z łańcuchem dwukierunkowym

1) Uzupełnić łańcuch do dwukierunkowego

2) Czytając rekordy w kolejności logicznej, przenosić je do działek tej samej tablicy. Działki tablicy zapełniać w kolejności fizycznej. Rekordy przeszkadzające wypychać na zwalniające się miejsca, odpowiednio korygując skierowane do nich odsyłacze w rekordach logicznie sąsiednich.

7.1.4.Etap fizyczny - wariant McLarena

Czytając rekordy w kolejności logicznej, przenosić je do działek tej samej tablicy. Działki tablicy zapełniać w kolejności fizycznej. Rekordy przeszkadzające wypychać na zwalniające się miejsca. Nowy adres rekordu wypchniętego wpisać do pola odsyłaczowego rekordu wypychającego.

7.2.Sortowanie skorowidzowe

7.2.1.Etap logiczny

1) Utworzyć skorowidz. Zapełnić skorowidz adresami działek tablicy głównej w ich kolejności fizycznej.

2) Posortować zawartość skorowidza dowolną metodą w oparciu o klucze, zawarte we wskazywanych rekordach tablicy głównej.

7.2.2.Etap fizyczny („cykliczne wciąganie”)

1) Usunnąć rekord z pierwszej działki do pomocniczego magazynu.

2) Cyklicznie wciągać rekordy wskazywane przez zawartości działek skorowidza do opróżniających się działek tablicy głównej. Rekord ulokowany definitywnie („trwały”) zaznaczać wstawiając do odpowiedniej działki skorowidza jej własny adres.

3) Po ukończeniu cyklu wciągań przeglądać sekwencyjnie skorowidz od miejsca zakończenia cyklu poprzedniego. Nowy cykl rozpoczynać od pierwszego napotkanego rekordu nietrwałego.

4) Realizację algorytmu zakończyć po dojściu do końca tablicy.

7.2.3.Skorowidz rozszerzony

Działka skorowidza oprócz odsyłacza zawiera klucz wskazywanego rekordu.

7.3.Sortowanie licznikowe

7.3.1.Założenie wstępne

Numeracja działek tablicy od 0 do n - 1.

7.3.2.Etap logiczny

1) Utworzyć pomocniczą tablicę liczników.

2) Sekwencyjnie przeglądać tablicę główną, traktując klucz w aktualnie rozpatrywanym rekordzie za wzorcowy.

3) Dla każdego klucza wzorcowego zliczyć rekordy o kluczach mniejszych. Wynik umieścić w odpowiednim liczniku.

4) W przypadku kluczy nieróżnowartościowych usunąć powtórzenia wartości liczników, odpowiednio je inkrementując. Po tej operacji zawartość k - tego licznika jest docelowym adresem rekordu z działki nr k.

7.3.3.Etap fizyczny („cykliczne wypychanie”)

1) Rozpoczynając od działki początkowej przenosić rekordy na ich definitywne lokalizacje według aktualnych wartości odpowiednich liczników. Rekordy przeszkadzające wypychać na ich lokalizacje według tej samej zasady. Rekordy trwałe zaznaczać, wstawiając do odpowiedniego licznika jego własny adres.

2) Po ukończeniu cyklu wypychań poszukiwać sekwencyjnie początku nowego cyklu od miejsca zakończenia cyklu poprzedniego. Nowy cykl rozpoczynać od pierwszego napotkanego rekordu nietrwałego.

3) Realizację algorytmu zakończyć po dojściu do końca tablicy.

7.3.4.Ogólna ocena metody

Metoda mało wydajna, jej analiza może być traktowana jako ćwiczenie.

========

8.Struktury liniowe o podłożu zmiennym

8.1.Stos

(ang. stack)

8.1.1.Definicja

Struktura dynamiczna:

o podłożu liniowym zmiennym,

o pokryciu zupełnym jednorodnym,

o dynamice stosowej.

8.1.2.Wyróżnienia

Wierzchołek stosu

Dno stosu

8.1.3.Szczególne przypadki

Stos elementarny

Stos pusty

8.1.4.Operacje proste

Sprawdzanie niepustości stosu

Opróżnianie stosu

Wprowadzanie nowego elementu na wierzchołek

Odczyt zawartości wierzchołka

Usuwanie (kasowanie, „strącanie”) wierzchołka

8.1.6.Operacje złożone

Przeglądanie stosu

8.1.7.Implementacje tablicowe

Stos o ograniczonej wysokości na tablicy liniowej

Dwa stosy na tablicy

Wiele stosów na tablicy

8.1.8.Implementacja odsyłaczowa

Łańcuch jednokierunkowy

8.1.9.Zastosowania

Magazyn LIFO („Last In First Out”)

Prosty magazyn jednorodnych elementów

8.2.Kolejka

(ang. queue)

8.2.1.Definicja

Jak stos, lecz z dynamiką kolejkową

8.2.2.Wyróżnienia

Początek kolejki

Koniec kolejki

8.2.3.Przypadki szczególne

Kolejka elementarna

Kolejka pusta

8.2.4.Operacje proste

Sprawdzanie niepustości kolejki

Opróżnianie kolejki

Wprowadzanie nowego elementu na koniec kolejki

Odczytywanie zawartości działki początkowej

Usuwanie (kasowanie) elementu początkowego

8.2.5.Operacje złożone

Przeglądanie kolejki

Konkatenacja kolejek

8.2.6.Implementacje tablicowe

Kolejka o ograniczonej długości na tablicy liniowej

Pełzanie kolejki i implementacja cykliczna

Wiele kolejek na tablicy

8.2.7.Implementacje odsyłaczowe

Łańcuch jednokierunkowy

Pierścień jednokierunkowy

8.2.8.Zastosowania

Magazyn FIFO („First In First Out”)

8.3.Talia niesymetryczna

(także „półka”; ang. deque)

8.3.1.Definicja

Jak stos, lecz z dynamiką talii niesymetrycznej

8.3.2.Wyróżnienia

Krańce lewy i prawy

8.3.3.Przypadki szczególne

Talia elementarna

Talia pusta

8.3.4.Operacje proste

Sprawdzanie niepustości talii

Opróżnianie talii

Wprowadzanie nowego elementu na lewy kraniec talii

Wprowadzanie nowego elementu na prawy kraniec talii

Odczytywanie zawartości działki krańcowej lewej

Kasowanie działki krańcowej lewej

8.3.5.Operacje złożone

Jak dla kolejki

8.3.6.Implementacje tablicowe

Jak dla kolejki

8.3.7.Implementacje odsyłaczowe

Jak dla kolejki

8.3.8.Zastosowanie

Kolejka zadań z pierszeństwem wysokim i zwykłym

8.4.Talia symetryczna

8.4.1.Definicja

Jak talia niesymetryczna, lecz z dynamiką talii symetrycznej

8.4.2.Wyróżnienia

Jak dla talii niesymetrycznej

8.4.3.Przypadki szczególne

Jak dla talii niesymetrycznej

8.4.4.Operacje proste

Jak dla talii niesymetrycznej, a oprócz tego:

Odczytywanie zawartości działki krańcowej prawej

Kasowanie działki krańcowej prawej

8.4.5.Operacje złożone

Jak dla talii niesymetrycznej

8.4.6.Implementacje tablicowe

Jak dla talii niesymetrycznej

8.4.7.Implementacje odsyłaczowe

Łańcuch dwukierunkowy

8.4.8.Zastosowanie

Kolejka zadań dla dwóch wykonawców z ich wzajemnym zastępowaniem się.

8.5.Lista jednokierunkowa

(niesymetryczna)

8.5.1.Definicja

Jak stos, lecz z dynamiką listy jednokierunkowej

8.5.2.Wyróżnienia

Działka początkowa

Działka robocza

8.5.3.Przypadki szczególne

Lista elementarna

Lista pusta

8.5.4.Operacje proste

Sprawdzanie niepustości listy

Opróżnianie listy

Przesuwanie wyróżnienia roboczego na działkę początkową

Przesuwanie wyróżnienia roboczego na działkę następną

Wprowadzanie nowego elementu na początek listy

Wprowadzanie nowego elementu na prawo od działki wyróżnionej roboczo

Odczytywanie zawartości działki wyróżnionej roboczo

Kasowanie działki początkowej

Kasowanie działki położonej na prawo od działki wyróżnionej roboczo

8.5.5.Operacje złożone

Przeglądanie listy

Przeszukiwanie listy

Sortowanie listy

Konkatenacja list

8.5.6.Implementacje tablicowe

Implementacje zwarta i luźna

8.5.7.Implementacja odsyłaczowa

Łańcuch jednokierunkowy

8.5.8.Zastosowania

Plik listowy

Implementacja zbioru lub multizbioru

8.6.Lista dwukierunkowa

(symetryczna)

8.6.1.Definicja

Jak lista jednokierunkowa, lecz z dynamiką listy dwukierunkowej

8.6.2.Wyróżnienia

Działka początkowa

Działka końcowa

Działka robocza

8.6.3.Przypadki szczególne

Jak dla listy jednokierunkowej

8.6.4.Operacje proste

Jak dla listy jednokierunkowej, a oprócz tego:

Przesuwanie wyróżnienia roboczego na działkę końcową

Przesuwanie wyróżnienia roboczego na działkę poprzednią

Wprowadzanie nowego elementu na koniec listy

Wprowadzanie nowego elementu na lewo od działki wyróżnionej roboczo

Kasowanie działki końcowej

Kasowanie działki położonej na lewo od działki wyróżnionej roboczo

8.6.5.Operacje złożone

Jak dla listy jednokierunkowej, lecz z możliwością stosowania bardziej dogodnych algorytmów.

8.6.6.Implementacje tablicowe

Jak dla listy jednokierunkowej

8.6.7.Implementacje odsyłaczowe

Łańcuch dwukierunkowy

8.6.8.Zastosowania

Jak dla listy jednokierunkowej, lecz z możliwością stosowania bardziej dogodnych algorytmów.

9.Sortowanie wielokluczowe i rozrzutowe

9.1.Przypadek kluczy równorzędnych

Przypadek kluczy równorzędnych omówiony był w rozdziale dotyczącym pośrednich metod sortowania.

9.2.Klucze zhierarchizowane

9.2.1.Przykłady

1) Klucz tekstowy w rozbiciu na klucze częściowe znakowe

2) Klucz numeryczny w rozbiciu na cyfry dziesiętne, dwójkowe lub w dowolnym innym zapisie pozycyjnym

9.2.2.Sortowanie pozycyjne, strategia MSD

(„Most Significant Digit First”)

1) Sortuj według kolejnych kluczy częściowych zaczynając od najstarszego

2) Sortowanie według następnego klucza: osobno dla każdej strefy równych wartości klu-cza bezpośrednio starszego

9.2.3.Sortowanie pozycyjne, strategia LSD

(„Least Significant Digit First”)

1) Sortuj według kolejnych kluczy częściowych zaczynając od najmłodszego

2) Sortowanie według następnego klucza: jednokrotne dla całego pliku

3) Każde sortowanie częściowe oprócz pierwszego: obowiązuje metoda stabilna

9.3.Sortowanie rozrzutowe

(ang. bin sort lub bucket sort, sortowanie „wiaderkowe”)

9.3.1.Ogólna charakterystyka metody

Metoda w zasadzie silnie ekstensywna, nadaje się tylko w przypadku małego zbioru dopuszczalnych wartości klucza sortowania. Ponieważ jest stabilna, może być stosowana jako metoda sortowania częściowego w ramach sortowania pozycyjnego.

9.3.2.Wariant podstawowy

1) W przypadku klucza sortowania o m wartościach i pliku sortowanego o n działkach utwórz m pomocniczych kolejek, indeksowanych przez te wartości. Każda kolejka powinna mieć pojemność n działek.

2) Czytaj klucze w kolejnych rekordach sortowanego pliku. Rekord R[i] z kluczem k[i] przenieś na koniec kolejki, indeksowanej przez k[i].

3) Po przeniesieniu wszystkich rekordów skatenuj kolejki w kolejności wzrastających klu-czy.

9.3.3.Wariant łańcuchowy

W przypadku implementacji pliku sortowanego i wszystkich kolejek pomocniczych na łańcuchach odsyłaczowych algorytm jw. staje się intensywny („in situ”).

9.3.4.Uwaga dotycząca terminologii

Proces przenoszenia rekordów do kolejek jest sortowaniem (dzieleniem rekordów na sor-ty), stąd ogólnie przyjęte określanie monotonizacji jako „sortowania”.

========

10.Tablice rozproszone

10.1.Wprowadzenie

Terminy angielskie: scatter storage; hashing

Literatura: Jagielski R.: Tablice rozproszone, 1982

Algorytmy: numeryzujące klucze tekstowe; rozpraszające (mieszające, „haszujące”) rekordy; usuwające kolizje adresowe; reorganizujące tablicę

Metody łańcuchowe

10.2.Numeryzacja kluczy tekstowych

Potrzeba numeryzacji

Składanie (ang. folding) cykliczne z dodawaniem arytmetycznym

Składanie cykliczne z różnicą symetryczną („XOR”)

Składanie zygzakowe

Składanie jako metoda rozpraszania

10.3.Metody rozpraszania

10.3.1.Metoda środka kwadratu

Algorytm:

1) Znumeryzowany klucz podnieś do kwadratu

2) Z binarnej reprezentacji wyniku wybierz k środkowych bitów

Ogólna ocena metody

10.3.2.Metoda mnożenia

Obliczenie adresu początkowego:

a₀ := trunc ( [(k * c) mod 1] * l )

gdzie k - klucz znumeryzowany

c - liczba rzeczywista, np. stosunek złotego podziału ( √5 + 1 ) / 2

l - długość tablicy o działkach numerowanych od 0 do l * 1

Ogólna charakterystyka metody

10.3.3.Metoda dzielenia

Obliczenie adresu początkowego:

a₀ := k mod l

gdzie k - klucz znumeryzowany

l - długość tablicy o działkach numerowanych od 0 do l * 1

Warunek: l - liczba pierwsza albo pseudopierwsza (czynniki pierwsze * 20)

10.4.Algorytmy usuwania kolizji adresowych

10.4.1.Wprowadzenie

Konieczność kolizji i jakość rozpraszania

Terminologia:

rekordy czołowe, nadmiarowe i synonimiczne

Rozmieszczenie synonimów:

1) wszystkie w tablicy głównej

2) czołowy w głównej, nadmiarowe w pomocniczej

3) odsyłacz w głównej, synonimy w pomocniczej

Powiązania w łańcuchu synonimów:

1) algorytmiczne

2) odsyłaczowe

10.4.2.Metoda liniowa

a_i := ( a₀ + b * i ) mod l

Najprościej przyjąć b = 1 albo * 1, otrzymując:

a_i := ( a₀ * i ) mod l

Zalety metody: prostota; małe odległości między synonimami

Wada: skłonność do tworzenia skupień

Zalecany współczynnik zapełnienia tablicy: ≤ 80 %

10.4.3.Metoda kwadratowa, wariant prymitywny

(Jagielski, str.36)

a_i := ( a₀ + b * i + c * i ² ) mod l

Najprościej przyjąć b = 0, c = 1 albo * 1, otrzymując:

a_i := ( a₀ * i ² ) mod l

Przykład: l = 10; adresy: 0, 1, ..., 9; a₀ = 0

Numery prób i : 1 2 3 4 5 6 7 8 9

Adresy a_i : 1 4 9 6 5 6* 9* 4* 1*

Uwagi: (1) * - adresy zdublowane

(2) 2, 3, 7, 8 - adresy pominięte

10.4.4.Metoda Radkego

Warunek wstępny: l - liczba Radkego ( = liczba pierwsza spełniająca dodatkowo warunek

l = 4 * j + 3, gdzie j - dowolna liczba naturalna)

Kolejne adresy:

a₁ := ( a₀ + 1 ² ) mod l a₂ := ( a₀ * 1 ² ) mod l

a₃ := ( a₀ + 2 ² ) mod l a₄ := ( a₀ * 2 ² ) mod l

a₅ := ( a₀ + 3 ² ) mod l a₆ := ( a₀ * 3 ² ) mod l itd.

Uwagi: (1) Liczba kwadratowana nie jest już numerem próby.

(2) Liczba prób musi pozostać mniejsza od l .

(3) Kwadraty kolejnych liczb naturalnych trzeba każdorazowo obliczać albo kopiować z tablicy.

10.4.5.Różnicowanie ciągu liczb kwadratowych

Liczby naturalne: 0 1 2 3 4 5 6 7 8

Liczby kwadratowe: 0 1 4 9 16 25 36 49 64

Pierwsza różnica: 1 3 5 7 9 11 13 15

Druga różnica: 2 2 2 2 2 2 2

10.4.6.Metoda Daya

Warunek wstępny: l jest liczbą Radkego

Algorytm (wg Jagielskiego, str.38):

1: a : = a ₀ ; m : = * l ;

2: znal : = false;

3: while not znal and m * l do begin

4: m : = m + 2 ;

5: a : = ( a + * m * ) mod l ;

6: test ( znal )

7: end { while }

Ogólna ocena metody

10.4.7.Metody sześcienne

(Jagielski, str.39)

Mniejsze ryzyko skupień

Większy nakład obliczeń

10.4.8.Inne metody

1) Rozpraszanie podwójne (Jagielski, str.33; ang. double hashing):

a_i : = ( h₁(k) + h₂(k) * i ) mod l

(metoda liniowa z losowanym krokiem)

2) Szukanie losowe (HS, str.475, ang. random probing):

a_i : = ( h₁(k) + h₂(i) ) mod l

3) Rozpraszanie wielokrotne (HS, str.465, ang. rehashing):

a_i : = h_i(k) albo a_i : = h(i, k)

10.5.Zastosowanie odsyłaczy

(ang. chaining)

10.5.1.Problem kasowania rekordów

Zapełnianie luk po rekordach skasowanych

Markowanie rekordów martwych

10.5.2.Problem sortowania łańcuchów

Optymalizacja dostępów przez sortowanie łańcuchów

10.5.3.Zastosowanie powiązań odsyłaczowych

Przypadek 1: Wszystkie rekordy w tablicy głównej

Przypadek 2: Rekordy nadmiarowe w tablicy pomocniczej

Przypadek 3: Wszystkie rekordy w tablicy pomocniczej

(Jagielski, str.29: „tablica indeksowa”)

10.6.Algorytm reorganizujący tablicę

10.6.1.Założenie wstępne

Wszystkie rekordy w tablicy głównej

10.6.2.Potrzeba reorganizacji

1) Zmiana rozmiaru tablicy

2) Zmiana algorytmu rozpraszającego albo usuwającego kolizje

3) Oczyszczanie pamięci z rekordów martwych

10.6.2.Algorytm

1) Wprowadź i odpowiednio ustaw jednobitowe znaczniki „rekord żywy” i „rekord trwały”.

2) Sekwencyjnie przeglądaj tablicę.

3) W przypadku napotkania rekordu żywego nietrwałego (uważajmy go rekord aktualny) uruchom algorytm rozpraszający i wyznacz nim adres a₀. Działkę o adresie a₀ uważaj za działkę aktualną. Jeżeli działka aktualna jest wolna albo zajęta przez rekord martwy, przenieś do niej rekord aktualny i zamarkuj go jako rekord trwały. Jeżeli działka aktualna jest zajęta przez rekord żywy nietrwały, wypchnij go rekordem aktualnym. Rekord wypchnięty uważaj za nowy rekord aktualny, a dotychczasowy rekord aktualny osadź w działce i zamarkuj jako trwały. Z nowym rekordem aktualnym kontynuuj postępowanie jak z poprzednim. Jeżeli kolejny rekord przeszkadzający jest żywy i trwa-ły, uruchom algorytm usuwania kolizji i wyznacz dla rekordu aktualnego nowy adres. Działkę o tym adresie uważaj za nową działkę aktualną; kontynuuj z nią postępowanie jak poprzednio. Po osadzeniu rekordu aktualnego bez wypchnięcia rekordu żywego powróć do sekwencyjnego przeglądu.

4) Algorytm kończy pracę po dojściu sekwencyjnego przeglądu do końca tablicy.

10.7.Statystyczne porównanie metod rozpraszania

(HS, str.468, wg Luma, Yuena i Dodda, CACM, r.1971)

10.7.1.Kolizje: szukanie liniowe

(Liczby w polu głównym tabeli oznaczają średnią ilość dostępów)

Współczynnik Zapełnienia	Metoda
		Składanie Cykliczne	Składanie Zygzakowe	Środek Kwadratu	Dzielenie
0,5 0,75 0,9 0,95	21,75 65,10 77,01 118,57	22,97 48,70 69,63 97,56	1,73 9,75 27,14 37,53	4,52 7,20 22,42 25,79

10.7.2.Kolizje: odsyłaczowe łańcuchy synonimów

Współczynnik Zapełnienia	Metoda
		Składanie Cykliczne	Składanie Zygzakowe	Środek Kwadratu	Dzielenie
0,5 0,75 0,9 0,95	1,33 1,48 1,40 1,51	1,39 1,57 1,55 1,51	1,26 1,40 1,45 1,47	1,19 1,31 1,38 1,41

10.7.3.Wniosek

Wyniki przemawiają za metodą dzielenia z synonimami powiązanymi przez łańcuch odsyłaczowy.

11.Struktury pierścieniowe

11.1.Pierścień jednokierunkowy

11.1.1.Definicja

Struktura dynamiczna:

o podłożu pierścieniowym zmiennym,

o pokryciu zupełnym jednorodnym,

o dynamice pierścienia jednokierunkowego

11.1.2.Działki wyróżnione

Umowny początek pierścienia

Działka robocza

11.1.3.Przypadki szczególne

Pierścień elementarny

Pierścień pusty

11.1.4.Operacje proste

Sprawdzanie niepustości pierścienia

Opróżnianie pierścienia

Przesuwanie wyróżnienia roboczego na działkę początkową

Przesuwanie wyróżnienia roboczego na działkę następną

Przesuwanie wyróżnienia początkowego na działkę roboczą

Wprowadzanie elementu jako nowego elementu początkowego

Wprowadzanie nowego elementu na prawo od działki roboczej

Odczytywanie zawartości działki roboczej

Kasowanie działki położonej na prawo od roboczej

11.1.5.Przykład operacji złożonej

Przeszukiwanie pierścienia

11.1.6.Implementacje

Implementacja tablicowa zwarta i luźna

Implementacja na pierścieniu odsyłaczowym jednokierunkowym

11.1.7.Przykład zastosowania

Implementacja multizbioru z wyrównaną częstością dostępu do poszcze-gólnych egzemplarzy

11.2.Pierścień dwukierunkowy

11.2.1.Definicja

Jak pierścień jednokierunkowy, lecz z dynamiką pierścienia dwukierunko-wego

11.2.2.Działki wyróżnione i przypadki szczególne

Jak dla pierścienia jednokierunkowego

11.2.3.Operacje proste

Jak dla pierścienia jednokierunkowego, a oprócz tego:

Przesuwanie wyróżnienia roboczego na działkę poprzednią

Wprowadzanie nowego elementu na lewo od działki roboczej

Kasowanie działki położonej na lewo od roboczej

11.2.4.Przykład operacji złożonej

Przeszukiwanie pierścienia

11.2.5.Implementacje

Implementacja tablicowa zwarta i luźna

Implementacja na pierścieniu odsyłaczowym dwukierunkowym

12.Podstawowe pojęcia teorii grafów

12.1.Graf prosty nieskierowany

12.1.1.Definicja

G = ( V, E )

gdzie: V (wierzchołki, vertices lub vertexes) - dowolny zbiór

E (krawędzie, edges): E ⊆ {{v₁, v₂} | v₁, v₂ ∈ V }

Wnioski: zakaz krawędzi zapętlonych;

zakaz krawędzi równoległych

12.1.2.Podstawowe relacje między wierzchołkami i krawędziami

Incydencja między wierzchołkiem a krawędzią

Adiacencja (sąsiedztwo) między wierzchołkami

12.1.3.Niektóre szczególne przypadki grafów

Graf pusty

Graf elementarny

Wierzchołek separowany

Graf wierzchołkowy

Graf pełny

12.1.4.Pojęcie podgrafu

G = ( V, E ), G' ⊆ G oznacza,

że V' ⊆ V, E' ⊆ E, oraz że G' = ( V', E' ) jest grafem.

12.1.5.Przykłady zastosowań

Sieć komunikacyjna

Sieć przesyłowa

Rysunek kreskowy

12.1.6.Ścieżka i pojęcia pochodne

Ścieżka prosta

Ścieżka uwikłana

Osiągalność wierzchołka v₂ z wierzchołka v₁

Spójność pary wierzchołków

Graf spójny

Część spójna grafu niespójnego

12.1.7.Cykl i pojęcia pochodne

Cykl prosty

Cykl uwikłany

Graf acykliczny

12.1.8.Parametry ilościowe grafu

Liczba wierzchołków

Liczba części spójnych

Stopień wierzchołka

Stopień grafu

12.1.9.Grafy etykietowane

Etykietowanie wierzchołków i krawędzi

Graf ważony

12.2.Drzewo bez korzenia

12.2.1.Definicja

Graf acykliczny spójny

12.2.2.Twierdzenie o jedynej ścieżce

Między dowolnymi wierzchołkami v₁ i v₂ drzewa występuje dokładnie jedna ścieżka.

12.2.3.Przykład

Drzewo rozpinające grafu spójnego ( = podgraf acykliczny, zawierający wszystkie wierzchołki i maksymalny podzbiór krawędzi grafu danego)

12.3.Drzewo z korzeniem

12.3.1.Definicja

Drzewo z korzeniem otrzymuje się z drzewa bez korzenia, powołując dowolnie wybrany wierzchołek do roli korzenia.

Terminologia: wierzchołek → węzeł

12.3.2.Podstawowe relacje między wierzchołkami i pojęcia pochodne

Relacje „przodek - potomek” i „ojciec - syn”

Rodzeństwo

Węzeł przelotowy, liść i korona drzewa

Poziom drzewa i numeracja poziomów

Ranga węzła

Ścieżka promieniowa

12.3.3.Parametry ilościowe drzewa z korzeniem

Liczba węzłów

Liczba poziomów ( = wysokość drzewa)

Stopień węzła

Stopień drzewa

12.3.4.Twierdzenie o jedynej ścieżce

W drzewie z korzeniem do każdego liścia prowadzi dokładnie jedna ścieżka promieniowa.

12.3.5.Drzewo mnogościowe

Drzewo z korzeniem, w którego rodzeństwach nie wprowadzono indeksacji ani porządku

12.3.6.Drzewo indeksowane

Drzewo z korzeniem, w którego rodzeństwach wprowadzono indeksację

12.3.7.Drzewo uporządkowane

Drzewo z korzeniem, w którego rodzeństwach wprowadzono porządki liniowe

12.3.8.Las mnogościowy

Zbiór drzew mnogościowych

12.3.9.Las indeksowany

Indeksowany zbiór drzew indeksowanych

12.3.10.Las uporządkowany

Liniowo uporządkowany zbiór drzew uporządkowanych

12.4.Graf prosty skierowany

12.4.1.Definicja

G = ( V, E )

gdzie: V - dowolny zbiór

E ⊆ {(v₁, v₂) | v₁, v₂ ∈ V ; v₁ ≠ v₂ }

Wnioski: zakaz krawędzi zapętlonych;

zakaz krawędzi zgodnie równoległych

dozwolone krawędzie przeciwrównoległe

12.4.2.Incydencje i adiacencje

Incydencje dodatnia i ujemna

Sąsiedztwo lewostronne, prawostronne i obustronne

12.4.3.Ścieżki, cykle i pojęcia pochodne

Zwrot krawędzi należącej do ścieżki (cyklu) musi być zgodny ze zwrotem ścieżki (cyklu)

Osiągalność wierzchołka v₂ z wierzchołka v₁ nie implikuje osiągalności wierzchołka v₁ z wierzchołka v₂ .

Słaba i silna spójność pary wierzchołków

Słaba i silna spójność grafu

12.4.4. Neutralizacja grafu

Każdą krawędź bez odpowiednika przeciwrównoległego uzupełnij takim odpowiednikiem. Każdą parę krawędzi przeciwrównoległych traktuj jako krawędź nieskierowaną.

12.4.5.Zastosowania

Sieci ze skierowanymi krawędziami

12.5.Graf prosty mieszany

Graf prosty, w którym mogą występować zarówno krawędzie skierowane jak i nieskiero-wane

12.6.Multigrafy

12.6.1.Multigraf skierowany

G = ( V, E, ι )

gdzie: V - dowolny zbiór

E - dowolny zbiór rozłączny w stosunku do V

ι (funkcja incydencji): E → V ²

Uwaga: Funkcja incydencji musi być funkcją zupełną.

Wnioski: 1) Krawędzie zapętlone są dozwolone.

2) Krawędzie równoległe są dozwolone.

12.6.2.Multigraf nieskierowany i mieszany

można uzyskać ze skierowanego przez całkowitą bądź częściową neutralizację

12.6.3.Zastosowanie

Sieci dowolnego charakteru.

13.Struktury drzewiaste: wprowadzenie

13.1.Definicje oparte na teorii grafów

13.1.1.Drzewiasta struktura danych

Struktura danych (na ogół: dynamiczna)

o podłożu drzewiastym (na ogół: zmiennym)

13.1.2.Podłoże drzewiaste

Drzewo lub las,

w którym węzły traktowane są jako działki podłoża,

a elementy relacji „ojciec - syn” - jako powiązania między działkami.

13.1.3.Uwagi dotyczące terminologii

1) W przypadkach, kiedy nie będzie to groziło wieloznacznością, statyczna lub dynamiczna struktura danych, której podłoże jest drzewem lub lasem, też będzie nazywana drzewem (lasem).

2) Drzewa, definiowane w oparciu o teorię grafów, będą tu nazywane drzewami grafowymi.

13.1.3.Uwaga dotycząca dynamiki

Dynamikę drzewiastych struktur danych łatwiej jest definiować wprowadzjąc rekurencyjne definicje tych struktur.

13.2.Definicje rekurencyjne

13.2.1.Uwagi wprowadzające

1) Definicje rekurencyjne pozwalają wykorzystać uprzednio wprowadzone definicje struktur dynamicznych (zbiór, tablica, lista) i przez to łatwiej definiować i klasyfikować dynamiczne struktury drzewiaste.

2) Struktury drzewiaste definiowane rekurencyjnie będą tu też nazywane drzewami rekurencyjnymi.

13.2.2.Drzewo rekurencyjne mnogościowe

Rekord o dwu polach:

1) pole korzenia (może być pokryte przez c ∈ C)

2) pole rozgałęzienia (może być pokryte przez las mnogościowy)

13.2.3.Las mnogościowy

Zbiór (w sensie mnogościowej struktury danych) drzew mnogościowych

13.2.4.Pojęcia związane

Korzeń drzewa T: pole korzenia drzewa T z pokryciem

Rozgałęzienie drzewa T: pokrycie pola rozgałęzienia drzewa T

Drzewo elementarne: drzewo o pustym rozgałęzieniu

Drzewo puste: drzewo elementarne o pustym polu korzenia

Poddrzewo główne drzewa T: element pokrycia rozgałęzienia drzewa T

Poddrzewo drzewa T:

1) drzewo T

2) poddrzewo główne drzewa T

3) poddrzewo poddrzewa głównego drzewa T

Węzeł drzewa T: korzeń poddrzewa drzewa T

Relacja „ojciec - syn” w drzewie T: zbiór par „węzeł N - korzeń poddrzewa głównego poddrzewa, którego korzeniem jest N”

13.2.5.Dynamika drzewa rekurencyjnego mnogościowego

jest zdeterminowana przez dynamikę zbioru (rozumianego jako mnogościowa struktura danych), zastosowaną do wszystkich występujących w tym drzewie rozgałęzień.

13.2.6.Związek z drzewem i lasem mnogościowym grafowym

Nietrudno zauważyć, że stan drzewa (lasu) mnogościowego rekurencyjnego, odpowiadający pewnej chwili czasu, może być traktowany jako drzewo grafowe mnogościowe (las grafowy mnogościowy), którego węzły potraktowane zostały jako działki grafowej struktury danych.

13.2.7.Drzewo rekurencyjne tablicowe

Jak drzewo rekurencyjne mnogościowe z tą różnicą, że każde występujące w tym drzewie rozgałązienie jest lasem tablicowym.

13.2.8.Las tablicowy

Tablica liniowa, której działki mogą być pokrywane przez drzewa tablicowe.

13.2.9.Związek z drzewem grafowym indeksowanym

Nietrudno zauważyć, że stan drzewa rekurencyjnego tablicowego, odpowiadający pewnej chwili czasu, może być traktowany jako drzewo grafowe indeksowane.

13.2.10.Drzewo rekurencyjne listowe

Jak drzewo rekurencyjne mnogościowe z tą różnicą, że każde występujące w tym drzewie rozgałęzienie jest lasem listowym.

13.2.11.Las listowy

Lista o działkach pokrytych przez drzewa listowe.

13.2.12.Związek z drzewem grafowym uporządkowanym

Nietrudno zauważyć, że stan drzewa rekurencyjnego listowego, odpowiadający pewnej chwili czasu, może być traktowany jako drzewo grafowe uporządkowane.

13.3.Drzewa i lasy mnogościowe

13.3.1.Lasy „Union - Find”

Relacja równoważnościowa (zwrotna, symetryczna i przechodnia)

Klasy równoważnościowe

Implementacja klas równoważnościowych na lesie mnogościowym

Operacja „Find”

Operacja „Union”

Odsyłaczowa implementacja lasu „Union - Find”

13.3.2.Algorytm Kruskala

(drzewo rozpinające o minimalnym koszcie)

Założenia:

1) graf prosty nieskierowany ważony

2) poszukiwane jest drzewo rozpinające o minimalnym koszcie

Algorytm:

1) Utwórz podgraf wierzchołkowy z wszystkich wierzchołków grafu danego. Przynależność wierzchołków do części spójnych podgrafu rejestruj przy pomocy lasu „Union - Find”.

2) Listę krawędzi grafu danego posortuj według niemalejących wag.

3) Przeglądając sekwencyjnie listę krawędzi włączaj do podgrafu każdą krawędź, incydentną z wierzchołkami należącymi do różnych części spójnych.

4) Realizację algorytmu zakończ po wyczerpaniu listy krawędzi. Otrzymany podgraf będzie poszukiwanym drzewem rozpinającym.

13.3.3.Zastosowania różne

Hierarchie o nieuporządkowanych rodzeństwach

14.Drzewa binarne

14.1.Wprowadzenie

14.1.1.Definicja drzewa binarnego

Drzewo tablicowe, w którym każde rozgałęzienie jest tablicą o dwu działkach.

Adresacja działek: np. 0 - 1, 1 - 2, L - P

Wniosek: węzeł pierwszego stopnia z synem pierwszym

≠ węzeł pierwszego stopnia z synem drugim

14.1.2.Drzewo binarne pełne

Drzewo binarne, w którym każdy poziom zawiera maksymalną liczbę węzłów

Numeracja węzłów poziomami w drzewie binarnym:

14.1.3.Parametry ilościowe w drzewie binarnym pełnym

1) Liczba węzłów na poziomie k: n_k = 2^{k - 1}

2) Ogólna liczba węzłów drzewa o h poziomach: n = 2^k - 1

14.1.4.Drzewo binarne kompletne o n węzłach

Powstaje z drzewa pełnego przez odrzucenie węzłów o numerach > n

Przykład: n = 6

Wniosek: Drzewo binarne kompletne może mieć dowolną liczbę węzłów.

14.1.5.Tablicowa implementacja drzewa binarnego kompletnego

(implementacja poziomami)

Położenia synów węzła o adresie a: a₁ = 2*a; a₂ = 2*a + 1

Położenie ojca węzła o adresie a: a₀ = a div 2

Wnioski:

1) Każda tablica liniowa może być uważana za drzewo binarne kompletne za-implementowane poziomami.

2) Strefa ojców: a ≤ l div 2 ; strefa liści: a > l div 2

14.2.Kopiec i sortowanie kopcowe

14.2.1.Kopiec

(także „stóg”, ang. heap)

Założenia:

1) Dane jest drzewo binarne kompletne o działkach pokrytych przez rekordy.

2) W każdym rekordzie jest jedno pole kluczowe.

Warunek, aby plik jw. był kopcem:

Klucz każdego ojca jest niemniejszy niż klucz któregokolwiek jego syna.

Wnioski:

1) Każde poddrzewo kopca jest kopcem.

2) Klucz korzenia kopca jest maksymalnym kluczem kopca.

14.2.2.Pseudokopiec

Założenia: jak dla kopca

Warunek: Warunek kopca jest spełniony dla wszystkich węzłów oprócz, być może, korzenia.

Wnioski:

1) Każdy kopiec jest pseudokopcem.

2) Każde drzewo spełniające założenia jw. i mające wysokość niewiększą niż 2 jest pseudokopcem.

14.2.3.Przesiewanie pseudokopca

( = operacja przeprowadzająca pseudokopiec w kopiec przez przestawianie jego węzłów)

Algorytm przesiewania:

1) Weź pod uwagę korzeń pseudokopca i tego z jego synów, który ma większy klucz. Jeżeli węzły te naruszają warunek kopca, zamień je miejscami.

2) Dotychczasowy korzeń pseudokopca stał się korzeniem poddrzewa, w którym - być może - narusza warunek kopca. Jeżeli tak jest, zamień go miejscami z sy-nem o większym kluczu.

3) Kontynuuj przemieszczanie korzenia do coraz głębszych poziomów aż przestanie on naruszać warunek kopca albo aż osiągnie pozycję liścia.

14.2.4.Kopcowanie drzewa

( = przekształcanie drzewa binarnego kompletnego spełniającego założenia jw. w kopiec)

Algorytm:

Przeglądaj sekwencyjnie strefę ojców od prawej do lewej. Dla każdego ojca przesiej poddrzewo, którego jest on korzeniem (zauważ, że poddrzewa o wysokości 2 są pseudokopcami na mocy wniosku 2 z p.14.2.2; poddrzewa wyższe są pseudokopcami, ponieważ ich poddrzewa główne zostały kopcami w toku poprzednich działań tego algorytmu). Po dojściu do korzenia drzewo będzie kopcem.

14.2.4.Sortowanie kopcowe

(także „stogowe”, ang. heapsort)

Algorytm:

1) Sortowaną tablicę liniową uważaj za implementację poziomami drzewa binar-nego kompletnego.

2) Przeprowadź sortowaną tablicę w implementację kopca. Zauważ, że w pierwszej działce znajduje się rekord z kluczem maksymalnym.

3) Zamień miejscami pierwszy i ostatni rekord sortowanej tablicy. Rekord, który znalazł się w ostatniej działce, jest na swojej definitywnej pozycji. Wyłącz tę pozycję z dalszego sortowania.

4) Zauważ, że pozostawiona do dalszego sortowania część tablicy stanowi implementację pseudokopca. Przesiej ten pseudokopiec i przejdź do punktu 3 algorytmu.

5) Algorytm kończy działanie, gdy nie posortowana część tablicy osiągnie długość 1.

Ogólna ocena metody:

Złożoność liniowo-logarytmiczna bez niebezpieczeństwa ukwadratowienia.

Statystyczny czas sortowania: około 1,5 qs.

14.3.Rekurencyjne implementacje drzew binarnych na listach

Przykład: wyrażenie a = b / ( c² + d² )

Reprezentacja rysunkowa:

1) Implementacja LKP (infiksowa, wymaga użycia nawiasów albo zastosowania konwencji, zastępującej nawiasy):

b / (( c ** 2 ) + ( d ** 2 ))

2) Implementacja KLP (prefiksowa, zwana notacją Łukasiewicza albo „polską”, nie wymaga użycia nawiasów):

/ b + ** c 2 ** d 2

3) Implementacja LPK (postfiksowa, beznawiasowa, zwana też „odwrotną polską” = IPN = Inverse Polish Notation, szczególnie dogodna przy automatycznym obliczaniu wartości wyrażeń):

b c 2 ** d 2 ** + /

14.4.Implementacje odsyłaczowe

14.4.1.Implementacja o trzech odsyłaczach w rekordzie

(Umożliwia szybkie przechodzenie w dół i w górę drzewa z dowolnego rekordu)

14.4.2.Implementacja o dwóch odsyłaczach w rekordzie

(Wymaga wejścia przez korzeń i notowania przejrzanych węzłów w notatniku stoso-wym)

14.5.Binarne drzewa poszukiwań

(ang. BST = Binary Search Trees)

14.5.1.Wprowadzenie

BST = drzewo binarne o działkach pokrytych przez rekordy; w każdym rekordzie jedno pole kluczowe

Zasady wprowadzania nowego rekordu:

1) Rekord wprowadza się przez korzeń.

2) Rekord o kluczu mniejszym (większym) od klucza rekordu aktualnego kieruje się do lewego (prawego) poddrzewa tego rekordu.

3) Każdy nowo wprowadzony rekord staje się nowym liściem drzewa.

Zasady odszukiwania rekordu o zadanym kluczu wzorcowym:

1) Przeglądać drzewo począwszy od korzenia.

2) Jeżeli klucz wzorcowy jest mniejszy (większy) od klucza rekordu aktualnego, wybierać lewe (prawe) podrzewo.

3) Koniec przeszukiwania (z wynikiem negatywnym) - po dojściu do liścia.

14.5.2.Drzewo binarne zygzakowe

Oprócz jedynego liścia wszystkie węzły są pierwszego stopnia.

Przypadki szczególne: drzewa binarne liniowe (lewoskośne i prawoskośne).

14.5.3.Złożoność przeszukiwania w drzewie BST

Wniosek z zasad wprowadzania nowego rekordu: Kształt drzewa zależy od wartości kluczy we wprowadzanych rekordach oraz od kolejności, w jakiej rekordy są wprowadzane.

Złożoność przeszukiwania dla drzewa liniowego: liniowa

Złożoność przeszukiwania dla drzewa zbliżonego do pełnego: logarytmiczna

Optymalizacja drzewa BST przez sortowanie

14.6.Drzewa AVL

(skrót „AVL” od nazwisk autorów: Adelsona-Velskiego i Landisa)

14.6.1.Drzewa zrównoważone

(ang. balanced, „wyważone”)

Definicja 1: W każdej parze bratnich poddrzew wartość bezwzględna różnicy między ilościami węzłów nie przekracza liczby 1.

Definicja 2 (stosowana w przypadku drzew AVL): W każdej parze bratnich poddrzew wartość bezwzględna różnicy między ich wysokościami nie przekracza liczby 1.

Wniosek: Czas przeszukiwania drzewa zrównoważonego zależy logarytmicznie od ogólnej ilości jego węzłów.

14.6.2.Dynamika drzewa AVL: wprowadzanie rekordu

1) Wprowadź rekord jak w drzewie BST, odnotowując ścieżkę, po której był wpro-wadzany.

2) Przeglądając ścieżkę od końca sprawdzaj zrównoważenie kolejnych węzłów.

3) W przypadku wykrycia węzła niezrównoważonego utwórz z niego i z dwu wę-złów poprzednio przejrzanych (syna i wnuka) „ośrodek rotacji”.

4) Zrealizuj rotację według zasad podanych na następnej planszy. Po wykonaniu rotacji dalsza kontrola zrównoważenia węzłów jest zbędna.

14.6.3.Rotacje LL i LR

Stan przed rotacją:

Stan po rotacji:

Rotacje RL i RR są lustrzanymi odbiciami rotacji jw.

15.Drzewa pozycyjne i listowe

15.1.Drzewa pozycyjne

(ang. trie indexing, prawdopodobnie od „retrieval”)

15.1.1.Założenia dotyczące struktury

1) Drzewo tablicowe. Rekordami pokryte wyłącznie liście.

3) W każdym rekordzie klucz k rozpada się na l zhierarchizowanych kluczy częściowych k₁, k₂, ..., k_i, ..., k_l .

4) Na i - tym poziomie drzewa rozgałęzienie indeksowane jest przez zbiór dopuszczalnych wartości klucza k_i .

15.1.2.Założenia dotyczące dynamiki

1) Nowy rekord wprowadza się przez korzeń.

2) Przez i - ty poziom przeprowadza się rekord, kierując go do poddrzewa indeksowanego przez aktualną wartość klucza k_i .

3) Jeżeli poddrzewo, do którego należałoby wprowadzić rekord, jest puste, należy w tym miejscu utworzyć dla niego poddrzewo elementarne.

4) Po utworzeniu nowego poddrzewa elementarnego proces wstawiania nowego rekordu należy zakończyć.

15.1.3.Implementacja odsyłaczowa

Rekord implementujący węzeł przelotowy na i - tym poziomie powinien być tablicą o działkach indeksowanych przez dopuszczalne wartości klucza k_i . Działki powinny być pokryte przez odsyłacze do korzeni odpowiednich poddrzew.

Rekord implementujący liść może być zredukowany do pola korzenia, pokrytego przez rekord implementowany.

15.1.4.Ogólna ocena i zastosowanie

Drzewo pozycyjne jest strukturą o małym nakładzie czasu na odszukiwanie, ale niezbyt oszczędną, jeżeli chodzi o zapotrzebowanie na pamięć. Bywa zalecane do systemów dialogowych, gdy zachodzi potrzeba szybkiego rozpoznawania wprowadzanych wyrazów.

15.2.Implementacje drzew listowych na listach

15.2.1.Implementacja drzewa o węzłach przelotowych niepustych

Przykład drzewa:

Implementacja listowa:

A(B(F, G), C, D(H, I, J), E)

15.2.2.Implementacja drzewa koronowego

Założenia:

1) Drzewo jak w poprzednim przykładzie

2) Węzły przelotowe puste

Implementacja listowa:

((F, G), C, (H, I, J), E)

15.2.3.Uwaga o implementacjach postfiksowych

Nie stosowane.

15.3.Odsyłaczowe implementacje drzew listowych

5.3.1.Implementacja czteroodsyłaczowa

15.3.2.Implementacja trójodsyłaczowa

Uwaga: Przeglądanie z zastosowaniem tej implementacji ta wymaga:

1) Wejścia do drzewa przez korzeń

2) Prowadzenia stosowego notatnika przejść przez węzły

15.3.3.Implementacja dwuodsyłaczowa

15.3.4.Implementacja dwuodsyłaczowa z bitem powrotu

Wyjaśnienie: W przypadku gdy P = 1 odsyłacz prawy wskazuje na ojca, dlatego nie ma potrzeby prowadzenia notatnika przejść przez węzły.

15.4.Zastosowania drzew listowych

Hierarchie z porządkiem liniowym w każdym rodzeństwie, w szczególności implementacja drzew mnogościowych, sztucznie rozbudowanych o porządki liniowe w rodzeństwach.

16.Struktury grafowe

16.1.Klasyfikacja grafowych struktur danych

16.1.1.Według rodzaju grafu

Grafowa struktura danych może być oparta:

1) na grafie prostym nieskierowanym

2) na grafie prostym skierowanym

3) na multigrafie nieskierowanym

4) na multigrafie skierowanym

16.1.2.Według sposobu wykorzystania grafu

Jako działki podłoża mogą być wykorzystane:

1) wierzchołki grafu ( = struktura wierzchołkowa)

(wtedy krawędzie odgrywają rolę powiązań między działkami)

2) krawędzie grafu ( = struktura krawędziowa)

(np. w grafie ważonym)

3) wierzchołki i krawędzie ( = struktura wierzchołkowo-krawędziowa)

(rolę powiązań odgrywają elementy relacji incydencji)

16.1.3.Według regularności grafu

Podłoże struktury grafowej może być:

1) regularne (np. w przypadku tablicy wielowymiarowej)

2) nieregularne

16.2.Struktury regularne

(por.Turski: „Struktury danych”)

16.2.1.Przykład: tablica trójwymiarowa

16.2.2.Linearyzacja leksykograficzna

(najszybciej zmienia się wskaźnik ostatni):

A(1, 1, 1), A(1, 1, 2), A(1, 2, 1), A(1, 2, 2), ..., A(4, 3, 2)

16.2.3.Linearyzacja antyleksykograficzna

(najszybciej zmienia się wskaźnik pierwszy):

A(1, 1, 1), A(2, 1, 1), ..., A(4, 1, 1), A(1, 2, 1), ..., A(4, 3, 2)

16.3.Macierze niepełne

16.3.1.Wprowadzenie

Macierz = tablica dwuwymiarowa

Linearyzacja leksykograficzna = linearyzacja wierszowa

Linearyzacja antyleksykograficzna = linearyzacja kolumnowa

Macierz niepełna = macierz o dużej liczbie elementów trywialnych (np. działki puste, wyzerowane albo wyspacjowane) lub powtarzających się

16.3.2.Macierz pasmowa

Elementy nietrywialne na przekątni głównej i w pasie symetrycznie rozmieszczonym względem tej przekątni:

16.3.3.Macierze trójkątne

(Część nietrywialna poniżej linii podziału mieści się w części pustej powyżej tej linii)

16.3.4.Macierze symetryczne

Nietrywialna część macierzy symetrycznej jest macierzą trójkątną dużą.

16.3.5.Macierze antysymetryczne

Nietrywialna część macierzy antysymetrycznej jest macierzą trójkątną małą.

16.4.Macierze rzadkie

16.4.1.Definicja i zastosowanie

Macierze o niewielkiej liczbie elementów nietrywialnych (np. kilka procent; macierzami takimi są z reguły macierze adiacencji i macierze incydencji implementujące strukturę grafu).

16.4.2.Implementacja na triadach (trójkach)

Triada = rekord o trzech polach:

i - numer wiersza; j - numer kolumny; A(i, j) - pokrycie działki

Struktura implementująca: lista o działkach pokrytych przez triady

Zaleta: prostota struktury

Wada: uciążliwość przeszukiwania

16.4.3.Implementacja odsyłaczowa

Zalety: elastyczność; łatwość przeglądania wierszami i kolumnami

16.5.Struktury wierzchołkowe oparte na grafach prostych nieskierowanych

16.5.1.Założenia dotyczące wyróżnień

1) Dogodnie jest wprowadzić dwa wyróżnienia wierzchołków: „pierwsze” i „drugie”

2) Jeżeli wierzchołki wyróżnione są sąsiadami, to łącząca je krawędź też będzie uważana za wyróżnioną.

16.5.2.Operacje proste

1) Opróżnianie struktury

2) Dołączanie wierzchołka separowanego

3) Wyróżnianie dowolnego wierzchołka

4) Dołączanie krawędzi między wierzchołki wyróżnione

5) Przenoszenie wyróżnienia na dowolny wierzchołek sąsiedni

6) Zmiana pokrycia wierzchołka wyróżnionego

7) Usuwanie wyróżnionej krawędzi

8) Usuwanie wyróżnionego wierzchołka separowanego

16.5.3.Wybrane operacje złożone

1) Przeglądanie grafu

2) Budowa drzewa rozpinającego

3) Badanie spójności grafu

4) Badanie acykliczności grafu

5) Badanie planarności grafu

6) Poszukiwanie maksymalnego podgrafu pełnego („kliki”)

16.5.4.Przeglądanie w głąb („stosowe”)

(dotyczy grafu spójnego albo części spójnej grafu niespójnego)

1) Wyróżnij dowolny wierzchołek, zamarkuj go jako przeglądnięty i odnotuj w stosowym notatniku.

2) Zbadaj, czy wierzchołek odnotowany na wierzchołku notatnika ma nie zamarkowanego sąsiada. Jeżeli ma, wyróżnij go, zamarkuj i odnotuj w notatniku.

3) Kontynuuj czynność z punktu (2) aż okaże się, że wierzchołek grafu odnotowany na wierzchołku stosu nie ma nie zamarkowanego sąsiada. Strąć wtedy bezużyteczną notatkę z wierzchołka stosu i wróć do punktu (2).

4) Realizacja algorytmu kończy się z chwilą opróżnienia stosu.

16.5.5.Przeglądanie wszerz („kolejkowe”)

(również do grafu spójnego)

Jak przeglądanie w głąb z tą różnicą, że nowo zamarkowane wierzchołki odnotowuje się na końcu notatnika kolejkowego, a przejścia na nowy wierzchołek dokonuje się na podstawie notatki umieszczonej na początku tego notatnika.

16.5.6.Budowa drzewa rozpinającego oparta na przeglądaniu w głąb lub wszerz

Do drzewa należy włączać wszystkie kolejno markowane wierzchołki i wszystkie efektywnie wykorzystane krawędzie. Przez krawędź efektywnie wykorzystaną należy rozumieć krawędź, przez którą nastąpiło przejście z poprzednio zamarkowanego wierzchołka na wierzchołek nowo markowany.

Nietrudno zauważyć:

1) że zarówno w przypadku przeglądania tak stosowego jak i kolejkowego kształt drzewa rozpinającego zależy od zasady, według której wybiera się nie zamarkowanego sąsiada w przypadku, gdy takich sąsiadów jest więcej niż jeden;

2) że drzewo rozpinające budowane w oparciu o przeglądanie stosowe jest zwykle bardziej smukłe niż drzewo budowane w oparciu o przeglądanie kolejkowe.

16.5.7.Implementacja tablicowa z zastosowaniem macierzy adiacencji

1) Ustal maksymalną dopuszczalną liczbę wierzchołków N w implementowanym grafie

2) Utwórz tablicę liniową W o długości N. W działkach tej tablicy umieść reprezentacje wierzchołków grafu implementowanego.

3) Utwórz macierz kwadratową A o boku N (będzie to macierz adiacencji grafu imple-mentowanego). Zarówno wiersze jak i kolumny tej macierzy powinny być indeksowane przez wierzchołki implementowanego grafu. Każda działka macierzy powinna mieć pojemność 1b.

4) Do działki A(i, j) macierzy A wpisz 1, jeżeli i - ty wierzchołek grafu implementowanego jest adiacentny z wierzchołkiem j - tym. W przeciwnym razie wpisz do działki 0.

Wnioski:

1) Istotnym utrudnieniem, wprowadzanym przez implementację tablicową, jest konieczność wprowadzania górnego ograniczenia liczby wierzchołków implementowanego grafu.

2) Ponieważ relacja adiacencji jest symetryczna, symetryczna jest też macierz A ( A(i, j) = A(j, i) ).

3) W przypadku grafu pełnego macierz A jest w całości pokryta przez jedynki. W przypadku przeciętnym (np. kilkadziesiąt wierzchołków, każdy ma kilku sąsiadów) A będzie macierzą rzadką.

16.5.8.Implementacja z zastosowaniem listy krawędzi

1) Utwórz listę W (lista wierzchołków). Element W(i) listy W powinien reprezentować i - ty wierzchołek implementowanego grafu.

2) Utwórz listę K (lista krawędzi), której każdy element będzie odpowiadał jednej z kra-wędzi implementowanego grafu. Krawędź, łącząca wierzchołek i - ty z j - tym powinna być w liście K reprezentowana przez rekord o dwu polach; pierwsze z tych pól powinno zawierać odsyłacz p(i) do elementu W(i), drugi - odsyłacz p(j) do elementu W(j) listy W. Każda krawędź powinna być w liście K reprezentowana jednokrotnie, bądź to jako para (p(i), p(j)), bądź jako para (p(j), p(i)).

Wniosek:

Jest oczywiste, że przypadkowa na ogół kolejność elementów w liście K nie sprzyja szyb-kiemu odszukiwaniu sąsiadów danego wierzchołka. Przeszukiwanie to musi - w ogólnym przypadku - objąć wszystkie elementy tej listy, a w obrębie danego elementu - obydwa pola.

16.5.9.Implementacja z listami sąsiadów

Po utworzeniu listy W jak w poprzednio omówionej implementacji dołącz do każdego elementu W(i) tej listy listę odsyłaczy do tych jej elementów, które reprezentują sąsiadów i - tego rekordu implementowanego grafu.

Ocena ogólna:

Rozwiązanie wymaga utrzymywania wielu pomocniczych list sąsiadów, ale umożliwia szybkie dotarcie do każdego z nich, co jest istotną zaletą tej implementacji z punktu widzenia potrzeb algorytmu przeglądania grafu.

Ćwiczenie:

Zaleca się uzupełnienie ostatnio zreferowanej metody tak, aby mogła ona służyć do implementacji nie tylko danego grafu, ale także jedego z jego rozpinających drzew.

16.6.Struktury wierzchołkowe oparte na grafach prostych skierowanych

16.6.1.Operacje proste

Jak dla grafów nieskierowanych z tą różnicą, że w przypadku wstawiania nowej krawędzi między wierzchołki v₁ i v₂ należy odróżnić podprzypadek wstawiania krawędzi (v₁, v₂) od podprzypadku wstawiania krawędzi (v₂, v₁). Podobnie krawędź (v₁, v₂) należy odróżnić od krawędzi (v₂, v₁) w przypadku kasowania krawędzi wstawionej między wyróżnione wierzchołki v₁ i v₂.

16.6.2.Implementacja z zastosowaniem tablicy adiacencji

Jak dla grafów nieskierowanych z tą różnicą, że działkę A(i, j) macierzy A należy traktować jako odpowiednik uporządkowanej pary (v_i, v_j), różnej od uporządkowanej pary (v_j, v_i). Macierz A tym samym nie musi już być symetryczna.

16.6.3.Implementacja z zastosowaniem listy krawędzi

Odróżniając pary (v_i , v_j ) od par (v_j , v_i ) należy w liście K wprowadzić zasadę, że pierwsze pole w rekordzie pokrywającym działkę listy odnosi się do początku danej krawędzi, a drugie do jej końca.

16.6.4.Implementacja z listami sąsiadów

Do każdego elementu listy W należy dołączyć dwie listy odsyłaczy do rekordów reprezentujących wierzchołki sąsiednie, a mianowicie listę odsyłaczy do sąsiadów lewostronnych oraz listę odsyłaczy do sąsiadów prawostronnych. Można też pozostawić jedną listę sąsiadów, wprowadzając do każdego jej elementu dwubitowe pole techniczne informujące, czy w danym przypadku chodzi o sąsiada lewo-, prawo-, czy obustronnego.

16.7.Struktury wierzchołkowo-krawędziowe oparte na grafach prostych skierowanych

16.7.1.Wprowadzenie

Wierzchołki grafu implementowanego powinny być reprezentowane przez rekordy, pokrywające działki tablicy lub listy W; krawędzie powinny być reprezentowane przez rekordy pokrywające działki tablicy lub listy K. Incydencje między wierzchołkami a kra-wędziami mogą być reprezentowane przez macierz incydencji albo przez odsyłacze do incydentnych krawędzi lub wierzchołków.

16.7.2.Macierz incydencji

Załóżmy prostokątną macierz incydencji I o wierszach indeksowanych przez wierzchołki i kolumnach indeksowanych przez krawędzie grafu implementowanego. Działka I(i, j) tej macierzy, należąca do jej i - tego wiersza i j - tej kolumny, powinna zawierać informację, czy wierzchołek v_i i krawędź k_j są ze sobą incydentne oraz jaka jest orientacja tej incydencji (ujemna czy dodatnia, tj. czy v_i jest początkiem czy końcem k_j). Łatwo zauważyć, że wystarczą tu trzy dopuszczalne wartości pokrycia działki I(i, j), np. 1 dla incydencji ujemnej, 2 dla dodatniej i 0 dla braku incydencji.

16.7.3.Rozszerzona lista krawędzi

O elemencie K(j) listy K można założyć, że oprócz reprezentacji krawędzi k_j zawiera on odsyłacze do tych elementów listy W, które reprezentują początek i koniec tej krawędzi. Rozszerzenie takie umożliwia szybkie przejście z krawędzi na incydentne z nią wierzchołki, natomiast przejście odwrotne, tzn. z wierzchołka na incydentną krawędź wymaga tu przeglądnięcia obydwu odsyłaczy we wszystkich elementach listy K.

16.7.4.Listy krawędzi incydentnych

Poprzednio omówioną implementację można rozszerzyć o dołączone do każdego elementu W(i) listy W dwie listy odsyłaczy: do elementów listy K odpowiadających krawędziom ujemnie bądź dodatnio incydentnym z wierzchołkiem v_i. Uzupełnienie takie umożliwia szybkie przechodzenie z rekordu wierzchołka na rekordy incydentnych krawędzi.

16.8.Struktury wierzchołkowo-krawędziowe oparte na multigrafach skierowanych

16.8.1.Wprowadzenie

Nowościami w stosunku do grafów prostych, jakie dopuszcza multigraf skierowany, są:

1) dopuszczalność krawędzi zapętlonych oraz

2) dopuszczalność krawędzi zgodnie równoległych.

Należy zwrócić uwagę, że w stosunku do wierzchołka, będącego równocześnie jej początkiem i końcem, krawędź zapętlona wykazuje jednocześnie dwa rodzaje incydencji: ujemną i do-datnią.

16.8.2.Implementacja krawędzi zapętlonej w przypadku posłużenia się macierzą incydencji

Zbiór dopuszczalnych pokryć działki macierzy należy rozszerzyć o nową wartość (np. 3), oznaczającą podwójną incydencję.

16.8.3.Implementacja krawędzi zapętlonej w przypadku posłużenia się listami krawędzi incydentnych

Krawędź podwójnie incydentną można umieszczać jednocześnie na liście krawędzi incy-dentnych ujemnie i na liście krawędzi incydentnych dodatnio, albo też można utworzyć przy rekordzie wierzchołka trzecią listę, tzn. listę krawędzi podwójnie incydentnych.

16.8.4.Krawędzie zgodnie równoległe

Poprzednio omówione rozwiązania, dotyczące implementacji struktur opartych na grafach skierowanych prostych umożliwiają implementację krawędzi zgodnie równoległych w strukturach opartych na multigrafach bez jakichkolwiek nowych komplikacji.

=====

17.Dane w pamięci niejednorodnej

17.1.Wprowadzenie

17.1.1.Pamięć operacyjna

Struktura zapisu:

Tablica liniowa adresowana

Dynamika dostępu:

Czas przejścia jest krótki i nie zależy od adresów bieżącego i docelowego.

Zastosowanie:

Wykorzystanie pamięci operacyjnej jest konieczne przy operacjach wykorzystujących pamięć zewnętrzną.

17.1.2.Pamięć taśmowa

Struktura zapisu:

Standard fizyczny: szerokość taśmy 1/2”, 9 ścieżek ( 1 B + kontrola parzystości), gęstość podłużna np. 32 rządki/mm, prędkość odczytu i zapisu np. 4 m/s, długość taśmy na rolce np. 720 m.

Przerwa międzyblokowa (o długości np. 20 mm), przewidziana na hamowanie, postój i rozbieg układu głowic powoduje, że efektywna podłużna gęstość zapisu waha się między około 0 do blisko 100 %.

Długość bloku determinowana jest przez pojemność buforów wyjściowego i wejścio-wego.

Dynamika dostępu:

Czas przejścia jest w przybliżeniu proporcjonalny do odległości między blokami aktualnym i docelowym i może się wyrażać w dziesiątkach sekund, a nawet w minutach.

Zastosowanie:

Praktycznie zredukowane do roli pamięci archiwalnej.

17.1.3.Pamięć dyskowa

Struktura zapisu:

Tablica wielowarstwowa, adres - w ogólnym przypadku - hierarchiczny pięcio-członowy. Człony adresu:

1) oznaczenie pakietu wymiennego albo jednostki napędowej

2) numer cylindra w obrębie pakietu

3) numer ścieżki w obrębie cylindra

4) numer sektora w obrębie ścieżki

5) numer jednostki podstawowej (np. bajtu) w obrębie sektora

Dynamika dostępu:

Czas przełączenia na inną jednostkę napędową albo na inną ścieżkę w obrębie tego samego cylindra jest pomijalnie mały.

Czas przejścia grzebienia głowic na inny cylinder jest rzędu 0,1 s.

Czas oczekiwania na żądany sektor waha się od zera do czasu pełnego obrotu pakietu, wartość średnia = czas półobrotu pakietu, rząd wielkości 0,01 s.

Zalecenia:

1) Unikać rozmieszczania pliku na kilku różnych cylindrach tej samej jednostki napędowej.

2) Unikać częstych dostępów dla wyeliminowania wielokrotnych oczekiwań.

3) Dążyć do obejmowania jednorazową transmisją możliwie dużej ilości potrzebnych danych.

Zastosowanie:

Podstawowy rodzaj pamięci masowej o względnie krótkim czasie dostępu.

17.2.Pamięć taśmowa

17.2.1.Uwaga wstępna

Pamięć taśmowa była w przeszłości podstawowym rodzajem pamięci masowej. Niektóre algorytmy, opracowane dla pamięci taśmowej, mają obecnie zastosowanie także w od-niesieniu do pamięci dyskowej.

17.2.2.Dopisywanie i kasowanie informacji

Dopisywanie nowych informacji do taśmy i kasowanie tych informacji dopuszczalne jest tylko na końcu aktualnego zapisu.

17.2.3.Modyfikacja zapisów

Modyfikacja informacji zapisanych na taśmie może być realizowana tylko w trybie transak-cyjnym.

17.3.Sortowanie taśmowe

17.3.1.Wprowadzenie

Sortowanie taśmowe obejmuje dwa etapy:

1) etap tworzenia (możliwie długich) serii początkowych,

2) etap scalania serii.

17.3.2.Tworzenie serii początkowych metodą buforową

1) Utwórz w pamięci operacyjnej możliwie duży bufor sortowania.

2) Napełnij bufor rekordami z czoła taśmy wejściowej.

3) Posortuj zawartość bufora dowolną dobrą metodą (np. „Quicksort” lub „Heapsort”)

4) Wyprowadź posortowane rekordy na taśmę wyjściową.

5) Powtarzaj punkty (2) - (4) jak wyżej do wyczerpania taśmy wejściowej.

Uwaga: Serie początkowe tworzone metodą buforową mają jednakową objętość, równą pojemności bufora sortowania.

17.3.3.Tworzenie serii początkowych metodą przelotową

1) Utwórz w pamięci operacyjnej możliwie duży bufor sortowania.

2) Napełnij bufor rekordami z czoła sortowanego pliku.

3) Z rekordów umieszczonych w buforze sortowania utwórz kopiec odwrócony (tj. z kluczem minimalnym w korzeniu)

4) Na taśmę wyjściową wyprowadzaj rekord z korzenia kopca umieszczonego w buforze bądź z czoła taśmy wejściowej kierując się zasadą, że klucz rekordu przenoszonego na wyjście powinien być niemniejszy niż klucz poprzednio wyprowadzonego tam rekordu, ale poza tym jak najmniejszy.

5) Jeżeli rekord z korzenia kopca wyprowadziłeś na wyjście, wprowadź do korzenia rekord z taśmy wejściowej i przesiej otrzymany w ten sposób pseudokopiec.

6) Jeżeli zarówno w korzeniu kopca jak i na czole taśmy wejściowej występują klucze mniejsze niż klucz ostatnio wyprowadzonego rekordu, wybierz mniejszy z tych kluczy i rozpocznij nim nową serię.

7) Kontynuuj algorytm aż do wyczerpania pliku wejściowego.

Uwaga: Serie początkowe tworzone metodą przelotową mają niejednakową objętość, na ogół większą jednak od pojemności bufora sortowania.

17.3.4.Scalanie na trzech taśmach z redystrybucją

17.3.5.Scalanie na czterech taśmach bez redystrybucji

17.4.Scalanie taśmowe wielofazowe

17.4.1.Ciąg Fibonacciego

F₀ = 0; F₁ = 1; F_k = F _{k - 1} + F_{k - 2} ( dla k = 2, 3, ...)

Wniosek: F_k = F _{k + 2} - F_{k + 1} ( dla k = 0, 1, 2, ...)

Piersze wyrazy ciągu: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89

17.4.2.Scalanie wielofazowe

1) Dopełnij ciąg serii początkowych seriami pustymi tak, aby ogólna liczba serii N była liczbą Fibonacciego F_n .

2) Podziel zbiór serii tak, aby w pierwszej części znalazło się F_{n - 1} serii, a w drugiej F_{n - 2} . Nagraj pierwszą część na taśmę A, a drugą na taśmę B.

3) Scalaj jedną serię z taśmy A z jedną serią z taśmy B aż do opróżnienia taśmy B. Serie scalone lokuj na taśmie C. Po ukończeniu scalania na taśmie A pozostanie F_{n - 3} serii, na taśmie C będzie ich F_{n - 2} , a taśma B będzie oczywiście pusta.

4) Powtarzaj scalanie serii z dwóch niepustych taśm na trzecią początkowo pustą aż do uzyskania jednej serii, tzn. zmonotonizowanego pliku.

17.4.3.Przykład

N = 144. Na taśmę A nagrywam 89 serii, na taśmę B - 55. Liczby serii na poszczególnych taśmach po ukończeniu kolejnych faz będą się przedstawiały jak poniżej:

Taśma L i c z b y s e r i i

A 89 34 - 21 8 - 5 2 - 1 -

B 55 - 34 13 - 8 3 - 2 1 -

C - 55 21 - 13 5 - 3 1 - 1

17.5.Sortowanie dyskowe

17.5.1.Wprowadzenie

1) Sortowanie dyskowe przebiega jak taśmowe z tą różnicą, że dla przyspieszenia scalania zaleca się, aby było to scalanie wielostrumieniowe.

2) W przypadku scalania wielostrumieniowego zaleca się, aby dla przyspieszenia poszukiwań minimalnego klucza w zbiorze czołowych rekordów poszczególnych strumieni wejściowych wspomóc się zastosowaniem drzewa turniejowego.

17.5.2.Drzewo turniejowe

(ang. tournament tree)

W przypadku wielostrumieniowego scalania jest to drzewo binarne pełne, w którym:

1) liście pokryte są przez klucze czołowych rekordów poszczególnych strumieni wejś-ciowych;

2) klucz ojca jest równy mniejszemu z kluczy synów.

Zastosowanie drzewa turniejowego do odszukiwania rekordu czołowego z minimalnym kluczem: rozpoczynając od korzenia przechodź na syna z mniejszym kluczem, aż doj-dziesz do liścia.

Korektura drzewa po przeniesieniu wybranego rekordu do strumienia wyjściowego: wystarczy sprawdzać i korygować węzły na ścieżce promieniowej od liścia, w którym nastąpiła wymiana, do korzenia.

17.6.Pamięć dyskowa: sieci odsyłaczowe

17.6.1.Uwaga wstępna

Ze względu na długi zazwyczaj okres przechowywania zapisów dyskowych i wynikające stąd ryzyko ich sprzętowego lub programowego uszkodzenia zaleca się, aby tworzone na dyskach sieci odsyłaczowe wyposażane były w nadmiarowe powiązania zabezpiecza-jące.

17.6.2.Przykłady powiązań zabezpieczających

1) Długodystansowe powiązania zabezpieczające w łańcuchu lub pierścieniu odsyłaczowym

2) Drzewo nizane (HS, str.239; ang. threaded tree), w którym puste pola odsyłaczowe wykorzystuje się na zabezpieczające odsyłacze do sąsiadów w porządku infiksowym

17.7.Pamięć dyskowa: tablice rozproszone

17.7.1.Uwaga wstępna

Zaleca się, aby dla uniknięcia częstych transmisji małych ilości danych stosować sekcyjną organizację tablic rozproszonych.

17.7.2.Tablica rozproszona: organizacja sekcyjna

Sekcyjna organizacja tablicy rozproszonej polega:

1) na zgrupowaniu działek tablicy w jednakowej wielkości sekcje, rozmiarem zbliżone do optymalnej objętości jednorazowo transmitowanej porcji informacji

2) na przejściu z adresowego dostępu do działki na adresowy dostęp do sekcji i sekwenyjny dostęp do działki w obrębie sekcji

17.8.Pamięć dyskowa: drzewa Bayera

(„B-drzewa”, por. Wirth, „Algorytmy + struktury”, str.257)

17.8.1.Struktura drzewa

1) Węzeł drzewa Bayera n - tego stopnia jest tablicą o 2n „dużych” działkach, zawierającą n_r monotonicznie uszeregowanych rekordów r(1), r(2), ..., r(n_r) z kluczami - kolejno - k(1), k(2), ..., k(n_r). Dla korzenia drzewa powinno być przy tym 1 ≤ n_r ≤ 2n , dla pozostałych węzłów - n ≤ n_r ≤ 2n .

2) Oprócz działek dużych węzeł przelotowy drzewa powinien zawierać n_r + 1 działek „małych”, rozmieszczonych jak na poniższym rysunku, przy czym działka mała, umieszczona między działkami z rekordami r(i) i r(i +1), powinna zawierać odsyłacz do korzenia poddrzewa mieszczącego rekordy o kluczach z przedziału ( k(i), k(i +1) ).

3) Stopień drzewa powinien być tak dobrany, aby objętość węzła była zbliżona do optymalnej objętości jednorazowo transmitowanej porcji informacji.

17.8.2.Dynamika drzewa

Z dynamiką drzewa Bayera (przeszukiwanie drzewa, wprowadzanie nowego rekordu i usu-wanie rekordu uprzednio wprowadzonego) studenci powinni się zapoznać według powyżej cytowanej monografii N.Wirtha.

17.8.3.Ocena ogólna

Struktura i dynamika drzew Bayera jest trafnie dobrana do technicznych warunków współpracy między pamięcią operacyjną a pamięcią dyskową, w związku z czym drzewa te są chętnie stosowane jako środek organizacji dużych plików, służących do przechowywania i odszukiwania rekordów jednakowego typu.

17.9.Pliki indeksowe

17.9.1.Wprowadzenie

W przypadku dużych plików korzystne jest ograniczenie poszukiwania do indeksu (skorowidza), w którym przechowywane są tylko klucze rekordów oraz adresy, pod którymi przechowywane są same rekordy.

17.9.2.Indeksy pierwotne i wtórne

Klucz pierwotny = klucz rozmieszczenia

Klucze wtórne = pozostałe klucze

Indeks pierwotny (wtórny): indeks, w którym poszukuje się adresu rekordu na podstawie jego klucza pierwotnego (wtórnego)

Objętość indeksu pierwotnego może być znacznie mniejsza niż objętość indeksu wtórnego, jeżeli indeks ten ogranicza się do ewidencji sekcji pliku głównego

Sumaryczna objętość indeksów przewyższa niekiedy objętość pliku głównego.

17.9.3.Organizacja indeksu

1) Monotoniczna

2) Algorytmiczna

3) Wielostopniowa

18.Kompresja danych

18.1.Wprowadzenie

18.1.1.Terminologia

1) Łac.: comprim*re = ścieśniać, sprężać; compressio = ścieśnianie

Pol.: komprymować; kompresja

Słowa pochodne: dekompresja, kompresor, dekompresor

(W informatyce także: upakowywać, rozpakowywać)

2) Łac.: codex = książka

Ang.: code = kod; symbol kodowy

Terminy pochodne: długość kodu; długość symbolu kodowego

18.1.2.Przedmiot kompresji

1) Teksty (znakowe; numeryczne)

2) Obrazy

3) Obrazy animowane i filmy

4) Dźwięki i filmy dźwiękowe

18.1.3.Cele kompresji

1) Oszczędność pamięci

2) Oszczędność kosztów transmisji

18.1.4.Koszty kompresji

Koszty kompresji i dekompresji

18.1.5.Straty w procesie kompresji

Kompresja bezstratna (ang. lossless)

Kompresja stratna (ang. lossy)

18.2.Kompresja tekstów

18.2.1.Środki kompresji

1) Eliminacja obszarów pustych

2) Eliminacja powtórzeń

3) Kody oszczędzające pamięć

4) Kody o zmiennej długości symbolu

5) Kody specjalne

18.2.2. Kody oszczędzające pamięć

Kody alfanumeryczne siedmiobitowe

Kody alfanumeryczne pięciobitowe

Kody z przesunięciami (ang. shift, np. ICL-1900: przesunięcia trwałe α i β , przesunięcie dla jednego znaku δ )

Kody z przesunięciami A i N („alfabetyczne” i „numeryczne”, np. w pięciobitowym kodzie dalekopisowym długość kodu = (32 - 2) * 2 = 60)

18.2.3.Kody o zmiennej długości symbolu

( = kody Huffmana)

Statystyka częstości występowania znaków

Zakaz prefiksowania się symboli

Statystyczna ocena oszczędności pamięci

18.2.4.Kody specjalne

Kody specjalne jednobajtowe (długość do 256 symboli)

Kody specjalne dwubajtowe (długość do 64K symboli)

18.3.Kompresja obrazów

(wg Levine J.: „Programowanie plików graficznych”, 1994)

18.3.1.Kodowanie obrazu bez kompresji

Palety: 2; 16; 256 kolorów ( = 1; 4; 8 bitów/piksel; „pełne kolory” = 24 b/px)

18.3.2.Kompresja z licznikami powtórzeń

(Levine, str.32, format PackBits)

Zapis obrazu składa się z zapisów dwojakiego rodzaju:

1) Zmiennej długości zapis nie komprymowanego ciągu bajtów:

Jeżeli pierwszy bit pierwszego bajtu zapisu ma wartość 0 (tzn. wartość bajtu p = 0...127), to l = p + 1 odczytuje się jako długość nie komprymowanego ciągu bajtów następujących bezpośrednio po nim.

2) Dwubajtowy zapis komprymowanego ciągu powtarzających się bajtów

Jeżeli pierwszy bit pierwszego bajtu zapisu ma wartość 1 (tzn. wartość bajtu p = 128...255), to r = 257 - p odczytuje się jako licznik długości ciągu powtórzeń bajtu następującego bezpośrednio po nim.

18.3.3.Kompresja słownikowa

(Levine, str.245, format LZW)

Kod słownikowy LZW (Levine, str.34: od nazwisk Lempel, Ziv i Welch) buduje słownik „w locie” podczas czytania danych wejściowych.

Zasady ogólne:

1) Słownik jest ciągiem par (symbol ciągu, ciąg)

2) Do słownika wprowadzane są:

a) ciągi o długości jednego piksela

b) ciągi dłuższe, które w komprymowanym obrazie wystąpiły co najmniej raz, pod warunkiem, że poprzednio wprowadzony został do słownika prefiks główny danego ciągu

3) Ciąg pikseli zapisywany jest w słowniku w postaci pary (symbol prefiksu głównego, ostatni piksel ciągu)

Odszukiwanie ciągu w słowniku: tablica rozproszona

18.3.4.Kompresja JPEG

(Levine, str.408; Joint Photographic Experts Group)

Stratna; przeznaczona do cyfrowo reprezentowanych kolorowych fotografii

Statystyczna średnia współczynnika kompresji: ok. 1 b/px

Etapy:

1) Obliczenie luminancji i chrominancji pikseli:

- zakłada się, że obraz wejściowy zapisany jest w telewizyjnym standardzie RGB (Red, Green, Blue)

- dla każdego piksela oblicza się luminancję Y oraz chrominancję niebieską C_b i czerwoną C_r (liniowe przekształcenie składowych RGB)

- rozdziela się dalszą obróbkę obrazu na obróbkę obrazów częściowych Y, C_b i C_r

- dzieli się obrazy C_b i C_r na bloki o wymiarach 2*2 piksele i uśrednia chrominancje w obrębie każdego z tych bloków (*)

2) Dyskretna transformacja kosinusowa (DCT, Discrete Cosine Transform):

- każdy blok 8*8 elementów obrazu częściowego rozkłada się na składową stałą i 63 harmoniczne przestrzenne

3) Kwantyzacja (**):

- kwantuje się amplitudy harmonicznych, ograniczając pamięć potrzebną do ich zapisu

4) Kompresja końcowa:

- komprymuje się ciągi zer metodą licznikową

- pozostałe zapisy komprymuje się np. metodą Huffmana

Objaśnienie:

(*) Częściowa utrata informacji dotyczącej kolorów

(**) Główny czynnik kompresji, ale także i utraty informacji

18.3.5.Przykład skutków kwantyzacji JPEG

(B.C.Smith, „Multimedia Systems”, 1995, Topic 5)

1) Kompresja 9,6 : 1

2) Kompresja 98 : 1

18.4.Kompresja obrazów ruchomych i dźwięku

18.4.1.Obrazy ruchome wieloplanowe („2,5-wymiarowe”)

W przypadku kilku wzajemnie przesłaniających się planów komprymować każdy plan osobno. W czasie dekompresji uwzględniać priorytety poszczególnych planów.

18.4.2.Standard H.261

(B.C.Smith jw., Topic 5, str.15)

Opracowany w latach 1988 - 1990 przez CCITT (Comit* Consultatif International de T*l*graphie et T*l*phonie, Międzynarodowy Komitet Konsultacyjny dla Telegrafii i Telefonii) z przeznaczeniem dla wideokonferencji i wideotelefonii

W zakresie wizji wykorzystuje:

1) standard JPEG (bloki Y, C_b i C_r , dyskretną transformację kosinusową oraz kwantyzację jej wyników)

2) kodowanie różnicowe

3) predykcję ruchu

18.4.3.Standard MPEG

(B.C.Smith jw., Topic 6, str.9)

Opracowany ok. roku 1990 przez Motion Picture Experts Group z przeznaczeniem dla kom-presji wizji i fonii filmów dźwiękowych

W zakresie fonii:

1) Przekształca zapis na częstotliwościowy, stosując szybką transformację Fouriera (FFT)

2) Rozbija analizowane pasmo na 32 częściowe pasma „krytyczne”

2) Eliminuje pasma charakteryzujące się niską energią

3) Komprymuje zapis, stosując jego kwantyzację

28

---