Algorithmes d'approximation / Vijay V. Vazirani

Public ISBD Titre : Algorithmes d'approximation Type de document : texte imprimé Auteurs : Vijay V. Vazirani, Auteur ; Nicolas Schabanel, Traducteur Editeur : Paris : Springer Année de publication : 2006 Collection : Collection IRIS (Paris. 2000), ISSN 1623-071X Importance : 1 vol. (XX-427 p.) Présentation : ill., couv. ill. en coul. Format : 24 cm ISBN/ISSN/EAN : 978-2-287-00677-7 Note générale : Bibliogr. p. 399-415. Index Langues : Français (fre) Langues originales : Anglais (eng) Catégories : Informatique Mathématique Mots-clés : Approximation, Théorie de l' Algorithmes d'approximation Optimisation mathématique : Problèmes et exercices Algorithmes : Problèmes et exercices Programmation linéaire Index. décimale : 519.7 Programmation mathématique Résumé : Le champ des algorithmes d'approximation est aujourd'hui l'un des domaines de recherche les plus actifs en informatique. Il allie la profondeur de la théorie mathématique aux promesses d'applications pratiques d'un intérêt considérable. La plupart des problèmes issus d'applications relevant de domaines aussi différents que la conception de circuits VLSI, la conception et la planification de réseaux, l'ordonnancement, la théorie des jeux, la biologie ou la théorie des nombres, sont des problèmes NP-difficiles. Leur résolution exacte demanderait des ressources informatiques inaccessibles et ne peut donc être envisagée. Pour faire face à cette situation, un grand nombre d'algorithmes proposant des solutions approchées à ces problèmes ont été développés. Une quantité considérable de résultats nouveaux a été établie lors de la dernière décennie et a révolutionné ce champ d'étude. Le défi relevé par cet ouvrage est de présenter clairement les théories et méthodologies sous-jacentes sans rien ôter à la beauté des résultats. Ce livre expose ces questions algorithmiques complexes en proposant des démonstrations simples et intuitives accompagnées de nombreux exemples. Note de contenu : Couverture par ensembles L'arbre de Steiner et le voyageur de commerce Coupe multiséparatrice et coupe en k morceaux k-Centre Coupe-cycles de sommets Surfacteur minimum Sac à dos Empaquetage Minimisation du temps d'exécution total Voyageur de commerce euclidien Introduction à la dualité en programmation linéaire Alignement dual pour la couverture par ensembles Arrondi en programmation linéaire et couverture par Ensembles Schéma primal-dual et couverture par ensembles Satisfaction maximum Ordonnancement hétérogène Multicoupe et multiflot entier dans un arbre Coupe multiséparatrice Multicoupe dans les graphes Coupe la moins dense Forêt de Steiner Réseau de Steiner Placement d'installations k-Médiane Programmation semi-définie Vecteur le plus court Problèmes de dénombrement Difficulté de l'approximation Problèmes ouverts Annexes Bibliographie Index des problèmes Index Glossaire des mots anglais Algorithmes d'approximation [texte imprimé] / Vijay V. Vazirani, Auteur ; Nicolas Schabanel, Traducteur . - Paris : Springer, 2006 . - 1 vol. (XX-427 p.) : ill., couv. ill. en coul. ; 24 cm. - (Collection IRIS (Paris. 2000), ISSN 1623-071X) . ISBN : 978-2-287-00677-7 Bibliogr. p. 399-415. Index Langues : Français (fre) Langues originales : Anglais (eng) Catégories : Informatique Mathématique Mots-clés : Approximation, Théorie de l' Algorithmes d'approximation Optimisation mathématique : Problèmes et exercices Algorithmes : Problèmes et exercices Programmation linéaire Index. décimale : 519.7 Programmation mathématique Résumé : Le champ des algorithmes d'approximation est aujourd'hui l'un des domaines de recherche les plus actifs en informatique. Il allie la profondeur de la théorie mathématique aux promesses d'applications pratiques d'un intérêt considérable. La plupart des problèmes issus d'applications relevant de domaines aussi différents que la conception de circuits VLSI, la conception et la planification de réseaux, l'ordonnancement, la théorie des jeux, la biologie ou la théorie des nombres, sont des problèmes NP-difficiles. Leur résolution exacte demanderait des ressources informatiques inaccessibles et ne peut donc être envisagée. Pour faire face à cette situation, un grand nombre d'algorithmes proposant des solutions approchées à ces problèmes ont été développés. Une quantité considérable de résultats nouveaux a été établie lors de la dernière décennie et a révolutionné ce champ d'étude. Le défi relevé par cet ouvrage est de présenter clairement les théories et méthodologies sous-jacentes sans rien ôter à la beauté des résultats. Ce livre expose ces questions algorithmiques complexes en proposant des démonstrations simples et intuitives accompagnées de nombreux exemples. Note de contenu : Couverture par ensembles L'arbre de Steiner et le voyageur de commerce Coupe multiséparatrice et coupe en k morceaux k-Centre Coupe-cycles de sommets Surfacteur minimum Sac à dos Empaquetage Minimisation du temps d'exécution total Voyageur de commerce euclidien Introduction à la dualité en programmation linéaire Alignement dual pour la couverture par ensembles Arrondi en programmation linéaire et couverture par Ensembles Schéma primal-dual et couverture par ensembles Satisfaction maximum Ordonnancement hétérogène Multicoupe et multiflot entier dans un arbre Coupe multiséparatrice Multicoupe dans les graphes Coupe la moins dense Forêt de Steiner Réseau de Steiner Placement d'installations k-Médiane Programmation semi-définie Vecteur le plus court Problèmes de dénombrement Difficulté de l'approximation Problèmes ouverts Annexes Bibliographie Index des problèmes Index Glossaire des mots anglais

Exemplaires (9)

Code-barres	Cote	Support	Localisation	Section	Disponibilité
Fs/2192	Fs/2192-2200	Livre	Bibliothéque des sciences	Français	Disponible Disponible
Fs/2193	Fs/2192-2200	Livre	Bibliothéque des sciences	Français	Disponible Disponible
Fs/2194	Fs/2192-2200	Livre	Bibliothéque des sciences	Français	Disponible Disponible
Fs/2195	Fs/2192-2200	Livre	Bibliothéque des sciences	Français	Disponible Disponible
Fs/2196	Fs/2192-2200	Livre	Bibliothéque des sciences	Français	Disponible Disponible
Fs/2197	Fs/2192-2200	Livre	Bibliothéque des sciences	Français	Disponible Disponible
Fs/2198	Fs/2192-2200	Livre	Bibliothéque des sciences	Français	Disponible Disponible
Fs/2199	Fs/2192-2200	Livre	Bibliothéque des sciences	Français	Disponible Disponible
Fs/2200	Fs/2192-2200	Livre	Bibliothéque des sciences	Français	Disponible Disponible

---

1 (1 - 1 / 1)