Informatique 1

1ère Année GC
Ecole Hassania des Travaux Publics

Karim Guennoun

1
 Plan du cours

 Partie 1: Algorithmique générale

– C’est quoi un algorithme?
– Notions de variables, d’actions…etc
– Structures de contrôle
– Structures de données avancées
– Fonctions et procédures
 Partie 2: Le langage C
– Passer de l’algorithme à la programmation

2
 Partie 1:
Algorithmique

3
 Un algorithme, c’est quoi?
 Origine étymologique:
– Vient du nom du mathématicien Al Khawarizmi latinisé en
« algoritmi »
 Définitions:
– Académie Française: Méthode de calcul qui indique la
démarche à suivre pour résoudre une série de problèmes
équivalents en appliquant dans un ordre précis une suite
finie de règles.
– Wikipedia: Un algorithme est un moyen pour un humain de
présenter la résolution par calcul d’un problème à une autre
personne physique (un autre humain) ou virtuelle (un
4 calculateur)
 Pour faire simple:
 Un algorithme est une suite d’instructions, d’actions permettant de
résoudre un problème donné
– Aller quelque part: le chemin
– Réaliser un plat de cuisine: la recette
– Faire un calcul mathématique: la méthode
 La granularité des instructions correspond au contexte d’utilisation
de l’algorithme
– Le chemin: l’interlocuteur
– La recette : Le cuisiner
– Le calcul: Les bibliothèques et la puissance de l’ordinateur
 Heureusement, les ordinateurs sont à peu près aussi idiots les uns
que les autres: même types d’instructions élémentaires
5 compréhensibles
 Qualités d’un bon concepteur
d’algorithmes

 L’intuition:
– Pas de méthode universelle absolue pour résoudre
un problème
 La rigueur et la logique
– La méthodologie, la capacité à se mettre à la place
de la machine et d’être aussi idiot qu’elle!
 L’expérience
– Renforce les deux premiers points
– Plus on écrit d’algorithmes, plus on est performant à
6 le faire
 Algorithmique Vs programmation
 Un langage de programmation n’est que l’outil de
réalisation de l’algorithme
 L’algorithme permet de concevoir la solution alors
que la programmation permet de la mettre en œuvre
 L’algorithme est généralement à un niveau
d’abstraction plus haut que la programmation
 Il est, cependant, nécessaire de prendre en compte
la nature, la puissance et l’expressivité du langage
de programmation avant de concevoir l’algorithme

7
 Les variables

8
 L’intérêt des variables
 Parfois, il est nécessaire de stocker de l’information
au cours du calcul effectué par un algorithme
– Pour additionner deux valeurs, j’ai besoin de stocker ces
deux valeurs
– Pour additionner trois valeurs, j’ai besoin de stocker, en
plus, le résultat intermédiaire
 Une variable est donc une case où on peut stocker
de l’information repérée par une étiquette permettant
d’écrire dedans et de lire depuis.
 Physiquement, c’est une case de la mémoire vive de
l’ordinateur repérée par une adresse binaire
9
 Cycle de vie d’une variable

 La déclaration

 L’instruction d’affectation

 La lecture/écriture et les opérations

10
 La déclaration d’une
variable

11
 La déclaration

 Avant de pouvoir utiliser une variable, il faut

– La créer
– Lui associer une étiquette
 L’étiquette d’une variable correspond en gros
au nom qu’on lui associe
 Préciser le type d’information qu’on souhaite
lui associer.

12
 Bonnes pratiques pour les
étiquettes
 Pour plus de lisibilité,
– Toujours privilégier les étiquettes qui ont du sens
– Éviter des étiquettes à rallonge
 Le nom doit observer certaines règles
dépendantes du langage de programmation
ciblé. Règles absolues:
– Une suite de lettres et de chiffres
– Pas de signes de ponctuation
– Surtout pas d’espaces
13
 Les types classiques

 Les types numériques

 Les types alphanumériques

 Le type booléen

14
 Les types numériques

 Correspondent à des variables destinées à

recevoir des nombres
 La taille de l’espace réservé pour le stockage
détermine
– Les valeurs maximales et minimales des nombres
pouvant être stockés dans la variable
– La précision des valeurs décimales
– E.g. pour un octet, on pourra coder 28 nombres
c-a-d 256 nombres
15
 Types numériques

 Engros, on retrouve pour la plus part des

langages, les types classiques suivants:
Type Numérique Plage
Byte (octet) 0 à 255
Entier simple -32 768 à 32 767
Entier long -2 147 483 648 à 2 147 483 647
-3,40x1038 à -1,40x10-45 pour les valeurs négatives
Réel simple
1,40x10-45 à 3,40x1038 pour les valeurs positives
1,79x10308 à -4,94x10-324 pour les valeurs négatives
Réel double
4,94x10-324 à 1,79x10308 pour les valeurs positives
16
 Types numériques

 Question:
– Pourquoi, pour éviter tout problème, ne pas tout déclarer
en Réel double?
 Réponse:
– Parce que les ressources d’un programme sont limitées
 Bonne nouvelle:
– en algorithmique, on se contentera de faire le distinguo
entier/réel (existence de la virgule ou non)
– Le raffinement vers les autres sous-types numériques
17 sont laissés à l’étape de programmation
 Pseudo-code

 EnPseudo-code, nous écrivons la déclaration

d’une variable numérique :
– Variable v: Entier
– Variable v1, v2, v3: Réel
– Variable v1: Entier
Variable v2: Réel
Variable v3: Entier

18
 Types alphanumériques

 On dispose, en plus du type numérique, du

type caractères ou chaîne de caractères
– En Anglais, string
 Pour ce type de variables, on peut stocker
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
19 dépend du langage utilisé.
 Types alphanumériques

 En Pseudo-code, la valeur est déclarée entre

guillemets "chaîne de caractères"
 "bonjour"
 "Mesdames, messieurs, bonjour!"
 "1234"
 Déclaration
– Variable v: caractères

20
 Type booléen

 Permet de stocker les valeurs logiques

Vrai/Faux (True/False)
 Peut être remplacé par les valeurs
numériques 0 et 1, mais l’utilisation des
booléens:
– Rend l’algorithme plus lisible
– Est plus économique en terme d’utilisation de la
mémoire, un bit suffit pour le stocker (deux octets
pour un entier)
21
 Les instructions
d’affectation

22
 L’affectation

 Une variable n’est exploitable que si elle est

instanciée.
 L’instruction d’affectation permet d’associer
une valeur à la variable
 Une variable ne peut recevoir que des
valeurs correspondant au type avec lequel
elle a été déclarée
 En pseudo-code, l’instruction d’affectation se
note «  »
23
 Exemples

 Variable ecole1: caractères

ecole1  "EHTP"
 On peut aussi écrire.

Variable ecole2: caractères

ecole2 ecole1
ecole2 "ecole1"
 Mais l’instruction suivante n’est pas
consistante:
24 ecole2 1
 Exemples

 L’instructiond’affectation n’altère que la

variable se situant à gauche
 Variable e1, e2: entier

e1 5
e2 e1 * 2
e1 e1+10
e2e1+e2

25
 Ordre des instructions
 L’ordre des instructions est déterminant:
– Elles s’exécutent séquentiellement dans l’ordre où elles
apparaissent
 Variable e1: entier
e110
e15
Vs
e1 5
e110
 Les deux algorithmes sont pour illustration, si vous écrivez
26 quelque chose de semblable, posez-vous des questions!
 Pause exercices

27
 Exo1

 Quellesseront les valeurs des variables A et

B après exécution des instructions
suivantes ?
– Variables A, B: Entier
Début
A←1
B←A+3
A←3
Fin

28
 Exo2

 Quellesseront les valeurs des variables A, B

et C après exécution des instructions
suivantes ?
– Variables A, B, C : Entier
Début
A←5
B←3
C←A+B
A←2
C←B–A
29 Fin
 Exo3

 Quellesseront les valeurs des variables A et

B après exécution des instructions
suivantes ?
– Variables A, B en Entier
Début
A←5
B←A+4
A←A+1
B←A–4
Fin
30
 Exo4

 Quellesseront les valeurs des variables A, B

et C après exécution des instructions
suivantes ?
– Variables A, B, C en Entier
Début
A←3
B ← 10
C←A+B
B←A+B
A←C
31 Fin
 Exo5
 Quelles seront les valeurs des variables A et B après
exécution des instructions suivantes ?
 Variables A, B en Entier
Début
A←5
B←2
A←B
B←A
Fin
 Les deux dernières instructions permettent-elles d’échanger
les deux valeurs de B et A ?
 Si l’on inverse les deux dernières instructions, cela
32 change-t-il quelque chose ?
 Exo6

 Problème classique
– écrire un algorithme permettant d’échanger les
valeurs de deux variables A et B, et ce quel que
soit leur contenu préalable.

33
 Exo7

 On dispose de trois variables A, B et C.

Ecrivez un algorithme transférant à B la
valeur de A, à C la valeur de B et à A la
valeur de C (toujours quels que soient les
contenus préalables de ces variables).

34
 Expressions et opérateurs

 Dans une instruction d’affectation

– À gauche, une variable
 c’est toujours le cas!, sinon il y a un problème!
– À droite, une expression
 Suitede variables et de constantes reliées par des
opérateurs
 Équivalent à une valeur unique!

– La partie gauche et la partie droite sont

évidemment du « même » type

35
 Opérateurs numériques

 Les plus classiques:

– + : addition
– - : soustraction
– * : multiplication
– / : division
– ^ : puissance
 Priorités
– * et / sont prioritaire par rapport à + et –
– Évaluation de gauche à droite
36 – L’utilisation des parenthèses force les priorités
 Exemples

 3*4/2
 3+2*5
 3+4-2*3
 3+(4-2)*3
 (3+(4-2))*3

37
 Opérateurs alphanumériques

 Opérateurs de concaténation
– En pseudo code: « & » ou « + » ou « ^ »
 Exemples
– Variable v: caractères
v  " Bon" + "jour"

38
 Opérateurs booléens

 Le ET: ˄
 Le OU: v
 La négation: ˥
 Exemples
– Vrai ˄ Faux
– Vrai v Faux
– Faux v ˥ Faux
 Ordre de priorité: ˥ puis ˄ puis v
39
 Les opérateurs de comparaison

 Renvoient un booléen comme résultat

– Égalité: =
– Différents: <>
– strictement inférieur: <
– Inférieur ou égal: <=
– strictement supérieur: >
– Supérieur ou égal:>=

40
 Mathématique Vs Informatique
 Quelques pièges à éviter pour les grands mathématiciens
que vous êtes:
– La notion de variable n’est pas vraiment la même dans les deux
cas:
 x=2*y en mathématique est une équation à résoudre ou une assertion
liant deux variables
 En informatique,
– cette expression n’a de sens que si "y" possède une valeur fixe
– Le rapport entre x et y n’est plus maintenu après l’exécution de cette
affectation
– L’opérateur  n’est pas symétrique:
 x=y et y=x sont deux expressions identiques
 x y et yx ne le sont absolument pas!
41
 Lecture et écriture

42
 Motivation
 Un programme effectue des calculs mais, au
final, il serait intéressant de voir le résultat
quelque part:
– Un programme qui additionne 2 et 3 puis l’affiche à
l’écran est un peu plus intéressant qu’un programme
qui garde le résultat pour lui-même!
 Il
est parfois intéressant de pouvoir lui fournir des
entrées pendant son exécution
– Un programme qui additionne deux valeurs que vous
lui donnez en entrée est un peu plus intéressant qu’un
43 programme qui additionne toujours 2 et 3!
 L’opération d’écriture

 Permetà un programme d’afficher une valeur

par exemple sur l’écran
– En pseudo-code:
 Variable V: caractères
V "bonjour"
Ecrire V
Ecrire " Le monde"
– A la rencontre d’une telle instruction, le
programme affiche la valeur courante de
l’expression à droite
44
 L’opération de Lecture

 Permet à un programme de lire une valeur

saisie par exemple au clavier
– En pseudo-code:
 Variable V: caractères
Lire V
– A la rencontre d’une telle instruction, le
programme s’arrête jusqu’à la saisie d’une chaîne
de caractères au clavier
– Le programme continue son exécution après la
saisie de la touche entrée
45
 Bonne pratique

 Ilest fortement conseillé, avant une

instruction de lecture, de prévenir l’utilisateur
et de lui indiquer ce qu’il doit faire
– Exemple:
Variable N: caractères
Ecrire "Veuillez renseigner votre nom, svp!"
Lire N
Ecrire "Merci" + " " + N

46
 Re-pause exercices

47
 Exo1

 Quel résultat produit le programme suivant ?

– Variables val, Double: Réel
Début
Val ← 231
Double ← Val * 2
Ecrire Val
Ecrire Double
Fin

48
 Exo2

 Ecrire un programme qui demande un

nombre à l’utilisateur, puis qui calcule et
affiche le carré de ce nombre.

49
 Exo3

 Ecrire un programme qui lit le prix HT d’un

article, le nombre d’articles et le taux de TVA,
et qui fournit le prix total TTC correspondant.
Faire en sorte que des libellés apparaissent
clairement.

50
 Les Tests

51
 Motivation

 Prenons l’exemple de la recette de cuisine et un

algorithme pour se faire cuire un œuf à la coque
– Prenez un bel œuf frais. Si vous avez un micro-ondes,
mettez le dedans 20s, sinon utilisez une casserole et
mettez-le dans de l’eau bouillante pendant 5min
 L’algorithme précédent prend en compte les deux
situations où le cuisinier possède ou non un micro-
ondes
 Les ordinateurs sont aussi capable d’évaluer une
situation et de réaliser les calculs adéquats en
52 conséquence
 Structure d’un Test

 Deux structures:
– Si expression booléenne Alors
Instructions
Finsi
– Si booléen Alors
Instructions 1
Sinon
Instructions 2
Finsi
 L’expression conditionnelle peut être une
53 variable de type booléen ou une condition
 La condition

 Unecondition est le résultat d’une

comparaison
 Généralement,
– Une valeur
– Un opérateur de comparaison
– Une autre valeur
 On retrouve les opérateurs: =, <, >, <>, <=,
>=

54
 Sémantique

 Dans le premier cas,

– Si l’expression booléenne est vraie, alors la
séquence comprise dans « instructions » sera
exécutée puis les autres instructions qui suivent
seront exécutées
– Sinon, le programme saute la séquence
instructions, et exécute directement les
instructions qui suivent le bloc de test

55
 Sémantique

 Dans le deuxième cas,

– Si l’expression booléenne est vraie, alors le
programme:
 exécute la séquence d’instructions « instructions1 »,
 Saute la séquence d’instructions « instuctions2 »,
 Puis exécute les instructions suivantes

– Sinon, alors le programme:

 saute la séquence d’instructions « instructions1 »
 Exécute la séquence d’instructions « instructions2 »
 Puis continue en exécutant les instructions suivantes

56
 L’œuf à la coque
Prendre un œuf frais, Beldi de préférence
Si vous avez un micro-ondes Alors
Mettre l’œuf dans ce micro-ondes
Le sortir après 20s
Sinon
Prendre une casserole
Remplir la casserole d’eau
Mettre l’œuf dans la casserole
Le sortir après 5min
FinSi
Mettre l’œuf dans un coquetier
57 Le déguster
 Un petit exo

 Ecrire un algorithme qui demande un nombre

à l’utilisateur, et l’informe ensuite si ce
nombre est positif ou négatif (on laisse de
côté le cas où le nombre vaut zéro).

58
 Les conditions composées

 Parfois,il n’est pas possible d’énoncer une

condition en utilisant une forme simple (de
type V>0)
 Dans ces cas (e.g. 0<V<10), on utilisera les
opérateurs logiques: ET, OU, NON, …

59
 Tables de vérité

C1 et C2 C2 Vrai C2 Faux
C1 Vrai Vrai Faux
C1 Faux Faux Faux

C1 ou C2 C2 Vrai C2 Faux
C1 Vrai Vrai Vrai
C1 Faux Vrai Faux

C1 xor C2 C2 Vrai C2 Faux

C1 Vrai Faux Vrai
60 C1 Faux Vrai Faux
 Encore deux petits exos

 Ecrire un algorithme qui demande deux

nombres à l’utilisateur et l’informe ensuite si
leur produit est négatif ou positif (on laisse
de côté le cas où le produit est nul). Attention
toutefois : on ne doit pas calculer le produit
des deux nombres.
 Ecrire un algorithme qui demande trois noms
à l’utilisateur et l’informe ensuite s’ils sont
rangés ou non dans l’ordre alphabétique.
61
 Tests imbriqués: motivation
 Prenons, un autre exemple:
– Un programme qui détermine l’état de l’eau selon la température:
– Une solution:
Variable Temp: Entier
Début
Ecrire "Entrez la température de l’eau :"
Lire Temp
Si Temp <= 0 Alors
Ecrire "C’est de la glace"
FinSi
Si Temp > 0 Et Temp =< 100 Alors
Ecrire "C’est du liquide"
Finsi
Si Temp > 100 Alors
Ecrire "C’est de la vapeur"
62 Finsi
Fin
 Tests imbriqués
 Pour notre exemple, en imbriquant les tests, il est plus élégant
d’écrire:
Variable Temp: Entier
Début
Ecrire "Entrez la température de l’eau :"
Lire Temp
Si Temp <= 0 Alors
Ecrire "C’est de la glace"
Sinon
Si Temp =< 100 Alors
Ecrire "C’est du liquide"
Sinon
Ecrire "C’est de la vapeur"
Finsi
63 Finsi
 Utilité

 L’utilisation
des tests imbriqués n’est pas
indispensable, cependant elle permet d’avoir:
– des programmes plus lisibles
– des conditions moins complexes
– des programmes "plus performants"

64
 La pause exos!

65
 Exo1

 Ecrire un algorithme qui demande un nombre

à l’utilisateur, et l’informe ensuite si ce
nombre est positif ou négatif (on inclut cette
fois le traitement du cas où le nombre vaut
zéro).

66
 Exo2

 Ecrire un algorithme qui demande deux

nombres à l’utilisateur et l’informe ensuite si
le produit est négatif ou positif (on inclut cette
fois le traitement du cas où le produit peut
être nul). Attention toutefois, on ne doit pas
calculer le produit !

67
 Exo3

 Ecrire un algorithme qui demande l’âge d’un

enfant à l’utilisateur. Ensuite, il l’informe de
sa catégorie sachant qu’un enfant âgé de
moins de 6 ans n’est pas admis (l’utilisateur
est supposé coopératif et ne rentrera pas de
valeur inférieure à 6):
– "Poussin" de 6 à 7 ans
– "Pupille" de 8 à 9 ans
– "Minime" de 10 à 11 ans
68 – "Cadet" après 12 ans
 Exo4

 Un magasin de reprographie facture 1DH les

dix premières photocopies, 0,75 DH les vingt
suivantes et 0,50 DH au-delà. Ecrire un
algorithme qui demande à l’utilisateur le
nombre de photocopies effectuées et qui
affiche la facture correspondante.

69
 Exo5

 Les habitants de Mars paient l’impôt selon

les règles suivantes :
– les hommes de plus de 20 ans paient l’impôt
– les femmes paient l’impôt si elles ont entre 18 et
35 ans
– les autres ne paient pas d’impôt
 Leprogramme demandera donc l’âge et le
sexe du Marcien, et se prononcera donc
ensuite sur le fait que l’habitant est
70 imposable.
 Exo6
 Les élections législatives sur Jupiter obéissent à la règle
suivante :
– lorsque l'un des candidats obtient plus de 50% des suffrages, il est
élu dès le premier tour.
– en cas de deuxième tour, peuvent participer uniquement les
candidats ayant obtenu au moins 12,5% des voix au premier tour.
 Ecrire un algorithme qui permette la saisie des scores de
quatre candidats au premier tour. Cet algorithme traitera
ensuite le candidat numéro 1 (et uniquement lui) : il dira s'il est
élu, battu, s'il se trouve en ballottage favorable (il participe au
second tour en étant arrivé en tête à l'issue du premier tour) ou
défavorable (il participe au second tour sans avoir été en tête
71 au premier tour).
 Les boucles

72
 Justification, un exemple
 Posons le problème suivant:
– Nous voulons réaliser un programme qui renvoie l’inverse d’un
chiffre: pour N, renvoyer 1/N.
– En bon concepteur, le programmeur veut prendre en compte le
fait que l’utilisateur ne doit pas rentrer un 0.
 En utilisant une structure conditionnelle, on peut écrire:
– Variable UnChiffre: Entier
Ecrire "donner un chiffre et je vous renvoie son inverse"
Lire UnChiffre
Si UnChiffre =0 Alors
Ecrire "Saisie erronnée. Donner un chiffre non nul !"
Lire UnChiffre
FinSi
73
Ecrire 1/UnChiffre
 Justification

 Qu’est-ce qui se passe si l’utilisateur donne

encore un zéro?
 Combien de Tests il faut inclure pour
résoudre le problème d’un utilisateur têtu?
 Conceptuellement, quelle serait la solution?

74
 La solution: une boucle itérative
 Structure:
– TantQue booléen
…
Instructions
…
FinTantQue
 Pour notre problème, cela donnerait:
– Variable UnChiffre: Entier
Ecrire "donner un chiffre et je vous renvoie son inverse"
Lire UnChiffre
TantQue (UnChiffre=0)
Ecrire "Saisie erronée. Donner un chiffre non nul !"
Lire UnChiffre
FinTantQue
75 Ecrire 1/UnChiffre
 Principe de la boucle

 Le principe est simple :

– le programme arrive sur la ligne du TantQue.
– Il examine alors la valeur du booléen (qui peut
être une variable booléenne ou une 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.
– Le Programme poursuit l’exécution des
instructions qui suivent la boucle dès que le
76 booléen prend la valeur FAUX.
 Exo1

 Ecrire un algorithme qui demande à

l’utilisateur un nombre compris entre 1 et 3
jusqu’à ce que la réponse convienne.

77
 Exo2

 Ecrireun algorithme qui demande un nombre

compris entre 10 et 20, jusqu’à ce que la
réponse convienne. En cas de réponse
supérieure à 20, on fera apparaître un
message : « Plus petit ! », et inversement,
« Plus grand ! » si le nombre est inférieur à
10.

78
 Exo3

 Ecrire un algorithme qui demande un nombre

de départ, et qui ensuite affiche les dix
nombres suivants. Par exemple, si
l'utilisateur entre le nombre 17, le programme
affichera les nombres de 18 à 27.

79
 Les boucles « Pour »:
Boucler en comptant

 Parfois le nombre de boucles peut être

déterminé à l’avance, exemple de l’exo3
 Dans ce cas on peut utiliser une structure
itérative qui utilise une variable entière qui
s’incrémente à chaque itération. Structure:
– Pour Compteur <- ValeurInitiale à ValeurFinale
…
Instructions
…
80 Compteur Suivant
 Les pas d’incrémentation

 Par défaut, le compteur est incrémenté de 1

 Parfois, on peut avoir besoin d’incrémenter le
compteur d’une valeur différente
 Dans ce cas, l’incrément est spécifié explicitement:
– Pour Compteur <- ValeurInitiale à ValeurFinale PAS ValeurDuPas
…
Instructions
…
Compteur Suivant

81
 Arbitrage,
boucle «TantQue» Vs boucle «Pour»

 La boucle "TantQue" sera utilisée lors du

traitement d’ensembles dont on ne connaît pas la
taille, e.g. :
– Contrôle de saisie
– Lecture dans un fichier/ une base de donnée
– Gestion d’applications interactives, …
 Laboucle "Pour" sera privilégiée lors du traitement
d’ensembles dont la taille est connue, e.g.:
– Un intervalle d’entiers
82 – Un tableau, …
 Les boucles imbriquées

 De la même manière que les structures de tests

imbriquées, on peut imbriquer des boucles
 Exemple:
– Variables i,j : Entier Variables i,j : Entier
Pour i0 à 3 Pour i0 à 3
Ecrire "boucle sup" Ecrire "boucle sup"
Pour j0 à 3 Suivant i
Pour j0 à 3
Ecrire "boucle inf"
Ecrire "boucle inf"
Suivant j Suivant j
83 Suivant i
 Exo4

 Ecrire un algorithme qui demande un nombre

de départ, et qui ensuite écrit la table de
multiplication de ce nombre, présentée
comme suit :
Table de n :
nx1=7
n x 2 = 14
n x 3 = 21
…
84 n x 10 = 70
 Exo5

 Ecrire un algorithme qui demande un nombre

de départ, et qui calcule la somme des
entiers jusqu’à ce nombre. Par exemple, si
l’on entre 5, le programme doit calculer :
– 1 + 2 + 3 + 4 + 5 = 15

85
 Exo6

 Ecrireun algorithme qui demande un nombre

de départ, et qui calcule sa factorielle.
– la factorielle de 8, notée 8 !, vaut
– 1x2x3x4x5x6x7x8

86
 Exo7
 Ecrire un algorithme qui demande successivement 20
nombres à l’utilisateur, et qui lui dit ensuite quel était le
plus grand parmi ces 20 nombres, e.g. :
– Entrez le nombre numéro 1 : 12
Entrez le nombre numéro 2 : 14
etc.
Entrez le nombre numéro 20 : 6
Le plus grand de ces nombres est : 14
 Modifiez ensuite l’algorithme pour que le programme
affiche de surcroît en quelle position avait été saisie ce
nombre :
– C’était le nombre numéro 2
87
 Exo8

 Réécrire l’algorithme de l’exo7, mais cette

fois-ci on ne connaît pas d’avance combien
l’utilisateur souhaite saisir de nombres. La
saisie des nombres s’arrête lorsque
l’utilisateur entre un zéro.

88
 Exo9
 Écrire un algorithme qui permet de connaître ses
chances de gagner au tiercé, quarté, quinté:
– On demande à l’utilisateur le nombre de chevaux partants,
et le nombre de chevaux joués. Les deux messages
affichés devront être :
– Dans l’ordre : une chance sur X de gagner
Dans le désordre : une chance sur Y de gagner
– X et Y nous sont donnés par la formule suivante, si n est le
nombre de chevaux partants et p le nombre de chevaux
joués :
 X = n ! / (n - p) !
Y = n ! / (p ! * (n – p) !)
89
 Les tableaux

90
 Motivation
 Il
est nécessaire parfois de stocker et de traiter un
certains nombres d’informations du même type
– Les noms d’utilisateurs d’un forum
– Les notes d’une classe, …
 Une première possibilité est de créer autant de
variables que d’informations
 Pbs:
– Leur nombre peut être assez conséquent
– Ce nombre peut ne pas être connu à l’avance
91 – Ce nombre peut fluctuer pendant l’exécution
 La solution magique:
Utiliser la structure tableau

 Un tableau est une variable contenant

plusieurs éléments
 Chaque éléments est identifié par sa position
dans le tableau,
 La position d’un élément est appelée « indice »

92
 Notation

 Un tableau est déclaré en spécifiant

– Son nom
– Le type de ces éléments
– Accessoirement, sa taille
 Dansla plus part des langages, un tableau est
homogène. On va donc s’en tenir à cette contrainte
 Exemple
– Tableau Noms(10) : Caractères
– Déclare une variable de type tableau nommée «Noms»
93 contenant au plus 10 éléments de type caractères
 Les indices
 Dansla majorité des langages de
programmation, les indices commencent à 0
– L’indice est toujours un entier
– Le premier élément du tableau est l’élément qui
possède l’indice 0
– Le ième élément possède l’indice (i-1)
– L’indice ne peut être supérieur ou égal à la taille du
tableau
– L’élément possédant l’indice i est accessible via la
notation : NomTableau(i)
94
 Les tableaux et les boucles

 Un des gros avantages de l’utilisation des

tableaux est de pouvoir faire des traitements
génériques en utilisant les boucles
 Exemple,
– saisie de notes d’une classe de 10 élèves et
calcul de la moyenne:

95
 Solution
Tableau Note(10) : Réel
Variable Moyenne, Somme: Réel
Variable i: Entier
Pour i  0 à 9
Ecrire "Entrez la note numéro: "
Ecrire i+1
Lire Note(i)
i Suivant
Som  0
Pour i  0 à 9
Som  Som + Note(i)
i Suivant
Moyenne  Somme / 10
96 Ecrire "la moyenne de la classe est égale à : " + Moyenne
 Exo1

 Ecrireun algorithme qui déclare et remplit un

tableau de 7 valeurs numériques en les
mettant toutes à zéro.

97
 Exo2

 Que produit l’algorithme suivant ?

– Tableau Nb(5) : Entier
Variable i : Entier
Pour i ← 0 à 4
Nb(i) ← i * i
i suivant
Pour i ← 0 à 4
Ecrire Nb(i)
i suivant
 Peut-on simplifier cet algorithme ?
98
 Exo3

 Que produit l’algorithme suivant ?

– Tableau N(7) : Entier
Variables i, k : Entier
N(0) ← 1
Pour k ← 1 à 6
N(k) ← N(k-1) + 2
k Suivant
Pour i ← 0 à 6
Ecrire N(i)
i suivant
99
 Exo4

 Que produit l’algorithme suivant ?

– Tableau Suite(7) : Entier
Variable i : Entier
Suite(0) ← 1
Suite(1) ← 1
Pour i ← 2 à 7
Suite(i) ← Suite(i-1) + Suite(i-2)
i suivant
Pour i ← 0 à 7
Ecrire Suite(i)
100
i suivant
 Les tableaux dynamiques

 Parfois, la taille du tableau n’est pas connue

dans la phase de programmation, mais
pendant la phase d’exécution
 Pour cela, il est possible de déclarer un
tableau sans indiquer sa dimension
 En utilisera l’instruction « Redim » pour
indiquer ultérieurement sa dimension

101
 Exemple
Tableau Note() : Réel
Variable Moyenne, Somme: Réel
Variable taille, i: Entier
Ecrire "donner le nombre d’élèves"
Lire taille
Redim Note(taille)
Pour i  0 à (taille-1)
Ecrire "Entrez la note numéro: "
Ecrire i+1
Lire Note(i)
i Suivant
……..
102
 Exo5

 Ecrivez un algorithme permettant à l’utilisateur

de saisir un nombre quelconque de valeurs, qui
devront être stockées dans un tableau.
– L’utilisateur doit donc commencer par entrer le nombre
de valeurs qu’il compte saisir. Il effectuera ensuite
cette saisie.
– Enfin, une fois la saisie terminée, le programme
affichera le nombre de valeurs négatives et le nombre
de valeurs positives.

103
 Exo6

 Ecrivez un algorithme calculant la somme

des valeurs d’un tableau.

104
 Exo7

 Ecrivez un algorithme qui permette la saisie

d’un nombre quelconque de valeurs, spécifié
par l’utilisateur.
 Toutes les valeurs doivent être ensuite
augmentées de 1, l’ancien et le nouveau
tableau seront affiché à l’écran sous la forme
[i0,i1,….,in].

105
 Exo8

 Ecrivez un algorithme permettant, toujours

sur le même principe, à l’utilisateur de saisir
un nombre déterminé de valeurs. Le
programme, une fois la saisie terminée,
renvoie la plus grande valeur en précisant
quelle position elle occupe dans le tableau.
On prendra soin d’effectuer la saisie dans un
premier temps, et la recherche de la plus
grande valeur du tableau dans un second
106 temps.
 Exo9

 Toujours et encore sur le même principe,

écrivez un algorithme permettant, à
l’utilisateur de saisir les notes d'une classe.
Le programme, une fois la saisie terminée,
renvoie le nombre des notes supérieures à la
moyenne de la classe.

107
 Les algorithmes
classiques pour les
tableaux

108
 Objectif

 Dans une multitude de cas, des problèmes

classiques sont soulevés:
– trier un tableau, exemples classiques:
 Dictionnaire
 Notes

– Rechercher une valeur dans un tableau

 Est-ce qu’un mot existe?
 Est-ce qu’un étudiant a eu une note éliminatoire

109
 Algorithmes classiques

 Algorithmes de Tri
– Tri par sélection
– Tri à bulles
 Algorithme de recherche
– Utilisation d’un drapeau (flag)

110
 Tri par sélection

 Idée très simple:

– Parcourir le tableau,
– Détecter l’élément le plus petit
– Mettre cet élément à la position 0 (en fait
échanger son indice avec celui qui est
initialement à l’indice 0)
– Refaire le même traitement pour le deuxième
élément le plus petit et l’indice 1
– Continuer ainsi jusqu’à épuisement du tableau

111
 L’algorithme:
 Pour i  0 à taille-2
posmini i
Pour j  i + 1 à taille-1
Si t(j) < t(posmini) Alors
posmini  j
Finsi
j suivant
temp  t(posmini)
t(posmini)  t(i)
t(i)  temp
112 i suivant
 Algorithme de recherche:
l’utilisation des flags

 Un flag est un drapeau correspondant à

l’occurrence d’un événement
 Généralement, c’est une valeur booléenne
– Mise au départ à Faux
– Pendant le traitement, elle change de valeur si
l’événement est rencontré, elle reste à faux sinon
– A la fin du traitement, la valeur du booléen permet
de dire s’il y a occurrence ou pas de l’événement.

113
 Exemple de problème

 Prenons l’exemple suivant:

– Un tableau d’entier
– L’utilisateur saisit un entier au clavier
– L’algorithme détermine si l’entier est dans le tableau
ou pas
 Tableau Tab(20) : Entier
Variable N : Entier
Ecrire "Entrez une valeur entière"
Lire N
Pour i ← 0 à 19
xxxxxxxxxx
xxxxxxxxxx
114 i suivant
 Examinons une solution intuitive
 Tableau Tab(20) : Entier
 Que fait l’algo si la valeur n’y
Variable N : Entier
Début est pas?
Ecrire "Entrez une valeur"  Que fait-il quand elle y est ?
Lire N
 Qu’est ce qu’il se passe si le
Pour i ← 0 à 19
Si N = Tab(i) Alors tableaux comprend
Ecrire "y est!" 1 000 000 de valeurs?
Sinon 
Ecrire "y est pas!" Qu’est-ce qui se passe si le
FinSi tableau comprend 1 000 000
i suivant de valeurs égales à la valeur
recherchée
115
 Conclusions

 A l’intérieur de la boucle
– Faire le test
 A l’extérieur
– Récupérer le résultat des traitements
– Effectuer les affichages correspondants
 Solution magique: utiliser un flag!
– Flag = true  y est
– Flag = false  y est pas

116
 Algorithme
 Tableau Tab(20) : Entier
Variable N : Entier
Variable Trouvé: Booléen
Ecrire "Entrez une valeur entière"
Lire N
Trouvé ← Faux
Pour i ← 0 à 19
Si N = Tab(i) Alors
Trouvé ← Vrai
FinSi
i suivant
Si Trouvé Alors
Ecrire "y est!"
Sinon
Ecrire "y est pas!"
117
FinSi
 Le tri à bulles

 Tri
à bulles = tri de tableau + flag
 Pour le tri par sélection, l’idée simple:
– Le plus petit élément est dans position 0
– Le suivant est dans la position 1
– Ainsi de suite
 Maintenant, une autre propriété simple: pour
un tableau trié:
– Dans un tableau trié, tout élément est plus petit
que l’élément qui le suit
118
 Principe de base du à bulles
 fonctionnement:
– Si un élément est plus grand que l’élément qui le suit,
on les permute
– Continuer tant que notre propriété simple n’est pas
vérifiée
 Dispositif:
– Nous utiliserons un flag correspondant à la vérification
de notre propriété
– À chaque parcours du tableau, les éléments les plus
petits remontent vers le haut
119 – Quand le flag est à true, le tableau est trié
 Le flag
 Variable Trié: Booléen
Trié ← Faux
TantQue non Trié
Trié ← VRAI
Pour i ← 0 à 9
Si t(i) > t(i+1) Alors
temp ← t(i)
t(i) ← t(i+1)
t(i+1) ← temp
Trié ← FAUX
Finsi
i suivant
120
FinTantQue
 Un autre algorithme classique:
La recherche dichotomique

 L’algorithme de recherche dichotomique est

– Un algorithme de recherche
– Destiné aux tableaux de grande taille
– Exemple classique: recherche d’un mot dans un
dictionnaire
 Motivation principale: profiter du fait que le
tableau soit trié pour effectuer une recherche
plus efficace qu’une recherche simple

121
 Démarche
 Subdiviser le tableau en deux parties
 identifier la partie où peut être l’élément
 Prendre cette partie et la subdiviser à son tour en
deux sous parties
 Identifier la sous partie où est susceptible de se
trouver l’élément
 Continuer, jusqu’à
– trouver l’élément sur un milieu de sous partie élément
trouvé, Ou:
– Qu’il n’y aie plus de partie à subdiviser  élément absent
122
 L’algorithme
Variable Sup, Inf, i, Comp : Entier TantQue Non(arret)
Tableau tab(N): Entier Comp ← (Sup + Inf)/2
Variable arret : Booléen Si i < tab(Comp) Alors
Ecrire "Entrez l’entier à trouver" Sup ← Comp - 1
Lire i Sinon
Sup ← N - 1 Inf ← Comp + 1
Inf ← 0 FinSi
arret ← Faux arret ← (i = tab(Comp) ou
Sup < Inf)
FinTantQue
Si i = tab(Comp) Alors
Ecrire "y est!"
Sinon
Ecrire "y est pas!"
123
Finsi
 Exo1

 Ecrivez un algorithme qui trie un tableau

dans l’ordre décroissant. Vous écrirez bien
entendu deux versions de cet algorithme,
l'une employant le tri par selection, l'autre le
tri à bulles

12
 Exo2

 Ecrivez un algorithme qui inverse l’ordre des

éléments d’un tableau dont on suppose qu'il
a été préalablement saisi (« les premiers
seront les derniers… ») en utilisant un
tableau unique.

125
 Exo3

 Ecrivez un algorithme qui permette à

l’utilisateur de supprimer une valeur d’un
tableau préalablement saisi. L’utilisateur
donnera l’indice de la valeur qu’il souhaite
supprimer. Attention, il ne s’agit pas de
remettre une valeur à zéro, mais bel et bien
de la supprimer du tableau lui-même !

126
 Partie 4:
Les tableaux
mutidimensionnels

127
 Motivation

 Prenons, l’exemple d’un calcul matricielle

 Une matrice de M lignes et N colonnes peut
bien évidemment être modélisée par un
tableau de taille M*N
 Afin de calculer la multiplication de deux
matrices, imaginez le casse tête!
 L’idée, pourquoi ne pas modéliser une
matrice par une structure matricielle:
– Un tableau de tableaux, i.e. un tableau de
128
dimension 2
 Un tableau de tableaux

 Untableau de tableaux est déclaré de la

manière suivante:
– Tableau Nom_tableau(dim1)(dim2): T
 Cette déclaration permet la réservation d’un
espace mémoire équivalent à dim1*dim2 de
l’espace mémoire de stockage d’un élément
de type T.
 L’accès à l’élement se trouvant à la i ème ligne
et la jème colonne se fait à travers l’appel:
129 – Nom_Tableau(i-1)(j-1)
 Exo1

 Écrivez un algorithme remplissant un tableau

de 6 sur 13, avec des zéros.

130
 Exo2
 Quel résultat produira cet algorithme ?
 Tableau X(2, 3) : Entier
Variables i, j, val : Entier
Val ← 1
Pour i ← 0 à 1
Pour j ← 0 à 2
X(i, j) ← Val
Val ← Val + 1
j Suivant
i Suivant
Pour i ← 0 à 1
Pour j ← 0 à 2
Ecrire X(i, j)
131 j Suivant
i Suivant
 Exo3

 Quel résultat produira cet algorithme ?

 Tableau X(2, 3) en Entier
Variables i, j, val en Entier
Val ← 1
Pour i ← 0 à 1
Pour j ← 0 à 2
X(i, j) ← Val
Val ← Val + 1
j Suivant
i Suivant
Pour j ← 0 à 2
Pour i ← 0 à 1
Ecrire X(i, j)
i Suivant
132 j Suivant
 Exo4

 Quel résultat produira cet algorithme ?

 Tableau T(4, 2) en Entier
Variables k, m, en Entier
Pour k ← 0 à 3
Pour m ← 0 à 1
T(k, m) ← k + m
m Suivant
k Suivant
Pour k ← 0 à 3
Pour m ← 0 à 1
Ecrire T(k, m)
m Suivant
k Suivant
133
 Exo5

 Mêmes questions, en remplaçant la ligne :

 « T(k, m) ← k + m » par
– « T(k, m) ← 2 * k + (m + 1) »
 puis par :
– « T(k, m) ← (k + 1) + 4 * m »

134
 Exo6

 Soit un tableau T à deux dimensions (12, 8)

préalablement rempli de valeurs numériques.
 Écrire un algorithme qui recherche la plus
grande valeur au sein de ce tableau.

135
 Tableau à N dimensions

 Ilest possible de déclarer des tableaux à N

dimensions:
– Position d’un objet dans l’espace: un tableau à 3
dimension  un cube
– Position d’un objet dans l’espace et dans le
temps: un tableau à 4 dimension
 Déclaration:
– Tableau Nom_tableau(dim1)…(dimN): type
 Accès à l’élément i1,…,iN:
136 – Nom_tableau(i1-1)…(iN-1)
 Les fonctions prédéfinies

137
 Utilité

 Les algorithmes peuvent s’appuyer sur des

bibliothèques pour effectuer des calculs
 Les bibliothèques offrent des fonctions
prédéfinies
– Effectuent des traitement impossible à réaliser
par un algorithme
– Soulagent le programmeur:
 Sin(x)=x-(x^3/3!)+ (x^5/5!)-….
 Exemple: calculer Sin(x)
138
 C’est quoi une fonction en
informatique?

 Une fonction est constituée du:

– Nom de la fonction
– Deux parenthèses, une ouvrante et une fermante
– D’un certain nombres d’arguments ou de
paramètres
 Chaque argument possède une position et un type
 Exemple
– Variable A: Réel
– A sin(55)
139
 Exemple

 Parmi ces affectations (considérées

indépendamment les unes des autres), lesquelles
provoqueront des erreurs, et pourquoi ?
 Variables A, B, C : Réel
Variables D, E : Caractère
A ← Sin(B)
A ← Sin(A + B * C)
B ← Sin(A) – Sin(D)
D ← Sin(A / B)
140 C ← Cos(Sin(A)
 Quelques exemples de fonctions
prédéfinies classiques

 Les fonctions de textes

– Len(chaîne) : renvoie le nombre de caractères d’une chaîne
– Mid(chaîne,n1,n2) : renvoie un extrait de la chaîne, commençant
au caractère n1 et faisant n2 caractères de long.
– Left(chaîne,n) : renvoie les n caractères les plus à gauche dans
chaîne.
– Right(chaîne,n) : renvoie les n caractères les plus à droite dans
chaîne
– Trouve(chaîne1,chaîne2) : renvoie un nombre correspondant à la
position de chaîne2 dans chaîne1. Si chaîne2 n’est pas comprise
dans chaîne1, la fonction renvoie zéro.

141
 Exo1

 Ecrivez un algorithme qui demande un mot à

l’utilisateur et qui affiche à l’écran le nombre
de lettres de ce mot

142
 Exo2

 Ecrivez un algorithme qui demande une

phrase à l’utilisateur et qui affiche à l’écran le
nombre de mots de cette phrase. On
suppose que les mots ne sont séparés que
par des espaces

143
 Exo3

 Ecrivez un algorithme qui demande une

phrase à l’utilisateur. Celui-ci entrera ensuite
le rang d’un caractère à supprimer, et la
nouvelle phrase doit être affichée (on doit
réellement supprimer le caractère dans la
variable qui stocke la phrase, et pas
uniquement à l’écran).

144
 Exemples

Méthode résultat
Len("Bonjour, ça va ?") 16
Len("") 0
Mid("Zorro is back", 4, 7) "ro is b"
Mid("Zorro is back", 12, 1) "c"
Left("Et pourtant…", 8) "Et pourt"
Right("Et pourtant…", 4) "t…"
Trouve("Un pur bonheur", "pur") 4
Trouve("Un pur bonheur", "Sur terre") 0

145
 Quelques exemples de fonctions
prédéfinies classiques

 Les fonctions numériques classiques:

– Ent(nombre_Réel): renvoie la valeur entière
 E.g. Ent(1,5) renvoie 1
– Mod(nombre1,nombre2): renvoie le modulo
 E.g. Mod(3,10): renvoie 3
– Alea(): permet de générer un chiffre aléatoire
entre 0 et 1
 E.g Alea()*N: permet de générer un chiffre aléatoire
entre 0 et N

146
 Exo1

 Ecrivez un algorithme qui demande un

nombre entier à l’utilisateur. L’ordinateur
affiche ensuite le message "Ce nombre est
pair" ou "Ce nombre est impair" selon le cas.

147
 Exo2

 Ecrivezles algorithmes qui génèrent un

nombre X aléatoire tel que …
– 0 =< X < 2
– –1 =< X < 1
– 1,35 =< X < 1,65
– X modélise un dé à six faces
– –10,5 =< X < +6,5
– Glup modélise la somme du jet simultané de deux
dés à six faces
148
 En Conclusion

 L’algorithmique reste un moyen

– de réfléchir à la résolution d’un problème
– de structurer et de vérifier la validité d’une solution
– de communiquer et de publier cette solution
 On a parcouru les mécanismes classiques
utilisés dans l’algorithmique et mis à disposition
du programmeur

149
 Complexité des Algorithmes

15
 La double problématique de
l’algorithmique:
 Trouver une méthode de résolution (exacte
ou approchée) du problème.
– E.g. calculer pour un X réel et un n entier la
valeur X^n
 Trouver une méthode efficace.
 Savoir résoudre un problème est une chose,
le résoudre efficacement en est une autre.

151
Motivation
 Calcul de x^n
 Données : un entier naturel n et un réel x. On
veut calculer x^n.
 Moyens :
– Nous partons de y1 = x.
– Nous allons construire une suite de valeurs y1, ..., ym
telle que la valeur yk soit obtenue par multiplication de
deux puissances de x précédemment calculées :
 yk = yu yv, avec 1 u;v < k, k [2;m].
 But : ym= x^n.
– Le coût de l’algorithme sera alors de m-1, le nombre de
153
multiplications faites pour obtenir le résultat recherché
 Algorithme trivial

 y[1] =x
Pour i de 2 à n faire
y[i] = y[i-1] y[1]
renvoyer y[n]
 Le coût de l’algorithme: n-1 multiplications

154
 Méthode binaire
 Écrire
n sous forme binaire
 Remplacer chaque :
– 1 par la paire de lettres « SX » ;
– 0 par la lettre « S ».
 Éliminer la paire « SX » la plus à gauche.
 Résultat : un mode de calcul de x^n, en partant
de x où
– S signifie « élever au carré » (squaring)
– X signifie « multiplier par x ».
155 – SX élevé au carré puis multiplier par X
 Illustration
 Illustration avec n = 25
 n = 11001

1 1 0 0 1
SX SX S S SX
SX S S SX
 Nous partons de x et nous obtenons successivement :
 x^2, x^3, x^6, x^12, x^24, x^25.
 Nous sommes donc capables de calculer x^25 en 6
multiplications au lieu de 24 pour l’algorithme trivial
156
 La complexité

 Soitn un chiffre dont la représentation prend

p chiffres binaires, on a:
–
– Ce qui donne:
 SoitNb1, le nombre de 1 dans l’écriture
binaire de n
– On a donc : élévations au carré
(élimination du premier SX)
– Et multiplications par x
157  Le nombre de multiplications:
 La complexité

 Trivialement :
–

 On obtient donc:
–

 Ce qui donne 20 multiplications au plus pour

calculer x^1000 au lieu de 999 multiplications

158
 Y a t-il mieux?
 Prenons le cas n = 15 = 1111
1 1 1 1
SX SX SX SX
SX SX SX
 Nous partons de x et nous obtenons successivement :
– x2, x3, x6, x7, x14, x15.
 Nous sommes donc capables de calculer x^15 en 6 multiplications
par la méthode binaire
 Autre schéma de calcul : x2, x3, x6, x12, x15 = x12x3.
 Nous obtenons ainsi x15 en 5 multiplications
 La méthode binaire n’est donc pas optimale (c’est-à-dire que l’on
peut faire mieux).
159
 Algorithme de l’arbre

 Lek+1e niveau de l’arbre est défini comme

suit :
– on suppose que l’on a déjà les k premiers niveaux
;
– on construit le k+1e de la gauche vers la droite en
ajoutant sous le nœud n les nœuds de valeur
n+1, n+a1, ...,n+ak-1 où 1, a1, ..., ak-1 est le
chemin de la racine au nœud n ;
– on supprime tous les nœuds qui dupliquent une
valeur déjà obtenue.
160
 Illustration

x^2

x^3 x^4

x^5 x^6 x^8

x^7 x^10 x^9 x^12 x^16

x^14 x^13 x^15 x^20 ………………………………

161
 Comparaison

 Pour calculer x^15, on effectue, donc le chemin:

– x^2=x * x
– x^3=x^2 * x
– x^5=x^3 * x^2
– x^10=x^5 * x^5
– x^15=x^10 * x^5
5 multiplications au lieu de 6!
 L’algorithme de l’arbre est optimal pour tout n≤76

162
 En conclusion…

 Pour un problème donné (même aussi

simple que calculer x^n), il est parfois facile
de trouver un algorithme mais pas toujours
l’algorithme le plus optimal
 La suite:
– Des problèmes classiques
– Des méthodes classiques de résolution
– Des structures de données classiques
– Une étude de complexité comparative, sera
163 réalisée tout au long
 Complexité et optimalité:
Concepts et définitions

164
 La complexité

 Définition: La complexité d’un algorithme est la

mesure du nombre d’opérations fondamentales
qu’il effectue sur un jeu de données. La
complexité est exprimée comme une fonction
de la taille du jeu de données
 Dn, note l’ensemble des données de taille n
 T(d), le coût de l’algorithme sur une donnée d

165
 Complexité au meilleur

 Le plus petit nombre d’opérations qu’aura à

exécuter l’algorithme sur un jeu de données de
taille fixée.

 C’est une borne inférieure de la complexité de

l’algorithme

166
 Complexité au pire

 C’est le plus grand nombre d’opérations

qu’aura à exécuter l’algorithme sur un jeu de
données de taille fixée

 il s’agit d’un maximum, et l’algorithme finira

donc toujours avant d’avoir effectué Tmax(n)
opérations


167
 Complexité en moyenne
 C’est la moyenne des complexités de
l’algorithme sur les jeux de données d’une taille
donnée
 Parfois, il faut prendre en compte la probabilité
de leur apparition
 reflète le comportement « général » de
l’algorithme si les cas extrêmes sont rares ou si
la complexité varie peu en fonction des données


168
 Optimalité

 Un algorithme est dit optimal si sa complexité est

la complexité minimale parmi les algorithmes de
sa classe.

169
 Caractéristiques des études de
complexité

 Dans une étude de complexité, on

s’intéresse
– Généralement à la complexité en temps des
algorithmes.
– Parfois (rarement) à d’autres caractéristiques
 la complexité en espace (taille de l’espace mémoire
utilisé),
 la largeur de bande passante requise,
…

170
 Contexte de l’étude

 Dans l’étude de complexité, il est parfois

intéressant de considérer le modèle de
machine d’exécution
– Généralement machines à:
 accès aléatoire (RAM)
 processeur unique
 Exécution séquentielle

171
 Ordre de grandeurs pour la
complexité

 La complexité d’un algorithme est considérée

d’un point de vue ordre de grandeur et pas
en terme de complexité exacte.
 On utilise généralement les Notation de
landau
–
–
–

172
 Exemple

O :
– n = O(n), 2n = O(3n), n+2 = O(n), pn = O(n),
– log(n) = O(n),
– n = O(n2).
o :
– Racine(n) = o(n), n = o(n2),
– log(n) = o(n), log(n) = o(racine(n)).
 : n+log(n) = (n+racine(n)).

173
 Illustration:
Algorithme du tri par
sélection

174
 L’algo

 Idée très simple:

– Parcourir le tableau,
– Détecter l’élément le plus petit
– Mettre cet élément à la position 0 (en fait
échanger son indice avec celui qui est
initialement à l’indice 0)
– Refaire le même traitement pour le deuxième
élément le plus petit et l’indice 1
– Continuer ainsi jusqu’à épuisement du tableau

175
 (

Etude de complexité:
tableau de taille n
 Pour j  0 à n-2
posmini j c1 n-1
Pour i  j + 1 à n-1
Si t(i) < t(posmini) Alors
posmini  i c2
Finsi
i suivant
temp  t(posmini) c4 n-1
t(posmini)  t(j) c5 n-1
t(j)  temp c6 n-1
j suivant c7 n-1
 C_boucle(j) = nbre d’exécution de l’instruction pour un i donné

 Complexité =
176
 (

Complexité au meilleur cas

 Le meilleur cas se présente si le tableau est

déjà trié
 Dans ce cas,
– C_boucle(j)=0
– La complexité est de:
 T(n)=

 T(n)est de la forme an+b

 C’est une complexité linéaire

177
 Complexité au pire

 La pire situation se présente quand le

tableau est trié dans le sens inverse
 Dans ce cas
– C_boucle(j)= n-j-1
 On retrouve sachant que

– T(n)=
 Complexité de la forme ax^2+bx+c : complexité
178 quadratique
 Complexité en moyenne

 En moyenne, on peut avancer que pour un j

donné, on va retrouver la moitié des valeurs
plus grandes et l’autre plus petites
 Dans ce cas: C_boucle(j)= |j/2|
 En remplaçant cette valeur dans l’équation,
on retrouve aussi une complexité
quadratique

179
 Ordre de grandeur

 En se référant aux ordres de grandeur, on

retrouve, pour l’algorithme de tri par
sélection:
– Complexité au mieux: (n)
– Complexité au pire: (n^2)
– Complexité en moyenne: (n^2)

180
 Autres classes des complexités
 Les algorithmes usuels peuvent être classés en un certain nombre
de grandes classes de complexité :
– Les algorithmes sub-linéaires : O(log n)
– Les algorithmes linéaires: O(n)
– Les algorithmes polynomiaux en O(n^k) pour k > 2
– Exponentiels: la complexité est supérieure à tout polynôme en n)
 Les algorithmes linéaires et sub-linéaires sont considérés comme
rapides
 Les algorithmes polynomiaux sont considérés comme lents
 Les algorithmes exponentiels sont considérés comme très lents et
impraticable au-delà d’une taille des données supérieure à quelques
dizaines d’unités.
181
 THE END

182