Justification des algorithmes

Afin d'affirmer qu'un algorithme est efficace, nous avons besoin de certains outils mathématiques comme preuve. Ces outils nous aident à fournir une explication mathématiquement satisfaisante sur les performances et la précision des algorithmes. Vous trouverez ci-dessous une liste de certains de ces outils mathématiques qui peuvent être utilisés pour justifier un algorithme par rapport à un autre.

• Preuve directe : Il s'agit de la vérification directe de l'affirmation en utilisant des calculs directs. Par exemple, la somme de deux nombres pairs est toujours un nombre pair. Dans ce cas, il suffit d'additionner les deux nombres que vous étudiez et de vérifier que le résultat est pair.
• Preuve par induction : Ici, on commence par une instance spécifique d'une vérité et on la généralise ensuite à toutes les valeurs possibles qui font partie de la vérité. L'approche consiste à prendre un cas de vérité vérifiée, puis à prouver qu'elle est également vraie pour le cas suivant pour la même condition donnée. Par exemple, tous les nombres positifs de la forme 2n-1 sont impairs. Nous le prouvons pour une certaine valeur de n, puis nous le prouvons pour la valeur de n suivante. Cela établit que l'affirmation est généralement vraie par preuve d'induction.
• Preuve par contraposition : Cette preuve est basée sur la condition Si Pas A implique Pas B alors A implique B. Un exemple simple est que si le carré de n est pair alors n doit être pair. Car si le carré de n n'est pas pair, alors n n'est pas pair.
• Preuve par épuisement : Elle est similaire à la preuve directe mais elle est établie en visitant chaque cas séparément et en prouvant chacun d'entre eux. Un exemple d'une telle preuve est le théorème des quatre couleurs.