Strona główna

1. Obliczalność problemu. Problemy decyzyjne i optymalizacyjne-zależności. Algorytm jest poprawny, gdy dla każdego egzemplarza problemu algorytmu zatrzymuje się i daje poprawny wynik. Mówimy wtedy, że poprawny algorytm „rozwiązuje”


Pobieranie 76.98 Kb.
Data19.06.2016
Rozmiar76.98 Kb.
1.Obliczalność problemu. Problemy decyzyjne i optymalizacyjne-zależności.

Algorytm jest poprawny, gdy dla każdego egzemplarza problemu algorytmu zatrzymuje się i daje poprawny wynik. Mówimy wtedy, że poprawny algorytm „rozwiązuje” zadany problem obliczeniowy. Algorytm niepoprawny może się nigdy nie zatrzymać albo po zatrzymaniu dać wynik zły. Niepoprawne algorytmy mogą być jednak użyteczne, jeśli ich błędne działanie może być kontrolowane. Algorytm może być przedstawiany w postaci programu komputerowego albo zrealizować sprzętowo. Jedynym wymaganiem jest precyzja opisu wynikającej z niego procedury obliczeniowej.

Problemy decyzyjne – problemy, na które można dać odpowiedź tak lub nie.

Np. problemy z dziedzin: teorii liczb, teorii grafów, teorii automatów



Problemy optymalizacyjne – ekstremalizacja pewnej funkcji celu.W sensie „natury obliczeniowej” można badać w ten sam sposób co problemy decyzyjne. Problem optymalizacyjny można sprowadzić do problemu decyzyjnego. Taki problem decyzyjny nie jest obliczeniowo trudniejszy niż odpowiadający mu problem optymalizacyjny.

Jeśli problem decyzyjny jest obliczeniowo „trudny” (NP.-zupełny), to trudny jest również problem optymalizacyjny.



Teoria złożoności obliczeniowej w odniesieniu do problemów decyzyjnych.

Pytanie: czy dla rozważanego problemu istnieje w ogóle jakiś rozwiązujący go algorytm (tzn. procedura pozwalająca dać odpowiedź tak lub nie).

Odpowiedź, to stwierdzenie czy problem jest rozstrzygalny czy nierozstrzygalny.

Postulat rozróżniania algorytmów lepszych i gorszych z obliczeniowego punktu widzenia: czas i zajętość pamięci. Istnieje wiele algorytmów, dla których nie udało się podać „dobrych” algorytmów, ale sprowadzają się te problemy do siebie nawzajem, tak że znając rozwiązanie jednego z nich, można w wielomianowym czasie skonstruować rozwiązanie innego.



Def. Przez problem Π rozumiany będzie zbiór parametrów, które nie muszą mieć nadanych wartości, oraz zdanie określające właściwości jakie powinno mieć rozwiązanie tego problemu. Ustalając wartości wszystkich parametrów problemu Π otrzymamy konkretny problem (instalację) I. Zbiór wszystkich konkretnych problemów oznaczamy przez DΠ .
2. Kodowanie problemu. Rozsądna reguła kodowania. Długość łańcucha kodującego

Dane konkretnego I є DΠ (I-instancja,DΠ-zbiór problemów) , kodowane są za pomocą skończonego łańcucha x(I) symboli należących do z góry określonego alfabetu Σ zgodnie z ustalonymi regułami kodowania. Rozmiar konkretnego problemu N(L), to długość łańcucha danych x(I).



Reguły kodowania powinny spełniać następujące postulaty: 1.Łańcuch symboli kodujących dane konkretnego problemu nie może zawierać nadmiarowych symboli, 2. Liczby występujące w danych powinny być zapisane dwójkowo lub przy użyciu dowolnej innej ustalonej podstawie liczenia większej od 1.

Można przyjąć każdą „rozsądną” regułę kodowania, która nie powoduje wykładniczego wzrostu rozmiaru kodowania konkretnego problemu w stosunku do innych reguł kodowania. W praktyce dogodne jest wyrażanie rozmiaru problemu za pomocą jednego parametru, określającego liczbę elementów zbioru charakterystycznego dla danych rozważanego konkretnego problemu. Np. dla określenia maksymalnego przepływu w sieciach – liczba wierzchołków w sieci.



Problemowi decyzyjnemu Π i regule kodowania e odpowiada język L(Π,e) = {x(I) є Σ*: I є DΠ Σ jest alfabetem używanym przez e odpowiedź na I brzmi „tak”}.

Σ* - zbiór wszystkich skończonych łańcuchów symboli należących do Σ

Rozwiązania problemu Π odpowiada rozpoznanie języka L(Π,e) . Algorytm rozwiązuje problem Π, jeśli znajduje rozwiązanie dla każdego konkretnego problemu I є DΠ

Def.Funkcja f(k) jest rzędu g(k), co zapisuje się O(g(k)), jeśli istnieje taka stała c, że |f(k)| <= c * |g(k)|, dla wszystkich wartości k.
3.Funkcja złożoności obliczeniowej. DTM

Def. Funkcja złożoności obliczeniowej algorytmu A rozwiązującego problem Π będziemy rozumieli funkcję złożoności czasowej przyporządkowującą każdej wartości rozmiaru konkretnego problemu I є DΠ maksymalną liczbę elementarnych kroków maszyny cyfrowej potrzebnych do rozwiązania za pomocą algorytmu A konkretnego problemu o tym rozmiarze, tzn. funkcję fA(N(I)) = max{t: t-jest liczbą elementarnych kroków niezbędnych dla rozwiązania konkretnego problemu I є DΠ x(I)| = N(I)}

Można udowodnić, że wybór konkretnej reguły kodowania i modelu maszyny cyfrowej nie ma wpływu na rozróżnienie między algorytmami wielomianowymi i wykładniczymi.



Def.Algorytmem wielomianowym nazywamy algorytm, którego funkcja złożoności obliczeniowej jest O(p(k)), gdzie p jest pewnym wielomianem, a k rozmiarem rozwiązywanego konkretnego problemu.

Każdy algorytm, którego funkcja złożoności nie może być tak ograniczona, nazywa się algorytmem wykładniczym! Funkcja złożoności obliczeniowej tych algorytmów nie musi być funkcją wykładniczą!

Algorytmy wielomianowe-efektywne ,- Algorytmy wykładnicze-nie efektywne

Klasy złożoności obliczeniowej - Uogólnione modele maszyn cyfrowych: -maszyna o dostępie swobodnym RAM; - maszyna Turinga (DTM)Maszyna Turinga

Maszyna Turinga jest prostym urządzeniem algorytmicznym, które pozwala na wykonanie nawet najbardziej złożonych algorytmów. Maszyna Turinga jest mechanizmem powstałym w wyniku ciągu uproszczeń: danych, sterowania nimi oraz uproszczeń podstawowych operacji. Maszynę tą wymyślił w roku 1936 brytyjski matematyk A.M.Turing. Z DTM korzysta się gdy problem ma złożoność obliczeniową „wyższego rzędu”.

PODSTAWOWY MODEL MASZYNY TURINGA

Maszyna Turinga jest z przedstawionych modeli najprostszym modelem matematycznym komputera.

Podstawowy model przedstawiony na rysunku 2 ma skończone sterowanie, taśmę wejściową podzieloną na komórki (kwadraty) oraz głowicę taśmy, mogącą obserwować w dowolnej chwili tylko jedna komórkę taśmy. Taśma ma komórkę położoną najbardziej na lewo, ale jest prawostronnie nieskończona. Każda z komórek taśmy może zawierać dokładnie jeden symbol z skończonego alfabetu symboli. Przyjmuje się umownie, że ciąg symboli wejściowych umieszczony jest na taśmie począwszy od lewej, pozostałe komórki ( na prawo od symboli wejściowych) są wypełnione specjalnym symbolem taśmowym noszącym nazwę symbolu pustego.

Maszyna Turinga składa się z następujących elementów: -skończonego alfabetu symboli; -skończonego zbioru stanów; -nieskończonej taśmy z zaznaczonymi kwadratami, z których każdy może zawierać pojedynczy symbol; -ruchomej głowicy odczytująco - zapisującej, która może wędrować wzdłuż taśmy przesuwając się na raz o  jeden kwadrat; -diagramu przejść między stanami, zawierającego instrukcje, które powodują, że zmiany następują przy każdym zatrzymaniu się.

Def. wielotaśmowej maszyny Turinga - Struktura wielotaśmowej maszyny Turinga zawiera k taśm np. prawostronnie nieskończonych. Każda taśma podzielona jest na klatki. W każdej klatce może być umieszczony jeden symbol ze skończonego alfabetu, zwanego alfabetem symboli roboczych. Każda taśma posiada głowicę, która może poruszać się po taśmie oraz czytać lub pisać na niej symbole robocze. Operacje wielotaśmowej maszynyTuringa wyznaczone są przez pewien skończony zbiór stanów i sterowanie zawsze jest w jednym z takich stanów. Formalnie maszynę Turinga (MT) nazywamy:

M = ,, ð, q0, B, F > gdzie: Q – jest skończonym zbiorem stanów, – skończony zbiór dopuszczalnych symboli taśmowych, B – symbol pusty należący do , – podzbiór nie zawierający B, zwany zbiorem symboli wejściowych, ð - funkcja następnego ruchu, będąca odwzorowaniem

Q x Q x x { L, P } dla maszyny jednotaśmowej i

Q x k Q x ( x { L, P })k dla maszyny k – taśmowej.

Gdzie: L- oznacza ruch w lewo; P- ruch w prawo, q0- stan początkowy, F Q - zbiór stanów końcowych



Maszyny Turinga potrafią rozwiązać każdy efektywnie rozwiązywalny problem algorytmiczny(oczywiscie pomijajac czas)


  1. Klasy P i NP problemów. Schemat klas problemów decyzyjnych.

Najczęściej spotykane rzędy złożoności

1:stała log2n:logarytmiczna n:liniowa nlog2n:liniowo-logarytmiczna n2:kwadratowa n3:sześcienna nc:wielomianowa cn,n!:wykładnicza



Klasa P to wszystkie problemy, dla których rozwiązania można znaleźć w czasie co najwyżej wielomianowym (polynomial time). Klasa NP to wszystkie problemy, których rozwiązania pozytywne razem z odpowiednim certyfikatem można potwierdzić w czasie wielomianowym.Przykładem problemu klasy NP jest pytanie "czy liczba jest złożona". Certyfikatem jest tutaj dowolny dzielnik, a algorytm sprawdzający to po prostu podzielenie i sprawdzenie czy jest reszta.

Klasa Co-NP to wszystkie problemy, których rozwiązania negatywne razem z odpowiednim certyfikatem można potwierdzić w czasie wielomianowym.Jeśli problem X należy do NP to problem NIE-X należy do Co-NP. Tak więc przykładowym problemem klasy Co-NP może być pytanie "czy liczba jest pierwsza". Rozwiązanie negatywne, którego certyfikatem jest dzielnik może być łatwo sprawdzone.Klasa Co-NP sama w sobie nie wnosi nic nowego - można ją skonstruować za pomocą klasy NP i prostej operacji negacji. Najciekawszym problemem w którym klasa ta występuje jest pytanie o właściwości klasy będącej częścią wspólną NP i Co-NP.

Klasa P jest oczywiście podzbiorem zarówno dla NP jak i dla Co-NP. Problem klasy P można rozumieć jako problem klas NP bez certyfikatu.

Pytanie czy istnieją problemy klasy NP które nie są problemami klasy P pomimo dziesiątek lat prób rozwiązania pozostaje do dziś bez odpowiedzi. Są trzy możliwe rozwiazania przy czym pierwsze z nich wydaje się być mało prawdopodobne. - Wszystkie znane problemy klasy NP są ze sobą powiązane. Oznacza to, że każdy problem, który jest NP można sprowadzić do innego problemu NP. To z kolei oznacza, że udowodnienie, że przynajmniej jeden problem klasy NP należy w rzeczywistości do klasy P, będzie jednocześnie udowodnieniem, że P = NP.



Określenia P i NP są też często używane do oznaczenia złożoności odpowiednio co najwyżej wielomianowej (wielomianowej) i większej niż wielomianowa (wykładniczej). Mimo iż to użycie nie jest matematycznie poprawne, rzadko jest to źródłem problemów.

Złożoność obliczeniowa definiuje się jako ilość zasobów komputera jaką potrzebuje algorytm. Pojęcie to wprowadzili J. Hartmanis i R. Stearns. Najczęściej jako zasób rozumie się czas, oraz pamięć - dlatego też używa się określeń "złożoność czasowa" i "złożoność pamięciowa".

Za jednostkę złożoności pamięciowej przyjmuje się pojedyncze słowo maszyny (np. bajt).



W przypadku złożoności czasowej nie można podać bezpośrednio jednostki czasu, np. milisekundy, bowiem nie wiadomo na jakiej maszynie dany algorytm będzie wykonywany. Dlatego też wyróżnia się, charakterystyczną dla algorytmu, operację dominującą. Liczba wykonań tej operacji jest proporcjonalna do wykonań wszystkich operacji.

Rozróżnia się dwa rodzaje złożności: - złożoność pesymistyczna: określa złożonośc w "najgorszym" przypadku. Jeśli D to zbiór wszystkich możliwych danych wejściowych, d jeden z elementów tego zbioru, a f funkcja która dla podanego d zwraca liczbę operacji, to złożoność pesymistyczna jest zdefiniowana jako:sup {f(d):d nal.do D} - złożoność oczekiwana: określa złożoność średnią, czyli złożność w przypadku "przeciętnych" danych wejściowych. [wymaga uzupełnienia o wzór]

Złożoność obliczeniowa nie jest zbyt wygodna w stosowaniu, bowiem operacja dominująca na jednym komputerze może wykonywać się błyskawicznie, na innym zaś musi być zatąpiona szeregiem instrukcji.
5. Problemy NP-zupełne.

Klika w grafie nieskierowanym G=(V,E)to podzbiór V'V w którym każda para wierzchołków jest połączona krawędzią do E. Inaczej mówiąc klika to pełny podgraf grafu G. Rozmiar kliki to liczba wierzchołków, które zawiera. Problem kliki to optymalizacyjny problem znalezienia w grafie kliki max. Rozmiaru. W wersji dezycyjnej pytamy poprostu,czy istnieje w grafie klika danego rozmiaru k. Formalna def.to: CLIQUE= {:G: G jest grafem zawierającym klikę rozmairu k} Algorytm naiwny stwierdzenia czy graf G=(V,) o |V| wierzchołkach zawiera klikę rozmiaru k polega na przejrzeniu wszystkich k-podzbiorów zbioru Vi sprawdzeniu każdego z nich, czy aby nie tworzy onkliki. Czas działania tego algorytmu równy W(k2(|V| po k)) jest wielomianowy, jeśli k jest stałą. Ogólnie k moze być proporcjonalne do |V| a wówczas algorytm działa w czasie większym niż wilomainowy. Jak można przypuszczać efektywny algorytm dla problemu kliki najprawdopodobniej NIE istnieje.

Pokrycie wierzchołkowe grafu nie skierowane go G = (V, E) to podzbiór V 'V taki, że jeśli (u, v)=E, to uV” lub vV'. Inaczej mówiac, każdy wierzchołek „pokrywa" incydentne z nim krawędzie, a pokryciem wierzchołkowym G jesi zbiór wierzchołków pokrywający wszystkie krawędzie zbioru E. Rozmiar pokrycia wierzchołkowego to liczba składających się na nie wierzchołków. Problem pokrycia wierzchołkowego polega na znalezieniu w danym grafie pokrycia wierzchołkowego minimalnego rozmiaru. Przeformulowując ten problem optymalizacyjny na decyzyjny, chcemy stwierdzić, czy graf ma pokrycie wierzchołkowe danego rozmiaru k. Trzymając się terminologii jeżyków formalnych, definiujemy

VERTEX-COVKR = {: graf G ma pokrycie wierzchołkowe rozmiaru k} Poniższe twierdzenie mówi, że problem ten jest NP-zupelny.

Podział zbioru - Zbiory A i B są rozłączne, jeżeli: nie mają wspólnych elementów, tzn. jeżeli AUB=0. Zbiór Y ={Si;} niepustych zbiorów tworzy podział zbioru S, jeżeli zbiory w Y parami rozłączne, co znaczy, że jeśli Si ,Sj Y , to Si Sj = oraz ich suma jest S (S= Usi Y Si) Innymi słowy Y tworzy podział S jeżlei każdy elem. S wystęuje w dokładnie jednym zbiorze Si Y

Problem znalezienia cyklu Hamiltona w grafie nieskierownaym badano od przeszło stu lat. Cykl Hamiltona w grafie nieskierowanym G=(V,E) too cykl prosty zawierający wszystkie wierzchołki zbioru V. Graf,który ma cykl Hamiltona nazywamy hamiltonowskim, w przeciwnym razie jest niehamiltonowski. HAM-CYCLE={:G jest grafem hamiltonowskim}

Problem 3-wymiarowego skojarzenia jet problemem silnie NP-zupełnym ! (SNPC) M WxXxY |W|=|X|=|Y|=q q=|M'| - skojarzenie
6. Sformułowanie i przykłady problemu plecakowego:

Dany jest plecak o pojemności b oraz zbiór A różnych przedmiotów {a1,a2...an}, z których każdy ma określony rozmiar w(ai) oraz wartość s(ai).

Parametry: skończony zbiór elementów A={a1,a2,...,an}, rozmiar s(ai) oraz wartość w(ai), będący liczbą naturalną, stała b=const. oznaczająca pojemność plecaka i y=const będąca wartością progową funkcji celu, w tym przypadku dolną granicą łącznej wartości pakowanych do plecaka przedmiotów.

Pytanie: czy istnieje podzbiór zbioru A, taki że:

Suma rozmiarów elementów ai jest niewiększa niż b (wszystkie przedmioty mieszczą się w plecaku)

Suma wartości elementów ai jest niemniejsza od b?

Przykład: Instancja : zbiór A składa się z 5 elementów o rozmiarach a1=5,a2=3,a3=2,a4=4,a5=3 i wartościach a1=3,a2=4,a3=2,a4=6,a5=1 oraz pojemność b=10 i stała y=12. Czy można dobrać tak elementy, by suma była niewiększa od pojemności plecaka a łączna wartość niemniejsza od 12? TAK!

Problem plecakowy (optymalizacyjnie).

Parametry: skończony zbiór elementów A={a1...a5}, z których każdy ma określoną rozmiar s(ai) i wartość w(ai), a także pojemność plecaka b=10.

Brak tu stałej y, ponieważ rozwiązanie wymaga ekstremalizacji funkcji celu. Należy znaleźdź taki podzbiór zbioru A,że łączny rozmiar elementów jest niewiększy od 10, a łączna wartość jest możliwie największa.


9. Algorytmy sortowania

QuickSort Algorytm sorotwania szybkiego jest uważany za najszybszy algorytm dla danych losowych.
Zasada jego działania opiera się o metodę dziel i zwyciężaj. Zbiór danych zostaje podzielony na dwa podzbiory i każdy z nich jest sortowany niezależnie od drugiego.

Jak działa przykład: Dla zadanej tablicy a[l..p] wybieramy element v=a[l] i przeszukujemy resztę tablicy (tzn. a[l+1..p]) tak długo, aż nie znajdziemy elementu nie większego niż a[l]. Następnie przeszukujemy tą tablicę od strony prawej póki nie znajdziemy elementu nie większego niż a[l]. Gdy to osiągniemy, zamieniamy miejscami te dwa elementy i zaczynamy cały proces od początku. Algorytm działa tak długo, aż wskaźnik poruszający się w lewo i wskaźnik poruszający się w prawo spotkają się. Należy wówczas zamienić element v=a[l] z ostatnim elementem lewej części tablicy. Mimo, że w najgorszym przypadku algorytm ma złożoność kwadratową, jest on bardzo często stosowany. Powodem tego jest niska- liniowologarytmiczna, złożoność w średnim przypadku.



HeapSort Jest to metoda bardziej skomplikowana niż sortowanie bąbelkowe czy przez wstawianie, ale za to działa w krótszym czasie. Zrozumienie algorytmu HeapSort wymaga zaznajomienia się z pojęciem Kopca/Stogu.

Budowa drzewa binarnego z elementów tablicy, którą mamy posortować wygląda następująco:

Zaczynamy od pierwszego elementu tablicy, który będzie korzeniem.Każdy następny i-ty element tablicy będzie miał co najwyżej dwa następniki o wyrazach odpowiednio: 2*i oraz 2*i+1 Łatwo stwierdzić, że dla każdego i-tego elementu (oprócz korzenia) numer elementu w tablicy, będącego jego poprzednikiem określa się wzorem: i div 2



Po zbudowaniu drzewa należy wykonać odpowiednie instrukcje, które zapewnią mu warunek kopca. Należy więc sprawdzać (poczynając od poprzednika ostatniego liścia schodząc w górę do korzenia) czy poprzednik jest mniejszy od następnika i jeżeli tak jest to zamienić je miejscami. Po wykonaniu tych czynności drzewo binarne zamieniło się w stóg. Z jego własności wynika, że w korzeniu znajduje się największy element. Korzystając z tego faktu możemy go pobrać na koniec tablicy wynikowej a na jego miejsce wstawić ostatni liść. Po pobraniu korzenia tablica źródłowa zmniejszyła się o 1 element a porządek kopca został zaburzony (nie wiadomo, czy ostatni liść będący teraz korzeniem jest rzeczywiście największym elementem). By przywrócić warunek stogu należy ponownie uporządkować jego elementy, tym razem jednak zaczynając od korzenia (ponieważ to on jest nowym elementem). Po przywróceniu porządku w kopcu możemy znów pobrać korzeń i wstawić go do tablicy wynikowej (tym razem na drugie miejsce od końca), wstawić na jego miejsce liść i zmniejszyć rozmiar tablicy źródłowej o 1. Tu pętla się zamyka. Wykonujemy te czynności aż do ostatniego korzenia. Po całkowitym wyczyszczeniu kopca w tablicy wynikowej będziemy mieli posortowane elementy z tablicy wejściowej. Aby zlikwidować drugą tablicę (co zwiększa złożoność pamięciową algorytmy) wystarczy w kolejnych krokach odkładać korzenie w tej samej tablicy, od końca zmniejszając jednocześnie zmienną, która odpowiada za liczbę elementów kopca. Po zmniejszeniu tej liczby algorytm nie będzie "widział" tylnej, posortowanej już części tablicy.Złożoność tego algorytmu to O(nlogn).

SelectionSort Metoda ta nazywana jest sortowaniem przez wymianę gdyż na początku szukany jest najmniejszy element, po znalezieniu go jest on zamieniany z pierwszym elementem tablicy. Następnie szukany jest znów najmniejszy element, ale począwszy od elementu drugiego (pierwszy - najmniejszy jest już wstawiony na odpowiednie miejsce), po jego znalezieniu jest on zamieniany z drugim elementem. Czynność tą powtarzamy kolejno na elementach od trzeciego, czwartego, aż do n-tego.

InsertionSort Zasada działania tego algorytmu jest często porównywana do porządkowania kart w wachlarz podczas czasie gry. Każdą kartę wstawiamy w odpowiednie miejsce, tzn. po młodszej, ale przed starszą. Podobnie jest z liczbami.
Pierwszy element pozostaje na swoim miejscu. Następnie bierzemy drugi i sprawdzamy, w jakiej relacji jest on z pierwszym. Jeśli jest niemniejszy, to zostaje na drugim miejscu, w przeciwnym wypadku wędruje na pierwsze miejsce. Dalej sprawdzamy trzeci element (porównujemy go do dwóch pierwszych i wstawiamy w odpowiednie miejsce), czwarty (porównujemy z trzema pierwszymi), piąty itd. Idea działania algorytmu opiera się na podziale ciągu na dwie części: pierwsza jest posortowana, druga jeszcze nie. Wybieramy kolejną liczbę z drugiej części i wstawiamy ją do pierwszej. Ponieważ jest ona posortowana, to szukamy dla naszej liczby takiego miejsca, aby liczba na lewo była niewiększa a liczba na prawo niemniejsza. Wstawienie liczby do posortowanej tablicy wymaga więc czasu O(n). Wynika z tego złożoność algorytmy: O(n2) Oto przykład dla nieposortowanego ciągu <2, 4, 1, 3>

BubbleSort Jest to jeden z prostszych algorytmów sortowania. Sprawdzamy całą tablicę od końca, jeżeli trafimy na parę elementów, w której większy poprzedza mniejszy to zamieniamy je miejscami i znów zaczynamy przeszukiwać tą tablicę od końca. Czynność powtarzamy tak długo aż podczas sprawdzania całej tablicy, nie zajdzie ani jedna zamiana elementów. Realizuje sięto najczęściej za pomocą zmiennej logicznej. Algorytm nosi nazwę bąbelkowego, gdyż najmniejsze liczby "wypływają" z dołu tablicy na jej szczyt.

Oto przykład zastosowania dla nieuporządkowanego ciągu liczb <<2, 4, 1, 3>>.

Przy następnym przebiegu nie zajdzie ani jedna zmiana, to znak, że ciąg jest już posortowany.
Z powyższego zdania można wyciągnąć wniosek, że gdy ciąg wejściowy będzie posortowany, to algorytm wykona tylko jeden przebieg. Jest to duża zaleta tego sposobu sortowania, niektóre metody będą sortowały ciąg nawet jeśli będzie on posortowany. Z kolei najgorszym zestawem danych dla tego algorytmu jest ciąg posortowany nierosnąco.

CoutingSort Sortowanie przez zliczanie ma jedną potężną zaletę i jedną równie potężną wadę: Zaleta: działa w czasie liniowym (jest szybki)

Wada: może sortować wyłącznie liczby całkowite Obydwie te cechy wynikają ze sposobu sortowania. Polega ono na liczeniu, ile razy dana liczba występuje w ciągu, który mamy posortować. Następnie wystarczy utworzyć nowy ciąg, korzystając z danych zebranych wcześniej. Np. mamy posortować ciąg: 3,6,3,2,7,1,7,1. Po zliczeniu (w jednym korku) operujemy danymi na temat liczności poszczególnych liczb:

Liczba 1 występuje 2 razy Liczba 2 występuje 1 raz Liczba 3 występuje 2 razy Liczba 4 występuje 0 razy Liczba 5 występuje 0 razy Liczba 6 występuje 1 raz

Liczba 7 występuje 2 razy Na podstawie tych danych tworzymy ciąg: 1,1,2,3,3,6,7,7. Jest to ciąg wejściowy, ale posortowany. Należy zauważyć trzy ważne rzeczy: 1.Proces zliczania odbył się w jednym kroku 2.Nie doszło do ani jednej zamiany elementów 3.Proces tworzenia tablicy wynikowej odbył się w jednym kroku

Algorytmy ten posiada jednak również wady: 1.Do przechowywania liczby wyrazów ciągu musimy użyć tablicy, o liczbie elementów równej największemu elementowi ciągu 2.Sortować można jedynie liczby całkowite

RADIXSORT Sortowanie pozycyjne opiera się na sortowaniu przez zliczanie. Jeżeli nie wiesz co to jest countsort, najpierw się dowiedz. Sortowanie pozycyjne opiera się na fakcie, że w komputerze liczby reprezentowane są jako ciąg bitów. Liczby do posortowania dzielimy na grupy e-bitowe (po e bitów w każdej grupie). Radixsort polega na sortowaniu countsortem po kolejnych najmniej znaczących grupach bitów. Bardzo ważny jest tutaj fakt, że algorytm countsort jest stabilny. Dzięki temu sortując po pierwszych bitach nie zaburzymy porządku ustalonego podczas sortowania po mniej znaczących bitach.

Przykład: Do posortowania są liczby

10001010 (=138) 01101011 (=107) 10001101 (=141) 00110111 (=55)

Jeżeli podzielimy je na grupy 2-bitowe (e=2) to wyglądają one tak:

10_00_10_10 01_10_10_11 10_00_11_01 00_11_01_11

I sortujemy po kolejenych grupach od prawej. Będą cztery przebiegi. Po kolejnych przebiegach mamy: (na czerwono jest grupa, po której właśnie posortowano)

1.10_00_11_01 10_00_10_10 01_10_10_11 00_11_01_11

2.00_11_01_11 10_00_10_10 01_10_10_11 10_00_11_01

3.10_00_10_10 10_00_11_01 01_10_10_11 00_11_01_11

4.00_11_01_11 (=55) 01_10_10_11 (=107) 10_00_10_10 (=138) 10_00_11_01 (=141)



Złożoności pesymistyczna i oczekiwana radixsorta wynoszą O(n+m). Niestety współczynnik stojący przy sumie (m+n) jest dosyć duży, więc dla małych danych algorytm jest dosyć wolny. Dla dużych danych jest jednak potrzebny spory dodatkowy narzut pamięci (ze względu na wykorzystanie countosorta). Po modyfikacjach , algorytmu radixsort można z powodzeniem używać do sortowania słów w porządku alfabetycznym lub liczb rzeczywistych z jakiegoś przedziału.

BUCKETSORT Sortowanie kubełkowe (ang. bucket sort) to algorytm sortowania działający w czasie liniowym, tzn. O(n). Liczby przeznaczone do tego sortowania powinny być liczbami z przedziału [0;1) i powinny być dosyć równo rozłożone w tymże przedziale. Cały algorytm opiera się na podziale przedziału [0;1) na pewną ilość równych podprzedziałów, tzw. kubełków. Następnie każda z liczb przeznaczona do sortowania jest "wrzucana" do odpowiedniego kubełka. Aby otrzymać posortowane liczby najpierw sortuje się liczby w każdym z kubełków, a następnie łączy się je wszystkie po kolei.
10. Struktury drzewiaste

ZŁOŻONE STRUKTURY DANYCH – LISTY

Lista jest to liniowo uporządkowany zbiór elementów, z których dowolny element można usunąć oraz dodać w dowolnym miejscu. Pierwszy i ostatni element listy nazywamy końcami listy. Szczególnym przypadkiem listy może być stos (gdy pobrać, odczytać i wstawić element można tylko na końcu listy) lub kolejka (pobrać i odczytać element można tylko na początku listy, a dodać na końcu).
Listy mogą być posortowane (najmniejszy element jest w korzeniu). Rozważmy przypadek jednokierunkowej listy posortowanej.
Aby dodać element do listy posortowanej należy sprawdzić, w którym miejscu powinien się on znajdować. Sprawdzamy od korzenia, schodząc w dół, jeśli element, który chcemy dodać jest większy od badanego węzła i mniejszy od jego następnika, to należy umieścić go między nimi. Musimy więc ustawić wskaźnik aktualnego węzła na dodawany element, a wskaźnik tego elementu na następnik. Ponieważ jest to lista jednokierunkowa, przeszukiwanie jej należy zawsze zaczynać od korzenia. Dodając więc pierwszy element do pustej listy należy zapamiętać jego wskaźnik, by później móc się do niego przenieść.
W przeciwieństwie do stosu i kolejki listy mogą zawierać dwa wskaźniki. Takie listy nazywamy dwukierunkowymi, poruszać się możemy w niej w obydwu kierunkach, co przyspiesza wszystkie operacje. Analogicznie odejmowanie elementu nie powinno sprawić problemu .

Drzewo BST (binary search tree) jest drzewem binarnym. Oprócz pola wartości drzewo BST posiada jeszcze dwa pola: L i P, wskazujące odpowiednio na lewy i prawy następnik. Drzewo BST ma szczególną własność: - jeżeli element drzewa znajduje się w lewej gałęzi to jest mniejszy od swego poprzednika ; - jeżeli element drzewa znajduje się w prawej gałęzi to jest większy od swego poprzednika

Przeszukiwanie drzewa: - Wzdłużna - preorder: korzeń, lewe poddrzewo, prawe poddrzewo. ; - Poprzeczna - inorder: lewe poddrzewo, korzeń, prawe poddrzewo.

- Wsteczne - postorder: lewe poddrzewo, prawe poddrzewo, korzeń. Dodawanie_elementów: Jeśli drzewo BST jest puste (korzeń=nil) należy wstawić element (nie porównujemy go z innymi), w przeciwnym wypadku porównujemy wartość elementu z następnikami każdego węzła (zaczynając od korzenia). Jeżeli wartość elementu jest niewiększa od wartości porównywanego wierzchołka to przechodzimy do lewego następnika, w przeciwnym razie przechodzimy do prawego następnika. Krok ten powtarzamy aż znajdziemy dla naszego elementu odpowiedznie miejsce, tzn. gdy następnik, do którego powinniśmy iść jest pusty (nil). Następnie wstawiamy element jako odpowiedni następnik (prawy, jeśli element jest większy od węzła, lewy jeśli niewiększy). Usuwanie_elementów: Jeżeli usuwany element nie ma nastepników to można zwolnić przydzieloną mu pamięć. Jeśli element do usunięcia ma jeden następnik należy go połączyć (następnik) z poprzednikiem usuwanego elementu. Jeśli element ma dwa następniki mozna go usunąć na dwa sposoby: - połączyć poprzednik elementu z wierzchołkiem o najmniejszej wartości z prawego poddrzewa usuwanego, - połączyć poprzednik elementu z wierzchołkiem o największej wartości z lewego poddrzewa. Usuwanie_drzewa: Można to zrobić na dwa sposoby: od końca, schodząc za każdym razem od korzenia lub od korzenia. Ta druga metoda jest znacznie szybsza, wymaga jednak zastosowania stosu, na którym umieszczamy następniki usuwanego elementu. Po usunięciu elementu zdejmujemy ze stosu następny do usunięcia, umieszczamy na stosie jego następniki itd...


11. Algorytmy grafowe. Cykle, MDR w grafach.

W informatyce grafem nazywamy strukturę G=(V, E) składającą się z węzłów (wierzchołków, oznaczanych przez V) wzajemnie połącznonych za pomocą krawędzi (oznacznych przez E). Grafy dzielimy na grafy skierowane i nieskierowane. Niech V będzie niepustym zbiorem i niech A zawiera się w V x V. Parę G=(V,A) nazywamy grafem skierowanym (zbiór V - zbiór wierzchołków, zbiór A - zbiór łuków). Niech V będzie niepustym zbiorem i niech E zawiera się w {{vi,vj}: vi należy do V i vj należy do V}. Parę G=(V,E) nazywamy grafem nieskierowanym (zbiór V - zbiór wierzchołków, zbiór E - zbiorem krawędzi).



Jeśli krawędź łączy dwa wierzchołki to jest z nimi incydentna. Pętla własna to krawędź łączące wierzchołek z samym sobą.
Stopień wierzchołka w grafie nieskierowanym to liczba incydentnych z nim krawędzi. Istnieje kilka algorytmów do przechowania grafu w pamięci.

Macierz sąsiedztwa: Budujemy tablicę o rozmiarach V*V, gdzie V-liczba wierzchołków. Następnie wypełniamy ją zerami- jeśli dwa wierzchołki nie są połączone krawędzią i jedynkami- jeśli dwa wierzchołki są połączone. Widać, że macierz jest symetryczna. Stosując tablicę dynamiczną można więc zmniejszyć rozmiar macierzy do połowy zapisując ją jako macierz dolno-(górno)-trójkątną. Złożoność pamięciowa O(V2).

Macierz incydencji: To tablica o rozmiarach V*E. Składa się ona z E kolumn i V wierszy, jeśli krawędź wychodzi z danego wierzchołka to piszemy w odpowiedniej kolumnie (-1), jeśli do niego wchodzi piszemy (+1), jeśli wierzchołek nie należy do krawędzi piszemy 0, jeśli jest to pętla własna piszemy 2. Zł. pamięciowa O(E*V).

Lista incydencji: Należy utworzyć listę dla każdego wierzchołka v, w której przechowujemy zbiór wierzchołków połączonych krawędzią z v. Lista dla grafu z rysunku 1 wygląda następująco:

1: 2, 3, 5 2: 1, 3, 4 3: 1, 2, 4 4: 2, 3, 5 5: 4, 1 Złożoność pamięciowa O(E+V).



Lista krawędzi: Jest to lista, na której przechowujemy wszystkie krawędzie występujące w grafie.
Przykład dla grafu skierowanego z rys.2:

1 – 2 2 - 4 2 - 5 3 - 1 3 - 2 4 - 3 5 - 1 5 - 4

Zapisując przy pomocy tej reprezentacji graf, w którym występują krawędzie skierowane i nieskierowane należy w przypadku krawędzi nieskierowanej z u do v zapisać krawędź dwukrotnie: u - v oraz v – u. Złożoność pamięciowa O(E).

Przeszukiwanie w głąb i w szerz: Procedury przeglądania grafu w głąb (DFS) i wszerz (BFS) są bardzo często wykorzystywane w innych, bardziej złożonych algorytmach (np. badania spójności). W strategii DFS wybrany wierzchołek należy umieścić na stosie, zaznaczyć jako odwiedzony a następnie przejść do jego następnika. Następnik również umieszczamy na stosie, zaznaczamy jako odwiedzony przechodzimy do jego następnika. Jak widać procedurę można wywoływać rekurencyjnie. Jeśli dojdziemy do takiego wierzchołka, że nie ma on krawędzi incydentych z nieodwiedzonymi wierzchołkami, należy usunąć go ze stosu i pobrać ze stosu kolejny wierzchołek do przeszukania. W praktyce stosuje się zasadę, że jeśli przeszukiwany wierzchołek jest połączony krawędziami z wieloma wierzchołkami, wybiera się do przeszukania wierzchołek o najmniejszej liczbie porządkowej. Dlatego szukając kolejny nieodwiedzony następnik należy rozpoczynać od końca macierzy. Przeszukiwanie DFS wykorzystuje się do badania spójności grafu. Jeśli procedura wywołana dla pierwszego wierzchołka "dotrze" do wszystkich wierzchołków grafu to graf jest spójny. Aby przeszukać graf wszerz (BFS) należy zamiast stosu wykorzystać kolejkę do przechowywania wierzchołków a kolejnych nieodwiedzonych następników szukać od początku macierzy.
Oto przykładowy graf: - w wyniku wywołania procedury DFS dla danego grafu otrzymamy wierzchołki w następującej kolejności: 1,2,4,5,3,6. - w wyniku wywołania procedury BFS dla danego grafu otrzymamy wierzchołki w kolejności: 1,2,3,4,5,6.

Cykl Eulera: To taki cykl w grafie, który zawiera każdą krawędź grafu dokładnie raz. Warunkiem istnienia cyklu są: -spójność grafu,

- dla grafu skierowanego należy sprawdzić czy do każdego wierzchołka wchodzi tyle samo krawędzi co wychodzi, - dla grafu nieskierowanego z każdego wierzchołka musi wychodzić parzysta liczba krawędzi. Szukanie_cyklu: Zaczynamy od dowolnego wierzchołka (w naszym przypadku będzie to ten z najmniejszym indeksem), dodajemy ten wierzchołek na stos i idziemy do następnego, osiągalnego z niego wierzchołka z najmniejszym indeksem, a łącząca go z nim drogę usuwamy (rys.1), dodajemy ten wierzchołek na stos i idziemy do następnego, osiągalnego wierzchołka z najmniejszym indeksem, a łączącą go z nim drogę usuwamy (rys.2),itd...


Jeżeli nie możemy już nigdzie pójść pobieramy element ze stosu (będzie on kolejnym w cyklu) i teraz z ostatniego wierzchołka na stosie idziemy dalej (rys. 4). Czynność powtarzamy tak długo jak długo mamy jakieś wierzchołki na stosie. Graf posiada cykl Hamiltona, jeśli istnieje w nim cykl (droga, która zaczyna się i kończy w tym samym wierzchołku), który zawiera każdy wierzchołek dokładnie raz. Algorytm znajdujący cykl Hamiltona w grafie jest znacznie bardziej skomplikowany, niż w przypadku cyklu Eulera. Nie istnieje żaden algorytm rozwiązujący ten problem w czasie wielomianowym, algorytm należy więc do klasy NP-zupełnych

MDR- Minimalne drzewo rozpinające: Niech będzie dany spójny graf nieskierowany o wierzchołkach V i krawędziach E. Ponad to z każdą krawędzią będzie związana tzw. waga, określna przez funkcję w, która oznaczają długość danej krawędzi. Jeżeli znajdziemy taki podzbiór T zawarty w zbiorze krawędzi E, który łączy wszystkie wierzchołki i taki, że suma wszystkich wag krawędzi wchodzących w skład T jest możliwie najmniejszy, to znajdziemy tzw. minimalne drzewo rozpinające. Jest znanych kilka algorytmów tworzące takie drzewo. Wszystkie one wykorzystują tzw. metodę "zachłanną". Do rozrastającego się drzewa dodawane są "najlepsze" krawędzie, w tym przypadku o najmniejszej wadze.

Algorytm Kruskala: Algorytm polega na łączeniu wielu poddrzew w jedno za pomocą krawędzi o najmniejszej wadze. W rezultacie powstałe drzewo będzie minimalne. Na początek należy posortować wszystkie krawędzie w porządku niemalejącym. Po tej czynności można przystąpić do tworzenia drzewa. Proces ten nazywa się rozrastaniem lasu drzew. Wybieramy krawędzie o najmniejszej wadze i jeśli wybrana krawędź należy do dwóch różnych drzew należy je scalić (dodać do lasu). Krawędzie wybieramy tak długo, aż wszystkie wierzchołki nie będą należały do jednego drzewa.

Algorytm Prima: Budowę minimalnego drzewa rozpinającego zaczynamy od dowolnego wierzchołka, np. od pierwszego. Dodajemy wierzchołek do drzewa a wszystkie krawędzie incydentne umieszczamy na posortowanej wg. wag liście. Następnie zdejmujemy z listy pierwszą krawędź (o najmniejszej wadze). Sprawdzamy, czy drugi wierzchołek tej krawędzi nalerzy do tworzonego drzewa. Jeżeli tak, to nie ma sensu dodawać takiej krawędzi (bo oba jej wierzchołki znajdują sięw drzewie), porzucamy krawędź i pobieramy z listy następną. Jeżeli jednak wierzchołka nie ma w drzewie, to nalerzy dodać krawędź do drzewa, by wierzchołek ten znalazł się w drzewie rozpinającym. Następnie dodajemy do posortowanej listy wszystkie krawędzie incydentne z dodanym wierzchołkiem i pobieramy z niej kolejny element. Jednym zdaniem: zawsze dodajemy do drzewa krawędź o najmniejszej wadze, osiągalną (w przeciwieństwie do Kruskala) z jakiegoś wierzchołka tego drzewa. Można zauważyć, że kluczową, z punktu widzenia wydajności algorytmu, czynnością jest zaimplementowanie listy posortowanej, gdyż po każdym dodaniu krawędzi, lista musi być nadal posortowana.

12. Algorytmy przybliżone i zachłanne.

Algorytm zachłanny Metoda "zachłanna" polega na rozpatrywaniu danych w kolejności uporządkowanej, np. posortowanej. W danym kroku wybierane są te dane, które są najodpowiedniejsze. Najczęściej metoda ta prowadzi do otrzymania rozwiązania przybliżonego, choć istnieją problemy, dla których metoda zachłanna daje roziwązanie optymalne (jest tak, gdy problem ten daje się przedstawić w postaci matroidu zob: minimalne drzewo rozpinające).

Problem komiwojażera przedstawia się następująco: komiwojażer musi odwiedzić n miast w taki sposób, by wrócił do miasta, z którego wyruszył pokonując jak najmniejszą drogę, musi wyznaczyć więc sobie taką trasę między miastami, aby całkowity koszt jego podróży był najmniejszy. Problem ten można przestawić za pomocą grafu pełnego, tzn. grafu o stuprocentowym nasyceniu krawędziowym, co oznacza, że każda para wierzchołków jest połączona krawędzią. Miasta, które musi odwiedzić komiwojażer są wierzchołkami, a drogi łączące te miasta to krawędzie z wagami, symbolizującymi koszt podróży daną drogą. Należy wyznaczyć więc cykl Hamiltona o najmniejszej sumie wag krawędzi należących do tego cyklu. Klasyczny sposób rozwiązania tego problemu polegający na sprawdzaniu długości każdego cyklu Hamiltona wymaga sprawdzenia wszystkich permutacji wierzchołków, co w konsekwencji prowadzi do złożoności wykładniczej (n!), praktyczne zastosowanie takiego algorytmu już dla kilkunastu miast jest więc niemożliwe. Nawet przy zastosowaniu powracania, gdy w każdym kroku aktualny koszt porównywany jest z najkrótszym wyznaczonym do tej pory cyklem, nie zmniejszy tej złożoności, choć może skrócić czas wykonania algorytmu w średnim przypadku, gdy najkrótsza trasa zostanie wyznaczona w pierwszych krokach. Jednak złożoność nadal będzie wykładnicza. Alternatywą dla przeglądu wyczerpującego jest zastosowanie strategii zachłannej w algorytmie aproksymacyjnym, dającym wprawdzie rozwiązanie przybliżone, lecz w czasie O(n2). Dzieje się tak przy założeniu, że funkcja kosztu podróży spełnia warunek trójkąta, to znaczy, że koszt podróży z miasta u do miasta v jest na pewno mniejszy niż suma kosztów podróży z miasta u do w i z w do v, czyli: c(u,v) < c(u,w) + c(v,w). W przypadku problemu komiwojażera nierówność ta jest spełniona, gdyż koszt podróży z miasta u do v jest po porostu odległością euklidesową między tymi miastami. Można wykazać, że odległość przybliżona jest co najwyżej dwa razy większa od odległości optymalnej. Aproksymacyjny algorytm wyznaczania najkrótszego cyklu Hamiltona w grafie polega na zastosowaniu algorytmu wyznaczającego minimalne drzewo rozpinające (metodą Kruskala lub Prima). Po zbudowaniu minimalnego drzewa rozpinającego należy przejść je metodą preorder (tzn. odwiedzać ojców przed synami) i zapisywać wierzchołki na liście tylko, gdy są odwiedzane po raz pierwszy. Przechodząc drzewo należy równocześnie sumować koszt przebycia krawędzi między dwoma kolejnymi wierzchołkami a na końcu dodać jeszcze koszt przebycia krawędzi między pierwszym i ostatnim wierzchołkiem na liście, ponieważ, zgodnie z założeniami problemu, komiwojażer musi powrócić do miasta, z którego wyruszył.
13. Metoda podziału i ograniczeń.

ALGORYTM PODZIAŁU I OGRANICZEŃ (B&B) – jest zdef przez następujące elementy, złożonośc wykładnicza w najgorszym przypadku...

Ograniczamy tak by nieograniczony obszar miał rozw. Optymalne (Bp, S,F,D,LB,UB,E,BR,RB)



Bp-reguła podziału, S-reguła wyboru,F-funkcja chcrakt. Do eliminacji rozw. Częsciowych, D- relacja dominacji,LB-dolne ograniczenie funkcji celu, UB – górne ograniczenie.... , E-reguła eliminacji, BR tolerancja, RB-ograniczenie nakładów obliczeniowych. TIME LIMIT -max akceptowany czas obliczeń, MAXDAB -max akceptowana liczność zbioru następników wierzch. podziałowego. MAXAS -max liczność zbioru wierzch. aktywnych. Po zastosoawniu BR i RB metoda staje się heurytyczną.

Nakłady obliczeniowe (porównanie) – nakłady oblicz. Nie wzrosną, mogą zmaleć gdy wierzchołki są eliminowane z powodu przekroczenia górnego ograniczenia UB poprzez funkcję LB. Nakłady obliczeń nie wzrosną gdy zastosuje się silniejszą funkcje charakterystyczną do elliminacji rozw. niedopuszczalnych. Nakłady onl. Moga wzrosnąć gdy zastosuje się silniejszą realcję eliminacji. Rozw. częsciowe z płytszym poddrzewem moze zostać usunięte.
14. Metodologia rozwiazywania problemów otwartych.

Złożoność dla problemu (optymalizacyjnego):

*** łatwy obliczeniowo: – wielomian (złożoność f) - badanie złoż. w przypadku najgorszym, - badanie złoż. w przypadku średnim

*** trudny obliczeniowo (dowód np.-zupełności) : - uproszczenia(ograniczenia problemu) -algorytmy dokładne (wykladnicze i pseudowykładnicze) - algorytmy aproksymacyjne (analiza w najgorszym przypadku,....w średnim przypadku, probabilstyczne//kazda liczba jest jednakowo prawdopodbna//, eksperymentalna)


©snauka.pl 2016
wyślij wiadomość