Domanda per principianti riguardante la logica di una prova di correttezza molto semplice

Question

Sto cercando di familiarizzare con le prove di correttezza e necessitano di aiuto.In Prova per SimplesELECT (P.25), perché assumiamo sia $ a '[i] e $ 1 \ LeqI \ Leq K $ ?Non sono sicuro del motivo per cui lo facciamo, poiché il testo afferma che perché "di cosa significhi per un algoritmo per soddisfare le sue specifiche, qualsiasi prova di correttezza inizierà assumendo la precondizione".Tuttavia, non è la precondizione qui semplicemente la precondizione di Simpleselect come specificato qui (P.6)?

Answer 1

Entrambe le ipotesi che menzioni sono "locali" nel senso che sono una sottocomprensione nella prova e non fanno parte delle condizioni del teorema. Puoi anche vederli come definizione di una variabile locale $ i $ , una formulazione equivalente delle due ipotesi sarebbe

.

.

1. Let $ I $ Sii tale che $ a '[i] e $ 1 \ leq i \ leq n $ .

2. Let $ i $ Sii tale che $ 1 \ leq i \ leq k $ .

La prova conta il numero di valori di $ I $ per il quale queste affermazioni Hold, che mostrano che la postcondition è soddisfatta.

---

.

Penso che parte della tua confusione deriva da un linguaggio implicito in questi paragrafi, quindi riscriverò uno di loro per essere più esplicito. Il primo paragrafo del libro legge:

.

Supponiamo $ a '[i] per alcuni $ i $ , $ 1 \ Leq I \ Leq N $ . Quindi $ i , per se $ k , $ A '[k]> a' [i] $ viola la postcondition del tipo. Quindi, ci sono meno di $ k $ elementi di $ a '$ e quindi della classe $ a $ , con valore inferiore a $ a '[k] $ .

Un fraseggio più esplicito è il seguente:

Let $ i $ essere tale che $ a '[i] e $ 1 \ Leq I \ Leq N $ . Se $ k , quindi $ a '[i] contraddice Con la postcondition di ordinamento, quindi $ i \ leq k $ . Se $ i= k $ , quindi $ a '[i]= a' [k] $ , che contraddice con la nostra definizione di $ i $ .

Quindi, abbiamo dimostrato che se $ a '[i] e $ 1 \ Leq I \ Leq N $ , quindi $ i . Ciò significa che il numero di elementi di $ A '$ con valore rigorosamente inferiore a $ A' [K] $ è strettamente inferiore a $ k $ . Dal momento che $ A $ è una permutazione di $ a '$ , ci sono meno di $ k $ elementi di $ a $ rigorosamente inferiore a $ a '[k] $ . Dal momento che $ a '[k] $ è il valore di ritorno dell'algoritmo, la prima parte della postcondition della selezione è soddisfatta.

La struttura complessiva del secondo paragrafo è simile, quindi dovresti essere in grado di afferrarlo se riesci a capire il primo.