1 ALGORYTMY I STRUKTURY DANYCHWYKŁAD 03 Minimum i maksimum Grażyna Mirkowska PJWSTK, ITN semestr letni 2002

2 G. Mirkowska, ASD_03 Minimum i maksimumPlan wykładu Minimum i maksimum Algorytm naiwny Jak poprawić algorytm naiwny Analiza kosztu średniego Algorytm optymalny Algorytm rekurencyjny 20 marca 2002 G. Mirkowska, ASD_03 Minimum i maksimum

3 Specyfikacja algorytmuMinimum i maksimum Problem Dany jest ciąg elementów e[i] i= 1,...,n należących do pewnego zbioru E liniowo uporządkowanego przez relację . Znaleźć największy i najmniejszy element tego ciągu. Specyfikacja algorytmu Wp ={e[i]  e[j] dla ij, e[i] E dla i =1...n,  liniowy porządek w E } Wk = { e[min]e[i] oraz e[max]  e[i] dla wszystkich i=1,2...n} Algorytm naiwny może wyglądać następująco: { max := 1; for i := 2 to n do if e[i] >e[max] then max := i fi od; min := 1; if e[i] } Oczywiści operacja dominującą jest to operacja porównywania Koszt algorytmu nie zależy od wartości elementów ciągu a tylko od wzajemnej relacji między elementami. poprawność tego algorytmu można wykazać przez indukcje ze względu na długość ciągu. 20 marca 2002 G. Mirkowska, ASD_03 Minimum i maksimum

4 G. Mirkowska, ASD_03 Minimum i maksimumAlgorytm naiwny Krok 1 Znajdź minimum metodą sekwencyjnego przeglądania ciągu. Krok 2 Znajdź maksimum, tą samą metodą. { min :=1; max :=1; i:= 2; while i  n do if e[i] >e[max] then max := i fi; if e[i]< e[min] then min := i fi; i:= i+1; od; } Koszt : T(min_max1,n) = 2n-2 min_max1 e[max] e[j] , e[min]  e[j] dla j< i Niezmiennik 20 marca 2002 G. Mirkowska, ASD_03 Minimum i maksimum

5 Modyfikacja algorytmu naiwnegoAlgorytm naiwny nie jest optymalny! Jeśli e[i] jest większe od e[max], to nie ma potrzeby porównywać e[i] z e[min]. { min :=1; max :=1; for i := 2 to n do if e[i] >e[max] then max := i else if e[i]< e[min] then min := i fi fi od; } Niezmiennik ( 1j min_max2 Koszt pesymistyczny: W(n) = 2n-2 20 marca 2002 G. Mirkowska, ASD_03 Minimum i maksimum

6 Analiza kosztu min-max 2{ min :=1; max :=1; for i := 2 to n do if e[i] >e[max] then max := i else if e[i]< e[min] then min := i fi fi od; } Uwaga 1 Pierwsze porównanie jest wykonywane w każdym przebiegu pętli. Uwaga 2 Drugie porównanie jest wykonywane tylko wtedy, gdy odpowiedź w pierwszym porównaniu jest negatywna. powrót 20 marca 2002 G. Mirkowska, ASD_03 Minimum i maksimum

7 Analiza kosztu średniego min-max 2A(n) = S d Dn p(d)* t(d) Dn - zbiór wszystkich danych rozmiaru n. Jeśli założymy, że wszystkie permutacje są jednakowo prawdopodobne, to p(d) = 1/n! Zbiór wszystkich permutacji 20 marca 2002 G. Mirkowska, ASD_03 Minimum i maksimum

8 G. Mirkowska, ASD_03 Minimum i maksimumKoszt średni c.d. Niech d = a1...an będzie daną permutacją liczb 1...n i b = b1,...bn będzie ciągiem takim, że bi = liczba elementów większych niż ai na lewo od ai , tzn. o mniejszych indeksach w ciągu d. Przykład Niech d = , wtedy b = Obserwacja (a) Ciąg b jest jednoznacznie wyznaczony przez d (b) 0 bi < i Drugiego porównania w algorytmie nie wykonujemy tylko wtedy, gdy na lewo od i-tego elementu nie było liczby większej, czyli tylko wtedy gdy bi =0. Min-max2 20 marca 2002 G. Mirkowska, ASD_03 Minimum i maksimum

9 G. Mirkowska, ASD_03 Minimum i maksimumKoszt średni c.d. Prawdopodobieństwo tego, że bi =0 wynosi 1/i, ponieważ bi przyjmuje tylko wartości od 0 do i-1. Stąd prawdopodobieństwo wykonania drugiego porównania wynosi /i. t(d) = (n-1) + S i =2...n 1* p(drugie porównanie) = (n -1) + S i=2...n (1-1/i) = 2n-2 - lg n +c S i=2...n (1/i) 1/x dx= ln|x| Ostatecznie A(n) = S i =2...n 1/n! t(d) = 2n - lg n +c 20 marca 2002 G. Mirkowska, ASD_03 Minimum i maksimum

10 G. Mirkowska, ASD_03 Minimum i maksimumAlgorytm min-max 3 Idea algorytmu: Porównaj parami elementy danego ciągu. Mniejszy z każdej pary wstaw do ciągu M, a większy z każdej pary do ciągu W. Mniejsze: Większe: 5 8 34 44 7 4 1 11 4 2 Wspomnij o różnych wersjach tego algorytmu: Np.. bez pomocniczych tablic ale z zamianami , z innym ustawieniem par, np.:pierwszy-ostatni itd Wybierz minimum Wybierz maksimum Dany ciąg: 4, 5, 1, 8, 34, 11, 44, 4, 7, 2, 4, 5, 1, 8, 34, 11, 44, 4, 7, 2, 20 marca 2002 G. Mirkowska, ASD_03 Minimum i maksimum

11 G. Mirkowska, ASD_03 Minimum i maksimumAnaliza kosztu { // min-max 3 i:=1; k:=1; while i< n do if e[i] >e[i+1] then w[k] :=i; m[k] :=i else w[k] :=i+1; m[k] :=i fi i := i+2; k := k+1; od; min := m[1]; max :=w[1]; for i := 2 to k-1 do if e[m[i]] < e[min] then min := m[i] fi; if e[w[i]]> e[max] then max := w[i] fi; od; } Operacja dominująca : porównywanie. Załóżmy, że n jest liczbą parzystą. 1szy krok = n/2 porównań Wybranie minimum = n/ porównań Wybranie maksimum = n/ porównań. Razem = 3n/2 -2 porównań 20 marca 2002 G. Mirkowska, ASD_03 Minimum i maksimum

12 G. Mirkowska, ASD_03 Minimum i maksimumAnaliza poprawności Niezmiennik { //rozdzielanie i:=1; k:=1; while i< n do if e[i] >e[i+1] then w[k] :=i; m[k] :=i else w[k] :=i+1; m[k] :=i fi i := i+2; k := k+1; od; } Dla każdego j=1...k-1 istnieje takie u e[m[j]]  e[w[u]] Dla każdego j=1...k-1 istnieje takie u e[w[j]]  e[m[u]] Żaden indeks w tablicy w[i] nie może wskazywać minimum ciągu e. Żaden indeks w tablicy m[i] nie może wskazywać maksimum ciągu e. 20 marca 2002 G. Mirkowska, ASD_03 Minimum i maksimum

13 Analiza poprawności c.d.Wśród indeksów m[1], ...m[k] istnieje taki indeks min, że e[min]  e[i] dla wszystkich i =1,...n Wśród indeksów m[1], ...m[k] istnieje taki indeks max, że e[i]  e[max] dla wszystkich i =1,...n min := m[1]; max :=w[1]; for i := 2 to k-1 do if e[m[i]] e[max] then max := w[i] fi; od; e[min]  e[i] dla wszystkich i =1,...n e[i]  e[max] dla wszystkich i =1,...n 20 marca 2002 G. Mirkowska, ASD_03 Minimum i maksimum

14 G. Mirkowska, ASD_03 Minimum i maksimumMin-max przykład Założenie: n = 2 k Dany ciąg: 4, 5, 1, 8, 33, 11, 44, 4, 7, 2, 13, 22, 3, 55, 9, 6 4, 5, 1, 8, 33, 11, 44, 4 min= max= 7, 2, 13, 22, 3, 55, 9, 6 min= max= 1 44 7, 2, 13, 22 min= max= 3, 55, 9, 6 min= max= 4, 5, 1, 8 min= max= 33, 11, 44, 4 min= max= 1 8 4 44 4,5 33,11 44,4 7,2 13,22 1,8 3,55 9,6 20 marca 2002 G. Mirkowska, ASD_03 Minimum i maksimum

15 G. Mirkowska, ASD_03 Minimum i maksimumMin-max 4 -- przykład Założenie: n = 2 k Dany ciąg: min = max = 55 4, 5, 1, 8, 33, 11, 44, 4, 7, 2, 13, 22, 3, 55, 9, 6 4, 5, 1, 8, 33, 11, 44, 4 min= max= 7, 2, 13, 22, 3, 55, 9, 6 min=2 max=55 1 44 7, 2, 13, 22 min=2 max=22 3, 55, 9, 6 min=3 max=55 4, 5, 1, 8 min= max= 33, 11, 44, 4 min= max= 1 8 4 44 4,5 33,11 44,4 7,2 13,22 1,8 3,55 9,6 20 marca 2002 G. Mirkowska, ASD_03 Minimum i maksimum

16 G. Mirkowska, ASD_03 Minimum i maksimumAlgorytm min-max 4 obiekt function min_max4 (int i, j); //deklaracja i tworzenie obietktów result, lewy, prawy; { if ( i+1=j ) then if e[j] > e[i] then result.max := j; result.min := i else result.min := j; result.max :=i fi else x:= (i+j-1) div 2; lewy := min_max4( i, x); prawy := min_max4( x+1, j); if e[prawy.min] min max obiekt i x j Tu również znajduje zastosowanie zasada podziału zadania na podzadania: metoda „dziel i zwyciężaj”. Jak już się przekonaliśmy metoda ta często pozwala wykonać zadanie szybciej, z mniejszym kosztem, niż inne metody. W podanym rozwiązaniu, dany ciąg e jest informacja zewnętrzną. Funkcja, którą opiszemy zwraca w wyniku dwie wartości przechowywane w obiekcie obiekt. Oczywiście klasa obiekt musi być zdefiniowana w programie, który będzie wykorzystywał funkcję min-max4 20 marca 2002 G. Mirkowska, ASD_03 Minimum i maksimum

17 G. Mirkowska, ASD_03 Minimum i maksimumPoprawność min-max 4 Wp = {( m) n= 2 m, e[i]  dla i=1,...n} Wk = {(i) e[min]  e[i] , (i) e[i]  e[max]} Jeżeli spełniony jest warunek początkowy wp , to po wykonaniu następujących instrukcji {wynik := min_max4(1,n); min := wynik.min; max := wynik.max;} spełniony będzie warunek końcowy wk. Twierdzenie 20 marca 2002 G. Mirkowska, ASD_03 Minimum i maksimum

18 Czy algorytm min-max4 zatrzymuje się?W każdym wywołaniu funkcji min_max4(i,j) parametry aktualne i, j spełniają warunek j-i+1 = 2 k dla pewnego k, 1 k  m Lemat j = n, i =1 Dla pierwszego wywołania własność jest oczywiście spełniona. bo i+j=1 Jeżeli w ciągu są tylko 2 elementy, tzn. k=1. Wtedy nie wywołujemy powtórnie funkcji min-max4. Jeżeli k>1 oraz j-i+1 = 2 k , to funkcja zostanie wywołana dla nowych argumentów: i, x oraz x+1, j, ale wtedy x-i+1 = (i+j-1)/2 – i +1 = (j-i+1)/2 = 2 k-1 Min- max4 j-(x+1)+1 = j – ((i+j-1)/2 +1) +1 =(j-i+1)/2 = 2 k-1 20 marca 2002 G. Mirkowska, ASD_03 Minimum i maksimum

19 G. Mirkowska, ASD_03 Minimum i maksimumC.d. ‘stop’ dla min-max4 jest 2 razy mniejsza Długość rozważanego przez funkcję min-max4 ciągu maleje w kolejnych wywołaniach. W konskwencji proces musi się zakończyć dla k=1. Wniosek Jeśli spełniony jest warunek początkowy wp, to algorytm min_max4 zatrzymuje się dla dowolnych danych. 20 marca 2002 G. Mirkowska, ASD_03 Minimum i maksimum

20 G. Mirkowska, ASD_03 Minimum i maksimumPoprawność min-max4 Dowód przez indukcję ze względu na liczbę wywołań rekurencyjnych funkcji min_max4. Analogicznie dla minimum Dla jednego tylko wywołania , tzn. gdy m=1 wynik algorytmu jest poprawny. Załóżmy, że wynik algorytmu jest poprawny dla wewnętrznych wywołań, czyli if e[lewy.max] e[k]  e[lewy.max] dla i  k  x oraz e[k]  e[prawy.max] dla x+1  k  j Po wykonaniu instrukcji : Mamy : e[k]  e[result.max] dla i  k  j 20 marca 2002 G. Mirkowska, ASD_03 Minimum i maksimum

21 Ostatecznie: Koszt min_max4 T(min_max4, 2) = 1Operacja dominująca - porównywanie elementów Jeśli w ciągu są tylko 2 elementy, to wykonujemy 1 porównanie T(min_max4, 2) = 1 T(min_max4, 2 k)= 2* T(min_max4,2 k-1) +2 Min- max4 Dla k>1 wykonujemy 2 wywołania rekurencyjnie Dwa dodatkowe porównania dla ustalenia ostatecznego wyniku Ostatecznie: T(min_max4, n) = 3/2 n - 2 20 marca 2002 G. Mirkowska, ASD_03 Minimum i maksimum

22 Czy można zrobić lepiej?min_max4 jest optymalnym rozwiązaniem problemu min-max Twierdzenie Każdy algorytm wyznaczający dla dowolnego ciągu e[1],...e[n] elementów dowolnej liniowo uporządkowanej przestrzeni musi wykonać w przypadku pesymistycznym co najmniej [3/2 n] – 2 porównania. 20 marca 2002 G. Mirkowska, ASD_03 Minimum i maksimum