Licence d'informatique. Algorithmique et programmation. Cours ...

Description

Licence, Supérieur, Licence (bac+3)

• mémoire
• exposé

Licence d'informatique. Algorithmique et programmation. Cours avancé Jacques Stern Année 2010–2011

• exé- cution de l'algorithme ff
• problème de placement
• structures de données fusionnables
• instance du problème
• algorithme polynomial
• évaluation —
• algorithme
• algorithmes
• programmation linéaire
• tailles
• taille

Sujets

• Mémoire
• Exposé
• Algorithmique
• Problème
• Donnée
• Placement
• Taille
• Linéaire
• Polynomial

Informations

• Publié par: foeh
• Nombre de lectures: 194
• Langue: Français

Extrait

Licence d’informatique.
Algorithmique et programmation.
Cours avancé
Jacques Stern
Année 2010–2011Table des matières
1 Algorithmes : conception et évaluation
— approchés et analyse amortie 3
1.1 Algorithmes approchés . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Analyse amortie . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Tri et hachage
— Tri de Shell 11
2.1 Le tri de Shell . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Tris de Shell à deux passes . . . . . . . . . . . . . . . . . . . . 12
2.3 Tris à plus de deux . . . . . . . . . . . . . . . . . . . . 18
3 Recherche de motifs
— Algorithmes d’alignement en bio-informatique 21
3.1 Extraction et alignements pour deux suites . . . . . . . . . . . 21
3.2 Alignement de plusieurs suites . . . . . . . . . . . . . . . . . . 25
4 Arbres
— Structures de données fusionnables 29
4.1 Arbres binomiaux et tas binomiaux . . . . . . . . . . . . . . . 29
4.2 Tas de Fibonacci . . . . . . . . . . . . . . . . . . . . . . . . . 31
5 Graphes
— d’expansion 36
5.1 Graphes et valeurs propres . . . . . . . . . . . . . 36
5.2 Applications algorithmiques . . . . . . . . . . . . . . . . . . . 38
6 Flots
— Méthode de flot bloquant 42
6.1 Flots bloquants . . . . . . . . . . . . . . . . . . . . . . . . . . 42
6.2 Graphes unitaires et applications . . . . . . . . . . . . . . . . 47
17 Entiers
— Tests de primalité; sommes de quatre carrés 51
7.1 Symboles de Legendre et de Jacobi . . . . . . . . . . . . . . . 51
7.2 Tests de primalité . . . . . . . . . . . . . . . . . . . . . . . . . 56
7.3 Décomposition d’un entier en somme des quatre carrés . . . . 58
8 Transformation de Fourier rapide
— Algorithme de multiplication des entiers 63
8.1 T de Fourier dans un anneau . . . . . . . . . . . 63
8.2 Multiplication rapide des entiers . . . . . . . . . . . . . . . . . 67
9 Algèbre linéaire et géométrie des nombres
— Algorithme LLL de réduction des réseaux 71
9.1 Réseaux à coordonnées entières . . . . . . . . . . . . . . . . . 71
9.2 Algorithme LLL . . . . . . . . . . . . . . . . . . . . . . . . . . 74
10 Programmation linéaire
— Algorithme de Khachyan 80
10.1 Ellipsoïdes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
10.2 L’algorithme de Khachyan . . . . . . . . . . . . . . . . . . . . 81
10.3 Conclusion : algorithme de complexité polynomiale pour la
programmation linéaire . . . . . . . . . . . . . . . . . . . . . . 84
11 Polynômes à une variable
— Algorithme de Berlekamp 87
11.1 L’algorithme de Berlekamp . . . . . . . . . . . . . . . . . . . . 87
11.2 Algorithme de Cantor-Zassenhaus . . . . . . . . . . . . . . . . 90
2Cours 1 (5 octobre)
Algorithmes : conception et
évaluation
— Algorithmes approchés et analyse amortie
1.1 Algorithmes approchés
1.1.1 Présentation
Le but de cette partie est de présenter des exemples d’algorithmes per-
mettant de résoudre de manière approchée un problème d’optimisation dont
le problème de décision associé est connu comme NP-complet. Le problème
choisi est le “bin packing” (en français problème de placement ou empaque-
tage). L’intérêt du problème est double. D’une part, il existe des algorithmes
pratiquesetefficacesavecunegarantie de performance,cequiveutdirequela
solution trouvée par l’algorithme est dans un rapport constant de l’optimum.
D’autre part, il existe des algorithmes (théoriques) donnant à ce rapport une
valeur aussi proche que possible de 1. En d’autres termes, même si le pro-
blème est NP-complet, on peut s’approcher autant qu’on veut de l’optimum
par un algorithme polynomial. Toutefois, le degré du polynôme qui mesure
la complexité augmente avec la précision choisie.
Le problème du “bin packing” s’énonce de la manière suivante : étant
donnés un entier n et un ensemble U = (u ;;u ) de n objets, auxquels1 n
est associée une taille s(u )2 [0; 1], trouver une partition de U en k sous-i
ensemble X de U, k étant choisi minimum et chaque ensemble X de la
partition tel que X
s(u ) 1i
i2X
36
6
En d’autres termes, on place les objets u dans des boîtes de taille 1 et oni
cherche à minimiser le nombre de boîtes nécessaires.
1.1.2 Algorithmes pratiques
L’algorithme le plus simple est “first fit” ou FF : on prend les objets de U
l’un après l’autre et on place chaque objet dans la première boîte possible. En
notantX [‘] l’ensemble des objets placés dans la j-ième boîte après qu’aientj
été traités les objetsu ;u , on choisit donc le plus petit indicej, tel que1 ‘ 1
X
s(u ) +s(u ) 1i ‘
i2X [‘]j
et on ajoute u à X [‘] pour former X [‘ + 1], les autres X [‘], q = j, étant‘ j j q
inchangés.
Lemme 1 Soit I une instance du problème “bin packing” et soit OPT (I)
l’optimum correspondant; on a
FF (I) 2:OPT (I) + 1
PreuveOnnoted’abordque,puisquepourchaqueélémentX delapartitionj
optimale, on a : X
s(u ) 1;i
i2Xj
il vient
nX XX
s(u ) s(u )k =OPT (I):i i
i=1 j i2Xj
Par ailleurs, on ne peut trouver dans la partition obtenue par l’algorithme
0FF deux boîtes X et X 0, j <j , à moitié vides, c’est à dire telles quej j
X
s(u ) 1=2;i
i2Xj
0eneffet,aumomentoùunpremierobjetestplacédansX ,laplacedisponiblej
dansX permet l’ajout de cet objet, contredisant ainsi la règle de placementj
de l’algorithme. En notant j l’indice de l’unique boîte à moitié vide, si elle0
existe, a donc pour j =j :0
X
s(u ) 1=2:i
i2Xj
46
En sommant, il vient :
nX XX FF (I) 1
s(u ) s(u ) (k 1) 1=2 = :i i
2
i=1 j=j i2X0 j
P
n FF (I) 1Finalement, la somme s(u ) est minorée par et majorée, ainsiii=1 2
qu’on l’a vu plus haut, par OPT (I). Il vient
FF (I) 1
OPT (I);
2
et donc
FF (I) 2:OPT (I) + 1:
On peut en fait démontrer par une combinatoire un peu plus fine que
FF (I) 17=10:OPT (I) + 2 (voir [2]). En effectuant, préalablement à l’exé-
cutiondel’algorithmeFF,untrirangeantlesobjetspartailledécroissante,on
améliorelagarantiedeperformancequidevientFFD(I) 11=9:OPT (I)+2.
1.1.3 Un algorithme théorique
Le résultat exposé dans cette section est dû à de la Vega et Lueker [5]. Il
apparaît également dans [4].
Théorème 1 Pour tout ", 0 < " 1=2, il existe un algorithme polynomial
A qui calcule pour toute instance I du problème bin packing une solution"
utilisant un nombre de boîtes majoré par (1 + 2")OPT (I) + 1.
La preuve se fait en plusieurs étapes.
On commence par se restreindre aux instances telles que s(u ) soit tou-i
jours" et ne prenne que K valeurs distinctes, " et K étant fixés. On pose
M =b1="c. Pour tout placement, chaque boîte contient au plus M objets.
En notant t ;;t , les valeurs possibles prises par s, on définit le type1 K
d’une boîte comme la suite n ;;n , chaque n étant le nombre de fois où1 K i
un objet de taille k apparaît dans la boîte. Le nombre de types possibles dei
boîtes est majoré par une constante T qui est le nombre de possibilités de
répartirM objets en K sous ensembles. On peut voir que cette constante
M +K
est le coefficient du binôme , ce que le lecteur est invité à établir
K
à titre d’exercice.
On dit que deux placements sont équivalents, si l’un est obtenu à partir
de l’autre en appliquant à U une permutation qui respecte la taille s(u) des
5objets. A tout placement, on peut associer la fonction définie sur U par le
type de la boîte dans laquelle un objet est placé. Cette fonction est constante
sur chaque classe et elle est injective sur les classes d’équivalence. En effet,
on peut l’inverser à équivalence près en associant à chaque boîte un ensemble
d’objets ayant les tailles et les répétitions de tailles prescrites par le type de
la boîte. Finalement, le nombre de classes est majoré par le nombre de façons
n +T
de répartir n objets en T, et donc par , qui est un polynôme en
T
n. L’optimum peut ainsi être trouvé par recherche exhaustive sur ce nombre
polynomial de classes.
La seconde étape se restreint toujours aux instances telles que s(u ) soiti
" mais abandonne la condition sur le nombre de valeurs distictes. On
commence par trier les objets de U en ordre croissant de taille et on crée
2 2K =d1="e groupes d’objets consécutifs ayant tous Q =bn"c éléments
exactement, sauf le dernier groupe moins nombreux. En arrondissant par
excès chaque valeur des à la taille du plus grand objet de chaque groupe, on
est ramené à une instance J du cas précédent.
Lemme 2 On a OPT (J) (1 +"):OPT (I).
0Preuve du lemme On introduit l’instance J où chaque valeu