Como provar por indução que um programa faz alguma coisa?

Question

Eu tenho um programa de computador que lê em uma matriz de caracteres que operandos e operadores escritos em notação postfix. O programa então verifica através das obras de matriz fora o resultado usando uma pilha como mostrado:

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

Como posso provar por indução que este programa avalia corretamente qualquer expressão postfix? (Retirado do exercício 4.16 Algoritmos em Java (Sedgewick 2003))

Answer 1

Eu não tenho certeza que expressões que você precisa provar o algoritmo contra. Mas se eles se parecem com expressões RPN típicas, você vai precisar para estabelecer algo como o seguinte:

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

Boa sorte; -)

Faça coração sobre provas matemáticas, e também seus nomes por vezes confusa. No caso de um indutiva uma prova é ainda esperado para "descobrir" alguma coisa (algum fato ou alguma regra), às vezes por dedutivo lógicas, mas depois desses fatos e regras juntos constituem uma verdade mais ampla, compra de indução; Isto é: porque o caso base é estabelecida como verdadeira e porque um provou que, se X era verdade para um "n" caso, então X também seria verdadeiro para um "n + 1" caso, então não precisamos tentar cada caso, o que poderia ser um grande número ou mesmo infinito)

De volta ao avaliador de expressão baseada em pilha ... Uma dica final (em addtion a excelente explicação do capitão Segfault você vai se sentir mais informado ...).

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).

Assumindo que a expressão é válida (e, portanto, não fornece muitos operadores muito em breve), a ordem em que o operando / operadores são alimentados no algoritmo não importa; eles sempre deixam o sistema em um situtation estável: - seja com um operando extra na pilha (mas o conhecimento que se operando extra virá eventualmente) ou - com um a menos operando na pilha (mas o conhecimento de que o número de operandos ainda está por vir é também um menos)

.

Assim, a ordem não importa.

Answer 2

Você sabe o que a indução é? Você geralmente ver como o algoritmo funciona? (Mesmo se você não pode provar isso ainda?)

A sua hipótese de indução deveria dizer que, depois de processar o personagem enésimo, a pilha é "correta". Uma pilha "correta" para uma expressão RPN completo tem apenas um elemento (a resposta). Para uma expressão RPN parcial a pilha tem vários elementos.

A sua prova é, então, a pensar desse algoritmo (menos o resultado = pop da linha pilha) como um analisador que voltas parcial expressões RPN em pilhas, e provar que ele transforma-los em pilhas corretas .

Pode ajudar a olhar para a sua definição de uma expressão RPN e para trás trabalho dele.