Jean Vuillemin is a French computer scientist known for his work in data structures and parallel computing. He is a professor of computer science at the École normale supérieure (Paris). [1]
Vuillemin invented the binomial heap [2] [B] and Cartesian tree data structures. [3] [C] With Ron Rivest, he proved the Aanderaa–Rosenberg conjecture, according to which any deterministic algorithm that tests a nontrivial monotone property of graphs, using queries that test whether pairs of vertices are adjacent, must perform a quadratic number of adjacency queries. [4] [A]
In the 1980s, Vuillemin was the director of a project to develop a workstation using VLSI technology, under which the Le Lisp programming language was developed. [5] With Franco P. Preparata, he also introduced the cube-connected cycles as a network topology in parallel computing. [6] [D]
Vuillemin earned an engineering degree at the École Polytechnique in 1968, a doctorate (troisième cycle) at the University of Paris in 1969, a Ph.D. from Stanford University in 1972 under the supervision of Zohar Manna, and a state doctorate from Paris Diderot University in 1974. [1] [7]
He became an assistant professor at the University of California, Berkeley in 1974, but then returned to France in 1975 for a position at the University of Paris-Sud. He moved to the École Polytechnique in 1982, to the Ecole de Management Léonard De Vinci in 1994, and to the École normale supérieure in 1997. [1]
A. | Rivest, Ronald L.; Vuillemin, Jean (1975), "A generalization and proof of the Aanderaa–Rosenberg conjecture", Proc. 7th ACM Symposium on Theory of Computing, pp. 6–11, CiteSeerX 10.1.1.309.7236 , doi:10.1145/800116.803747 |
B. | Vuillemin, Jean (April 1978), "A data structure for manipulating priority queues", Communications of the ACM , 21 (4): 309–314, CiteSeerX 10.1.1.309.9090 , doi:10.1145/359460.359478 |
C. | Vuillemin, Jean (1980), "A unifying look at data structures", Communications of the ACM , 23 (4): 229–239, doi: 10.1145/358841.358852 |
D. | Preparata, Franco P.; Vuillemin, Jean (1981), "The cube-connected cycles: a versatile network for parallel computation", Communications of the ACM , 24 (5): 300–309, doi:10.1145/358645.358660, hdl: 2142/74219 |
In computer science, a binomial heap is a data structure that acts as a priority queue but also allows pairs of heaps to be merged. It is important as an implementation of the mergeable heap abstract data type, which is a priority queue supporting merge operation. It is implemented as a heap similar to a binary heap but using a special tree structure that is different from the complete binary trees used by binary heaps. Binomial heaps were invented in 1978 by Jean Vuillemin.
École polytechnique, also known as Polytechnique or l'X[liks], is a grande école university located in Palaiseau, France. It specializes in science and engineering and is a founding member of the Polytechnic Institute of Paris.
The École normale supérieure de Lyon is a French grande école located in the city of Lyon. It is one of the four prestigious écoles normales supérieures in France. The school is composed of two academic units— Arts and Sciences— with campuses in Lyon, near the confluence of the Rhône and Saône rivers.
A grande école is a specialised university that is separate from, but parallel and often connected to, the main framework of the French public university system. The grandes écoles offer teaching, research and professional training in single academic fields such as engineering, architecture, business administration, academic research, or public policy and administration. The schools only admit students through an extremely competitive examination process; a significant proportion of their graduates occupy senior positions in French business, academia, civil service and civil society.
An école normale supérieure or ENS is a type of publicly funded higher education institution in France. A portion of the student body, admitted via a highly-selective competitive examination process, are French civil servants and are known as normaliens. ENSes also offers master's degrees, and can be compared to "Institutes for Advanced Studies". They constitute the top level of research-training education in the French university system.
Mines Paris - PSL, officially École nationale supérieure des mines de Paris, is a French grande école and a constituent college of PSL Research University. It was originally established in 1783 by King Louis XVI.
Bernard Chazelle is a French-American computer scientist. He is currently the Eugene Higgins Professor of Computer Science at Princeton University. Much of his work is in computational geometry, where he is known for his study of algorithms, such as linear-time triangulation of a simple polygon, as well as major complexity results, such as lower bound techniques based on discrepancy theory. He is also known for his invention of the soft heap data structure and the most asymptotically efficient known algorithm for finding minimum spanning trees.
The École normale supérieure Paris-Saclay, formerly ENS Cachan, is a grande école and a constituent member of Paris-Saclay University. It was established in 1892. It is located in Gif-sur-Yvette within the Essonne department near Paris, Île-de-France, France.
Joël Scherk was a French theoretical physicist who studied string theory and supergravity.
In computer science, a Cartesian tree is a binary tree derived from a sequence of numbers. The smallest number in the sequence is at the root of the tree; its left and right subtrees are constructed recursively from the subsequences to the left and right of this number. When all numbers are distinct, the Cartesian tree is uniquely defined from the properties that it is heap-ordered and that a symmetric (in-order) traversal of the tree returns the original sequence.
In computer science, a range minimum query (RMQ) solves the problem of finding the minimal value in a sub-array of an array of comparable objects. Range minimum queries have several use cases in computer science, such as the lowest common ancestor problem and the longest common prefix problem (LCP).
In computer science, the all nearest smaller values problem is the following task: for each position in a sequence of numbers, search among the previous positions for the last position that contains a smaller value. This problem can be solved efficiently both by parallel and non-parallel algorithms: Berkman, Schieber & Vishkin (1993), who first identified the procedure as a useful subroutine for other parallel programs, developed efficient algorithms to solve it in the Parallel Random Access Machine model; it may also be solved in linear time on a non-parallel computer using a stack-based algorithm. Later researchers have studied algorithms to solve it in other models of parallel computation.
Maurice Paul Nivat was a French computer scientist. His research in computer science spanned the areas of formal languages, programming language semantics, and discrete geometry. A 2006 citation for an honorary doctorate (Ph.D.) called Nivat one of the fathers of theoretical computer science. He was a professor at the University Paris Diderot until 2001.
Raphael Douady is a French mathematician and economist. He holds the Robert Frey Endowed Chair for Quantitative Finance at Stony Brook, New York. He is a fellow of the Centre d’Economie de la Sorbonne, Paris 1 Pantheon-Sorbonne University, and academic director of the Laboratory of Excellence on Financial Regulation.
Radhia Cousot was a Tunisian French computer scientist known for inventing abstract interpretation.
Grégory Miermont is a French mathematician working on probability, random trees and random maps.
Jean-Michel Bony is a French mathematician, specializing in mathematical analysis. He is known for his work on microlocal analysis and pseudodifferential operators.
Lenka Zdeborová is a Czech physicist and computer scientist who applies methods from statistical physics to machine learning and constraint satisfaction problems. She is a professor of physics and computer science and communication systems at EPFL.
Claude Bouchiat, born 16 May 1932, is a French physicist, member of the French Academy of sciences.
Jean-Yves Chemin is a French mathematician, specializing in nonlinear partial differential equations.