Wyklad 04, Studia - Politechnika Opolska, Semestr 3, Systemy Operacyjne

//-->.pos {position:absolute; z-index: 0; left: 0px; top: 0px;}Techniki budowania algorytmówCo w ramach wykładu?1. Rekurencja2. Dziel i zwyciężaj3. Programowanie dynamiczne4. Metoda zachłannaAiSD - Wykład 4 – Dziel i zwyciężajSlajd 1Dziel i zwyciężajBitwa pod Austerlitz, 2 grudnia 1805 r. – zwycięstwo wojsk Napoleona nad liczniejszymio około 15 000 żołnierzy połączonymi armiami Austrii i Rosji.Schemat ogólnyTrzy zasadnicze kroki:1. transformacja danychxna danex1, . . . ,xko mniejszym rozmiarze;2. rozwiązanie problemu dla danychxi(i = 1, . . . ,k);3. obliczenie rozwiązania dla danychxna podstawie wyników otrzymanych w punkcie 2.W naturalny sposób implementowane są jako procedury rekurencyjne:functionDiZ(x)ifxjest małe lub prostethen returnAdHoc(x)przekształćxnax1, . . . ,xko mniejszym rozmiarze niżxfori←1tokdoyi←DiZ(xi)na podstawiey1. . .ykoblicz rozwiązanieydlaxreturnyAiSD - Wykład 4 – Dziel i zwyciężajSlajd 2Przykład 1 – Wyszukiwanie binarneWyszukiwanie binarneProblem:czy kluczxznajduje się wposortowanejtablicyS,zawierającejnkluczy?Dane wejściowe:całkowita liczba dodatnian,tablica kluczySindeksowana od 1 donorazkluczx.Dane wyjściowe:location– lokalizacja kluczaxw tablicyS(0, jeślixnie występuje wS)Algorytm wyszukiwania binarnegoJeżeli x jest równe elementowi środkowemu, kończymy. W przeciwnym przypadku:1. Dzielimytablicę na dwie podtablice o rozmiarze mniej więcej dwa razy mniejszym odoryginalnej. Jeżeli x jest mniejsze od elementu środkowego, wybieramy lewąpodtablicę. Jeśli x jest większe od elementu środkowego, wybieramy prawąpodtablicę.2. Zwyciężamy(rozwiązujemy) podtablicę poprzez określenie, czy x do niej należy. O ilepodtablica nie posiada dostatecznie małych rozmiarów, należy wykorzystaćrekurencję.3. Otrzy mujemyrozwiązanie problemu tablicy na podstawie rozwiązania problemupodtablicy.AiSD - Wykład 4 – Dziel i zwyciężajSlajd 3Wyszukiwanie binarne c.d.intlocation(int low,inthigh){intmid;if(low >high)return0;else{mid=ë(low+high)/2û;if(x ==S[mid])returnmid;else if(x <S[mid])returnlocation(low, mid-1);elsereturnlocation(mid+1, high);}}Operacja podstawowa:porównaniexzS[mid]Rozmiar danych wejściowych:liczbanelementów tablicySZłożoność czasowa w najgorszymprzypadku:W(n)=W(ën/2û)+ 1 ,W(1)= 1W(n)=ëlgnû+ 1AiSD - Wykład 4 – Dziel i zwyciężajSlajd 4Przykład 2 – Sortowanie przez scalanieSortowanie przez scalanieProblem:posortowaćnkluczy w ciąg niemalejącyDane wejściowe:całkowita liczba dodatnian,tablica kluczySindeksowana od 1 don.Dane wyjściowe:tablicaS,zawierająca klucze w porządku niemalejącymAlgorytm sortowania przez scalanie1. Dzielimytablicę na dwie podtablice o rozmiarze mniej więcej dwa razy mniejszym odoryginalnej.2. Zwyciężamy(rozwiązujemy) każdą podtablicę, sortując ją. O ile podtablica nieposiada dostatecznie małych rozmiarów, należy wykorzystać rekurencję.3. Łączymyrozwiązania podtablic poprzez scalenie ich w jedną posortowaną tablicę.MERGE-SORT(A, p, r)ifp<rthenq←ë(p+r)/2ûMERGE-SORT(A, p, q)MERGE-SORT(A, q+1, r)MERGE(A,p, q, r)Jak scalić dwie posortowane tablice w jednąposortowaną tablicę w czasieQ(n)?Slajd 5AiSD - Wykład 4 – Dziel i zwyciężaj

zanotowane.pl

doc.pisz.pl

pdf.pisz.pl

kachorra.htw.pl