Jak opisywać algorytmy, je udowadniać i analizować?

Przed przeczytaniem „Sztuki programowania komputerowego” (TAOCP) nie zastanawiałem się głęboko nad tymi pytaniami. Używałbym pseudokodu do opisywania algorytmów, rozumienia ich i szacowania czasu działania tylko o rzędach wzrostu. TAOCP gruntownie zmienia zdanie.

TAOCP używa angielskiego mieszanego z krokami i goto do opisywania algorytmu, i wykorzystuje schematy blokowe do łatwiejszego zobrazowania algorytmu. Wygląda na niski poziom, ale uważam, że są pewne zalety, szczególnie w przypadku schematu blokowego, który bardzo często ignorowałem. Każdą ze strzałek możemy oznaczyć twierdzeniem o aktualnym stanie rzeczy w chwili, gdy obliczenia przechodzą przez tę strzałkę, i wykonać indukcyjny dowód na algorytm. Autor mówi:

Twierdzeniem autora jest to, że naprawdę rozumiemy, dlaczego algorytm jest ważny tylko wtedy, gdy osiągniemy punkt, w którym nasze umysły pośrednio wypełniły wszystkie twierdzenia, jak to pokazano na ryc. 4.

Nie doświadczyłem takich rzeczy. Kolejną zaletą jest to, że możemy policzyć, ile razy każdy krok jest wykonywany. Łatwo jest sprawdzić pierwsze prawo Kirchhoffa. Nie analizowałem dokładnie czasu działania, więc niektóre $\pm1$ mogło zostać pominięte, gdy szacowałem czas działania.

Analiza rzędów wzrostu jest czasami bezużyteczna. Na przykład nie możemy odróżnić quicksort od heapsort, ponieważ wszystkie są , gdzie E X jest oczekiwaną liczbą zmiennych losowych X , dlatego powinniśmy przeanalizować stałą, powiedzmy E ( T 1 ( n ) ) = A 1 n lg n + B 1 n + O ( log n $E(T(n))=\Theta(n\log n)$$EX$$X$$E(T_1(n))=A_1n\lg n+B_1n+O(\log n)$i $E(T_2(n))=A_2\lg n+B_2n+O(\log n)$ , dzięki czemu możemy lepiej porównać $T_1$ i $T_2$ . A także czasami powinniśmy porównywać inne wielkości, takie jak wariancje. Tylko zgrubna analiza rzędów wzrostu czasu pracy nie wystarczy. Jako TAOCP tłumaczy algorytmy na język asemblerowy i oblicza czas działania, To dla mnie zbyt trudne, więc chcę poznać niektóre techniki bardziej szczegółowej analizy czasu działania, co jest również przydatne, w przypadku języków wyższego poziomu, takich jak C, C ++ lub pseudokody.

I chcę wiedzieć, jaki styl opisu jest używany głównie w pracach badawczych i jak leczyć te problemy.

Istnieje ogromna różnorodność wykonalnych podejść. To, co najlepiej pasuje, zależy od

• co próbujesz pokazać,
• ile szczegółów chcesz lub potrzebujesz.

Jeśli algorytm jest powszechnie znany, którego używasz jako podprogramu, często pozostajesz na wyższym poziomie. Jeśli algorytm jest głównym przedmiotem badań, prawdopodobnie chcesz być bardziej szczegółowy. To samo można powiedzieć o analizach: jeśli potrzebujesz z grubsza górnej granicy czasu wykonywania, postępujesz inaczej niż wtedy, gdy chcesz precyzyjnej liczby instrukcji.

Podam trzy przykłady dobrze znanego algorytmu Mergesort, które, mam nadzieję, ilustrują to.

Wysoki poziom

Algorytm Mergesort pobiera listę, dzieli ją na dwie (mniej więcej) jednakowo długie części, powtarza się na tych listach częściowych i łączy (posortowane) wyniki, aby posortować wynik końcowy. W przypadku pojedynczych lub pustych list zwraca dane wejściowe.

$\Theta(n)$$T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n)$$T(n) \in \Theta(n\log n)$

Średni poziom

Algorytm Mergesort podaje następujący pseudo-kod:

procedure mergesort(l : List) {
  if ( l.length < 2 ) {
    return l
  }

  left  = mergesort(l.take(l.length / 2)
  right = mergesort(l.drop(l.length / 2)
  result = []

  while ( left.length > 0 || right.length > 0 ) {
    if ( right.length == 0 || (left.length > 0 && left.head <= right.head) ) {
      result = left.head :: result
      left = left.tail
    }
    else {
      result = right.head :: result
      right = right.tail
    }
  }

  return result.reverse
}

mergesort$n$$n>1$$L$$n+1$leftright$L$whileresultresultleftright$L$

$n>1$whilereverse$n$while$n$reverse$2n$operacje na liście - każdy element jest usuwany z wejścia i umieszczany na liście wyników. Dlatego liczba operacji spełnia następującą cykliczność:

$\qquad \begin{align}T(0) = T(1) &= 0 \\ T(n) &\leq T\left(\left\lceil\frac{n}{2}\right\rceil\right) + T\left(\left\lfloor\frac{n}{2}\right\rfloor\right) + 7n\end{align}$

$T$$n=2^k$

$\qquad \begin{align}T(0) = T(1) &= 0 \\ T(n) &\leq 2T\left(\frac{n}{2}\right) + 7n\end{align}$

$T \in \Theta(n \log n)$mergesort

Ultra niski poziom

Rozważ to (ogólne) wdrożenie Mergesort w Isabelle / HOL :

types dataset  =  "nat * string"

fun leq :: "dataset \<Rightarrow> dataset \<Rightarrow> bool" where
   "leq (kx::nat, dx) (ky, dy) = (kx \<le> ky)"

fun merge :: "dataset list \<Rightarrow> dataset list \<Rightarrow> dataset list" where
"merge [] b = b" |
"merge a [] = a" |
"merge (a # as) (b # bs) = (if leq a b then a # merge as (b # bs) else b # merge (a # as) bs)"

function (sequential) msort :: "dataset list \<Rightarrow> dataset list" where
  "msort []  = []" |
  "msort [x] = [x]" |
  "msort l   = (let mid = length l div 2 in merge (msort (take mid l)) (msort (drop mid l)))"
by pat_completeness auto
  termination
  apply (relation "measure length")
by simp+

Obejmuje to już dowody dobrego zdefiniowania i rozwiązania umowy. Znajdź (prawie) kompletny dowód poprawności tutaj .

W przypadku „środowiska wykonawczego”, czyli liczby porównań, można ustawić powtarzalność podobną do tej z poprzedniej sekcji. Zamiast korzystać z twierdzenia Master i zapominając o stałych, można również je przeanalizować, aby uzyskać przybliżenie, które jest asymptotycznie równe prawdziwej wielkości. Pełną analizę można znaleźć w [1]; Oto ogólny zarys (niekoniecznie pasuje do kodu Isabelle / HOL):

Jak wyżej, powtarzalność liczby porównań jest

$\qquad \begin{align}f_0 = f_1 &= 0 \\ f_n &= f_{\left\lceil\frac{n}{2}\right\rceil} + f_{\left\lfloor\frac{n}{2}\right\rfloor} + e_n\end{align}$

$e_n$$n$

$\qquad \displaystyle \begin{cases} f_{2m} &= 2f_m + e_{2m} \\ f_{2m+1} &= f_m + f_{m+1} + e_{2m+1} \end{cases}$

$f_n$$e_n$

$\qquad \displaystyle \sum\limits_{k=1}^{n-1} (n-k) \cdot \Delta\kern-.2em\nabla f_k = f_n - nf_1$

$\Delta\kern-.2em\nabla f_k$

$\qquad \displaystyle W(s) = \sum\limits_{k\geq 1} \Delta\kern-.2em\nabla f_k k^{-s} = \frac{1}{1-2^{-s}} \cdot \underbrace{\sum\limits_{k \geq 1} \frac{\Delta\kern-.2em\nabla e_k}{k^s}}_{=:\ \boxminus(s)}$

do czego prowadzi nas formuła Perrona

$\qquad \displaystyle f_n = nf_1 + \frac{n}{2\pi i} \int\limits_{3-i\infty}^{3+i\infty} \frac{\boxminus(s)n^s}{(1-2^{-s})s(s+1)}ds$ .

Ocena zależy od tego, który przypadek jest analizowany. Poza tym możemy - po pewnym oszustwie - zastosować twierdzenie o pozostałościach, aby uzyskać$\boxminus(s)$

$\qquad \displaystyle f_n \sim n \cdot \log_2(n) + n \cdot A(\log_2(n)) + 1$

gdzie jest funkcją okresową o wartościach w .$A$$[-1,-0.9]$

1. Mellin przekształca się i asymptotyka: nawrót połączenia scalonego Flajoleta i Golina (1992)
2. Najlepszy przypadek: Najgorszy przypadek: Przeciętny przypadek:en=n-1en=n-⌊$e_n = \left\lfloor\frac{n}{2}\right\rfloor$
   $e_n = n-1$
   $e_n = n - \frac{\left\lfloor\frac{n}{2}\right\rfloor}{\left\lceil\frac{n}{2}\right\rceil + 1} - \frac{\left\lceil\frac{n}{2}\right\rceil}{\left\lfloor\frac{n}{2}\right\rfloor + 1}$

„Dyscyplina programowania” Dijkstry polega na analizowaniu i sprawdzaniu algorytmów oraz projektowaniu pod kątem niezawodności. W przedmowie do tej książki Dijkstra wyjaśnia, w jaki sposób bardzo prosty skonstruowany mini-język, odpowiednio zaprojektowany do analizy, wystarcza do formalnego wyjaśnienia wielu algorytmów:

Zaczynając od książki takiej jak ta, od razu pojawia się pytanie: „Z jakiego języka programowania będę korzystać?”, A to nie jesttylko kwestia prezentacji! Najważniejszym, ale także najbardziej nieuchwytnym aspektem każdego narzędzia jest jego wpływ na nawyki tych, którzy ćwiczą się w jego użyciu. Jeśli narzędzie jest językiem programowania, wpływ ten - czy nam się to podoba, czy nie - wpływa na nasze nawyki myślenia. Po przeanalizowaniu tego wpływu zgodnie z moją najlepszą wiedzą doszedłem do wniosku, że żaden z istniejących języków programowania ani ich podzbiór nie odpowiada mojemu celowi; z drugiej strony tak bardzo nie znałem się na zaprojektowanie nowego języka programowania, że ​​ślubowałem, że tego nie zrobię przez następne pięć lat, i miałem wyraźne przeczucie, że ten okres jeszcze nie upłynął! (Wcześniej, między innymi, ta monografia musiała zostać napisana.

Później wyjaśnia, jak mały zdołał zdobyć swój mini-język.

Jestem winien czytelnikowi wyjaśnienie, dlaczego utrzymałem tak mały język, aby nie zawierał on nawet procedur i rekurencji. ... Chodzi o to, że nie potrzebowałem ich, aby przekazać moją wiadomość, a mianowicie. w jaki sposób ostrożnie wybrany podział problemów jest niezbędny do opracowania pod każdym względem programów wysokiej jakości; skromne narzędzia tego mini-języka dały nam już więcej niż wystarczającą swobodę dla nietrywialnych, ale bardzo satysfakcjonujących projektów.