Algorithmique - Faculté des Sciences Rabat
Contents
1. lire A crire Entrer le second nombre lire B si A gt B alors crire Le nombre le plus grand est A sinon crire Le nombre le plus grand est B finsi fin M El Marraki 24 15 02 2007 Algorithmique module I SMP SMC Organigramme sa nb annee Tests imbriqu s Graphiquement on peut tr s facilement repr senter un si comme un aiguillage de chemin de fer Un si ouvre donc deux voies correspondant deux traitements diff rents Mais il y a des tas de situations o deux voies ne suffisent pas Par exemple un programme devant donner l tat de l eau selon sa temp rature doit pouvoir choisir entre trois r ponses possibles solide liquide ou gazeuse Exemple Variable Temp entier D but crire Entrez la temp rature de l eau lire Temp si Temp lt 0 Alors crire C est de la glace finsi si Temp gt 0 Et Temp lt 100 Alors crire C est du liquide finsi si Temp gt 100 Alors crire C est de la vapeur finsi M El Marraki 25 15 02 2007 Algorithmique module I SMP SMC Les tests successifs portent sur une la m me chose la temp rature la valeur de la variable Temp Il serait ainsi bien plus rationnel d imbriquer les tests de cette mani re Exemple Variable Temp en Entier D but crire Entrez la temp rature de l eau lire Temp si Temp lt 0 Alors crire C est de la glace sinon si Temp2. A B Exercice 4 Que produit l algorithme suivant Variables A B C cha ne de caract res D but Nas B 12 CEARB crire C C Fin Exercice 5 1 Ecrire un algorithme permettant d changer les valeurs de deux variables A et B et ce quel que soit leur contenu pr alable 2 On dispose de trois variables A B et C Ecrivez un algorithme transf rant A la valeur de B B la valeur de C et C la valeur de A quels que soient les contenus pr alables de ces variables Exercice 6 Ecrivez un algorithme qui calcule et affiche la surface et la circonf rence d un cercle 27r et zr L algorithme demandera l utilisateur d entrer la valeur du rayon M El Marraki 21 15 02 2007 Algorithmique module I SMP SMC Exercice 7 Comment calculer le plus rapidement possible x 99 Calculer x avec le minimum de multiplication Exercice 8 Ecrivez un algorithme qui calcule et affiche la surface et la circonf rence d un cercle 27 r et zr L algorithme demandera l utilisateur d entrer la valeur du rayon Exercice 9 crire un algorithme qui effectue la lecture du temps t en seconde et il affiche le temps t en jours heure minutes secondes Exemple si t 21020 secondes l algorithme affichera 0 jours 5 heures 50 minutes et 20 secondes M El Marraki 22 15 02 2007 Algorithmique module I SMP SMC 3 5 4 si alors si alors sinon Les
3. El Marraki 26 15 02 2007 Algorithmique module I SMP SMC Bien pour une moyenne comprise entre 14 et 16 14 lt moyenne lt 16 Assez bien pour une moyenne comprise entre 12 et 14 12 lt moyenne lt 14 Passable pour une moyenne comprise entre 10 et 12 10 lt moyenne lt 12 Exercice 13 crivez un algorithme qui permet de r soudre une quation du second degr ax bx c 0aveca 40 Exercice 14 Les tudiants ayant pass l examen d algorithmique en session de Juin ont t class s selon leurs notes en trois cat gories pour une note inf rieure strictement 5 l tudiant est limin pour une note sup rieure ou gale 5 et inf rieur strictement 10 l tudiant passe la session de rattrapage pour une note sup rieure ou gale 10 l tudiant valide le module Ecrivez un algorithme qui demande l utilisateur d entrer la note du module puis affiche la situation de l tudiant selon sa note on suppose que l utilisateur entre une note valide entre 0 et 20 3 5 5 Les Boucles La notion d it ration boucle est une des notions fondamentales de l algorithmique On l utilise souvent quand on doit exercer plusieurs fois le m me traitement sur un m me objet ou plusieurs objets de m me nature Mais son r el int r t r side dans le fait que l on peut modifier chaque r p tition les objets sur lesquels s exerce l action r p t e Pour comprendre l int
4. e ci dessus Prenons le cas n est compris entre 5 et 8 En fait cette phrase cache non une mais deux conditions Car elle revient dire que n est sup rieur 5 et n est inf rieur 8 Il y a donc bien l deux conditions reli es par ce qu on appelle un op rateur logique le mot ET Comme on l a voqu plus haut l informatique met notre disposition trois op rateurs logiques ET OU et NON Le ET a le m me sens en informatique que dans le langage courant Pour que C ET C3 soit VRAI il faut imp rativement que C soit VRAIE et que C soit VRAIE M El Marraki 23 15 02 2007 Algorithmique module I SMP SMC Il faut se m fier un peu plus du OU Pour que C1 O C3 soit VRAI il suffit que C soit VRAIE ou que C soit VRAIE Le point important est que si C est VRAIE et C2 est VRAIE alors C O C2 est VRAIE Le OU informatique ne veut donc pas dire ou bien VRAI amp NON FAUX On repr sente tout ceci dans des tables de v rit ET V F V V F O V F F F F VV v F V F Exemple Probl me Etant donn s deux nombres entiers positifs identifier le plus grand des deux nombres Solution Analyse si A gt B alors le plus grand est A sinon le plus grand est B Conception Algorithme variables A B entiers d but crire Programme permettant de d terminer le plus grand de deux entiers positifs crire Entrer le premier nombre
5. on r p te ce proc d jusqu ce que le quotient obtenu est nul L algorithme Variables i n nb entiers Debut Ecrire Entrer la valeur de n lire n igen nb 0 TantQue i lt gt 0 faire i i 2 nb nb 1 FinTantQue Ecrire Pour coder n en binaire il faut nb bits Fin Ex cution Entrer la valeur de n 13 Pour coder 13 en binaire il faut 4 bits Entrer la valeur de n 1750 Pour coder 1750 en binaire il faut 11 bits Entrer la valeur de n 0 Pour coder 0 en binaire il faut 0 bits Erreur Am lioration Variables i n nb entiers Debut Ecrire Entrer la valeur de n lire n i n 2 Pour le cas de z ro nb 1 TantQue i lt gt 0 faire 1 lt 1j2 nb nb 1 FinTantQue Ecrire Pour coder n en binaire il faut nb bits Fin Une autre solution Variables i n n entiers Debut Ecrire Entrer la valeur de n M El Marraki 33 15 02 2007 Algorithmique module I SMP SMC lire n LEen nb 0 R p ter i i 2 nb nb 1 jusqu i 0 Ecrire Pour coder n en binaire il faut nb bits Fin 3 6 Exercices Exercice 15 1 crivez un algorithme qui affiche 100 fois la phrase je ne dois pas arriver en retard en classe 2 crivez un algorithme qui affiche les entiers de 1 100 3 crivez un algorithme qui affiche les entiers pairs de 1 100 Exercice 16 1 crivez un algorithm
6. traduction et r alisation de l algorithme dans un langage pr cis Test V rification du bon fonctionnement de l algorithme Remarque Les programmes sont souvent sur optimis s Il n est pas toujours indispensable de se donner la peine de trouver l implantation la plus efficace d un algorithme mois que ce dernier ne soit susceptible d tre utilis pour une t che tr s r p titive Dans les autres cas une mise en uvre simple conviendra souvent on pourra tre s r que le programme fonctionnera peut tre cinq ou dix fois moins vite que la version la plus optimis e ce qui se traduira ventuellement par quelques secondes suppl mentaires l ex cution En revanche un mauvais choix d algorithme peut entra ner une diff rence d un facteur cent mille ou plus ce qui se traduira en minutes en heures voir en jours au niveau des temps d ex cution Les caract ristiques d un Algorithme e Un algorithme est une marche suivre 1 dont les op rations sont toutes d finies et portent sur des objets appel s informations dont l ordre d ex cution des op rations est d fini sans ambigu t qui est r put e r soudre de mani re certaine un probl me ou une classe de probl mes s exprime dans un langage ind pendant des langages de programmation D 13 L algorithmique et la programmation Un programme est la traduction d un algorithme dans un certain langage de programmation Il faut
7. de l algorithme R le que fait cet algorithme Facultatifs Entr e les donn es n cessaires Sortie les r sultats produits par l algorithme Variables la d claration des variables Debut Instruction 1 Instruction 2 ind les commentaires explicatives des instructions Instruction k Fin M El Marraki 11 15 02 2007 Algorithmique module I SMP SMC 2 Variables Dans un programme informatique on va avoir en permanence besoin de stocker provisoirement des valeurs Il peut s agir de donn es issues du disque dur fournies par l utilisateur frapp es au clavier Ces donn es peuvent tre de plusieurs types elles peuvent tre des nombres du texte etc D s que l on a besoin de stocker une information au cours d un programme on utilise une variable 2 1 D claration des variables La premi re chose faire avant de pouvoir utiliser une variable est de cr er la bo te et de lui coller une tiquette Ceci se fait tout au d but de l algorithme avant m me les instructions proprement dites C est ce qu on appelle la d claration des variables Une variable ne peut tre utilis e que s elle est d clar e La d claration se fait par la donn e du nom de la variable et du type de la variable 2 1 1 Noms de variables Le nom de la variable l tiquette de la bo te ob it des r gles qui changent selon le langage utiliser Les principales r gles respecter sont e Le nom de variab
8. il faudra alors parfois r crire enti rement le programme Il y a trois cat gories de langage de programmations les langages interpr t s et les langages interm diaires et les langages compil s Langage interpr t Un langage de programmation est par d finition diff rent du langage machine Il faut donc le traduire pour le rendre intelligible du point de vue du processeur Un programme crit dans un langage interpr t a besoin d un programme auxiliaire l interpr teur pour traduire au fur et mesure les instructions du programme Exemples de langages interpr t s Le langage HTML les pages web le langage Maple calcul math matique Prolog Intelligence artificielle etc Langage compil Un programme crit dans un langage dit compil va tre traduit une fois pour toutes par un programme annexe le compilateur afin de g n rer un nouveau fichier qui sera autonome c est dire qui n aura plus besoin d un programme autre que lui pour s ex cuter on dit d ailleurs que ce fichier est ex cutable Un programme crit dans un langage compil a comme avantage de ne plus avoir besoin une fois compil de programme annexe pour s ex cuter De plus la traduction tant faite une fois pour toute il est plus rapide l ex cution Toutefois il est moins souple qu un programme crit avec un langage interpr t car chaque modification du fichier source il faudra recompiler le programme pour que les modificat
9. lt 100 Alors crire C est du liquide sinon crire C est de la vapeur finsi finsi Fin Nous avons fait des conomies au niveau de la frappe du programme au lieu de devoir taper trois conditions dont une compos e nous n avons plus que deux conditions simples Mais aussi et surtout nous avons fait des conomies sur le temps d ex cution de l ordinateur Si la temp rature est inf rieure z ro celui ci crit dor navant C est de la glace et passe directement la fin sans tre ralenti par l examen d autres possibilit s qui sont forc ment fausses Cette deuxi me version n est donc pas seulement plus simple crire et plus lisible elle est galement plus performante l ex cution Les structures de tests imbriqu s sont donc un outil indispensable la simplification et l optimisation des algorithmes Exercices Exercice 10 Ecrivez un algorithme qui donne le maximum de trois nombres saisis au clavier Effectuez des tests pour 2 5 8 313 8 6 1 Exercice 11 Ecrivez un algorithme qui demande deux nombres l utilisateur et l informe ensuite si leur produit est n gatif positif ou nul attention on ne doit pas calculer le produit des deux nombres Exercice 12 crivez un algorithme qui permet de discerner une mention un tudiant selon la moyenne de ses notes Tr s bien pour une moyenne comprise entre 16 et 20 16 lt moyenne lt 20 M
10. primitives que nous allons pr senter maintenant vont permettre la machine de choisir les ex cutions suivant les valeurs des donn es Lors de l ex cution l algorithme la primitive si C alors A finsi O C est une condition on pr cisera plus loin la nature de cette condition et A une instruction ou une suite d instructions a pour effet de faire ex cuter A si et seulement si C est satisfaite La primitive si C alors A sinon B finsi A pour effet de faire ex cuter A si C est satisfaite ou bien B dans la cas contraire C non satisfaite Une condition est une comparaison C est dire qu elle est compos e de trois l ments a une valeur a un op rateur de comparaison a une autre valeur Les valeurs peuvent tre a priori de n importe quel type num riques caract res Les op rateurs de comparaison sont lt gt lt gt L ensemble constitue donc si l on veut une affirmation qui a un moment donn est VRAIE ou FAUSSE A noter que ces op rateurs de comparaison s emploient tout fait avec des caract res Ceux ci sont cod s par la machine dans l ordre alphab tique les majuscules tant syst matiquement plac es avant les minuscules Ainsi on a E lt WwW VRA I Maman gt Papa FAUX maman gt Papa VRAI Conditions compos es Certains probl mes exigent parfois de formuler des conditions qui ne peuvent pas tre exprim es sous la forme simple expos
11. savoir qu chaque instruction d un programme correspond une action du processeur M El Marraki 5 15 02 2007 Algorithmique module I SMP SMC 1 3 1 Le but de la programmation e Utiliser l ordinateur pour traiter des donn es afin d obtenir des r sultats e Abstraction par rapport au mat riel ind pendance application plate forme mat rielle e Interm diaire entre le langage machine binaire et le langage humain 1 3 2 Langages de programmation Le langage utilis par le processeur est appel langage machine Il s agit d une suite de 0 et de 1 du binaire Toutefois le langage machine est difficilement compr hensible par l humain Ainsi il est plus pratique de trouver un langage interm diaire compr hensible par l homme qui sera ensuite transform en langage machine pour tre exploitable par le processeur L assembleur est le premier langage informatique qui ait t utilis Celui ci est encore tr s proche du langage machine mais il permet d j d tre plus compr hensible Toutefois un tel langage est tellement proche du langage machine qu il d pend troitement du type de processeur utilis chaque type de processeur peut avoir son propre langage machine Ainsi un programme d velopp pour une machine ne pourra pas tre port sur un autre type de machine on d signe par le terme portable un programme qui peut tre utilis sur un grand nombre de machines Pour pouvoir l utiliser sur une autre machine
12. une variable de type primitif on copie le contenu d un endroit un autre Par exemple si on crit A B pour des types primitifs alors le contenu de B est copi dans A Si alors on modifie A bien entendu B n est pas affect par cette modification C est ce qu on rencontre g n ralement en programmation Echanger deux valeurs Probl me soit 2 variables quelconques nombres ou caract res x et y ayant respectivement comme valeur a et b quelles sont les affectations qui donneront x la valeur b et y la valeur a Analyse la premi re id e est d crire x y y lt x Mais a ne marche pas les deux variables se retrouvent avec la m me valeur b Il faut mettre la valeur de x de cot pour ne pas la perdre on utilise une variable auxiliaire z et on crit les instructions suivantes ARS le CIRE Ey a a AE Le programme complet avec notre pseudo langage est Nom change R le changer deux valeurs Entr e x et y Sortie x et y Variables x y zZz quelconques Debut x 3 initialisation de x et y y 6 z Ex on stocke la valeur de x dans z x y on peut maintenant crire dans x RE on remet l ancien contenu de x dans y Fin M El Marraki 15 15 02 2007 Algorithmique module I SMP SMC V rification 1l s agit de v rifier que l algorithme donne bien la solution voulu Ecrivant apr s chaque instruction les valeurs des variables X Y et Z x 3 Rec G
13. 007 Algorithmique module I SMP SMC Ex cution donner un entier 234 le double de 234 est 468 Exemple 2 Probl me Multiplier deux nombres entiers En utilisant les primitives suivantes lire crire affecter multiplier Solution Algorithme Nom multiplication R le demander deux nombres et afficher leur multiplication Entr e AetB Sortie C variables B C entiers D but crire entrer la valeur de A lire A crire entrer la valeur de B lire B CEA B crire le produit de A et B est C Fin Ex cution entrer la valeur de A 12 entrer la valeur de B 11 le produit de 12 est de 11 est 132 3 2 5 Exercices Exercice 1 Quelles seront les valeurs des variables A B et C apr s ex cution des instructions suivantes Variables A B C Entier D but A lt 8 B 2 C lt A B A64 CEB A Fin M El Marraki 20 15 02 2007 Algorithmique module I SMP SMC Exercice 2 Quelles seront les valeurs des variables A et B apr s ex cution des instructions suivantes Variables A B Entier D but A lt 2 B lt lt A S5 A lt A B B lt B 2 A lt B A Fin Exercice 3 Que produit l algorithme suivant Variables B Entier D but crire entrer la valeur de A lire A crire entrer la valeur deB lire B A lt A B B lt A B A lt B A B crire crire Fin
14. Algorithmique module I SMP SMC Universit Mohammed V Agdal Facult des Sciences Rabat D partement Math matiques et Informatique Le module I2 SMP SMC Facult des Sciences Algorithmique Par Pr Mohamed El Marraki 2005 2006 M El Marraki 1 15 02 2007 Algorithmique module I SMP SMC Sommaire 1 G n ralit s sur l Algorithmique Introduction L algorithmique Principe Les caract ristiques d un Algorithme Analyse descendante L algorithmique et la programmation Le but de la programmation Langages de programmation Pseudo langage 2 Les variables D claration des variables Noms de variables Types de variables 3 Les Primitives Affectation D finition et notation Utilisations Lire et crire Donn es et r sultats Les objets manipul s par l algorithme Les tests si alors si alors sinon Conditions compos es Organigramme Tests imbriqu s Les Boucles La boucle TantQue La boucle R p ter jusqu La boucle Pour jusqu Les boucles imbriqu es Une m thodologie pour l criture d une boucle 4 Les structures de donn es statiques Tableaux une dimension Introduction Notation et utilisation algorithmique M El Marraki 2 15 02 2007 Algorithmique module I SMP SMC Types pour les tableaux Quelques algorithmes utilisant les tableaux une dimension Tableaux deux dimensions Notation et d finitions Algorithmes sur les matrices 5 L
15. P 3 Z n y 6 x 3 y 6 z j z amp MR 3 V G 2 31 x y Mg eph ya e6 2 g y z x 6 y 3 z 3 donc tout va bien Autre m thode s il s agit de nombres entiers nous pouvons nous passer d une variable auxiliaire mais en utilisant les primitives additionner et soustraire xa M x y n vb ge 4 1 yo x E x y T a Dy y p y G REY x atb y atb b a x E x y x a b a b y a donc tout va bien Le programme complet avec notre pseudo langage est Nom change entiers R le changer deux valeurs enti res Entr e x et y Sortie x et y Variables x y nombres Debut x lt lt 3 initialisation de x et y y 6 x x y yE amp Ex y x x y Fin 3 1 2 Expression et op rateurs Expression Dans une instruction d affectation on trouve o gauche de la fl che un nom de variable o droite de la fl che ce qu on appelle une expression un ensemble de valeurs reli es par des op rateurs et quivalent une seule valeur o L expression situ e droite de la fl che doit tre du m me type que la variable situ e gauche Si l un des trois points num r s ci dessus n est pas respect la machine sera incapable d ex cuter l affectation et d clenchera une erreur M El Marraki 16 15 02 2007 Algorithmique module I SMP SMC Op rateurs Un op rateur est un signe qui relie deux valeurs pour produire un r sulta
16. a R p ter jusqu a Pour jusqu La boucle TantQue Le sch ma de la boucle TantQue est TantQue conditions Instructions FinTantQue Le principe est simple le programme arrive sur la ligne du TantQue Il examine alors la valeur de la condition Si cette valeur est VRAI le programme ex cute les instructions qui suivent jusqu ce qu il rencontre la ligne FinTantQue Il retourne ensuite sur la ligne du TantQue proc de au m me examen et ainsi de suite On ne s arr te que lorsque la condition prend la valeur FAUX Illustration avec notre probl me de contr le de saisie Variable Rep en Caract re Ecrire Voulez vous un caf O N TantQue Rep O ET Rep N Lire Rep Si Rep O ET Rep N Alors Ecrire Saisi rron e Recommencez Finsi FinTantQue La boucle R p ter jusqu Le sch ma de la boucle r p ter est R p ter Instructions jusqu conditions M El Marraki 28 15 02 2007 Algorithmique module I SMP SMC Le principe est simple toutes les instructions crites entre R p ter et jusqu sont ex cut es au moins une fois et leur ex cution est r p t e jusqu ce que la condition plac e derri re jusqu soit satisfaite Illustration avec notre probl me de contr le de saisie Variable Rep en Caract re Ecrire Voulez vous un caf O N R p ter Lire Rep Si Rep O ET Rep N Alors Ecrire Saisi rro
17. culant une autre variable sommel N N 1 2 qui est la somme 1 2 3 N et la compar e somme ensuite afficher le r sultat de la comparaison M thodologie pour l criture d une boucle gt gt YYY rep rer une action r p titive donc une boucle choix entre boucle avec compteur ou sans Question Peut on pr voir d terminer le nombre d it rations a si oui boucle avec compteur la boucle pour a sinon boucle sans compteur Est ce que il faut commencer l action avant de tester ou l inverse si tester d abord alors boucle TantQue si action puis tester alors R p ter jusqu crire l action r p titive et l instruction de boucle choisie Question Faut il pr parer les donn es l it ration suivante si oui compl ter le corps de boucle initialiser les variables utilis es si n cessaires crire les conditions d arr t voire l incr mentation de la variable de contr le ex cuter pour les cas extr mes et au moins un cas normal M El Marraki 32 15 02 2007 Algorithmique module I SMP SMC 3 6 Exemple Ecrire l algorithme qui compte le nombre de bits n cessaires pour coder en binaire un entier n Le nombre de bits n cessaire pour coder l entier n est Ig n l entier juste au dessus du logarithme base 2 de l entier n Analyse on initialise une variable nb 0 et chaque fois que l on divise n par 2 on augment de 1 la valeur de nb
18. e passage Il va sans dire que de telles manipulations perturbent compl tement le d roulement normal de la boucle Exemple Probl me On veut crire un algorithme qui calcul la somme des entiers positifs inf rieurs ou gaux N R solution 1 tape Analyse 1 Entrer la valeur de N 2 Calculer la somme des N premiers entiers positifs 3 Afficher le r sultat 2 tapes Conceptions 1 d claration des variables N i somme entiers crire donner la valeur de N lire N si N lt 0 alors erreur initialiser somme et i R p ter somme somme i ie i 1 jusqu i gt N crire la somme est somme 2 d claration des variables N i somme entiers crire donner la valeur de N lire N si N lt 0 alors erreur initialiser somme et i TantQue i lt N somme somme i ie i 1 M El Marraki 31 15 02 2007 Algorithmique module I SMP SMC FinTantque Ecrire la somme est somme 3 d claration des variables N i somme entiers crire donner la valeur de N lire N si N lt 0 alors erreur initialiser somme et i Pour i allant de 1 N somme amp somme i FinPour Ecrire la somme est somme 3 tape Test Somme N entiers Donner N 1 N doit etre gt 0 Somme N entiers Donner N 7845 La somme est 30775935 Somme N entiers Donner N 10 La somme est 55 Remarque Pour cet exemple on peut faire une v rification plus compl te en cal
19. e qui calcule la somme des n premiers nombres entiers positifs L algorithme demandera l utilisateur d entrer la valeur de n 2 crivez un algorithme qui calcule la somme des n premiers nombres entiers positifs paires L algorithme demandera l utilisateur d entrer la valeur de n Exercice 17 1 Ex cuter le programme suivant Variable i j Entier debut Pour i lt 1 jusqu 5 Ecrire i i Pour j lt 1 jusqu 3 Ecrire le produit de i et j est i j FinPour FinPour Fin 2 Ex cuter le programme suivant Variable i j Entier debut Pour i lt 1 jusqu 5 Ecrire i i FinPour Pour j lt 1 jusqu 3 Ecrire le produit de i et j est i j FinPour Fin Exercice 18 M El Marraki 34 15 02 2007 Algorithmique module I SMP SMC 1 crivez un algorithme qui calcule la somme S suivante Sie y D dE SR 2 nel m2 L algorithme demandera l utilisateur d entrer la valeur de n 2 crivez un algorithme qui calcule le factoriel de n n 1x2x3x x n 1 x n L algorithme demandera l utilisateur d entrer la valeur de n Exercice 19 Soit l algorithme suivant variables a b r entiers d but crire donner les valeurs de a et b lire a b TantQue b gt 0 faire r asb a b reste de la division de a par b a lt b brer FinTanQue crire a Fin 1 Ex cuter l algorithme afficher dans un tableau les valeurs de a b et r
20. es et r sultat Pour pouvoir effectuer un calcul sur une variable la machine doit conna tre la valeur de cette variable Si cette valeur n a pas t d termin e par des initiations ou des calculs pr c dents il faut que l utilisateur lui fournisse c est une donn e Il s agit alors d introduire une valeur partir de l ext rieur de la machine et pour cela l algorithme doit contenir l instruction qui commande la machine de lire la donn e Si un algorithme contenant l instruction X A 2 la machine ne peut ex cuter cette instruction que si elle conna t la valeur de A en supposant que la valeur de A en ce moment n est pas connu alors l algorithme doit contenir l instruction lire A qui signifie mettre dans la case la valeur donn e par le clavier organe d entr e de la machine D s que le programme rencontre une instruction lire l ex cution s interrompt attendant l arriver d une valeur par l interm diaire du clavier D s que la touche Entr e Enter a t frapp e l ex cution reprend Si on veut conna tre le r sultat d un calcul ou le contenu d une variable X l algorithme doit contenir l instruction qui commande la machine de fournir ce r sultat Cette instruction est crire X quisignifie mettre sur l cran organe de sortie de la machine le contenu de la case X Cette action ne modifie pas le contenu de X Exemple soit le morceau d algorithme su
21. es fonctions et les proc dures Introduction Les fonctions Introduction Les fonctions pr d finies D claration d une fonction Passage d arguments Utilisation des fonctions Les fonctions r cursives Les Proc dures M El Marraki 3 15 02 2007 Algorithmique module I SMP SMC 1 G n ralit s sur l Algorithmique 1 1 Introduction L algorithmique est un terme d origine arabe hommage Al Khawarizmi 780 850 auteur d un ouvrage d crivant des m thodes de calculs alg briques Un algorithme est une m thode de r solution de probl me nonc e sous la forme d une s rie d op rations effectuer La mise en uvre de l algorithme consiste en l criture de ces op rations dans un langage de programmation et constitue alors la brique de base d un programme informatique 1 Une recette de cuisine est un algorithme 2 Le mode d emploi d un magn toscope est aussi un algorithme 3 Indiqu un chemin un touriste gar ou faire chercher un objet quelqu un par t l phone c est fabriquer et faire ex cuter des algorithmes Un algorithme c est une suite d instructions qui une fois ex cut e correctement conduit un r sultat donn 1 Si l algorithme est juste le r sultat est le r sultat voulu et le touriste se retrouve l o il voulait aller 2 Si l algorithme est faux le r sultat est disons al atoire et d cid ment ce magn toscope ne marche pas Pour fonctionner un algorith
22. i TantQue i lt n faire crire Bonjour tous la 1 1 fois 1 i 1 FinTantQue Des boucles imbriqu es De m me qu une structure SI ALORS peut contenir d autres structures SI ALORS une boucle peut contenir d autres boucles Variables i j entier Pour i allant de 1 10 crire Premi re boucle Pour j allant de 1 6 crire Deuxi me boucle Finpour Finpour Dans cet exemple le programme crira une fois Premi re boucle puis six fois de suite 3 Deuxi me boucle et ceci dix fois en tout A la fin il y aura donc eu 10 x 6 60 passages dans la deuxi me boucle celle du milieu Notez la diff rence marquante avec cette structure Variables i j entier Pour i allant de 1 10 crire Premi re boucle Finpour Pour j allant de 1 6 crire Deuxi me boucle Finpour M El Marraki 30 15 02 2007 Algorithmique module I SMP SMC Ici il y aura dix critures cons cutives de Premi re boucle puis six critures cons cutives de Deuxi me boucle et ce sera tout Examinons l algorithme suivant Variable i entier Pour i allant de 1 10 i lt i x 2 crire Passage num ro i Finpour On remarque que la variable i est g r e en double ces deux gestions tant contradictoires D une part la ligne Pour augmente la valeur de i de 1 chaque passage D autre part la ligne i i 2 double la valeur de i chaqu
23. ions prennent effet D autre part un programme compil a pour avantage de garantir la s curit du code source En effet un langage interpr t tant directement intelligible lisible permet n importe qui de conna tre les secrets de fabrication d un programme et donc de copier le code voire de le M El Marraki 6 15 02 2007 Algorithmique module I SMP SMC modifier Il y a donc risque de non respect des droits d auteur D autre part certaines applications s curis es n cessitent la confidentialit du code pour viter le piratage transaction bancaire paiement en ligne communications s curis es Exemples de langages compil s Le langage C Programmation syst me le langage C Programmation syst me objet le Cobol Gestion etc Langages interm diaires Certains langages appartiennent en quelque sorte aux deux cat gories pr c dentes LISP Java Python car le programme crit avec ces langages peut dans certaines conditions subir une phase de compilation interm diaire vers un fichier crit dans un langage qui n est pas intelligible donc diff rent du fichier source et non ex cutable n cessit d un interpr teur Les applets Java petits programmes ins r s parfois dans les pages Web sont des fichiers qui sont compil s mais que l on ne peut ex cuter qu partir d un navigateur Internet ce sont des fichiers dont l extension est class Toutefois peu pr s tous les langages de progra
24. iques du langage O O O 1 3 4 Les donn es et les programmes sont stock s dans des fichiers Un fichier est identifi par un nom et une extension fichier doc pgcd c texte tex etc Un fichier est caract ris par des attributs taille date de cr ation date de modification etc L exploitation d un fichier par une application se fait par l interm diaire du syst me d exploitation qui accomplit les op rations logiques de base suivantes ouvrir fermer un fichier lire crire dans un fichier L utilisateur peut cr er d truire organiser lire crire modifier et copier des fichiers ou des enregistrements qui les composent La d marche de programmation et analyse descendante La r solution d un probl me passe par toute une suite d tapes Phase d analyse et de r flexion algorithmique Phase de programmation choisir un langage de programmation traduction de l algorithme en programme programme ou code source compilation traduction du code source en code objet traduction du code objet en code machine ex cutable compr hensible par l ordinateur Phase de test Phase d ex cution M El Marraki 8 15 02 2007 Algorithmique module I SMP SMC Programme binaire ex cutable Le travail est ici surtout bas sur l analyse du probl me et l criture de l algorithme La r alisation d un programme passe par l analyse descendante du probl me il faut r ussi
25. ivant A tant une donn e X un r sultat lire A x A2 crire X Sch ma des actions effectu es par l utilisateur et la machine Utilisateur Machine A X lecture L utilisateur donne 12 12 calcul 12 144 criture L utilisateur lit 144 La machine lit sur le clavier et crit sur l cran l utilisateur crit sur le clavier et lit sur l cran M El Marraki 18 15 02 2007 Algorithmique module I SMP SMC 3 2 3 Les libell s Avant de lire une variable il est tr s fortement conseill d crire des libell s l cran afin de pr venir l utilisateur de ce qu il doit frapper crire Entrez votre nom lire NomFamille 3 2 4 Exemples Exemple 1 Quel est le r sultat produit par le programme suivant Variables val dval entiers D but val 234 dval val 2 crire val crire dval Fin R ponses 234 468 1 am lioration Variables val dval entiers D but crire donner un entier un libell lire val dval val 2 crire le double est crire dval Fin Ex cution donner un entier 234 le double est 468 2 am lioration Nom double R le demande un nombre et affiche sont double Entr e val Sortie dval Variables val dval entiers D but crire donner un entier lire val dval val 2 crire le double de val est dval Fin M El Marraki 19 15 02 2
26. le peut comporter des lettres et des chiffres e On exclut la plupart des signes de ponctuation en particulier les espaces e Un nom de variable doit commencer par une lettre e Le nombre maximal de caract res qui composent le nom d une variable d pend du langage utilis e Ne pas utiliser les mots cl s du langage de programmation 2 1 2 Types de variables Lorsqu on d clare une variable il ne suffit pas de cr er une bo te r server un emplacement m moire il faut pr ciser ce que l on voudra mettre dedans car de cela d pendent la taille de la bo te l emplacement m moire et le type de codage utilis Types num riques classiques Commen ons par le cas tr s fr quent celui d une variable destin e recevoir des nombres Si l on r serve un octet pour coder un nombre on ne pourra coder que 2 256 valeurs diff rentes Cela peut signifier par exemple les nombres entiers de 1 256 ou de 0 255 ou de 127 128 Si l on r serve deux octets on a droit 216 65 536 valeurs avec trois octets 2 16 777 216 etc M El Marraki 12 15 02 2007 Algorithmique module I SMP SMC Type Num rique Plage Octet de 0 255 Entier simple de 32768 32767 Entier double de 2147483648 2147483647 de 3 40x10 _1 40x10 pour les n gatives de 1 40x10 3 40x10 R el simple a pour les positives 324 308 les n gatives les positive
27. mbres 0 et 1 Le type bool en est tr s conomique en termes de place m moire occup e un seul bit suffit M El Marraki 13 15 02 2007 Algorithmique module I SMP SMC En g n ral dans un algorithme on trouve des d clarations de variables de la forme Variables a b c delta x y nombres nom prenom chaines de caract res ok booleen 3 Primitives 3 1 Affectation expression et op rateurs 3 1 1 Affectation D finition et notation L affectation est l action l mentaire dont l effet est de donner une valeur une variable ranger une valeur une place L affectation est r alis e au moyen de l op rateur ou en C et en Pascal Elle signifie prendre la valeur se trouvant du c t droit souvent appel e rvalue et la copier du c t gauche souvent appel e value Une rvalue repr sente toute constante variable ou expression capable de produire une valeur mais une lvalue doit tre une variable distincte et nomm e autrement dit il existe un emplacement physique pour ranger le r sultat Par exemple on peut affecter une valeur constante une variable A lt 4 mais on ne peut pas affecter quoi que ce soit une valeur constante elle ne peut pas tre une lvalue on ne peut pas crire 4 A Exemple Xx lt 3 Signifie mettre la valeur 3 dans la case identifi e par X A l ex cution de cette instruction la valeur 3 est rang e en X nom de la variable La valeur corre
28. me doit donc contenir uniquement des instructions compr hensibles par celui qui devra l ex cuter l ordinateur L ADN qui est en quelque sorte le programme g n tique l algorithme la base de construction des tres vivants est une cha ne construite partir de quatre l ments invariables Ce n est que le nombre de ces l ments et l ordre dans lequel ils sont arrang s qui vont d terminer si on obtient une puce ou un l phant Les ordinateurs eux m mes ne sont fondamentalement capables d ex cuter que quatre op rations logiques 1 l affectation de variables 2 la lecture criture 3 les tests 4 les boucles Un algorithme informatique se ram ne donc toujours au bout du compte la combinaison de ces quatre petites briques de base Il peut y en avoir quelques unes quelques dizaines et jusqu plusieurs centaines de milliers dans certains programmes La taille d un algorithme ne conditionne pas en soi sa complexit de longs algorithmes peuvent tre finalement assez simples et de petits algorithmes peuvent tre tr s compliqu s L informatique est la science du traitement automatique de l information Pour cela il faut 1 mod liser cette information 2 d finir l aide d un formalisme strict les traitements dont elle fera l objet 3 et enfin traduire ces traitements dans un langage compr hensible par un ordinateur Les deux premiers points concernent l algorithmique alors que le der
29. mmation sont bas s sur le m me principe Le programme est constitu d une suite d instructions que la machine doit ex cuter Celle ci ex cute les instructions au fur et mesure qu elle lit le fichier donc de haut en bas jusqu ce qu elle rencontre une instruction appel e parfois instruction de branchement qui lui indique d aller un endroit pr cis du programme Il s agit donc d une sorte de jeu de piste dans lequel la machine doit suivre le fil conducteur et ex cuter les instructions qu elle rencontre jusqu ce qu elle arrive la fin du programme et celui ci s arr te Historique des langages e Langage de bas niveau proche du langage machine Jusqu en 1945 langage binaire 1950 langage assembleur e Langage de haut niveau proche des langages naturels Depuis 1955 Programmation proc durale Fortran Cobol Basic Pascal C Ada Programmation orient objet SmallTalk C Delphi Java Programmation logique Prolog Et beaucoup d autres e Evolution o Programmation imp rative fonction Exemples Pascal C o Programmation orient e objet POO Exemples SmallTalk Java C M El Marraki 7 15 02 2007 Algorithmique module I SMP SMC 1 3 3 La notion de fichier Dans un programme les instructions et donn es r sident en m moire centrale pour tre ex cut es Les programmes et les donn es sont sauvegard es dans des fichiers qui portent des extensions sp cif
30. n e Recommencez Finsi Jusqu Rep O OU Rep N La boucle Pour jusqu Cette boucle est utile surtout quand on conna t le nombre d it rations effectuer Le sch ma de la boucle Pour est Pour i allant de d but jusqu fin Instructions FinPour Le principe est simple a oninitialise i par d but a on test si on a pas d pass fin a on ex cute les instructions a onincr mentei i lt i l a on test si on a pas d pass fin a etc Exemple Probl me On veut crire un algorithme qui affiche le message Bonjour tous 100 fois R solution Au lieu d crire l instruction crire Bonjour tous 100 fois On utilise plut t une boucle variable i enti re Pour i allant de 1 100 faire crire Bonjour tous finpour On peut am liorer ce programme par M El Marraki 29 15 02 2007 Algorithmique module I SMP SMC a ajouter un entier n le nombre de fois que le message s afficher l cran a afficher la variable i dans la boucle pour num roter les passages dans la boucle variable n i enti res crire entrer le nombre n lire n Pour i allant de 1 n faire crire Bonjour tous la i fois finpour Dans la boucle pr c dente le i est incr ment automatiquement Si on d sire utiliser la boucle TantQue il faut incr menter le i soit m me variable n i enti res crire entrer le nombre n lire n ic
31. nier point rel ve de ce que l on nomme la programmation M El Marraki 4 15 02 2007 Algorithmique module I SMP SMC L criture d un programme consiste g n ralement implanter une m thode de r solution d j connue et souvent con ue ind pendamment d une machine pour fonctionner aussi bien sur toutes les machines ou presque Ainsi ce n est pas le programme mais la m thode qu il faut tudier pour comprendre comment traiter le probl me Le terme algorithme est employ en informatique pour d crire une m thode de r solution de probl me programmable sur machine Les algorithmes sont la mati re de l informatique et sont l un des centres d int r t de la plupart sinon la totalit des domaines de cette science 1 2 L alsorithmique Principe D finition Un algorithme est une s quence bien d finie d op rations calcul manipulation de donn es etc permettant d accomplir une tache en un nombre fini de pas En principe un algorithme est ind pendant de toute implantation Cependant dans la pratique de la programmation il s av re indispensable de tenir compte des capacit s du langage de programmation utilis e La conception d un algorithme passe par plusieurs tapes Analyse d finition du probl me en terme de s quences d op rations de calcul de stockage de donn es etc Conception d finition pr cise des donn es des traitements et de leur s quencement Implantation
32. pour a a 50 et b 45 b a 21 et b 13 on a 96 et b 81 2 Que fait l algorithme pr c dant Exercice 20 1 Un nombre entier p diff rent de 1 est dit premier si ses seuls diviseurs positifs sont 1 et p Ecrivez un algorithme qui effectue la lecture d un entier p et d termine si cet entier est premier ou non 2 Deux nombres entiers n et m sont qualifi s d amis si la somme des diviseurs de n est gale m et la somme des diviseurs de m est gale n on ne compte pas comme diviseur le nombre lui m me et 1 Exemple les nombres 48 et 75 sont deux nombres amis puisque Les diviseurs de 48 sont 2 3 4 6 8 12 16 24 et 2 3 4 6 8 12 16 24 75 Les diviseurs de 75 sont 3 5 15 25 et 3 5 15 25 48 Ecrire un algorithme qui permet de d terminer si deux entiers n et m sont amis ou non M El Marraki 35 15 02 2007
33. programme 1 3 5 Ex cuter un programme La mise au point d un programme informatique se fait en plusieurs tapes Donn es Ex cution du programme Transformation des donn es en r sultats Ordinateur Programme 1 3 6 Pseudo langage Un algorithme doit tre lisible et compr hensible par plusieurs personnes Il doit donc suivre des r gles pr cises il est compos d une ent te et d un corps l ent te qui sp cifie o le nom de l algorithme Nom o son utilit R le o les donn es en entr e c est dire les l ments qui sont indispensables son bon fonctionnement Entr e o les donn es en sortie c est dire les l ments calcul s produits par l algorithme Sortie o les donn es locales l algorithmique qui lui sont indispensables D claration le corps qui est compos M El Marraki 10 15 02 2007 Algorithmique module I SMP SMC o du mot clef d but o d une suite d instructions indent es o du mot clef fin Le plus important pour un algorithme sont les d clarations ainsi que les instructions qui constituent le corps de l algorithme Il existe des instructions qui ne servent qu la clart de l algorithme l ordinateur les ignore compl tement ce sont les commentaires Un commentaire a la syntaxe suivante ceci est un commentaire Exemple voici le sch ma d un algorithme crit en notre pseudo langage Nom le nom
34. r trouver les actions l mentaires qui en partant d un environnement initial nous conduisent l tat final L analyse descendante consiste d composer le probl me donn en sous probl mes et ainsi de suite jusqu descendre au niveau des primitives Les tapes successives donnent lieu des sous algorithmes qui peuvent tre consid r s comme les primitives de machine interm diaires proc dures en Pascal fonction en C Le travail de l analyse est termin lorsqu on a obtenu un algorithme ne comportant que e Des primitives de la machine initiale e Des algorithmes d j connus L analyse descendante est la mise en pratique du Discours de la m thode de Descartes M El Marraki 9 15 02 2007 Algorithmique module I SMP SMC L ordre des instructions est essentiel la machine ne peut ex cuter qu une action la fois et dans l ordre donn c est la propri t de s quentialit Une fois ces actions d termin es il suffit de les traduire dans le langage de programmation Durant l criture d un programme on peut tre confront 2 types d erreur o les erreurs syntaxiques elles se remarquent la compilation et sont le r sultat d une mauvaise criture dans le langage de programmation o les erreurs s mantiques elles se remarquent l ex cution et sont le r sultat d une mauvaise analyse Ces erreurs sont beaucoup plus graves car elles peuvent se d clencher en cours d exploitation du
35. r t des boucles on se place dans un cas bien pr cis Prenons le cas d une saisie au clavier une lecture par exemple on pose une question laquelle l utilisateur doit r pondre par O Oui ou N Non Mais l utilisateur maladroit risque de taper autre chose que O ou N D s lors le programme peut soit planter par une erreur d ex cution parce que le type de r ponse ne correspond pas au type de la variable attendu soit se d rouler normalement jusqu au bout mais en produisant des r sultats faux Alors dans tout programme on met en place ce qu on appelle un contr le de saisie pour v rifier que les donn es entr es au clavier correspondent bien celles attendues par l algorithme On pourrait essayer avec un si Voyons voir ce que a donne Variable Rep Caract re crire Voulez vous un caf O N lire Rep si Rep O et Rep N alors crire Saisie erronn e Recommencez Lire Rep finsi M El Marraki 27 15 02 2007 Algorithmique module I SMP SMC a marche tant que l utilisateur ne se tromper qu une seule fois et il rentre une valeur correcte la deuxi me demande Si l on veut galement viter une deuxi me erreur il faudrait rajouter un SI Et ainsi de suite on peut rajouter des centaines de SI Mais cela ne r sout pas le probl me La seule issue est l utilisation d une boucle Il existe trois fa ons d exprimer algorithmiquement l it ration u TantQue
36. s R el double de 1 79x10 4 94x10 de 4 94x10 t 1 79x10 La syntaxe d une d claration de variable num rique en pseudo langage aura la forme Variable g Num rique Variables PrixHT TauxTVA PrixTTC Num rique Type alphanum rique On dispose donc galement du type alphanum rique galement appel type caract re type cha ne ou en anglais le type string Dans une variable de ce type on stocke des caract res qu il s agisse de lettres de signes de ponctuation d espaces ou m me de chiffres Le nombre maximal de caract res pouvant tre stock s dans une seule variable string d pend du langage utilis e Un groupe de caract res est appel cha ne de caract res e En pseudo code une cha ne de caract res est toujours not e entre guillemets car il peut y avoir une confusion entre des nombres et des suites de chiffres Par exemple 423 peut repr senter e le nombre 423 quatre cent vingt trois e ou la suite de caract res 4 2 et 3 not e 423 LL La syntaxe d une d claration de variable de type alphanum rique en pseudo langage aura la forme Variable nom cha ne Variables x y caract re Type bool en Le dernier type de variables est le type bool en on y stocke uniquement les valeurs logiques VRAI et FAUX On peut repr senter ces notions abstraites de VRAI et de FAUX par tout ce qu on veut de l anglais TRUE et FALSE ou des no
37. spond au contenu 3 La variable correspond au contenant X On peut repr senter la variable X par une boite ou case et quand elle prend la valeur 3 la valeur 3 est dans la case X gm On remarque qu une variable ne peut contenir un instant donn qu une seule valeur Utilisations Voici quelques effets d clench es par l utilisation de l affectation Instructions actions effets ke3 X 3 X En x 2 x 2 x plus de 3 Y lt Xx Y X ka X FA X EM M El Marraki 14 15 02 2007 Algorithmique module I SMP SMC La derni re instruction Y X signifie copier dans Y la valeur actuelle de X Un petit exercice instructif Quelles sont les valeurs successives prises par les variables X et Y suit aux instructions suivantes XER D R ponses X 1 1 4 29 9 9 Y 4 4 4 13 Remarque A noter aussi que l affectation est une expression comme une autre c est dire qu elle retourne une valeur Il est donc possible d crire Xx E y E Z ceci revenant affecter Y le r sultat de l valuation de Z 2 puis X le r sultat de l affectation Y Z 2 c est dire la valeur qu on a donn e Y Remarquez l ordre d valuation de la droite vers la gauche L affectation des types primitifs est tr s simple Puisque les donn es de type primitif contiennent une valeur r elle et non une r f rence un objet en affectant une valeur
38. t o Op rateurs num riques Ce sont les quatre op rations arithm tiques addition E soustraction multiplication division Mentionnons galement le qui signifie puissance 45 au carr s crira donc 45 2 La multiplication et la division sont prioritaires sur l addition et la soustraction e 12 3 5e et 12 3 5 valent strictement la m me chose savoir 41 e En revanche 12 3 5 vaut 12 8 soit 96 o Op rateur alphanum rique amp Cet op rateur permet de concat ner deux cha nes de caract res Exemple Nom concat ner R le concat ner deux cha nes de caract res Entr e A et B Sortie CARS Variables A B C caract re D but A Bonjour Be Tous le monde C lt AE amp B Fin La valeur de C la fin de l algorithme est Bonjour Tous le monde 3 2 Lire et crire 3 2 1 Introduction Soit le programme suivant Variable enti re D but A 1272 Fin Ce programme nous donne le carr de 12 soit 144 On remarque que o si l on veut le carr d un autre nombre que 12 il faut r crire le programme M El Marraki 17 15 02 2007 Algorithmique module I SMP SMC o Le r sultat est calcul par la machine elle le garde pour elle et l utilisateur qui ex cute ce programme ne saura jamais quel est le carr de 12 C est pourquoi il faut utiliser des instructions qui permettent l utilisateur de dialoguer avec la machine 3 2 2 Donn
Download Pdf Manuals
Related Search