Wie kann man Algorithmen beschreiben, beweisen und analysieren?

20

Bevor ich The Art of Computer Programming (TAOCP) gelesen habe , habe ich diese Fragen nicht gründlich untersucht. Ich würde Pseudocode verwenden, um Algorithmen zu beschreiben, sie zu verstehen und die Laufzeit nur über Wachstumsordnungen zu schätzen. Das TAOCP ändert meine Meinung gründlich.

TAOCP verwendet Englisch gemischt mit Schritten und Gehe zu, um den Algorithmus zu beschreiben, und verwendet Flussdiagramme, um den Algorithmus leichter darzustellen. Es scheint auf niedrigem Niveau zu sein, aber ich finde, dass es einige Vorteile gibt, insbesondere bei Flussdiagrammen, die ich oft ignoriert habe. Wir können jeden der Pfeile mit einer Aussage über den aktuellen Stand der Dinge zum Zeitpunkt der Berechnung beschriften und einen induktiven Beweis für den Algorithmus erstellen. Der Autor sagt:

Es ist die Behauptung des Autors, dass wir wirklich verstehen, warum ein Algorithmus nur dann gültig ist, wenn wir den Punkt erreichen, an dem unser Verstand alle Behauptungen implizit ausgefüllt hat, wie dies in Abb. 4 getan wurde.

Ich habe solche Sachen nicht erlebt. Ein weiterer Vorteil ist, dass wir zählen können, wie oft jeder Schritt ausgeführt wird. Mit Kirchhoffs erstem Gesetz lässt sich das leicht überprüfen. Ich habe die Laufzeit nicht genau analysiert, sodass bei der Schätzung der Laufzeit möglicherweise weggelassen wurden.±1

Die Analyse von Wachstumsordnungen ist manchmal nutzlos. Beispielsweise können wir keine Quicksortierung von Heapsortierung unterscheiden, da sie alle , wobei E X die erwartete Anzahl der Zufallsvariablen X ist. Daher sollten wir die Konstante E analysieren ( 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)und , so können wir T 1 und T 2 besser vergleichen. Und manchmal sollten wir auch andere Größen wie Abweichungen vergleichen. Nur eine grobe Analyse der Wachstumsordnungen der Laufzeit reicht nicht aus. Wie TAOCPE(T2(n))=A2lgn+B2n+O(logn)T1T2 übersetzt die Algorithmen in Assemblersprache und berechnet die Laufzeit. Es ist zu schwer für mich, deshalb möchte ich einige Techniken kennen, um die Laufzeit etwas gröber zu analysieren, was auch für übergeordnete Sprachen wie C, C ++ nützlich ist oder Pseudocodes.

Und ich möchte wissen, welcher Beschreibungsstil hauptsächlich in Forschungsarbeiten verwendet wird und wie diese Probleme zu behandeln sind.

Yai0Phah
quelle
6
Sie sollten sehr vorsichtig sein, wenn Sie die Ausführungszeiten von Algorithmen so genau vergleichen. Echte Computer haben Caches, Register und Pipelines, die die Laufzeit drastisch verändern können. Wenn Sie herausfinden möchten, welcher Algorithmus tatsächlich schneller ist, müssen Sie ihn tatsächlich auf einem Computer ausführen.
Svick
1
Tatsächlich ist das Analysieren von Assemblern, wie sie Knuth verwendet, viel einfacher als das Analysieren von Code aus dem wirklichen Leben, da nichts verborgen ist und der Steuerungsfluss einfach ist. Sie bitten um Übung; Ich denke, Daves Kommentar trifft zu. Es ist wahrscheinlicher, dass Praktiker ihre Algorithmen mithilfe von Laufzeitmessungen entwickeln, als dass sie strenge Analysen durchführen. Aber dann bin ich kein Praktizierender, also nimm was ich sage mit einem Körnchen Salz.
Raphael
1
@Raphael My in der Praxis bedeutet, dass in der Praxis nicht programmiert , sondern geforscht wird .
Yai0Phah,
@ Frank, was meinst du mit Varianz ? Meine Leistungstests geben mir zeitliche Abweichungen.
edA-qa mort-ora-y
@Raphael, dein erster Punkt, das ist nicht mehr wirklich wahr. Moderne Chips ordnen Ihre Baugruppe neu, lagern / laden nicht in der richtigen Reihenfolge und ermöglichen vorausschauendes Laufen und Laden. Für Parallelität und die vorherigen Ausgaben ist eine gründliche Analyse erforderlich, aber ich mache es nicht in einer formalen Form.
edA-qa mort-ora-y

Antworten:

18

Es gibt eine Vielzahl von realisierbaren Ansätzen. Welches am besten geeignet ist, hängt davon ab

  • was du versuchst zu zeigen,
  • wie viel Detail Sie wollen oder brauchen.

Wenn es sich bei dem Algorithmus um einen allgemein bekannten Algorithmus handelt, den Sie als Unterroutine verwenden, bleiben Sie häufig auf einer höheren Ebene. Wenn der Algorithmus das zu untersuchende Hauptobjekt ist, möchten Sie wahrscheinlich detaillierter werden. Dasselbe gilt für Analysen: Wenn Sie eine grobe Obergrenze für die Laufzeit benötigen, verfahren Sie anders, als wenn Sie eine genaue Anzahl von Anweisungen wünschen.

Ich werde Ihnen drei Beispiele für den bekannten Algorithmus Mergesort geben, die dies hoffentlich veranschaulichen.

Hohes Level

Der Algorithmus Mergesort nimmt eine Liste, teilt sie in zwei (ungefähr) gleich lange Teile auf, rekursiert auf diese Teillisten und führt die (sortierten) Ergebnisse zusammen, so dass das Endergebnis sortiert wird. Bei einzelnen oder leeren Listen wird die Eingabe zurückgegeben.

Dieser Algorithmus ist offensichtlich ein korrekter Sortieralgorithmus. Das Aufteilen und Zusammenführen der Liste kann jeweils in der Zeit implementiert werden , was eine Wiederholung für die Worst-Case-Laufzeit T ( n ) = 2 T ( n ) ergibtΘ(n). Durch das MasterTheorem, diese auswertet bisT(n)egr& THgr;(nlogn).T(n)=2T(n2)+Θ(n)T(n)Θ(nlogn)

Mittleres Level

Der Algorithmus Mergesort ist durch folgenden Pseudocode gegeben:

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
}

Wir beweisen die Richtigkeit durch Induktion. Für Listen der Länge Null oder Eins ist der Algorithmus trivial korrekt. Nehmen Sie als Induktionshypothese an, dass mergesortbei Listen mit einer Länge von höchstens für ein willkürliches, aber festes natürliches n > 1 die Leistung korrekt ist . Nun sei L eine Liste der Länge n + 1 . Durch Induktionshypothese, und halten (nicht abnehmend) sortierte Versionen der ersten resp. zweite Hälfte von L nach den rekursiven Aufrufen. Daher wählt die Schleife in jeder Iteration das kleinste Element aus, das noch nicht untersucht wurde, und hängt es an ; somit handelt es sich um eine nicht zunehmend sortierte Liste, die alle Elemente von enthältnn>1Ln+1leftrightLwhileresultresultleftund right. Die Umkehrung ist eine nicht abnehmend sortierte Version von , bei der es sich um das zurückgegebene - und gewünschte - Ergebnis handelt.L

Zählen wir zur Laufzeit Elementvergleiche und Listenoperationen (die die Laufzeit asymptotisch dominieren). Listen mit einer Länge von weniger als zwei verursachen keine. Für Listen mit einer Länge von haben wir die Operationen, die durch das Vorbereiten der Eingaben für die rekursiven Aufrufe verursacht werden, diejenigen aus den rekursiven Aufrufen selbst sowie die Schleife und eine . Beide rekursiven Parameter können mit jeweils höchstens n Listenoperationen berechnet werden. Die Schleife wird genau n Mal ausgeführt und jede Iteration verursacht höchstens einen Elementvergleich und genau zwei Listenoperationen. Das Finale kann implementiert werden, um 2 n zu verwendenn>1whilereversenwhilenreverse2nListenoperationen - Jedes Element wird aus der Eingabe entfernt und in die Ausgabeliste eingefügt. Daher erfüllt die Anzahl der Vorgänge die folgende Wiederholung:

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

Da eindeutig nicht abnimmt, ist es ausreichend, n = 2 k für asymptotisches Wachstum zu berücksichtigen . In diesem Fall vereinfacht sich die Wiederholung zuTn=2k

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

Durch den Master - Satz erhalten wir , die zur Laufzeit erstreckt .TΘ(nlogn)mergesort

Ultra-Low-Level

Betrachten Sie diese (verallgemeinerte) Implementierung von Mergesort in 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+

Dies schließt bereits Beweise für die Richtigkeit und Kündigung ein. Finden Sie einen (fast) vollständigen Korrektheitsbeweis hier .

Für die "Laufzeit", also die Anzahl der Vergleiche, kann eine ähnliche Wiederholung wie im vorherigen Abschnitt eingerichtet werden. Anstatt den Hauptsatz zu verwenden und die Konstanten zu vergessen, können Sie ihn auch analysieren, um eine Näherung zu erhalten, die asymptotisch der wahren Größe entspricht. Die vollständige Analyse finden Sie in [1]; Hier ist eine grobe Übersicht (sie muss nicht unbedingt zum Isabelle / HOL-Code passen):

Wie oben ist die Wiederholung für die Anzahl der Vergleiche

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

where en is the number of comparisons needed for merging the partial results². In order to get rid of the floors and ceils, we perform a case distinction over whether n is even:

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

Using nested forward/backward differences of fn and en we get that

k=1n1(nk)Δfk=fnnf1.

The sum matches the right-hand side of Perron's formula. We define the Dirichlet generating series of Δfk as

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

which together with Perron's formula leads us to

fn=nf1+n2πi3i3+i(s)ns(12s)s(s+1)ds.

Evaluation of (s) depends on which case is analysed. Other than that, we can -- after some trickery -- apply the residue theorem to get

fnnlog2(n)+nA(log2(n))+1

where A is a periodic function with values in [1,0.9].


  1. Mellin transforms and asymptotics: the mergesort recurrence by Flajolet and Golin (1992)
  2. Best case: en=n2
    Worst case: en=n1
    Average case: en=nn2n2+1n2n2+1
Raphael
quelle
My question of running-time-analysis is that, how to determine α and β exactly T(n)=T(n/2)+T(n/2)+αn+β, which is close to practice (e.g, it's availabe to compare merge-sort and qsort).
Yai0Phah
@Frank: The short answer is You can't; the constants depend on implementation details—including the machine architecture, language, and compiler—that are immaterial to the underlying algorithm.
JeffE
@JeffE I have to claim that, the α and β should only be exact enough to do some comparison. More briefly, a mathematical model which can do a lot of works, without machine languages, to determine the constants.
Yai0Phah
@JeffE for example, the MIX/MMIX in taocp is, but it's too hard to translate an algorithm to such a machine language.
Yai0Phah
@FrankScience: In order to get close to practice, you would have to count all operations (like Knuth does). Then, you can instantiate your result with machine-specific operation costs to get real runtime (ignoring effects the order of operations might have, caching, pipelines, ...). Usually, people only count some operations, and in that case fixing α and β does not tell you much.
Raphael
3

Dijkstra's "A discipline of Programming" is all about analyzing and proving algorithms and designing for provability. In the preface to that book, Dijkstra explains how a very simple constructed mini-language that is properly designed to be analyzed suffices to explain many algorithms formally:

When starting on a book like this, one is immediately faced with the question: "Which programming language am I going to use?", and this is not a mere question of presentation! A most important, but also a most elusive, aspect of any tool is its influence on the habits of those who train themselves in its use. If the tool is a programming language, this influence is -- whether we like it or not -- an influence on our thinking habits. Having analyzed that influence to the best of my knowledge, I had come to the conclusion that none of the existing programming languages, nor a subset of them, would suit my purpose; on the other hand I knew myself so unready for the design of a new programming language that I had taken a vow not to do so for the next five years, and I had a most distinct feeling that that period had not yet elapsed! (Prior to that, among many other things, this monograph had to be written.) I have tried to resolve this conflict by only designing a mini-language suitable for my purposes, by making only those commitments that seemed unavoidable and sufficiently justified.

Later he explains just how small he managed to get his mini-language.

I owe the reader an explanation why I have kept the mini-language so small that it does not even contain procedures and recursion. ... The point is that I felt no need of them in order to get my message across, viz. how a carefully chose separation of concerns is essential for the design of in all respect, high-quality programs; the modest tools of the mini-language gave us already more than enough latitude for nontrivial, yet very satisfactory designs.

Mike Samuel
quelle