Comment prouver par induction qu'un programme fait quelque chose?

Question

J'ai un programme informatique qui lit dans un tableau de caractères que opérandes et les opérateurs écrits en notation postfix. Le programme scanne ensuite à travers le réseau fonctionne sur le résultat à l'aide d'une pile comme indiqué:

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

Comment puis-je prouver par induction que ce programme évalue correctement toute expression postfix? (Tiré de l'exercice 4.16 algorithmes en Java (Sedgewick 2003))

Answer 1

Je ne suis pas sûr que vous devez prouver expressions l'algorithme contre. Mais si elles ressemblent à des expressions RPN typiques, vous aurez besoin d'établir quelque chose comme ce qui suit:

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

Bonne chance; -)

Rassurez-vous au sujet des preuves mathématiques, et aussi leurs noms parfois confus. Dans le cas d'un inductive la preuve on est toujours attendu à « comprendre » quelque chose (un fait ou une règle), parfois par déductives logique, mais ces faits et règles ensemble constitue une vérité plus large, acheter induction; C'est: parce que le cas de base est établie comme vraie et parce qu'on a prouvé que si X était vrai pour un « n » cas, alors X serait aussi vrai pour un « n + 1 » cas, on n'a pas besoin d'essayer tous les cas, ce qui pourrait être un grand nombre, voire infini)

Retour à l'évaluateur d'expression stack ... Un indice finale (en plus du capitaine explication excellente Segfault vous allez sentir plus informé ...).

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

Si l'on suppose que l'expression est valable (et par conséquent, ne fournit pas trop d'opérateurs trop tôt), l'ordre dans lequel l'opérande / opérateurs sont introduits dans l'algorithme ne pas d'importance; ils quittent toujours le système dans une situtation stable:    - soit avec un opérande supplémentaire sur la pile (mais sachant que l'un des opérandes supplémentaire viendra éventuellement) ou    -. Avec un moins opérande sur la pile (mais sachant que le nombre d'opérandes à venir est aussi un de moins)

l'ordre n'a pas d'importance.

Answer 2

Vous savez ce que l'induction est? Ne voyez-vous généralement comment l'algorithme fonctionne? (Même si vous ne pouvez pas prouver encore il?)

Votre hypothèse d'induction doit dire que, après le traitement du caractère Nième, la pile est « correcte ». Un « correct » pile pour une expression RPN complète n'a qu'un seul élément (la réponse). Pour une expression RPN partielle de la pile comporte plusieurs éléments.

Votre preuve est alors de penser à cet algorithme (moins le résultat = pop de la ligne de la pile) comme un analyseur qui transforme partielles expressions RPN en piles, et prouver qu'il les transforme en les piles correctes .

Il pourrait aider à regarder votre définition d'une expression RPN et le travail en arrière de celui-ci.