Algorytmy i Struktury Danych

Ćwiczenia 1

rok I, kierunek informatyka

WSB-NLU w Nowym Sączu

Rozpoczniemy od przypomnienia prostych algorytmów sortowania. Wszystkie one charakteryzują się złożonością rzędu O(n2).

Ćwiczenie 1

Zrealizować i przetestować następujące wersje algorytmu sortowania bąbelkowego

Zakładamy, że dana jest tablica t[] rozmiaru n.

Wersja I

Algorytm

1 for (i=0; i < n-1; i++)

2    for(j = 1; j < n; j++)

3       if (t[j-1] > t[j])

4          t[j] <-> t[j];

·         Ile razy wykonuje się dla tablicy rozmiaru n porównanie z linii 3?

·         Czy zamiana n-1 na n w linii 1 spowoduje błędne działanie algorytmu?

·         Co należy zrobić, aby algorytm sortował tablicę w odwrotnej kolejności (od największych wartości do najmniejszych). Czy wystarczy w tym celu zamiana nierówności t[j-1] > t[j] na t[j-1] > t[j] w linii 3?

Wersja II

Łatwo zauważyć, że druga pętla for niepotrzebnie za każdym razem zawsze dochodzi do końca tablicy. Można ją zawsze „skrócić” o 1 po wykonaniu się kolejnego kroku zewnętrznej pętli for.

Algorytm

1 for (i=0; i < n-1; i++)

2    for(j = 1; j < n - i; j++)

3       if (t[j-1] > t[j])

4          t[j] <-> t[j];

·         Ile razy wykonuje się dla tablicy rozmiaru n porównanie z linii 3?

·         Dodać zmienną licznik umieszczając ją pomiędzy linią 1 a 2 (tak aby zliczać wszystkie porównania), która będzie zwiększana o 1

Wersja III

Zauważmy, że usprawnienie z Wersji II nie uwzględnia faktu, że w ostatnim obiegu „bąbelek” mógł być przesunięty znacznie bliżej niż do miejsca o indeksie n-i+1. Aby efektywnie wykorzystać informację do którego miejsca jest sens próbować w następnym obiegu, powinniśmy zapamiętywać pozycję ostatniej faktycznej zamiany, i w następnym obiegu próbować nie dalej niż do tej pozycji minus 1.

Algorytm

1   last = n;

2   for (i=0; i < n-1; i++) {

3      k = last;

4      for (j=1; j < k; j++)

5         if (t[j-1] > t[j]) {

6            last = j;

7            t[j-1] <-> t[j];

8         }

9   }

·         Zauważmy, ze teraz nie możemy już tak łatwo policzyć ile porównań będzie wykonywanych w linii, gdyż to jak „głęboko” w tablicę wchodzi za każdym razem druga pętla for z wiersza 4 zależy od rozkłady danych w tablicy.

·         Obliczyć eksperymentalnie złożoność tego algorytmu i porównać z funkcjami

Ćwiczenie 2

Przypomnieć sobie i przetestować algorytm sortowania przez wybieranie

Algorytm:

1 for (i=0; i < n-1; i++) {

2               k = i; x = t[i];

3        for (j=i+1; j < n; j++)

4           if (t[i] < t[k])

5                                          k = j; // zapamiętanie indeksu kandydata na najmniejszy element

   // ustawienie kolejnego najmniejszego na pozycji t[i]

6               t[i] = t[k];

7               t[k] = x;

8 }

·         Jaka jest złożoność tego algorytmy?

·         Napisać wersją, która będzie sortowała w odwrotnej kolejności

Ćwiczenie 3

Przypomnieć sobie i przetestować algorytm sortowania przez wstawianie. Podstawowa idea jest następująca

for (i=1; i < n; i++){

              x = t[i];

              Wstaw x w odpowiednie miejsce w kawałku t[0]...t[i];

}

Wersja I (bez wartownika)

Algorytm

1 for (i=1; i < n; i++) {

2               x = t[i]; j = i;

3      while (j > 0 && t[j-1] < x) {  

4         t[j] = t[j-1];

5         j = j - 1;

6      }

7      t[j] = x;

8   }

·         Obliczyć optymistyczną i pesymistyczną złożoność tego algorytmu. Dodać licznik porównań, które mają miejsce w linii 3. Dla wielu losowych tablic wykonać obliczenie średniej złożoności i porównać z funkcjami

·         Przeanalizować tablice:

1.  t[] = {1,2,3,4,5,6,7}

2.  t[] = {7,6,5,4,3,2,1}

Jak się zachowuje algorytm sortowania przez wstawianie dla tych tablic?

Wersja II ( z wartownikiem)

Musimy w tablicy zarezerwować dodatkową pozycję [0] na samym początku tablicy. Tak więc efektywny obszar tablicy do przechowywania danych to t[1,...,n-1].

Algorytm

1 for (i=1; i < n; i++) {

2               x = t[i]; t[0] = x; j = i;

3               while (t[j-1] < x)) {  

4                             t[j] = t[j-1];

5                             j = j - 1;

6              }

7               t[j] = x;

8 }

·         Zauważmy, ze liczba porównań wykonywanych w wierszu 3 zależy od rozkładu danych w tablicy. Jaki jest przypadek optymistyczny i pesymistyczny

·         Napisać algorytm, w którym wartownika obliczamy tylko raz na samym początku i wstawiamy na pozycję [0]. Najlepiej jako takiego wartownika wybrać element najmniejszy w tablicy.

Wersja II (wstawianie połówkowe)

Podstawowy algorytm wstawiania można łatwo poprawić. Zauważmy mianowicie, że ciąg wynikowy t[0], ... t[i-1], w którym należy umieścić kolejny element(t[i]), jest już uporządkowany. W związku z tym można zastosować metodę przeszukiwania połówkowego do znajdowania miejsca gdzie należy wstawić element t[i].

Algorytm

1   for (i=1; i < n; i++) {

2      x = t[i]; left = 0; right = n-1;

3      while (left £ right) {

4         m = (left + right)/2;

5         if (x < t[m]) right = m-1;

6         else left = m+1;

7      }

8      for (j=i-1; j ³ left; t[j+1] = t[j];

9      t[left] = x;

10   }

Ćwiczenie 4

Dane są xÎ R (liczba rzeczywista) oraz nÎ N (liczba naturalna). Napisać algorytm obliczający potęgę xn.

Wersja I (najprostsza)

xn = x×...×x (n razy)

Można więc zrealizować prostą pętlę.

Algorytm

1 pow = 1;

2 for(i=0; i < n; i++)

3               pow = pow*x;

4 printf(pow);

·         Przeanalizować, czy algorytm porwanie się zachowuje w skrajnych przypadkach (dla n=0 i dla n=1)

·         Ile mnożeń z linii 3 wykonuje się w zależności od n?

Wersja II (potęgowanie binarne)

Algorytm ten ma o wiele lepszą złożoność niż ten z Wersji I. Aby go zrozumieć należy wykładnik n zapisać w postaci binarnej (dwójkowej).

Algorytm

1 z = x; y = 1; m = n;

2 while (m > 0) {

3               if (m % 2 == 1) y = y*z;

4                             m = m/2;

5                             z = z*z;

6               }

7 printf(y);

·         Przeanalizuj jak zmieniają się wartości zmiennych y, m, z dla n = 13 i dla n =32:

·         Weźmy rozkład 13 = (1101)2. Zatem x13 = x8x4x1. To pomoże zrozumieć jak działa nasz algorytm.

·         Jaka jest złożoność tego algorytmu. Na początek weźmy „proste” d obliczeń wartości n=64, n=1024. Ile razy wykonuje się pętla:

while (n > 0)

   n = n/2;

Ćwiczenie 5

Zajmiemy się teraz zliczaniem słów w pliku tekstowym. Z punktu widzenia algorytmu, który to robi, plik taki składa się po prostu z dwóch rodzajów znaków: „a” (znaki słów) oraz „s” (znaki separatorów, np. spacja, znak końca wiersza, znaki przestankowe):

text =  aaaasaaassaassaaasaaaasaaasaaaaaassaaaasaasaaaass

Główna idea algorytmu polega na zliczaniu miejsc gdzie jest granica separator-słowo:

.......ssaaaaaaa.......

...