ROBERT TARJAN
PRIX TURING 1986
PAGE
BIO
DEDALE
GRAPHE
" Pour leur travaux sur la création et l'analyse de structures de données "
avec John Hopcroft
Robert Endre Tarjan (né le 30 avril en 1948 à Pomona en Californie ) est un informaticien américain. Il a découvert de nombreux algorithmes en théorie des graphes . Il a reçu le prix Turing
Il est professeur en informatique à l'université de Princeton
*
Les graphes et leurs algorithmes
La notion de graphe est une structure combinatoire permettant de représenter de nombreuses situations rencontrées dans des applications faisant intervenir des mathématiques discrètes et nécessitant une solution informatique. Circuits électriques, réseaux de transport (ferrés, routiers, aériens), réseaux d'ordinateurs, ordonnancement d'un ensemble de tâches sont les principaux domaines d'application où la structure de graphe intervient. ens uqac ca
On considère généralement que le problème des ponts de Königsberg, résolu par Euler, est le premier résultat formel de la théorie des graphes. Elle s'est surtout développée depuis la deuxième moitié du 19ème siècle (avec Hamilton, Heawood, Kempe, Kirchhoff, Petersen, Tait), et connait un grand boom depuis les années 30 (avec König, Hall, Kuratowski, Whitney, Erdös, Tutte, Edmonds, Berge, Lovász, Seymour, et beaucoup d'autres). Elle présente des liens évidents avec l'algèbre, la topologie, et d'autres domaines de la combinatoire. On trouve des applications de la théorie des graphes -- et souvent aussi la motivation de nouveaux problèmes -- en informatique, recherche opérationnelle, théorie des jeux, théorie de la décision.
La quantité de notions que l'on peut définir sur un graphe est très grande, et plusieurs d'entre elles sont à l'origine de problèmes ou conjectures célèbres (par exemple le problème des quatre couleurs). En fait, un certain nombre de ces notions et questions "théoriques" sont issues non pas de l'imagination des mathématiciens mais de problèmes pratiques qui se modélisent en termes de graphes. De plus, les chercheurs en théorie des graphes s'attachent souvent à trouver des algorithmes efficaces pour résoudre un problème donné.
Les grands problèmes classiques de la théorie des graphes sont : flots et connectivité ("fiabilité" d'un réseau), couplage (affectation), parcours eulérien (qui traverse chaque arête : problème du "postier chinois"), parcours hamiltonien (qui traverse chaque sommet : problème du "voyageur de commerce"), coloration, ensemble stable, ensemble absorbant. Certains de ces problèmes (flot maximum, couplage maximum, parcours eulérien) peuvent être résolus "efficacement", mais la plupart sont très difficiles ("NP-complets").
Une généralisation récente du concept de graphe, introduite par Claude Berge dans les années 60, est celle d'hypergraphe, où les arêtes peuvent être de taille arbitraire et non plus seulement de taille deux leibniz imag
Inscription à :
Publier les commentaires (Atom)
Messages les plus consultés
-
PRIX NOBEL 2001 DISCOURS CHRONIQUE INTERVIEW FORUM OEUVRE CHALLENGE VIDEO SITE "Pour leurs travaux sur les marchés avec asymétrie d'...
-
PRIX NOBEL 2009 SITE WEIZMANN INSTITUTE LAUREATES UNESCO L'OREAL DOSSIER BIO FEMME CRISTALLOGRAPHY Parce qu’Israël le vaut bien ! Scienc...
-
POEME HISTOIRE yiddish Le Chant du peuple juif assassiné Poème d'Isaac Katznelson La peur, l’angoisse, la terreur horrible m’enserrent é...
-
HISTOIRE Parlement de Paris BIO cimetière juif Ouderkerk Médecin juif ex-marrane originaire du Portugal (1567-1616), spécialiste des maladie...
-
AMNESTY INTERNATIONAL BIOGRAPHIE DISPARITION FRANCE ONG RAPPORT SECRET 31 juillet 1921 - 25 février 2005 Biographie du fondateur d’Amnesty I...
-
A. BECK SITE PRINCIPES TEST METHODE DEPRESSION Il a remis en cause le dogme freudien dans les années soixante en développant la thérapie cog...
-
VIDEO HALL OF FAME BIO L'athlète « Bobbie » Rosenfeld excellait dans de nombreux sports. Elle fut nommée meilleure femme athlète du Cana...
-
Langage et redemption Livre de Raziel Une des figures dominantes du judaïsme allemand au Moyen Âge, Éléazar, né à Mayence, étudie dans les...
-
PRIX ABEL 2004 SITE BIO "It's true we pure mathematicians are connected to a different world. But it is a very real world neverthel...
Aucun commentaire:
Enregistrer un commentaire