Domanda circa la prova formale l'attraversamento in ordine simmetrico

Question

Serie famosi in Don Knuth di libri, The Art of Computer Programming , la sezione 2.3.1, egli descrive un algoritmo per attraversare albero binario in ordine simmetrico, facendo uso di uno stack ausiliario:

T1 [Inizializza.] Set pila $ \ rm A $ svuotare e impostare la variabile link $ \ rm P \ T ottiene $

T2 [$ \ rm P = \ Lambda $?] Se $ \ rm P = \ Lambda $, andare al passaggio T4.

T3 [Stack $ \ rm \; \ Leftarrow P $] (. Ora $ \ rm P $ punta a un albero binario non vuoto che deve essere mosso) spingere il valore di $ \ rm P $ sulla pila $ \ rm A $, quindi impostare $ \ rm P \ ottiene llink (P) $

T4 [$ \ rm P \ Leftarrow Stack $] Se pila $ \ rm A $ è vuota, i termina algoritmo; altrimenti pop la parte superiore di $ \ rm A $ a $ \ rm P $.

T5 [Visita $ \ rm P $] Visita $ \ rm NODE (P) $. Quindi impostare $ \ rm P \ ottiene RLINK (P) $ e tornare al punto T2.

Siamo in grado di tracciare un diagramma di flusso dell'algoritmo. Nel paragrafo successivo, egli dà un prova formale dell'algoritmo:

A partire da passo T2 con $ \ rm P $ un puntatore a un albero binario di $ n $ nodi e con lo stack $ \ rm A $ contenente $ \ rm A [1] \ dotsc A [m] $ per un po ' $ m \ ge 0 $, la procedura dei punti T2-T5 attraverserà l'albero binario in questione, in ordine simmetrico, e poi arrivare al passo T4 con stack di $ \ rm a $ tornata al suo valore originale $ \ rm a [1 ] \ dotsc A [m] $.

Tuttavia, per quanto ne so, una prova tale formale è molto diverso dal metodo generale descritto nella sezione 1.2.1:

per ogni casella nel diagramma di flusso, che se un'affermazione collegato a qualsiasi freccia che conduce verso l'area è vero prima di eseguire l'operazione in tale casella, allora tutte le affermazioni su relative frecce che partono dalla scatola sono vere dopo l'operazione.

In realtà, tale metodo è in qualche modo equivalente a Hoare logica , che viene utilizzato per controllare la validità formale di algoritmi .

Possiamo girare la dichiarazione di cui per dimostrare l'algoritmo di traslazione in uno schema di logica Hoare, o l'affermazione attaccamento di un diagramma di flusso?

Grazie!

Answer 1

E 'sicuramente possibile analizzare questo algoritmo utilizzando triple Hoare. Il primo passo sarebbe quello di sostituire le chiamate di procedura visita con qualche meccanismo di contabilità più ragionevole, diciamo una lista che elenca i nodi visitati in ordine. È quindi definire formalmente ciò che un albero binario è e ciò che un attraversamento in ordine simmetrico è, qualcosa lungo le seguenti linee:

Tree = Leaf N | Node N LTree RTree
Inorder(Leaf N) = N
Inorder(Node N LTree RTree) = Inorder(LTree) || N || Inorder(RTree)

Ecco N è il "nome" del nodo, e || è la lista concatenazione. Armati di queste nozioni, è un esercizio di costruire le triple Hoare richiesti. Probabilmente avrete bisogno di venire con ancora più nozioni (ad esempio, è necessario spiegare che cosa il contenuto dello stack sono quando un nodo P è spuntato).

Cosa ci guadagniamo da questo esercizio? Capiamo l'algoritmo di meglio? Probabilmente no. Ma si capisce come motivo preciso di algoritmi, il che è utile se si ha intenzione di fare la verifica del software o la programmazione teoria dei linguaggi, le aree che formano la cosiddetta "Teoria B". Se siete più di una "Teoria Un" tipo (algoritmi e complessità) poi, come me, si trovano tali esercizi un po 'fuori luogo.