Flashcards: Fondamentaux de la vérification algorithmique — 20 cards

Spécifications — définition ?

Conditions précises décrivant le résultat attendu.

Données d’entrée/sortie — rôle ?

Définissent ce que l’algorithme doit recevoir et produire.

Cahier des charges — contenu ?

Objectifs, contraintes, conditions du programme.

Spécifications vs algorithme — différence ?

Spécifications décrivent le résultat, l’algorithme la démarche.

Correction partielle — garantie ?

Validité du résultat si l’algorithme termine.

Correction totale — garantie ?

Terminaison et conformité aux spécifications.

Terminaison — définition ?

L’algorithme s’arrête après un nombre fini d’étapes.

Algorithme non terminé — exemple ?

Boucle infinie, tourne indéfiniment.

Variant de boucle — rôle ?

Prouver que la boucle termine en décroissant strictement.

Preuve de terminaison — comment ?

En montrant qu’un variant décroît vers une limite.

Invariant de boucle — rôle ?

Propriété qui reste vraie à chaque itération.

Preuve par invariants — étape clé ?

Montrer que l’invariant est vrai initialement, maintenu, et implique la propriété finale.

Preuve par variants — principe ?

Démontrer qu’un variable strictement positive décroît, assurant la terminaison.

Algorithme simple — caractéristique ?

Pas ou peu de boucles, ou boucles for de longueur fixe.

Algorithme récursif — principe ?

S’appelle lui-même pour réduire le problème.

Correction d’un algorithme récursif — base ?

Vérifier que chaque appel réduit le problème et atteint une condition d’arrêt.

Signature d’une fonction — contenu ?

Types des paramètres d’entrée et de sortie.

Vérification de signature — méthode ?

Utiliser annotations, commentaires ou docstrings en Python.

Vérification de signature — limite ?

Ne garantit pas la validité des valeurs, seulement les types.

Vérification des pré-conditions — but ?

Assurer que les paramètres respectent la signature et les contraintes.