Fiche de révision : Spécification des programmes Python

📋 Plan du Cours

1. Expressions, instructions et effets de bord
2. Contrat des fonctions
3. Préconditions et postconditions
4. Invariants et correction des boucles
5. Précondition et contrôle des entrées
6. Spécification, programmation et tests
7. Recherche dichotomique et terminaison

📖 1. Expressions, instructions et effets de bord

🔑 Notions clés & Définitions

• Expression : Construction qui peut être évaluée pour produire une valeur.
• Instruction : Construction qui demande à Python d’effectuer une action.
• Effet de bord : Modification observable de l’environnement provoquée par l’exécution d’une fonction ou d’une instruction, en plus de sa valeur de retour éventuelle.

★ À maîtriser

• En Python, l’affectation, comme x = 3, est une instruction qui modifie l’environnement d’exécution.

Compléments

• Les exemples d’effets de bord comprennent : la modification d’une variable globale, la modification d’une liste passée en argument, l’écriture dans un fichier, l’affichage avec print

💡 Astuce mémo

L’expression produit une valeur ; l’instruction réalise une action.

📖 2. Contrat des fonctions

★ À maîtriser

• Le contrat d’une fonction précise ses données d’entrée et ses données de sortie.

• Pour les données d’entrée, une spécification précise leur nombre, leur type et les contraintes qu’elles doivent respecter.

• Pour les données de sortie, une spécification précise leur type, leur signification et les propriétés qu’elles vérifient.

Compléments

• Pour racine_entiere(n), l’entrée est un entier n tel que n ≥ 0, et la sortie est un entier r tel que r² ≤ n < (r + 1)².

• La spécification de maximum(L) exige une liste non vide et décrit la sortie comme le plus grand élément de L.

📖 3. Préconditions et postconditions

🔑 Notions clés & Définitions

• Précondition : Condition qui doit être vraie avant l’exécution d’un programme ou d’une fonction et qui se note souvent P.
• Postcondition : Condition qui doit être vraie après l’exécution d’un programme ou d’une fonction et qui se note souvent Q.

★ À maîtriser

📌 La correction signifie que si la précondition P est vraie avant l’exécution, alors la postcondition Q est vraie après l’exécution.

Compléments

• Pour maximum(L), la précondition est que L soit une liste non vide et la postcondition est que le résultat m appartienne à L et qu’aucun élément de L ne soit strictement supérieur à m.

💡 Astuce mémo

Avant l’exécution : P ; après l’exécution : Q.

📖 4. Invariants et correction des boucles

🔑 Notions clés & Définitions

• Propriété invariante : Propriété qui reste vraie à chaque étape d’une boucle.

★ À maîtriser

• 🔄 Pour établir un invariant de boucle, il faut montrer qu’il est : vrai avant la première itération, conservé après chaque itération, suffisant pour démontrer la postcondition à la fin

Compléments

• Dans la boucle de somme, après traitement des premiers éléments de L, s est égal à leur somme.

• Dans la boucle de recherche du maximum, après traitement des éléments déjà parcourus, m est leur maximum.

💡 Astuce mémo

Initialiser, conserver, conclure.

📖 5. Précondition et contrôle des entrées

★ À maîtriser

📌 Une précondition fixe les conditions dans lesquelles le comportement de la fonction est garanti, mais elle n’impose pas automatiquement au programme de tester ces conditions.

Compléments

• Pour inverse(x) = 1/x, la précondition proposée est x ≠ 0.

• Le programme peut contrôler la précondition de inverse(x) en levant ValueError lorsque x vaut 0.

💡 Astuce mémo

La précondition fixe une condition de validité ; le test dans le code la contrôle.

📖 6. Spécification, programmation et tests

★ À maîtriser

• 🔄 La démarche de l’activité bilan consiste à :

  1. spécifier la fonction compte
  2. la programmer
  3. proposer un invariant
  4. la tester

• Pour compte(L, x), la précondition est que L soit une liste et la postcondition est que la fonction retourne le nombre d’éléments de L égaux à x.

Compléments

• Dans compte(L, x), après traitement d’une partie de L, n est le nombre d’éléments égaux à x parmi les éléments déjà traités.

• Les tests proposés pour compte couvrent une liste vide, une valeur répétée, une valeur absente et une liste composée uniquement de répétitions : compte([], 2), compte([1,2,2,3], 2), compte([1,2,3], 4) et compte([5,5,5], 5).

💡 Astuce mémo

Spécifier, programmer, établir l’invariant, tester.

📖 7. Recherche dichotomique et terminaison

★ À maîtriser

• La recherche dichotomique présentée suppose que la liste L est triée dans l’ordre croissant.

• La recherche dichotomique présentée retourne un booléen indiquant si x appartient à L.

Compléments

• Dans l’algorithme présenté, les indices de recherche sont initialisés à g = 0 et d = len(L) − 1, et la boucle continue tant que g ≤ d.

• L’activité sur la recherche dichotomique demande d’identifier une quantité permettant de justifier la terminaison de l’algorithme.