ALGO
Transféré par
triedALGO
Transféré par
triedPlan
Algorithmique et Structures de Données I
Dr. Maher Helaoui
2019 - 2020
1/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 1/120
Plan
Bibliographie
Kernighan, B. et Ritchie, D.:
The C Programming Language. (1988)
Faber, F.:
Cours : Programmation C.
http://www.ltam.lu/cours-c/prg-c c.htm, (1997)
Ben Ayed, D.:
Cours : Algorithmique et structures de données.
ISI, (2018)
Helaoui, M.:
Travaux Dirigés : Algorithmique et Structures de Données.
https://www.researchgate.net/publication/266392442,
(2016) 2/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 2/120
Plan
Plan
1 Introduction à l’algorithmique et structures de données
Définir la notion d’algorithmique
Structure générale d’un algorithme
Premier algorithme : instructions d’entrée/sortie
2 Les variables
Déclarer une variable
Type d’une variable
Instruction d’affectation
3 Les structures de contrôle
Les Instructions conditionnelles
Les structures itératives
4 Les Sous programmes et Tableaux
Les Sous programmes
Les Tableaux et les Matrices
3/71
Les Algorithmes de Tri
Dr. Maher Helaoui Algorithmique et Structures de Données I 3/120
Introduction
Notion d’algorithmique
LES VARIABLES
Structure générale
Structures de contrôle
Entrée/sortie
Sous programmes et Tableaux
Introduction à l’algorithmique et structures de données
4/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 4/120
Introduction
Notion d’algorithmique
LES VARIABLES
Structure générale
Structures de contrôle
Entrée/sortie
Sous programmes et Tableaux
Algorithmique : résoudre un problème par le calcul
Résoudre un problème par le calcul
Pendant plusieurs millénaires, les mathématiciens se sont
contentés d’une notion intuitive, informelle, d’algorithme :
une méthode effective de calcul ,
un processus de résolution d’un problème par le calcul
5/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 5/120
Introduction
Notion d’algorithmique
LES VARIABLES
Structure générale
Structures de contrôle
Entrée/sortie
Sous programmes et Tableaux
Les Baboliens
Figure: Le premier algorithme
6/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 6/120
Introduction
Notion d’algorithmique
LES VARIABLES
Structure générale
Structures de contrôle
Entrée/sortie
Sous programmes et Tableaux
Historique: les algorithmes
2000 ans avant J.C.
les Babyloniens (l’actuel Irak) ont marqué les premiers
algorithmes sur terre et étaient principalement des méthodes
de calcul pour le commerce et les impôts.
300 ans avant J.C.
les Grecs ont présenté l’algorithme D’Euclide pour le calcul du
pgcd.
900 ans après J.C.
Al Khuwarizmi, un mathématicien perse (actuel Iran), consacre
un ouvrage aux algorithmes.
7/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 7/120
Introduction
Notion d’algorithmique
LES VARIABLES
Structure générale
Structures de contrôle
Entrée/sortie
Sous programmes et Tableaux
Historique: les machines et l’automatisation du calcul
Entre 1600 et 1800
Pascal et Leibniz construisent des machines à calculer
mécaniques (la Pascaline en 1642) ou des automates, et d’où
l’automatisation du calcul et la recherche d’algorithmes
efficaces.
8/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 8/120
Introduction
Notion d’algorithmique
LES VARIABLES
Structure générale
Structures de contrôle
Entrée/sortie
Sous programmes et Tableaux
La pascaline
Figure: La Pascaline : calculatrice mécanique
9/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 9/120
Introduction
Notion d’algorithmique
LES VARIABLES
Structure générale
Structures de contrôle
Entrée/sortie
Sous programmes et Tableaux
Premier ordinateur
En 1928
Hilbert avec son Entscheidungsproblem ( problème de
décision ) demande s’il existe un algorithme capable de
décider si un énoncé mathématique est vrai ?
Une machine peut elle prendre une décision ?
En 1930 − 1937
Présentation de la machine de Turing.
En 1945
la construction des premiers ordinateurs inspirés de la machine
de Turing.
10/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 10/120
Introduction
Notion d’algorithmique
LES VARIABLES
Structure générale
Structures de contrôle
Entrée/sortie
Sous programmes et Tableaux
Machine de Turing
Figure: Machine de Turing
11/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 11/120
Introduction
Notion d’algorithmique
LES VARIABLES
Structure générale
Structures de contrôle
Entrée/sortie
Sous programmes et Tableaux
Section II. Définir la notion d’algorithmique
12/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 12/120
Introduction
Notion d’algorithmique
LES VARIABLES
Structure générale
Structures de contrôle
Entrée/sortie
Sous programmes et Tableaux
Algorithme
Définition
Un algorithme est une méthode générale pour résoudre un
type ou une classe de problèmes. Il est dit correct lorsque qu’il
résout le problème posé.
Efficacité
l’efficacité d’un algorithme est mesurée par sa durée de calcul,
par sa consommation de mémoire vive, par la précision des
résultats obtenus, etc.
13/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 13/120
Introduction
Notion d’algorithmique
LES VARIABLES
Structure générale
Structures de contrôle
Entrée/sortie
Sous programmes et Tableaux
Algorithmique
Définition
L’algorithmique est l’étude et la production de règles et
techniques qui sont impliquées dans la définition et la
conception d’algorithmes, c’est-à-dire de processus
systématiques de résolution d’un problème permettant de
décrire précisément des étapes pour résoudre un problème
algorithmique.
L’algorithmique est la logique d’écrire des algorithmes.
14/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 14/120
Introduction
Notion d’algorithmique
LES VARIABLES
Structure générale
Structures de contrôle
Entrée/sortie
Sous programmes et Tableaux
Etapes de résolution d’un problème P
Résoudre P
Définir
Analyser
Algorithme informel
Conception
Algorithme formel
Implémentation et tests
Algorithme codés
Maintenance
15/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 15/120
Introduction
Notion d’algorithmique
LES VARIABLES
Structure générale
Structures de contrôle
Entrée/sortie
Sous programmes et Tableaux
Section III. Structure générale d’un algorithme
16/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 16/120
Introduction
Notion d’algorithmique
LES VARIABLES
Structure générale
Structures de contrôle
Entrée/sortie
Sous programmes et Tableaux
Structure générale d’un algorithme
Syntaxe de la structure générale
Algorithme <Nom de l’Algorithme>
<Déclaration de constantes>
<Déclaration de types>
<Déclaration de variables>
Début
<Instructions>
Fin
Il est possible d’ajouter des commentaires (des explications et
des informations qui ne vont pas être exécutées ou prises en
considération par l’ordinateur) :
/* commentaires */ (plusieurs lignes) ou
// commentaires (une seule ligne) 17/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 17/120
Introduction
Notion d’algorithmique
LES VARIABLES
Structure générale
Structures de contrôle
Entrée/sortie
Sous programmes et Tableaux
Section IV. Premier programme : instructions
d’entrée/sortie
18/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 18/120
Introduction
Notion d’algorithmique
LES VARIABLES
Structure générale
Structures de contrôle
Entrée/sortie
Sous programmes et Tableaux
Instruction de sortie : d’affichage ou d’écriture
L’instruction d’écriture ”Ecrire” affiche des informations sous
une forme compréhensible sur un périphérique de sortie
(L’écran). Ce qui permet au développeur de communiquer
avec l’utilisateur de son programme.
Syntaxe de l’instruction de sortie
Ecrire(Ident) ⇒ affiche sur l’écran le contenu de la variable
Ident
Ecrire(100) ⇒ affiche sur l’écran 100
Ecrire(”Bonjour tous les étudiants présents”) ⇒ affiche sur
l’écran le texte Bonjour tous les étudiants présents.
Ecrire(”Bonjour”, X) ⇒ affiche sur l’écran le texte Bonjour
puis le contenu de la variable X
19/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 19/120
Introduction
Notion d’algorithmique
LES VARIABLES
Structure générale
Structures de contrôle
Entrée/sortie
Sous programmes et Tableaux
Instruction d’entrée : de lecture
L’instruction de lecture ”Lire” permet à l’utilisateur d’entrer des
valeurs au programme à partir de l’entrée standard. (Le
clavier).
Syntaxe de l’instruction de sortie
Lire(Ident1, . . . , Identi, . . . , identn) ⇒ saisir une valeur à
partir du clavier et la mettre dans la variable Identi
20/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 20/120
Introduction
Notion d’algorithmique
LES VARIABLES
Structure générale
Structures de contrôle
Entrée/sortie
Sous programmes et Tableaux
Premier algorithme
Exercice
Ecrire un algorithme qui lit :
le prix hors taxe d’un article
le nombre d’articles achetés
le taux de la TVA
Et qui affiche le montant total toute taxe comprise.
21/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 21/120
Introduction
Notion d’algorithmique
LES VARIABLES
Structure générale
Structures de contrôle
Entrée/sortie
Sous programmes et Tableaux
Premier algorithme
Solution
Algorithme montant
/* Cette partie de déclaration sera expliquée lors du prochain
chapitre*/
PHT, TVA: Réel
Nbre: Entier
Début
Ecrire(”Veillez donner le prix hors taxe d’un article”)
Lire(PHT)
Ecrire(”Veillez donner le nombre d’articles achetés”)
Lire (Nbre) Ecrire(”Veillez donner le taux de la TVA”)
Lire (TVA)
Ecrire (”le montant total est:”, (PHT*Nbre) * (1+(TVA*0.01)))
Fin 22/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 22/120
Introduction
Notion d’algorithmique
LES VARIABLES
Structure générale
Structures de contrôle
Entrée/sortie
Sous programmes et Tableaux
Merci pour votre attention
https://sites.google.com/site/maherhelaoui/
23/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 23/120
Introduction
Déclaration
LES VARIABLES
Type
Structures de contrôle
Affectation
Sous programmes et Tableaux
Chapitre II. Les variables
24/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 24/120
Introduction
Déclaration
LES VARIABLES
Type
Structures de contrôle
Affectation
Sous programmes et Tableaux
Section I. Introduction
25/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 25/120
Introduction
Déclaration
LES VARIABLES
Type
Structures de contrôle
Affectation
Sous programmes et Tableaux
Objectif ?
Maı̂triser les notions : variable, type et valeur.
à la fin de ce chapitre vous devez
faire la différence entre variable et valeur
savoir affecter une valeur à une variable
savoir accorder le bon type à une variable
26/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 26/120
Introduction
Déclaration
LES VARIABLES
Type
Structures de contrôle
Affectation
Sous programmes et Tableaux
Section II. Déclaration de variable
27/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 27/120
Introduction
Déclaration
LES VARIABLES
Type
Structures de contrôle
Affectation
Sous programmes et Tableaux
Besoin d’un programme
Mémoriser provisoirement des informations
Un programme a besoin de mémoriser provisoirement
des valeurs (information)
ces valeurs peuvent être de plusieurs types (des nombres,
du texte, etc.)
pour ce faire, nous pouvons utiliser des variables.
28/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 28/120
Introduction
Déclaration
LES VARIABLES
Type
Structures de contrôle
Affectation
Sous programmes et Tableaux
Schématiser une variable
Une variable peut être schématisée par une boı̂te, repérée par
une étiquette. Pour avoir accès au contenu de la boı̂te, il suffit
de la désigner par son étiquette.
01231456
893 6996
29/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 29/120
Introduction
Déclaration
LES VARIABLES
Type
Structures de contrôle
Affectation
Sous programmes et Tableaux
Déclaration des variables
Une variable : un emplacement de mémoire, désigné par une
adresse binaire
Dans la mémoire vive de l’ordinateur, la boı̂te et
l’étiquette sont remplacées par un emplacement de
mémoire, désigné par une adresse binaire.
Le compilateur se charge d’affecter une étiquette choisie
par le programmeur pour chaque adresse binaire.
Afin d’utiliser une variable il faut préparer son emplacement
mémoire : créer la boı̂te et lui coller une étiquette.
Ceci peut se faire au début de l’algorithme (Variables
globales), avant même les instructions proprement dites.
C’est ce qu’on appelle la déclaration des variables. 30/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 30/120
Introduction
Déclaration
LES VARIABLES
Type
Structures de contrôle
Affectation
Sous programmes et Tableaux
Type ?
C’est quoi un compilateur ?
Un programme écrit par le programmeur (en Langage
structuré) ne peut être exécuté par votre ordinateur que s’il est
transformé en langage compris par la machine : Le langage
binaire.
Le compilateur est un programme permettant de transformer
un code écrit en Langage structuré en un code écrit en
langage binaire.
31/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 31/120
Introduction
Déclaration
LES VARIABLES
Type
Structures de contrôle
Affectation
Sous programmes et Tableaux
Syntaxe de la déclaration des variables
Variable g : Entier Long
Variables PrixHT, TauxTVA, PrixTTC : Réel Simple
Une variable est déclarée par la syntaxe suivante :
Variable Nom de la variable (étiquette ou identificateur) : Type
de la variable
32/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 32/120
Introduction
Déclaration
LES VARIABLES
Type
Structures de contrôle
Affectation
Sous programmes et Tableaux
Type ?
C’est quoi le type d’une variable ?
Une bonne question, le type d’une variable est l’objet de la
prochaine Section.
33/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 33/120
Introduction
Déclaration
LES VARIABLES
Type
Structures de contrôle
Affectation
Sous programmes et Tableaux
Section III. Type d’une variable et opérateurs associés
34/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 34/120
Introduction
Déclaration
LES VARIABLES
Type
Structures de contrôle
Affectation
Sous programmes et Tableaux
Type ?
C’est quoi le type d’une variable ?
Pour créer une boı̂te (réserver un emplacement mémoire
pour notre variable) nous devons préciser sa taille.
Elle doit correspondre à ce que l’on voudra mettre dedans,
il faut éviter :
1 un gaspillage de mémoire de créer une boite (réserver un
emplacement mémoire) plus grande par rapport à notre
besoin.
2 une taille insuffisante pour mémoriser toute l’information
utile. (Perte de données utiles)
Optimiser la taille
Imaginons que nous allons construire un château pour élever
un oiseau ou construire une toute petite cage pour un éléphant. 35/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 35/120
Introduction
Déclaration
LES VARIABLES
Type
Structures de contrôle
Affectation
Sous programmes et Tableaux
Types numériques
Types numériques classiques
Byte (octet) de 0 à 255
Entier simple de -32 768 à 32 767
Entier long de -2 147 483 648 à 2 147 483 647
Réel simple de -3,40E38 à -1,40E-45 pour les valeurs
négatives et de 1,40E-45 à 3,40E38 pour les valeurs
positives
Réel double de -1,79E308 à -4,94E-324 pour les valeurs
négatives et de 4,94E-324 à 1,79E308 pour les valeurs
positives.
36/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 36/120
Introduction
Déclaration
LES VARIABLES
Type
Structures de contrôle
Affectation
Sous programmes et Tableaux
Opérateurs : Types numériques
Opérateurs : Types numériques classiques
Entier : Parenthèse, Exposant, {+, −, ∗, /, %, div },
{=, 6=, <, <=, >, >=}
Réel : Parenthèse, Exposant, {+, −, ∗, /},
{=, 6=, <, <=, >, >=}
37/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 37/120
Introduction
Déclaration
LES VARIABLES
Type
Structures de contrôle
Affectation
Sous programmes et Tableaux
Types non numériques
exemples de types non numériques
alphanumérique (également appelé caractère) lettres, de
signes de ponctuation, d’espaces, ou de chiffres.
chaı̂ne de caractères (une telle chaı̂ne de caractères est
toujours notée entre guillemets) selon le type 2010 peut
représenter le nombre 2010, ou la suite de caractères 2, 0,
1 et 0.
booléen uniquement les valeurs logiques VRAI et FAUX
38/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 38/120
Introduction
Déclaration
LES VARIABLES
Type
Structures de contrôle
Affectation
Sous programmes et Tableaux
Opérateurs : Types non numériques
Opérateurs et fonctions
caractère : {=, 6=, <, <=, >, >=}
La comparaison entre les caractères se fait selon leur code
ASCII ’ ’ < ’0’ < ’7’ < ’A’ < ’Z’ < ’a’ < ’z’ < ’}
∃ des fonctions prédéfinies comme Succ(Ident),
Pred(Ident), ASCII(Ident)
booléen : NON, ET, OU, {=, 6=, <, <=, >, >=}
Chaı̂ne de caractères : ∃ des procédures et des fonctions
prédéfinies comme la fonctions LONG(”Bonjour”) renvoie
la cardinalité de la chaı̂ne dans cet exemple 7
39/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 39/120
Introduction
Déclaration
LES VARIABLES
Type
Structures de contrôle
Affectation
Sous programmes et Tableaux
Types et langage C
0123 45267879 8 79233
!" #$ "! ! #! "!
" % & " ! "! ' ()% * () ! 6
" "'! # !"'! % & #! "! +,-./012 " %345
7$ "8 9:;<= ' ! # "'! % 6 E# 6" $# ! "
"'! >) 3453 !##$ #@5! "!"!' 796379 3?@AB= C@AB5 # ) F
!'D
!"'! 7$ "8 9:;<= ' 3!I 5 # !"'! % 6 E# 6 $# ! "
>#! "! 796379 3G= AHH5 !'% # ) F
JKLMN "'! "! ' ()% 3> ) #$ #! "!"!' 796379
# 3?4A=BOB= C4A=BOB5 !'D453!# @5 = " " @O "
# "! "! "8% P !' "Q Q " ?4ABOB E!# ?4ABORF # 6"
"'! # #!ST#)! ! "'!T'!" )! "#!
"'! # "! #U ( ! = # ' U#ST
#)! )! "#! " # ##!%3H5
!"'! # JKLMN !"'! 34 "5! ' ()% >#! "! 796379 3G= 6
!"'! # "! OH=H4H5 !'D
"! V" "'! "! ' ()% 3> ) #$ #! "!"!' 796379
"'! 3?4A=BOB= C4A=BOB5 !'D453!# @5 = " " @O " 6" # 6
"'! "! "! "8%
!"'! V" !"'! 34 "5! ' ()% >#! "! 796379 3G= 6
!"'! "! OH=H4H5 !'D
#!' WLXY "'! "! ' ()% >) #$ #!3 45"3!!#"! ' @ 7596379
#!' "! 3?A=@IB=IR4=OIB= CA=@IB=IR4=OIB5 !'D = " " 6"
"'! #!' 4A " "! "8%
"'! #!' "!
!"'! #!' WLXY !"'! "! ' ()% >) 345 #$ #! "!"!' 79 6
!"'! #!' "! 6379 3G= I=AZI=ZOB=AZH5 !'D
#!' #!' WLXY[\LXY "'! "! ' ()% >) #$ #! "!"!' 79
#!' #!' "! 6379
"'! #!' #!' 3?Z=AA434=543!B#A = G@45O=RHI=BBH=RGB= CZ=AA4=4BA=G4O=RHI=BBH=RGB5 6"
"'! #!' #!' "! !'D = " " OI " "! "8% )"$"
"! >ZZ Q"#! #$ ! %
!"'! #!' #!' WLXY[\LXY !"'! "! ' ()% >#! 345"! 796379 3G=
=IIO=BII=GB4=BGZ=HH@=O@H5 !'D )"$" "! 6
!"'! #!' #!' "! C@R >Z Z Q"#! #$ ! %
] $# "!'T)#"! ()= ( $ # "!'T >#!Q "!' $# ^ c35
)""#! $# "!'T)#"! ()% * )#) " !)"$" 6$ 6a
$# E^) "!" "" F= #UQ #! # ( " " 6' 6d
&___ BHI "!'T)""#! "!( $# "!'T)#"! $# E4A
" F% P" $# " ` " ( #) "#! *!!^ a b&_> 6 6_
OGHHZ $# "!'T)#"! " "b% 6 6*
] $# "!'T)#"! ()= ( $ # # T 6$ 6a
)""#! $# "!'T)#"! ()% * )#) " !)"$" 6' 6d
# E^) "!" "" F= #UQ #! # ( " "
&___ BHI # T)""#! "!( $# "!'T)#"! 6 6_
$# EOI " F% P" $# " ` " ( #) "#! 6 6*3 5
*!!^ a b&_> OGHHZ $# "!'T)#"! " "b%
] $# "!'T)#"! ()= ( )) # ! ^ !
)""#! $# "!'T)#"! ! $# % * )#) "
!)"$" % & ! " ^RO ^ ! T)""#! $# "!'T 6e$ 6ea 40/71
#!' # )#"! $# ERG " = ()"( ZO " # @AR " "! 6e' 6ed
#( U" ) "!' ( F= !#!T&___ b # T # b 6e 6e_3 5
E@AR " F= &___ BHI ` )T)""#! $# "!'T)#"! 6e 6e*
$# E@AR " F= # # % " #!
#!' # $# "%
Dr. Maher Helaoui Algorithmique et Structures de Données I 40/120
Introduction
Déclaration
LES VARIABLES
Type
Structures de contrôle
Affectation
Sous programmes et Tableaux
Opérateurs et priorités
Ordre de priorité entre les opérateurs
Parenthèse Exposant Non {∗, /, %, div } {+, −}
{<, <=, >, >=} {=, 6=} ET OU
NB : en cas d’égalité dans l’ordre de priorité la priorité est
de gauche à droite
41/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 41/120
Introduction
Déclaration
LES VARIABLES
Type
Structures de contrôle
Affectation
Sous programmes et Tableaux
Tables de vérité (1)
Table de vérité de négation
Ident1 NON Ident1
vrai faux
faux vrai
Table de vérité : conjonction ET
Ident1 Ident2 Ident1 ET Ident2
vrai vrai vrai
vrai faux faux
faux vrai faux
faux faux faux
42/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 42/120
Introduction
Déclaration
LES VARIABLES
Type
Structures de contrôle
Affectation
Sous programmes et Tableaux
Tables de vérité (2)
Table de vérité : disjonction OU
Ident1 Ident2 Ident1 OU Ident2
vrai vrai vrai
vrai faux vrai
faux vrai vrai
faux faux faux
43/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 43/120
Introduction
Déclaration
LES VARIABLES
Type
Structures de contrôle
Affectation
Sous programmes et Tableaux
Section III. Instruction d’affectation
44/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 44/120
Introduction
Déclaration
LES VARIABLES
Type
Structures de contrôle
Affectation
Sous programmes et Tableaux
Syntaxe de l’instruction affectation
Syntaxe
Une variable permet de mémoriser une information, cette
opération se fait à travers une instruction : l’affectation (lui
attribuer une valeur).
En algorithmique, cette instruction se note avec le signe ← .
Syntaxe de l’instruction affectation :
Nom de la variable ← Valeur de la variable.
45/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 45/120
Introduction
Déclaration
LES VARIABLES
Type
Structures de contrôle
Affectation
Sous programmes et Tableaux
Exemple déclaration
Exemple
Variable Boite : Entier
/*Cette ligne permet de réserver un espace mémoire suffisant
pour contenir un entier au niveau de la déclaration notre boite
est vide.*/
23456 46/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 46/120
Introduction
Déclaration
LES VARIABLES
Type
Structures de contrôle
Affectation
Sous programmes et Tableaux
Exemple affectation
Exemple
Boite ← 12
/*Cette ligne permet d’affecter la valeur entière de 12 à notre
variable Boite.*/
12
45678 47/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 47/120
Introduction
Déclaration
LES VARIABLES
Type
Structures de contrôle
Affectation
Sous programmes et Tableaux
Exemple réaffectation
Exemple
Boite ← 20
/*Cette ligne permet d’écraser la valeur de 12 dans notre
variable Boite et affecter une nouvelle valeur entière de 20.*/
12
45678 48/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 48/120
Introduction
Déclaration
LES VARIABLES
Type
Structures de contrôle
Affectation
Sous programmes et Tableaux
Des questions ?
Questions :
1 Et les constantes ?
2 Pourquoi avez-vous confondu Bita et octet ?
3 Est-il possible d’allouer x/8 octetb avec un langage
structuré comme le C ?
4 Pourquoi le type booléen n’est pas numérique ? Il
n’existe pas en C ?
5 Quel est l’espace mémoire réservé au type booléen ?
a
The byte is a unit of digital information that most commonly consists of
eight bits ... The size has historically been hardware dependent
b
Le Byte est la plus petite unité logiquement adressable par un
programme
49/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 49/120
Introduction
Déclaration
LES VARIABLES
Type
Structures de contrôle
Affectation
Sous programmes et Tableaux
Les constantes
Une constante
Une constante est une variable dont la valeur est fixée tout
au long du programme.
Syntaxe constante
Constante
Nom de la constante ← Valeur de la constante : Type
50/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 50/120
Introduction
Déclaration
LES VARIABLES
Type
Structures de contrôle
Affectation
Sous programmes et Tableaux
L’enregistrement
Créer mon propre type
L’enregistrement est le fait de créer une nouvelle structure
de données en créant un nouveau type.
Syntaxe
Type
Nom de la structure : Enregistrement
Structures de données Typés
Fin Enregistrement
51/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 51/120
Introduction
Déclaration
LES VARIABLES
Type
Structures de contrôle
Affectation
Sous programmes et Tableaux
Créer un enregistrement
Booléen
1 Supposons que nous n’avons pas de type booléen, ce qui
est le cas avec le langage c, et nous voulons le créer.
2 quelle est l’allocation mémoire à réserver pour le nouveau
type créé ?
52/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 52/120
Introduction
Déclaration
LES VARIABLES
Type
Structures de contrôle
Affectation
Sous programmes et Tableaux
Exercice
Exercice 1
Soit l’algorithme Test1 suivant :
Algorithme Test1
// Ajouter les déclarations nécessaires
Début
A ← 4(1)
B ← 11(2)
A ← B − A(3)
B ← B − A(4)
A ← A + B(5)
Fin
Ajouter les déclarations nécessaires à l’algorithme Test1
Que fait l’algorithme ci-dessus ? 53/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 53/120
Introduction
Déclaration
LES VARIABLES
Type
Structures de contrôle
Affectation
Sous programmes et Tableaux
Exercice 1 suite
Exercice 1 suite
Ce résultat est-t-il toujours vrai ? Etablir la trace de cet
algorithme (sous forme de tableau) avec a et b pour
valeurs initiales de A et B.
Ecrire un nouvel algorithme équivalant en n’utilisant que
des variables ? (Utiliser une variable intermédiaire).
54/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 54/120
Introduction
Déclaration
LES VARIABLES
Type
Structures de contrôle
Affectation
Sous programmes et Tableaux
Section IV. Conclusion
55/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 55/120
Introduction
Déclaration
LES VARIABLES
Type
Structures de contrôle
Affectation
Sous programmes et Tableaux
Ce qu’il faut retenir
Variable, type et valeur.
à la fin de ce chapitre vous devez
faire la différence entre variable et valeur
savoir déclarer une variable
savoir utiliser l’instruction d’affectation
Gérer la déclaration des structures de données.
56/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 56/120
Introduction
Déclaration
LES VARIABLES
Type
Structures de contrôle
Affectation
Sous programmes et Tableaux
Merci pour votre attention
https://sites.google.com/site/maherhelaoui/
57/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 57/120
Introduction
LES VARIABLES Instructions conditionnelles
Structures de contrôle Structures itératives
Sous programmes et Tableaux
Chapitre III. Les structures de contrôle
58/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 58/120
Introduction
LES VARIABLES Instructions conditionnelles
Structures de contrôle Structures itératives
Sous programmes et Tableaux
Section I. Introduction
59/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 59/120
Introduction
LES VARIABLES Instructions conditionnelles
Structures de contrôle Structures itératives
Sous programmes et Tableaux
Pourquoi ?
Objectifs ?
Ce chapitre a pour objectifs de
Définir et présenter la syntaxe des structures de contrôle
Maı̂triser et savoir utiliser les structures de contrôle
60/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 60/120
Introduction
LES VARIABLES Instructions conditionnelles
Structures de contrôle Structures itératives
Sous programmes et Tableaux
Section II. Les Instructions conditionnelles
61/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 61/120
Introduction
LES VARIABLES Instructions conditionnelles
Structures de contrôle Structures itératives
Sous programmes et Tableaux
Formes de l’instruction conditionnelle Si
Syntaxes des divers formes
1 Si (expression logique) Alors Instructions FinSi
2 Si (expression logique 1) Alors Instructions 1 Sinon
Instructions 2 FinSi
3 // Les conditionnelles emboı̂tées :
Si (expression logique 1) Alors Instructions 1
Sinon Si (expression logique 2) Alors Instructions 2
...
Sinon Si (expression logique n-1) Alors Instructions n-1
Sinon Instructions n
FinSi
62/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 62/120
Introduction
LES VARIABLES Instructions conditionnelles
Structures de contrôle Structures itératives
Sous programmes et Tableaux
Exemple : instruction conditionnelle Si
Instruction conditionnelle Si
Ecrire un programme permettant à un étudiant de l’ISI de saisir
sa moyenne et il affiche le résultat et la mention obtenue.
63/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 63/120
Introduction
LES VARIABLES Instructions conditionnelles
Structures de contrôle Structures itératives
Sous programmes et Tableaux
Syntaxe de l’instruction Selon
Nous pouvons remplacer Les conditionnelles emboı̂tées par
l’instruction Selon ( permet une facilité d’écriture)
Syntaxe
Selon identificateur Faire
(liste de) valeur(s) 1 : instructions 1
(liste de) valeur(s) 2 : instructions 2
...
(liste de) valeur(s) n-1: instructions n-1
Sinon
instructions n
FinSelon
64/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 64/120
Introduction
LES VARIABLES Instructions conditionnelles
Structures de contrôle Structures itératives
Sous programmes et Tableaux
Exemple : instruction conditionnelle Selon
Instruction conditionnelle Selon
Ecrire un programme permettant à un étudiant de l’ISI de saisir
sa moyenne et selon la moyenne il affiche le résultat et la
mention obtenue.
65/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 65/120
Introduction
LES VARIABLES Instructions conditionnelles
Structures de contrôle Structures itératives
Sous programmes et Tableaux
Section III. Les structures itératives
66/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 66/120
Introduction
LES VARIABLES Instructions conditionnelles
Structures de contrôle Structures itératives
Sous programmes et Tableaux
La structure itérative Pour
Syntaxe
1 Pour compteur de début à fin [(pas = val)] Faire
Instructions
FinPour
67/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 67/120
Introduction
LES VARIABLES Instructions conditionnelles
Structures de contrôle Structures itératives
Sous programmes et Tableaux
Exemple : structure itérative Pour
structure itérative Pour
Ecrire un programme permettant à un étudiant de l’ISI de
proposer cinq idées permettant à son avis d’améliorer la qualité
des formations.
68/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 68/120
Introduction
LES VARIABLES Instructions conditionnelles
Structures de contrôle Structures itératives
Sous programmes et Tableaux
La structure itérative Tant que
Syntaxe
1 Tantque (expression logique) Faire
Instructions
FinTantque
69/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 69/120
Introduction
LES VARIABLES Instructions conditionnelles
Structures de contrôle Structures itératives
Sous programmes et Tableaux
Exemple : structure itérative Tant que
structure itérative Tant que
Ecrire un programme permettant à un étudiant de l’ISI de
proposer toutes idées permettant à son avis d’améliorer la
qualité des formations.
70/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 70/120
Introduction
LES VARIABLES Instructions conditionnelles
Structures de contrôle Structures itératives
Sous programmes et Tableaux
La structure itérative Répéter Jusqu’à
Syntaxe
1 Répéter
Instructions
Jusqu’à (expression logique)
71/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 71/120
Introduction
LES VARIABLES Instructions conditionnelles
Structures de contrôle Structures itératives
Sous programmes et Tableaux
Exemple : structure itérative Répéter Jusqu’à
structure itérative Répéter Jusqu’à
Ecrire un programme permettant à un étudiant de l’ISI de
proposer au minimum une idée permettant à son avis
d’améliorer la qualité des formations.
72/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 72/120
Introduction
LES VARIABLES Instructions conditionnelles
Structures de contrôle Structures itératives
Sous programmes et Tableaux
Section V. Conclusion
73/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 73/120
Introduction
LES VARIABLES Instructions conditionnelles
Structures de contrôle Structures itératives
Sous programmes et Tableaux
Conclusion
Conclusion
Dans ce Chapitre nous avons présenté:
Les instructions conditionnelles.
Les structures itératives
74/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 74/120
Introduction
LES VARIABLES Instructions conditionnelles
Structures de contrôle Structures itératives
Sous programmes et Tableaux
Merci pour votre attention
https://sites.google.com/site/maherhelaoui/
75/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 75/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Chapitre IV. Les Sous programmes et Tableaux
76/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 76/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Section I. Introduction
77/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 77/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Pourquoi ?
Objectifs ?
Ce chapitre a pour objectifs de
Maı̂triser la programmation modulaire
Introduire les tableaux et les matrices
Présenter des algorithmes de tri
78/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 78/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Section II. Les Sous programmes
79/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 79/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Exemple 1
Pourquoi les sous programmes ?
Pouvez vous écrire un programme qui
demande à l’utilisateur de remplir les valeurs de deux
variables de types entiers X 1 et Y 2 ?
calcule la somme de X 1 et Y 2 ?
demande à l’utilisateur de remplir deux autres variables de
types entiers X 2 et Y 3 ?
calcule la somme de X 2 et Y 3 ?
demande à l’utilisateur de remplir deux autres variables de
types entiers X 3 et Y 4 ?
calcule la moyenne de X 3 et Y 4 ?
80/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 80/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Exemple 2
Pourquoi les sous programmes ?
Pouvez vous écrire un programme qui
demande à l’utilisateur de remplir deux variables X 1 et Y 2
?
permute les valeurs de X 1 et Y 2 ?
demande à l’utilisateur de remplir deux autres variables X 2
et Y 3 ?
permute les valeurs de X 2 et Y 3 ?
demande à l’utilisateur de remplir deux autres variables X 3
et Y 4 ?
permute les valeurs de X 3 et Y 4 ?
81/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 81/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Procédure et fonction
Procédure
Une procédure est un sous programme qui n’a pas de retour
propre à la procédure.
Fonction
Une fonction est une procédure qui a un type et un retour, de
même type que la fonction, une ou un ensemble de valeurs,
propres à la fonction.
82/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 82/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Syntaxe d’une procédure
Syntaxe
Nom de la procédure(liste typée de paramètres formels)
/*en-tête de la procédure*/
Déclaration des variables locales
Début
Instructions /*Un bloc homogène*/
Fin
83/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 83/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Syntaxe d’une fonction
Syntaxe
Nom de la fonction(liste typée paramètres formels) : [type
propre à la fonction]/*en-tête de la fonction*/
Déclaration des variables locales
Début
Instructions /*Un bloc homogène*/
Nom de la fonction ← expression ou variable à renvoyer /*Mot
Clé du retour*/
Fin
84/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 84/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Structure générale d’un algorithme
Mise à jour de la Syntaxe de la structure générale
Algorithme <Nom de l’Algorithme>
<Déclaration de constantes>
<Déclaration de types>
<Déclaration de variables>
<Procédures et Fonctions>
Début
<Instructions>
Fin
Instruction d’appel d’une fonction ou une procédure
Nom de la procédure(Liste de paramètres non typée)
Variable ← Nom de la fonction(Liste de paramètres non typée)
85/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 85/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Fonctions somme et moyenne
Fonction somme de deux entiers
Somme(A:Entier, B:Entier) : Entier/*en-tête de la fonction
somme*/
Début
Somme ← A+B
Fin
Fonction moyenne de deux entiers
Moyenne(A:Entier, B:Entier) : Réel /*en-tête de la fonction
Moyenne*/
Somme(A:Entier, B:Entier) : Entier /*La déclaration de la
fonction Somme n’est pas obligatoire*/
Début
Moyenne ← Somme(A,B)/2 86/71
Fin Dr. Maher Helaoui Algorithmique et Structures de Données I 86/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Exercice 1
Solution Exercice 1
Algorithme Solution-Exercice-1
Somme(A:Entier, B:Entier) : Entier/*en-tête de la fonction
somme*/
Début Somme ← A+B Fin
Moyenne(A:Entier, B:Entier) : Réel /*en-tête de la fonction
Moyenne*/
Début Moyenne ← Somme(A,B)/2 Fin
i, a, b : Entiers c: Réel
Début
Pour i de 1 à 3 Faire
Ecrire(”Donnez un entier”) Lire(a)
Ecrire(”Donnez un entier”) Lire(b)
Si (i < 3) alors Ecrire(”La somme est : ”, Somme(a,b) ) FinSi 87/71
FinPour Dr. Maher Helaoui Algorithmique et Structures de Données I 87/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Passage de paramètres par valeurs et par adresses
Passage de paramètres par valeurs
Nous passons le contenu de la variable en paramètre : le
contenu de la variable passée en paramètre ne sera pas
modifié suite à l’appel de la fonction ou la procédure.
Passage de paramètres par adresses
Nous passons l’adresse physique de la variable en paramètre :
le contenu de la variable passée en paramètre sera modifié
suite à l’appel de la fonction ou la procédure.
88/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 88/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Passage de paramètre par adresse
Var Boite xxxxxx
L’Adresse de la variable est son emplacement
mémoire physique.
89/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 89/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Exercice 2
Solution Exercice 2
Algorithme Solution-Exercice-2
Permuter(Var A:Entier, Var B:Entier) /*en-tête de la Procédure
Permuter*/
temps : Entier Début
temps ← A
A←B
B ← temps
Fin
a, b,c,d,e,f : Entiers
Début
Ecrire(”Donnez un entier X1”) Lire(a)
Ecrire(”Donnez un entier Y1”) Lire(b)
Ecrire(”Donnez un entier X2”) Lire(c) 90/71
Ecrire(”Donnez un entier
Dr. Maher Y2”)
Helaoui Lire(d)
Algorithmique et Structures de Données I 90/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Appel d’une fonction (1)
Fonctions ne renvoyant rien au programme et sans passage
d’arguments
Une fonction ne renvoyant rien au programme est une
Procédure de type void.
Fonction renvoyant une valeur au programme et sans passage
d’arguments
Une fonction ne possède pas de paramètre formel et après
exécution, renvoie une valeur. Le type de cette valeur est
déclaré avec la fonction. La valeur retournée est spécifiée à
l’aide du mot réservé return.
Fonction avec passage d’arguments
91/71
Fonctions utilisent les valeurs de certaines variables du
Dr. Maher Helaoui Algorithmique et Structures de Données I 91/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Appel d’une fonction (2)
Fonction avec passage d’arguments
Fonctions utilisent les valeurs de certaines variables du
programme les ayant appelé.
92/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 92/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Exemple 4
Fonction ne renvoyant rien au programme et sans passage
d’arguments
Appelons une fonction carre ne renvoyant rien au programme
et sans passage d’arguments pemettant de calculer le carré
d’un entier choisi par l’utilisateur de notre programme.
93/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 93/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Exemple 4 bis
Fonction renvoyant une valeur au programme et sans passage
d’arguments
Appelons une fonction carre renvoyant au programme le carré
d’un entier choisi par l’utilisateur et sans passage d’arguments.
94/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 94/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Exemple 4 bis bis
Fonction avec passage d’arguments
Appelons une fonction carre renvoyant au programme le carré
d’un entier choisi par l’utilisateur au programme principale et
passons le comme argument à cette fonction.
Nous pouvons appeler la fonction carre autant de fois que l’on
veut avec des variables différentes.
x est un paramètre formel ou argument : ce n’est pas une
variable du programme.
n1 une variable du programme est un paramètre effectif de la
fonction carre.
95/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 95/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Le passage de paramètres
Le passage de paramètres d’une fonction
Avec l’instruction return d’une part et la liste des paramètres
d’autre part, une fonction dispose de deux moyens pour
communiquer ou pour échanger des données avec d’autres
fonctions.
Divers passage de paramètres d’une fonction
Passage de paramètres par valeur.
Passage de paramètres par adresse.
96/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 96/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Exemple : Passage de paramètres par valeur d’une
fonction
Passage de paramètres par valeur
Reprenons l’Exemple 3 et présentons
une première solution avec passage de paramètres par
valeur.
une deuxième solution avec passage de paramètres par
adresse.
97/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 97/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Section III. Les Tableaux et les Matrices
98/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 98/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Tableaux ?
C’est quoi un tableau ?
Un tableau ou vecteur T est une suite de N variables ou
enregistrement de même types (appelées éléments) dont les
adresses sont ordonnées.
N est la dimension de T : elle nous permet de connaı̂tre
l’espace mémoire consommé par T .
99/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 99/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Adresses ordonnées ?
Pourquoi les adresses sont ordonnées ?
L’ordre sur les adresses de T permet l’accès à n’importe quel
élément T [i] de T étant donnée son indice et l’adresse du
premier élément.
Indice ?
Les indices est un ordre sur les adresses des divers éléments
de T .
1 Le premier élément est d’indice 1 : accessible par T[1]
2 Le deuxième élément est d’indice 2 : accessible par T[2]
3 ...
4 Le nième élément est d’indice n : accessible par T[n] 100/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 100/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Syntaxe des Tableaux
Déclaration
Nom Tableau : Tableau [premier indice . . . dernier indice]de
Type élément
101/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 101/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Tableaux à 2 dimentions ?
C’est quoi une Matrice ?
Un tableau à deux dimensions ou Matrice M est une suite de L
Tableaux chacun de dimension C de même types dont les
adresses sont ordonnées.
L’espace mémoire consommé par M est de L ∗ C de type d’un
élément.
102/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 102/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Adresses ordonnées ?
Pourquoi les adresses sont ordonnées ?
L’ordre sur les adresses de M permet l’accès à n’importe quel
élément M[i][j] de M étant donnée ses indices et l’adresse du
premier élément.
Indice ?
Les indices est un ordre sur les adresses des divers éléments
de M.
1 Le premier élément est d’indice 1ere Ligne 1ere Colonne :
accessible par M[1][1]
2 Le deuxième élément est d’indice 1ere Ligne 2eme
Colonne : accessible par M[1][2]
103/71
3 ...
Dr. Maher Helaoui Algorithmique et Structures de Données I 103/120
4
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Syntaxe des Tableaux
Déclaration
Nom Matrice : Tableau [1er indice . . . Leme indice] [1er indice
. . . Ceme indice] de Type élément
104/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 104/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Section IV. Les Algorithmes de Tri
105/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 105/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Tri par sélection
Principe
1 Permuter l’élément le plus petit de T[1 . . . N] avec l’élément
1 de T
2 Permuter l’élément le plus petit de T[2 . . . N] avec l’élément
2 de T . . .
3 Permuter l’élément le plus petit de T[N-1, N] avec l’élément
N-1 de T
Pour i de 1 à N-1 Faire
Permuter l’élément le plus petit de T[i . . . N] avec l’élément i de
T
FinPour
106/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 106/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Tri par sélection
Algorithme : Tri par sélection
Const
NMax ← 1000 : Entier
Variables
i,N, IndicePP : Entiers
T: Tableau [1 . . . NMax] d’Entiers
Debut
Pour i de 1 à N-1 Faire
IndicePP ← SelectionnerLePlusPetit(T [], i, N)
Permuter(T,i,IndicePP)
FinPour
Fin
107/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 107/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Sélectionner Le Plus Petit
SelectionnerLePlusPetit(T[]:Entier,i:Entier,N:Entier) : Entier
Variables
j,IndiceMin : Entiers
Debut
IndiceMin ← i
Pour j de i+1 à N Faire
Si T[j] < T[IndiceMin] Alors
IndiceMin ← j
FinSi
FinPour
SelectionnerLePlusPetit ← IndiceMin
Fin
108/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 108/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Permuter Le Plus Petit
Permuter(T:Entier,i,IndicePP)/*T:Entier est équivalente à Var
T[]*/
Début
Si i 6= IndicePPAlors
Variable
Aux : Entier
Aux ← T [i]
T[i] ← T [IndicePP]
T[IndicePP] ← Aux
FinSi
Fin
109/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 109/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Tri à bulle
Principe
Tantque une permutation est possible Faire
Permuter les plus grands éléments du tableau enfin de tableau.
FinTantque
Ceci est équivalent à
Tantque une permutation est possible Faire
Permuter les plus petits éléments du tableau au début du
tableau.
FinTantque
110/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 110/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Tri à bulle
Procédure TRISBULLE (VAR T : tableau entier, N : entier)
Variables i, j, aux : Entiers
DEBUT
Pour i de 1 à N-1 Faire
j←N
Tantque (j 6= i) Faire
Si (T[j] < T[j - 1] ) alors
Permuter(T,j,j-1)
Finsi
j←j 1
FinTantque
FinPour
FIN
111/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 111/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Tri par insertion
Procédure TriInsertion( T:tableau Entier, n: Entier)
Variables
x,i,j:Entiers
pour (i de 1 à n - 1) Faire
x ← T[i]
j←i
Tant que (j > 0 et T[j - 1] > x) Faire
T[j] ← T[j - 1]
j←j-1
FinTantque
T[j] ← x
FinPour
Fin
112/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 112/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Section V. Conclusion
113/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 113/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Conclusion
Conclusion
Dans ce Chapitre nous avons présenté:
Les Sous programmes.
Les Tableaux et les Matrices.
Les Algorithmes de Tri.
114/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 114/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Merci pour votre attention
https://sites.google.com/site/maherhelaoui/
115/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 115/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
P UBLICATIONS
116/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 116/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
Bibliographie
Kernighan, B. et Ritchie, D.:
The C Programming Language. (1988)
Faber, F.:
Cours : Programmation C.
http://www.ltam.lu/cours-c/prg-c c.htm, (1997)
Ben Ayed, D.:
Cours : Algorithmique et structures de données.
ISI, (2018)
Helaoui, M.:
Travaux Dirigés : Algorithmique et Structures de Données. 117/71
https://www.researchgate.net/publication/266392442,
Dr. Maher Helaoui Algorithmique et Structures de Données I 117/120
Introduction
Sous programme
LES VARIABLES
Tableaux
Structures de contrôle
Tri
Sous programmes et Tableaux
MERCI POUR VOTRE ATTENTION
118/71
Dr. Maher Helaoui Algorithmique et Structures de Données I 118/120
Vous aimerez peut-être aussi
- Capture D'écran . 2024-12-25 À 12.44.34Pas encore d'évaluationCapture D'écran . 2024-12-25 À 12.44.34109 pages
- Introduction à l'Algorithmique et ProgrammationPas encore d'évaluationIntroduction à l'Algorithmique et Programmation109 pages
- Algorithme G1 Ig 2021-2022 094656-1Pas encore d'évaluationAlgorithme G1 Ig 2021-2022 094656-142 pages
- Algorithmique Et Programmation: Berlin DJIONANGPas encore d'évaluationAlgorithmique Et Programmation: Berlin DJIONANG84 pages
- Algorithmique Et Programmation: Berlin DJIONANGPas encore d'évaluationAlgorithmique Et Programmation: Berlin DJIONANG97 pages
- Chapitre1 - ASD - Introduction À L'algorithmiquePas encore d'évaluationChapitre1 - ASD - Introduction À L'algorithmique14 pages
- ESCAT-Algorithme & Structures de Données - L1Pas encore d'évaluationESCAT-Algorithme & Structures de Données - L118 pages
- Cours d'Algorithmique et Structures de DonnéesPas encore d'évaluationCours d'Algorithmique et Structures de Données24 pages
- Cours d'Algorithmique I: Concepts ClésPas encore d'évaluationCours d'Algorithmique I: Concepts Clés9 pages
- Acfrogdh9s Ocm51lmnbgcfslfbfgos52zzwspszxmizwdnb0efc Cjdydw3ag Ifuvnwwr8afalzvov9yfabkhy0283 8bnn4oxhqzjicjdmgnd Jsiq2s2xs0ppo1mvnstlh5qpyscwcfqyee6Pas encore d'évaluationAcfrogdh9s Ocm51lmnbgcfslfbfgos52zzwspszxmizwdnb0efc Cjdydw3ag Ifuvnwwr8afalzvov9yfabkhy0283 8bnn4oxhqzjicjdmgnd Jsiq2s2xs0ppo1mvnstlh5qpyscwcfqyee694 pages
- Introduction À L'algorithmique Et À La ProgrammationPas encore d'évaluationIntroduction À L'algorithmique Et À La Programmation8 pages
- Cours Informatique Algorithmique SMP3 104734Pas encore d'évaluationCours Informatique Algorithmique SMP3 10473440 pages
- Capture D'écran . 2023-10-22 À 15.35.59Pas encore d'évaluationCapture D'écran . 2023-10-22 À 15.35.5930 pages
- Algorithmique 2 & 3 - Environement Algorithmiques & Structures ConditionnellesPas encore d'évaluationAlgorithmique 2 & 3 - Environement Algorithmiques & Structures Conditionnelles34 pages
- Introduction à l'algorithmique et aux instructions de basePas encore d'évaluationIntroduction à l'algorithmique et aux instructions de base30 pages
- La Représentation Et L'exécution Des Traitements - MyMaxicoursPas encore d'évaluationLa Représentation Et L'exécution Des Traitements - MyMaxicours8 pages
- Algorithmique, Structures de Données Et Programmation en C - Cours Et Exercices (Semestre 1)Pas encore d'évaluationAlgorithmique, Structures de Données Et Programmation en C - Cours Et Exercices (Semestre 1)104 pages
- Cours Algorithmes et Programmation 1Pas encore d'évaluationCours Algorithmes et Programmation 140 pages
- Algorithmique et Structures de DonnéesPas encore d'évaluationAlgorithmique et Structures de Données98 pages
- Algorithmique - Philippe LECARDONNELPas encore d'évaluationAlgorithmique - Philippe LECARDONNEL9 pages
- Insérer Une Image Dans Une Base de Données Mysql: Formulaire - HTMLPas encore d'évaluationInsérer Une Image Dans Une Base de Données Mysql: Formulaire - HTML2 pages
- Guide Complet sur la Virtualisation et la Gestion des Data CentersPas encore d'évaluationGuide Complet sur la Virtualisation et la Gestion des Data Centers4 pages
- Design Patterns JAVA et Principes GRASPPas encore d'évaluationDesign Patterns JAVA et Principes GRASP239 pages
- Introduction au Système d'ExploitationPas encore d'évaluationIntroduction au Système d'Exploitation4 pages
- Objectifs de certification LPIC-2 V4Pas encore d'évaluationObjectifs de certification LPIC-2 V428 pages
- Fanuc Pmc-Model Nb6 (Langue ÉCHELLE) : Types de Documents Techniques AppliquésPas encore d'évaluationFanuc Pmc-Model Nb6 (Langue ÉCHELLE) : Types de Documents Techniques Appliqués56 pages
- Concurrence et Parallélisme expliquésPas encore d'évaluationConcurrence et Parallélisme expliqués80 pages
- Évaluation Correction HTML - N3 - 3STI 2023-2024Pas encore d'évaluationÉvaluation Correction HTML - N3 - 3STI 2023-20247 pages
