Next PDF List

Licence d"informatique.Algorithmique et programmation.Cours avancéJacques SternAnnée 2010-2011Table des matières1 Algorithmes : conception et évaluation- Algorithmes approchés et analyse amortie31.

1) Algorithmes approchés . . . . . . . . . . . . . . . . . . . . . . 31.

2) Analyse amortie . . . . . . . . . . . . . . . . . . . . . . . . . . 72 Tri et hachage- Tri de Shell112.

1) Le tri de Shell . . . . . . . . . . . . . . . . . . . . . . . . . . . 112. 2) Tris de Shell à deux passes . . . . . . . . . . . . . . . . . . . . 122.

3) Tris à plus de deux passes . . . . . . . . . . . . . . . . . . . . 183 Recherche de motifs- Algorithmes d"alignement en bio-informatique213.

1) Extraction et alignements pour deux suites . . . . . . . . . . . 213.

2) Alignement de plusieurs suites . . . . . . . . . . . . . . . . . . 254 Arbres- Structures de données fusionnables294.

1) Arbres binomiaux et tas binomiaux . . . . . . . . . . . . . . . 294.

2) Tas de Fibonacci . . . . . . . . . . . . . . . . . . . . . . . . . 315 Graphes- Graphes d"expansion365.

1) Graphes d"expansion et valeurs propres . . . . . . . . . . . . . 365.

2) Applications algorithmiques . . . . . . . . . . . . . . . . . . . 386 Flots- Méthode de flot bloquant426.

1) Flots bloquants . . . . . . . . . . . . . . . . . . . . . . . . . . 426.

2) Graphes unitaires et applications . . . . . . . . . . . . . . . . 4717 Entiers- Tests de primalité; sommes de quatre carrés517.

1) Symboles de Legendre et de Jacobi . . . . . . . . . . . . . . . 517. 2) Tests de primalité . . . . . . . . . . . . . . . . . . . . . . . . . 567.

3) Décomposition d"un entier en somme des quatre carrés . . . . 588 Transformation de Fourier rapide- Algorithme de multiplication rapide des entiers638.

1) Transformation de Fourier dans un anneau . . . . . . . . . . . 638.

2) Multiplication rapide des entiers . . . . . . . . . . . . . . . . . 679 Algèbre linéaire et géométrie des nombres- Algorithme LLL de réduction des réseaux719.

1) Réseaux à coordonnées entières . . . . . . . . . . . . . . . . . 719.

2) Algorithme LLL . . . . . . . . . . . . . . . . . . . . . . . . . . 7410 Programmation linéaire- Algorithme de Khachyan8010.

1) Ellipsoïdes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8010. 2) L"algorithme de Khachyan . . . . . . . . . . . . . . . . . . . . 8110.

3) Conclusion : algorithme de complexité polynomiale pour laprogrammation linéaire . . . . . . . . . . . . . . . . . . . . . . 8411 Polynômes à une variable- Algorithme de Berlekamp8711.

1) L"algorithme de Berlekamp . . . . . . . . . . . . . . . . . . . . 8711.

2) Algorithme de Cantor-Zassenhaus . . . . . . . . . . . . . . . . 902Cours 1 (5 octobre)Algorithmes : conception etévaluation- Algorithmes approchés et analyse amortie1.

1) Algorithmes approchés1.1.

1) PrésentationLe 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 dontle problème de décision associé est connu comme NP-complet.

Le problèmechoisi est le "bin packing" (en français problème deplacementouempaque-tage). L"intérêt du problème est double.

D"une part, il existe des algorithmespratiques et efficaces avec unegarantie de performance, ce qui veut dire que lasolution 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 unevaleur 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"optimumpar un algorithme polynomial.

Toutefois, le degré du polynôme qui mesurela complexité augmente avec la précision choisie.Le problème du "bin packing" s"énonce de la manière suivante : étantdonnés un entiernet un ensembleU= (u1;;un)denobjets, auxquelsest associée une tailles(ui)2[0;1], trouver une partition deUenksous-ensembleXdeU,kétant choisi minimum et chaque ensembleXde lapartition tel queXi2Xs(ui)13En d"autres termes, on place les objetsuidans des boîtes de taille 1 et oncherche à minimiser le nombre de boîtes nécessaires.1.1.

2) Algorithmes pratiquesL"algorithme le plus simple est "first fit" ou FF : on prend les objets deUl"un après l"autre et on place chaque objet dans la première boîte possible.

EnnotantXj[`]l"ensemble des objets placés dans laj-ième boîte après qu"aientété traités les objetsu1;u`1, on choisit donc le plus petit indicej, tel queXi2Xj[`]s(ui) +s(u`)1et on ajouteu`àXj[`]pour formerXj[`+ 1], les autresXq[`],q6=j, étantinchangés.Lemme 1SoitIune instance du problème "bin packing" et soitOPT(I)l"optimum correspondant; on aFF(I)2:OPT(I) + 1PreuveOn note d"abord que, puisque pour chaque élémentXjde la partitionoptimale, on a :Xi2Xjs(ui)1;il vientnXi=1s(ui)XjXi2Xjs(ui)k=OPT(I):Par ailleurs, on ne peut trouver dans la partition obtenue par l"algorithmeFF deux boîtesXjetXj0,j < j0, à moitié vides, c"est à dire telles queXi2Xjs(ui)1=2;en effet, au moment où un premier objet est placé dansXj0, la place disponibledansXjpermet l"ajout de cet objet, contredisant ainsi la règle de placementde l"algorithme.

En notantj0l"indice de l"unique boîte à moitié vide, si elleexiste, a donc pourj6=j0:Xi2Xjs(ui)1=2:4En sommant, il vient :nXi=1s(ui)Xj6=j0Xi2Xjs(ui)(k1)1=2 =FF(I)12:Finalement, la sommePni=1s(ui)est minorée parFF(I)12et majorée, ainsiqu"on l"a vu plus haut, parOPT(I).

Il vientFF(I)12OPT(I);et doncFF(I)2:OPT(I) + 1:On peut en fait démontrer par une combinatoire un peu plus fine queFF(I)17=10:OPT(I)+2(voir [2]).

En effectuant, préalablement à l"exé-cution de l"algorithme FF, un tri rangeant les objets par taille décroissante, onaméliore la garantie de performance qui devientFFD(I)11=9:OPT(I)+2.1.1.

3) Un algorithme théoriqueLe résultat exposé dans cette section est dû à de la Vega et Lueker [5].

Ilapparaît également dans [4].Théorème 1Pour tout",0< "1=2, il existe un algorithme polynomialA"qui calcule pour toute instanceIdu problème bin packing une solutionutilisant 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 ques(ui)soit tou-jours"et ne prenne queKvaleurs distinctes,"etKétant fixés.

On poseM=b1="c.

Pour tout placement, chaque boîte contient au plusMobjets.En notantt1;;tK, les valeurs possibles prises pars, on définit le typed"une boîte comme la suiten1;;nK, chaqueniétant le nombre de fois oùun objet de taillekiapparaît dans la boîte.

Le nombre de types possibles deboîtes est majoré par une constanteTqui est le nombre de possibilités derépartirMobjets enKsous ensembles.

On peut voir que cette constanteest le coefficient du binômeM+KK, ce que le lecteur est invité à établirà titre d"exercice.On dit que deux placements sont équivalents, si l"un est obtenu à partirde l"autre en appliquant àUune permutation qui respecte la tailles(u)des5objets.

A tout placement, on peut associer la fonction définie surUpar letype de la boîte dans laquelle un objet est placé.

Cette fonction est constantesur 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 ensembled"objets ayant les tailles et les répétitions de tailles prescrites par le type dela boîte.

Finalement, le nombre de classes est majoré par le nombre de façonsde répartirnobjets enT, et donc parn+TT, qui est un polynôme enn.

L"optimum peut ainsi être trouvé par recherche exhaustive sur ce nombrepolynomial de classes.La seconde étape se restreint toujours aux instances telles ques(ui)soit"mais abandonne la condition sur le nombre de valeurs distictes.

Oncommence par trier les objets deUen ordre croissant de taille et on créeK=d1="2egroupes d"objets consécutifs aya