les outils informatiques

Quels sont les outils informatiques à maîtriser:

les outils informatiques Les outils informatiques à maîtriser sont les
suivants :
⚫ Algorithmique
⚫ Offices ( PowerPoint, Word, Excel
⚫ Les Langages de programmation
⚫ Internet
⚫ La Messagerie Électronique
⚫ Etc

LA LOGIQUE ALGORITHMIQUE
DEFINTION :
L’expression algorithmique permet de dégager
les principes de construction d’un programme
Cours d’Algorithmique quel que soit l’environnement logiciel de sa mise
en œuvre.
OBJECTIFS :
⚫ Identifier les données utilisées dans un
algorithme (type, constante, variable)
⚫ Identifier la structure d’un algorithme
(séquence alternative, répétitive)

1
 Pourquoi un cours d’ "Algo" ?
Objectif
⚫ Objectif : Apprendre les concepts de base de ⚫ Etre capable de mettre en œuvre les
l'algorithmique et de la programmation concepts pour analyser des problèmes et
écrire les programmes correspondants
⚫ Problème : expliquer à la «machine» comment elle ⚫ savoir expliciter son raisonnement
doit s'y prendre
Mais... comment le lui dire ? ⚫ savoir formaliser son raisonnement
Comment le lui apprendre ? ⚫ concevoir et écrire des algorithmes :
Comment s'assurer qu'elle fait ce travail aussi - séquence d’instructions qui décrit comment résoudre
bien que nous ? un problème particulier
Mieux que nous? - Algorithme = suite d’actions que devra effectuer un
automate pour arriver à partir d’un état initial, en un
temps fini et afficher un résultat

Objectif
Plan du cours
➢ Un algorithme sert à transmettre un savoir faire.
➢ Il décrit les étapes à suivre pour réaliser un travail. • Généralités (matériel Informatique,
systèmes d’exploitation, langages de
➢ Il permet d'expliciter clairement les idées de solution programmation, …)
d'un problème indépendamment d'un langage de
programmation.
➢ L'utilisateur d'un algorithme n'aura qu'à suivre • Algorithmique (variables, affectations,
toutes les instructions, dans l'ordre pour arriver au instructions conditionnelles, instructions
résultat que doit donner l'algorithme. itératives, tableaux, fonctions, procédures,
structures, fichiers…)

2
 Domaines de l’informatique
⚫ Domaine du matériel (hardware) Informatique?
• partie physique de l’ordinateur ⚫ Techniques du traitement automatique de l’information au
• composants constituant un ordinateur moyen des ordinateurs (Science de Traitement automatique de
l’Information)
(microprocesseur …)
• support du traitement de l’information (disque dur …) ⚫ Éléments d’un système informatique
Applications
⚫ Domaine du logiciel (software) (Word, Excel, PowerPoint, Jeux, Maple, etc.)
• instructions expliquant à l’ordinateur comment traiter Langages
un problème (Java, C/C++, Fortran, Cobol, PL/1, Pascal, MatLab etc.)
• Cela nécessite de décrire des : algorithmes et Système d’exploitation
représentations informatiques de ces instructions pour (DOS, Windows, OS, Unix, Linux, IOS, etc.)
aboutir à un programme Matériel
(PC HP, IBM, Macintosh, Bull, station SUN, etc.)

Informatique? Informatique : L’ordinateur

⚫Computer Science
⚫ Machine qui permet de traiter de l’information :
⚫INFORMATIQUE ? (en anglais) • d’acquérir et de conserver de l’information
(acquisition, stockage)
• d’effectuer des traitements (calcul),
⚫INFORMATION ⚫AUTOMATIQUE
• de restituer les informations stockées (restitution)
⚫Science de l’information
⚫Art d’entraîner automatiquement des actions ⚫ Permet de lier «information»  «données» (0
ou 1)
⚫Traitement automatique de l’information ⚫ Différents types d’informations : valeurs
⚫Machine automatique
⚫ORDINATEUR
numériques, textes, images, sons, …: tout cela
avec des 0 ou 1

3
Informatique : Traitement de l’information Informatique : L’ordinateur / l’homme
⚫ Raison du remplacement :
⚫Schéma de principe du traitement de l’information • Vitesse (pour des opérations « bas niveau »)
• Fiabilité (répétitivité)
⚫Données à l’état brut
• Mémoire
⚫ENTREE
• Coût
⚫Données Traitées
Résultats ⚫ 2 types d’ « informaticiens »
⚫TRAITEMENT
⚫Par ordinateur • les utilisateurs des outils informatiques
⚫SORTIE
• les concepteurs de ces outils

Informatique? Structure des ordinateurs

⚫Saisie ⚫Traitement ⚫Restitution

Informatique
⚫Instructions
⚫UC ⚫Résultats
⚫Données

⚫Mémoire
Conception Utilisation

⚫Périphériques d’entrée
Matériel Logiciel Technologie Processus ⚫Périphériques de sortie
⚫Mémoires auxiliaires

Développement ⚫Carte
⚫Scanner ⚫Micro ⚫Souris ⚫DVDR
Architectures Méthodologies Données Utilisateurs perforée ⚫Disquette ⚫Clé USB ⚫Ecran
⚫Modem
& Langages

⚫CD-ROM
⚫Modem ⚫Caméra ⚫Bande
⚫Clavier ⚫Disque dur Magnétique
⚫Imprimante
⚫Haut parleur

4
Structure de l’ordinateur Schéma d’une configuration informatique
⚫Carte vidéo ⚫Unité Centrale
(cerveau)
⚫Unité de Traitement
⚫Disque
⚫Ecran ⚫Mémoire ⚫Unité de Commande
⚫Dur
⚫et de Contrôle
⚫Centrale
⚫Clavier
⚫Unité Arithmétique
⚫Unité de ⚫Disquette
⚫et Logique
⚫Souris ⚫traitement
⚫Mémoire
⚫CDROM ⚫Périphériques Centrale
⚫Haut- ⚫Périphériques
d’Entrées de Sorties
⚫parleurs ⚫Unité Centrale

⚫Carte son ⚫Périphériques d’Entrées/Sorties

⚫Périphériques de communication ⚫Unités d’échange ⚫Informations ⚫Mémoires Auxiliaires
⚫Commandes
⚫Périphériques de mémorisation ⚫Bus

Vue d’ensemble de l’ordinateur Vue d’ensemble de l’ordinateur:

Carte mère : Unité Centrale
⚫Alimentation ⚫Ventilateur du CPU
⚫Lecteur CD/DVD ⚫Processeur ⚫Mémoire SDRAM
(barrettes)

⚫Disque dur ⚫Portssérie ⚫Bus IDE

⚫Carte mère (COM) (disque dur)

⚫USB

⚫Carte
graphique ⚫Slot AGP ⚫Pile
(carte graphique) (alimente l’horloge)

⚫Carte PCI ⚫Slots PCI

(son, réseau, …) (carte son, réseau)
⚫Mémoire BIOS
(paramétrise la carte)

5
L’unité centrale Le processeur (CPU)
⚫Supports de barrettes ⚫Séquenceur d ’instructions
⚫Connecteurs de souris et clavier ⚫de mémoires ⚫Interface du bus d ’instructions

⚫Connecteurs de contrôleur
⚫de disquettes et disque dur ⚫Décodeur d ’instructions

⚫Unité de traitement
⚫Emplacements de
⚫Unité arithmétique et logique
⚫cartes d ’extensions

⚫Registres:
⚫Batterie

⚫Unité de contrôle ⚫Unité de détection d’erreurs

⚫Puce du BIOS ⚫CPU

Les bus

Matériel: Principaux éléments d’un PC

⚫ Unité centrale (le boîtier)

• Processeur ou CPU (Central Processing Unit)
• Mémoire centrale
• Disque dur, lecteur disquettes, lecteur CD-ROM
• Cartes spécialisées (cartes vidéo, réseau, ...)
• Interfaces d'entrée-sortie (Ports série/parallèle, …)

⚫ Périphériques
• Moniteur (l'écran), clavier, souris
• Modem, imprimante, scanner, …

6
Les bus
⚫Ecran ⚫Mémoire ⚫Disque
Quelques types de microprocesseurs
⚫Centrale ⚫Dur
⚫Clavier  Intel: Core, Pentium, Celeron, Xeon, Itanium …
⚫Disquette
⚫Souris
⚫Unité de  AMD: Athlon, Opteron, Turion …
⚫traitement
 Motorola
⚫CDROM
⚫Haut-  Aeroflex
⚫Unité Centrale ⚫DVDROM
⚫parleurs
 Atmel
⚫ Permettent de faire le lien entre les  Microchip
différentes unités d’un ordinateur  etc.
⚫ représente le chemin utilisé par les
informations pour aller d’une unité à l’autre

Unités de Mesure
Types de Mémoire Principale
 ROM  Fréquence du processeur
◼ mémoire morte (ne peut pas être modifiée) ◼ Nombre d’opérations effectuées en une
◼ utilisée pour le BIOS (basic input output seconde par le processeur exprimée en hertz
system): programme de base pour lancer (Ghertz, Giga hertz)
l’ordinateur  Unités d’Affichage
 RAM ◼ Nombre de pixels par pouce pour l’affichage
◼ mémoire vive (peut être modifiée) sur écran. 1 pouce=2,54 cm. La qualité est
◼ SDRAM meilleure si le nombre d’affichage par pouce
est élevè.
◼ DDR
◼ DR-SDRAM

7
Unités de Mesure Qu’est ce qu’un système d’exploitation SE
ou operating system OS ?
 Unités FPS ⚫ Ensemble de programmes qui dirige l'utilisation
des ressources matériel d'un ordinateur par
◼ Nombre d’images affichés par seconde FPS des logiciels applicatifs:
(Frames per second sur un écran d’ordinateur . • Gestion des périphériques (affichage à l'écran, lecture du
clavier, pilotage d’une imprimante, …)
 Unités d’impression
◼ Nombre de pages imprimés par minutes (ppm). • Gestion des utilisateurs et de leurs données (comptes,
partage des ressources, gestion des fichiers et répertoires, …)
 Unités de transfert
◼ Transfert des volumes des données dans le
• Interface avec l’utilisateur (textuelle ou graphique):
Interprétation des commandes
domaine des réseaux et connexions internet
bit/s (bits par seconde ou bps) • Contrôle des programmes (découpage en taches, partage
du temps processeur, …)

Fonctionnalités d’un système d’exploitation

Exemples des Systèmes d’Exploitation
 exemples:
◼ Windows (dans toutes ses variétés)
◼ Linux
◼ Unix

◼ Mac OS

◼ OS/2
◼ MS-DOS
 pourquoi un système d’exploitation?
◼ sans système d’exploitation, on ne peut charger et exécuter qu’un
seul programme à la fois
Le système d'exploitation est un intermédiaire entre les logiciels
d'application et le matériel. ◼ si on n’a pas de système d’exploitation, chaque programme doit
avoir toutes les routines nécessaires pour accéder aux
composantes matérielles de l’ordinateur

8
 Systèmes d’Exploitation Systèmes d’Exploitation
 trois composantes
◼ le noyau: interagit avec les composantes matérielles
 accès aux disques durs, CD, etc.  quelques considérations …
 gestion de la mémoire
 ordonnancement des tâches
◼ convivialité
accès réseau

◼ robustesse, stabilité et fiabilité
◼ librairies de fonctions qui peuvent être appelées par d’autres
programmes ◼ gestion des tâches en temps réel
 créer des fenêtres à l’écran
 détecter un mouvement de souris
 envoyer un fichier à une imprimante
 etc.
◼ programmes de base pour gérer des fichiers et configurer le
système
 Internet Explorer: une partie du système d’exploitation Windows ou
non?

Langages informatiques Langage machine

⚫ Dans les domaines de l'automatisme, de
⚫ Un langage informatique est un outil permettant de l'électronique et de l'informatique, nous utilisons la
donner des ordres (instructions) à la machine base 2 (0 et 1)
❑ Un interrupteur est ouvert ou fermé
• A chaque instruction correspond une action du processeur
❑‰Une diode est allumée ou éteinte
⚫ Intérêt : écrire des programmes (suite consécutive ❑‰Une tension est présente ou absente
d’instructions) déstinés à effectuer une tache donnée ❑‰Une surface est réfléchissante ou pas (CD)
• Exemple: un programme de gestion de comptes bancaires ❑‰Un champ magnétique est orienté Nord-Sud ou
Sud-Nord (disque dur)
⚫ Contrainte: être compréhensible par la machine A chaque état du système technologique, on
associe un état logique (binaire).
 Un bit (binary digit) = 0 ou 1 (2 états électriques)

9
Langage machine : Codage Langage machine
⚫ Langage binaire: l’information est exprimée et manipulée sous
forme d’une suite de bits

⚫ Un bit (binary digit) = 0 ou 1 (2 états électriques)

⚫ Une combinaison de 8 bits= 1 Octet ➔ 28 = 256 possibilités qui permettent

de coder tous les caractères alphabétiques, numériques, et symboles tels que ?,*,&, …

• Le code ASCII (American Standard Code for Information Interchange) donne les
correspondances entre les caractères alphanumériques et leurs
représentation binaire, Ex. A= 01000001, ?=00111111

⚫ Les opérations logiques et arithmétiques de base (addition,

multiplication, … ) sont effectuées en binaire

INFORMATIQUE = Organisation de la Mémoire

Information + Traitement de cette Information  bit: la plus petite unité (valeur de 0 ou 1)
 groupes de bits
◼ quartet (nibble): 4 bits
8 = 1000 8+9 1000 ◼ octet (byte): 8 bits correspond à un caractère
9 = 1001 + 1001 ◼ mot (word): 16 bits
----- ◼ long mot (long word): 32 bits
Binaire
10001
Le sens d’un bit dépendra de son contexte d’utilisation
D’où la nécessité d’établir des standards

10
 Information Binarisée: Ecriture,
Organisation de la Mémoire Nombres, Images, Sons
 par convention … ⚫ La valeur d’un mot binaire dépend du contexte
d’utilisation: mot, images, sons,...
◼ 1 octet (O) 8 Bits 1 Caractère
⚫ On vise la standardisation
◼ 1 kilo-octet (Ko) 103 octet = 1000 Octets
⚫ Ecriture = Code ASCII
◼ 1 méga-octet (Mo) 106 octets = 1000 Ko
◼ 1 giga-octet (Go) 109 octets = 1000 Mo
• Sur 7 bits --> 128 caractères, Sur 8 bits --> 256
caractères, par ex. «a» = 1100001
1 Téra-octet (To) 1012 octets = 1000 Go
◼
• Equivalence Bytes (8 bits) --> Texte
• 1.4 MBytes = 500 pages (1 page = 3000 char)

les nombres entiers Codage binaire: les nombres entiers

⚫ Codage binaire des nombres ⚫ La clé: comment interpréter les bits?

• Entiers non-signés: • Supposons des chiffres entiers non signés codés sur 8
• Sur 8 bits: bits
Position 8 7 6 5 4 3 2 1
• De 0 à 255 = 256 valeurs en tout (28)
• Sur 16 bits: Signific. 27 26 25 24 23 22 21 20

• De 0 à 65535 = de 0 à 216-1 Valeur 128 64 32 16 8 4 2 1

• Sur 32 voire 64 bits? • Exemples:

• Quel est le plus grand entier codé sur 32 bits? 00000000 = 0
• 232-1 = [Link] 00000001 = 1
• Et sur 64 bits? 10000000 = 128
• 264-1 01010101 = 85 = 0x128+1x64+0x32+1x16+0x8+1x4+0x2+1x1
11111111 = 255 = 1x128+1x64+1x32+1x16+1x8+1x4+1x2+1x1

11
 les nombres entiers les nombres entiers

⚫ Arithmétique élémentaire: l’addition d’entiers

non signés
(ici codés sur 8 bits)

8 = 00001000
+ 9 = 00001001
----------------
= 17 = 00010001

les nombres entiers : Changement

de base : de la base 10 vers une les nombres entiers: Conversion d'un
base b nombre décimal (entier) en binaire
➢ La règle à suivre est les divisions successives :
o On divise le nombre par la base b
o Puis le quotient par la base b
o Ainsi de suite jusqu’à l’obtention d’un
quotient nul
o La suite des restes correspond aux
symboles de la base visée.
o On obtient en premier le chiffre de poids
faible et en dernier le chiffre de poids fort.

12
les nombres entiers: Conversion d'un les nombres entiers: Conversion d'un
nombre décimal (entier) en binaire nombre décimal (entier) en binaire
⚫ Méthode par soustraction : par exemple N=73 ⚫ Exercice : par exemple N=172

73 9
-64 -8
____ ____
09 1
73 (10) = 0100 1001 (2)

les nombres entiers: Conversion d'un les nombres entiers

nombre décimal (entier) en binaire
⚫ Exercice : par exemple N=175 ⚫ Exemple : (25)10 en binaire
25 / 2 = 12 reste 1
12 / 2 = 6 reste 0
175 2 175 47 15 7 3
1 87 2 - 128 - 32 - 8 - 4 - 2 6 / 2 = 3 reste 0
1 43 2 47 15 7 3 1 3 / 2 = 1 reste 1
1 21 2
1 10 2 1 < 2 donc on arrête
0 5 2 Résultat : (11001)2
1 0 1 0 1 1 1 1
1 2 2
0 1 2
1 0
175=10101111
175=128+32+8+4+2+1

13
 les nombres entiers :Opérations les nombres entiers : arithmétique
usuelles en binaire
élémentaire
Travaillons avec 4 bits
les deux opérations binaires de base sont
0011(3) 1010(10)
⚫ l'addition
+0010(2) +1100(12)
⚫ la multiplication ______ _________________

= 0101 = 0110

(impossible, overflow car le bit significatif est différent des

deux nombres ---> détection très facile des overflows)

les nombres entiers : Produit logique en les nombres entiers : arithmétique

binaire élémentaire

14
les nombres entiers les nombres entiers : Codage des
entiers relatifs -code complément à 1
⚫ Le bit le plus significatif est utilisé pour
représenter le signe du nombre :
➢ si le bit le plus fort = 1 alors nombre négatif
➢ si le bit le plus fort = 0 alors nombre positif
⚫ Les autres bits codent la valeur absolue du
nombre
⚫ Exemple : Sur 8 bits, codage des nombres -24
et -128 en (bs)
➢ -24 est codé en binaire signé par : 1 0 0 1 1 0 0 0 (bs)
➢ -128 hors limite ➔ nécessite 9 bits au minimum

les nombres entiers : Codage des les nombres entiers : Codage des
entiers relatifs -code complément à 2 entiers relatifs -code complément à 2

Exemples:
1-Comment écrit-on N = -15 (5 bits + 1 bit de signe) ?
⚫ |N| = 15 = 001111(2) => 110000 (Cà1) =>
-15 ≡ 110000(Cà1) +000001(2) = 110001 (2)

2-Comment écrit-on -35 (6 bits + 1 bit de signe) ?

⚫ |N| = 35 = 0100011 (2) => 1011100 (Cà1) =>

-35 ≡ 1011100 (Cà1) + 0000001 (2) = 1011101 (2)

15
 les nombres entiers : Codage des les nombres entiers : Codage des
entiers relatifs en Binaire entiers relatifs -code complément à 2
⚫ Les nombres sont codés sur 8 bits
⚫ On veut coder -50 sur 8 bits, la plage des nombres est de - 27 à 27 -1 Addition avec retranchement de la retenue :
soit de -128 à 127. ⚫ Considérons un exemple un peu plus élaboré que le lecteur est
Première méthode : - 50 + 28 = -50 + 256 = 206 invité à détailler : Termes Écriture binaire sur 16 bits Complément à 2
on code 206 en binaire : 11001110 au nombre - 50 on fait correspondre
11001110
Deuxième méthode : c'est la méthode qu'utilisent les ordinateurs
au niveau langage machine

50 est représenté par : 00110010

- on applique le complément à 1 : 11001101 ⚫ Aussi étonnant que cela puisse sembler, le simple retranchement
( c'est le "négatif" au sens photographique du nombre précédent) du 17e bit a pour effet de rendre le résultat correct dans le cas du
complément à 2.
- on applique le complément à 2 : 11001101 + 1 = 11001110

Conversion d’un nombre décimal Conversion réel décimal en base B

réel en base B
⚫ Pour la partie entière: ⚫Exemple : conversion de 12,6875 en binaire
➢Utiliser la méthode de la division entière comme pour les
entiers ➢ Conversion de 12 : donne (1100)2
⚫ Pour la partie fractionnaire: ➢ Conversion de 0,6875:
➢ Multiplier la partie fractionnaire par B
➢ Noter la partie entière obtenue ➢ 0,6875 x 2 = 1,375 = 1 + 0,375
➢ Recommencer cette opération avec la partie fractionnaire
du résultat et ainsi de suite
0,375 x 2 = 0,75 = 0 + 0,75
➢ Arrêter quand la partie fractionnaire est nulle
0,75 x 2 = 1,5 = 1 + 0,5
✓ Ou quand la précision souhaitée est atteinte 0,5 x2=1 =1+0
✓ Car on ne peut pas toujours obtenir une conversion en
un nombre fini de chiffres pour la partie fractionnaire ➢ (12,6875)10 = (1100,1011)2
➢ La partie fractionnaire dans la base B est la concaténation
des parties entières obtenues dans l'ordre de leur calcul

16
 Conversion réel décimal en base B Codage et calcul de nombres à
virgule flottante (floating-point)
⚫Exemple : conversion de 14,375 en binaire 1 8 23
➢ Conversion de 14 : 32 bits
➢ Conversion de 0,375:
signe
➢Conversion de 14 : donne (1110)2
➢ Conversion de 0,375 Exposant Mantisse

0,375 x 2 = 0,75 = 0 + 0,75 En général, les nombres sont représentés après la

0,75 x 2 = 1,5 = 1 + 0,5 virgule: 0.32 107. On peut aller jusque 1038 (en 64
bits, 2127), après c’est NaN (Not a Number).
0,5 x2=1 =1+0
(14,375)10 = (1110, 011)2

Codage des nombre réels en virgule Codage des nombres réels en virgule
flottante flottante
⚫ Principe et intérêts ⚫ Exemple : 1234,5 en base 10
⚫ Avoir une virgule flottante et une précision limitée
⚫ Ne coder que des chiffres significatifs ➢On normalise pour n'avoir que des chiffres après la virgule
:

N = nombre codé
➢ ➢Mantisse codée = 12345, exposant = 4, signe = +
M = mantisse : nombre de X chiffres de la base B
➢
➢ E = exposant : nombre de Y chiffres de la base B ⚫Standard IEEE 754 : codage binaire de réels en virgule
➢ +/- = codage du signe : positif ou négatif
flottante
➢ Précision simple : 32 bits:
⚫ Le nombre est présenté sous forme normalisée pour
déterminer la mantisse et exp. 1 bit de signe, 8 bits exposant, 23 bits mantisse
➢ Pas de chiffre avant la virgule : ➢ Précision double : 64 bits :
1 bit de signe, 11 bits exposant, 52 bits mantisse

17
Codage hexadécimal Codage hexadécimal

⚫La manipulation des nombres écrits en binaire ⚫Les règles sont ici aussi les mêmes que pour le
est une opération fastidieuse en raison de la taille décimal
des codes obtenus. Il serait donc judicieux
d'utiliser un autre système qui permet de réduire
la longueur de ces codes. C'est pourquoi nous
utilisons de préférence le système hexadécimal
(base 16).

Correspondance entre binaire et Correspondance entre binaire et

hexadécimal hexadécimal
⚫La conversion du binaire en hexadécimal est ⚫La méthode par divisions s'applique comme
très simple, c'est d'ailleurs la raison pour en binaire (exemple : N = 2623).
laquelle nous utilisons cette base. Il suffit de
faire correspondre un mot de quatre bits
(quartet) à chaque chiffre hexadécimal.
Conversion d'un mot de 16 bits entre binaire
et hexadécimal

18
Correspondance entre binaire et Les langages de programmation:
hexadécimal Assembleur
⚫ Problème: le langage machine est difficile à comprendre par l'humain
⚫ Exemple : N = 7254
⚫ Idée: trouver un langage compréhensible par l'homme qui sera
ensuite converti en langage machine
7254 (10) = 1C56 (16) • Assembleur (1er langage): exprimer les instructions élémentaires
de façon symbolique

ADD A, 4
traducteur langage machine
LOAD B
MOV A, OUT
…
• +: déjà plus accessible que le langage machine
• -: dépend du type de la machine (n’est pas portable)
• -: pas assez efficace pour développer des applications complexes

 Apparition des langages évolués

Langages haut niveau Compilateur/interpréteur

⚫ Compilateur: traduire le programme entier une fois pour toutes
⚫ Intérêts multiples pour le haut niveau:
• proche du langage humain «anglais» (compréhensible) exemple.c
Compilateur
exemple
exécution
• permet une plus grande portabilité (indépendant du matériel) fichier source fichier exécutable
• Manipulation de données et d’expressions complexes (réels, • + plus rapide à l’exécution
objets, a*b/c, …) • + sécurité du code source
⚫ Nécessité d’un traducteur (compilateur/interpréteur), • - il faut recompiler à chaque modification

exécution plus ou moins lente selon le traducteur ⚫ Interpréteur: traduire au fur et à mesure les instructions du
programme à chaque exécution
Code source Compilateur ou Interprétation+exécution
Langage machine [Link]
en langage évolué fichier source
interpréteur
• + exécution instantanée appréciable pour les débutants
• - exécution lente par rapport à la compilation

19
 Historique de langage de Historique de langage de
programmation programmation
⚫ 3ème génération
⚫ 1ère génération (Code machine) • FORTRAN, COBOL, ALGOL-60, PASCAL, MODULA-2, PL1, C,
• F0 00 A0 B8 20 …. •
ADA, BASIC, SIMULA
Soutiennent la notion d’algorithme

⚫ 4ème génération
• Langage applicatif
⚫ 2ème génération (Assembleur) • SQL, GUI, …
• LDA #$00 5ème génération
• STA $B820
⚫
• I.A.
• PROLOG

⚫ Langages Orientés Objet (00)

• EIFFEL, C++, Python, ..

Classification des Languages de Classification des Languages de

Programmation I Programmation II
Tous les Languages
de Programmation ⚫ Programmation Procedurale: Le programme est
Languages Languages
divises en blocs qui peuvent contenir leurs propres variables
Imperatifs Declaratifs ainsi que d ’autres blocs.
Programmation Programmation Programmation Programmation Programmation
Procedurale Orientee Objets Concurrente Fonctionelle Logique ⚫ Programmation Orientee Objet: Programmation qui
Ada, Pascal, C C++, Java Ada 95 LISP, SCHEME PROLOG
supporte l ’interaction d ’objets. Un objet contient des
Languages Imperatifs: Languages incluant des moyens pour le donnees ainsi que des fonctions qui peuvent s ’appliquer a
programmeur d ’attribuer des valeurs a des locations en memoire. ces donnees.

Languages Declaratifs: Languages pour lesquels le programmeur ⚫ Programmation Concurrente: Languages de

reflechit en terme de valeurs des fonctions et de relations entre
programmation qui s ’appliquent a plusieurs CPU ’s qui
entites diverses. Il n ’y a pas d ’attribution de valeurs aux variables.
operent en parallele. Les donnees peuvent etre partagees ou
non.
79 80

20
Classification des Languages de
Programmation III Langages de programmation:

⚫ Programmation Fonctionnelle: Un programme est

un appel de fonction avec un certain nombre de ⚫ types de langages:
paramètres, qui eux-mêmes peuvent être des appels • Langages procéduraux :

d ’autres fonctions. Le programme renvoie donc un • Fortran, Cobol, PL/ 1, Pascal, Basic, C, …
• Langages orientés objets
seul résultat, qui peut-être assez complexe (exemple: • ADA, C++, Java, MatLab
une nouvelle fonction). • Langages de programmation Evénementielle
⚫ Programmation Logique: Un programme consiste • Visual Basic, Visual C++, DELPHI, Visual J++
en une série d ’axiomes, de règles de déduction et
en un théorème a prouver. Le programme renvoie la ⚫ Choix d’un langage?
valeur « vrai » si les axiomes supporte le théorème. Il
renvoie la valeur « fausse » autrement.
81

Etapes de réalisation d’un programme

AGL:
⚫Étude
préliminaire ⚫ Étapes de mise en oeuvre d'un logiciel
1. Comprendre le problème
⚫ Un atelier de génie logiciel (noté AGL ou en 2. Concevoir l’algorithme
⚫Analyse
• Faire la trace pour valider l'algorithme
anglais Case, pour Computer Aided Software fonctionnelle 3. Coder l’algorithme
Environment) est un ensemble d'outils structurés • Traduire l’algorithme en langage de
programmation
permettant la conception, le développement et la 4. Éditer le programme
réalisation de logiciels. ⚫Conception • Saisir le programme sur ordinateur
de système
5. Compiler le programme
6. Faire l’édition des liens
⚫ Exemples d’AGL: • Ajout au programme des éléments de la
⚫Mise en librairie
• WinDev, œuvre du
système
7. Exécuter le programme
• Visual Studio, 8. Vérifier et valider le programme
• PowerAMC
⚫Entretien du
système

21
 Etapes de réalisation d’un programme
Enoncé du problème
Spécification

Algorithmique
Cahier des charges
Analyse
Algorithme
Traduction en langage
Programme source
Compilation
Programme exécutable
Tests et modifications
Version finale et résultats

La réalisation de programmes passe par l’écriture d’algorithmes

 D’où l’intérêt de l’Algorithmique

Comment présenter un algorithme de

façon structurée
Algorithmique
⚫ Le terme algorithme vient du nom du mathématicien arabe
Al-Khawarizmi (820 après J.C.)
⚫ On doit retrouver les 4 éléments suivants
⚫ Un algorithme est une description complète et détaillée des actions à
• Description de l'algorithme
effectuer et de leur séquencement pour arriver à un résultat donné • Texte décrivant ce que fait l'algorithme
• Intérêt: séparation analyse/codage (pas de préoccupation de syntaxe)
• Constantes utilisées
• Qualités: exact (fournit le résultat souhaité), efficace (temps d’exécution, • Liste des constantes (étiquette et valeur)
mémoire occupée), clair (compréhensible), général (traite le plus grand
nombre de cas possibles), … • Variables utilisées
L’algorithmique désigne aussi la discipline qui étudie les algorithmes
• Liste des variables (étiquette et valeur)
• Logique de l'algorithme
⚫
et leurs applications en Informatique

⚫ Une bonne connaissance de l’algorithmique permet d’écrire des

• La description détaillée des opérations réalisées par
algorithmes exacts et efficaces l'algorithme

22
Passage de l'algorithme au programme
Représentation d’un algorithme
⚫ L'algorithme décrit la logique nécessaire pour Historiquement, deux façons pour représenter un algorithme:
résoudre un problème • L’Organigramme: représentation graphique avec des symboles
⚫ Le programme implante l'algorithme dans un (carrés, losanges, etc.)
• offre une vue d’ensemble de l’algorithme
langage cible • représentation quasiment abandonnée aujourd’hui
⚫ Éléments à considérer lors du passage de la
• Le pseudo-code: représentation textuelle avec une série de
structure d'algorithme au programme conventions ressemblant à un langage de programmation (sans
• Déclaration des variables et des constantes les problèmes de syntaxe)
• plus pratique pour écrire un algorithme
• Lecture des données • représentation largement utilisée

• Écriture de l'algorithme
• Affichage des résultats

Représentation d’un algorithme

Exemple 1 : Algorithme d'Euclide
Donné ci-après sous forme d'organigramme (ou ordinogramme), l'algorithme 'Euclide
permet de trouver le plus grand diviseur commun de deux nombres (A > B).

Algorithmique

Notions et instructions de base

23
 ⚫L’ALGORITHME

⚫L’algorithme est l’outil normalisé de l’analyse. Il permet de décrire précisément la succession logique
Algorithme
des actions nécessaires au traitement, en vue de programmations en langages appropriés.
⚫ Le "langage algorithmique" que nous utilisons est un
⚫Déclaration de l’algorithme.
⚫Déclaration
constantes.
des variables et des compromis entre un langage naturel et un langage de
⚫Début.

⚫Entrées : Elles ont pour but d’affecter les programmation.

variables de valeurs provenant de saisies.
⚫Les saisies sont précédées d’affichages
de messages explicatifs.
⚫ Nous présentons les algorithmes comme une suite

⚫Traitements avec structure alternative : d'instructions dans l'ordre des traitements. Ils sont
⚫Ils permettent d’exécuter des actions

⚫
obéissant à une ou plusieurs conditions
déterminées.
toujours accompagnés d'un lexique qui indique, pour
⚫Les conditions font intervenir des opérateurs chaque variable, son type et son rôle.
de comparaison : < <= = > >= <>
⚫ Nous manipulerons les types couramment rencontrés
⚫Le symbole  représente l’opérateur
d’affectation.
⚫Sorties : Elles ont pour but d’afficher des dans les langages de programmation : entier, réel,
résultats de traitements précédés de messages
explicatifs. Il est possible d’y inclure des
données entrées que l’on désire retrouver telles booléen, caractère, chaîne, tableau et type composite.
quelles en sorties.
⚫Fin.

⚫ 6/8

Formalisme
⚫ Un algorithme doit être lisible et compréhensible
⚫ Il doit donc suivre des règles. Il est composé d'une Introduction à l’Algorithmique
entête et d'un corps. ⚫ Un algorithme, c’est une suite d’instructions, qui une fois exécutée
✓L'entête comprend : correctement, conduit à un résultat donné.
- Nom : le nom de l'algorithme ⚫ un algorithme doit donc contenir uniquement des instructions
compréhensibles par celui qui devra l’exécuter.
- Rôle : ce que fait l'algorithme
⚫ Enfin, les ordinateurs ne sont capables de comprendre que quatre
- Données : les données fournies à l'algorithme familles d'instructions sont :
- Résultat : ce que l'on obtient à la fin du traitement ➢ l’affectation de variables
- Principe : le principe utilisé dans l'algorithme ➢ la lecture / écriture

✓Le corps : ➢

➢
les tests
les boucles
- il est délimité par les mots clés début et fin.
- il se termine par un lexique, décrivant les variables utilisées

24
Notion de variable Choix des identificateurs
⚫ Dans les langages de programmation une variable sert à stocker Le choix des noms de variables est soumis à quelques règles qui
la valeur d’une donnée varient selon le langage, mais en général:
⚫ Un nom doit commencer par une lettre alphabétique
⚫ Une variable désigne en fait un emplacement mémoire dont exemple valide: A1 exemple invalide: 1A
le contenu peut changer au cours d’un programme (d’où le nom ⚫ doit être constitué uniquement de lettres, de chiffres et du
variable) soulignement _ (Eviter les caractères de ponctuation et les espaces)
valides: SMIP2007, SMP_2007 invalides: SMP 2005,SMI-2007,SMP;2007
⚫ Règle : Les variables doivent être déclarées avant d’être
⚫ doit être différent des mots réservés du langage (par exemple en
utilisées, elle doivent être caractérisées par : Java: int, float, else, switch, case, default, for, main, return, …)
• un nom (Identificateur)
⚫ La longueur du nom doit être inférieure à la taille maximale spécifiée
• un type (entier, réel, caractère, chaîne de caractères, …) par le langage utilisé

Choix des identificateurs Types des variables

Conseil: pour la lisibilité du code choisir des noms significatifs Le type d’une variable détermine l’ensemble des valeurs qu’elle peut
qui décrivent les données manipulées prendre, les types offerts par la plus part des langages sont:
⚫ Type numérique (entier ou réel)
exemples: TotalVentes2004, Prix_TTC, Prix_HT • Byte (codé sur 1octet): de 0 à 255
• Entier court (codé sur 2 octets) : -32 768 à 32 767
• Entier long (codé sur 4 ou 8 octets) : -2 147 483 648 à 2 147 483 647
Remarque: en pseudo-code algorithmique, on va respecter • Réel simple précision (codé sur 4 octets)
les règles citées, même si on est libre dans la • Réel double précision (codé sur 8 octets)

syntaxe ⚫ Type logique ou booléen: deux valeurs VRAI ou FAUX

⚫ Type caractère: lettres majuscules, minuscules, chiffres, symboles, …

exemples: ’A’, ’a’, ’1’, ’?’, …
⚫ Type chaîne de caractère: toute suite de caractères,
exemples: " Nom, Prénom", "code postale: 1000", …

25
Déclaration des variables L’instruction d’affectation
⚫ l’affectation consiste à attribuer une valeur à une variable
⚫ Rappel: toute variable utilisée dans un programme doit avoir
(ça consiste en fait à remplir où à modifier le contenu d'une zone mémoire)
fait l’objet d’une déclaration préalable
⚫ En pseudo-code, on va adopter la forme suivante pour la ⚫ En pseudo-code, l'affectation se note avec le signe ←
déclaration de variables Var← e: attribue la valeur de e à la variable Var
Variables liste d'identificateurs : type - e peut être une valeur, une autre variable ou une expression
⚫ Exemple: - Var et e doivent être de même type ou de types compatibles
Variables i, j,k : entier - l’affectation ne modifie que ce qui est à gauche de la flèche
x, y : réel ⚫ Ex valides: i ←1 j ←i k ←i+j
OK: booléen x ←10.3 OK ←FAUX ch1 ←"SMI"
ch1, ch2 : chaîne de caractères ch2 ←ch1 x ←4 x ←j
⚫ Remarque: pour le type numérique on va se limiter aux entiers (voir la déclaration des variables dans le transparent précédent)
et réels sans considérer les sous types ⚫ non valides: i ←10.3 OK ←"SMI" j ←x

Quelques remarques Exercices simples sur l'affectation

⚫ Beaucoup de langages de programmation (C/C++, Java, …) utilisent Donnez les valeurs des variables A, B et C après exécution
le signe égal = pour l’affectation ←. Attention aux confusions: des instructions suivantes ?
• l'affectation n'est pas commutative : A=B est différente de B=A
• l'affectation est différente d'une équation mathématique : Algorithme Affectation
Variables A, B, C: Entier
• A=A+1 a un sens en langages de programmation Début
• A+1=2 n'est pas possible en langages de programmation et n'est A←3
pas équivalente à A=1 B←7
A←B
⚫ Certains langages donnent des valeurs par défaut aux variables B ← A+5
déclarées. Pour éviter tout problème il est préférable d'initialiser les
C←A+B
variables déclarées
C←B–A
Fin

26
Exercices simples sur l'affectation Exercices simples sur l'affectation
Donnez les valeurs des variables A et B après exécution des
instructions suivantes ?
Algorithme Calcul_AB ⚫Ecrire un algorithme permettant d’échanger
Variables A, B : Entier les valeurs de deux variables A et B
Début
A←1
B←2
A←B
B←A
Fin

Les deux dernières instructions permettent-elles d’échanger les

valeurs de A et B ?

Exercices Échange de valeurs entre

deux variables
Exercices simples sur l'affectation
⚫ Problème de l'échange de chandails entre
deux individus A et B
Algorithme Echange_valeurs • Contrainte : une seule action à la fois

Variables A, B,C : Entier 1. A enlève le chandail et le pose sur une table

2. B enlève le chandail et le donne à A qui le met
Début 3. B prends le chandail sur la table et le met
C←A ⚫ Les chandails sont les valeurs à échanger
A←B ⚫ A et B sont les variables contenant les valeurs
à échanger
B←C ⚫ La table est une variable temporaire ou tampon

Fin

27
 Opérateur, opérande et expression
Exercices simples sur l'affectation
⚫ Quelles seront les valeurs des variables A et B ⚫ Un opérateur est un symbole d’opération qui
après exécution des instructions suivantes ? permet d’agir sur des variables ou de faire des
Algorithme Calcul_AB “calculs”
Variables A, B en Entier
Début ⚫ Une opérande est une entité (variable, constante ou
A←5 expression) utilisée par un opérateur
B←A+4
A←A+1
⚫ Une expression est une combinaison d’opérateur(s)
B←A–4 et d’opérande(s), elle est évaluée durant l’exécution
Fin de l’algorithme, et possède une valeur (son
interprétation) et un type

Expressions et opérateurs Priorité des opérateurs

⚫ Une expression peut être une valeur, une variable ou une
opération constituée de variables reliées par des opérateurs ⚫ Pour les opérateurs arithmétiques donnés ci-dessus, l'ordre de
exemples: 1, b, a*2, a+ 3*b-c, … priorité est le suivant (du plus prioritaire au moins prioritaire) :

⚫ L'évaluation de l'expression fournit une valeur unique qui est le • ^ : (élévation à la puissance)
résultat de l'opération • * , / (multiplication, division)
• % (modulo)
⚫ Les opérateurs dépendent du type de l'opération, ils peuvent être : • + , - (addition, soustraction)
• des opérateurs arithmétiques: +, -, *, /, % (modulo), ^ (puissance) exemple: 2+3*7 vaut 23
• des opérateurs logiques: NON, OU, ET, XOR
• des opérateurs relationnels: =,  , <, >, <=, >= ⚫ En cas de besoin (ou de doute), on utilise les parenthèses pour
• des opérateurs sur les chaînes: & (concaténation) indiquer les opérations à effectuer en priorité
⚫ Une expression est évaluée de gauche à droite mais en tenant exemple: (2 + 3) * 7 vaut 35
compte de priorités des opérateurs

28
 Exercices simples sur l'affectation Exercices simples sur l'affectation

⚫Que produit l’algorithme suivant ? ⚫Que produit l’algorithme suivant ?

Algorithme ABC
Variables A, B, C : chaine de caractères Algorithme ABC
Début Variables A, B, C : chaine de caractères
A ← "423" Début
B ← "12" A ← "423"
C ←A+B B ← "12"
Fin C ←A&B
Fin

Les instructions d'entrées-sorties:

# Lecture
ALGORITHMIQUE ⚫ Les instructions de lecture et d'écriture permettent à la machine de
communiquer avec l'utilisateur

⚫ La lecture permet d'entrer des donnés à partir du clavier

• En pseudo-code, on note: lire (var) ou Saisir (var)

la machine met la valeur entrée au clavier
dans la zone mémoire nommée var
Instructions d'entrées-sorties
• Remarque: Le programme s'arrête lorsqu'il rencontre une
instruction Lire et ne se poursuit qu'après la frappe d’une valeur
au clavier et de la touche Entrée

29
Les instructions d'entrées-sorties:
# Ecriture Exemple les instructions E/S
Ecrire un algorithme qui demande un nombre entier à l'utilisateur, puis
⚫ L'écriture permet d'afficher des résultats à l'écran (ou de les écrire qui calcule et affiche le double de ce nombre
dans un fichier)

• En pseudo-code, on note: écrire (var) ou Afficher (var)

Algorithme Calcul_double
la machine affiche le contenu de la variables A, B : entier
zone mémoire var Début
écrire("entrer le nombre ")
• Conseil: Avant de lire une variable, il est fortement conseillé
d’écrire des messages à l’écran, afin de prévenir l’utilisateur de lire(A)
ce qu’il doit frapper B ← 2*A
écrire("le double de ", A, "est :", B)
Fin

Exercice sur les instructions E/S

Exemple les instructions E/S
⚫ Quel résultat produit le programme suivant ? Ecrire un algorithme qui vous demande de saisir votre nom puis
votre prénom et qui affiche ensuite votre nom complet
Algorithme Val_Double
Algorithme Affichage_Nom_Complet
Variables Val, Double : Entier variables Nom, Prenom, Nom_Complet : chaîne de caractères
Début Début
Val ← 231 écrire("entrez votre nom")
Double ← Val * 2 lire(Nom)
écrire("entrez votre prénom")
Ecrire ("la valeur de Val = ", Val)
lire(Prenom)
Ecrire ("la valeur de Double = ", Double)
Nom_Complet ← Nom &" " & Prenom
Fin écrire("Votre nom complet est : ", Nom_Complet)
Fin

30
 Tests: instructions conditionnelles

ALGORITHMIQUE ⚫ Les instructions conditionnelles servent à n'exécuter une instruction

ou une séquence d'instructions que si une condition est vérifiée

⚫ On utilisera la forme suivante: Si condition alors

instruction ou suite d'instructions1
Sinon
instruction ou suite d'instructions2
Finsi
Instructions conditionnelles • la condition ne peut être que vraie ou fausse
• si la condition est vraie, se sont les instructions1 qui seront exécutées

• si la condition est fausse, se sont les instructions2 qui seront exécutées

• la condition peut être une condition simple ou une condition composée de
plusieurs conditions

Tests: instructions conditionnelles Exemple sur instructions conditionnelles

⚫ La partie Sinon n'est pas obligatoire, quand elle n'existe pas et que
Algorithme AffichageValeurAbsolue (version1)
la condition est fausse, aucun traitement n'est réalisé
Variable x : réel
• On utilisera dans ce cas la forme simplifiée suivante: Début
Ecrire (" Entrez un réel : “)
Si condition alors Lire (x)
instruction ou suite d'instructions1 Si (x < 0) alors
Finsi Ecrire ("la valeur absolue de ", x, "est:",-x)
Sinon
Ecrire ("la valeur absolue de ", x, "est:",x)
Finsi
Fin

31
Exemple sur instructions conditionnelles Exemple sur instructions conditionnelles

Ecrire un algorithme qui demande un nombre entier à l'utilisateur,

Algorithme AffichageValeurAbsolue (version2)
puis qui teste et affiche s'il est divisible par 3
Variable x,y : réel
Algorithme Divsible_par3
Début
Ecrire (" Entrez un réel : “) Variable n : entier
Lire (x) Début
Ecrire (" Entrez un entier : “)
y← x
Lire (n)
Si (x < 0) alors
y ← -x Si (n%3=0) alors
Ecrire (n," est divisible par 3")
Finsi
Ecrire ("la valeur absolue de ", x, "est:",y) Sinon
Ecrire (n," n‘est pas divisible par 3")
Fin
Finsi
Fin

Conditions composées

Tables de vérité
⚫ Une condition composée est une condition formée de plusieurs C1 C2 C1 ET C2 C1 C2 C1 OU C2
conditions simples reliées par des opérateurs logiques:
VRAI VRAI VRAI VRAI VRAI VRAI
ET, OU, OU exclusif (XOR) et NON
VRAI FAUX FAUX VRAI FAUX VRAI
⚫ Exemples : FAUX VRAI FAUX FAUX VRAI VRAI
• x compris entre 2 et 6 : (x > 2) ET (x < 6) FAUX FAUX FAUX FAUX FAUX FAUX

• n divisible par 3 ou par 2 : (n%3=0) OU (n%2=0)

C1 C2 C1 XOR C2 C1 NON C1
• deux valeurs et deux seulement sont identiques parmi a, b et c :
VRAI VRAI FAUX VRAI FAUX
(a=b) XOR (a=c) XOR (b=c)
VRAI FAUX VRAI FAUX VRAI
FAUX VRAI VRAI
⚫ L'évaluation d'une condition composée se fait selon des règles
présentées généralement dans ce qu'on appelle tables de vérité FAUX FAUX FAUX

32
 Tests imbriqués Exemple Tests imbriqués

⚫ Les tests peuvent avoir un degré quelconque d'imbrications Algorithme Nombre_entier

Si condition1 alors Variable n : entier
Si condition2 alors Début
Ecrire ("entrez un nombre : ")
instructionsA
Lire (n)
Sinon Si (n < 0) alors
instructionsB Ecrire ("Ce nombre est négatif")
Finsi Sinon
Sinon Si (n = 0) alors
Si condition3 alors Ecrire ("Ce nombre est nul")
instructionsC Sinon
Finsi Ecrire ("Ce nombre est positif")
Finsi Finsi
Finsi
Fin

Tests imbriqués: exemple (version 2) Tests imbriqués: exercice

Algorithme Nombre_entier
Le prix de photocopies dans une reprographie varie selon le
Variable n : entier
Début nombre demandé: 0,5 DH la copie pour un nombre de copies
Ecrire ("entrez un nombre : ") inférieur à 10, 0,4DH pour un nombre compris entre 10 et 20 et
Lire (n) 0,3DH au-delà.
Si (n < 0) alors Ecrire ("Ce nombre est négatif")
Finsi Ecrivez un algorithme qui demande à l’utilisateur le nombre de
Si (n = 0) alors Ecrire ("Ce nombre est nul") photocopies effectuées, qui calcule et affiche le prix à payer
Finsi
Si (n > 0) alors Ecrire ("Ce nombre est positif")
Finsi
Fin
Remarque : dans la version 2 on fait trois tests systématiquement alors que
dans la version 1, si le nombre est négatif on ne fait qu'un seul test
Conseil : utiliser les tests imbriqués pour limiter le nombre de tests et placer
d'abord les conditions les plus probables

33
 Sélection Multiple
Tests imbriqués: corrigé de l'exercice

Algorithme Montant_Copies
Exercice:
Variables copies : entier
prix : réel ➢ Ecrire un algorithme qui lit un chiffre entier compris
Début entre 0 et 9 et qui l’affiche en lettre;
Ecrire ("Nombre de photocopies : ")
Lire (copies)
Si (copies < 10) Alors ➢ Travail demander :
prix ← copies*0.5 ➢ Travail à faire : Lecture d’un chiffre compris entre 0 et 9
Sinon Si (copies) < 20
prix ← copies*0.4
➢ Résultat : Afficher le chiffre en lettre
Sinon ➢ Solution : utiliser les condition
prix ← copies*0.3
Finsi
Finsi
Ecrire (“Le prix à payer est : ”, prix)
Fin

Sélection Multiple
Sélection Multiple
Objectif :
Solution:
Permet d’exécuter un bloc d’instructions selon la valeur
➢ Algorithme Traduction
de la variable ou une expression. Cette solution est
➢ Variable ch : entier
identique à un choix multiple.
➢ Début
Syntaxe:
Ecrire ( ‘’ veuillez saisir un chiffre compris entre 0 et 9 ‘’)
Selon variable (ou Expression) faire
Lire(ch)
Valeur 1 : Bloc Instruction 1
Si (ch=0) alors écrire(‘’Zéro’’) Finsi
Valeur 2 : Bloc Instruction 2
Si (ch=1) alors écrire(‘’un’’) Finsi
Valeur 3 : Bloc Instruction 3
. ..
. Valeur n : Bloc Instruction n
Si (ch=9) alors écrire(‘’Neuf’’) Finsi Sinon : Bloc Instruction par défaut
➢ Fin FinSelon

34
Sélection Multiple

Solution:
➢ Algorithme Traduction
ALGORITHMIQUE
➢ Variable ch : entier
➢ Début
Ecrire ( ‘’ veuillez saisir un chiffre compris entre 0 et 9 ‘’)
Lire(ch)
Selon ch faire Instructions itératives:
les boucles
0 : écrire(‘’Zéro’’)
1 : écrire(‘’un’’)
.
9 : écrire(‘’Neuf’’)
Sinon écrire(‘message d’erreur’’)
FinSelon
➢ Fin

Instructions itératives: les boucles Les boucles Tant que

⚫ Les boucles servent à répéter l'exécution d'un groupe d'instructions TantQue (condition)
un certain nombre de fois
instructions condition Vrai instructions
⚫ On distingue trois sortes de boucles en langages de programmation :
FinTantQue
• Les boucles tant que : on y répète des instructions tant qu'une certaine Faux
condition est réalisée

• Les boucles Répéter jusqu'à : on y répète des instructions jusqu'à ce ⚫ la condition (dite condition de contrôle de la boucle) est évaluée avant chaque
qu'une certaine condition soit réalisée itération
• Les boucles pour ou avec compteur : on y répète des instructions en ⚫ si la condition est vraie, on exécute instructions (corps de la boucle), puis, on
faisant évoluer un compteur (variable particulière) entre une valeur initiale retourne tester la condition. Si elle est encore vraie, on répète l'exécution, …
et une valeur finale
⚫ si la condition est fausse, on sort de la boucle et on exécute l'instruction qui
est après FinTantQue

35
Les boucles Tant que : remarques Boucle Tant que : exemple1
⚫ Le nombre d'itérations dans une boucle TantQue n'est pas connu Contrôle de saisie d'une lettre majuscule jusqu’à ce que le caractère
au moment d'entrée dans la boucle. Il dépend de l'évolution de la entré soit valable
valeur de condition
Algorithme Saisie_Lettre
⚫ Une des instructions du corps de la boucle doit absolument changer Variable C : caractère
la valeur de condition de vrai à faux (après un certain nombre Debut
d'itérations), sinon le programme tourne indéfiniment Ecrire (" Entrez une lettre majuscule ")

 Attention aux boucles infinies Lire (C)

TantQue (C < 'A' ou C > 'Z')
⚫ Exemple de boucle infinie :
Ecrire ("Saisie erronée. Recommencez")
i←2 Lire (C)
TantQue (i > 0) FinTantQue
i ← i+1 (attention aux erreurs de frappe : + au lieu de -) Ecrire ("Saisie valable")
FinTantQue Fin

Boucle Tant que : exemple2 Boucle Tant que : exemple2 (version2)

Un algorithme qui détermine le premier nombre entier N tel que la Un algorithme qui détermine le premier nombre entier N tel que la
somme de 1 à N dépasse strictement 100 somme de 1 à N dépasse strictement 100

version 1 version 2: attention à l'ordre des instructions et aux valeurs initiales

Algorithme Somme_N Algorithme Somme_N
Variables som, i : entier Variables som, i : entier
Debut Debut
i←0 som ← 0
som← 0 i←1
TantQue (som <=100) TantQue (som <=100)
i ← i+1 som ← som + i
som ← som+i
i ← i+1
FinTantQue
Ecrire (" La valeur cherchée est N= ", i) FinTantQue
Fin Ecrire (" La valeur cherchée est N= ", i-1)
Fin

36
 Les boucles Pour Les boucles Pour
Pour compteur allant de valeur initiale à finale par pas ⚫ Remarque : le nombre d'itérations dans une boucle Pour est connu
avant le début de la boucle
instructions

FinPour ⚫ Compteur est une variable de type entier Elle doit être déclarée

i ←initiale ⚫ Pas est un entier qui peut être positif ou négatif. Pas peut ne pas
être mentionné, car par défaut sa valeur est égal à 1. Dans ce cas, le
nombre d'itérations est égal à finale - initiale+ 1
Vrai
i n'a pas atteint finale instructions i ← i + pas ⚫ Initiale et finale peuvent être des valeurs, des variables définies
avant le début de la boucle ou des expressions de même type que
Faux compteur

Déroulement des boucles Pour Boucle Pour : exemple1

1) La valeur initiale est affectée à la variable compteur Calcul de x à la puissance n où x est un réel non nul et n un
entier positif ou nul
2) On compare la valeur du compteur et la valeur de finale : Algorithme Puissance
a) Si la valeur du compteur est > à la valeur finale dans le cas d'un pas Variables x, puiss : réel
positif (ou si compteur est < à finale pour un pas négatif), on sort de la n, i : entier
boucle et on continue avec l'instruction qui suit FinPour Debut
Ecrire (" Entrez la valeur de x ")
b) Si compteur est <= à finale dans le cas d'un pas positif (ou si compteur Lire (x)
est >= à finale pour un pas négatif), instructions seront exécutées Ecrire (" Entrez la valeur de n ")
Lire (n)
i. Ensuite, la valeur de compteur est incrémentée de la valeur du pas
si pas est positif (ou décrémenté si pas est négatif) puiss ← 1
Pour i allant de 0 à n-1
ii. On recommence l'étape 2 : La comparaison entre compteur et
puiss← puiss*x
finale est de nouveau effectuée, et ainsi de suite … FinPour
Ecrire (x, " à la puissance ", n, " est égal à ", puiss)
Fin

37
Boucle Pour : exemple1 (version 2) Boucle Pour : remarque
Calcul de x à la puissance n où x est un réel non nul et n un entier ⚫ Il faut éviter de modifier la valeur du compteur (et de finale) à
positif ou nul (version 2 avec un pas négatif) l'intérieur de la boucle. En effet, une telle action :
Algorithme Puissance
• perturbe le nombre d'itérations prévu par la boucle Pour
Variables x, puiss : réel • rend difficile la lecture de l'algorithme
n, i : entier • présente le risque d'aboutir à une boucle infinie
Debut
Ecrire (" Entrez respectivement les valeurs de x et n ") Exemple : Pour i allant de 1 à 5
Lire (x, n) i  i -1
écrire(" i = ", i)
puiss ← 1
Finpour
Pour i allant de n à 1 par pas -1
puiss← puiss*x
FinPour
Ecrire (x, " à la puissance ", n, " est égal à ", puiss)
Fin

Lien entre Pour et TantQue Lien entre Pour et TantQue: exemple

Calcul de x à la puissance n où x est un réel non nul et n un entier positif ou
La boucle Pour est un cas particulier de Tant Que (cas où le nombre nul (version avec TantQue)
d'itérations est connu et fixé) . Tout ce qu'on peut écrire avec Pour peut être Algorithme Puissance
remplacé avec TantQue (la réciproque est fausse)
Variables x, puiss : réel
Pour compteur allant de valeur initiale à finale par pas n, i : entier
Debut
Ecrire (" Entrez la valeur de x ")
instructions Lire (x)
Ecrire (" Entrez la valeur de n ")
FinPour Lire (n)
peut être remplacé par : compteur ← initiale
puiss ← 1
(cas d'un pas positif) TantQue compteur <= finale i←1
instructions TantQue (i<=n)
puiss← puiss*x
compteur ← compteur+pas i ← i+1
FinTantQue FinTantQue
Ecrire (x, " à la puissance ", n, " est égal à ", puiss)
Fin

38
Boucles imbriquées Les boucles Répéter … jusqu’à …
⚫ Les instructions d'une boucle peuvent être des instructions
Répéter
itératives. Dans ce cas, on aboutit à des boucles imbriquées
instructions instructions
⚫ Exemple: Exécution
Jusqu'à condition
Pour i allant de 1 à 5 OX
Faux
Pour j allant de 1 à i OOX condition
écrire("O") OOOX
Vrai
FinPour OOOOX
écrire("X") OOOOOX ⚫ Condition est évaluée après chaque itération
FinPour
⚫ les instructions entre Répéter et jusqu’à sont exécutées au moins une fois et
leur exécution est répétée jusqu’à ce que condition soit vrai (tant qu'elle est
fausse)

Boucle Répéter jusqu’à : exemple Choix d'un type de boucle

Un algorithme qui détermine le premier nombre entier N tel que la somme de 1 ⚫ Si on peut déterminer le nombre d'itérations avant l'exécution de la
à N dépasse strictement 100 (version avec répéter jusqu'à) boucle, il est plus naturel d'utiliser la boucle Pour
Algorithme Somme _N_entier
Variables som, i : entier ⚫ S'il n'est pas possible de connaître le nombre d'itérations avant
Debut l'exécution de la boucle, on fera appel à l'une des boucles TantQue
som ← 0 ou répéter jusqu'à
i←0
Répéter ⚫ Pour le choix entre TantQue et répéter jusqu'à :
i ← i+1
• Si on doit tester la condition de contrôle avant de commencer les
som ← som+i instructions de la boucle, on utilisera TantQue
Jusqu'à ( som > 100)
Ecrire (" La valeur cherchée est N= ", i) • Si la valeur de la condition de contrôle dépend d'une première
exécution des instructions de la boucle, on utilisera répéter jusqu'à
Fin

39
 Insertion des commentaires
⚫ Syntaxe
⚫ il faut précéder une ligne de commentaires des ALGORITHMIQUE
symboles \\ (deux antéslashs consécutifs) :
tout ce qui suit jusqu'à la fin de la ligne est alors ignoré
lors de la compilation de l'algorithme. Pour prolonger un
commentaire sur plusieurs lignes, il faut commencer
chaque ligne par \\ :
\\ Voici un exemple de commentaire se Exercices
\\ propageant sur plus d'une ligne
DÉBUT
ÉCRIRE "Bonjour tout e monde" \\ Exemple de commentaire en fin de ligne
FIN

Exercice 1 :
⚫Écrire un algorithme permettant de Lire la suite des prix (en Exercice 1 :
Dirhams entiers et terminée par zéro) des achats d’un client, de
Calculer le montant des achats, de lire la somme versée, et de
simuler la remise de la monnaie en affichant les textes " Pièces de
10 Dh", " Pièces de 5 Dh" et " Pièces de 1 Dh" autant de fois qu’il y ⚫Écrire un algorithme permettant de Lire la suite
a de pièces à rendre. des prix (en Dirhams entiers et terminée par zéro)
Exercice 2 : des achats d’un client, de Calculer le montant
⚫Ecrire un algorithme permettant de résoudre une
des achats, de lire la somme versée, et de simuler
équation de seconde degré : la remise de la monnaie en affichant les textes "
ax² + bx + c = 0. Pièces de 10 Dh", " Pièces de 5 Dh" et " Pièces de
1 Dh" autant de fois qu’il y a de pièces à rendre.

40
 Solution de l’Exercice 1 : Suite de la solution de l’Exercice 1:
Algorithme guichet ⚫
TantQue Reste >= 10
Variables PA, MontP, MontV, Reste, NP10, NP5 : Entier NP10 ← NP10 + 1
Debut Reste ← Reste – 10
PA ← 1 FinTantQue
MontP ← 0 NP5 ← 0
TantQue PA <> 0 Si Reste >= 5
Ecrire ("Entrez le montant de l’article : " ) NP5 ← 1
Lire (PA) Reste ← Reste – 5
MontP ← MontP + PA FinSi
FinTantQue Ecrire ("la monnaie rendue est :")
Ecrire ("Vous devez payer :", MontP, " dirhams" ) Ecrire ("Les Pièces de 10 Dh : ", NP10)
Ecrire ("Saisir le Montant versé :") Ecrire ("Les Pièces de 5 Dh : ", NP5)
Lire (MontV) Ecrire ("Les Pièces de 1 Dh : ", reste)
Reste ← MontV - MontP Fin
NP10 ← 0

Exercice 2 : Solution de l’Exercice 2:

Algorithme Equation
⚫ Écrire un algorithme permettant de résoudre Variables a, b, c, Delta: réel
une équation de seconde degré : Début
ax² + bx + c = 0. Écrire( "Introduisez le coefficient de x2:’’ )
lire (a)
écrire ("Introduisez le coefficient de x:’’ )
lire (b)
écrire ("Introduisez le terme indépendant:’’ )
lire (c)
•

41
Suite de la Solution de l’Exercice 2:
si a=0 alors écrire "Equation du premier degré."
sinon Delta  b*b-4a*c
si Delta>0 alors écrire ("2 racines réelles distinctes:")
écrire ("x1=",(-b+ Sqrt(Delta))/(2*a))
ALGORITHMIQUE
écrire ("x2=",(-b- Sqrt( Delta))/(2*a))
sinon si Delta=0 alors écrire ("2 racines réelles égales:")
écrire ("x1=x2=",-b/(2*a))
sinon écrire ("2 racines complexes conjuguées:")
écrire ("x1=",-b/(2*a)," + i", Sqrt( -Delta) /(2*a)) Les tableaux
écrire ("x2=",-b/(2*a)," - i", Sqrt( -Delta)/(2*a))
Finsi
Finsi
Finsi
Fin
•

Exemple introductif Tableaux

⚫ Supposons qu'on veut conserver les notes d'une classe de 30 étudiants ⚫ Un tableau est un ensemble d'éléments de même type désignés
pour extraire quelques informations. Par exemple : calcul du nombre par un identificateur unique
d'étudiants ayant une note supérieure à 10
⚫ Une variable entière nommée indice permet d'indiquer la position
⚫ Le seul moyen dont nous disposons actuellement consiste à déclarer 30
d'un élément donné au sein du tableau et de déterminer sa valeur
variables, par exemple N1, …, N30. Après 30 instructions lire, on doit écrire
30 instructions Si pour faire le calcul ⚫ La déclaration d'un tableau s'effectue en précisant le type de ses
nbre ← 0 éléments et sa dimension (le nombre de ses éléments)
Si (N1 >10) alors nbre ←nbre+1 FinSi • En pseudo code :
…. variable tableau identificateur[dimension] : type
Si (N30>10) alors nbre ←nbre+1 FinSi • Exemple :
c'est lourd à écrire variable tableau notes[30] : réel
⚫ Heureusement, les langages de programmation offrent la possibilité de
rassembler toutes ces variables dans une seule structure de donnée ⚫ On peut définir des tableaux de tous types : tableaux d'entiers, de
appelée tableau réels, de caractères, de booléens, de chaînes de caractères, …

42
Tableaux : remarques Tableaux : exemples (1)
⚫ L'accès à un élément du tableau se fait au moyen de l'indice. Par exemple, ⚫ Pour le calcul du nombre d'étudiants ayant une note supérieure à
notes[i] donne la valeur de l'élément i du tableau notes 12 avec les tableaux, on peut écrire :
⚫ Selon les langages, le premier indice du tableau est soit 0, soit 1. Le plus Algorithme CalculNote
souvent c'est 0 (c'est ce qu'on va adopter en pseudo-code). Dans ce cas, Variables i ,nbre : entier
notes[i] désigne l'élément i+1 du tableau notes tableau notes[30] : réel
Début
⚫ Il est possible de déclarer un tableau sans préciser au départ sa dimension.
nbre ← 0
Cette précision est faite ultérieurement .

Pour i allant de 0 à 29
• Par exemple, quand on déclare un tableau comme paramètre d'une procédure, Si (notes[i] >12) alors
on peut ne préciser sa dimension qu'au moment de l'appel
nbre ←nbre+1
• En tous cas, un tableau est inutilisable tant qu’on n’a pas précisé le nombre de FinSi
ses éléments FinPour
⚫ Un grand avantage des tableaux est qu'on peut traiter les données qui y écrire ("le nombre de notes supérieures à 12 est : ", nbre)
sont stockées de façon simple en utilisant des boucles Fin

Tableaux : saisie et affichage Tableaux à deux dimensions

⚫ Algorithme qui permet de saisir et d'afficher les éléments d'un tableau : ⚫ Les langages de programmation permettent de déclarer des
Algorithme Tableaux tableaux dans lesquels les valeurs sont repérées par deux indices.
variable n,i : entier Ceci est utile par exemple pour représenter des matrices
tableau T[ ] : réel
Début ⚫ En pseudo code, un tableau à deux dimensions se déclare ainsi :
Écrire (" Entrez la dimension du tableau T")
variable tableau identificateur[dimension1] [dimension2] : type
Lire (n)
Pour i allant de 0 à n-1
écrire ("Saisie de l'élément ", i + 1)
• Exemple : une matrice A de 3 lignes et 4 colonnes dont les éléments
sont réels
lire (T[i] )
FinPour variable tableau A[3][4] : réel
Pour i allant de 0 à n-1
écrire ("T[",i, "] =", T[i]) ⚫ A[i][j] permet d'accéder à l’élément de la matrice qui se trouve à
FinPour l’intersection de la ligne i et de la colonne j
Fin

43
 Exemple: Tableaux à deux dimensions Exemple: Tableaux à deux dimensions ( Suite)
Exemple d'algorithme qui permet de saisir, d’afficher et de calculer la somme
Pour i allant de 0 à n-1
des éléments de deux matrices :
écrire ("saisie de la ligne ", i + 1)
Algorithme Somme_Matricielle
Pour j allant de 0 à m-1
variables tableau A[ ][ ],B [ ][ ],C [ ][ ] : réel
écrire ("Entrez l'élément de la ligne ", i + 1, " et de la
i, j, n, m : entier colonne ", j+1)
Début lire (B[i][j])
Écrire (" Entrez le nombre de lignes et de colonnes des matrices
A,B et C") FinPour
Lire (n,m) FinPour
Pour i allant de 0 à n-1 Pour i allant de 0 à n-1
écrire ("saisie de la ligne ", i + 1) Pour j allant de 0 à m-1
Pour j allant de 0 à m-1 C[i][j] ← A[i][j]+B[i][j]
écrire ("Entrez l'élément de la ligne ", i + 1, " et de la écrire ("C[",i, "] [",j,"]=", C[i][j])
colonne ", j+1) FinPour
lire (A[i][j]) FinPour
FinPour Fin
FinPour

Solution de l’Exercice:
Exercice : Algorithme notesclasse
Variables Som, Moy, Tableau T() : Réel

⚫ Écrire un algorithme permettant à l’utilisateur de Nb, i, Nbsup : entier

saisir les notes d'une classe. Le programme, Debut
une fois la saisie terminée, renvoie le nombre Ecrire ( "Entrez le nombre de notes à saisir : ")
Lire (Nb)
des notes supérieures à la moyenne de la • Som  0
classe. Pour i allant de 0 à Nb - 1
Ecrire( "Entrez la note de l’étudiant n° ", i + 1)
Lire (T(i))
Som Som + T(i)
FinPour
Moy  Som / Nb
NbSup  0

44
 Suite de la Solution de l’Exercice:

Pour i allant de 0 à Nb - 1
ALGORITHME
Si T(i) > Moy Alors
NbSup  NbSup + 1
FinSi
FinPour
Ecrire( NbSup, " étudiants dépassent la moyenne de la
classe" ) Fonctions et procédures
• Fin

Programmation procédurale
Fonctions et procédures
⚫ Certains problèmes complexes conduisent à réaliser des programmes
longs et sophistiqués, difficiles à les écrire et à les comprendre. Et ⚫ Principe:
difficiles à avoir une vision globale sur leurs fonctionnement et à • Il s’agit d’écrire des programmes en utilisant des
localiser les erreurs. sous-programmes
⚫ Forme générale d’un programme
⚫ Solution : décomposer le problème en des
modules cohérents organisés sous forme d’entités Programme P
indépendantes appelées sous-programmes Sous-programme SP1
exécutant une tâche précise:
• Trouver une solution à chacun
…
• La solution partielle donne lieu à un sous-programme Sous-programme SPn
FinP
180

45
 Exemple
⚫ Algorithme qui teste si M est la matrice inverse de N Fonctions et procédures

Algorithme Matrice_Inverse ⚫ En algorithmique, on distingue deux types de sous-programmes

Variables Tableau M[ ][ ], N[ ][ ], O[ ][ ] : Entier Les procédures

Les fonctions
debut
Lecture_Matrice(M) ⚫ Les fonctions et les procédures sont des modules (groupe d'instructions)
indépendants désignés par un nom. Elles ont plusieurs intérêts :
Lecture_Matrice(N)
• permettent de "factoriser" les programmes, càd de mettre en commun
O M*N les parties qui se répètent
Vérification( si O est l’identité) • permettent une structuration et une meilleure lisibilité des programmes
Affichage (" du message adéquat ") • facilitent la maintenance du code (il suffit de modifier une seule fois)
Fin • ces procédures et fonctions peuvent éventuellement être réutilisées dans
181 d'autres programmes

Fonctions : structure Fonctions

⚫ Une fonction est un sous-programme qui : ⚫ Le rôle d'une fonction en programmation est similaire à
• A un nom celui d'une fonction en mathématique : elle retourne un
• Peut avoir des paramètres
résultat à partir des valeurs des paramètres
• Qui retourne une valeur d’un certain type
• Qui peut avoir besoin de variables
Pour le choix d'un nom de fonction il faut respecter les mêmes règles
• Qui est composé d’instructions
⚫
que celles pour les noms de variables
⚫ Une fonction s'écrit en dehors du programme principal sous la forme : ⚫ type_fonction est le type du résultat retourné
⚫ L'instruction retourne sert à retourner la valeur du résultat
Fonction nom_fonction (paramètres et leurs types) : type_fonction
Déclaration des variables
Début
Instructions constituant le corps de la fonction
retourne …
FinFonction
183

46
Structure générale des fonctions
Fonctions : exemples
⚫ La fonction SommeCarre suivante calcule la somme des carrées de
deux réels x et y :
Fonction SommeCarre (x : réel, y: réel ) : réel
variable z : réel
Début
z ←x^2+y^2
retourne (z)
FinFonction
⚫ La fonction Pair suivante détermine si un nombre est pair :
Fonction Pair (n : entier ) : booléen
retourne (n%2=0)
FinFonction

Utilisation des fonctions Procédures : définition

⚫ L'utilisation d'une fonction se fera par simple écriture de son nom
dans le programme principale. Le résultat étant une valeur, devra ⚫ Une procédure est un sous-programme qui ne
être affecté ou être utilisé dans une expression, une écriture, ... retourne pas de valeur
⚫ Exepmle : Algorithme exepmleAppelFonction
variables x,y, z : réel, b : booléen , a: entier ⚫ C’est donc un type particulier de fonction
Début
Ecrire(" saisir un nombre entier et deux réel") ⚫ En général, une procédure modifie la valeur de
lire(a,x,y)
ses paramètres
b ←Pair(a)
z ←5*SommeCarre(x,y)+1 • Je dis bien « en général », ce n’est pas toujours le cas
écrire("SommeCarre(x,y)= ", SommeCarre(x,y))
Fin
⚫ Lors de l'appel Pair(a) le paramètre formel n est remplacé par le
paramètre effectif a 188

47
 Procèdures
Procédures : structure
⚫ Tout comme les fonctions, une ⚫ Une procédure s'écrit en dehors du programme principal
procédure est un sous-programme qui : sous la forme :
• A un nom Procédure nom_procédure (paramètres et leurs
• Peut avoir des paramètres types)
• Qui peut avoir besoin de variables Déclaration des variables
• Qui est composé d’instructions Début
Instructions
FinProcédure
⚫ Remarque : une procédure peut ne pas avoir de
paramètres
189

Appel d'une procédure Exemple de Procédures & fonctions:

⚫ L'appel d'une procédure, se fait dans le programme principale ou dans une
autre procédure par une instruction indiquant le nom de la procédure : ⚫ Ecrire un algorithme de tri en utilisant des
Procédure exemple_proc (…) fonctions et des procédures:
…
FinProcédure • Procédure de saisie d’un tableau T
Algorithme AppelProcédure
• Procédure qui fait le tri en faisant appel à:
Début • Une Procédure qui échange les valeurs de
exemple_proc (…)
…
deux cases du tableau T
Fin • une Fonction qui retourne l’indice de la
⚫ Remarque : contrairement à l'appel d'une fonction, on ne peut pas affecter la valeur max dans le tableau
procédure appelée ou l'utiliser dans une expression. L'appel d'une
procédure est une instruction autonome

192

48
 Procédure de saisie
Algorithme de saisie et de tri Procédure saisir(n, tableau T[] :Entiers)
variable i: entier
Algorithme Tri_Tableau Début
Variable n, Tableau T[ ] :Entier Pour i allant de 0 à n-1
Début Lire(T(i))
Fin Pour
Ecrire ( "Entrez le nombre de notes à saisir : ")
Fin Procédure
Lire (n)
Saisir(n,T)
Trier(n,T)
Fin
193 194

Procédure qui échange les cases i et j

Procédure de Tri
Procédure Trier(n,Tableau T[ ] :entiers) Procédure échanger(i, j : entier, tableau T[]:entiers )
Variable i: entier Variable Z : entier
Début Début
Pour i allant de 0 à n-2 Z  T(i)
Echanger(i, IndMax(n,i,T), T) T(i)  T(j)
FinPour T(j)  Z
Fin Procédure
FinProcédure

195 196

49
Fonction qui retourne l’indice de la
valeur max dans une partie du tableau Paramètres d'une procédure
⚫ Les paramètres servent à échanger des données entre le programme
Fonction IndMax ( n, i: entier, tableau T[] :entiers) : entier
principale (ou la procédure appelante) et la procédure appelée
variable j, Max: entier
Début
⚫ Les paramètres placés dans la déclaration d'une procédure sont appelés
Max  i paramètres formels. Ces paramètres peuvent prendre toutes les valeurs
Pour j allant de i à n-1 possibles mais ils sont abstraits (n'existent pas réellement)
Si T(Max) < T(j) Alors
Max  j ⚫ Les paramètres placés dans l'appel d'une procédure sont appelés
FinSi paramètres effectifs. ils contiennent les valeurs pour effectuer le
Fin Pour traitement
IndMax  Max
⚫ Le nombre de paramètres effectifs doit être égal au nombre de paramètres
Fin Fonction
formels. L'ordre et le type des paramètres doivent correspondre

197

Transmission des paramètres Transmission des paramètres : exemples

Il existe deux modes de transmission de paramètres dans les langages de Procédure incrementer1 (x : entier par valeur, y : entier par adresse)
programmation : x ← x+1
y ← y+1
⚫ La transmission par valeur : les valeurs des paramètres effectifs sont
FinProcédure
affectées aux paramètres formels correspondants au moment de l'appel de la
procédure. Dans ce mode le paramètre effectif ne subit aucune modification Algorithme Test_incrementer1
⚫ La transmission par adresse (ou par référence) : les adresses des variables n, m : entier
paramètres effectifs sont transmises à la procédure appelante. Dans ce Début
mode, le paramètre effectif subit les mêmes modifications que le paramètre n←3
formel lors de l'exécution de la procédure
m←3
• Remarque : le paramètre effectif doit être une variable (et non une incrementer1(n, m)
valeur) lorsqu'il s'agit d'une transmission par adresse écrire (" n= ", n, " et m= ", m)
Fin
⚫ En pseudo-code, on va préciser explicitement le mode de transmission dans
la déclaration de la procédure Remarque : l'instruction x ← x+1 n'a pas de sens avec un passage par valeur
résultat : n=3 et m=4

50
Transmission par valeur, par adresse : exemples
Variables locales et globales (1)
Procédure qui calcule la somme et le produit de deux entiers :
Procédure SommeProduit (x,y: entier par valeur, som, prod : entier par adresse) ⚫ On peut manipuler 2 types de variables dans un module (procédure ou
Début fonction) : des variables locales et des variables globales. Elles se
som ← x+y distinguent par ce qu'on appelle leur portée (leur "champ de définition", leur
prod ← x*y "durée de vie")
FinProcédure
Procédure qui échange le contenu de deux variabales : ⚫ Une variable locale n'est connue qu'à l'intérieur du module ou elle a été
définie. Elle est créée à l'appel du module et détruite à la fin de son exécution
Procédure Echange (x : réel par adresse, y : réel par adresse)
variables z : réel
⚫ Une variable globale est connue par l'ensemble des modules et le
Début programme principale. Elle est définie durant toute l’application et peut être
z←x utilisée et modifiée par les différents modules du programme
x←y
y←z
FinProcédure

Variables locales et globales (2) Récursivité

⚫ La manière de distinguer la déclaration des variables locales et globales ⚫ Un module (fonction ou procédure) peut faire appel à lui-même: on
diffère selon le langage dit que c'est un module récursif

• En général, les variables déclarées à l'intérieur d'une fonction ou ⚫ Tout module récursif doit posséder un cas limite (cas trivial) qui
procédure sont considérées comme variables locales arrête la récursivité

• En pseudo-code, on va adopter cette règle pour les variables locales et on ⚫ Exemple : Calcul du factorielle
déclarera les variables globales dans le programme principale Fonction fact (n : entier ) : entier
Début
• Conseil : Il faut utiliser autant que possible des variables locales plutôt que Si (n=0) alors
des variables globales. Ceci permet d'économiser la mémoire et d'assurer retourne (1)
l'indépendance de la procédure ou de la fonction Sinon
retourne (n*fact(n-1))
Finsi
FinFonction

51
Fonctions récursives : exercice Fonctions récursives : exercice (suite)
⚫ Ecrivez une fonction récursive (puis itérative) qui calcule le terme n ⚫ Une fonction itérative pour le calcul de la suite de Fib :
de la suite de Fib définie par : U(0)=U(1)=1 Fonction Fib (n : entier ) : entier
U(n)=U(n-1)+U(n-2) Variables i, AvantDernier, Dernier, Nouveau : entier
Début
Fonction Fib (n : entier ) : entier Si (n=1 OU n=0) alors retourne (1)
Début Finsi
Variable res : entier AvantDernier ←1, Dernier ←1
Si (n=1 OU n=0) alors Pour i allant de 2 à n
res ←1 Nouveau← Dernier+ AvantDernier
Sinon AvantDernier ←Dernier
res ← Fib(n-1)+Fib(n-2) Dernier ←Nouveau
Finsi FinPour
retourne (res) retourne (Nouveau)
FinFonction FinFonction
Remarque: la solution récursive est plus facile à écrire

Procédures récursives : exemple LES FONCTIONS PRÉDÉFINIES: exemple

⚫ Une procédure récursive qui permet d'afficher la valeur binaire d'un entier n ⚫ FONCTIONS DE TEXTE :
• Len(chaîne) : renvoie le nombre de caractères d’une chaîne
Procédure binaire (n : entier ) • Mid(chaîne,n1,n2) : renvoie un extrait de la chaîne,
Début commençant au caractère n1 et faisant n2 caractères de
Si (n<>0) alors long.
binaire (n/2) • Left(chaîne,n) : renvoie les n caractères les plus à gauche
écrire (n mod 2) dans chaîne.
Finsi • Right(chaîne,n) : renvoie les n caractères les plus à droite
FinProcédure 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.

52
 LES FONCTIONS PRÉDÉFINIES: exemple
⚫ Les fonctions mathématiques prédéfinies permettent la
LES FONCTIONS PRÉDÉFINIES: exemple réalisation d'un traitement mathématiques sur des données
numériques:
⚫ FONCTIONS DE TEXTE EXEMPLES:
⚫ Abs(x) Retourne la valeur absolue d'un nombre x ← Abs(-12) x = 12
• Len("Bonjour, ça va ?") vaut 16 ⚫ Ent(x) Retourne la partie entière d'un nombre x ← Ent(12.3) x = 12
Len("") vaut 0
⚫ Cos(x) Retourne une valeur spécifiant le cosinus d'un angle x ← Cos(0) x = 1
Mid("Zorro is back", 4, 7) vaut "ro is b"
Mid("Zorro is back", 12, 1) vaut "c" ⚫ Sin(x) Retourne une valeur spécifiant le sinus d'un angle x ← Sin(0) x = 0
Left("Et pourtant…", 8) vaut "Et pourt" ⚫ Tan(x) Retourne une valeur contenant la tangente d'un angle x ← Tan(0) x = 0
Right("Et pourtant…", 4) vaut "t…" ⚫ Sqrt(x) Retourne une valeur spécifiant la racine carrée d'un nombre x ← Sqrt(4) x = 2
Trouve("Un pur bonheur", "pur") vaut 4 ⚫ Alea() Retourne un nombre aléatoire compris entre 0 (inclus) et 1 (exclu)
Trouve("Un pur bonheur", "techno") vaut 0
x ← alea() 0 =< x < 1
La fonction Alea renvoie un nombre réel aléatoire compris entre 0 et 1. Pour obtenir
une valeur entière comprise entre min et max (avec min < max), on utilise la formule
suivante : Ent((max-min+1)*Alea() + min)
Exemple : Générer un nombre aléatoire X compris entre 5 et 10.
Solution :
X ← Ent(6 * Alea() + 5)

LES FONCTIONS PRÉDÉFINIES: exemple

Tableaux : saisie et affichage
⚫ Les fonctions numériques: ⚫ Procédures qui permettent de saisir et d'afficher les éléments d'un tableau :
Procédure SaisieTab(n : entier par valeur, tableau T : réel par référence )
variable i: entier
Début
Pour i allant de 0 à n-1
écrire ("Saisie de l'élément ", i + 1)
lire (T[i] )
FinPour
Fin Procédure
Procédure AfficheTab(n : entier par valeur, tableau T : réel par valeur )
variable i: entier
Début
Pour i allant de 0 à n-1
écrire ("T[",i, "] =", T[i])
FinPour
Fin Procédure

53
 Tableaux : fonction longueur
Tableaux : exemples d'appel La plus part des langages offrent une fonction longueur qui donne la dimension
du tableau. Les procédures Saisie et Affiche peuvent être réécrites comme suit :
⚫ Algorithme principale qui fait appel aux procédures SaisieTab et Procédure SaisieTab( tableau T : réel par référence )
AfficheTab : variable i: entier
Début
Algorithme Tableaux Pour i allant de 0 à longueur(T)-1
variable p : entier écrire ("Saisie de l'élément ", i + 1)
tableau A[] : réel lire (T[i] )
FinPour
Début
Fin Procédure
Ecrire ( "Entrez la dimension du tableau: ")
Procédure AfficheTab(tableau T : réel par valeur )
Lire (p)
variable i: entier
SaisieTab(p, A) Début
AfficheTab(p,A) Pour i allant de 0 à longueur(T)-1
Fin écrire ("T[",i, "] =", T[i])
FinPour
Fin Procédure

Appel aux procédures

Exercice Exemple d'algorithme principale qui fait appel aux procédures définies
précédemment pour la saisie, l'affichage et la somme des matrices :
Écrire un algorithme qui fait appel aux procédures suivantes:
⚫ saisie de deux matrices ;
Algorithme Matrices
⚫ Affichage de deux matrices
variables tableau A[ ][ ],B [ ][ ],C [ ][ ] : réel
⚫ Somme de deux matrices n, m : Entier
⚫ Affichage de la matrice somme Début
Écrire (" Entrez le nombre de lignes et de colonnes de la matrices")
Lire (n,m)
SaisieMatrice(n, m, A)
SaisieMatrice(n, m, B)
AfficheMatrice(n,m, A)
AfficheMatrice(n,m, B)
SommeMatrice(n, m, A,B,C)
AfficheMatrice(n,m, C)
Fin

54
Exemples : lecture d'une matrice Exemples : affichage d'une matrice
⚫ Procédure qui permet de saisir les éléments d'une matrice : ⚫ Procédure qui permet d'afficher les éléments d'une matrice :

Procédure SaisieMatrice(n : entier par valeur, m : entier par valeur , Procédure AfficheMatrice(n : entier par valeur, m : entier par valeur
tableau T[ ][ ] : réel par référence ) ,tableau T[ ][ ]: réel par valeur )
variables i ,j : entier variables i ,j : entier
Début
Début
Pour i allant de 0 à n-1
écrire ("saisie de la ligne ", i + 1) Pour i allant de 0 à n-1
Pour j allant de 0 à m-1
Pour j allant de 0 à m-1
écrire ("Entrez l'élément de la ligne ", i + 1, " et de la colonne ", j+1) écrire ("T[",i, "] [",j,"]=", T[i][j])
lire (T[i][j]) FinPour
FinPour FinPour
FinPour Fin Procédure
Fin Procédure

Exemples : somme de deux matrices Tableaux : 2 problèmes classiques

⚫ Procédure qui calcule la somme de deux matrices :
⚫ Recherche d’un élément dans un tableau
Procédure SommeMatrices(n, m : entier par valeur,
tableau M1[ ][ ], M2 [ ][ ]: réel par valeur , tableau M3 [ ][ ]: réel • Recherche séquentielle
par référence ) • Recherche dichotomique
variables i, j : entier
Début ⚫ Tri d'un tableau
Pour i allant de 0 à n-1
Pour j allant de 0 à m-1 • Tri à bulles
M3[i][j] ← M1[i][j]+M2[i][j] • Tri par sélection
FinPour • Tri par insertion
FinPour • Tri rapide
Fin Procédure

55
 Recherche séquentielle (version 2)
Recherche séquentielle
⚫ Une fonction Recherche qui retourne un booléen pour indiquer si une valeur
⚫ Recherche de la valeur x dans un tableau T de N éléments : x appartient à un tableau T de dimension N.
Algorithme RechercheValeur x , N et T sont des paramètres de la fonction
Variables i,N: entier, Trouvé : booléen, tableau T[}: réel , X Réel
Debut Fonction Recherche(x : réel par valeur, N: entier par valeur, tableau
Ecrire ("Saisir la dimension du Tableau et la valeur de X ") T : réel par valeur) : booléen
lire (N,x) Variable i: entier
i←0 , Trouvé ← Faux
Début
TantQue (i < N) ET (Trouvé=Faux)
Si (T[i]=x) alors Pour i allant de 0 à N-1
Trouvé ← Vrai Si (T[i]=x) alors
Sinon retourne (Vrai)
i←i+1 FinSi
FinSi FinPour
FinTantQue
retourne (Faux)
Si Trouvé alors // c'est équivalent à écrire Si Trouvé=Vrai alors
FinFonction
écrire ("x appartient au tableau")
Sinon écrire ("x n'appartient pas au tableau")
FinSi
Fin

Notion de complexité d'un algorithme Recherche séquentielle : complexité

⚫ Pour évaluer l’efficacité d'un algorithme, on calcule sa complexité ⚫ Pour évaluer l’efficacité de l'algorithme de recherche séquentielle, on va
calculer sa complexité dans le pire des cas. Pour cela on va compter le
⚫ Mesurer la complexité revient à quantifier le temps d'exécution et l'espace nombre de tests effectués
mémoire nécessaire
⚫ Le pire des cas pour cet algorithme correspond au cas où x n'est pas dans
⚫ Le temps d'exécution est proportionnel au nombre des opérations le tableau T
effectuées. Pour mesurer la complexité en temps, on met en évidence ⚫ Si x n’est pas dans le tableau, on effectue 3N tests : on répète N fois les
certaines opérations fondamentales, puis on les compte
tests (i < N), (Trouvé=Faux) et (T[i]=x)

⚫ Le nombre d'opérations dépend généralement du nombre de données à ⚫ La complexité dans le pire des cas est d'ordre N, (on note O(N))
traiter. Ainsi, la complexité est fonction de la taille des données. On
s'intéresse souvent à son ordre de grandeur asymptotique ⚫ Pour un ordinateur qui effectue 106 tests par seconde on a :
N 103 106 109
⚫ En général, on s'intéresse à la complexité dans le pire des cas et à la
complexité moyenne temps 1ms 1s 16mn40s

56
 Recherche dichotomique : algorithme
Recherche dichotomique Algorithme RechercheDichotomique
Variables inf, sup, N: entier, Trouvé : booléen, tableau T : réel , X Réel
Debut
Ecrire ("Saisir la dimension du Tableau et la valeur de X ")
⚫ Dans le cas où le tableau est ordonné, on peut améliorer l'efficacité
lire (N,x)
de la recherche en utilisant la méthode de recherche dichotomique
inf←0 ,Trouvé ← Faux , sup←N-1
TantQue (inf <=sup) ET (Trouvé=Faux)
⚫ Principe : diviser par 2 le nombre d'éléments dans lesquels on milieu←(inf+sup)/2
cherche la valeur x à chaque étape de la recherche. Pour cela on Si (x=T[milieu]) alors Trouvé ← Vrai
compare x avec T[milieu] : Sinon Si (x>T[milieu]) alors inf←milieu+1
Sinon sup←milieu-1
• Si x < T[milieu], il suffit de chercher x dans la 1ère moitié du tableau FinSi
entre (T[0] et T[milieu-1]) FinSi
FinTantQue
• Si x > T[milieu], il suffit de chercher x dans la 2ème moitié du tableau Si Trouvé alors écrire ("x appartient au tableau")
entre (T[milieu+1] et T[N-1])
Sinon écrire ("x n'appartient pas au tableau")
FinSi
Fin

Recherche dichotomique : complexité

Exemple d'exécution
⚫ Considérons le tableau T : 4 6 10 15 17 18 24 27 30 ⚫ La complexité dans le pire des cas est d'ordre log 2 N

⚫ Si la valeur cherché est 20 alors les indices inf, sup et milieu vont évoluer ⚫ L'écart de performances entre la recherche séquentielle et la recherche
comme suit : dichotomique est considérable pour les grandes valeurs de N

inf 0 5 5 6 • Exemple: au lieu de N=1milion ≈220 opérations à effectuer avec une

sup 8 8 5 5 recherche séquentielle il suffit de 20 opérations avec une recherche
dichotomique
milieu 4 6 5
⚫ Si la valeur cherché est 10 alors les indices inf, sup et milieu vont évoluer
comme suit :
inf 0 0 2
sup 8 3 3
milieu 4 1 2

57
 Tri d'un tableau Tri à bulles
⚫ Le tri à bulles ou tri par propagation est
un algorithme de tri qui consiste à faire remonter
⚫ Le tri consiste à ordonner les éléments du tableau dans l’ordre progressivement les plus grands éléments
croissant ou décroissant. Le tri en algorithmique est attaché au
processus de classement d'un ensemble d'éléments dans un ordre
d'un tableau, comme les bulles d'air remontent à
donné. Par exemple, trier N entiers dans l'ordre croissant, ou N la surface d'un liquide.
noms dans l'ordre alphabétique. Tout ensemble muni d'un ordre
total peut fournir une suite d'éléments à trier. ⚫ Le tri à bulles est souvent enseigné en tant
qu'exemple algorithmique, car son principe est
⚫ Il existe plusieurs algorithmes connus pour trier les éléments d’un simple
tableau :
• Le tri à bulles
• Le tri par sélection
• Le tri par insertion
• Le tri rapide

Tri à bulles : Principe de l’algorithme Exemple de Tri à bulles

Si l’on prend (8, 7, 1, 4, 6) comme suite de
nombres, et que l’on utilise l’algorithme du tri à
⚫ L'algorithme parcourt le tableau, et compare bulles pour trier cette suite dans l’ordre croissant:
1èr Tour Résultat du 2ème Tour Résultat du 2ème
les couples d'éléments successifs. Lorsque 1er Tour Tour
deux éléments successifs ne sont pas dans 8 > 7 donc on .7, 8, 1, 4, 6 7 > 1 donc on échange 1, 7, 4, 6, 8
échange.
l'ordre croissant, ils sont échangés. Après
8 > 1 donc on 7, 1, 8, 4, 6 7 > 4 donc on échange. 1, 4, 7, 6, 8
chaque parcours complet du tableau, échange.

l'algorithme recommence l'opération. 8 > 4 donc on

échange.
7, 1, 4, 8, 6 7 > 6 donc on échange. 1, 4, 6, 7, 8

Lorsqu’aucun échange n'a lieu pendant un 8 > 6 donc on 7, 1, 4, 6, 8

échange.
parcours, cela signifie que le tableau est trié.
On arrête alors l'algorithme

58
Animation : Tri à bulles : Exemple version non optimisée de Tri à bulles
procédure tri_bulle(tableau t : réel par référence)
// On échange les éléments de rang j et j+1
Début
n ← longueur(t)
pour i allant de n-1 à 0 pas -1 faire
pour j allant de 0 à i faire
si (t[j] > t[j+1]) alors
tmp ← t[j]
t[j] ← t[j+1]
t[j+1] ← tmp
fin si
fin pour
fin pour
fin procédure

Exemple version optimisée de Tri à bulles

Tri à bulles : complexité et remarques
procédure tri_bulle(tableau t : réel par référence)
Début ⚫ Le pire des cas (n itérations) est atteint lorsque le plus
i ← longueur(t) petit élément est à la fin du tableau. La complexité est
échange ← vrai alors O(n2).
tant que ((i>0) ET (échange)) faire ⚫ En moyenne, la complexité est aussi O(n2). En effet, le
échange ← faux nombre d'échanges de paires d'éléments successifs est
pour j allant de 0 à i-1 faire égal au nombre d'inversions de la permutation, c'est-à-
si (t[j] > t[j + 1]) alors dire de couples (i,j) tels que i < j et T(i) > T(j). Ce nombre
tmp ← t[j] est indépendant de la manière d'organiser les échanges.
t[j] ← t[j+1] ⚫ Le meilleur cas (une seule itération) est atteint quand le
t[j+1] ← tmp tableau est déjà trié. Dans ce cas, la complexité est
échange ← vrai linéaire
fin si
finpour
i←i-1
Fintantque
finprocédure

59
 Tri par sélection Tri par sélection : Animation
⚫ Principe : Sur un tableau de n éléments (numérotés de 1 à n), le principe
du tri par sélection est le suivant :
• rechercher le plus petit élément du tableau, et l'échanger avec l'élément d'indice 1 ;
• rechercher le second plus petit élément du tableau, et l'échanger avec l'élément
d'indice 2 ;
• continuer de cette façon jusqu'à ce que le tableau soit entièrement trié.

⚫ Exemple :
9 4 1 7 3
• Étape 1: on cherche le plus petit parmi les 5 éléments du tableau. On
l’identifie en troisième position, et on l’échange alors avec l’élément 1 :

1 4 9 7 3
• Étape 2: on cherche le plus petit élément, mais cette fois à partir du
deuxième élément. On le trouve en dernière position, on l'échange
avec le deuxième:
1 3 9 7 4
• Étape 3:
1 3 4 7 9

Tri par sélection : algorithme

Tri par sélection : complexité
⚫ Supposons que le tableau est noté T et sa taille n
procédure tri_selection( tableau t : réel par référence , n: entier par valeur)
variable i, j, min: Entier ⚫ Quel que soit l'ordre du tableau initial, le nombre de tests et d'échanges
début reste le même

pour i de 0 à n - 1 ⚫ On effectue N-1 tests pour trouver le premier élément du tableau trié, N-2
min ← i tests pour le deuxième, et ainsi de suite. Soit : (N-1)+(N-2)+…+1 = N(N-1)/2
pour j de i + 1 à n On effectue en plus (N-1) échanges.
si t[j] < t[min], alors
⚫ La complexité du tri par sélection est d'ordre N² à la fois dans le meilleur
min ← j des cas, en moyenne et dans le pire des cas
finpour
si min <> i, alors
échanger (t[i] ,t[min])
finpour
finprocédure

60
Tri par insertion Tri par insertion

⚫ Cette méthode de tri insère (au ième passage) le • Données: un tableau de n éléments à trier
ième élément T[i] à la bonne place parmi • Principe: la partie gauche est triée; on essaie d'insérer chaque
T[1],T[2]...T[i-1]. nouvel élément dans cette liste, en décalant d'un élément la
partie droite restante.
⚫ Après l'étape i, tous les éléments entre la première ⚫place du nouveau
et la ième position sont triés.
⚫ Il existe plusieurs méthode de tri par insertion
⚫liste triée ⚫nouveau
selon le principe qui est utilisé pour rechercher le
rang de l’élément à insérer parmi les éléments du
début de la liste déjà triés ⚫liste triée
⚫reste à trier

Animation : Tri par insertion

Tri par insertion

4 2 0 5 3 Vecteur de départ

2 4 0 5 3 Les cellules 1 à 2 sont triées

0 2 4 5 3 Les cellules 1 à 3 sont triées

0 2 4 5 3 Les cellules 1 à 4 sont triées

0 2 3 4 5 Les cellules 1 à 5 sont triées

61
 Tri par insertion Tri par Insertion : complexité
procédure tri_insertion(tableau T: réel par référence, n:
entier valeur) ⚫ La complexité du tri par insertion est Θ(n2) dans le pire des
Variable i, j, x: entier cas et en moyenne, et linéaire dans le meilleur des cas.
début Plus précisément :
pour i de 1 à n ➢ Dans le pire des cas, atteint lorsque le tableau est trié à
x ← T[i] l'envers, l'algorithme effectue de l'ordre
j←i de n2/2 affectations et comparaisons ;
tant que ( j > 0 et T[j - 1] > x) ➢ Si les éléments sont distincts et que toutes
T[j] ← T[j - 1] leurs permutations sont équiprobables (ie avec
j←j–1 une distribution uniforme), la complexité en moyenne de
fin tant que l'algorithme est de l'ordre de n2/4 affectations et
T[j] ← x comparaisons ;
finpour ➢ Si le tableau est déjà trié, il y a n-1 comparaisons et O(n)

finprocédure affectations.

Tri rapide
Principe de Tri rapide
⚫ Le tri rapide est un tri récursif basé sur l'approche "diviser pour régner"
(consiste à décomposer un problème d'une taille donnée à des sous
problèmes similaires mais de taille inférieure faciles à résoudre) ⚫ La méthode consiste à placer un élément du tableau (appelé pivot) à sa
place définitive, en permutant tous les éléments de telle sorte que tous
⚫ Description du tri rapide : ceux qui sont inférieurs au pivot soient à sa gauche et que tous ceux qui
sont supérieurs au pivot soient à sa droite.
• 1) on considère un élément du tableau qu'on appelle pivot ⚫ Cette opération s'appelle le partitionnement. Pour chacun des sous-
tableaux, on définit un nouveau pivot et on répète l'opération de
• 2) on partitionne le tableau en 2 sous tableaux : les éléments inférieurs
partitionnement. Ce processus est répété récursivement, jusqu'à ce que
l'ensemble des éléments soit trié.
ou égaux à pivot et les éléments supérieurs à pivot. on peut placer
ainsi la valeur du pivot à sa place définitive entre les deux sous ⚫ Concrètement, pour partitionner un sous-tableau :
tableaux ➢on place le pivot à la fin (arbitrairement), en l'échangeant avec le
dernier élément du sous-tableau ;
• 3) on répète récursivement ce partitionnement sur chacun des sous ➢on place tous les éléments inférieurs au pivot en début du sous-
tableaux crées jusqu'à ce qu'ils soient réduits à un à un seul élément tableau ;
➢on place le pivot à la fin des éléments déplacés.

62
 Animation: Tri rapide
Procédure Tri rapide
Procédure TriRapide(tableau T : réel par référence, p, d: entier par valeur)
variable q: entier
Début
Si p <d alors
Partition(T,p,d,q)
TriRapide(T,p,q-1)
TriRapide(T,q+1,d)
FinSi
Fin Procédure

A chaque étape de récursivité on partitionne un tableau T[p..d] en deux

sous tableaux T[p..q-1] et T[q+1..d] tel que chaque élément de T[p..q-1]
soit inférieur ou égal à chaque élément de A[q+1..r] . L'indice q est
calculé pendant la procédure de partitionnement

Procédure de partition
Procédure Partition(tableau T : réel par référence, p, d: entier par valeur,
q: entier par référence )
Procédure de partition
Variables i, j: entier
pivot: réel
Debut
pivot← T[p], i←p+1, j ← d
TantQue (i<=j)
TantQue (i<=d et T[i] <=pivot) i ← i+1 FinTantQue
TantQue (j>=p et T[j] >pivot ) j ← j-1 FinTantQue
Si i <j alors
Echanger(T[i], T[j]), i ← i+1, j ← j-1
FinSi
FinTantQue
Echanger(T[j], T[p])
q←j
Fin Procédure

63
 Comparaison des algorithmes de Tri
Tri rapide : complexité et remarques
⚫ La complexité du tri rapide dans le pire des cas est en O(N²)
Pire des
Nom Cas Optimal Cas Moyen
⚫ La complexité du tri rapide en moyenne est en O(N log N) Cas
n2
⚫ Le choix du pivot influence largement les performances du tri rapide Tri à bulles n n2

⚫ Le pire des cas correspond au cas où le pivot est à chaque choix le plus petit
Tri par n2 n2 n2
élément du tableau (tableau déjà trié) Sélection
Tri par
⚫ différentes versions du tri rapide sont proposés dans la littérature pour rendre n n2 n2
Insertion
le pire des cas le plus improbable possible, ce qui rend cette méthode la plus
rapide en moyenne parmi toutes celles utilisées nlog n n2
Tri Rapide nlog n

[Link]

Présentation

ALGORITHMIQUE ⚫ Le stockage des données dans les variables et

tableaux est temporaire :
→ Les variables et donc les données sont détruites
lorsque l’on quitte l’application. La mémoire est restituée
au système d’exploitation
• Pour les données en entrée : elles sont soit recueillies
manuellement soit assignées de manière statique
Les fichiers dans le code (constantes)

→ Il nous faut une solution permettant la (ré)utilisation

des données d’une exécution à l’autre

64
 Organisation des Fichiers
Les Fichiers
⚫ 3 points essentiels requis pour stocker des informations à long terme : ⚫ 3 Types de fichiers
• Suite d'octets
1. Pouvoir stocker des informations de très grande taille, • Suite d'enregistrements
• Arbre d'enregistrements
2. Les informations ne doivent pas disparaître lorsque le processus
qui les utilise se termine,

3. Plusieurs processus doivent pouvoir accéder simultanément aux

informations.

⚫ SOLUTION : stocker des informations de manière permanente dans des

fichiers sur des périphériques à mémoire de masse : disque dur ou
autres supports.

STRUCTURE DES ENREGISTREMENTS STRUCTURE DES ENREGISTREMENTS

⚫ 2 Possibilités pour structurer les ⚫Exemple:

enregistrements dans un fichier : ⚫Champs de largeur variable :
" Ali"; " KARI";0642156487;« kali@[Link]"
1. Enregistrements avec des champs de largeur "DEROUI";« Khawla";0656912347;« Dkhawla@[Link]"
variable et utilisation d’un caractère spécial, appelé "KABOURI ";« Mehdi";0689765194;« mkabouri@[Link]"
caractère de délimitation "BACHIRI";"Omar";0649875231;« omarb@[Link]"
2. Enregistrements avec des champs de largeur fixe ⚫Champs de largeur fixe:
Ali Kari 0642156487 Kali@[Link]
DEROUI Khawla 0656912347 Dkhawla@[Link]
KABOURI Mehdi 0689765194 mkabouri@[Link]
BACHIRI Omar 0649875231 omarb@[Link]

65
 STRUCTURE DES ENREGISTREMENTS
TYPES D’ACCÈS

⚫Champs de largeur variable : ⚫ Accès séquentiel : Lecture des enregistrements

➢Avantage: faible encombrement en place mémoire ; d’un fichier dans l’ordre à partir du début du fichier
il n’y a aucun espace perdu (enregistrement par enregistrement), mais ne pouvait
pas les lire dans le désordre.
⚫ Accès direct (ou aléatoire (Random Access File) :) :
➢ Inconvénient : lenteur de la lecture et problème Accès direct à l’enregistrement en précisant son
de récupération des champs numéro.
 gestion fastidieuse des déplacements dans le
⚫Champs de largeur fixe: fichier.
➢Avantage: récupération des différents champs est ⚫ Accès indexé : Combine la rapidité de l'accès direct
très rapide et la simplicité de l'accès séquentiel. Il est
➢ Inconvénient : Perte de la place mémoire, particulièrement adapté au traitement des gros
fichiers, comme les bases de données importantes.

INSTRUCTIONS INSTRUCTIONS
⚫Exemples:
⚫ Pour travailler sur un fichier, la première chose à ⚫Ouverture d’un fichier:
faire est de l’ouvrir en précisant le nom du fichier ou Ouvrir "[Link]" sur 4 en Lecture
un numéro de canal
⚫ Les opérations sur le Fichier :lecture, écriture ou Algorithme LectureFichier
ajout. Variables Indiv, Nom, Prénom, Tel, Mail : chaine de Caractères
1. Lecture: on pourra uniquement récupérer les Début
informations qu’il contient, sans les modifier. Ouvrir "[Link]" sur 4 en Lecture
LireFichier 4, Indiv
2. Ecriture: on pourra lire et modifier les informations Nom ← Mid(Indiv, 1, 20)
existantes. Mais les informations précédentes, si Prénom ← Mid(Indiv, 21, 15)
elles existent, seront intégralement écrasées Tel ← Mid(Indiv, 36, 10)
3. Ajout: on ne peut ni lire, ni modifier les Mail ← Mid(Indiv, 46, 20)
informations existantes. Mais on pourra, ajouter de Fermer 4
nouvelles lignes (d’enregistrements). Fin

66
INSTRUCTIONS
Algorithme LectureFichier
Tableaux Nom(), Prénom(), Tel(), Mail(), Etud : chaine de
Caractères INSTRUCTIONS
Variable i : entier ⚫Exemples:
Début
Ouvrir "[Link]" sur 5 en Lecture ⚫Ouverture d’un fichier:
i ← -1
Tantque Non EOF(5) Algorithme OuvFichier
LireFichier 5, Etud
i←i+1 Variable Ch : chaine de Caractères
Redim Nom(i) Début
Redim Prénom(i) Ouvrir "[Link]" sur 5 en Lecture
Redim Tel(i) Tantque Non EOF(5)
Redim Mail(i) LireFichier 5, Ch
Nom(i) ← Mid(Etud, 1, 20) …
Prénom(i) ← Mid(Etud, 21, 15) FinTantQue
Tel(i) ← Mid(Etud, 36, 10) Fermer 5
Mail(i) ← Mid(Etud, 46, 20) Fin
FinTantQue
Fermer 5
Fin

INSTRUCTIONS INSTRUCTIONS
Algorithme permettant de saisir et d’ajouter . Algorithme permettant l’ajout
Algorithme ajout Algorithme ajout
Variables Nom * 20, Prénom * 15, Tel * 10, Mail * 20, Lig : Variable Zone : chaine de Caractères
chaine de Caractères Variables Nom*20, Prénom*15, Tel*10, Mail*20 :
Debut chaine de Caractères
Ecrire "Entrez le nom : " Debut
Lire Nom
Ecrire "Entrez le prénom : " Ouvrir "[Link]" sur 3 en Ajout
Lire Prénom Nom ← " OTMANI"
Ecrire "Entrez le téléphone : " Prénom ← " Hamza"
Lire Tel Tel ← "0537946532"
Ecrire "Entrez le Mail : "
Lire Mail Mail ← " Hotmani@[Link]"
Lig ← Nom & Prénom & Tel & Mail Zone ← Nom & Prénom & Tel & Mail
Ouvrir "[Link]" sur 1 pour Ajout EcrireFichier 3, Zone
EcrireFichier 1, Lig Fermer 3
Fermer 1 Fin
Fin

67
 DONNÉES STRUCTURÉES
STRATÉGIES DE TRAITEMENT
Définition :
Deux manières de traiter les fichiers textes: un enregistrement est une structure de données
1. Modifier directement (ou presque) les informations sur le disque dur.
hétérogène ( éléments de types différents) : c’est donc
2. Recopier l’intégralité du fichier de départ en mémoire vive. lorsque un ensemble d’entités hétérogènes mais liées
le traitement est terminé, recopie à nouveau dans l'autre sens, depuis
la mémoire vive vers le fichier d’origine.
logiquement les unes aux autres.
Les avantages de la seconde technique sont nombreux: Déclaration d’une structure:
⚫ Rapidité : les accès en mémoire vive sont plus rapides (nanosecondes) Structure Individu
que les accès aux mémoires de masse (millisecondes au mieux pour un
disque dur). matricule * 6 : chaine de caratères
⚫ Facilité de programmation : largement plus facile de faire des
traitements avec un tableau qu’avec des fichiers. Désignation * 20 : chaine de Caractères
Inconvénient : Quantité en entier
⚫ Recopie de très gros fichier en mémoire vive exige des ressources;
Prix en réel
⚫ fichier contenant des données de type non homogènes (chaînes,
numériques, etc.) Fin Structure

DONNÉES STRUCTURÉES DONNÉES STRUCTURÉES

I. Données structurées simples: I. Données structurées simples:

❖ la déclaration de la structure ❖ Une structure peut être manipulée :
Structure Etudiant ➢ Individuellement sur chacun des champs
Nom * 20 : chaine de Caractères ➢ ou globalement sur l’ensemble de la structure
Prénom * 15 : chaine de Caractères Exemple :
Tel * 10 : chaine de Caractères
Mail * 20 : chaine de Caractères [Link] ← "OTMANI"
Fin Structure [Link]énom ← "Hamza"
❖ Réserve d’un emplacement nommé individu de [Link] ← " 0537946532 "
type Etudiant [Link] ← " Hotmani@[Link] "
Variable Individu en Etudiant
Individu ← "OTMANI", “Hamza", " 0537946532 ",
"Hotmani@[Link] "

68
I. Données structurées simples II. Tableaux de données structurées
Algorithme de lecture du fichier et de la recopie des données
Accès à un des champs de la variable structurée en mémoire vive, en utilisant un tableau structuré.
En utilisant le point : Algorithme GestEtudiant
[Link] ← " OTMANI" Structure Etudiant
[Link]énom ← " Hamza" Nom * 20 : chaine de Caractères
[Link] ← " 0537946532 " Prénom * 15 : chaine de Caractères
Tel * 10 : chaine de Caractères
[Link] ← " Hotmani@[Link]" Mail * 20 : chaine de Caractères
Fin Structure
L’écriture dans le fichier en utilisant la variable Tableau TabEtudiant[] en Etudiant
Individu Variable i : entier
EcrireFichier 3, Individu Début
Ouvrir "[Link]" sur 3 en Lecture
i←0
Lecture de l’enregistrement du fichier vers la variable Individu: Tantque Non EOF(3)
Redim TabEtudiant[i]
LireFichier 5, Individu LireFichier 3, TabEtudiant[i]
i←i+1
FinTantQue
Fermer 3
Fin

Exercice :
RÉCAPITULATIF
Écrire un algorithme ,en utilisant les procédures ou les
fonctions, qui permet de :
L’utilisation des données d’un fichier nécessite plusieurs choix :
➢Organisation en enregistrements du fichier (choix
➢ saisir des informations sur les étudiants( Nom ;
entre fichier texte ou fichier binaire) prénom ; note en contrôle continu , note en TP , note
➢Type d'accès aux enregistrements du fichier en examen final) sur un fichier.
(direct ou séquentiel ou indexé)
➢ Structure des enregistrements (présence de
➢ Calculer la moyenne générale sachant que le
séparateurs ou champs de largeur fixe) coefficient de chaque note est de : contrôle continu 3 ;
➢Méthode de traitement des informations (recopie TP 2 et note de l’examen final 5.
intégrale du fichier en mémoire vive ou non)
➢Type de variables utilisées (plusieurs tableaux de
➢ Déterminer le nombre des étudiants qui ont la
type simple, ou un seul tableau de type structuré). moyenne générale supérieure à la moyenne de la
classe et afficher les résultats.
Pas de règle de conduite valable. Il faut connaître ces
techniques, et savoir choisir la bonne option selon le problème
à traiter.

69
 Solution : Solution :
Algorithme Notesétudiants Procédure Saisicalnote(n : entier par valeur, Tableau Mesnotes : par
Structure etudiant référence )
Nom * 20 : chaine de Caractères variables i : entier
Prénom * 15 : chaine de Caractères Début
Notecc en réel
Ouvrir "[Link]" sur 2 pour Ecriture
Notetp en réel
Pour i allant de 0 à n-1
NoteEF en réel écrire ("Entrez les informations sur l’étudiant ", i + 1, )
Moyeng en réel lire ([Link][i])
Fin Structure
lire ([Link]énom[i])
Tableau Mesnotes[] en etudiant
lire ([Link][i])
Variables n: entier
lire ([Link][i])
Début
lire ([Link][i])
écrire ("Entrez le nombre des etudiants ")
[Link][i]  ([Link][i]*3+ [Link][i]*2+
lire (n)
[Link][i]*5)/10
Saisicalnote(n, Mesnotes)
EcrireFichier 2, MesNotes[i]
Afficherésultat(n,Mesnotes)
FinPour
Fin
Fin Procédure

Procédure Afficherésultat (n : entier par valeur, Tableau Mesnotes : par

valeur )
Variables i , NbSup: entier,
variables som, moy : réel
Début
Som  0
Pour i allant de 0 à n-1
écrire ("La moyenne générale de l’étudiant ", [Link](i) ,
"=", [Link] [i])
Som Som + [Link] [i]
Finpour
Moy  Som / n, NbSup  0
Pour i allant de 0 à n - 1
Si [Link] [i] > Moy Alors
NbSup  NbSup + 1
FinSi
FinPour
Ecrire( NbSup, " élèves dépassent la moyenne de la classe" )
Fin Procédure

70