Algorytmy i struktury danych/Wstęp: poprawność i złożoność algorytmu: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m (Zastępowanie tekstu - "\ =\" na "=")
 
(Nie pokazano 290 wersji utworzonych przez 6 użytkowników)
Linia 2: Linia 2:
  
  
Podstawowym elementem przy rozwiązywaniu zadanego problemu na komputerze jest dobór  
+
Wykład ''Algorytmy i struktury danych'' jest poświęcony przede wszystkim koncepcyjnym i strukturalnym metodom efektywnego rozwiązywania
 +
problemów na komputerze. Podstawowym elementem przy rozwiązywaniu zadanego problemu jest dobór  
 
algorytmu i struktury danych. Najważniejszymi aspektami algorytmu są jego poprawność i  
 
algorytmu i struktury danych. Najważniejszymi aspektami algorytmu są jego poprawność i  
złożoność.
+
złożoność (czasowa i pamięciowa).
Będziemy zasadniczo rozpatrywać tylko złożoność czasową i pamięciową.
 
  
W przypadku złożoności czasowej z reguły wyróżnimy pewną operację dominującą i czas będziemy  
+
W przypadku złożoności czasowej, z reguły wyróżnimy pewną operację dominującą, a czas będziemy  
 
traktować jako liczbę wykonanych operacji dominujących.  
 
traktować jako liczbę wykonanych operacji dominujących.  
W ten sposób nasza analiza będzie zależna jedynie od algorytmu a nie od implementacji i sprzętu. W  
+
W ten sposób nasza analiza będzie zależna jedynie od algorytmu, a nie od implementacji i sprzętu. W  
przypadku sortowania przeważnie operacją dominującą jest porównanie dwóch elementów (mniejsze,  
+
przypadku sortowania, operacją dominującą jest przeważnie porównanie dwóch elementów,  
równe, mniejsze), a w przypadku przeglądania drzewa jedno przejście w drzewie między   
+
a w przypadku przeglądania drzewa - jedno przejście w drzewie między   
 
wierzchołkami. W przypadku algorytmów tekstowych operacją dominującą jest porównanie dwóch  
 
wierzchołkami. W przypadku algorytmów tekstowych operacją dominującą jest porównanie dwóch  
symboli. Z reguły będziemy przyjmować, że każda operacja arytmetyczna ''na małych liczbach'' daje się
+
symboli. Zazwyczaj określamy pewien parametr <math>n</math>, będący rozmiarem problemu wejściowego i  
zrobić w jednym kroku.  Z reguły określamy pewien parametr <math>n</math>, będący rozmiarem problemu wejściowego i  
+
określamy złożoność jako funkcję <math>T(n)</math>, której argumentem jest rozmiar problemu. Z reguły będziemy przyjmować, że każda operacja arytmetyczna na małych liczbach daje się
określamy złożoność jako funkcję <math>T(n)</math>, której argumentem jest rozmiar problemu. Przez ''małe'' rozumiemy  
+
wykonać w jednym kroku. Przez "małe" rozumiemy liczby mające <math>O(\log n)</math> bitów.
liczby mające <math>O(\log n)</math> bitów.  
 
  
Przeważnie rozważamy złożoność pesymistyczną - maksymalną złożoność dla danych tego samego  
+
 
 +
Złożoność algorytmu może być rozumiana w sensie złożoności najgorszego przypadku lub złożoności średniej. Złożoność najgorszego przypadku nazywamy złożonością pesymistyczną - jest to maksymalna złożoność dla danych tego samego  
 
rozmiaru <math>n</math>.  
 
rozmiaru <math>n</math>.  
W praktyce ważniejszą może się okazać złożoność średnią, lub oczekiwaną, w tym przypadku  
+
W praktyce ważniejsza może się okazać złożoność średnia lub oczekiwana. W tym przypadku  
 
<math>T(n)</math> jest średnią (oczekiwaną) wartością złożoności dla wszystkich problemów  
 
<math>T(n)</math> jest średnią (oczekiwaną) wartością złożoności dla wszystkich problemów  
 
rozmiaru <math>n</math>. Tego typu złożoność zależy  istotnie od tego, jaka się pod tym kryje  
 
rozmiaru <math>n</math>. Tego typu złożoność zależy  istotnie od tego, jaka się pod tym kryje  
przestrzeń probabilistyczna problemów wejściowych. Z reguły zakładamy, że wszystkie problemy
+
przestrzeń probabilistyczna danych wejściowych. Z reguły zakładamy, że wszystkie dane
 
wejściowe tego samego rozmiaru mogą się pojawić z tym samym prawdopodobieństwem. Jednakże  
 
wejściowe tego samego rozmiaru mogą się pojawić z tym samym prawdopodobieństwem. Jednakże  
 
jest to często mało realistyczne założenie. Przestrzeń probabilistyczna danych wejściowych może być  
 
jest to często mało realistyczne założenie. Przestrzeń probabilistyczna danych wejściowych może być  
bardzo skomplikowana, prowadzić to może do bardzo trudnych (i wykraczających poza ten kurs)  
+
bardzo skomplikowana. Prowadzić to może do bardzo trudnych (i wykraczających poza ten kurs)  
 
analiz.
 
analiz.
  
Rozważmy następujący przykład. Przypuśćmy, że chcemy znaleźć pierwszą jedynkę w tablicy zerojedynkowej i nasz  
+
Rozważmy następujący przykład. Przypuśćmy, że chcemy znaleźć pierwszą jedynkę w  
 +
''n''-elementowej tablicy zerojedynkowej i nasz  
 
algorytm przegląda tablicę od strony lewej sprawdzając kolejne elementy.
 
algorytm przegląda tablicę od strony lewej sprawdzając kolejne elementy.
 
Niech operacją dominującą będzie sprawdzenie jednego elementu. Jeśli nie ma jedynki, to wykonamy  
 
Niech operacją dominującą będzie sprawdzenie jednego elementu. Jeśli nie ma jedynki, to wykonamy  
<math>n</math> sprawdzeń, jest to maksymalna liczba, zatem złożoność pesymistyczna wynosi  
+
<math>n</math> sprawdzeń. Jest to maksymalna liczba, zatem złożoność pesymistyczna wynosi  
<math>T(n)=n</math>. Jeśli każdy ciąg binarny jest dany z tym samym prawdopodobieństwem to  
+
<math>T(n)=n</math>. Jeśli każdy ciąg binarny jest dany z tym samym prawdopodobieństwem, to  
 
łatwo policzyć, że złożoność średnia jest ograniczona przez stałą.
 
łatwo policzyć, że złożoność średnia jest ograniczona przez stałą.
  
 
Do wyrażania złożoności stosujemy opis asymptotycznego wzrostu funkcji:
 
Do wyrażania złożoności stosujemy opis asymptotycznego wzrostu funkcji:
<math>f(n)\ =\ O(g(n))</math>  oznacza że <math>f(n) \le c\cdot g(n)</math> dla pewnej stałej  
+
<math>f(n)= O(g(n))</math>  oznacza, że <math>f(n) \le c\cdot g(n)</math> dla pewnej stałej  
<math>c</math> i dla każdego (dostatecznie dużego) <math>n</math>.
+
<math>c</math>.  
Gdy <math>g(n)=n</math> to mówimy, że <math>f(n)</math> jest liniowa, a dla  
+
Gdy <math>g(n)=n</math>, to mówimy, że <math>f(n)</math> jest liniowa, oraz dla  
 
<math>g(n)=n^2</math> mówimy, że złożoność <math>f(n)</math> jest
 
<math>g(n)=n^2</math> mówimy, że złożoność <math>f(n)</math> jest
kwadratowa. Jeśli <math>g(n)</math> jest wielomianem to mówimy o złożoności  
+
kwadratowa. Jeśli <math>g(n)</math> jest wielomianem, to wtedy mówimy o złożoności  
 
wielomianowej.  
 
wielomianowej.  
  
Linia 47: Linia 48:
 
Będziemy używać dodatkowych notacji:
 
Będziemy używać dodatkowych notacji:
  
<math>f(n)=\Theta(g(n)),\ f(n)=\Omega(g(n))</math>.  
+
<math>f(n)=\Theta(g(n)),\ f(n)=\Omega(n)</math>.  
 
 
 
Były one wprowadzone na wykładach z matematyki dyskretnej.
 
Były one wprowadzone na wykładach z matematyki dyskretnej.
  
 
+
{{przyklad|||
Dla przypomnienia:
+
<math>\frac{1}{100}\cdot n^2- 2n = \Theta(n^2 ), n^5+2^n = \Theta(2^n),
 +
n!=\Omega(10^n)</math>,<br>
 +
}}
  
  
<math>f(n)=\Theta(g(n)) \Leftrightarrow f(n)=O(g(n)) </math> & <math>  g(n)=O(f(n))\,</math>
 
<br>
 
  
<math>f(n)=\Omega(g(n)) \Leftrightarrow g(n) = O(f(n))</math>
 
  
{{przyklad|||
 
<math>\frac{1}{100}\cdot n^2- 2n = \Theta(n^2),  n^5+2^n = \Theta(2^n),
 
n!=\Omega(10^n)</math>.
 
}}<br>
 
  
'''Konwencje językowe.''' Jaki jest najlepszy język do opisu algorytmu ? Jest to przykład problemu  
+
'''Konwencje językowe.''' Jaki jest najlepszy język do opisu algorytmu? Jest to przykład problemu  
 
nierozstrzygalnego. Niewątpliwie język ojczysty jest najlepszym  
 
nierozstrzygalnego. Niewątpliwie język ojczysty jest najlepszym  
językiem potocznym , a ulubiony język programowania jest  najlepszym językiem do implementacji  
+
językiem potocznym, a ulubiony język programowania jest  najlepszym językiem do implementacji  
algorytmu. Język, którym będziemy opisywać algorytmy jest gdzieś pomiędzy tymi językami, język  
+
algorytmu. Język, którym będziemy opisywać algorytmy, jest gdzieś pomiędzy tymi językami - język  
potoczny nie wystarcza a konkretny język programowania może spowodować to, że "prosty" algorytm  
+
potoczny nie wystarcza, a konkretny język programowania może spowodować, że "prosty" algorytm  
 
się zrobi nieczytelny.  Będziemy używać, o ile się da, nieformalnych konstrukcji programistycznych, a  
 
się zrobi nieczytelny.  Będziemy używać, o ile się da, nieformalnych konstrukcji programistycznych, a  
w przypadku bardzo prostych algorytm będziemy się starali pisać algorytm w języku C-podobnym.
+
w przypadkach bardzo prostych będziemy się starali pisać algorytm w języku Pascalopodobnym.
  
 
== Poprawność algorytmu: niezmienniki, własność stopu ==
 
== Poprawność algorytmu: niezmienniki, własność stopu ==
Przez poprawność algorytmu rozumiemy to, że daje on takie odpowiedzi jakich oczekujemy.  
+
Przez poprawność algorytmu rozumiemy to, że daje on takie odpowiedzi, jakich oczekujemy.  
Oczywiście algorytm musi być poprawny aby miało sens rozpatrywanie jego złożoność.
+
Oczywiście algorytm musi być poprawny, aby miało sens rozpatrywanie jego złożoności.
  
 
=== Pojęcie niezmiennika ===
 
=== Pojęcie niezmiennika ===
 
Poprawność algorytmu sprowadza się do spełniania określonych niezmienników na różnych etapach  
 
Poprawność algorytmu sprowadza się do spełniania określonych niezmienników na różnych etapach  
tego algorytmu.
+
wykonywania tego algorytmu.
 
Rozważmy kilka przykładów pozwalających zrozumieć znaczenie niezmiennika.  
 
Rozważmy kilka przykładów pozwalających zrozumieć znaczenie niezmiennika.  
  
Załóżmy, że mamy zbiór <math>S</math> składający się z <math>n</math> przedmiotów, niektóre z  
+
Załóżmy, że mamy zbiór <math>S</math> składający się z <math>n</math> przedmiotów. Niektóre z  
przedmiotów są czarne a niektóre białe. Zakładamy, że liczba czarnych przedmiotów jest nieparzysta.
+
przedmiotów są czarne, a niektóre białe. Zakładamy, że liczba czarnych przedmiotów jest nieparzysta.
  
  
{{algorytm|||
+
{{algorytm|Biało-czarne1||
  1 '''while'''  <math>|S|> 1</math>
+
  1 '''while'''  <math>|S|> 1</math> '''do''' '''begin'''
 
  2    pobierz dwa przedmioty z S;
 
  2    pobierz dwa przedmioty z S;
  3    '''if''' przedmioty są różnego koloru to wstaw z powrotem czarny
+
  3    '''if''' przedmioty są różnego koloru '''then''' wstaw z powrotem czarny
  4 '''return''' kolor ostatniego przedmiotu w S;
+
  4 '''end;'''
 +
'''return''' kolor ostatniego przedmiotu w S;
 
  }}
 
  }}
  
 
Załóżmy, że mamy 10000001 czarnych przedmiotów i  1000000001 białych, jaki jest ostatni  
 
Załóżmy, że mamy 10000001 czarnych przedmiotów i  1000000001 białych, jaki jest ostatni  
przedmiot ? Rozpatrzmy niezmiennik: parzystość liczby czarnych przedmiotów.
+
przedmiot? Rozpatrzmy niezmiennik: parzystość liczby czarnych przedmiotów.
  
Ponieważ na początku mamy nieparzystą liczbę czarnych przedmiotów, zatem na wyjściu mamy kolor  
+
Ponieważ na początku mamy nieparzystą liczbę czarnych przedmiotów, zatem wynikiem jest kolor  
 
czarny.
 
czarny.
  
  
Rozpatrzmy modyfikację tego algorytmu, zakładamy że n jest niezerowe.
+
Rozpatrzmy modyfikację tego algorytmu, zakładamy że <math>n</math> jest niezerowe.
  
{{algorytm|||
+
{{algorytm|Biało-czarne2||
  1 '''while'''  <math>|S|> 1</math>
+
  1 '''while'''  <math>|S|> 1</math> '''do''' '''begin'''
 
  2    pobierz dwa przedmioty z S;
 
  2    pobierz dwa przedmioty z S;
  3    '''if''' co najmniej jeden jest biały to wstaw z powrotem jeden biały;
+
  3    '''if''' co najmniej jeden jest biały '''then''' wstaw z powrotem jeden biały;
  4 '''return''' kolor ostatniego przedmiotu w S.
+
  4 '''end;'''
 +
'''return''' kolor ostatniego przedmiotu w S;
 
}}
 
}}
  
 
Załóżmy, że mamy  10000001 czarnych przedmiotów i 1000000001 białych, jaki jest ostatni  
 
Załóżmy, że mamy  10000001 czarnych przedmiotów i 1000000001 białych, jaki jest ostatni  
 
przedmiot? Tym razem rozważmy niezmiennik: znak liczby białych przedmiotów.  
 
przedmiot? Tym razem rozważmy niezmiennik: znak liczby białych przedmiotów.  
(Znak liczby jest równy 0 jeśli jest ona równa zeru, 1 jeśli jest większa od zera.) Zatem ostatnim  
+
(Znak liczby jest równy 0, jeśli jest ona równa zeru, 1 - jeśli jest większa od zera.) Zatem ostatnim  
 
przedmiotem jest przedmiot biały.
 
przedmiotem jest przedmiot biały.
 +
 +
 +
  
 
=== Własność stopu===  
 
=== Własność stopu===  
Podstawowym elementem poprawności algorytmu jest to, że ma on własność stopu: dla poprawnych
+
Jednym z podstawowych elementów  poprawności algorytmu jest własność stopu: dla poprawnych
danych wejściowych da odpowiedź po skończonym czasie. Na przykładzie dwóch prostych
+
danych wejściowych algorytm zatrzymuje się w  skończonym czasie.<br>
algorytmów pokażemy,
+
Na przykładzie czterech krótkich
że sprawdzanie własności stopu może nie być czynnością trywialną.
+
algorytmów pokażemy, że sprawdzanie własności stopu może nie być czynnością trywialną.
  
{{algorytm|Suma-Kwadratów-Cyfr|suma_kwadratow_cyfr|suma_kwadratow_cyfr
+
{{algorytm|Suma-Kwadratów-Cyfr|suma_kwadratow_cyfr|
   1  '''while'''  ((n <>4)  and  (n<> 1))
+
   1  '''while'''  <math>((n <>4)</math> '''and''' <math>(n<> 1))</math> '''do'''
   2 <math> n := </math> suma kwadratów cyfr liczby <math> n </math>;
+
   2   <math> n := </math> suma kwadratów cyfr liczby <math> n </math>;
 
}}
 
}}
  
  
 
{{algorytm|6174|algorytm_6174|
 
{{algorytm|6174|algorytm_6174|
  wejściem jest czterocyfrowa liczba naturalna niepodzielna przez 1111
+
  // <math>n</math> jest czterocyfrową liczbą naturalną niepodzielną przez 1111
  pierwszymi cyframi mogą być zera
+
  // pierwszymi cyframi ''n'' mogą być zera
  '''while''' (n<>6174)
+
1 '''while''' (n<>6174) '''do''' <br>
    <math>n1 :=</math>  największa liczba czterocyfrowa której cyfry są permutacją cyfr liczby n;
+
2      <math>n1 :=</math>  największa liczba czterocyfrowa, której cyfry są permutacją cyfr liczby <math>n</math>;
    <math>n2 :=</math> najmniejsza liczba czterocyfrowa której  cyfry są permutacją cyfr liczby n;
+
3      <math>n2 :=</math> najmniejsza liczba czterocyfrowa, której  cyfry są permutacją cyfr liczby <math>n</math>;
    <math>n := </math>n1 - n2;
+
4      <math>n := n1 - n2</math>
 
}}
 
}}
{{algorytm|X|algorytm_X|
+
 
  '''while''' (n<>1)
+
W przypadku liczb trzycyfrowych rolę liczby 6174 pełni liczba 495.
    '''if''' n parzyste <math>n :=</math> n div 2; '''else''' <math>n := </math>3*n+1;
+
W przypadku liczb pięciocyfrowych nie ma takiej pojedyńczej liczby.
   
+
<br>
 +
 
 +
 
 +
Rozpatrzmy następujący algorytm (zaprojektowany podobno przez<br>
 +
Fibonacciego) na rozkład ułamka na sumę '''parami różnych''' ułamków Egipskich,<br>
 +
<br>
 +
tzn. ułamków postaci <math> \frac{1}{q_i}</math>.
 +
 
 +
 
 +
Rozkład Egipski jest postaci
 +
<math>  \frac{p}{q}= \frac{1}{q_1}+\frac{1}{q_2}+\frac{1}{q_3}+\frac{1}{q_4}+\ldots , </math>
 +
gdzie <math>q_1<q_2<q_3<\ldots </math> są liczbami  naturalnymi:
 +
 
 +
 
 +
Każdy ułamek ma rozkład Egipski,
 +
oto przykład takiego rozkładu:
 +
 
 +
 
 +
<math>
 +
31/311= 1/12 + 1/63 + 1/2799 + 1/8708</math>
 +
 
 +
 
 +
Niech <math> DolnyEgipt(x)</math> oznacza najwięszy ułamek Egipski (tzn. postaci <math>\frac{1}{q}</math>)
 +
nie przekraczający x.
 +
<br>
 +
<br>
 +
Przykłady: <br>
 +
<math> DolnyEgipt(2/3)=1/2,\ DolnyEgipt(4/5)=1/2,\ </math> <math>DolnyEgipt(2/5)=1/3,\ DolnyEgipt(2/7)=1/4. </math>
 +
 
 +
 
 +
Niech <math> 1\le p<q</math> będą dwiema względnie pierwszymi liczbami naturalnymi.
 +
Następujący algorytm oblicza rozkład (niekoniecznie najkrótszy) nieskracalnego ułamka <math>\frac{p}{q}</math>
 +
na ułamki Egipskie.
 +
 
 +
 
 +
{{algorytm|Rozkład-Egipski<math> (p,q)</math>|RozkładEgipski|
 +
(algorytm Fibonacciego)<br>
 +
1  <math> x:=\frac{p}{q};</math><br>
 +
2 '''while''' (x>0) '''do''' <br>
 +
3      <math> y:=DolnyEgipt(x);</math> '''output''' y;
 +
4      <math> x:=x-y;</math>
 
}}
 
}}
Pierwsze dwa algorytmy mają własność stopu, w pierwszym łatwo to sprawdzić gdyż dla  
+
 
 +
 
 +
Nasz algorytm dla wejścia (31,311), tzn. <math>x=31/311</math>, wyprodukuje 10 składników w rozkładzie Egipskim.
 +
 
 +
 
 +
Dla wejścia <math>\frac{7}{15}</math> otrzymamy jako wynik następujący ciąg
 +
ułamków Egispskich:
 +
<math> \frac{1}{3},\ \frac{1}{8},\ \frac{1}{120}.</math>
 +
 
 +
 
 +
Algorytm ma własność stopu ponieważ liczniki kolejnych dodatnich wartości <math>x</math> (przedstawionych jako nieskracalne ułamki)  maleją<br>
 +
(pozostawiamy dowód tego faktu jako ćwiczenie). <br>
 +
Oto przykład ciągu kolejnych wartości <math>x</math>: 4/5 -> 3/10 -> 1/10. Liczniki maleją: <math>4>3>1</math>. <br>
 +
W pewnym momencie licznik liczby <math>x</math> dochodzi do jedynki, wtedy następna wartość <math>x</math> staje się zerem i algorytm zatrzymuje się.<br>
 +
Zatem algorytm wykonuje co najwyżej <math>p</math> iteracji dla wejścia <math>p/q</math>.
 +
 
 +
 
 +
Rozpatrzmy jeszcze jeden abstrakcyjny algorytm.
 +
 
 +
 
 +
 
 +
{{algorytm|Bez-Sensu|algorytm_X|
 +
1 '''while''' <math>(n<>1)</math> '''do'''
 +
2    '''if''' <math>n</math> parzyste '''then''' <math>n := n \mbox{ div } 2 </math>
 +
3    '''else''' <math>n := 3*n+1</math>; 
 +
}}
 +
Pierwsze trzy algorytmy mają własność stopu. W pierwszym łatwo to sprawdzić, gdyż dla  
 
<math>n>100</math> następna wartość jest istotnie mniejsza.  
 
<math>n>100</math> następna wartość jest istotnie mniejsza.  
  
Pozostawiamy jako ćwiczenie jak najkrótszy koncepcyjnie dowód własności stopu obu algorytmów  
+
Pozostawiamy jako ćwiczenie znalezienie najkrótszego koncepcyjnie dowodu własności stopu dwu pierwszych algorytmów  
 
(nie chodzi nam tu o brutalny dowód polegający na sprawdzeniu wszystkich  przypadków przez  
 
(nie chodzi nam tu o brutalny dowód polegający na sprawdzeniu wszystkich  przypadków przez  
 
komputer).  
 
komputer).  
  
Algorytm X jest dosyć zagadkowy, nie wiadomo, czy dla dowolnego naturalnego dodatniego
+
 
 +
 
 +
Natomiast
 +
algorytm ''Bez-Sensu'' jest najbardziej zagadkowy. Nie wiadomo, czy dla '''każdej''' dodatniej liczby całkowitej
 
<math>n</math> ma on własność stopu.
 
<math>n</math> ma on własność stopu.
 +
Problem ten postawił L. Collatz w roku 1937, wiadomo, że własność stopu zachodzi dla każdego <math> 1 \le n \le 10^{16}</math>.
 +
Problem stopu dwóch ostatnich algorytmów jest teoretycznym problemem matematycznym o dużym stopniu trudności.
 +
 +
===Opis  algorytmu za pomocą niezmienników===
 +
 +
 +
Niezmienniki są często podstawową konstrukcji algorytmu na poziomie koncepcyjnym. Opisujemy jedynie co dana
 +
część algorytmu ma wykonać w sensie zachowania odpowiedniego niezmiennika. Reszta jest czasami prostą
 +
sprawą natury inżynieryjno-technicznej.
 +
 +
<br>
 +
Zademonstrujemy to na następujacym przykładzie posegregowania tablicy
 +
liczbowej <math>A[1..n]</math> względem elementu <math>x</math>.  Dla zbiorów pozycji <math>X,Y</math> tablicy <math>A</math> piszemy <math>X<Y</math> gdy każda pozycja w X jest mniejsza od każdej pozycji w <math>Y</math>. Piszemy <math>A[X]<a</math> gdy wartości na pozycjach X są mniejsze od a (podobnie z równością).
 +
 +
Zdefiniujmy następujący niezmiennik <math> \alpha(M,R,W):\ \ </math>  <br>
 +
 +
<center>
 +
<math> M<R<W,\ A[M]<x,\ A[R]=x,\ A[W]>x </math></center>
 +
 +
<br>
 +
Nazwy M,R,W biorą się od '''M'''niejsze, '''R'''ówne, '''W'''iększe.<br>
 +
 +
 +
Naszym problemem jest
 +
poprzestawiać elementy tablicy tak aby dla pewnych zbiorów M,R,W dających w sumie cały zbiór pozycji
 +
zachodził niezmiennik <math> \alpha(M,R,W)</math> (algorytmy tego typu maja  zastosowanie w
 +
implmentacji bardzo praktycznego algorytmu ''Quicksort'').
 +
<br>
 +
 +
Algorytm wykonuje swoje zadanie  startując od zbiorów pustych i zwiększając zbiory.
 +
Chcemy aby algorytm działał ''w miejscu'' (dodatkowa pamięć stała) i w każdej iteracji wykonywał stałą liczbę operacji.
 +
 +
 +
{{algorytm|PosegregujTablicę|PosegregujTablicę|
 +
0  <math> M := \emptyset; \ R := \emptyset;\  W:= \emptyset</math>;
 +
1  '''while'''  <math>|M|+|R|+|W|<n</math> '''do'''
 +
2    zwiększ o jeden sumę <math>|M|+|R|+|W|</math> zachowując niezmiennik <math>\alpha(M,R,W)</math> 
 +
3    w czasie i dodatkowej pamięci <math>O(1)</math>
 +
}}
 +
 +
 +
Możliwe są różne scenariusze tego algorytmu poprzez dospecyfikowanie niezmiennika.
 +
Na przykład możemy
 +
zażądąc aby zbiory M,R,W były sąsiednimi przedziałami, tworzącymi razem sufiks (lub prefiks) tablicy, lub
 +
aby M było prefiksem a W sufiksem tablicy. Otrzymamy różne algorytmy w pewnym sensie izomorficzne.
 +
Naturalnym jest aby zażądać, by
 +
każdy ze zbiorów M, R, W był przedziałem, nawet jeśli tego nie zażądamy to tak będzie po zakończeniu algorytmu.
 +
Jeśli zbiory są przedziałami to pojedyńcza iteracja polega na ''manipulacji'' w okolicy końców przedziałów.
 +
<br>
 +
 +
Możemy problem ouogólnić i segregować tablicę względem większej liczby elementów, np. względem
 +
elementów <math> x<y</math>. Teraz zamiast dwóch segmentów M, R, W tablicy A mamy pięć zbiorów
 +
pozycji, a niezmiennik zamienia się na
 +
<br>
  
== Złożoność algorytmów: analiza siedmiu prostych algorytmów ==
+
<center>
 +
<math> Z1<Z2<Z3<Z4<Z5,\ A[Z1]<x,\ A[Z2]=x,</math></center>
  
Na przykładzie siedmiu prostych algorytmów pokażemy, jak się analizuje i osiąga złożoność liniową.
+
<center>
Po dokładniejsze uzasadnienia i analizy odsyłamy do ćwiczeń.  Naiwne wersje tych algorytmów
+
<math>
działają w czasie kwadratowym.  
+
x<A[Z3]<y,\ A[Z4]=y,\ A[Z5]>y. </math></center>
  
==== Przywódca ciągu ====  
+
<br>
 +
 
 +
== Poprawność i złożoność 10 prostych algorytmów ==
 +
 
 +
Poniżej dokonamy pobieżnej analizy złożoności obliczeniowej siedmiu algorytmów i wykażemy, że ich złożoności są lepsze od złożoności kwadratowej
 +
rozwiązań <br> naiwnych,
 +
chociaż nasze algorytmy  będą niewiele bardziej skomplikowane od naiwnych.
 +
 
 +
Poza dwoma z nich  (działającymi w czasie czas <math> O(n \log n),</math>)
 +
wszystkie algorytmy działają w czasie liniowym.
 +
 
 +
Dokładne analizy pozostawiamy jako ćwiczenia. 
 +
 
 +
 
 +
==== Algorytm 1. Przywódca ciągu ====  
 
Przywódcą ciągu jest element, który występuje w ciągu więcej razy niż połowa długości tego ciągu.  
 
Przywódcą ciągu jest element, który występuje w ciągu więcej razy niż połowa długości tego ciągu.  
Naszym problemem jest wyznaczenie przywódcy ciągu danego tablicą <math>A[1..n]</math>. Dla  
+
Naszym problemem jest policzenie przywódcy ciągu danego w tablicy <math>A[1..n]</math>. Dla  
uproszczenia przyjmijmy, że w tym ciągu jest przywódca. Łatwo można tak zmodyfikować algorytm, by  
+
uproszczenia przyjmijmy, że w tym ciągu jest przywódca. Łatwo zmodyfikować algorytm tak, by  
 
sprawdzał istnienie przywódcy.
 
sprawdzał istnienie przywódcy.
 +
  
 
{{algorytm|Liczenie-Przywódcy|algorytm_liczenie_przywodcy|
 
{{algorytm|Liczenie-Przywódcy|algorytm_liczenie_przywodcy|
   <math> ile :=  0 </math>;
+
   <math> ile :=  0 </math>;<br>
    '''for''' i <math>:=</math> 1 to n do
+
  2  '''for''' i <math>:=</math> 1 '''to''' n '''do'''<br>
      '''if''' <math>(ile = 0) \{ile := ile+1; j := i\}</math>;
+
  3      '''if''' <math>(ile = 0)</math> '''then'''
      '''else if''' <math>( A[i]=A[j]) </math> <math> ile:=ile+1; </math> '''else'''
+
  4          <math>ile := ile+1; j := i</math> <br>
        <math> ile :=ile-1</math>;<br>
+
  5      '''else if''' <math>(A[i]=A[j])</math> '''then''' <math>ile:=ile+1; </math> <br>
    '''return''' <math>A[j]</math>;
+
  6      '''else''' <math> ile :=ile-1</math>;<br>
 +
  7  '''return''' <math>A[j]</math>;
 
}}
 
}}
Przyspieszenie wynika z następującej własności problemu: jeśli mamy dwa różne elementy w tablicy  
+
Przyspieszenie wynika z następującej własności problemu: jeśli mamy dwa różne elementy w tablicy, to możemy je usunąć i przywódca pozostanie taki sam.
to możemy je usunąć i przywódca pozostanie taki sam.
 
  
Algorytm można zmodyfikować tak aby w czasie liniowym liczył on słabego przywódcę: element,  
+
Algorytm można zmodyfikować tak, aby w czasie liniowym liczył słabego przywódcę: element,  
który występuje w tablicy więcej niż n/5 razy.
+
który występuje w tablicy więcej niż <math>n/5</math> razy.
 
W tym przypadku potrzebne są cztery liczniki  odpowiadające czterem kandydatom na słabego  
 
W tym przypadku potrzebne są cztery liczniki  odpowiadające czterem kandydatom na słabego  
 
przywódcę.  
 
przywódcę.  
Algorytm liczy  element który jest kandydatem na słabego przywódcę (jeśli istnieje taki przywódca to  
+
Algorytm liczy  element, który jest kandydatem na słabego przywódcę (jeśli istnieje taki przywódca, to  
na pewno jest nim wyliczony element). Jeśli istnieje słaby przywódca i mamy pięć różnych elementów to można je usunąć bez zmiany  
+
na pewno jest nim wyliczony element). Jeśli istnieje słaby przywódca i mamy pięć różnych elementów, to można je usunąć bez zmiany  
 
wyniku. Pozostawiamy napisanie odpowiedniego algorytmu jako ćwiczenie.
 
wyniku. Pozostawiamy napisanie odpowiedniego algorytmu jako ćwiczenie.
  
Problem można rozwiązać inaczej sortując tablicę, wtedy mamy złożoność O(n log n). Podamy potem  
+
Problem można rozwiązać inaczej, sortując tablicę, wtedy mamy złożoność <math>O(n log n)</math>. Podamy potem  
 
również rozwiązanie metodą "dziel i zwyciężaj".
 
również rozwiązanie metodą "dziel i zwyciężaj".
  
Linia 187: Linia 326:
 
<flash>file=przywodca_slaby.swf|width=520|height=270</flash></center>
 
<flash>file=przywodca_slaby.swf|width=520|height=270</flash></center>
  
W animacji kolorem żółtym na końcu zaznacza się licznik słabego przywódcy, jego nazwa jest w  
+
W animacji kolorem żółtym na końcu jest zaznaczony licznik słabego przywódcy, a jego nazwa jest  
 +
umieszczona w  
 
niebieskim kwadraciku.
 
niebieskim kwadraciku.
  
====Szukanie sumy==== Mamy dane dwie posortowane rosnąco tablice <math>A,B</math> i liczbę  
+
==== Algorytm 2. Szukanie sumy====  
x,pytamy czy <math>a \in A,\ b \in B</math> takie, że <math>x=a+b</math>.
+
 
 +
Mamy dane dwie tablice  posortowane rosnąco <math>A,B</math> i liczbę <math>x</math>, pytamy, czy istnieją <math>a \in A,\ b \in B</math> takie, że <math>x=a+b</math>.
 +
 
  
 
{{algorytm|Szukanie Sumy|algorytm_szukanie_sumy|
 
{{algorytm|Szukanie Sumy|algorytm_szukanie_sumy|
   Szukanie Sumy
+
1   <math>i := 1; j := n;</math><br>
    <math>i := 1; j := n;</math>
+
'''while''' <math>(i <= n</math>  '''and''' <math> j > 0)</math> '''do'''<br>
    '''while''' <math>(i <= n</math>  and <math> j > 0)</math>
+
3      '''if''' <math>(A[i]+B[j]=x) </math> '''then''' '''return''' true;  
      '''if''' <math>(A[i]+B[j]=x) </math>'''return''' true; else
+
4      '''else''' '''if''' <math>(A[i]+B[j]<x)</math> '''then''' <math>i:=i+1;</math>
      '''if''' <math>(A[i]+B[j]<x) i:=i+1; </math>'''else''' <math>j:=j-1</math>;
+
5      '''else''' <math>j:=j-1</math>;<br>
    '''return''' false;
+
'''return''' false;
 
}}
 
}}
 
Przyspieszenie jest możliwe dzięki odpowiedniej kolejności sprawdzania <math>i,j</math> i  
 
Przyspieszenie jest możliwe dzięki odpowiedniej kolejności sprawdzania <math>i,j</math> i  
 
pominięciu zbędnych sprawdzeń.
 
pominięciu zbędnych sprawdzeń.
  
==== Maksymalny segment ====  Dla tablicy <math>A[1..n] \,</math> liczymy maksymalną  
+
==== Algorytm 3. Maksymalny segment ====   
wartość z zera i  
+
 
 +
Dla tablicy <math>A[1..n] \,</math> liczymy maksymalną wartość z zera i  
 
ze wszystkich liczb <math>\sum_{k=i}^j\ A[k]</math>, gdzie <math>1\le i\le j\le n</math>.
 
ze wszystkich liczb <math>\sum_{k=i}^j\ A[k]</math>, gdzie <math>1\le i\le j\le n</math>.
 +
  
 
  '''Algorytm''' Maksymalny-Segment;<br>
 
  '''Algorytm''' Maksymalny-Segment;<br>
    wynik := 0; sufiks := 0;
+
wynik := 0; sufiks := 0;<br>
    '''for''' i := 1 to n do
+
'''for''' i := 1 '''to''' n '''do''' <br>
       sufiks := max(A[i]+sufiks,0);
+
3       sufiks := max(A[i]+sufiks,0); wynik := max(wynik,sufiks);
      wynik := max(wynik, sufiks);
 
  
 +
<br>
 
Przyspieszenie w stosunku do algorytmu kwadratowego następuje dzięki wprowadzeniu dodatkowej  
 
Przyspieszenie w stosunku do algorytmu kwadratowego następuje dzięki wprowadzeniu dodatkowej  
 
zmiennej sufiks.  
 
zmiennej sufiks.  
 
Po każdym zakończeniu  pętli "for" zachodzi: wynik jest maksymalną sumą przedziału zawierającego  
 
Po każdym zakończeniu  pętli "for" zachodzi: wynik jest maksymalną sumą przedziału zawierającego  
 
się w <math>[1..i]</math>  
 
się w <math>[1..i]</math>  
oraz sufiks jest maksymalną sumą segmentu który jest sufiksem przedziału <math>[1..i]</math>.
+
oraz sufiks jest maksymalną sumą segmentu, który jest sufiksem przedziału <math>[1..i]</math>.
  
 +
====Algorytm  4. Najbliższy mniejszy sąsiad w ciągu ====
 +
Dla każdego <math>i > 1</math> zdefiniujmy najbliższego mniejszego (lewego) sąsiada <math>i</math> jako
 +
 +
<math>Lewy[i] =max \{j<i : A[j]<A[i] \}</math>.<br>
  
==== Najbliższy mniejszy sąsiad z lewej strony ====
 
Dla każdego <math>i > 1</math> zdefiniujmy najbliższego mniejszego sąsiada <math>i</math> jako: 
 
<math>Lewy[i] =max \{j<i : A[j]<A[i] \}</math>
 
 
Dla uproszczenia zakładamy, że  <math>A[i]> 0</math> dla <math>i>0</math> oraz  
 
Dla uproszczenia zakładamy, że  <math>A[i]> 0</math> dla <math>i>0</math> oraz  
 
<math>A[0]=0</math>.
 
<math>A[0]=0</math>.
  
 
{{algorytm|Najbliższy-Mniejszy-Sąsiad|algorytm_najblizszy_mniejszy_sasiad|
 
{{algorytm|Najbliższy-Mniejszy-Sąsiad|algorytm_najblizszy_mniejszy_sasiad|
  Najbliższy Mniejszy Sąsiad
+
  1 '''for''' <math>i := 1</math> '''to''' n '''do''' <br>
  '''for''' <math>i := 1</math> to n do
+
2    <math>j := i-1;</math><br>
  <math> j := i-1;</math>
+
3    '''while''' <math>( A[j] >= A[i])</math> '''do''' <math>j := Lewy[j];</math><br>
    '''while''' <math>( A[j] >= A[i]) j := Lewy[j];</math>
+
4    <math>Lewy[i] := j;</math>
      <math>Lewy[i] := j;</math>
 
 
}}
 
}}
  
Przyspieszenie następuje dzięki temu, że nie ma potrzeby sprawdzania tablicy dla indeksów istotnie  
+
 
wewnątrz przedziału  <math>[[Lewy[i-1]...(i-1)]</math> .  Niech <math>k_i</math> będzie liczbą  
+
Przyspieszenie w stosunku do algorytmu naiwnego następuje dzięki temu, że nie ma potrzeby sprawdzania tablicy dla indeksów istotnie  
tych <math>j</math> dla których <math>A[j]>=A[i]</math>. Wystarczy
+
wewnątrz przedziału  <math>[Lewy[i-1]...(i-1)]</math>.  Niech <math>k_i</math> będzie liczbą  
pokazać, że suma wszystkich <math>k_i</math> jest liniowa. Może się zdarzyć, że niektóre  
+
tych <math>j</math>, dla których <math>A[j]>=A[i]</math> (w wierszu 3). Wystarczy
 +
pokazać, że suma wszystkich <math>k_i</math> jest liniowa ze względu na ''n''. Może się zdarzyć, że niektóre  
 
<math>k_i</math> mają wartość
 
<math>k_i</math> mają wartość
liniową. Zauważmy jednak, że dany indeks <math>j</math> pojawia się co najwyżej raz w sytuacji  
+
liniową. Zauważmy jednak, że dany indeks <math>j</math> pojawia się co najwyżej raz w sytuacji,
 
gdy <math>A[j] >= A[i]</math>,
 
gdy <math>A[j] >= A[i]</math>,
 
potem będzie "przeskoczony".
 
potem będzie "przeskoczony".
  
==== Najdłuższy malejący podciąg ====
+
 
Niech <math>A[1], A[2],\ldots A[n]</math> będzie ciągiem dodatnich liczb. Następujący algorytm  
+
Opiszemy teraz nieformalnie alternatywny algorytm korzystajacy ze stosu. <br>
oblicza długość najdłuższego  malejącego podciągu.   
+
Zamiast indeksu lewego sasiada bedziemy teraz liczyc wartosc lewego sasiada, inaczej mowiac<br>
 +
liczymy pierwsza wartosc na lewo mniejsza od danej wartosci.
 +
<br> Niech y oznacza element na wierzcholku stosu.
 +
<br>
 +
 
 +
 
 +
Czytamy kolejne elementy.<br>
 +
Po wczytaniu kolejnego elementu x usuwamy elementy ze stosu dopoki x<y.<br>
 +
W tym momencie znajdujemy lewego sasiada x, jego wartoscia jest y.<br>
 +
Wrzucamy x na stos.
 +
 
 +
 
 +
Zalozmy ze A jest permutacja liczb 1,2,..n. Wtedy mozliwy jest jeszcze inny algorytm liniowy.
 +
<br>
 +
 
 +
Trzymamy elementy tablicy w liscie dwukierunkowej.<br>
 +
 
 +
Dla k=n,n-1,..2 wykonujemy:<br>
 +
lewym sasiadem
 +
k zostaje jego poprzednik na liscie.<br> Nastepnie element k usuwamy z listy.
 +
 
 +
====Algorytm  5. Najdalszy mniejszy sąsiad w permutacji  ====
 +
W tym algorytmie zakładamy że na wejściu jest permutacja A elementów od 1 do n. <br>
 +
Dla każdego <math>i > 1</math> zdefiniujmy najdalszego mniejszego (prawego) sąsiada <math>i</math> jako
 +
<br>
 +
<math>Najd\_Prawy[i] =max \{j>i : A[j]<A[i] \}</math>.<br>
 +
<br>
 +
W trakcie algorytmu obliczamy tablicę Pozycja, będącą odwrotościa permutacji.
 +
<br>
 +
Załóżmy, że początkowo Najd_Prawy[i]=0, Pozycja[i]=0, dla każdego i.
 +
 
 +
{{algorytm|Najdalszy-Prawy-Mniejszy-Sąsiad|algorytm_najdalszy_mniejszy_sasiad|
 +
1    <math> min:=1;</math> <br>
 +
2    '''for''' <math>i := 1</math> '''to''' n '''do''' <br>
 +
3    <math>Pozycja[A[i]]:=i;</math><br>
 +
4    '''while''' <math> min \le n  \ \&\ Pozycja[min]\ne 0</math> '''do'''<br>
 +
5            <math>Najd\_Prawy[Pozycja[min]]:=i;</math> <math>min := min+1;</math> 
 +
}}
 +
 
 +
Algorytm ten dziła oczywiście w czasie liniowym.
 +
Jego wadą jest ograniczenie się do permutacji.
 +
 
 +
====Algorytm  6. Najdłuższy malejący podciąg ====
 +
 
 +
 
 +
Niech <math>A[1], A[2],\ldots A[n]</math> będzie ciągiem <math> n </math> '''dodatnich''' liczb. <br>
 +
Następujący algorytm  
 +
oblicza długość najdłuższego  malejącego podciągu (w kolejności ''od lewej do prawej strony'').  
 +
 
 +
    
 
{{algorytm|Najdłuższy-Malejący|algorytm_najdluzszy_malejacy|
 
{{algorytm|Najdłuższy-Malejący|algorytm_najdluzszy_malejacy|
  Najdłuższy-Malejący
+
  1 <math>wynik := 1;</math><br>
  <math>wynik := 1;</math>
+
2 '''for''' <math>i := 1</math> '''to''' n '''do'''<br> <br>
  '''for''' <math>i := 1</math> to n do
+
3     <math>x := A[i]; A[i]:=0;</math> <br>
     <math>x := A[i]; A[i]:=0;</math>
+
4     <math>k := min \{ j \le i : x  \ge A[j]\};</math>  <br>
     <math>k := min \{ j : x  > A[j]\};</math>  
+
5     <math>A[k] := x</math>; <math>wynik := max(k, wynik);</math>  
     <math>A[k] := x ;</math>
 
    <math>wynik := max(k, wynik);</math>
 
 
}}
 
}}
  
 +
Poprawność algorytmu nie jest całkowicie oczywista, uzasadnienie można znależć w rozwiązaniu
 +
stosownego zadania (patrz Ćwiczenia). Jeśli wejściem jest [5,2,1,3,7] to w momencie gdy algorytm kończy obliczenia, tablica A jest
 +
równa [7,3,1,0,0]. Zauważmy, że [7,3,1] wcale nie jest podciągiem (w kierunku ''od lewej do prawej strony'') tablicy wejściowej. Niemniej wynik jest poprawny.
 +
 +
Złożoność alorytmu istotnie zależy od implementacji instrukcji: <br>
 +
<center> <math>k := min \{ j : x  \ge A[j]\}</math>. </center>
 +
Ponieważ wszystko się odbywa w tablicy, możemy minimum policzyć łatwo w czasie logarytmicznym stosując szukanie binarne w posortowanej tablicy
 +
(segment tablicy <math> A[1..i] </math> jest posortowany).
 +
Zatem całkowity koszt algorytm jest <math> O(n \log n) </math> przy dosyć prostej implementacji.
  
Algorytm może, przy niewielkim dodatkowym  wysiłku, podać najdłuższy malejący  
+
Algorytm może, po niewielkim ''dodatkowym  wysiłku procesora'', podać najdłuższy malejący  
 
podciąg, albo też rozkład na minimalną liczbę podciągów niemalejących.
 
podciąg, albo też rozkład na minimalną liczbę podciągów niemalejących.
 
Nie jest jasne, jak policzyć leksykograficznie minimalny i leksykograficznie maksymalny podciąg  
 
Nie jest jasne, jak policzyć leksykograficznie minimalny i leksykograficznie maksymalny podciąg  
malejący o długości k, gdzie
+
malejący o długości <math>k</math>, gdzie
k jest wynikiem powyższego algorytmu. Możemy się również zastanowić nad efektywnym  
+
<math>k</math> jest wynikiem powyższego algorytmu. Możemy się też zastanowić nad efektywnym  
algorytmem znajdowania liczby wszystkich takich ciągów długości k.
+
algorytmem znajdowania liczby wszystkich takich ciągów długości <math>k</math>.
 +
 
 +
====Algorytm  7. Dwa-Pakowanie====
 +
 
 +
Załóżmy, że mamy dowolnie dużą liczbę  pudełek, każde o rozmiarze ''R'', oraz ''n'' przedmiotów o rozmiarach <math>
 +
r[1], r[2],\ldots r[n]</math>. Zakładamy, że <center> <math>R \ge 
 +
r[1]\ge r[2]\ldots \ge r[n]</math>.</center>
 +
Mamy włożyć przedmioty do pudełek, co najwyżej dwa do jednego
 +
pudełka.
 +
 
 +
Pozostawiamy jako ćwiczenie analizę następującego algorytmu, który oblicza minimalną
 +
liczbę pudełek do zapełnienia.
  
==== Proste Pakowanie====
 
Załóżmy, że mamy n pudełek, każde o rozmiarze R, oraz n przedmiotów o rozmiarach <math>R \ge 
 
r[1]\ge r[2]\ldots \ge r[n]</math>. Mamy włożyć przedmioty do pudełek, co najwyżej dwa do jednego
 
pudełka.  Pozostawiamy jako ćwiczenie analizę następującego algorytmu, który oblicza minimalną
 
liczbę pudełek.
 
 
   
 
   
{{algorytm|Proste-Pakowanie|algorytm_proste_pakowanie|
+
{{algorytm|2-Pakowanie|algorytm_pakowanie|
  <math>wynik := n;</math>
+
1 <math>wynik := n;</math><br><br>
  '''for''' <math>i := 1</math> to n do
+
2 '''for''' <math>i := 1</math> '''to''' n '''do'''<br>
    '''if''' <math>(i < wynik</math>  and <math> r[i]+r[wynik] <= R)</math>
+
3    '''if''' <math>(i < wynik</math>  '''and''' <math> r[i]+r[wynik] <= R)</math> ''' <br>
      <math>wynik := wynik-1;</math>
+
4            <math>wynik := wynik-1;</math>
 
}}
 
}}
  
 
<center><flash>file=Klocki.swf|width=450|height=250</flash></center>
 
<center><flash>file=Klocki.swf|width=450|height=250</flash></center>
  
Naiwne wersje powyższych sześciu algorytmów  działają w czasie kwadratowym. W każdym z tych
+
==== Algorytm 8. Równoważność cykliczna ciągów ====
algorytmów bardzo proste spostrzeżenia prowadzą do algorytmów liniowych.
 
Podamy jeszcze jeden bardzo krótki ciekawy algorytm (chociaż bez żadnego widocznego
 
zastosowania praktycznego).
 
  
==== Permutacje wagowe====
+
Niech <math>u,v</math> będą całkowitoliczbowymi ciągami długości <math>n</math> zadanymi tablicami o zakresie [0..n-1].
Przypuśćmy, że mamy wagę
+
Jest to wyjątek, z reguły poprzednio przyjmowaliśmy, że tablica zaczyna się od pozycji jeden.  
szalkową, początkowo obie szalki sa puste, oraz mamy odważniki o numerach  1,2,..n. Waga i-tego
 
odważnika wynosi <math> a_i</math>.
 
Dla danej permutacji <math>\Pi</math> numerów odważników będziemy je wkładać na wagę
 
zgodnie z permutacją. Kładziemy kolejno odważniki
 
w kolejności <math> \Pi </math> na lewą lub prawa szalkę, raz położony odważnik nie zmieia już
 
nigdy swego położenia na szalce (wybór szalki jest dosyć
 
niedeterministyczny). Otrzymujemy ciąg wyników ważenia: +1 gdy lewa szalka  przeważa, wpp. -1.  
 
Ciąg ten oznaczamy przez Input.
 
Mówimy że  permutacja <math> \Pi </math> jest zgodna z ciągiem wyników ważeń danych tablicą
 
Input. Zajmiemy się problemem: dany
 
jest na wejściu ciąg Input wyników ważeń i mamy znalezć
 
jakąkolwiek permutację <math> \Pi </math> zgodną z ciągiem Input. Takich permutacji może być
 
wiele. Zauważmy, że  
 
liczba permutacji wynosi n!, a liczba ciągów wyników ważeń wynosi <math> 2^n</math>, co jest
 
liczbą znacznie mniejszą. <br>
 
Następujący algorytm znajduje pewną permutację zgodną.
 
Zakładamy że
 
  
  <center> <math> a_1<a_2<a_3<\ldots a_n</math></center>
+
Mówimy, że u, v sa cyklicznie równoważne gdy <math> v= u[k+1.. n-1]u[0.. k]</math> dla pewnego przesunięcia cyklicznego k.
  
{{algorytm|Permutacja-Wagowa|algorytm_permutacja_wagowa|
+
Niech <math> x \mod n </math> oznacza resztę modulo n, np. dla <math>n=9</math> mamy:  <math>88 \mod n= 7</math> .  <br>
    <math> p:=1; q:=n;</math>
+
 
    '''for''' <math>i:=n </math> '''downto''' <math>1</math> '''do'''
+
Naiwny algorytm sprawdzałby równość <math> v= u[k+1.. n-1]u[0.. k]</math> dla każego k, za każdym razem wykonując być może liniową
      '''if''' <math>(i>1)\ \textrm{and}\   (Input[i-1] \ne Input[i])</math>)
+
liczbę operacji (w sumie kwadratową).
        <math> Wynik[i]:= q; q:=q-1; </math>
+
 
      '''else '''  
+
Następujący algorytm jest niewiele bardziej skomplikowany w porówaniu z naiwnym,
          <math> Wynik[i] := p; p:=p+1</math>;
+
działa w czasie liniowym i daje w wniku (zatrzymując się)  wartość ''true'' wtedy i tylko wtedy gdy <br>
 +
ciągi są cyklicznie równoważne.
 +
 
 +
{{algorytm|Równoważność-Cykliczna|algorytm_równoważność_cykliczna|
 +
<math>i:=-1</math>; <math>j:=-1</math>;<br>
 +
2  '''while''' <math>true </math> '''do''' <br>
 +
3    '''if ''' <math> (i>n-1)</math> '''or''' <math>(j>n-1)</math> '''then return''' false; <math>k:=1</math>; <br>
 +
4    '''while''' <math>u[(i+ k) \mod\ n]=v[(j+ k)\mod\ n]</math> '''and''' <math> k\le n</math> '''do''' <math>k:=k+1</math>; <br>
 +
5    '''if''' <math>k>n</math> '''then return''' true; <br>
 +
6    '''if''' <math>u[(i+ k)\mod\ n]>v[(j+ k)\mod\ n]</math> '''then''' <math>i:=i+k</math> '''else''' <math>j:=j+k</math>;
 
}}
 
}}
  
Jeśli Input = [+1,+1,+1,-1,-1,-1,+1,+1,-1], to Wynik = [6 5 4 7 3 2 8 1 9].
+
Problem poprawności jest tutaj znacznie bardziej skomplikowany niż dosyć oczywista złóżoność liniowa.  Pozostawiamy to jako ćwiczenie.
Ciąg Input jest zrealizowany przez następujący ciąg wyborów wkładania kolejnego odważnika:
 
<center>  L  P  L  P  P  L  L  P  P </center>
 
  
gdzie L oznacza połóż na lewą szalkę, P na prawą.
+
==== Algorytm 9. Liczba inwersji permutacji ====
  
Wynik algorytmu pozostawia pewien niedosyt: generujemy dobry wynik ale
+
Niech <math>P[0..n-1]</math> będzie permutacją liczb <math>0,\ 1,\ 2\ ..n-1</math> zadaną tablicą o zakresie [0..n-1].<br>
w pewnym sensie jakikolwiek dobry. Nie jest jasne, jak policzyć efektywnie liczbę wszystkich
+
Liczbą inwersji jest liczba par <math>i<j</math>
permutacji zgodnych z danym ciągiem wyników, albo
+
takich że <math> P[i]>P[j]</math>.
znależć jakąś szczególną permutację, np. leksykograficznie pierwszą lub ostatnią.
+
<br>
Co będzie, jeśli tablica Input zawiera również zera (wagi szalek są równe)? Wtedy nie każdy ciąg Input
+
Na przkład mamy 15 inwersji w permutacji  
jest realizowalny.  Jak można by to efektywnie sprawdzać?
+
<br>
 +
<center><math> P[0..6]= [5,\ 4,\ 3,\ 6,\ 0,\ 1,\ 2]</math></center>
  
== Koszt zamortyzowany ==
+
 
Jeśli mamy ciąg operacji <math>op_1,op_2,\ldots, op_n</math> to koszt zamortyzowany jednej z  
+
Pomocniczą tablicą będzie <math>Licz[0..n]</math>, załóżmy że początkowo zawiera ona same zera.
 +
<br>
 +
Funkcja logiczna <math>odd()</math> sprawdza czy liczba jest nieparzysta.
 +
Funkcja <math> div</math> jest dzieleniem całkowitoliczbowym,
 +
pomijamy resztę.
 +
<br>
 +
Funkcja <math> \log n</math> zwraca całkowitoliczbową część logarytmu przy podstawie 2, np. <math>\log 1025= 10</math>.
 +
 
 +
Końcową wartością zmiennej <math> wynik</math> jest liczba inwersji permutacji P.
 +
 
 +
{{algorytm|Liczba-Inwersji (algorytm Ryttera)|algorytm_liczenie_inwersji|
 +
1  <math> wynik:=0 </math>; <br>
 +
2  '''repeat''' <math>\log n </math> '''times''' <br>
 +
3      '''for''' <math>i:=0</math> '''to''' <math>n-1</math> '''do'''<br>
 +
4            '''if''' <math> odd(P[i])</math> '''then''' <math>Licz[P[i]]:=Licz[P[i]]+1</math><br>
 +
5              '''else''' <math>wynik:=wynik+Licz[P[i]+1]</math>;<br>
 +
6      '''for''' <math>i=0</math> '''to''' <math>n-1</math> '''do'''<br>
 +
7            <math> Licz[i]:=0; P[i]:=P[i]\ div\ 2</math>
 +
}}
 +
 
 +
 
 +
 
 +
Algorytm naiwny liczyłby wynik sprawdzając wszystkie pary <math>i<j</math>, a więc w czasie kwadratowym.
 +
 
 +
Nasz algorytm liczy to w czasie <math>O(n \log n)</math>. Złożoność jest oczywista, poprawność jest mniej oczywista.
 +
 
 +
Oznaczmy  <math>\delta(x)=x\ div\ 2,\ \  \delta^0(x)=x,\ \ \delta^{k+1}(x)=\delta(\delta^{k}(x))</math>.
 +
<br>
 +
Poprawność algorytmu wynika z nastepujacego faktu:
 +
<br>
 +
dla każdych liczb naturalnych <math> x<y</math> istnieje '''dokladnie jedna''' liczba naturalna k
 +
taka że
 +
<br>
 +
<center>  <math> \delta^k(x)+1=\delta^k(y)\ \ \text{oraz}\ \  odd(\delta^k(y))</math>.</center>
 +
 
 +
 
 +
 
 +
Funkcję dzielenia można łatwo wyeliminowac i pozostawić jedynie operacje arytmetyczne dodawania i odejmowania.
 +
 
 +
 
 +
Przy okazji algorytmów sortowania można skonstruować kilka innych algorytmów dla tego samego probemu.
 +
<br> Możemy terza liczyć inwersję dla każdego ciągu elementów, niekoniecznie będącego permutacją.
 +
<br>
 +
Liczba zamian elementów w ''insertion-sort'' jest równa liczbie inwersji,<br>
 +
podobnie algorytm
 +
''merge-sort'' możemy rozbudować tak aby liczył liczbę inwersji w czasie rzędu n log n.<br>
 +
Algorytmy inserion-sor, merge-sort poznamy w następnych modułach.<br> Ograniczymy się tutaj jedynie do
 +
algorytmu licznia inwersji między dwiema posortowanymi rosnąco tablicami <math> A[1..n],B[1..n]</math>.<br>
 +
 
 +
W poniższym algorytmie zakładamy że tablice A, B są posortowane rosnąco.<br>
 +
Wynikiem jest liczba par <math> (i,j) </math> taich,że <math> A[i]>B[j]</math>.
 +
 
 +
{{algorytm|Inwersje-Między-AB|algorytm_między|
 +
1  <math> wynik:=0; i:=1; j:=1; </math>; <br>
 +
2  '''while''' <math>i <= n </math> '''do''' <br>
 +
3      '''if''' <math>j<=n</math> ''and'' <math>A[i]>B[j]</math> '''then''' <math> j:=j+1;</math>
 +
5      '''else'''
 +
6              <math> wynik:=wynik+j-1; i:=i+1;</math>
 +
}}
 +
 
 +
==== Algorytm 10. Generacja permutacji ====
 +
 
 +
Niech <math>P[1..n]</math> będzie permutacją liczb 1,2,..n.
 +
Oznaczmy przez <math> P_0=[1,2,3\ldots n]</math> permutację identycznościową.<br>
 +
Operacja <math>rotacja(k,P)</math> polega na
 +
rotacji cyklicznej pierwszych k elementów tablicy P: <math>k</math>-ty element wędruje na początek. Na przykład:
 +
<br>
 +
<center>
 +
<math>  rotacja(4,[a_1,a_2,a_3,a_4,a_5,a_6])= [a_4,a_1,a_2,a_3,a_5,a_6]</math>
 +
</center>
 +
 
 +
 
 +
Następujący algorytm generuje wszystkie permutacje,
 +
każdą dokladnie raz. <br>
 +
Operacja <math> wypisz</math> wypisuje w kolejnym wierszu tablicę P.
 +
 +
 
 +
{{algorytm|Generacja-Permutacji|Generacja|
 +
1  <math>P := P_0; \ j:=n;\ wypisz(P);</math><br><br>
 +
2  '''while''' <math>j>1</math> '''do'''<br>
 +
3    <math> rotacja(j,P);</math><br>
 +
4    '''if''' <math>j\ne P[j] </math> 
 +
5            <math>wypisz(P); j:=n;</math>
 +
6    '''else'''
 +
7            <math>j:=j-1</math>
 +
}}
 +
 
 +
 
 +
Algorytm ten ma następujacą ciekawą własność: jesli zdefiniujemy rotację jako
 +
operację odwrotna do tej którą mamy (pierwszy element wędruje <br> za <math>k</math>-ty element) to
 +
algorytm w dalszym ciągu jest poprawny: wypisuje dokładnie raz każdą permutację.
 +
 
 +
<br>
 +
Mozna rozwazyc jeszcze prostsza operacje zmiany jednej permutacji w druga: wymiana elementu na pozycji 1-szej
 +
z elementem na pozyci k-tej.<br> Pokazac ze mozna wygenerowac wszystkie permutacje stosujac za kazdym razem pojedyncza
 +
operacje takiej zamiany.<br>
 +
Jednakze ten algorytm ma musi miec zupelnie inna strukture.<br>
 +
Na przyklad dla <math>n=4</math> ciag pozycji k moze byc nastepujacy: 2 3 2 3 2 4 3 2 3 2 3 4 2 3 2 3 2 4 3 2 3 2 3 .
 +
 
 +
<br>
 +
Rozważmy podobny algorytm do algorytmu Generacja-Permutacji generowania podzbiorów k-elemntowych (kombinacji)<br> zbioru n-elementowego,
 +
każda konfiguracja jest ciągiem K zerojedynkowym mającym dokładnie k jedynek.<br>
 +
Inaczej mowiąc chcemy wygenerowąc każdy taki ciąg dokładnie raz.
 +
K jest jednocześnie traktowane jako ciąg i jako tablica n-elementowa.
 +
<br><br>
 +
Oznaczmy przez
 +
SzukajWzorzec(01,K)
 +
długośc najkrótszego prefiksu
 +
ciągu K kończącego się na 01. Na przykład SzukajWzorzec(01,111100001001) = 9.
 +
<br>
 +
 
 +
{{algorytm|Generacja-kombinacji|Generacja|
 +
1  <math>K := 1^k0^{n-k}; \ j:=n-1;</math> <br>
 +
2  Załóżmy że <math> 0<k<n </math><br><br>
 +
3  '''while''' <math>j<n</math> '''do'''<br>
 +
4    <math> wypisz(K);\ rotacja(j+1,K);</math><br>
 +
5    <math> j:=  \text{SzukajWzorzec}(01,K)</math> 
 +
}}
 +
 
 +
=== Koszt zamortyzowany ===
 +
Jeśli mamy ciąg operacji <math>op_1,op_2,\ldots, op_n</math>, to koszt zamortyzowany jednej z  
 
nich jest sumarycznym kosztem
 
nich jest sumarycznym kosztem
wykonania wszystkich operacji podzielonym przez liczbę operacji, inaczej mówiąc jest to, dla danego  
+
wykonania wszystkich operacji podzielonym przez liczbę operacji. Inaczej mówiąc jest to, dla danego  
ciągu operacji, średni koszt jednej z nich. Zauważmy,  
+
ciągu operacji, "średni" koszt jednej z nich. Zauważmy,  
że nie mówmy tu nic o prawdopodobieństwie, model jest deterministyczny. Na przykład w algorytmie  
+
że nie mówimy tu nic o prawdopodobieństwie - model jest deterministyczny. Na przykład w algorytmie  
 
Najbliższy-Mniejszy-Sąsiad rozważmy ciąg operacji  
 
Najbliższy-Mniejszy-Sąsiad rozważmy ciąg operacji  
  
 
<math>op_i</math>: while <math>( A[j] >= A[i])\ j = Lewy[j]</math>
 
<math>op_i</math>: while <math>( A[j] >= A[i])\ j = Lewy[j]</math>
  
Koszt pojedyńczej operacji może być liniowy, również sumaryczny koszt ciągu tych operacji  
+
Koszt pojedynczej operacji może być liniowy, również sumaryczny koszt ciągu tych operacji  
 
<math>op_1,op_2,\ldots, op_n</math> jest liniowy. Zatem
 
<math>op_1,op_2,\ldots, op_n</math> jest liniowy. Zatem
 
pesymistyczny koszt jednej operacji jest tutaj liniowy, natomiast zamortyzowany koszt jednej operacji  
 
pesymistyczny koszt jednej operacji jest tutaj liniowy, natomiast zamortyzowany koszt jednej operacji  
Linia 346: Linia 661:
 
odbywa się tylko raz dla danej wartości <math>j</math>. Możemy powiedzieć, że księgujemy koszt  
 
odbywa się tylko raz dla danej wartości <math>j</math>. Możemy powiedzieć, że księgujemy koszt  
 
operacji elementom <math>j</math>
 
operacji elementom <math>j</math>
 
 
o tej własności. Nieformalna metoda księgowania kosztów polega na rozdzielaniu (księgowaniu)  
 
o tej własności. Nieformalna metoda księgowania kosztów polega na rozdzielaniu (księgowaniu)  
 
kosztu, a
 
kosztu, a
 
następnie szacowaniu sumarycznej złożoności poprzez sumowanie wszystkich zaksięgowanych  
 
następnie szacowaniu sumarycznej złożoności poprzez sumowanie wszystkich zaksięgowanych  
 
kosztów. Operacje
 
kosztów. Operacje
pożyczają, w pewnym sensie, fundusze na pokrycie kosztów z różnych źródeł. Metoda ta będzie  
+
pożyczają w pewnym sensie fundusze na pokrycie kosztów z różnych źródeł. Metoda ta będzie  
 
wykorzystana
 
wykorzystana
 
do analizy algorytmu dla interesującego problemu Find-Union.  
 
do analizy algorytmu dla interesującego problemu Find-Union.  
  
Typowym przykładem liczenia kosztu w sposób zamortyzowany jest analiza generacji kolejnych
+
Typowym przykładem liczenia kosztu w sposób zamortyzowany jest analiza generacji  
reprezentacji binarnych kolejnych liczb naturalnych od 0 do <math>2^n-1</math>,
+
reprezentacji binarnych kolejnych liczb naturalnych od 0 do <math>2^n-1</math> przez
dodając jedynkę. W jednym kroku zastępujemy najdłuższy ciąg jedynek od końca zerami, następnie  
+
dodawanie jedynki. W jednym kroku zastępujemy najdłuższy ciąg jedynek od końca zerami, następnie  
 
wstawiamy
 
wstawiamy
 
jedną jedynkę. Ponieważ w sumie wstawiliśmy <math>2^n-1</math> jedynek w ciągu <math>2^n-
 
jedną jedynkę. Ponieważ w sumie wstawiliśmy <math>2^n-1</math> jedynek w ciągu <math>2^n-
Linia 377: Linia 691:
 
Metodę magazynu można uogólnić na tzw. metodę potencjału. Niech <math>\Phi_i</math> będzie  
 
Metodę magazynu można uogólnić na tzw. metodę potencjału. Niech <math>\Phi_i</math> będzie  
 
pewną liczbą naturalną (włączając zero) odpowiadającą potencjałowi  
 
pewną liczbą naturalną (włączając zero) odpowiadającą potencjałowi  
po wykonaniu <math>i</math> operacji.  (Wyglądałoby to mniej tajemniczo, gdybyśmy zamiast <math> \Phi(i)</math>
+
po wykonaniu <math>i</math>-tej operacji.   
pisali Bilans(i).
+
Wyglądałoby to mniej tajemniczo, gdybyśmy zamiast <math> \Phi(i)</math> pisali <math>Bilans(i)</math>.
  
 
Niech <math> koszt(i)</math>
 
Niech <math> koszt(i)</math>
będzie kosztem wykonania operacji i-tej.
+
będzie rzeczywistym kosztem wykonania ''i''-tej operacji.
  
 
Zakładamy, że potencjał jest początkowo zero, nigdy nie jest  
 
Zakładamy, że potencjał jest początkowo zero, nigdy nie jest  
ujemny, oraz że:
+
ujemny oraz że:
  
 
<center>  <math>\Phi_i=\Phi_{i-1}+wplata(i)-wyplata(i)</math> oraz <math> koszt(i)\le wyplata(i) </math>.</center>
 
<center>  <math>\Phi_i=\Phi_{i-1}+wplata(i)-wyplata(i)</math> oraz <math> koszt(i)\le wyplata(i) </math>.</center>
Linia 392: Linia 706:
 
W naszych poprzednich przykładach rozmiar magazynu jest w tym sensie potencjałem.
 
W naszych poprzednich przykładach rozmiar magazynu jest w tym sensie potencjałem.
  
Można powiedzieć obrazowo że potencjał jest kapitałem Funduszu Ubezpieczeń Kosztów  
+
Można powiedzieć obrazowo, że potencjał jest kapitałem Funduszu Ubezpieczeń Kosztów  
Algorytmicznych. Jeśli wszystkie wpłaty są takie same to koszt zamortyzowany jednej operacji jest wpłatą (składką),  którą ta operacja wpłaca do funduszu.
+
Algorytmicznych. Jeśli wszystkie wpłaty są takie same, to koszt zamortyzowany jednej operacji jest wpłatą (składką),  którą ta operacja wpłaca do funduszu.
  
Operacja najpierw wpłaca swoją składkę a następnie pobiera z funduszu tyle, żeby proporcjonalnie (być może z dokładnością do stałego współczynnika) zapłacić za swój koszt wykonania.
+
Operacja najpierw wpłaca swoją składkę, a następnie pobiera z funduszu tyle, żeby proporcjonalnie (być może z dokładnością do stałego współczynnika) zapłacić za swój koszt wykonania.
  
Dzięki temu, że wiele operacji pobiera z funduszu znacznie mniej niż wpłaca niektóre operacje mogą  
+
Dzięki temu, że wiele operacji pobiera z funduszu znacznie mniej niż wpłaca, niektóre operacje mogą  
jednorazowo pobrać dużą kwotę, którą płacą za koszt wykonania. Operacje
+
jednorazowo pobrać dużą kwotę, którą płacą za koszt wykonania. Istotne jest jedynie,
ubezpieczają się od kosztów ich
+
żeby Fundusz nie zbankrutował i kapitał nie zszedł poniżej zera. Możliwa jest również sytuacja, gdy  
wykonani. Poszczególne operacje płacą drobne składki <math>wplata(i)</math>, a swój koszt za każdym
 
razem opłacają biorąc pieniądze z Funduszu.
 
Czasami koszt operacji jest duży ale do tego czasu wpłacono tyle drobnych składek, że możemy ten
 
koszt pokryć. Istotne jest jedynie  
 
żeby Fundusz nie zbankrutował i kapitał nie zszedł poniżej zera. Możliwa jest również sytuacja gdy  
 
 
Fundusz startuje  
 
Fundusz startuje  
 
z kapitałem początkowym. Wtedy kapitał ten wlicza
 
z kapitałem początkowym. Wtedy kapitał ten wlicza
Linia 414: Linia 723:
 
==== Tablica dynamiczna====
 
==== Tablica dynamiczna====
 
Przypuśćmy, że mamy dynamiczną tablicę. W każdym momencie wiemy, ile elementów w tablicy jest  
 
Przypuśćmy, że mamy dynamiczną tablicę. W każdym momencie wiemy, ile elementów w tablicy jest  
aktywnych; elementy nieaktywne zaznaczamy. Przy
+
aktywnych, elementy nieaktywne zaznaczamy. W
każdej operacji, jeśli liczba elementów aktywnych spada poniżej <math>\frac{1}{4}</math>  
+
każdej operacji, jeśli liczba elementów nieaktywnych jest mniejsza od <math>\frac{1}{4}</math>  
rozmiaru tablicy, to tworzymy tablicę  
+
wielkości tablicy, to tworzymy tablicę  
dwa razy mniejszą i tam przepisujemy elementy aktywne, a starą tablicę zwalniamy. Jeśli natomiast chcemy dodać element,  
+
dwa razy mniejszą i tam przepisujemy elementy aktywne. Starą tablicę zwalniamy. W przeciwnym
który spowoduje przepełnienie tablicy to całą tablicę kopiujemy do tablicy dwa razy większej.  
+
wypadku jeśli chcemy dodać element,  
 +
który spowoduje przepełnienie tablicy, to całą tablicę kopiujemy do tablicy dwa razy większej.  
 
Początkowo tablica ma rozmiar 1.  
 
Początkowo tablica ma rozmiar 1.  
 
Zakładamy, że operacją dominującą jest kopiowanie aktywnego elementu do nowej tablicy. Jeśli  
 
Zakładamy, że operacją dominującą jest kopiowanie aktywnego elementu do nowej tablicy. Jeśli  
mamy <math>n</math> operacji to  
+
mamy <math>n</math> operacji, to  
 
całkowity koszt kopiowania jest liniowy. Wystarczy w każdej operacji dać składkę 4 jednostek do  
 
całkowity koszt kopiowania jest liniowy. Wystarczy w każdej operacji dać składkę 4 jednostek do  
 
Funduszu (potencjału).   
 
Funduszu (potencjału).   
 
Wtedy koszt jednej dużej operacji przepisywania  zamortyzuje się zmianą potencjału.
 
Wtedy koszt jednej dużej operacji przepisywania  zamortyzuje się zmianą potencjału.
 +
  
 
==== Zastąpienie kolejki dwoma stosami====
 
==== Zastąpienie kolejki dwoma stosami====
Jedną kolejkę Q można zastąpić dwoma stosami <math>S1,\ S2</math>. Jeśli pierwszy element stosu  
+
Jedną kolejkę ''Q'' można zastąpić dwoma stosami <math>S1,\ S2</math>. Jeśli pierwszy element stosu  
 
lub kolejki w
 
lub kolejki w
 
reprezentacji poziomej jest w ciągu na pierwszej pozycji (tzn. pobieramy <math>e_1</math>,  
 
reprezentacji poziomej jest w ciągu na pierwszej pozycji (tzn. pobieramy <math>e_1</math>,  
dostawiamy za <math>e_n</math>)
+
stawiamy za <math>e_n</math>),
 
oraz <math> Q = (e_1,e_2,..,e_k)</math>, to dla pewnego <math>j </math> mamy:
 
oraz <math> Q = (e_1,e_2,..,e_k)</math>, to dla pewnego <math>j </math> mamy:
  
Linia 438: Linia 749:
 
ostatni element kolejki jest na wierzchołku pierwszego stosu.
 
ostatni element kolejki jest na wierzchołku pierwszego stosu.
  
Operacja wstawiania do A odpowiada wstawieniu elementu do <math>S1</math>, operacja pobrania  
+
Operacja wstawiania do ''Q'' odpowiada wstawieniu elementu do <math>S1</math>, operacja pobrania  
z Q odpowiada pobraniu elementu z S2  
+
z ''Q'' odpowiada pobraniu elementu z S2  
z tym, że jeśli <math>S2</math> jest pusty to przepisujemy najpierw wszystkie elementy z S1 do S2.  
+
z tym, że jeśli <math>S2</math> jest pusty, to przepisujemy najpierw wszystkie elementy z S1 do S2.  
 
Niech operacją dominującą  
 
Niech operacją dominującą  
 
będzie jedna operacja stosowa (wstawienie lub pobranie pojedynczego elementu ze stosu). Wtedy ciąg  
 
będzie jedna operacja stosowa (wstawienie lub pobranie pojedynczego elementu ze stosu). Wtedy ciąg  
Linia 449: Linia 760:
  
 
==== Zastąpienie kolejki dwustronnej  trzema stosami====
 
==== Zastąpienie kolejki dwustronnej  trzema stosami====
Roważmy podobny problem, z tym że nasza kolejka jest dwustronna: możemy wkładać i pobierać  
+
Rozważmy podobny problem - z tym, że nasza kolejka jest dwustronna, możemy wkładać i pobierać  
 
element z każdego z dwóch końców kolejki.
 
element z każdego z dwóch końców kolejki.
 
Wtedy możemy taką kolejkę zastąpić trzema stosami tak, że teraz również każda operacja kolejkowa  
 
Wtedy możemy taką kolejkę zastąpić trzema stosami tak, że teraz również każda operacja kolejkowa  
 
będzie mieć zamortyzowany koszt stały.
 
będzie mieć zamortyzowany koszt stały.
Elementy kolejki trzymamy w dwóch stosach S1, S2 tak jak poprzednio. Niezmiennikiem jest to, że  
+
Elementy kolejki trzymamy w dwóch stosach S1, S2 tak, jak poprzednio. Niezmiennikiem jest to, że  
oba stosy są niepuste lub mają w sumie co  
+
oba stosy są niepuste, lub mają w sumie co  
 
najwyżej jeden element. Zapewniamy zachodzenie niezmiennika wykorzystując trzeci stos. W  
 
najwyżej jeden element. Zapewniamy zachodzenie niezmiennika wykorzystując trzeci stos. W  
 
momencie, gdy jeden ze stosów ma więcej niż jeden element, a  
 
momencie, gdy jeden ze stosów ma więcej niż jeden element, a  
drugi jest pusty, korzystając z trzeciego stosu doprowadzamy do reprezentacji aktualnej kolejki przez  
+
drugi jest pusty, korzystając z trzeciego stosu, doprowadzamy do reprezentacji aktualnej kolejki przez  
stosy S1, S2, tak aby miały one tę samą  
+
stosy S1 i S2 tak, aby miały one tę samą  
 
liczbę elementów (z dokładnością do 1). Pozostawiamy jako ćwiczenie dowód (metodą potencjału)  
 
liczbę elementów (z dokładnością do 1). Pozostawiamy jako ćwiczenie dowód (metodą potencjału)  
 
tego, że zamortyzowany koszt jest stały.
 
tego, że zamortyzowany koszt jest stały.

Aktualna wersja na dzień 12:52, 9 cze 2020


Wykład Algorytmy i struktury danych jest poświęcony przede wszystkim koncepcyjnym i strukturalnym metodom efektywnego rozwiązywania problemów na komputerze. Podstawowym elementem przy rozwiązywaniu zadanego problemu jest dobór algorytmu i struktury danych. Najważniejszymi aspektami algorytmu są jego poprawność i złożoność (czasowa i pamięciowa).

W przypadku złożoności czasowej, z reguły wyróżnimy pewną operację dominującą, a czas będziemy traktować jako liczbę wykonanych operacji dominujących. W ten sposób nasza analiza będzie zależna jedynie od algorytmu, a nie od implementacji i sprzętu. W przypadku sortowania, operacją dominującą jest przeważnie porównanie dwóch elementów, a w przypadku przeglądania drzewa - jedno przejście w drzewie między wierzchołkami. W przypadku algorytmów tekstowych operacją dominującą jest porównanie dwóch symboli. Zazwyczaj określamy pewien parametr , będący rozmiarem problemu wejściowego i określamy złożoność jako funkcję , której argumentem jest rozmiar problemu. Z reguły będziemy przyjmować, że każda operacja arytmetyczna na małych liczbach daje się wykonać w jednym kroku. Przez "małe" rozumiemy liczby mające bitów.


Złożoność algorytmu może być rozumiana w sensie złożoności najgorszego przypadku lub złożoności średniej. Złożoność najgorszego przypadku nazywamy złożonością pesymistyczną - jest to maksymalna złożoność dla danych tego samego rozmiaru . W praktyce ważniejsza może się okazać złożoność średnia lub oczekiwana. W tym przypadku jest średnią (oczekiwaną) wartością złożoności dla wszystkich problemów rozmiaru . Tego typu złożoność zależy istotnie od tego, jaka się pod tym kryje przestrzeń probabilistyczna danych wejściowych. Z reguły zakładamy, że wszystkie dane wejściowe tego samego rozmiaru mogą się pojawić z tym samym prawdopodobieństwem. Jednakże jest to często mało realistyczne założenie. Przestrzeń probabilistyczna danych wejściowych może być bardzo skomplikowana. Prowadzić to może do bardzo trudnych (i wykraczających poza ten kurs) analiz.

Rozważmy następujący przykład. Przypuśćmy, że chcemy znaleźć pierwszą jedynkę w n-elementowej tablicy zerojedynkowej i nasz algorytm przegląda tablicę od strony lewej sprawdzając kolejne elementy. Niech operacją dominującą będzie sprawdzenie jednego elementu. Jeśli nie ma jedynki, to wykonamy sprawdzeń. Jest to maksymalna liczba, zatem złożoność pesymistyczna wynosi . Jeśli każdy ciąg binarny jest dany z tym samym prawdopodobieństwem, to łatwo policzyć, że złożoność średnia jest ograniczona przez stałą.

Do wyrażania złożoności stosujemy opis asymptotycznego wzrostu funkcji: oznacza, że dla pewnej stałej . Gdy , to mówimy, że jest liniowa, oraz dla mówimy, że złożoność jest kwadratowa. Jeśli jest wielomianem, to wtedy mówimy o złożoności wielomianowej.


Będziemy używać dodatkowych notacji:

. Były one wprowadzone na wykładach z matematyki dyskretnej.

Przykład

,



Konwencje językowe. Jaki jest najlepszy język do opisu algorytmu? Jest to przykład problemu nierozstrzygalnego. Niewątpliwie język ojczysty jest najlepszym językiem potocznym, a ulubiony język programowania jest najlepszym językiem do implementacji algorytmu. Język, którym będziemy opisywać algorytmy, jest gdzieś pomiędzy tymi językami - język potoczny nie wystarcza, a konkretny język programowania może spowodować, że "prosty" algorytm się zrobi nieczytelny. Będziemy używać, o ile się da, nieformalnych konstrukcji programistycznych, a w przypadkach bardzo prostych będziemy się starali pisać algorytm w języku Pascalopodobnym.

Poprawność algorytmu: niezmienniki, własność stopu

Przez poprawność algorytmu rozumiemy to, że daje on takie odpowiedzi, jakich oczekujemy. Oczywiście algorytm musi być poprawny, aby miało sens rozpatrywanie jego złożoności.

Pojęcie niezmiennika

Poprawność algorytmu sprowadza się do spełniania określonych niezmienników na różnych etapach wykonywania tego algorytmu. Rozważmy kilka przykładów pozwalających zrozumieć znaczenie niezmiennika.

Załóżmy, że mamy zbiór składający się z przedmiotów. Niektóre z przedmiotów są czarne, a niektóre białe. Zakładamy, że liczba czarnych przedmiotów jest nieparzysta.


Algorytm Biało-czarne1


1  while   do begin
2    pobierz dwa przedmioty z S;
3    if przedmioty są różnego koloru then wstaw z powrotem czarny
4  end;
5  return kolor ostatniego przedmiotu w S;

Załóżmy, że mamy 10000001 czarnych przedmiotów i 1000000001 białych, jaki jest ostatni przedmiot? Rozpatrzmy niezmiennik: parzystość liczby czarnych przedmiotów.

Ponieważ na początku mamy nieparzystą liczbę czarnych przedmiotów, zatem wynikiem jest kolor czarny.


Rozpatrzmy modyfikację tego algorytmu, zakładamy że jest niezerowe.

Algorytm Biało-czarne2


1  while   do begin
2    pobierz dwa przedmioty z S;
3    if co najmniej jeden jest biały then wstaw z powrotem jeden biały;
4  end;
5  return kolor ostatniego przedmiotu w S;

Załóżmy, że mamy 10000001 czarnych przedmiotów i 1000000001 białych, jaki jest ostatni przedmiot? Tym razem rozważmy niezmiennik: znak liczby białych przedmiotów. (Znak liczby jest równy 0, jeśli jest ona równa zeru, 1 - jeśli jest większa od zera.) Zatem ostatnim przedmiotem jest przedmiot biały.



Własność stopu

Jednym z podstawowych elementów poprawności algorytmu jest własność stopu: dla poprawnych danych wejściowych algorytm zatrzymuje się w skończonym czasie.
Na przykładzie czterech krótkich algorytmów pokażemy, że sprawdzanie własności stopu może nie być czynnością trywialną.

Algorytm Suma-Kwadratów-Cyfr


 1  while    and   do
 2     suma kwadratów cyfr liczby ;


Algorytm 6174


//  jest czterocyfrową liczbą naturalną niepodzielną przez 1111
// pierwszymi cyframi n mogą być zera
1  while (n<>6174) do 
2 największa liczba czterocyfrowa, której cyfry są permutacją cyfr liczby ; 3 najmniejsza liczba czterocyfrowa, której cyfry są permutacją cyfr liczby ; 4

W przypadku liczb trzycyfrowych rolę liczby 6174 pełni liczba 495. W przypadku liczb pięciocyfrowych nie ma takiej pojedyńczej liczby.


Rozpatrzmy następujący algorytm (zaprojektowany podobno przez
Fibonacciego) na rozkład ułamka na sumę parami różnych ułamków Egipskich,

tzn. ułamków postaci .


Rozkład Egipski jest postaci gdzie są liczbami naturalnymi:


Każdy ułamek ma rozkład Egipski, oto przykład takiego rozkładu:



Niech oznacza najwięszy ułamek Egipski (tzn. postaci ) nie przekraczający x.

Przykłady:


Niech będą dwiema względnie pierwszymi liczbami naturalnymi. Następujący algorytm oblicza rozkład (niekoniecznie najkrótszy) nieskracalnego ułamka na ułamki Egipskie.


Algorytm Rozkład-Egipski


(algorytm Fibonacciego)
1
2 while (x>0) do
3 output y; 4


Nasz algorytm dla wejścia (31,311), tzn. , wyprodukuje 10 składników w rozkładzie Egipskim.


Dla wejścia otrzymamy jako wynik następujący ciąg ułamków Egispskich:


Algorytm ma własność stopu ponieważ liczniki kolejnych dodatnich wartości (przedstawionych jako nieskracalne ułamki) maleją
(pozostawiamy dowód tego faktu jako ćwiczenie).
Oto przykład ciągu kolejnych wartości : 4/5 -> 3/10 -> 1/10. Liczniki maleją: .
W pewnym momencie licznik liczby dochodzi do jedynki, wtedy następna wartość staje się zerem i algorytm zatrzymuje się.
Zatem algorytm wykonuje co najwyżej iteracji dla wejścia .


Rozpatrzmy jeszcze jeden abstrakcyjny algorytm.


Algorytm Bez-Sensu


1 while  do
2    if  parzyste then 
3    else ;   

Pierwsze trzy algorytmy mają własność stopu. W pierwszym łatwo to sprawdzić, gdyż dla następna wartość jest istotnie mniejsza.

Pozostawiamy jako ćwiczenie znalezienie najkrótszego koncepcyjnie dowodu własności stopu dwu pierwszych algorytmów (nie chodzi nam tu o brutalny dowód polegający na sprawdzeniu wszystkich przypadków przez komputer).


Natomiast algorytm Bez-Sensu jest najbardziej zagadkowy. Nie wiadomo, czy dla każdej dodatniej liczby całkowitej ma on własność stopu. Problem ten postawił L. Collatz w roku 1937, wiadomo, że własność stopu zachodzi dla każdego . Problem stopu dwóch ostatnich algorytmów jest teoretycznym problemem matematycznym o dużym stopniu trudności.

Opis algorytmu za pomocą niezmienników

Niezmienniki są często podstawową konstrukcji algorytmu na poziomie koncepcyjnym. Opisujemy jedynie co dana część algorytmu ma wykonać w sensie zachowania odpowiedniego niezmiennika. Reszta jest czasami prostą sprawą natury inżynieryjno-technicznej.


Zademonstrujemy to na następujacym przykładzie posegregowania tablicy liczbowej względem elementu . Dla zbiorów pozycji tablicy piszemy gdy każda pozycja w X jest mniejsza od każdej pozycji w . Piszemy gdy wartości na pozycjach X są mniejsze od a (podobnie z równością).

Zdefiniujmy następujący niezmiennik


Nazwy M,R,W biorą się od Mniejsze, Równe, Większe.


Naszym problemem jest poprzestawiać elementy tablicy tak aby dla pewnych zbiorów M,R,W dających w sumie cały zbiór pozycji zachodził niezmiennik (algorytmy tego typu maja zastosowanie w implmentacji bardzo praktycznego algorytmu Quicksort).

Algorytm wykonuje swoje zadanie startując od zbiorów pustych i zwiększając zbiory. Chcemy aby algorytm działał w miejscu (dodatkowa pamięć stała) i w każdej iteracji wykonywał stałą liczbę operacji.


Algorytm PosegregujTablicę


0  ;
1  while   do 
2    zwiększ o jeden sumę  zachowując niezmiennik    
3    w czasie i dodatkowej pamięci 


Możliwe są różne scenariusze tego algorytmu poprzez dospecyfikowanie niezmiennika. Na przykład możemy zażądąc aby zbiory M,R,W były sąsiednimi przedziałami, tworzącymi razem sufiks (lub prefiks) tablicy, lub aby M było prefiksem a W sufiksem tablicy. Otrzymamy różne algorytmy w pewnym sensie izomorficzne. Naturalnym jest aby zażądać, by każdy ze zbiorów M, R, W był przedziałem, nawet jeśli tego nie zażądamy to tak będzie po zakończeniu algorytmu. Jeśli zbiory są przedziałami to pojedyńcza iteracja polega na manipulacji w okolicy końców przedziałów.

Możemy problem ouogólnić i segregować tablicę względem większej liczby elementów, np. względem elementów . Teraz zamiast dwóch segmentów M, R, W tablicy A mamy pięć zbiorów pozycji, a niezmiennik zamienia się na


Poprawność i złożoność 10 prostych algorytmów

Poniżej dokonamy pobieżnej analizy złożoności obliczeniowej siedmiu algorytmów i wykażemy, że ich złożoności są lepsze od złożoności kwadratowej rozwiązań
naiwnych, chociaż nasze algorytmy będą niewiele bardziej skomplikowane od naiwnych.

Poza dwoma z nich (działającymi w czasie czas ) wszystkie algorytmy działają w czasie liniowym.

Dokładne analizy pozostawiamy jako ćwiczenia.


Algorytm 1. Przywódca ciągu

Przywódcą ciągu jest element, który występuje w ciągu więcej razy niż połowa długości tego ciągu. Naszym problemem jest policzenie przywódcy ciągu danego w tablicy . Dla uproszczenia przyjmijmy, że w tym ciągu jest przywódca. Łatwo zmodyfikować algorytm tak, by sprawdzał istnienie przywódcy.


Algorytm Liczenie-Przywódcy


 1  ;
2 for i 1 to n do
3 if then 4
5 else if then
6 else ;
7 return ;

Przyspieszenie wynika z następującej własności problemu: jeśli mamy dwa różne elementy w tablicy, to możemy je usunąć i przywódca pozostanie taki sam.

Algorytm można zmodyfikować tak, aby w czasie liniowym liczył słabego przywódcę: element, który występuje w tablicy więcej niż razy. W tym przypadku potrzebne są cztery liczniki odpowiadające czterem kandydatom na słabego przywódcę. Algorytm liczy element, który jest kandydatem na słabego przywódcę (jeśli istnieje taki przywódca, to na pewno jest nim wyliczony element). Jeśli istnieje słaby przywódca i mamy pięć różnych elementów, to można je usunąć bez zmiany wyniku. Pozostawiamy napisanie odpowiedniego algorytmu jako ćwiczenie.

Problem można rozwiązać inaczej, sortując tablicę, wtedy mamy złożoność . Podamy potem również rozwiązanie metodą "dziel i zwyciężaj".


<flash>file=przywodca_slaby.swf|width=520|height=270</flash>

W animacji kolorem żółtym na końcu jest zaznaczony licznik słabego przywódcy, a jego nazwa jest umieszczona w niebieskim kwadraciku.

Algorytm 2. Szukanie sumy

Mamy dane dwie tablice posortowane rosnąco i liczbę , pytamy, czy istnieją takie, że .


Algorytm Szukanie Sumy


1   
2 while and do
3 if then return true; 4 else if then 5 else ;
6 return false;

Przyspieszenie jest możliwe dzięki odpowiedniej kolejności sprawdzania i pominięciu zbędnych sprawdzeń.

Algorytm 3. Maksymalny segment

Dla tablicy liczymy maksymalną wartość z zera i ze wszystkich liczb , gdzie .


Algorytm Maksymalny-Segment;
1 wynik := 0; sufiks := 0;
2 for i := 1 to n do
3 sufiks := max(A[i]+sufiks,0); wynik := max(wynik,sufiks);


Przyspieszenie w stosunku do algorytmu kwadratowego następuje dzięki wprowadzeniu dodatkowej zmiennej sufiks. Po każdym zakończeniu pętli "for" zachodzi: wynik jest maksymalną sumą przedziału zawierającego się w oraz sufiks jest maksymalną sumą segmentu, który jest sufiksem przedziału .

Algorytm 4. Najbliższy mniejszy sąsiad w ciągu

Dla każdego zdefiniujmy najbliższego mniejszego (lewego) sąsiada jako

.

Dla uproszczenia zakładamy, że dla oraz .

Algorytm Najbliższy-Mniejszy-Sąsiad


1  for  to n do 
2
3 while do
4


Przyspieszenie w stosunku do algorytmu naiwnego następuje dzięki temu, że nie ma potrzeby sprawdzania tablicy dla indeksów istotnie wewnątrz przedziału . Niech będzie liczbą tych , dla których (w wierszu 3). Wystarczy pokazać, że suma wszystkich jest liniowa ze względu na n. Może się zdarzyć, że niektóre mają wartość liniową. Zauważmy jednak, że dany indeks pojawia się co najwyżej raz w sytuacji, gdy , potem będzie "przeskoczony".


Opiszemy teraz nieformalnie alternatywny algorytm korzystajacy ze stosu.
Zamiast indeksu lewego sasiada bedziemy teraz liczyc wartosc lewego sasiada, inaczej mowiac
liczymy pierwsza wartosc na lewo mniejsza od danej wartosci.
Niech y oznacza element na wierzcholku stosu.


Czytamy kolejne elementy.
Po wczytaniu kolejnego elementu x usuwamy elementy ze stosu dopoki x<y.
W tym momencie znajdujemy lewego sasiada x, jego wartoscia jest y.
Wrzucamy x na stos.


Zalozmy ze A jest permutacja liczb 1,2,..n. Wtedy mozliwy jest jeszcze inny algorytm liniowy.

Trzymamy elementy tablicy w liscie dwukierunkowej.

Dla k=n,n-1,..2 wykonujemy:
lewym sasiadem k zostaje jego poprzednik na liscie.
Nastepnie element k usuwamy z listy.

Algorytm 5. Najdalszy mniejszy sąsiad w permutacji

W tym algorytmie zakładamy że na wejściu jest permutacja A elementów od 1 do n.
Dla każdego zdefiniujmy najdalszego mniejszego (prawego) sąsiada jako
.

W trakcie algorytmu obliczamy tablicę Pozycja, będącą odwrotościa permutacji.
Załóżmy, że początkowo Najd_Prawy[i]=0, Pozycja[i]=0, dla każdego i.

Algorytm Najdalszy-Prawy-Mniejszy-Sąsiad


1     
2 for to n do
3
4 while do
5

Algorytm ten dziła oczywiście w czasie liniowym. Jego wadą jest ograniczenie się do permutacji.

Algorytm 6. Najdłuższy malejący podciąg

Niech będzie ciągiem dodatnich liczb.
Następujący algorytm oblicza długość najdłuższego malejącego podciągu (w kolejności od lewej do prawej strony).


Algorytm Najdłuższy-Malejący


1  
2 for to n do

3
4
5 ;

Poprawność algorytmu nie jest całkowicie oczywista, uzasadnienie można znależć w rozwiązaniu stosownego zadania (patrz Ćwiczenia). Jeśli wejściem jest [5,2,1,3,7] to w momencie gdy algorytm kończy obliczenia, tablica A jest równa [7,3,1,0,0]. Zauważmy, że [7,3,1] wcale nie jest podciągiem (w kierunku od lewej do prawej strony) tablicy wejściowej. Niemniej wynik jest poprawny.

Złożoność alorytmu istotnie zależy od implementacji instrukcji:

.

Ponieważ wszystko się odbywa w tablicy, możemy minimum policzyć łatwo w czasie logarytmicznym stosując szukanie binarne w posortowanej tablicy (segment tablicy jest posortowany). Zatem całkowity koszt algorytm jest przy dosyć prostej implementacji.

Algorytm może, po niewielkim dodatkowym wysiłku procesora, podać najdłuższy malejący podciąg, albo też rozkład na minimalną liczbę podciągów niemalejących. Nie jest jasne, jak policzyć leksykograficznie minimalny i leksykograficznie maksymalny podciąg malejący o długości , gdzie jest wynikiem powyższego algorytmu. Możemy się też zastanowić nad efektywnym algorytmem znajdowania liczby wszystkich takich ciągów długości .

Algorytm 7. Dwa-Pakowanie

Załóżmy, że mamy dowolnie dużą liczbę pudełek, każde o rozmiarze R, oraz n przedmiotów o rozmiarach . Zakładamy, że

.

Mamy włożyć przedmioty do pudełek, co najwyżej dwa do jednego pudełka.

Pozostawiamy jako ćwiczenie analizę następującego algorytmu, który oblicza minimalną liczbę pudełek do zapełnienia.


Algorytm 2-Pakowanie


1  

2 for to n do
3 if and
4
<flash>file=Klocki.swf|width=450|height=250</flash>

Algorytm 8. Równoważność cykliczna ciągów

Niech będą całkowitoliczbowymi ciągami długości zadanymi tablicami o zakresie [0..n-1]. Jest to wyjątek, z reguły poprzednio przyjmowaliśmy, że tablica zaczyna się od pozycji jeden.

Mówimy, że u, v sa cyklicznie równoważne gdy dla pewnego przesunięcia cyklicznego k.

Niech oznacza resztę modulo n, np. dla mamy: .

Naiwny algorytm sprawdzałby równość dla każego k, za każdym razem wykonując być może liniową liczbę operacji (w sumie kwadratową).

Następujący algorytm jest niewiele bardziej skomplikowany w porówaniu z naiwnym, działa w czasie liniowym i daje w wniku (zatrzymując się) wartość true wtedy i tylko wtedy gdy
ciągi są cyklicznie równoważne.

Algorytm Równoważność-Cykliczna


1  ; ;
2 while do
3 if or then return false; ;
4 while and do ;
5 if then return true;
6 if then else ;

Problem poprawności jest tutaj znacznie bardziej skomplikowany niż dosyć oczywista złóżoność liniowa. Pozostawiamy to jako ćwiczenie.

Algorytm 9. Liczba inwersji permutacji

Niech będzie permutacją liczb zadaną tablicą o zakresie [0..n-1].
Liczbą inwersji jest liczba par takich że .
Na przkład mamy 15 inwersji w permutacji


Pomocniczą tablicą będzie , załóżmy że początkowo zawiera ona same zera.
Funkcja logiczna sprawdza czy liczba jest nieparzysta. Funkcja jest dzieleniem całkowitoliczbowym, pomijamy resztę.
Funkcja zwraca całkowitoliczbową część logarytmu przy podstawie 2, np. .

Końcową wartością zmiennej jest liczba inwersji permutacji P.

Algorytm Liczba-Inwersji (algorytm Ryttera)


1  ; 
2 repeat times
3 for to do
4 if then
5 else ;
6 for to do
7


Algorytm naiwny liczyłby wynik sprawdzając wszystkie pary , a więc w czasie kwadratowym.

Nasz algorytm liczy to w czasie . Złożoność jest oczywista, poprawność jest mniej oczywista.

Oznaczmy .
Poprawność algorytmu wynika z nastepujacego faktu:
dla każdych liczb naturalnych istnieje dokladnie jedna liczba naturalna k taka że

.


Funkcję dzielenia można łatwo wyeliminowac i pozostawić jedynie operacje arytmetyczne dodawania i odejmowania.


Przy okazji algorytmów sortowania można skonstruować kilka innych algorytmów dla tego samego probemu.
Możemy terza liczyć inwersję dla każdego ciągu elementów, niekoniecznie będącego permutacją.
Liczba zamian elementów w insertion-sort jest równa liczbie inwersji,
podobnie algorytm merge-sort możemy rozbudować tak aby liczył liczbę inwersji w czasie rzędu n log n.
Algorytmy inserion-sor, merge-sort poznamy w następnych modułach.
Ograniczymy się tutaj jedynie do algorytmu licznia inwersji między dwiema posortowanymi rosnąco tablicami .

W poniższym algorytmie zakładamy że tablice A, B są posortowane rosnąco.
Wynikiem jest liczba par taich,że .

Algorytm Inwersje-Między-AB


1  ; 
2 while do
3 if and then 5 else 6

Algorytm 10. Generacja permutacji

Niech będzie permutacją liczb 1,2,..n. Oznaczmy przez permutację identycznościową.
Operacja polega na rotacji cyklicznej pierwszych k elementów tablicy P: -ty element wędruje na początek. Na przykład:


Następujący algorytm generuje wszystkie permutacje, każdą dokladnie raz.
Operacja wypisuje w kolejnym wierszu tablicę P.


Algorytm Generacja-Permutacji


1  

2 while do
3
4 if 5 6 else 7


Algorytm ten ma następujacą ciekawą własność: jesli zdefiniujemy rotację jako operację odwrotna do tej którą mamy (pierwszy element wędruje
za -ty element) to algorytm w dalszym ciągu jest poprawny: wypisuje dokładnie raz każdą permutację.


Mozna rozwazyc jeszcze prostsza operacje zmiany jednej permutacji w druga: wymiana elementu na pozycji 1-szej z elementem na pozyci k-tej.
Pokazac ze mozna wygenerowac wszystkie permutacje stosujac za kazdym razem pojedyncza operacje takiej zamiany.
Jednakze ten algorytm ma musi miec zupelnie inna strukture.
Na przyklad dla ciag pozycji k moze byc nastepujacy: 2 3 2 3 2 4 3 2 3 2 3 4 2 3 2 3 2 4 3 2 3 2 3 .


Rozważmy podobny algorytm do algorytmu Generacja-Permutacji generowania podzbiorów k-elemntowych (kombinacji)
zbioru n-elementowego, każda konfiguracja jest ciągiem K zerojedynkowym mającym dokładnie k jedynek.
Inaczej mowiąc chcemy wygenerowąc każdy taki ciąg dokładnie raz. K jest jednocześnie traktowane jako ciąg i jako tablica n-elementowa.

Oznaczmy przez SzukajWzorzec(01,K) długośc najkrótszego prefiksu ciągu K kończącego się na 01. Na przykład SzukajWzorzec(01,111100001001) = 9.

Algorytm Generacja-kombinacji


1   
2 Załóżmy że

3 while do
4
5

Koszt zamortyzowany

Jeśli mamy ciąg operacji , to koszt zamortyzowany jednej z nich jest sumarycznym kosztem wykonania wszystkich operacji podzielonym przez liczbę operacji. Inaczej mówiąc jest to, dla danego ciągu operacji, "średni" koszt jednej z nich. Zauważmy, że nie mówimy tu nic o prawdopodobieństwie - model jest deterministyczny. Na przykład w algorytmie Najbliższy-Mniejszy-Sąsiad rozważmy ciąg operacji

: while

Koszt pojedynczej operacji może być liniowy, również sumaryczny koszt ciągu tych operacji jest liniowy. Zatem pesymistyczny koszt jednej operacji jest tutaj liniowy, natomiast zamortyzowany koszt jednej operacji jest ograniczony przez stałą. W tym przypadku wiemy, że każde sprawdzenie z wynikiem negatywnym odbywa się tylko raz dla danej wartości . Możemy powiedzieć, że księgujemy koszt operacji elementom o tej własności. Nieformalna metoda księgowania kosztów polega na rozdzielaniu (księgowaniu) kosztu, a następnie szacowaniu sumarycznej złożoności poprzez sumowanie wszystkich zaksięgowanych kosztów. Operacje pożyczają w pewnym sensie fundusze na pokrycie kosztów z różnych źródeł. Metoda ta będzie wykorzystana do analizy algorytmu dla interesującego problemu Find-Union.

Typowym przykładem liczenia kosztu w sposób zamortyzowany jest analiza generacji reprezentacji binarnych kolejnych liczb naturalnych od 0 do przez dodawanie jedynki. W jednym kroku zastępujemy najdłuższy ciąg jedynek od końca zerami, następnie wstawiamy jedną jedynkę. Ponieważ w sumie wstawiliśmy jedynek w ciągu operacji, to zamortyzowana liczba operacji zamiany zera na jedynkę wynosi 1.

Zasada magazynu. W ostatnim przykładzie możemy powiedzieć, że analizowaliśmy koszt tzw. metodą magazynu. W każdej operacji koszt jest proporcjonalny do liczby przedmiotów włożonych do magazynu lub do liczby przedmiotów wyjętych z magazynu. Magazyn początkowo jest pusty. Wtedy całkowity koszt jest proporcjonalny do liczby przedmiotów włożonych. W przypadku generowania liczb binarnych do magazynu wkładamy nowe jedynki, a wyjmujemy te jedynki, które zamieniamy na zera.

Potencjał - Fundusz Ubezpieczeń Kosztów Algorytmicznych

Metodę magazynu można uogólnić na tzw. metodę potencjału. Niech będzie pewną liczbą naturalną (włączając zero) odpowiadającą potencjałowi po wykonaniu -tej operacji. Wyglądałoby to mniej tajemniczo, gdybyśmy zamiast pisali .

Niech będzie rzeczywistym kosztem wykonania i-tej operacji.

Zakładamy, że potencjał jest początkowo zero, nigdy nie jest ujemny oraz że:

oraz .

Wtedy całkowity koszt jest tego samego rzędu co . W naszych poprzednich przykładach rozmiar magazynu jest w tym sensie potencjałem.

Można powiedzieć obrazowo, że potencjał jest kapitałem Funduszu Ubezpieczeń Kosztów Algorytmicznych. Jeśli wszystkie wpłaty są takie same, to koszt zamortyzowany jednej operacji jest wpłatą (składką), którą ta operacja wpłaca do funduszu.

Operacja najpierw wpłaca swoją składkę, a następnie pobiera z funduszu tyle, żeby proporcjonalnie (być może z dokładnością do stałego współczynnika) zapłacić za swój koszt wykonania.

Dzięki temu, że wiele operacji pobiera z funduszu znacznie mniej niż wpłaca, niektóre operacje mogą jednorazowo pobrać dużą kwotę, którą płacą za koszt wykonania. Istotne jest jedynie, żeby Fundusz nie zbankrutował i kapitał nie zszedł poniżej zera. Możliwa jest również sytuacja, gdy Fundusz startuje z kapitałem początkowym. Wtedy kapitał ten wlicza się do całkowitego kosztu algorytmu, który się dodaje do sumy składek.


Rozważmy przykłady ilustrujące wykorzystanie potencjału. Najistotniejsze jest określenie składek.

Tablica dynamiczna

Przypuśćmy, że mamy dynamiczną tablicę. W każdym momencie wiemy, ile elementów w tablicy jest aktywnych, elementy nieaktywne zaznaczamy. W każdej operacji, jeśli liczba elementów nieaktywnych jest mniejsza od wielkości tablicy, to tworzymy tablicę dwa razy mniejszą i tam przepisujemy elementy aktywne. Starą tablicę zwalniamy. W przeciwnym wypadku jeśli chcemy dodać element, który spowoduje przepełnienie tablicy, to całą tablicę kopiujemy do tablicy dwa razy większej. Początkowo tablica ma rozmiar 1. Zakładamy, że operacją dominującą jest kopiowanie aktywnego elementu do nowej tablicy. Jeśli mamy operacji, to całkowity koszt kopiowania jest liniowy. Wystarczy w każdej operacji dać składkę 4 jednostek do Funduszu (potencjału). Wtedy koszt jednej dużej operacji przepisywania zamortyzuje się zmianą potencjału.


Zastąpienie kolejki dwoma stosami

Jedną kolejkę Q można zastąpić dwoma stosami . Jeśli pierwszy element stosu lub kolejki w reprezentacji poziomej jest w ciągu na pierwszej pozycji (tzn. pobieramy , stawiamy za ), oraz , to dla pewnego mamy:

.

Inaczej mówiąc, pierwszy element kolejki jest na wierzchołku drugiego stosu, a ostatni element kolejki jest na wierzchołku pierwszego stosu.

Operacja wstawiania do Q odpowiada wstawieniu elementu do , operacja pobrania z Q odpowiada pobraniu elementu z S2 z tym, że jeśli jest pusty, to przepisujemy najpierw wszystkie elementy z S1 do S2. Niech operacją dominującą będzie jedna operacja stosowa (wstawienie lub pobranie pojedynczego elementu ze stosu). Wtedy ciąg operacji kolejkowych, startujących od pustej kolejki, ma koszt liniowy w tej implementacji. Wystarczy, że każda operacja wkłada do Funduszu składkę 3 jednostek. Dowód tego pozostawiamy jako ćwiczenie.

Zastąpienie kolejki dwustronnej trzema stosami

Rozważmy podobny problem - z tym, że nasza kolejka jest dwustronna, możemy wkładać i pobierać element z każdego z dwóch końców kolejki. Wtedy możemy taką kolejkę zastąpić trzema stosami tak, że teraz również każda operacja kolejkowa będzie mieć zamortyzowany koszt stały. Elementy kolejki trzymamy w dwóch stosach S1, S2 tak, jak poprzednio. Niezmiennikiem jest to, że oba stosy są niepuste, lub mają w sumie co najwyżej jeden element. Zapewniamy zachodzenie niezmiennika wykorzystując trzeci stos. W momencie, gdy jeden ze stosów ma więcej niż jeden element, a drugi jest pusty, korzystając z trzeciego stosu, doprowadzamy do reprezentacji aktualnej kolejki przez stosy S1 i S2 tak, aby miały one tę samą liczbę elementów (z dokładnością do 1). Pozostawiamy jako ćwiczenie dowód (metodą potencjału) tego, że zamortyzowany koszt jest stały.