Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Correction d'un algorithme
Résumé
Un algorithme est correct s'il fait ce qu'on attend de lui. Plus précisément, rappelons qu'un algorithme est décrit par une spécification des données sur lesquelles l'algorithme va démarrer son calcul et une spécification du résultat produit par l'algorithme. Démontrer la correction de l'algorithme consiste à démontrer que l'algorithme retourne, quand il calcule en partant des données, un objet qui est un des résultats escomptés et qui satisfait la spécification du résultat comme énoncé dans la description de l'algorithme.
Pour s'assurer qu'un algorithme est correct, il faut démontrer deux choses: il faut démontrer que l'algorithme se termine (terminaison), autrement dit qu'il ne boucle pas ou ne diverge pas, produisant au moins un résultat et que le résultat de l'algorithme est effectivement de la forme énoncée par la spécification (correction partielle). La conjonction de la correction partielle et de la terminaison s'appelle la correction totale.
Comme la construction essentielle d'un algorithme itératif est la boucle (construction tant que ou while), l'argument principal de la démonstration de la correction partielle d'un algorithme itératif est la recherche d'un invariant pour chaque boucle (un invariant de boucle). Un invariant est un prédicat portant sur les variables du programme et sur des variables auxiliaires (ajoutées pour exprimer ce prédicat). La recherche des invariants est une opération difficile qui peut faire sortir de la logique utilisée pour décrire l'algorithme (incomplétude). Une fois ces invariants exhibés, le cœur de la démonstration consiste à démontrer que chaque invariant est effectivement stable lors de l'exécution de la boucle ; cela signifie que si l'invariant est satisfait avant l'exécution du corps de la boucle, il est satisfait après.
Algorithme récursif#Le problème de la correction partielle
Pour démontrer la correction d'un algorithme récursif, il faut connaître une précondition (un prédicat satisfait avant l'appel de l'algorithme) et une postcondition (un prédicat satisfait après l'appel de l'algorithme).
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.