Niveau: Licence ptrochimie deuxime semestreUniversit du 20 aout 55 Skikda

Cours 2 : bases dalgorithmique11-Dfinitions:1-1-Dfinitions du terme algorithme :Cours 2: bases dalgorithmiqueLe mot algorithme signifie tymologiquement le nom dun mathmaticien arabe du moyen ge : Al-Khawarizmi, il a t le premier a dcrire une mthode claire pour la rsolution dquation en 825.21-Dfinitions:Un algorithme est une squence finie dinstructions faite pour tre excute dans le but de rsoudre un problme prcis, nous retiendrons quun algorithme est une squence dinstructions excutes de faon logique mais non intelligente. 1-2-Dfinitions de lalgorithme:Cours 2: bases dalgorithmique31-Dfinitions:Logique parce que la personne (ou la machine) qui excute les instructions sera capable de facilement comprendre et excuter sans erreur ni ambigit chacune des instructions.Non intelligente parce que la personne qui excute lalgorithme n'aura qu' suivre toutes les instructions, dans l'ordre pour arriver au rsultat sans avoir a comprendre la mthode de solution.1-2-Dfinitions de lalgorithme:Cours 2: bases dalgorithmique41-Dfinitions:Lordinateur nest pas intelligent, pour rsoudre un problme, vous devez lui donner des successions claires dinstructions suivre, ici, nous nous intresserons uniquement la faon de combiner des instructions pour rsoudre un problme indpendamment des langages de programmation, le but de ce cours est donc de vous apprendre crer des algorithmes, a dcomposer des calculs compliqus en successions dtapes simples.1-3- Utilisation en informatique:Cours 2: bases dalgorithmique51-Dfinitions:Un algorithme sert transmettre un savoir faire. Il dcrit clairement les tapes suivre pour raliser un travail. Il permet d'expliciter clairement les ides de solution d'un problme indpendamment d'un langage de programmation.1-4- Les avantages de lutilisation dalgorithme :Cours 2: bases dalgorithmique62-Composition:Un algorithme doit tre lisible et comprhensible par plusieurs personnes, donc, chaque algorithme doit tre compos des lments suivants:Algorithme nom_de_algorithmeVariables:Liste des variables utilises dans lalgorithme.Dbut InstructionsFin2-1- Convention dcriture :Cours 2: bases dalgorithmiqueTitre dcrivant lutilit de lalgorithmeListe et type de toutes les variables utilises par lalgorithmeLe traitement a effectuer par lalgorithme (bloc dinstruction)72-Composition:Le premier concept ncessaire pour concevoir un algorithme est celui de variable, une variable est ladresse dun emplacement dans la mmoire ou est stocke une valeur, une variable porte un nom, ce nom est laisse au choix du concepteur de lalgorithme, il doit commencer par une lettre et ne pas comporter despace, on se sert du nom dune variable pour lire sa valeur ou bien pour la modifier.2-2-Variables dfinition:Cours 2: bases dalgorithmique82-Composition:tudiantNote2universit_de_Skikdatudiant universitaire2013petrochimie2-2- Variables (exemples):Cours 2: bases dalgorithmique92-Composition:Nous manipulerons les types couramment rencontrs dans les langages de programmation : Naturel:Entier:Rel:boolen:caractre, chane,...2-2- Variables les types :Cours 2: bases dalgorithmique102-Composition:Vrifiez si les oprations suivantes sont possible, quel type donne le rsultat :. naturel + naturel. entier - entier. rel * rel. naturel / entier. entier + rel. naturel / rel. caractre + caractre. caractre + chaine de caractres. caractre chaine de caractres2-2- Variables les types (exemple):Cours 2: bases dalgorithmiquenaturelentierrelrelrelrelchaine de caractreschaine de caractresimpossible112-Composition:L'affectation est une opration permettant de modifier la valeur dune variable, la syntaxe de l'affectation est la suivante :nomvariable valeurnomvariable est le nom de la variable dont on souhaite modifier la valeur, valeur est la valeur que lon veut placer dans lemplacement de la variable, notez bien que cette valeur doit tre de mme type que la variable.2-2- Variables - les oprations :Cours 2: bases dalgorithmique122-Composition:A 5 (affectation)A A+1 (incrmentation)place la valeur 5 dans la variable A, si A contenait pralablement une valeur, celle-ci est crase. On peut aussi affecter une variable la valeur dune autre variable: A 5C A+B

2-2- Variables - les oprations :Cours 2: bases dalgorithmiqueOn prend la valeur contenue dans la variable A.On prend la valeur contenue dans la variable B.On additionne ces deux valeurs.On met ce rsultat dans la variable C.132-Composition:Operations arithmtiques: + , - , * , / : concernant les variables de type numriques (naturel, entier, rel,..).Operations de comparaisons:, , , : concerne les variables de possdant un ordre (numrique ou caractre).Operations logiques:Non, et, ou, ouExlusif : sapplique aux operateurs logiques (boolens).Operations sur les caractres et les chaines de caractres:+ : la concatnation.2-2- Variables - les oprations :Cours 2: bases dalgorithmique142-Composition:Quelles sont les valeurs des variables aprs lexcution des instructions suivantes ?A 1B 2C 3D AA C+1B D+CC D+1

2-2- Variables - les oprations (exemple):Cours 2: bases dalgorithmiquePour excuter manuellement les instructions, on construit un tableau nous montrant les valeurs des variables au fil des excutions :

instructionABCDDbut ninininiA 11nininiB 212niniC 3123niD A1231A C+14231B D+C4431C D+14421152-Composition:Quel est lordre de priorit dexcution des oprations (A 2 et B 4 et C 3, D 5) : A+B-C = 2 + 4 3 = 6 3 = 3 A+B*C = 2 + 4 * 3 = 2 + 12 = 14(A+B)*C = (2+4) * 3 = 6 * 3 = 18A/B-C = 2 / 4 3 = - 10 / 4A*B + A*C = 2 * 4 + 2 * 3 = 8 + 6 = 14A*(B+A)*C = 2 * (4 + 2) * 3 = 2 * 6 * 3 = 12 * 3 = 36A ^ C * B = 2 ^ 3 * 4 = 8 * 4 = 32C+D+C+D+C+D = 3 + 5 + 3 + 5 + 3 + 5 = 8 + 3 + 5 + 3 + 5 = 11 + 5 + 3 + 5 = 16 + 3 + 5 = 19 + 5 = 242-2- Variables - les oprations (exemple):Cours 2: bases dalgorithmiqueLordre de la priorit est: ( ) > puissance ^ > / et * > + et Encas dgalit de la priorit, lvaluation seffectue de gauche a droite. 162-Composition:La table de vrit des fonctions logiques :

Non Et Ou ouEx

2-2- Variables boolens :Cours 2: bases dalgorithmique

172-Composition:Rappels sur la logique boolenne :Valeurs possibles : Vrai ou Faux.Associativit des oprateurs et et ou : a et (b et c) = (a et b) et cCommutativit des oprateurs et et ou : a et b = b et a a ou b = b ou aDistributivit des oprateurs et et ou : a ou (b et c) = (a ou b) et (a ou c) a et (b ou c) = (a et b) ou (a et c)Loi de Morgan : non (a ou b) = non a et non b non (a et b) = non a ou non b

2-2- Variables boolens :Cours 2: bases dalgorithmiqueTout comme en arithmtique les oprateurs boolens ont des priorits, la priorit des oprateurs est: ( ) > non > et > ouEx > ouEncas dgalit de la priorit, lvaluation seffectue de gauche a droite. 182-Composition:Pour les variable logique A, B donner le rsultat des opration suivantes (en sachant que A Vrai, B faux) :Non A = non(1) = 0.A et B = 1 et 0 = 0.A ou B = 1 ou 0 = 1.Non A et B = non1 ou 0 = 0 ou 0 = 0.Non(A et B) = non(1 et 0) = non(0) = 1.Non(A ou B) = non(1 ou 0) = non(1) = 0.(A et B) ou (A et non B) = (1 et 0) ou (1 et non(0)) = 0 ou (1 et 1) = 0 ou 1 = 1.2-2- Variables boolens (exemple):Cours 2: bases dalgorithmique192-Composition:Algorithme Dmonstrationvariables:A, B, C : numriques.t : chaine de caractres. Dbut A 1 B A+1 C A A A+1 t exemple1 + exemple2Fin2-3- Lisibilit :Cours 2: bases dalgorithmiqueLa lisibilit des algorithmes est un critre de qualit important, un algorithme correct mais indchiffrable est aussi efficace quun algorithme faux, donc cest un algorithme faux, vous devrez par consquent soigner particulirement vos algorithmes, ils doivent tre faciles a lire, et rdigs de sorte quun lecteur soit non seulement capable de lexcuter, mais aussi capable de le comprendre rapidement.203-Les instructions:De nombreux algorithmes ont pour but de communiquer avec un utilisateur, cela se fait dans les deux sens, les sorties sont des envois de messages a lutilisateur, les entres sont des informations fournies par lutilisateur.3-1- Les entres/sorties :Cours 2: bases dalgorithmiqueUtilisateurcomputer>>Donne moi les donnes que vous voulez traiter?

>> Donnes saisies

>> Voila le rsultat:Entre des donnes traiterDemande de donnesAffichage des rsultats213-Les instructions:Lecture :Il est possible de demander un utilisateur du programme de saisir une valeur, la syntaxe de la saisie est la suivante : Lire(nomvariable)La saisie interrompt le programme jusqua ce que lutilisateur ait saisi une valeur au clavier, une fois cela fait, la valeur saisie est place dans la variable nomvariable, il est possible de saisir plusieurs variables a la suite:lire(A,B,C) place trois valeurs saisies par lutilisateur dans les variables A, B et C.

3-1- Les entres/sorties :Cours 2: bases dalgorithmique223-Les instructions:Ecriture :Pour afficher un message a destination de lutilisateur, on se sert de la commande: crire(message)Cette instruction affiche le message a lutilisateur, par exemple crire(bonjour) affiche bonjour sur lcran, (les guillemets sont trs importantes), il est aussi possible d'afficher le contenu dune variable: crire(A) affiche lcran le contenu de la variable A. 3-1- Les entres/sorties :Cours 2: bases dalgorithmique233-Les instructions:Ecriture :On peut mlanger les messages et les valeurs des variables, par exemple, les instructions: crire(la valeur de A est:) crire(A)ont le mme effet que linstruction crire(la valeur de A est:,A)Lorsque lon combine messages et variables dans les instructions d'affichage, on les spare par des virgules. 3-1- Les entres/sorties :Cours 2: bases dalgorithmique243-Les instructions:Cet algorithme demande a lutilisateur de saisir un entier, ensuite il affiche la valeur saisie puis la mme valeur incrmente de 1.Algorithme Affichage_incrment variables :a: entierDbut crire(Saisissez une valeur numrique) lire(a) crire(Vous avez saisi la valeur:, a) crire( a+1 =,a+1)Fin3-1- Les entres/sorties (exemple) :Cours 2: bases dalgorithmiquecomputer>>Saisissez une valeur numrique

>> 12

>> vous avez saisi la valeur : 12

>> a+1 = 13253-Les instructions:On appelle traitement conditionnel un bloc dinstructions dont lexcution est soumise la vrification dun test.si ... alorsLa syntaxe dun traitement conditionnel est la suivante:Si condition alors Instructionsfin siLes instructions ne sont excutes que si condition est vrifie, par exemple:Si A = 0 alors crire(la valeur de la variable A est nulle)fin si3-2- Traitements conditionnels :Cours 2: bases dalgorithmiqueSi la variable A, au moment du test, a une valeur nulle, alors linstruction crire(La valeur de la variable A est nulle) est excute, sinon, elle est ignore.263-Les instructions:Condition:Une condition est une comparaison, son rsultat est de type boolen, et prend donc deux valeurs: vrai ou faux.Lvaluation de la condition seffectue de la mme manire que lvaluation dune expression boolenne, exemple:Lire(moyenne)Si moyenne 10 alors crire(tudiant admis)finsi3-2- Traitements conditionnels :Cours 2: bases dalgorithmiqueOn peu ajouter une autre condition:Lire(moyenne, sanction_disciplinaire)Si moyenne 10 et non sanction_disciplinaire alors crire(tudiant admis)finsi273-Les instructions:ConditionsUne condition peut tre tout type de test, par exemple:A=2A=B A = B et B 72 >7Not A et B3-2- Traitements conditionnels :Cours 2: bases dalgorithmiqueLa condition A= 2 est vrifie si la valeur contenue dans A est 2. A= B est vrifie si les valeurs contenues dans A et dans B sont les mmes. B 7 est vrifie si B contient une valeur diffrente de 7. 2> 7 est vrifie si 2 est suprieur a 7, donc jamais, cette condition est donc fausse et ne dpend pas des valeurs des variables.283-Les instructions:Si tendueLe traitement conditionnel peut tre tendu de la sorte :si condition alors instructionssinon autres instructionsfinsi3-2- Traitements conditionnels :Cours 2: bases dalgorithmiquesi condition est vrifie, les instructions sont excutes, dans le cas contraire, donc si condition nest pas vrifie, alors ce sont les autres instructions qui sont excutes. 293-Les instructions:Algorithme Valeurs_Distinctes_variablesa,b: entiers.Dbut crire(Saisissez deux valeurs numriques) lire(a,b) si a = b alors crire(Vous avez saisi deux fois la mme valeur, a savoir, a) Sinon crire(Vous avez saisi deux valeurs diffrentes, a,et,b) finsiFin 3-2- Traitements conditionnels (exemple):Cours 2: bases dalgorithmiqueDans lexemple ci-dessus, la condition a= b est value, si a ce moment-la les variables a et b contiennent la mme valeur, alors la condition a= b sera vrifie, dans ce cas, linstruction crire(Vous avez saisi deux fois la mme valeur, a savoir, a) sera excute. Si la condition a= b nest pas vrifie, donc si les variables a et b ne contiennent pas la mme valeur au moment de lvaluation de la condition, cest alors linstruction crire(Vous avez saisi deux valeurs diffrentes, ,a, et , b) qui sera excute.303-Les instructions:ImbricationIl est possible dimbriquer les si a volont :si a < 0 alors si b < 0 alors crire(a et b sont ngatifs) sinon crire(a est ngatif, b est positif ) finsi sinon si b < 0 alors crire('b est ngatif, a est positif') sinon crire('a et b sont positifs') finsifinsi3-2- Traitements conditionnels :Cours 2: bases dalgorithmiqueSi par exemple a et b sont tous deux positifs, alors aucun des deux tests ne sera vrifies, et cest donc le sinon du sinon qui sera excut, a savoir crire(a et b sont positifs).313-Les instructions:Algorithme Signe_du_produitvariables :a,b: entiersDbut crire(Saisissez deux valeurs numriques) lire(a, b) crire(Le produit de, a, par, b, est :) si (a 0 et b 0) ou (a 0 et b 0) alors crire(positif ou nul) sinon crire(ngatif) finsifin3-2- Traitements conditionnels (exemple) :Cours 2: bases dalgorithmiqueLinstruction crire(positif ou nul) sera excute si au moins une des deux conditions suivantes est vrifie :a0 et b0a0 et b0323-Les instructions:Suivant casLorsque qu'on souhaite conditionner lexcution de plusieurs ensembles dinstructions par la valeur que prend une variable, plutt que de faire des imbrications de si a outrance, on prfrera la forme suivante:Suivant variable faire cas valeur1 instructions1 cas valeur2 instructions2 . . . cas valeur n instructions n autres cas instructionsfinsuivant3-2- Traitements conditionnels :Cours 2: bases dalgorithmiquesuivant la valeur que prend la variable, le bloc dinstructions a excuter est slectionne, par exemple, si la valeur de variable est valeur1, alors le bloc instructions1 est excute. Le bloc autres cas est excut si la valeur de variable ne correspond a aucune des valeurs numres.333-Les instructions:Ecrivons un algorithme demandant a lutilisateur le jour de la semaine, affichons ensuite le jour correspondant au lendemain.3-2- Traitements conditionnels (exemple) :Cours 2: bases dalgorithmique343-Les instructions:3-2- Traitements conditionnels (exemple) :Cours 2: bases dalgorithmiqueAlgorithme Lendemainvariables :Erreur: boolenjour, lendemain : chaine de caractresDbut crire(Saisissez un jour de la semaine) lire( jour) erreur 0 suivant jour faire cas dimanche lendemain lundi cas lundi lendemain mardi cas mardi lendemain mercredi cas mercredi lendemain jeudi cas jeudi lendemain vendredi cas vendredi lendemain samedi cas samedi lendemain dimanche autres cas erreur 1 finsuivant si erreur alors crire(Erreur de saisie) sinon crire(Le lendemain du, jour,est, lendemain) finsiFinVous remarquez que si on avait voulu crire le mme algorithme avec des si, on utilise plusieurs imbrications.353-Les instructions:Cest une reprsentation graphique de lalgorithme, pour le construire, on utilise des symboles normaliss, ici on prsente quelques symboles utiliss dans la construction dun algorigramme:3-3- Lalgorigramme :Cours 2: bases dalgorithmiqueSymboleDsignation et rleSymboleDsignation et rleSymbole de traitementSymbole auxiliaireSymbole gnralOpration ou groupe doprations sur des donnes, instructions, pour laquelle il nexiste aucun symbole normalis.Dbut, fin, interruptionDbut, fin ou interruption dun algorigramme.Entre-SortieMise disposition dune information traiter ou enregistrement dune information traite.CommentaireSymbole utilis pour donner des indications sur les oprations effectues.TestExploitation de conditions variables impliquant un choix parmi plusieurs.Les diffrents symboles sont relis entre eux par des lignes de liaisons.Sens conventionnel des liaisonsLe sens gnral des lignes de liaison doit tre :De haut en bas.De gauche droite.363-Les instructions:3-3- Lalgorigramme (exemple):Cours 2: bases dalgorithmiqueAlgorithme comparaisonVariables:A,B : entiers.DEBUT crire(Saisissez A et B:) lire(A, B) Si A > B alors crire(A est suprieur a B) Sinon crire(B est suprieur a A) fin si FINDbutFin crire(Saisissez A et B:)Lire(A,B)Si A > B alorscrire(B est suprieur a A) crire(A est suprieur a B)ouinon373-Les instructions:3-4- les boucles :Cours 2: bases dalgorithmiqueComment on peut calculer la suite suivante:1+2+3+..+1000 ???!!Une boucle permet dexcuter plusieurs fois de suite le mme sous bloc dinstructions, chaque excution du corps dune boucle sappelle une itration, on va voir deux types de boucles :Tant quePourChacune de ces boucles a ses avantages et ses inconvnients que nous verrons dans les planches suivantes.383-Les instructions:3-4- les boucles tant que :Cours 2: bases dalgorithmiqueLa syntaxe dune boucle tant que est la suivante:tant que condition instructionsFin tant queLa condition est value avant chaque itration, a chaque fois quelle est vrifie, on excute les instructions de la boucle, une fois que la condition nest plus vrifie, lexcution se poursuit aprs le fin tant que.

Lavantage de cette boucle est quon est pas obliger de connaitre le nombre ditration a lavance.L inconvnient est le risque dentrer dans une boucle infinie si on ne gre pas bien la condition.393-Les instructions:3-4- les boucles tant que (exemple):Cours 2: bases dalgorithmiqueAffichons par exemple tous les nombres de 1 5 dans lordre croissant:Algorithme de1a5variables :i : entierDbut i 1 tant que i 5 crire (la valeur de i est de :,i ) i i+1 fin tant queFin

Cet algorithme initialise i a 1 et tant que la valeur de i ne dpasse pas 5, cette valeur est affiche puis incrmente, les instructions se trouvant dans le corps de la boucle sont donc excutes 5 fois de suite.La variable i sappelle un compteur, on gre la boucle par incrmentations successives de i et on sort de la boucle une fois que i a atteint une certaine valeur, linitialisation du compteur est trs importante, si vous ninitialisez pas i explicitement, alors cette variable contiendra nimporte quelle valeur et votre algorithme ne se comportera pas du tout comme prvu.403-Les instructions:3-4- les boucles pour :Cours 2: bases dalgorithmiqueLa syntaxe dune boucle pour est la suivante:pour variable de premierevaleur a dernierevaleur [par pas de pas] instructionsFin pourLa boucle pour fait varier la valeur du compteur variable entre premirevaleur et dernirevaleur, le pas est optionnel et permet de prciser la variation du compteur entre chaque itration, le pas par dfaut est 1 et correspond donc a une incrmentation.La boucle pour initialise le compteur variable a la premirevaleur, et tant que la dernirevaleur na pas t atteinte, les instructions sont excutes et le compteur incrment automatiquement.Lavantage de cette boucle est quon est pas obliger de grer le compteur (condition d arrt).L inconvnient est quon doit connaitre a lavance le nombre ditrations a effectuer.413-Les instructions:3-4- les boucles pour (exemple):Cours 2: bases dalgorithmiqueOn reprend lexemple prcdent:Algorithme pour1a5variables :i : entierDbut pour i de 1 a 5 crire(la valeur de i est de :,i ) fin pourFinIci on remarque que linitialisation et lincrmentation du compteur i se fait automatiquement par la boucle.A chaque itration la boucle fait le test sur la valeur de i, si i 5 alors les instructions se trouvant dans le corps de la boucle sont donc excutes.424-Lexcution dun algorithme:4-1- le tableau dexcution :Cours 2: bases dalgorithmiquePour une excution facile et sans ambigit dun algorithme, on introduit la notion de tableau dexcution, ce tableau contiendra les valeurs de toutes les variables utilises dans lalgorithme ainsi que les messages changs entre lutilisateur et lalgorithme travers les instructions dentres sorties.instructionVariable 1..Variable iEntreSortieDbut ninini//Instruction 1Instruction 2.Instruction nFin434-Lexcution dun algorithme:4-1- le tableau dexcution (exemple):Cours 2: bases dalgorithmiqueOn excute lalgorithme suivant pour la valeur de N = 4 ?Algorithme pour1aNvariables :i : entierDbut pour i de 1 a N crire(la valeur de i est de :,i) fin pourFin

instructioni EntreSortieDbut ni//i 11//crire(la valeur de i est de :,i)1/la valeur de i est de : 1i 22//crire(la valeur de i est de :,i)2/la valeur de i est de : 2i 33//crire(la valeur de i est de :,i)3/la valeur de i est de : 3i 44//crire(la valeur de i est de :,i)4/la valeur de i est de : 4i 55//crire(la valeur de i est de :,i)5/la valeur de i est de : 5fin//444-Lexcution dun algorithme:4-1- le tableau dexcution (exemple):Cours 2: bases dalgorithmiqueOn excute lalgorithme suivant?Algorithme carreVariables:nb, nbcarre : entiersDebut nb 1 Tant que nb 3 nbcarre nb * nb crire(nb, ^2 = , nbcarre) nb nb + 1 fin tant queFininstructionnbnbcarreEntreSortieDbut nini//nb 11ni//nbcarre nb * nb11//crire(nb, ^2 = , nbcarre)11/1^2 = 1nb nb + 121//nbcarre nb * nb24//crire(nb, ^2 = , nbcarre)24/2^2 = 4nb nb + 134//nbcarre nb * nb39//crire(nb, ^2 = , nbcarre)39/3^2 = 9nb nb + 149//Fin//45Des questions???Cours 2: bases dalgorithmique46