| dbo:abstract
|
- Mark Richard Jerrum (* 1955) ist ein britischer Informatiker. Jerrum wurde 1981 bei Leslie Valiant an der University of Edinburgh promoviert (On the complexity of evaluating multivariate polynomials). Er war Professor in Edinburgh und ist Professor für Reine Mathematik am Queen Mary College der Universität London. Jerrum befasst sich mit Kombinatorik, Komplexitätstheorie und stochastischen Prozessen, insbesondere mit randomisierten Algorithmen und Mischungszeiten von Markow-Ketten in kombinatorischen und geometrischen Problemen. Ende der 1980er Jahre untersuchte er mit seinem Studenten Alistair Sinclair, der bei ihm 1988 in Edinburgh promoviert wurde, Mischungseigenschaften von Markow-Ketten und konstruierte damit Monte Carlo Markow-Ketten-Näherungsalgorithmen für Abzählprobleme wie der von Matchings und damit zusammenhängend der Berechnung der Permanente, einem nach Ergebnissen von Valiant innerhalb der Komplexitätstheorie schwierigen Problem. 1996 erhielten beide dafür den Gödel-Preis. 2006 erhielt er mit Alistair Sinclair und den Fulkerson-Preis für die Angabe eines polynomzeitlichen probabilistischen Näherungs-Algorithmus zur Berechnung der Permanente einer Matrix mit nicht negativen Elementen (A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, Journal of the ACM, Band 51, 2004, S. 671--697). Er untersuchte auch Näherungsalgorithmen für Abzählprobleme aus dem Ising-Modell, innerhalb der Polya´s Theorie von Abzählproblemen (wie denen von chemischen Verbindungen und Färbungen auf Graphen) und für Hamiltonsche Wege in Zufalls-Graphen. (de)
- Mark Richard Jerrum (born 1955) is a British computer scientist and computational theorist. Jerrum received his Ph.D. in computer science 'On the complexity of evaluating multivariate polynomials' in 1981 from University of Edinburgh under the supervision of Leslie Valiant. He is professor of pure mathematics at Queen Mary, University of London. With his student Alistair Sinclair, Jerrum investigated the mixing behaviour of Markov chains to construct approximation algorithms for counting problems such as the computing the permanent, with applications in diverse fields such as matching algorithms, geometric algorithms, mathematical programming, statistics, physics-inspired applications, and dynamical systems. This work has been highly influential in theoretical computer science and was recognised with the Gödel Prize in 1996. A refinement of these methods led to a fully polynomial-time randomised approximation algorithm for computing the permanent, for which Jerrum and his co-authors received the Fulkerson Prize in 2006. (en)
- Mark Richard Jerrum es un informático teórico británico. Recibió su Ph.D. en ciencias de la computación en 1981 en la Universidad de Edimburgo bajo la supervisión de Leslie Valiant. Es profesor de matemáticas puras en . Con su alumno Alistair Sinclair, Jerrum investigó las combinaciones detrás de las cadenas de Markov para construir algoritmos de aproximación para problemas de enumeración, con aplicaciones en diversos campos tales como algoritmos de matching, algoritmos geométricos, programación matemática, estadísticas, aplicaciones inspiradas en la física, y sistemas dinámicos. Este trabajo ha sido muy influyente en el área más teórica de las ciencias de la computación, y fue reconocido con el Premio Gödel en 1996. Jerrum mejoró la eficiencia de estos algoritmos, lo que le significó junto con sus co-autores el recibimiento del Premio Fulkerson en 2006. (es)
- Mark Richard Jerrum est un chercheur en informatique théorique anglais, né en 1955. Il a reçu le prix Gödel en 1996. (fr)
- Mark Richard Jerrum (1955) é um teórico da computação britânico. Jerrum obteve um Ph.D. em ciência da computação em 1981 na Universidade de Edimburgo, orientado por Leslie Valiant, com a tese On the complexity of evaluating multivariate polynomials. É professor de matemática pura na Queen Mary University of London. Com seu aluno investiga o comportamento misto de Cadeias de Markov para construir algoritmos de aproximação para o problema de contagem tal como o , com aplicações em diversas áreas. Este trabalho tem sido altamente influente em ciência da computação teórica e foi reconhecido com o Prêmio Gödel de 1996. Um refinamento destes métodos levou a um algoritmo de aproximação aleatória em tempo completamente polinomial para calcular o permanente, pelo qual Jerrum e seus co-autores receberam o Prêmio Fulkerson de 2006. Foi palestrante convidado do Congresso Internacional de Matemáticos em Zurique (1994: The computational complexity of counting). (pt)
|
