12/03/2013
COURS ALGORITHMIQUE
ET PROGRAMMATION
INFORMATIQUE
DUT INFORMATIQUE
S1
Marie-Agns peraldi-frati
Mitre de confrences en informatique
UNS/IUT de Nice cte dazur
1
M AP @ U N I C E . F R
MAP - UNS
RFRENCES
Algorithmes D.E Knuth CSLI Publications 2011
Introductipon a la science informatique G. Dowek Ed RPA 2010
Elments pour une histoire de linformatique, D.E Knuth CSLI
Publications 2011
Cours et exercices corrigs dalgorithmique- J. Julliand Ed Vuibert
Fev 2010
Algorthmique mthodes et modles , P Lignelet Ed Masson 1988
Cours algorithme Ccile Balkanski, Nelly Bensimon, Grard Ligozat
IUT Orsay
MAP - UNS 2
1
12/03/2013
OBJECTIF DU COURS API
Notions de base en algorithmique
Types de donnes et lien avec la machine
Notion de sous-programmes et lien avec la compilation
Qualit
nommage des variables, assertions, documentation ,
pr et post conditions
Structures algorithmiques fondamentales: .
Implantation des algorithmes dans un langage de
programmation.
Introduction au test unitaire, bote noire,
Algorithmes fondamentaux de recherche recherche dun
lment, parcours, tri,
Avoir une premire notion des performances des algorithmes
utiliss MAP - UNS 3
NOTION DE BASE EN
ALGORITHMIQUE
4
MAP - UNS
2
12/03/2013
CONCEPTS IMPORTANTS EN
INFORMATIQUE
Algorithme : mot driv du nom du mathmaticien
al_Khwarizmi qui a vcu au 9me sicle, tait
membre dun acadmie des sciences Bagdad .
Un algorithme prend des donnes en entre,
exprime un traitement particulier et fournit des
donnes en sortie.
Programme : srie dinstructions pouvant sexcuter
en squence, ou en parallle (paralllisme
matriel) qui ralise (implmente) un algorithme
MAP - UNS 5
POURQUOI UN COURS D "ALGO" ?
Pour obtenir de la machine quelle effectue
un travail notre place
Problme: expliquer la machine comment
elle doit s'y prendre
Besoins :
savoir expliciter son raisonnement
savoir formaliser son raisonnement
concevoir (et crire) des algorithmes:
squence dinstructions qui dcrit comment rsoudre un
problme particulier
MAP - UNS 6
3
12/03/2013
ALGORITHME
Savoir expliquer comment faire un travail sans la
moindre ambigut
langage simple : des instructions (pas lmentaires)
suite finie d'actions entreprendre en respectant une
chronologie impose
Lcriture algorithmique : un travail de programmation
vise universelle
un algorithme ne dpend pas du langage dans lequel il est
implant,
ni de la machine qui excutera le programme correspondant.
MAP - UNS 7
EXEMPLE DALGORITHMES
Recette de cuisine
Notice de montage de meuble
en kit
Mathmatiques : problme 3n+1: lmentaire mais
redoutable
si n est pair, on le divise par 2 ;
si n est impair, on le multiplie par 3 et on ajoute 1.
Est-il vrai que lon finira tt ou tard par tomber sur 1 ?
MAP - UNS 8
4
12/03/2013
LES PROBLMES FONDAMENTAUX
EN ALGORITHMIQUE
Complexit
En combien de temps un algorithme va -t-il atteindre le
rsultat escompt?
De quel espace a-t-il besoin?
Calculabilit:
Existe-t-il des tches pour lesquelles il n'existe aucun
algorithme ?
Etant donne une tche, peut-on dire s'il existe un
algorithme qui la rsolve ?
Correction
Peut-on tre sr qu'un algorithme rponde au problme
pour lequel il a t conu ?
MAP - UNS 9
EXEMPLE DE LANGAGE ALGORITHMIQUE
MAP - UNS 10
5
12/03/2013
ETAPES DUN ALGORITHME
Prparation du traitement
donnes ncessaires la rsolution du problme
Traitement
rsolution pas pas,
aprs dcomposition en sous-problmes si
ncessaire
Edition des rsultats
impression lcran,
dans un fichier, etc.
MAP - UNS 11
LANGAGE ALGORITHMIQUE
Algorithme NomAlgorithme Algorithme Bonjour
{ ceci est un commentaire} {il dit juste bonjour mais en anglais !
Dbut Dbut
... Actions afficher('Hello world !!!')
Fin ALaLigne
Fin
Il faut avoir une criture rigoureuse
Il faut avoir une criture soigne : respecter lindentation
Il est ncessaire de commenter les algorithmes
Il existe plusieurs solutions algorithmiques un problme pos
Il faut rechercher lefficacit de ce que lon crit
MAP - UNS 12
6
12/03/2013
DCLARATION DES DONNES
Variable <nom de donne>: type
Instruction permettant de rserver de lespace
mmoire pour stocker des donnes
Dpendant du type des donnes : entiers, rels,
caractres, etc.)
Exemples :
Variables val, unNombre: entiers
nom, prnom : chanes de caractres
MAP - UNS 13
DCLARATION DES DONNES
Constante <nom de donne>: type valeur ou
expression
Instruction permettant de rserver de lespace
mmoire pour stocker une constante dont la valeur
ne varie pas.
Exemples :
Constante MAX : entier 10
DEUXFOISMAX : entier MAX x 2
MAP - UNS 14
7
12/03/2013
LECTURE CRITURE DE DONNES
Saisir<nom de donne, >
Afficher<nom de donne, >
Fonction : Instructions permettant
de placer en mmoire les informations fournies par l'utilisateur.
De visualiser des donnes places en mmoire
Exemples:
Saisir(unNombre)
Afficher ( le nom est , nom, et le prnom est ,
prnom )
Saisir(val)
MAP - UNS 15
PHASE DANALYSE
Consiste extraire de lnonc du
problme des lments de modlisation
Technique : Distinguer en soulignant de
diffrentes couleurs quelles sont
Quel est le but du programme (traitement
raliser)
Donnes en entre du problme :
O vont se situer les rsultats en sortie
MAP - UNS 16
8
12/03/2013
EXEMPLE DNONC DUN PROBLME
On souhaite calculer et afficher , partir dun prix
hors taxe saisi, la TVA ainsi que le prix TTC
Le montant TTC dpend de :
Du prix HT
Du taux de TVA de 20,6
MAP - UNS 17
EXEMPLE DNONC DUN PROBLME
On souhaite calculer et afficher , partir dun prix
hors taxe saisi, la TVA ainsi que le prix TTC
Le montant TTC dpend de :
Du prix HT
Du taux de TVA de 20,6
Traitement raliser
MAP - UNS 18
9
12/03/2013
EXEMPLE DNONC DUN PROBLME
On souhaite calculer et afficher , partir dun prix
hors taxe saisi, la TVA ainsi que le prix TTC
Le montant TTC dpend de :
Du prix HT
Du taux de TVA de 20,6
Donnes en entre
MAP - UNS 19
EXEMPLE DNONC DUN PROBLME
On souhaite calculer et afficher , partir dun prix
hors taxe saisi, la TVA ainsi que le prix TTC
Le montant TTC dpend de :
Du prix HT
Du taux de TVA de 20,6
Donnes en sortie
MAP - UNS 20
10
12/03/2013
ALGORITHME TVA
Algorithme CalculTVA
{Saisit un prix HT et affiche le prix TTC correspondant}
Constantes (TVA : rel) 20.6
(Titre : chane) "Rsultat"
Variables prixHT : rel
Variable prixTTC, montantTVA : rels {dclarations}
Dbut {prparation du traitement}
afficher("Donnez-moi le prix hors taxe :")
saisir(prixHT)
prixTTC prixHT* (1+TVA/100) {calcul du prix TTC} Code peu efficace
montantTVA prixTTC- prixHT
afficher(Titre) {prsentation du rsultat}
afficher(prixHT, euros H.T. + TVA ",TVA, devient ,prixTTC,
eurosT.T.C.") MAP - UNS 21
Fin
INSTRUCTIONS SQUENTIELLES
RSULTAT DUN ALGORITHME
Constante (SEUIL : rel) 13.25
Variables valA, valB: rels
compteur : entier
mot , tom : chanes
valA0.56
valBvalA
valAvalA(10.5 + SEUIL)
compteur 1
compteur compteur + 10
mot " Bonjour "
tom "Au revoir ! "
Quelles sont les diffrentes valeurs des variables ?
MAP - UNS 22
11
12/03/2013
SIMULATION DUN ALGORITHME
Algorithme CaDoitEchanger?
{Cet algorithme .........................................}
Variables valA, valB: rels {dclarations}
Dbut {prparation du traitement}
Afficher ("Donnez-moi deux valeurs :")
Saisir (valA, valB)
Afficher ("Vous m'avez donn ", valA, " et ", valB)
{traitement mystre}
valAvalB
valBvalA {prsentation du rsultat}
Afficher("Maintenant , mes donnes sont : ", valA, " et ", valB)
Fin
Que fait cet algorithme ? Pas ce qui est prvu !
MAP - UNS 23
CE QUIL MANQUE
Dclarer une variable supplmentaire
Variables valA, valB, valTemp: entiers
Utiliser cette variable pour stocker provisoirement
une des valeurs
Saisir(valA, valB)
valTempvalA
valAvalB
valBvalTemp
MAP - UNS 24
12
12/03/2013
STRUCTURE ALTERNATIVE
SI ALORS SINON FSI (1)
Exemple :
Algorithme SimpleOuDouble
{Cet algorithme saisit une valeur entire et affiche son double si
cette donne est infrieure un seuil donn.)
constante (SEUIL : entier) 10
Variable val : entier
dbut
Afficher("Donnez-moi un entier : ") { saisie de la valeur entire}
Saisir(val)
si val < SEUIL { comparaison avec le seuil}
alors Afficher ("Voici son double :" , val 2)
sinon Afficher ("Voici la valeur inchange :" , val)
fsi
fin
MAP - UNS 25
STRUCTURE ALTERNATIVE
SI ALORS SINON FSI (2)
Ou instruction conditionnelle
si <expression logique>
alors instructions
[sinon instructions]
fsi
Si lexpression logique (la condition) prend la valeur
vrai, le premier bloc dinstructions est excut;
si elle prend la valeur faux, le second bloc est
excut (sil est prsent, sinon, rien).
MAP - UNS 26
13
12/03/2013
STRUCTURE ALTERNATIVE
SI ALORS SINON FSI (3)
Autre criture de lexemple :
Algorithme SimpleOuDouble
{Cet algorithme saisit une valeur entire et affiche son double si cette
donne est infrieure un seuil donn.)
constante (SEUIL : entier) 10
Variable val : entier
dbut
Afficher("Donnez-moi un entier : ") { saisie de la valeur entire}
Saisir(val)
si val < SEUIL { comparaison avec le seuil}
alors val val 2
Fsi
Afficher ("Voici la valeur val :" , val)
MAP - UNS 27
fin
STRUCTURES ALTERNATIVES
IMBRIQUES
Problme: afficher :
"Reu avec mention Assez Bien " si une note est suprieure ou
gale 12,
" Reu mention Passable" si elle est suprieure 10 et
infrieure 12, et
"Insuffisant" dans tous les autres cas.
si note 12
alors afficher( "Reu avec mention AB" )
sinon si note 10
alors afficher( Reu mention Passable" )
sinon afficher("Insuffisant" )
fsi
fsi
MAP - UNS 28
14
12/03/2013
SELECTION CHOIX MULTIPLES
SELON (1)
selon <identificateur>
(liste de) valeur(s) : instructions
(liste de) valeur(s) : instructions
[autres: instructions]
Sil y a plus de deux choix possibles, linstruction
selon permet une facilit dcriture
MAP - UNS 29
SLECTION CHOIX MULTIPLES
SELON (2)
selon abrviation
"M" : afficher( " Monsieur " )
"Mme" :afficher( " Madame " )
"Mlle" : afficher( " Mademoiselle " )
autres :afficher( " Monsieur, Madame " )
quivalent avec instruction Conditionnelle
si abrviation = "M "
alors afficher( "Monsieur" )
sinon si abrviation = Mlle
alors afficher("Mademoiselle")
sinon si abrviation = "Mme"
alors afficher( "Madame" )
sinon afficher( "Monsieur,Madame " )
fsi
fsi MAP - UNS 30
fsi
15
12/03/2013
SLECTION CHOIX MULTIPLES
EXEMPLE (3) AVEC INVERSION DES TESTS
selon abrviation
"M" : afficher( " Monsieur " )
"Mme" :afficher( " Madame " )
"Mlle" : afficher( " Mademoiselle " )
autres :afficher( " Monsieur, Madame " )
quivalent avec instruction Conditionnelle
si abrviation = "Mme "
alors afficher( Madame" )
sinon si abrviation = Mlle
alors afficher("Mademoiselle")
sinon si abrviation = "M"
alors afficher( "Monsieur" )
sinon afficher( "Monsieur,Madame " )
fsi
fsi MAP - UNS 31
fsi
SLECTION CHOIX MULTIPLES
EXEMPLE (4) AVEC SI ALORS FSI SQUENTIELS
selon abrviation
"M" : afficher( " Monsieur " )
"Mme" :afficher( " Madame " )
"Mlle" : afficher( " Mademoiselle " )
autres :afficher( " Monsieur, Madame " )
quivalent avec instruction Conditionnelle
si abrviation = "Mme "
alors afficher( Madame" )
fsi
si abrviation = Mlle
alors afficher("Mademoiselle")
fsi
si abrviation = "M"
alors afficher( "Monsieur" )
sinon afficher( "Monsieur,Madame " )
fsi
MAP - UNS 32
16
12/03/2013
TO DO
Calculez le nombre dinstructions ncessaires pour
valuer lexcution dans le cas de 24 tudiants et 2
tudiantes clibataires.
Traiter les 3 cas de exemple 2, 3 et 4.
MAP - UNS 33
RPTITION DUN TRAITEMENT
BOUCLE POUR
Exemple
Algorithme FaitLeTotal
{Cet algorithme fait la somme des nbVal donnes qu'il saisit}
variables nbVal, cpt : entiers
valeur, totalValeurs: rels
dbut
{initialisation du traitement}
afficher("Combien de valeurs voulez-vous saisir ?")
saisir(nbVal)
{initialisation du total 0 avant cumul}
totalValeurs0
{traitement qui se rpte nbVal fois}
pour cpt 1 nbVal faire
afficher("Donnez une valeur :")
saisir(valeur)
totalValeurstotalValeurs+ valeur {cumul}
fpour
{dition des rsultats}
afficher("Le total des ", nbVal, "valeurs est " , totalValeurs)
MAP - UNS 34
fin
17
12/03/2013
BOUCLE POUR
Valeur Valeur
initiale finale
pour <var> valInit valfin [par <pas>] faire
traitement {suite dinstructions}
fpour
Valeur ajouter
<var> chaque
passage dans la
boucle
Fonction: rpter une suite dinstructions un certain
nombre de fois
Pour utilise quand le nombre ditration est connu
MAP - UNS 35
SMANTIQUE BOUCLE POUR
linstruction pour:
initialise une variable de boucle (le compteur)
incrmente cette variable de la valeur de pas
vrifie que cette variable ne dpasse pas la borne suprieure
Attention :
-le traitement ne doit pas modifier la variable de boucle
Pour cpt 1 MAX faire
si () alors INTERDIT !
cpt MAX
fpour
MAP - UNS 36
18
12/03/2013
RPTITION DUN TRAITEMENT
NOMBRE ITRATIONS INCONNU
TANT QUE FAIRE
Exemple
Algorithme FaitLeTotal
{Cet algorithme fait la somme des nbVal donnes qu'il saisit, arrt
la lecture de -1 }
constante (STOP : entier) -1
variables val, totalValeurs: entiers
dbut
totalValeurs0
afficher("Donnez une valeur,", STOP, " pour finir.") {amorage}
saisir(val)
tant que val STOP faire
totalValeurstotalValeurs+ val {traitement}
afficher("Donnez une autre valeur,", STOP, " pour finir.")
saisir(val) {relance}
ftq
afficher("La somme des valeurs saisies est", totalValeurs)
fin MAP - UNS 37
BOUCLE TANT QUE FAIRE
initialisation de la (des)
variable(s) de condition
amorage
tant que <expression logique (vraie)> faire
traitement suite dinstructions
relance excuter si condition
ftq vraie
r-affectation de la
(des) variable(s) de
condition
Fonction: rpter une suite dinstructions un certain
nombre de fois
MAP - UNS 38
19
12/03/2013
BOUCLE TANT QUE FAIRE
Structure itrative "universelle"
n'importe quel contrle d'itration peut se traduire par le
"tant que "
Structure itrative irremplaable ds que la
condition d'itration devient complexe
MAP - UNS 39
BOUCLE TANT QUE FAIRE
Exemple:
saisir des valeurs, les traiter, et sarrter la saisie de
la valeur darrt 1 ou aprs avoir saisi 5 donnes.
Constantes (STOP : entier) -1
(MAX : entier) 5
Variables nbVal, val : entiers
Dbut
nbVal0 {compte les saisies traites}
saisir(val) {saisie de la 1re donne}
tant que val STOP et nbVal< MAX faire
nbValnbVal+ 1{traitement de la valeur saisie}
saisir(val) {relance}
Ftq
afficher(val, nbVal) {valeurs en sortie de boucle}
Remarque : La valeur darrt nest jamais traite (et donc, jamais
comptabilise)
MAP - UNS 40
20
12/03/2013
BOUCLE TANT QUE FAIRE
Interprter l'arrt des itrations
nbVal0 {compte les saisies traites}
saisir(val) {saisie de la 1re donne}
tant que val STOP et nbVal< MAX faire
nbValnbVal+ 1{traitement de la valeur saisie}
saisir(val) {relance}
Ftq
si val = STOP
alors {la dernire valeur teste tait la valeur darrt}
afficher(Sortie de boucle car saisie de la valeur darrt )
{toutes les donnes significatives ont t traites.}
sinon {il y avait plus de 5 valeurs tester}
afficher(Sortie de boucle car nombre maximum de valeurs traiter
atteint ) { des donnes significatives nont pas pu t traites.}
MAP - UNS 41
fsi
COMPARAISON BOUCLES
POUR ET TANT QUE (1)
pour cpt 1 nbVal faire
afficher("Donnez une valeur :")
saisir(valeur)
totalValeurstotalValeurs+ valeur {cumul}
fpour
Est quivalent
cpt 0
tant que cpt <nbVal faire
afficher("Donnez une valeur :")
saisir(valeur)
totalValeurstotalValeurs+ valeur {cumul}
cpt cpt + 1 {compte le nombre de valeurs traites}
ftq
MAP - UNS 42
21
12/03/2013
COMPARAISON BOUCLES
POUR ET TANT QUE (2)
Implicitement, linstruction pour:
initialise un compteur
incrmente le compteur chaque pas
vrifie que le compteur ne dpasse pas la borne
suprieure
Explicitement, linstruction tant que doit
initialiser un compteur {amorage}
incrmenter le compteur chaque pas {relance}
vrifier que le compteur ne dpasse pas la borne
suprieure {test de boucle}
MAP - UNS 43
QUAND CHOISIR
POUR OU TANT QUE ?
Nombre ditration connu lavance : POUR
Parcours de tableaux
Test sur un nombre donn de valeurs
Boucle sarrte sur vnement particulier : TANT
QUE
Itration avec arrt dcid par saisie utilisateur
MAP - UNS 44
22
12/03/2013
MAIS ON NA PAS FINI DITRER !
Boucle rpter tant que : exemple
Algorithme Essai
{Cet algorithme a besoin dune valeur positive paire}
Variables valeur : entier
Dbut
Rpter
afficher("Donnez une valeur positive non nulle : ")
saisir(valeur)
tant que valeur 0
afficher("La valeur positive non nulle que vous avez saisie est ")
afficher( valeur ){traitement de la valeur saisie}
fin
MAP - UNS 45
BOUCLE RPTER TANT QUE
Rpter
(r)affectation de la (des) variable(s) de condition
traitement
Tant que <expression logique (vraie)>
Fonction: excuter une suite dinstructions au moins une fois
et la rpter tant quune condition est remplie
Remarque: le traitement dans lexemple prcdent se limite
la r-affectation de la variable de condition (saisir(valeur))
MAP - UNS 46
23
12/03/2013
COMPARAISON
RPTER ET TANT QUE
Rpter
afficher("Donnez une valeur positive paire :")
saisir(valeur)
tant que(valeur < 0 ou(valeur % 2) 0)
quivaut
afficher("Donnez une valeur positive paire :") saisir(valeur)
tant que(valeur < 0 ou(valeur % 2) 0) faire
afficher("Donnez une valeur positive paire:")
saisir(valeur)
ftq
MAP - UNS 47
COMPARAISON
RPTER ET TANT QUE
boucle tant que
condition vrifie avant chaque excution du traitement
le traitement peut donc ne pas tre excut
de plus : la condition porte surtout sur la saisie de nouvelles
variables (relance)
boucle rpter tant que
condition vrifie aprs chaque excution du traitement
=>le traitement est excut au moins une fois
de plus: la condition porte surtout sur le rsultat du traitement
Remarque: la boucle rpter est typique pour les saisies avec
vrification
MAP - UNS 48
24
12/03/2013
DE LNONC LA BOUCLE
saisir des donnes et s'arrter ds que leur somme
dpasse 500
somme 0
rpter
saisir(val)
somme somme + val
tant que somme 500
saisir(val)
somme val
tant que somme 500 faire
saisir(val)
somme somme + val
ftq
MAP - UNS 49
DE LNONC LA BOUCLE
saisir des donnes et s'arrter ds que leur somme
dpasse 500
somme 0
rpter
saisir(val)
somme somme + val
tant que somme 500
MAP - UNS 50
25
