INFORMATIQUE PROGRAMMATION MODULAIRE EN PYTHON

Denis Monasse

Informations

• Publié par: Rue des écoles
• Date de parution: 01 janvier 2023
• Nombre de lectures: 55
• EAN13: 9782820807663
• Langue: Français
• Poids de l'ouvrage: 1 Mo

Extrait

INFORMATIQUE PROGRAMMATION MODULAIRE EN PYTHON

Auteur Denis Monasse

© 2018, Epistemon ISBN : 9782820807663 Achevé d’imprimer en France par Dupliprint en février 2018 Dépôt légal : mars 2018

Table des matières

Préface

Objets et classes

7

Objets et classes 13 1. Modularité. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .13 2. Objets et classes en Python. . . . . . . . . . . . . . . . . . . . . . . . . . .14 3. Et la programmation orientée objet ?. . . . . . . . . . . . . . . . . . . . . .20

Patrons de conception : les créateurs

Le patron de conception Fabrique 25 1. Objet du patron de conception Fabrique. . . . . . . . . . . . . . . . . . . .25 2. Un exemple simple. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25 3. Une fabrique dynamique : les formes d’un logiciel de dessin. . . . . . . . .26

Le patron de conception Monteur 29 1. Objet du patron de conception Monteur. . . . . . . . . . . . . . . . . . . .29 2. Un exemple de Monteur. . . . . . . . . . . . . . . . . . . . . . . . . . . . .29

Le patron de conception Prototype 32 1. Objet du patron de conception Prototype. . . . . . . . . . . . . . . . . . .32 2. Le principe du patron de conception Prototype. . . . . . . . . . . . . . . .32 3. Un exemple de prototype. . . . . . . . . . . . . . . . . . . . . . . . . . . . .33

Patrons de conception : les structurants

Le patron de conception Décorateur 37 1. Objet du patron de conception décorateur. . . . . . . . . . . . . . . . . . .37 2. Décorateurs en Python. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .38 3. Un décorateur de mémorisation. . . . . . . . . . . . . . . . . . . . . . . . .39 4. Enchaînement de décorateurs. . . . . . . . . . . . . . . . . . . . . . . . . .40 5. Décorateur d’une fonction à nombre variable d’arguments. . . . . . . . .41 6. Un décorateur de mesure du temps d’exécution. . . . . . . . . . . . . . . .42 7. Décorateurs avec paramètres. . . . . . . . . . . . . . . . . . . . . . . . . .43

3

4

8. 9.

Conservation des attributs d’une fonction décorée. . . . . . . . . . . . . . Décorateurs standards. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Le patron de conception Pont 1. Objet du patron de conception Pont. . . . . . . . . . . . . . . . . . . . . . 2. Le schéma général du Pont. . . . . . . . . . . . . . . . . . . . . . . . . . . 3. Un exemple d’utilisation du patron de conception Pont. . . . . . . . . . . .

Le patron de conception Adaptateur 1. Objet du patron de conception Adaptateur. . . . . . . . . . . . . . . . . . 2. Un exemple d’Adaptateur. . . . . . . . . . . . . . . . . . . . . . . . . . . .

Le patron de conception Façade 1. Objet du patron de conception Façade. . . . . . . . . . . . . . . . . . . . . 2. Principe et exemple de la mise en œuvre. . . . . . . . . . . . . . . . . . . .

Patrons de conception : les comportementaux

Les patrons de conception Itérateur et Générateur 1. Le patron de conception itérateur. . . . . . . . . . . . . . . . . . . . . . . . 2. Itérateurs obtenus à partir de containers. . . . . . . . . . . . . . . . . . . . 3. Lecture du flux d’un itérateur. . . . . . . . . . . . . . . . . . . . . . . . . . 4. Itérateurs avancés. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5. Générateurs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6. Chaîner des générateurs. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Le patron de conception Observateur 1. Le patron de conception Observateur. . . . . . . . . . . . . . . . . . . . . 2. Principe du patron de conception Observateur. . . . . . . . . . . . . . . . 3. Implémentation du patron de conception Observateur. . . . . . . . . . . .

Le patron de conception Stratégie 1. Objet du patron de conception Stratégie. . . . . . . . . . . . . . . . . . . . 2. Le schéma général. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3. Un cas particulier : les tris. . . . . . . . . . . . . . . . . . . . . . . . . . . .

Programmation modulaire en Python

44 45

49 49 49 50

52 52 52

54 54 54

59 59 59 61 62 64 66

67 67 67 67

71 71 71 72

Le patron de conception Commande 1. Objet du patron de conception Commande. . . . . . . . . . . . . . . . . . 2. Un exemple du patron de conception Commande. . . . . . . . . . . . . . .

Algorithmique élémentaire

Les tris 1. Introduction aux tris. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2. Tris quadratiques. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3. Tris semilogarithmiques. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

74 74 74

79 79 80 83

Chaînage, piles, files d’attente 91 1. Listes chaînées. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .91 2. Piles et files d’attente. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .100 3. Expressions algébriques postfixées. . . . . . . . . . . . . . . . . . . . . . .102

Arbres 111 1. Les arbres. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .111 2. Arbres homogènes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .129 3. Analyse lexicale et syntaxique. . . . . . . . . . . . . . . . . . . . . . . . . .153

Graphes 163 1. Notion de graphe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .163 2. Parcours de graphes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .169 3. Graphes (non orientés) pondérés. . . . . . . . . . . . . . . . . . . . . . . .173

Le retour sur trace 183 1. Un schéma de programmation. . . . . . . . . . . . . . . . . . . . . . . . .183 2. Le problème des 8 reines. . . . . . . . . . . . . . . . . . . . . . . . . . . . .183 3. Résoudre un Sudoku. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .186

Programmation dynamique 190 1. Un schéma de programmation. . . . . . . . . . . . . . . . . . . . . . . . .190 2. Le problème du sac à dos. . . . . . . . . . . . . . . . . . . . . . . . . . . .190 3. Recherche des plus courts chemins dans un graphe. . . . . . . . . . . . . .192

Programmation modulaire en Python

6

Programmation modulaire en Python

Préface

L’idée de cet ouvrage m’est venue lors de la préparation d’un cours que je devais assurer à la fin de l’automne 2017 dans le Centre de Préparation à l’Agrégation d’Informatique de 1 Marrakech (Maroc) . Les étudiants agrégatifs avaient certainement de bonnes connaissances en algorithmique et en codage Python, mais qu’en étaitil de leurs méthodes de programma tion ? Le tout n’est pas de savoir écrire du code correct, encore fautil pouvoir le relire (parfois quelques années après l’avoir écrit), le réutiliser et le transmettre (parfois à des clients). Les enseignants qui réussiront l’agrégation, exerceront dans l’enseignement supérieur pour des étudiants qui seront la plupart du temps les développeurs de demain. Leur rôle sera évidem ment crucial pour enseigner à leurs élèves des méthodes de programmation rigoureuses qui leur seront indispensables dans leur profession future. La responsabilité du développeur d’applications est cruciale. Le mathématicien ou l’astro physicien qui commet une erreur aura la possibilité d’en être averti par un collègue lors d’un prochain colloque quelques mois après la parution de son article, et il n’aura plus qu’à tenter de la corriger. Rappelons que la première démonstration du grand théorème de Fermat par Andrew Wiles comportait un trou détecté par un auditeur lors de la conférence de présenta tion et que Andrew Wiles a mis un an, avec un travail acharné, pour combler ce trou. Mais pendant toute l’année en question, le monde ne s’est pas arrêté de tourner. Par contre, le dé veloppeur qui commet une erreur met souvent en jeu des sommes colossales et parfois des vies humaines. On en a vu bien des exemples dans ces dernières années : •un mauvais contrôle d’un débordement de capacité dans un calcul en nombres réels provoque la destruction au départ d’un nouveau modèle de fusée Ariane •un programmeur qui confond mètres et pieds, et c’est une mission sur Mars qui subit un échec extrêmement coûteux •une mauvaise interface d’utilisation et c’est un avion qui s’écrase sur une montagne ou des malades qui sont gravement irradiés •une mauvaise temporisation des ordres exécutés en bourse et c’est un crack qui met des millions de personnes au chômage On pourrait multiplier les exemples de ces "erreurs informatiques". Mais, contrairement à ce qu’on peut entendre dans les médias, ce n’est pas l’informatique qui se trompe, c’est le développeur qui a commis des erreurs. Je voudrais à ce propos évoquer une anecdote qui concerne un de mes amis informaticiens il y a plusieurs années. Il se trouvait dans une queue pour prendre un billet de train et une dame devant lui demandait au comptoir qu’on lui réserve une place dans le sens de la marche.

1. En effet, le Royaume du Maroc, en avance sur l’Éducation Nationale Française, a décidé au printemps 2017 d’instaurer une agrégation d’informatique, qui est préparée en 2 ans par des étudiants de niveau Master.

Programmation modulaire en Python

8

Préface

La vendeuse lui répondit que "l’informatique ne permet pas de choisir le sens des fauteuils". Mon ami a failli exploser en entendant cette réponse : ce n’est pas l’informatique qui était responsable de cette lacune, c’est le développeur et sa hiérarchie. Si le développeur qui écrit des programmes a une telle responsabilité, il faut lui apprendre à programmer dès ses débuts avec toute la rigueur nécessaire, pas seulement à écrire des lignes de code qui sont syntaxiquement correctes, même si elles ont la bonne sémantique (leur signification). Pour cela, il y a plusieurs écueils qu’il faut lui apprendre à éviter : •; si on a écrit des partiesil ne faut pas réinventer la roue à chaque nouveau programme de programme qui sont parfaitement testées, il faut pouvoir les réutiliser : les phy siciens utilisent souvent des librairies d’analyse numérique comme IMSL écrites en Fortran dans les années 6070, pour l’unique raison que l’on sait qu’elles fonctionnent parfaitement, même si Fortran est un langage largement dépassé •il ne faut pas "bidouiller" un code existant pour l’adapter à un nouveau problème ; d’une part cela nécessiterait de comprendre parfaitement ce code existant, avec ses tenants et ses aboutissants, d’autre part le risque de faire une petite erreur aux conséquences peut être dramatiques est très important •quand on réutilise des codes existants, parfaitement rodés et sans bidouillage, il faut penser aux interactions entre ces différents codes ; imaginez que deux variables portent le même nom dans deux parties du code avec évidemment des significations différentes Pour éviter ces écueils et faire une programmation la plus sûre possible, la programmation en modules est essentielle avec deux maîtres mots : réutilisabilité et encapsulation. C’est l’idée que nous développerons dans le premier chapitre, avec comme solution proposée pour le développement dans le langage Python, l’encapsulation systématique du code dans des objets. Par contre, nous ne ferons pas de programmation objet et éviterons en particulier toutes les notions délicates liées à l’héritage. Bien entendu, la réutilisation, la combinaison et l’enrichissement de modules (préexistants ou développés ad hoc) demandent des méthodes de programmation rigoureuse. C’est là qu’in terviennent les patrons de conception (les fameux Design Pattern). Nous ne passerons en re vue qu’un certain nombre de ces patrons de conception, que j’ai considérés, à tort ou à raison, comme les plus utiles et les plus faciles à comprendre, avec des exemples simplissimes (par fois trop simples, mais la place nous est mesurée) de leur utilisation. Dans un premier temps, je conseille au lecteur de s’intéresser de manière approfondie à trois patrons de conception indispensables pour la suite de l’ouvrage. •les décorateurs •les itérateurs et les générateurs •les ponts Il pourra revenir par la suite aux autres patrons qui tous ont leur utilité. Enfin, l’ouvrage comprend une partie d’algorithmique extrêmement classique concernant les tris, les listes chaînées, les arbres et les graphes, mais avec une programmation modulaire sys tématique, des démonstrations rigoureuses et, en cas de besoin, l’utilisation de bibliothèques Python standard. Nous avons également ajouté deux schémas de programmation classiques, le retour sur trace (ou backtracking) et la programmation dynamique, pensant que d’autres schémas comme "diviser pour régner" ou les algorithmes gloutons sont suffisamment connus pour que le lecteur trouve par ailleurs matière à se documenter.

Programmation modulaire en Python

Préface

9

Le lecteur pourra considérer à sa lecture que cet ouvrage, plus qu’un manuel de programma tion, est un livre qui traite de la méthodologie de la programmation ; dans ce cas, c’est que j’aurai atteint mon but.

Denis Monasse

Bibliographie En ce qui concerne l’algorithmique proprement dite, les deux références fondamentales sont [1] Robert Sedgewick et Kevin Wayne,Algorithms,ed. Addison Wesley.

[2] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein,Introduc tion to Algorithms,ed. PHI Learning. Il n’existe malheureusement pas de version en Python de l’ouvrage de Robert Sedgewick (alors qu’il en existe de multiples versions en C, C++ ou Java), mais les programmes en Java ne sont pas trop difficiles à adapter en Python. En ce qui concerne les patrons de conception, une excellente introduction se trouve dans Wikilivres à l’adresse https://fr.wikibooks.org/wiki/Patrons_de_conception Un certain nombre d’exemples élémentaires de ces patrons de conception sont adaptés de ceux présentés dans les pages de ce site (sous licence Creative Commons). La version anglaise que l’on trouve à l’adresse https://en.wikibooks.org/wiki/Computer_Science_Design_Patterns présente également un certain nombre d’autres exemples.

Programmation modulaire en Python

10

Programmation modulaire en Python