Informatique - Programmation modulaire en Python , livre ebook
192
pages
Français
Ebooks
2018
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe en t'inscrivant gratuitement
Découvre YouScribe en t'inscrivant gratuitement
192
pages
Français
Ebooks
2018
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Publié par
Date de parution
02 avril 2018
Nombre de lectures
45
EAN13
9782820807663
Langue
Français
Poids de l'ouvrage
1 Mo
Les fondements de la programmation modulaire en Python à travers les patrons de conception et l'algorithmique classiqueDepuis plusieurs années, le langage Python s'est imposé dans la tour de Babel des langages de programmation comme un choix incontournable aussi bien dans l'enseignement que dans l'industrie. Les principales raisons de sa popularité sont : la simplicité de mise en œuvre, la puissance du langage et la richesse des bibliothèques.Issu d'un cours professé au Centre de préparation à l'agrégation d'informatique de Marrakech à l'automne 2017, l'ouvrage présente les fondements de la programmation modulaire en Python, certains des schémas classiques de construction de programmes à travers les fameux Design Patterns (patrons de conception) et un retour sur toute l'algorithmique classique (tris, listes, arbres et graphes) à travers les objets Python. Cette approche modulaire facilite la correction des programmes et la réutilisation du code à travers des projets de développement logiciel.L'ouvrage s'adresse à des enseignants, des étudiants de niveau Master, mais aussi à des développeurs ou des ingénieurs informaticiens désirant améliorer leur méthodologie de la programmation. Il demande une pratique de base du langage Python, sans connaissance préalable de la programmation par objets.L'auteur :Agrégé de mathématiques, Denis Monasse a été professeur en classes préparatoires pendant 35 ans au lycée Louis-le-Grand. Il a largement contribué au développement de l'enseignement de l'informatique en classes préparatoires en France et au Maroc. Il a écrit de nombreux ouvrages pédagogiques aux éditions Vuibert et rue des écoles. Il est également rédacteur en chef de la RMS.
Voir
Publié par
Date de parution
02 avril 2018
Nombre de lectures
45
EAN13
9782820807663
Langue
Français
Poids de l'ouvrage
1 Mo
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 classes13 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 Fabrique25 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 Monteur29 1. Objet du patron de conception Monteur. . . . . . . . . . . . . . . . . . . .29 2. Un exemple de Monteur. . . . . . . . . . . . . . . . . . . . . . . . . . . . .29
Le patron de conception Prototype32 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écorateur37 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 semilogarithmiques. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
74 74 74
79 79 80 83
Chaînage, piles, files d’attente91 1. Listes chaînées. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .91 2. Piles et files d’attente. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .100 3. Expressions algébriques postfixées. . . . . . . . . . . . . . . . . . . . . . .102
Arbres111 1. Les arbres. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .111 2. Arbres homogènes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .129 3. Analyse lexicale et syntaxique. . . . . . . . . . . . . . . . . . . . . . . . . .153
Graphes163 1. Notion de graphe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .163 2. Parcours de graphes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .169 3. Graphes (non orientés) pondérés. . . . . . . . . . . . . . . . . . . . . . . .173
Le retour sur trace183 1. Un schéma de programmation. . . . . . . . . . . . . . . . . . . . . . . . .183 2. Le problème des 8 reines. . . . . . . . . . . . . . . . . . . . . . . . . . . . .183 3. Résoudre un Sudoku. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .186
Programmation dynamique190 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 étaitil de leurs méthodes de programma tion ? Le tout n’est pas de savoir écrire du code correct, encore fautil 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 6070, 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
