Les principes de l’Algorithmique et Programmation1 IntroductionInformatique : traitement automatis´e de l’information.Algorithme :ensembleder`eglesop´eratoiresdontl’applicationpermetder´esoudreunprobl`emeen un nombre fini d’op´erations.Programme :s´equencesd’instructionsetdedonn´eesenregistr´eessurunsupportetsusceptiblesd’ˆetre trait´ee par un ordinateur.Donn´ees : objets manipul´es par le programme.StructuresdeDonn´ees :organisationdesdonn´eesdansdesstructuresayantunerepr´esentationfix´ee et des op´erations d’acc`es, modification,...Le programme est la traduction d’un algorithme et des structures de donn´ees dans un langagede programmation qui impose une syntaxe rigoureuse.Objectif de l’analyste programmeur : Ecrire un programme dans un langage donn´e dontl’ex´ecution permet de r´esoudre un probl`eme.Exercice 1 Donner les avantages d’un algorithme sur un programme. Donner les avantages d’unprogramme sur un algorithme.Exercice 2 Citer des exemples d’algorithmes.1Exercice 3 Le texte suivant est-il un algorithme?Recette de la pate a` choux :Ingr´edients : 1/4 litre d’eau, 100g de beurre, 125g de farine, 4 oeufs,1 pinc´ee de sel, 1 cuill´er´eede sucre.Dans une casserole, faire bouillir l’eau avec le beurre, le sel le sucre. A la premi`ere ´ebullition,retirer la casserole du feu, et verser la farine. Tourner rapidement avec un ecuill`ere en bois entravaillant sur le feu jusqu’`a ce qu’elle se d´etache compl`etement de la casserole. Hors du feuajouter ...
StructuresdeDonne´esesndnndoisanioatgro:ntunerepturesayaedssrtcue´seadsnnoitatnese´r fixe´eetdesop´erationsd’acce`s,modification,... Leprogrammeestlatraductiond’unalgorithmeetdesstructuresdedonne´esdansunlangage de programmationqui impose une syntaxe rigoureuse.
Objectif de l’analyste programmeuragnalnusnademmarntdo´enndogeprogreunEcri: l’exe´cutionpermetder´esoudreunproble`me.
Exercice 1Donner les avantages d’un algorithme sur un programme. Donner les avantages d’un programme sur un algorithme.
Exercice 2Citer des exemples d’algorithmes.
1
Exercice 3Le texte suivant estil un algorithme? Recettedelapatea`choux: Ingre´dients:1/4litred’eau,100gdebeurre,125gdefarine,4oeufs,1pince´edesel,1cuill´er´ee de sucre. Dansunecasserole,fairebouillirl’eauaveclebeurre,lesellesucre.Alapremi`eree´bullition, retirerlacasseroledufeu,etverserlafarine.Tournerrapidementavecunecuille`reenboisen travaillantsurlefeujusqu’a`cequ’ellesed´etachecomple`tementdelacasserole.Horsdufeu ajouterlesoeufsuna`unentravaillantchaquefoislapre´parationaveclacuill`ere.
2 LesLangages 2.1 Constituants Une langue : –Syntaxe:cate´goriesdemots(noms,verbes,adjectifs,...),re`glesdegrammaire...Analyse lexicale permet de reconnaitre les mots de la langue. Analyse syntaxique permet de recon naitrelesphrasesbienform´ees. –Se´mantique:lesensd’unephraseBienforme´en’apastoujoursunsens. Cat´egoriesdelangages: –languenaturelle:syntaxeets´emantiqueassezlaxistesmaissoupled’emploi.Onpeutseparler memeavecdesphrasespeuorthodoxesetincorrectes.Se´mantiqueintuitivemaispouvant eˆtreambigue.Ler´ecepteurestunetrehumainintelligentetre´actif. –langageinformatique:syntaxerigoureuseetrigide.Las´emantiquen’estpasintuitiveet metenoeuvredescadrescomplexes(memesilesprincipessontsimples)etdifficiles`abien apprehender.Lerecepteurestunemachinedenu´eed’intelligence. – langagede description d’algorithme : une syntaxe moins rigide mais assez stricte pour ne pasdonnerd’ambiguit´esurlas´emantiquedecequiestde´crit.
2.2 Unexemple Proble`me:Donnerlatabledeconversiondefranceneurode100en100depuis0jusqu’a`1000 en utilisant un coefficient de conversion de 6.56 Donne´es:sommeenfranceteuros Algorithme:re´p´etitionducalculdeconversionde100en100 MIN=0 MAX=1000 INTER=100 COEF=6.56 franc=MIN Tant que franc <=MAX faire euro=franc/COEF afficher euro franc=franc+INTER fait Programmes C : /* File: conver.c Auteurs: Prof cree le 08 02 04 modifie le:08 02 04*/ /* conversion des sommes en francs en euros */ /* affichage de 0 a 1000 par intervalle de 100 */ #include <stdio.h>
2
#define MIN 0/*somme minimale a convertir*/ #define MAX 1000/*somme maximale a convertir */ #define INTER 100/*intervalle entre deux sommes*/ #define COEF 6.56/*coefficient de conversion */ int main () { float franc, euro; franc=MIN; while (franc <= MAX) { euro = franc / COEF; printf("somme: en franc %4.0fen euro %6.2f\n",franc, euro); franc=franc+INTER; } return 0; } Programme Python : def franc2euro(): " conversion des sommes en francs en euros \ affichage de 0 a 1000 par intervalle de 100" MIN=0 MAX=1000 INTER=100 COEF=6.56 franc=MIN while (franc<=MAX): euro=franc/COEF print "somme en franc: ",franc, "en euro: ",euro franc=franc+INTER Lesdeuxprogrammessontsimilairesmaisdiff´erents:l’unestplussimplequel’autre.Tousles 1 deuxsontd´ecritsdansunlangageimpe´ratifetimpl´emententunmeˆmealgorithmedeconversion quireposesurlar´ep´etitiond’uneop´erationsimple. Danscecoursd’initiation,nousallonsapprendre`ae´criredesprogrammesenPython. Exercice 4Trouver les exemples d’algorithmes les plus anciens connus. Calculdesurface(carr´e,triangle,..),algorithmed’euclide(1ersiecle),desresteschinois. Exercice 5.eonddegr´iondusece´entauqoituu’dnr´deolesrigomethD´ecl’alrire
3 Langageet Machine Pourcommencernousdonnonslasyntaxedeslangagesquenousutilisons.Nousdonnonsa`la fois la syntaxe d’un vrai langage informatique : Python et un langage de description d’algorithme.
3.1 Commentaires Lescommentairesservent`aexpliquerlecomportementduprogrammes(enlanguenaturelle) et ne jouent aucun role dans le comportement du langage. #ce programme calcule la surface d’un cercle 1.enfaitpythonestunlangageobjet,maisonneleverraquesoussonaspectimp´eratif
3
3.2 Lesexpressions –Lesnomsappel´esidentificateurs:de´signentdesvariables,fonctions,... Usuellementde changex, y, pi, taux`treracamoemsec(i.e....,edecsuit,eltturentnap¸nacre eng´en´eral) –Lesexpressions:combinaisonsdenoms,valeurde´finies,avecdesop´erateurs(pre´de´finisdans lelangageetfabriqu´esparleconcepteurduprogramme).. .pi*(r**2), x+z,. Exp::=C|Idf|Exp op Exp| Certainessuitesdecaract`eresnesontpasautorise´escommeidentificateurscarcesontdesmots re´serve´s:leursensestpr´ede´finietcorresponda`desconstructionsdulangage.Exempleif, while, for,. . . Op´erateursclassiques: –Arithme´tique:+,,*,/,% –Op´erateurdecomparaison(`are´sultatboole´enVouF)<, >,==, <=, >= –Op´erateurbool´eenand,or(a`argumentsetre´sultatbool´een) Ambiguit´e:quesignifie4+3*2? leverlesambiguite´s:parenth´esage(4+3)*2ou4+(3*2)oure`glesdepriorite´:**plusfortque *,/plusfortsque+,.Sinone´valuationdeG`aD:5*10/6 Exercice 6:deontiuavelale´’atdtseluler´nnerDo 2**3*31, 8/2+3, 12*3+1 3.3 Constructionsde base Remarque : en python, l’indentation fait partie de la syntaxe (elle remplace l’utilisation de parenthe`seoudemotscl´ebeginend). Instructions de base – affectation: var=exp Python var=exp Sensintuitif:Donnelavaleurdeexpa`var – condition: si cond alors Ins1 sinon Ins2 fsi Python if cond: Ins1 else: Ins2 avec la variante elif en cas de suite de conditions Sensintuitif:sil’´evaluationdeconddonnevraion´evalueIns1sinonon´evalueIns2. –Ite´ration:TantquecondfaireInstfait Python : while cond: Inst Sch´ema: Sens intuitif : Tant que evaluer cond donne vrai on effectue Inst – Sequence: Ins1 Ins2 Python Ins1 Ins2 – Entree/sortie: x=input() output(x) Python x=input() print x