Introduction à

l’algorithmique
ATSA ETOUNDI Roger
Professeur Titulaire en Informatique
[email protected]
La société se
digitalise!!!
La société se digitalise!!!
 La société se digitalise!!!

 Réalité virtuelle

• Marketing digital
Réalité augmentée
• Internet
 Intelligence artificielle • Systèmes distribués
 • etc
Robotisation
 Algorithmes
 Génie logiciel
 Data science
 Réseaux informatiques
 Internet des objets
 Résolution Informatique des Problèmes
 Nous vivons dans un monde digital, les ordinateurs et les robots sont désormais autour de nous.
 Les ordinateurs à travers les programmes informatiques ou logiciels et les robots permettent à l’homme de réaliser des travaux répétitifs non
cognitifs en faisant des économies en temps tout en minimisant les erreurs et maintenant une certaine qualité de service.
 Les ordinateurs et les robots remplacent l’humain dans l’exécution de certaines activités au sein de l’entreprise.
 Les ordinateurs et les robots ont une chose en commun, c’est les programmes informatique qui tournent ou sont exécutés en leur sein.
 Les programmes informatiques constituent la base de l’informatique et qui donnent un sens à l’informatique.
 Avant que l’ordinateur ou le robot ne résolve le problème, l’informaticien doit dans un premier temps comprendre comment ce problème est
résolu par l’homme.
 Un problème est résolu avec les définition des différentes étapes non conflictuelles qui permettent d’attendre le résultat souhaité.
 Les différentes étapes conflictuelles permettant l’atteinte d’un résultat escompté est appelé un algorithme.
 L’algorithme sera par la suite traduit dans un langage compréhensible par l’ordinateur.
 L’activité de traduction de l’algorithme en langage compréhensible par l’ordinateur est appelée programmation.
 La programmation se fait en utilisant un langage de programmation.
 C’est au terme de la programmation que l’informaticien va mettre en place une application ou logiciel devant être exécuté par un ordinateur
ou un robot.
 Retenons: Pas d’algorithme pas de programmation. Pas de programmation pas de logiciel. Pas de logiciel pas d’ordinateur et de robot. Tout
informaticien doit savoir écrire les algorithme et les programmes informatiques.
 Résolution Informatique des Problèmes
 L’informaticien pour mener à bien son travail doit:
 Définir les étapes non conflictuelles a la résolution du problème
 Pour définir ces étapes, l’informaticien doit tres bien comprendre le problème.
 La compréhension du problème suppose la définition ou l’existence d’un cahier de charges.
 Le cahier de charges contient les différentes contraintes et différents besoins des utilisateurs finaux ou les demandeurs ou ceux qui
observent le problème.
 Chaque étapes de l’algorithme doit être maitrisée.
 La maitrise suppose la connaissance des données à prendre en compte des le départ (données d’entrée - Input) et les données à
l’arrivée (donnée en sortie – output)
 Les données de la première étape sont appelées données initiales.
 Les données de la dernière étape sont appelées données résultats.
 Pour les étapes intermédiaires, les données résultats de l’ étape précédentes constituent les les données d’entrée pour l’ étape
suivante.
 Un algorithme peut etre vu comme une boîte noire ou une boîte blanche.
 L’algorithme vu comme une boite noir es juste la définition des données initiales associées à leurs contraintes et les données
résultats associées à leurs contraintes.
 L’algorithme vu comme une boite blanche est la données des détails de toutes étapes et les conditions pour leurs exécutions
Algorithme
Algorithme vu comme une boîte noire

Entrées sorties

Nom de l’algorithme
 Résolution Informatique des Problèmes

Identification du Analyse de l’environnement visant a définir les difficultés liées aux

Problème 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
Codification de la solution duquel 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
Implantation de la solution dans l’infrastructure technologique
solution
Techniques de conception d’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
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
Ilpermet 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 p<- p*j Pour j =0 a 100,2 faire
p<- p*j Finpour afficher (j)
Finpour afficher (p) Finpour
La valeur du pas est 1
afficher (p) ce bout de
La valeur du pas est 1 programme affiche
Le bout de programme calcule la
factoriel de 100 tous les nombres pairs
Le bout de programme
inferieur ou egal a 100
calcule la factoriel de 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 ayant les mêmes propriétés
 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
étendre Bool1 avec
false:Bool
Constructeurs Constructeur
et: Bool xBool -> Bool non: Bool -> Bool
ou : Bool x Bool -> Bool Propriété
eq : Bool x Bool -> Bool
P3:  b:Bool non (non b))=b
Propriétés
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 TAD Nat1

Type Nat
utilise Bool2 etendre Nat0 avec
Générateur
0:Nat
observateur
1:Nat isnat: Nat -> Bool
Constructeur
succ : Nat -> Nat
Propriété
+ : Nat x Nat -> Nat P4:  n:Nat isnat(n) => 0=n \/ 1=n \/
Propriété
P1:  n:Nat Succ(n) = N+1 m:Nat succ(n)=m
p2: succ(0) = 1
fin
P3: 0+1 = 1
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
P3: i = j => Set(Set(t, i, x), i, y) = Set(t, i, y);
Opérations :
Create : → Tab
P4: Get(Set(t, i, x), i) = x;
findex: Tab → Nat P5: findex(t) i /\ i<j /\ get(t,j)=x => o:Obj
lindex: Tab → Nat get(t,i) = o;
P6 findex(t)  lindex(t)
get : Tab × Nat → Obj
set : Tab × Nat ×Obj → Tab
last: Tab → Nat P7: taille(t) = lindex(t) – findex(t) +1
taille: Tab → Nat p8: isin(t,x) => n:Nat get(t,n)=x /\
n last(t)
full: Tab → Bool
empty: Tab → Bool
isin: Tab x Obj → Bool 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
 P: Pile, o:Obj EstVide(Empiler(o, p)) =
Utilise Bool FAUX
Opérations :  P: Pile, o;Obj Depiler(Empiler(o, p)) = p
fin
PileVide : {} → Pile
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
utilise Bool Axiomes : f,f’:File, o:obj
Opérations : P1: defiler(f ) =f’ => non estVide(f )
fileVide : → File
P2: estVide(FileVide()) = VRAI
P3: estVide(Enfiler(o,f )) = FAUX
estVide : File → Booleen
P4: defiler(Enfiler(o, f)) = f
enfiler : Obj x File → File
P5: non estVide(f ) =>
defiler : File → File
defiler(Enfiler(o, f )) = f
fin
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’ =>
fileVide : → Filep
priority(dernier(f’) 
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 de comprendre la spécification d’une cellule,
car en réalité, une liste est une association des cellules
TAD Cellule
mémoires.
Type Cel, Obj. Adr
*Une cellule est constituée: Opérations
créer: → Cel
d’une zone d’adresse de la cellule suivante
adresse: Cel → Adr
*d’une zone de donnée data: Cel → Obj
adrsuiv: Cel → Adr
Axiomes
" c,c:Cel
c  c’ => adresse Cc)  adresse(c’)
fin
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
Etendre List0 avec Axiomes  l’l’:List. o:Obj
Operations P1: l’=ajouterfin(l,o) => data(last(l’))=o /\
ajouterfin: ListxObjt → List
delfin: List → List precedent(last(l’))=last(l)
last : List → List
P2: l’=delfin(l) => l listvide /\
last(l’) =
precedent: CelxList → Cel
precedent(last(l))
Fin
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
P2: l’=delfinter(l,c) => l  listvide /\
last : List → List 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
oo’ => ajoute(o,ajoute(o’,e)) =
ajoute : Obj x Ens → Ens ajoute(o’ ajoute(o, e))
supprime : Obj x Ens → Ens
Supprime(o,ajoute(o’,e)) =
appartient : Obj x Ens → Booleen 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

 Unenregistrement 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 k­ième argument doit correspondre au type du k­ième paramètre.
 Un paramètre défini en "Donnée" doit correspondre à un argument qui
possè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 (bubble Pseudo code associé au principe

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

←1 QUE ((sens='avant') ET (en_cours<fin)) OU (
(sens='arriere) ET (en_cours>debut))
REPETER SI (sens='avant') ALORS
permut ← FAUX sens ← 'arriere'
REPETER fin ← fin - 1
SI a[en_cours] > a[en_cours + 1] ALORS SINON
echanger a[en_cours] et a[en_cours + 1] sens ← 'avant'
permut ← VRAI debut ← debut + 1
FIN SI FIN SI
SI (sens='avant') ALORS TANT QUE permut = VRAI
en_cours ← en_cours + 1
SINON FIN PROCEDURE
en_cours ← en_cours - 1
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 h 1 = 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
 Différentes problématiques

 Terminaison : terminera en un temps fini.

 Complexité en temps : terminera en un temps borné
(raisonnable).
 Complexitéen espace : terminera en utilisant une quantité de
mémoire bornée (raisonnable).
 Correction : si l’algorithme termine en donnant une proposition
de solution, alors cette solution est correcte.
 Complétude : pour un espace de problèmes donné,
l’algorithme, s’il termine, donnera toujours des propositions de
solutions
 Introduction à l’analyse des algorithmes
 Lors du développement d'un logiciel, de nombreux éléments importants doivent être pris en compte:
 la convivialité
 la modularité
 la sécurité
 la facilité de maintenance
 L’aisance dans son utilisation
 Pourquoi se préoccuper des performances?
 La réponse à cette question est simple, nous ne pouvons avoir tous les attributs ci-dessus que si nous avons des
performances.
 Parler de la performance reviens a définir la quantité de ressources qu’il utilise:
1. son temps d’exécution ou l’efficacite
2. L’espace qu’il consomme pendant son exécution
 Deux types de complexité
 complexité temporelle
 complexité spatiale.
Introduction à l’analyse des algorithmes

 Pour un même objectif, nous pouvons avoir des algorithmes différents

 Comment savoir, lequel est le meilleur?
 L'analyse asymptotique est la grande idée pour repondre a cette question
 Elle traite la qualité en analysant les algorithmes.
 Dans l’analyse asymptotique, nous évaluons les performances d’un algorithme en
termes de taille d’entrée (nous ne mesurons pas le temps d’exécution réel).
 Nous calculons comment le temps (ou l'espace) pris par un algorithme augmente avec
la taille d'entrée.
Types d’analyse

 Généralement, nous effectuons les types d'analyse suivants avec n la taille des données
en entree:
 Le pire des cas: Le nombre maximum de mesures prises sur une instance de taille n.
 Le meilleur des cas: Le nombre minimum de mesures prises sur une instance de taille n.
 Cas moyen: Nombre moyen d'étapes effectuées sur une instance de taille n.
Le pire des cas - Worst case

 Dans le pire des cas, nous calculons jusqu'à la limite supérieure du temps d'exécution
d'un algorithme.
 Nous devons connaître le cas qui entraîne l'exécution d'un nombre maximal
d'opérations.
 Pour la recherche linéaire dans un tableau, le pire des cas se produit lorsque l'élément à
rechercher n'est pas présent dans le tableau.
 Lorsque l’element n’est pas présent, la fonction recherche() le compare à tous les
éléments de tab[0..n] un à un.
 Par conséquent, la complexité temporelle de la recherche linéaire dans le pire des cas
serait Θ(n).
Cas moyen - Average case

 Dans l'analyse de cas moyen, nous prenons toutes les entrées possibles et calculons le
temps de calcul pour toutes les entrées.
 Faites la somme de toutes les valeurs calculées et divisez la somme par le nombre total
d'entrées.
 Nous devons connaître (ou prédire) la distribution des cas.
 Pour le problème de la recherche linéaire, supposons que tous les cas soient
uniformément distribués (y compris le cas où l’element n'est pas présent dans le
tableau).
 Nous additionnons donc tous les cas et divisons la somme par (n + 1).
Cas moyen - Average case
Le meilleur des cas - Best case

 Dans l'analyse meilleur des cas, nous calculons la limite inférieure du temps
d'exécution d'un algorithme.
 Nous devons connaître le cas qui entraîne l'exécution d'un nombre minimal
d'opérations.
 Dans le problème de la recherche linéaire, le meilleur des cas se produit lorsque
l’element est présent au premier emplacement. Le nombre d'opérations dans le meilleur
des cas est constant (ne dépend pas de n).
 Donc, la complexité temporelle dans le meilleur des cas serait Θ(1).
Conclusion

 La plupart du temps, nous effectuons une analyse dans le pire des cas. Dans la pire
analyse, nous garantissons une limite supérieure sur le temps d'exécution d'un
algorithme, ce qui est une bonne information.
 L'analyse de cas moyen n'est pas facile à faire dans la plupart des cas pratiques et c'est
rarement fait. Dans l'analyse de cas moyen, nous devons connaître (ou prévoir) la
distribution mathématique de toutes les entrées possibles.
 L'analyse meilleur de cas est fausse. Garantir une limite inférieure sur un algorithme ne
fournit aucune information car dans le pire des cas, un algorithme peut prendre des
années à s'exécuter.