Algorithmique et Programmation

ETE -1-

2016/2017

2016 / 2017 DUT - GUE - ETE 1 1

 Tâches de l’ordinateur
• Diverses application:
– Edition de feuilles de page
– Gestion de stock
– Jeux
– Traitement de texte
– Montage vidéo
–…

2016 / 2017 DUT - GUE - ETE 1 2

 Tâches de l’ordinateur
• Programme ?
– A chaque tâche correspond un programme
• L’ordinateur est capable de mettre en mémoire un
programme puis l’exécuter
• Un programme est constitué d’une suite d’instructions.
• Une instruction spécifie
– Les opérations à exécuter
– La façon dont elles s’enchaînent
• Puissance = vitesse d’exécution
• Souplesse = programme
2016 / 2017 DUT - GUE - ETE 1 3
Données du programme et résultats
• Exemple: on dispose d’un programme qui
calcule la moyenne des notes.
– Celui-ci a besoin qu’on lui fournisse les notes
(données)
– Pour qu’il nous retourne la moyenne (résultat)
• Autre exemple: établissement d’un bulletin
de paye:
– Données: nombre d’heures, grade, …
– Résultat: salaire net, salaire brut, retenues, …

2016 / 2017 DUT - GUE - ETE 1 4

 Communication ou archivage
• D’où viennent les données ? Où vont les
résultats?

Données
Programme
Archive

Résultat

2016 / 2017 DUT - GUE - ETE 1 5

 Notion de codage
• Toutes les informations traitées par l’ordinateur sont en
binaire
– Quand on tape sur une touche du clavier, l’ordinateur la
transforme en binaire
– Quand l’ordinateur affiche sur l’écran un résultat, il fait
l’opération inverse
• Nous aussi on utilise le codage
– 13, treize, XIII
• Nous avons interprété XIII par le nombre 13. Comment
on a pu dire que ce ne sont pas les lettres X et I ?
• Pour interpréter les informations, l’ordinateur a en plus
besoin du type de l’info

2016 / 2017 DUT - GUE - ETE 1 6

 Fonctionnement de l’ordinateur
• Il traite l’informations grâce à un programme
qu’il mémorise. Il communique et archive des
informations
• Mémoire centrale: Programme+infos
temporaires
• Unité centrale: chargée de prélever une à une
les instructions du programme
– Deux types d’instructions
• Opérations internes (addition, soustraction, …)
• Opérations de communication (affichage, archivage, …)
• Périphériques: d’entrée, de sortie,
d’entrée/sortie
2016 / 2017 DUT - GUE - ETE 1 7
 Fonctionnement de l’ordinateur

Périphérique UC MC

1
Programme
+
2 Infos
temporaires
3

1. Prélèvement d’une instruction

2. Exécution de l’instruction avec possibilité d’échange avec la MC
3. Exécution d’une instruction d’échange avec un périphérique
2016 / 2017 DUT - GUE - ETE 1 8
 Organisation de la MC
• C’est une grille où chaque case peut
prendre la valeur 0 ou 1 (bit)
• On ne manipule pas de cases mais des
ensembles de case qu’on appelle mots
• Généralement un mot correspond à un
octet (8 bits)
• Chaque mot a une adresse.

2016 / 2017 DUT - GUE - ETE 1 9

 Unité centrale
• Sait exécuter des opérations très simples:
– Addition, soustraction, comparaison, …
• Chaque instruction du programme doit préciser
– la nature de l’opération (son code binaire)
– la ou les adresses sur lesquelles porte l’opération
• Les instructions sont exécutées l’une à la suite
de l’autre
– Sauf si on rencontre une opération de branchement

2016 / 2017 DUT - GUE - ETE 1 10

 Programmation
• L’ordinateur ne comprend que le binaire,
est-ce pour autant qu’on doive écrire des
programmes en binaire ?
• Il existe des langages de programmation
dits « évolués » (proches du langage
courant
• Pour chaque langage, il existe un
programme « qui le traduit » en binaire

2016 / 2017 DUT - GUE - ETE 1 11

 Traduction des programmes

Programme Programme
source Traducteur exécutable

Il existe essentiellement deux modes de traduction

•Compilation: la traduction se fait une fois pour toute
•Interprétation: a chaque fois qu’on veut exécuter le programme,
l’interprète traduit une instruction à la fois. Une fois que celle-ci est
exécutée, il passe à l’instruction suivante.
2016 / 2017 DUT - GUE - ETE 1 12
 Programmation

• A priori, écriture de programmes dans un

langage de programmation (C, Java, Pascal,
Visual Basic, Fortran, Python, Perl, …)
• Or il y a plusieurs langages, est-ce que ça veut
dire qu’il existe plusieurs sortes de
programmation?
• En fait, la plupart des langages utilisent les
mêmes concepts  L’algorithmique

2016 / 2017 DUT - GUE - ETE 1 13

 Programmation
• 2 étapes:
1. Analyse du problème et recherche du
moyen d’aboutir au résultat à partir des
données dont on dispose  écriture d’un
algorithme
2. Traduction de l’algorithme dans un langage
de programmation

2016 / 2017 DUT - GUE - ETE 1 14

 Algorithme
• Une description des différentes étapes permettant
de résoudre un problème quelconque
• Exemple: résolution d’une équation du 2nd degré
ax 2  bx  c  0
1. Connaître les valeurs de a, b et c
2. Calculer le discriminant   b  4ac
3. Si D < 0 alors pas de solution
4. Si D = 0 alors solution double = -b/2a
5. Si D > 0 alors deux solutions

2016 / 2017 DUT - GUE - ETE 1 15

 Notion de variable
• Les variables servent à « nommer » des
emplacements ou adresses de la mémoire
• Permettent de manipuler des valeurs sans
connaître leurs emplacements exactes
001 A
010 B
011 Montant

Coté machine Coté programmeur

2016 / 2017 MC
DUT - GUE - ETE 1 16
 Type d’une variable
• Le type d’une variable permet
– De savoir quel est l’espace mémoire occupé par une
variable
– Quelles sont les opérations autorisées sur la variable
• Déclaration d’une variable dans un algorithme
– Variable <nom_variable>: type
– Exemple:
• Variable Note: Réel
• Variable coefficient: entier

2016 / 2017 DUT - GUE - ETE 1 17

 Instruction d’affectation
• Rôle: mettre une valeur dans un emplacement
mémoire désigné par son nom
• Syntaxe:
1. nom_variable  valeur
Ex: Note  15
2. nom_variable1  nom_variable2
Ex: Note1  Note2
3. nom_varible  expression
Ex: Moyenne  (Note1*2 +Note1)/3

2016 / 2017 DUT - GUE - ETE 1 18

 Instruction d’affectation
• Si la variable Note est égale = 10, à quoi sera-t-elle
égale après l’exécution de
Note  Note + 5
• A quoi seront égales les variables A et B après
l’exécution de la suite d’instructions suivante ?
1. A 5
2. B  A+4
3. A  A+1
4. B  A-4

2016 / 2017 DUT - GUE - ETE 1 19

 Trace d’un algorithme
Instruction valeur de A Valeur de B
0: ? ?
1: A  5 5 ?
2: B  A+4 5 9
3: A  A+1 6 9
4: B  A-4 6 5

A la fin, A=6 et B=5

2016 / 2017 DUT - GUE - ETE 1 20

 Affection : exercices
Donnez les valeurs des variables A et B après exécution
des instructions suivantes ?
Variables A, B : Entier
Début
A←6
B←2
A←B
B←A
Fin
Les deux dernières instructions permettent-elles
d’échanger
2016 / 2017 les valeurs DUT
de -AGUE
et- ETE
B ?1 21
 Affectation : l’échange

2016 / 2017 DUT - GUE - ETE 1 22

 Écrire un algorithme permettant d’échanger les valeurs de
deux variables A et B ?

Réponse :

On utilise une variable auxiliaire C et on écrit les

instructions suivantes :
C A; A B; B C;

2016 / 2017 DUT - GUE - ETE 1 23

 Expressions et opérateurs
• Une expression peut être une valeur, une variable ou une opération
constituée de variables reliées par des opérateurs
exemples: 1, b, a*2, a+ 3*b-c, …

• L'évaluation de l'expression fournit une valeur unique qui est le résultat

de l'opération

• Les opérateurs dépendent du type de l'opération, ils peuvent être :

• des opérateurs arithmétiques: +, -, *, /, %

(modulo),^(puissance)
• des opérateurs logiques: NON(!), OU(| |), ET (&&)
• des opérateurs relationnels: =, <, >, <=, >=
• des opérateurs sur les chaînes: & (concaténation)

• Une expression est évaluée de gauche à droite mais en tenant compte

des priorités des opérateurs.
2016 / 2017 DUT - GUE - ETE 1 24
 Expression : remarques

• On ne peut pas additionner un entier et un caractère

• Toutefois dans certains langages on peut utiliser un opérateur avec deux

opérandes de types différents, c’est par exemple le cas avec les types
arithmétiques (4 + 5.5)

• La signification d’un opérateur peut changer en fonction du type des

opérandes
• l’opérateur + avec des entiers effectue l’addition, 3+6 vaut 9
• avec des chaînes de caractères il effectue la concaténation "bonjour"
+ " tout le monde" vaut "bonjour tout le monde"

2016 / 2017 DUT - GUE - ETE 1 25

 Les opérateurs boolean
• Associativité des opérateurs et et ou
a et (b et c) = (a et b) et c

• Commutativité des opérateurs et et ou

a et b = b et a
a ou b = b ou a

• Distributivité des opérateurs 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)

• Involution (homographie réciproque) : non non a = a

• Loi de Morgan : non (a ou b) = non a et non b

non (a et b) = non a ou non b

• Exemple : soient a, b, c et d quatre entiers quelconques :

(a<b)| |((a>=b)&&(c==d)) (a<b)| |(c==d)
2016 / 2017 DUT - GUEest
car (a<b)| |(!(a<b)) - ETE 1
toujours vraie 26
 Table de vérité

2016 / 2017 DUT - GUE - ETE 1 27

 Instruction d’écriture
• Rôle: permet de restituer une valeur. Généralement, ça
consiste à afficher sur l’écran
• Syntaxe:
1. Ecrire (valeur)
Ex: Ecrire (4)
2. Ecrire (variable)
Ex: Ecrire(Note)
3. Ecrire (expression)
Ex: Ecrire (‘La moyenne=‘, (Note1+Note2)/2)

• Remarque: Ecrire(Note) n’est pas la même chose que

Ecrire(‘Note’)

2016 / 2017 DUT - GUE - ETE 1 28

 Instruction de lecture
• Rôle: Permet d’introduire une donnée au
programme. Généralement, on tape la valeur
• Syntaxe: Lire(variable)
Ex: Lire(Note)
• Effet:
– à la rencontre de cette instruction, l’ordinateur arrête
l’exécution du programme et attend qu’on tape une
valeur.
– On termine la saisie en appuyant sur la touche
Entrée.
– La valeur qu’on tape est affectée à la variable lue
• Remarque: Lire(valeur) et Lire(expression) n’ont
pas de sens
2016 / 2017 DUT - GUE - ETE 1 29
 Algorithme
• Syntaxe:
Algorithme nom_algo
Déclaration des variables
Début
la suite des instructions
Fin

2016 / 2017 DUT - GUE - ETE 1 30

 Algorithme: Exemple
Algorithme somme 2 variable entières sont
déclarées
variable X, Y: Entier
Début
4
X4 instructions
Ecrire(‘Donner la valeur de Y’) forment le
corps de
l’algorithme
Lire(Y)
Ecrire(X+Y)
Fin
2016 / 2017 DUT - GUE - ETE 1 31
 Exercices
• Écrire un algorithme qui demande un
nombre entier à l'utilisateur, puis qui
calcule et affiche le carré de ce nombre;

• Écrire un algorithme qui permet d’effectuer

la saisie d’un nom, d’un prénom et affiche
ensuite le nom complet

2016 / 2017 DUT - GUE - ETE 1 32

 Instruction de choix simple
• Rôle: Permet d’exécuter des instructions
quand une condition est vérifiée
• Syntaxe:
Si condition Alors
DébutSi
{ Instructions }
FinSi

2016 / 2017 DUT - GUE - ETE 1 33

 Instruction de choix simple
• Ex: on veut afficher un message quand X
est positive
Si X > 0 Alors
DébutSi
Ecrire(‘X est positive’)
FinSi

2016 / 2017 DUT - GUE - ETE 1 34

 Instruction de choix simple
• La condition peut être composée en
utilisant des ‘ET’ et des ‘OU’
Exemple:
Si ( ((Y=3) OU (Z<4)) ET (X>0)) Alors
DébutSi
{Instructions}
FinSi

2016 / 2017 DUT - GUE - ETE 1 35

Instruction de choix avec alternative
• Rôle: permet de spécifier ce qu’il faut faire dans le cas
où la condition n’est pas vérifiée
• Syntaxe:
Si condition Alors
DébutSi
{ Instructions }
FinSi
Sinon
DébutSinon
{ Instructions’ }
FinSinon

2016 / 2017 DUT - GUE - ETE 1 36

 Instruction de choix avec
alternative
• Exemple :
Si X > 0 Alors
DébutSi
Ecrire(‘X est positive’)
Finsi
Sinon
DébutSinon
Ecrire(‘X n’est pas positive)
FinSinon

2016 / 2017 DUT - GUE - ETE 1 37

 Instruction de choix
• On peut imbriquer les conditions
• Exemple
Si X > 0 alors
DébutSi
Ecrire(‘ X supérieur à 0’)
Finsi
Sinon
DébutSinon
Si X=0 alors
DébutSi
Ecrire(‘X égal à 0’)
FinSi
Sinon
DébutSinon
Ecrire(‘X inférieur à 0’)
FinSinon
FinSinon
2016 / 2017 DUT - GUE - ETE 1 38
 Algorithme 1
• Écrire un algorithme qui permet de
– Lire une note puis
– affiche un message. Ce dernier sera
• « reçu(e) » si la note lue est supérieure ou égale à
10
• « recalé(e) » si la note est inférieure à 10

2016 / 2017 DUT - GUE - ETE 1 39

 Algorithme 1
• De quelles variables a-t-on besoin ?
– On n’a besoin que d’une seule variable.
Appelons la X
• Quelle est le type de cette variable ?
– A priori, une note est un réel

2016 / 2017 DUT - GUE - ETE 1 40

 Algorithme 1
• Description de l’algorithme :
– On lit d’abord la variable X
– On teste ensuite sa valeur
• Si elle est c alors on affiche « reçu(e) »
• Sinon, on affiche « recalé(e) »

2016 / 2017 DUT - GUE - ETE 1 41

 Algorithme 1
Algorithme Exemple1
Variable X: réel
Début
Lire(X)
Si X  10 alors
Ecrire(« reçu(e) »)
Finsi
Sinon
Ecrire(« recalé(e) »)
FinSinon
Fin
2016 / 2017 DUT - GUE - ETE 1 42
 Algorithme 1
Algorithme Exemple1
Variable X: réel
Début
Ecrire (« donner une note »)
Lire(X)
Si X  10 alors
Ecrire(« reçu(e) »)
Finsi
Sinon
Ecrire(« recalé(e) »)
FinSinon
Fin
2016 / 2017 DUT - GUE - ETE 1 43
 Structure Tant que
• En algorithmique, la boucle Tant que est utilisée lorsque
des instructions se répètent sans connaître le nombre de
répétitions mais en connaissant une condition d’arrêt.

Tant que (Condition)

suite d’instructions …
….
FinTantQue

2016 / 2017 DUT - GUE - ETE 1 44

 Algorithme 1
Algorithme Exemple1
…
Ecrire (« donner une note »)
Lire(X)
Tant que (X<0)
Ecrire(X, « n’est pas une note valable »)
Ecrire(« taper une autre valeur »)
Lire(X)
FinTantQue
Si X  10 alors
…
Fin

2016 / 2017 DUT - GUE - ETE 1 45

 Algorithme 1
Algorithme Exemple1
…
Ecrire (« donner une note »)
Lire(X)
Tant que ((X<0) OU (X > 20))
Ecrire(X, « n’est pas une note valable »)
Ecrire(« taper une autre valeur »)
Lire(X)
FinTantQue
Si X  10 alors
…
Fin

2016 / 2017 DUT - GUE - ETE 1 46

 Algorithme 2
• Écrire un algorithme qui
– lit deux notes puis
– affiche leur moyenne

2016 / 2017 DUT - GUE - ETE 1 47

 Algorithme 2
• De quelles variables a-t-on besoin ?
– Première solution :
• Deux variables pour les deux notes. Appelons les
X et Y
• Une variable pour la moyenne. Appelons la M
• Chacune de ces 3 variables est un réel
– Deuxième solution :
• On peut n’utiliser que deux variables X et Y pour
les deux notes. La moyenne sera calculée lors de
l’affichage

2016 / 2017 DUT - GUE - ETE 1 48

 Algorithme 2
• Description de l’algorithme
– On lit d’abord les deux notes
– On calcule leur moyenne
– On affiche la moyenne

2016 / 2017 DUT - GUE - ETE 1 49

 Algorithme 2

Algorithme Exemple 2
Variable X, Y: réel
Début
Lire(X)
Lire(Y)
Ecrire(« moyenne de », X, « et », Y , « est », (X+Y)/2)
Fin

2016 / 2017 DUT - GUE - ETE 1 50

 Algorithme 3
• Ecrire un algorithme qui
– Lit 5 notes puis
– Affiche leur moyenne

• On peut reprendre le même principe:

– 5 variables pour les notes toutes réelles

2016 / 2017 DUT - GUE - ETE 1 51

 Algorithme 4
• Ecrire un algorithme qui
– Lit 100 notes puis
– Affiche leur moyenne

• On peut aussi s’en sortir en utilisant là

aussi 100 notes mais ça devient lourd

2016 / 2017 DUT - GUE - ETE 1 52

 Algorithme 4
• Idée :
– La moyenne est calculée en faisant la
somme de toutes les notes lues
– Utiliser une boucle Tant que qui nous
permet de
• Lire 100 fois la même variable X
• A chaque fois qu’on lit une nouvelle valeur
de X, on la rajoute à une variable S
– A la fin, il suffit de diviser S par 100 pour
avoir la moyenne

2016 / 2017 DUT - GUE - ETE 1 53

 Algorithme 4
• De quelles variables a-t-on besoin ?
– X va nous permettre de lire les notes
– S va nous permettre de calculer la somme
• Nous avons aussi besoin d’une variable i
qui nous permet de compter le nombre de
fois qu’on lit X
• X et S sont de type réel, alors que i est de
type entier

2016 / 2017 DUT - GUE - ETE 1 54

 Algorithme 4
Algorithme exemple4
Variable X, S : réel
Variable i : entier
Début
i 1 ‘initialisation de i
S0 ‘initialisation de S
Tant que i  100
Lire (X)
SS+X
ii+1
FinTantQue
Ecrire (« la moyenne est », S/100)
Fin
2016 / 2017 DUT - GUE - ETE 1 55
 La structure de répétition Pour
• Permet de répéter l’exécution d’une
suite d’instructions un certain nombre
de fois
• Syntaxe:
Pour variable=val1 à val2
Instructions
FinPour

2016 / 2017 DUT - GUE - ETE 1 56

 La structure de répétition Pour
• Exemple:
Pour i = 1 à 100
Ecrire(« donner une note »)
Lire (X)
FinPour
• La première valeur de i est 1
• A chaque itération, on ajoute 1 à i

2016 / 2017 DUT - GUE - ETE 1 57

 La structure de répétition Pour
Pour i=10 à 8
Ecrire(i)
FinPour
Cette boucle ne sera exécutée aucune
fois car Val1 > Val2
• On peut toujours remplacer une boucle
Pour par une boucle TantQue. L’inverse
n’est pas vrai.

2016 / 2017 DUT - GUE - ETE 1 58

 La structure de répétition Pour
Algorithme exemple4’
Variable X, S : réel
Variable i : entier
Début
i 1 ‘initialisation de i
S0 ‘initialisation de S
Tant que i  100
Pour i = 1 à 100
Lire (X)
SS+X
ii+1
FinTantQue
FinPour
Ecrire (« la moyenne est », S/100)
Fin

2016 / 2017 DUT - GUE - ETE 1 59

 La structure de répétition Pour
• Ecrire un algorithme qui affiche le
produit de tous les nombres compris
entre 1 et 10
• Idée 1:
– Utiliser deux variables entières i et j
– i et j prennent leurs valeurs dans l’intervalle
[1..10]
– A chaque nouvelle valeur, on affiche i*j

2016 / 2017 DUT - GUE - ETE 1 60

 Structure de répétition Pour
Algorithme exemple5
Variable i, j : entier
Début
Pour i = 1 à 10
Pour j = 1 à 10
Ecrire(i, « * », j, « = », i * j)
FinPour i=1, j= 1..10

FinPour i= 2, j=1 .. 10
…
Fin i=10, j=1 .. 10
2016 / 2017 DUT - GUE - ETE 1 61
 Structure de répétition Pour
• Idée 2:
– Utiliser deux variables entières i et j
– i prend ses valeurs dans l’intervalle [1..10]
– j prend ses valeurs dans l’intervalle [i..10]
– Ceci nous permettra d’éviter de calculer
deux fois le même produit

2016 / 2017 DUT - GUE - ETE 1 62

 Structure de répétition Pour
Algorithme exemple5’
Variable i, j : entier
Début
Pour i = 1 à 10
Pour j = i à 10
Ecrire(i, « * », j, « = », i * j)
FinPour i=1, j= 1..10

FinPour i= 2, j=2 .. 10
…
Fin
i=10, j=10 .. 10
2016 / 2017 DUT - GUE - ETE 1 63