L'informatique au lycée Chapitre 9

[Link]

Chapitre 9
Algorithmique
On désigne par algorithmique l'ensemble des activités logiques qui relèvent des algorithmes ; en
particulier, en informatique, cette discipline désigne l'ensemble des règles et des techniques qui sont
impliquées dans la définition et la conception des algorithmes.

9.1. Quelques définitions

Le mot « algorithme » vient du nom du mathématicien Al Khwarizmi, qui, au 9ème siècle écrivit
le premier ouvrage systématique sur la solution des équations linéaires et quadratiques. La notion
d'algorithme est donc historiquement liée aux manipulations numériques, mais elle s'est
progressivement développée pour porter sur des objets de plus en plus complexes : des textes, des
images, des formules logiques, des objets physiques, etc.
Un algorithme est un énoncé d'une suite d'opérations permettant de donner la réponse à un
problème.
• Si les opérations s'exécutent sur plusieurs processeurs en parallèle, on parle d'algorithme
parallèle.
• Si les tâches s'exécutent sur un réseau de processeurs on parle d'algorithme distribué.
• Un algorithme qui contient un appel à lui-même est dit récursif.
• Un algorithme glouton est un algorithme qui suit le principe de faire, étape par étape, un
choix optimum local, dans l'espoir d'obtenir un résultat optimum global. Dans les cas où
l'algorithme ne fournit pas systématiquement la solution optimale, il est appelé une
heuristique gloutonne.
• En optimisation combinatoire, théorie des graphes et théorie de la complexité, une
heuristique est un algorithme qui fournit rapidement (en temps polynomial) une solution
réalisable, mais pas nécessairement optimale, pour un problème d'optimisation difficile.
Une heuristique, ou méthode approximative, est donc le contraire d'un algorithme exact qui
trouve une solution optimale pour un problème donné. L'usage d'une heuristique est
pertinente pour calculer une solution approchée d'un problème et ainsi accélérer le
processus de résolution exacte.
• Les métaheuristiques forment une famille d'algorithmes d'optimisation visant à résoudre des
problèmes d'optimisation difficile (souvent issus des domaines de la recherche
opérationnelle, de l'ingénierie ou de l'intelligence artificielle) pour lesquels on ne connaît
pas de méthode classique plus efficace. Ces méthodes utilisent cependant un haut niveau
d'abstraction, leur permettant d'être adaptées à une large gamme de problèmes différents.
Les métaheuristiques les plus connues sont la recherche avec tabous, le recuit simulé, les
algorithmes génétiques et les colonies de fourmis.

Exemple 1 : Algorithme d'Euclide

Donné ci-après sous forme d'organigramme (aussi appelé parfois ordinogramme), l'algorithme
d'Euclide permet de trouver le plus grand diviseur commun de deux nombres (A > B).

Didier Müller 9-1 août 2013

 Algorithmique

Euclide
(325-265 av. J.-C.)

Exercice 9.1
Programmez l'algorithme d'Euclide en Python.

Exemple 2 : Multiplication à la russe

Il existe une méthode pour multiplier deux nombres où il ne faut que
savoir multiplier ou diviser par deux, et additionner. On appelle cette
méthode "multiplication à la russe".
1. Dans la colonne de gauche, on divise par deux en prenant la partie
entière et on s'arrête à 1.
2. Dans la colonne de droite, on double successivement chaque
nombre.
3. On raye à droite tous les chiffres en face d'un nombre pair.
4. On fait la somme des nombres de droite restants.
[Link]
Justification
Remplacer dans la colonne de gauche chaque nombre impair par 1 et chaque nombre pair par 0
revient à exprimer le nombre de gauche en base 2, si on lit de haut en bas. Les opérations effectuées
sur la colonne de droite correspondent alors à une multiplication dans la base 2.
Exercice 9.2
Programmez cet algorithme en Python et estimez le nombre d'opérations moyen pour aboutir au
résultat de la multiplication.

Exemple 3 : Méthode de Héron

En mathématiques, la méthode de Héron ou méthode de Babylone est une méthode efficace
d'extraction de racine carrée. Pour déterminer la racine carrée du nombre a, on choisit un nombre x0
assez proche de √a, en général la partie entière de √a, puis on construit une suite définie par :

a
x n
Héron xn
d'Alexandrie x n1 =
(10-75) 2

La suite ainsi obtenue est une suite décroissante à partir du second terme, convergeant vers √a.
La convergence est quadratique : l'écart entre chaque terme et la limite √a évolue comme le carré
de l'écart précédent, c'est-à-dire que le nombre de décimales exactes double à chaque itération.

Didier Müller 9-2 août 2013

L'informatique au lycée Chapitre 9

Exercice 9.3
Programmez cet algorithme en Python et testez-le.

9.2. Sortir d'un labyrinthe

Vous êtes prisonnier d'un labyrinthe et vous voulez en sortir. Comment faire ? Vous n'avez
Le texte et les
images de ce évidemment aucun plan du labyrinthe. Voici quelques algorithmes, plus ou moins efficaces.
paragraphe
proviennent
de [9]. 9.2.1. La méthode de la souris
L'algorithme de la souris est l'algorithme le plus simple pour se sortir d'un labyrinthe : il consiste
à prendre à chaque intersection un chemin au hasard. Les théorèmes sur les marches aléatoires sont
formels : en procédant de cette façon, vous finirez par sortir du labyrinthe... Cependant, le temps que
vous mettrez pour trouver la sortie sera vraiment très long (proportionnel au moins au carré de la
taille du labyrinthe).

9.2.2. La méthode de la main sur le mur

Cet algorithme consiste à se déplacer en gardant la main contre un des murs, disons le droit.
Ainsi, à chaque intersection, on tournera à droite. En notant les endroits où l'on est passé qu'une seule
fois, on peut en déduire un chemin (pas forcément le plus rapide).

L'algorithme du mur en action : le point rouge est le point de départ, le chemin en orange est le
chemin obtenu en suivant le mur droit. On peut en déduire le chemin le plus rapide, en bleu.

Cette méthode permet de sortir à coup sûr du labyrinthe en un temps raisonnable, mais on prend
le risque de visiter l'ensemble du labyrinthe.
La méthode du mur pose un problème quand le labyrinthe contient des îlots.

L'algorithme du mur en action dans un labyrinthe avec îlots : en suivant toujours le mur (gauche
ou droit), on finit par tourner en rond.

Didier Müller 9-3 août 2013

 Algorithmique

9.2.3. L'algorithme de Pledge

Le principe de base, c'est de longer les murs, mais en évitant de rester coincé sur un même îlot.
Pour ça, il faut trouver le bon moment où lâcher son mur. Dans la pratique, il faut garder un
compteur dans la tête, que l'on initialise à 0 : si le compteur indique 0, on va tout droit jusqu'au mur
en face. À partir de ce mur, on tourne du côté que l'on préfère (mais toujours le même, disons
gauche) et on suit le mur en ajoutant 1 au compteur dès que l'on tourne à droite et en soustrayant 1
dès que l'on tourne à gauche. Si le compteur indique 0, on lâche le mur, et on va tout droit.

L'algorithme de Pledge en action : on part du point rouge (compteur en position 0) et on file tout
droit. On suit alors le mur par la gauche. Dès que l'on tourne à gauche (angle bleu), on
incrémente le compteur), et si on tourne à droite (angle vert foncé) on le décrémente. Si le
compteur atteint à nouveau 0 (angle vert clair), on lâche le mur, et on continue tout droit.

Évidemment, cet algorithme ne marche que dans le cas où le labyrinthe est orthogonal (tous les
angles sont à 90°), mais on peut adapter l'algorithme aux autres labyrinthes. Au lieu d'incrémenter le
compteur de 1 dès que l'on tourne, on l'incrémente par l'angle du virage (avec son signe + ou -).
Cet algorithme présente un problème si la sortie est une trappe située sur un îlot.

L'algorithme de Pledge en action sur un labyrinthe où la sortie (en jaune) se trouve sur un îlot :
au bout d'un moment, on tourne en rond...

9.2.4. La méthode de Trémaux

Marquez à la craie le chemin que vous suivez. Si vous tombez dans un cul-de-sac, faites
simplement demi-tour. Si vous tombez sur une intersection que vous n'aviez encore jamais croisée,
prenez le chemin que vous préférez. Si vous êtes déjà tombé sur cette intersection auparavant, faites
comme si vous étiez tombé sur un cul-de-sac en faisant demi-tour, pour rejoindre la dernière
intersection où vous avez fait un choix.
Si vous revenez à un moment où à un autre sur votre point de départ, c'est que vous avez visité la
totalité du labyrinthe et qu'il n'avait aucune sortie... Par contre, si vous trouvez la sortie, rien ne vous
dit que c'était le chemin le plus court !

Didier Müller 9-4 août 2013

L'informatique au lycée Chapitre 9

L'algorithme de Trémaux en action : au fur et à mesure, on peut marquer certains passages

comme étant des culs-de-sac, ici en gris.

9.3. Le problème des huit dames

Le but du problème des huit dames, est de placer huit dames
d'un jeu d'échecs sur un échiquier de 8×8 cases sans que les
dames ne puissent se menacer mutuellement, conformément aux
règles du jeu d'échecs. Par conséquent, deux dames ne devraient
jamais partager la même rangée, colonne, ou diagonale (voir
dessin ci-contre).
Durant des années, beaucoup de mathématiciens, y compris
Gauss ont travaillé sur ce problème, qui est un cas particulier du
problème généralisé des n-dames, posé en 1850 par Franz
Nauck, et qui est de placer n dames « libres » sur un échiquier
de n×n cases. En 1874, S. Gunther proposa une méthode pour
trouver des solutions en employant des déterminants, et J. W. L.
Glaisher affina cette approche.
Le problème des huit dames a 92 solutions distinctes, ou
seulement 12 solutions si l'on tient compte de transformations
telles que des rotations ou des réflexions (voir dessin ci-après).
Le problème des huit dames est un bon exemple de problème simple mais non évident. Pour cette
raison, il est souvent employé comme support de mise en œuvre de différentes techniques de
programmation, y compris d'approches non traditionnelles de la programmation telles que la
programmation par contraintes, la programmation logique ou les algorithmes génétiques.

Didier Müller 9-5 août 2013

 Algorithmique

9.3.1. Algorithme naïf

L'algorithme naïf de recherche exhaustive teste toutes les manières possibles de placer une dame
par colonne, pour retirer toutes celles pour lesquelles des dames se menacent mutuellement.
Il y a 88 = 16'777'216 placements à explorer.
Exercice 9.4
Programmez l'algorithme naïf pour trouver les 92 solutions au problème des huit dames.
Vous représenterez la position par une liste de nombres de 0 à 7. Ces nombres indiquent la ligne sur
laquelle la dame se trouve pour la colonne correspondante. Par exemple, la 12 ème solution du
graphique ci-dessus sera représentée par la liste : [2,4,1,7,0,6,3,5].

9.3.2. Recherche en profondeur

La recherche en profondeur consiste à trouver les solutions en plaçant les dames de gauche à
droite. Prenons pour simplifier un exemple sur un damier 4x4. Imaginons que toutes les solutions
avec la première dame sur la première ligne ont été trouvées (voir dessin ci-dessous).

On veut maintenant placer la première dame sur la 2ème ligne.

Plaçons la deuxième dame sur la ligne 1. Il y a conflit : STOP. On ne cherche pas plus loin. Idem
pour les lignes 2 et 3. La seule solution possible est la 4ème ligne.
Plaçons maintenant la troisième dame. On peut la mettre sur la première ligne sans conflit.
Plaçons alors la 4ème et dernière dame. La seule ligne possible est la 3ème. On a une solution :
[1,3,0,2].
On remonte alors dans l'arbre : la troisième dame ne peut se placer sur aucune autre ligne.
Remontons encore d'un cran.
On a déjà essayé toutes les lignes pour la deuxième dame.
Remontons encore d'un cran : plaçons la première dame sur la 3ème ligne et recommençons une
recherche en profondeur...
Exercice 9.5
Programmez la recherche en profondeur expliquée ci-dessus. Comptez le nombre de situations
(intermédiaires et finales) analysées.

9.3.3 Méthode heuristique

Un algorithme de « réparation itérative » commence typiquement à partir d'un placement de
toutes les dames sur l'échiquier, par exemple avec une seule dame par ligne et par colonne. Il essaie
ensuite toutes les permutations des colonnes (il n'y a que des conflits diagonaux à tester) pour ne

Didier Müller 9-6 août 2013

L'informatique au lycée Chapitre 9

garder que les configurations sans conflits.

Il y a 8! = 40'320 placements à explorer.
Exercice 9.6
Placez initialement les 8 dames sur la diagonale de l'échiquier, puis échangez deux colonnes
choisies au hasard. Répétez l'opération jusqu'à ce qu'une solution soit trouvée.
Exercice 9.7
Modifiez le programme de l'exercice 9.6 pour trouver les 92 solutions. Le programme ci-dessous
pourra vous aider. N'essayez pas de le comprendre, il fait appel à des notions avancées de Python que
l'on n'a pas vues (Iterators et generators). Contentez-vous de l'intégrer à votre programme.

def all_perms(str):
if len(str)<=1:
yield str
else:
for perm in all_perms(str[1:]):
for i in range(len(perm)+1):
yield perm[:i] + str[0:1] + perm[i:]

for p in all_perms([0,1,2]):
print(p)

Le résultat sera :
[0, 1, 2]
[1, 0, 2]
[1, 2, 0]
[0, 2, 1]
[2, 0, 1]
[2, 1, 0]

9.4. Algorithmes gloutons

Un algorithme glouton (en anglais : greedy) est un algorithme qui suit le principe de faire, étape
par étape, un choix optimum local, dans l'espoir d'obtenir un résultat optimum global. Il n'y a pas de
retour en arrière : à chaque étape de décision dans l'algorithme, le choix qui semble le meilleur à ce
moment est effectué et est définitif. Les algorithmes gloutons servent surtout à résoudre des
problèmes d'optimisation.
Exemple : rendu de monnaie
Dans le problème du rendu de monnaie (donner une somme avec le moins possible de pièces),
l'algorithme consistant à répéter le choix de la pièce de plus grande valeur qui ne dépasse pas la
somme restante est un algorithme glouton.
Suivant le système de pièces, l'algorithme glouton est optimal ou pas. Dans le système de pièces
européen (en centimes : 1, 2, 5, 10, 20, 50, 100, 200), où l'algorithme glouton donne la somme
suivante pour 37 : 20+10+5+2, on peut montrer que l'algorithme glouton donne toujours une solution
optimale.
Dans le système de pièces (1, 3, 4), l'algorithme glouton n'est pas optimal. En effet, il donne pour
6 : 4+1+1, alors que 3+3 est optimal.

Exercice 9.8
Une route comporte n stations-service, numérotées dans l'ordre du parcours, de 0 à n−1. La
première est à une distance d[0] du départ, la deuxième est à une distance d[1] de la première, la
troisième à une distance d[2] de la deuxième, etc. La fin de la route est à une distance d[n] de la
n-ième et dernière station-service.
Un automobiliste prend le départ de la route avec une voiture dont le réservoir d'essence est plein.
Sa voiture est capable de parcourir une distance r avec un plein.

Didier Müller 9-7 août 2013

 Algorithmique

Question 9.8.1
Donnez une condition nécessaire et suffisante pour que l'automobiliste puisse effectuer le
parcours. On la supposera réalisée par la suite.

Question 9.8.2
Prenez 17 stations-service avec les distances d = [23, 40, 12, 44, 21, 9, 67, 32, 51, 30, 11, 55, 24,
64, 32, 57, 12, 80] et r = 100.
L'automobiliste désire faire le plein le moins souvent possible. Écrivez une fonction Python
rapide qui détermine à quelles stations-service il doit s'arrêter.

Exercice 9.9
Un cambrioleur entre par effraction dans une maison. Il n'est capable de porter que K kilos : il lui
faudra donc choisir entre les différents objets de valeur, afin d'amasser le plus gros magot possible.
On supposera dans un premier temps que les objets sont fractionnables (on peut en prendre
n'importe quelle quantité, c'est le cas d'un liquide ou d'une poudre). Il y a n matières différentes,
numérotées de 0 à n−1, la i-ème ayant un prix p[i] par kilo. La quantité disponible de cette matière
est q[i]. On suppose que tous les prix sont différents deux à deux.

Question 9.9.1
Proposez un algorithme qui donne un choix optimal pour le voleur. Ce choix est-il unique ?
Programmez une fonction voleur en Python qui reprenne cet algorithme (vous pourrez supposer
que le tableau p est trié).

Prenez par exemple : p = [43, 40, 37, 33, 28, 25, 20, 17, 14, 13], q = [7, 6, 12, 11, 2, 23, 1, 4, 24,
43], K = 55.

Question 9.9.2
On suppose maintenant que les objets sont non fractionnables (c'est le cas d'un vase ou d'un
téléviseur). Le i-ème objet vaut un prix p[i] et pèse un poids q[i].
Proposez une méthode dérivée de la question 1 (sans la programmer).
Donne-t-elle un choix optimal ?

9.5. Algorithmes de tri

Une des opérations les plus courantes en programmation est
le tri d'objets. Les ordres les plus utilisés sont l'ordre numérique
et l'ordre lexicographique.
Les principales caractéristiques qui permettent de différencier
les algorithmes de tri sont la complexité algorithmique (voir
annexe) et les ressources nécessaires (notamment en terme
d'espace mémoire utilisé) .
On peut montrer que la complexité temporelle en moyenne et dans le pire des cas d'un algorithme
[Link]
basé sur une fonction de comparaison ne peut pas être meilleure que O(n·log(n)). Les tris qui ne
demandent que O(n·log(n)) comparaisons en moyenne sont alors dits optimaux.
Dans les algorithmes ci-dessous, on effectuera des tris par ordre croissant.

9.5.1. Tri par sélection

Le tri par sélection est un des algorithmes de tri les plus triviaux.
On recherche le plus grand élément que l'on va replacer à sa position finale, c'est-à-dire en
dernière position.
Puis on recherche le second plus grand élément que l'on va placer en avant-dernière position, etc.,
jusqu'à ce que le tableau soit entièrement trié.

Didier Müller 9-8 août 2013

L'informatique au lycée Chapitre 9

def swap(l,i,j):
# echange 2 valeurs d'une liste
l[i],l[i] = l[j], l[i]

def tri_selection(l):
for i in range(len(l)-1):
mini=i
for j in range(i+1,len(l)):
if l[j]<l[mini]: mini=j
swap(l,i,mini)

Complexité
• Meilleur des cas : O(n2) quand le tableau est déjà trié.
• Pire cas : O(n2) quand le tableau est trié en ordre inverse.
• En moyenne : O(n2).

9.5.2. Tri à bulles (Bubble sort)

Le tri à bulles est un algorithme de tri qui consiste à faire remonter progressivement les plus
petits éléments d'une liste, comme les bulles d'air remontent à la surface d'un liquide.
L'algorithme parcourt la liste, et compare les couples d'éléments successifs. Lorsque deux
éléments successifs ne sont pas dans l'ordre croissant, ils sont échangés. Après chaque parcours
complet de la liste, l'algorithme recommence l'opération. Lorsqu'aucun échange n'a lieu pendant un
parcours, cela signifie que la liste est triée : l'algorithme peut s'arrêter.
Cet algorithme est souvent enseigné en tant qu'exemple algorithmique. Cependant, il présente
une complexité en O(n2) dans le pire des cas (où n est la longueur de la liste), ce qui le classe parmi
les mauvais algorithmes de tri. Il n'est donc quasiment pas utilisé en pratique.

def swap(l,i,j):
# echange 2 valeurs d'une liste
l[i],l[j] = l[j],l[i]

def tri_a_bulles(l):
for i in range(len(l)):
for j in reversed(range(i,len(l))):
if l[j]<l[j-1]:
swap(l,j-1,j)

Complexité
• Meilleur cas : O(n) quand le tableau est trié.
• Pire des cas : O(n2) quand le tableau est trié en ordre inverse (n−1)·(n−1) = O(n²)

9.5.3. Tri par insertion

Le tri par insertion est le tri le plus efficace sur des listes de petite taille. C'est pourquoi il est
utilisé par d'autres méthodes comme le Quicksort (voir § 9.5.4). Il est d'autant plus rapide que les
données sont déjà triées en partie dans le bon ordre.
Le principe de ce tri est très simple : c'est le tri que toute personne utilise naturellement quand
elle a des dossiers (ou n'importe quoi d'autre) à classer. On prend un dossier et on le met à sa place
parmi les dossiers déjà triés. Puis on recommence avec le dossier suivant.
Pour procéder à un tri par insertion, il suffit de parcourir une liste : on prend les éléments dans
l'ordre. Ensuite, on les compare avec les éléments précédents jusqu'à trouver la place de l'élément
qu'on considère. Il ne reste plus qu'à décaler les éléments du tableau pour insérer l'élément considéré
à sa place dans la partie déjà triée.

def tri_insertion(liste):
j = 1
n = len(liste)
while j != n:
i = j - 1
temp = liste[j]

Didier Müller 9-9 août 2013

 Algorithmique

while i > -1 and liste[i] > temp:

liste[i+1] = liste[i]
i = i - 1
liste[i+1] = temp
j = j + 1

Complexité
• Pire cas : O(n2) quand le tableau est trié en ordre inverse
• Moyenne : O(n2)

9.5.4. Quicksort
Le Quicksort est une méthode de tri inventée par Sir
Charles Antony Richard Hoare en 1961 et fondée sur la
méthode de conception « diviser pour régner ». Il peut
être implémenté sur un tableau ou sur des listes ; son
utilisation la plus répandue concerne tout de même les
tableaux.
Le Quicksort est un tri dont la complexité moyenne
est en O(n·log(n)), mais dont la complexité dans le pire
des cas est un comportement quadratique en O(n2).
Malgré ce désavantage théorique, c'est en pratique un des
tris les plus rapide pour des données réparties
aléatoirement. Les entrées donnant lieu au comportement
quadratique dépendent de l'implémentation de
l'algorithme, mais sont souvent (si l'implémentation est
maladroite) les entrées déjà presque triées. Il sera plus
avantageux alors d'utiliser le tri par insertion.
La méthode consiste à placer un élément du tableau
(appelé pivot) à sa place définitive, en permutant tous les
éléments de telle sorte que tous ceux qui lui sont
inférieurs soient à sa gauche et que tous ceux qui lui sont
supérieurs soient à sa droite. Cette opération s'appelle le
partitionnement.
Pour chacun des sous-tableaux, on définit un nouveau
pivot et on répète l'opération de partitionnement. Ce
processus est répété récursivement, jusqu'à ce que
l'ensemble des éléments soit trié.

def partition(tab, debut, fin):

while debut < fin:
while debut < fin:
if tab[debut] > tab[fin]:
tab[debut], tab[fin] = tab[fin], tab[debut]
break
fin = fin - 1
while debut < fin:
if tab[debut] > tab[fin]:
tab[debut], tab[fin] = tab[fin], tab[debut]
break
debut = debut + 1
return debut

def quicksort(tab, debut=None, fin=None):

if debut is None: debut = 0
if fin is None: fin = len(tab)
if debut < fin:
i = partition(tab, debut, fin-1)
quicksort(tab, debut, i)
quicksort(tab, i+1, fin)

Dans la pratique, pour les partitions avec un faible nombre d'éléments (jusqu'à environ 15

Didier Müller 9-10 août 2013

L'informatique au lycée Chapitre 9

éléments), on a souvent recours à un tri par insertion qui se révèle plus efficace que le Quicksort.
Le problème le plus important est le choix du pivot. Une implémentation du Quicksort qui ne
choisit pas adéquatement le pivot sera très inefficace pour certaines entrées. Par exemple, si le pivot
est toujours le plus petit élément de la liste, Quicksort sera aussi inefficace qu'un tri par sélection,
c'est-à-dire de performance O(n2).
Complexité
• Pire des cas : O(n2) quand le tableau est trié en ordre inverse
• En moyenne et dans le meilleur des cas : O(n·log(n))

9.5.5. Tri par fusion (Mergesort)

Le tri par fusion repose sur le fait que, pour fusionner deux listes/tableaux trié(e)s dont la somme
des longueurs est n, n−1 comparaisons au maximum sont nécessaires. Pour aller aussi vite que le
Quicksort, il a donc besoin d'utiliser O(n) mémoire
supplémentaire, mais il a l'avantage d'être stable
c'est-à-dire de ne pas mélanger ce qui est déjà trié.

L'algorithme peut être décrit récursivement :

1. On découpe en deux parties à peu près

égales les données à trier.
2. On trie les données de chaque partie.
3. On fusionne les deux parties.

La récursivité s'arrête car on finit par arriver à

des listes composées d'un seul élément et le tri est
alors trivial.

On peut aussi utiliser un algorithme itératif :

1. On trie les éléments deux à deux.

2. On fusionne les listes obtenues.
3. On recommence l'opération précédente
jusqu'à ce qu'on ait une seule liste triée.

Complexité
• Moyenne et pire des cas : O(n log(n))

def merge(l1, l2):

liste = []
i = j =0
n1=len(l1)
n2=len(l2)
while True:
if i<n1 and j<n2:
if l1[i]<l2[j]:
[Link](l1[i])
i+=1
else:
[Link](l2[j])
j+=1
elif i>=n1:
[Link](l2[j:])
break
else:
[Link](l1[i:])

Didier Müller 9-11 août 2013

 Algorithmique

break
return liste

def tri_fusion(liste):

def tri_fusion_interne(liste):
if len(liste)<2 :
return liste
return merge(tri_fusion_interne(liste[:len(liste)//2]),
tri_fusion_interne(liste[len(liste)//2:]))

liste[:] = tri_fusion_interne(liste)

9.5.6. Tri par tas (Heapsort)

Cet algorithme permet de trier les éléments d'un tableau en O(n log (n)) dans le pire des cas, où n
est le nombre d'éléments à trier. Les principaux atouts de cette méthode sont la faible consommation
mémoire et l'efficacité optimale.
Principe
L'idée qui sous-tend cet algorithme consiste à voir le tableau comme un arbre binaire. Le premier
élément est la racine, le deuxième et le troisième sont les deux descendants du premier élément, etc.
Ainsi le n-ième élément a pour fils les éléments 2n+1 et 2n+2. Si le tableau n'est pas de taille 2n, les
branches ne se finissent pas tout à fait à la même profondeur.
Dans l'algorithme, on cherche à obtenir un tas, c'est-à-dire un arbre binaire vérifiant les propriétés
suivantes (les deux premières propriétés découlent de la manière dont on considère les éléments du
tableau) :
• la différence maximale de profondeur entre deux feuilles est de 1 (i.e. toutes les feuilles se
trouvent sur la dernière ou sur l'avant-dernière ligne) ;
• les feuilles de profondeur maximale sont « tassées » sur la gauche.
• chaque nœud est de valeur supérieure à celles de ses deux fils, pour un tri ascendant.
Comme expliqué au paragraphe 6.4.2, un tas ou un arbre binaire presque complet peut être stocké
dans un tableau, en posant que les deux descendants de l'élément d'indice n sont les éléments
d'indices 2n+1 et 2n+2 (pour un tableau indicé à partir de 0). En d'autres termes, les nœuds de l'arbre
sont placés dans le tableau ligne par ligne, chaque ligne étant décrite de gauche à droite.
Une fois le tas de départ obtenu, l'opération de base de ce tri est le tamisage d'un élément,
supposé le seul « mal placé » dans un arbre qui est presque un tas. Plus précisément, considérons un
arbre T = T[0] dont les deux sous-arbres (T[1] et T[2]) sont des tas, tandis que la racine est
éventuellement plus petite que ses fils. L'opération de tamisage consiste à échanger la racine avec le
plus grand de ses fils, et ainsi de suite récursivement jusqu'à ce qu'elle soit à sa place.
Pour construire un tas à partir d'un arbre quelconque, on tamise les racines de chaque sous-tas, de
bas en haut (par taille croissante) et de droite à gauche.
Pour trier un tableau à partir de ces opérations, on commence par le transformer en tas. On
échange la racine avec le dernier élément du tableau, et on restreint le tas en ne touchant plus au
dernier élément, c'est-à-dire à l'ancienne racine. On tamise la racine dans le nouveau tas, et on répète
l'opération sur le tas restreint jusqu'à l'avoir vidé et remplacé par un tableau trié.

def faire_tas(tab, debut, n):

# transforme le tableau "tab" en un tas
racine = debut
while racine*2 + 1 < n:
fils = racine*2 + 1
if fils < n-1 and tab[fils] < tab[fils+1]:
fils += 1
if tab[racine] < tab[fils]:
tab[racine], tab[fils] = tab[fils], tab[racine]
racine = fils
else:
return

def heapsort(tab):

Didier Müller 9-12 août 2013

L'informatique au lycée Chapitre 9

n = len(tab)
debut = n//2 - 1
fin = n - 1
while debut >= 0:
faire_tas(tab, debut, n)
debut -= 1
while fin > 0:
tab[fin], tab[0] = tab[0], tab[fin]
faire_tas(tab, 0, fin)
fin -= 1

9.6. Tester si un point est dans un polygone

Dans le plan, étant donné un polygone simple (dont les arêtes ne se coupent pas), comment
déterminer si un point se trouve à l'intérieur ou à l'extérieur de ce polygone ?
Méthode
La méthode la plus utilisée est de tracer une demi-droite de ce point vers l'infini et de compter les
intersections entre cette droite et les segments du polygone.
• Tracer une demi-droite à partir du point vers l'infini.
• Calculer le nombre L d'intersections entre cette demi-droite et les côtés du polygone.
• Un nombre L impair indique que le point est à l'intérieur.
• Il faut bien sûr faire attention aux coins qui tombent juste sur la demi-droite.

Nombre pair d'intersection : Nombre impair d'intersections :

point à l'extérieur point à l'intérieur

9.6.1. Pour savoir si deux segments se coupent

La première chose à faire est de trouver une méthode pour localiser un point P par rapport à une
ligne passant par les points P0 et P1. Le dessin ci-dessous illustre les trois possibilités.
Pour différencier ces trois cas, on peut utiliser les déterminants. En effet, rappelons-nous qu'un
déterminant peut être interprété comme une aire signée.

Ainsi, sur le dessin ci-contre :

dét(P0P1, P0P2) > 0

dét(P0P1, P0P3) < 0
dét(P0P1, P0P4) = 0

où les PiPj désignent des vecteurs-colonnes

et dét un déterminant 2x2.

On dira que :

orientation(P0, P1, P2) = 1

orientation(P0, P1, P3)= −1
orientation(P0, P1, P4)= 0

Didier Müller 9-13 août 2013

 Algorithmique

D'où la condition ci-dessous :

SI orientation(Q0,Q1,P0) ≠ orientation(Q0,Q1,P1)
ET orientation(P0,P1,Q0) ≠ orientation(P0,P1,Q1) ALORS
RETOURNER « les deux segments se coupent »

Exercice 9.10
Écrivez un programme Python qui implémente la méthode vue ci-dessus. Le polygone sera donné
par la liste de ses sommets. Vous trouverez sur le site compagnon une ébauche à compléter.

9.7. Enveloppe convexe

Imaginons une planche avec des clous qui dépassent. Englobons ces points avec un élastique que
l'on relâche. Le polygone obtenu (en bleu ci-dessous) est l'enveloppe convexe (convex hull).

En trois dimensions, l'idée serait la même avec un ballon qui se dégonflerait jusqu'à être en
contact avec tous les points qui sont à la surface de l'enveloppe convexe.

9.7.1. Marche de Jarvis (Gift wrapping algorithm)

La marche de Jarvis est un algorithme qui « enveloppe » un ensemble de points dans un « papier
cadeau » : on accroche ce papier à un point initial p1, puis on le tend, et on tourne autour du nuage de
points Le premier point rencontré par le papier sera p1, puis p2, ... jusqu'à retrouver p0.

Didier Müller 9-14 août 2013

L'informatique au lycée Chapitre 9

On construit donc l'enveloppe convexe segment par segment, en partant du point p0. Il ne doit y
avoir aucun point à gauche du prochain segment pi pi+1. Il n'y a
qu'un point pi+1 qui satisfait cette condition ; il faut le chercher
parmi les points qui ne sont pas encore sur l'enveloppe convexe.
On s'arrête lorsque pi+1 = p0.
Remarquons que les points ne sont pas triés, alors que ce sera
le cas pour le parcours de Graham.
Cet algorithme doit son nom à R. A. Jarvis, qui publia cet
algorithme en 1973.
Complexité
La complexité est en O(nh), où n est le nombre total de
sommets et où h représente le nombre de sommets de
l'enveloppe convexe. On qualifie ce genre d'algorithme de « sensible à la sortie ».
Exercice 9.11
Écrivez un programme Python qui implémente la marche de Jarvis. Vous trouverez sur le site
compagnon une ébauche à compléter.

9.7.2. Parcours de Graham (Graham's scan)

Cet algorithme doit son nom à Ronald Graham, qui a publié l'algorithme original en 1972.
La première étape de cet algorithme consiste à rechercher le point le plus à gauche. S'il y a égalité
entre plusieurs points, l'algorithme choisit parmi eux le point de plus petite ordonnée. Nommons P0
ce point. La complexité en temps de cette étape est en O(n), n étant le nombre de points de
l'ensemble.
Les autres points Pi sont ensuite triés en fonction de la pente du segment P0Pi, de la plus grande
pente à la plus petite. N'importe quel algorithme efficace de tri convient pour cela. À l'issue de cette
étape, on dispose d'un tableau T contenant les points ainsi triés. P0 sera le premier élément de ce
tableau.

L'algorithme considère ensuite successivement les séquences de trois points contigus dans le
tableau T, vus comme deux segments successifs. On regarde ensuite si ces deux segments mis about
à bout constitue un « tournant à gauche » ou un « tournant à droite ».
• Si l'on rencontre un « tournant à droite », l'algorithme passe au point suivant de T.
• Si c'est un « tournant à gauche », cela signifie que l'avant-dernier point considéré (le
deuxième des trois) ne fait pas partie de l'enveloppe convexe, et qu'il doit être enlevé de T.
Cette analyse se répète ensuite, tant que l'ensemble des trois derniers points est un
« tournant à gauche » .

Le processus se terminera quand on retombera sur le point P0. T contiendra alors les points
formant l'enveloppe convexe.

Didier Müller 9-15 août 2013

 Algorithmique

Complexité
Le tri des points peut se faire avec une complexité en temps en O(nlog(n)). La complexité de la
boucle principale peut sembler être en O(n2), parce que l'algorithme revient en arrière à chaque point
pour évaluer si l'un des points précédents est un « tournant à droite ». Mais elle est en fait en O(n),
parce que chaque point n'est considéré qu'une seule fois. Ainsi, chaque point analysé soit termine la
sous-boucle, soit est retiré de T et n'est donc plus jamais considéré. La complexité globale de
l'algorithme est donc en O(nlog(n)), puisque la complexité du tri domine la complexité du calcul
effectif de l'enveloppe convexe.
Exercice 9.12
Écrivez un programme Python qui implémente le parcours de Graham. Vous trouverez sur le site
compagnon une ébauche à compléter.

9.8. Algorithmes probabilistes

Un algorithme probabiliste est un algorithme dont le déroulement fait appel à des données tirées
au hasard. Dans leur ouvrage Algorithmique, conception et analyse, G. Brassard et P. Bratley
classent les algorithmes probabilistes en quatre catégories :
Algorithmes numériques
• Utilisés pour approcher la solution à des problèmes numériques (ex. calcul de pi, intégration
numérique, etc.).
• La précision augmente avec le temps disponible.
• Certains auteurs classent ces algorithmes dans la catégorie Monte Carlo
Algorithmes de Sherwood
• Utilisés lorsqu'un algorithme déterministe fonctionne plus rapidement en moyenne qu'en
pire cas.
• Ces algorithmes peuvent éliminer la différence entre bonnes et mauvaises entrées.
• Exemple : Quicksort
Algorithmes de Las Vegas
• Ces algorithmes peuvent parfois retourner un message disant qu'ils n'ont pas pu trouver la
réponse.
• La probabilité d'un échec peut être rendu arbitrairement petite en répétant l'algorithme
suffisamment souvent.
Algorithmes de Monte Carlo
• Ces algorithmes retournent toujours une réponse mais celle-ci n'est pas toujours juste.
• La probabilité d'obtenir une réponse correcte augmente avec le temps disponible.

Exercice 9.13
Modifiez le programme de l'exercice 9.10 qui teste si un point est à l'intérieur d'un polygone, afin
d'estimer l'aire de ce polygone. Pour ce faire, vous générerez 100'000 points au hasard et calculerez
le pourcentage de points « tombés » à l'intérieur du polygone.

Didier Müller 9-16 août 2013

L'informatique au lycée Chapitre 9

Exercice 9.14
Développez et programmez une méthode basée sur l'estimation de l'aire d'un quart de cercle pour
approcher la valeur de π.

9.8.1. Test de primalité de Miller-Rabin

Le test de Miller-Rabin est un algorithme de Monte Carlo qui peut décider avec un taux d'erreur
très faible si un nombre est premier ou composé. Ce test est en fait un test de non-primalité, c'est-à-
dire que s'il répond qu'un nombre n'est pas premier, alors il est sûr que ce nombre ne l'est pas. Il peut
aussi répondre qu'un nombre est probablement premier. Dans ce cas, si ce nombre n'est pas premier,
la probabilité de ne pas avoir été détecté non premier est infime : on peut imposer par exemple que
cette probabilité soit inférieure à 2-100.

L'algorithme peut être écrit de la façon suivante :

Données : n : une valeur impaire à tester pour sa primalité ;

k : un paramètre qui détermine le nombre de fois
qu'il faut tester la primalité.
Résultat : "composé" si on trouve pour n au moins un Témoin de Miller a,
autrement il est "très probablement premier"

FONCTION miller_rabin(n,k)
écrire n comme 2^r × s + 1
REPETER k fois :
prendre a aléatoirement dans l'intervalle [1, n-1]
SI a^s mod n≠1 et a^(s·2^j) mod n≠-1 pour tout j dans [0, r-1] ALORS
RETOURNER "composé"
RETOURNER "probablement premier"

Plus on teste de valeurs de a (donc plus k est grand), meilleure est la précision du test. Monier
(1980) et Rabin (1980) ont montré qu'un nombre composé passe le test pour au plus 1/4 des valeurs
a. Si l'on fait k fois le test, alors on se trompera environ 1 fois sur 4k.

# Miller-Rabin
# teste si un nombre est premier

import random

def en_binaire(n):
r = []
while n>0:
[Link](n%2)
n = n//2
return r

def test(a, n):

# vrai : n est composé
# faux : n est PROBABLEMENT premier
b = en_binaire(n-1)
d = 1
for i in range(len(b)-1, -1, -1):
x = d
d = (d*d) % n
if d==1 and x!=1 and x!=n-1:
return True # composé
if b[i]==1:
d=(d*a)%n
if d!=1:
return True # composé
return False # premier

def MillerRabin(n, k = 50):

for j in range(1, k+1):
a = [Link](1, n-1)
if (test(a, n)):
return False # composé

Didier Müller 9-17 août 2013

 Algorithmique

return True # premier

print("Nombres probablement premiers : ")

for n in range(1000000001,1000000999,2):
if MillerRabin(n):
print(n)

9.8.2. Le compte est bon (2)

Nous avons vu au § 7.5 un algorithme récursif cherchant les solutions du jeu. Nous allons ici
nous contenter d'une méthode naïve et peu efficace, mais facile à programmer : il s'agira de
rechercher aléatoirement des solutions et de ne garder que celle qui se rapproche le plus du résultat
demandé.

Données : six nombres dans une liste L et le résultat r à approcher.

1. Choisir deux nombres a et b au hasard dans la liste L.

2. Choisir une opération arithmétique (+, -, *, /) au hasard. L'opération doit
être possible (par exemple, on ne peut pas diviser 5 par 9) et utile (il est
inutile par exemple de multiplier un nombre par 1).
3. Poser c := opération(a, b). Mémoriser ce calcul intermédiaire dans une chaîne
de caractères (une string).
4. Éliminer a et b de la liste L.
5. Ajouter c à la liste L.
6. SI c = r ALORS
afficher tous les calculs intermédiaires.
STOP
7. SI il y a plus d'un nombre dans la liste ALORS
aller à 1
SINON afficher la liste des calculs intermédiaires et le résultat obtenu

On répétera cet algorithme des milliers de fois et on n'affichera que la meilleure solution trouvée.
Exercice 9.15
Programmez cet algorithme en Python.

Exercice 9.16
Modifiez le programme du §8.11.2 pour trouver la plus belle grille de Ruzzle grâce à un
algorithme probabiliste. Par « plus belle », on entend celle qui contient le plus de mots français.
Vous utiliserez le dictionnaire du §8.10 qui est disponible sur le site web compagnon :
[Link]
Voici les fréquences des lettres de ce dictionnaire (on a analysé tous les mots de 2 à 16 lettres
sans tiret et sans apostrophe) :

E S A I R N T O L U C M D
14.89% 10.21% 9.71% 9.40% 8.67% 7.34% 6.82% 5.82% 4.01% 3.60% 3.40% 2.54% 2.36%
P G B F H Z V Q Y X J K W
2.35% 1.60% 1.40% 1.36% 1.16% 1.07% 0.96% 0.50% 0.34% 0.25% 0.18% 0.05% 0.01%

9.9. Le problème des n dames pour illustrer les

métaheuristiques
Le problème des n dames est une généralisation de du problème des 8 dames, vu au paragraphe
9.3 : on considère un échiquier nxn au lieu d'un échiquier 8x8. Bien que ce ne soit pas à proprement
parlé un problème d'optimisation, il présente de nombreux avantages :
• il est visuel et facile à comprendre ;

Didier Müller 9-18 août 2013

L'informatique au lycée Chapitre 9

• on peut coder la position des dames très simplement : pour chaque colonne, on note sur
quelle ligne se trouve la dame. La position ci-contre sera :
[2, 4, 6, 8, 3, 1, 7, 5]
• on passe très facilement d'une configuration à une
configuration voisine (qui ne satisfait pas forcément les
contraintes du problème) : il suffit d'échanger deux
colonnes. Une position voisine de celle ci-contre pourrait
être [2, 1, 6, 8, 3, 4, 7, 5].
On peut le traiter comme un problème d'optimisation si l'on
considère qu'il faut minimiser le nombre de conflits (on parlera de
conflit quand deux dames se menacent mutuellement). Il s'agira ici
de placer n dames sur l'échiquier nxn, sans aucun conflit, en partant
d'une solution avec une seule dame par ligne et par colonne (par
exemple toutes les dames sur la diagonale) et en échangeant deux
colonnes. On ne cherchera pas toutes les solutions possibles : une
seule nous suffira. Notons que dans un problème d'optimisation classique, il n'y a en général qu'une
seule meilleure solution. Ici il y en a plusieurs.
Il est à noter qu'il existe un algorithme permettant de trouver une solution quel que soit n
supérieur à 3 (voir exercice 9.17). L'intérêt de l'exercice n'est donc pas de trouver une solution, mais
d'illustrer sur ce problème classique comment se comportent trois des métaheuristiques les plus
connues : la recherche avec tabous, le recuit simulé et un algorithme génétique.
Exercice 9.17
1. soit r = n mod 12
2. écrire les nombres pairs de 2 à n
3. si r = 3 ou r = 9 mettre le 2 à la fin de la liste
4. écrire ensuite les nombres impairs de 1 à n, mais si r=8 permuter les nombres
impairs 2 par 2 (i.e. 3, 1, 7, 5, 11, 9, ...)
5. si r = 2, permuter les places de 1 et 3, puis mettre 5 à la fin de la liste
6. si r = 3 ou r = 9, mettre 1 puis 3 en fin de liste

Programmez cet algorithme en Python. Il donnera une solution au problème des n dames. Ainsi,
pour n=8 on obtient la position [2, 4, 6, 8, 3, 1, 7, 5]. Pour n=15, on aura la solution [4, 6, 8, 10, 12,
14, 2, 5, 7, 9, 11, 13, 15, 1, 3].
Vérifiez la validité de cet algorithme pour n = 4 ... 1000.

9.9.1. Première approche : descente de plus grande pente

À partir d'une position donnée, essayer toutes les permutations de deux colonnes et échanger les
deux colonnes qui permettent de diminuer le plus le nombre de conflits.
Répéter le processus jusqu'à avoir 0 conflit (dans l'idéal) ou un blocage.
Résultats avec la descente de plus grande pente
Nombre de dames (n) 20 40 60 80 100
Temps ou nombre de conflits restants 2 conflits 13 sec. 1 conflit 418 sec. 1308 sec.
Commentaires
• Selon la position initiale et le nombre de dames, il arrive que l'algorithme se bloque dans un
minimum local. C'est arrivé ici avec 20 et 60 dames placées au départ sur la diagonale.
• Avec 100 dames, on passe d'une situation avec 4950 conflits à une configuration sans
conflit en 82 échanges de colonnes.
• Les temps sont seulement indicatifs et dépendent évidemment de l'ordinateur utilisé. Toutes
les expériences ont été faites sur le même ordinateur et dans les mêmes conditions.
Exercice 9.18
Modifiez le programme de l'exercice 9.16 pour trouver la meilleure grille de Ruzzle grâce à une
recherche avec tabous.

Didier Müller 9-19 août 2013

 Algorithmique

9.9.2. Deuxième approche : recherche avec tabous

La méthode taboue est une métaheuristique d'optimisation présentée par Fred Glover en 1986.
On trouve souvent l'appellation « recherche avec tabous » en français.
La méthode taboue consiste, à partir d'une position donnée, à explorer le voisinage et à choisir la
position dans ce voisinage qui minimise la fonction objectif (comme dans la descente de plus grande
pente). Il est essentiel de noter que cette opération peut conduire à dégrader la valeur de la fonction :
c'est le cas lorsque tous les points du voisinage ont une valeur plus élevée. Le risque est qu'à l'étape
suivante, on retombe dans le minimum local auquel on vient d'échapper. C'est pourquoi il faut que
l'heuristique ait de la mémoire : le mécanisme consiste à interdire (d'où le nom de « tabou ») de
revenir sur les dernières positions explorées.
Les positions déjà explorées sont conservées dans une file (voir § 6.2), souvent appelée liste des
tabous, d'une taille donnée. Cette file doit conserver des positions complètes, mais cela ne pose pas
de problèmes avec les n dames. Pour nos expériences, nous avons utilisé une liste de 10 mouvements
tabous.

Résultats avec la méthode taboue

Nombre de dames (n) 20 40 60 80 100
Temps ou nombre de conflits restants 1 sec. 15 sec. 114 sec. 422 sec. 1756 sec.

Commentaires
• Le programme ne se bloque plus dans un minimum local.
• La solution finale est toujours la même et dépend de la position initiale.
• Avec 100 dames, on passe d'une situation avec 4950 conflits à une configuration sans
conflit en 95 échanges de deux colonnes.

Exercice 9.19
Modifiez le programme de l'exercice 9.16 pour trouver la meilleure grille de Ruzzle grâce à une
recherche avec tabous.

Didier Müller 9-20 août 2013

L'informatique au lycée Chapitre 9

9.9.3. Troisième approche : recuit simulé

Le recuit simulé (Simulated Annealing en anglais) est une métaheuristique inspirée d'un
processus utilisé en métallurgie. Ce processus alterne des cycles de refroidissement lent et de
réchauffage (recuit) qui tendent à minimiser l'énergie du matériau. Elle est aujourd'hui utilisée en
optimisation pour trouver les extrema d'une fonction.
Elle a été mise au point par trois chercheurs de la société IBM, S. Kirkpatrick, C.D. Gelatt et
M.P. Vecchi en 1983, et indépendamment par V. Cerny en 1985.

Ce qu'on appelle « modification élémentaire » dans ce schéma consistera simplement à échanger

deux colonnes choisies aléatoirement. L'énergie sera dans notre problème le nombre de conflits.
Le réglage des paramètres est ici plus délicat. En particulier, comment faut-il faire baisser la
température ? Trop vite, on risque de se bloquer dans un minimum local. Trop lentement, le temps de
calcul augmentera, sans garantie de trouver une solution.
La solution retenue a été de faire baisser la température par palier de longueur 10, avec une
température initiale T=100, avec Tk+1=0.6·Tk, k représentant un numéro de palier. C'est très inhabituel,
car on prend généralement un coefficient proche de 1.
Résultats avec le recuit simulé
Nombre de dames (n) 20 40 60 80 100
Temps moyen en cas de succès* 0.3 sec. 1.5 sec 4 sec. 9 sec. 23 sec.
Nombre de succès sur 10 essais 7 10 10 10 10

*Il s'agit d'une moyenne sur 10 essais, puisque le hasard joue ici un rôle important. Les temps des
essais où l'on n'a pas trouvé de solution n'ont pas été pris en compte.
Commentaires
• Étant donné l'usage du hasard, on ne sait pas quelle solution finale sera trouvée. Ce ne sera
pas toujours la même, contrairement à la recherche avec tabous.
• Curieusement, le recuit simulé marche le moins bien quand il y a peu de dames (7 succès
seulement avec 20 dames).
• Il est par contre redoutable en temps de calcul, puisqu'il ne lui faut que 23 secondes pour
trouver une solution avec 100 dames, alors que la méthode taboue en mettait 1756.
Exercice 9.20
Modifiez le programme de l'exercice 9.16 pour trouver la meilleure grille de Ruzzle grâce à un
recuit simulé.

Didier Müller 9-21 août 2013

 Algorithmique

9.9.4. Quatrième approche : algorithme génétique

Les algorithmes génétiques appartiennent à la famille des algorithmes évolutionnistes (un sous-
ensemble des métaheuristiques). Leur but est d'obtenir une solution approchée, en un temps correct,
à un problème d'optimisation, lorsqu'il n'existe pas ou qu'on ne connaît pas de méthode exacte pour
le résoudre en un temps raisonnable. Les algorithmes génétiques utilisent la notion de sélection
naturelle développée au XIXe siècle par le scientifique Darwin et l'appliquent à une population de
solutions potentielles au problème donné. On se rapproche par bonds successifs d'une solution,
comme dans une procédure de séparation et évaluation, à ceci près que ce sont des formules qui sont
recherchées et non plus directement des valeurs.
L'utilisation d'algorithmes génétiques, dans la résolution de problèmes, est à l'origine le fruit des
recherches de John Holland et de ses collègues et élèves de l'Université du Michigan qui ont, dès
1960, travaillé sur ce sujet. La nouveauté introduite par ce groupe de chercheurs a été la prise en
compte de l'opérateur d'enjambement en complément des mutations. Et c'est cet opérateur qui permet
le plus souvent de se rapprocher de l'optimum d'une fonction en combinant les gènes contenus dans
les différents individus de la population. Le premier aboutissement de ces recherches a été la
publication en 1975 de Adaptation in Natural and Artificial System.

• Les positions « enfants » sont générées en combinant deux positions « parents ».

• L'algorithme commence avec un ensemble de k configurations générées aléatoirement
appelé population. (a)
• Chaque position est représentée pas une liste de n nombres indiquant la ligne occupée pour
la colonne correspondante. Avec 8 dames, la configuration ci-dessous est représentée par la
liste [0, 5, 1, 4, 6, 3, 7, 2].

• Chaque configuration est évaluée grâce à la fonction de performance. (b)

• Une phase de reproduction détermine quelles positions seront sélectionnées pour la
reproduction. Certaines positions peuvent être reproduites plusieurs fois, d'autres jamais. (c)
• Pour chaque paire se combinant, on détermine aléatoirement le point de croisement. (c)
• Les enfants sont créés en permutant les points de croisement dans chaque paire. (d)
• Finalement, chaque configuration subit une mutation aléatoire. (e)

Didier Müller 9-22 août 2013

L'informatique au lycée Chapitre 9

Croisement de positions
[2, 1, 6, 4, 1, 3, 0, 0] + [1, 3, 6, 3, 7, 4, 4, 1] = [2, 1, 6, 3, 7, 4, 4, 1]

Commentaire
• Cette approche n'a pour l'instant pas donné de résultats intéressants. Elle ne fonctionne
qu'avec de petits damiers. Il semble difficile de choisir les différents paramètres.

Exercice 9.21
Modifiez le programme de l'exercice 9.16 pour trouver la meilleure grille de Ruzzle grâce à un
algorithme génétique.

Sources
[1] Wikipédia, « Algorithmique », <[Link]
[2] Wikipédia, « Algorithmes de tri »,
<[Link]
[3] Wikipédia, « Marche de Jarvis », <[Link]
[4] Wikipédia, « Parcours de Graham », <[Link]
[5] Wikipédia, « Test de primalité de Miller-Rabin »,
<[Link]
[6] Wikipédia, « Méta-heuristique », <[Link]
[7] Wikipédia, « Recuit simulé », <[Link]
[8] Wikipédia, « Algorithme génétique », <[Link]
[9] Le labyrinthe dont vous êtes le héros,
<[Link]

Didier Müller 9-23 août 2013