Python1a PDF

Introduction lalgorithmique et la programmation avec Python
Laurent Signac https://deptinfo-ensip.univ-poitiers.fr
16 dcembre 2012
Algorithmique et Programmation avec Python
Table des matires

I Ordinateur, codage numrique 1 Ordinateur ? . . . . . . . . . . . . . . 2 Codage numrique de linformation . 3 Langages de programmation . . . . . 4 Constructions typiques des langages 5 5 5 10 11 13 13 13 15 15 17 21 22 24 28 29 30 36 41 41 43 49 50
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
II Algorithmique et programmation 5 quoi sert un algorithme ? . . . . . . . . . . 6 Algorithme dEuclide . . . . . . . . . . . . . 7 Poser les problmes . . . . . . . . . . . . . . . 8 Types, aectations, expressions . . . . . . . . 9 Fonctions et procdures . . . . . . . . . . . . 10 Conditions . . . . . . . . . . . . . . . . . . . . 11 Boucles . . . . . . . . . . . . . . . . . . . . . 12 Aectation, mode de passage des paramtres 13 Notation pointe . . . . . . . . . . . . . . . . 14 Rcursivit . . . . . . . . . . . . . . . . . . . 15 Rsoudre des problmes : mthode de travail 16 Rcursivit et Logo . . . . . . . . . . . . . . . III Complments sur Python 17 Types simples . . . . . . . 18 Types collections . . . . . 19 Types modiables ou non 20 Clavier et cran . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
Notations
Dans ce support de cours, les programmes sont gnralement typographis en police machine crire et encadrs, alors que les algorithmes nont pas de cadre et utilisent une police sans empattements. Sauf si une indication contraire est donne, le langage utilis est Python. On direncie les sessions shell par la prsence du prompt >>>. En labsence de prompt, il sagit gnralement dun programme entrer dans un diteur de texte et excuter ensuite (linterface Idle convient trs bien pour faire tout ceci).
Introduction
Linformatique, telle que nous la connaissons aujourdhui rsulte la fois des progrs thoriques, amorcs dans les annes 30 par les travaux de Turing, et des progrs technologiques, lis llectronique, avec en particulier linvention du transistor dans les annes 40. Depuis, ces deux facettes, science thorique et ds technologiques progressent de conserve. Lobjet de ce cours est de prsenter lre numrique sous langle du codage des informations, puis celle des ordinateurs sous celui des algorithmes et de la programmation.
Ressources
La dernire version de ce chier est disponible ici : https://deptinfo-ensip.univ-poitiers.fr/FILES/PDF/python1a. pdf Les ressources Web associes ce cours sont : Sur Updago : Algorithmique et Programmation Python https://deptinfo-ensip.univ-poitiers.fr/ENS/doku Les introduction Python sont nombreuses sur le Web, et certaines sont de trs bonne qualit : Le cours de Bob Cordeau : http://hebergement.u-psud.fr/iut-orsay/Pedagogie/MPHY/Python/courspython3.pdf Le cours de Pierre Puiseux : http://web.univ-pau.fr/~puiseux/enseignement/python/python.pdf Les livres sur Python 3 sont encore assez peu nombreux. plus forte raison en Franais. Voici ceux qui ont t utiliss lors de lcriture de ce cours : Le Goff, Vincent, Apprenez Programmer en Python, Le livre du Zro Puiseux, Pierre, Le Langage Python, Ellipses TechnoSup Zelle, John, Python Programming, Franklin, Beedle, and Associates Lee, Kent D., Python Programming Fundamentals, Springer Summerfield, Mark, Programming in Python 3, Addison Wesley, 2e ed. Les parties du cours qui ne concernent pas prcisment Python sont issues de nombreux ouvrages impossibles tous mentionner ici et de quelques annes de pratique.
Chapitre I
Ordinateur, codage numrique

1 Ordinateur ?
Les machines lectroniques nous entourent dsormais : de la simple calculatrice aux super-ordinateurs, en passant par les smartphones, les tablettes et les micro-ordinateurs. partir de quel degr de complexit avons-nous aaire un ordinateur ? Comme nous allons le voir, les ordinateurs actuels sont peu prs calqus sur un modle datant des annes 50, le modle de Von Neumann. Si nous devions retenir deux caractristiques des ordinateurs, ce serait que : un ordinateur doit tre programmable son programme doit tre enregistr dans sa mmoire. Par voie de consquence, une simple calculatrice de poche nest pas vraiment un ordinateur, alors que les modles programmables plus perfectionns en sont. De mme que les tablettes et les smartphones...
1.1
Modle de Von Neumann
Le modle de Von Neumann distingue : lunit arithmtique et logique, qui ralise les calculs lunit de contrle, qui veille au droulement du programme la mmoire, qui contient les donnes, et le programme en cours dexcution
Mmoire
Unit de contrle
Unit arithmtique et logique

Accumulateur
Entre
Sortie
1.2
Ordinateurs domestiques
Dans nos micro-ordinateurs, les dirents composants sont : la carte mre, le processeur, la mmoire, la carte graphique, les disques... Ces composants lectroniques communiquent entre eux par lintermdiaire de bus et les donnes qui transitent sont reprsentes sous forme binaire. Dans un ordinateur, absolument tout (donnes et programmes, en mmoire, sur les disques durs ou sur cd...) est stock sous forme binaire. Dans le suite, nous verrons comment utiliser le systme binaire, et comment des objets complexes, comme des images ou de la musique, sont codes en binaire.
Codage numrique de linformation
Linformation est la matire premire de linformatique (le mot vient dailleurs de l...). Les algorithmes, qui sont constitus dinformations, stockent, manipulent et transforment dautres informations, laide de machines. 5
Algorithmique et Programmation avec Python Tout, en informatique, est reprsent comme une squence de 0 et de 1 : les algorithmes, ou plutt les programmes, le contenu dun livre, une photo, une vido... Pourquoi le binaire ? Il y a une raison thorique et une raison technique lutilisation du binaire : on ne peut pas faire plus simple que 2 symboles. Avec un seul symbole, plus rien ne fonctionne (on a un seul codage de longueur xe, la taille de lcriture dun nombre, crit en unaire est proportionnelle au nombre, et non pas son logarithme). les deux symboles 0 et 1 sont transposables lectroniquement par : le courant passe ou ne passe pas (systme assez robuste) En consquence, toute information est reprsentable sous forme de bits (binary digit = chire binaire). La quantit dinformation est justement le nombre de bits ncessaires pour reprsenter cette information. Units le bit (binary digit ) est lunit dinformation : 0 ou 1 loctet est un groupe de 8 bits (attention, octet se dit byte en anglais) un kilo-octet (Ko) vaut 1024 octets (210 octets) un mega-octet (Mo) vaut 210 Ko un giga-octet (Go) vaut 210 Mo un tera-octet (To) vaut 210 Go un peta-octet (Po) vaut 210 To les dbits se mesurent en bits/secondes (ou Kbits/s ou Mbits/s).
2.1
Changements de base
Lcriture dun nombre en base b est forme partir de b symboles, appels chires. Les 10 chires de la base 10 sont par exemple : 0, 1, 2, 3, 4, 5, 6, 7, 8 et 9. Si lcriture dun nombre en base b est : cn cn1 ...c1 c0 (les ci sont les chires ), sa valeur sera : v (cn ) bn + v (cn1 ) bn1 + ... + v (c1 ) b1 + v (c0 ) b0 o v (ci ) est la valeur associe au chire (symbole) ci . La valeur du symbole 9 en base 10 est par exemple neuf. Gnralement, pour une base b infrieure 10, on reprend les mme chires quen base 10, avec les mmes valeurs (mais on nutilise que les b premiers chires). Pour une base b suprieure 10, on ajoute aux chires ordinaires dautres symboles, comme des lettres. La base 16 utilise par exemple les 16 chires suivantes : 0, 1, 2, ..., 9, A, B, C, D, E, F . Voici quelques exemple, la base est indique en indice la n du nombre. En labsence de cet indication, cest la base 10 qui est utilise. 1011010|2 = 1 26 + 0 25 + 1 24 + 1 23 + 0 22 + 1 21 + 0 20 = 90 5A|16 = 5 161 + 10 160 = 90 Pour passer de la base 10 la base 2, on peut procder par lcriture binaire de 90 : 90 = 2 45 45 = 2 22 22 = 2 11 11 = 2 5 5 =22 2 =21 1 =20 divisions successives (par 2). Voici comment trouver +0 +1 +0 +1 +1 +0 +1
La squence des restes successifs, lue du dernier au premier donne : 1011010 qui est lcriture en base 2 de 90. 0n peut procder de mme en base 16 (en faisant des divisions par 16). Les restes sont alors entre 0 et 15, ce qui correspond bien aux valeurs des chires de la base 16. On peut coder de la mme manire les nombres non-entiers. Chaque chire plac aprs la virgule est associ une puissance ngative de la base : 101, 011|2 = 1 22 + 0 21 + 1 20 + 0 21 + 1 22 + 1 23 = 5 + 0, 25 + 0, 125 = 5, 375 Le passage de la base 10 la base 2, pour la partie fractionnaire, est ralis par multiplications successives (on reporte la partie fractionnaire de chaque rsultat sur la ligne suivante, et les parties entires des rsultats obtenus forment 6
Notes de cours, Ensip 1A lcriture en base 2). Voici comment crire 0, 6875 en base 2 : 0, 6875 0, 375 0, 75 0.5 2 = 1, 375 2 = 0, 75 2 = 1, 5 2 = 1
Nous prenons les parties entires des rsultats dans lordre o elles sont obtenues : 1011. Donc 0, 6875 = 0, 1011|2 . Dveloppement binaires innis Notons que si lcriture dun nombre non entier en base 2 est nie, ce sera aussi le cas en base 10 (car les puissances ngatives de 2 ont toutes une criture dcimale nie). En revanche, si lcriture dcimale est nie, lcriture en base 2 ne le sera pas forcment (elle sera alors priodique). Par exemple : 0, 2 0, 4 0, 8 0, 6 0, 2 En consquence : 0, 2 = 0, 00110011... 2 = 0, 4 2 = 0, 8 2 = 1, 6 2 = 1, 2 2 = ...
2.2
Numrique vs analogique
Beaucoup dobjets quotidiens existent la fois en version numrique et analogique, mme si la premire tend remplacer petit petit la seconde. Ainsi, nous pouvons opposer les disques compacts audio et les disques vinyles, la photo numrique et la photo argentique, les e-book et les livres traditionnels. Dans tous ces cas, lobjet numrique nest quune succession de chires 0 et 1... Codage des couleurs Les couleurs, sur un cran, sont formes par synthse additive (addition de la lumire). Limpression, au contraire, est ralise par synthse soustractive. Les couleurs primaires en synthse additive sont : le rouge, le vert et le bleu (en synthse soustractive, il sagit du cyan, du magenta, et du jaune). Supposons quon dispose de 3 leds, une rouge, une verte et une bleue, et que chacune puisse tre allume ou teinte (on ne peut pas varier leur intensit). partir de ces 3 leds, nous pouvons obtenir 23 = 8 couleurs puisque chaque led peut tre soit allume, soit teinte. Nous obtenons ainsi du noir si toutes les leds sont teintes, du blanc si elles sont toutes allumes ou du cyan si seules les leds bleues et vertes sont allumes. Puisqu chacune des 8 couleurs obtenues, correspond un tat de chacune des trois leds, nous pouvons convenir de coder ltat des leds dans lordre rouge, vert, bleu par 0 (led teinte) ou 1 (led allume). Ainsi, une srie de 3 chires binaires, (autrement dit un entier entre 0 et 7) est associ une couleur : 0 1 2 3 000 001 010 011 noir bleu vert cyan 4 5 6 7 100 101 110 111 rouge magenta jaune blanc
Les dirents moyens de codage reposent sur un certain nombre de conventions. Par exemple, modier lordre des couleurs primaires dans le codage des couleurs en vert, bleu, rouge la place de rouge, vert, bleu modie bien entendu les couleurs associes aux nombres. Respecter ces conventions, cest adopter un standard, et cette adoption facilitera grandement les changes de donnes entre les personnes ou les programmes. En particulier, si le standard est publi, on dit quil est ouvert 1 , par opposition un standard ferm, qui restreint, de manire lgale ou en ne publiant pas les spcications du standard, lcriture dapplications compatibles qui pourraient utiliser les mmes chiers de donnes, par exemple. Les standards de reprsentation et de codage des informations sont extrmement nombreux. Pour chaque type dobjet numrique, il existe de nombreux standards : pour le texte (latin, utf, ascii...), pour les documents mis en page (Open Document Format, Oce Open xml...), les images (jpeg, png...), laudio (mp3, ogg, flac...), la vido (mpegv2, Vorbis, h-264...).
1. Prcisment, un standard ouvert est publi mais ne doit pas imposer non plus de restrictions quant son utilisation.
2.3
Codage du texte
Les caractres sont gnralement cods par des nombres, par une simple table de correspondance. Le standard le plus ancien est lascii, qui contient les caractres latins non accentus, les chires, des symboles de ponctuation, cods sur 7 bits (au total, la gure I.1 contient donc 128 symboles, caractres non imprimables compris)
Figure I.1 Table ascii (numrote de 0 7F, en hxa) tire de Wikipdia Le code ascii a rapidement t insusant, faute de caractres accentus, grecs, cyrilliques, hbreux, chinois... Deux autres types de codage ont donc fait leur apparition : Les extensions rajoutent des caractres la suite de la table (chaque alphabet possde alors son extension) : cest le cas du latin-1 (iso-8859-1). Il y a des extensions pour le chinois, lhbreu... Il faut donc indiquer quelle est lextension utilise pour pouvoir lire correctement le chier. Unicode est une norme qui recense tous les caractres existant dans une table (il y en a plus de 100 000 actuellement). Les codes sont ensuite reprsents dans un codage particulier comme utf-8, ou utf-16. Cest ce type de codage quil convient dutiliser maintenant.
2.4
Nombres
Nombres ngatifs Les nombres ngatifs sont reprsents en binaire en utilisant la mthode du complment deux, qui permet de raliser simplement des oprations arithmtiques directement sur le codage. Pour reprsenter un nombre avec la mthode du complment 2, on choisit auparavant le nombre de bits maximum qui sera occup par le code. Les valeurs typiques sont multiples de 8. Dans la suite, nous utiliserons des complments 2 sur 8 bits. Coder les nombres en complment 2 sur 8 bits revient partager les 256 codes possibles en deux parties. Ceux dont le bit de poids fort est 0 reprsenteront les nombres positifs de 0 127 (codage immdiat en base 2 avec les 7 bits restants). Ceux dont le bit de poids fort est 1 reprsenteront les nombres ngatifs de -128 -1. Dans le cas dun nombre ngatif n, on obtient le complment 2 de n en calculant la reprsentation binaire du nombre 256 |n|. Cette reprsentation est obtenue rapidement en crivant sur 8 bits la reprsentation binaire de la valeur absolue de n, puis en inversant les 0 et les 1, puis en ajoutant 1 : Exemple de codage en complment deux Nous souhaitons coder le nombre -66 en complment deux sur 8 bits. On commence par crire sa valeur absolue en binaire, sur 8 bits : 01000010 Puis on change les 0 et les 1 : 10111101 Puis on ajoute 1 (attention aux ventuelles retenues) : 10111110 Le rsultat est le codage en complment 2 sur 8 bits de 66. On remarque que cest aussi lcriture binaire de 256 66 = 190. Virgule ottante Nous avons vu quil tait possible de reprsenter les nombres virgule en binaire. Cependant, lutilisation trs frquente des calculs laide de nombres non entiers, et le soucis de coder ces nombres en un minimum de bits a donn naissance 8
Notes de cours, Ensip 1A au codage en virgule ottante. Ce codage (norme ieee-754) existe essentiellement en deux versions, simple et double prcision, utilisant des codages sur 32 et 64 bits. Le codage en simple prcision permet de reprsenter de manire approche les nombres entre 3.4 1038 et 3.4 1038 , tout en atteignant des valeurs aussi petites (en valeur absolue) que 1.4 1045 . Nous ne dtaillerons pas ici ce codage, assez technique, mais il est important de retenir : que cest le codage le plus utilis pour les nombres non entiers ; quil reprsente les nombres de manire approche, et quen virgule ottante, les calculs ne sont (pratiquement) jamais exacts. Flops Une indication de vitesse des processeurs donne en flops (ou un de ses multiples) fait rfrence au nombre doprations en virgule ottantes par seconde (FLoating point Operations Per Second). Lordinateur le plus rapide du monde (depuis juin 2012, cest la version de BlueGene/Q 1,5 millions de curs) a une vitesse estime de 16,32 PetaFlops (1015 ) soit plus de 16 millions de milliards doprations en virgule ottante par seconde. Un ordinateur domestique atteint des vitesses de quelques dizaines de GigaFlops (109 Flops)
2.5
Sons
Le codage dun son, ou dune courbe en gnral, est ralis en chantillonnant dans le temps le signal continu. Chaque chantillon est reprsent par un nombre, avec une certaine prcision (souvent exprime en bits). Ce codage se nomme pcm (Pulse Code Modulation). Selon la nature du signal ainsi numris, il est possible dutiliser des codages plus conomes en mmoires (compression), comme Flac (compression sans perte) ou mp3 (compression avec pertes). Compact-disc Audio Sur un compact-disc audio, les donnes ne sont pas compresss, et ce sont les chantillons qui sont directement reprsents. Les enregistrements sont stro (deux signaux), chantillonns 44100 Hz (pour conserver les frquences jusqu 22kHz), chaque chantillon tant reprsent sur 16 bits.
2.6
Images
Un image numrique (telle que celle stocke dans les appareils photos) est une matrice de pixels. Chaque pixel est un point indivisible en couleur de limage. Les lments importants en matire de qualit de limage sont donc : la taille de la matrice, et le nombre de bits utiliss pour coder la couleur de chacun des pixels. Typiquement, chaque pixel est cod sur 24 bits (8 bits par composante) et un appareil photo annonant 12 millions de pixels ralise des photographies de 4000 sur 3000 pixels. Rsolution La rsolution en dpi (Dots Per Inch) fait rfrence au nombre de pixels dune image rapport la taille physique (sur un cran ou sur papier). On estime quune impression est trs correcte (pour des besoins ordinaires) au del de 300 dpi, cest dire au del de 300 pixels par pouce. La taille maximum laquelle pourra tre imprime une photo prise avec un appareil 12 millions de pixels, tout en satisfaisant cette contrainte de qualit, sera donc (1 pouce = 2, 54 cm) : 4000/300 2, 54 33, 8 cm cest dire environ 25 centimtres sur 34. Formats dimage Si la comprhension de la numrisation dun image est assez simple, le stockage de limage numrique est ralis dans un des multiples formats disponibles. Comme pour le son, ces codages ont gnralement pour objectif de rduire la taille des chiers de stockage. La compression ralise peut tre faite avec perte (cest le cas du format jpeg) ou sans perte (cest le cas du format png). Le nombre de couleurs simultanment prsentes peut tre de 16,7 millions (codage sur 24 bits sans palette) ou moins (comme avec le format gif). Ainsi, le choix dun format dimage peut dpendre du type dimage coder (on utilise facilement jpeg pour des photos, et le format png est prfrable pour des dessins au trait).
2.7
Codages symboliques
Avant de terminer cette section sur le codage, signalons lexistence des codages symboliques, que lon peut rencontrer pour tout type dobjet (images, musique). Grossirement, on peut dire que le codage symbolique est un codage plus 9
Algorithmique et Programmation avec Python intelligent de lobjet. Il se situe un niveau suprieur dabstraction et sintresse au contenu et au sens de lobjet plutt qu son rendu. Cette dirence est prsente aussi en dehors du monde numrique : un enregistrement musical (du son donc...) nest pas la mme chose quun ensemble de partitions musicales, mme si lenregistrement correspond des musiciens jouant prcisment ces partitions. La partition est alors le codage symbolique. Cette mme dualit existe dans le monde numrique. Le codage dimages que nous avons dj voqu est dit codage matriciel ou bitmap. Mais nous pouvons aussi dcrire une image (certains types tout au moins) en dtaillant les objets qui sont prsents sur cette image (des cercles, des lignes etc...). Une description des objets gomtriques composant un dessin est un codage vectoriel de limage. Cette description a pour principales caractristiques dtre plus conome en mmoire (dire que limage est un disque blanc est plus rapide que dtailler les 12 millions de pixels dune photo dun disque blanc...), et de ne pas tre sensible aux problmes de pixelisation (de prs ou de loin, un disque blanc est toujours aussi parfait, ce qui nest pas le cas de sa description matricielle). Les formats vectoriels usuels sont : postscript (ps), portable document format (pdf), au, swf, scalar vector graphics (svg)... De mme, en ce qui concerne le son, le codage symbolique le plus utilis est midi, qui dtaille un morceau en pistes, chaque piste correspondant un instrument et contenant les notes joues, avec leur hauteur et leur dure. Cest plus ou moins lquivalent dune partition. On peut dailleurs crer de manire automatique une partition partir dun chier midi, alors quil est peu probable quon puisse y parvenir partir de lenregistrement dune symphonie. Le passage du symbolique vers lchantillonn est gnralement facile 2 . En revanche, linverse est dicile, et parfois impossible (tous les sons enregistrs ne peuvent pas tre retranscrits par une partition, et lorsque cest possible, la mthode nest pas triviale).
Langages de programmation
Un langage de programmation permet dcrire un programme. Un programme, lorsquil est sous la forme de code source, est un texte qui exprime un algorithme (nous y reviendrons), en vue de permettre lexcution de ce dernier sur une machine. Les langages utiliss pour programmer sont situs quelque part entre les squences de 0 et 1 chres la machine et le langage naturel cher lhumain. Pourquoi choisir un langage ? Linformatique sur papier est possible, mais elle est moins distrayante que sur machine. De plus, la ralisation dun programme est le moyen dobtenir des rponses eectives aux problmes qui ncessitent lutilisation dun ordinateur. Enn, la programmation est une activit de cration et de rigueur trs formatrice, et elle aide comprendre la manire dont fonctionnent les algorithmes. Il existe des centaines de langages dirents, qui peuvent tre plus ou moins spcialiss pour certaines tches, qui permettent dutiliser dirents paradigmes de programmation (impratif, objet, par contraintes, logique...). Les langages peuvent tre plus ou moins verbeux, plus ou moins expressifs. Certains langages sont trs rpandus, ou au contraire ne sont utiliss que par une poigne de personnes. Les langages peuvent tre jeunes ou vieillissant, et, lorsque le ct aectif sen mle, ils peuvent tre agrables utiliser ou au contraire agaants... La tche qui consiste choisir un langage de programmation pour illustrer un cours dalgorithmique et dinformatique, destination dun public htrogne est donc... dicile. Dans la suite, cest le langage Python qui sera utilis. Il est : gnraliste, assez rpandu (la pente tant dans le bon sens...), multi-paradigmes, assez jeune, expressif et agrable utiliser. Il nest cependant pas le seul possder toutes ces qualits. Dun point de vue plus technique, Python est aussi un langage interprt (par opposition un langage compil). En partie pour cette raison, il est dapprentissage rapide, il est portable, mais il est en revanche lent lexcution. Enn, il existe plusieurs interprteurs Python, et linterprteur standard, nomm CPython, est libre, gratuit et multi plates-formes. Voici un exemple de programme crit en Python : def fibonacci(n) : f=[0,1] while len(f)<n+1 : f.append(f[-1]+f[-2]) return f[n] def main() : n=input("Entrez un nombre entier :") n=int(n)
2. Pour une image, cette tape sappelle la rasterisation et elle est eectue chaque fois quon ache lobjet vectoriel sur un cran.
10
Notes de cours, Ensip 1A f=fibonacci(n) print("Suite de Fibonacci : U_{}={}\n".format(n,f)) La page 14 permet de comparer un mme programme crit en plusieurs langages.
Constructions typiques des langages
Cette section a pour objectifs de familiariser le lecteur avec la lecture de programmes, donns ici en Python. Les constructions les plus utilises sont les variables et les calculs. Les variables servent stocker des valeurs (ici fare et celc), et les calculs sont raliss trs simplement en utilisant par exemple les oprateurs arithmtiques habituels. fare=float(input("Temprature en degrs Fahrenheit ")) celc=(fare-32)/1.8 print("En degrs Celcius, cela fait : ",celc) galit = aectation Attention ne pas confondre le symbole =, utilis comme symbole daectation dans la plupart des langages avec le = mathmatique qui indique que deux valeurs sont gales. Lquation mathmatique a = a + 1 est par exemple (dans la plupart des contextes) sans intrt, alors que la ligne de programme a=a+1 indique quil faut rajouter 1 au contenu de a. Non seulement ce nest pas absurde, mais cest une criture trs courante. La plupart des programmes nont pas un unique l dexcution possible. Selon les valeurs donnes en entres, ou selon le rsultat de certains calculs, une chose plutt quune autre doit tre faite (par exemple, pour un programme de recherche de racines dun polynme de degr 2, aprs que lutilisateur a entr les coecients, la portion de programme excuter ne sera pas la mme selon que le discriminant est positif, ngatif ou nul). Dans lexemple suivant, selon que la temprature est en dessous de 0 C ou non, un message dirent sera ach : fare=float(input("Temprature en degrs Fahrenheit ")) celc=(fare-32)/1.8 print("En degrs Celcius, cela fait : ",celc) if celc>0 : print("a va, il ne va pas geler...") else : print("Tous aux abris, il va faire froid...") Lors de la conception dun programme un peu long, il est indispensable de le structurer en parties indpendantes. Il est trs utile de commencer prendre cette habitude mme avec des programmes courts. Dans lexemple qui suit, nous avons crit une fonction, nomme conversion, qui convertit une temprature, donne en degrs Fahrenheit en une temprature exprime en degrs Celcius. La fonction est ensuite utilise dans le programme principal : # Fonction def conversion(f) : c=(f-32)/1.8 return c # Programme principal fare=float(input("Temprature en degrs Fahrenheit ")) celc=conversion(fare) print("En degrs Celcius, cela fait : ",celc) Le propre de lordinateur est de ne pas se plaindre si on lui demande de recommencer de nombreuses fois les mmes oprations (avec quelques petites variantes). La structure de boucle permet dexprimer les rptitions et nous lutilisons ci-dessous pour acher une table de conversion de degrs Fahrenheit vers degrs Celcius (en vue de limprimer par exemple). # Fonction def conversion(f) : c=(f-32)/1.8 return c # Programme principal 11
Algorithmique et Programmation avec Python fare=0 while fare < 100 : celc=conversion(fare) print(fare," / ",celc) fare=fare+10
12
Chapitre II
Algorithmique et programmation
5 quoi sert un algorithme ?
Lalgorithmique est bien plus ancienne que linformatique, que lordinateur, et que le langage Python, utilis dans ce support de cours. Les exemples les plus anciens et clbres sont : les calculs dimpts Babyloniens (il y a 4000 ans) le calcul du plus grand diviseur commun (Euclide, vers 350) les premire mthodes de rsolution systmatique dquations (Al Khawarizmi, ixe sicle) Les algorithmes taient donc dabord utiliss la main. Aujourdhui on entend gnralement par algorithmique la rexion prliminaire lcriture dun programme dordinateur, cest dire la recherche dune mthode systmatique et non ambigu pour rsoudre un problme. Cest la partie conceptuelle de la programmation, labstraction 1 dun programme dordinateur. Lalgorithmique est parfois considre comme une branche des mathmatiques, parfois comme une branche de linformatique. Les notions dalgorithme, puis dordinateur ont t formalises dans les annes 30 et 40 par : Kurt Gdel, Alan Turing, John von Neumann... Avoir des notions en algorithmique permet de dvelopper soi-mme des programmes, et/ou davoir une discussion constructive avec une quipe de dveloppeurs. Les comptences en algorithmique font aussi partie du bagage minimum dun scientique, quil soit technicien, chercheur, ingnieur ou simplement curieux.
Algorithme dEuclide
Commenons par un exemple historique clbre : lalgorithme dEuclide. Algorithme dEuclide tant donns deux entiers, retrancher le plus petit au plus grand et recommencer jusqu ce que les deux nombres soient gaux. La valeur obtenue est le plus grand diviseur commun. Exercice Appliquez lalgorithme dEuclide ( la main) aux nombres 133 et 49 Voici les direntes tapes vers la rdaction propre dun algorithme. Nous partons de lide de dpart et la ranons par tapes...
1. La mme manire de trier une liste, dajouter deux nombres ou de compresser un chier peut sexprimer dans dirents langages de programmation. Il existe donc un objet abstrait, qui sincarne dans ces programmes crits dans dirents langages. Cest cet objet que lon appelle un algorithme extrait de Introduction la Science Informatique
Figure II.1 Les lments, livre VII, dition de 1632
13
tape 1 : crire proprement lide Prendre les deux nombres et, tant quils ne sont pas gaux, retirer le plus petit au plus grand. tape 2 : Dcrire prcisment les tapes a,b : deux nombres Rpter tant que a et b sont dirents : si le plus grand est a : les deux nombres deviennent ab et b sinon (b est donc le plus grand) : les deux nombres deviennent a et ba le pgcd est a
tape 3 : crire un algorithme formel fonction pgdc(a,b : entiers ) repeter tant que a=b si a>b a=ab sinon b=ba retourner a tape 4 : crire un programme def pgdc(a,b) : while a!=b : if a>b : a=a-b else : b=b-a return a
Finalement, cest quoi la programmation ? Programmer est lactivit qui consiste : traduire des algorithmes dans un langage de programmation : an dobtenir des rponses eectives (souvent numriques) des problmes ; an de se distraire... corriger des erreurs dans un programme ; rester calme... Voici lalgorithme du pgdc prsent dans plusieurs langages 2 .
# CODE PYTHON def pgdc(a,b): while a!=b : if a>b : a=a-b else : b=b-a return a // Code Java public static int pgdc(int a, int b) { while (a!=b) { if (a>b) a=a-b; else b=b-a; } return a; }
% CODE OCTAVE function r=pgdc(a,b) while (a~=b) if (a>b) a=a-b; else b=b-a; end r=a;
(* Code OCaml *) let rec pgcd(a, b) = if a = b then a else if a > b then pgcd(a-b, b) else pgcd(a,b-a) ;;
2. Notons quune implmentation plus ecace nenlve pas le plus petit nombre au plus grand, mais calcule le reste de la division entire du plus grand nombre par le plus petit. Les fonctions Scheme et OCaml sont un peu direntes des autres et utilisent la rcursivit plutt que les boucles.
14
Notes de cours, Ensip 1A
/* CODE C */ int pgdc(int a,int b) { while (a != b) { if (a>b) a=a-b; else b=b-a; } return a; }
# CODE RUBY def pgdc(a,b) while a!=b if a>b then a=a-b else b=b-a end end a end Rem Code OOBasic Function Pgdc(ByVal a As Integer , ByVal b As Integer) As Integer Do While a<>b If a>b Then a=a-b Else b=b-a EndIf Loop Pgdc=a End Function
; Code Scheme (define (pgdc a b) (cond ((< a b) (pgdc a (- b a) )) ((> a b) (pgdc (- a b) b )) (else a) ) )
Poser les problmes
Rsoudre un problme ncessite : que lnonc soit prcis ; quon le comprenne parfaitement ; ... Autant que possible, il faut prendre lhabitude de prciser, de prfrence par crit, quelles sont les entres et les sorties du problme (ou des sous-problmes, comme nous le verrons plus tard). Voici quelques exemples : Problme : Puissance (lever un rel une certaine puissance) Entres un rel x, un entier n Sortie le rel xn Problme : Facteurs premiers Entres un entier n > 1 Sortie liste des facteurs premiers de n Problme : Calculer le plus grand diviseur commun Entres deux entiers a et b Sortie un entier, pgdc de a et b
8
8.1
Types, aectations, expressions

Types simples
Le type dune donne caractrise sa nature (est-ce que cest un entier, un nombre virgule une couleur, une liste... ?) et par voie de consquence les oprations quil est possible de lui appliquer (on peut ajouter des nombres, mais peut tre pas des couleurs). Les types dans un langage informatique dpendent fortement du codage utilis pour reprsenter les donnes. En algorithmique, on peut parfois se permettre dutiliser des types mathmatiques qui nont pas dimplmentation relle en machine. Cas des entiers et des rels Les entiers, par exemple, ont une taille limite en C (quelques octets). Cette taille est limite la mmoire disponible en Python (lentier maximum est considrablement grand). Lensemble des entiers mathmatiques nest en 15
Algorithmique et Programmation avec Python revanche pas born. Les rels, que lon manipule en mathmatique nexistent ni en Python, ni en C, o il sont remplacs par les nombres virgule ottante (ou ottants). En consquence, tous les calculs sur ordinateur utilisant les ottants sont intrinsquement faux. Voici quelques exemples de types simples : Nom commun Entier Rels Boolen Caractre Python int float bool C int float,double int char
en C, un entier a une taille limite assez faible Les calculs en ottants sont approchs En Python, il ny a pas de type caractre
8.2
Variables
Une variable sert despace de stockage pour les rsultats intermdiaires dun calcul. Elle possde un certain nombre de caractristiques : identicateur (nom) Il doit tre bien choisi, surtout dans un programme long. Un identicateur ne comporte aucun espace ou caractre spcial et ne peut pas tre un mot cl. Chaque langage dispose de rgles (direntes) trs prcises dcrivant la syntaxe des identicateurs type Dans certains langages, le type dune variable peut changer en cours dexcution du programme (Python, Ruby). Dans dautres, le type est x une fois pour toutes (Java, C). valeur Il y a ncessairement quelque chose dans une variable. porte On ne peut utiliser le nom dune variable que dans la fonction ou la procdure (en ralit le bloc) qui la contient. La dure de vie de la variable correspond la dure dexcution de la fonction ou de la procdure (du bloc). Sans ce principe, les programmes longs deviendraient incomprhensibles et diciles dverminer. Attention laectation Nous lavons dj mentionn, mais nous rappelons quil ne faut pas confondre laectation et lgalit. Laectation est une opration typiquement informatique et permet de stocker une donne dans une variable Voici un exemple de session shell qui calcule un prix ttc : >>> >>> >>> >>> a=19.6 sommeht=245 sommettc=sommeht*(1+a/100) print(sommettc)
Exercice La session shell suivante ache deux prix ht et ttc : 1000 et 1196, puis 2000 et 1196... Il y a manifestement une erreur. La comprenez-vous ? # Attention, ce programme comporte # une erreur de conception >>> sommeht=1000 >>> sommettc=sommeht*1.196 >>> print(sommeht,sommettc) >>> sommeht=sommeht*2 >>> print(sommeht,sommettc) Laectation en Python En Python, laectation a un sens un peu particulier qui pourra vous conduire de mauvaises surprises. Nous y reviendrons par la suite, mais les impatients peuvent partir dun principe que les donnes ont une existence en mmoire et que les variables sont des rfrences vers ces donnes en mmoire. Lopration daectation : x=DATA nalise la cration en mmoire de lobjet DATA, puis stocke dans x une rfrence vers cet objet. Le comportement observ est la plupart du temps le mme que celui des autres langages... mais pas toujours.
16
8.3
Expressions
Nous utiliserons une dnition intuitive des expressions, en retenant que cest une portion de code, plus ou moins longue, qui peut tre value. La valeur obtenue peut par exemple tre aecte une variable. 3*i+5 : ok si i est un nombre pgdc(105,i)+3 : ok si i est un entier, et si pgdc est une fonction retournant un nombre. On utilise les notations les plus classiques possibles : +, -, *, /, % (modulo), ** (puissance) Division entires Attention, en Python 3 (mais pas en Python 2), la division entre deux entiers, note /, donne un ottant (mme si la division tombe juste). La division entire est en revanche note //. Ce comportement est dirent de ce quon trouve dans la plupart des langages, pour lesquels cest le type des oprandes qui xe le type du rsultat.
8.4
Listes
Un tableau, tel que ceux utiliss en C par exemple, permet de stocker selon une ou plusieurs dimensions des donnes homognes (on parle de tableau dentiers par exemple). Si le type array existe aussi en Python (module array), on utilise plus volontiers dans les langages de scripts modernes le type list qui permet de stocker des objets htrognes (voire dautres listes). Voici un exemple dutilisation de listes : # Crer des listes >>> l1=[] >>> l2=[1, 3, 2, 4] # Mettre jour un lment >>> l2[3]=45 # Accder un lment >>> print(2*l2[1]) # Attention !!! >>> l1[0]=5 # Rajout dlment >>> l1.append(56) >>> l2.append(Fin) #Connatre le nombre dlments >>> len(l1) >>> len(l2)
8.5
Tuples
Les tuples 3 de Python sont des listes non modiables 4 . Il nest pas strictement ncessaire dutiliser des tuples. Mais certaines mthodes ou fonctions Python en renvoient et il faut donc connatre leur existence.
9
9.1
Fonctions et procdures
Fonctions
Les fonctions et procdures sont la pierre angulaire de la programmation procdurale. Il y aura deux points fondamentaux retenir ds la n de lecture de cette sous-section : comprendre pourquoi on crit des fonctions ; sobliger le faire ds les premiers programmes. Commenons par un exemple en Python : def calculttc(val,taux) : """ Calcule le montant ttc, connaissant la somme hors taxe (val) et le taux (par ex 19.6) """
3. Nous devrions les appeler n-uplets en franais, mais cest le mot anglais qui est systmatiquement repris dans les ouvrages sur Python. 4. Cela signie que chaque lment du tuple devra toujours rfrencer le mme objet (mais cet objet, sil est lui-mme modiable pourrait changer)...
17
Algorithmique et Programmation avec Python ttc=val*(1+taux/100) return ttc Instruction return Que ce soit en langage algorithmique, en C, en Octave ou en Python, linstruction retourner (return) termine la fonction ou la procdure, mme si cette instruction est excute avant la n du texte de la fonction. Une fois la fonction calculttc lue par le shell, il est possible de lutiliser ainsi : >>> calculttc(1000,19.6) => 1196 Notons quil convient de bien sparer la dnition et lutilisation de la fonction : dnition : on indique comment marche la fonction et comment on sen sert (dclaration). La fonction nest pas utilise (excute), mais juste lue pour tre connue de linterprteur. utilisation : on excute de manire eective le code de la fonction pour des valeurs dentres xes (1 000 et 19, 6 dans lexemple). Voici quelques occasions dans lesquelles vous devez crire des fonctions (ou des procdures) : 1. Le bloc de programme que vous crivez ne tient pas entier la vue sur votre cran. 2. Vous utilisez plus dune fois des portions de code exactement identiques, ou presque identiques. Vous gagnerez en clart et en maintenabilit crire une fonction la place de ce bloc et lappeler plusieurs fois. 3. Vous ne savez pas exactement si la mthode de rsolution employe pour telle tche est la meilleure. Mettez la dans une fonction et utilisez cette fonction. Si vous trouvez une meilleure faon de procder, il sura de modier la fonction sans toucher au reste. 4. Le problme que vous traitez est dicile : dcoupez le en fonctions que vous crirez et testerez sparment les unes des autres (le bnce que vous aurez pouvoir tester trs facilement des portions de programme est norme). Dans chaque fonction indpendante, vous pourrez choisir des noms de variables appropris, qui rendront votre code plus simple comprendre.
9.2
Fonctions dans dautres langages
La faon dcrire les fonctions, mthodes et procdures varie selon les langages. Une manire plus algorithmique et francise dcrire pourrait tre : fonction calculttc ( val ,taux : rels ) : rel ttc : rel ttc val(1+taux/100) retourner ttc Voici dautres exemples, pour comparaison : // En langage C float calculttc(float val,float taux) { float ttc; ttc=val*(1+taux/100); return ttc; } # En Ruby def calculttc(val,taux) val*(1+taux/100) end // En Octave function ttc=calculttc(val,taux) ttc=val*(1+taux/100)
18
9.3
Procdures
Il ne faut pas confondre procdure et fonction, mme si leur dnition, en Python par exemple, est similaire : Une fonction calcule. Elle vaut quelque chose (exemples : pgdc et calculttc) Une procdure na pas de valeur 5 , mais elle fait/modie quelque chose (exemple : acher lcran, modier un objet). On dit quelle a un eet de bord (elle modie quelque chose qui est en dehors de la procdure). Mme si la dirence fonction/procdure nest pas syntaxique (au niveau de la ligne de prototype) en Python, elle est trs importante :
# Ceci est une fonction def foncttc(val,taux) : ttc=val*(1+taux/100) return ttc
# Ceci est une procdure def procttc(val,taux) : ttc=val*(1+taux/100) print(ttc)
On pourrait penser que la fonction foncttc et la procdure procttc sont quivalentes 6 . Ce serait une erreur. La fonction est plus gnrale. On ne peut pas crire par exemple : # La ligne suivante ne fonctionne pas >>> print("Double du prix ttc : ",procttc(100,19.6)*2) En revanche, la mme ligne, en utilisant foncttc fournirait le bon rsultat. Assurez-vous davoir bien compris pourquoi la ligne qui prcde marche avec une fonction et pas avec une procdure. Cest vraiment trs important. Eets de bords Autant que possible, on souhaite quune fonction nait pas deet de bord on ne fait donc pas dachage dans une fonction (ce nest pas interdit... cest dconseill ).
9.4
Prototype dune fonction
Le prototype est la premire ligne de la fonction : fonction calculttc ( val ,taux : rels ) : rel Il peut indiquer 4 choses : 1. le nom de la fonction ou de la procdure : foncttc 2. les paramtres (les entres du problme) : (val,taux : rels) 3. les ventuels types de sortie (dans le cas dune fonction) : rel 4. si lon a aaire une fonction ou une procdure (on le voit si le type des donnes de sortie est mentionn par exemple, ou parce que le mot cl est dirent (fonc ou fonction pour une fonction et proc ou procdure sinon). Ce prototype est trs abrg en Python : def foncttc(val,taux) Le prototype Python nindique pas les types des entres, et nous ne pouvons pas savoir si nous avons aaire une fonction ou une procdure.
9.5
Variables locales
Les variables locales sont les variables qui nexistent que dans le corps de la fonction ou procdure (dans une certaine mesure, les paramtres peuvent tre assimils aux variables locales). Voici un exemple de fonction avec un paramtre u et une variable locale v : def aucarre(u): v=u**2 return v
5. En Python, une procdure renvoie la valeur spciale None. 6. Si on entre procttc(100,7) ou foncttc(100,7) dans le shell, on verra une rponse correcte sacher (quoique un peu diremment) dans les deux cas...
19
Algorithmique et Programmation avec Python Pour utiliser la fonction qui prcde, il est inutile de connatre les noms de variable u et v. Ce qui est important, cest que la fonction prend en paramtre un nombre et renvoie un nombre (le carr du premier) : >>> a=9 >>> b=aucarre(a) >>> print(a,b) 9 81 La notion de porte des variables (variables locales, globales) est souvent mal comprise au dbut : elle peut tre perue comme une dicult, voire un dfaut, alors quelle simplie grandement le travail du programmeur. Local, englobant, global et built-in Les auteurs anglophones conseillent de retenir la rgle legb, acronyme qui permet de retenir lordre de rsolution des noms de variable dans Python : local, englobant, global et built-in. Les variables locales une fonction sont celles dnies dans la fonction ainsi que ses paramtres. Les variables du bloc englobant dune fonction sont celles dont la porte contient la fonction. Les variables globales sont celles dclares au niveau du chier python. Enn, built-in regroupe ce qui est dni lexcution de linterprteur. Dans un premier temps, il est ncessaire de : ne pas utiliser de variable globale (ce qui est une bonne chose de toutes faons) ; bien comprendre quune variable locale une fonction nexiste pas en dehors de cette fonction.
9.6
Conseils aviss
On ne mche pas un chewing-gum en montant un escalier : Ce proverbe tir dune campagne lectorale amricaine exprime une ide de bon sens : on ne fait bien quune seule chose la fois. Cest pour cela quon dcoupe un programme en procdures et en modules indpendants. Nommez ce que vous ne connaissez pas encore : Ce proverbe sapplique chaque fois que vous rencontrez un sous-problme lintrieur dun problme. Refusez de rsoudre le sous-problme, laissez-le de ct et avancez. Comment ? En donnant un nom ce que vous ne connaissez pas encore (du code, une fonction). Cela vous permettra de terminer le travail (i.e. le problme) en cours. Pour le sous-problme, voyez le proverbe suivant. Demain, ce sera mieux ; aprs-demain, ce sera encore mieux : [...] vous constatez un blocage provoqu par lapparition dun nouveau problme lintrieur du problme que vous essayez de rsoudre : appliquez le proverbe prcdent [...] apprenez distinguer lessentiel de laccessoire ; ne vous noyez pas prmaturment dans les dtails [...] Vous lavez certainement pratique en mathmatique : Je vais dabord prouver mon thorme en admettant provisoirement les lemmes 1, 2 et 3. [...] retenir sur les fonctions 1. Une fonction vaut quelque chose, une procdure fait quelque chose. 2. Le prototype (dclaration) dune fonction sut (normalement) savoir ce quelle calcule et comment on lutilise, mais pas comment elle le calcule. 3. On crit des fonctions et des procdures pour ne plus avoir se soucier de la faon de rgler le problme quelles traitent. En consquence, tre oblig de retoucher le code dune fonction pour un problme particulier indique gnralement que la fonction a t mal conue au dpart. 4. Gnralement, lorsquon a termin lcriture dune fonction et quon la teste, on souhaite ne plus avoir revenir dessus et ne plus devoir la modier.
Tir de Math-Info de Raymond Sroul, Interditions
20
10
Conditions
<instructions avant le test> if <condition> : <instructions du bloc "alors"> <instructions aprs le test> Nous souhaitons demander un nombre lutilisateur et acher un message particulier si ce nombre est un multiple de 13 : n=int(input(Entrez un nombre :)) if n%13==0 : print(n,est divisible par 13) print(Bravo,n) print("Merci davoir particip")
instructions avant le test
condition
Vrai
Faux
instructions du bloc alors
instructions apr` es le test
Exercice Identiez chaque partie du programme qui prcde avec les blocs correspondant de lorganigramme.
On cherche traduire un choix, une alternative.

instructions avant le test
condition
Faux Vrai
instructions du bloc sinon instructions apr` es le test
instructions du bloc alors
<instructions avant le test> if <condition> : <instructions du bloc "alors"> else : <instructions du bloc "sinon"> <instructions aprs le test>
La suite de Collatz est dnie ainsi : un+1 = un /2 si un est pair 3un + 1 sinon
Pour chaque valeur de u0 choisie, on obtient une nouvelle squence de nombres. crivons une fonction qui calcule un+1 en fonction de un . fonction collatz (u : entier ) : entier res : entier si u est pair res u/2 sinon res 3u+1 retourner res def collatz(u) : if u%2==0 : res=u//2 else : res=3*u+1 return res
21
Exercice Identiez chaque partie du programme qui prcde avec les blocs correspondant de lorganigramme. Oprateurs boolens Ce sont les classiques : and, or, not. Attention aux priorits : True or True and False vaut True (True or True) and False vaut False True or (True and False) vaut True
11
11.1
Boucles
Boucles Tant Que
instructions avant la boucle
<instructions avant la boucle> while <condition>: <corps de la boucle> <instructions aprs la boucle> Nous souhaitons faire un programme de jeu qui propose lutilisateur de deviner un nombre entre 1 et 100 en faisant des propositions. chaque proposition, le programme lui indique si le nombre propos est trop petit ou trop grand. Le jeu sarrte lorsque le nombre est dcouvert.
Non
Est-ce que la condition de la boucle est vraie ?

boucle Oui
corps de la boucle instructions apr` es la boucle
import random nb=random.randint(1,100) ch=-1 while nb!=ch : ch=int(input(Entrez un nombre )) if ch<nb : print(Trop petit) if ch>nb : print(Trop grand) print(Bravo)
Exercice Identiez chaque partie du programme qui prcde avec les blocs correspondant de lorganigramme. Voici un autre exemple de boucle : la suite de collatz, que nous avons rcemment rencontr a la proprit, quel que soit son nombre de dpart, de toujours terminer sur le cycle 1, 2, 4. Ce fait a t vri exprimentalement jusqu de trs grandes valeurs, mais a pour linstant le statut de conjecture car la preuve semble chapper aux mathmatiques actuelles. Voici une fonction qui renvoie une liste contenant la suite issue dun nombre n, jusqu ce que la valeur 1 soit atteinte. Cette liste sappelle le vol n : def suite(depart) : s=[] val=depart while val!=1 : s.append(val) val=collatz(val) s.append(1) Exercice Identiez chaque partie du programme qui prcde avec les blocs correspondant de lorganigramme. Protez de 22
Notes de cours, Ensip 1A la prsence dune machine prs de vous pour vous merveiller devant la longueur du vol 270. Quel est son point culminant ?
11.2
Boucles Rpter Pour et itrateurs
Beaucoup de langage orent un autre type de boucle, permettant de grer un compteur. Voici un exemple qui ache des tables de multiplication : Rpter pour i de 1 10 : Rpter pour j de 1 10 : crire ( i , x , j ,=, i j) Python nest pas en reste pour ce type de boucle, mme si la construction oerte est plus gnrale que la simple boucle avec compteur. La traduction de lalgorithme qui prcde en Python donnerait : for i in range(1,11) : for j in range(1,11) : print(i,x,j,=,i*j) La boucle for de Python permet en fait ditrer sur nimporte quel objet itrable. Or lobjet range(a,b) est itrable et contient les entiers de a b-1 inclus. Cest pourquoi dans lexemple qui prcde i prend successivement toutes les valeurs de 1 10. Avec la boucle for de Python, il est possible de traverser toutes sortes dobjets : liste=(5,10,15,23,13,29) for nombre in liste : print(Le nombre est,nombre) for lettre in Hello World : print(lettre) for i,l in enumerate(Hello World) : print(i,l) for mot in Hello World.split() : print(mot) 1. Dans la premire boucle, nombre prendra successivement toutes les valeurs de la liste. 2. Une chane est itrable. Dans la seconde boucle, lettre vaudra successivement chaque lettre de la chane de caractres 3. La fonction enumerate sur un itrable renvoie un nouvel itrable dont les lments sont des tuples 2 lments : le premier est un numro dordre et le second llmnt dans litrable de dpart. Par exemple enumerate(Hello) correspond [(0, H), (1, e), (2, l), (3, l), (4, o)]. Cette boucle aurait pu tre crite : for t in enumerate(Hello World) : print(t[0],t[1]) La premire criture dpaquette le tuple t en i et l la vole. 4. la mthode split renvoie une liste contenant chaque mot de la chane. Dans la quatrime boucle, mot vaudra donc successivement Hello puis World Inspecter les objets itrables En premire lecture, vous pouvez omettre ce paragraphe. Depuis Python 3, il nest pas toujours immdiat dinspecter les valeurs dun objet itrable : >>> s="analphabte" >>> l=enumerate(s) >>> l <enumerate object at 0x7feecc10cb40> Pour connatre les valeurs de l, on peut le transformer en liste : 23
>>> list(l) [(0, a), (1, n), (2, a), (3, l), (4, p), (5, h), (6, a), (7, b), (8, ), (9, t), (10, e)] Mais attention, lobjet l est gnrateur qui ne peut tre travers quune fois (et le transformer en liste implique quon le traverse) : >>> list(l) [] Pour nouveau accder aux valeurs, il sut de crer un nouveau gnrateur : >>> l=enumerate(s) >>> list(l) [(0, a), (1, n), (2, a), (3, l), (4, p), (5, h), (6, a), (7, b), (8, ), (9, t), (10, e)]
12
Aectation, mode de passage des paramtres
Par valeur ou par adresse Dans la plupart des langages, on direncie le passage des paramtres par valeur et par adresse. Dans le premier cas, cest une copie du paramtre qui est communique la fonction. Dans le second, cest lobjet original, si bien quune modication de lobjet pass en paramtre dans la fonction modie eectivement lobjet original. Lorsquon crit un algorithme, cest bien souvent le contexte et le type de valeurs manipules (on fait donc appel lexprience du lecteur) qui permet de connatre le type de passage de paramtres envisag. Dans ce qui suit, nous allons nous appuyer spciquement sur le mcanisme de Python. Intressons-nous au problme suivant : Si on envoie une variable en paramtre une fonction ou une procdure, et quon la modie dans la fonction, est-elle rellement modie aprs lappel ?
12.1
Premier exemple
Voici un exemple crit en Python : # Procdure ajoute def ajoute(a) : a=a+1 # Programme principal b=5 ajoute(b) print(b) La question est de savoir ce que va acher la ligne print(b). 5 ou 6 ? En Python, le passage des paramtres est comparable une aectation. Le l dexcution ressemble donc ceci : b=5 # excution de ajoute(b) : a=b a=a+1 # retour au prog principal print(b) Sur cet exemple, il est vident que le programme achera 5 (cest a qui contient 6, pas b). Le mcanisme responsable de ce comportement est plus complexe quil ny parait, et est assez spcique Python. Tout se passe comme si le paramtre tait pass par valeur : une copie du contenu de la variable est recopi de b vers a et cest la copie qui est modie, pas loriginal. Pour comprendre le mcanisme rel, dtaillons les deux lignes de code suivantes : 24
a=5 c=a+1 Nous avons dj mentionn que les variables, en Python, taient des rfrences vers des objets. Cette nuance est maintenant centrale. La gure suivante illustre la manire dont les lignes prcdentes, et tout particulirement la seconde, sont excutes 7 : 1 2 a 5 a 5 6 a 5 c 6
La ligne c=a+1 est dcompose en : 1. Lobjet droite du symbole daectation est cr, sauf si cest une rfrence simple (ici, cration de lobjet 6). 2. La variable gauche du symbole daectation rfrence maintenant le nouvel objet cr. Pour les variables numriques, on peut tout ignorer de ce mcanisme, et considrer que les variables sont de simples tiroirs pour ranger les nombres. Mais connatre ce mcanisme permet dexpliquer les autres comportements de Python que nous allons dtailler dans la suite. Voyons prsent ce qui se produit lors du passage dun paramtre : b=5 # excution de ajoute(b) : a=b a=a+1
1 a b 5 b 5
2 a b 5 6
3 b 5 a 6
1 b=5 : on cre lobjet 5, et b est une nouvelle rfrence vers cet objet 2 a=b : on a une simple rfrence droite du symbole =, a devient une nouvelle rfrence vers lobjet b, qui existait dj. 3 et 4 a=a+1 : on cre lobjet spci droite du = (6), et a devient une rfrence vers ce nouvel objet. On comprend donc pourquoi la valeur indique dans b na pas chang.
12.2
Second exemple
Voyons maintenant ce qui se produit lorsquon passe une liste en paramtre : # Procdure ajoute_liste # ajoute v la fin de la liste l def ajoute_liste(l,v) : l.append(v) # Programme principal lst=[1,2,3] ajoute_liste(lst,42) print(lst)
7. Dans cette gure, les objets sont reprsents par des carrs ou des rectangles, et les rfrences par des cercles. Nous conserverons cette convention par la suite.
25
Algorithmique et Programmation avec Python Nous posons toujours la mme question : que va acher le programme principal : [1,2,3] ou [1,2,3,42]. L aussi (ceci est toujours valable), le passage des paramtres est comparable une aectation. Aussi, la machine excute : lst=[1,2,3] # excution de ajoute_liste(lst,42) l=lst v=42 l.append(v) # retour au prog principal print(lst) Cette fois-ci, cest [1,2,3,42] qui va sacher, comme si la procdure ajoute_liste avait pu modier la liste originale, de manire contradictoire avec ce qui se passait prcdemment avec la procdure ajoute et un nombre entier... Dans cet exemple, tout se passe comme si la liste tait passe par adresse. Cest donc la liste originale qui est modie dans la procdure. Examinons dans un premier temps ce qui se cache derrire la simple ligne : lst=[1,2,3] Lors de lexcution de cette instruction, les objets 1, 2 et 3 sont crs, suivis dune liste qui contient les rfrences vers chacun des objets : les lment de la liste ne sont pas les objets mais des rfrences vers ces objets. Cette liste est enn rfrence par lst. On se trouve dans cette situation : lst
Voyons maintenant ce qui se cache derrire le passage de paramtres de notre second exemple : lst=[1,2,3] # excution de ajoute_liste(lst,42) # on fait grce du passage de 42... l=lst l.append(42) Le droulement des oprations est le suivant :
1 lst 2 lst l 3 lst l 4 lst l
42
42
Voici ce qui se produit : 1 lst=[1,2,3] : la liste lst est cre, et contient des rfrences vers 3 entiers. 2 l=lst : une nouvelle rfrence la liste est ajoute 3 et 4 l.append(42) : lobjet 42 est cr. Puis, la mthode append demande la liste rfrence par l de stocker une rfrence vers lobjet pass en paramtre. Dans ce cas, la liste dorigine (celle qui tait dsigne par lst est bel et bien modie. Ceci explique que la liste du programme principal, qui contenait [1,2,3], contient eectivement quatre lments aprs lappel ajoute_liste.
12.3
Troisime exemple
Voici maintenant un troisime exemple qui va nous permettre de terminer sur le mcanisme de passage des paramtres en Python. 26
# Procdure ajoute_liste # cre une liste contenant la liste dorigine # plus un lment def ajoute_liste2(l,v) : l=l+[v] # Programme principal lst=[1,2,3] ajoute_liste2(lst,42) print(lst) Le passage des paramtres est toujours quivalent une aectation et tout se passe comme si nous excutions : lst=[1,2,3] # excution de ajoute_liste2(lst,42) l=lst v=42 l=l+[v] # retour au prog principal print(lst) Cette fois-ci le programme ache [1,2,3]... Ceci peut paratre surprenant aprs la lecture du second exemple, mais sexplique trs simplement si nous reprenons nos schmas dobjets et de rfrences. Dessinons les objets mis en jeu dans le code : lst=[1,2,3] # excution de ajoute_liste2(lst,42) l=lst l=l+[42] Voici le droulement des oprations :
1 lst 2 lst l 3 lst l
1 4
2 5
42
lst
lst
42
42
Lexcution semble un peu plus complexe : 1 lst=[1,2,3] : la liste lst est cre, et contient des rfrences vers 3 entiers. 2 l=lst : une nouvelle rfrence vers la mme liste est ajoute La ligne suivante : l=l+[42] correspond, comme a a t le cas jusqu prsent, la cration de lobjet droite du signe =. Puis l devient une rfrence vers ce nouvel objet. La cration de lobjet l+[42] est la cration dune nouvelle liste, concatnation de deux listes (l et [42] 8 , de la mme manire que 3+5 provoquerait la cration dun nouvel entier, somme de 3 et de 5. 3 cration de la liste temporaire [42], an de lutiliser comme oprande.
8. Cest pour que [42] soit bien une liste et pas un nombre quil y a des crochets.
27
Algorithmique et Programmation avec Python 4 cration de la troisime liste, concatnation des deux autres. Notez que les objets (1,2, etc...) ne sont pas recopis, ce sont les rfrences vers ces objets (le contenu dune liste, ce sont les rfrences vers les objets) qui le sont. 5 La nouvelle liste sappelle maintenant l. Lancienne liste lst na donc pas t modie. Rsum Lorsquon passe des objets en paramtres dune procdure, il est ncessaire de savoir si les modications quon leur apporte dans la procdure altrent lobjet dorigine. Les cas simples sont rgls facilement par habitude (nombres entiers, simples listes), mais lorsquon hsite (liste de listes par exemple), une solution est de revenir au modle daectation de Python, qui permet dans tous les cas dexpliquer ce qui se produit.
13
Notation pointe
Bien que ce support de cours nait pas pour but denseigner la programmation oriente objets, il est ncessaire den comprendre certaines notations an de bien utiliser Python. Un objet est une entit compose dattributs (typiquement des valeurs) et de mthodes (les actions que lobjet peut eectuer). Cest le cas de la tortue du module turtle. Un objet de type Turtle encapsule une position, une orientation, la taille du trait tracer, la couleur utiliser etc... Tout ceci est stock dans lobjet. On peut par exemple disposer de deux tortues, lune crivant en rouge et lautre en bleu. Les mthodes sont les actions que peut eectuer la tortue : avancer (forward), tourner droite (right)... Les objets orent un plus grand niveau dabstraction : Si la tortue est en (0,0), orient selon langle 45, et que nous lui ordonnons davancer de 10, le calcul de la nouvelle position est fait dans lobjet : Nous donnons des ordres de haut niveau et lobjet gre ses dtails interne. Les ordres donns des objets (les appels de mthodes donc) utilisent la notation pointe. Pour faire avancer une tortue t1 de 50 par exemple, nous indiquerons t1.forward(50) qui signie : appeler la mthode forward de lobjet t1 et lui transmettre le paramtre 50. La fonction help de python, lorsquon lui donne un objet en paramtre, indique ainsi lensemble des attributs et des mthodes de lobjet en question. Voici un exemple dutilisation du module turtle : >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> from turtle import * t1=Turtle() t2=Turtle() t1.forward(50) t1.color(blue) t2.color(red) t2.right(90) t1.left(90) t2.forward(100) t1.forward(100)
Rappelons que nous avons dj utilis la notation pointe : l=[1,2,3,4] l.append(5) # ajoute 5 la liste l ... Dans lexemple qui prcde, l est une rfrence vers un objet, instance de la classe list. Cet objet contient des donnes (les rfrences vers les objets stocks dans la liste, et dautres choses encore) ainsi que des mthodes, que lobjet peut appliquer. La programmation oriente objets ne se rsume pas a bien sr, mais ce qui prcde est lessentiel savoir pour utiliser les objets.
28
14
14.1
Rcursivit
Rcurrence en mathmatiques
Nous allons commencer par lexemple de la fonction factorielle, qui peut tre dnie de manire rcursive : n n! = fact(n) = n fact(n 1) si n > 0 1 si n = 0
Voici quelques lments qui sont toujours prsents dans une dnition rcursive : lobjet de taille n est dni partir dun objet de taille plus petite (fact(n) est dni partir de fact(n 1)). Ce point nest pas toujours vident. les petits objets ne sont pas dnis de manire rcursive (cest le cas de fact(0) dans notre exemple).
14.2
Algorithme rcursif
De la mme manire quune dnition peut tre rcursive, un algorithme peut tre rcursif. fonction fact (n: entier ) : entier si n>0 : r nfact(n1) sinon r 1 retourner r
def fact(n) : if n>0 : r=n*fact(n-1) else : r=1 return r
Comment un algorithme rcursif fonctionne-t-il ? Une fonction rcursive utilise la pile des appels pour stocker les rsultats intermdiaires. Il nest pas ncessaire de savoir a pour crire des fonctions rcursives.
14.3
Quelques exemples
Suite de Fibonacci La suite de Fibonacci est dnie ainsi : F0 = 0 F1 = 1 Fn = Fn1 + Fn2 si n > 1
Wikimedia, Fibonacci2.jpg
def fibo(n) : if n<2 : return n return fibo(n-1)+fibo(n-2)

Wikimedia, Liber_abbaci_magliab_f124r.jpg
29
Algorithmique et Programmation avec Python Les tours de Hano Le jeu consiste dplacer une tour de plusieurs disques dun piquet vers un autre, en dplaant les disques un par un, sans jamais poser un grand disque sur un plus petit. Extrait de lArithmtique amusante de Lucas ( 1895) : Le mandarin N. Claus (de Siam) 9 nous raconte quil a vu, dans ses voyages pour la publication des crits de lillustre Fer-Fer-TamTam, dans le grand temple de Bnars, audessous du dme qui marque le centre du monde, trois aiguilles de diamant, plantes dans une dalle dairain, hautes dune coude et grosses comme le corps dune abeille. Sur une de ces aiguilles, Dieu enla au commencement des sicles, 64 disques dor pur, le plus large reposant sur lairain, et les autres, de plus en plus troits, superposs jusquau sommet ; cest la tour sacre de Brahma. Nuit et jour, les prtres se succdent sur les marches de lautel, occups transporter la tour de la premire aiguille de diamant sur la troisime, sans scarter des rgles xes que nous venons dindiquer, et qui ont t poses par Brahma. Quand tout sera ni, la tour et les brahmes tomberont, et ce sera la n des mondes !
archive.org, larithmetiqueam00lucarich
Il est possible dcrire un algorithme rcursif, trs concis, qui indique la liste des dplacements raliser pour un nombre quelconque de disques. Exemple pour 3 disques : 1 3, 1 2, 3 2, 1 3, 2 1, 2 3, 1 3. Cet exercice sera corrig en cours...
15
Rsoudre des problmes : mthode de travail
Un algorithme prsente gnralement plusieurs tapes de calcul, qui sont plus ou moins immdiates. Il faut tre capable de : hirarchiser les tapes de calcul dcouper le problmes en sous-problmes plus simples, et indpendants On rappliquera la mthode chaque sous-problme, jusqu arriver des problmes connus ou triviaux. Les avantages de la dcomposition en sous-problmes sont nombreux et dune grande importance : clart du code ; rpartition possible du travail entre plusieurs personnes ; possibilit de remplacer facilement un sous-algorithme par un autre plus ecace sans pour autant apporter de retouche lensemble du programme.
15.1
Dveloppement selon John Zelle
Dans son ouvrage Python Programming : an introduction to computer science 10 , John Zelle donne les recommandations suivantes : Analysez le problme Comprenez le problme rsoudre et sa nature. Essayez den apprendre le plus possible sur lui. Vous ne pourrez pas le rsoudre avant de le connatre parfaitement. Spciez le programme Dcrivez trs exactement ce que votre programme va faire. Vous ne devez pas dj vous soucier de la faon dont il va le faire, mais plutt dcider trs exactement ce quil va faire. Pour des programmes simples, cela consistera dcrire ce que seront les entres et les sorties du programme et ce qui les relie. Concevez le programme Formulez la structure globale du programme. Cest ce moment que vous traiterez de la faon dont le programme rsoudra le problme. Le travail principal est de concevoir le ou les algorithmes qui rempliront les tches pralablement spcies.
9. du collge Li-Sou-Stian 10. Deuxime dition, Franklin, Beedle & Associates
30
Notes de cours, Ensip 1A Codez Traduisez les algorithmes conus dans un langage de programmation et entrez les sur un ordinateur. Dans ce livre, nous programmerons nos algorithmes en Python. Testez/Dbuggez le programme Essayez votre programme et voyez sil fonctionne comme vous le souhaitiez. Sil y a des erreurs (souvent appeles bugs), revenez ltape prcdente et corrigez les. Lactivit qui consiste dbusquer et corriger les erreurs sappelle le debuggage 11 . Durant cette phase, votre objectif est de trouver des erreurs, et pour cela, vous devez tester tout ce qui vous passe par le tte et qui pourrait planter le programme. Il sera utile de garder lesprit la maxime : Nothing is foolproof because fools are too ingenious 12 Faites de la maintenance Continuez dvelopper votre programme en rpondant aux besoins des utilisateurs. La plupart des programmes ne sont jamais vraiment nis ; ils continuent dvoluer au l des annes dutilisation.
15.2
Rechercher un lment dans une liste trie
Nous allons nous intresser au problme suivant : Nous disposons dune liste dlments classs par ordre croissant. Nous voulons vrier si une valeur donne est dans la liste ou pas. Ce petit problme peut se rencontrer lintrieur de nombreux autres problmes. Une premire solution Voici un exemple de liste sur laquelle nous pourrions tre amens travailler : -5 -2 3 6 7 9
La premire tape consiste avoir une ide sur la faon de procder. Le problme ntant pas trs dicile, nous pouvons envisager une premire solution : Commencer sur la premire case. Tant que la case examine est strictement infrieure au contenu recherch, avancer dune case. Si on puise la liste ou quon tombe sur une valeur strictement suprieure la valeur recherche, cest quelle nest pas dans la liste. Sinon, elle y est. Nous devons maintenant essayer de formaliser un peu plus notre algorithme. En premier lieu, nous allons choisir comme structure de donnes, une liste (ou un tableau) telle quon en trouve dans Python. La numrotation des cases commencera 0 13 . Limportant pour la suite est que la structure de donnes doit pouvoir stocker une collection dobjets, ordonns, et numrots. Cette tape de formalisation est dicile franchir lorsquon dbute en programmation : fonction recherche( l : liste , v: valeur ) i 0 repeter tant que i <longueur(l) et l [ i ]<v i i+1 si i longueur(l) ou l [ i ]>v : retourner Faux sinon retourner vrai Il ne nous reste plus qu traduire cet algorithme, par exemple en Python : def rechercher(l,v) : i=0 while i<len(l) and l[i]<v : i=i+1 if i>=len(l) or l[i]>v : return False else : return True De la mme ide de dpart nous aurions pu dcliner un algorithme formel un peu dirent et nir sur un autre programme tout aussi correct :
11. On dit parfois dverminage en franais, mais personnellement, je trouve que a supprime le ct aectif... ;-) 12. Rien nest lpreuve des imbciles, car ils sont trop malins. 13. la numrotation partir de 0 est habituelle en informatique, mme si elle nest pas utilise dans tous les langages.
31
def rechercher(l,v) : i=0 while True : if i>=len(l) or l[i]>v : return False if l[i]==v : return True i=i+1
Plusieurs mthodes pour un problme ? Notre mthode (notre algorithme) est-elle ecace ? Si la valeur cherche est plus grande que la dernire case, nous devons tout parcourir Cette mthode revient rechercher un mot dans le dictionnaire en tournant les pages une par une depuis la premire jusqu la bonne page... Reprenons la comparaison avec le dictionnaire pour essayer de dgager une autre mthode : Pour rechercher dans un dictionnaire, nous tournons les pages par paquets, quitte parfois revenir en arrire. Mme si la recherche dans un dictionnaire, manuellement, est approximative, lide est douvrir le dictionnaire, et den dduire si le mot chercher est avant ou aprs. Une fois ceci dcid, on ouvre nouveau le dictionnaire sur la portion slectionne et on compare nouveau avec le mot cherch. chaque tape, nous rduisons ainsi peu prs de moiti le nombre de pages dans lesquelles il reste eectuer la recherche. Algorithme de la mthode dichotomique Pour chercher v entre les cases g et d, regarder le contenu de la case du milieu m (m = (g + d)/2). Sil est plus petit que v , continuer chercher dans lintervalle m, d sinon, continuer chercher dans lintervalle g, m. Voici lalgorithme, crit de manire plus formelle : Pour rechercher v dans la liste l : g,d 0,len ( l ) 1 rpter tant que la tranche g,d fait plus dune case : mmilieu de g,d si v>l[m] : gm+1 sinon : dm si l [g]=v : retourner Vrai sinon retourner Faux Attention aux dicults caches Les raccourcis, qui nexisteront plus dans le programme nal (tout sera dtaill) peuvent contenir des erreurs potentielles. Nous avons par exemple crit que m tait le milieu de g, d. Tous ces nombres tant entiers, la manire de faire larrondi sur m a son importance. Voici le programme Python correspondant : def cherchedicho(l,v) : g,d=0,len(l)-1 while g!=d : m=(g+d)//2 if v>l[m] : g=m+1 else : d=m if l[g]==v : return True else : return False Cette fonction a beau tre courte et assez simple, elle peut contenir des erreurs qui ne sont pas videntes dtecter. Par exemple, si nous avions crit : # ATTENTION, cette fonction ne marche pas def cherchedicho(l,v) : g,d=0,len(l)-1 while g!=d : m=(g+d)//2 if v<l[m] : d=m-1 32
Notes de cours, Ensip 1A else : g=m if l[g]==v : return True else : return False alors le programme naurait pas fonctionn. Vous vous en rendrez compte en excutant la main ce que fait lalgorithme pour rechercher la valeur 5 dans la liste [3,4]. Excution manuelle Excuter un algorithme la main, pour quelques jeux de valeur, est essentiel dans la dtection des erreurs. Il faut le faire de manire systmatique, et ne pas sen priver, plus forte raison, lorsque lalgorithme est simple. Comparaison des mthodes Nous voyons donc que pour rsoudre un problme particulier, il y a plusieurs mthodes. Une fois la mthode (lalgorithme) choisie, on peut encore trouver des programmes avec des petites variantes. Est-il intressant de trouver plusieurs mthodes ou la premire fera-t-elle tout le temps laaire ? La gure II.2 (gauche) reprsente en abscisse le nombre de valeurs de la liste (la valeur max est environ 10 millions) et en ordonne le temps mis pour rechercher 200 valeurs dans cette liste (valeur max : 0.1 secondes). Cette courbe a t obtenue en utilisant la mthode dichotomique. La gure II.2 (droite) reprsente 14 les temps dexcution de la premire mthode, pour les mmes essais, ainsi que, plaqu sur laxe des abscisses, nouveau les rsultats de la mthode dichotomique.
0.1 Recherche dichotomique 2000 1800 0.08 1600 1400 0.06 1200 1000 0.04 800 600 0.02 400 200 0 0 Recherche dichotomique Recherche nave
107
107
Figure II.2 Comparaison des temps (s) dexcution de deux algorithmes de recherche
Notion de complexit Pouvions nous prdire les performances de ces algorithmes sans les programmer, an destimer leurs mrites respectifs et choisir la bonne mthode ? Dans le cas de la recherche nave, le nombre doprations dans la premire boucle est proportionnel la position de la valeur dans le tableau. La n de lalgorithme sexcute en temps constant. En moyenne, le nombre doprations est donc k1 n 2 + k2 . On dit que lalgorithme est en (n) ou linaire. Cela signie que son temps dexcution varie comme n. Autrement dit, lorsque n est grand, si on multiplie la taille des donnes par k , le temps dexcution sera lui aussi multipli par k . Notation de Landau Une fonction g (n) appartient (f (n)) si : n0 , k1 > 0, k2 > 0|n > n0 , k1 f (n) g (n) k2 f (n)
La notation permet en quelques sorte dencadrer le comportement asymptotique dune fonction.

14. En rouge si vous avez la couleur...
33
Algorithmique et Programmation avec Python Une fonction g (n) appartient O(f (n)) si : n0 , k > 0|n > n0 , g (n) kf (n)
La notation O permet donc de majorer le comportement asymptotique dune fonction. Malgr cette dirence, on trouve trs souvent, dans les calculs de complexit, O la place de . Il convient donc de faire attention la convention utilise par lauteur. Dans le cas de la recherche dichotomique, le corps de la boucle sexcute en temps constant. La boucle sexcute jusqu ce que g et d soient gaux. La distance g d est divise par 2 chaque tour. On a donc ln2 (n) tours de boucle. Le nombre doprations est donc : k1 ln2 (n) + k2 . On dit que lalgorithme est en (log (n)) ou logarithmique. Autrement dit lorsque n est grand, pour doubler le temps dexcution, il faut lever le nombre de cases au carr ! Cet algorithme est donc incroyablement plus rapide que le prcdent. Est-ce vraiment important ? Un algorithme logarithmique est considrablement plus ecace quun algorithme linaire (lui-mme considrablement plus ecace quun algorithme quadratique, ou encore exponentiel). Cette dirence devient fondamentale si la taille des donnes est importante. On peut estimer que pour un tableau de 1010 valeurs, 1. le temps moyen pour retrouver un seul nombre serait denviron 2 heures dans le premier cas 2. il serait de moins dune milliseconde dans lautre cas
Le livre et la tortue Gustave Dor
15.3
Algorithmes de tri
Nous allons nous intresser maintenant un second problme, celui des trs classiques algorithmes de tri. Nous supposons que nous disposons dune liste dobjets, par exemple : -2 9 -5 7 3 6
Nous devons crire un algorithme capable de fournir en retour une liste trie par ordre croissant : -5 Tri par slection Une premire ide est de procder ainsi : 1. rechercher le plus petit, le mettre au dbut, 2. rechercher le second plus petit, le mettre en deuxime position 3. ... Une fois le minimum plac en premire position, tout se passe comme si on recommenait la mme chose sur tout le tableau priv du premier lment. Puis nouveau sur tout le tableau priv des deux premiers etc... Voici lalgorithme correspondant. Notez comment le problme a t dcompos en deux parties : lalgorithme gnral tri_selection et la fonction rechmin, qui recherche le plus petit lment dans une portion de tableau. En cas, de problme, nous pouvons tester sparment la fonction rechmin et ainsi cibler plus facilement les erreurs. 34 -2 3 6 7 9
Notes de cours, Ensip 1A fonction tri_selection ( tableau t) / Trie le tableau sur place / n taille (t) repeter pour i de 0 n2 : j rechmin(t,i) changer le contenu des cases i et j fonction rechmin(tableau t, entier i ) : entier min=i repeter pour j de i +1 taille (t) 1 : si t [ j]<t[min] : minj retourner min Cet algorithme est quadratique (complexit en (n2 )). Tri rapide Voici une autre ide dalgorithme (probablement moins facile avoir) : 1. Slectionner une valeur au hasard dans le tableau : le pivot 2. Organiser le tableau en deux parties : gauche les lments infrieurs au pivot et droite, les lments suprieurs au pivot. 3. Trier les deux parties avec la mme mthode Partitionner le tableau Il existe plusieurs faons de partitionner le tableau, qui sont plus ou moins quivalentes, mais lide reste la mme : mettre les petits lments gauche, et les grands droite. Voici lalgorithme du tri rapide : fonction tri_rapide ( tableau t, indices d, f ) si f>d : ppartitionner(t ,d, f ) tri_rapide (t ,d,p1) tri_rapide (t ,p+1,f) fonction partitionner ( tableau t, indices d, f ) : entier pindice au hasard entre d et f / le pivot / echanger t [ f ], t [p] / on met le pivot la n / i d j f 1 repeter tant que i j : repeter tant que i j et t [ i ] t[f ] : i i+1 repeter tant que i j et t [ j ] t[f ] : j j1 si i <j : echanger t [ i ] et t [ j ] changer t [ f ] et t [ i ] retourner i La fonction partitionner a un temps dexcution proportionnel la taille de la tranche de tableau. La fonction tri_rapide est rcursive. Son temps dexcution est donn par une relation de rcurrence :
partitionner
T (n) = a n +2 T (n/2)
puisquen moyenne, p est au milieu de la tranche
Tous calculs faits, on trouve une complexit en (n log(n)) Comme pour le cas de la recherche, connatre la complexit des algorithmes est une indication particulirement utile ds que lon a beaucoup de grandes quantits de donnes. La gure II.3 montre les temps mis pour trier des tableaux de 500 10 millions de valeurs, en utilisant 3 algorithmes dirents : le tri par fusion, le tri par slection et le tri rapide. 35

Temps d execution moyen en millisecondes de trois algorithmes de tri en fonction du nombre dentiers ` a trier 200 Temps (ms) 180 160 140 120 100 80 60 40 20 0 Fusion S election Rapide k.n.ln (n) k.n 2
0.2
0.4
0.6
0.8
1 1.2 Nb dentiers
1.4
1.6
1.8 x 10
2
5
Figure II.3 Comparaison des temps dexcution de plusieurs algorithmes de tri pour n < 500 le temps dexcution reste infrieur 1 milliseconde. pour n = 100 000, le tri par slection met quelques dizaines de secondes sexcuter, contre 0,4 secondes pour le tri rapide. pour n = 10 millions (estimation), le tri par slection mettrait plus de 2 jours, contre environ 5 secondes pour le tri rapide.
16
Rcursivit et Logo
Le monde tel quil est vu par Logo, un langage but pdagogique invent dans les annes 60 par Seymour Papert, est un espace en deux dimensions 15 dans lequel se dplace une tortue, qui peut ou non laisser une trace des endroits o elle passe. Un programme Logo est compos dordres donns la tortue (comme avance de 10 ou tourne gauche de 90 degrs). Nous allons ici utiliser le module turtle de Python, qui permet de programmer comme en Logo. Les programmes pouvant tre rcursifs, cest laspect graphique du Logo et la possibilit dutiliser la rcursivit qui permet de raliser des gures complexes en trs peu de lignes.
16.1
criture des primitives
Le programme suivant trace un carr ayant pour ct la valeur passe en paramtre : def carre(cote) : for i in range(4) : fd(cote) rt(90) Pour utiliser ce programme, il faut ensuite entrer, dans un shell Python : from turtle import * carre(100)
16.2
Courbe de Koch
Supposons que nous dsirions crer la gure II.4(a), chaque segment tant de longueur gale et quelconque. Nous cririons la primitive suivante : def fig(l) : fd(l)
15. lorigine il ny avait que deux dimensions. Les versions actuelles de Logo permettent de faire de la 3D.
36
(a) Dbut de la courbe de Koch
(b) tape 2 de la construction...
(c) tape 3 de la construction...
(d) Courbe de Koch
Figure II.4 Construction de la courbe de Koch lt(60) fd(l) rt(120) fd(l) lt(60) fd(l) Considrons prsent la gure II.4(b). Cest la mme que prcdemment, except que chaque segment a t remplac par un modle rduit de la gure elle mme.... Sur la gure II.4(c), nous avons nouveau remplac chaque segment par le dessin de dpart. Et ainsi de suite, jusqu obtenir ( linni...), la courbe complte (gure II.4(d)). Naturellement, linni est ici li la taille dun pixel lcran. Comment tracer de telles gures ? La rponse est trs simple, et correspond tout fait la faon de tracer la gure la main. Il sut de remplacer chaque segment par la gure elle-mme, trois fois plus petite, comme dans le programme suivant : # Attention, cette version nest pas fonctionnelle def fig(l) : fig(l/3) lt(60) fig(l/3) rt(120) fig(l/3) lt(60) fig(l/3) Ce programme comporte nanmoins une grosse erreur. Lorsque longueur vaudra par exemple 1, la tortue va continuer 1 la descente rcursive et vouloir tracer la gure pour une arte de 1 3 , puis 9 , ... sans jamais sarrter... Nous devons donc, de mme que nous arrtons la descente rcursive lors dun dessin la main, indiquer la tortue quel moment elle ne doit plus remplacer un segment potentiel par la gure complte, mais bien tracer le segment. Nous pouvons par exemple dcider que lorsque la longueur sera infrieure ou gale un, alors, il faudra arrter la descente rcursive. ce moment, au lieu de tracer le dessin de la gure II.5(a), il faudra faire un simple segment comme indiqu gure II.5(b). Voici maintenant notre programme complet et fonctionnel : def fig(l) : if l<2 : fd(l) return fig(l/3) lt(60) fig(l/3) rt(120) 37
gu eu r/
3 lon r/ eu gu lon
longueur/3
(a)
longueur/3
longueur
(b)
Figure II.5 Arrt de la rcursivit pour la courbe de Koch fig(l/3) lt(60) fig(l/3)
16.3
Autres gures
Il existe de nombreuses courbes, que lon peut obtenir simplement de manire rcursive. En voici quelques-unes : Triangle de Sierpinski Le triangle de Sierpinski est obtenu par les oprations suivantes. On dessine tout dabord un triangle (gure II.6(a)), puis, on divise en 4 triangles (gure II.6(b)). Chaque triangle extrieur (il y en a 3) est considr comme le triangle de dpart. Il est donc divis en 4 (gure II.6(c)). Au bout de quelques itrations, on obtient la gure II.6(d).
(a)
(b)
(c)
(d)
Figure II.6 Trac du triangle de Sierpinski
Courbe du dragon La rcursivit est parfois croise en ce sens que ce nest pas toujours la procdure A qui sappelle elle-mme. Ce peut tre la procdure A qui appelle la procdure B, et la procdure B qui appelle la procdure A. Cest par exemple le cas dans la courbe du dragon. Sur la gure II.7. sont reprsentes les courbes : 1. dragon droit de profondeur 1 2. dragon gauche de profondeur 1 3. dragon droit de profondeur 2 4. dragon gauche de profondeur 2 38
Notes de cours, Ensip 1A 5. dragon droit de profondeur 3 6. dragon gauche de profondeur 3 7. dragon gauche de profondeur 5 8. dragon gauche de profondeur 10 (les cases sont sont plus petites que prcdemment)
1 2 3 4 5 6 7 8
Figure II.7 Courbe du dragon Vous devriez remarquer (mais ce nest pas facile) quun dragon gauche de profondeur n est compos dun dragon gauche de profondeur n 1 dune rotation de + 2 , et dun dragon droit de profondeur n 1. Inversement un dragon droit de profondeur n est compos dun dun dragon gauche de profondeur n 1 dune rotation de 2 , et dun dragon droit de profondeur n 1. Enn, un dragon de profondeur 0 est simplement un trait. Si lon rduit la taille des traits 1, on obtient comme dragon gauche de profondeur 15 lobjet de la gure II.8.
Figure II.8 Dragon gauche de profondeur 15
39
40
Chapitre III
Complments sur Python

Dans ce chapitre sont regroupes des informations sur lutilisation de Python. Elles ne sont pas exhaustives (le lecteur est encourag consulter la documentation ocielle), mais pourront aider dbloquer rapidement bon nombre de situations.
17
17.1
Types simples
Entiers
Le type int, permet de reprsenter les entiers de taille machine (quelques octets) ou les grands entiers (limits uniquement par la taille de la mmoire). Le passage de lun lautre (entiers machines ou grands entiers) est transparent pour lutilisateur depuis la version 3 de Python. Pour indiquer une valeur entire, il est possible dutiliser direntes bases : >>> >>> >>> >>> 42 # en dcimal 0o52 # en octal 0x2A # en hexadcimal 0b101010 # en binaire
Les oprations disponibles sur les nombre entiers sont rsumes dans la table III.1. Les oprations de conversion vers les direntes bases sont raliss avec les fonctions bin, oct, et hex. Les oprations arithmtiques ordinaires sont disponibles sur les entiers : >>> 15 >>> -3 >>> 54 >>> 1.5 >>> 1 >>> 3 6+9 6-9 6*9 9/6 9//6 # division entire 9%6 # reste
Division entire Notons quen Python 3, loprateur de division / est un oprateur de division non entire contrairement ce qui se faisait en Python 2 et contrairement ce qui se fait dans de nombreux langages. Mme si une division tombe juste, le rsultat de lopration / sera un float. Il faut donc penser, lorsquon souhaite manipuler des entiers, utiliser loprateur //.
17.2
Boolens
Les deux seules valeur du type bool sont True et False. Ces deux valeurs peuvent tre entres litralement ou peuvent tre le rsultat doprateurs de comparaison, comme >, <, >=, <=, == (gal), != (dirent). 41
Algorithmique et Programmation avec Python Opration x+y x-y x*y x/y x//y x%y -x x&y x|y x^y x<<y x>>y ~x abs(x) divmod(x, y) float(x) hex(x) oct(x) bin(x) int(x) pow(x, y[, z]) repr(x) str(x) Type retour int int int oat int int int int int int int int int int (q,r) oat str str str int int str str Description Somme Dirence Produit Quotient Quotient entier Reste de la division entire Oppos de x Opration et sur les bits de x et y Opration ou sur les bits de x et y Opration ou exclusif sur les bits de x et y Dcalage gauche de y bits sur x Dcalage droite de y bits sur x Inversion des bits de x Valeur absolue Quotient (q) et reste (r) de la division entire de x par y Conversion vers un oat Reprsentation hexadcimale Reprsentation octale Reprsentation binaire Conversion vers un int (pas de changement donc...) x la puissance y modulo z si z est prcis Reprsentation ocielle sous forme de chane de caractres Conversion en chane de caractres
Table III.1 Oprations disponibles sur les nombre entiers Les oprateurs dont les oprandes sont des boolens sont les oprateurs logiques or, and, not. valuation incomplte des expressions logiques Lvaluation des expressions logiques nest pas complte. Elle sarrte ds que le rsultat est connu. En logique, dans lexpression a and b, il sut que a soit valu False pour que le rsultat soit False. En Python, si a est valu False, le rsultat de a and b sera a. De mme si a est valu True, le rsultat de a and b sera b. Ceci permet de construire des expressions riches, mais qui ne sont pas toujours trs simples comprendre. notre niveau, il convient dviter de les crire, mais il faut tre capable de les comprendre. Par exemple, 6<10 and 6*9 vaut 54 puisque 6<10 est vrai. Inversement, 42==6*7 or 6*9 vaut True (valeur de 42==6*7) En rsum, x and y : vaut x si x est faux (et alors y nest pas valu) vaut y si x est vrai (x et y sont valus) De mme, x or y : vaut y si x est faux (x et y sont valus) vaut x si x est vrai (et alors y nest pas valu)
Les expression qui ne sont ni le rsultat de connecteurs logiques, ni le rsultat doprateurs de comparaison sont values True sauf : False, None, la valeur 0 ou 0.0, les collections vides (tuples, dictionnaires, listes, ensembles).
17.3
Nombres virgule ottante
Le type float permet dutiliser la reprsentation en virgule ottante (Norme ieee-754). Toute valeur numrique comportant un point dcimal ou entre en notation scientique sera de type float. Le type float de Python correspond au codage en double prcision 1 (cest dire au type double du C) : >>> a=7.54 >>> b=7e3 >>> c=0.745e1 Le module math contient de nombreuses fonctions mathmatiques (fonctions trigonomtriques, logarithmiques...). >>> import math
1. sys.float_info contient des informations sur le codage utilis.
42
Notes de cours, Ensip 1A >>> >>> >>> >>> a=4.5 math.sin(a) b=1e-10 math.log10(b)
17.4
Nombres complexes
Python ore la possibilit de manipuler des nombres complexes sans utiliser de module complmentaire. Un nombre complexe peut tre indiqu littralement en utilisant j ou le constructeur complex : >>> >>> >>> >>> a=4+3j b=5+0j a=complex(4,3) b=complex(5,0)
Ne pas confondre le j complexe et la variable j. Ce qui suit ne cre pas de nombre complexe : # Ajoute 5 et le contenu de la variable j >>> a=5+j # Multiplie le contenu de j par 3 et ajoute 5. >>> b=5+3*j Pour utiliser les nombres complexes, il faudrait crire : >>> a=5+1j >>> b=5+3j Voici quelques mthodes et accesseurs sur les nombres complexes (le module cmath contient dautres outils) : >>> a=5+4j >>> a.real 5.0 >>> a.imag 4.0 >>> abs(a) 6.4031242374328485
18
Types collections
Les collections : listes, tuples, objets itrables etc. font la force et lecacit des langages interprts modernes. Savoir les manipuler permet de concevoir des programmes concis, lgants et ecaces. Conteneur ou Collection objet destin contenir dautres objets. Une collection peut tre ordonne (cest alors une squence) ou non. Les conteneurs standards sont : list tuple set str dict... Squence collection ordonne dlments indics par des entiers. Les squences Python sont par exemple : list,tuple,str. On peut accder un lment dune squence en prcisant entre crochets le numro dordre de lenregistrement. La numrotation commence 0. (un objet de type range se comporte aussi comme une squence) Modiable capacit pour un objet (pas forcment une collection) de modier son contenu sans que lobjet soit recr. Ce point est dlicat, et il est assez spcique Python. Dans le cas dun conteneur, on peut le qualier de rcursivement (ou compltement) non modiable sil est non modiable et que tous les lments quil contient sont rcursivement non modiables. Les termes anglais pour modiable/non modiable sont : mutable, immutable. Type list squence modiable dlments ventuellement htrognes Type tuple squence non modiable dlments ventuellement htrognes. Hashable Un objet hashable est un objet rcursivement non modiable. Il peut servir de cl dans un dictionnaire. Les lments dun ensemble (set) doivent tre hashables. Type dict (dictionnaire ou tableau associatif) : collection non ordonne modiable dlments ventuellement htrognes. Un tableau associatif est un type de donnes permettant de stocker des couples cl/valeur, avec un accs rapide la valeur partir de la cl. Celle-ci ne peut bien sr tre prsente quune seule fois dans le tableau. La cl doit tre hashable. Le type dict fait partie des collections de la catgorie Mapping qui associent un objet un autre. 43
Algorithmique et Programmation avec Python Type list tuple set str dict bytearray frozenset bytes Ordonn ? Oui Oui Non Oui Non Oui Non Oui Itrable ? Oui Oui Oui Oui Oui Oui Oui Oui Modiable ? Oui Non Oui Non Oui Oui Non Non
Table III.2 Proprits des collections Type set collection non ordonne dlments hashables distincts. Itrable capacit, pour une collection, dgrener ses valeurs, par exemple avec une boucle for Python. Les objets itrables peuvent tre parcourus, mais on ne peut pas ncessairement prendre un lment ou un autre en ladressant. La table III.2 donne les proprits des dirents types collection.
18.1
Accder aux lments
On peut accder aux lments dune squence par leurs numros : >>> l=[1,3,5,7] # cration dune liste >>> print(l,l[1]) [1, 3, 5, 7] 3 >>> t=(2,4,6,8) # cration dun tuple >>> print(t,t[2]) (2, 4, 6, 8) 6 >>> s=Supercalifragilistique # cration dune chane >>> print(s,s[4]) Supercalifragilistique r Indices ngatifs En Python, il existe un moyen de dsigner les lments dune squence en partant de la n : s[-1] est le dernier lment de la squence, s[-2] est lavant-dernier etc... En rgle gnrale, si k>0, s[-k] vaut s[len(s)-k]. On peut extraire une tranche de squence, voire une tranche chantillone 2 : >>> >>> [0, >>> [3, >>> [3, >>> [1, >>> [1, >>> [0, t=list(range(11)) # 0 1 2 ... 10 t[:] 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] t[3:] 4, 5, 6, 7, 8, 9, 10] t[3:6] 4, 5] t[1:8] 2, 3, 4, 5, 6, 7] t[1:8:2] 3, 5, 7] t[::2] 2, 4, 6, 8, 10]
Pour les dictionnaires, les numros sont remplacs par des cls (nimporte quel lment hashable) : >>> cri={chien : aboie, chat:miaule, caravane:passe} >>> cri {chien: aboie, chat: miaule, caravane: passe}
2. Lopration dextraction dune tranche de tableau se nomme slicing en anglais. En Python, elle cre un nouvel objet, et non une vue sur lobjet dorigine.
44
Notes de cours, Ensip 1A >>> cri[chat] miaule
18.2
Agir sur les collections
Lorsquon agit sur un objet (s), il y a deux faons de le faire : En aectant s, comme dans s=s[:]+s[5]. Ceci fonctionne que lobjet soit modiable ou non. On extrait s[:] et s[5], et on ralise lopration +, le rsultat tant un nouvel objet (il se peut que lopration + ne soit pas possible avec les oprandes donnes...). Puis s rfrencera (aectation) le nouvel objet, lancien ntant plus rfrenc par s (mais il existe peut tre encore, rfrenc par une autre variable). On peut constater que lobjet rfrenc par s nest plus le mme en contrlant la valeur id(s) avant et aprs lopration. En appelant une mthode qui agit sur lobjet qui est rfrenc par s comme dans s.sort(). Dans ce cas, lidentiant (id) de s nest pas modi et cest lobjet qui tait dsign par s qui est modif (le type de s doit donc tre modiable, ce qui implique quon peut trier ainsi une liste, mais pas un tuple). Il existe en outre quelques algorithmes implments de deux manires : modiant lobjet dorigine retournant un nouvel objet modi Par exemple, si t est une squence : t.sort() trie la squence t sur place (elle doit tre modiable) sorted(t) ne modie pas t et renvoie une nouvelle squence trie (t na pas besoin dtre modiable) On trouve de mme : reversed(t) et t.reverse() etc...
18.3
Copier une collection
La copie des types simples ne pose pas de problme particulier. Il faut en revanche tre prudent avec les collections. On peut copier une collection ainsi : >>> a=[1,2,[5,6,7]] >>> b=list(a) Mais cest une copie supercielle (shallow copy). Si un des lments est modiable (si cest une liste par exemple), a peut tre un problme. Le test suivant permet de comprendre ce qui se passe : >>> a=[1,[1,2]] >>> print (id(a), id(a[0]), id(a[1]) ) 19360368 9357408 19351600 >>> b=list(a) >>> print (id(b), id(b[0]), id(b[1]) ) 20017520 9357408 19351600 >>> print(a,b) [1, [1, 2]] [1, [1, 2]] >>> b[0]=42 >>> print(a,b) [1, [1, 2]] [42, [1, 2]] >>> b[1][0]=54 >>> print(a,b) [1, [54, 2]] [42, [54, 2]] Pour obtenir un comportement dirent, on dispose dun module copy qui ore une copie en profondeur (deep copy) : >>> >>> >>> >>> >>> [1, import copy a=[1,2,[5,6,7]] b=copy.deepcopy(a) b[2][0]=3.2 print(a,b) 2, [5, 6, 7]] [1, 2, [3.2, 6, 7]]
18.4
Oprations sur les collections
Les oprations sur les collections sont regroupes dans direntes tables : 45
Algorithmique et Programmation avec Python Oprations Oprations Oprations Oprations Oprations sur sur sur sur sur les les les les les squences (listes, tuples, chanes), table III.3 listes, table III.4 itrables (listes, tuples, chanes, dictionnaires, ensembles...), table III.5 dictionnaires, table III.6 ensembles, table III.7 Type retour list bool bool bool bool bool bool item list Description Renvoie une liste contenant les objets de sequence Retourne True si x et y contiennent les mme objets (au sens de == pour chaque paire dobjets) Vrai si x est avant y (comparaison lmnt par lment, comme pour lordre lexicographique) ou si x==y. Faux sinon. Vrai si x est aprs y (comparaison lmnt par lment, comme pour lordre lexicographique) ou si x==y. Faux sinon. Vrai si x est avant y (comparaison lmnt par lment, comme pour lordre lexicographique). Faux sinon Vrai si x est aprs y (comparaison lmnt par lment, comme pour lordre lexicographique). Faux sinon Vrai si x et y sont de longueur dirente ou si un item de x est dirent dun item de y. Faux sinon. Retourne litem en position i de x. Si i est strictement ngatif, vaut x[len(x)+i] Retourne la tranche ditems de la position i la position j-1. Si i nest pas prcis, il est pris gal 0. Si j nest pas prcis, il est pris gal len(x). Les indices ngatifs ont la mme signication que ci-dessus. Retourne un itrateur sur x Reprsentation ocielle de x sous forme de chane de caractres Table III.3 Oprations sur les squences
Mthode list(sequence) x==y x>=y x<=y x>y x<y x!=y x[i] x[[i]:[j]]
iter(x) repr(x)
iterator str
46
Mthode list() [item[,item]+] del x[i] x[i]=e x+=y x*=i x.append(e) x.count(e) x.extend(iter) x.index(e,[i,[j]])
Type retour list list ............. ............. ............. ............. None int None int
x.insert(i, e) x.pop([index]) x.remove(e) x.reverse() x.sort()
None item None None None
Description Renvoie une liste vide Liste contenant les //items// donns entre crochets Eace lobjet en position i de x (et dcale les autres lments) Aecte litem e la position i de x. Litem i doit dj exister (la liste nest pas tire). Modie la liste x en lui ajoutant les lments de y Modie la liste x pour quelle contienne i copies concatne de la liste originale. Modie x en lui ajoutant e comme dernire lment. Retourne le nombre dapparitions de e dans x. Les apparitions sont dtectes en utilisant ==. Modie x en lui ajoutant les lments de litrable iter. Retourne lindice du premier lment de x gale e (au sens de ==), situ entre les indices i et j-1. Lve lexception ValueError si un tel lment nexiste pas. Modie x en insrant e de tel sorte quil se trouve lindice i. Supprime (modie donc x) et renvoie llment en position index. Si index nest pas prcis, il est pris par dfaut gal len(x)-1. Modie x en supprimant la premire occurence de e. Lve lexception ValueError si e nest pas trouv. Modie x en renversant lordre de ses lments. Modie x pour quil soit tri en utilisant la mthode de comparaison __cmp__ de ses lments. La mthode accepte deux paramtres optionels : key et reverse. Si reverse vaut True, le tri est fait lenvers (dcroissant). Le paramtre key est une fonction qui prend en paramtre un lment et renvoie la valeur qui sera utilise rellement pour le tri. Table III.4 Oprations sur les listes
Mthode x+y x*i e in x all(x) any(x) enumerate(x,start) len(x) max(x,key) min(x,key) reversed(x) sorted(x,key,reverse)
sum(x,start) zip(x1,...,xN)
Description Concatnation Retourne un nouvel itrable contenant i copies de x Retourne True si e est dans x et False sinon Vaut True si chaque lment de x est valu True Vaut True sil y a au moins un lment de x valu True Retourne une squence de tuples de la forme (index,item) numrant les lments de x avec leur position. start est un oset appliqu la position initiale (0). Nombre dlments de x Retourne le plus grand lmnt de x. Largument key a le mme rle que pour la fonction sorted Retourne le plus petitlmnt de x. Largument key a le mme rle que pour la fonction sorted() Retourne un nouvel itrateur contenant les mme lments que x mais en sens inverse. Retourne une liste contenant les mmes lments que x, mais tris en utilisant la mthode de comparaison __cmp__ de ses lments. Si reverse vaut True, le tri est fait lenvers (dcroissant). Le paramtre key est une fonction qui prend en paramtre un lment et renvoie la valeur qui sera utilise rellement pour le tri. Retourne la somme des lments de x augmente de start (qui vaut 0 par dfaut) Retourne un nouvel itrateur contenant des tuples de N lment. Chaque lment est pris dans un des itrateurs. Exemple : zip((a,b,c),(1,2,3)) vaudra ((a,1),(b,2),(c,3)) Table III.5 Oprations sur les itrables
47
Mthode dict() dict(mapping) dict(seq) dict(**kwargs) k in D del D[k] D1==D2 D[k] iter(D) len(D) D1!=D2 repr(D) D[k]=e D.clear() D.copy() D.get(k[,e]) D.items()
Description Retourne un dictionnaire Construit un dictionnaire partir dun objet de type mapping (cl/valeur) Construit un dictionnaire partit dune squence. Remplace le code D = {}; for k, v in seq: D[k] = v Construit un dictionnaire partir de paires nom=valeur : dict(alpha=1,beta="omega") Vaut True si k est une cl de D et faux sinon Eace la cl k du dictionnaire Retourne True si les dictionaires ont les mme cls associes aux mmes valeurs (comparaison avec ==) Renvoie la valeur associe la cl k dans D. Si la cl k nexiste pas,lve lexception KeyError Renvoie un itrateur sur le dictionnaire Renvoie le nombre de cls de D Vaut Vrai si D1 et D2 ont des cls direntes ou que certaines cls identiques sont associes des valeurs direntes Retourne la reprsentation de D Associe la valeur e la cl k Vide D de ses cls Retourne une copie non rcursive de D Retourne D[k] si k est une cl de D et e sinon (par dfaut, e vaut None Retourne une vue sur le dictionnaire. Souvent utilis sous la forme : for k,v in D.items():... Table III.6 Oprations sur les dictionnaires
Mthode set(iter) k in E E.pop() E | F E ^ F E & F E - F E <= F
Description Retourne un ensemble, contenant les lments de litrable Vaut True si k est dans lensemble et faux sinon Eace un lment au hasard et le renvoie Ensemble union de deux ensembles Ensemble des lments qui sont dans E ou dans F, mais pas dans E et F (dirence symtrique) Ensemble intersection de E et F Ensemble des lments qui sont dans E mais pas dans F Vaut True si E est un sous ensemble de F Table III.7 Oprations sur les ensembles
48
19
Types modiables ou non
En Python, un type peut tre modiable ou non. Cette distinction est droutante lorsquon dbute. Type int float tuple str list dict set Modiable/Non modiable Non modiable Non modiable Non modiable Non modiable Modiable Modiable Modiable
Un objet est modiable si on peut modier le contenu rfrenc. Le contenu dune liste tant une liste de rfrences, et une liste tant modiable, on peut changer ces rfrences, ce qui autorise crire : >>> l=[1,2,3] >>> id(l[0]) 9357408 >>> l[0]=42 >>> id(l[0]) # lobjet rfrenc nest plus le mme 9358720 >>> l [42, 2, 3] Un tuple ntant pas modiable, les mmes oprations ne sont pas possible : >>> t=(1,2,3) >>> id(t[0]) 9357408 >>> t[0]=42 # on ne peut pas rfrencer un autre objet Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: tuple object does not support item assignment En revanche, si un des lments dun tuple est une liste, et quon modie cette liste, alors a fonctionne... : >>> t=([6,7,8],2,3) >>> id(t[0]) 30698096 >>> t[0].append(1000) >>> id(t[0]) # lobjet rfrenc est toujours le mme... 30698096 >>> t ([6, 7, 8, 1000], 2, 3) Une chane de caractres ntant pas modiable, on ne peut donc pas modier un de ses caractres : >>> s=Pithon >>> s[1]=y Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: str object does not support item assignment On sen sort en faisant : >>> s=Pithon >>> s=s[0:1]+y+s[2:] >>> s Python ou bien : 49
>>> s=Pithon >>> ls=list(s) >>> ls [P, i, t, h, o, n] >>> ls[1]=y >>> s=.join(ls) >>> s Python
20
Clavier et cran
Vos programme peuvent permettre la saisie au clavier avec la fonction input : >>> a=input(Entrez votre nom) >>> print(a,type(a)) La fonction input renvoie une chane de caractres, mais on peut la convertir au passage : >>> a=int(input(Entrez votre age)) >>> print(a,type(a)) Lachage de chanes formates peut se faire de plusieurs faons direntes : La plus simple et la moins souple : >>> a=43.34456 >>> b=12 >>> print("Un entier",b,"et un float",a) Un entier 12 et un float 43.34456 La nouvelle mthode (format) : >>> a=43.34456 >>> b=12 >>> print("Un entier {} et un float {}".format(b,a)) Un entier 12 et un float 43.34456 >>> print("Un entier {0} et un float {1}".format(b,a)) Un entier 12 et un float 43.34456 >>> print("Un entier {1} et un float {0}".format(a,b)) Un entier 12 et un float 43.34456 >>> print("Un entier {0:03d} et un float {1:.2f}".format(b,a)) Un entier 012 et un float 43.34
50

Python1a PDF

Transféré par

Droits d'auteur :

Formats disponibles

Python1a PDF

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Python1a PDF

Transféré par

Droits d'auteur :

Formats disponibles

Introduction lalgorithmique et la programmation avec Python

Laurent Signac https://deptinfo-ensip.univ-poitiers.fr

Algorithmique et Programmation avec Python

Table des matires

Algorithmique et Programmation avec Python

Ordinateur, codage numrique

Modle de Von Neumann

Unit arithmtique et logique

Codage numrique de linformation

Algorithmique et Programmation avec Python

Constructions typiques des langages

Figure II.1 Les lments, livre VII, dition de 1632

Algorithmique et Programmation avec Python

Notes de cours, Ensip 1A

Poser les problmes

Types, aectations, expressions

Notes de cours, Ensip 1A

Fonctions dans dautres langages

Notes de cours, Ensip 1A

# Ceci est une fonction def foncttc(val,taux) : ttc=val*(1+taux/100) return ttc

# Ceci est une procdure def procttc(val,taux) : ttc=val*(1+taux/100) print(ttc)

Prototype dune fonction

Tir de Math-Info de Raymond Sroul, Interditions

Notes de cours, Ensip 1A

instructions avant le test

instructions du bloc alors

instructions apr` es le test

On cherche traduire un choix, une alternative.

instructions du bloc sinon instructions apr` es le test

instructions du bloc alors

Algorithmique et Programmation avec Python

instructions avant la boucle

Est-ce que la condition de la boucle est vraie ?

corps de la boucle instructions apr` es la boucle

Boucles Rpter Pour et itrateurs

Algorithmique et Programmation avec Python

Aectation, mode de passage des paramtres

Notes de cours, Ensip 1A

Notes de cours, Ensip 1A

Notes de cours, Ensip 1A

def fact(n) : if n>0 : r=n*fact(n-1) else : r=1 return r

def fibo(n) : if n<2 : return n return fibo(n-1)+fibo(n-2)

Rsoudre des problmes : mthode de travail

Dveloppement selon John Zelle

Rechercher un lment dans une liste trie

Algorithmique et Programmation avec Python

La notation permet en quelques sorte dencadrer le comportement asymptotique dune fonction.

Le livre et la tortue Gustave Dor

Algorithmique et Programmation avec Python

criture des primitives

Notes de cours, Ensip 1A

(a) Dbut de la courbe de Koch

(b) tape 2 de la construction...

(c) tape 3 de la construction...

(d) Courbe de Koch

Algorithmique et Programmation avec Python

Figure II.6 Trac du triangle de Sierpinski

Figure II.8 Dragon gauche de profondeur 15

Algorithmique et Programmation avec Python