L421 - Algorithmique avancé

N. TSOPZE
MC-UYI
Objectifs
manipuler les différentes structures de
données Algorithmiques,
Evaluer les différentes complexités
Bien choisir une structure de données pour
la résolution d’un problème quelconque
Implémenter les structures de données en
C
Contenu
PARTIE 1 : STRUCTURES DE DONNEES
1 - TYPES ABSTRAITS DE DONNÉES
2 - PROGRAMMATION EN LANGAGE C DE STRUCTURES DE DONNÉES FONDAMENTALES
ETUDE DES STRUCTURES DE DONNÉES : PILE, FILE, FILES DE PRIORITÉS, LISTES.

PARTIE 2 : COMPLEXITE, STRATEGIES ET METHODES ALGORITHMIQUES

1 - ALGORITHMES ET CONCEPTION
COMPARAISON DES ALGORITHMES
RÉCURSIVITÉ
STRATÉGIES ALGORITHMIQUES : FORCE BRUTE, GLOUTON, DIVISER-POUR-RÉGNER
ALGORITHMES FONDAMENTAUX : TRIS, OPÉRATIONS SUR LES ARBRES
UTILISATION DE STRUCTURES DE DONNÉES FONDAMENTALES (LISTES, CHAINES, SETS,
DICTIONNAIRES,...)
2 - CONCEPTS FONDAMENTAUX DE LA CONCEPTION DE PROGRAMMES
- TABLEAUX DE SITUATION
- VÉRIFICATION DYNAMIQUE
- VÉRIFICATION STATIQUE

EN TP
IMPLÉMENTATION DES STRUCTURES DE DONNÉES EN C
PLATEFORME FRAMA-C
Structure
1. COURS MAGISTRAL
Diapositives (Enseignant)

2. TD
 Exercices faits à la maison (étudiant)

3. TP
Mise en œuvre des algorithmes (étudiant)
Discipline
Téléphones et ordinateurs fermés (sauf en
TP)
Retards proscrits
Assiduité absolument recommandée
Prise de paroles
Participation au cours encouragée
évaluation
Contrôle continu écrit
Examen écrit
Travaux Pratiques
Devoir fait à la maison
Types de données abstraits
TAD

abstraction : mécanisme consistant à penser à un
objet en termes d’actions que l’on peut effectuer sur lui,
et non pas en termes de représentation et d’implantation
de cet objet.

structure de données : collection d’informations
structurées et reliées entre elles .

spécification abstraite : description d’une
forme d’implantation informatique choisie pour
représenter et décrire la structure de donnée.

Type Abstrait de Données (TAD) : notation pour
décrire les types de données utilisés dans un algorithme,
ensemble des opérations + propriétés de ces opérations
TAD
Caractéristiques d’un TAD :
• Son nom,
• Les sortes qu’il manipule,
• Les opérations sur les données,
• Les propriétés de ces opérations.

Signature : donnée de son nom, les sortes qu’il utilise et

les différentes opérations sur les données.
Sortes : noms servant à représenter des ensembles de
valeurs sur lesquels vont porter les opérations.
Exemple : naturel, booleen, entier, etc.
Profil d’une opération : sortes de ses paramètres et la
sorte du résultat.
forme générale du profil :
Nom-opération : sorte1, sorte2, ..., sorten → sorter.
TAD (syntaxe)

sorte : ...............
utilise : ...........
opérations :
préconditions :
........ def_ssi .......
axiomes :
FinTAA
TAD (axiome)

Utiliser pour énoncer les propriétés des opérations

Forme générale de l’écriture des axiomes : termeg ≡ termed
symbole ”≡” pour ”équivalent à”, on peut remplacer ce qui est à
gauche par ce qui est à droite et réciproquement.

Extension à la condition : termeg ≡ si condition alors termed1
sinon termed2

écriture des axiomes


pour définir le résultat de la composition des opérations
observateurs et internes non constructeurs avec toutes les
opérations internes constructeurs.

nombre d’axiomes nécessaires pour définir les propriétés d’une
telle opération dépend de son nombre d’arguments et les
opérations constructeurs associées aux sortes de ces arguments.
TAD (Précondition)
Préconditions : restreindre l’utilisation des opérations à des opérandes
appartenant au domaine de définition de cette opération.
Syntaxe : pré(nom_opération(arguments)) définie ssi < condition >

NB : lorsqu’une opération n’a pas de précondition, le domaine de définition de

cette opération est toute la sorte.
Pré-condition : vérifiée pour que l’opération produise le résultat
attendu
post-condition (ou axiome) : description du comportement de chaque
opération
Questions lors de l’écriture des axiomes d’un TAD:

N’y a t-il pas d’axiomes contradictoires : consistance ?

A t-on donné un nombre suffisant d’axiomes pour décrire toutes
les propriétés du TAD : complétude ?
TAD (Types d’opérations)

1. Constructeur : allouer la mémoire nécessaire

à l'objet et d'initialiser ses attributs
2. Transformateur (modificateur) ; changer le
comportement du TAD
3. Observateur : surveiller le comportement des
attributs lorsque survient un évènement
4. Sélecteur : interroger le TDA.
3 itérateur : parcourir le TDA
Evaluation des algorithmes
 Mesure de coût
problème donne P,
algorithme A pour le résoudre;
Sur la donnée x de taille n, l'algorithme requiert,
mesure en nombre d'Operations élémentaires: c(x).
Le coût en temps varie :
taille de la donnée,
les différentes données de même taille n
Dépend:
De la machine sur lequel s’exécute l’algorithme,
de la traduction de l’algorithme en langage exécutable
par la machine
Mais en général le coût est en fonction de la
taille n des données.
 Mesure de coût
Cas défavorable ou pire des cas: définition le
maximum des coûts

Cas moyen: connaissance une distribution de

probabilités sur les données de taille n.
p(x) est la probabilité de la donnée x,
le coût moyen

Meilleur des cas: définition du minimum des

coûts
 Complexité
complexité des algorithmes est une
évaluation du coût d’exécution d’un
algorithme en termes de temps (complexité
temporelle) ou d’espace mémoire (complexité
spatiale).
Utilisée pour comparer deux algorithmes
dans leur comportement asymptotique
Notations de Landeau
g : R → R. Etant donné un point x0 ∈ R ∪]-∞,
+∞[
O(g) : ensemble des fonctions f pour
lesquelles il existe un voisinage V de x 0 et
une constante k > 0 tels que
|f(x)| ≤ k|g(x)|
voisinage d'un point x0 = partie de R
contenant un intervalle ouvert contenant le
point x0
Cela revient à calculer à l’infini lim
 Notations de Landeau
Opérations
f+ O(g) = {f + h / h ∈O(g)}
fO(g) = {fh / h ∈ O(g)}
h = f + O(g) si et seulement si h- f ∈ O(g
Formules
f = O(f)
O(-f) = O(f)
cO(f) = O(f)
O(f) + O(f) = O(f)
O(f)O(g) = O(fg)
fO(g) = O(fg)
Si f et g sont a valeurs positives, alors O(f) + O(g) = O(f
+ g)
 Notations de Landeau
ϴ(g) = ensemble des fonctions f pour
lesquelles il existe deux nombres k; a > 0 tels
que:
|f(x)| ≥ k|g(x)| pour tout x > a
Donc f ∈ ϴ(g) ⇔ g ∈ O(f)
Ω(g) = ensemble des fonctions f pour
lesquelles il existe des
nombres k1, k2, a > 0 tels que:
k1 |g(x)| ≤ |f(x)| ≤ k2 |g(x)| pour tout x > a
Donc Ω(g) = O(g) ∩ ϴ(g)
Complexité en temps
Permet de juger un algorithme
indépendamment de son implémentation
La plus utilisée pour l’évaluation d’un
algorithme
Évaluer le temps (théoriquement) utilisé
pour l’exécution en fonction de la taille des
données
Le plus souvent dans l’ordre asymptotique
Ne pas confondre avec le temps
d’exécution
Complexité en espace
Évaluer toutes les ressources matérielles
utilisées (théoriquement) pour la mise en
place de l’exécution de l’algorithme
Tenir compte des structures de données
Tableau
Listes
Piles
Arbres
Matrice
…
modèle de calcul de
complexité
Règles de calcul
Structures de contrôle
séquence
embranchement (ou sélection)
boucle (ou itération)
Structures de données
constantes
variables
tableaux
structures récursives (listes, arbres,
graphes)
 Règles de calcul
Enchaînement
Soient deux suites

Debut d’actions A1 et A2, et

A1+A2, la suite « A1
Action A1
suivi de A2 » Alors:
Action A2
fin TA1+A2(n) = TA1(n)+ TA2(n)
 Règles de calcul
Algorithme Conditionnelle

Debut TA(n) = TC(n) +

Si C alors Max( TA1(n), TA2(n))
Action A1
sinon
Action A2
fin
 Règles de calcul
Algorithme
Debut
Pour i allant de 1 à n Faire
A
FinPour
fin
n

∑TA
Itération (Pour) : i=1
 Règles de calcul
Algorithme
Debut
TantQue C
Faire A1
FinTantQue
fin

Itération (TantQue)
En notant niter(n) le nombre d’itérations, on a:
 Règles de calcul (sous algo)
Tenir compte du temps d’exécution du sous
algorithme dans le calcul
Enchainement:
TActions+sou-algo(n) = TActions(n)+ Tsous-algo(n)

Conditionnelle
boucle
Tableau, Pointeur et Allocation
dynamique
Tableau
Pointeur
Allocation dynamique
Types de données composés
Impossible de représenter certaines
informations à l’aide des données de types
simples
Mise en commun des éléments de types
simples pour un ensemble plus complexe
Doivent être déclarés dans la partie
« type » du corps d’algorithme et les
variables de types créées dans l’algorithme
Tableaux et enregistrements
Tableau
Composé des éléments de même type
(homogène)
Taille fixée dès la déclaration du type
Éléments numérotés de 1 à n, accès aux
éléments avec ces numéros
Exemple:
Vecteur = (1, 2, 7, -6, 4, 5, 2)
Prenom = (J,E,A,N)
Liste des étudiants
matrice
Tableau
Type type_tab= tableau[1…MAX] de
type_des_éléments

Max : maximum d’éléments pour une

variable
Type_tab : nom du type (identificateur)
Type_des_éléments : type des éléments
Tableau (accès aux éléments)
toujours élément par élément
accéder à l’élément d’indice i : Var_tab[i]
assurer que les indices ne sortent pas des
bornes
Exemple :
 i←1
V[i] ← 0 ;
ecrire(V[3]) ;
lire(V[2])
V[i]← V[i-1]+V[i-2]
Tableau (Opérations)
1. Créer un tableau (initialiser)
2. Afficher un tableau
3. ranger n valeurs dans un tableau
4. récupérer, consulter des valeurs rangées
dans un tableau
5. rechercher si une valeur est dans un tableau
6. Mettre à jour un tableau
7. effectuer des opérations entre tableaux :
comparaison de tableaux, multiplication, …
8. Trier un tableau
Tableau à plusieurs
dimensions
Type nom_type = tableau[1…MAX1 ; 1…
MAX2] de type_éléments

Nom_type : nom du type

MAX1: taille max de la première dimension
MAX2 : taille max de la deuxième
dimension
Type_éléments : type des éléments
Tableau à plusieurs
dimensions
Var M : nom_type
Exemple
Type matrice = tableau[1…10 ; 1…20] de
entier
Var M1: matrice
M1[1,1]←0
Ecrire (M1[i,i])
Lire(M1[i,j])
Listes Chainées
Listes chainées
ensemble de cellules liées entre elles par des
pointeurs;
pas de dimension fixée à sa création
cellule : structure :
une ou plusieurs données (comme toute
structure) ;
pointeur suivant sur la cellule suivante.
accès à la liste par un pointeur L sur la première
cellule
Parcourt de la liste d’une cellule à l’autre en
suivant les pointeurs suivant.
Le dernier pointeur suivant vaut NULL.
Tableau dynamique
Listes chainées (déclaration)
définir le type des éléments de liste :
Type Cellule= enregistrement
Info : type_élément // entier, réel, …
Suivant : Liste
finenregistrement
définir le type du pointeur :
Type Liste = ^Cellule
déclarer une variable pointeur :
Var P : Liste
Listes chainées (déclaration)
Allocation (réservation) d’une cellule
mémoire en mémoire et donne à P la valeur
de l'adresse de l'espace mémoire P^:
Allouer(P)
affecter des valeur à l'espace mémoire
P^.Info ← "Essai" ;
P^.Suivant ← Nil
Listes chainées (déclaration
en C)
Création d’une cellule
typedef float TypeDonnee;
/* definition du type cellule : */
typedef struct Cell
{
TypeDonnee donnee; /* definition des donnees */
/* on peut mettre ce qu’on veut comme donnee */
struct Cell *suivant; /* pointeur sur la structure suivante */
/* (de meme type que celle qu’on est en train de definir) */
}TypeCellule;
Déclaration de la liste vide
TypeCellule *L; /* declaration d’une liste */
Listes chainées (Traitement)
Créer une liste;
Ajouter un élément;
Supprimer un élément;
Modifier un élément;
Parcourir une liste;
Rechercher une valeur dans une liste.
 Listes chainées (simple
création)
Algorithme CréationListe
Var Tete, P : Liste
NombreElt : entier
DEBUT
Tete ← Nil /* pour l'instant la liste est vide*/
Allouer(P) /* réserve un espace mémoire pour un élément*/
Lire(P^.Info) /* lit et stocke dans l'Info lu dans la cellule P */
P^.Suivant ← Nil /* il n'y a pas d'élément suivant */
Tete ← P /* le pointeur Tete pointe maintenant sur P */
Allouer(P) /* réserve un espace pour le second élément */
Lire(P^.Info) /* lit et stocke dans l'Info lue dans P */
P^.Suivant ← Tete /* élément inséré en tête de liste */
Tete ← P
FIN
 Listes chainées (fonctions)
Fonction listeVide(a: liste): booléen;
Si(a == Nil) Alors
Retourner Vrai;
Fin

Procédure ajoutTete(var a: liste, x: entier);

allouer(u); // Créer une cellule vide.
[Link] ← x;
[Link] ← a;
a ← u;
Fin,
 Listes chainées (fonctions)
Procédre insertQueue(var a: liste, x: entier);
Var b: liste;
Debut
b ← a;
TantQue([Link] != nil) Faire
b ← [Link];
fintantque
allouer (u);
[Link] ← x;
[Link] ← nil;
[Link] ← u;
Fin,
 Listes chainées (fonctions)
Procédure ajoutQueue(var a: liste, x: entier);
Var u, b: liste;
Debut
Si(a == nil) Alors
allouer (u);
u. info ← x; [Link] ← nil; a ← u;
Sinon Si([Link] == nil) Alors
allouer (u);
[Link] ← x; [Link] ← nil; [Link] ← u;
Sinon
b ← [Link];
insertQueue(b, x);
[Link] ← b;
FinSi
Fin.
 Listes chainées (création)
Exercices: Adapter l’algorithme précédent
pour :
1. Créer une liste de n éléments lus avec n
lu par l’utilisateur
2. Créer une liste d’éléments lus sachant
que le dernier est 00
3. Créer une liste de n éléments à partir
d’un tableau
 Listes chainées (Affichage)
Procedure AfficherListe (Entrée P : Liste)
/* Afficher les éléments d’une liste chaînée
passée en paramètre */
DEBUT
P Tete
TANT QUE P <> NIL FAIRE
Ecrire(P^.Info)
P ← P^.Suivant
FIN TANT QUE
FIN
 Listes chainées (suppression)
Suppression entête
deux actions à réaliser :
faire pointer la tête de liste sur le deuxième
élément de la liste,
libérer l'espace mémoire occupé par l'élément
supprimé.
Principe
déclarer un pointeur local et le pointer sur
l'élément à supprimer,
Avancer la tête au suivant
libérer le pointeur local.
 Listes chainées (suppression)
Procedure SupprimerPremier (Entrée/Sortie Tete : Liste)
Var P : Liste
DEBUT
SI Tete <> Nil ALORS
P ← Tete
Tete ← P^.Suivant
Desallouer(P)
SINON
Ecrire("La liste est vide")
FINSI
FIN
 Listes chainées (suppression)
Suppression une valeur donnée
utiliser la suppression du premier élément car il faut
modifier le pointeur de tête,
1. trouver l'adresse P de l'élément à supprimer,
2. sauvegarder l'adresse Prec de l'élément
précédant l'élément pointé par P pour connaître
l'adresse de l'élément précédant l'élément à
supprimer,
3. faire pointer l'élément précédent sur l'élément
suivant l'élément à supprimer,
4. Libérer l'espace mémoire occupé par l'élément
supprimé.
 Listes chainées (suppression)
Procedure SupprimerElement (Entrée/Sortie Tete : Liste, Val : variant)
Var P : Liste /* pointeur sur l'élément à supprimer */
Prec : Liste /* pointeur sur l'élément précédant l'élément à supprimer */
Trouvé : Liste /* indique si l'élément à supprimer a été trouvé */
DEBUT
SI Tete <> Nil ALORS /* la liste pas vide */
SI Tete^.info = Val ALORS
P ← Tete ; Tete ← Tete^Suivant; Desallouer(P)
SINON /* l'élément à supprimer n'est pas le premier */
Trouve ← Faux ; Prec ← Tete ; P← Tete^.Suivant /* pointeur courant */
TANTQUE (P <> Nil ET Non Trouve) faire
SI P^.Info = Val ALORS /* L'élément recherché */
Trouve← Vrai
SINON /* L'élément courant n'est pas l'élément cherché */
Prec ← P ; P ← P^.Suivant
FINSI
FIN TANT QUE
SI Trouve ALORS
Prec^.Suivant ← P^.Suivant /* on "saute" l'élément à supprimer "/
Desallouer(P)
SINON Ecrire ("La valeur ", Val, " n'est pas dans la liste")
FINSI
FINSI
SINON Ecrire("La liste est vide") FINSI
FIN
 Listes chainées (recherche)
Conditions d’arrêt de parcours de liste
avoir trouvé la valeur de l'élément;
avoir atteint la fin de la liste.
Principe: se positionner au début de la
liste, la parcourir en allant à
« suivant » jusqu’à satisfaire une des
conditions précédentes
 Listes chainées (recherche)
Procedure RechercherValeur (Entrée Tete : Liste, Val : variant) Var P : Liste /*
pointeur de parcours de la liste */
Trouve : booléen /* indicateur de succès de la recherche */
DEBUT
SI Tete <> Nil ALORS /* la liste n'est pas vide
P ← Tete ; Trouve ← Faux
TANTQUE P <> Nil ET Non Trouve faire
SI P^.Info = Val ALORS /* élément courant */
Trouve ← Vrai
SINON /* pas l'élément courant */
P ← P^.Suivant /*élément suivant dans la liste */
FINSI
FIN TANT QUE
SI Trouve ALORS Ecrire (" La valeur ", Val, " est dans la liste")
SINON Ecrire (" La valeur ", Val, " n'est pas dans la liste")
FINSI
SINON Ecrire("La liste est vide") FINSI
FIN
Autres formes de liste
Piles
Files
Listes doublement chainées
Arbres et ABR
Définitions
Graphe connexe
Nœud particulier: racine
Chemin unique allant de la racine à n’importe quel
nœud
pas de cycle
nœud est représenté par un objet;
Chaque nœud contient un champ clé
pointeurs sur les autres nœuds (fils);
Nombre variable selon le type d’arborescence

Les structures arborescentes permettent une

amélioration globale des accès aux informations
Définitions
Arbre = graphe purement hiérarchique
Arbre binaire = tout nœud a au plus deux
fils „
Liste = arbre dégénéré „
Forêt = ensemble d ’arbres

Définition récursive d’un arbre :

 vide
constitué d’un élément
Constitué de plusieurs arbres
Définitions
nœud : caractérisé par une valeur + un nombre fini de
fils, possède un unique père
feuille : nœud sans fils
nœud interne : nœud qui n’est pas une feuille
arité d’un nœud n : nombre de fils du nœud n
arité d’un arbre a : nombre maximal de fils d’un nœud
de a
racine d’un arbre a : c’est le seul nœud sans père
profondeur d’un nœud n : nombre de nœuds sur la
branche entre la racine et le nœud n exclu
hauteur d’un arbre a : c’est le nombre de nœuds sur la
branche qui va de la racine de a à la feuille de
profondeur maximale
Structure de données
Pointeur=^noeud
noeud = Enregistrement
fils1: pointeur;
…
info:type_élément;
fils:pointeur;
fin;
 Parcours de l’arbre
préfixé (préordre): on traite la racine,
puis les sous-arbres gauches, enfin
les sous-arbres droits
infixé (projectif ou symétrique) : on
traite les sous-arbres gauches, puis
la racine, et enfin les sous-arbres
droits
postfixé (ordre terminal) : on traite
les sous-arbres gauche, puis les
sous-arbres droits, enfin la racine
Arbres binaires
Arbres binaires
chaque noeud a au plus 2 fils,
vide ou composé d’un élément
auquel sont rattachés un sous-
arbre gauche et un sous-arbre droit
valeur d’un noeud,
fils gauche d’un noeud
fils droit d’un noeud.
Arbre binaire complet
Chaque noeud non terminal a
exactement deux fils
parfait :
avant-dernier niveau complet
les feuilles du dernier niveau
groupées le plus à gauche
possible
Arbre binaire Ordonné
La chaîne infixée des valeurs
est ordonnée
Tous les éléments dans le sous-
arbre gauche d’un noeud sont
inférieurs à l’élément racine
Tous les éléments dans son
sous-arbre droit sont supérieurs
à l’élément racine
Arbre binaire - parcours
préfixé (préordre): on traite la
racine, puis le sous-arbre gauche,
puis le sous-arbre droit
infixé (projectif ou symétrique) : on
traite le sous-arbre gauche, puis la
racine, puis le sous-arbre droit
postfixé (ordre terminal) : on traite
le sous-arbre gauche, le sous-arbre
droit, puis la racine
 Arbre binaire - parcours
procédure
parcoursprefixe(racine: noeud)
si racine < > nil alors
1. traiter(racine);
2. parcoursprefixe(racine^.gauche);
3. parcoursprefixe(racine↑.droite);
finsi
fin
 Arbre binaire - parcours
procédure parcours_infixe(racine:
noeud)
si racine < > nil alors
1. Parcours_infixe(racine^.gauche);
2. traiter(racine);
3. Parcours_infixe(racine^.droite);
finsi
fin
 Arbre binaire - parcours
procédure
postfixé(racine:noeud);
si racine <> nil alors
1. postfixé(racine^.gauche);
2. postfixé(racine^.droite);
3. traiter(racine);
finsi
 Arbre binaire
1. Calcul de la taille d’un arbre binaire
2. Nombre de feuilles d’un arbre
binaire
3. Vérifier qu’un arbre n’est pas
dégénéré
4. Recherche une valeur dans un arbre
binaire
5. Longueur de cheminement de l’arbre =
somme des longueurs de tous les
chemins issus de la racine : LC
 Arbre binaire
1. Longueur de cheminement externe =
somme des longueurs de toutes les
branches issues de la racine : LCE
2. Profondeur moyenne (d’un noeud) de l
’arbre = moyenne des hauteurs de tous
les noeuds : LC/taille
3. Profondeur moyenne externe (d’une
feuille) de l’arbre = moyenne des
longueurs de toutes les branches
:LCE/nbfeuilles
Arbres Binaires de
Recherche
 ABR
opérations d’ensemble dynamique:
RECHERCHER, MINIMUM,
MAXIMUM,PRÉDÉCESSEUR, SUCCESSEUR,
INSÉRER et SUPPRIMER
arbre binaire complet à n noeuds, opérations
en Θ(lg n) dans le cas le plus défavorable.
arbre dégénéré à n noeuds, opérations en
Θ(n)
 hauteur attendue d’un arbre binaire de
recherche construit aléatoirement est O(lg n),
ce opérations de base en Θ(lg n) en moyenne
ABR - éléments
champ clé ou info
son enfant de gauche,
son enfant de droite
son parent
 ABR
propriété d’ABR
Si y est un noeud du sous-
arbre de gauche de x, alors
clé[y] ≤ clé[x].
Si y est un noeud du sous-
arbre de droite de x, alors
clé[x] ≤ clé[y].
 ABR
ARBRE-RECHERCHER(x, k)
si x = NIL ou k = clé[x] alors
retourner x
si k < clé[x] alors retourner
ARBRE-RECHERCHER(gauche[x], k)
sinon
retourner ARBRE-
RECHERCHER(droite[x], k)
 ABR
Fonction minimum
Fonction Maximum
Fonction Successeur
Fonction prédécesseur
 D

F
B

E H
A C

G I

J
 ABR - INSERTION ET
SUPPRESSION
Modification de la structure
de l’arbre binaire de
recherche.
conservation la propriété
d’arbre binaire de recherche
ABR - SUPPRESSION
ABR - SUPPRESSION