Introduction à

l’algorithmique
ATSA ETOUNDI Roger
Professeur Titulaire en Informatique
[Link]@[Link]
 Résolution Informatique des Problèmes
• Nous vivons dans un monde digital, les ordinateurs et autres terminaux sont
tout autour de nous.
• Les ordinateurs nous permettent de réaliser des travaux en faisant des
économies en temps tout en minimisant les erreurs
• C’est la base de l’informatique
• C’est cela qui donne un sens à l’informatique
• Avant que l’ordinateur ne résolve le problème, les programmeurs doivent
dans un premier temps comprendre comment ce dernier est résolution par
l’homme
• C’est au terme de cette étape que le programmeur va mettre en place une
application devant être exécutée par un ordinateur.
Résolution Informatique des Problèmes
• Le programmeur pour mener a bien son travail doit:
• Etre capable de représenter les données
• En occurrence les données initiales
• Etre capable de trouver les étapes pour la transformation des données d’une
représentation à une autre
• En occurrence les données intermédiaires et les données finales
 Résolution Informatique des Problèmes
Identification du Problème Analyse de l’environnement visant a définir les difficultés liées aux activités

Analyse du problème identifié à l’effet de déterminer les contraintes liées à

Analyse du Problème
sa résolution. Elle permet une bonne compréhension du problème
Identification et énumération des différentes contraintes fonctionnelles et
Définitions des besoins
non fonctionnelles pour la résolution du problème
Définition des algorithmes et des structures de données inhérents la
Conception de la solution
résolution du problème

Traduction des algorithmes dans un langage de programmation à partir duquel

Codification de la solution
des transformations seront faites pour une compréhension par l’ordinateur
Validation de la solution conformément aux contraintes définies dans la
Test de la solution
phase de définition des besoins

Déploiement de la solution Implantation de la solution dans l’infrastructure technologique

 Résolution Informatique des Problèmes

Problème Algorithme Programme Résultat

Algorith Program Utilisatio

mique mation n

Analyse et Choix du Compilation &

Conception langage & Exécution
Codification
Résolution Informatique des Problèmes

Abstraction

Monde virtuel
Monde Réel
(algorithme,
(problème &
programme,
Résultat)
résultat)
Définition des concepts
• Algorithmique: consiste a concevoir et mettre au point des
algorithmes décrivant les solutions d’un certain type de problèmes.
L’algorithmique comporte deux phases:
• La phase d’analyse
• La phase de conception
• Algorithme: une suite finie et logique d’instructions à appliquer
dans un ordre déterminé sur les données afin d’aboutir à un certain
résultat en un temps fini.
Techniques algorithmiques de conception
des algorithmes
• Algorithme de glouton
• Diviser pour régner
• Programmation dynamique
Algorithme de glouton
• Les algorithmes pour problèmes d’optimisation exécutent en général une
série d’étapes, chaque étape proposant un ensemble de choix.
• Pour de nombreux problèmes d’optimisation, la programmation
dynamique est une approche bien trop lourde pour déterminer les
meilleurs choix ; d’autres algorithmes, plus simples et plus efficaces,
peuvent faire l’affaire. Un algorithme glouton fait toujours le choix qui
lui semble le meilleur sur le moment.
• Autrement dit, il fait un choix localement optimal dans l’espoir que ce
choix mènera à une solution globalement optimale. Cette activité étudie
les problèmes d’optimisation qui peuvent se résoudre par des algorithmes
gloutons.
Algorithme de glouton: Le principe
• Un algorithme de glouton est un algorithme qui résout des
problèmes d’optimisation (qui optimise une fonction objectif), il
cherche à construire une solution pas à pas:
• en espérant obtenir une solution optimale en effectuant une suite de choix:
à chaque étape on fait le meilleur choix local
• Pas de retour en arrière : à chaque étape de décision dans l’algorithme, le
choix qui semble le meilleur à ce moment est effectué.
• Progression descendante : choix puis résolution d’un problème plus petit
Exemple: Le monnayeur
• On dispose des pièces des monnaies correspondant aux valeurs P =
{25,25,25,10,10,5,1,1,1,1}
• montant à payer (n = 67).
• Sortie: ensemble des pièces utilisées (S = {25,25,10,5,1,1}), le moins
de pièces possibles.
• Etant donnée une quantité c entière, on veut trouver une façon de
"rendre" la somme c avec un nombre de pièces minimum.
• Construction de la solution:
• S={}; s={25}, s={25}u{25}, s={25,25}u{10}; s={25,25,10}u{5};
s={25,25,10,5}u{1}; s={25,25,10,5,1}u{1}
Stratégie
• ajouter la plus grande pièce possible
• tant que la somme n’excède pas le montant à payer
Exercice
1. En utilisant l’approche gloutonne, donner la solution au
problème de remplissage d’un sac dont le poids maximal est
connu avec les objets ayant chacun un poids. La contrainte étant
que le sac doit avoir le plus d’objets possible
2. En utilisant l’approche gloutonne, donner la solution au
problème de remplissage d’un sac dont le poids et le volume
maximal sont connus avec les objets ayant chacun un poids et un
volume. La contrainte étant que le sac doit avoir le plus d’objets
possible
Diviser pour régner
• La méthode de diviser pour régner est une méthode qui permet,
parfois de trouver des solutions efficaces à des problèmes
algorithmiques.
• L’idée est de découper le problème initial, de taille n, en sous-
problèmes de taille plus petite, résoudre les sous-problèmes
récursivement (ou les résoudre directement si de taille
suffisamment petite), puis recombiner les solutions des sous-
problèmes pour obtenir la solution du problème d’origine.
Principe
• Le paradigme diviser-pour-régner implique trois étapes à chaque
niveau de la récursivité :
• Diviser : le problème en sous-problèmes plus petits
• Régner : sur les sous-problèmes en les résolvant récursivement ou, si la
taille d’un sous-problème est assez réduite, le résoudre directement ;
• Combiner : les réponses des sous-problèmes afin d'obtenir la réponse au
problème de départ
Attention lors de la composition
• La solution S3 vérifiant les propriétés P3 est issue de S1 vérifiant P1 et
de S2 vérifiant p2
• Il existe un homomorphisme h: S1xS2 -> S3 ou h: S2xS1 -> S3
• P3 = P1uP2uP3’ avec P3’ les propriétés vérifiées exclusivement par S3.
Programmation dynamique
• La programmation dynamique, comme la méthode diviser-pour-
régner, résout des problèmes en combinant des solutions de sous-
problèmes.
• (le mot « Programmation », dans ce contexte, fait référence à une
méthode tabulaire et non à l’écriture de code informatique.).
• Les algorithmes diviser-pour-régner partitionnent le problème en
sous-problèmes indépendants qu’ils résolvent récursivement, puis
combinent leurs solutions pour résoudre le problème initial.
• La programmation, quant à elle, peut s’appliquer même lorsque les
sous-problèmes ne sont pas indépendants, c’est-à-dire lorsque des
sous-problèmes ont des sous-sous-problèmes communs.
Programmation dynamique
• Dans ce cas, un algorithme diviser-pour-régner fait plus de travail que
nécessaire, en résolvant plusieurs fois le sous-sous-problème commun.
• Un algorithme de programmation dynamique résout chaque sous-sous-
problème une seule fois et mémorise sa réponse dans un tableau, évitant
ainsi le recalcul de la solution chaque fois que le sous-sous-problème est
rencontré.
• Lorsque les sous-problèmes ne sont pas indépendants (c’est-à-dire
lorsque les sous-problèmes ont des sous-sous-problèmes communs) la
programmation récursive se révèle le plus souvent très inefficace car elle
conduit à résoudre de nombreuses fois les sous-sous-problèmes
communs.
Principe
• Afin de résoudre un problème, on commence tout d’abord par
résoudre les plus petits sous-problèmes et on stocke les valeurs de
ces sous-problèmes dans une table de programmation dynamique.
• Ensuite, on utilise ces valeurs pour calculer la valeur des sous-
problèmes de plus en plus grands, jusqu’à obtenir la solution de
notre problème global.
Spécification d’un algorithme
• (Nm, De, Ds, Aut, Pde, PDs)
• Nm: dénote le nom de l’algorithme
• De: dénote les données en entrée
• Ds: dénote le données en sortie
• PDe: dénote les propriétés devant être vérifiées par De
• PDs: dénote les propriétés devant être vérifiées par Ds
• Aut: dénote l’automate qui transforme les De en Ds
Donnée
• Une donnée est caractérisée par trois attributs:
• Identificateur (identifiant)
• Valeur
• Type
Transforme des données

• Les donnes sont transformées à l’aide des instructions

• Ces instructions peuvent avoir l’une des formes suivantes
• Les séquences
• Les sélections
• repetitions
Séquence
• Une séquence est une série d’ étape s qui s’exécutent une par une
suivant un ordre prédéfini
• Une étape sera appelée une instruction
• Exemple
• Présenter le probatoire
• Présenter le baccalauréat
Les sélections

• Seules certaines instruction sont exécuter lorsque certaines

conditions sont satisfaites
• On en distingue:
• Si..
• Si sinon
• Cas selon
Structures de contrôle

• Dans l’ecriture d’un algorithme, si on ne

retrouve pas une structure de contrôle ou
itérative, les instructions vont s’executer de la
première a la dernière.
• On distingue trois structures de contrôle:
• Le Si simple
• Le Si alternatif
• Le Si imbriqué
Le Si simple
• Il permet de contrôler l’exécution d’une instruction
ou bloc d’instructions
• Sa syntaxe est la suivante:
• Si cond alors action finsi
• Cond dénote une proposition, lorsqu’elle est évaluée à
vraie l’action s’exécute
• Exemple
Si gagne (Cameroun, matches_barrage) alors
afficher (« Cameroun qualifié pour le mondial 2022 »)
finsi
Le Si alternatif
• Il permet de contrôler l’exécution d’une instruction ou
bloc d’instructions et donne une alternative lorqu’on ne
saurait executer l’instruction principale
• Sa syntaxe est la suivante:
• Si cond alors action1 sinon action2 finsi
• Cond dénote une proposition, lorsqu’elle est évaluée à vraie
l’action1 s’exécute, si évaluée a faux action2 s’exécute.
• Exemple
Si gagne (Cameroun, matches_barrage) alors
afficher (« Cameroun qualifié pour le mondial 2022 »)
Sinon
afficher(« tous les camerounais seront déçus »)
finsi
Le Si imbriqué
• Il permet d’exécuter des instructions selon des cas
• Syntaxe:
cas var selon
val1: action1
val2: action2
…
valn: action_n
autre: action_n+1
fncas
Le Si imbriqué: expression équivalente
si val =val1 alors
action1
sinon
si val = val2
action2
sinon
…
si val =valn alors
action_n
sinon
action_n+1
finsi
…
finsi
finsi
Structures itératives ou repetitives

• On en distingue trois:
• Pour
• Tant que
• repeter
Structures: Pour
• On
• On execute un nombre fini de fois un ensemble d’instructions
• Syntaxe
Pour cp = val-ini a valf, pas faire
Action(s)
Fin_pour

Cp represdnte le compteur
Val-ini représente la valeur initiale du compteur
Valf représente la valeur finale
Pas représente le saut a chaque iteration
Remarques
Si val-ini < valf, on va incrementer cp du pas à la fin de chaque interation
Si val-ini > valf, on decremengte cp du pas à la fin de chaque iteration
Si pas = 1 ou pas = -1, on ne le représente pas sur la boucle
 Exemple
…. ….
….
P<- 1
P<- 1
Pour j =100 a 1 faire
Pour j =1 a 100 faire Pour j =0 a 100,2 faire
p<- p*j
p<- p*j
Finpour afficher (j)
Finpour
afficher (p) Finpour
afficher (p)
La valeur du pas est 1
La valeur du pas est 1 ce bout de
programme affiche
Le bout de programme
Le bout de programme calcule la factoriel de tous les nombres pairs
calcule la factoriel de 100 inferieur ou egal a 100
100
Répéter
• Ce mot clé permet l’execution d’un ensemble d’instructions jusqua
ce que une condition soit satisfaite
Syntaxe
Répéter
action(s)
Jusqu’à cond
Sémantique
L’ensemble d’actions est executees jusqu’à ce que la condition cond
soit evaluee a vraie
 Repeter
….
P<- 1
J<-1
repeter
p<- p*j
j <- j+1
Jusqu’à j>100
afficher (p)

Le bout de programme
calcule la factoriel de 100
Tant-que
• Ce mot cle permet d’executer un ensemble d’instruction tant
qu’une condition est satisfaite
Syntaxe
Tantque Cond faire
action(s)
Fintantque
Sémantique
On execute l’ensemble des actions tant que la condition cond est
evaluee a vraie
 Exemple
….
P<- 1
J<-1
Tantque j<=100 faire
p<- p*j
j <- j+1
fintantque
afficher (p)

Le bout de programme
calcule la factoriel de 100
Ecriture d’algorithme
Pour écrire un algorithme simple, on a besoin de:
• Donner son nom
• Définir lorsque cela est nécessaire les types de données à manipuler
• Définir les variables si nécessaire à manipuler
• Donner la suite d’instructions commençant par le mot clé début et
se terminant par le mot clé fin
• La suite d’instruction peut contenir des structures de contrôle, des
structure itératives
• Dans chaque structure de contrôle ou itérative, on peut définir un
bloc d’instructions
• Un bloc d’instructions est un ensemble d’au moins deux
instructions
• En règle général, chaque bloc est délimité par les mots clé début et
fin
Structures de données
• Structures de données de base
• Structures de données évoluées
• Structures de données dynamiques
Structure de données de base
• Les entiers: 0,1,2, …, n, n+1
• Les nombres relatifs
• Les réels,
• Booléens,
• bit
• Caractère
• Chaine de caractères
Type abstrait de donnée
• Pour concevoir un algorithme complexe, on adopte une démarche
descendante : l'analyse procède par raffinements successifs.
• Au départ, on reste loin de toute implémentation ; en particulier, la
représentation concrète des données n'est pas fixée. On parle alors de
type abstrait de données.
• Un type de données abstrait est composé d’un ensemble d’objets,
similaires dans la forme et dans le comportement, et d’un ensemble
d’opérations sur ces objets.
• On se donne une notation qui décrit les données, des opérations
applicables à ces données (primitives), et les propriétés de ces opérations
(sémantique).
Principe d’abstraction
• Il permet de représenter un objet du monde réel en ne detant pas
compte du détail
• Plus on a des détails mois l’abstraction est élevée
• Moins on a des details sur un objet, plus l’abstraction est élevée.
• NB:
• le principe d’abstraction fait partie des outils important de tout
informaticien
• Il est très important dans la modélisation ou représentation en
informatique
Type abstrait de donnée
• Un type abstrait de donnée est une représentation formelle d’un type de
données, le type de données étant un ensemble de données ayant les mêmes
opérations
• La représentation est dite formelle car elle utilise les concepts mathématiques
• Elle est définie par
• Son nom
• Son type d’ Intérêt ou ensemble de données ayany les memes proprietes
• Primitive (utilise, étendre)
• Les opérations
• Générateurs
• transformateur
• Constructeurs
• Observateurs
• prédicats
• Les propriétés
Type abstrait de donnée
• La primitive « Utilise » est suivie ou definit les types abstraits que
l'on va utiliser dans celui que l'on est en train de décrire
• Parmi les opération on a:
• Un générateur est une opération qui donne naissance au type que l’on est
entrain de définir
• les constructeurs permettent de créer un objet du type que l'on est en train
de définir ;
• les transformateurs permettent de modifier les objets et leur contenu;
• les observateurs sont des fonctions donnant des informations sur l'état de
l'objet.
 Type Booléen
TAD Bool1
Tyepe: Bool
Générateur
TAD Bool2
true:Bool
false:Bool étendre Bool1 avec
Constructeurs Constructeur
et: Bool xBool -> Bool non: Bool -> Bool
ou : Bool x Bool -> Bool
Propriété
eq : Bool x Bool -> Bool
Propriétés P3:  b:Bool non (non b))=b
P1:  b:Bool b et b =b fin
p2:  b,b’:Bool, b=/=b’ => b eq b’ = false
fin
Type abstrait des entiers naturels
TAD Nat0
Type Nat
TAD Nat1
utilise Bool2 etendre Nat0 avec
Générateur
0:Nat observateur
1:Nat
Constructeur isnat: Nat -> Bool
succ : Nat -> Nat
+ : Nat x Nat -> Nat
Propriété
Propriété
P4:  n:Nat isnat(n) => 0=n \/ 1=n \/
P1:  n:Nat Succ(n) = N+1
p2: succ(0) = 1 m:Nat succ(n)=m
P3: 0+1 = 1
fin fin
Exercice

Etendre le TAD Nat 1 pour ajouter les

opérations suivantes avec leurs
propriétés: puissance, multiplication,
division entière, division, inferieur,
supérieur.
Type Tableau

• Le type tableau est un ensemble indexé i.e les objets sont

accédés à l’aide des indexes
• Un tableau est un ensemble fini de cases qui se suivent,
chaque case ayant un indice. Les cases sont adjacentes les
unes des autres. Chaque case a un numéro
• Par exemple si A est un tableau pouvant contenir n objets
• A[1] représente le contenu de la première case
• A[2] représente le contenu de la deuxième case
• ..
• A[n] représente le contenu de la nième case
Type Tableau
1. Le nombre de cases d’un tableau constitue sa taille.
2. Pour utiliser un tableau on doit connaitre sa taille i.e
le numéro de la première case et celui de la dernière
case
3. La taille du tableau = numéro dernière case –
numéro première case + 1
4. Tous les éléments d’un tableau sont de même type
5. On se saurait avoir une case libre entre deux cases
occupées
Type abstrait tableau
Axiomes x, y ∈ Obj, i, j : Nat, t : Tab
P1: get(t, i) =x => findex ≤ i ≤ last(t);
TAD Tableau P2: i j => set(Set(t, i, x), j, y) = Set(Set(t, j,
Type Tab, Obj y), i, x);
Utilise Nat, Bool2
Opérations :
P3: i = j => Set(Set(t, i, x), i, y) = Set(t, i, y);
Create : → Tab P4: Get(Set(t, i, x), i) = x;
findex: Tab → Nat
lindex: Tab → Nat
P5: findex(t) i /\ i<j /\ get(t,j)=x => o:Obj
get : Tab × Nat → Obj get(t,i) = o;
set : Tab × Nat ×Obj → Tab
last: Tab → Nat
P6 findex(t)  lindex(t)
taille: Tab → Nat P7: taille(t) = lindex(t) – findex(t) +1
full: Tab → Bool
empty: Tab → Bool
p8: isin(t,x) => n:Nat get(t,n)=x /\
isin: Tab x Obj → Bool n last(t)
findex(t)  n
fin
Type abstrait tableau
TAD Tableau1
Etendre Tableau avec
Axiome x ∈ Obj, j : Nat, t,t’ : Tab
P9: empty(t) => last(t) = findex(t) -1
P10: set(t,j,x) = t’ => non full(t) /\
last(t’)=last(t)+1 /\
get(t’,last(t’))=x
P11: full(t) => last(t) = lindex(t)
Type abstrait pile
• Une pile est une liste linéaire d’objets où les consultations les
insertions et les suppressions se font du même coté.
• Dernier arrivé, premier servi.
• Les opérations suivantes peuvent lui être appliquées: empiler (push),
dépiler (pop), sommet (top), pile vide (empty)
Type abstrait pile
TAD Pile Axiomes :
 P,p’: Pile Depiler(p) =p’ => non EstVide(p)
Type Pile, Obj EstVide(PileVide()) = VRAI
Utilise Bool  P: Pile, o:Obj EstVide(Empiler(o, p)) =
FAUX
Opérations :  P: Pile, o;Obj Depiler(Empiler(o, p)) = p
PileVide : {} → Pile fin
EstVide : Pile(T) → Booleen
Empiler : T × Pile(T) → Pile
Depiler : Pile(T) → T × Pile
Formes canoniques de la pile

Soit p une Pile d’objets. Il existe un unique

entier n et un unique n-uplet
(a1, : : : , an)  ObjtxObj…xObj n fois tel
que:
p = empiler(an, empiler(an-1, : : :
(Empiler(a1; PileVide()) : : : ))
File d’attente
• Une file d’attente ou tout simplement un file est une liste linéaire
d’objets où les consultations et les suppressions se font du même
coté, les insertions se font de l’autre coté.
• Elle respecte le principe: Premier arrivé, premier servi.
• Les opérations suivantes sot appliquées à une file:
• enfiler, défiler,tête, queue, file vide
Formalisation de la File d’attente
TAD File
Type File, Obj Axiomes : f,f’:File, o:obj
utilise Bool P1: defiler(f ) =f’ => non estVide(f )
Opérations : P2: estVide(FileVide()) = VRAI
P3: estVide(Enfiler(o,f )) = FAUX
fileVide : → File P4: defiler(Enfiler(o, f)) = f
estVide : File → Booleen P5: non estVide(f ) =>
defiler(Enfiler(o, f )) = f
enfiler : Obj x File → File fin
defiler : File → File
Formes canoniques de la file

Soit f une File d’objets. Il existe un unique n

et un unique n-uplet
(a1, : : : , an)  ObjxObjx…xObj n fois tel
que:
f = enfiler(an; enfiler(an, : : : (enfiler(a1;
fileVide()) : : : )) :
File d’attente prioritaire
Une file d’attente prioritaire est une liste linéaire d’objets où les
consultations et les suppressions se font du même coté, les insertions
se font de l’autre coté, à la différence de la file normale, les objets
sont classés par ordre de priorité.
Notons:
L’objet le plus prioritaire se trouve toujours le premier à être consulté
ou supprimé.
File prioritaire
TAD Objet
Type Obj, Priorité
Opération
priority : Obj → Priorité
Axiome
 o,o’ :Obj o=o’ => priority(o) = priority(o’)
fin
 File prioritaire
Axiomes : f,f’:Filep, o:obj
TAD Filep P1: defiler(f ) =f’ => non estVide(f )
Type Filep P2: estVide(fileVide()) = VRAI
utilise Bool, Objet P3: estVide(Enfiler(o,f )) = FAUX
Opérations : P4: defiler(o, f)) = f’ =>
priority(dernier(f’) 
fileVide : → Filep
priority(premier(f’))
estVide : Filep → Booleen P5: enfiler(o, enfiler(0’,fileVide))
enfiler : Obj x Filep → Filep = f => priority(dernier(f) 
defiler : Filep → Filep priority(premier(f))
premier: FileP → Obj fin
dernier: FileP → Obj
Les listes chaînées
l'utilisation des files, si elle semble similaire à celle des piles, est en
réalité fort différente.
Chacun de ces TAD a ses avantages et inconvénients.
Le principal défaut de ces TAD est d'être obligé de défiler/dépiler les
éléments les uns après les autres pour pouvoir les traiter, ce qui oblige
à les rempiler/renfiler par la suite avec tous les risques que cela
implique quant à l'ordre des éléments.
Notre troisième TAD va donc régler ce souci puisque nous allons
traiter des listes chaînées
Les listes chaînées
Comme dit précédemment, les listes chaînées sont linéaires,
doublement chaînées, non cycliques et non contraintes.
Qui plus est, elles pourront être traitées en LIFO (comme une pile)
ou en FIFO (comme une file) mais il sera également possible
d'insérer un élément au beau «milieu» de la liste.
Pour cela, il devra être possible de parcourir la liste sans la
«démonter» comme nous le faisions avec les piles ou les files.
Les listes chaînées
• Une liste L est composée de 2 parties :
• sa tête (souvent noté car), qui correspond au dernier élément ajouté à la liste,
• sa queue (souvent noté cdr) qui correspond au reste de la liste.
• Le langage de programmation Lisp (inventé par John McCarthy en 1958) a été un des premiers
langages de programmation à introduire cette notion de liste (Lisp signifie "list processing").
• Voici les opérations qui peuvent être effectuées sur une liste :
• créer une liste vide (L=vide() on a créé une liste L vide)
• tester si une liste est vide (estVide(L) renvoie vrai si la liste L est vide)
• ajouter un élément en tête de liste (ajouteEnTete (x,L) avec L une liste et x l'élément à ajouter)
• Ajouter un élément a une position intermédiaire
• Ajouter un élément a la fin de la liste
• supprimer la tête x d'une liste L et renvoyer cette tête x (supprEnTete(L))
• Compter le nombre d'éléments présents dans une liste (compte(L) renvoie le nombre
d'éléments présents dans la liste L)
• Supprimer l’ élément de fin de liste
• Supprimer un élément intermédiaire
Formalisation de la liste chaînée
Pour formaliser le fonctionnement
d’une liste chainée, il est important
TAD Cellule
de comprendre la spécification d’une Type Cel, Obj. Adr
cellule, car en réalité, une liste est Opérations
une association des cellules créer: → Cel
adresse: Cel → Adr
mémoires. data: Cel → Obj
adrsuiv: Cel → Adr
*Une cellule est constituée: Axiomes
 c,c:Cel
d’une zone d’adresse de la cellule c  c’ => adresse Cc)  adresse(c’)
suivante fin

*d’une zone de donnée

Formalisation de la liste chaînée
TAD Liste0
Type List
Utilise Cellule
Operations Axiomes  l’l’:List. o:Obj
listevide: List P1: l’=ajouter(l,o) => data(tete(l’))=o /\
queue(l’)=l /\
créer: → List adrsuiv(tete(l’))=adr(tete(l))
ajoutertete: ListxObjt → List P2: l’=deltete(l) => l listvide /\ l’=queue(l)
fin
deltete: List → List
tete : List → Cel
queue: List → List
Formalisation de la liste chaînée
TAD Liste1
Axiomes  l’l’:List. o:Obj
Etendre List0 avec
P1: l’=ajouterfin(l,o) => data(last(l’))=o /\
Operations
ajouterfin: ListxObjt → List precedent(last(l’))=last(l)
P2: l’=delfin(l) => l listvide /\
delfin: List → List last(l’) =
last : List → List precedent(last(l))
Fin
precedent: CelxList → Cel
Formalisation de la liste chaînée
TAD Liste2
Etendre List1 avec Axiomes  l’l’:List. o:Obj,c:Cel
P1: l’=ajouterinter(l,o,c) =>
Operations
data(precedent(c,l’))=o /\
ajouterinter: ListxObjtxCel→ List suiv(suiv(precedent(c,l),l’),l’)=c
delinter: ListxCel→ List
last : List → List P2: l’=delfinter(l,c) => l  listvide /\
suiv(precedent(c,l),l’) =
suiv: CelxList → Cel
suiv(c,l)
Fin
Le type Ensemble

Définition informelle
On décrit une collection d’objets de même type, avec les
opérations d’ajout d’un élément, de suppression, d’appartenance et
de cardinalité (nombre d’éléments).
Notons:
un élément, s’il appartient à un ensemble n’y apparaît
qu’une fois et une seule.
Définition formelle d’un ensemble
Axiomes : o, o’:Obj, e:Ens
estVide(Vide()) = Vrai
TAD Ensemble estVide(ajoute(x; e)) = Faux
appartient(o,Vide()) = Faux
Type Ens. Obj
appartient(o; ajoute(o; e)) = Vrai
Utilise Bool
o =o’ => ajoute(o, ajoute(o’, e)) =
Opérations :
ajoute(o, e)
vide : → Ens
supprime(o,ajoute(o, e)) = e
estVide : Ens(T) → Booleen
ajoute : Obj x Ens → Ens oo’ => ajoute(o,ajoute(o’,e)) =
ajoute(o’ ajoute(o, e))
supprime : Obj x Ens → Ens
appartient : Obj x Ens → Booleen Supprime(o,ajoute(o’,e)) =
ajoute(o,supprime(o, e))
fin
 Type chaine de caractères
TAD Ch1
Type: Ch, Char
utilise Nat
Générateur
chv:Ch
Constructeurs
concat: Ch x Ch -> Ch
sousch: ChxNatxNat -> Nat
long: Ch -> Nat
souschg: Ch x Nat -> Ch
souschd ChxNat -> Ch
observateur
char: ChxNat -> Char
Enregistrement

• Un enregistrement est une structure de donnée qui agrège

un ensemble d’attributs ou de caractéristique d’un objet ou
phénomène du monde réel.
• Lors de la définition d’un type abstrait symbolisant un
enregistrement, les seules fonctions ou opérations qui y
sont définies sont beaucoup plus les observateurs, car on
fait des projections sur les attributs
Enregistrement
TAD Etudiant
type: Etud, Nom, Filiere, Niveau, Matricule
Operations
nom: Etdu -> Nom
matricule: Etud -> Matricule
filiere-etud: Etud -> Filiere
niveau: Etud -> Niveau
Axiomes
[a1] e,e’:Etud ee’ => matricule(e)  matricule(e’)
fin
Exercices
1. Ecrire les algorithmes associés aux fonctions définies dans les types
abstraits vus précédemment
2. En reprenant l’épreuve du contrôle continu, donner les
algorithmes associés aux fonctions décrites.
Sous-programmes
• Le sous-programme est une partie presque indépendante d’un
alogorithme qui a un nom et peut être appelée d'un autre sous-
programme ou de l’algorithme principal.
• Il y a deux sortes de sous-programmes:
• Procédures
• fonctions.
• L'appel d'une fonction est une expression, c'est-à-dire que la fonction
renvoie un résultat (valeur).
• L’appel d’une procédure est
• une instruction, c'est-à-dire que la procédure ne renvoie rien
Ecriture de Sous-programmes
• Ces paramètres sont appelés paramètres formels.
• Les paramètres sont nécessaires pour que le sous-programme puisse
communiquer avec le programme qui l’appelle
• Un algorithme appelle un sous-algorithme : – L'algorithme appelant
passe momentanément le contrôle de l'exécution du traitement au
sous-algorithme.
• Un sous-algorithme est conçu pour faire un traitement bien défini,
bien délimité́, si possible indépendamment du contexte particulier de
l’algorithme appelant.
• Remarque : un sous-algorithme peut en appeler un autre.
Comment les informations circulent ?
Exemple
Communications d'informations
Paramètres et Arguments
Paramètres et Arguments
 Paramètres et arguments
• Les paramètres (formels) d'un sous-algorithme sont simplement des
variables locales qui sont initialisées par les valeurs obtenues lors de l'appel
(paramètres effectifs ou arguments)
• Au moment de l'appel du sous-algorithme , les valeurs des arguments sont
affectés aux paramètres formels de statut (D) ou (D/R) ; • Le nombre de
paramètres doit correspondre au nombre d’arguments.
• Le type du kième argument doit correspondre au type du kième
paramètre.
• Un paramètre défini en "Donnée" doit correspondre à un argument qui po
ssède une valeur dans l’algorithme appelant au moment de l’appel. • Un
paramètre défini en "Résultat" doit recevoir une valeur dans le sous
algorithme
Procédure : syntaxe
Fonction : syntaxe
Mise en ouvre d'une fonction

• L’utilisation d’une fonction nécessite trois étapes :

• la déclaration de la fonction (interface, en-tête ou
encore prototype)
• la définition du corps de la fonction
• l’appel de la fonction
• SYNTAXE:
• fonction identificateur (paramètres_formels) : type
Agenda
• Les algorithmes classiques de Tri
• Tris stables
• Le tri par insertion
• Le tri bulle
• Le tri Shaker
• Le tri Gnome
• Le tri fusion
• Tri non stable
• Tri rapide
• Le tri par sélection
• Le tri Shell
• Le tri maximier
• Le tri à peigne
Problématique du Tri
• On désigne par "tri" l'opération consistant à ordonner un ensemble
d'éléments en fonction de clés/poids/valeur sur lesquels est définie une
relation d'ordre.
• Les algorithmes de tri ont une grande importance pratique. Ils sont
fondamentaux dans certains domaines, comme l'informatique de
gestion où l'on tri de manière quasi-systématique des données avant de
les utiliser.
• L'étude du tri est également intéressante en elle-même car il s'agit sans
doute du domaine de l'algorithmique qui a été le plus étudié et qui a
conduit à des résultats remarquables sur la construction d'algorithmes
et l'étude de leur complexité.
 Le tri par insertion
• On fait comme si les éléments à trier étaient donnés un par un, le premier
élément constituant, à lui tout seul, une liste triée de longueur 1. On range
ensuite le second élément pour constituer une liste triée de longueur 2, puis
on range le troisième élément pour avoir une liste triée de longueur 3 et
ainsi de suite...
• Le principe du tri par insertion est donc d'insérer à la nième itération le
nième élément à la bonne place.

Pseudo code associé à la description de l’agorithme

PROCEDURE tri_Insertion ( Tableau a[1:n])

POUR i VARIANT DE 2 A n FAIRE
INSERER a[i] à sa place dans a[1:i-1];
FIN PROCEDURE;

Devoir: Développer un simulateur de cet algorithme en s’appuyant sur les technologies

Le tri par sélection
• Le principe du tri par sélection/échange (ou tri par extraction) est
d'aller chercher le plus petit élément du vecteur pour le mettre en
premier, puis de repartir du second élément et d'aller chercher le plus
petit élément du vecteur pour le mettre en second, etc..

Pseudo code associé

PROCEDURE tri_Selection ( Tableau a[1:n])
POUR i VARIANT DE 1 A n - 1 FAIRE
TROUVER [j] LE PLUS PETIT ELEMENT DE [i + 1:n];
ECHANGER [j] ET [i];
FIN PROCEDURE;
 Le tri bulle

Le principe du tri à bulles Pseudo code associé au principe

(bubble sort ou sinking sort) PROCEDURE tri_bulle ( TABLEAU a[1:n])
est de comparer deux à deux passage ← 0
les éléments e1 et REPETER
e2 consécutifs d'un tableau et permut ← FAUX
d'effecteur une permutation si POUR i VARIANT DE 1 A n - 1 - passage FAIRE
SI a[i] > a[i+1] ALORS
e1 > e2. echanger a[i] ET a[i+1]
permut ← VRAI
FIN SI
On continue de trier jusqu'à FIN POUR
ce qu'il n'y ait plus de passage ← passage + 1
TANT QUE permut = VRAI
permutation. Fin procedure
 Le tri à peigne

• Le tri à peigne est un algorithme de tri par comparaison qui améliore

de façon notable les performances du tri à bulle. Cet algorithme fut
conçu en 1980 par Włodzimierz Dobosiewicz. Quelques années plus
tard, en 1991, Stephen Lacey et Richard Box ont montré dans un
article dans Byte Magazine que l'idée de Donald Shell pouvait
s'appliquer également, et avec autant de bénéfices, au tri bulle.
• Le principe est de ne plus comparer uniquement des éléments
adjacents, mais de commencer par comparer des éléments plus
lointains, puis de raccourcir progressivement l'intervalle entre les
éléments pour aboutir finalement à un tri à bulle classique.
 Le tri à peigne
PROCEDURE tri_peigne ( TABLEAU a[1:n])
gap ← n
REPETER
permut ← FAUX
gap ← gap / 1.3
SI gap < 1 ALORS gap ← 1
POUR i VARIANT DE 1 A n AVEC UN PAS gap FAIRE
SI a[i] > a[i+gap] ALORS
echanger a[i] et a[i+gap]
permut ← VRAI
FIN SI
FIN POUR
TANT QUE permut = VRAI OU gap > 1
Fin procedure
 Le tri shaker
• Le tri "Shaker", également appelé tri "Cocktail", tri "Shuttle",
tri "boustrophédon" ou tri à bulles bidirectionnel est une variante du tri
à bulles.
• Son principe est identique à celui du tri à bulles, sauf qu'il change de
direction à chaque passe.
• C'est une légère amélioration car il permet non seulement aux plus
grands éléments de migrer vers la fin de la série mais également aux
plus petits éléments de migrer vers le début.
 Le tri shaker
PROCEDURE tri_shaker ( TABLEAU a[1:n])

sens ← 'avant', debut ← 1, fin ← n-1, en_cours ← 1 TANT

QUE ((sens='avant') ET (en_cours<fin)) OU ((sen
REPETER s='arriere) ET (en_cours>debut))
permut ← FAUX SI (sens='avant') ALORS
REPETER sens ← 'arriere'
SI a[en_cours] > a[en_cours + 1] ALORS fin ← fin - 1
echanger a[en_cours] et a[en_cours + 1] SINON
permut ← VRAI sens ← 'avant'
FIN SI debut ← debut + 1
SI (sens='avant') ALORS FIN SI
en_cours ← en_cours + 1 TANT QUE permut = VRAI
SINON
en_cours ← en_cours - 1 FIN PROCEDURE
FIN SI
 Le tri de Shell

• Donald L. Shell proposa, en 1959, une variante du tri par insertion. Ce

tri consiste à trier séparément des sous-suites de la table, formées par
les éléments répartis de h en h.
• Empiriquement, Shell propose la suite d'incréments vérifiant h1 = 1,
hn+1 = 3hn+1 en réalisant les tris du plus grand intervalle possible vers
le plus petit.
 Le tri de Shell
PROCEDURE tri_Insertion ( Tableau a[1:n],gap,debut)
POUR i VARIANT DE debut A n AVEC UN PAS gap FAIRE
INSERER a[i] à sa place dans a[1:i-1];
FIN PROCEDURE;

PROCEDURE tri_shell ( Tableau a[1:n])

POUR gap DANS (6,4,3,2,1) FAIRE
POUR debut VARIANT DE 0 A gap - 1 FAIRE
tri_Insertion(Tableau,gap,debut);
FIN POUR;
FIN POUR;
FIN PROCEDURE
Le tri Gnome
• Cet algorithme a été d'abord proposé en 2000 - sous le nom de "tri
stupide" - par le Dr. Hamid Sarbazi-Azad (Professeur à l'université de
Sharif, une des plus grandes universités d'Iran) puis redécouvert plus
tard par Dick Grune (le premier développeur de CVS) qui l'appela
"gnome sort" (parce qu'il parait que c'est la méthode qu'utilisent les
nains de jardin hollandais pour trier une rangée de pots de fleurs).
• L'algorithme est similaire au tri par insertion, sauf que, au lieu de
insérer directement l'élément à sa bonne place, l'algorithme effectue
une série de permutations, comme dans un tri bulle.
Le tri Gnome
PROCEDURE tri_Gnome(tableau[])
pos ← 1
TANT QUE pos < longueur(tableau)
SI (tableau[pos] >= tableau[pos-1])
pos ← pos + 1
SINON
echanger tableau[pos] ET tableau[pos-1]
SI (pos > 1)
pos ← pos - 1
FIN SI
FIN SI
FIN TANT QUE
FIN PROCEDURE
Le tri maximier
• Cette méthode de tri (aussi appelée «tri par tas» ou «heapsort» ou «tri
de Williams») est basée sur la notion de tas. Un tas est un arbre binaire
parfait tel que l’information contenue dans tout nœud est supérieure à
celle contenue dans ses fils. La méthode du tri par tas comporte deux
étapes :
• Construction par insertions successives d’un tas à partir du vecteur à
trier.
• On remplace la racine, qui est nécessairement le plus grand élément du
tableau par son fils le plus grand. La racine est transférée à la place de
la dernière feuille de l’arbre et celle-ci est repositionnée. On réitère
avec la nouvelle racine autant de fois qu’il y a de nœuds dans l’arbre.
Le tri fusion
• Il s’agit à nouveau d’un tri suivant le paradigme diviser pour régner. Le
principe du tri fusion (ou tri par interclassement) en est le suivant :
• On divise en deux moitiés la liste à trier (en prenant par exemple, un élément
sur deux pour chacune des listes).
• On trie chacune d’entre elles.
• On fusionne les deux moitiés obtenues pour reconstituer la liste triée.
 Le tri fusion
PROCEDURE tri_fusion ( TABLEAU a[1:n])
FAIRE
SI TABLEAU EST VIDE RENVOYER TABLEAU
gauche = partie_gauche de TABLEAU
droite = partie_droite de TABLEAU
gauche = tri_fusion gauche
droite = tri_fusion droite
renvoyer fusion gauche droite
POUR i VARIANT DE 1 A n - 1 - passage FAIRE
SI a[i] > a[i+1] ALORS
echanger a[i] ET a[i+1]
permut ← VRAI
FIN SI
FIN POUR
passage ← passage + 1
FIN PROCEDURE
Le tri rapide
• Le tri rapide - aussi appelé "tri de Hoare" (du nom de son inventeur Tony
Hoare) ou "tri par segmentation" ou "tri des bijoutiers" ou, en anglais
"quicksort" - est certainement l’algorithme de tri interne le plus efficace.
• Le principe de ce tri est d’ordonner le vecteur T.(0)..T.(n) en cherchant dans
celui-ci une clé pivot autour de laquelle réorganiser ses éléments. Il est
souhaitable que le pivot soit aussi proche que possible de la clé relative à
l’enregistrement central du vecteur, afin qu’il y ait à peu près autant d’éléments
le précédant que le suivant, soit environ la moitié des éléments du tableau.
Dans la pratique, comme dans la démo ci-dessous, on prend souvent le dernier
élément du tableau.
• On permute ceux-ci de façon à ce que pour un indice j particulier tous les
éléments dont la clé est inférieure à pivot se trouvent dans T.(0)...T.(j) et tous
ceux dont la clé est supérieure se trouvent dans T.(j+1)...T.(n). On place ensuite
le pivot à la position j.
• On applique ensuite le tri récursivement à, sur la partie dont les éléments sont
inférieurs au pivot et sur la partie dont les éléments sont supérieurs au pivot.
Le tri rapide
• Le choix du pivot est déterminant pour l'efficacité de ce tri. Plusieurs
options sont possibles :
• Choisir le premier élément du tableau
• Choisir le dernier élément du tableau
• Choisir un élément au hasard
• Choisir l'élément au milieu du tableau
• Trouver le pivot optimal en recherchant la médiane
• Ces différentes options peuvent être testées avec l'application ci-
dessous. Choisir la médiane comme pivot est bien entendu la solution
optimale... sauf que, la recherche de cette médiane est elle-même
coûteuse.
 Le tri rapide
Procedure tri_rapide (tableau [1:n], gauche, droit )
DEBUT
(* mur marque la separation entre les elements plus petits et ceux plus grands que
pivot*)
mur ← gauche;
(* On prend comme pivot l element le plus a droite *)
pivot ← tableau[droit];
placer a gauche de mur tout les elements plus petits
placer a droite de mur tout les element plus grands
(* On place correctement le pivot *)
placer le pivot a la place de mur
(* On poursuit par recursivite *)
SI (gauche<mur-1) ALORS tri_rapide(tableau,gauche,mur-1);
SI (mur+1<droit) ALORS tri_rapide(tableau,mur,droit);
FIN procedure