Introduction à l’algorithmique et à la programmation avec Python

Introduction à l’algorithmique et à la programmation avec Python

-

Documents
50 pages
Lire
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description

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 >>>.

Sujets

Informations

Publié par
Ajouté le 27 février 2014
Nombre de lectures 101
Langue Français
Signaler un problème
Introduction à l’algorithmique et à la programmation avec Python
Laurent Signac https://deptinfo-ensip.univ-poitiers.fr
28 août 2013
Algorithmique et Programmation avec Python
2
Tabledesmatières
I Ordinateur,codage numérique5 1 Ordinateur?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5 2 Codagenumérique de l’information5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Langagesde programmation10. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 4 Constructionstypiques des langages11. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . II Algorithmiqueet programmation13 5 Àquoi sert un algorithme?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .13. . . . . . . 6 Algorithmed’Euclide13. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Poserles problèmes15. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 8 Types,affectations, expressions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 15 9 Fonctionset procédures. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17 10 Conditions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .22 11 Boucles23. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . 12 Affectation,mode de passage des paramètres25. . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 13 Notationpointée. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .29 14 Récursivité30. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 15 Résoudredes problèmes : méthode de travail. . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 31 16 Récursivitéet Logo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .37 III Complémentssur Python41 17 Typessimples. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41 18 Typescollections. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .43 19 Typesmodifiables ou non. . . . . . . 49. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 Clavieret écran. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 50
3
Algorithmique et Programmation avec Python
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’interfaceIdleconvient 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 :https://deptinfo-ensip.univ-poitiers.fr/FILES/PDF/python1a. pdf Les ressources Web associées à ce cours sont : – SurUpdago : Algorithmique et Programmation Python https://deptinfo-ensip.univ-poitiers.fr/ENS/doku Les introduction à Python sont nombreuses sur le Web, et certaines sont de très bonne qualité : – Lecours de Bob Cordeau : http://hebergement.u-psud.fr/iut-orsay/Pedagogie/MPHY/Python/courspython3.pdf – Lecours 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 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 e Summerfield, Mark,Programming in Python 3ed., Addison Wesley, 2 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.
Licence Ce travail est mis à disposition sous licence Creative Commonsby nd(paternité, pas de modification).
http://creativecommons.org/licenses/by-nd/3.0
4
Chapitre I
Ordinateur,codagenumérique
1 Ordinateur? Les machines électroniques nous entourent désormais : de la simple calculatrice aux super-ordinateurs, en passant par lessmartphones, 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 : – unordinateur doit tre programmable – sonprogramme 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 lessmartphones...
1.1 Modèlede 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 – lamémoire, qui contient les données, et le programme en cours d’exécution
1.2 Ordinateursdomestiques 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 debus et les données qui transitent sont représentées sous formebinaire. Dans un ordinateur, absolument tout (données et programmes, en mémoire, sur les disques durs ou surcd...) 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. Obtenir plus d’informations Le film suivant : http://www-sop.inria.fr/science-participative/film/ e a été produit par l’Inriaet retrace l’histoire de l’informatique du 9 siècle à aujour-d’hui en 24 minutes...
2 Codagenumé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. 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...
5
Algorithmique et Programmation avec Python
Pourquoi le binaire? Il y a une raison théorique et une raison technique à l’utilisation 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 fixe, la taille de l’écriture d’un 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 (système assez robuste) En conséquence, toute information est représentable sous forme debits(binary digit = chiffre binaire). La quantité d’information est justement le nombre de bits nécessaires pour représenter cette information.
Unités – lebit(binary digit) est l’unité d’information : 0 ou 1 – l’octetest un groupe de 8 bits (attention, octet se ditbyteen anglais) Tout le reste.... dépend du contexte. En particulier, le préfixe «kilo» correspond dans le système international au 3 101 multiplicateur10, mais conventionnellement, il était utilisé en informatique pour le multiplicateur2. La vérité 3 est que, maintenant, nous devrions utiliser les préfixes dusipour le multiplicateur10(symboles k,M,G...) et 10 20 30 d’autres préfixes (kibi, mébi, gibi,... symboles ki,Mi,Gi...) pour les multiplicateurs2,2,2...Il en est de mme pour les débits (bits/seconde, puis kbits par seconde etc...). Dans les symboles, le «o» de octet est parfois remplacé par le «B» de byte, à ne pas confondre avec le «b» de bit... 10 3 Enfin, l’explorateur Windows utilise le symbole Ko pour2octets (alors que ce devrait tre10octets) et l’utilitaire gnudu -kutilise aussi des kilos de 1024 octets (encore qu’il a une option supplémentaire permettant d’utiliser les kilos dusi). Dans le doute, partez du principe que si on vous vend de la mémoire (disque dur, mémoire flash...) sa taille est indiqué en utilisant lesi...
2.1 Changementsde base L’écriture d’un nombre en basebest formée à partir debsymboles, appelés chiffres. Les 10 chiffres de la base 10 sont par exemple :0,1,2,3,4,5,6,7,8et9. Si l’écriture d’un nombre en basebest :cncn1...c1c0(lescisont leschiffres), sa valeur sera : n n1 10 v(cn)×b+v(cn1)×b+...+v(c1)×b+v(c0)×b v(ci)est lavaleurassociée au chiffre (symbole)ci. La valeur du symbole 9 en base 10 est par exemple neuf. Généralement, pour une basebinférieure à 10, on reprend les mme chiffres qu’en base 10, avec les mmes valeurs (mais on n’utilise que lesbpremiers chiffres). Pour une basebsupé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. 6 5 4 3 2 1 0 1011010|2= 1×02 +×2 +1×12 +×02 +×2 +1×02 +×2 =90 1 0 5A|16= 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 : 90 =2×45 +0 45 =2×22 +1 22 =2×11 +0 11 =2×5 +1 5 =2×2 +1 2 =2×1 +0 1 =2×0 +1 La séquence des restes successifs, lue du dernier au premier donne :1011010qui 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 : 2 1 0123 101,011|2= 1×2 +0×12 +×2 +0×12 +×12 +×2 =5 + 0,25 + 0,125 = 5,375 6
Notes de cours,Ensip1A
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 écrire0,6875en base 2 :
0,6875 0,375 0,75 0.5
×2 = ×2 = ×2 = ×2 =
1,375 0,75 1,5 1
Nous prenons les parties entières des résultats dans l’ordre où elles sont obtenues :1011. Donc0,6875 = 0,1011|2. Développement binaires infinis Notons que si l’écriture d’un nombre non entier en base 2 est finie, ce sera aussi le cas en base 10 (car les puissances négatives de 2 ont toutes une écriture décimale finie). En revanche, si l’écriture décimale est finie, l’écriture en base 2 ne le sera pas forcément (elle sera alors périodique). Par exemple :
En conséquence :0,2 = 0,00110011...
0,2 0,4 0,8 0,6 0,2
×2 = ×2 = ×2 = ×2 = ×2 =
0,4 0,8 1,6 1,2 ...
2.2 Numériquevs 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 argen-tique, 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 – Lescouleurs, sur un écran, sont formées par synthèse additive (addition de la lumière). L’impression, au contraire, est réalisée par synthèse soustractive. – Lescouleurs primaires en synthèse additive sont : le rouge, le vert et le bleu (en synthèse soustractive, il s’agit du cyan, du magenta, et du jaune). – Supposons qu’on dispose de 3 leds, une rouge, une verte et une bleue, et que chacune puisse tre allumée ou éteinte (on ne peut pas varier leur intensité). 3 À partir de ces 3 leds, nous pouvons obtenir2 =8couleurs puisque chaque led peut tre soit allumée, soit éteinte. Nous obtenons ainsi du noir si toutes les leds sont éteintes, du blanc si elles sont toutes allumées ou du cyan si seules les leds bleues et vertes sont allumées. Puisqu’à chacune des 8 couleurs obtenues, correspond un état de chacune des trois leds, nous pouvons convenir de coder l’état des leds dans l’ordre rouge, vert, bleu par 0 (led éteinte) ou 1 (led allumée). Ainsi, une série de 3 chiffres binaires, (autrement dit un entier entre 0 et 7) est associé à une couleur : 0 000 noir4 100 rouge 1 001 bleu5 101 magenta 2 010 vert6 110 jaune 3 011 cyan7 111 blanc
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 unstandard, et cette adoption facilitera grandement les échanges de données entre les personnes ou les programmes. En particulier, si le standard est publié, 2 on dit qu’il estouvert, 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.
2. Précisément,un standard ouvert est publié mais ne doit pas imposer non plus de restrictions quant à son utilisation.
7
Algorithmique et Programmation avec Python
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 Openxml...), les images (jpeg,png...), l’audio (mp3,ogg,flac...), la vidéo (mpegv2, Vorbis,h-264...).
2.3 Codagedu 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 figureI.1contient donc 128 symboles, caractères non imprimables compris)
FigureI.1 –Tableascii(numérotée de 0 à 7F, en héxa) tirée de Wikipédia
Le codeasciia rapidement été insuffisant, faute de caractères accentués, grecs, cyrilliques, hébreux, chinois... Deux autres types de codage ont donc fait leur apparition : – Lesextensionsrajoutent 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. – Unicodeest une norme qui recensetousles caractères existant dans une table (il y en a plus de100 000actuellement). Les codes sont ensuite représentés dans un codage particulier commeutf-8, ouutf-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égatifn, on obtient le complément à 2 denen 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 den, puis en inversant les 0 et les 1, puis en ajoutant 1 : Exemple de codage en complément à deux Nous souhaitons coder le nombre -66 en complément à 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
8
Notes de cours,Ensip1A
Le résultat est le codage en complément à 2 sur 8 bits de66. On remarque que c’est aussi l’écriture binaire de 25666 = 190.
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 envirgule flottante. Ce codage (normeieee-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ésenterde manière 38 38 approchéeles nombres entre3.4×10et3.4×10, tout en atteignant des valeurs aussi petites (en valeur absolue) 45 que1.4×10. Nous ne détaillerons pas ici ce codage, assez technique, mais il est important de retenir : – quec’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 Une indication de vitesse des processeurs donnée enflops(ou un de ses multiples) fait référence au nombre d’opérations en virgule flottantes par seconde (FLoating point Operations Per Second). L’ordinateur le plus rapide du monde (depuis juin 2012, c’est la version de BlueGene/Q à 1,5 millions de curs) a 15 une vitesse estimée de 16,32 PetaFlops (10) soit plus de 16 millions de milliards d’opérations en virgule flottante 9 par seconde. Un ordinateur domestique atteint des vitesses de quelques dizaines de GigaFlops (10Flops)
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) oump3(compression avec pertes). Compact-disc Audio Sur un compact-disc audio, les données ne sont pas compressés, et ce sont les échantillons qui sont directement représentés. Les enregistrements sont stéréo (deux signaux), échantillonnés à 44100 Hz (pour conserver les fréquences jusqu’à 22kHz), chaque échantillon étant représenté sur 16 bits.
2.6 Images Un image numérique (telle que celle stockée dans les appareils photos) est une matrice depixels. 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 Larésolutionendpi(Dots Per Inch) fait référence au nombre de pixels d’une image rapporté à la taille physique (sur un écran ou sur papier). On estime qu’une impression est très correcte (pour des besoins ordinaires) au delà de 300dpi, c’est à dire au delà de 300 pixels par pouce. La taille maximum à laquelle pourra tre imprimée une photo prise avec un appareil à 12 millions de pixels, tout en satisfaisant cette contrainte de qualité, sera donc (1pouce= 2,54cm) : 4000/300×2,5433,8cm c’est à dire environ 25 centimètres sur 34.
Formats d’image Si la compréhension de la numérisation d’un image est assez simple, le stockage de l’image numérique est réalisé dans un des multiples formats disponibles. Comme pour le son, ces codages ont généralement pour objectif de réduire la taille des fichiers de stockage. La compression réalisée peut tre faite avec perte (c’est le cas du formatjpeg) ou sans perte (c’est le cas du formatpng). Le nombre de couleurs simultanément présentes peut tre de 16,7 millions (codage sur 24 bits sans palette) ou moins (comme avec le formatgif). Ainsi, le choix d’un format d’image peut 9
Algorithmique et Programmation avec Python
dépendre du type d’image à coder (on utilise facilementjpegpour des photos, et le formatpngest préférable pour des dessins au trait).
2.7 Codagessymboliques Avant de terminer cette section sur le codage, signalons l’existence des codagessymboliques, que l’on peut rencontrer pour tout type d’objet (images, musique). Grossièrement, on peut dire que le codage symbolique est un codageplus intelligentde l’objet. Il se situe à un niveau supérieur d’abstraction et s’intéresse aucontenuet ausensde l’objet plutôt qu’à sonrendu. 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 codagevectorielde 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 depixelisation(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é estmidi, 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èreautomatiqueune 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 3 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 Langagesde 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 unalgorithme(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? L’informatique sur papier est possible, mais elle est moins distrayante que sur machine. De plus, la réalisation d’un programme est le moyen d’obtenir des réponseseffectivesaux problèmes qui nécessitent l’utilisation d’un ordinateur. Enfin, la programmation est une activité de création et de rigueur très formatrice, et elle aide à comprendre la manière dont fonctionnent les algorithmes.
Pseudo-code Le pseudo-code est utilisé dans de nombreux ouvrages d’algorithmique (ci-dessous, l’exponentiation modulaire don-4 née dans leclr, et légèrement remise en page) : Exponentionation_modulaire(a,b,n) c0 d1 soit< bk, bk1, ..., b0>la représentation binair de b pour ik à 0 faire c2c d(d.d) mod n sibi=1 alors cc+1 d(d.a) mod n retournerd Il s’agit d’un algorithme rédigé dans un langage assez naturel (plutôt qu’un langage de programmation), mais qui 3. Pourune image, cette étape s’appelle larasterisationet elle est effectuée chaque fois qu’on affiche l’objet vectoriel sur un écran.
10