Graphes et algorithmes (4e éd.)
Coll. EDF R&D

Auteurs :

Langue : Français
Couverture de l'ouvrage Graphes et algorithmes (4e éd.)

Thèmes de Graphes et algorithmes (4e éd.)

200,00 €

En stock : expédition en 24h !

Ajouter au panierAjouter au panier
Date de parution :
Ouvrage 784 p. · 16x24 cm · Relié
ISBN : 9782743010355 EAN : 9782743010355
Tec & Doc

· PDF : 200,00 € ·
Acheter l'e-book e-book
Les modèles et les algorithmes de graphes se sont imposés aujourd'hui dans de nombreuses disciplines, aussi bien dans les sciences de base (physique, chimie, biologie, sciences humaines, informatique théorique et algorithmique) que dans les sciences de l'ingénieur (automatique, optimisation de systèmes, économie et recherche opérationnelle, analyse de données, ingénierie des grands réseaux de communication de type internet). Cette nouvelle édition est la seule à offrir un panorama aussi complet de ces outils et de leurs plus récents développements.
Graphes et algorithmes rend compte de la puissance de modélisation procurée par les graphes, et de la disponibilité d'une vaste panoplie d'algorithmes opérationnels. Cette nouvelle édition développe les nombreux résultats, souvent fins, conduisant à la réduction de la complexité des algorithmes (flots, chemins, arbres), les nouvelles familles d'algorithmes approchés (ou métaheuristiques) en particulier ceux inspirés de la biologie (algorithmes génétiques, ou ceux imitant le comportement des colonies de fourmis), les algorithmes fondés sur des processus aléatoires (algorithmes itératifs aléatoires ou algorithmes gloutons aléatoires).
Proposant au lecteur environ 230 exercices et plus de 100 problèmes concrets modélisés, cette nouvelle édition s'est enrichie aussi d'une présentation plus aérée et de nombreuses références bibliographiques.
Graphes et algorithmes s'adresse à un large éventail de chercheurs et ingénieurs des laboratoires et bureaux d'études, et de futurs ingénieurs et étudiants en licence et master.
1. Généralités sur les graphes. Définitions et concepts de base. Matrices associées à un graphe. Connexité. Cycles et cocycles - Nombre cyclomatique. Quelques graphes particuliers. Les hypergraphes. Graphes aléatoires et connexité. 2. Le problème du plus court chemin. Définitions et exemples. Les algorithmes. Le problème central de l'ordonnancement. 3. Algèbres de chemins et dioïdes. L'algèbre du plus court chemin. Définitions et propriétés. Quelques exemples. Algorithmes généraux. Algèbres de chemins dans un graphe sans circuit. Un dioïde particulier. Les dioïdes à gauche et à droite. Généralisation des algèbres de chemins. Théorie des dioïdes et applications. 4. Arbres et arborescences. Arbres - Définitions et propriétés. Le problème de l'arbre de poids minimum. Arborescences. 5. Flots et réseaux de transport. Définitions et propriétés. Le problème du flot maximum dans un réseau de transport. Le problème du flot compatible - Théorème de compatibilité. Flots et connexité. Flots à coût minimum. 6. Flots avec multiplicateurs - Multiflots. Flots avec multiplicateurs. Problèmes de multiflots. 7. Couplages et b-couplages. Le problème du couplage maximum. Algorithme de recherche d'un couplage maximum. Couplage de poids maximum. Un algorithme pour le problème du couplage de poids maximum. b-Couplages - b-Couplages maximum et b-couplage de poids maximum. 8. Parcours eulériens et hamiltoniens. Cycles et chaînes eulériens. Le problème du "Postier chinois" (non orienté). Circuits et cycles hamiltoniens. 9. Matroïdes. Définitions et résultats fondamentaux. Dualité. Le problème du sous-ensemble indépendant de poids maximum : l'algorithme glouton. Intersection de matroïdes. Matroïdes avec conditions de parité et généralisations. Polymatroïdes. 10. Les problèmes difficiles de la classe NP. Réductions et relations d'équivalence entre problèmes. Partition et recouvrement d'un hypergraphe. Le problème du couplage d'un hypergraphe. Coloration d'un graphe et d'un hypergraphe. Le problème du sac à dos multidimensionnel. Les problèmes de coûts fixes et les fonctions d'ensemble. Les problèmes d'ordonnancement. Quelques autres problèmes concrets. Problèmes NP-complets et réductions entre problèmes. 11. Les algorithmes d'énumération par séparation, évaluation et propagation de contraintes. Un exemple d'exploration par séparation, évaluation et propagation. Les procédures d'exploration par séparation et évaluation. Deux exemples d'applications. Évaluation par défaut et pénalités. "ALICE". 12. Algorithmes approchés et métaheuristiques. Les algorithmes itératifs de voisinage. Les algorithmes gloutons. Les métaheuristiques inspirés de la biologie. Régularisation des coûts. Optimalité des algorithmes approchés. Annexe 1. Programmation linéaire. Annexe 2. Programmation linéaire en nombres entiers. Annexe 3. Relaxation lagrangienne et résolution du problème dual. Annexe 4. Programmation dynamique. Annexe 5. Les problèmes de ratio minimum. Index. (Exercices et références bibliogra­phiques en fin de chaque chapitre).
• Michel Gondran est président de l’Académie européenne interdisciplinaire des sciences. Il est lauréat du prix Monpetit de l’Académie des sciences pour ses travaux fondamentaux couvrant de nombreux domaines de l’informatique et des mathématiques appliquées.

• Michel Minoux est professeur à l’université Pierre et Marie Curie (Paris VI). Ses travaux, largement diffusés dans la littérature scientifique internationale, concernent les graphes et les méthodes mathématiques de l’optimisation. De nombreux modèles étudiés dans le présent ouvrage, tels que ceux concernant l’optimisation de flux dans les réseaux, témoignent de l’impact direct de ces recherches sur les applications.
Retrouvez tous les ouvrages de la collection EDF R&D.