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
-
RABBI HISTOIRE JEWISHGEN ORIGINE MAROC YESHIVOT TOLEDO PANORAMA ISRAEL SEPHARDIC NOMS JEWS INSTITUT SPAIN -MIMOUNA -MUSEE -CA...
-
PRIX NOBEL 1985 CHIMIE PHASAGE FICHE PROJECT CRISTAUX PHOTO MPHPA 1918 Jerome Karle, né le 18 juin 1918 à Brooklyn (New York), dans une fami...
-
SITE AMNH BIO SCIENCES HUMAINES TEXTE INUIT REVUE potlatch Pionnier de l’ethnologie de terrain Boas, Franz, anthropologue, ethnologue, folkl...
-
PATINAGE ASSEMBLEE FLAMME VIDEO JOUBERT Carrière sportive Alain Calmat(1940) est un ancien patineur artistique. Il a été ...
-
SITE RIVERAMURAL F. KAHLO ART ARTCHIVE BIO PORTRAIT VISUAL MUSEUM GALLERY CUBIST VIRTUAL Portrait par Modigliani "Je n'ai jamais cr...
-
WORLD CHAMPION FIDE BIO TOUS LES CHAMPIONS The 14th world champion in the history of chess was born January 18, 1966 in Leningrad. Placed nu...
-
EINSTEIN -PORTRAIT BIOGRAPHIE ARCHIVES -ON LINE E = mc² NORMALE SUP REPORTAGE RELATIVITE PRIX NOBEL 1921 SIONISTE LA BOMBE 1905 -C...
-
GOLEM NEHER KABBALA CYBERNETIQUE AV ETUDE KOUNTRASS PRAGUE CREATURE HISTOIRE ETINCELLES CORPS RODOLPHE II La statue du Maha...
-
MAIMONIDE GHANSEL PRIERE COURS PORTRAIT LIVRES BIOGRAPHIE PEDAGOGIE SCIENCE LOIS 13 ARTICLES CULTURES QUIZ TIMBRES INFLUENCES JOB Moses Maim...
-
W. BENJAMIN PORTRAIT PASSAGE LIVRE TEXTE SITE BIO DOSSIER MODERNITE CITATION "L'image dialectique est une image fulgurante.C'es...
Aucun commentaire:
Enregistrer un commentaire