Embedded Files
Le livre "À la découverte des graphes et des algorithmes de graphes" est publié par EDP-sciences (suivez le lien ici). Livre de vulgarisation (tout en couleurs) sur les graphes et les algorithmes qui les manipulent.
Auteur : Christian Laforest.
Il est disponible en version papier et en version numérique.
Voici le résumé de la 4ème de couverture :
"Un graphe est un objet abstrait très simple, composé d’éléments (les sommets) et de relations entre ces éléments (les arêtes). Un graphe permet de représenter des liens d’amitié entre des gens, des lignes aériennes entre des villes, des câbles entre des ordinateurs, des références entre des pages web, etc. Ce concept est utilisé dans l’industrie (informatique, recherche opérationnelle) mais il intéresse aussi les chercheurs (étude des réseaux sociaux, biologie, mathématiques…).
En s’appuyant sur de multiples exemples et illustrations, ce livre propose une initiation aux graphes et à certaines de leurs propriétés (représentation planaire, cycles eulériens, hamiltoniens…). En évitant tout jargon technique, il décrit des algorithmes classiques (parcours en largeur, en profondeur, Prim, tri topologique, flots…) et d’autres, plus avancés, permettant de traiter les problèmes de coloration, de couverture, d’arbre de Steiner, du voyageur de commerce etc. Cet ouvrage est une invitation à la découverte, sans prérequis, d’un sujet que nul ne devrait ignorer, situé entre les mathématiques discrètes et l’informatique."
Les graphes sont enseignés dans le secondaire et dans de nombreux cursus universitaires. Plusieurs ouvrages traitent de ce sujet passionnant à l'intersection des mathématiques et de l'informatique. Mais ce sont des "manuels techniques'' (parfois en anglais) que le grand public n'ouvre jamais. Or, le cœur des notions et des algorithmes qui les manipulent est parfois assez simple et naturel. Ce qui peut rebuter un lecteur c'est l'aspect formel d'une présentation trop "orientée technique''. Ces présentations sont importantes pour qui veut devenir expert mais ne sont pas indispensables pour les gens simplement curieux, désirant avoir une première approche pour se familiariser avec ces sujets.
Ce livre est conçu pour être lu par toute personne ayant une expérience minimale dans la manipulation de notions abstraites et de raisonnements simples.
* Le jargon informatique est évité (ni structures de données, ni langages de programmation, on s'en tient à la présentation des principes généraux).
* Le lecteur est accompagné pas à pas. De nombreuses illustrations et de nombreux exemples jalonnent chaque chapitre. L'auteur profite de son expérience d'enseignant pour non seulement donner les informations pertinentes mais aussi pour déjouer les pièges les plus courants, pour montrer que telle ou telle interprétation ou solution (que les gens ont en tête spontanément) est fausse, en expliquant pourquoi.
* Les chapitres sont assez courts et sont suffisamment indépendants pour être lus dans un ordre quelconque, au grès des envies et des besoins des lecteurs.
* Des zones colorées marquent des passages plus difficiles, qui peuvent être sautés lors d'une première lecture (zone Orange ou rouge, suivant le niveau de difficulté).
* Ce livre présente des résultats et algorithmes "classiques'' de graphes : parcours de graphes (en largeur, en profondeur, Dijkstra), arbres de poids minimal, graphes planaires, cycles eulérien et hamiltonien, ordre topologique, flot max., affectations stables).
* Il présente aussi quelques algorithmes d'approximation. C'est un sujet qui touche la question fondamentale "P=NP?'', pour aller plus loin et aborder une piste de recherche actuellement très active (couverture de graphes, voyageur de commerce, arbre de Steiner, etc., ainsi qu'une brève présentation des algorithmes dit « en ligne » et des algorithmes aléatoires).
Cet ouvrage s'adresse :
* Aux curieux, désirant aborder simplement un sujet qui prend de l'importance, à la croisée des chemins, entre l'informatique et les mathématiques.
* Aux étudiants et lycéens à qui ce sujet est enseigné et qui veulent avoir un autre regard sur cette matière, qui ont besoin d'une vue moins technique pour bien saisir les principes.
* Aux enseignants qui doivent aborder ce sujet en cours et qui cherchent une initiation avant d'approfondir.
* Aux chercheurs d'autres disciplines ou aux ingénieurs qui veulent découvrir les graphes pour savoir si cela peut leur être utile dans leurs travaux.
Google Sites
Report abuse