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

20

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 ±1 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))=Θ(nlogn)EXXE(T1(n))=A1nlgn+B1n+O(logn)i E(T2(n))=A2lgn+B2n+O(logn) , dzięki czemu możemy lepiej porównać T1 i T2 . 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.

Yai0Phah
źródło
6
Należy bardzo uważnie porównywać czasy wykonania algorytmów. Prawdziwe komputery mają pamięci podręczne, rejestry i potoki, które mogą drastycznie zmienić czas działania. Jeśli chcesz dowiedzieć się, który algorytm jest rzeczywiście szybszy, musisz go uruchomić na komputerze.
svick
1
W rzeczywistości analiza asemblera, takiego jak Knuth, jest znacznie łatwiejsza niż analiza kodu z życia, ponieważ nic nie jest ukryte, a kontrola przepływu jest łatwa. Prosicie o praktykę; Myślę, że komentarz Dave'a ma zastosowanie. Praktycy częściej opracowują swoje algorytmy przy użyciu pomiarów czasu wykonywania niż przeprowadzają rygorystyczną analizę. Ale nie jestem praktykiem, więc weź to, co mówię, z odrobiną soli.
Raphael
1
@Raphael My w praktyce oznacza, że w praktyce prace badawcze , a nie programowanie .
Yai0Phah
@Frank, co masz na myśli przez wariancję ? Moje testy wydajności dają mi wariancje czasowe.
edA-qa mort-ora-y
@Raphael, twój pierwszy punkt nie jest już tak naprawdę prawdą. Nowoczesne układy scalone zmieniają kolejność montażu, robią zakupy / ładunki poza kolejnością oraz przewidują uruchamianie i ładowanie. W przypadku współbieżności i poprzednich problemów wymagana jest dokładna analiza, ale nie robię tego w formalnej formie.
edA-qa mort-ora-y

Odpowiedzi:

18

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.

Θ(n)T(n)=2T(n2)+Θ(n)T(n)Θ(nlogn)

Ś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
}

mergesortnn>1Ln+1leftrightLwhileresultresultleftrightL

n>1whilereversenwhilenreverse2noperacje 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ść:

T(0)=T(1)=0T(n)T(n2)+T(n2)+7n

Tn=2k

T(0)=T(1)=0T(n)2T(n2)+7n

TΘ(nlogn)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

f0=f1=0fn=fn2+fn2+en

enn

{f2m=2fm+e2mf2m+1=fm+fm+1+e2m+1

fnen

k=1n1(nk)Δfk=fnnf1

Δfk

W(s)=k1Δfkks=112sk1Δekks=: (s)

do czego prowadzi nas formuła Perrona

fn=nf1+n2πi3i3+i(s)ns(12s)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ć(s)

fnnlog2(n)+nA(log2(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- nen=n2
    en=n1
    en=nn2n2+1n2n2+1
Raphael
źródło
Moje pytanie dotyczące analizy w czasie wykonywania jest takie, jak określić i dokładnie , który jest bliski praktyce (np. można porównywać sortowanie-sortowanie i qsort). β T ( n ) = T ( n / 2 ) + T ( n / 2 ) + α n + βαβT(n)=T(n/2)+T(n/2)+αn+β
Yai0Phah
@Frank: Krótka odpowiedź brzmi: nie możesz ; stałe zależą od szczegółów implementacji - w tym architektury maszyny, języka i kompilatora - które są nieistotne dla podstawowego algorytmu.
JeffE
@JeffE mam zastrzeżenia tym, i powinna być dokładna wystarczy zrobić tylko jakieś porównanie. W skrócie: model matematyczny, który może wykonać wiele prac , bez języków maszynowych, w celu ustalenia stałych. βαβ
Yai0Phah
@JeffE na przykład MIX / MMIX w taocp jest, ale zbyt trudno jest przetłumaczyć algorytm na taki język maszynowy.
Yai0Phah
@FrankScience: Aby zbliżyć się do praktyki, musisz policzyć wszystkie operacje (podobnie jak Knuth). Następnie możesz utworzyć wynik z kosztami operacyjnymi specyficznymi dla maszyny, aby uzyskać rzeczywisty czas działania (ignorując efekty, jakie może mieć kolejność operacji, buforowanie, potoki ...). Zwykle ludzie liczą tylko niektóre operacje, w takim przypadku naprawianie i niewiele mówi. βαβ
Raphael
3

„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.

Mike Samuel
źródło