Essayer de comprendre cette preuve d'exactitude Quicksort

Cette preuve est une preuve par induction, et va comme suit:

P (n) est l'affirmation selon laquelle "Tri rapide trie correctement chaque tableau d'entrée de longueur n".

Cas de base: chaque tableau d'entrée de longueur 1 est déjà trié (P (1) tient)

Étape inductive: fixer n => 2. Fixer un tableau d'entrée de longueur n.

Besoin de montrer: si P (k) est valable pour tout k <n, alors P (n) est également valable

Il trace ensuite un tableau A partitionné autour d'un pivot p. Il dessine donc p et appelle la partie du tableau qui est <p comme 1ère partie, et la partie qui est> p est la deuxième partie. La longueur de la partie 1 = k1, et la longueur de la partie 2 est k2. Par la preuve d'exactitude du sous-programme de partition (prouvée précédemment), le pivot p se termine dans la bonne position.

Par hypothèse inductive: les 1ère, 2e parties sont triées correctement par appels récursifs. (En utilisant P (K1), P (k2))

Donc: après des appels récursifs, tout le tableau est correctement trié.

QED

Ma confusion : j'ai beaucoup de mal à voir exactement comment cela prouve l'exactitude de celui-ci. Nous supposons donc que P (k) est vrai pour tous les nombres naturels k <n.

La plupart des preuves d'induction que j'avais vues jusqu'à présent vont quelque chose comme: Prouver le cas de base et montrer que P (n) => P (n + 1). Ils impliquaient généralement une sorte de manipulation algébrique. Cette preuve semble très différente, et je ne comprends pas comment lui appliquer le concept d'Induction. Je peux quelque peu raisonner que l'exactitude du sous-programme de partition est la clé. Le raisonnement pour son exactitude est le suivant: Nous savons que chaque appel récursif, il partitionnera le tableau autour d'un pivot. Ce pivot sera alors dans sa position légitime. Ensuite, chaque sous-réseau sera encore partitionné autour d'un pivot, et ce pivot sera alors dans sa position légitime. Cela continue indéfiniment jusqu'à ce que vous obteniez un sous-tableau de longueur 1, qui est trié de manière triviale.

Mais alors nous ne supposons pas que P (k) est valable pour tous les k <n .... nous le montrons réellement (puisque le sous-programme de partition placera toujours un élément dans sa position légitime.) Ne supposons-nous pas que P (k) est valable pour tout k

correctness-proof induction quicksort FrostyStraw
la source

Qu'est-ce que "QUE"? Voulez-vous dire "QED"? (le latin Quod Erat Demonstrandum qui ne contient aucun mot commençant par U )

Bakuriu

Je voulais bien dire QED. Je suppose que ma confusion m'a amené à écrire "QUOI?" en espagnol

FrostyStraw

Réponses:

$P(k)$ $k < n$ $P(n-1)$ $P(n)$

La preuve que vous décrivez est connue comme le principe d'une forte induction mathématique et a la forme

$P(n)$ $n\in \{1, 2, \dotsc\}$

$P(1)$

$(\forall k < n \;[P(k)])\Longrightarrow P(n)$

$P(n)$ $n\ge 1$

$n$ $k$ $n-k-1$

$k<n$ $n-k-1<n$

Rick Decker
la source

P (1)

$P(1)$

n = 1

$n=1$

\forall k < 1, P (k)

$\forall k<1,P(k)$

P (1)

$P(1)$

Bon alors ... pour être clair ... Nous supposons que P (k) est vrai pour tout k <n. Et la façon dont nous MONTRONS que P (k) ==> P (n) (pour tout k <n) est par la combinaison de savoir que le pivot sera à coup sûr dans sa position correcte, et par l'hypothèse (l'hypothèse inductive ) que les sous-réseaux gauche et droit sont également triés. Combinez cela avec le cas de base (dans lequel k = 1 <n), et la preuve est complète?

FrostyStraw

eh bien je suppose que ce ne serait pas suffisant de savoir que le pivot est dans sa position correcte, mais aussi que le sous-tableau de droite est tout plus grand que le pivot et que celui de gauche est tout moins que

FrostyStraw

@FrostyStraw Ce sont des chuchotements chinois.

Raphael

@FrostyStraw Hehe, je voulais dire la stratégie de preuve. :)

Raphael

Cette preuve utilise le principe de l' induction complète :

Supposer que:

$P(1)$

$n > 1$ $P(1),\ldots,P(n-1)$ $P(n)$

$P(n)$ $n \geq 1$

Q (m) \Leftrightarrow P (1) and P (2) and \dots and P (m)

$Q(m) \Leftrightarrow P(1) \text{ and } P(2) \text{ and } \cdots \text{ and } P(m)$

Maintenant, utilisons l'induction complète pour prouver que la version suivante de Quicksort trie correctement son entrée:

Quicksort(A, n)
    if n = 1 then:
        return
    else:
        let X[1...x] consist of all elements of A[2],...,A[n] which are at most A[1]
        let Y[1...y] consist of all elements of A[2],...,A[n] which are larger than A[1]
        call Quicksort(X, x)
        call Quicksort(Y, y)
        set A to the concatenation of X, A[1], Y

Voici A[1],...,A[n]le tableau d'entrée et nsa longueur. La déclaration que nous voulons prouver est la suivante:

$A$ $n \geq 1$ $A$ $B$

$A$

$\pi_1,\ldots,\pi_n$ $1,\ldots,n$ $B[i] = A[\pi_i]$

$B[1] \leq B[2] \leq \cdots \leq B[n]$

$P(n)$

$A$ $n \geq 1$ $B$ Quicksort(A, n) $B[1] \leq B[2] \leq \cdots \leq B[n]$

$n$ $n = 1$ $n > 1$ $X,x,Y,y$ Quicksort $x,y < n$

X [1] \leq X [2] \leq \dots \leq X [x] Y [1] \leq Y [2] \leq \dots \leq Y [y]

$X[1] \leq X[2] \leq \cdots \leq X[x] \\ Y[1] \leq Y[2] \leq \cdots \leq Y[y]$

X

$X$

Y

$Y$

X [x] \leq A [1] < Y [1]

$X[x] \leq A[1] < Y[1]$

X [1] \leq \dots \leq X [x] \leq A [1] < Y [1] \leq \dots \leq Y [y] .

$X[1] \leq \cdots \leq X[x] \leq A[1] < Y[1] \leq \cdots \leq Y[y].$

B [1] \leq \dots \leq B [n]

$B[1] \leq \cdots \leq B[n]$

P (n)

$P(n)$

Yuval Filmus
la source

La partie manquante de l'argument est la transitivité de '<' - c'est-à-dire la propriété que si a <b et b <c, alors a <c. La preuve que le tableau final est trié ressemble à ceci:

Soit A [i], A [j] des éléments du tableau post-tri, où i <j. Alors A [i] <A [j] découle de l'un des cas de placement suivants (et il n'y a pas d'autres cas):

(a) i et j sont dans la première partition - A [i] <A [j] suit par récursivité / induction.

(b) i et j sont dans la deuxième partition - A [i] <A [j] suit par récursivité / induction.

(e) i est dans la première partition et j est dans la deuxième partition - puis par la procédure de partition, A [i] <pivot et pivot <A [j]. Donc par transitivité, A [i] <A [j].

PMar
la source