L'objectif de ce TP est de réaliser un projet en Java Eclipse avec cahier de charge

(Pseudo code et analyse de la complexité des algorithmes implémentés). La réalisation du

projet doit s’effectuer en groupe de 3 ou 4 étudiants au plus (sur demande), mais la notation
est individuelle. Ainsi la répartition des tâches doit être clairement définie. Vous serez évalué
sur la qualité du programme produit (modularité, clarté, documentation...) et sur le bon emploi
de l'environnement de développement. Chaque projet doit contenir les noms et matricules des
membres du groupe. Chaque groupe doit réaliser et présenter au moins six (06) projets.

Projet 1 : Evaluation d’un polynôme

On donne un tableau Tab an, a(n-1), …, a1, a0 représentant les coefficients du polynôme
n 1
p ( x )  a n x  a n 1 x    a1 x  a 0
n

Travail à faire :
1. Implémenter un algorithme de la force brute pour évaluer le polynôme
n 1
p ( x )  a n x  a n 1 x    a 1 x  a 0 en un point donné x 0 et déterminer la classe
n

d’efficacité au pire.
2. Si l’algorithme que vous avez conçu est dans  n 2  , implémenter un autre algorithme
linéaire, par exemple celui de Hörner, pour ce problème.
3. Faites une comparaison du temps d’exécution de ces deux programme pour n=25, 50,
100 et 1000.

Projet 2 : Carrés magiques

Un carré magique d’ordre n est un arrangement des nombres de un à n 2 dans une matrice
carrée d’ordre n, avec chaque élément apparaissant exactement une seule fois, tel que chaque
ligne, chaque colonne et chaque diagonale principale a la même somme.
Travail à faire :
1. Montrer que si une matrice carrée d’ordre n existe la somme en question doit être
égale à n ( n 2  1) / 2 .
2. Concevoir un algorithme de recherche exhaustive pour générer tous les carrés
magiques d’ordre n.
3. Chercher sur Internet ou dans votre bibliothèque un algorithme meilleur pour générer
les carrés magiques.
4. Implémenter les 2 algorithmes—la recherche exhaustive et celui que vous aurez
trouvé—et effectuer une expérience pour déterminer la plus grande valeur de n pour
laquelle chacun des algorithmes est capable de trouver un carré magique d’ordre n en
moins de une minute sur la machine que vous utilisez.

Projet 3 : Problème de la clique

Etant donné un graphe G et un entier positif k, déterminer si le graphe contient une
clique de taille k, c’est-à-dire un sous-graphe complet de k sommets.

Projet 4 : Plus petit et plus grand éléments

On donne un tableau Tab de n éléments ordonnable.
Travail à faire :
1. Implémenter l’algorithme du diviser-pour-régner pour trouver les valeurs du plus petit
et du plus grand élément dans un vecteur de n nombres.
2. Comparer votre algorithme avec l’algorithme de la force brute de ce problème pour
n=100 ; 300 et 500.
Travail à faire : Concevoir un algorithme de recherche exhaustive pour ce problème.

TP Conception et Analyse des Algorithmes Page 1

Projet 5: Paire la plus proche
Le problème de la paire la plus proche demande de trouver deux points les plus proches dans
un ensemble de n points. Pour simplifier, nous considérons le cas bidimensionnel, même si le
problème peut aussi bien se poser pour des points appartenant à des espaces de dimension
supérieure. Nous supposons que les points en question se spécifiés dans une forme standard
par leurs coordonnées cartésiennes (x , y) et que la distance entre deux points Pi  ( x i , y i ) et
Pj  ( x j , y j ) est la distance euclidienne standard d Pi , P j   ( x i  x j ) 2  ( y i  y j ) 2
Travail à faire :
1. Implémenter par l’approche de la force brute
Résoudre ce problème conduit à l’algorithme évident suivant : calculer la distance entre
chaque paire de points distincts et trouver la paire qui a la plus petite distance. Naturellement,
nous n’avons pas besoin de calculer deux fois la distance associée à la même paire de points.
Pour éviter de le faire, nous considérons uniquement les paires de points ( Pi , P j ) pour
lesquels i  j.
2. Implémenter par l’approche de Diviser pour Mieux régner
Considérons la version diviser-pour-régner bidimensionnelle de l’algorithme de la paire la
plus proche dans laquelle on trie simplement chacun des deux ensembles C1 et C2 dans
l’ordre croissant de leurs coordonnées y à chaque appel récursif. En supposant que la tri est
effectué par le tri fusion, écrire et résoudre la relation de récurrence du temps d’exécution
dans le pire cas pour n  2 k .
3. Problème : Poste de police
Soient x1  x 2    x n des nombres réels représentant les coordonnées de n villages situés
le long d’une route droite. Un poste de police doit être construit dans l’un de ces villages.
a) Concevoir un algorithme efficace pour déterminer la position du poste de police
qui minimise la distance moyenne entre les villages et le poste de police.
b) Concevoir un algorithme efficace pour déterminer la position du poste de police
qui minimise la distance maximum d’un village au poste de police.
4. Implémenter le problème un espace k-dimensionnel
Le problème de la paire la plus proche peut être posé dans un espace k-dimensionnel dans
lequel la distance euclidienne entre deux points x  ( x1 ,  , x k ) et y  ( y1 ,  , y k ) est
k

 x  ys  .
2
définie par d ( x , y )  s
s 1

Projet 6: couverture convexe

Le problème de la couverture convexe est le problème de la construction de la couverture
convexe d’un ensemble donné de n points.
Travail à faire :
1. Trouver la couverture convexe des ensembles suivants et identifier leurs points
extrêmes (s’ils existent)
a) un segment de droite
b) un carré
c) la frontière d’un carré
d) une ligne droite
2. Concevoir un algorithme temps-linéaire pour déterminer deux points extrêmes de la
couverture convexe d’un ensemble de n points du plan.
3. Apporter une modification à l’algorithme de la force brute pour le problème de la
couverture convexe pour traiter plus de deux points situés sur la même ligne droite.

TP Conception et Analyse des Algorithmes Page 2

Projet 7 : Reconnaissance des chaînes

Etant donné une chaîne de n caractères appelée texte et une chaîne de m caractères
( m  n ) appelée forme, trouver une sous chaîne du texte égale à cette forme. Pour le dire plus
précisément, il s’agit de trouver un indice i —l’indice du caractère le plus à gauche de la
première sous-chaîne assortissante dans le texte—tel que t i  p 0 ,  ,t i  j  p j ,  , t i  m 1  p m 1 :
t0  ti  ti j  t i  m 1  t n 1 Texte T
↕ ↕ ↕
p0  pj  p m 1 Forme P

ALGORITHME BruteForceStringMatch(T[0..n – 1], P[0..m – 1])

//Implémente la reconnaissance des chaînes par la force brute
//Input : Un vecteur T[0..n – 1] de n caractères représentant un texte et un vecteur P[0..m– 1]
//de m caractères représentant une forme.
//Output : L’indice du premier caractère du texte où commence une correspondance ou -1
//si la recherche échoue.
for i  0 to n – m do
j0
while j  m and P[j] = T[i + j] do
jj+1
if j = m return i
return – 1
Travail à faire :
1- Programme reconnaissant des chaînes par la force brute
2- Ecrire un autre programme
Capable de trouver un mot à l'intérieur d'une matrice de caractères. Le programme devra tout
d'abord demander à l'utilisateur la matrice de caractères de dimension NN (N sera demandé à
l'utilisateur). Il demandera ensuite le mot à rechercher, la longueur M du mot devra être
inférieure à N. Le programme devra rechercher la présence du mot à l'intérieur de la matrice,
horizontalement de gauche à droite et de droite à gauche et verticalement de haut en bas et de
bas en haut. Si le mot est trouvé, le programme affichera les coordonnées du caractère de
début de la chaine et sa direction. Si le mot n'est pas trouvé, un message sera affiché. Exemple
de matrice et de mots trouvés:

TP Conception et Analyse des Algorithmes Page 3

Projet 8 : Recherche exhaustive
Le problème du voyageur de commerce : En termes simples, le problème du voyageur de
commerce demande de trouver le plus court chemin passant par n cités qui visite chaque cité
exactement une fois avant de revenir à la cité de départ. Ce problème peut convenablement
être modélisé par un graphe pondéré dans lequel les sommets représentent les cités et les
poids des arcs représentent les distances. Le problème peut alors être posé comme le problème
de la recherche du plus court chemin Hamiltonien d’un graphe.
Le problème du sac à dos : Etant donné n objets de poids connus w1 ,  , w n et des valeurs
v 1 ,  , v n et un sac à dos de capacité W, trouver le sous-ensemble d’objets le plus valuable qui
s’ajuste dans le sac.
Travail à faire :
1. Implémenter le backpack
a. Implémenter une fonction qui génère n objets O(w, v) de poids w  1, 7  et de
valeur v  5 ,10  .
b. Implémenter l’algorithme pouvant contenir le maximum d’objet dans un sac de
n

poids maximal W     w i pour  =0.25, 0.50 et 0.75.

i 1

2. Implémenter le traveling salesman et afficher le temps d’exécution du problème pour

n=10 ; 30 et 50 ;

Projet 9 : Recherche ternaire

Soit l’algorithme suivant pour la recherche d’une clé K dans un vecteur trié A[0..n – 1 ].
Si n = 1, comparer simplement la clé de recherche K avec le seul élément du vecteur ; sinon,
chercher récursivement en comparant K avec A n / 3   , et si K est plus grand, comparer le
avec A 2 n / 3   pour déterminer dans quel tiers du vecteur continuer la recherche.
Travail à faire :
1- Implémenter l’algorithme de rechercher ternaire
2- Comparer l’algorithme avec celle de la recherche dichotomique.

Projet 10 : Les nombres palindromes

Un nombre sera dit « palindrome » s’il peut se lire de gauche à droite et de droite à gauche en
représentant le même nombre. Les nombres suivants sont palindromes : 425524, 121, 3, etc.
Travail demandé :
1- Ecrire une fonction extrait qui reçoit un entier (nb) en paramètre et qui :
• retourne –1 et ne modifie pas nb si nb<10
• retourne le 1er chiffre de nb et modifie nb en retirant le chiffre de plus fort poids.
Par exemple extrait(4657) retourne 4 et nb vaut au retour 657.
2- Ecrire, en utilisant la fonction précédente une fonction « booléenne » palindrome qui
recevant un entier en paramètre retourne vrai ou faux selon que cet entier est un
palindrome ou non
3- Ecrire le programme principal qui demande de façon répétitive un entier non signé à
l’utilisateur et dit si c’est un palindrome ou non.

TP Conception et Analyse des Algorithmes Page 4

Projet 11 : Tri rapide (Quicksort)
Le Quicksort est un autre algorithme de tri important basé sur l’approche du diviser-pour-
régner. Contrairement au tri par fusion, qui divise ses éléments d’entrée suivant leur position
dans le vecteur, le Quicksort les divise selon leur valeur. Spécifiquement, il réarrange les
éléments du vecteur A[0..n – 1] pour obtenir sa partition, une situation où tous les éléments
avant une certaine position s sont plus petits ou égaux à A[s] et tous éléments après la position
s sont supérieurs ou égaux à A[s] :
A [ 0 ]  A [ s  1] A [ s ] A [ s  1]  A [ n  1 ]
         
 A[ s ]  A[ s ]

Evidemment, après avoir obtenu une partition, A[s] sera dans sa position finale dans le vecteur
trié, et nous pouvons continuer le tri des deux sous-vecteurs formés des éléments qui
précèdent et qui suivent A[s] séparément (par exemple, par la même méthode).

ALGORITHME QuickSort(A[L..R])
//Trie un sous-vecteur par le quicksort
//Input : Un sous-vecteur A[L..R] de A[0..n – 1] défini par ses indices inférieur et
supérieur.
//Output : Le sous-vecteur A[L..R] trié par ordre croissant
if L  R
s  Partition(A[L..R]) // s est la position de coupure
QuickSort(A[L..s – 1])
QuickSort(A[s + 1..R])

Une partition de A[0..n – 1] et, plus généralement, de ses sous-vecteurs peut être obtenue par
l’algorithme suivante. D’abord, on choisit un élément par rapport auquel on va diviser le sous-
vecteur. A cause de son rôle directeur, on appelle cet élément le pivot. Il existe plusieurs
stratégies différentes pour choisir le pivot, nous reviendrons sur ce sujet lorsque nous
analyserons l’efficacité de l’algorithme.
Travail à faire : Implémenter le QuickSort () si la stratégie de la fonction Partition ()
consiste à :
1. Prendre le premier élément du sous-vecteur comme pivot : p  A[ L ] ;
2. Prendre le dernier élément du sous-vecteur comme pivot : p  A[ R ] .

Projet 12 : Tableau des complexes

Un nombre complexe est une structure composée d’une partie réelle et d’une autre imaginaire.
Il est de la forme x + iy, où x et y sont des nombres réels, et i un « nombre imaginaire » tel que
i2 = - 1.
typedef struct Complex{
float Reel ;
float Imag;
};
Travail demandé :
1- On demande de créer un tableau Tab dont les éléments sont des complexes.
2- Ecrire une fonction Norme() qui prend en entrée un nombre complexe C= x + iy et
renvoie en sortie sa norme norm  x  y .
2 2

3- Ecrire le programme principal qui trie les éléments du Tab selon l’ordre croissant de
leurs normes.

TP Conception et Analyse des Algorithmes Page 5

Projet 13 : Calcul de sin ()
3 2 n 1 2 2n
x x x x
Le développement de sin( x )  x   ...  (  1)
n
et cos( x )  1   ...  (  1)
n
.
3! ( 2 n  1)! 2! ( 2 n )!
2 n 1 2n
x x
Pour cela on pose Un    1   et Vn    1  
n n
. Trouver les relations rs et rc
( 2 n  1)! ( 2 n )!
U n 1 V n 1
entre deux termes consécutifs des suites Un et Vn en calculant rs  et rc  .
Un Vn
Travail demandé :
1- Ecrire une fonction sin() qui prend en entrée une valeur réel x et une précision
U n 1
  0 . 0001 et calcule la valeur de sin(x) jusqu’à l’ordre n tel que  .
Un
2- Ecrire une fonction cos() qui prend en entrée une valeur réel x et une précision
V n 1
  0 . 0001 et calcule la valeur de cos(x) jusqu’à l’ordre n tel que  .
Vn
3- Ecrire le programme principal qui de façon répétitive demande à l’utilisateur de faire
entrer un réel x puis calcule sin(x) ou cos(x) selon le choix de l’utilisateur.

Projet 14 : Nombre de jours sur terre

On veut écrire un algorithme pour calculer le jour qu’une personne a déjà vécu connaissant la
date du jour et sa date de naissance.
Une année est bissextile si elle est multiple de 4, et si de plus elle est multiple de 100 elle doit
aussi être multiple de 400. Par exemple :
 1985 non, car elle n’est pas multiple de 4 c’est-à-dire 1985 modulo 4 ≠ 0 ;
 1996 oui, car 1996 modulo 4 =0 et 1996 n’est pas multiple de 100;
 1900 non, car 1900 modulo 4 = 0; 1900 modulo 100 = 0 mais 1900 modulo 400 ≠ 0
 2000 oui, car 2000 modulo 4 = 0; 2000 modulo 100 = 0 et 2000 modulo 400 = 0.
Travail demandé :
typedef struct Date {
unsigned short Jour ;
unsigned short Mois ;
unsigned short Annee ;
};
1- Ecrire une fonction Bissextile() qui prend en argument une année, puis renvoie 1 si elle
est bissextile et 0 sinon.
2- Ecrire une fonction NbrJoursMois() qui prend en argument Mois et Année, puis
renvoie le nombre de jours que Mois a durant l’année Année.
3- Ecrire une fonction ValideDate() qui prend en entrée une structure Date D et affiche 1
si c’est une date valide et 0 sinon.
4- Ecrire une fonction NbrJours() qui prend en argument Dn la date de naissance d’une
personne et Dj la date du jour et puis renvoie le nombre de jours depuis la naissance à
la date courante.

TP Conception et Analyse des Algorithmes Page 6

Projet 15 : Multiplication de grands entiers
Certaines applications, notamment la cryptographie moderne, nécessitent la manipulation des
entiers de plus de 100 chiffres décimaux. Comme de tels entiers sont si longs pour être
représentés dans un seul mot d’information sur un ordinateur moderne, ils nécessitent un
traitement particulier. Ce besoin pratique nécessite la recherche soutenue d’algorithmes pour
une manipulation efficace de grands entiers. Dans cette section, nous présentons un
algorithme intéressant pour la multiplication de tels nombres. Evidemment, si nous utilisons
l’algorithme manuel classique de multiplications des nombres de n chiffres, chacun des n
chiffres du premier nombre est multiplié par chacun des n chiffres du deuxième nombre pour
un total de multiplications de chiffres. Bien qu’il puisse apparaître qu’il sera impossible de
concevoir un algorithme avec moins de multiplications de chiffres, il ressort qu’il n’en est
rien. Le miracle du diviser-pour-régner vient à la rescousse pour accomplir ce miracle.

Supposons que A et B sont deux nombres entiers de 2n chiffres (on ajoute des zéros
supplémentaires si nécessaire pour avoir des nombres de longueur). Posons
A  ( a 2 n 1 a 2 n  2  a1 a 0 ) 10 et B  ( b 2 n 1b 2 n  2  b1b 0 ) 10
Soit A  10 n A1  A0 , B  10 n B1  B 0
Où A1  ( a 2 n 1  a n 1 a n )10 , A0  ( a n 1  a1 a 0 ) 10
B1  ( b 2 n 1  b n 1b n ) 10 , B 0  ( b n 1  b1b0 ) 10
L’algorithme pour la multiplication rapide des entiers est basé sur l’identité
AB  (10  10 ) A1 B1  10 ( A1  A0 )( B 0  B1 )  (10  1) A0 B 0
2n n n n

 10 A1 B1  10 ( A1 B 0  A0 B1 )  A0 B 0
2n n

 C 2 10  C 110  C 0
2n n

Où C 2  A1 B1 est le produit de leurs premières moitiés

C 0  A0 B 0 est le produit de leurs deuxièmes moitiés
C 1  ( A1  A0 )( B1  B 0 )  ( C 2  C 0 ) est le produit de la somme des deux moitiés de A et la
somme des deux moitiés de B moins la somme de C 2 et C 0 .
Si n est pair, nous pouvons appliquer la même méthode pour calculer les produits A1 B1 ,
( A1  A0 )( B 0  B1 ) et A 0 B 0 . Ainsi, si n est une puissance de 2, nous avons un algorithme
récursif pour calculer le produit de deux nombres entiers de n chiffres. Dans sa pure forme, la
récursion s’arrête lorsque n devient un. Elle peut aussi être arrêtée lorsque nous considérons n
assez petit pour multiplier directement les nombres de cette taille.
Travail à faire : Implémenter l’algorithme en considérant qu’on arrête de faire l’appel
récursif pour : n=1 ; n=2.

Projet 16 : L’algorithme de Floyd

Etant donné un graphe connexe pondéré (orienté ou non orienté), le all-pairs shortest-paths
problem demande de trouver les distances (les longueurs des plus courts chemins) de chaque
sommet à tous les autres sommets. Il est commode d’enregistrer les longueurs des plus courts
chemins dans une matrice D d’ordre n appelée la matrice des distances : l’élément d ij dans la
ième ligne et la jème colonne de la matrice indique la longueur du plus court chemin de ième
sommet au jème sommet (1  i , j  n ) . Par exemple, voir la Figure 3.
Nous pouvons générer la matrice des distances avec un algorithme qui très semblable à
l’algorithme de Warshall. Il s’appelle l’algorithme de Floyd, d’après son inventeur R. Floyd
[Flo62]. Il est applicable à la fois aux graphes pondérés orientés et non orientés.

TP Conception et Analyse des Algorithmes Page 7

(Naturellement, dans le cas d’un graphe orienté, on entend par chemin ou cycle un chemin
dirigé ou un cycle dirigé).

2 a b c d a b c d
a b
a 0  3  a 0 10 3 4
3 6 7 W= b 2 0   D= b 2 0 5 6
c d c  7 0 1 c 7 7 0 1
1
d 6   0 d 6 16 9 0

(a) (b) (c)

Figure 3 : (a) Un digraphe. (c) Sa matrice des poids. (c) Sa matrice des distances.

L’algorithme de Floyd calcule la matrice des distances d’un graphe pondéré avec n sommets à
travers une série de matrices d’ordre n :

(0) ( k 1 ) (k ) (n)
D , , D ,D , , D (13.2)

Chacune de ces matrices contient les longueurs des plus courts chemins avec certaines
contraintes sur les chemins considérées pour la matrice en question. Précisément, l’élément
(k )
d ij dans la ième ligne et la jème colonne de la matrice D ( k ) ( 0  k  n ) est égal à la
longueur du plus court chemin parmi tous les chemins du ième somme au jème sommet,
chaque sommet intermédiaire, s’il en existe, ayant un numéro inférieur à k. En particulier, la
suite commence avec D ( 0 ) , qui n’autorise aucun sommet intermédiaire dans ses chemins ; par
conséquent D ( 0 ) n’est pas autre chose que la matrice des poids du digraphe. La dernière
matrice de la suite D ( n ) , contient les longueurs des plus courts chemins parmi tous les
chemins qui peuvent utiliser tous les n sommets comme intermédiaires et par conséquent elle
n’est pas autre chose que la matrice des distances que nous cherchons.

Comme dans l’algorithme de Warshall, nous pouvons calculer tous les éléments de chaque
matrice D ( k ) à partir de son prédécesseur immédiat D ( k 1) dans la suite (13.2). Soit d ij( k ) ,
l’élément de la ième ligne et de la jème colonne de la matrice D ( k ) . Ceci signifie que d ij( k ) est
égal à la longueur du plus court chemins parmi tous les chemins du ième sommet v i au jème
somment v j dans lequel chaque sommet intermédiaire a un numéro inférieur à k :

vi ,une liste de sommets intermédiaires ayant chacun un numéro inférieur à k, v j

(13.3)

Nous pouvons diviser de tels sommets en deux sous-ensembles disjoints : ceux qui n’utilisent
pas le kème sommet v k comme intermédiaire et ceux qui ne le font pas. Comme les
intermédiaires des chemins du premier sous-ensemble ont des numéros inférieurs à k  1 , le
plus court d’entre eux est par définition de nos matrices, de longueur d ij( k 1 ) .

TP Conception et Analyse des Algorithmes Page 8

Quelle est la longueur du plus court chemin dans le deuxième sous-ensemble ? Si le graphe ne
contient pas un cycle de longueur négative, nous pouvons limiter notre attention seulement
aux chemins du deuxième sous-ensemble qui utilise le sommet v k comme leur sommet
intermédiaire exactement une fois (comme la visite de v k plus d’une fois peut seulement
augmenter la longueur du chemin). Tous les chemins de ce genre ont la forme suivante :
v i , sommets de numéros  k – 1, v k , sommets de numéros  k – 1, v j
En d’autres termes, chacun des chemins est constitué d’un chemin de v i à v k dans lequel
chaque sommet intermédiaire a un numéro inférieur à k – 1 et un chemin de. Cette situation
est présentée à la Figure 4.
( k 1 )
d ij
vi vj

( k 1 )
( k 1 )
d kj
d ik

vk

Figure 4 : Idée sous-jacente de l’algorithme de Floyd

Comme la longueur du plus court chemin de de v i à v k parmi les chemins qui utilisent des
sommets intermédiaires ayant un numéro inférieur à k – 1 est égal à d ik( k 1 ) et la longueur du
plus court chemin de v k à v j parmi tous les chemins qui utilisent des sommets intermédiaires
ayant un numéro inférieur à k – 1 est égal à d kj( k 1 ) , la longueur du plus court chemin parmi les
chemins qui utilisent le kème sommet est égale à d ik( k  1)  d kj( k  1) . La prise en compte des
longueurs des plus courts chemins dans les deux sous-ensembles conduit à la récurrence
suivante :
d ij  min d ij , d ik  d kj  pour k  1 , d ik  w ij
(k ) ( k 1 ) ( k 1 ) ( k 1 ) (0)
(13.1)
Pour le dire autrement, l’élément de la ième ligne et jème colonne de la matrice des distances
courante D ( k 1) est remplacé par la somme des éléments de la même ligne i et le kème colonne
et la même colonne j et la kème colonne si et seulement si cette dernière somme est plus petite
que sa valeur courante.
L’application de l’algorithme de Floyd au graphe de la Figure 3 est illustrée à la Figure 5.
a b c d
a 0  3  Les longueurs des plus courts chemins sans sommet
(0)
D(0) = b 2 0   intermédiaire. (D est juste simplement la matrice
des poids).
c  7 0 1
d 6   0

a b c d
a 0  3  Les longueurs des plus courts chemins dont les
sommets intermédiaires ont des numéros inférieur à

(1)
D = b 2 0 5
un, i.e., juste le sommet a (noter deux nouveaux plus
c  7 0 1 courts chemins de d à c et de d à c).
d 6  9 0

TP Conception et Analyse des Algorithmes Page 9

 a b c d
a 0  3  Les longueurs des plus courts chemins dont les
sommets intermédiaires ont des numéros inférieur à
D(2) = b 2 0 5 
deux, i.e., a et b (noter un nouveau plus court chemin
c 9 7 0 1 de c à a).
d 6  9 0

a b c d
a 0 10 3 4 Les longueurs des plus courts chemins dont les
D (3)
= b 2 0 5 6 sommets intermédiaires ont des numéros inférieur à
3, i.e., a, b et c (noter quatre nouveaux plus courts
c 9 7 0 1 chemins de a à b, de a à d, de b à d et de d à b).
d 6 16 9 0

a b c d
a 0 10 3 4 Les longueurs des plus courts chemins dont les
D (4)
= b 2 0 5 6 sommets intermédiaires ont des numéros inférieur à
3, i.e., a, b, c et d (noter un nouveau plus court
c 7 7 0 1 chemin de c à a).
d 6 16 9 0

FIGURE 5 Une application de l’algorithme de Floyd au graphe de la Figure 3. Les

éléments mis à jour sont montrés en gras.

Voici un pseudocode de l’algorithme de Floyd. Il s’appuie sur le fait que la matrice suivante
de la suite (13.2) peut être écrite au-dessus de la précédente.

ALGORITHME Floyd(W[1..n, 1..n])

//Implémente l’algorithme de Floyd pour le all-pairs shortest-paths problem
//Input : La matrice des poids W d’un graphe n’ayant pas un cycle de longueur négative.
//Ouput : La matrice des distances des longueurs des plus courts chemins
DW
for k 1 to n do
for i  1 to n do
for j  1 to n do
D[i, j]  min{D[i, j], D[i, k] + D[k, j]}
return D

Clairement, l’efficacité temporelle de l’algorithme de Floyd est cubique comme l’efficacité

temporelle de l’algorithme de Warshall. Dans le chapitre suivant, nous examinons
l’algorithme de Dijkstra, une autre méthode pour trouver les plus courts chemins.

Nous terminons cette section avec un important commentaire général. Il traite d’un principe
général qui sous-tend les algorithmes de programmation dynamique pour les problèmes
d’optimisation. Richard Bellman l’appelle le principe d’optimalité. En termes quelques peu
différents de sa formulation originale, il dit qu’une solution optimale à une instance d’un
problème d’optimisation est composé de solutions optimales à ses sous-instances. Le principe
d’optimalité tient plus souvent que non. Bien que son applicabilité à un problème particulier

TP Conception et Analyse des Algorithmes Page 10

doit être vérifié, une telle vérification n’est pas habituellement la principale difficulté en
développant un algorithme de programmation dynamique. Le challenge se trouve typiquement
dans la mise en exergue des sous-instances qui doivent être considérées et dériver une
équation reliant la solution d’une instance aux solutions de ses instances plus petites.
Travail à faire : Implémenter l’algorithme de Floyd

Projet 17 : Triangle de Pascal

Ecrire un programme qui construit le triangle de PASCAL de degré N et le mémorise dans
une matrice carrée P de dimension N+1. Une matrice carré est de Pascal si elle est définit par :
 0 si j  i

M ( i , j )  1 si j  1
 M ( i  1, j )  M ( i  1, j  1) sinon

Exemple de matrice de Pascal pour N=9
1 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0
1 2 1 0 0 0 0 0 0 0
1 3 3 1 0 0 0 0 0 0
1 4 6 4 1 0 0 0 0 0
1 5 10 10 5 1 0 0 0 0
1 6 15 20 15 6 1 0 0 0
1 7 21 35 35 21 7 1 0 0
1 8 28 56 70 56 28 8 1 0
1 9 36 84 126 126 84 36 9 1

Travail demandé :
1- Ecrire une fonction qui prend en entrée une matrice et renvoie true ou false selon que la
matrice soit de Pascal ou non.
2- Ecrire une fonction qui prend en entrée une matrice nulle et la transforme en une matrice
de Pascal.

Projet 18 : Décomposition en produit de nombres premiers

Le but de l’exercice est d’écrire un programme qui décompose un entier en produit de
nombres premiers. Par exemple 2904 = 2 3  3 1  11 2 . Si n est un entier naturel non nul et p est
un nombre premier, on note vp(n) le plus grand entier k tel que pk divise n. Si p ne divise pas
n, on pose vp(n) =0. L’entier vp(n) s’appelle la valuation p-adique de n.
Travail demandé :
1- Écrire une fonction booléenne estPremier(n) qui prend en argument un entier naturel
non nul n et renvoie true si n est premier et false sinon. On pourra utiliser le critère
suivant :
 0 et 1 ne sont pas des nombres premiers ;
 2 est un nombre premier ;
2
 tout entier n >2 qui n’est divisible par aucun entier d tel que d ≥ 2 et d ≤ n est
premier.
2- Ecrire une fonction listePremiers(n) qui prend en argument un entier naturel n >2 et
renvoie un tableau des nombres premiers inférieurs ou égaux à n.

TP Conception et Analyse des Algorithmes Page 11

 3- Pour calculer la valuation 2-adique de 40, on peut utiliser la méthode suivante :
 40 est divisible par 2 et le quotient vaut 20
 20 est divisible par 2 et le quotient vaut 10
 10 est divisible par 2 et le quotient vaut 5
 5 n’est pas divisible par 2. La valuation 2-adique de 40 vaut donc 3.
Écrire une fonction valuation_p_adique(n, p) non récursive qui implémente cet
algorithme. Elle prend en arguments un entier naturel n non nul et un nombre premier
p et renvoie la valuation p-adique de n. Par exemple, puisque 40=23×5 :
 valuation_p_adique(40, 2) renvoie 3 ;
 valuation_p_adique(40, 5) renvoie 1 ;
 valuation_p_adique(40, 7) renvoie 0.
4- Écrire une fonction decomposition_facteurs_premiers(n) qui calcule la décomposition
en facteurs premiers d’un entier n≥2. Cette fonction doit renvoyer un tableau de deux
ligne des couples (p, vp(n)) pour tous les nombres premiers p qui divisent n. Par
exemple, decomposition_facteurs_premiers(40) renvoie le tableau Tab suivant.
2 5 Ligne de nombre premier p,
Tab
3 1 Ligne la valuation p-adique vp(n))
5- Écrire une fonction AfficheDecomposition(Tab) qui prend en paramètre un tableau
représentant la décomposition en facteurs premiers d'un entier et renvoie la valeur de
n, tout en affichant sa décomposition sous la forme [(p1, k1), (p2, k2), …, (pn, kn)]. Par
exemple, pour lle tableau suivant
2 3 11
Tab
3 1 2
La fonction AfficheDecomposition(Tab) renvoie 2904 et affiche [(2, 3), (3, 1), (11, 2)].

Projet 19 : Le plus grand diviseur commun de deux entiers positifs

Le plus grand diviseur commun de deux entiers positifs non tous nuls m et n, dénoté
gcd( m , n ) , est défini comme le plus grand entier naturel qui divise à la fois m et n. Il y a
plusieurs algorithmes pour calculer le plus grand diviseur commun.
1. Euclide of Alexandria a proposé un algorithme pour résoudre ce problème dans l’un des
volumes de ses Elements, plus fameux de sa présentation systématique de la géométrie. En
termes modernes, l’Algorithme d’Euclide est basé sur l’application répétitive de la
relation : gcd( m , n )  gcd( n , m mod n ) . (où m mod n est le reste de la division
euclidienne de m par n) jusqu’à ce que m mod n soit égal à zéro. Comme gcd( m , 0 )  m
(pourquoi ?), la dernière valeur de m est aussi le plus grand diviseur commun de m et n.

Algorithme d’Euclide pour calculer GCD(m, n)

Si n = 0, retourner la valeur de m comme réponse et STOP sinon
Etape 1. continuer à l’Etape 2.
Etape 2. Diviser m par n et affecter la valeur du reste à r.
Etape 3. Affecter la valeur de n à m et la valeur de r à n. Aller à l’Etape 1.

2. La deuxième est simplement basée sur la définition du plus grand diviseur commun de m
et n comme le plus grand entier qui divise les deux nombres. Clairement, un tel diviseur

TP Conception et Analyse des Algorithmes Page 12

 commun ne peut pas être plus grand que le plus petit de ces nombres, que nous dénotons
par p = min{m, n}. Ainsi on commence par vérifier si p divise les deux nombres, si oui p
est la réponse, sinon, on décrémente p et on essaie encore.
Algorithme de vérification des entiers consécutifs pour le calcul de GCD(m, n)
Etape 1. Affecter à p la valeur de min{m, n}
Etape 2. Diviser m par p. Si le reste de cette division est zéro, alors aller à
l’Etape 3, sinon aller à l’Etape 4.
Etape 3. Diviser n par p. Si le reste de cette division est zéro, retourner la valeur
de p comme réponse et STOP, sinon continuer à l’Etape 4.
Etape 4. Décrémenter la valeur de p. Aller à l’Etape 2.

3. La troisième procédure pour le calcul du plus grand diviseur commun sera familière aux
élèves des classes intermédiaires.
Procédure des classes intermédiaires pour le calcul de GCD(m, n)
Etape 1. Trouver la décomposition en facteurs premiers de m.
Etape 2. Trouver la décomposition en facteurs premiers de n.
Etape 3. Identifier tous les facteurs communs des décompositions en facteurs
premiers trouvées à l’Etape 1 et à l’Etape 2. Si p est un facteur
commun apparaissant pm fois et pn fois dans m et n, respectivement, il
sera répété min{pm, pn} fois.
Etape 4. Calculer le produit de tous les facteurs communs et retourner ce produit
comme le plus grand diviseur commun des nombres m et n.
Présentons maintenant un algorithme simple pour générer les nombres premiers consécutifs
inférieurs à un entier donné n. L’algorithme commence par initialiser la liste des nombres
premiers candidats par les entiers consécutifs de 2 à n. Ensuite, à la première itération de
l’algorithme, on élimine de la liste tous les multiples de 2. Ensuite on passe au deuxième
élément de la liste qui est 3, et on élimine tous ses multiples. Le prochain nombre restant dans
la liste et qui est utilisé à la troisième itération est 5. Comme pour 2 et 3, tous les multiples de
5 sont supprimés de la liste. L’algorithme continue de cette façon jusqu’à ce qu’aucun nombre
ne puisse plus être supprimé de la liste. Les nombres restant de la liste sont les nombres
premiers recherchés.
Travail demandé :
1- Ecrire une fonction PGCDEuclide() qui reçoit deux positifs non tous nuls n et m en
paramètre et utilise la méthode d’Euclide pour retourner le plus grand diviseur
commun de m et n.
2- Ecrire une fonction PGCDSoustraction() qui reçoit deux positifs non tous nuls n et m
en paramètre et utilise la méthode de vérification des entiers consécutifs pour le
calcul de plus grand diviseur commun de m et n tous non nuls.
3- Ecrire une fonction Eratosthenes() qui recoit n entier positif et renvoie un tableau des
nombres premiers consécutifs inférieurs à un entier donné n.
4- Ecrire une fonction PGCDClasseIntermediaire() qui reçoit deux positifs non tous nuls
n et m en paramètre et utilise la procédure des classes intermédiaires pour le calcul
pour le calcul de plus grand diviseur commun de m et n tous non nuls.

TP Conception et Analyse des Algorithmes Page 13

Projet 20 : Problème de la couverture convexe
Soit P1  ( x1 , y 1 ),  , P  ( x n , y n ) un ensemble de n points du plan. Nous supposons que les
points sont triés dans l’ordre croissant de leur coordonnée en x. Il n’est pas difficile de
montrer le fait géométriquement évident que le point le plus à gauche P1 et le point le plus à
droite Pn sont deux points extrêmes distincts de la couverture convexe (Figure 4.8). Soit P1 Pn
la droite passant par les points P1 et Pn dirigé de P1 à Pn. Cette droite sépare les points de S en
deux ensembles : S1 est l’ensemble des points situés à gauche ou sur cette droite et S2 est
l’ensemble situés à droite ou cette droite. Les points de S situés sur la droite P1 Pn autres que
P1 et Pn ne peuvent pas être des points extrêmes de la couverture convexe et par sont
conséquent exclus des investigations ultérieures.


 
  Pn

P1  
 

Figure 1 : Couvertures supérieure et inférieure de l’ensemble de points

La frontière de la couverture convexe de S est composée de deux polynômes chaînés : une
frontière supérieure et une frontière inférieure. La frontière supérieure, appelée la couverture
supérieure, est une suite de segments de droite ayant des sommets en P1, certains des points
de S1 (si S1 n’est pas vide) et Pn. La frontière inférieure, appelée couverture inférieure, est une
suite de segments de droite ayant des sommets en P1, certains points de S2 (si S2 n’est pas
vise) et Pn.
Le fait que la couverture convexe de l’ensemble entier S est composée par les couvertures
supérieure et inférieure, qui peuvent être construites indépendamment et de façon similaire,
est une observation très utile qui est exploitée par plusieurs algorithmes de ce problème.
Plus concrètement, voyons comment le Quickhull procède pour construire la frontière
supérieure. La frontière inférieure peut être construite de la même manière. Si S1 est vide, la
frontière supérieure est simplement le segment de droite ayant pour extrémités P1 et Pn. Si S1
n’est pas vide, l’algorithme identifie le sommet Pmax dans S1, qui est le plus éloigné de la
droite P1 Pn (Figure 4.9). S’il y a une tie, le point qui maximise l’angle  Pmax P1 Pn peut être
sélectionné. (Noter que le point Pmax maximise la surface du triangle ayant deux sommets en
P1 et Pn et le troisième à un autre point de S1). Ensuite l’algorithme identifie tous les points de
S1 qui se trouvent à gauche de la droite P1 Pn ; ceux-ci sont les points qui, avec P1 et Pmax,
formeront l’ensemble S1.1. Les points de S1 à gauche de la droite P1 Pmax formeront, avec Pmax
et Pn, l’ensemble S1.2. Il n’est pas difficile de montrer que :
 Pmax est un sommet de la couverture supérieure
 les points à l’intérieure de  P1 Pmax Pn ne peuvent pas être des sommets de la couverture
supérieure (et donc sont éliminés des considérations ultérieures) ; et

TP Conception et Analyse des Algorithmes Page 14

  il n’existe aucun point à gauche des droites P1 Pmax et Pmax Pn
Par conséquent, l’algorithme peut continuer la construction de la couverture supérieure de
P1  S 1 ,1  Pmax et Pmax  S 1, 2  Pn récursivement et ensuite les concaténer simplement pour
obtenir la couverture de l’ensemble entier P1  S 1  Pn .

Pmax
 



  

  Pn

P1
Figure 2 : L’idée du Quichhull

Travail à faire :
1. Implémenter l’algorithme du Quickhull.
2. Expliquer comment on peut trouver analytiquement le point Pmax dans l’algorithme du
Quickhull.
3. Quelle est l’efficace au mieux du Quickhull ?
4. Donner un exemple spécifique d’entrées qui permettent à l’algorithme du Quickhull
d’avoir un temps d’exécution quadratique.

Groupe_01 = {1, 20, 3, 18, 5, 17} Groupe_11 = {11, 10, 13, 8, 15, 7}
Groupe_02 = {2, 1, 4, 19, 6, 18} Groupe_12 = {12, 11, 14, 9, 16, 8}
Groupe_03 = {3, 2, 5, 20, 7, 19} Groupe_13 = {13, 12, 15, 10, 17, 9}
Groupe_04 = {4, 3, 6, 1, 8, 20} Groupe_14 = {14, 13, 16, 11, 18, 10}
Groupe_05 = {5, 4, 7, 2, 9, 1} Groupe_15 = {15, 14, 17, 12, 19, 11}
Groupe_06 = {6, 5, 8, 3, 10, 2} Groupe_16 = {16, 15, 18, 13, 20, 12}
Groupe_07 = {7, 6, 9, 4, 11, 3} Groupe_17 = {17, 16, 19, 14, 1, 13}
Groupe_08 = {8, 7, 10, 5, 12, 4} Groupe_18 = {18, 17, 20, 15, 2, 14}
Groupe_09 = {9, 8, 11, 6, 13, 5} Groupe_19 = {19, 18, 1, 16, 3, 15}
Groupe_10 = {10, 9, 12, 7, 14, 6} Groupe_20 = {20, 19, 2, 17, 4, 16}

TP Conception et Analyse des Algorithmes Page 15