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

Wersja z 16:43, 24 wrz 2006

Podstawowym elementem przy rozwiązywaniu zadanego problemu na komputerze jest dobór algorytmu i struktury danych. Najważniejszymi aspektami algorytmu są jego "poprawność" i złożoność. Zasadniczo rozpatrywać będziemy tylko złożoność czasową i pamięciową.

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 (mniejsze, równe, mniejsze ???), 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. Z reguły będziemy przyjmować, że każda operacja arytmetyczna na małych liczbach daje się zrobić w jednym kroku. Przez małe rozumiemy liczby mające $O (\log n)$ bitów. Z reguły określamy pewien parametr $n$ , będący rozmiarem problemu wejściowego i określamy złożoność jako funkcję $T (n)$ , której argumentem jest rozmiar problemu.

Przeważnie rozważamy złożoność pesymistyczną - maksymalną złożoność dla danych tego samego rozmiaru $n$ . W praktyce ważniejszą może się okazać złożoność średnia, lub oczekiwana, w tym przypadku $T (n)$ jest średnią (oczekiwaną) wartością złożoności dla wszystkich problemów rozmiaru $n$ . 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 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 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 $n$ sprawdzeń, jest to maksymalna liczba, zatem złożoność pesymistyczna wynosi $T (n) = n$ . 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: $f (n) = O (g (n))$ oznacza, że $f (n) \leq c \cdot g (n)$ dla pewnej stałej $n$ . Gdy $g (n) = n$ , to mówimy, że $f (n)$ jest liniowa, oraz dla $g (n) = n^{2}$ mówimy, że złożoność $f (n)$ jest kwadratowa. Jeśli $g (n)$ jest wielomianem, to wtedy mówimy o złożoności wielomianowej.

Będziemy używać dodatkowych notacji:

$f (n) = Θ (g (n)), f (n) = Ω (n)$ . Były one wprowadzone na wykładach z matematyki dyskretnej.

Dla przypomnienia:

$f (n) = Θ (g (n)) \Leftrightarrow f (n) = O (g (n))$ & $g (n) = O (f (n))$

$f (n) = Ω (g (n))$ , gdy dla nieskończenie wielu $n$ i pewnej stałej $c > 0$ zachodzi $f (n) \geq c \cdot g (n)$

Przykład

$\frac{1}{100} \cdot n^{2} - 2 n = Θ (n^{2}) \cdot n^{5} + 2^{n} = Θ (2^{n}), n! = Ω (1 0^{n})$ ,
Jeśli $f (n) = (1 + (- 1)^{n}) \cdot n$ , to $f (n) = Ω (n), f (n) = O (n)$ , ale nie

zachodzi

f (n) = Θ (n)

.

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ć to, ż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 C-podobnym.

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ść.

Pojęcie niezmiennika

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

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

Algorytm

1 while   $| S | > 1$ 
2    pobierz dwa przedmioty z S;
3    if przedmioty są różnego koloru to wstaw z powrotem czarny
4 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 na wyjściu mamy kolor czarny.

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

Algorytm

1 while   $| S | > 1$ 
2    pobierz dwa przedmioty z S;
3    if co najmniej jeden jest biały, to wstaw z powrotem jeden biały;
4 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

Podstawowym elementem poprawności algorytmu jest to, że ma on własność stopu: dla poprawnych danych wejściowych da odpowiedź po skończonym czasie. Na przykładzie dwóch prostych 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
 1  while  ((n <>4)  and  (n<> 1))
 2   $n : =$  suma kwadratów cyfr liczby  $n$ ;

Algorytm 6174

wejściem jest czterocyfrowa liczba naturalna niepodzielna przez 1111
pierwszymi cyframi mogą być zera
while (n<>6174)
    $n 1 : =$   największa liczba czterocyfrowa, której cyfry są permutacją cyfr liczby n;
    $n 2 : =$  najmniejsza liczba czterocyfrowa, której  cyfry są permutacją cyfr liczby n;
    $n : =$ n1 - n2;

Algorytm X

while (n<>1)
   if n parzyste  $n : =$  n div 2; else  $n : =$ 3*n+1;

Pierwsze dwa algorytmy mają własność stopu, w pierwszym łatwo to sprawdzić, gdyż dla $n > 100$ następna wartość jest istotnie mniejsza.

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

Algorytm X jest dosyć zagadkowy, nie wiadomo, czy dla dowolnego naturalnego dodatniego $n$ ma on własność stopu.

Złożoność algorytmów: analiza siedmiu prostych algorytmów

Na przykładzie siedmiu prostych algorytmów pokażemy, jak się analizuje i osiąga złożoność liniową. Po dokładniejsze uzasadnienia i analizy odsyłamy do ćwiczeń. Naiwne wersje tych algorytmów działają w czasie kwadratowym (Wybraliśmy "siedem" losowo, na przykład jest siedem dni w tygodniu ,był taki film pt. Siedmiu wspaniałych itp.)

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 tablicą $A [1 . . n]$ . Dla uproszczenia przyjmijmy, że w tym ciągu jest przywódca. Łatwo można modyfikować algorytm, by sprawdzał istnienie przywódcy.

Algorytm Liczenie-Przywódcy

  $i l e : = 0$ ;
   for i  $: =$  1 to n do
      if  $(i l e = 0) {i l e : = i l e + 1; j : = i}$ ;
      else if  $(A [i] = A [j])$    $i l e : = i l e + 1;$  else
        $i l e : = i l e - 1$ ;

   return  $A [j]$ ;

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ł on słabego przywódcę: element, który występuje w tablicy więcej niż n/5 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ść O(n log n). 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 zaznacza się licznik słabego przywódcy, jego nazwa jest w niebieskim kwadraciku.

====Szukanie sumy==== Mamy dane dwie posortowane rosnąco tablice $A, B$ i liczbę x,pytamy czy są $a \in A, b \in B$ takie, że $x = a + b$ .

Algorytm Szukanie Sumy

 Szukanie Sumy
    $i : = 1; j : = n;$ 
   while  $(i < = n$   and  $j > 0)$ 
      if  $(A [i] + B [j] = x)$ return true; else
      if  $(A [i] + B [j] < x) i : = i + 1;$ else  $j : = j - 1$ ;
   return false;

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

==== Maksymalny segment ==== Dla tablicy $A [1 . . n]$ liczymy maksymalną wartość z zera i ze wszystkich liczb $\sum_{k = i}^{j} A [k]$ , gdzie $1 \leq i \leq j \leq n$ .

Algorytm Maksymalny-Segment;

   wynik := 0; sufiks := 0;
   for i := 1 to n do
      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 $[1 . . i]$ oraz sufiks jest maksymalną sumą segmentu który jest sufiksem przedziału $[1 . . i]$ .

Najbliższy mniejszy sąsiad z lewej strony

Dla każdego $i > 1$ zdefiniujmy najbliższego mniejszego sąsiada $i$ jako: $L e w y [i] = m a x {j < i : A [j] < A [i]}$ Dla uproszczenia zakładamy, że $A [i] > 0$ dla $i > 0$ oraz $A [0] = 0$ .

Algorytm Najbliższy-Mniejszy-Sąsiad

Najbliższy Mniejszy Sąsiad
for  $i : = 1$  to n do
  $j : = i - 1;$ 
   while  $(A [j] > = A [i]) j : = L e w y [j];$ 
       $L e w y [i] : = j;$

Przyspieszenie następuje dzięki temu, że nie ma potrzeby sprawdzania tablicy dla indeksów istotnie wewnątrz przedziału $[[L e w y [i - 1] . . . (i - 1)]$ . Niech $k_{i}$ będzie liczbą tych $j$ , dla których $A [j] > = A [i]$ . Wystarczy pokazać, że suma wszystkich $k_{i}$ jest liniowa. Może się zdarzyć, że niektóre $k_{i}$ mają wartość liniową. Zauważmy jednak, że dany indeks $j$ pojawia się co najwyżej raz w sytuacji, gdy $A [j] > = A [i]$ , potem będzie "przeskoczony".

Najdłuższy malejący podciąg

Niech $A [1], A [2], \dots A [n]$ będzie ciągiem dodatnich liczb. Następujący algorytm oblicza długość najdłuższgo malejącego podciągu.

Algorytm Najdłuższy-Malejący

Najdłuższy-Malejący
 $w y n i k : = 1;$ 
for  $i : = 1$  to n do
    $x : = A [i]; A [i] : = 0;$ 
    $k : = m i n {j : x > A [j]};$  
    $A [k] : = x;$ 
    $w y n i k : = m a x (k, w y n i k);$

Algorytm może, po niewielkim dodatkowym wysiłku fizycznym 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 k, gdzie k jest wynikiem powyższego algorytmu. Jak również możemy się zastanowić nad efektywnym algorytmem znajdowania liczby wszystkich takich ciągów długości k.

Proste Pakowanie

Załóżmy, że mamy n pudełek, każde o rozmiarze R, oraz n przedmiotów o rozmiarach $R \geq r [1] \geq r [2] \dots \geq r [n]$ . 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

 $w y n i k : = n;$ 
for  $i : = 1$  to n do
   if  $(i < w y n i k$   and  $r [i] + r [w y n i k] < = R)$ 
       $w y n i k : = w y n i k - 1;$

<flash>file=Klocki.swf|width=450|height=250</flash>

Naiwne wersje powyższych sześciu algorytmów działają w czasie kwadratowym. W każdym z tych 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

Przypuśćmy, że mamy wagę szalkową, początkowo obie szalki sa puste, oraz mamy odważniki o numerach 1,2,..n. Waga i-tego odważnika wynosi $a_{i}$ . Dla danej permutacji $Π$ numerów odważników będziemy je wkładać na wagę zgodnie z permutacją. Kładziemy kolejno odważniki w kolejności $Π$ 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 $Π$ 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ę $Π$ 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 $2^{n}$ , co jest liczbą znacznie mniejszą.
Następujący algorytm znajduje pewną permutację zgodną. Zakładamy, że

a_{1} < a_{2} < a_{3} < \dots a_{n}

Algorytm Permutacja-Wagowa

    $p : = 1; q : = n;$ 
   for   $i : = n$  downto  $1$  do
      if  $(i > 1) and (I n p u t [i - 1] \neq I n p u t [i])$ )
         $W y n i k [i] : = q; q : = q - 1;$ 
      else  
           $W y n i k [i] : = p; p : = p + 1$ ;

Jeśli Input = [+1,+1,+1,-1,-1,-1,+1,+1,-1], to Wynik = [6 5 4 7 3 2 8 1 9]. Ciąg Input jest zrealizowany przez następujący ciąg wyborów wkładania kolejnego odważnika:

L P L P P L L P P

,

gdzie L oznacza połóż na lewą szalkę, P na prawą. Korzystając (tylko częściowo) z dialeku C++, możemy zapisać algorytm krócej

Algorytm Permutacja-Wagowa1

    $p : = 1; q : = n;$ 
   for   $i : = n$  downto  $1$  do
      if  $(i > 1) and (I n p u t [i - 1] \neq I n p u t [i])$ )
         $W y n i k [i] : = q - -$ ; else   $W y n i k [i] : = p + +$ ;

Wynik algorytmu pozostawia pewien niedosyt. Generujemy dobry wynik, ale w pewnym sensie jakikolwiek dobry. Nie jest jasne, jak policzyć efektywnie liczbę wszystkich permutacji zgodnych z danym ciągiem wyników, albo znaleźć jakąś szczególną permutację, np. leksykograficznie pierwszą lub ostatnią. Co będzie jeśli tablica Input zawiera również zera (wagi szalek są równe). Wtedy nie każdy ciąg Input jest realizowalny. Jak to można efektywnie sprawdzać?

Koszt zamortyzowany

Jeśli mamy ciąg operacji $o p_{1}, o p_{2}, \dots, o p_{n}$ , 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

$o p_{i}$ : while $(A [j] > = A [i]) j = L e w y [j]$

Koszt pojedyńczej operacji może być liniowy, również sumaryczny koszt ciągu tych operacji $o p_{1}, o p_{2}, \dots, o p_{n}$ 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 $A [j] > = A [i])$ z wynikiem negatywnym odbywa się tylko raz dla danej wartości $j$ . Możemy powiedzieć, że księgujemy koszt operacji elementom $j$

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 kolejnych reprezentacji binarnych kolejnych liczb naturalnych od 0 do $2^{n} - 1$ , dodając jedynkę. 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 $2^{n} - 1$ jedynek w ciągu $2^{n} - 1$ 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 $Φ_{i}$ będzie pewną liczbą naturalną (włączając zero) odpowiadającą potencjałowi po wykonaniu $i$ operacji. (Wyglądałoby to mniej tajemniczo, gdybyśmy zamiast $Φ (i)$ pisali Bilans(i).

Niech $k o s z t (i)$ będzie kosztem wykonania operacji i-tej.

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

Φ_{i} = Φ_{i - 1} + w p l a t a (i) - w y p l a t a (i)

oraz

k o s z t (i) \leq w y p l a t a (i)

.

Wtedy całkowity koszt jest tego samego rzędu co $\sum w p l a t a (i)$ . 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. Operacje ubezpieczają się od kosztów ich wykonania. Poszczególne operacje płacą drobne składki $w p l a t a (i)$ , 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 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 $\frac{1}{4}$ 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 $n$ 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 $S 1, S 2$ . Jeśli pierwszy element stosu lub kolejki w reprezentacji poziomej jest w ciągu na pierwszej pozycji (tzn. pobieramy $e_{1}$ , stawiamy za $e_{n}$ ), oraz $Q = (e_{1}, e_{2}, . ., e_{k})$ , to dla pewnego $j$ mamy:

$S 1 = (e_{n}, e_{n - 1}, . . ., e_{j}), S 2 = (e_{1}, e_{2}, . . ., e_{j - 1})$ .

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

Operacja wstawiania do A odpowiada wstawieniu elementu do $S 1$ , operacja pobrania z Q odpowiada pobraniu elementu z S2 z tym, że jeśli $S 2$ 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 $n$ 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

Roważ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. Plik:Example.jpg

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

Wersja z 16:43, 24 wrz 2006

Spis treści

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

Pojęcie niezmiennika

Własność stopu

Złożoność algorytmów: analiza siedmiu prostych algorytmów

Przywódca ciągu

Najbliższy mniejszy sąsiad z lewej strony

Najdłuższy malejący podciąg

Proste Pakowanie

Permutacje wagowe

Koszt zamortyzowany

Potencjał - Fundusz Ubezpieczeń Kosztów Algorytmicznych

Tablica dynamiczna

Zastąpienie kolejki dwoma stosami

Zastąpienie kolejki dwustronnej trzema stosami

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia

@@ Linia 3: / Linia 3: @@
 Podstawowym elementem przy rozwiązywaniu zadanego problemu na komputerze 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ść.
-Będziemy zasadniczo rozpatrywać tylko złożoność czasową i pamięciową.
+Zasadniczo rozpatrywać będziemy 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.
 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 (mniejsze,
-równe, mniejsze), a w przypadku przeglądania drzewa jedno przejście w drzewie między
+równe, mniejsze <font color=red>???</font>), 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. Z reguły będziemy przyjmować, że każda operacja arytmetyczna ''na małych liczbach'' daje się
+symboli. Z reguły będziemy przyjmować, że każda operacja arytmetyczna na małych liczbach daje się
-zrobić w jednym kroku.  Z reguły określamy pewien parametr <math>n</math>, będący rozmiarem problemu wejściowego i
+zrobić w jednym kroku. Przez małe rozumiemy liczby mające <math>O(\log n)</math> bitów.  Z
-określamy złożoność jako funkcję <math>T(n)</math>, której argumentem jest rozmiar problemu. Przez ''małe'' rozumiemy
+reguły określamy pewien parametr <math>n</math>, będący rozmiarem problemu wejściowego i
-liczby mające <math>O(\log n)</math> bitów.
+określamy złożoność jako funkcję <math>T(n)</math>, której argumentem jest rozmiar problemu.
 Przeważnie rozważamy złożoność pesymistyczną - maksymalną złożoność dla danych tego samego
 rozmiaru <math>n</math>.
-W praktyce ważniejszą może się okazać złożoność średnią, lub oczekiwaną, w tym przypadku
+W praktyce ważniejszą 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
 rozmiaru <math>n</math>. Tego typu złożoność zależy  istotnie od tego, jaka się pod tym kryje
@@ Linia 33: / Linia 33: @@
 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>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łą.
 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>n</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
-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.
@@ Linia 47: / Linia 47: @@
 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.
@@ Linia 58: / Linia 57: @@
 <br>
-<math>f(n)=\Omega(g(n)) \Leftrightarrow g(n) = O(f(n))</math>
+<math>f(n)=\Omega(g(n)) \,</math>, gdy  dla nieskończenie wielu <math>n</math> i pewnej stałej
+<math>c>0</math> zachodzi  <math>f(n) \ge c\cdot g(n)</math>
 {{przyklad|||
-<math>\frac{1}{100}\cdot n^2- 2n = \Theta(n^2),  n^5+2^n = \Theta(2^n),
+<math>\frac{1}{100}\cdot n^2- 2n = \Theta(n^2 )\cdot n^5+2^n = \Theta(2^n),
-n!=\Omega(10^n)</math>.
+n!=\Omega(10^n)</math>,<br>
-}}<br>
+Jeśli <math>f(n)=(1+(-1)^n)\cdot n</math>, to <math>f(n)=\Omega(n),\ f(n)=O(n)</math>, ale nie
+zachodzi <math>f(n)=\Theta(n)\,</math>.}}
-'''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
-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
-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ć to, że "prosty" algorytm
 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 C-podobnym.
 == 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ść.
 === Pojęcie niezmiennika ===
@@ Linia 94: / Linia 98: @@
 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
@@ Linia 105: / Linia 109: @@
 '''while'''  <math>|S|> 1</math>
     pobierz dwa przedmioty z S;
-    '''if''' co najmniej jeden jest biały to wstaw z powrotem jeden biały;
+    '''if''' co najmniej jeden jest biały, to wstaw z powrotem jeden biały;
 '''return''' kolor ostatniego przedmiotu w S.
 }}
@@ Linia 111: / Linia 115: @@
 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
+(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.
@@ Linia 130: / Linia 134: @@
   pierwszymi cyframi mogą być zera
   '''while''' (n<>6174)
-     <math>n1 :=</math>  największa liczba czterocyfrowa której cyfry są permutacją cyfr liczby n;
+     <math>n1 :=</math>  największa liczba czterocyfrowa, której cyfry są permutacją cyfr liczby n;
-     <math>n2 :=</math> najmniejsza liczba czterocyfrowa której  cyfry są permutacją cyfr liczby n;
+     <math>n2 :=</math> najmniejsza liczba czterocyfrowa, której  cyfry są permutacją cyfr liczby n;
      <math>n := </math>n1 - n2;
 }}
@@ Linia 139: / Linia 143: @@
 }}
-Pierwsze dwa algorytmy mają własność stopu, w pierwszym łatwo to sprawdzić gdyż dla
+Pierwsze dwa algorytmy mają własność stopu, w pierwszym łatwo to sprawdzić, gdyż dla
 <math>n>100</math> następna wartość jest istotnie mniejsza.
@@ Linia 153: / Linia 157: @@
 Na przykładzie siedmiu prostych algorytmów pokażemy, jak się analizuje i osiąga złożoność liniową.
 Po dokładniejsze uzasadnienia i analizy odsyłamy do ćwiczeń.  Naiwne wersje tych algorytmów
-działają w czasie kwadratowym.
+działają w czasie kwadratowym (Wybraliśmy ''"siedem"'' losowo, na przykład jest ''siedem'' dni w
+tygodniu ,był taki film pt. ''Siedmiu wspaniałych'' itp.)
 ==== 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 wyznaczenie przywódcy ciągu danego tablicą <math>A[1..n]</math>. Dla
+Naszym problemem jest policzenie przywódcy ciągu danego tablicą <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 można modyfikować algorytm, by
 sprawdzał istnienie przywódcy.
@@ Linia 169: / Linia 174: @@
      '''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.
-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ł on słabego przywódcę: element,
 który występuje w tablicy więcej niż n/5 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
+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.
-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ść O(n log n). Podamy potem
 również rozwiązanie metodą "dziel i zwyciężaj".
@@ Linia 237: / Linia 242: @@
 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ą
-tych <math>j</math> dla których <math>A[j]>=A[i]</math>. Wystarczy
+tych <math>j</math>, dla których <math>A[j]>=A[i]</math>. Wystarczy
 pokazać, że suma wszystkich <math>k_i</math> jest liniowa. Może się zdarzyć, że niektóre
 <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>,
 potem będzie "przeskoczony".
@@ Linia 246: / Linia 251: @@
 ==== 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
-oblicza długość najdłuższego  malejącego podciągu.
+oblicza długość najdłuższgo  malejącego podciągu.
 {{algorytm|Najdłuższy-Malejący|algorytm_najdluzszy_malejacy|
   Najdłuższy-Malejący
@@ Linia 258: / Linia 263: @@
-Algorytm może, przy niewielkim dodatkowym  wysiłku, podać najdłuższy malejący
+Algorytm może, po niewielkim dodatkowym  wysiłku fizycznym 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 k, gdzie
-k jest wynikiem powyższego algorytmu. Możemy się również zastanowić nad efektywnym
+k jest wynikiem powyższego algorytmu. Jak również możemy się zastanowić nad efektywnym
 algorytmem znajdowania liczby wszystkich takich ciągów długości k.
@@ Linia 281: / Linia 286: @@
 Naiwne wersje powyższych sześciu algorytmów  działają w czasie kwadratowym. W każdym z tych
-algorytmów bardzo proste spostrzeżenia prowadzą do algorytmów liniowych lub prawie liniowych
+algorytmów bardzo proste spostrzeżenia prowadzą do algorytmów liniowych.
-(z dokladnoscia do wspolczynnika logarytmicznego).
 Podamy jeszcze jeden bardzo krótki ciekawy algorytm (chociaż bez żadnego widocznego
 zastosowania praktycznego).
@@ Linia 294: / Linia 298: @@
 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.
+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ą
+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ć
@@ Linia 304: / Linia 308: @@
 liczbą znacznie mniejszą. <br>
 Następujący algorytm znajduje pewną permutację zgodną.
-Zakładamy że
+Zakładamy, że
   <center> <math> a_1<a_2<a_3<\ldots a_n</math></center>
@@ Linia 319: / Linia 323: @@
 Jeśli Input = [+1,+1,+1,-1,-1,-1,+1,+1,-1], to Wynik = [6 5 4 7 3 2 8 1 9].
 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>
+<center>  L  P  L  P  P  L  L  P  P </center>,
 gdzie L oznacza połóż na lewą szalkę, P na prawą.
+Korzystając (tylko częściowo) z dialeku C++, możemy zapisać algorytm krócej
-Wynik algorytmu pozostawia pewien niedosyt: generujemy dobry wynik ale
+{{algorytm|Permutacja-Wagowa1|algorytm_permutacja_wagowa|
+    <math> p:=1; q:=n;</math>
+    '''for'''  <math>i:=n  </math> '''downto''' <math>1</math> '''do'''
+       '''if''' <math>(i>1)\ \textrm{and}\   (Input[i-1] \ne Input[i])</math>)
+         <math> Wynik[i]:= q-- </math>; '''else ''' <math> Wynik[i] := p++ </math>;
+}}
+Wynik algorytmu pozostawia pewien niedosyt. Generujemy dobry wynik, ale
 w pewnym sensie jakikolwiek dobry. Nie jest jasne, jak policzyć efektywnie liczbę wszystkich
 permutacji zgodnych z danym ciągiem wyników, albo
-znależć jakąś szczególną permutację, np. leksykograficznie pierwszą lub ostatnią.
+znaleźć jakąś szczególną permutację, np. leksykograficznie pierwszą lub ostatnią.
-Co będzie, jeśli tablica Input zawiera również zera (wagi szalek są równe)? Wtedy nie każdy ciąg Input
+Co będzie jeśli tablica Input zawiera również zera (wagi szalek są równe). Wtedy nie każdy ciąg Input
-jest realizowalny.  Jak można by to efektywnie sprawdzać?
+jest realizowalny.  Jak to można efektywnie sprawdzać?
 == Koszt zamortyzowany ==
-Jeśli mamy ciąg operacji <math>op_1,op_2,\ldots, op_n</math> to koszt zamortyzowany jednej z
+Jeśli mamy ciąg operacji <math>op_1,op_2,\ldots, op_n</math>, 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ó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
@@ Linia 385: / Linia 398: @@
 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>
@@ Linia 394: / Linia 407: @@
 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
 ubezpieczają się od kosztów ich
-wykonani. Poszczególne operacje płacą drobne składki <math>wplata(i)</math>, a swój koszt za każdym
+wykonania. 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.
+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
+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
+koszt pokryć. Istotne jest jedynie,
-żeby Fundusz nie zbankrutował i kapitał nie zszedł poniżej zera. Możliwa jest również sytuacja gdy
+ż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
@@ Linia 411: / Linia 424: @@
-Rozważmy  przykłady ilustrujące wykorzystanie potencjału. Najistotniejsze jest określenie 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. 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.
 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
 Funduszu (potencjału).
 Wtedy koszt jednej dużej operacji przepisywania  zamortyzuje się zmianą potencjału.
 ==== Zastąpienie kolejki dwoma stosami====
@@ Linia 431: / Linia 446: @@
 lub kolejki w
 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:
 <math>S1 = (e_n,e_{n-1},...,e_j),\ S2 = (e_{1},e_{2}, ...,e_{j-1})</math>.
-Inaczej mówiąc, pierwszy element kolejki jest na wierzchołku drugiego stosu, a
+Inaczej mówiąc pierwszy element kolejki jest na wierzchołku drugiego stosu, a
-ostatni element kolejki jest na wierzchołku pierwszego stosu.
+ostatni lement kolejki jest na wierzchołku pierwszego stosu.
 Operacja wstawiania do A odpowiada wstawieniu elementu do <math>S1</math>, operacja pobrania
 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ą
 będzie jedna operacja stosowa (wstawienie lub pobranie pojedynczego elementu ze stosu). Wtedy ciąg
 <math>n</math> operacji
-kolejkowych, startujących od pustej kolejki, ma koszt liniowy w tej implementacji. Wystarczy, że
+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====
-Roważmy podobny problem, z tym że nasza kolejka jest dwustronna: możemy wkładać i pobierać
+Roważ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
+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
 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)
 tego, że zamortyzowany koszt jest stały.
+[[Grafika:Example.jpg]]