Algorithmique avancée
A. Mouloudi
Table des matières
Introduction
Chap 1: Complexité algorithmique
Chap 2: Arbre Binaire
Arbre Binaire de Recherche (ABR)
Les Arbres Equilibrés
Les B Arbres
Chap 3 : Graphes
Eléments de la théorie des graphes
Le problème du plus court chemin
Flots dans les réseaux
Master: Génie informatique
2
Table des matières
Chap 4 : Programmation linéaire
Résolution graphique
Méthode du simplexe
Chap 5 : Décidabilité
Machine de Turing
Décidabilité
Classes de complexité
Master: Génie informatique
3
Table des matières
NP-Complétude
o 3-SAT
o Clique
o Couverture par les sommets
o Circuit hamiltonien
o Coloration de graphes
Chap 6 : Algorithmes d’approximation
Vertex cover
Voyageur de commerce (TSP)
Bin Packing
2-Partition
Master: Génie informatique
4
Introduction
L’algorithmique est une science apparue, il y
a très longtemps, bien avant l’idée même
d’ordinateur.
Citons, vers 1800 avant J-C, les babyloniens
de l’époque d’Hammurabi formulant des
règles précises pour la résolution de certains
types d’équations.
5 Master: Génie informatique
Introduction
Plus tard, au 3ème siècle avant J-C, chez les
grecs, fleurissent un grand nombre de procédés de
calcul, dont le célèbre « algorithme d'Euclide ».
En Perse, au 9ème siècle après J-C, on trouve
l’origine du mot « algorithme », qui provient du nom
de Abu Ja'far Mohammed Ibn Mûsâ Al-Khowâ-
rismi.
6 Master: Génie informatique
Introduction
Al-Khowâ-rismi, a écrit un ouvrage
d’arithmétique utilisant les règles de calcul sur
la représentation décimale des nombres, et
montra l’inutilité des tables et abaques. Il eut
une influence capitale pendant plusieurs
siècles.
7 Master: Génie informatique
Introduction
Au fil du temps, la signification du mot s’élargit et
finalement vient à désigner tout procédé de calcul
systématique, voire automatique, mais sans
référence nécessaire à une machine.
Côté informatique du 21ème siècle et en première
approche, on peut dire qu'un algorithme est un
« mode d'emploi pour résoudre un problème ».
8 Master: Génie informatique
Introduction
Un algorithme est un procédé de calcul
automatique composé d’un ensemble fini
d’étapes, chaque étape étant formée d’un
nombre fini d’étapes élémentaires, qui permet
de résoudre le problème en donnant la sortie
requise.
Master: Génie informatique
9
Introduction
Chaque étape élémentaire est :
définie de façon rigoureuse et non ambiguë
effective, c-à-d, pouvant être réalisée par une
machine
De plus, l’algorithme doit toujours terminer après un
nombre fini d’opérations, quelle que soit la donnée
en entrée, et fournir un résultat.
Master: Génie informatique
10
Introduction
Quels sont les types de problème susceptibles
d’être résolus par des algorithmes ?
Les applications concrètes des algorithmes sont
innombrables, entre autres :
– L’Internet permet à des gens éparpillés un peu
partout dans le monde d’accéder rapidement à toutes
sortes de données. Tout cela repose sur des
algorithmes intelligents qui permettent de gérer et
manipuler de grosses masses de données.
Introduction
– Le commerce électronique permet de négocier et
échanger, de manière électronique, biens et services.
Le commerce électronique exige que l’on préserve la
confidentialité de données telles que numéros de
carte de crédit, mots de passe et relevés bancaires.
La cryptographie à clé publique et les signatures
numériques qui font partie des technologies
fondamentales employées dans ce contexte,
s’appuient sur des algorithmes numériques et sur la
théorie des nombres.
Introduction
- Dans l’industrie et le commerce, il faut souvent optimiser
l’allocation de ressources limitées. Une compagnie pétrolière
veut savoir où placer ses puits de façon à maximiser les profits
escomptés. Un candidat à la présidence veut savoir dans
quels supports publicitaires il doit investir pour maximiser ses
chances d’élection. Une compagnie aérienne désire réaliser
l’affectation des équipages aux vols de telle façon que les
coûts soient minimisés, les vols assurés sans défaillance et la
législation respectée. Un fournisseur de services Internet veut
savoir où placer des ressources supplémentaires pour
desservir ses clients de manière plus efficace.
Ces exemples de problèmes peuvent être résolus par la
programmation linéaire, que nous étudierons dans un chapitre.
Introduction
Les algorithmes que nous considérons sont
déterministes : toute exécution de l’algorithme sur
les mêmes données donne le même résultat.
À tout algorithme écrit en langage naturel ou
pseudo-code, on peut associer un programme
implémentant l’algorithme.
Master: Génie informatique
14
Introduction
Ce programme écrit avec des règles syntaxiques
rigoureuses et destiné à être compris par une
machine.
Il se pose alors le problème de trouver le bon degré
de précision nécessaire pour définir l’algorithme: il
doit être suffisant pour permettre d’écrire un
programme lui correspondant et pour calculer sa
complexité.
Master: Génie informatique
15
Introduction
Il est à noter qu’à tout problème ne correspond pas
nécessairement un algorithme permettant de le
résoudre : problème indécidable, tel que le
problème de la diagonalisation de Cantor ou l’arrêt
de la machine de Turing (il est démontré qu’il ne
peut pas exister d’algorithme général , qui pour tout
programme P, et toute donnée D, répondrait oui ou
non à la question « P termine-t-il pour D ? »).
16 Master: Génie informatique
Introduction
On parle aussi de fonction non calculable. En effet,
vers 1930, avant la construction des premiers
ordinateurs, plusieurs mathématiciens (Gödel,
Church, Turing, Post) ont formalisé le concept
d’algorithme, ou de fonction calculable, par
différents modèles abstraits à ressources infinies
(machines de Turing, fonctions récursives, λ-calcul).
17 Master: Génie informatique
Introduction
En conséquence, si un algorithme est
implémentable dans un langage (ou modèle)
donné, en C par exemple, alors il est forcément
implémentable dans un autre et des transcriptions
d’un langage dans un autre sont possibles (thèse
de Church).
Master: Génie informatique
18
Introduction
On peut décrire un algorithme
indépendamment du langage de
programmation (et de la machine sur
laquelle sera exécuté le programme) et si
l’on n’utilise que des pas raisonnables,
l’algorithme est implémentable dans tout
langage.
Master: Génie informatique
19
Introduction
Ce qui nous intéresse, étant donné un problème,
est de trouver le "meilleur " algorithme. Pour cela,
on va comparer des algorithmes qui ont la même
spécification. Ce que l’on veut pouvoir dire :
« Sur toute machine, quel que soit le langage de
programmation, l’algorithme A1 est meilleur que
l’algorithme A2 pour les données de grande taille. »
20 Master: Génie informatique
Introduction
Il faut donc évaluer les ressources nécessaires pour
réaliser l’algorithme : place mémoire et temps
d’exécution. Attention avec les algorithmes récursifs,
il peut y avoir de la place mémoire utilisée pour la
création de la pile.
Il faut trouver un juste compromis entre espace et
temps. On peut parfois gagner du temps mais c’est
au détriment de la place, et réciproquement.
Master: Génie informatique
21
Introduction
Un algorithme peut être préféré à un autre pour sa
clarté et sa lisibilité (produit de 2 matrices), même
s’il est moins performant.
Certains algorithmes ne sont pas performants en
général, mais peuvent l’être pour certaines
configurations de données. Par exemple, si on sait
que les données d’une liste sont presque triées, le
tri par insertion est intéressant.
22 Master: Génie informatique
