Inscrivez vous

Se souvenir de moi

Tutoriels et astuces

Tutoriels informatiques

Soyez à jour !

Entrez votre mail :

 


Suivez Cours PDF sur Twitter

Algorithmique et programmation. Cours avancé



Télécharger le cours

Algorithmique et programmation. Cours avancé


Le but de cette partie est de présenter des exemples d’algorithmes permettant 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.


1 Algorithmes : conception et évaluation
— Algorithmes 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 passes . . . . . . . . . . . . . . . . . . . . 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
— Graphes d’expansion 36
5.1 Graphes d’expansion 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

Envoyé le :
31 May 2013
Taille :
586.72 Kb
Téléchargements :
183
Evaluation :
Total des Votes : 0


Soyez le premier à écrire un commentaire sur ce fichier!
Veuillez vous identifier ou vous enregistrer.


All right reserved copyright © Plan du site