[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/wiki10\/2020\/12\/25\/jack-edmonds-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/wiki10\/2020\/12\/25\/jack-edmonds-wikipedia\/","headline":"Jack Edmonds – Wikipedia","name":"Jack Edmonds – Wikipedia","description":"Amerikanischer \/ kanadischer Mathematiker und Informatiker Jack R. Edmonds (* 5. April 1934 in London) ist ein in Amerika geborener","datePublished":"2020-12-25","dateModified":"2020-12-25","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/wiki10\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/wiki10\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":100,"height":100},"url":"https:\/\/wiki.edu.vn\/wiki10\/2020\/12\/25\/jack-edmonds-wikipedia\/","wordCount":3168,"articleBody":"Amerikanischer \/ kanadischer Mathematiker und Informatiker  Jack R. Edmonds (* 5. April 1934 in London) ist ein in Amerika geborener und ausgebildeter Informatiker und Mathematiker, der einen Gro\u00dfteil seines Lebens in Kanada gelebt und gearbeitet hat.  Er hat grundlegende Beitr\u00e4ge zu den Bereichen kombinatorische Optimierung, polyedrische Kombinatorik, diskrete Mathematik und Computertheorie geleistet.  Er erhielt 1985 den John-von-Neumann-Theoriepreis.Table of ContentsFr\u00fche Karriere[edit]Forschung[edit]Auszeichnungen und Ehrungen[edit]Pers\u00f6nliches Leben[edit]Siehe auch[edit]Verweise[edit]Externe Links[edit]Fr\u00fche Karriere[edit]Edmonds besuchte die Duke University, bevor er 1957 sein Grundstudium an der George Washington University abschloss. Danach absolvierte er ein Studium an der University of Maryland mit einer Arbeit \u00fcber das Problem der Einbettung von Graphen in Oberfl\u00e4chen.  Von 1959 bis 1969 arbeitete er am Nationalen Institut f\u00fcr Standards und Technologie (damals National Bureau of Standards) und war 1961 Gr\u00fcndungsmitglied der neu geschaffenen Operations Research Section von Alan Goldman. Goldman erwies sich als entscheidender Einflussfaktor, indem er Edmonds dies erm\u00f6glichte Arbeit in einem von der RAND Corporation gesponserten Workshop in Santa Monica, Kalifornien.  Hier pr\u00e4sentierte Edmonds erstmals seine Erkenntnisse zur Definition einer Klasse von Algorithmen, die effizienter ausgef\u00fchrt werden k\u00f6nnten.  Die meisten Kombinatoriker konzentrierten sich in dieser Zeit nicht auf Algorithmen.  Edmonds war jedoch von ihnen angezogen und diese ersten Untersuchungen waren Schl\u00fcsselentwicklungen f\u00fcr seine sp\u00e4tere Arbeit zwischen Matroiden und Optimierung.  Er verbrachte die Jahre von 1961 bis 1965 mit dem Thema NP gegen P und brachte 1966 die Vermutungen NP \u2260 P und NP \u2229 coNP = P hervor.  Forschung[edit]Edmonds 1965er Artikel \u201ePaths, Trees and Flowers\u201c war ein herausragender Artikel, in dem zun\u00e4chst die M\u00f6glichkeit vorgeschlagen wurde, eine mathematische Theorie effizienter kombinatorischer Algorithmen aufzustellen.  Einer seiner fr\u00fchesten und bemerkenswertesten Beitr\u00e4ge ist der 1961 entdeckte Bl\u00fctenalgorithmus zur Konstruktion maximaler \u00dcbereinstimmungen auf Graphen[1]  und 1965 ver\u00f6ffentlicht.[2]  Dies war der erste Polynom-Zeit-Algorithmus f\u00fcr die maximale \u00dcbereinstimmung in Graphen.  Seine Verallgemeinerung auf gewichtete Graphen[3]  war ein konzeptioneller Durchbruch bei der Verwendung linearer Programmierideen bei der kombinatorischen Optimierung.  Es besiegelte die Wichtigkeit von Beweisen oder “Zeugen”, dass die Antwort f\u00fcr eine Instanz Ja ist und es Beweise oder “Zeugen” gibt, dass die Antwort f\u00fcr eine Instanz Nein ist.  In diesem Artikel \u00fcber Bl\u00fctenalgorithmen charakterisiert Edmonds auch m\u00f6gliche Probleme als solche, die in Polynomzeit l\u00f6sbar sind.  Dies ist einer der Urspr\u00fcnge der Cobham-Edmonds-These.[4]Ein Durchbruch der Cobham-Edmonds-These war die Definition des Konzepts der Polynomzeit, das den Unterschied zwischen einem praktischen und einem unpraktischen Algorithmus charakterisiert (in modernen Begriffen ein nachvollziehbares Problem oder ein unl\u00f6sbares Problem).  In der Polynomzeit l\u00f6sbare Probleme werden heute als Komplexit\u00e4tsklasse bezeichnet PTIME, oder einfach P..Edmonds Artikel \u201eMaximale \u00dcbereinstimmung und ein Polyeder mit 0-1 Eckpunkten\u201c sowie seine fr\u00fcheren Arbeiten lieferten erstaunliche Polynom-Zeit-Algorithmen f\u00fcr die Konstruktion maximaler \u00dcbereinstimmungen.  Insbesondere haben diese Arbeiten gezeigt, wie eine gute Charakterisierung des mit einem kombinatorischen Optimierungsproblem verbundenen Polyeders \u00fcber die Dualit\u00e4tstheorie der linearen Programmierung zur Konstruktion eines effizienten Algorithmus zur L\u00f6sung dieses Problems f\u00fchren kann.Weitere wegweisende Arbeiten von Edmonds liegen im Bereich der Matroiden.  Er fand eine polyedrische Beschreibung f\u00fcr alle \u00fcberspannenden B\u00e4ume eines Graphen und allgemeiner f\u00fcr alle unabh\u00e4ngigen S\u00e4tze einer Matroid.[5]  Darauf aufbauend bewies er als neuartige Anwendung der linearen Programmierung auf die diskrete Mathematik den Matroid-Schnittpunktsatz, einen sehr allgemeinen kombinatorischen Min-Max-Satz[6][7]  was in modernen Begriffen zeigte, dass das Matroid-Schnittpunkt-Problem sowohl im NP als auch im Co-NP lag.  Edmonds ist bekannt f\u00fcr seine S\u00e4tze \u00fcber Verzweigungsalgorithmen mit maximalem Gewicht[8]  und Packen von kantendisjunkten Verzweigungen[9]  und seine Arbeit mit Richard Karp an schnelleren Flussalgorithmen.  Der Edmonds-Gallai-Zerlegungssatz beschreibt endliche Graphen unter dem Gesichtspunkt von \u00dcbereinstimmungen.  Er f\u00fchrte Polymatroide ein,[6]submodulare Str\u00f6mungen mit Richard Giles,[10]  und die Begriffe Unordnung und Blocker bei der Untersuchung von Hypergraphen.[1]  Ein wiederkehrendes Thema in seiner Arbeit[11]  besteht darin, nach Algorithmen zu suchen, deren zeitliche Komplexit\u00e4t polynomiell durch ihre Eingabegr\u00f6\u00dfe und Bitkomplexit\u00e4t begrenzt ist.[1]Von 1969 an war er mit Ausnahme von 1991\u20131993 Fakult\u00e4tsstelle am Institut f\u00fcr Kombinatorik und Optimierung der Fakult\u00e4t f\u00fcr Mathematik der Universit\u00e4t von Waterloo, wo seine Forschung kombinatorische Optimierungsprobleme und damit verbundene Polyeder umfasste.  In dieser Zeit betreute er die Doktorarbeit von einem Dutzend Studenten.Von 1991 bis 1993 war er in einen Streit (“die Edmonds-Aff\u00e4re”) mit der University of Waterloo verwickelt.[12][13]  wobei die Universit\u00e4t behauptete, dass ein eingereichtes Schreiben ein R\u00fccktrittsschreiben darstelle, das Edmonds bestritt.[14]  Der Konflikt wurde 1993 gel\u00f6st und er kehrte an die Universit\u00e4t zur\u00fcck.Edmonds zog sich 1999 von der University of Waterloo zur\u00fcck.Auszeichnungen und Ehrungen[edit]Edmonds erhielt 1985 den John von Neumann Theory Prize.Im Jahr 2001 wurde seine Arbeit “Path, Trees and Flowers” vom National Institute of Standards and Technology in ihrer feierlichen Ausgabe von A Century of Excellence in Measurements Standards and Technology als herausragende Ver\u00f6ffentlichung ausgezeichnetEr wurde 2002 in die Fellows-Klasse des Instituts f\u00fcr Operations Research und Management Sciences gew\u00e4hlt.[15]2006 verlieh die K\u00f6nigin von D\u00e4nemark Edmonds die Ehrendoktorw\u00fcrde der University of Southern Denmark.2014 wurde er als Distinguished Scientist geehrt und in die Galerie des National Institute of Standards and Technology aufgenommen.Ihm war der f\u00fcnfte australische Workshop zur kombinatorischen Optimierung im Jahr 2001 gewidmet.[7]Pers\u00f6nliches Leben[edit]Jacks Sohn Jeff Edmonds ist Professor f\u00fcr Informatik an der York University und seine Frau Kathie Cameron ist Professorin f\u00fcr Mathematik an der Laurier University.Siehe auch[edit]Verweise[edit]^ ein b c Edmonds, Jack (1991), “Ein Blick in den Himmel”, in JK Lenstra;  AHG Rinnooy Kan;  A. Schrijver (Hrsg.), Geschichte der mathematischen Programmierung – Eine Sammlung pers\u00f6nlicher Erinnerungen, CWI, Amsterdam und Nordholland, Amsterdam, S. 32\u201354^ Edmonds, Jack (1965).  “Wege, B\u00e4ume und Blumen”. K\u00f6nnen.  J. Math. 17: 449\u2013467.  doi:10.4153 \/ CJM-1965-045-4.^ Edmonds, Jack (1965).  “Maximale \u00dcbereinstimmung und ein Polyeder mit 0,1 Eckpunkten”. Journal of Research des National Bureau of Standards, Abschnitt B.. 69: 125\u2013130.^ Meurant, Gerard (2014). Algorithmen und Komplexit\u00e4t.  p. p.  4.  ISBN 978-0-08093391-7. Ein Problem soll sein m\u00f6glich wenn es in Polynomzeit gel\u00f6st werden kann (wie zum ersten Mal in Edmonds angegeben [26] [1965, Paths, trees, and flowers])).^ Edmonds, Jack (1971).  “Matroiden und der gierige Algorithmus”. Mathematik.  Programmierung (Princeton Symposium Math. Prog. 1967). 1: 127\u2013136.^ ein b Edmonds, Jack (1970), “Submodulare Funktionen, Matroiden und bestimmte Polyeder”, in R. Guy;  H. Hanam;  N. Sauer;  J. Schonheim (Hrsg.), Kombinatorische Strukturen und ihre Anwendungen (Proc. 1969 Calgary Conference)Gordon and Breach, New York, S. 69\u201387.^ ein b J\u00fcnger, Michael;  Reinelt, Gerhard;  Rinaldi, Giovanni, Hrsg.  (2003), “Kombinatorische Optimierung – Eureka, du schrumpfst!”, Vorlesungsunterlagen in Informatik, Springer, 2570^ Edmonds, Jack (1967).  “Optimale Verzweigungen”. J. Res.  Nat.  Bur.  Standards. 71B: 233\u2013240.^ Edmonds, Jack (1973), R. Rustin (Hrsg.), “Edge-disjoint branchings”, Kombinatorische Algorithmen, Monterey, Kalifornien, 1972: Algorithmics Press, New York: 91\u201396CS1-Wartung: Standort (Link)^ Edmonds, Jack;  Giles, Richard (1977), PL Hammer;  EL Johnson;  BH Korte;  GL Nemhauser (Hrsg.), “Eine Min-Max-Beziehung f\u00fcr submodulare Funktionen in Graphen”, Studium der Integer-Programmierung, Annalen der diskreten Mathematik, Nordholland, Amsterdam, 1: 185\u2013204^ Christoph Witzgall (2001), “Wege, B\u00e4ume und Blumen”, Ein Jahrhundert der Exzellenz in Messungen, Standards und Technologie (PDF), Nationales Institut f\u00fcr Standards und Technologie, S. 140\u2013144, archiviert von das Original (PDF) am 25.03.2006abgerufen 2011-08-11^ UW Gazette, 7. Oktober 1992: CAUT hat den Fall Jack Edmonds angerufen^ Einf\u00fchrung des Herausgebers Archiviert 27.10.2010 an der Wayback Machine, in: Kenneth Westhues, Hrsg., Workplace Mobbing in Academe: Berichte von 20 Universit\u00e4ten, Lewiston: NY: The Edwin Mellen Press, 2004^ Daily Bulletin der University of Waterloo, 5. M\u00e4rz 2001: Konferenz ehrt Jack Edmonds^ Fellows: Alphabetische Liste, Institut f\u00fcr Operations Research und Management Sciences, archiviert von das Original am 10.05.2019abgerufen 2019-10-09Externe Links[edit]"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki10\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki10\/2020\/12\/25\/jack-edmonds-wikipedia\/#breadcrumbitem","name":"Jack Edmonds – Wikipedia"}}]}]