Introduction à l’algorithmique et à la programmation avec Python

Introduction à l’algorithmique et à la programmation avec Python

Laurent Signac

16 décembre 2012

Table des matières

I    Ordinateur, codage numérique 5

1      Ordinateur? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   5

2      Codage numérique de l’information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    5

3      Langages de programmation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .         10

4      Constructions typiques des langages     . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  11

II   Algorithmique et programmation            13

5      À quoi sert un algorithme? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .            13

6      Algorithme d’Euclide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

7      Poser les problèmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .             15

8      Types, affectations, expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .       15

9      Fonctions et procédures         . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   17

10   Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    21

11   Boucles        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                22

12   Affectation, mode de passage des paramètres   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .             24

13   Notation pointée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

14   Récursivité  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    29

15   Résoudre des problèmes : méthode de travail    . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .             30

16   Récursivité et Logo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .               36

IIICompléments sur Python                                                                                                                                                                  41

17   Types simples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  41

18   Types collections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

19   Types modifiables ou non . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .            49

20   Clavier et écran . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

3

Notations

Dans ce support de cours, les programmes sont généralement typographiés en police machine à écrire et encadrés, alors que les algorithmes n’ont pas de cadre et utilisent une police sans empattements.

Sauf si une indication contraire est donnée, le langage utilisé est Python. On différencie les «sessions shell» par la présence du prompt >>>. En l’absence de prompt, il s’agit généralement d’un programme à entrer dans un éditeur de texte et à exécuter ensuite (l’interface Idle convient très bien pour faire tout ceci).

Introduction

L’informatique, telle que nous la connaissons aujourd’hui résulte à la fois des progrès théoriques, amorcés dans les années 30 par les travaux de Turing, et des progrès technologiques, liés à l’électronique, avec en particulier l’invention du transistor dans les années 40.

Depuis, ces deux facettes, science théorique et défis technologiques progressent de conserve.

L’objet de ce cours est de présenter l’ère numérique sous l’angle du codage des informations, puis celle des ordinateurs sous celui des algorithmes et de la programmation.

Ressources

La dernière version de ce fichier est disponible ici :

pdf

Les ressources Web associées à ce cours sont :

–   Sur Updago : Algorithmique et Programmation Python

–  

Les introduction à Python sont nombreuses sur le Web, et certaines sont de très bonne qualité : – Le cours de Bob Cordeau : – Le cours de Pierre Puiseux :

Les livres sur Python 3 sont encore assez peu nombreux. À plus forte raison en Français. Voici ceux qui ont été utilisés lors de l’écriture de ce cours :

–   Le Goff, Vincent, Apprenez à Programmer en Python, Le livre du Zéro

–   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, 2^e ed.

Les parties du cours qui ne concernent pas précisément Python sont issues de nombreux ouvrages impossibles à tous mentionner ici et de quelques années de pratique.

Chapitre I

Ordinateur, codage numérique

             1        Ordinateur?

Les machines électroniques nous entourent désormais : 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 affaire à un ordinateur ?

Comme nous allons le voir, les ordinateurs actuels sont à peu près calqués sur un modèle datant des années 50, le modèle de Von Neumann. Si nous devions retenir deux caractéristiques des ordinateurs, ce serait que :

–   un ordinateur doit être programmable

–   son programme doit être enregistré dans sa mémoire.

Par voie de conséquence, une simple calculatrice de poche n’est pas vraiment un ordinateur, alors que les modèles programmables plus perfectionnés en sont. De même que les tablettes et les smartphones

             1.1        Modèle de Von Neumann

Le modèle de Von Neumann distingue :

–   l’unité arithmétique et logique, qui réalise les calculs

–   l’unité de contrôle, qui veille au déroulement du programme

–   la mémoire, qui contient les données, et le programme en cours d’exécution

             1.2        Ordinateurs domestiques

Dans nos micro-ordinateurs, les différents composants sont : la carte mère, le processeur, la mémoire, la carte graphique, les disques

Ces composants électroniques communiquent entre eux par l’intermédiaire de bus et les données qui transitent sont représentées sous forme binaire.

Dans un ordinateur, absolument tout (données et programmes, en mémoire, sur les disques durs ou sur cd ) est stocké sous forme binaire.

Dans le suite, nous verrons comment utiliser le système binaire, et comment des objets complexes, comme des images ou de la musique, sont codées en binaire.

             2            Codage numérique de l’information

L’information est la matière première de l’informatique (le mot vient d’ailleurs de là ). Les algorithmes, qui sont constitués d’informations, stockent, manipulent et transforment d’autres informations, à l’aide de machines.

5

Tout, en informatique, est représenté comme une séquence de 0 et de 1 : les algorithmes, ou plutôt les programmes, le contenu d’un livre, une photo, une vidéo

Pourquoi le binaire ?

Unités

2.1        Changements de base

L’écriture d’un nombre en base b est formée à partir de b symboles, appelés chiffres. Les 10 chiffres de la base 10 sont par exemple : 0,1,2,3,4,5,6,7,8 et 9.

Si l’écriture d’un nombre en base b est : c_nc_n?1c₁c₀ (les c_i sont les chiffres), sa valeur sera :

v(c_n) × bⁿ + v(c_n?1) × b^n?1 + + v(c₁) × b¹ + v(c₀) × b⁰

où v(c_i) est la valeur associée au chiffre (symbole) c_i. La valeur du symbole 9 en base 10 est par exemple neuf. Généralement, pour une base b inférieure à 10, on reprend les même chiffres qu’en base 10, avec les mêmes valeurs (mais on n’utilise que les b premiers chiffres). Pour une base b supérieure à 10, on ajoute aux chiffres ordinaires d’autres symboles, comme des lettres. La base 16 utilise par exemple les 16 chiffres suivantes : 0,1,2, ,9,A,B,C,D,E,F. Voici quelques exemple, la base est indiquée en indice à la fin du nombre. En l’absence de cet indication, c’est la base 10 qui est utilisée.

1011010|₂ = 1 × 2⁶ + 0 × 2⁵ + 1 × 2⁴ + 1 × 2³ + 0 × 2² + 1 × 2¹ + 0 × 2⁰ = 90

5A|₁₆ = 5 × 16¹ + 10 × 16⁰ = 90

Pour passer de la base 10 à la base 2, on peut procéder par divisions successives (par 2). Voici comment trouver l’écriture binaire de 90 :

La séquence des restes successifs, lue du dernier au premier donne : 1011010 qui est l’écriture en base 2 de 90. 0n peut procéder de même en base 16 (en faisant des divisions par 16). Les restes sont alors entre 0 et 15, ce qui correspond bien aux valeurs des chiffres de la base 16.

On peut coder de la même manière les nombres non-entiers. Chaque chiffre placé après la virgule est associé à une puissance négative de la base :

101,011|₂ = 1 × 2² + 0 × 2¹ + 1 × 2⁰ + 0 × 2^?1 + 1 × 2^?2 + 1 × 2^?3 = 5 + 0,25 + 0,125 = 5,375

Le passage de la base 10 à la base 2, pour la partie fractionnaire, est réalisé par multiplications successives (on reporte la partie fractionnaire de chaque résultat sur la ligne suivante, et les parties entières des résultats obtenus forment

l’écriture en base 2). Voici comment écrire 0,6875 en base 2 :

Nous prenons les parties entières des résultats dans l’ordre où elles sont obtenues : 1011. Donc 0,6875 = 0,1011|₂. Développement binaires infinis

             2.2        Numérique vs analogique

Beaucoup d’objets quotidiens existent à la fois en version numérique et analogique, même si la première tend à remplacer petit à petit la seconde.

Ainsi, nous pouvons opposer les disques compacts audio et les disques vinyles, la photo numérique et la photo argentique, les e-book et les livres traditionnels. Dans tous ces cas, l’objet numérique n’est qu’une succession de chiffres 0 et 1

Codage des couleurs

Les différents moyens de codage reposent sur un certain nombre de conventions. Par exemple, modifier l’ordre des couleurs primaires dans le codage des couleurs en vert, bleu, rouge à la place de rouge, vert, bleu modifie bien entendu les couleurs associées aux nombres. Respecter ces conventions, c’est adopter un standard, et cette adoption facilitera grandement les échanges de données entre les personnes ou les programmes. En particulier, si le standard est publié, on dit qu’il est ouvert, par opposition à un standard fermé, qui restreint, de manière légale ou en ne publiant pas les spécifications du standard, l’écriture d’applications compatibles qui pourraient utiliser les mêmes fichiers de données, par exemple.

Les standards de représentation et de codage des informations sont extrêmement nombreux. Pour chaque type d’objet numérique, il existe de nombreux standards : pour le texte (latin, utf, ascii ), pour les documents mis en page (Open Document Format, Office Open xml ), les images (jpeg, png ), l’audio (mp3, ogg, flac ), la vidéo (mpegv2, Vorbis, h-264 ).

2.3        Codage du texte

Les caractères sont généralement codés par des nombres, par une simple table de correspondance. Le standard le plus ancien est l’ascii, qui contient les caractères latins non accentués, les chiffres, des symboles de ponctuation, codés sur 7 bits (au total, la figure I.1 contient donc 128 symboles, caractères non imprimables compris)

Figure I.1 – Table ascii (numérotée de 0 à 7F, en héxa) tirée de Wikipédia

Le code ascii a rapidement été insuffisant, faute de caractères accentués, grecs, cyrilliques, hébreux, chinois

Deux autres types de codage ont donc fait leur apparition :

–   Les extensions rajoutent des caractères à la suite de la table (chaque alphabet possède alors son extension) : c’est le cas du latin-1 (iso-8859-1). Il y a des extensions pour le chinois, l’hébreu Il faut donc indiquer quelle est l’extension utilisée pour pouvoir lire correctement le fichier.

–   Unicode est une norme qui recense tous les caractères existant dans une table (il y en a plus de 100000 actuellement). Les codes sont ensuite représentés dans un codage particulier comme utf-8, ou utf-16. C’est ce type de codage qu’il convient d’utiliser maintenant.

2.4      Nombres

Nombres négatifs

Les nombres négatifs sont représentés en binaire en utilisant la méthode du complément à deux, qui permet de réaliser simplement des opérations arithmétiques directement sur le codage.

Pour représenter un nombre avec la méthode du complément à 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 compléments à 2 sur 8 bits.

Coder les nombres en complément à 2 sur 8 bits revient à partager les 256 codes possibles en deux parties. Ceux dont le bit de poids fort est 0 représenteront les nombres positifs de 0 à 127 (codage immédiat en base 2 avec les 7 bits restants). Ceux dont le bit de poids fort est 1 représenteront les nombres négatifs de -128 à -1.

Dans le cas d’un nombre négatif n, on obtient le complément à 2 de n en calculant la représentation binaire du nombre 256 ? |n|. Cette représentation est obtenue rapidement en écrivant sur 8 bits la représentation binaire de la valeur absolue de n, puis en inversant les 0 et les 1, puis en ajoutant 1 :

Exemple de codage en complément à deux

Virgule flottante

Nous avons vu qu’il était possible de représenter les nombres à virgule en binaire. Cependant, l’utilisation très fréquente des calculs à l’aide de nombres non entiers, et le soucis de coder ces nombres en un minimum de bits a donné naissance au codage en virgule flottante. Ce codage (norme ieee-754) existe essentiellement en deux versions, simple et double précision, utilisant des codages sur 32 et 64 bits. Le codage en simple précision permet de représenter de manière approchée les nombres entre ?3.4 × 10³⁸ et 3.4 × 10³⁸, tout en atteignant des valeurs aussi petites (en valeur absolue) que 1.4 × 10^?45.

Nous ne détaillerons pas ici ce codage, assez technique, mais il est important de retenir :

–   que c’est le codage le plus utilisé pour les nombres non entiers;

–   qu’il représente les nombres de manière approchée, et qu’en virgule flottante, les calculs ne sont (pratiquement) jamais exacts.

Flops

             2.5     Sons

Le codage d’un son, ou d’une courbe en général, est réalisé en échantillonnant dans le temps le signal continu. Chaque échantillon est représenté par un nombre, avec une certaine précision (souvent exprimée en bits). Ce codage se nomme pcm (Pulse Code Modulation).

Selon la nature du signal ainsi numérisé, il est possible d’utiliser des codages plus économes en mémoires (compression), comme Flac (compression sans perte) ou mp3 (compression avec pertes).

Compact-disc Audio

             2.6      Images

Un image numérique (telle que celle stockée dans les appareils photos) est une matrice de pixels. Chaque pixel est un point indivisible en couleur de l’image. Les éléments importants en matière de qualité de l’image sont donc : la taille de la matrice, et le nombre de bits utilisés pour coder la couleur de chacun des pixels.

Typiquement, chaque pixel est codé sur 24 bits (8 bits par composante) et un appareil photo annonçant 12 millions de pixels réalise des photographies de 4000 sur 3000 pixels. Résolution

Formats d’image

             2.7        Codages symboliques

Avant de terminer cette section sur le codage, signalons l’existence des codages symboliques, que l’on peut rencontrer pour tout type d’objet (images, musique). Grossièrement, on peut dire que le codage symbolique est un codage plus intelligent de l’objet. Il se situe à un niveau supérieur d’abstraction et s’intéresse au contenu et au sens de l’objet plutôt qu’à son rendu.

Cette différence est présente aussi en dehors du monde numérique : un enregistrement musical (du son donc ) n’est pas la même chose qu’un ensemble de partitions musicales, même si l’enregistrement correspond à des musiciens jouant précisément ces partitions. La partition est alors le codage symbolique.

Cette même dualité existe dans le monde numérique. Le codage d’images que nous avons déjà évoqué est dit codage matriciel ou bitmap. Mais nous pouvons aussi décrire une image (certains types tout au moins) en détaillant les objets qui sont présents sur cette image (des cercles, des lignes etc ). Une description des objets géométriques composant un dessin est un codage vectoriel de l’image. Cette description a pour principales caractéristiques d’être plus économe en mémoire (dire que l’image est un disque blanc est plus rapide que détailler les 12 millions de pixels d’une photo d’un disque blanc ), et de ne pas être sensible aux problèmes de pixelisation (de près ou de loin, un disque blanc est toujours aussi parfait, ce qui n’est 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 même, en ce qui concerne le son, le codage symbolique le plus utilisé est midi, qui détaille un morceau en pistes, chaque piste correspondant à un instrument et contenant les notes jouées, avec leur hauteur et leur durée. C’est plus ou moins l’équivalent d’une partition. On peut d’ailleurs créer de manière automatique une partition à partir d’un fichier midi, alors qu’il est peu probable qu’on puisse y parvenir à partir de l’enregistrement d’une symphonie. Le passage du symbolique vers l’échantillonné est généralement facile. En revanche, l’inverse est difficile, et parfois impossible (tous les sons enregistrés ne peuvent pas être retranscrits par une partition, et lorsque c’est possible, la méthode n’est pas triviale).

3           Langages de programmation

Un langage de programmation permet d’écrire un programme. Un programme, lorsqu’il est sous la forme de code source, est un texte qui exprime un algorithme (nous y reviendrons), en vue de permettre l’exécution de ce dernier sur une machine.

Les langages utilisés pour programmer sont situés quelque part entre les séquences de 0 et 1 chères à la machine et le langage naturel cher à l’humain.

Pourquoi choisir un langage ?

Il existe des centaines de langages différents, qui peuvent être plus ou moins spécialisés pour certaines tâches, qui permettent d’utiliser différents paradigmes de programmation (impératif, objet, par contraintes, logique ). Les langages peuvent être plus ou moins verbeux, plus ou moins expressifs. Certains langages sont très répandus, ou au contraire ne sont utilisés que par une poignée de personnes. Les langages peuvent être jeunes ou vieillissant, et, lorsque le côté affectif s’en mêle, ils peuvent être agréables à utiliser ou au contraire agaçants

La tâche qui consiste à choisir un langage de programmation pour illustrer un cours d’algorithmique et d’informatique, à destination d’un public hétérogène est donc difficile. Dans la suite, c’est le langage Python qui sera utilisé. Il est : généraliste, assez répandu (la pente étant dans le bon sens ), multi-paradigmes, assez jeune, expressif et agréable à utiliser. Il n’est cependant pas le seul à posséder toutes ces qualités.

D’un point de vue plus technique, Python est aussi un langage interprété (par opposition à un langage compilé). En partie pour cette raison, il est d’apprentissage rapide, il est portable, mais il est en revanche lent à l’exécution. Enfin, il existe plusieurs interpréteurs Python, et l’interpréteur standard, nommé CPython, est libre, gratuit et multi plates-formes.

Voici un exemple de programme écrit en Python :

La page 14 permet de comparer un même programme écrit en plusieurs langages.

             4            Constructions typiques des langages

Cette section a pour objectifs de familiariser le lecteur avec la lecture de programmes, donnés ici en Python. Les constructions les plus utilisées sont les variables et les calculs. Les variables servent à stocker des valeurs (ici fare et celc), et les calculs sont réalisés très simplement en utilisant par exemple les opérateurs arithmétiques habituels.

Égalité 6= affectation

La plupart des programmes n’ont pas un unique fil d’exécution possible. Selon les valeurs données en entrées, ou selon le résultat de certains calculs, une chose plutôt qu’une autre doit être faite (par exemple, pour un programme de recherche de racines d’un polynôme de degré 2, après que l’utilisateur a entré les coefficients, la portion de programme à exécuter ne sera pas la même selon que le discriminant est positif, négatif ou nul).

Dans l’exemple suivant, selon que la température est en dessous de 0?C ou non, un message différent sera affiché :

Lors de la conception d’un programme un peu long, il est indispensable de le structurer en parties indépendantes. Il est très utile de commencer à prendre cette habitude même avec des programmes courts. Dans l’exemple qui suit, nous avons écrit une fonction, nommée conversion, qui convertit une température, donnée en degrés Fahrenheit en une température exprimée en degrés Celcius. La fonction est ensuite utilisée dans le programme principal :

Le propre de l’ordinateur est de ne pas se plaindre si on lui demande de recommencer de nombreuses fois les mêmes opérations (avec quelques petites variantes). La structure de boucle permet d’exprimer les répétitions et nous l’utilisons ci-dessous pour afficher une table de conversion de degrés Fahrenheit vers degrés Celcius (en vue de l’imprimer par exemple).

Chapitre II

Algorithmique et programmation

5            À quoi sert un algorithme?

L’algorithmique est bien plus ancienne que l’informatique, que l’ordinateur, et que le langage Python, utilisé dans ce support de cours.

Les exemples les plus anciens et célèbres sont :

–   les calculs d’impôts Babyloniens (il y a 4000 ans)

–   le calcul du plus grand diviseur commun (Euclide, vers ?350)

–   les première méthodes de résolution systématique d’équations (Al Khawarizmi, ix^e siècle) Les algorithmes étaient donc d’abord utilisés «à la main».

Aujourd’hui on entend généralement par algorithmique la réflexion préliminaire à l’écriture d’un programme d’ordinateur, c’est à dire la recherche d’une méthode systématique et non ambiguë pour résoudre un problème. C’est la partie conceptuelle de la programmation, l’abstractiond’un programme d’ordinateur.

L’algorithmique est parfois considérée comme une branche des mathématiques, parfois comme une branche de l’informatique. Les notions d’algorithme, puis d’ordinateur ont été formalisées dans les années 30 et 40 par : Kurt Gödel, Alan Turing, John von Neumann

Avoir des notions en algorithmique permet de développer soi-même des programmes, et/ou d’avoir une discussion constructive avec une équipe de développeurs. Les compétences en algorithmique font aussi partie du bagage minimum d’un scientifique, qu’il soit technicien, chercheur, ingénieur ou simplement curieux.

6          Algorithme d’Euclide

Commençons par un exemple historique célèbre : l’algorithme d’Euclide.

Algorithme d’Euclide

Exercice

133 et 49                                                                                                                     Figure II.1 – Les éléments, livre VII, édition de 1632

Voici les différentes étapes vers la rédaction propre d’un algorithme. Nous partons de l’idée de départ et la raffinons par étapes

13

Étape 1 : Écrire proprement l’idée                                                    Étape 3 : Écrire un algorithme formel

Prendre les deux nombres et, tant qu’ils ne sont pas égaux, retirer le plus petit au plus grand.

fonction pgdc(a,b : entiers)

repeter tant que a6=b

Étape 2 : Décrire précisément les étapessi a>b

a=a?b

a,b : deux nombressinon

Répéter tant que a et b sont différents :b=b?a si le plus grand est a :

les deux nombres deviennent a?b et b retourner a sinon (b est donc le plus grand) :

les deux nombres deviennent a et b?a

le pgcd est a                                                                                          Étape 4 : Écrire un programme

Finalement, c’est quoi la programmation ?

Voici l’algorithme du pgdc présenté dans plusieurs langages.

7         Poser les problèmes

Résoudre un problème nécessite :

– que l’énoncé soit précis; – qu’on le comprenne parfaitement; –

Autant que possible, il faut prendre l’habitude de préciser, de préférence par écrit, quelles sont les entrées et les sorties du problème (ou des sous-problèmes, comme nous le verrons plus tard). Voici quelques exemples :

8           Types, affectations, expressions

8.1        Types simples

Le type d’une donnée caractérise sa nature (est-ce que c’est un entier, un nombre à virgule une couleur, une liste ?) et par voie de conséquence les opérations qu’il est possible de lui appliquer (on peut ajouter des nombres, mais peut être pas des couleurs).

Les types dans un langage informatique dépendent fortement du codage utilisé pour représenter les données. En algorithmique, on peut parfois se permettre d’utiliser des types «mathématiques» qui n’ont pas d’implémentation réelle en machine.

Cas des entiers et des réels

Les entiers, par exemple, ont une taille limitée en C (quelques octets). Cette taille est limitée à la mémoire disponible en Python (l’entier maximum est considérablement grand). L’ensemble des entiers «mathématiques» n’est en revanche pas borné.

Voici quelques exemples de types simples :

8.2 Variables

Une variable sert d’espace de stockage pour les résultats intermédiaires d’un calcul. Elle possède un certain nombre de caractéristiques :

identificateur (nom) Il doit être bien choisi, surtout dans un programme long. Un identificateur ne comporte aucun espace ou caractère spécial et ne peut pas être un mot clé. Chaque langage dispose de règles (différentes) très précises décrivant la syntaxe des identificateurs

type Dans certains langages, le type d’une variable peut changer en cours d’exécution du programme (Python, Ruby). Dans d’autres, le type est fixé une fois pour toutes (Java, C).

valeur Il y a nécessairement quelque chose dans une variable.

portée On ne peut utiliser le nom d’une variable que dans la fonction ou la procédure (en réalité le bloc) qui la contient. La durée de vie de la variable correspond à la durée d’exécution de la fonction ou de la procédure (du bloc). Sans ce principe, les programmes longs deviendraient incompréhensibles et difficiles à déverminer.

Attention à l’affectation

Voici un exemple de session shell qui calcule un prix ttc :

Exercice

L’affectation en Python

8.3       Expressions

Nous utiliserons une définition «intuitive» des expressions, en retenant que c’est une portion de code, plus ou moins longue, qui peut être évaluée. La valeur obtenue peut par exemple être affectée à 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 entières

8.4      Listes

Un tableau, tel que ceux utilisés en C par exemple, permet de stocker selon une ou plusieurs dimensions des données homogènes (on parle de tableau d’entiers 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 hétérogènes (voire d’autres listes). Voici un exemple d’utilisation de listes :

8.5      Tuples

Les tuplesde Python sont des listes non modifiables.

Il n’est pas strictement nécessaire d’utiliser des tuples. Mais certaines méthodes ou fonctions Python en renvoient et il faut donc connaître leur existence.

9          Fonctions et procédures

9.1      Fonctions

Les fonctions et procédures sont la pierre angulaire de la programmation procédurale.

Il y aura deux points fondamentaux à retenir dès la fin de lecture de cette sous-section :

– comprendre pourquoi on écrit des fonctions; – s’obliger à le faire dès les premiers programmes. Commençons par un exemple en Python :

Une fois la fonction calculttc lue par le shell, il est possible de l’utiliser ainsi :

Notons qu’il convient de bien séparer la définition et l’utilisation de la fonction :

définition : on indique comment «marche» la fonction et comment on s’en sert (déclaration). La fonction n’est pas utilisée (exécutée), mais juste «lue» pour être connue de l’interpréteur.

utilisation : on exécute de manière effective le code de la fonction pour des valeurs d’entrées fixées (1000 et 19,6 dans l’exemple).

Voici quelques occasions dans lesquelles vous devez écrire des fonctions (ou des procédures) :

1.    Le bloc de programme que vous écrivez ne tient pas entier à la vue sur votre écran.

2.    Vous utilisez plus d’une 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 à l’appeler plusieurs fois.

3.    Vous ne savez pas exactement si la méthode de résolution employée pour telle tâche est la meilleure. Mettez la dans une fonction et utilisez cette fonction. Si vous trouvez une meilleure façon de procéder, il suffira de modifier la fonction sans toucher au reste.

4.    Le problème que vous traitez est difficile : découpez le en fonctions que vous écrirez et testerez séparément les unes des autres (le bénéfice que vous aurez à pouvoir tester très facilement des portions de programme est énorme). Dans chaque fonction indépendante, vous pourrez choisir des noms de variables appropriés, qui rendront votre code plus simple à comprendre.

9.2 Fonctions dans d’autres langages

La façon d’écrire les fonctions, méthodes et procédures varie selon les langages. Une manière plus algorithmique et francisée d’écrire pourrait être :

fonction calculttc (val ,taux : réels ) : réel ttc : réel ttc?val?(1+taux/100)

retourner ttc

Voici d’autres exemples, pour comparaison :

9.3       Procédures

Il ne faut pas confondre procédure et fonction, même si leur définition, en Python par exemple, est similaire :

–   Une fonction calcule. Elle vaut quelque chose (exemples : pgdc et calculttc)

–   Une procédure n’a pas de valeur, mais elle fait/modifie quelque chose (exemple : afficher à l’écran, modifier un objet). On dit qu’elle a un effet de bord (elle modifie quelque chose qui est en dehors de la procédure).

Même si la différence fonction/procédure n’est pas syntaxique (au niveau de la ligne de prototype) en Python, elle est très importante :

On pourrait penser que la fonction foncttc et la procédure procttc sont équivalentes. Ce serait une erreur. La fonction est plus générale. On ne peut pas écrire par exemple :

En revanche, la même ligne, en utilisant foncttc fournirait le bon résultat. Assurez-vous d’avoir bien compris pourquoi la ligne qui précède marche avec une fonction et pas avec une procédure. C’est vraiment très important.

Effets de bords

9.4         Prototype d’une fonction

Le prototype est la première ligne de la fonction :

fonction calculttc (val ,taux :             réels ) : réel

Il peut indiquer 4 choses :

1.    le nom de la fonction ou de la procédure : foncttc

2.    les paramètres (les entrées du problème) : (val,taux : réels)

3.    les éventuels types de sortie (dans le cas d’une fonction) : réel

4.    si l’on a affaire à une fonction ou à une procédure (on le voit si le type des données de sortie est mentionné par exemple, ou parce que le mot clé est différent (fonc ou fonction pour une fonction et proc ou procédure sinon).

Ce prototype est très abrégé en Python :

Le prototype Python n’indique pas les types des entrées, et nous ne pouvons pas savoir si nous avons affaire à une fonction ou à une procédure.

9.5        Variables locales

Les variables locales sont les variables qui n’existent que dans le corps de la fonction ou procédure (dans une certaine mesure, les paramètres peuvent être assimilés aux variables locales). Voici un exemple de fonction avec un paramètre u et une variable locale v :

Pour utiliser la fonction qui précède, il est inutile de connaître les noms de variable u et v. Ce qui est important, c’est que la fonction prend en paramètre un nombre et renvoie un nombre (le carré du premier) :

La notion de portée des variables (variables locales, globales) est souvent mal comprise au début : elle peut être perçue comme une difficulté, voire un défaut, alors qu’elle simplifie grandement le travail du programmeur.

Local, englobant, global et built-in

9.6 Conseils avisés

Tiré de Math-Info de Raymond Séroul, InterÉditions

On ne mâche pas un chewing-gum en montant un escalier :

Ce proverbe – tiré d’une campagne électorale américaine – exprime une idée de bon sens : on ne fait bien qu’une seule chose à la fois. C’est pour cela qu’on découpe un programme en procédures et en modules indépendants.

Nommez ce que vous ne connaissez pas encore :

Ce proverbe s’applique chaque fois que vous rencontrez un sous-problème à l’intérieur d’un problème. Refusez de résoudre le sous-problème, laissez-le de côté 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 problème) en cours. Pour le sous-problème, voyez le proverbe suivant.

Demain, ce sera mieux; après-demain, ce sera encore mieux :

[ ] vous constatez un blocage provoqué par l’apparition d’un nouveau problème à l’intérieur du problème que vous essayez de résoudre : appliquez le proverbe précédent [ ] apprenez à distinguer l’essentiel de l’accessoire; ne vous noyez pas prématurément dans les détails [ ] Vous l’avez certainement pratiquée en mathématique : «Je vais d’abord prouver mon théorème en admettant provisoirement les lemmes 1, 2 et 3». [ ]

À retenir sur les fonctions

10        Conditions

Nous souhaitons demander un nombre à l’utilisateur et afficher un message particulier si ce nombre est un multiple de 13 :

Exercice

On cherche à traduire un choix, une alternative.

Pour chaque valeur de u₀ choisie, on obtient une nouvelle séquence de nombres. Écrivons une fonction qui calcule u_n+1 en fonction de u_n.

fonction collatz (u : entier) : entier

res : entier si u est pair res ?u/2 sinon

res ?3?u+1

retourner res

Exercice

Opérateurs booléens

11 Boucles

11.1 Boucles Tant Que

Nous souhaitons faire un programme de jeu qui propose à l’utilisateur 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 s’arrête lorsque le nombre est découvert.

Exercice

Voici un autre exemple de boucle : la suite de collatz, que nous avons récemment rencontré a la propriété, quel que soit son nombre de départ, de toujours terminer sur le cycle 1, 2, 4. Ce fait a été vérifié expérimentalement jusqu’à de très grandes valeurs, mais a pour l’instant le statut de conjecture car la preuve semble échapper aux mathématiques actuelles.

Voici une fonction qui renvoie une liste contenant la suite issue d’un nombre n, jusqu’à ce que la valeur 1 soit atteinte. Cette liste s’appelle le vol n :

Exercice

Identifiez chaque partie du programme qui précède avec les blocs correspondant de l’organigramme. Profitez de

11.2           Boucles Répéter Pour et itérateurs

Beaucoup de langage offrent un autre type de boucle, permettant de gérer un compteur. Voici un exemple qui affiche des tables de multiplication :

Répéter pour i de 1 à 10 :

Répéter pour j de 1 à 10 :

écrire (i ,’ x’, j ,’=’, i?j)

Python n’est pas en reste pour ce type de boucle, même si la construction offerte est plus générale que la simple boucle avec compteur.

La traduction de l’algorithme qui précède en Python donnerait :

La boucle for de Python permet en fait d’itérer sur n’importe quel objet itérable. Or l’objet range(a,b) est itérable et «contient» les entiers de a à b-1 inclus. C’est pourquoi dans l’exemple qui précède i prend successivement toutes les valeurs de 1 à 10.

Avec la boucle for de Python, il est possible de traverser toutes sortes d’objets :

1.    Dans la première boucle, nombre prendra successivement toutes les valeurs de la liste.

2.    Une chaîne est itérable. Dans la seconde boucle, lettre vaudra successivement chaque lettre de la chaîne de caractères

3.    La fonction enumerate sur un itérable renvoie un nouvel itérable dont les éléments sont des tuples à 2 éléments : le premier est un numéro d’ordre et le second l’élémént dans l’itérable de départ. Par exemple enumerate(’Hello’) correspond à [(0, ’H’), (1, ’e’), (2, ’l’), (3, ’l’), (4, ’o’)]. Cette boucle aurait pu être écrite :

La première écriture dépaquette le tuple t en i et l à la volée.

4.    la méthode split renvoie une liste contenant chaque mot de la chaîne. Dans la quatrième boucle, mot vaudra donc successivement ’Hello’ puis ’World’

Inspecter les objets itérables            En première lecture, vous pouvez omettre ce paragraphe. Depuis Python 3, il n’est pas toujours immédiat d’inspecter les valeurs d’un objet itérable :

Pour connaître les valeurs de l, on peut le transformer en liste :

Mais attention, l’objet l est générateur qui ne peut être traversé qu’une fois (et le transformer en liste implique qu’on le traverse) :

Pour à nouveau accéder aux valeurs, il suffit de créer un nouveau générateur :

12    Affectation, mode de passage des paramètres

Par valeur ou par adresse

Intéressons-nous au problème suivant : Si on envoie une variable en paramètre à une fonction ou une procédure, et qu’on la modifie dans la fonction, est-elle réellement modifiée après l’appel?

12.1 Premier exemple

Voici un exemple écrit en Python :

La question est de savoir ce que va afficher la ligne print(b). 5 ou 6?

En Python, le passage des paramètres est comparable à une affectation. Le fil d’exécution ressemble donc à ceci :

Sur cet exemple, il est évident que le programme affichera 5 (c’est a qui contient 6, pas b).

Le mécanisme responsable de ce comportement est plus complexe qu’il n’y parait, et est assez spécifique à Python. Tout se passe comme si le paramètre était passé par valeur : une copie du contenu de la variable est recopié de b vers a et c’est la copie qui est modifiée, pas l’original.

Pour comprendre le mécanisme réel, détaillons les deux lignes de code suivantes :

Nous avons déjà mentionné que les variables, en Python, étaient des références vers des objets. Cette nuance est maintenant centrale. La figure suivante illustre la manière dont les lignes précédentes, et tout particulièrement la seconde, sont exécutées:

La ligne c=a+1 est décomposée en :

1.    L’objet à droite du symbole d’affectation est créé, sauf si c’est une référence simple (ici, création de l’objet 6).

2.    La variable à gauche du symbole d’affectation référence maintenant le nouvel objet créé.

Pour les variables numériques, on peut tout ignorer de ce mécanisme, et considérer que les variables sont de simples «tiroirs» pour ranger les nombres. Mais connaître ce mécanisme permet d’expliquer les autres comportements de Python que nous allons détailler dans la suite.

Voyons à présent ce qui se produit lors du passage d’un paramètre :

1   b=5 : on crée l’objet 5, et b est une nouvelle référence vers cet objet

2   a=b : on a une simple référence à droite du symbole =, a devient une nouvelle référence vers l’objet b, qui existait déjà.

3  et 4 a=a+1 : on crée l’objet spécifié à droite du = (6), et a devient une référence vers ce nouvel objet.

On comprend donc pourquoi la valeur indiquée dans b n’a pas changé.

12.2       Second exemple

Voyons maintenant ce qui se produit lorsqu’on passe une liste en paramètre :

Nous posons toujours la même question : que va afficher le programme principal : [1,2,3] ou [1,2,3,42]. Là aussi (ceci est toujours valable), le passage des paramètres est comparable à une affectation. Aussi, la machine exécute :

Cette fois-ci, c’est [1,2,3,42] qui va s’afficher, comme si la procédure ajoute_liste avait pu modifier la liste originale, de manière contradictoire avec ce qui se passait précédemment avec la procédure ajoute et un nombre entier Dans cet exemple, tout se passe comme si la liste était passée par adresse. C’est donc la liste originale qui est modifiée dans la procédure.

Examinons dans un premier temps ce qui se cache derrière la simple ligne :

Lors de l’exécution de cette instruction, les objets 1, 2 et 3 sont créés, suivis d’une liste qui contient les références vers chacun des objets : les élément de la liste ne sont pas les objets mais des références vers ces objets. Cette liste est enfin référencée par lst. On se trouve dans cette situation :

Voyons maintenant ce qui se cache derrière le passage de paramètres de notre second exemple :

Le déroulement des opérations est le suivant :

Voici ce qui se produit :

1   lst=[1,2,3] : la liste lst est créée, et contient des références vers 3 entiers.

2   l=lst : une nouvelle référence à la liste est ajoutée

3  et 4 l.append(42) : l’objet 42 est créé. Puis, la méthode append demande à la liste référencée par l de stocker une référence vers l’objet passé en paramètre.

Dans ce cas, la liste d’origine (celle qui était désignée par lst est bel et bien modifiée. Ceci explique que la liste du programme principal, qui contenait [1,2,3], contient effectivement quatre éléments après l’appel à ajoute_liste.

12.3 Troisième exemple

Voici maintenant un troisième exemple qui va nous permettre de terminer sur le mécanisme de passage des paramètres en Python.

Le passage des paramètres est toujours équivalent à une affectation et tout se passe comme si nous exécutions :

Cette fois-ci le programme affiche [1,2,3]

Ceci peut paraître surprenant après la lecture du second exemple, mais s’explique très simplement si nous reprenons nos schémas d’objets et de références.

Dessinons les objets mis en jeu dans le code :

Voici le déroulement des opérations :

L’exécution semble un peu plus complexe :

1   lst=[1,2,3] : la liste lst est créée, et contient des références vers 3 entiers.

2   l=lst : une nouvelle référence vers la même liste est ajoutée

La ligne suivante : l=l+[42] correspond, comme ça a été le cas jusqu’à présent, à la création de l’objet à droite du signe =. Puis l devient une référence vers ce nouvel objet.

La création de l’objet l+[42] est la création d’une nouvelle liste, concaténation de deux listes (l et [42], de la même manière que 3+5 provoquerait la création d’un nouvel entier, somme de 3 et de 5.

3   création de la liste temporaire [42], afin de l’utiliser comme opérande.

4   création de la troisième liste, concaténation des deux autres. Notez que les objets (1,2, etc ) ne sont pas recopiés, ce sont les références vers ces objets (le contenu d’une liste, ce sont les références vers les objets) qui le sont.

5   La nouvelle liste s’appelle maintenant l. L’ancienne liste lst n’a donc pas été modifiée.

Résumé

13 Notation pointée

Bien que ce support de cours n’ait pas pour but d’enseigner la programmation orientée objets, il est nécessaire d’en comprendre certaines notations afin de bien utiliser Python.

Un objet est une entité composée d’attributs (typiquement des valeurs) et de méthodes (les actions que l’objet peut effectuer). C’est 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 l’objet. On peut par exemple disposer de deux tortues, l’une écrivant en rouge et l’autre en bleu.

Les méthodes sont les actions que peut effectuer la tortue : avancer (forward), tourner à droite (right)

Les objets offrent un plus grand niveau d’abstraction : Si la tortue est en (0,0), orienté selon l’angle 45, et que nous lui ordonnons d’avancer de 10, le calcul de la nouvelle position est fait dans l’objet : Nous donnons des ordres de haut niveau et l’objet gère ses détails interne.

Les ordres donnés à des objets (les appels de méthodes donc) utilisent la notation pointée. Pour faire avancer une tortue t1 de 50 par exemple, nous indiquerons t1.forward(50) qui signifie : appeler la méthode forward de l’objet t1 et lui transmettre le paramètre 50. La fonction help de python, lorsqu’on lui donne un objet en paramètre, indique ainsi l’ensemble des attributs et des méthodes de l’objet en question. Voici un exemple d’utilisation du module turtle :

Rappelons que nous avons déjà utilisé la notation pointée :

Dans l’exemple qui précède, l est une référence vers un objet, instance de la classe list. Cet objet contient des données (les références vers les objets stockés dans la liste, et d’autres choses encore) ainsi que des méthodes, que l’objet peut appliquer.

La programmation orientée objets ne se résume pas à ça bien sûr, mais ce qui précède est l’essentiel à savoir pour utiliser les objets.

14        Récursivité

14.1          Récurrence en mathématiques

Nous allons commencer par l’exemple de la fonction factorielle, qui peut être définie de manière récursive :

n × fact(n ? 1)             si n > 0 ?n > n! = fact(n) =

                                                                                                                                         1      si n = 0

Voici quelques éléments qui sont toujours présents dans une définition récursive :

–   l’objet de taille n est défini à partir d’un objet de taille plus petite (fact(n) est défini à partir de fact(n ? 1)). Ce point n’est pas toujours évident.

–   les petits objets ne sont pas définis de manière récursive (c’est le cas de fact(0) dans notre exemple).

14.2        Algorithme récursif

De la même manière qu’une définition peut être récursive, un algorithme peut être récursif.

fonction fact(n: entier) : entier

si n>0 :

r?n?fact(n?1)

sinon

r?1

retourner r

Comment un algorithme récursif fonctionne-t-il ?

14.3        Quelques exemples

Suite de Fibonacci

La suite de Fibonacci est définie ainsi :

                                                                ? F₀ =         0

?

F₁ =        1

                                                             ? F_n            =           F_n?₁ + F_n?₂ si n > 1

Wikimedia,

Wikimedia,

Les tours de Hanoï

Le jeu consiste à déplacer une tour de plusieurs disques d’un piquet vers un autre, en déplaçant les disques un par un, sans jamais poser un grand disque sur un plus petit.

Extrait de l’Arithmétique amusante de Lucas (? 1895) :

Le mandarin N. Claus (de Siam)nous raconte qu’il a vu, dans ses voyages pour la publication des écrits de l’illustre Fer-Fer-TamTam, dans le grand temple de Bénarès, audessous du dôme qui marque le centre du monde, trois aiguilles de diamant, plantées dans une dalle d’airain, hautes d’une coudée et grosses comme le corps d’une abeille. Sur une de ces aiguilles, Dieu enfila au commencement des siècles, 64 disques d’or pur, le plus large reposant sur l’airain, et les autres, de plus en plus étroits, superposés jusqu’au sommet; c’est la tour sacrée de Brahma. Nuit et jour, les prêtres se succèdent sur les marches de l’autel, occupés à transporter la tour de la première aiguille de diamant sur la troisième, sans s’écarter des règles fixes que nous venons d’indiquer, et qui ont été posées par Brahma. Quand tout sera fini, la tour et les brahmes

tomberont, et ce sera la fin des mondes!                                                                    , larithmetiqueam00lucarich

Il est possible d’écrire un algorithme récursif, très concis, qui indique la liste des déplacements à réaliser 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    Résoudre des problèmes : méthode de travail

Un algorithme présente généralement plusieurs étapes de calcul, qui sont plus ou moins immédiates. Il faut être capable de :

–   hiérarchiser les étapes de calcul

–   découper le problèmes en sous-problèmes plus simples, et indépendants

On réappliquera la méthode à chaque sous-problème, jusqu’à arriver à des problèmes connus ou triviaux. Les avantages de la décomposition en sous-problèmes sont nombreux et d’une grande importance :

–   clarté du code;

–   répartition possible du travail entre plusieurs personnes;

–   possibilité de remplacer facilement un sous-algorithme par un autre plus efficace sans pour autant apporter de retouche à l’ensemble du programme.

15.1 Développement selon John Zelle

Dans son ouvrage Python Programming : an introduction to computer science, John Zelle donne les recommandations suivantes :

Analysez le problème Comprenez le problème à résoudre et sa nature. Essayez d’en apprendre le plus possible sur lui. Vous ne pourrez pas le résoudre avant de le connaître parfaitement.

Spécifiez le programme Décrivez très exactement ce que votre programme va faire. Vous ne devez pas déjà vous soucier de la façon dont il va le faire, mais plutôt décider très exactement ce qu’il va faire. Pour des programmes simples, cela consistera à décrire ce que seront les entrées et les sorties du programme et ce qui les relie.

Concevez le programme Formulez la structure globale du programme. C’est à ce moment que vous traiterez de la façon dont le programme résoudra le problème. Le travail principal est de concevoir le ou les algorithmes qui rempliront les tâches préalablement spécifiées.

Codez Traduisez les algorithmes conçus dans un langage de programmation et entrez les sur un ordinateur. Dans ce livre, nous programmerons nos algorithmes en Python.

Testez/Débuggez le programme Essayez votre programme et voyez s’il fonctionne comme vous le souhaitiez. S’il y a des erreurs (souvent appelées bugs), revenez à l’étape précédente et corrigez les. L’activité qui consiste à débusquer et corriger les erreurs s’appelle le debuggage. Durant cette phase, votre objectif est de trouver des erreurs, et pour cela, vous devez tester tout ce qui vous passe par le tête et qui pourrait planter le programme. Il sera utile de garder à l’esprit la maxime : Nothing is foolproof because fools are too ingenious

Faites de la maintenance Continuez à développer votre programme en répondant aux besoins des utilisateurs. La plupart des programmes ne sont jamais vraiment finis; ils continuent d’évoluer au fil des années d’utilisation.

15.2            Rechercher un élément dans une liste triée

Nous allons nous intéresser au problème suivant : Nous disposons d’une liste d’éléments classés par ordre croissant. Nous voulons vérifier si une valeur donnée est dans la liste ou pas. Ce petit problème peut se rencontrer à l’intérieur de nombreux autres problèmes.

Une première solution

Voici un exemple de liste sur laquelle nous pourrions être amenés à travailler :

La première étape consiste à avoir une idée sur la façon de procéder. Le problème n’étant pas très difficile, nous pouvons envisager une première solution :

Commencer sur la première case. Tant que la case examinée est strictement inférieure au contenu recherché, avancer d’une case. Si on épuise la liste ou qu’on tombe sur une valeur strictement supérieure à la valeur recherchée, c’est qu’elle n’est 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 données, une liste (ou un tableau) telle qu’on en trouve dans Python. La numérotation des cases commencera à 0. L’important pour la suite est que la structure de données doit pouvoir stocker une collection d’objets, ordonnés, et numérotés.

Cette étape de formalisation est difficile à franchir lorsqu’on débute 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 :

De la même idée de départ nous aurions pu décliner un algorithme formel un peu différent et finir sur un autre programme tout aussi correct :

Plusieurs méthodes pour un problème?

Notre méthode (notre algorithme) est-elle efficace?

–   Si la valeur cherchée est plus grande que la dernière case, nous devons tout parcourir

–   Cette méthode revient à rechercher un mot dans le dictionnaire en tournant les pages une par une depuis la première jusqu’à la bonne page

Reprenons la comparaison avec le dictionnaire pour essayer de dégager une autre méthode : Pour rechercher dans un dictionnaire, nous tournons les pages par paquets, quitte à parfois revenir en arrière. Même si la recherche dans un dictionnaire, manuellement, est approximative, l’idée est d’ouvrir le dictionnaire, et d’en déduire si le mot à chercher est avant ou après. Une fois ceci décidé, on ouvre à nouveau le dictionnaire sur la portion sélectionnée et on compare à nouveau avec le mot cherché. À chaque étape, nous réduisons ainsi à peu près de moitié le nombre de pages dans lesquelles il reste à effectuer la recherche.

Algorithme de la méthode dichotomique Pour chercher v entre les cases g et d, regarder le contenu de la case du milieu m (m = (g + d)/2). S’il est plus petit que v, continuer à chercher dans l’intervalle m,d sinon, continuer à chercher dans l’intervalle g,m.

Voici l’algorithme, écrit de manière plus formelle :

Pour rechercher v dans la liste l : g,d ?0,len(l)?1 répéter tant que la «tranche» g,d fait plus d’une case :

m?milieu de g,d

si v>l[m] : g?m+1

sinon : d?m

si l [g]=v : retourner Vrai

sinon retourner Faux

Attention aux difficultés cachées

Voici le programme Python correspondant :

Cette fonction a beau être courte et assez simple, elle peut contenir des erreurs qui ne sont pas évidentes à détecter. Par exemple, si nous avions écrit :

alors le programme n’aurait pas fonctionné. Vous vous en rendrez compte en exécutant à la main ce que fait l’algorithme pour rechercher la valeur 5 dans la liste [3,4].

Exécution manuelle

Comparaison des méthodes

Nous voyons donc que pour résoudre un problème particulier, il y a plusieurs méthodes. Une fois la méthode (l’algorithme) choisie, on peut encore trouver des programmes avec des petites variantes.

Est-il intéressant de trouver plusieurs méthodes ou la première fera-t-elle tout le temps l’affaire?

La figure II.2 (gauche) représente en abscisse le nombre de valeurs de la liste (la valeur max est environ 10 millions) et en ordonnée le temps mis pour rechercher 200 valeurs dans cette liste (valeur max : 0.1 secondes). Cette courbe a été obtenue en utilisant la méthode dichotomique.

La figure II.2 (droite) représente¹⁴ les temps d’exécution de la première méthode, pour les mêmes essais, ainsi que, plaqué sur l’axe des abscisses, à nouveau les résultats de la méthode dichotomique.

Figure II.2 – Comparaison des temps (s) d’exécution de deux algorithmes de recherche

Notion de complexité

Pouvions nous prédire les performances de ces algorithmes sans les programmer, afin d’estimer leurs mérites respectifs et choisir la bonne méthode?

Dans le cas de la recherche naïve, le nombre d’opérations dans la première boucle est proportionnel à la position de la valeur dans le tableau. La fin de l’algorithme s’exécute en temps constant. En moyenne, le nombre d’opérations est donc k₁ⁿ₂ + k₂. On dit que l’algorithme est en ?(n) ou linéaire. Cela signifie que son temps d’exécution varie comme n. Autrement dit, lorsque n est grand, si on multiplie la taille des données par k, le temps d’exécution sera lui aussi multiplié par k.

Dans le cas de la recherche dichotomique, le corps de la boucle s’exécute en temps constant. La boucle s’exécute jusqu’à ce que g et d soient égaux. La distance g ? d est divisée par 2 à chaque tour. On a donc ln₂(n) tours de boucle. Le nombre d’opérations est donc : k₁ ln₂(n) + k₂. On dit que l’algorithme est en ?(log(n)) ou logarithmique. Autrement dit lorsque n est grand, pour doubler le temps d’exécution, il faut élever le nombre de cases au carré! Cet algorithme est donc incroyablement plus rapide que le précédent.

Est-ce vraiment important ?

Le lièvre et la tortue – Gustave Doré

15.3 Algorithmes de tri

Nous allons nous intéresser maintenant à un second problème, celui des très classiques algorithmes de tri. Nous supposons que nous disposons d’une liste d’objets, par exemple :

Nous devons écrire un algorithme capable de fournir en retour une liste triée par ordre croissant :

Tri par sélection

Une première idée est de procéder ainsi :

1.    rechercher le plus petit, le mettre au début,

2.    rechercher le second plus petit, le mettre en deuxième position

3.   

Une fois le minimum placé en première position, tout se passe comme si on recommençait la même chose sur tout le tableau privé du premier élément. Puis à nouveau sur tout le tableau privé des deux premiers etc

Voici l’algorithme correspondant. Notez comment le problème a été décomposé en deux parties : l’algorithme général tri_selection et la fonction rechmin, qui recherche le plus petit élément dans une portion de tableau. En cas, de problème, nous pouvons tester séparément la fonction rechmin et ainsi cibler plus facilement les erreurs.

fonction tri_selection (tableau t) /? Trie le tableau ??sur place?? ?/ n ? taille (t) repeter pour i de 0 à n?2 : 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] : min?j retourner min

Cet algorithme est quadratique (complexité en ?(n²)).

Tri rapide

Voici une autre idée d’algorithme (probablement moins facile à avoir) :

1.    Sélectionner une valeur au hasard dans le tableau : le pivot

2.    Organiser le tableau en deux parties : à gauche les éléments inférieurs au pivot et à droite, les éléments supérieurs au pivot.

3.    Trier les deux parties avec la même méthode

Partitionner le tableau

Voici l’algorithme du tri rapide :

fonction tri_rapide (tableau t,            indices d,f)

si f>d :

p?partitionner(t,d,f) tri_rapide (t,d,p?1) tri_rapide (t,p+1,f)

fonction partitionner (tableau t,              indices d,f) : entier

p?indice au hasard entre d et f /? le pivot ?/

echanger t[f ], t[p] /? on met le pivot à la fin ?/ 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?j?1

si i<j : echanger t[ i ] et t[ j ]

échanger t[f] et t[ i ] retourner i

– La fonction partitionner a un temps d’exécution proportionnel à la taille de la tranche de tableau. – La fonction tri_rapide est récursive. Son temps d’exécution est donné par une relation de récurrence :

partitionner

T(n) = ^z}|{an +2 × T(n/2)

| {z }

puisqu’en moyenne, p est au milieu de la tranche

Tous calculs faits, on trouve une complexité en ?(nlog(n))

Comme pour le cas de la recherche, connaître la complexité des algorithmes est une indication particulièrement utile dès que l’on a beaucoup de grandes quantités de données. La figure II.3 montre les temps mis pour trier des tableaux de 500 à 10 millions de valeurs, en utilisant 3 algorithmes différents : le tri par fusion, le tri par sélection et le tri rapide.

Figure II.3 – Comparaison des temps d’exécution de plusieurs algorithmes de tri

–   pour n < 500 le temps d’exécution reste inférieur à 1 milliseconde.

–   pour n = 100000, le tri par sélection met quelques dizaines de secondes à s’exécuter, contre 0,4 secondes pour le tri rapide.

–   pour n = 10 millions (estimation), le tri par sélection mettrait plus de 2 jours, contre environ 5 secondes pour le tri rapide.

16 Récursivité et Logo

Le monde tel qu’il est vu par Logo, un langage à but pédagogique inventé dans les années 60 par Seymour Papert, est un espace en deux dimensionsdans lequel se déplace une tortue, qui peut ou non laisser une trace des endroits où elle passe. Un programme Logo est composé d’ordres donnés à la tortue (comme «avance de 10» ou «tourne à gauche de 90 degrés»).

Nous allons ici utiliser le module turtle de Python, qui permet de programmer comme en Logo. Les programmes pouvant être récursifs, c’est l’aspect graphique du Logo et la possibilité d’utiliser la récursivité qui permet de réaliser des figures complexes en très peu de lignes.

16.1 Écriture des primitives

Le programme suivant trace un carré ayant pour côté la valeur passée en paramètre :

Pour utiliser ce programme, il faut ensuite entrer, dans un shell Python :

16.2 Courbe de Koch

Supposons que nous désirions créer la figure II.4(a), chaque segment étant de longueur égale et quelconque. Nous écririons la primitive suivante :

                                                     (a) Début 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

Considérons à présent la figure II.4(b).

C’est la même que précédemment, excepté que chaque segment a été remplacé par un modèle réduit de la figure elle même . Sur la figure II.4(c), nous avons à nouveau remplacé chaque segment par le dessin de départ. Et ainsi de suite, jusqu’à obtenir (à l’infini ), la courbe complète (figure II.4(d)).

Naturellement, l’infini est ici lié à la taille d’un pixel à l’écran.

Comment tracer de telles figures? La réponse est très simple, et correspond tout à fait à la façon de tracer la figure à la main. Il suffit de remplacer chaque segment par la figure elle-même, trois fois plus petite, comme dans le programme suivant :

Ce programme comporte néanmoins une grosse erreur. Lorsque longueur vaudra par exemple 1, la tortue va continuer la descente récursive et vouloir tracer la figure pour une arête de , puis , sans jamais s’arrêter Nous devons donc, de même que nous arrêtons la descente récursive lors d’un dessin à la main, indiquer à la tortue à quel moment elle ne doit plus remplacer un segment potentiel par la figure complète, mais bien tracer le segment. Nous pouvons par exemple décider que lorsque la longueur sera inférieure ou égale à un, alors, il faudra arrêter la descente récursive. À ce moment, au lieu de tracer le dessin de la figure II.5(a), il faudra faire un simple segment comme indiqué figure II.5(b). Voici maintenant notre programme complet et fonctionnel :

                                                       (a)                                                                                   (b)

Figure II.5 – Arrêt de la récursivité pour la courbe de Koch

16.3 Autres figures

Il existe de nombreuses courbes, que l’on peut obtenir simplement de manière récursive. En voici quelques-unes :

Triangle de Sierpinski Le triangle de Sierpinski est obtenu par les opérations suivantes. On dessine tout d’abord un triangle (figure II.6(a)), puis, on divise en 4 triangles (figure II.6(b)). Chaque triangle extérieur (il y en a 3) est considéré comme le triangle de départ. Il est donc divisé en 4 (figure II.6(c)). Au bout de quelques itérations, on obtient la figure II.6(d).

                                  (a)                                                            (b)                                                             (c)

(d)

Figure II.6 – Tracé du triangle de Sierpinski

Courbe du dragon La récursivité est parfois «croisée» en ce sens que ce n’est pas toujours la procédure A qui s’appelle elle-même. Ce peut être la procédure A qui appelle la procédure B, et la procédure B qui appelle la procédure A. C’est par exemple le cas dans la courbe du dragon. Sur la figure II.7. sont représentées 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

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 précédemment)

                        1                    2                        3                      4                       5                        6                                                       7                                                          8

Figure II.7 – Courbe du dragon

Vous devriez remarquer (mais ce n’est pas facile) qu’un dragon gauche de profondeur n est composé d’un dragon gauche de profondeur n ? 1 d’une rotation de +, et d’un dragon droit de profondeur n ? 1. Inversement un dragon droit de profondeur n est composé d’un d’un dragon gauche de profondeur n?1 d’une rotation de ?, et d’un dragon droit de profondeur n ? 1. Enfin, un dragon de profondeur 0 est simplement un trait.

Si l’on réduit la taille des traits à 1, on obtient comme dragon gauche de profondeur 15 l’objet de la figure II.8.

Figure II.8 – Dragon gauche de profondeur 15

Chapitre III

Compléments sur Python

Dans ce chapitre sont regroupées des informations sur l’utilisation de Python. Elles ne sont pas exhaustives (le lecteur est encouragé à consulter la documentation officielle), mais pourront aider à débloquer rapidement bon nombre de situations.

             17        Types simples

              17.1      Entiers

Le type int, permet de représenter les entiers de taille machine (quelques octets) ou les grands entiers (limités uniquement par la taille de la mémoire). Le passage de l’un à l’autre (entiers machines ou grands entiers) est transparent pour l’utilisateur depuis la version 3 de Python.

Pour indiquer une valeur entière, il est possible d’utiliser différentes bases :

Les opérations disponibles sur les nombre entiers sont résumées dans la table III.1.

Les opérations de conversion vers les différentes bases sont réalisés avec les fonctions bin, oct, et hex. Les opérations arithmétiques ordinaires sont disponibles sur les entiers :

Division entière

              17.2      Booléens

Les deux seules valeur du type bool sont True et False. Ces deux valeurs peuvent être entrées litéralement ou peuvent être le résultat d’opérateurs de comparaison, comme >, <, >=, <=, == (égal), != (différent).

41

Table III.1 – Opérations disponibles sur les nombre entiers

Les opérateurs dont les opérandes sont des booléens sont les opérateurs logiques or, and, not.

Évaluation incomplète des expressions logiques

Les expression qui ne sont ni le résultat de connecteurs logiques, ni le résultat d’opérateurs de comparaison sont évaluées à True sauf : False, None, la valeur 0 ou 0.0, les collections vides (tuples, dictionnaires, listes, ensembles).

17.3         Nombres à virgule flottante

Le type float permet d’utiliser la représentation en virgule flottante (Norme ieee-754). Toute valeur numérique comportant un point décimal ou entrée en notation scientifique sera de type float. Le type float de Python correspond au codage en double précision(c’est à dire au type double du C) :

Le module math contient de nombreuses fonctions mathématiques (fonctions trigonométriques, logarithmiques ).

              17.4       Nombres complexes

Python offre la possibilité de manipuler des nombres complexes sans utiliser de module complémentaire. Un nombre complexe peut être indiqué littéralement en utilisant j ou le constructeur complex :

Ne pas confondre le j complexe et la variable j. Ce qui suit ne crée pas de nombre complexe :

Pour utiliser les nombres complexes, il faudrait écrire :

Voici quelques méthodes et accesseurs sur les nombres complexes (le module cmath contient d’autres outils) :

             18         Types collections

Les collections : listes, tuples, objets itérables etc. font la force et l’efficacité des langages interprétés modernes. Savoir les manipuler permet de concevoir des programmes concis, élégants et efficaces.

Conteneur ou Collection objet destiné à contenir d’autres objets. Une collection peut être ordonnée (c’est alors une séquence) ou non. Les conteneurs standards sont : listtuplesetstrdict

Séquence collection ordonnée d’éléments indicés par des entiers. Les séquences Python sont par exemple : list,tuple,str.

On peut accéder à un élément d’une séquence en précisant entre crochets le numéro d’ordre de l’enregistrement. La numérotation commence à 0. (un objet de type range se comporte aussi comme une séquence)

Modifiable capacité pour un objet (pas forcément une collection) de modifier son contenu sans que l’objet soit recréé. Ce point est délicat, et il est assez spécifique à Python. Dans le cas d’un conteneur, on peut le qualifier de récursivement (ou complètement) non modifiable s’il est non modifiable et que tous les éléments qu’il contient sont récursivement non modifiables. Les termes anglais pour modifiable/non modifiable sont : mutable, immutable. Type list séquence modifiable d’éléments éventuellement hétérogènes

Type tuple séquence non modifiable d’éléments éventuellement hétérogènes.

Hashable Un objet hashable est un objet récursivement non modifiable. Il peut servir de clé dans un dictionnaire. Les éléments d’un ensemble (set) doivent être hashables.

Type dict (dictionnaire ou tableau associatif) : collection non ordonnée modifiable d’éléments éventuellement hétérogènes. Un tableau associatif est un type de données permettant de stocker des couples clé/valeur, avec un accès rapide à la valeur à partir de la clé. Celle-ci ne peut bien sûr être présente qu’une seule fois dans le tableau. La clé doit être hashable. Le type dict fait partie des collections de la catégorie Mapping qui associent un objet à un autre.

Table III.2 – Propriétés des collections

Type set collection non ordonnée d’éléments hashables distincts.

Itérable capacité, pour une collection, d’égrener ses valeurs, par exemple avec une boucle for Python. Les objets itérables peuvent être parcourus, mais on ne peut pas nécessairement prendre un élément ou un autre en l’adressant.

La table III.2 donne les propriétés des différents types collection.

18.1         Accéder aux éléments

On peut accéder aux éléments d’une séquence par leurs numéros :

Indices négatifs

On peut extraire une tranche de séquence, voire une tranche échantillonée:

Pour les dictionnaires, les numéros sont remplacés par des clés (n’importe quel élément hashable) :

              18.2        Agir sur les collections

Lorsqu’on agit sur un objet (s), il y a deux façons de le faire : En affectant s, comme dans s=s[:]+s[5]. Ceci fonctionne que l’objet soit modifiable ou non. On extrait s[:] et s[5], et on réalise l’opération +, le résultat étant un nouvel objet (il se peut que l’opération + ne soit pas possible avec les opérandes données ). Puis s référencera (affectation) le nouvel objet, l’ancien n’étant plus référencé par s (mais il existe peut être encore, référencé par une autre variable). On peut constater que l’objet référencé par s n’est plus le même en contrôlant la valeur id(s) avant et après l’opération.

En appelant une méthode qui agit sur l’objet qui est référencé par s comme dans s.sort(). Dans ce cas, l’identifiant (id) de s n’est pas modifié et c’est l’objet qui était désigné par s qui est modifé (le type de s doit donc être modifiable, ce qui implique qu’on peut trier ainsi une liste, mais pas un tuple).

Il existe en outre quelques algorithmes implémentés de deux manières :

–   modifiant l’objet d’origine – retournant un nouvel objet modifié Par exemple, si t est une séquence :

–   t.sort() trie la séquence t sur place (elle doit être modifiable)

–   sorted(t) ne modifie pas t et renvoie une nouvelle séquence triée (t n’a pas besoin d’être modifiable) On trouve de même : reversed(t) et t.reverse() etc

              18.3        Copier une collection

La copie des types simples ne pose pas de problème particulier. Il faut en revanche être prudent avec les collections. On peut copier une collection ainsi :

Mais c’est une copie superficielle (shallow copy). Si un des éléments est modifiable (si c’est une liste par exemple), ça peut être un problème. Le test suivant permet de comprendre ce qui se passe :

Pour obtenir un comportement différent, on dispose d’un module copy qui offre une copie en profondeur (deep copy) :

              18.4         Opérations sur les collections

Les opérations sur les collections sont regroupées dans différentes tables :

–   Opérations sur les séquences (listes, tuples, chaînes), table III.3

–   Opérations sur les listes, table III.4

–   Opérations sur les itérables (listes, tuples, chaînes, dictionnaires, ensembles ), table III.5

–   Opérations sur les dictionnaires, table III.6

–   Opérations sur les ensembles, table III.7

Table III.3 – Opérations sur les séquences

Table III.4 – Opérations sur les listes

Table III.5 – Opérations sur les itérables

Table III.6 – Opérations sur les dictionnaires

Table III.7 – Opérations sur les ensembles

             19          Types modifiables ou non

En Python, un type peut être modifiable ou non. Cette distinction est déroutante lorsqu’on débute.

Un objet est modifiable si on peut modifier le contenu référencé. Le contenu d’une liste étant une liste de références, et une liste étant modifiable, on peut changer ces références, ce qui autorise à écrire :

Un tuple n’étant pas modifiable, les mêmes opérations ne sont pas possible :

En revanche, si un des éléments d’un tuple est une liste, et qu’on modifie cette liste, alors ça fonctionne :

Une chaîne de caractères n’étant pas modifiable, on ne peut donc pas modifier un de ses caractères :

On s’en sort en faisant :

ou bien :

20         Clavier et écran

Vos programme peuvent permettre la saisie au clavier avec la fonction input :

La fonction input renvoie une chaîne de caractères, mais on peut la convertir au passage :

L’affichage de chaînes formatées peut se faire de plusieurs façons différentes : La plus simple et la moins souple :

La nouvelle méthode (format) :

---