RSS
 

Archiwum dla kategorii ‘VI. Algorytmy i struktury danych’

Programowanie dynamiczne

07 paź

Wspólne podproblemy
Programowanie dynamiczne
stosuje się wówczas, gdy podproblemy, na które dzieli się problem wyjściowy, nie są zależna. W takim przypadku algorytmy typu dziel i zwyciężaj wykonują więcej pracy niż to niezbędne, rozwiązując ten sam problem wielokrotnie.

Warunki, które powinien spełniać problem optymalizacyjny, aby można było z powodzeniem stosować metodę programowania dynamicznego:
- własność optymalnej podstruktury: optymalne rozwiązanie problemu jest funkcją optymalnych rozwiązań podproblemów,
- własność wspólnych podproblemów: algorytm rekurencyjny rozwiązujący problem wielokrotnie oblicza rozwiązanie tego samego problemu.

Algorytmy programowania dynamicznego zwykle są oparte na metodzie wstępującej. Zaczynają od rozwiązania najprostszych podproblemów i zapamiętania rozwiązań, a następnie rozwiązują problemy bardziej złożone, wykorzystując gotowe rozwiązania prostszych, powtarzających się problemów.

Najdłuższy wspólny podciąg
Dane są dwa ciągi A i B o długościach odpowiednio: n i m. Problem polega na znalezieniu najdłuższego podciągu D, który zawarty jest zarówno w A, jak i w B.

Rozwiązanie naiwne
Dla każdego z n potencjalnych punktów początkowych wspólnego podciągu z A należy znaleźć najdłuższy wspólny podciąg z każdym z m punktów początkowych z B. Złożoność algorytmu opartego na takim postępowaniu wynosi O(n2 * m).

Niech L będzie tabelą o n kolumnach i m wierszach Na pozycji L[i, j] należy wpisać maksymalną długość ciągu kończącego się w A[i] i B[j]. Tabelę L wypełnia się według następujących reguł:
- jeżeli A[i] ≠ B[j], to L[i, j] = 0, ponieważ nie ma wspólnego podciągu, który kończy się w A[i] i B[j],
- jeżeli A[i] = B[j], to wspólny podciąg, który kończy się A[i] i B[j], jest o jeden znak dłuższy od tego, który kończy się w A[i - 1] i B[j - 1], tj. nową wartością :[i, j] staje się L[i - 1, j - 1] + 1.

 

Algorytmy zachłanne

06 paź

Strategia zachłanna
Zastosowanie strategii zachłannej polega na podejmowaniu lokalnie optymalnych decyzji z nadzieją, że prowadzą one do globalnie optymalnego rozwiązania. Algorytmy zachłanne nie zawsze prowadzą do znalezienia optymalnego, jednak dla wielu problemów są wystarczające.

Wydajemy resztę i pakujemy plecak
Problem optymalizacyjny
– problem obliczeniowy, którego rozwiązanie polega na znalezieniu największej bądź najmniejszej wartości pewnego parametru problemu, która spełnia określoną własność. Parametr, którego największej bądź najmniejszej wartości szukamy, nazywa się funkcją kosztu (funkcja celu). Problem optymalizacyjny nazywa się problemem maksymalizacyjnym, jeśli polega on na znalezieniu największej wartości funkcji kosztu, i minimalizacyjnym, jeśli szukana jest najmniejsza wartość funkcji kosztu.

Problem plecakowy – maksymalizacyjny problem wyboru przedmiotów tak, by ich sumaryczna wartość była jak największa i jednocześnie mieściły się w plecaku. Przy podanym zbiorze elementów o podanej wadze i wartości, należy wybrać taki podzbiór, by suma wartości byłą możliwie jak największa, a suma wag była nie większa od danej pojemności plecaka.

Planowanie zadań
Danych jest n zadań (programów) oznaczonych przez t1, …, tn, każde z czasem rozpoczęcia i zakończenia pracy si i e1, dla i od 1 do n. Problem polega na znalezieniu takiego planu wykonania zadań, aby do ich realizacji zużyć najmniejszą liczbę maszyn (komputerów). Na danej maszynie można wykonać tylko niezakłócające się zadania, tj. takie, że ich czasy wykonania mogą mieć najwyżej jeden punkt wspólny (kolejne zadanie nie może się rozpocząć przed zakończeniem poprzedniego).

Należy wybrać zadanie t z minimalnym czasem rozpoczęcia. Jeżeli jakaś maszyna ze zbioru już używanych jest w tym momencie wolna, można wykonać na niej zadanie t. Jeżeli nie, to trzeba wziąć nową maszynę i wykonać na niej nadanie t. Czynność należy powtarzać, aż do wyczerpania zadań.

 

Dziel i zwyciężaj

05 paź

Podział problemu
Rozwiązywanie problemów metodą dziel i zwyciężaj przebiega w dwóch etapach. W pierwszym problem dzielony jest na kilka podproblemów, które są prostsze od problemu wyjściowego. W drugim etapie z rozwiązań wyodrębnionych, prostszych podproblemów, konstruowane jest rozwiązanie problemu podstawowego.

Sortowanie przez scalanie
Dane są rekordy r1, …, rn, mające w swojej strukturze pole kluczowe k. Zakłada się, że na wartościach pól kluczowych zadany jest porządek liniowy: ≤. Problem sortowania rekordów względem porządku zadanego na polach kluczowych sprowadza się do znalezienia takiej permutacji rekordów (zmiany kolejności rekordów) σ : {1, …, n} → {1, …, n}, że: r0(i), k ≤ r0(j), k, dla σ(i) < σ(j) oraz i, j ϵ {1, …, n}.

Najprostsze algorytmy sortowania mają złożoność czasową O(n2). Stosując metodę dziel i zwyciężaj, możemy przyspieszyć proces sortowania i uzyskać algorytm sortujący o złożoności O(n * log2n). Jest to najmniejszy rząd złożoności algorytmu sortowania opartego na porównaniach elementów.

Jeżeli lista elementów do posortowania składa się z dwóch podlist posortowanych, to aby uzyskać listę posortowaną, wystarczy scalić te podlisty z zachowaniem porządku na elementach. Np. gdy podlisty są uporządkowane rosnąco, wówczas w każdym kroku należy porównać pierwsze elementy obu podlist i wybrać mniejszy z nich, aby dołączyć go na koniec listy wynikowej. Czynność powtarza się do wyczerpania elementów.

Mając listę nieuporządkowanych elementów, wystarczy dzielić ją w każdym kroku na dwie podlisty o zbliżonej długości, aż otrzyma się podlisty o długości 1. Listy takie z natury swojej są uporządkowane, wystarczy teraz scalić je parami z zachowaniem porządku, aż otrzyma się pojedynczą listę uporządkowaną.

Sortowanie przebiega w dwóch etapach: dzielenie i scalenie. Etap dzielenia wymaga tylu porównań, ile jest węzłów wewnętrznych w drzewie dzielenia o n liściach, czyli O(n * log2n). Etap scalania wymaga O(log2n) scaleń średniej liczby O(n) elementów. Stąd algorytmu sortowania przez scalanie tablicy o rozmiarze n:

CMergesort(n) ϵ O(n * log2n) oraz TMergesort(n) ϵ O(n * log2n).

Podobne złożoności do prezentowanych powyżej mają również algorytmu sortowania szybkiego oraz sortowania kopcowego.

 

Rekurencja i obliczalność

04 paź

Algorytm rekurencyjny
Rekurencja
jest sposobem definiowania obiektów, czy to matematycznych, czy informatycznych, przez odwołanie się do samego obiektu w jego definicji.

Analiza złożoności algorytmów rekurencyjnych
Algorytm Hanoi
– dany jest stos zbudowany z n krążków o coraz mniejszej średnicy, nawleczonych na jeden z trzech patyków. Zadanie polega na przeniesieniu stosu na ostatni patyk, przy czym należy traktować drugi patyk jako bufor i przestrzegać następujących reguł:
- w jednym kroku wolno przenieść tylko jeden krążek,
- nigdy nie wolno kłaść większego krążka na mniejszy.

Algorytmy o takiej złożoności mogą być stosowane tylko dla niewielkich n.

Granice obliczalności
Istnieją funkcje zdefiniowane rekurencyjnie o duże złożoności obliczeniowej, Co więcej, złożoność taka może rosnąć wraz ze wzrostem argumentów funkcji. Przykładem takiej funkcji jest funkcja Ackermanna, A : Nat x Nat → Nat, zdefiniowana następująco:

A(0, n) = n + 1,
A(m, 0) = A(m – 1, 1),
dla m > 0,
A (m, n) = A(m – 1, A(m, n – 1)), dla m > 0 i n > 0.

WYBRANE WARTOŚCI FUNKCJI ACKERMANNA
Wybrane wartości funkcji Ackermanna

Funkcja ta niezwykle szybko rośnie. Złożoność czasowa tej funkcji jest równie duża, jak jej wartości.

Funkcję nazywa się obliczalną, jeżeli może być ona obliczona za pomocą maszyny Turinga. Maszyna Turinga jest abstrakcyjnym modelem maszyny liczącej (komputera). Składa się ona z nieskończenie długiej taśmy podzielonej na pole. Na każdym polu może się znajdować jedna z ustalonych wartości. Głowica maszyny jest zawsze ustawiona nad jednym z pól i znajduje się w jednym z ustalonych stanów. W zależności od stanu maszyny oraz zapisanej w bieżącym polu wartości, maszyna zapisuje w polu nową wartość, zmienia swój stan, po czym przesuwa głowicę o jedno pole w prawo lub lewo. W wyróżnionym stanie, zwanym stanem końcowym, maszyna się zatrzymuje.

Należy zwrócić uwagę, że w przypadku maszyny Turinga nie można mówić o czasie obliczeń, lecz tylko o liczbie kroków przez nią wykonywanych – nie zdefiniowano czasu wykonywania przez nią poszczególnych kroków. W przypadku prawdziwych maszyn liczących wykonanie każdego kroku obliczeń wymaga niezerowego czasu. Również dostępna pamięć jest ograniczona.

Funkcję Ackermanna często podaje się jako ograniczenie górne złożoności funkcji rekurencyjnych, które można w rozsądnym czasie obliczyć, używając maszyn liczących.

 

Struktury danych

03 paź

Typy proste
Dane przetwarzane przez algorytm zazwyczaj mają swoją strukturę. Najprostszymi strukturami danych są tzw. typy proste. To zwykle typy liczbowe (całkowite i rzeczywiste), typ znakowy oraz typ wartości logicznych. Z wartościami każdego z tych typów związane są odpowiednie operacje. W przypadku liczb są to operacje arytmetyczne, w przypadku znaków – operacje porównania, wzięcia następnika/poprzednika, a w przypadku wartości logicznych – operacje związane ze standardowymi spójnikami logicznymi.

Struktury statyczne to takie struktury, które przez cały czas działania logarytmu mogą przechowywać dane o z góry ustalonym rozmiarze, a struktury dynamiczne to struktury, których rozmiar może ulegać zmianom w trakcie działania algorytmu.

Struktury statyczne
Do najczęściej używanych w informatyce statycznych struktur danych należą rekordy i tablice.

Rekord jest statyczną strukturą danych, odpowiadającą iloczynowi kartezjańskiemu swoich podstruktur składowych, zwanych polami rekordu. Zwykle definicja rekordu ma następującą postać:

T = rekord s1 : T1, …, sn : Tnend

T jest definiowanym typem rekordu, s1, …, sn są nazwami pól rekordu, natomiast T1, …, Tn ich typami składowymi. Przykładem typów o naturalnej implementacji w postaci typu rekordowego są: liczba zespolona, punkt na płaszczyźnie czy charakterystyka osoby.

Odwołania do poszczególnych pól typu rekordowego następują przy użyciu nazwy pól. Np. jeżeli zmienna x jest typu:
Osoba – rekord imię: Napis, nazwisko: Napis, wiek: Liczba end,
to x. nazwisko oznacza składową nazwisko rekordu typu Osoba. Tak skonstruowane odwołania służą zarówno do odczytu istniejących w rekordzie wartości, jak i do przypisania im nowych wartości.

Tablica jest jedną z najbardziej znanych struktur danych. Tablica jest strukturą jednorodną, tj. wszystkie jej składowe, w odróżnieniu od rekordów, są tego samego typu.
Definicja typu tablicowego ma następującą postać:

T = array [I]of T0
T0 jest typem wartości składowych tablicy, natomiast I jest typem indeksów tablicy. Rozmiar tablicy jest wyznaczony przez rozmiar typu indeksującego I. Każdej składowej typu tablicowego jest przypisany dokładnie jeden indeks typu I. Dostęp do poszczególnych składowych tablicy odbywa się za pomocą indeksów.

Niech t będzie zmienną tablicową o typie:
Liczby = array [1 .. 10] of Liczba,
wówczas t[i] dla i od 1 do 10 oznacza i-tą składową tablicy t i może służyć d odczytu danych istniejący w tablicy wartości oraz przypisywania składowym nowych wartości.

Struktury dynamiczne
Lista
jest skończonym ciągiem elementów L = [x1, ..., xn]. Skrajne elementy listy nazywa się odpowiednio prawym i lewym końcem listy. Wielkość |L| to długość lub rozmiar listy.

Elementarnymi operacjami na listach są operacje:
- dostępu do elementów listy: L[i] – i-ty element listy L: xi,
- brania podlisty: L[i .. j] – wynikiem jest lista [xi, ..., xj],
- sklejenia dwóch list: L & K = [x1, ..., xn, y1, ... ym], gdzie K = [y1, ..., ym].

Zwykle, pracując z listami, nie używa się bezpośrednio operacji elementarnych, lecz ogranicza się je do podzbioru następujących operacji:
- front(L) = L[1],
- push(L, x) = [x] & L,
- pop(L) = L[2..|L|],
- rear(L) = L[|L|],
- inject(L, x) = L & [x],
- eject(L) = L[1..|L| - 1].

Listę wraz ze wszystkimi powyższymi operacjami nazywa się kolejką podwójną. Bardzo popularne w zastosowaniach informatycznych stosy i kolejki otrzymuje się, ograniczając dostępne operacje odpowiednio do: front, push i pop oraz front, pop i inject.

Drzewo jest:
- strukturą pustą albo,
- węzłem ze skończoną liczbą dowiązanych rozłącznych struktur drzewiastych, zwanych poddrzewami, taki węzeł zwykle nazywa się rodzicem poddrzew, a poddrzewa jego synami.

Węzeł w drzewie nieposiadający rodzica nazywa się korzeniem, natomiast węzeł nieposiadający synów – liściem. Poziom węzła definiuje się następująco: korzeń drzewa ma poziom 1, poziom węzła wewnętrznego jest o jeden większy od poziomu rodzica. Maksymalny poziom liczony po wszystkich węzłach drzewa nazywa się głębokością lub wysokością drzewa.

Stopniem drzewa nazywa się maksymalną liczbę poddrzew dowiązanych do dowolnego węzła w drzewie. W zastosowaniach informatycznych na szczególną uwagę zasługują drzewa stopnia 2, zwane także drzewami binarnymi.

Jeżeli na elementach przechowywanych w węzłach określona jest relacja liniowego porządku ≤, to drzewo binarne, w którym dla każdego węzła x niebędącego liściem wszystkie węzły lewego syna są ≤ x oraz x ≤ od wszystkich węzłów prawego syna, nazywa się uporządkowanym drzewem binarnym. Drzewa binarne, których maksymalna różnica poziomu liści nie przekracza 1, nazywa się binarnymi drzewami wyważonymi.

Uporządkowane i wyważone drzewa binarne cechuje bardzo krótki czas wyszukiwania elementu w drzewie, równy maksymalnej wysokości takiego drzewa, która dla drzewa przechowującego n węzłów wynosi O(log2n). Oznacza to, że aby w takiej strukturze znaleźć dany element pośród 1 000 000 elementów, trzeba wykonać tylko ok. 20 operacji, natomiast znalezienie takiego elementu na nieuporządkowanej liście 1 000 000 elementów wymaga średnio 500 000 operacji.

 

Złożoność algorytmów

02 paź

Długość oczekiwania na wynik działania programu zależy od wielkości danych wejściowych oraz od zastosowanego algorytmu, a także od środowiska, w którym program został uruchomiony, czyli od procesora, pamięci czy systemu operacyjnego.

Ile operacji elementarnych wykona algorytm A na danych wejściowych x? Spodziewana odpowiedź: Algorytm A dla danych x wykona f(x) operacji elementarnych.

Niech A będzie algorytmem. Koszt algorytmu A, oznaczany przez KA(x), to liczba wykonanych przez algorytm A operacji elementarnych, przy danych wejściowych x.

Operacjami dominującymi nazywa się operacje elementarne decydujące o czasie wykonywania danego algorytmu.

Wyznaczenie dokładnej złożoności obliczeniowej algorytmu bywa zadaniem trudnym. Za zadowalające uważa się określenie rzędu funkcji ograniczającej złożoność obliczeniową algorytmu z dołu i z góry. Często przyjmuje się, że złożoność obliczeniowa algorytmu jest funkcją rozmiaru danych wejściowych algorytmu n. Uważa się, że funkcja g(n) jest rzędem funkcji ograniczającej funkcję f(n) z góry, jeżeli można znaleźć taki argument n0, że dla wszystkich n > n0, wykres funkcji f(n) leży pod wykresem funkcji c * g(n), dla pewnej stałej dodatniej c. Analogicznie, intuicje związane są z pojęciem rzędu funkcji ograniczającej złożoność algorytmu z dołu.

Analiza efektywności algorytmów

Dla algorytmu Suma, niezależnie od przyjętego zbioru operacji dominujących:
Tsuma(n) ϵ O(n).

CZASY DZIAŁANIA ALGORYTMÓW PRZY DANEJ ZŁOŻONOŚCI CZASOWEJ
Czasy działania algorytmów przy danej złożoności czasowej

 

Algorytm, od problemu do programu

01 paź

Algorytm jest ściśle określoną procedurą obliczeniową, która dla danych wejściowych produkuje żądane dane wyjściowe, zwane wynikiem. Algorytm jest ciągiem kroków obliczeniowych, przekształcanych dane wejściowe w dane wyjściowe.

Analiza algorytmów jest działem informatyki zajmującym się oceną i optymalizacją algorytmów rozwiązywania problemów informatycznych. Głównym zadaniem tego działania jest jest szykanie odpowiedzi na następujące pytania:
- Czy dany problem może by rozwiązany przy wykorzystaniu dostępnych zasobów?
- Czy istnieje algorytm rozwiązywania danego problemu?
- Czy znaleziony algorytm jest optymalny?
- Czy zastosowanie znalezionego algorytmu rzeczywiście rozwiązuje problem?

Od problemu do algorytmu
Mając jakiś konkretny problem, wystarczy zakwalifikować go do pewnej znanej klasy problemów, pobrać z biblioteki gotowy algorytm i zapisać go w ulubionym języku programowania. Proces taki jest nazywany kodowaniem. Następnie pozostaje już tylko uruchomić program i czekać na wyniki.

Gdy problem nie daje się łatwo zakwalifikować do znanych klas problemów należy ustalić, które parametry rozpatrywanego problemu są dane, tj. mogą stanowić dane wejściowe algorytmu, a których parametrów problemu się poszukuje, tj. będą stanowiły wynik działania algorytmu. Następnie należy przejść do konstrukcji algorytmu. Konstrukcja ta zależy od złożoności problemu i wiedzy oraz pomysłowości. Ostatnim etapem jest realizacja algorytmu w konkretnym języku programowania. Czynności realizowane od przedstawienia problemu po dostarczenie gotowego programu są nazywane łącznie programowaniem.

Każdy algorytm musi spełniać następujące warunki:
- skończoność opisu: tekst opisujący algorytm jest skończony,
- efektywność i wydajność:
a) efektywność: algorytm,
b) wydajność: zadanie,
- terminacja: po skończonej liczbie kroków wszystkie kroki algorytmu zostaną wykonane,
- jednoznaczność: przebieg algorytmu jest jednoznaczny (deterministyczny) w każdym kroku.

Biorąc pod uwagę praktyczne wykorzystanie algorytmów, często również zakłada się następujące ich własności:
- adaptacyjność – małe zmiany w specyfikacji problemu powodują niewielkie zmiany w algorytmie,
- wytrzymałość – niepoprawne dane wejściowe nie powodują powstawania niepoprawnego wyniku,
- optymalność – algorytm znajduje rozwiązanie przy minimalnym wykorzystaniu zasobów.