SPECIALITE NSI NUMERIQUE Se) eae Ue ssSPECIALITE NSI . a NUMERIQUE ET SCIENCES INFORMATIQUES 24 lecons avec exercices corrigés NOUVEAUX ] O Thibaut Balabonski Sylvain Conchon Jean-Christophe Filliatre Kim Nguyen Préface de Xavier LeroyPréface Enseigner informatique au lycée n'est pas une idée nouvelle : les pre- mires expériences pédagogiques remontent aux années 1980. Mais c’est de- puis peu qu’un enseignement approfondi d’informatique est offert dans tous les lycées généraux, avec, depuis la rentrée 2019, un enseignement Sciences numériques et technologie (SNT) en seconde et un enseignement de spécia- lité Numérique et sciences informatiques (NSI) en premitre et, das la rentrée 2020, en terminale. La spécialité NST est ambitieuse : par le volume horaire qui lui est consa- cré, mais aussi par la richesse de son programme, qui va bien au-dela de la simple «littératie informatique» et aborde frontalement les notions fonda- mentales de la science informatique. Algorithmique et programmation — les deux piliers de la pensée informatique — y sont largement présentes, mais on y découvre également les bases de données, 'architecture des ordinateurs, les systémes d’exploitation et les réseaux. Un programme d’une telle richesse est une aventure pour l’éléve comme pour lenseignant, ce dernier n’ayant souvent pas suivi de cours d’informa- tique comparables lors de sa formation universitaire. L’ouvrage de Thibaut Balabonski, Sylvain Conchon, Jean-Christophe Fillidtre et Kim Nguyen, so- brement intitulé Spécialité Numérique et sciences informatiques, est le par- fait guide pour les accompagner tout au long de ce voyage a la découverte des bases de l’informatique. Le premier volume de cet ouvrage, consacré A la classe de premiére et paru A la rentrée 2019, avait beaucoup impressionné : Gilles Dowek, I’un des initiatours de la spécialité NSI, a employé & son propos le mot de «miracle». Crest done avec impatience que je découvre le second volume, consacré & la classe de terminale, et avec plaisir que je constate que nos quatre auteurs ont fait, une fois de plus, un travail admirable. Deux styles sont (hélas) trés répandus dans les manuels pour lensei- gnement de l’informatique : la vulgarisation légére, qui effieure plaisam- ment le sujet mais laisse le lecteur sur sa faim, et le traité universitaire, qui Pétouffe sous l’exhaustivité et la rigueur formelle. Rien de tel dans l'ouvrage de Thibaut Balabonski, Sylvain Conchon, Jean-Christophe Filliatre et Kim Nguyen : la présentation des concepts va droit A V'essentiel, mais ne céde jamais 4 l’approximation. C’est ainsi, dans un bel équilibre entre intuitioniv Préface et rigueur, que ce livre nous fait parcourir d’un bon pas — andante — un joli chemin A travers les bases de l’informatique. Ce livre sera sans aucun doute une grande aide dans la mise en place de la. spécialité NSI. Remercions les auteurs pour cette précieuse contribution, et souhaitons A tous les enseignants et & tous les élves de la spécialité NSI bien des satisfactions et bien des succés dans leur découverte et leur transmission de la pensée informatique. Xavier Leroy Professeur au Collége de France, chaire de sciences du logicielAvant- propos A qui s’adresse cet ouvrage? Cet ouvrage s’adresse autant a l’enseignant qu’a V’éléve. Un éléve de terminale trouvera dans cet ouvrage un rappel du cours, de nombreux exercices pour s’entrainer, ainsi que des encarts pour approfondir certains points. L’enseignant y trouvera un cours structuré pour mener |’enseignement de NSI en classe de terminale, sous la forme de vingt- quatre legons couvrant tous les points du programme officiel. Chaque legon prend la forme d'un chapitre, contenant a la fois l’introduction de nouvelles notions et des exercices corrigés. Les legons peuvent étre traitées dans l’ordre, au sens oil chacune ne fait appel qu’a des notions introduites dans les legons précédentes. Il reste possible de traiter beaucoup de legons dans un ordre différent. Cet ouvrage fait suite A un premier volume pour l’enseignement de la spécialité NSI en classe de premiére. Nous y faisons parfois référence (avec la notation [NSI 1', 9.3] pour un renvoi vers la section 9.3, par exemple) mais ces références peuvent étre facilement ignorées. Style. On adopte un style de programmation en Python le plus idioma- tique possible, mais tout en restant relativement simple. En particulier, on s’interdit d’utiliser des concepts et notations introduits dans des chapitres ultérieurs, ce qui rend parfois le code un peu plus lourd qu’il ne pourrait étre. Exercices. Cet ouvrage contient de nombreux exercices, regroupés A chaque fois en fin de chapitre. Les exercices sont tous corrigés, les solu- tions étant regroupées A la fin de louvrage. Pour chaque exercice, il existe le plus souvent de trés nombreuses solutions. Nous n’en donnons qu’une seule, avec seulement parfois une discussion sur des variantes possibles. Certains exercices sont plus longs que d’autres et peuvent constituer des séances de travaux pratiques relativement longues voire de petits projets. Des exemples sont le jeu des lemmings (exercice 28 page 65) ou celui de la course de tor- tues (exercice 29 page 67), la simulation d’attente a des guichets (exercice 69 page 145) ou encore la méthode de Karatsuba (exercice 117 page 231).vi Avant-propos Le site du livre. Le site https://www.nsi-terminale.fr/ propose des ressources complémentaires. En particulier, il donne acc’s au code Python de tous les programmes décrits dans cet ouvrage. Ils pourront ainsi étre facilement réutilisés, par exemple dans des séances de travaux pratiques visant & les manipuler ou les modifier. Remerciements. Nous tenons remercier trés chaleureusement toutes les personnes qui ont contribué a cet ouvrage par leur relecture attentive et leurs suggestions pertinentes, & savoir David Baelde, Lila Boukhatem, Alain Busser, Jérme Duval, Frangois Fayard, Yann Régis-Gianas, Laurent Sartre. Nous remercions tout particulitrement notre collégue Frédéric Voisin pour sa relecture, de trés grande qualité, de presque tous les chapitres de ce livre. De nombreux enseignants de la spécialité NSI de classe de premiére nous ont fait des retours constructifs et encourageants sur le précédent volume et nous tenons A les en remercier sinctrement. Nous remercions aussi les participants au groupe de discussion national NSI : certaines remarques de ce livre font écho & leurs échanges. Nous sommes reconnaissants & Corinne Baud et Anne Laure Tedesco, des éditions Ellipses, pour la confiance qu’elles nous ont accordée et leur réactivité. Nous remercions également Didier Rémy pour son excellent paquet XTX exercise. Enfin, nous sommes trés honorés que Xavier Leroy ait accepté de préfacer cet ouvrage et nous le remercions vivement.Table des matiéres 1 Programmation 1 Récursivité 1.1 Probléme : la somme des n premiers entiers . . . 1.2 Formulations récursives 1.3 Programmer avec des fonctions récursives Exercices. ee ee eee 2 Modularité 2.1 Variations sur les ensembles . 2.2 Modules, interfaces et encapsulation . 2.3. Exceptions Exercices. 3 Programmation objet 3.1 Classes et attributs : structurer les données 3.2 Méthodes : manipuler les données . . 3.3. Retour sur I'encapsulation . . 3.4 Heritage . Exercices. 0... 4 Mise au point des programmes 4.1 Types : 4.2. Tester un programme ....... . 4.3 Invariant de structure . . . Exercices 5 Programmation fonctionnelle 5.1 Fonctions passées en arguments 5.2. Fonctions renvoyées comme résultats 5.3. Structures de données immuables . . Exercices SRB 45 50 57 59 62 71 71 79 86 89 o1 95 7 . 100viii 6 10 il Algorithmique Listes chainées 6.1 Structure de liste chainge 6.2 Opérations sur les listes . 6.3 Modification d'une liste 6.4 Encapsulation dans un objet Exercices. 2.2.22 Piles et files 7.1 Interface et utilisation d'une pile . . . 7.2 Interface et utilisation d'une file 7.3 Réaliser une pile avec une liste chainée Table des matiéres 7.4 Réaliser une file avec une liste chainée mutable 7.5 Réaliser une file avec deux piles . . . Exercices Arbres binaires 8.1 Structures arborescentes . 8.2 Définition et propriétés des arbres binaires wee 8.3. Représentation en Python... ... . 8.4 Algorithmique des arbres binaires Exercices 9.1 Notion... 9.2 Recherche dans un ABR . 9.3. Ajout dans un ABR 9.4 Suppression dans un ABR . . 9.5 Encapsulation dans un objet 9.6 Arbre équilibré Exercices . Autres structures arborescentes 10.1 Arborescence.......... 10.2 Exemples de structures arborescentes . Exercices . . Graphes 11.1 Définitions .... . 11.2 Exemples de graphes 11.3 Représentation d'un graphe en Python 11.4 Exemple d'algorithme sur les graphes . . Exercices. .. 2. . 105 107 108 . ill . 119 . 121 . 124 127 128 130 .. 133 . 135 . 138 141 147 . 147 . 155 .. 148 . 161 153 157 . 158 . 159 - 161 166 168 169 . 170 173 173 . 176 . 185 189 . 190 . 194 - 196 . 202 . 204Table des matiéres 12 Parcours en profondeur et en largeur 12.1 Parcours en profondeur . 2... 2.2.0... 12.2 Détecter la présence d'un cycle dans un graphe orienté 12.3 Parcours en largeur.... 22... Exercices.. 2... 13 ser pour régner 13.1 Retour sur la recherche dichotomique...... . . 13.2 Trifusion. 2.0.22... 2... Exercices. 2 eee 14 Programmation dynamique 14.1 Rendu de monnaie . . . 14.2 Alignement de séquences . . Exercices . 15 Recherche textuelle 15.1 Un algorithme simple ................ 15.2 Accélération de la recherche : 15.3 Un algorithme plus efficace : Boyer-Moore ... . . Exercices 16 Calculabi 16.1 Probléme : détecteur d’erreurs en Python 16.2 Calculabilité, des mathématiques a |'informatique 16.3 Limites de la calculabilité ©... .... Exercices Ill Bases de données 17 Modéle relationnel 17.1 Le modéle relationnel cen ee 17.2 Modélisation relationnelle des données wee Exercices. 2 2. eee 18 Bases de données relationnelles 18.1 SQL : un langage de définition de données . . 18.2 Types de données en SQL 18.3 Spécification des contraintes d’i intégrité 18.4 Suppression de tables 18.5 Insertion dans une table Exercices. 2... 2... 207 . 208 212 . 214 . 218 221 . 222 224 . 229 233 234 - 239 - 246 249 . 250 - 252 254 . 261 263 . 263 - 268 . 274 - 280 283 286 . 288 295 297 . 298 . 300 . 302 . 304 305 . 306x Table des matiéres 19 Requétes SQL et mises a jour 19.1 Sélection de données . 19.2 Modification des données . . . 19.3 Requétes imbriquées............... Exercices. 022. ee 20 Systémes de Gestion de Bases de Données 20.1 Historique 20.2 Transactions . . . 20.3 Interaction entre un SGBD et un programme Exercices. 2... eee ae IV Architectures matérielles, systémes d’exploitation et ré- seaux 345 21 ts intégrés 347 21.1 Microcontréleurs .. 348 21.2 Systéme sur puce .. 351 Exercices... 2.0... . 356 22 Gestion des processus et des ressources 22.1 L'ordonnanceur bee eee 22.2 Commandes Unix de gestion des processus . . 22.3 Programmation concurrente . . Exercices . . 23 Protocoles de routage 383 23.1 Le protocole RIP 386 23.2 Protocole OSPF 390 23.3 Commandes systéme seve ee sees «396 Exercices beet eee bee eee eee. 402 24 Sécurisation des communications 405 24.1 Cryptographie symétrique 406 24.2 Cryptographie asymétrique 410 24.3 Authentification des participants ..............-. 415 24.4 Le protocole HTTPS ....... bee eens 417 Exercices. 2.22. . 424 Solutions des exercices 427 Index 507Premiére partie ProgrammationChapitre 1 Récursivité Notions introduites e définitions récursives © programmation avec fonctions récursives © arbre d’appels ‘© modéle d’exécution et pile d’appels On aborde dans ce chapitre la programmation & aide de fonctions récur- sives. Il s’agit A la fois d’un style de programmation mais également d’une technique pour définir des concepts et résoudre certains problémes qu’il n'est parfois pas facile de traiter en programmant uniquement avec des boucles. 1.1 Probléme : la somme des n premiers entiers Pour définir la somme des n premiers entiers, on a ’habitude d’écrire la formule suivante! : O+1424---4+n (1.1) Bien que cette formule nous paraisse simple et intuitive, il n’est pas si évident de V'utiliser pour écrire en Python une fonction somme(n) qui renvoie la somme des n premiers entiers. L’une des difficultés est de trouver un moyen de programmer la répétition des calculs qui est représentée par la notation fed. Une solution pour calculer cette somme consiste & utiliser une boucle for pour parcourir tous les entiers i entre 0 et n, en s’aidant d’une variable locale r pour accumuler la somme des entiers de 0 & 4. On obtient par exemple le code Python suivant : 1. Cet exemple est inspiré du cours Programmation récursive de Christian Queinnec.4 Chapitre 1. Récursivité def somme(n): r=0 for i in range(n + 1): rert+i return r S'il n'est pas difficile de se convaincre que la fonction sonme(n) ci-dessus calcule bien la somme des n premiers entiers, on peut néanmoins remarquer que ce code Python n'est pas directement lié & la formule (1.1). En effet, il n’y a rien dans cette formule qui puisse laisser deviner qu’une variable intermédiaire r est nécessaire pour calculer cette somme. Certains peuvent y voir l'art subtil de la programmation, d’autres peuvent se deman- der s'il ne serait pas possible de donner une définition mathématique plus précise A cette somme, A partir de laquelle il serait plus « simple » d’écrire un programme Python. Il existe en effet une autre maniére d’aborder ce probléme. Il s’agit de définir une fonction mathématique somme(n) qui, pour tout entier naturel n, donne la somme des n premiers entiers de la maniére suivante : 0 sin=0, somme(n) = { n+somme(n—1) sin>0. Cette définition nous indique ce que vaut somme(n) pour un entier n quel- conque, selon que n soit égal A 0 ou strictement positif. Ainsi, pour n = 0, la valeur de somme(0) est simplement 0. Dans le cas oft n est strictement positif, la valeur de somme(n) est n+ somme(n — 1). Par exemple, voici ci-dessous les valeurs de somme! 1, 2e3. , pour n valant 0, 0 1+ somme(0) 1+0 2+ somme(1) 241 3+somme(2) = 343 Comme on peut le voir, la définition de somme(n) dépend de la valeur de somme(n — 1). Il s'agit 1A d’une définition récursive, c’est-A-dire d’une définition de fonction qui fait appel a elle-méme. Ainsi, pour connaitre la valeur de somme(n), il faut connaitre la valeur de somme(n — 1), donc connaitre la valeur de somme(n—2), etc. Ceci jusqu’a la valeur de somme(0) qui ne dépend de rien et vaut 0. La valeur de somme(n) s’obtient en ajoutant toutes ces valeurs. L’intérét de cette définition récursive de la fonction somme(n) est qu’elle est directement calculable, ’est-A-dire exécutable par un ordinateur. En par- ticulier, cette définition est directement programmable en Python, comme le montre le code ci-dessous.11. Probléme : la somme des n premiers entiers 5 def somme(n’ if n == 0 return 0 else: return n + somme(n - 1) L’analyse par cas de la définition récursive est ici réalisée par une instruction conditionnelle pour tester si l’'argument n est égal A 0. Si c’est le cas, la fonction renvoie la valeur 0, sinon elle renvoie la somme n + somme(n - 1). Cet appel & somme(n - 1) dans le corps de la fonction est un appel récursif, c’est-A-dire un appel qui fait référence & la fonction que l’on est en train de définir. On dit de toute fonction qui contient un appel récursif que c’est une fonction récursive. Par exemple, l’évaluation de l’appel 4 sonme(3) peut se représenter de la maniére suivante somme(3) = return 3 + somme(2) | return 2 + somme(1) return 1 + somme(0) return 0 od on indique uniquement pour chaque appel & somme(n) V’instruction qui est exécutée aprés le test n == 0 de la conditionnelle. Cette maniére de représenter l'exécution d’un programme en indiquant les différents appels effectués est appelée un arbre d’appels. Ainsi, pour calculer la valeur renvoyée par sonme (3), il faut tout d’abord appeler somme(2). Cet appel va lui-méme déclencher un appel & somme(1), qui A son tour nécessite un appel A sonme(0). Ce dernier appel se termine directement en renvoyant la valeur 0. Le calcul de somme(3) se fait donc « Arebours ». Une fois que ’appel & somme(0) est terminé, c’est-d-dire que la valeur 0 a été renvoyée, l’arbre d’appels a la forme suivante, ot ’appel & sonme(0) a été remplacé par 0 dans lexpression return 1 + sonme(0). somme(3) = return 3 + somme(2) | return 2 + somme(1) return 1 + 0 A cet instant, l’'appel A somme(1) peut alors se terminer et renvoyer le ré- sultat de la somme 1 + 0. L’arbre d’appels est alors le suivant. somme(3) = return 3 + somme(2) return 2+ 16 Chapitre 1. Récursivité Enfin, l'appel & somme(2) peut Iui-méme renvoyer la valeur 2 + 1 comme résultat, ce qui permet 4 somme(3) de se terminer en renvoyant le résultat de 3 + 3. somme(3) = return 3 + 3 On obtient bien au final la valeur 6 attendue. Une notation ambigué. La formule (1.1) est non seulement éloignée du programme qui la calcule, elle est également ambigué quant a la spécification de son résultat. A lire cette formule a la lettre, comment savoir si la somme des premiers entiers pour n = 2 est 0+ 1+2 ou 0+1+2+ 2? Si la réponse A cette question peut sembler évidente, elle ne l’est que parce que nous avons l’habitude de la signification de +++++ et savons que les entiers (0, 1 et 2) dans cette formule sont déja des instances de n. De maniére générale, la programmation imposant la précision, nous sommes souvent amenés comme ici A considérer avec une rigueur nou- velle certaines choses « évidentes ». 1.2 Formulations récursives Une formulation récursive d’une fonction est toujours constituée de plu- sieurs cas, parmi lesquels on distingue des cas de base et des cas récursifs du calcul. Les cas récursifs sont ceux qui renvoient & la fonction en train d’étre définie (somme(n) = n + somme(n — 1) sin > 0). Les cas de base de la définition sont & l'inverse ceux pour lesquels on peut obtenir le résultat sans avoir recours la fonction définie elle-méme (somme(n) = 0 sin = 0). Ces cas de base sont habituellement les cas de valeurs particulitres pour lesquelles il est facile de déterminer le résultat. Prenons comme deuxiéme exemple l’opération de puissance n-itme d’un nombre «, c’est-d-dire la multiplication répétée n fois de x avec lui-méme, que l’on écrit habituellement de la maniére suivante SEX XE oes n fois avec, par convention, que la puissance de x pour n = 0 vaut 1. Pour écrire une version récursive de 2”, on va définir une fonction puissance(z,n) en commengant par chercher les cas de base & cette opé- ration. Ici, le cas de base évident est celui pour n = 0. On écrira donc la définition (partielle) suivante :1.2. Formulations récursives 7 pavanedenya{} S228 . ? sin>0. Pour définir la valeur de puissance(z,n) pour un entier n strictement positif, on suppose que I’on connait le résultat de x @ la puissance n — 1, c’est-d-dire la valeur de puissance(z,n — 1). Dans ce cas, puissance(xr,n) peut simplement étre définie par x x puissance(zr,n—1). Au final, on obtient done la définition suivante : sin=0, . 1 puiesance(2,n) = { © x puissance(z,n—1) sin>0. Faire confiance ala récursion. Pour faciliter I’écriture des cas récursits, il est trés important de supposer que les appels récursifs donnent les bons résultats pour les valeurs sur lesquelles ils opérent, sans chercher & « construire » dans sa téte l’arbre des appels pour se convaincre du bien fondé de la définition. Définitions récursives plus riches Toute formulation récursive d’une fonction posséde au moins un cas de base et un cas récursif. Ceci étant posé, une grande variété de formes est possible. Cas de base multiples. La définition de la fonction puissance(z,n) n'est pas unique. On peut par exemple identifier deux cas de base « faciles », celui pour n = 0 mais également celui pour n = 1 avec puissance(z, 1) = 2. Ce deuxiéme cas de base a ’avantage d’éviter de faire la multiplication (inutile) 2x1 de la définition préeédente. Ainsi, on obtient la définition suivante avec deux cas de base : 1 sin=0, puissance(x,n) = 4 sin=1, x x puissance(t,n—1) sin>1. Bien sir, on pourrait continuer & ajouter des cas de base pour n = 2, , etc., mais cela n’apporterait rien A la définition. En particulier, cela ne réduirait pas le nombre de multiplications a effectuer.8 Chapitre 1. Récursivité Cas récursifs multiples. Il est également possible de définir une fonction avec plusieurs cas récursifs. Par exemple, on peut donner une autre définition pour puissance(x,n) en distinguant deux cas récursifs selon la parité den. En effet, si n est pair, on a alors 2” = (2"/2)”, De méme, si n est impair, on a alors 2” = x x (2("-/2)?, ot Yopération de division est supposée ici étre la division entiére. Ceci nous améne & définir la fonction puissance(x,n) de la maniére suivante, en supposant que l'on dispose d’une fonction carre(z) = axe. puissance(,n) = 1 sin=0, carre(puissance(s, n/2)) sin > Let nest pair, 2 x carre(puissance(z,(n —1)/2)) sin >1et n est impair. Pour des raisons dont nous discuterons un peu plus loin, cette définition va nous permettre d’implémenter en Python une version plus efficace de la fonction puissance. Double récursion. Les expressions qui définissent une fonction peuvent aussi dépendre de plusieurs appels A la fonction en cours de définition. Par exemple, la fonction fibonacci(n), qui doit son nom au mathématicien Leo- nardo Fibonacci, est définie récursivement, pour tout entier naturel n, de la maniére suivante : 0 sin=0, fibonacei(n) = 4 1 sin=1, fibonacci(n — 2) + fibonacci(n—1) sin> 1. Voici par exemple les premiéres valeurs de cette fonction. fibonacci(0) = 0 fibonacei(1) = 1 fibonacei(2) = fibonacei(0) + fibonacci{1) = 041 = 1 fibonacci(3) = fibonacci(1) + fibonacci(2) = 1+1 = 2 fibonacci(4 ) fibonacci(2) + fibonacci(3) = 1+2 = 3 Abonacet®) fibonacci(3) + fibonacci(4) = 2+3 = 5 Récursion imbriquée. Les occurrences de la fonction en cours de défini- tion peuvent également étre imbriquées. Par exemple, la fonction fo1(n) ci-dessous, que l'on doit & John McCarthy (informaticien et lauréat du prix ‘Turing en 1971), est définie avec deux occurrences imbriquées, de la maniére suivante : for(n) _fn-10 sin > 100, for(for(n+11)) sin < 100.1.2. Formulations récursives 9 Voici par exemple la valeur de fo1(99) : for(99) ‘fo1(fo1(110)) puisque 99 < 100, for(100) puisque 110 > 100, = for(for(111)) puisque 100 < 100, foi(101) puisque 111 > 100, = 9 puisque 101 > 100. Le fait que fo: (99) renvoie 91 n’est pas un hasard! On peut en effet démon- trer que foi(n) = 91, pour tout entier naturel n inférieur ou égal A 101. Récursion mutuelle. Il est également possible, et parfois nécessaire, de définir plusieurs fonctions récursives en méme temps, quand ces fonctions font référence les unes aux autres. On parle alors de définitions récursives mutuelles. Par exemple, les fonctions a(n) et b(n) ci-dessous, inventées par Douglas Hofstadter (il y fait référence dans son ouvrage Gédel, Escher, Bach : Les Brins d’une Guirlande Eternelle, pour lequel il a obtenu le prix Pulitzer en 1980), sont définies par récursion mutuelle de la manitre suivante : 1 sin=0, n—b(a(n—1)) sin>0. 0 sin=0, n—a(b(n—-1)) sin>0. On peut vérifier que les premiéres valeurs de ces deux suites sont bien n:_0,1,2,3,4,5,6,7,8,9, “aln): 1, 1,2,2,3,3,4,5,5,6 b(n): 0,0,1,2,2,3,4,4,5,6,-.. D'une maniére amusante, on peut montrer que les deux séquences different. & un indice n si et seulement si n+1 est un nombre de Fibonacci, c’est-a-dire s'il existe un entier k tel que fibonacci(k) =n +1. Définitions récursives bien formées lest important de respecter quelques régles élémentaires lorsqu’on écrit, une définition récursive. Tout d’abord, il faut s’assurer que la récursion va bien se terminer, c’est-d-dire que l’on va finir par « retomber » sur un cas de base de la définition. Ensuite, il faut que les valeurs utilisées pour appeler la fonction soient toujours dans le domaine de la fonction. Enfin, il convient de vérifier qu'il y a bien une définition pour toutes les valeurs du domaine. Prenons comme premier exemple la fonction f(n) ci-dessous définie de la maniére suivante :10 Chapitre 1. Récursivité 1 sin=0, so) ={ n+f(ntl) sin>0. Cette définition est incorrecte car la valeur de f(n), pour tout n strictement positif, ne permet pas d’atteindre le cas de base pour n = 0. Par exemple, la valeur de f(1) est : F(1) =1+4 f(2)=14+2+ f(3) =... Notre deuxiéme exemple est celui d’une définition récursive pour une fonction g(n) qui s’applique & des entiers naturels. a= {> sin=0, n+g(n—2) sin>0. Cette définition n’est pas correcte car, par exemple, la valeur de g(1) vaut gl) = 1+9(-1) mais g(—1) n’a pas de sens puisque cette fonction ne s’applique qu’a des entiers naturels. Comme nous le verrons dans la section suivante, cette défi- nition peut conduire 4 une exécution infinie ou A une erreur, selon la maniére dont elle est écrite en Python. Enfin, notre dernier exemple est celui d’une fonction h(n) qui s’applique également & des entiers naturels et qui est définie de la manitre suivante : 1 sin=0, n+h(n-1) sin>1. A(n) Cette définition est incorrecte, puisqu’une valeur est oubliée. L’avez-vous repérée ?? Définition récursive de structures de données. Les techniques de dé- finition récursive peuvent s’appliquer & toute une variété d’objet, et pas seulement & la définition de fonctions. Nous verrons en particulier aux chapitres 6 et 8 des structures de données définies récursivement. 2. Crest la valeur de h(1) qui n’est pas définie.1.3. Programmer avec des fonctions récursives ul 1.3. Programmer avec des fonctions récursives Une fois que l'on dispose d’une définition récursive pour une fonction, il est en général assez facile de la programmer en Python. Comme nous Yavons montré pour la fonction somme(n), le code Python correspondant s‘obtient d’une maniére quasi immédiate en utilisant une conditionnelle pour distinguer les cas de base et les cas récursifs. Il faut néanmoins faire attention A deux points importants (explicités ci- aprés). Le premier est que le domaine mathématique d’une fonction, c’est-a- dire les valeurs sur lesquelles elle est définie, n’est pas toujours le méme que Vensemble des valeurs du type Python avec lesquelles elle sera appelée. Le deuxiéme point est que le choix d’une définition récursive plutét qu’une autre peut dépendre du modéle d’exécution des fonctions récursives, en particulier quand il s’agit de prendre en compte des contraintes d’efficacité. Domaine mathématique vs. type de données Le code de la fonction somme(n) présenté dans la section précédente, et rappelé ci-dessous & droite, ne se comporte pas exactement comme la fone- tion mathématique somme(n) définie récursivement, ci-dessous 4 gauche. somme(n) def sonme(n): 0 sin=0, ifn 0: n+somme(n—1) sin>0. return 0 else: return n + somme(n - 1) La principale différence est que la fonction mathématique est uniquement définie pour des entiers naturels, alors que la fonction somme(n) peut étre appelée avec un entier Python arbitraire, qui peut étre une valeur négative. Par exemple, bien que la fonction mathématique ne soit pas définie pour n= —1, l'appel somme(-1) ne provoque aucune erreur immédiate, mais il implique un appel & somme(-2), qui déclenche un appel & somme(-3), etc. Comme on le verra un peu plus loin, ce processus infini va finir par provoquer une erreur l’exécution. Pour éviter ce comportement, il y a plusieurs possibilités. La premire est de changer le test n == 0 par n <= 0. Cette solution a l’avantage de garantir la terminaison de la fonction, mais elle modifie la spécification de la fonction en renvoyant, de maniére arbitraire, la valeur 0 pour chaque appel sur un nombre négatif. Une autre solution est de restreindre les appels & la fonction somme(n) aux entiers positifs ou nuls. Pour cela, on peut utiliser une instruction assert [NSI 1", p. 124] comme ci-dessous.12 Chapitre 1. Récursivité def somme(n): assert n >= 0 if n == 0: return 0 else: return n + somme(n - 1) De cette maniére, une erreur sera déclenchée pour tout appel & somme(n) avec n < 0. Bien que cette solution soit correcte, elle n’est pas encore com- pl&tement satisfaisante. En effet, pour tout appel somme(n) avec n >= 0, chaque appel récursif commencera par faire le test associé l'instruction assert, alors que chaque valeur de n sera nécessairement positive. Une solution pour éviter ces tests inutiles est de définir deux fonctions. La premitre, sonme_bis(n), implémente la définition récursive de la fonction mathématique somme(n) sans vérifier son argument. def sonme_bis(n): if n == 0: return 0 else: return n + somme_bis(n - 1) La seconde, somme(n), est la fonction « principale » qui sera appelée par Vutilisateur. Cette fonction ne fait que vérifier (une et une seule fois) que son argument n est positif puis, si c’est le cas, elle appelle la fonction somme_bis(n). def somme(n): assert n >= 0 return somme_bis(n) Modéle d’exécution Comme nous l’avons présenté dans le volume pour la classe de pre- miére [NSI 1", chap. 23], une partie de espace mémoire d’un programme est organisée sous forme d’une pile ot sont stockés les contextes d’exécution de chaque appel de fonction. Par exemple, pour la fonction puissance (x,n) ci-dessous, def puissance(x, n): if n == 0: return 1 else: return x * puissance(x, n - 1) Vorganisation de la mémoire au début de l’appel & puissance(7,4) est représentée par une pile contenant un environnement d’exécution avec, entre1.3. Programmer avec des fonctions récursives 13 autres, un emplacement pour l’argument x initialisé A 7 et un autre pour n contenant la valeur 4. x |_7_| puissance(7, 4) L’environnement contient également d’autres valeurs (comme l’emplacement pour la valeur renvoyée par la fonction, la sauvegarde des registres, etc.) qui sont simplement représentées par des --- dans le schéma ci-dessus. Le calcul récursif de puissance(7,4) va engendrer une suite d’appels « en cascade » A la fonction puissance, que l’on peut représenter par l’arbre @appels suivant : puissance(7,4) = return 7 * puissance(7,3) | return 7 * puissance(7,2) return 7 * puissance(7,1) | return 7 * puissance(7,0) return 1 En ce qui concerne l’organisation de la pile mémoire, un environne- ment d’exécution, similaire 4 celui décrit ci-dessus, va étre alloué sur la pile pour chacun de ces appels. Ainsi, lors de l’évaluation de expression 7 * puissance(7,3), la pile d’appels contiendra deux environnements, ce- lui pour l’appel & puissance (7,4) et, juste en dessous (car l’allocation sur une pile se fait habituellement vers le bas de la mémoire), celui pour ’appel A puissance(7,3), comme décrit dans le schéma de gauche ci-dessous, oi nous n’avons indiqué que les emplacements pertinents pour notre propos. puissance(7, 4) x [7 | puissance(7, 4) puissance(7, 3) oSER x [7 | puissance(7, 0)14 Chapitre 1. Récursivité Juste aprés le dernier appel & puissance(7,0), la pile contient donc les environnements d’exécution pour les cing appels & la fonction puissance, comme représenté par le schéma de droite ci-dessus. Plus généralement, pour un appel initial puissance (x,n), il y aura n+1 environnements dans la pile. Erreurs. Malheureusement, Python limite explicitement le nombre @appels récursifs dans une fonction. Ainsi, aprés 1000 appels récursifs, Vinterpréteur Python va lever l'exception RecursionError et afficher le message d’erreur suivant : RecursionError: maximum recursion depth exceeded. Cette limite, fixée A 1000 appels récursifs, est une valeur par défaut qu'il est possible de modifier en utilisant la fonction setrecursionlimit disponible dans le module sys. Par exemple, pour passer cette limite A 2000 appels maximum, on exécutera le code Python suivant : import sys sys.setrecursionlimit (2000) Un tel changement reste cependant dérisoire lorsque on a une défini- tion récursive qui, par nature, effectue un trés grand nombre d’appels emboités. La récursion dans d'autres langages. Certains langages de program- mation, plus spécialisés que Python dans l’écriture de fonctions récur- sives, savent dans certains cas éviter de placer de trop nombreux environ- nements d’appel dans la pile. Cela leur permet dans les cas en question de s'affranchir de toute limite relative au nombre d’appels emboités. C’est le cas notamment des langages fonctionnels (voir le chapitre 5). On peut cependant utiliser une autre définition de la fonction mathéma- tique puissance(z,n) qui réduit drastiquement le nombre d’appels récursifs emboités. On peut le faire avec deux cas récursifs qui distinguent la parité de n et deux cas de base (n = 0 et n = 1), comme ci-dessous. puissance(,n) = 1 sin=0, z sin=1, carre(puissance(z,n/2)) sin > Let nest pair, x x carre(puissance(z,(n — 1)/2)) sin> et n est impair. Une implémentation possible de cette définition en Python est la sui- vante, oi l'appel a la fonction carre(x) est simplement remplacé par la1.3. Programmer avec des fonctions récursives 15 multiplication r * r et od le test de parité est réalisé par un test & zéro du reste de la division entire par 2 (soit r % 2 == 0). def puissance(x,n) : if n == return 1 elif n == return x else: r = puissance(x, n // 2) if 0% 2 == 0: return r * r else: return x *r* rT Cette fonction récursive a en effet l'avantage de diminuer largement le nombre d’appels récursifs. Pour s'en convaincre, prenons exemple de l’ap- pel puissance(7, 28). L’arbre des appels (simplifié) représenté ci-dessous montre que seuls quatre appels récursifs sont nécessaires pour effectuer le calcul. puissance(7, 28) = r = puissance(7, 14)---return r * r x = puissance(7, 7)---return r * r x = puissance(7, 3)---return 7 * r * r = puissance(7, 1)---return 7 *r #4 return 7 D’une maniére générale, il faut 1 + |logo(n)| appels pour calculer puissance(x, n) avec cette définition, c’est-d-dire un appel initial et [logo(n)| appels récursifs. Ainsi, le calcul de puissance(x, 1000) ne né- cessite que 1 + |log2(1000)} = 10 appels. A retenir. Un calcul peut étre décrit a l'aide d’une définition récur- sive. L’avantage de cette technique est que l’implémentation est souvent plus proche de la définition. L’écriture d’une fonction récursive néces- site de distinguer les cas de base, pour lesquels on peut donner un résultat facilement, et les cas récursifs, qui font appel & la définition en cours. Il faut faire attention A ce que la fonction en Python ne s’ap- plique que sur le domaine de la fonction mathématique, par exemple en utilisant linstruction assert. Enfin, il faut comprendre le modéle d’exécution des fonctions récursives pour choisir la définition qui limite le nombre d’appels récursifs.16 Chapitre 1. Récursivité Exercices Exercice 1 Donner une définition récursive qui correspond au calcul de la fonction factorielle n! définie par n! = 1 x 2x---xnsin > Oet 0! = 1, puis le code d’une fonction fact (n) qui implémente cette définition. Solution page 427 0 Exercice 2 Soit un la suite d’entiers définie par Unt1 = Un/2 si up est pair, = 3Xun+1 sinon. avec ug un entier quelconque plus grand que 1. Ecrire une fonction récursive syracuse (u_n) qui affiche les valeurs suc- cessives de la suite un tant que un est plus grand que 1. La conjecture de Syracuse affirme que, quelle que soit la valeur de uo, il existe un indice n dans la suite tel que un = 1. Cette conjecture défie toujours les mathématiciens. Solution page 427 0 Exercice 3 On considére la suite un définie par la relation de récurrence suivante, ott a et b sont des réels quelconques : aéeR sin=0 Uur= 1 bER sin=1 3up-1 t+ 2up2+5 Wn >2 Ecrire une fonction récursive serie(n, a, b) qui renvoie le n-éme terme de cette suite pour des valeurs a et b données en parameétres. Solution page 427 0 Exercice 4 Ecrire une fonction récursive boucle(i,k) qui affiche les entiers entre i et k. Par exemple, boucle(0,3) doit afficher 0 1 2 3. Solution page 428 O Exercice 5 Ecrire une fonction récursive pgcd(a, b) qui renvoie le PGCD de deux entiers a et b. Solution page 428 0 Exercice 6 Ecrire une fonction récursive nombre_de_chiffres(n) qui prend un entier positif ou nul n en argument et renvoie son nombre de chiffres. Par exemple, nombre_de_chiffres (34126) doit renvoyer 5. Solution page 428 O Exercice 7 En s'inspirant de lexercice 6, écrire une fonction récursive nombre_de_bits_1(n) qui prend un entier positif ou nul et renvoie le nombre de bits valant 1 dans la représentation binaire de n. Par exemple, nombre_de_bits_1(255) doit renvoyer 8. Solution page 428 0Exercices 17 Exercice 8 Ecrire une fonction récursive appartient(v, t, i) prenant en paramétres une valeur v, un tableau t et un entier i et renvoyant True si v apparait dans t entre Vindice i (inclus) et len (t) (exclu), et False sinon. On supposera que i est toujours compris entre 0 et len (t). Solution page 428 0 Exercice 9 Le triangle de Pascal (nommé ainsi en l’honneur du mathéma- ticien Blaise Pascal) est une présentation des coefficients binomiaux sous la forme d’un triangle défini ainsi de maniére récursive : O(n, p) = 1 sip=O0oun=p, C(n-1,p—1) +C(n—1,p) sinon. Ecrire une fonction récursive C(n,p) qui renvoie la valeur de C(n,p), puis dessiner le triangle de Pascal & l'aide d’une double boucle for en faisant varier n entre 0 et 10. Solution page 429 0 Exercice 10 La courbe de Koch est une figure qui s’obtient de manitre récursive. Le cas de base & l’ordre 0 de la récurrence est simplement le dessin d’un segment d’une certaine longueur [, comme ci-dessous (figure de gauche). Le cas récursif d’ordre n s’obtient en divisant ce segment en trois morceaux de méme longueur 1/3, puis en dessinant un triangle équilatéral dont la base est le morceau du milieu, en prenant soin de ne pas dessiner cette base. Cela forme une sorte de chapeau comme dessiné sur la figure de droite ci-dessus. On réitére ce processus & l'ordre n — 1 pour chaque segment de ce chapeau (qui sont tous de longueur 1/3). Par exemple, les courbes obtenues & l’ordre 2 et 3 sont données ci-dessous (4 gauche et & droite, respectivement). Pence aes Ecrire une fonction koch(n, 1) qui dessine avec Turtle un flocon de Koch de profondeur n A partir d’un segment de longueur 1. Solution page 429 018 Chapitre 1. Récursivité Erreurs. Considérons la tentative de réponse suivante A l'exercice 8 page 17, A savoir l’écriture d’une fonction récursive testant la présence d’une valeur v dans un tableau t A un indice supérieur ou égal a i. def appartient(v, t, i): if i == len(t): return False elif tli) vi return True else: appartient(v, t, i + 1) Si 4 a dépassé le dernier indice du tableau, alors la fonction renvoie False. Si au contraire la case d’indice i contient la valeur cherchée, alors la fonction renvoie True. Dans les autres cas enfin, la fonction procéde A un appel récursif poursuivant la recherche a partir de l'indice i + 4. Cette fonction donnera parfois les bons résultats. >>> appartient(3, [], 0) False >>> appartient(3, [3], 0) True Elle renverra cependant le plus souvent None. >>> appartient(3, [1, 2, 3, 4], 0: None >>> appartient(3, [1, 2], 0) None Ceci tient A Voubli du mot-clé return dans le troisiéme cas. En effet, en Python toute fonction doit utiliser return & chaque endroit oi elle renvoie un résultat, et cela vaut y compris lorsque ce résultat n’est que la transmission du résultat d’un appel récursif. Sans return, l’appel récursif est effectué mais son résultat est oublié sitét obtenu et la fonction en définitive ne renvoie rien, ou plutét elle renvoie None, c’est-i-dire la valeur traduisant habituellement l’absence de résultat. Cette erreur peut atre délicate A détecter si notre fonction appartient n’est pas testée ainsi de maniére isolée, puisque dans un branchement tel que if appartient(v, t, i): Yobtention de la valeur None serait interprétée comme False et ne pro- voquerait pas d’erreur immédiate.Chapitre 2 Modularité Notions introduites © modules et: interfaces © encapsulation © réutilisation de code « lever et rattraper des exceptions Le développement d’un grand programme demande une certaine organi- sation, et en particulier un découpage des différents aspects du programme et des différentes taches qui doivent étre accomplies. Ceci est d’autant plus vrai lorsque plusieurs personnes participent au développement. Parmi ces questions relevant du génie logiciel (« génie », au sens d’ingénierie), nous nous intéressons dans ce chapitre & la maniére dont les différentes parties dun programme peuvent s’articuler. L’un des objectifs consiste a spécifier le rdle de chaque partie suffisamment précisément pour que chacune puisse ensuite étre réalisée indépendamment des autres. 2.1 Variations sur les ensembles « Te souviens-tu l’année derniére, Basile, le paradoxe des anniversaires ? — L’anecdote qui nous disait que dans une classe, il y avait plus d’une chance sur deux pour que deux éléves aient leur anniversaire le méme jour? — Oui, il suffisait méme de 23 personnes pour cela. — En loccurrence notre classe était un contre-exemple, mais on avait écrit un petit programme permettant de vérifier cette statistique [NSI 1", 14.1]. Il n’était méme pas trés compliqué, il suffisait d’utiliser sur des tableaux de 23 éléments aléatoires la fonction suivante qui vérifie si un tableau contient un élément en double.20 Chapitre 2. Modularité def contient_doublon(t: """le tableau t contient-il un doublon"”" s = set() for x in t: if x ins: return True s.add(x) return False On passe tous les éléments en revue et on les stocke & la volée dans un ensemble s, jusqu’s trouver un élément déja présent dans cet ensemble, c’est-a-dire qui apparaissait déja plus tot dans le tableau. — La fonction a l'air simple, je suis d’accord, mais cette structure set est une chose que l'on n’a finalement que trés peu utilisée dans l'année, et je ne sais toujours pas bien ce qu’elle cache. Tu penses qu’on arriverait & écrire une nouvelle version de cette fonction avec uniquement les éléments de base que l’on utilisait tout le temps? Par exemple des tableaux, des entiers, des booléens ? — Nous allons voir. Tu as déja une idée en téte? — Pas encore. Mais commencons par les choses les plus simples, nous verrons oi cela nous méne. » Deux approches rudimentaires « Si par exemple nous utilisions un simple tableau pour s comme dans le programme 1. C’est trés simple, et l'opération append est efficace. Le pro- bléme vient seulement du test x in s dont le temps d’exécution est le plus souvent proportionnel au nombre d’éléments stockés dans s. — On peut améliorer cela avec une recherche dichotomique si le tableau est trié, non? C’est extrémement efficace! — Oui mais, pour s’assurer que le tableau est bien toujours trié, Yopération append ne suffirait plus pour ajouter un nouvel élément : il faudrait linsérer au bon endroit et décaler tous les suivants. A nouveau, le coiit serait géné- ralement proportionnel au nombre d’éléments dans le tableau. — Joublie toujours ce cofit caché de l’insertion. Je me demande si l'on connaitra un jour une structure suffisamment ordonnée pour faire une sorte de recherche dichotomique dessus, et dans laquelle on peut insérer des élé- ments au bon endroit pour un cofit qui ne soit pas prohibitif. — En tout cas, ce serait neuf!! — Passons, j’ai une autre approche trés simple pour laquelle le coat du test est minimal. Regarde le programme 2, Alice, on y prend un grand tableau de booléens, un pour chaque date possible, et on décide que s [x] vaut True si on a enregistré x dans s et False sinon. Pour des dates représentées par 1. En loccurrence, chapitre 9.2.1. Variations sur les ensembles 21 Programme 1 — rechercher un doublon dans un tableau def contient_doublon(t): """le tableau t contient-il un doublon ?”"" s=O0 for x in t: if x ins: return True 8. append (x) return False Programme 2 — rechercher un doublon dans un tableau def contient_doublon(t): """le tableau t contient-il un doublon 7""" s = [False] * 367 for x in t: if s[x]: return True s(x] = True return False des entiers entre 1 et 366, on peut méme prendre un tableau de 367 cases et laisser tomber celle d’indice 0. — Pas mal, mais je trouve dommage de prendre un tableau de 367 cases si Vensemble typique que l’on doit représenter dans notre application n’a pas plus de 23 éléments. » Représentation plus compacte : le tableau de bits « ILest surtout dommage que les booléens occupent autant d’espace en mémoire que des nombres entiers (au moins 8 octets, 64 bits!), alors qu’un seul bit est réellement utile pour choisir entre les deux valeurs True et False. Ce tableau est 64 fois trop grand! — Saurions-nous compacter cela? Par exemple en utilisant des entiers pour représenter plusieurs booléens? Apres tout, la représentation des entiers en machine est une suite de bits (0 ou 1!) basée sur leur écriture en base 2, et il existe & cété des opérations arithmétiques classiques des opérations qui agissent directement sur cette représentation binaire. Par exemple, l’opéra-22 Chapitre 2, Modularité tion | de « ou » bit a bit renvoie l’entier pour lequel chaque bit vaut 1 dés lors qu'il valait 1 dans au moins l'un des paramétres : si je prends 40 qui s’écrit, en binaire 101000 et 10 qui s’écrit en binaire 1010 (ou 001010 si j’ajoute des zéros pour avoir le méme nombre de chiffres), lopération 40 | 10 me renvoie l'entier dont l’écriture binaire est 101010, c’est-a-dire 42. — Bonne idée, essayons. Considérons qu’un entier s de 64 bits repré- sente un tableau b de 64 booléens, avec comme clé de lecture que b[x] vaut True si et seulement si le bit de rang x de s vaut 1. Ainsi l’en- tier 26, qui s’écrit en binaire 0. . 011010, représente le tableau de boo- léens [False, True, False, True, True, False, ..., False], autre- ment dit l’ensemble {1,3,4}. Alors je peux utiliser lentier 2*, qui a tous ses bits & 0 sauf le bit de rang x qui vaut 1, comme révélateur. On cal- cule 2* avec l’opération de décalage 1 << x. Si je fais un « ou » bit a bit s | (1 << x) je fais passer le bit de rang x de s a 1 (et il y reste s'il y était déja). Si en revanche je fais un « et » bit a bit s & (1 << x) j’obtiens soit 2* si b[x] vaut True, soit 0 sinon. Avec ces ingrédients, on pourrait obtenir le programme 3. En plus, c’est particuligrement facile a écrire en Python, les entiers n’étant méme pas limités A 64 bits. — Et sans ces entiers illimités on pourrait aussi utiliser un tableau d’entiers ordinaires. On décompose x sous la forme x = i + 647 avec les opérations de quotient et de reste de la division entiére et on fait correspondre a x le bit de rang i de V'entier d’indice j. Ce serait peut-étre méme encore plus efficace, et transposable & n’importe quel autre langage de programmation. Le code est & peine plus compliqué, il s’exécute aussi vite, et on gagne un facteur 64 en occupation de la mémoire par rapport au tableau de booléens. On progresse! — Pour notre cas d’application effectivement il suffirait alors d’un tableau de six entiers pour représenter n’importe quel ensemble de dates d’anni- versaires, comme dans le programme 4. Dans ce cas précis, cela m’a l’air d’étre imbattable. Cependant, si on ne parle plus de jours de l'année et que Vamplitude des éléments auxquels on s’intéresse est bien plus grande que Vintervalle [1,366], ce facteur 64 gagné finira par devenir dérisoire. » Structure de tableau de bits. La représentation des ensembles déve- loppée dans les programmes 3 et 4 donne les idées essentielles de la structure de tableau de bits (en anglais bit array ou bit set). Cette structure donne une représentation compacte d’un ensemble de booléens. Elle permet donc une meilleure utilisation des ressources de mémoire limitées comme la mémoire cache, cette mémoire accessible beaucoup plus rapidement que la mémoire vive de ordinateur et conser- vant temporairement les derniers éléments consultés.2.1. Variations sur les ensembles 23 Programme 3 — rechercher un doublon dans un tableau def contient_doublon(t): """le tableau t contient-il un doublon 7""" s=0 for x in t: if s & (1 << x) != 0: return True s=sl (1 len(s[’paquets’]): etend(s) -ajoute_aux(s[’paquets’], x) det ~ajoute_aux(t, x): p =x % len(t) t[p] -append(x) det etend(s): tmp = [[] for _ in range(2 * len(s[’paquets’]))] for x in enumere(s): ajoute_aux(tmp, x) s[’paquets’] = tmp det enumere(s): tab = [] for paquet in s[’paquets’]: tab. extend(paquet) return tab2.2. Modules, interfaces et encapsulation 33 Encapsulation en Python. En Python, l’auteur d’un module peut in- diquer que certains éléments (variables globales ou fonctions) sont privés en faisant commencer leur nom par le symbole _. Par convention, tous les autres éléments sont « publics » et doivent étre compris comme ap- partenant & l’interface. Il faut cependant savoir que dans ce langage, encapsulation est une pure convention (certains disent, un voeu pieux), et son respect est sous la seule responsabilité des programmeurs des modules clients. Rien dans les mécanismes du langage n’empéche l’acc’s aux éléments privés, ni leur utilisation, ni leur modification. De nombreux autres langages de programmation, mieux adaptés aux projets & grande échelle, introduisent en revanche un contréle strict de Pencapsulation en rendant V'accés aux éléments privés trés compliqué voire impossible. Tables de hachage. Le programme 10 ébauche la structure de don- nées fondamentale de table de hachage, sous-jacente aux ensembles et aux dictionnaires de Python. Cette structure trés polyvalente permet de représenter des ensembles de taille arbitraire, avec des opérations d’ac- cés aux éléments extrémement rapides. Elle est considérée comme la plus efficace dans la plus grande variété des cas courants. Le principal élément manquant pour obtenir une vraie table de hachage est une fonction appelée fonction de hachage, qui prend en paramétre Vélément & stocker et renvoie un nombre entier définissant (modulo le nombre de paquets) le numéro du paquet dans lequel insérer I’élément. Via cette fonction de codage de l’élément a stocker, on peut done utili- ser une table de hachage pour représenter des ensembles d’éléments de toutes sortes, et pas seulement des ensembles d’entiers. En outre, une fonction de hachage est souvent utilisée méme pour les tables stockant des entiers, afin de mélanger les éléments et éviter que des nombres liés les uns aux autres (par exemple, des multiples) ne se retrouvent systé- matiquement dans le méme paquet. Dans le cas des nombres entiers, on pourra par exemple utiliser des multiplications par des grands nombres + premiers combinées & des rotations de la représentation binaire. L’équité de la répartition des éléments dans les différents paquets, et donc l’ef- ficacité de cette structure de données, dépend de la qualité du mélange opéré par cette fonction de hachage. Mais avec une fonction de hachage convenable, on peut en pratique considérer que la recherche ou l’ajout d’un élément dans une table de hachage sont des opérations instantanées.34 Chapitre 2, Modularité 2.3 Exceptions Manipuler les fonctionnalités d’un module en n’utilisant que les fonctions fournies par son interface permet de ne pas se soucier des détails d’implé- mentation de ce module. Du moins tant que tout se passe bien. Erreurs. Considérons le module dates du programme 6, et essayons d’ajouter 4 un ensemble une date invalide. >>> import dates >>> s = dates.cree() >>> dates.ajoute(s, 421) Traceback (most recent call last): File "", line 1, in File "~/lib/dates.py", line 12, in ajoute s[paquet] = s[paquet] | (1 << bit) IndexError: list index out of range Le message d’erreur est faicheux pour plusieurs raisons : ¢ il mentionne une IndexError, alors que nous ne voulions pas savoir que cette structure utilisait en interne un tableau; © pire, la ligne de code fournie ne permet en rien de comprendre le dépassement de tableau : elle mentionne un tableau s dont on ne connait pas la longueur, et un indice paquet dont on ne connait pas le lien avec les paramétres s et 421 fournis A ajoute. Comprendre en détail cette erreur demande d’explorer le code du module dates, ce qui fait perdre une partie des bénéfices de l’encapsulation. Remarquez que, plus sournoisement, d'autres dates invalides n’auraient pas déclenché d’erreur. >>> dates.ajoute(s, 377) >>> dates.ajoute(s, -383) Mais quelles dates auraient été ainsi ajoutées? Les six entiers de notre tableau fournissent au total 384 bits, dont nous n’utilisons que les numéros 1 & 366 (le numéro 0 est ignoré pour simplifier les calculs). L'ajout de 377 se fait sur un des bits inutilisés du dernier entier du tableau, qui ne correspond & aucune date particuliére. L'ajout de -383 en revanche touche le bit du premier janvier. En V’état actuel des modules définis dans ce chapitre, une mauvaise ut sation des fonctions de interface risque d’engendrer des erreurs ou des effets23. Exceptions 35 collatéraux qui ne peuvent étre compris et anticipés sans une connaissance approfondie du code de ces modules. Ceci contredit le principe d’encapsula- tion. Une meilleure pratique consiste, lors du développement de nos modules, & renvoyer 'utilisateur des erreurs explicites, qui peuvent étre interprétées & Paide de la seule connaissance de l'interface. Cette pratique approfondit la notion de programmation défensive évoquée dans le volume précédent [NST 1, 9.3). Signaler un probléme avec une exception Nous avons déja pu observer A de nombreuses reprises des programmes s'interrompre avec des messages d’erreurs variés. De telles « erreurs » sont Erreurs. >>> t = [1, 1, 2, 5, 14, 42, 132) >>> t[12] Traceback (most recent call last): File "", line 1, in IndexError: list index out of range appelées en programmation des exceptions et correspondent A la détection, ici faite par l'interpréte Python lui-méme, d’un probleme empéchant la bonne exécution du programme. Lorsqu’une exception survient, l'exécution du programme est interrompue sur le champ, & moins d’une prise en charge spécifique que nous verrons plus loin dans cette section. Le tableau suivant redonne quelques exceptions courantes, observables en utilisant les structures de base de Python. Eco Pd NameError accés & une variable inexistante IndexError accés & un indice invalide d’un tableau KeyError 4 une clé inexistante d’un dictionnaire ZeroDivisionError | division par zéro TypeError opération appliquée a des valeurs incompatibles Ilest possible de déclencher directement toutes ces exceptions (on dit « lever une exception ») avec ’opération raise de Python. >>> raise IndexError(’indice trop grand’) Traceback (most recent call last): File "", line 1, in IndexError: indice trop grand36 Chapitre 2. Modularité Cette opération s’écrit en faisant suivre le mot-clé raise du nom de l’ex- ception a lever, lui-méme suivi entre parenthéses d’une chaine de caractéres donnant des informations sur erreur signalée. On peut ainsi définir par exemple une fonction ecrit(t, i, v) destinée & remplacer l’opération primitive t{i] = v de modification de la valeur d’une case d’un tableau pour empécher tout accés involontaire & un indice négatif?. def ecrit(t, i, v): if i 366: return False paquet = x // 64 bit = x % 64 return s[paquet] & (1 << bit) !=0 def ajoute(s, x): if x < 1 or x > 366 raise ValueError("date "+ str(x) + " invalide") paquet = x // 64 bit =x % 64 s(paquet] = s[paquet] | (1 << bit) L’exception ValueError de Python est a utiliser dans les cas oi un para- métre inadapté est donné & une fonction. C'est ici le cas lorsque le para- metre x de la fonction ajoute est un nombre qui n’est pas dans la plage représentant une date valide. Pour se conformer & cette interface, le programme 6 peut étre complété sous la forme du programme 11. La fonction ajoute commence par vérifier la valeur de x, et léve une exception en cas de probléme. Le message associé précise la valeur de x qui a posé probléme. Notez que la fonction contient ne lve pas d’exception en cas de date invalide. Elle se contente alors de renvoyer False. Rattraper une exception Les exceptions levées par un programme peuvent avoir plusieurs causes. Certaines traduisent des erreurs du programme : elles sont imprévues et leurs conséquences ne sont par définition pas maitrisées. Dans ces conditions, interrompre l’exécution du programme est légitime. D’autre exceptions, en revanche, s’inscrivent dans le fonctionnement normal du programme : elles correspondent 4 des situations connues, exceptionnelles mais possibles. Dans cette ligne de code, par exemple, il est tout & fait envisageable que la chaine de caractéres entrée par l'utilisateur ne représente pas un entier valide. x = int(input("Entrer un jour"))38 Chapitre 2, Modularité Dans ce cas, la fonction int léve une exception ValueError, de méme que notre fonction ajoute du programme 11 lorsque l’entier fourni n’est pas dans la plage de valeurs attendue. Une telle exception, qui correspond a un événement prévisible, n’est pas forcément fatale. Certes le programme ne peut pas poursuivre son exécution comme si de rien n’était, puisque certaines choses n’ont pas eu lieu norma- lement : sur cet exemple, la variable x n’aurait pas été définie. Cependant, en tant que programmeur, on peut anticiper cette éventualité et prévoir un comportement alternatif du programme pour cette situation exceptionnelle. Dans le cas présent, on pourrait par exemple demander & nouveau un jour & Putilisateur, aprés avoir affiché un message précisant le format attendu. Pour mettre en place ce comportement alternatif, il faut rattraper cette exception, c’est-a-dire l'intercepter avant que ’exécution du programme ne soit définitivement abandonnée, avec la construction suivante. try: x = int(input("Entrer un jour")) except ValueError: print ("Priére d’entrer un entier valide") Le mot-clé try suivi du symbole : (deux-points) introduit un premier bloc de code, puis le mot-clé except suivi du nom de l’exception et du symbole : précéde un deuxiéme bloc de code. On qualifiera le premier bloc de normal et le second d’alternatif. L’exécution d’une telle instruction procéde comme suit. On exécute d’abord le bloc de code normal. Si l’exécution de ce bloc s’achéve normale- ment, sans lever d’exception, alors le bloc alternatif est ignoré et on passe directement aux instructions suivantes. Si a l’inverse une exception est levée dans l’exécution du bloc normal, alors l’exécution de ce bloc est immédia- tement interrompue et le nom de l'exception levée est comparé avec le nom précisé & la ligne except. Si les noms correspondent, l’exception est rattrapée et on exécute le bloc de code alternatif avant de passer a la suite. Sinon, Yexception est propagée et le programme s’interrompt, & moins que le frag- ment de code considéré soit lui-méme inclus dans une autre construction try /except qui pourra a son tour tenter de rattraper l'exception. Un fragment de code ajoutant une date saisie par un utilisateur un ensemble s pourra ainsi avoir la forme suivante. while True: try: x = int (input (“Entrer un jour")) dates.ajoute(s, x) break except ValueError: print("I1 faut un nombre entier entre 1 et 366")2.3. Exceptions 39 Notez que int et ajoute sont toutes deux susceptibles de lever une exception ValueError : la premiére si la saisie n’est pas un nombre entier et la seconde si’entier saisi n’est pas dans la bonne plage. Toutes deux sont rattrapées par notre bloc alternatif. Si en revanche la valeur saisie convient, alors l’exécution du bloc try s’achéve avec l’instruction break qui met fin a la boucle infinie. Alternatives multiples. Si l’on prévoit que plusieurs exceptions peuvent étre rattrapées, il est possible d’écrire plusieurs blocs alternatifs, chacun associé & sa ligne except. try: except Exception1: except Exception2: Notez que seules les exceptions levées lors de lexécution du bloc normal peuvent étre rattrapées : les exceptions du premier bloc alternatif ne sont jamais rattrapées par les blocs alternatifs suivants. Autrement dit, les exceptions levées par un bloc alternatif ne peuvent étre rattrapées que par une autre construction try /except englobante. Rattrapage indiscriminé. Si I’on ne précise pas de nom d’exception aprés except, alors toutes les exceptions seront rattrapées par ce bloc alternatif. try: quelque_chose_de_dangereux() except: boit_elixir_du_docteur_Doxey() C’est généralement une mauvaise idée, car on rattrape alors A la fois les exceptions qu'il est légitime de rattraper et celles qui traduisent des erreurs que l’on ne soupconnait pas. Ce faisant, on efface donc les traces _ de ces éventuelles erreurs et on complique leur diagnostic. Un cas d’usage légitime du rattrapage indiscriminé consisterait & fournir quelques informations sur le contexte de l'exception, par un affichage ou une écriture dans un fichier journal, avant de relancer la propagation de l'exception. On peut réaliser ce redémarrage de la propagation en utilisant le mot-clé raise sans paramdtre dans le bloc alternatif.40 Chapitre 2. Modularité Aretenir. Un grand programme est décomposé en plusieurs modules, dont chacun est dédié & la réalisation de taches précises. L’interface d'un module décrit ensemble des fonctions offertes par ce module, aux- quelles peuvent faire appel d’autres modules clients. Ces modules clients ne sont pas concernés par la maniére précise dont: chaque fonction ou structure est effectivement réalisée. Avec ce principe d’encapsulation, la connaissance de l’interface suffit pour utiliser convenablement un mo- dule, ce qui épargne au programmeur le besoin de lire et comprendre la totalité du code des modules tiers qu’il utilise. En outre, ce méme principe donne un cadre au développeur d’un module pour modifier, corriger ou améliorer son programme sans risquer de nuire aux autres programmes utilisant ce module. On complete l’encapsulation d’un mo- dule en gérant explicitement & l'aide d’exceptions les utilisations non conformes de son interface. Exercices Exercice 11 Ecrire un module réalisant l’interface 1 suivant la stratégie du programme 1. Solution page 429 0 Exercice 12 Ecrire un module réalisant l’interface 1 suivant la stratégie du programme 3. Attention : pour que la fonction ajoute fonctionne, il faut pouvoir modifier Vensemble. Solution page 429 0 Exercice 13 Supposons que I’on veuille ajouter a V’interface des ensembles la fonction enumere déja présente par exemple dans le programme 9. Adapter Ie module du programme 6 pour qu’il réalise cette interface étendue. Solution page 430 0 Exercice 14 Supposons que I’on veuille ajouter 4 l’interface des ensembles Jes deux fonctions d’union et d’intersection suivantes. certton union(si, 52) Tenvoie un nouvel ensemble composé de Punion des éléments de s; et s2 intersection(s;, 82) | renvoie un nouvel ensemble composé de |’in- tersection des éléments de 8) et s2 Précisons que ces fonctions ne doivent pas modifier les ensembles s1 et 52 qui leur sont donnés en paramétres. 1. Réaliser ces fonctions dans le module de l’exercice 11. 2. Réaliser ces fonctions dans le module du programme 6. Solution page 430 0Exercices 4l Exercice 15 Certaines réalisations des ensembles d’entiers vues dans ce cha- pitre représentent plus précisément des ensembles d’entiers compris entre 0 et un certain entier maximum nmaz- Lesquelles? Comment était décidé Nmaz? Que changer & Vinterface de ces programmes pour permettre a luti- lisateur de choisir nmaz? Solution page 431 0 Exercice 16 Les modules décrits par chacun des programmes 6, 9 et 10 réa- lisent tous interface 1 et peuvent donc tous étre utilisés par le programme 8. Pour autant, l’un est-il préférable aux autres pour cette application parti- culitre? Solution page 431 0 Exercice 17 Considérons une structure de table de hachage telle que réalisée par le programme 10 mais avec seulement 8 paquets. On place dedans les entiers 0, 1, 4, 9, 13, 24 et 30. Donner le contenu de chacun des paquets. Solution page 431 0 Exercice 18 L’interface des tableaux de Python fournit de nombreuses opé- rations a ’allure anodine mais cachant une complexité non négligeable. Rien de tel que d’essayer de réaliser soi-méme ces fonctions pour s’en rendre compte. Ecrire un module réalisant |’interface suivante tranche(t, i, j) renvoie un nouveau tableau contenant les éléments de t de l’indice i inclus 4 l’indice j exclu (et le tableau vide si j < é) concatenation(t,, 2) | renvoie un nouveau tableau contenant, dans ordre, les éléments de t; puis les éléments de tz sans utiliser les opérations + et t[i:j] du langage. Notez qu’aucune de ces fonctions ne doit modifier les tableaux passés en paramétres. Solution page 431 0 Exercice 19 Les tableaux de Python sont redimensionnables : leur nombre d’éléments peut augmenter au fil du temps, par exemple avec des opérations comme append. L’objectif de cet exercice est de définir un module réalisant une interface de tableau redimensionnable, mais sans utiliser les capacités de redimensionnement natives des tableaux Python. Voici une interface minimale pour une structure de tableau redimension- nable.42 Chapitre 2. Modularité cree() crée et renvoie un tableau vide lit(tr, renvoie élément de tr & l'indice i ecrit(tr, i, 2) | place la valeur « dans la case d’indice i du ta- bleau tr ajoute(tr, 2) | ajoute le nouvel élément ¢ au tableau tr, aprés ses éléments actuels Notez que ces opérations sont équivalentes aux opérations (J, ér[é], ér[é] = 1 et tr.append(x) des tableaux de Python. Pour réaliser cette interface, on va représenter un tableau redimension- nable tr de n éléments par une paire nommée contenant d’une part ce nombre n et d’autre part un tableau Python ¢ dont la longueur est su- périeure ou égale A n. Le nombre n sera appelé la taille de tr et la longueur de t sa capacité. Les n éléments sont stockés dans les cases d’indices 04 n-1 du tableau t, tandis que les cases suivantes contiennent None. 1. Ecrire une fonction cree() créant et renvoyant un tableau redimen- sionnable de taille 0 et de capacité 8. 2. Ecrire deux fonctions 1it(tr, i) et ecrit(tr, i, x) telles que dé- crites dans l’interface, en supposant que l’indice i fourni est bien com- pris entre 0 inclus et la taille de tr exclue. 3. Fonction ajoute. (a) Ecrire une fonction _ajoute_aux(tr, 2) qui ajoute l’élément x 4 la fin du tableau redimensionnable ¢r, en supposant que la ca- pacité de ce dernier est suffisante. (b) Ecrire une fonction _double(tr) qui double la capacité du ta- bleau redimensionnable ér, en conservant ses éléments. (c) En déduire une fonction ajoute(tr, x) telle que décrite dans Vinterface. Cette fonction doit doubler la capacité du tableau re- dimensionnable lorsqu’il ne peut accueillir de nouvel élément. Autres opérations qui pourraient étre ajoutées : pop, del, insert, extend. Solution page 432 0 Exercice 20 Voici une interface minimale pour une structure de dictionnaire. co ce n cree() crée et renvoie un dictionnaire vide cle(d, k) renvoie True si et seulement si le dictionnaire d contient la clé k lit(d, k) renvoie la valeur associée a la clé k dans le dic- tionnaire d, et None si la clé k n’apparait pas ecrit(d, k, v) | ajoute au dictionnaire d l'association entre la clé k et la valeur v, en remplagant une éventuelle association déja présente pour kExercices 43 On propose de réaliser cette interface de dictionnaire avec un tableau de couples clé-valeur, en faisant en sorte qu’aucune clé n’apparaisse deux fois. 1. Ecrire un module réalisant cela. 2. La description de l'une des quatre fonctions de notre interface ne cor- respond pas exactement a l’opération équivalente des dictionnaires de Python. Laquelle? Quelle expérience faire pour le confirmer? Corri- ger la description pour se rapprocher de celle de Python et adapter la réalisation. Solution page 432 0Chapitre 3 Programmation objet Notions introduites e définition de classes © création et manipulation d’objets ¢ attributs et méthodes Nous avons évoqué au chapitre précédent l’intérét de définir et identi- fier certaines structures de données composées de plusieurs éléments, par exemple avec la table de hachage pour laquelle nous avions besoin de mé- moriser & la fois un tableau de paquets et un entier représentant le nombre total d’éléments. Revenons sur les différents moyens de représenter une telle structure composite en Python. © Le couple, cas particulier de n-uplet pour n valant 2, permet effecti- vement de regrouper deux éléments de types distincts mais n’autorise pas la modification des éléments. En l’occurrence on pourrait modifier le contenu du tableau de paquets (cela ne change pas l’identité de ce tableau) mais pas modifier l’entier représentant la taille. © Le tableau permet de regrouper une séquence d’éléments et autorise la modification, mais nous avons invariablement recommandé de n’en faire qu’une utilisation homogéne (un méme type pour tous les élé- ments contenus). Le regroupement d’un tableau et d’un entier est in- compatible avec cette discipline. « Les n-uplets nommés sont une approche tout & fait adaptée. Cepen- dant, réaliser un n-uplet nommé & l'aide d’un dictionnaire ({NSI 1°, 14]) n'est. pas l’approche la plus idiomatique, ni en Python ni dans d’autres langages majeurs, chacun offrant pour cela des mécanismes plus intégrés.46 Chapitre 3. Programmation objet Le paradigme de programmation objet, qui est intégré A Python et que nous allons présenter dans ce chapitre, fournit une notion de classe, qui permet a la fois de définir (et nommer) des structures de données composites, et de structurer le code d’un programme. 3.1 Classes et attributs : structurer les données Une classe définit et nomme une structure de données qui vient s’ajouter aux structures de base du langage. La structure définie par une classe peut, regrouper plusieurs composantes de natures variées. Chacune de ces compo- santes est appelée un attribut (on dit aussi un champ ou une propriété) et est dotée d’un nom. Description d’une classe Supposons que l’on souhaite manipuler des triplets d’entiers représen- tant des temps mesurés en heures, minutes et secondes. On appellera la structure correspondante Chrono. Les trois nombres pourront étre appelés, dans lordre, heures, minutes et secondes, et nous pourrions nous figurer le temps « 21 heures, 34 minutes et 55 secondes » comme un triplet nommé correspondant a la représentation graphique suivante. houres| 21 minutes | 34 secondes | 55 Un triplet donné associe ainsi chacun des noms heures, minutes et secondes A un nombre entier. La structure Chrono elle-méme peut alors étre pensée comme le cas particulier des n-uplets nommés possédant exactement. trois composantes nommées respectivement heures, minutes et secondes. Python permet la définition de cette structure Chrono sous la forme d’une classe avec le code suivant. class Chrono: """une classe pour représenter un temps mesuré en heures, minutes et secondes""” def __init__(self, h, m, s): self.heures = h self.minutes = m self.secondes = s La définition d’une nouvelle classe est introduite par le mot-clé class, suivi du nom choisi pour la classe et d’un symbole : (deux-points). Le nom de la classe commence par une lettre majuscule. Tout le reste de la définition est alors placé en retrait. Nous avons en occurrence dans cet exemple une3.1. Classes et attributs : structurer les données 47 chaine de documentation décrivant la classe et la définition d’une fonction ~-init__ dont nous détaillerons la construction a la section 3.2. Notons pour l'instant simplement sa forme, a savoir qu’elle poss8de un premier pa- rametre appelé self, trois paramétres correspondant aux trois composantes de notre triplet, ainsi que trois instructions de la forme self.a respondant de méme aux trois composantes (et en l’occurrence, affectant & chaque attribut sa valeur). + cor Création d'un objet Une fois une telle classe définie, un élément correspondant a la structure Chrono peut étre construit avec une expression de la forme Chrono(h, m, s). On appelle un tel élément un objet ou une instance de la classe Chrono. On peut ainsi définir et affecter la variable t un objet représentant notre temps « 21 heures, 34 minutes et 55 secondes » avec la ligne suivante. >>> t = Chrono(21, 34, 55) Tout s’écrit comme si le nom de la classe était également une fonction at- tendant trois paramétres et construisant l’élément correspondant. Notez que, comme c’était le cas pour les tableaux, la variable t ne contient pas & strictement parler objet qui vient d’étre construit, mais un pointeur vers le bloc de mémoire qui a été alloué a cet objet. La situation correspond done au schéma suivant. heures| 21 minutes | 34 secondes| 55 En outre, comme le suggére ce schéma, Pobjet mémorise d’une maniére ou Yautre son appartenance a la classe Chrono. Manipulation des attributs On peut accéder aux attributs d’un objet t de la classe Chrono avec la notation t.a oi a désigne le nom de I’attribut visé. Les attributs, comme Jes cases d’un tableau, sont mutables en Python : on peut non seulement consulter leur valeur mais aussi la modifier. >>> t.secondes 55 >>> t.secondes = t.secondes + 1 >>> t.secondes 5648 Chapitre 3. Programmation objet Notez que l'on a parlé dans le paragraphe précédent « d’attribut d’un objet ». En effet, bien que les noms des attributs soient attachés A une classe, chaque objet possdde pour ses attributs des valeurs qui lui sont propres. C’est pour- quoi on parle parfois aussi d’attributs d’instance. Ainsi, chaque objet de la classe Chrono posséde bien trois attributs heures, minutes et secondes, dont les valeurs sont indépendantes des valeurs des attributs de méme nom des autres instances. Les deux définitions t = Chrono(21, 34, 55) et u = Chrono(5, 8, 13) conduisent donc a la situation suivante. +(-}-—_—[aaag] 0 heures| 21 ninutes| 34 secondes| 55 Les valeurs des attributs d’un objet pouvant varier, on les comprend parfois comme décrivant l’état de cet objet. Avec ce point de vue, un changement des valeurs des attributs d’un objet correspond alors 4 l’évolution de cet objet. Une avancée de cing secondes du chronométre t ménerait ainsi a la situation suivante. ec) of} a] ures 5 ales secondes| 13 Erreurs. I] n’est évidemment pas possible d’obtenir la valeur d’un at- tribut inexistant. >>> t.x Traceback (most recent call last): File "", line 1, in AttributeError: ’Chrono’ object has no attribute ’x’ De fagon plus surprenante, rien n’empéche en Python d’affecter par mé- garde une valeur 4 un attribut n’appartenant pas a la classe de V’objet. >>> t.x = 89 >>> (t.heures, t.minutes, t.secondes, t.x) (21, 34, 55, 89) Voir A ce propos l’encadré « spécificités des attributs en Python » ci- dessous.3.1. Classes et attributs : structurer les données 49 Spécificités des attributs en Python. La structure des objets en Py- thon ne correspond pas tout A fait & la pratique usuelle de la program- mation objet. Dans le paradigme objet habituel, une classe introduit un ensemble d’attributs, définissant la totalité des attributs que possédera chaque instance de cette classe. C’est cette situation que nous décrivons dans ce chapitre et que nous utiliserons dans le reste de Pouvrage. En Python, cependant, les attributs ne sont pas récllement introduits au niveau de la classe. Plutét, chaque affectation d’un attribut & un objet crée cet attribut pour cet objet particulier. Dans la terminologie de Python, ces « attributs » s’appellent ainsi des variables d’instance. Python permet donc techniquement que deux objets d’une méme classe possédent des attributs n’ayant aucun rapport les uns avec les autres. Utilisée sans discernement, cette possibilité est évidemment une source inépuisable d’erreurs. Pour rester dans le cadre habituel de la program- mation objet, on s'imposera done la discipline suivante en Python : que chaque objet au moment de sa création se voie doté des attributs prévus pour sa classe, et qu’aucun autre attribut ne lui soit ajouté par la suite. Attributs de classe. Une classe peut également définir des attributs de classe, dont la valeur est attachée a la classe elle-méme. class Chrono: heure_max = 24 On peut consulter de tels attributs depuis n’importe quelle instance, ou depuis la classe elle-méme. >>> t = Chrono(21, 34, 55) >>> (t.heure_max, Chrono.heure_max) (24, 24) On peut également modifier cet attribut en y accédant via la classe elle- méme pour que la modification soit. perceptible par toutes les instances présentes ou futures. >>> Chrono.heure_max = 12 >>> t.heure_max 12 En revanche, un tel attribut n’est pas destiné 4 étre modifié depuis une instance (techniquement cela ne ferait que créer une variable d’instance du méme nom, pour cette seule instance, qui serait done décorrélée de Pattribut de classe).50 Chapitre 3. Programmation objet Retour sur les tables de hachage Le programme 10 utilisait un n-uplet nommé pour regrouper la table des paquets et la taille d’une table de hachage. On utilisera plus couramment & la place une classe munie de deux attributs, dont les valeurs initiales sont fixes et n’ont donc pas besoin d’étre passées & la fonction __init__. class Ensemble: def __init__(self): self.taille 0 self.paquets = [[] for _ in range(32)] La fonction de création d’une table de hachage vide se contente alors de créer une nouvelle instance de la classe Ensemble. def cree(): return Ensemble() On pourrait également adapter chacune des fonctions écrites pour les n- uplets nommés & cette nouvelle organisation de la structure de données. La fonction contient par exemple s’écrirait ainsi. def contient(s, x): p= x % len(s.paquets) return x in s.paquets[p] Cette manitre d’écrire des fonctions manipulant des objets fonctionne par- faitement dans le cadre du programme de terminale. Elle n’est cependant pas l’usage idiomatique de la programmation orientée objet, que nous allons présenter dans la section suivante. 3.2 Méthodes : manipuler les données Dans le paradigme de la programmation objet, la notion de classe est souvent associée A la notion d’encapsulation : un programme manipulant un objet n'est pas censé accéder librement la totalité de son contenu, une partie de ce contenu pouvant relever du « détail d’implémentation ». La manipulation de lobjet passe donc de préférence par une interface constituée de fonctions dédiées, qui font partie de la définition de la classe et sont appelées les méthodes de cette classe. Uti tion d’une méthode Les méthodes d’une classe servent 4 manipuler les objets de cette classe. Chaque appel de méthode peut recevoir des paramétres mais s'applique donc avant tout & un objet de la classe concernée. L’appel A une méthode texte s’appliquant au chronométre t et renvoyant une chaine de caractéres décrivant le temps représenté par t est réalisé ainsi.3.2, Méthodes : manipuler les données 51 >>> t.texte() ’21h 34m 5s’ Cette notation pour l’appel de méthode utilise la méme notation pointée que l’accés aux attributs de t, mais fait apparaitre en plus une paire de parenthéses, comme pour ’'appel d’une fonction sans paramétres. Lorsqu'une méthode dépend d’autres paramétres que cet objet princi- pal t, ces autres paramétres apparaissent de la maniére habituelle, entre les parentheses et séparés par des virgules. L’appel & une méthode avance faisant avancer le chronométre t d’un certain nombre de secondes passé en paramétre s’écrit donc comme suit. >>> t-avance(5) >>> t.texte() °21h 35m Os? On a déja rencontré cette notation, par exemple avec tab.append(e) pour ajouter élément e a la fin d’un tableau tab. Remarquez également dans cet exemple qu'une méthode appliquée a l’objet t a la possibilité de modifier les attributs de cet objet. Lors d’un appel i.m(e1, ..., en) & une méthode m, l’objet i est appelé le paramétre implicite et les paramétres €1 & en les paramétres explicites. ‘Toutes les méthodes d’une classe attendent comme paramétre implicite un objet de cette classe. Les paramétres explicites, en revanche, de méme que léventuel résultat de la méthode, peuvent étre des valeurs Python arbi- traires : on y trouvera aussi bien des valeurs de base (nombres, chaines de caractéres, etc.) que des objets. On peut ainsi imaginer dans notre classe Chrono une méthode egale s’appliquant & deux chronométres (le paramétre implicite et un paramétre explicite) et testant légalité des temps représentés, et une méthode clone s’appliquant 4 un chronométre t et renvoyant un nouveau chronométre ini- tialisé au méme temps que t. >>> u = t.clone() >>> t.egale(u) True >>> t.avance(3) >>> t.egale(u) False Défi ‘ion d’une méthode Comme nous venons de le voir, une méthode d’une classe peut étre vue comme une fonction ordinaire, pouvant dépendre d’un nombre arbitraire de paramétres, & ceci prés qu'elle doit nécessairement avoir pour premier52 Chapitre 3. Programmation objet Erreurs. Ne pas faire apparaitre les parenthéses aprés un appel de mé- thode ne déclenche pas l’appel, méme si la méthode n’attendait aucun parameétre explicite. Cet oubli ne provoque pas pour autant une erreur en Python, l'interpréte construisant la place un élément particulier re- présentant « la méthode associée A son paramétre implicite ». On pourra ainsi observer la réponse suivante si ’on tente un appel incomplet dans Ja boucle interactive. >>> t.texte > L’appel n’ayant pas lieu, cet oubli se manifestera en revanche certaine- ment plus tard, soit du fait que cette valeur spéciale produite n’est pas le résultat de la méthode sur lequel on comptait, soit plus sournoisement car objet n’a pas été mis & jour comme il aurait da l’étre. En revanche, utiliser un attribut numérique comme une méthode dé- clenche cette fois bien une erreur immédiate. >>> t.heures() Traceback (most recent call last): File "", line 1, in TypeError: int’ object is not callable paramétre un objet de cette classe (le paramétre implicite). Une méthode ne peut done pas avoir zéro paramétre. La définition d’une méthode d’une classe se fait exactement avec la méme notation que la définition d’une fonction. En Python, le paramétre impli- cite apparait comme un paramétre ordinaire et prend la premiere position, les paramétres explicites 1 4 n prenant alors les positions 2 n + 1. Par convention, ce premier paramétre est systématiquement appelé self !. Ce paramétre étant un objet, notez que l'on va pouvoir accéder A ses attributs avec la notation self.a. Ainsi, les méthodes texte et avance de la classe Chrono peuvent étre définies de la maniére suivante : def texte(self): return (str(self.heures) + ’h ’ + str(self.minutes) + ’m’ + str(self.secondes) + ’s’) 1. Dans d'autres langages de programmation orientée objet, il s’appelle parfois this et peut ne pas apparaitre explicitement comme premier argument de la méthode.3.2, Méthodes : manipuler les données 53 def avance(self, s) self.secondes += s # dépassement secondes self.minutes += self.secondes // 60 self.secondes = self.secondes % 60 # dépassement minutes self.heures += self.minutes // 60 self.minutes = self.minutes % 60 Constructeur La construction d’un nouvel objet avec une expression comme Chrono(21, 34, 55) déclenche deux choses : 1. la création de Pobjet lui-méme, gérée directement par l’interpréte ou le compilateur du langage, 2. Pappel & une méthode spéciale chargée d’initialiser les valeurs des at- tributs. Cette méthode, appelée constructeur, est définie par le pro- grammeur. En Python, il s’agit de la méthode __init__ que nous avons pu observer dans les exemples. La définition de la méthode spéciale __init__ ne se distingue en rien de la définition d’une méthode ordinaire : son premier attribut est self et représente l'objet auquel elle s’applique, et ses autres paramétres sont les paramétres donnés explicitement lors de la construction. La particularité de cette méthode est la maniére dont elle est appelée, directement par l’inter- préte Python en réponse & une opération particulitre. Autres méthodes particulires en Python Il existe en Python un certain nombre d’autres méthodes particuliéres, chacune avec un nom fixé et entouré comme pour __init__ de deux paires de symboles _. Ces méthodes sont appelées par certaines opérations prédéfi- nies de Python, permettant parfois d’alléger ou d’uniformiser la syntaxe. I] existe de telles méthodes d’usage général, comme les exemples donnés dans le tableau suivant. LT __Str__(self) str(t) | renvoie une chaine de caractéres décri- vant t -lt__(self, u) | t

Vous aimerez peut-être aussi

• Ellipses Numerique Et Science Informatique Nsi 1ere

  

  100% (2)

  Ellipses Numerique Et Science Informatique Nsi 1ere

  509 pages
• Ellipses NSI Terminale 2ed

  

  100% (6)

  Ellipses NSI Terminale 2ed

  210 pages
• Manuel Version Python

  

  100% (4)

  Manuel Version Python

  356 pages
• BALABONSKI CONCHON Numérique Et Sciences Informatiques Tle

  

  100% (1)

  BALABONSKI CONCHON Numérique Et Sciences Informatiques Tle

  508 pages
• Spécialité NSI - Première - 2e Édition

  

  100% (3)

  Spécialité NSI - Première - 2e Édition

  391 pages
• Cours Complet Algorithmique Et Programmation en Python 2024-2025

  

  0% (1)

  Cours Complet Algorithmique Et Programmation en Python 2024-2025

  223 pages
• Algorithme Et Programmation

  

  Pas encore d'évaluation

  Algorithme Et Programmation

  199 pages
• Algo & Programmation Python - Partie I

  

  Pas encore d'évaluation

  Algo & Programmation Python - Partie I

  128 pages
• Documentation Kivy 2.1.0 en Français

  

  Pas encore d'évaluation

  Documentation Kivy 2.1.0 en Français

  203 pages
• Cours Algorithmique - Excercices Corrigés

  

  Pas encore d'évaluation

  Cours Algorithmique - Excercices Corrigés

  117 pages
• Automate Boring Stuff FR Demo

  

  100% (1)

  Automate Boring Stuff FR Demo

  1 page
• Apprenez Les Langages: Html5 Css3 Javascript

  

  100% (1)

  Apprenez Les Langages: Html5 Css3 Javascript

  13 pages
• Python Pour Les Débutants 2024 - Maîtrisez Les Principes Fondamentaux de Python Avec Un Guide Pratiqu

  

  100% (1)

  Python Pour Les Débutants 2024 - Maîtrisez Les Principes Fondamentaux de Python Avec Un Guide Pratiqu

  145 pages
• Algorithmique - Techniques Fond Amen Tales de Program Mat Ion (Exemples en PHP)

  

  Pas encore d'évaluation

  Algorithmique - Techniques Fond Amen Tales de Program Mat Ion (Exemples en PHP)

  225 pages
• 1 IntroductionInformatique

  

  Pas encore d'évaluation

  1 IntroductionInformatique

  21 pages
• Cahier D'algo - Cycle 4 V2021

  

  100% (1)

  Cahier D'algo - Cycle 4 V2021

  68 pages
• HTTP Avxhome - Se Blogs ALGEROIS PDF

  

  100% (1)

  HTTP Avxhome - Se Blogs ALGEROIS PDF

  345 pages
• CSS3 - Pratique Du Design Web-Eyrolles (2015)

  

  100% (3)

  CSS3 - Pratique Du Design Web-Eyrolles (2015)

  410 pages
• Informatique Et Algorithmique Avec Le Langage Python

  

  100% (1)

  Informatique Et Algorithmique Avec Le Langage Python

  76 pages
• Mon Cours Visuel de Programmati - Sean McManus PDF

  

  Pas encore d'évaluation

  Mon Cours Visuel de Programmati - Sean McManus PDF

  192 pages
• Algorithmes: Notions de Base

  

  100% (2)

  Algorithmes: Notions de Base

  16 pages
• Fondements de L Informatique Les Bersini Hugues Francq Pascal Van Zeebroeck Nicolas

  

  Pas encore d'évaluation

  Fondements de L Informatique Les Bersini Hugues Francq Pascal Van Zeebroeck Nicolas

  590 pages
• Algorithmes Et Programmation

  

  Pas encore d'évaluation

  Algorithmes Et Programmation

  300 pages
• Maths Appliquées À L'informatique

  

  100% (1)

  Maths Appliquées À L'informatique

  44 pages
• Apprendre A Programmer Avec Python 3 PDF

  

  Pas encore d'évaluation

  Apprendre A Programmer Avec Python 3 PDF

  51 pages
• Eni Algorithmique Technique de Programmation en Python 2ed... Wawacity - Tokyo

  

  100% (6)

  Eni Algorithmique Technique de Programmation en Python 2ed... Wawacity - Tokyo

  304 pages
• CSI 3201 - FRIntroduction Aux Systèmes D - Exploitation - Edited

  

  100% (1)

  CSI 3201 - FRIntroduction Aux Systèmes D - Exploitation - Edited

  132 pages
• Exercice Algorithme Avec Correction PDF

  

  36% (14)

  Exercice Algorithme Avec Correction PDF

  2 pages
• Cahier D'algorithmique Et Programmation 2de

  

  100% (9)

  Cahier D'algorithmique Et Programmation 2de

  52 pages
• Introduction à l'Algorithmique et Programmation

  

  Pas encore d'évaluation

  Introduction à l'Algorithmique et Programmation

  11 pages
• Exercices de Python sur chronomètre

  

  Pas encore d'évaluation

  Exercices de Python sur chronomètre

  129 pages
• Guide complet sur Bootstrap

  

  Pas encore d'évaluation

  Guide complet sur Bootstrap

  251 pages
• Livres Python IA

  

  Pas encore d'évaluation

  Livres Python IA

  1 page
• Mathe - Matiques Pour L - Informatique PDF

  

  100% (9)

  Mathe - Matiques Pour L - Informatique PDF

  302 pages
• PDF

  

  Pas encore d'évaluation

  PDF

  33 pages
• Tout Sur HTML5 Et CSS3 (PDFDrive)

  

  Pas encore d'évaluation

  Tout Sur HTML5 Et CSS3 (PDFDrive)

  208 pages
• Exercices d'Algorithmique MI

  

  Pas encore d'évaluation

  Exercices d'Algorithmique MI

  87 pages
• Introduction Aux Probabilites A - Thierry Alhalel

  

  Pas encore d'évaluation

  Introduction Aux Probabilites A - Thierry Alhalel

  253 pages
• Alain MOUHLI-Administration Système Réseaux - Bases de l'Administration-Alan MOUHLI (2016)

  

  Pas encore d'évaluation

  Alain MOUHLI-Administration Système Réseaux - Bases de l'Administration-Alan MOUHLI (2016)

  51 pages
• Exercices Python pour Algorithmes en Seconde

  

  100% (1)

  Exercices Python pour Algorithmes en Seconde

  27 pages
• "NSI Terminale: Guide Pratique"

  

  Pas encore d'évaluation

  "NSI Terminale: Guide Pratique"

  67 pages
• LSI0De But

  

  Pas encore d'évaluation

  LSI0De But

  24 pages
• Cours

  

  Pas encore d'évaluation

  Cours

  24 pages
• Poly

  

  100% (1)

  Poly

  178 pages
• Introduction à l'algorithmique et programmation

  

  Pas encore d'évaluation

  Introduction à l'algorithmique et programmation

  18 pages
• Cours Informatique 1ère Année Licence

  

  Pas encore d'évaluation

  Cours Informatique 1ère Année Licence

  73 pages
• Introduction A L'algorithmique Et A La Programmation Avec Python

  

  Pas encore d'évaluation

  Introduction A L'algorithmique Et A La Programmation Avec Python

  6 pages
• LDP Complet

  

  50% (2)

  LDP Complet

  224 pages
• 0741 Introduction A Lalgorithmique Et A La Programmation Avec Python

  

  Pas encore d'évaluation

  0741 Introduction A Lalgorithmique Et A La Programmation Avec Python

  57 pages
• Introduction à l'architecture des ordinateurs

  

  Pas encore d'évaluation

  Introduction à l'architecture des ordinateurs

  53 pages
• Spécialité NSI : Contenu et Objectifs

  

  Pas encore d'évaluation

  Spécialité NSI : Contenu et Objectifs

  20 pages
• CoursALM Id5868

  

  Pas encore d'évaluation

  CoursALM Id5868

  50 pages
• Un Zeste de Python

  

  Pas encore d'évaluation

  Un Zeste de Python

  526 pages
• Un Zeste de Python

  

  Pas encore d'évaluation

  Un Zeste de Python

  561 pages
• Du Au: de La Programmation Procédurale À L'objet

  

  Pas encore d'évaluation

  Du Au: de La Programmation Procédurale À L'objet

  31 pages
• Cours Algorithmique

  

  Pas encore d'évaluation

  Cours Algorithmique

  57 pages
• Informatique Pour Tous en Classes Préparatoires Aux Grandes Écoles Wack Conchon Courant DeFalco Dowek Filliatre Gonnord ÉditionsEyrolles

  

  Pas encore d'évaluation

  Informatique Pour Tous en Classes Préparatoires Aux Grandes Écoles Wack Conchon Courant DeFalco Dowek Filliatre Gonnord ÉditionsEyrolles

  402 pages
• Cours d'Informatique au Lycée Masséna

  

  Pas encore d'évaluation

  Cours d'Informatique au Lycée Masséna

  10 pages
• Poly Python

  

  Pas encore d'évaluation

  Poly Python

  210 pages
• Introduction à l'algorithmique Python

  

  Pas encore d'évaluation

  Introduction à l'algorithmique Python

  50 pages
• Analyse de la fable de La Fontaine

  

  Pas encore d'évaluation

  Analyse de la fable de La Fontaine

  5 pages
• Le parfait de l'indicatif actif en latin

  

  Pas encore d'évaluation

  Le parfait de l'indicatif actif en latin

  4 pages
• Conjugaison du passif en latin

  

  Pas encore d'évaluation

  Conjugaison du passif en latin

  3 pages
• Latin Les 3e Et 4e Conjugaisons

  

  Pas encore d'évaluation

  Latin Les 3e Et 4e Conjugaisons

  4 pages