Utilisateur:Claudeh5/racines

Pierre Rosenstiehl en 2002 (photo Hubert de Fraysseix)

Pierre Rosenstiehl, né en 1933, est un mathématicien français, directeur d'études à l'École des Hautes Études en Sciences Sociales de Paris, ancien élève de l'École polytechnique, promotion X1955. Il est également membre de l'Oulipo et Chevalier de la Légion d'honneur.

Son travail se concentre sur la théorie des graphes : Rosenstiehl est connu pour ses recherches sur les graphes planaires et les tracés de graphe. Le critère de planarité de Fraysseix-Rosenstiehl est à l'origine de l'algorithme de planarité gauche-droite, mis en œuvre dans le logiciel Pigale, considéré comme l'algorithme de test de planarité le plus rapide.

Pierre Rosenstiehl est rédacteur en chef de la revue European Journal of CombinatoricsEuropean Journal of Combinatorics sur la combinatoire. Pierre Rosenstiehl, Giuseppe Di Battista, Peter Eades et Roberto Tamassia organisent en 1992 à Marino (Italie) un séminaire consacré au tracé de graphes, qui inaugure une longue série de conférences internationales.

Pierre Rosenstiehl est coopté à l'Oulipo en 1992, pour ses talents en théorie des graphes et sa passion pour les labyrinthes. Il établit notamment pour Jacques Jouet le graphe d'un circuit optimisé du réseau du métro de Paris, afin que ce dernier compose en deux journées un long poème de métro de toutes les stations.

Pierre Rosenstiehl est marié avec l'auteur et illustratrice Agnès Rosenstiehl (créatrice de Mimi-cracra), avec laquelle il a publié Paris-Pékin par le Transsibérien.

Bibliographie sélective, avec mention des maîtres et collaborateurs

Sous la direction de Paul Lévy ; Calcul des probabilités

• P. Rosenstiehl, « Sur l’intégration de certaines fonctions caractéristiques simples ou composées », C.R. Acad. Sciences, p. 2213-2215, 14 avril 1958

(Calcul de l’espérance de l’inverse de $X_{n}$ par l’intégration des fonctions caractéristiques (version finale manuscrite de Paul Lévy).

Sous la direction de John D.C. Little : Processus d’attente avec abandons

• P. Rosenstiehl, Landing of Jet Aircrafts at a Congested Air Terminal; the example of Chicago Airport, Master Thesis in Operation Research at Case Institute, Sept. 1958.
• P. Rosenstiehl, « Processus d’atterrissage. Combinaison d’un traitement analytique et d’une simulation numérique », in P. Rosenstiehl, A. Ghouila Houri (eds.), Décisions séquentielles et simulation, Paris, Dunod, 1958.

(Sur l’introduction des courriers à réaction dans les processus d’atterrissage ; conduit en collaboration avec la Civil Aeronautical Administration d’Indianapolis ; simulation stochastique effectuée au Case Institute sur IBM 650, Runable I for SOAP III (compilateur écrit par Donald Knuth, jeune étudiant au Dept. Info de Case Institute.)

Sous la direction de Georges-Th. Guilbaud : Condorcet et les permutations

• P. Rosenstiehl, « La décision, agrégation et dynamique des ordres de préférence », Colloque International du CNRS, 1967.
• G.Th. Guilbaud, P. Rosenstiehl, « Analyse algébrique d’un scrutin », Mathématiques et Sciences humaines 4, 1963, p. 9-33 ; « Analyse algébrique d’un scrutin », in Ordres totaux finis, Paris, Gauthier-Villars et Mouton, 1971, p. 72-100.

(Preuve que le permutoèdre a une structure de treillis, ouvrant l’accès à la négociation.)

• P. Rosenstiehl, « Préface », in L’à peu près : aspects anciens et modernes de l’approximation, Paris, éditions de l’École des hautes études en sciences sociales, 1988, p. 7-9.

Sous la direction de Marcel-Paul Schützenberger : Automates finis

• P. Rosenstiehl, « Existence d’automates finis capables de s’accorder bien qu’arbitrairement connectés et nombreux », I.C.C. Bulletin, Vol. 5(4), 1966, p. 245-261.
• P. Rosenstiehl, « Réseaux d’automates autorécupérateurs », in La survie des réseaux de télécommunication (The survival of communication networks), actes de la conférence OTAN de recherche opérationnelle, Ile de Bendor (France), 17-21 juin 1968, A.M.J. Mensch (ed.), Imprimerie de la Marine nationale, 1970, p. 381-386.
• P. Rosenstiehl, J.R. Fiksel, A. Holliger, « Intelligent graphs : networks of finite automata capable of solving graph problems », in Graph Theory and Computing, R.C. Read (ed.), New York and London, Academic Press Inc., 1972, p. 219-265.

(Extension, aux réseaux d’automates quelconques, du problème linéaire du Firing Squad de John Myhill.)

Sous la direction du Contrôleur général des Armées Genevey : Transport optimal

• P. Rosenstiehl, « Étude de l’intégration des appels d’offres de l’État en carburant dans la programmation du transport optimal », non publiée, voir Archives du Comité d’Action Scientifique de la Défense nationale, 1964.

(La multiplication des lots, au total excédentaire, a déjoué le cartel des pétroliers et abaissé considérablement les coûts d’achat ; le problème défini par G. Monge a ici recours à un algorithme du transport de type Hitchcock-Koopmans, minimisant globalement coûts d’achat plus coûts de transport.)

Sous la direction de André Lichnerowicz : Corps ${\rm {GF}}_{2}$ et groupes sur les graphes

• P. Rosenstiehl, « Bicycles et diagonales des graphes planaires », Cahiers du Cerco, Vol. 17, fasc. 2-3-4, Bruxelles, 1975, p. 365-383.

(Un nouveau concept : les cycles-cocycles d’un graphe, ou bicycles, dans l’algèbre du corps 2. Définition également de cycle égal à un cocycle à une arête près.)

• P. Rosenstiehl, « Les graphes d’entrelacement d’un graphe », in Colloques internationaux du CNRS : Problèmes combinatoires et théorie des graphes 260, Orsay, 9-13 juillet 1976.

(Une définition algébrique de l’entrelacement dans un graphe quelconque.)

• P. Rosenstiehl, « Caractérisation des graphes planaires par une diagonale algébrique », C.R. Académie des Sciences de Paris, tome 283, série A, 4 octobre 1976, p. 417-419.

(Une nouvelle caractérisation algébrique des graphes planaires s’ajoutant à celles de Whitney.)

• P. Rosenstiehl, « Solution algébrique du problème de Gauss sur la permutation des points d’intersection d’une ou plusieurs courbes fermées du plan », C.R. Académie des Sciences de Paris, tome 283, série A, 11 octobre 1976, p. 551-553.

(Gauss définit en 1845 le problème combinatoire de caractérisation des mots à doubles occurrences de lettres représentables par la suite des points d’intersection d’une courbe plane avec elle-même ; il donne une condition non suffisante en termes de parité sur les lettres. László Lovász et Morris L. Marx produisent dans les mêmes termes de parité (GF2) une deuxième condition nécessaire. Nous établissons ici, toujours dans les mêmes termes, une troisième condition, laquelle constitue avec les deux autres une caractérisation résolvant complètement le problème posé par Gauss.)

Sous la direction de Claude Berge : Théorie des graphes

• P. Rosenstiehl, « L’arbre minimum d’un graphe », in Théorie des graphes. Journées internationales d’études, Rome, Juillet 1966. P. Rosenstiehl (dir. Scientifique de l’ouvrage), Paris, Dunod, New York, Gordon & Breach, 1967, p. 357-368.

(L’arbre minimum d’un graphe selon Kruskal est considéré ici sans métrique pour un ordre total donné des arêtes du graphe ; l’arête minimum d’un cocycle et l’arête maximum d’un cycle, deviennent pivot en algèbre linéaire ; dans le langage des matroïdes binaires, revue est faite des algorithmes connus et des autres possibles, dont quelques inédits.)

• P. Rosenstiehl, « Labyrinthologie mathématiques (I) », Mathématiques et Sciences humaines 33, 1971, p. 5-32.

Collaboration avec Alain Ghouila-Houri : Algorithme de graphes

• P. Rosenstiehl, A. Ghouila-Houri, Les choix économiques, processus séquentiels et simulation, Paris, Dunod, 1960.

(Ouvrage collectif sur les méthodes discrètes d’optimisation dans les systèmes complexes, versus les méthodes de simulation.)

• P. Rosenstiehl, « Les mots du labyrinthe », Colloque sur la théorie des graphes, Bruxelles, 26-27 avril 1973, Cahiers du C.E.R.O., Vol. 15(3), 1973, p. 245-252.

(Les deux types de fil d’Ariane, deux algorithmes pour l’explorateur myope d’un labyrinthe.)

Collaboration avec Jean-Claude Bermond : Circuits Hamiltoniens

• P. Rosenstiehl, J.-Cl. Bermond, « Pancyclisme du carré du graphe aux arêtes d’un graphe », Colloque sur la théorie des graphes, Bruxelles, 26-27 avril 1973, Cahiers du C.E.R.O., vol. 15(3), 1973, p. 285-286.

(Un cas de pancyclisme universel.)

Collaboration avec Robert E. Tarjan : Algorithmes de graphes planaires

• P. Rosenstiehl, R.E. Tarjan, “Gauss codes, planar hamiltonian graphs, and Stack-sortable permutations”, Journal of Algorithms 5, 1984, p. 375-390.
• P. Rosenstiehl, R.E. Tarjan, “Rectilinear planar layouts and bipolar orientations of planar graphs”, Discrete and Computational Geometry 1, New York, Springer Verlag, 1986, p. 343-353.

(Solution algorithmique, linéaire en temps, du problème des électriciens : la représentation d’un graphe par des segments selon deux directions du plan.)

• K. Hoffmann, K. Mehlhorn, P. Rosenstiehl, R.E. Tarjan, “Sorting Jordan sequences in linear time using level-linked search trees”, Information and control, vol. 68, n° 1-3, 1986, p. 170-184.

(Sur une nouvelle structure de données en cône, avec découpage de pièces devenant d’autres cônes.)

• P. Rosenstiehl, R.E. Tarjan, “Embedding in the plane with orientation constraints: the angle graph”, Annals of the new york academy of sciences. Combinatorial mathematics : proceedings of the third international conference, vol. 55, New York, The New York academy of sciences, 1989, p. 340-346.

(Sur la déformation topologique d’un graphe plan.)

Collaboration avec Ronald C. Read : Polynôme de Tutte

• P. Rosenstiehl, R.C. Read, “On the principal edge tripartition of a graph”, Annals of Discrete mathematics 3, North-holland Publishing Company, 1978, p. 195-226.

(Apparition de la dimension de l’espace des bicycles dans le polynome de Tutte.)

Collaboration avec Henry Crapo : Codes de Gauss sur les surfaces

• P. Rosenstiehl, “A new proof of the Gauss interface conjecture”, Advances in Applied Mathematics 23, 1999, p. 3-13.

(Une présentation plus algébrique du théorème des codes de Gauss publiée aux CRASP, 1976.)

• P. Rosenstiehl, H. Crapo, “On lacets and their manifolds”, in Discrete mathematics 233, 2001, p. 299-320.

(Extension de la caractérisation des codes de Gauss à diverses surfaces.)

Collaboration avec Hubert de Fraysseix : Tracés de graphes planaires

• P. Rosenstiehl, H. de Fraysseix, “A depth-first-search characterization of planarity”, Annals of Discrete mathematics 13, North-Holland Publishing Company, 1982, p. 75-80.
• P. Rosenstiehl, H. de Fraysseix, “Système de référence de Trémaux d’une représentation plane d’un graphe planaire”, Annals of Discrete mathematics 17, North-Holland Publishing Company, 1983, p. 293-302.

(Deux articles fondant l’usage du backtracking selon R. Tarjan grâce à l’étude structurelle des arbres de Trémaux ; écriture de l’algorithme Gauche-Droite du test de planarité reputé le plus efficace des algorithmes publiés.)

• H. de Fraysseix, P. Rosenstiehl, “A discriminatory theorem of Kuratowski subgraphs”, M. Borowiecki, J.W. Kennedy and M. Syslo (eds.), Graph Theory, Lagow 1981. Proceedings of the Conference. Lecture notes in Mathematics, vol. 1018, Springer-Verlag, 1983, p. 214-222.

(Hommage à Lagow au célèbre mathématicien polonais Kazimierz Kuratowski après sa disparition.)

• H. de Fraysseix, P. Rosenstiehl, “A characterization of planar graphs by Trémaux orders”, Combinatorica, vol. 5(2), Amsterdam, North-Holland, 1985, p. 127-135.

(Fondation théorique de l’algorithme, linéaire en temps, selon R.E. Tarjan.)

Collaboration avec Bojan Mohar : Tracés de graphes sur le tore

• B. Mohar, P. Rosenstiehl, “Tessellation and visibility representations of maps on the torus”, Discrete and Computational Geometry 19, 1998, p. 249-263.

(Tracé de graphes sur le tore, linéaire en temps.)

Collaboration avec Patrice Ossona de Mendez : Codage des cartes

• P. Ossona de Mendez, P. Rosenstiehl, “Transitivity and connectivity of permutations”, Probability and Computing 14(5-6), 2005, p. 861-872.
• P. Ossona de Mendez, P. Rosenstiehl, “Homomorphism and Dimension”, in Combinatorics, Probability and Computing 14, 2005, p. 861-872.
• P. Ossona de Mendez, P. Rosenstiehl, “Encoding pointed maps by double occurrence words”, Volume of essays in honour of Professor Antonios C. Panayotopoulos, Eptalofos E., 2006, p. 701-712.

(Trois articles sur la dimension d’un ordre partiel résolvant plusieurs conjectures sur les cartes.)

Collaboration avec Patrice Ossona de Mendez et Hubert de Fraysseix : Planarité

• H. de Fraysseix, P. Ossona de Mendez, P. Rosenstiehl, “On triangle contact graphs”, in Combinatorics, Probability and Computing 3, 1994, p. 233-246.
• H. de Fraysseix, P. Ossona de Mendez, P. Rosenstiehl, “Trémaux trees and planarity”, International Journal of Foundations of Computer Science 17(5), 2006, p. 1017-1029.

(Exposé et justifications de l’algorithme Gauche-Droite de l’Atelier de taxiplanie pour le test de planarité, diffusé par le logiciel libre PIGALE.)

Collaboration avec Bertrand Jouve et Michel Imbert : Investigations du cortex visuel

• B. Jouve, P. Rosenstiehl, M. Imbert, “A mathematical approach to the connectivity between the cortical visual areas of the macaque monkey”, Cerebral cortex 8(1), jan-fev. 1998, p. 8-39.

(Traitement d’un échantillon d’images médicales du cortex visuel ; une analyse en composantes principales révèle l’existence probable d’aires visuelles-relais.)

À l’instigation de Roland Barthes

• P. Rosenstiehl, « Les mots du labyrinthe », Cartes et figures de la terre, conférence du 24 février 1979 au séminaire de Roland Barthes, Collège de France, Centre culturel G. Pompidou, 1980, p. 94-103.
• P. Rosenstiehl, « Le dodécadédale ou l’éloge de l’heuristique », Critique 423-424, août-septembre 1982, p. 785-796.
• P. Rosenstiehl, “The dodécadédale or in praise of heuristics”, Order 26, M.I.T. Press, 1983, p. 17-26.

Collaboration avec Paolo Fabbri : Codes publiques

• P. Rosenstiehl, P. Fabbri, « Révélations. Sur les objets cryptiques du temps présent », Le Secret. Traverse 30/31, mars 1984, p. 212-227.

Collaboration avec Jean Petitot : Mathématiques et sciences sociales

• P. Rosenstiehl, J. Petitot, « Automate asocial et systèmes acentrés », Communications 22, 1974, p. 45-62.

Collaboration avec les encyclopédistes : commandes

• P. Rosenstiehl, « Combinatorica », in Enciclopedia, III : Città-Cosmologie, Turin, Einaudi, 1978, p. 437-501.
• P. Rosenstiehl, « Grafo », in Enciclopedia, VI : Famiglia-Ideologie, Turin, Einaudi, 1979, p. 865-896.
• P. Rosenstiehl, « Labirinto », in Enciclopedia, VIII : Labirinto-memoria, Turin, Einaudi, 1979, p. 3-31.
• P. Rosenstiehl, « Rete », enciclopedia XI : Prodotti-Ricchezza, Turin, Einaudi, 1980, p. 1027-1046.
• P. Rosenstiehl, « Labyrinthe », Les notions philosophiques, dictionnaire, tome 1 : Philosophie occidentale, Presses Universitaires de France, 1990, p. 1425-1432.

Collaboration avec les conservateurs de musées : commandes

• P. Rosenstiehl, « Désir, écriture, geste, méandre, monnaie, preuve, réseau », Epreuves d’écriture pour l’exposition Les Immatériaux, Paris, éditions du Centre Georges Pompidou, 1985.

(Exposition : Les Immatériaux, Centre Georges Pompidou, Paris, 28 mars – 15 juillet 1985. Commissaire : J.-F. Lyotard.)

• P. Rosenstiehl, « Geometer Daedalus : List Gegen Tücke », in Daedalus. Die Erfindung der Gegenwart, Verlag Stroemfeld/Roter Stern, 1990, p. 21-31.

(Museum moderner Kunst, Wien. Esposition « daedalus.daedalus-die Erfindung des Gegenwart. Commisaire : G. Fischer.)

• P. Rosenstiehl, « Le labyrinthe mental », in Erre, Variations labyrinthiques, éditions du Centre Pompidou, Metz, 2011.

(Exposition : Erre, Centre Georges Pompidou, Metz, 12 septembre 2011 – 5 mars 2012. Commissaires : H. Guenin, G. Désanges.)

Collaboration avec Agnès Rosenstiehl

• P. Rosenstiehl, A. Rosenstiehl, Paris-Pékin par le transibérien, Paris, Gallimard, 1981 ; Paris, Folio cadet, 1984.

(Récit du voyage d’une mission, sur invitation individuelle du mathématicien Hua Loo Keng, vice-président de l’Académie des sciences de Chine, en novembre 1976.)

Voir aussi

• Algorithme de Rete

Notes, sources et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Pierre Rosenstiehl » (voir la liste des auteurs).

;Catégorie:Mathématicien français ;Catégorie:Personnalité en théorie des graphes ;Catégorie:Oulipien ;Catégorie:Enseignant à l'École des hautes études en sciences sociales ;Catégorie:Chevalier de la Légion d'honneur ;Catégorie:Naissance en 1933