Come a dimostrare per induzione che un programma fa qualcosa?

Question

Ho un programma per computer che legge in un array di caratteri che gli operandi e gli operatori scritti in notazione postfissa. Il programma esamina poi attraverso la matrice elabora il risultato utilizzando una pila come mostrato:

get next char in array until there are no more
if char is operand
    push operand into stack
if char is operator 
    a = pop from stack
    b = pop from stack
    perform operation using a and b as arguments
    push result
result = pop from stack

Come posso dimostrare per induzione che questo programma valuta correttamente ogni espressione postfissa? (Tratto da esercizio 4.16 Algoritmi in Java (Sedgewick 2003))

Answer 1

Non sono sicuro che le espressioni è necessario dimostrare l'algoritmo contro. Ma se si guardano come espressioni tipiche RPN, è necessario stabilire qualcosa di simile al seguente:

1) algoritm works for 2 operands (and one operator)
   and 
   algorithm works for 3 operands (and 2 operators)
  ==> that would be your base case

2) if algorithm works for n operands (and n-1 operators)
  then it would have to work for n+1 operands.
  ==> that would be the inductive part of the proof

Buona fortuna; -)

Coraggio riguardante dimostrazioni matematiche, e anche i loro nomi a volte confuse. Nel caso di un induttivo una prova ancora si pensa che "capire" qualcosa (qualche fatto o qualche regola), a volte da deduttivi logica, ma poi questi fatti e regole mettere insieme costituiscono una verità più ampia, acquistare a induzione; Cioè: perché il caso base è stabilito come vero e perché uno ha dimostrato che, se X era vero per un caso "n" allora X sarebbe valido anche per un "+ n 1" caso, allora non abbiamo bisogno di provare ogni caso, che potrebbe essere un grande numero o anche infinito)

Torna sull'espressione valutatore stack-based ... Un suggerimento finale (in addtion a eccellente spiegazione del capitano Segfault ti sentirai oltre informato ...).

The RPN expressions are  such that:
  - they have one fewer operator than operand
  - they never provide an operator when the stack has fewer than 2 operands 
    in it (if they didn;t this would be the equivalent of an unbalanced 
    parenthesis situation in a plain expression, i.e. a invalid expression).

Supponendo che l'espressione è valida (e quindi non fornisce troppi operatori troppo presto), l'ordine in cui l'operando / operatori vengono condotti nella algoritmo non importa; lasciano sempre il sistema in un situtation stabile:    - sia con un operando in più sullo stack (ma la consapevolezza che un operando in più alla fine venire) o    -. Con un operando in meno sullo stack (ma la consapevolezza che il numero di operandi ancora a venire è anche uno di meno)

Quindi, l'ordine non ha importanza.

Answer 2

Non si sa che cosa è l'induzione? Ti generalmente vedere come funziona l'algoritmo? (Anche se non si può ancora dimostrarlo?)

L'ipotesi induttiva dovrebbe dire che, dopo l'elaborazione del carattere N'th, lo stack è "corretto". Una pila "corretta" per un'espressione completa RPN ha un solo elemento (risposta). Per un'espressione RPN parziale la pila ha diversi elementi.

La ricevuta è quindi di pensare a questo algoritmo (meno il risultato = pop dalla linea stack) come un parser che trasforma parziali espressioni RPN in cataste, e dimostrare che li trasforma in pile corrette .

Potrebbe aiutare a guardare la tua definizione di un'espressione RPN e lavorare a ritroso da esso.