Informatyka MIMUW

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 \( 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 Biało-czarne1

  while |S|> 1 do begin
    pobierz dwa przedmioty z S; 
    if przedmioty są różnego koloru then wstaw z powrotem czarny 
  end;
  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 \( n \) jest niezerowe.

Algorytm Biało-czarne2

  while   |S|> 1 do begin 
    pobierz dwa przedmioty z S; 
    if co najmniej jeden jest biały then wstaw z powrotem jeden biały; 
  end; 
  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

  while ((n <>4) and (n <> 1)) do
    n:= suma kwadratów cyfr liczby n;

Algorytm 6174

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

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 \( \frac{1}{q_i} \).

Rozkład Egipski jest postaci \( \hspace{0.4cm} \frac{p}{q}\ =\ \frac{1}{q_1}+\frac{1}{q_2}+\frac{1}{q_3}+\frac{1}{q_4}+\ldots , \hspace{0.4cm} \) gdzie \( q_1 < q_2 < q_3 < \ldots \) są liczbami naturalnymi:

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

\( 31/311\ =\ 1/12 + 1/63 + 1/2799 + 1/8708 \)

Niech \( DolnyEgipt(x) \) oznacza najwięszy ułamek Egipski (tzn. postaci \( \frac{1}{q} \)) nie przekraczający x.

Przykłady:
\( DolnyEgipt(2/3)=1/2,\ DolnyEgipt(4/5)=1/2,\ \)
\( DolnyEgipt(2/5)=1/3,\ DolnyEgipt(2/7)=1/4. \)

Niech \( 1\le p < q \) będą dwiema względnie pierwszymi liczbami naturalnymi. Następujący algorytm oblicza rozkład (niekoniecznie najkrótszy) nieskracalnego ułamka \( \frac{p}{q} \) na ułamki Egipskie.

Algorytm Rozkład-Egipski\( (p,q) \)

(algorytm Fibonacciego) 
  x:=p/q; 
  while (x>0) do
      y:=DolnyEgipt (x); output y; 
      x:=x-y;

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

Dla wejścia \( \frac{7}{15} \) otrzymamy jako wynik następujący ciąg ułamków Egispskich: \( \hspace{0.5cm} \frac{1}{3},\ \frac{1}{8},\ \frac{1}{120}. \)

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

Innym przykładem związanym z ułamkami jest następujący algorytm.
Mamy zbiór ułamków \(X\;=\; \{1/1,\; 1/2,\; 1/3,\; \ldots 1/100\}\).
dopóki zbiór ma co najmniej 2 elementy wykonaj
pobierz dwa różne elementy \(a,b\) z tego zbioru i włóż \(f(a,b)\).
return(ostatni jedyny element).

Jaki będzie wynik jeśli \(f(a,b)\,=\,ab/(a+b)\),
a jaki jeśli \(f(a,b)\,=\,ab+a+b.\) ?

W pierwszym przypadku niezmiennikiem jest wartość sumy odwrotności elementów zbioru X,
w drugim przypadku jeśli do odwrotności każdego elementu dodamy 1, to wartość iloczynu
otrzymanych liczb jest niezmiennikiem.

Rozpatrzmy jeszcze jeden ciekawy przykład związany z własnością stopu. Załóżmy, że mamy ciąg cykliczny liczb całkowitych zadany przez tablicę \(A[0..n-1]\), czyli pozycja \(0\) jest następną po pozycji \(n-1\)..
Nasz obecny algorytm jednocześnie dla każdej pozycji zmieniai jej wartość na wartość różnicy między wartością na danej pozycji i cyklicznie następnej. Pytamy się dla jakich \( n\) algorytm ten zatrzymuje się dla każdych danych całkowitoliczbowych w tablicy długości \(n+1\).

Algorytm Ciąg-cykliczny

 while ciąg nie składa się z samych zer do
  pom:= A[0]
  for i=0 to n-2 
    A[i]:=|A[i]-A[i+1|
  A[n-1]:=|A[n-1]-pom|

Pierwsze trzy algorytmy mają własność stopu. W pierwszym łatwo to sprawdzić, gdyż dla \( n>100 \) 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). Algorytm Ciąg-cykliczny, pomimo swojej prostoty, ma nietrywialą własność stopu (dla ciągu o długości będącej potęgą dwójki).

Następny algorytm jest bardziej abstrakcyjny. Pochodzi on od Collatza (jak również od polskiego matematyka Ulama).

Algorytm Collatza

 while n \neq 1 do
    if    n parzyste then n := n div 2; else n := 3*n+1;

Algorytm Collatza jest bardzo zagadkowy. Nie wiadomo, czy dla każdej dodatniej liczby całkowitej \( n \) ma on własność stopu. Problem ten postawił L. Collatz w roku 1937, wiadomo, że własność stopu zachodzi dla każdego \( 1 \le n \le 10^{16} \).

Rozważmy jeszcze jeden bardzo dziwny algorytm. Niech \(x^R\) oznacza wartość liczby będącej odwróceniem zapisu dziesiętnego liczby x, np \(12^R=21\).

Algorytm Dziwny

 while x <> x^R do
    x := x+x^R;

Algorytm Dziwny jest również zagadkowy. Nie wiadomo, czy dla każdej dodatniej liczby całkowitej \( n \) ma on własność stopu W szczególności najciekawszy jest przypadek liczby 196.

Jeśli zamiast zapisu dziesiętnego weźmiemy binarny to algorytm nie zawsze ma własność stopu, np. dla liczby 22 zapisanej binarnie nigdy sie nie zatrzyma. W tym przypadku co kilka iteracji otrzymamy liczbę (zapisaną binarnie) typu \(10 1^k 01 0^k \) dla coraz większych k.

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 \( A[1..n] \) względem elementu \( x \). Dla zbiorów pozycji \( X,Y \) tablicy \( A \) piszemy \( X < Y \) gdy każda pozycja w X jest mniejsza od każdej pozycji w \( Y \). Piszemy \( A[X] < a \) 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 \( \alpha(M,R,W) \) (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ę

  M:= ∅; R:= ∅; W:= ∅; 
  while |M|+|R|+|W| <n do 
    zwiększ o jeden sumę |M|+|R|+|W| zachowując niezmiennik alpha(M,R,W,x) 
    w czasie i dodatkowej pamięci  O(1)

Algorytm ten jest silnikiem algorytmu QuickSort, który jest praktycznie najszybszym algorytmem sortowania.

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 \( x < y \). Teraz zamiast dwóch segmentów M, R, W tablicy A mamy pięć zbiorów pozycji, a niezmiennik zamienia się na

\( Z1 < Z2 < Z3 < Z4 < Z5,\ A[Z1] < x,\ A[Z2]=x, \)

\( x < A[Z3] < y,\ A[Z4]=y,\ A[Z5]>y. \)