Python - Justification de l'algorithme

Afin de prétendre qu'un algorithme est efficace, nous avons besoin de quelques 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.

• Direct Proof:

  C'est une vérification directe de l'énoncé en utilisant les calculs directs. Par exemple, la somme de deux nombres pairs est toujours un nombre pair. Dans ce cas, ajoutez simplement les deux nombres que vous étudiez et vérifiez le résultat comme pair.

• Proof by induction:

  Ici, nous commençons par une instance spécifique d'une vérité, puis nous la généralisons à 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 le prouvons pour la valeur suivante de n. Cela établit l'énoncé comme généralement vrai par la preuve de l'induction.

• Proof by contraposition:

  Cette preuve est basée sur la condition Si Non A implique Non B alors A implique B. Un exemple simple est que si le carré de n est pair, alors n doit être pair. Parce que si le carré sur n n'est pas pair, alors n n'est pas pair.

• Proof by exhaustion:

  Ceci est similaire à la preuve directe, mais il est établi en visitant chaque cas séparément et en prouvant chacun d'eux. Un exemple d'une telle preuve est le théorème des quatre couleurs.