Hoja de repaso: Fondamentaux de la vérification algorithmique

📋 Plan du Cours

1. Spécifications d'un algorithme
2. Vérification des pré-conditions
3. Correction d'un algorithme
4. Terminaison
5. Preuve par invariants
6. Preuve par variants
7. Algorithmes simples
8. Algorithmes récursifs
9. Signature d'une fonction
10. Vérification de la signature

📖 1. Spécifications d'un algorithme

🔑 Notions clés & Définitions

• Spécifications : Ensemble des conditions décrivant précisément le cahier des charges d’un programme, notamment les données d’entrée et de sortie attendues. Elles servent de référence pour la conception et la vérification de l’algorithme.
• Données d’entrée et sortie : Les informations que l’algorithme doit recevoir (entrée) et produire (sortie) pour réaliser la tâche demandée, conformément aux spécifications.
• Cahier des charges : Document décrivant les objectifs, contraintes et conditions que doit respecter un programme ou un algorithme, sans préciser son mode de fonctionnement.
• Différence entre spécifications, algorithme et implémentation :
  • Spécifications : décrivent le résultat attendu, le cahier des charges.
  • Algorithme : la démarche ou l’architecture des instructions permettant de répondre aux spécifications.
  • Implémentation : la traduction concrète de l’algorithme dans un langage de programmation.
• Exemple de spécification (recherche dans liste triée) :
  • Données d’entrée : un nombre réel e, une liste L triée dans l’ordre croissant.
  • Données de sortie : un booléen indiquant si e appartient à L.

📝 Points essentiels

• La spécification ne décrit pas le mode de fonctionnement, mais uniquement le résultat attendu.
• Plusieurs algorithmes peuvent satisfaire une même spécification, mais leur efficacité ou leur mode de réalisation peuvent différer.
• La distinction entre cahier des charges, algorithme et implémentation est fondamentale pour assurer la cohérence et la vérification du programme.
• La spécification doit préciser clairement les données d’entrée et de sortie pour garantir la conformité de l’algorithme.
• La différence entre spécifications, algorithme et implémentation est illustrée par l’exemple de la recherche d’un élément dans une liste triée, où la spécification demande simplement si l’élément appartient ou non à la liste.

💡 À retenir

Les spécifications définissent le résultat attendu d’un algorithme, tandis que l’algorithme en détail en décrit la démarche, et l’implémentation en traduit cette démarche dans un langage de programmation.

📖 2. Vérification des pré-conditions

🔑 Notions clés & Définitions

• Conditions d'utilisation : ensemble des prérequis nécessaires pour qu'une fonction ou un algorithme fonctionne correctement, telles que la conformité des types ou la validité des valeurs d'entrée.
• Assertions en Python : instructions permettant de vérifier qu'une condition est vraie durant la phase de développement, et d'interrompre l'exécution si cette condition est fausse, avec un message d'erreur (voir G. Dupont (2025-2026)).
• Vérification de type avec isinstance : utilisation de la fonction isinstance(variable, type) pour s'assurer que la variable est d'un type attendu, évitant ainsi des dysfonctionnements implicites ou explicites (voir G. Dupont (2025-2026)).
• Gestion des erreurs liées au non-respect des préconditions : ensemble des réactions possibles lorsque les préconditions ne sont pas respectées, comprenant le fonctionnement fortuit (le programme continue sans garantie), le dysfonctionnement explicite (le programme plante avec une erreur claire), et le dysfonctionnement implicite (le programme renvoie un résultat incorrect sans erreur visible).
• Bon usage des assertions : elles doivent être employées uniquement en phase de développement pour détecter précocement des bugs, et non pour gérer des erreurs externes ou des situations attendues en production (voir G. Dupont (2025-2026)).

📝 Points essentiels

• La vérification des préconditions permet de sécuriser l'utilisation d'une fonction en s'assurant que ses paramètres respectent la signature définie, notamment en termes de types et de valeurs.
• Les assertions en Python (assert) sont un outil efficace pour cette vérification durant la phase de développement, car elles interrompent immédiatement l'exécution en cas de non-respect, facilitant la détection des bugs.
• La fonction isinstance() est essentielle pour vérifier que les variables sont du type attendu, notamment pour vérifier le type des éléments d'une liste ou d'autres structures complexes.
• La gestion des erreurs liées aux préconditions doit distinguer trois cas : fonctionnement fortuit, dysfonctionnement explicite, et dysfonctionnement implicite, ce dernier étant le plus dangereux car il peut produire des résultats incorrects sans erreur visible.
• Les assertions ne doivent pas être utilisées pour gérer des erreurs externes ou des cas attendus en production, mais uniquement pour déboguer et valider le code lors du développement (voir G. Dupont (2025-2026)).

💡 À retenir

La vérification des préconditions via assertions et isinstance() est essentielle pour garantir la fiabilité d'un algorithme durant la phase de développement, en évitant des dysfonctionnements implicites ou explicites liés à des paramètres non conformes.

📖 3. Correction d'un algorithme

🔑 Notions clés & Définitions

• Correction partielle : Un algorithme est partiellement correct s'il renvoie la bonne valeur lorsqu'il termine, sans obligation de s'assurer de sa terminaison (voir aussi correction totale).
• Correction totale : Un algorithme est totalement correct s'il termine et renvoie la bonne valeur pour toutes les entrées conformes aux spécifications.
• Différence entre correction partielle et correction totale : La correction partielle ne garantit que la validité du résultat en cas de terminaison, tandis que la correction totale inclut la garantie de terminaison.
• Lien entre correction et spécifications : La correction d’un algorithme consiste à assurer qu’il respecte les spécifications, c’est-à-dire qu’il renvoie la bonne valeur pour toutes les entrées valides, en tenant compte de la terminaison (voir aussi "spécifications").

📝 Points essentiels

• La correction partielle ne garantit pas la terminaison, elle assure seulement la validité du résultat si l’algorithme termine.
• La correction totale implique la terminaison et la conformité du résultat avec les spécifications.
• La distinction est cruciale pour la fiabilité des algorithmes critiques, notamment dans des domaines sensibles comme l’automobile ou la médecine.
• La relation entre correction et spécifications est fondamentale : l’algorithme doit respecter le cahier des charges pour être considéré comme correct.
• La preuve de correction s’appuie souvent sur la démonstration de la terminaison (avec un variant de boucle ou un invariant) et la conformité (avec un invariant ou une propriété).

💡 À retenir

La correction partielle garantit la validité du résultat en cas de terminaison, tandis que la correction totale assure à la fois la terminaison et la conformité aux spécifications.

📖 4. Terminaison

🔑 Notions clés & Définitions

• Terminaison : propriété d’un algorithme qui s’arrête après un nombre fini d’instructions, garantissant qu’il ne tourne pas indéfiniment. G. Dupont (2025) : « Un algorithme termine s'il s'arrête après un nombre fini d'étapes. »
• Algorithme qui ne termine pas : programme qui tourne indéfiniment, sans jamais s’arrêter, comme une boucle infinie. Exemple : while True: pass.
• Algorithme qui termine : programme dont l’exécution s’arrête après un nombre fini d’étapes, comme une boucle avec une condition de sortie finie. Exemple : for i in range(10): pass.
• Variant de boucle : variable modifiée à chaque itération d’une boucle, utilisée pour prouver la terminaison en montrant qu’elle atteint une valeur seuil ou un état d’arrêt. G. Dupont (2025) : « Le variant doit décroître strictement et atteindre une valeur limite finie. »
• Preuve de terminaison : démarche consistant à démontrer qu’un variant de boucle atteint une valeur d’arrêt, assurant ainsi que la boucle ou l’algorithme s’arrête.

📝 Points essentiels

• La terminaison est une propriété fondamentale pour garantir la fiabilité d’un algorithme, notamment dans des applications critiques.
• La preuve de terminaison repose souvent sur l’identification d’un variant de boucle : une variable dont la valeur diminue strictement à chaque étape et qui est bornée en dessous.
• La méthode consiste à montrer que, pour tout appel ou itération, le variant progresse vers une valeur limite, ce qui implique que la boucle ou l’algorithme doit finir.
• La preuve par invariants est également utilisée pour assurer que la propriété de terminaison est maintenue tout au long de l’exécution.
• Exemple : dans une boucle while a > 1, si a est décrémenté de 2 à chaque étape, le variant a décroît et la boucle finit lorsque a atteint 0 ou 1.

💡 À retenir

La terminaison d’un algorithme se prouve en identifiant un variant qui décroît strictement à chaque étape, garantissant ainsi que l’algorithme ne tourne pas indéfiniment.

📖 5. Preuve par invariants

🔑 Notions clés & Définitions

• Invariant de boucle : Propriété logique qui reste vraie à chaque itération d'une boucle, permettant de suivre l'évolution de l'algorithme et de garantir sa correction partielle (voir section 4).
• Preuve par invariants : Méthode consistant à identifier un invariant de boucle et à démontrer qu'il est vrai initialement, qu'il est préservé à chaque étape, et qu'il permet de conclure à la correction partielle de l'algorithme (voir section 4).
• Correction partielle : Garantie que l'algorithme renvoie la bonne valeur lorsqu'il termine, en s'appuyant notamment sur la conservation de l'invariant de boucle tout au long de l'exécution (voir section 4).
• Rôle de l'invariant : Assurer que la propriété logique reste vraie à chaque étape de la boucle, ce qui permet de déduire la correction partielle en fin d'exécution (voir section 4).
• Méthode de preuve : Consiste à prouver que l'invariant est vrai au départ, qu'il est conservé lors de chaque itération, et qu'il implique la propriété souhaitée à la fin de la boucle (voir section 4).
• Application : Utilisée pour démontrer la correction d'algorithmes avec boucle while, en particulier pour des invariants liés à la progression vers la condition d'arrêt (voir section 4).

📝 Points essentiels

• La preuve par invariants repose sur l'identification d'une propriété logique (l'invariant) qui doit être vraie au début, conservée à chaque étape, et qui garantit la correction partielle à la fin (voir section 4).
• La méthode consiste à démontrer trois étapes : initialisation (l'invariant est vrai au départ), maintien (il reste vrai après chaque étape), et terminaison (il implique la propriété finale souhaitée).
• La conservation de l'invariant permet de déduire que l'algorithme est correct en fin d'exécution, en particulier pour des boucles while où la terminaison n'est pas immédiate (voir section 4).
• La notion de variant de boucle, souvent une variable modifiée à chaque étape, est liée à la preuve de terminaison, mais l'invariant de boucle sert à prouver la correction partielle (voir section 4).
• La preuve par invariants est une étape clé dans la démonstration formelle de la correction des algorithmes utilisant des boucles, notamment pour assurer que la propriété attendue est atteinte à la sortie (voir section 4).

💡 À retenir

La preuve par invariants consiste à démontrer qu'une propriété reste vraie tout au long de l'exécution d'une boucle, garantissant ainsi la correction partielle de l'algorithme.

📖 6. Preuve par variants

🔑 Notions clés & Définitions

• Preuve par variants : méthode permettant de démontrer la terminaison d’un algorithme en montrant qu’une certaine variable, appelée variant, diminue strictement à chaque étape de la boucle ou de l’appel récursif, et ne peut pas devenir négative (voir aussi "variant de boucle").
• Définition d’un variant : une fonction ou une variable numérique strictement positive dont la valeur décroît à chaque étape de l’algorithme, assurant ainsi que l’algorithme finit par s’arrêter (voir aussi "fonction décroissante strictement positive").
• Utilisation des variants : consiste à associer à chaque étape de l’algorithme un variant qui diminue strictement, permettant de conclure que l’algorithme termine car la variable ne peut pas diminuer indéfiniment (voir aussi "preuve de terminaison").
• G. Dupont (2025-2026) : "Les preuves de terminaison d’algorithmes reposent souvent sur des variants de boucle et des récurrences finies, qui garantissent que l’algorithme ne peut pas tourner à l’infini."

📝 Points essentiels

• La preuve par variants est une technique fondamentale pour assurer la terminaison d’un algorithme, notamment dans le cas des boucles while ou des appels récursifs.
• La fonction ou la variable choisie comme variant doit être strictement positive au début et doit décroître strictement à chaque étape, ce qui implique qu’elle atteint une valeur limite (souvent zéro ou un seuil) en un nombre fini d’étapes.
• La méthode consiste à définir un invariant de boucle ou un invariant de récursion basé sur le variant, puis à montrer que ce dernier diminue à chaque étape, ce qui garantit la terminaison.
• La démarche est souvent illustrée par des exemples concrets, où l’on montre que la variable liée au problème (par exemple, une différence, un compteur, ou une valeur numérique) diminue strictement jusqu’à atteindre une condition d’arrêt.
• G. Dupont (2025-2026) : "L’utilisation du variant est essentielle pour prouver la terminaison, notamment dans le contexte des algorithmes récursifs, où il faut assurer que chaque appel récursif progresse vers une condition d’arrêt."

💡 À retenir

La preuve par variants consiste à associer une fonction strictement positive qui décroît à chaque étape de l’algorithme, garantissant ainsi sa terminaison en un nombre fini d’étapes.

📖 7. Algorithmes simples

🔑 Notions clés & Définitions

• Algorithme simple : Un algorithme qui ne contient pas de boucles ou uniquement des boucles for de longueur fixe. G. Dupont (2025-2026) : "Un algorithme simple ne comporte pas de boucle ou seulement des boucles for de longueur fixe."
• Preuve de correction : La démonstration que l'algorithme renvoie la bonne valeur lorsqu'il termine. G. Dupont (2025-2026) : "L'algorithme est correct s'il termine et renvoie la bonne valeur."
• Preuve de terminaison : La démonstration que l'algorithme s'arrête après un nombre fini d'instructions. G. Dupont (2025-2026) : "La terminaison se montre généralement à l'aide d'un variant de boucle."
• Invariant de boucle : Une propriété logique vraie à chaque étape d'une boucle, utilisée pour prouver la correction. G. Dupont (2025-2026) : "Une propriété qui est vraie à chaque itération d'une boucle."
• Principe de récurrence finie : La méthode permettant de prouver qu'une propriété est vraie pour tous les entiers dans un intervalle, en vérifiant initialisation et hérédité. G. Dupont (2025-2026) : "Pour tout n, si P(n0) est vraie et que P(n) implique P(n+1), alors P(n) est vraie pour tout n."

📝 Points essentiels

• Un algorithme simple peut ne pas contenir de boucle ou ne comporter que des boucles for de longueur fixe, ce qui simplifie la preuve de terminaison.
• La preuve de correction d’un algorithme simple repose soit sur une vérification élémentaire ligne par ligne (sans boucle), soit sur une preuve par récurrence finie si des boucles de longueur fixe sont présentes.
• La preuve de terminaison d’un algorithme avec boucle while s’appuie sur un variant de boucle, une variable modifiée à chaque étape, dont la valeur décroît strictement et atteint une valeur seuil.
• La méthode de preuve par invariants de boucle consiste à démontrer qu’une propriété est maintenue à chaque étape, assurant la correction.
• La preuve par récurrence finie est utilisée pour prouver la correction d’un algorithme basé sur une boucle for, en montrant que la propriété est vraie pour le début et qu’elle se maintient à chaque étape.

💡 À retenir

Les algorithmes simples, sans boucle ou avec des boucles de longueur fixe, facilitent la preuve de leur correction et de leur terminaison, notamment grâce à la méthode de récurrence finie et aux invariants de boucle.

📖 8. Algorithmes récursifs

🔑 Notions clés & Définitions

• Algorithme récursif : Un algorithme qui s'appelle lui-même pour résoudre un problème en le décomposant en sous-problèmes plus simples, jusqu'à atteindre une condition de terminaison (voir aussi "variant de boucle" pour la terminaison).
• Preuve de correction : La démonstration que l'algorithme récursif renvoie la bonne valeur pour tout cas d'entrée, en utilisant un invariant de boucle adapté à la récursion (voir aussi "invariant de boucle" en boucle).
• Preuve de terminaison : La démonstration que l'algorithme récursif termine, généralement en identifiant un variant de boucle strictement décroissant à chaque appel, qui atteint une valeur seuil finie (voir aussi "variant de boucle" en boucle).
• Exemple de fonction factorielle récursive partiellement correcte : Fonction qui calcule n! en s'appelant récursivement, mais qui peut ne pas terminer pour certains cas (exemple : n=0 ou n négatif), illustrant une correction partielle (voir aussi "Correction partielle" en correction d'algorithme).
• Principe de preuve pour algorithmes récursifs : La preuve de correction repose sur la vérification que chaque appel récursif réduit le problème selon un variant bien défini, et que la condition de terminaison est atteinte, assurant ainsi la correction et la terminaison (voir aussi "preuve par invariants" en boucle).

📝 Points essentiels

• La correction d’un algorithme récursif s’établit par induction sur la profondeur de récursion, en utilisant un invariant qui est préservé à chaque appel.
• La terminaison est assurée en choisissant un variant de boucle (ex : une fonction décroissante) qui atteint une valeur limite finie, garantissant que la récursion ne peut pas durer indéfiniment.
• La preuve de correction et de terminaison** repose sur la démonstration que chaque appel récursif réduit le problème selon le variant, et que la condition d’arrêt est atteinte.
• Exemple : La fonction récursive pour déterminer si un entier n est pair ou impair, en soustrayant 2 à chaque étape, illustrant la réduction du problème (voir aussi "exemple" en fonction récursive).
• La fonction factorielle récursive partiellement correcte : Fonction qui calcule n! en utilisant la récursion, mais qui peut ne pas terminer pour n négatif ou n=0 si mal définie, illustrant une correction partielle (voir aussi "exemple" en correction d'algorithme).

💡 À retenir

L’efficacité d’un algorithme récursif repose sur la réduction systématique du problème par un appel récursif avec un variant décroissant, et la preuve de correction s’appuie sur une induction structurée, garantissant à la fois la correction et la terminaison.

📖 9. Signature d'une fonction

🔑 Notions clés & Définitions

Signature d'une fonction : Ensemble des informations concernant le type des variables d’entrée et de sortie d’une fonction.
Relation avec la spécification : La signature constitue une partie de la spécification, précisant notamment les types attendus pour garantir le bon fonctionnement de l’algorithme (voir aussi "Spécifications" en section 2).
Exemples en Python : La signature peut être précisée via des commentaires, des annotations ou une docstring, permettant d’indiquer explicitement les types des paramètres et du résultat (voir "Exemples de signatures en Python").
Types des variables d’entrée et de sortie : La signature indique le type attendu pour chaque paramètre (ex. int, float, list) et pour la valeur de retour, facilitant la vérification et la compréhension du code.
Relation entre signature et spécifications : La signature est une sous-ensemble des informations de la spécification, se concentrant sur les types, tandis que la spécification inclut aussi les conditions de fonctionnement et les comportements attendus (voir "Spécifications" en section 2).

📝 Points essentiels

• La signature définit formellement le type des variables d’entrée et de sortie, ce qui facilite la vérification de leur conformité et la compréhension du contrat entre l’utilisateur et la fonction.
• En Python, la signature peut être précisée par des annotations (def f(x: int) -> bool:), par des commentaires, ou par une docstring structurée.
• La relation entre signature et spécification est essentielle : la signature précise les types, mais ne décrit pas nécessairement tous les comportements ou préconditions.
• La signature doit être cohérente avec la logique de l’algorithme, notamment pour assurer la correction et la robustesse du programme (voir "Vérification de la signature").
• La signature facilite la documentation et l’utilisation de la fonction, notamment via help() ou des outils de documentation automatique.

💡 À retenir

La signature d’une fonction précise ses types d’entrée et de sortie, servant de contrat pour garantir la compatibilité et la compréhension entre l’utilisateur et l’implémentation, tout en étant une partie essentielle de la spécification.

📖 10. Vérification de la signature

🔑 Notions clés & Définitions

• Vérification de signature (en Python) : Ensemble des méthodes permettant de préciser et contrôler les types de variables d’entrée et de sortie d’une fonction, afin de garantir la conformité avec la spécification.
• Commentaires : Textes insérés dans le code pour décrire la signature d’une fonction, mais qui nécessitent une lecture du code source pour être consultés.
• Annotations : Mécanisme en Python utilisant le mot-clé -> et : pour préciser explicitement le type des paramètres et de la valeur de retour d’une fonction, facilitant la consultation de la signature via help().
• Docstrings : Chaîne de caractères insérée après la déclaration d’une fonction, qui décrit la signature, la spécification et le comportement de la fonction, accessible avec help().
• Limites de la vérification sans préconditions : La vérification de la signature ne garantit pas que les données d’entrée respectent toutes les conditions d’utilisation (ex : types, valeurs), ce qui peut entraîner un fonctionnement fortuit, un dysfonctionnement explicite ou implicite (voir section 2).

📝 Points essentiels

• La signature d’une fonction en Python indique les types attendus pour les variables d’entrée et de sortie, mais ne vérifie pas leur conformité lors de l’appel.
• La méthode des commentaires est simple mais peu pratique, car elle oblige à consulter le code source pour connaître la signature.
• Les annotations offrent une façon explicite et automatique de préciser la signature, accessible via help() ou des outils d’analyse statique.
• La docstring est une documentation standardisée, permettant de décrire la signature, les paramètres, la valeur de retour, et la comportement de la fonction, accessible avec help().
• La vérification de la signature ne suffit pas à garantir la conformité des données d’entrée, d’où l’intérêt d’utiliser aussi des vérifications de pré-conditions (ex : assert, isinstance).
• La limite principale : la vérification de la signature ne contrôle pas la validité ou la cohérence des valeurs, seulement leur type ou leur présence.

💡 À retenir

La vérification de la signature en Python, via annotations ou docstrings, facilite la compréhension et l’utilisation des fonctions, mais ne remplace pas la vérification active des préconditions pour garantir la conformité des données d’entrée.

📊 Tableaux de Synthèse

Notion	Définition	Auteur / Référence
Spécifications	Conditions précises décrivant données d’entrée/sortie, cahier des charges	Non spécifique, général
Correction partielle	Garantie de la validité du résultat si l’algorithme termine	Non spécifique, général
Correction totale	Garantie de terminaison + conformité	Non spécifique, général
Terminaison	Propriété d’un algorithme qui s’arrête après un nombre fini d’étapes	G. Dupont (2025)
Variant de boucle	Variable utilisée pour prouver la terminaison, doit décroître	G. Dupont (2025)

⚠️ Pièges & Confusions Fréquentes

1. Confondre spécifications et algorithme : la spécification décrit le résultat, pas la démarche.
2. Confondre correction partielle et correction totale : la première ne garantit pas la terminaison.
3. Utiliser des assertions en production pour gérer des erreurs attendues : elles sont destinées au débogage.
4. Ignorer la différence entre vérification de type (isinstance) et validation de valeurs.
5. Supposer qu’un algorithme qui ne termine pas est correct : la terminaison est une propriété essentielle.
6. Confondre invariant et variant dans la preuve de terminaison.
7. Négliger la nécessité d’un variant strictement décroissant pour prouver la terminaison.

✅ Checklist Examen

1. Connaître la définition de spécifications selon G. Dupont (2025-2026).
2. Savoir distinguer entre cahier des charges, algorithme et implémentation.
3. Maîtriser la différence entre correction partielle et correction totale.
4. Comprendre la notion de terminaison et ses implications pour la fiabilité d’un algorithme.
5. Connaître le rôle du variant dans la preuve de terminaison.
6. Savoir utiliser assert et isinstance() pour vérifier les préconditions en Python.
7. Être capable d’identifier un invariant et un variant dans une preuve.
8. Connaître les conditions nécessaires pour prouver la terminaison d’un algorithme.
9. Savoir comment garantir la conformité d’un algorithme avec ses spécifications.
10. Comprendre la différence entre correction et vérification de la terminaison.
11. Savoir expliquer la différence entre correction partielle et correction totale.
12. Vérifier la maîtrise du concept de terminaison selon G. Dupont (2025).