déc.

-22

Objectifs

1. Connaître les points principaux d’un langage algorithmique.

2. Simuler l’exécution d’un algorithme (dérouler un algorithme).
3. Écrire soi-même un algorithme.
Algorithmique 4. Connaître certains algorithmes classiques (recherches, tris...).

Initiation à la Programmation 5. Connaître les bases du langage de programmation - Python.

Pr Sara RIAHI
2022/2023

Introduction
Introduction
Chapitre 1 : Les éléments de base d’un algorithme
Chapitre 2 : Les structures alternatives et répétitives Algorithme : mot dérivé du nom du mathématicien Al_Khawarizmi qui a vécu au
Chapitre 3 : Les Tableaux 9ème siècle, était membre de l’académie des sciences à Bagdad .
Chapitre 4 : Les structures • Un algorithme prend des données en entrée, exprime un traitement particulier et
fournit des données en sortie.
Chapitre 5 : Les fonctions prédéfinies
• Programme : série d’instructions pouvant s’exécuter en séquence, ou en parallèle
Chapitre 6 : Les algorithmes de tri et de recherche (parallélisme matériel) qui réalise (implémente) un algorithme
Exercices corrigés
POURQUOI UN COURS D’ "ALGO" ?

Introduction

▪ Pour obtenir de la «machine» qu’elle effectue un travail à notre place

▪ Problème: expliquer à la «machine» comment elle doit s'y prendre Savoir expliquer comment faire un travail sans la moindre ambiguïté

Besoins : • Langage simple : des instructions ( élémentaires)

• Savoir expliciter son raisonnement • Suite finie d'actions à entreprendre en respectant une chronologie imposée
• L’écriture algorithmique : un travail de programmation à visée universelle
• Savoir formaliser son raisonnement
• Concevoir (et écrire) des algorithmes: • Un algorithme ne dépend pas du langage dans lequel il est implanté, ni de la machine qui exécutera le
programme correspondant.
• Séquence d’instructions qui décrit comment résoudre un problème particulier

C’est quoi un Algorithme ?

Est-ce un algorithme est parfait !

1
 déc.-22

Les problèmes en Algorithmique

Les étapes d’un Algorithme :

Complexité
• Préparation du traitement
• En combien de temps un algorithme va -t-il atteindre le résultat escompté?
données nécessaires à la résolution du problème
• De quel espace a-t-il besoin?
• Traitement
Calculabilité
résolution pas à pas, après décomposition en sous-problèmes si nécessaire
• Existe-t-il des tâches pour lesquelles il n'existe aucun algorithme ?
• Edition des résultats
• Etant donnée une tâche, peut-on dire s'il existe un algorithme qui la résolve ?
impression à l’écran,
Correction
dans un fichier, etc.
• Peut-on être sûr qu'un algorithme réponde au problème pour lequel il a été conçu ?

Quelques définitions avant de commencer Pourquoi apprendre l’algorithmique pour apprendre à programmer ?
Un algorithme est une suite ordonnée d’instructions qui
indique la démarche à suivre pour résoudre une série de
problèmes équivalents Parce que l’algorithmique exprime les instructions résolvant un problème donné
L’algorithmique est la science des algorithmes , s’intéresse indépendamment des particularités de tel ou tel langage.
▪ Algorithme à l’art de construire des algorithmes ainsi qu’a caractériser
leur validité , robustesse , réutilisabilité , complexité et Apprendre l’algorithmique, c’est apprendre à manier la structure logique d’un programme
▪ Algorithmique leur efficacité informatique.
La validité d’un algorithme est son aptitude à réaliser
▪ Validité d’un Algorithme exactement la tache pour laquelle il a été conçu.

▪ Robustesse d’un Algorithme La robustesse d’un algorithme est son aptitude à se

protéger des conditions anormales d’utilisation . Cette dimension est présente quelle que soit le langage de programmation.
▪ Réutilisabilité d’un Algorithme La réutilisabilité d’un algorithme est son aptitude à
être réutilisé pour résoudre des taches équivalentes
▪ Complexité d’un Algorithme à celle pour laquelle il a été conçu ,

▪ Efficacité d’un Algorithme La complexité d’un algorithme est le nombre

d’instructions élémentaires à exécuter pour réaliser la Avec quelles conventions écrit-on un algorithme ?
tache pour laquelle il a été conçu
L’efficacité d’un algorithme est son aptitude à
utiliser de manière optimale les ressources du
matériel qui l’exécute

Représentation d’un Algorithme

Il y a eu notamment une représentation graphique, avec des carrés, des losanges, etc. qu’on Historiquement, deux façons pour représenter un algorithme:
appelait des organigrammes. Aujourd’hui, cette représentation est quasiment abandonnée,
pour deux raisons.
▪ L’Organigramme: représentation graphique avec des symboles (carrés, losanges, etc.)
D’abord, parce que dès que l’algorithme commence à grossir un peu, ce n’est plus pratique
du tout du tout………. ➢ Offre une vue d’ensemble de l’algorithme
Ensuite parce que cette représentation favorise le glissement vers un certain type de ➢ Représentation quasiment abandonnée aujourd’hui
programmation, dite non structurée, que l’on tente au contraire d’éviter.
▪ Le pseudo-code: représentation textuelle avec une série de conventions ressemblant à un
C’est pourquoi on utilise généralement une série de conventions appelée « pseudocode », langage de programmation (sans les problèmes de syntaxe)
qui ressemble à un langage de programmation authentique dont on aurait évacué la plupart ➢ Plus pratique pour écrire un algorithme
des problèmes de syntaxe
➢ Représentation largement utilisée

2
 déc.-22

Bases de l’algorithmique Algorithmique et Programmation

Tout problème à programmer doit être résolu , d’abord sous forme d’algorithme , puis
converti en programme dans le langage de notre choix .
Données Calcul
En effet , un algorithme est indépendant du langage de programmation utilisé
Variables Instructions
Un programme est un enchainement d’instructions , écrit dans un langage de
Structures Conditions programmation , exécutées par un ordinateur , permettant de traiter un problème et de
Tableaux Boucles renvoyer des résultats .
Pointeurs Fonctions Il représente la traduction d’un algorithme à l’aide d’un langage de programmation
Modèles dynamiques Récursion Le cycle de développement d’un programme informatique peut se résumer ainsi :
Analyse Programmation Exécution

L’ algorithmique c’est le choix d’un algorithme - le choix d’une structure de données

Problème Algorithme Programme Résultats
les deux sont indissociables

Cycle de développement d’un programme

Chapitre 1
Structure générale d’un algorithme
Chapitre 1 : Les éléments de base d’un algorithme
Un algorithme est composé de trois parties principales: Le moule d’un Algorithme
Un Algorithme comportera
l’en-tête : cette partie sert à donner un nom à l’algorithme.
Elle est précédée par le mot Algorithme ;
Une partie déclaration
Une partie encadrée par Debut – Fin où sont décrite les actions
la partie déclarative : dans cette partie, on déclare les différents
objets que l’algorithme utilise (constantes, variables,
Déclaration des Constantes
etc.) Déclaration des Variables
Déclaration des Fonctions
le corps de l’algorithme : cette partie contient les instructions de
l’algorithme. Elle est délimitée par les mots Début et Fin.

Suite d’instructions
Structure Alternatives
Structure Répétitive

Structure d’un Algorithme

Chapitre 1 Types de données Chapitre 1

I Les variables et les constantes
I.1 Notion de variable Le type d’une variable est l’ensemble des valeurs qu’elle peut prendre.
Les données ainsi que les résultats des calculs intermédiaires ou finaux, sont rangés dans des Par exemple, une variable de type logique (booléen) peut prendre les
cases mémoires qui correspondent à des variables. Ainsi, une variable est rangée dans un valeurs Vrai ou Faux.
emplacement mémoire nommé, de taille fixe (ou non) prenant au cours du déroulement de
l'algorithme, un nombre indéfini de valeurs différentes.
I. 2 Déclaration des variables
La partie déclaration consiste à énumérer toutes les variables dont on aura besoin au cours
de l'algorithme. Chaque déclaration doit comporter le nom de la variable (identificateur) et
son type.
Les Constantes
Syntaxe Un identificateur est le
Comme une variable, à une constante correspond un
nom donné à une variable emplacement mémoire réservé auquel on accède par le
Variable identificateur : type , une fonction , etc . nom qui lui a été attribué, mais dont la valeur stockée
Ce nom doit ne sera jamais modifiée au cours du programme.
obligatoirement
commencer par une lettre
suivie d’une suite de Syntaxe :
lettres et de chiffres et il Constante NOM_DE_LA_CONSTANTE = valeur
ne doit pas contenir
d’espace
EX: Constante PI = 3.14

3
 déc.-22

II Les instructions de base :

II.2 L’instruction d’entrée :
Une instruction est une action élémentaire commandant à la machine un calcul, ou une
communication avec l’un de ses périphériques d’entrées ou de sorties. Les instructions de
base sont : L’instruction d’entrée ou de lecture donne la main à l’utilisateur pour saisir une donnée au
L’instruction d’affectation L’instruction d’entrée L’instruction de sortie clavier. La valeur saisie sera affectée à une variable.
II.1 L’instruction d’affectation : Syntaxe :
L’affectation permet d’affecter une valeur à une variable. Elle est symbolisée en algorithmique Lire (identificateur) Lorsque le programme rencontre cette
instruction, l’exécution s’interrompt et
par Exemples : attend que l'utilisateur tape une valeur.
Expression peut être soit :
Le signe précise le sens de l’affectation ▪ Identificateur ;
Lire(A)
▪ Constante ; Cette valeur est rangée en mémoire dans la
Variable ← Expression ▪ Expression arithmétique ; Lire(A, B, C) variable désignée
▪ Expression logique.
Exemple :
L’instruction Lire(A) permet à l’utilisateur de saisir une valeur au clavier.
Cette valeur sera affectée à la variable A.

II.3 L’instruction de sortie: Exemple d’application

Avant de lire une variable, il est conseillé d’écrire des libellés à l’écran, afin de prévenir Un algorithme qui permet de saisir le prix hors taxe d’un article et de calculer son prix total
l’utilisateur de ce qu’il doit saisir . avec un taux de TVA de 20%.
L'instruction de sortie (d’écriture) permet d’afficher des informations à l'écran.
;
Syntaxe :
Ecrire (expression)
Expression peut être une valeur, un résultat, un message, le contenu d'une variable, etc.
Exemples :
Ecrire (A)
Cette instruction permet d’afficher à l’écran la valeur de la variable A.
II.4 Les commentaires :
Lorsqu’un algorithme devient long, il est conseillé d’ajouter des lignes de commentaires dans
l’algorithme, c'est-à-dire des lignes qui ont pour but de donner des indications sur les
instructions effectuées et d’expliquer le fonctionnement du programme (algorithme) sans que
le compilateur ne les prenne en compte.

Exercices d’applications Exercices d’applications

Exercice2 : Écrire un algorithme permettant de calculer la moyenne de deux entiers.

Exercice 1: Écrire un algorithme qui permute les valeurs de deux variables lues au clavier.

4
 déc.-22

Exercices d’applications Chapitre 2 : Les structures alternatives et répétitives

Exercice 3: Un supermarché accorde à ses clients, une réduction de 3% sur le montant Contrairement aux structures séquentiels, La structure alternative ou conditionnelle permet
d'achat. d’exécuter ou non une série d’instructions selon la valeur d’une condition.
Écrire un algorithme permettant de Lire le montant d'achat (MA) et de calculer le montant de La structure alternative permet d’exécuter un bloc d’instructions ou un autre en fonction de la
la remise (R) ainsi que le montant à payer (MP). réponse de la condition
II.1 Structure Alternative Simple
Cette structure permet d’effectuer certaines opérations ou au contraire de ne rien faire .
▪ Si ….Alors ……FinSi
Cette instruction se lit : Syntaxe :

Si la condition est vérifiée Alors l’instruction serait exécuté

Cette structure est utilisée si on veut exécuter une instruction(s) seulement si une condition
est vraie et ne rien faire si la condition est fausse

Chapitre 2
II.2 Structure Alternative Complète : Organigramme !!
▪ Si ….Alors …..Sinon……FinSi
Cette instruction se lit :
Si la condition est vérifiée Alors le bloc d’instructions serait exécuté Sinon il serait ignoré Pseudocode
Syntaxe :

Organigramme

II.3 Structure Alternative Imbriquée : Syntaxe :

▪ Si ….Alors ……SinonSi…..Sinon….FinSi
L’instruction qui sera exécutée est Certaines parties de l’algorithme ou du code sont en retrait par
l’instruction dont la condition est rapport à d’autres , c’est ce qu’on appelle l’indentation .
vraie. Si aucune condition n’a la L’indentation est très importante pour la lisibilité de l’algorithme ou du programme , elle montre rapidement le
valeur vraie, c’est l’instruction qui début et la fin de chaque instruction alternative ou répétitive ainsi que le début et la fin de l ’algorithme ou du
suit le Sinon qui sera exécutée programme.

Exercices d’applications Exercices d’applications

Exercice 6:
Exercice 5: Ecrire un algorithme qui demande deux nombres à l’utilisateur et l’informe ensuite Ecrire un algorithme qui résout une équation du premier degré A x + B = 0
si leur produit est négatif ou positif (on laisse de côté le cas où le produit est nul).
La solution de l’équation : A X +B=0 dépend
des valeurs de A et B

▪ Si A=0 et B=0 alors la

solution est l’ensemble des
réels
▪ Si A=0 et B≠0 alors pas de
solution
▪ Si A≠0 alors X = -B/A

5
 déc.-22

II. 4 Les structures répétitives /itératives - Les boucles II.4.1 La boucle Tant que…Faire / While …...do :
Une structure répétitive, encore appelée boucle, est utilisée quand une instruction ou une La boucle TantQue permet de répéter un traitement tant que la condition est vraie.
liste d’instructions, doit être répétée plusieurs fois. La répétition est soumise à une
condition. Syntaxe :
Les boucles servent à répéter l'exécution d'un groupe d'instructions un certain nombre de
fois.
On distingue trois sortes de boucles en langages de programmation :
L’exécution de la boucle dépend de la valeur de la condition. Si elle est vraie, le programme
▪ Les boucles Tant que……faire : on y répète des instructions tant qu'une certaine condition exécute les instructions qui suivent, jusqu’à ce qu’il rencontre la ligne FinTantQue.
est réalisée Il retourne ensuite sur la ligne du TantQue, procède au même examen, et ainsi de suite.
▪ Les boucles Pour avec compteur : on y répète des instructions en faisant évoluer un ▪La condition (condition de contrôle de la boucle) est évaluée avant chaque itération
compteur (variable particulière) entre une valeur initiale et une valeur finale
▪Si la condition est vraie, on exécute les instructions (corps de la boucle), puis on retourne
▪ Les boucles Répéter ….. Tant que :Comme pour la boucle Tant que , le nombre d'itération tester la condition. Si elle est encore vraie, on répète l'exécution, …
n'est pas connu à l'avance. La boucle est exécuté au moins une fois.
▪ Si la condition est fausse, on sort de la boucle et on exécute l'instruction qui est après
Dans ce cours, on va s'intéresser essentiellement aux boucles Tant que et boucles Pour qui sont plus utilisées FinTantQue La boucle ne s’arrête que lorsque la condition prend la valeur fausse,
et dans ce cas le programme poursuit son exécution après FinTantQue

Boucle TantQue en algorigramme:

▪ Le nombre d'itérations dans une boucle TantQue n'est pas connu au moment d'entrée dans
la boucle. Il dépend de l'évolution de la valeur de condition ➢ le fonctionnement de la boucle TantQue :
Attention aux boucles infinies
Exemple de boucle infinie 1) Quand le processeur arrive sur une boucle
Les opérateurs :
TantQue, il regarde l’expression qui est entre
Incrémentation : i++ incrémente la variable i de 1 parenthèses.
Décrémentation : j - - décrémente la variable j de 1 2) Si cette expression est vraie :
Les opérateurs ++ et - - sont employés dans les cas suivants:
Il va exécuter les instructions qui se trouvent
dans le corps de la boucle, entre le faire et le
incrémenter/décrémenter une variable (ex: dans une boucle). Dans FinTantQue (ou entre les { } dans la plupart des
ce cas il n'y a pas de différence entre la notation préfixe (++I - - I) et
X = I++ la notation postfixe (I++ I - - ).
langages).
passe d'abord la valeur de I à X et incrémente après. Quand il a fini d’exécuter toutes les instructions
X = I- - ▪ incrémenter/décrémenter une variable et en même temps du corps de boucle, il retourne à l’étape 1)
passe d'abord la valeur de I à X et décrémente après. affecter sa valeur à une autre variable.
X = ++I 3) Si cette expression est fausse:
incrémente d'abord et passe la valeur incrémentée à X. ✓ Dans ce cas, nous devons choisir entre la notation préfixe et il saute le corps de la boucle et va directement
X = - -I postfixe: exécuter les instructions qui se trouvent après.
décrémente d'abord et passe la valeur décrémentée à X.

Récap – Boucle Tant Que : II.4.2 La boucle Pour / for :

Organigramme
Cette première forme permet de construire une boucle sur une portion de code (autour d’un
Algorithme
bloc d’instructions) lorsque l’on connaît dés l’entrée dans la boucle le nombre d’itérations
souhaitées.
Pseudo-code
Syntaxe :

// Action avant la boucle

Tant que (condition) faire
{
// Action répétée dans la boucle
}
Sa construction s’articule autour de trois éléments :
// Action après la boucle 1. un élément d’initialisation exécuté avant toutes les boucles.
2. un élément de condition de boucle vérifié avant chaque boucle.
3. un élément d’instruction de fin de boucle (souvent une incrémentation ou une
décrémentation) exécuté après chaque boucle.
Ces trois éléments sont séparés par des points-virgules ”;”.

6
 déc.-22

Boucle Pour en algorigramme:

Exemple :

➢ le fonctionnement de la boucle Pour :

l'initialisation se produit en premier et une seule fois.

A chaque passage dans la boucle, la condition est testée;

▪ Si elle est vraie, le bloc d'instruction et l'incrément (le

« pas ») sont exécutés, puis la condition est testée à
▪ l´élément i = 1 initialise la variable i à 1. Il suppose l’existence préalable de la variable i nouveau.
(donc sa déclaration en amont). ▪ Quand la condition devient fausse, la boucle se termine.
▪ l´élément i <= 5 constitue la condition pour entrer dans la boucle (c’est la condition qui
autorise l’exécution du bloc d’instructions de la boucle).
▪ l´élément i = i + 1 correspond à l’incrémentation (on remplace parfois en i++ à la fin de
chaque boucle).

Récap – Boucle Pour : Organigramme ▪ Choix du type de la Boucle

Algorithme ✓ Si on peut déterminer le nombre d’itérations avant l’exécution de la boucle , il est plus
naturel d’utiliser la boucle Pour .
Pseudo-code
✓ S’il n’est pas possible de connaitre le nombre d’itérations avant l’exécution de la boucle , on
ferra appel à Tant Que .
▪ Lien entre Pour et Tant Que
// Action avant la boucle ✓La boucle Pour est un cas particulier de Tant Que (cas ou le nombre d’itérations est connu et
Pour (i=0 ; i<=10 ; i++)
{
fixé ).
// Action répétée dans la boucle ✓Tout ce qu’on peut écrire avec Pour peut être remplacé avec Tant que ( la réciproque est
} fausse)
// Action après la boucle

Imbrications de Boucle Important- choix du type de Boucle

Une structure répétitive ou( structure itérative )répète l’exécution d’un traitement , dans un
ordre précis , un nombre déterminé ou indéterminé de fois .
Imbrications Autorisées Imbrications Interdites
Une structure itérative est aussi appelé une Boucle
Deux cas sont cependant à envisager , selon que :

▪Le nombre de répétitions est connu à l’avance : c’est le cas des boucles itératives .
▪Le nombre de répétitions n’est pas connu ou variable : c’est le cas des boucles conditionnelles .

✓Dans tout les cas où la boucle Pour est appliquée nous pouvons utiliser la boucle Tant que
✓En général , si la première itération est réalisée sans condition , on peut utiliser l’instruction
répéter au lieu de tant que ,
✓La boucle répéter est équivalente à la boucle tant que

7
 déc.-22

Exercices d’applications ➢Boucles Imbriquées :

Les instructions d’une boucle peuvent être des instructions itératives
Exercice 1 : Dans ce cas , on aboutit à des boucles imbriquées

Ecrire un algorithme qui

Une boucle imbriquée est une boucle dans une boucle, une boucle à l'intérieur du corps d'une
affiche tous les nombres entre autre boucle.
deux nombres entiers N1 et
N2 et qui sont divisibles par un Ce qui se passe est que le premier tour de la boucle externe déclenche la boucle interne, qui
s'exécute jusqu'au bout.
nombre entier d .
Puis le deuxième tour de la boucle externe déclenche la boucle interne une nouvelle fois.
Ceci se répète jusqu'à ce que la boucle externe termine.
Bien sûr, un break à l'intérieur de la boucle interne ou externe peut interrompre ce processus.

L’instruction break : Elle sert à interrompre le déroulement d’une boucle

L’instruction Continue : Elle permet à passer au tour de boucle suivant

Exercices d’applications Exercices d’applications

Exercice 2: Exercice 3 :

Ecrire un algorithme
Ecrire un algorithme qui calcul la permettant de saisir N notes ,
factorielle d’un nombre entier n. de calculer la somme et la
moyenne de ces notes .

Chapitre 3
➢ Boucles Infinies : Chapitre 3 : Les Tableaux
Une boucle infinie est, en programmation informatique, une boucle dont la condition de sortie
n'a pas été définie ou ne peut pas être satisfaite. Un programme peut être amené à manipuler de nombreuses variables représentant des
valeurs distinctes mais de même nature.
Par exemple, un relevé de plusieurs températures en plusieurs endroits et à plusieurs dates
nécessitera autant de valeurs entières que de températures à stocker.
Il est difficilement envisageable de définir « manuellement » autant de variables que de
valeurs à stocker.
Les tableaux, en informatique, permettent de résoudre ce problème en proposant la
création de plusieurs variables de même type, d’une manière très compacte.
Définition :
Un tableau se définit en indiquant son nom, le type des éléments stockés dans le tableau,
ainsi que leur nombre, écrit entre crochets. Ce nombre se nomme également la taille
En conséquence, la boucle ne peut se terminer qu'à l'interruption du programme qui l'utilise. maximale du tableau.
Syntaxe :
Comment CHOISIR LE TYPE DE BOUCLE à utiliser? VAR nom_du_tableau : type_des_éléments [taille_maximale]

8
 déc.-22

Exemple
Relation entre tableaux et boucles :
VAR tab : entier[100]
Est la définition d’un tableau nommé tab qui peut stocker 100 valeurs de type entier au
maximum. La taille maximale d’un tableau doit être une constante numérique. Les boucles sont extrêmement utiles pour les algorithmes associés aux tableaux.

Indication En effet, de nombreux algorithmes relatifs au tableau nécessitent de parcourir les éléments du
tableau dans un certain ordre, le plus souvent dans le sens des indices croissant.
Un tableau est en réalité une variable comme les autres, mais son type est d’une nature
radicalement différent des types présentés plus haut. En particulier, ce n’est pas le type des Le traitement de chacun des éléments étant souvent le même, seule la valeur de l’indice est
amenée à changer.
éléments stockés.
Ainsi : Une boucle est donc parfaitement adaptée à ce genre de traitements.

• Un tableau stockant des entier n’est pas un entier . Les éléments d’un tableau sont des L’utilisation de ces éléments se fait en suite , via le
variables indicées qui s’utilisent exactement nom du tableau et son indice .Ce dernier peut être
• Un tableau stockant des réel n’est pas un réel . comme n’importe quelles autres variables soit une valeur ( Tab[3]) , soit une variable (Tab[i])
• Un tableau stockant des caractères n’est pas un caractère. classiques. Elles peuvent faire l’objet d’une ou encore une expression (Tab[i+1]).
affectation , elles peuvent figurer dans une
expression arithmétique , dans une Il ne faut pas confondre l’indice d’un élément d’un
comparaison , elles peuvent être affichées tableau avec son contenu.
et saisies .

III.1 Représentation du Tableau Important :

Un tableau peut être vu comme un ensemble de « cases » où chaque case stocke une valeur.
Soit la définition suivante : VAR Vals : réel[15] Un tableau est une suite d’éléments de même type .Il utilise plusieurs cases mémoire à l’aide
Cette définition crée un tableau nommé vals qui stocke au maximum quinze réel dans quinze d’un seul nom. Comme toutes les cases portent le même nom, elles se différencient par un
cases différentes. Aucune de ces cases n’est initialisée, ce qui est indiqué par un « ? ». numéro ou un indice .
Nous pouvons représenter schématiquement un tableau nommé Note composé de cinq cases
Tableau Vals ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? , dans la mémoire comme suit:
Chacune de ces cases est repérée par son numéro ou indice à l’intérieur du tableau.
Un tableau de taille maximale N verra ses cases numérotées de 0 à N–1. En effet, pour un
ordinateur, la valeur 0 est une valeur comme une autre. Soit i un indice (i est donc de type
entier puisqu’il s’agit d’un numéro de case). La valeur stockée dans la case d’indice i d’un
tableau tab se nomme tab[i]. Nous disposons alors de cinq variables .
Pour les nommer , on indique le nom du tableau suivi de son indice entre crochets ou entre
parenthèses: La première s’appelle Note [1], la deuxième Note[2],….jusqu’à la dernière
Note[5].
Note[4]représente le 4 ième élément du tableau Note et vaut 13.

III.1.1 Déclaration d’un tableau à une dimension : Important : La taille utile :

La déclaration d’un tableau permet d’associer à un nom une zone mémoire composée d’un Le fait de donner la taille maximale d’un tableau
certain nombres de cases mémoires de même type. Il ne faut pas confondre la valeur notée entre sous la forme d’une constante est une contrainte
Syntaxe: crochets lors de la définition du tableau lourde, puisque cette valeur est fixée lors de
l’écriture du programme. Or un tableau ne stockera
Variable identificateur: tableau [taille]de type (la taille maximale) et la valeur notée entre
Ou pas, en pratique, toujours autant d’éléments que sa
crochets lors des instructions (l’indice). taille maximale. Il est donc nécessaire de savoir
Variable identificateur: tableau [ indice_min…indice_max] de type
Toute expression qui donne une valeur combien de variables sont réellement intéressantes
▪ Le premier élément d’un tableau porte l’indice Exemple : entière peut jouer le rôle d’indice lors de à traiter.
zéro ou l’indice 1 selon les langages . l’accès aux valeurs stockées dans un tableau. Ce nombre de variables doit être stocké dans une
L’instruction suivante déclare un tableau de 30 éléments de type variable de type entier nommé taille utile du
▪ La valeur d’un indice doit être un nombre entier . réel:
La notation t[i], où t est un tableau et i un
tableau par opposition à la taille maximale fournie
Variable Note : tableau[1 .. 30] de Réels indice est équivalente à une variable et peut à la définition du tableau. Dans un tableau dont la
▪ La valeur d’un indice doit être inférieure ou égale être utilisée comme telle dans un taille utile est P et dont la taille maximale est N, les
au nombre d’éléments du tableau. Note : c’est le nom du tableau (identificateur)
programme. variables intéressantes seront rangées aux indices
Cette variable est considérée comme ayant le compris entre 0 et P–1. Les cases dont les indices
Exemple : 1 : c’est l’indice du premier élément du tableau
vont de P à N–1 stockent des valeurs (car une
type des éléments stockés dans le tableau.
avec le tableau tab[1 .. 20], il est impossible d’écrire 30: c’est l’indice du dernier élément du tableau(nombre variable n’est jamais vide) mais elles ne seront pas
tab[0] et tab[21] , ces expressions font référence à d’éléments du tableau). concernées par les traitements ou instructions
des éléments qui n’existent pas . effectuées.

9
 déc.-22

Taille du Tableau : Accès aux composantes d’un tableau à une dimension

À chaque définition d’un tableau est associée la définition de sa taille utile. En déclarant un tableau par :
T: tableau [1 .. 10]de Entier ;
Ceci doit être systématique.
On définit un tableau T de 10 composantes , indicées de 1 à 10.
Cette taille utile peut évoluer lorsque :
Composante de T T[1] T[2] T[3] T[4] T[5] T[6] T[7] T[8] T[9] T[10]
• Un élément est ajouté au tableau, dans ce cas la taille utile est augmentée de 1 (ou encore
incrémentée). Avant d’ajouter un élément, il faut vérifier qu’il reste au moins une case
Indice 1 2 3 4 5 6 7 8 9 10
disponible : la taille utile doit être inférieure strictement à la taille maximale du tableau. Cette
vérification est réalisée par l’emploi d’un test (instruction si).
•Un élément est retiré du tableau, dans ce cas la taille utile est diminuée de 1 (ou Pour accéder aux composantes du tableau T , on spécifie le nom du tableau et l’indice de la
décrémentée). Avant d’enlever un élément du tableau, il faut vérifier que la taille utile est composante:
strictement positive, c’est-à-dire qu’il y a au moins un élément dans le tableau. Enfin, cette T[1] , T[2] ,….., T[10]
variable stockant la taille utile d’un tableau n’a pas de nom qui lui est spécifiquement dédié.
Pour des raisons de lisibilité, cette variable sera nommée util ou tai_ut par exemple.

Exemple d’application : Quelques applications sur les tableaux

Déclarer deux tableaux nommés A et B composé chacun d’eux de 10 éléments de type chaine . Affectation d’un tableau à une dimension Affectation avec des valeurs initiales
Variables A, B : tableau [1 .. 10] de chaine Affectation avec des valeurs entrées au clavier

Lorsqu’on déclare un tableau , on déclare aussi de façon implicite toutes les variables indicées
qui le constituent .Nous utiliserons souvent la valeur 1 comme premier indice mais on peut
aussi utiliser un autre indice minimum, comme 0 .Dans ce cas l’indice maximum sera égal au
nombre d’éléments-1 .

Quelques Instructions :
▪L’instruction suivante affecte à la variable X la valeur du premier élément du tableau Note .
X ← Note [1]
▪L’instruction suivante affiche le contenu du quatrième élément du tableau Note.
Ecrire (Note [4])
▪L’instruction suivante affecte une valeur introduite par l’utilisateur à l’élément trois du tableau
Note
Lire (Note [3])

Affichage du contenu d’un tableau à une dimension Affichage de quelques composantes

Exercices d’applications
Affichage des valeurs d’un tableau dans l’ordre

Exercice 1:

Ecrire un algorithme permettant de

saisir 30 notes dans un tableau et de
les afficher après avoir multiplié
toutes ces notes par un coefficient
fourni par l’utilisateur .

10
 déc.-22

Exercices d’applications Tri d’un tableau à une dimension dans l’ordre croissant

Soit un tableau T de dimension 6 , rempli des valeurs suivantes :

Exercice 2: 6 4 1 2 16 5

Ecrire un algorithme qui calcul la Etape 1 : rechercher la plus grande valeur dans le tableau pour l’indice i variant de 1 à 6 .
somme des éléments d’un Etape 2 : rechercher la plus grande valeur dans le tableau pour l’indice i variant de 1 à 5 .
tableau.
Etape 3 : rechercher la plus grande valeur dans le tableau pour l’indice i variant de 1 à 4 .
Etape 4 : rechercher la plus grande valeur dans le tableau pour l’indice i variant de 1 à 3 .
Etape 5 : rechercher la plus grande valeur dans le tableau pour l’indice i variant de 1 à 2 .
Après ces étapes on aura le tableau trié dans l’ordre croissant

Etape 1 : rechercher la plus grande valeur dans le tableau pour l’indice i variant de 1 à 6 . Etape 2: rechercher la plus grande valeur dans le tableau pour l’indice i variant de 1 à 5 .
5 16

On trouve le maximum Max =16 qui se trouve à la position pi =5. On trouve le maximum Max =6 qui se trouve à la position pi =1.
On échange le maximum Max=16avec la dernière composante T[6] On échange le maximum Max=6 avec la composante T[5]
On aura le tableau suivant : Max ← T[pi] ; On aura le tableau suivant : Max ← T[pi] ;
T[pi] ← T[6] ; T[pi] ← T[5] ;
5 16 T[6] ← Max ; 6 T[5] ← Max ;

En Algorithmique
En Algorithmique
Max ← T[6-1+1]; // initialisation de Max à T[6]
Max ← T[6-2+1]; // initialisation de Max à T[5]
Pour i ← 1 à 6 Faire
Pour i ← 1 à 5 Faire
Si ( T[i]> Max) alors
Si ( T[i]> Max) alors
Max ← T[i];
Max ← T[i];
pi ← i; // pi est la position du Max
pi ← i; // pi est la position du Max
FinSi
FinSi
FinPour
1 ère étape FinPour 2 ème étape
Max ← T[pi] ;
Max ← T[pi] ;
T[pi] ← T[6] ; // T[6] = T[6-1+1]
T[pi] ← T[5] ; // T[5] = T[6-2+1]
T[6] ← Max ;
T[5] ← Max ;

Etape 3: rechercher la plus grande valeur dans le tableau pour l’indice i variant de 1 à 4 . Etape 4: rechercher la plus grande valeur dans le tableau pour l’indice i variant de 1 à 3.
5 6 16 52 5 6 16

On trouve le maximum Max =5 qui se trouve à la position pi =1. On trouve le maximum Max =4 qui se trouve à la position pi =2.
On échange le maximum Max=5 avec la composante T[4] On échange le maximum Max=4 avec la composante T[3]
On aura le tableau suivant : Max ← T[pi] ; On aura le tableau suivant : Max ← T[pi] ;
T[pi] ← T[4] ; T[pi] ← T[3] ;
2 5 6 T[4] ← Max ; 2 1 4 5 6 T[3] ← Max ;

En Algorithmique En Algorithmique

Max ← T[6-3+1]; // initialisation de Max à T[4] Max ← T[6-4+1]; // initialisation de Max à T[3]
Pour i ← 1 à 4 Faire Pour i ← 1 à 3 Faire
Si ( T[i]> Max) alors Si ( T[i]> Max) alors
Max ← T[i]; Max ← T[i];
pi ← i; // pi est la position du Max pi ← i; // pi est la position du Max
FinSi FinSi
FinPour 3 ème étape FinPour 4 ème étape
Max ← T[pi] ; Max ← T[pi] ;
T[pi] ← T[4] ; // T[4] = T[6-3+1] T[pi] ← T[3] ; // T[3] = T[6-4+1]
T[4] ← Max ; T[3] ← Max ;

11
 déc.-22

Etape 5: rechercher la plus grande valeur dans le tableau pour l’indice i variant de 1 à 2. Recherche de la plus grande valeur dans un tableau L’algorithme de tri sera donc

52 1 4 5 6 16 Pour une J ème étape

On trouve le maximum Max =2 qui se trouve à la position pi =1.

On échange le maximum Max=2 avec la composante T[2] Max ← T[6-J+1]; // initialisation de Max à T[6-J+1] Pour J ← 1 à 6 -1 Faire // J est le nombre d’étape
On aura le tableau suivant : Max ← T[pi] ;
Pour i ← 1 à 6-J+1 Faire Max ← T[6-J+1]; // initialisation de Max
T[pi] ← T[2] ;
1 2 4 5 6 T[2] ← Max ; Si ( T[i]> Max) alors Pour i ← 1 à 6-J+1 Faire
Max ← T[i]; Si ( T[i]> Max) alors
En Algorithmique
pi ← i; // pi est la position du Max Max ← T[i];
Max ← T[6-5+1]; // initialisation de Max à T[2] FinSi pi ← i; // pi est la position du Max
Pour i ← 1 à 2 Faire
Si ( T[i]> Max) alors FinPour FinSi
Max ← T[i]; Max ← T[pi] ; J ème étape FinPour
pi ← i; // pi est la position du Max
FinSi T[pi] ← T[6-J+1] ; // T[6-J+1] Max ← T[pi] ;
FinPour 5 ème étape T[6-J+1] ← Max ; T[pi] ← T[6-J+1] ;
Max ← T[pi] ;
T[pi] ← T[2] ; // T[2] = T[6-5+1] T[6-J+1] ← Max ;
T[2] ← Max ; FinPour

Exercices d’applications
Tri par sélection d’un tableau à une dimension
55 10 82 2 94 6 2 12 94 11

Parmi les nombreux algorithmes de tri existants, celui dont on a parlé aujourd'hui a
l'avantage d'être un des plus faciles à mettre en œuvre. Exercice 3:

Même si on l'implémente ici avec une liste d'entiers, il fonctionne parfaitement avec
n'importe quelle entité que l'on peut comparer (caractères, flottants, structures, etc...) Ecrire un algorithme permettant de lire
N entiers dans un tableau et de
déterminer la plus grande et la petite
Principe
valeur dans un tableau d’entiers A .
Afficher ensuite la valeur et la position
L'idée est simple : rechercher le plus grand élément (ou le plus petit), le placer en fin de du maximum et du minimum .
tableau (ou en début), recommencer avec le second plus grand (ou le second plus petit),
le placer en avant-dernière position (ou en seconde position) et ainsi de suite jusqu'à
avoir parcouru la totalité du tableau.

III.1.2 Déclaration d’un tableau à deux dimensions : Reprenons l’exemple des notes en considérant cette fois qu’un étudiant a plusieurs notes
Il est possible de définir des tableaux à plusieurs dimensions en les indiquant dans des (une note par chaque matière).Pour quatre étudiants , nous aurions le tableau de relevés des
crochets successifs lors de la définition du tableau. notes suivant: Etudiant 1 Etudiant 2 Etudiant 3 Etudiant 4
Pour des propos d’illustration l’exemple se limitera à deux dimensions, la généralisation à N Informatique 12 13 9 10
dimensions est immédiate. 12,5 14 12 11
Comptabilité
Définition : Mathématiques 15 12 10 13
Un tableau à deux dimensions T est à interpréter comme une juxtaposition de plusieurs Syntaxe:
tableaux de dimension C (nombre de colonnes ) .Le nombre de tableaux de dimension C est la
dimension L (nombre de lignes ) 1 2 3 ………………………………. C Variable identificateur: tableau [1..nb_lignes, 1..nb_colonnes]de type
Tableau T 1 Variable identificateur: tableau [nb_lignes, nb_colonnes] de type
2
Les tableaux à deux dimensions se
Exemple :
représentent comme une matrice L’instruction suivante déclare un tableau Note de type réel à deux dimensions composé de 3
…...

ayant un certain nombre de lignes lignes et de 4 colonnes :

(première dimension) et un certain
nombre de colonnes (seconde Variable Note : tableau [1 .. 3, 1..4] de réels
dimension). L
Le tableau T est formé par L lignes et C colonnes

12
 déc.-22

Quelques Instructions : III.1. 3 Déclaration d’un tableau dynamique :

Pour accéder à un élément de la matrice (tableau à deux dimensions ), il suffit de préciser , Les tableaux définis jusqu’ici sont dits statiques , car il faut qu’au moment de l’écriture du
entre crochets , les indices de la case contenant cet éléments . programme le programmeur décide de la taille maximale que pourra atteindre le tableau .
Les éléments de la matrice peuvent être utilisés comme n’importe quelle variable . Si le programmeur donne une taille très grande alors que lui il n’a pas besoin que d’une petite
taille , dans ce cas le programme consomme trop de mémoire . Dans certaines situations , on
Exemple : ne peut pas savoir la taille du tableau dans la phase de programmation .
L’instruction suivante affecte à la variable X la valeur du premier élément du tableau Note : Les tableaux dynamiques sont des tableaux dont la taille n’est définie que lors de l’exécution .
X ← Note [1 , 1] Pour créer un tableau dynamique , il suffit de lui affecter une taille vide .
Syntaxe:
Parcours complet d’un tableau à deux dimensions : Variable identificateur: tableau [ ]de type
Pour parcourir une matrice nous avons besoin de deux boucles, l’une au sein de l’autre , c’est Comme un tableau dynamique ne possède pas de taille prédéfinie , il convient de
ce qu’on appelle les boucles imbriquées. redimensionner le tableau avant de pouvoir s’en servir .
La première boucle par exemple est conçue pour parcourir les lignes tandis que la deuxième Syntaxe:
est utilisée pour parcourir les éléments de la colonne précisée par la boucle principale (la
première boucle) . Redimensionner identificateur [ N ]

Exercices d’applications
Accès aux composantes d’un tableau à deux dimensions:

Exercice 1 :
Pour accéder à une composante d’un tableau , on spécifie son adresse par :
Nom_ Tableau [Numéro_de_lignes, Numéro_de _colonnes]
La composante de la Nième ligne et Mième colonne est notée : Ecrire un algorithme permettant la saisie des
Nom_ Tableau [N,M] La composante de la 3ème ligne et 2ème colonne est notée: T[3,2] notes d’une classe de 30 étudiants en 5
La composante de la 4ème ligne et 5ème colonne est notée: T[4,5] matières .
En déclarant un tableau par : La composante de la 5ème ligne et 7ème colonne est notée: T[5,7]
T: tableau [5,7] de Entier ; 1 2 3 4 5 6 7

1
On définit un tableau 2
T de 5x7
3 T[3,2]
composantes
4 T[4,5]
5 T[5,7]

Exercices d’applications

Exercice 2 :

Ecrire un algorithme qui permet

d’initialiser et d’afficher le
tableau suivant :

13