[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/wiki16\/2020\/12\/31\/wt-tutte-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/wiki16\/2020\/12\/31\/wt-tutte-wikipedia\/","headline":"WT Tutte – Wikipedia","name":"WT Tutte – Wikipedia","description":"before-content-x4 Britisch-kanadischer Codebrecher und Mathematiker after-content-x4 William Thomas Tutte OC FRS FRSC (; 14. Mai 1917 – 2. Mai 2002)","datePublished":"2020-12-31","dateModified":"2020-12-31","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/wiki16\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/wiki16\/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:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/3\/39\/SZ42-6-wheels-lightened.jpg\/340px-SZ42-6-wheels-lightened.jpg","url":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/3\/39\/SZ42-6-wheels-lightened.jpg\/340px-SZ42-6-wheels-lightened.jpg","height":"255","width":"340"},"url":"https:\/\/wiki.edu.vn\/wiki16\/2020\/12\/31\/wt-tutte-wikipedia\/","wordCount":12129,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4Britisch-kanadischer Codebrecher und Mathematiker       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4William Thomas Tutte OC FRS FRSC (; 14. Mai 1917 – 2. Mai 2002) war ein in Gro\u00dfbritannien geborener kanadischer Codebrecher und Mathematiker.  W\u00e4hrend des Zweiten Weltkriegs machte er einen brillanten und grundlegenden Fortschritt in der Kryptoanalyse der Lorenz-Chiffre, eines wichtigen nationalsozialistischen deutschen Chiffriersystems, das f\u00fcr streng geheime Kommunikationen innerhalb des Oberkommandos der Wehrmacht verwendet wurde.  Der hochrangige strategische Charakter der Intelligenz, die aus Tuttes entscheidendem Durchbruch bei der Massenentschl\u00fcsselung von Lorenz-verschl\u00fcsselten Nachrichten gewonnen wurde, trug erheblich und vielleicht sogar entscheidend zur Niederlage von Nazideutschland bei.[2][3]  Er hatte auch eine Reihe bedeutender mathematischer Errungenschaften, darunter Grundlagenarbeiten auf den Gebieten der Graphentheorie und der Matroidentheorie.[4][5]Tuttes Forschungen auf dem Gebiet der Graphentheorie erwiesen sich als von bemerkenswerter Bedeutung.  Zu einer Zeit, als die Graphentheorie noch ein primitives Thema war, begann Tutte mit dem Studium der Matroiden und entwickelte sie zu einer Theorie, indem er die Arbeit erweiterte, die Hassler Whitney Mitte der 1930er Jahre zum ersten Mal entwickelt hatte.[6]  Obwohl Tuttes Beitr\u00e4ge zur Graphentheorie Einfluss auf die moderne Graphentheorie hatten und viele seiner Theoreme verwendet wurden, um Fortschritte auf diesem Gebiet zu erzielen, stimmte der gr\u00f6\u00dfte Teil seiner Terminologie nicht mit ihrer konventionellen Verwendung \u00fcberein und daher wird seine Terminologie von nicht verwendet Graphentheoretiker heute.[7]  “Tutte hat die Graphentheorie von einem Thema mit einem Text (D. K\u0151nigs) zu seinem gegenw\u00e4rtigen extrem aktiven Zustand weiterentwickelt.”[7]Table of Contents       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Fr\u00fches Leben und Ausbildung[edit]Zweiter Weltkrieg[edit]Diagnose des Chiffrierger\u00e4ts[edit]Tuttes statistische Methode[edit]Promotion und Karriere[edit]Forschungsbeitr\u00e4ge[edit]Positionen, Ehrungen und Auszeichnungen[edit]Pers\u00f6nliches Leben und Tod[edit]W\u00e4hlen Sie Ver\u00f6ffentlichungen aus[edit]B\u00fccher[edit]Artikel[edit]Siehe auch[edit]Verweise[edit]Quellen[edit]Externe Links[edit]Fr\u00fches Leben und Ausbildung[edit]Tutte wurde in Newmarket in Suffolk geboren.  Er war der j\u00fcngere Sohn von William John Tutte (1873\u20131944), einem G\u00e4rtner, und Annie (geb. Newell;  1881\u20131956), eine Haush\u00e4lterin.  Beide Eltern arbeiteten im Stall von Fitzroy House, wo Tutte geboren wurde.[5]  Die Familie verbrachte einige Zeit in Buckinghamshire, County Durham und Yorkshire, bevor sie nach Newmarket zur\u00fcckkehrte, wo Tutte die Grundschule der Cheveley Church of England besuchte[8]  im nahe gelegenen Dorf Cheveley.[4]  Im Jahr 1927, als er zehn Jahre alt war, gewann Tutte ein Stipendium an der Cambridge and County High School f\u00fcr Jungen.  Dort nahm er 1928 seinen Platz ein.1935 erhielt er ein Stipendium f\u00fcr ein Studium der Naturwissenschaften am Trinity College in Cambridge, wo er sich auf Chemie spezialisierte und 1938 mit Auszeichnung abschloss.[4]  Als Doktorand setzte er seine physikalische Chemie fort, wechselte jedoch Ende 1940 zur Mathematik.[4]  Als Student war er (zusammen mit drei seiner Freunde) einer der ersten, der das Problem der Quadratur des Quadrats l\u00f6ste, und der erste, der das Problem ohne ein quadratisches Teilrechteck l\u00f6ste.  Zusammen schufen die vier das Pseudonym Blanche Descartes, unter dem Tutte gelegentlich jahrelang ver\u00f6ffentlichte.[9]Zweiter Weltkrieg[edit]  Die Lorenz SZ-Maschinen hatten 12 R\u00e4der mit jeweils unterschiedlicher Anzahl von Nocken (oder “Stiften”). Kurz nach Ausbruch des Zweiten Weltkriegs schlug Tuttes Tutor Patrick Duff ihn f\u00fcr die Kriegsarbeit an der Government Code and Cypher School im Bletchley Park (BP) vor.  Er wurde interviewt und zu einem Schulungskurs nach London geschickt, bevor er in den Bletchley Park ging, wo er der Forschungsabteilung beitrat.  Zun\u00e4chst arbeitete er an der Hagelin-Chiffre, die von der italienischen Marine verwendet wurde.  Dies war eine Rotor-Verschl\u00fcsselungsmaschine, die im Handel erh\u00e4ltlich war, daher war die Mechanik der Verschl\u00fcsselung bekannt, und zum Entschl\u00fcsseln von Nachrichten musste nur herausgefunden werden, wie die Maschine eingerichtet war.[11]       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Im Sommer 1941 wurde Tutte versetzt, um an einem Projekt namens Fish zu arbeiten.  Geheimdienstinformationen hatten ergeben, dass die Deutschen die drahtlosen Fernschreiber-\u00dcbertragungssysteme nannten “S\u00e4gefisch” (S\u00e4gefisch).  Dies veranlasste die Briten, den Code Fish f\u00fcr das deutsche Teleprinter-Verschl\u00fcsselungssystem zu verwenden.  Der Spitzname Tunny (Thunfisch) wurde f\u00fcr die erste Nicht-Morse-Verbindung verwendet und anschlie\u00dfend f\u00fcr die Lorenz SZ-Maschinen und den von ihnen verschl\u00fcsselten Verkehr.[12]Die Telegraphie verwendete das 5-Bit International Telegraphy Alphabet Nr. 2 (ITA2).  \u00dcber den Verschl\u00fcsselungsmechanismus war nichts bekannt, au\u00dfer dass Nachrichten eine 12-Buchstaben-Anzeige vorausging, die eine 12-Rad-Rotor-Verschl\u00fcsselungsmaschine implizierte.  Der erste Schritt musste daher darin bestehen, die Maschine durch Festlegen der logischen Struktur und damit der Funktionsweise der Maschine zu diagnostizieren.  Tutte spielte dabei eine entscheidende Rolle, und erst kurz vor dem Sieg der Alliierten in Europa 1945 erwarb Bletchley Park eine Chiffriermaschine von Tunny Lorenz.[13]  Tuttes Durchbr\u00fcche f\u00fchrten schlie\u00dflich zu einer Massenentschl\u00fcsselung von Thunfisch-verschl\u00fcsselten Nachrichten zwischen dem deutschen Oberkommando (OKW) in Berlin und ihren Armeekommandos im gesamten besetzten Europa und trugen – vielleicht entscheidend – zur Niederlage Deutschlands bei.[2][3]Diagnose des Chiffrierger\u00e4ts[edit]Am 31. August 1941 wurden zwei Versionen derselben Nachricht mit identischen Schl\u00fcsseln gesendet, was eine “Tiefe” darstellte.  Dies erm\u00f6glichte es John Tiltman, dem Veteranen und bemerkenswert begabten Kryptoanalytiker von Bletchley Park, zu schlie\u00dfen, dass es sich um eine Vernam-Chiffre handelt, die die Exclusive Or (XOR) -Funktion (symbolisiert durch “\u2295”) verwendet, und die beiden Nachrichten zu extrahieren und damit den verdeckenden Schl\u00fcssel zu erhalten .  Nach einer fruchtlosen Zeit, in der Kryptoanalytiker der Forschungsabteilung versuchten, die Funktionsweise der Tunny-Maschine herauszufinden, wurden dieser und einige andere Schl\u00fcssel an Tutte \u00fcbergeben, der gebeten wurde, “zu sehen, was Sie daraus machen k\u00f6nnen”.[14]  Die Lorenz SZ42 Maschine mit abgenommenen Abdeckungen.  Bletchley Park MuseumW\u00e4hrend seines Trainings hatte Tutte die Kasiski-Pr\u00fcfungstechnik gelernt, einen Schl\u00fcssel auf Karopapier zu schreiben und eine neue Zeile nach einer definierten Anzahl von Zeichen zu beginnen, von denen vermutet wurde, dass sie die H\u00e4ufigkeit der Wiederholung des Schl\u00fcssels darstellen.[15]  Wenn diese Zahl korrekt w\u00e4re, w\u00fcrden die Spalten der Matrix mehr Wiederholungen von Zeichenfolgen anzeigen als der Zufall allein.  Tutte wusste, dass die Tunny-Indikatoren 25 Buchstaben (ohne J) f\u00fcr 11 der Positionen verwendeten, aber nur 23 Buchstaben f\u00fcr die anderen.  Er versuchte daher Kasiskis Technik auf den ersten Impuls der Schl\u00fcsselfiguren mit einer Wiederholung von 25 \u00d7 23 = 575. Er beobachtete in dieser Zeit keine gro\u00dfe Anzahl von Spaltenwiederholungen, aber er beobachtete das Ph\u00e4nomen auf einer Diagonale.  Er versuchte es daher erneut mit 574, was Wiederholungen in den Spalten zeigte.  Als er erkannte, dass die Primfaktoren dieser Zahl 2, 7 und 41 sind, versuchte er es erneut mit einer Periode von 41 und “bekam ein Rechteck aus Punkten und Kreuzen, das voller Wiederholungen war”.[16]Es war jedoch klar, dass der erste Impuls des Schl\u00fcssels komplizierter war als der, der von einem einzelnen Rad mit 41 Schl\u00fcsselimpulsen erzeugt wurde.  Tutte nannte diese Komponente des Schl\u00fcssels \u03c7{ displaystyle  chi}1 (Chi1).  Er nahm an, dass es eine andere Komponente gab, die mit XOR versehen war, die sich nicht immer mit jedem neuen Charakter \u00e4nderte, und dass dies das Produkt eines Rades war, das er nannte \u03c8{ displaystyle  psi}1 (psi1).  Gleiches gilt f\u00fcr jeden der f\u00fcnf Impulse (\u03c7{ displaystyle  chi}1\u03c7{ displaystyle  chi}2\u03c7{ displaystyle  chi}3\u03c7{ displaystyle  chi}4\u03c7{ displaystyle  chi}5 und \u03c8{ displaystyle  psi}1\u03c8{ displaystyle  psi}2\u03c8{ displaystyle  psi}3\u03c8{ displaystyle  psi}4\u03c8{ displaystyle  psi}5).  Also f\u00fcr ein einzelnes Zeichen der ganze Schl\u00fcssel K. bestand aus zwei Komponenten:K. = \u03c7{ displaystyle  chi}    \u2295  \u03c8{ displaystyle  psi} Im Bletchley Park wurden Markierungsimpulse durch angezeigt x und Raumimpulse durch \u2022 \u2022.[nb 1]  Zum Beispiel w\u00fcrde der Buchstabe “H” als codiert werden \u2022\u2022 x \u2022 x.[17]  Tuttes Ableitung der Chi und psi Komponenten wurden durch die Tatsache erm\u00f6glicht, dass Punkte mit gr\u00f6\u00dferer Wahrscheinlichkeit von Punkten gefolgt wurden und Kreuze mit gr\u00f6\u00dferer Wahrscheinlichkeit von Kreuzen gefolgt wurden.  Dies war ein Produkt einer Schw\u00e4che in der deutschen Schl\u00fcsseleinstellung, die sie sp\u00e4ter beseitigten.  Nachdem Tutte diesen Durchbruch geschafft hatte, schloss sich der Rest der Forschungsabteilung an, um die anderen Impulse zu untersuchen, und es wurde festgestellt, dass die f\u00fcnf Chi R\u00e4der alle mit jedem neuen Charakter vorger\u00fcckt und dass die f\u00fcnf psi Alle R\u00e4der bewegten sich unter der Kontrolle von zwei zusammen mu oder “Motor” R\u00e4der.  In den folgenden zwei Monaten erarbeiteten Tutte und andere Mitglieder der Forschungsabteilung die vollst\u00e4ndige logische Struktur der Maschine, wobei der Radsatz Nocken trug, die sich entweder in einer Position (angehoben) befanden, die hinzugef\u00fcgt wurde x zum Strom von Schl\u00fcsselfiguren oder an der alternativen Position, die hinzugef\u00fcgt wurde \u2022 \u2022.[18]Die Funktionsweise der Tunny-Maschine auf diese Weise zu diagnostizieren, war eine wirklich bemerkenswerte kryptoanalytische Errungenschaft, die unter Berufung auf Tuttes Einf\u00fchrung als Offizier des Ordens von Kanada als “eine der gr\u00f6\u00dften intellektuellen Leistungen des Zweiten Weltkriegs” beschrieben wurde.[5]Tuttes statistische Methode[edit]Um eine Tunny-Nachricht zu entschl\u00fcsseln, waren nicht nur Kenntnisse \u00fcber die logische Funktionsweise der Maschine erforderlich, sondern auch die Startpositionen jedes Rotors f\u00fcr die jeweilige Nachricht.  Es wurde nach einem Prozess gesucht, der den Chiffretext oder den Schl\u00fcssel manipuliert, um eine H\u00e4ufigkeitsverteilung von Zeichen zu erzeugen, die von der durch den Verschl\u00fcsselungsprozess angestrebten Einheitlichkeit abweicht.  Als Alan Turing im Juli 1942 zur Forschungsabteilung abgeordnet wurde, stellte er fest, dass die XOR-Kombination der Werte aufeinanderfolgender Zeichen in einem Strom aus Chiffretext und Schl\u00fcssel alle Abweichungen von einer gleichm\u00e4\u00dfigen Verteilung hervorhob.  Der resultierende Strom (symbolisiert durch den griechischen Buchstaben “Delta”) \u0394) wurde als Differenz bezeichnet, da XOR mit Modulo 2-Subtraktion identisch ist.Der Grund, warum dies einen Weg nach Tunny erm\u00f6glichte, war, dass die H\u00e4ufigkeitsverteilung der Zeichen im Chiffretext zwar nicht von einem zuf\u00e4lligen Strom unterschieden werden konnte, dies jedoch nicht f\u00fcr eine Version des Chiffretextes galt, aus der die Chi Element des Schl\u00fcssels wurde entfernt.  Dies war der Fall, weil der Klartext ein wiederholtes Zeichen enthielt und das psi R\u00e4der bewegten sich nicht weiter, die differenzierten psi Zeichen (\u0394\u03c8{ displaystyle  psi}) w\u00e4re das Nullzeichen (‘\/.  ‘im Bletchley Park).  Bei XOR-Bearbeitung mit einem beliebigen Zeichen hat dieses Zeichen keine Auswirkung.  Wiederholte Zeichen im Klartext waren sowohl aufgrund der deutschen Merkmale h\u00e4ufiger (EE, TT, LL und SS sind relativ h\u00e4ufig),[19]  und weil Telegraphen h\u00e4ufig die Zeichen der Zahlenverschiebung und der Buchstabenverschiebung wiederholten[20]  da ihr Verlust in einer gew\u00f6hnlichen Telegraphennachricht zu Kauderwelsch f\u00fchren k\u00f6nnte.[21]Um den allgemeinen Bericht \u00fcber Thunfisch zu zitieren:Turingery f\u00fchrte das Prinzip ein, dass sich der Schl\u00fcssel bei einem unterschied, der jetzt genannt wird \u0394\u039a, k\u00f6nnte Informationen liefern, die mit einem normalen Schl\u00fcssel nicht erh\u00e4ltlich sind.  Diese \u0394 Das Prinzip sollte die Grundlage f\u00fcr nahezu alle statistischen Methoden zum Brechen und Setzen von R\u00e4dern sein.[10]Tutte nutzte diese Verst\u00e4rkung der Ungleichm\u00e4\u00dfigkeit in den differenzierten Werten [nb 2]  und hatte bis November 1942 einen Weg gefunden, Radstartpunkte der Thunfischmaschine zu entdecken, die als “statistische Methode” bekannt wurde.[22]  Das Wesentliche dieser Methode war es, die Anfangseinstellungen des zu finden Chi Bestandteil des Schl\u00fcssels, indem alle Positionen seiner Kombination mit dem Chiffretext ausf\u00fchrlich ausprobiert werden und nach Beweisen f\u00fcr die Ungleichm\u00e4\u00dfigkeit gesucht wird, die die Eigenschaften des urspr\u00fcnglichen Klartextes widerspiegelt.[23][24]  Denn alle wiederholten Zeichen im Klartext w\u00fcrden immer erzeugen \u2022 \u2022und \u00e4hnlich \u2206\u03c8{ displaystyle  psi}1 \u2295 \u2206\u03c8{ displaystyle  psi}2 w\u00fcrde erzeugen \u2022 \u2022 wann immer die psi Die R\u00e4der bewegten sich nicht weiter und etwa die H\u00e4lfte der Zeit – insgesamt etwa 70%.Tutte wendete die Differenzierung nicht nur auf die vollst\u00e4ndigen 5-Bit-Zeichen des ITA2-Codes an, sondern auch auf die einzelnen Impulse (Bits).[nb 3]  Die jetzige Chi Die Radnockeneinstellungen mussten festgelegt worden sein, um die relevante Zeichenfolge der zu erm\u00f6glichen Chi R\u00e4der erzeugt werden.  Es war v\u00f6llig undurchf\u00fchrbar, die 22 Millionen Zeichen aus allen f\u00fcnf zu generieren Chi R\u00e4der, so war es zun\u00e4chst auf 41 \u00d7 31 = 1271 von den ersten beiden begrenzt.  Nachdem Newman Max Newman seine Ergebnisse erkl\u00e4rt hatte, wurde er beauftragt, einen automatisierten Ansatz zum Vergleichen von Chiffretext und Schl\u00fcssel zu entwickeln, um nach Abweichungen von der Zuf\u00e4lligkeit zu suchen.  Die erste Maschine hie\u00df Heath Robinson, aber der viel schnellere Colossus-Computer, der von Tommy Flowers entwickelt wurde und Algorithmen verwendet, die von Tutte und seinen Kollegen geschrieben wurden, \u00fcbernahm bald das Brechen von Codes.[25][26][27]Promotion und Karriere[edit]Tutte promovierte 1948 in Cambridge unter der Aufsicht von Shaun Wylie, der ebenfalls im Bletchley Park on Tunny gearbeitet hatte.  Ende 1945 nahm Tutte sein Studium in Cambridge wieder auf, jetzt als Doktorand in Mathematik.  Er ver\u00f6ffentlichte einige fr\u00fcher begonnene Arbeiten, eine mittlerweile ber\u00fchmte Arbeit, die charakterisiert, welche Graphen perfekt zusammenpassen, und eine andere, die einen nicht-Hamiltonschen Graphen konstruiert.  Er fuhr fort, eine bahnbrechende Doktorarbeit zu erstellen, Eine algebraische Theorie der Graphen\u00fcber das Thema, das sp\u00e4ter als Matroidentheorie bekannt wurde.[28]Im selben Jahr nahm er auf Einladung von Harold Scott MacDonald Coxeter eine Stelle an der University of Toronto an.  1962 zog er an die University of Waterloo in Waterloo, Ontario, wo er f\u00fcr den Rest seiner akademischen Karriere blieb.  Er ging 1985 offiziell in den Ruhestand, blieb aber als emeritierter Professor t\u00e4tig.  Tutte war ma\u00dfgeblich an der Gr\u00fcndung der Abteilung f\u00fcr Kombinatorik und Optimierung an der University of Waterloo beteiligt.Seine mathematische Karriere konzentrierte sich auf die Kombinatorik, insbesondere die Graphentheorie, die er in ihrer modernen Form mitgestaltet haben soll, und die Matroidentheorie, zu der er tiefgreifende Beitr\u00e4ge geleistet hat.  Ein Kollege beschrieb ihn als “den f\u00fchrenden Mathematiker in der Kombinatorik seit drei Jahrzehnten”.  Er war Chefredakteur der Zeitschrift f\u00fcr kombinatorische Theorie bis er 1985 aus Waterloo in den Ruhestand ging.[28]  Er war auch Redaktionsmitglied mehrerer anderer mathematischer Forschungszeitschriften.Forschungsbeitr\u00e4ge[edit]Tuttes Arbeit in der Graphentheorie umfasst die Struktur von Zyklusr\u00e4umen und Schnittr\u00e4umen, die Gr\u00f6\u00dfe maximaler \u00dcbereinstimmungen und die Existenz von k-Faktoren in Graphen sowie Hamilton- und Nicht-Hamilton-Graphen.[28]  Er widerlegte Taits Vermutung \u00fcber die Hamiltonizit\u00e4t polyedrischer Graphen, indem er die als Tuttes Fragment bekannte Konstruktion verwendete.  Der letztendliche Beweis des Vierfarbensatzes bediente sich seiner fr\u00fcheren Arbeit.  Das von ihm als “Dichromat” bezeichnete Graphenpolynom ist unter dem Namen Tutte-Polynom ber\u00fchmt und einflussreich geworden und dient als Prototyp kombinatorischer Invarianten, die f\u00fcr alle Invarianten universell sind, die ein bestimmtes Reduktionsgesetz erf\u00fcllen.Die ersten gro\u00dfen Fortschritte in der Matroidentheorie wurden von Tutte in seiner Cambridge-Doktorarbeit von 1948 erzielt, die die Grundlage f\u00fcr eine wichtige Abfolge von Arbeiten bildete, die in den n\u00e4chsten zwei Jahrzehnten ver\u00f6ffentlicht wurden.  Tuttes Arbeiten in der Graphentheorie und der Matroidentheorie haben die Entwicklung sowohl des Inhalts als auch der Richtung dieser beiden Bereiche ma\u00dfgeblich beeinflusst.[7]  In der Matroidentheorie entdeckte er das hochentwickelte Homotopiesatz und gr\u00fcndete die Studien \u00fcber Kettengruppen und regul\u00e4re Matroiden, \u00fcber die er tiefe Ergebnisse nachwies.Dar\u00fcber hinaus entwickelte Tutte einen Algorithmus zur Bestimmung, ob eine bestimmte bin\u00e4re Matroid eine grafische Matroid ist.  Der Algorithmus nutzt die Tatsache, dass ein planarer Graph einfach ein Graph ist, dessen Schaltungsmatroid, das Dual seiner Bindungsmatroid, grafisch ist.[29]Tutte schrieb eine Arbeit mit dem Titel Wie zeichnet man ein Diagramm? in dem er bewies, dass jedes Gesicht in einem 3-zusammenh\u00e4ngenden Graphen von einem peripheren Zyklus eingeschlossen ist.  Mit dieser Tatsache entwickelte Tutte einen alternativen Beweis, um zu zeigen, dass jeder Kuratowski-Graph nicht planar ist, indem er dies zeigt K.5 und K.3,3 Jeder hat drei verschiedene periphere Zyklen mit einer gemeinsamen Kante.  Tutte verwendete nicht nur periphere Zyklen, um zu beweisen, dass die Kuratowski-Graphen nicht planar sind, sondern bewies auch, dass jeder einfache 3-zusammenh\u00e4ngende Graph mit all seinen konvexen Fl\u00e4chen gezeichnet werden kann, und entwickelte einen Algorithmus, der die Ebenenzeichnung durch L\u00f6sen eines linearen Systems erstellt.  Die resultierende Zeichnung wird als Tutte-Einbettung bezeichnet.  Der Tutte-Algorithmus verwendet die baryzentrischen Abbildungen der Peripherieschaltungen eines einfachen 3-verbundenen Graphen.[30]Die in diesem Artikel ver\u00f6ffentlichten Ergebnisse haben sich als von gro\u00dfer Bedeutung erwiesen, da die von Tutte entwickelten Algorithmen zu beliebten Methoden zum Zeichnen planarer Graphen geworden sind.  Einer der Gr\u00fcnde, aus denen Tuttes Einbettung beliebt ist, ist, dass die notwendigen Berechnungen, die von seinen Algorithmen ausgef\u00fchrt werden, einfach sind und eine Eins-zu-Eins-Entsprechung eines Graphen und seiner Einbettung in die euklidische Ebene gew\u00e4hrleisten, was bei der Parametrisierung von Bedeutung ist ein dreidimensionales Netz zur Ebene bei der geometrischen Modellierung.  “Tuttes Theorem ist die Grundlage f\u00fcr L\u00f6sungen f\u00fcr andere Computergrafikprobleme wie Morphing.”[31]Tutte war haupts\u00e4chlich f\u00fcr die Entwicklung der Theorie der Aufz\u00e4hlung planarer Graphen verantwortlich, die enge Verbindungen zu chromatischen und dichromatischen Polynomen aufweist.  Diese Arbeit umfasste einige hochinnovative Techniken seiner eigenen Erfindung, die eine betr\u00e4chtliche manipulative Geschicklichkeit beim Umgang mit Potenzreihen (deren Koeffizienten geeignete Arten von Graphen z\u00e4hlen) und die Funktionen, die sich als ihre Summen ergeben, sowie geometrische Geschicklichkeit beim Extrahieren dieser Potenzreihen aus dem Graphen erfordern -theoretische Situation.[32]Tutte fasste seine Arbeit in der Ausgew\u00e4hlte Artikel von WT Tutte1979 und in Graphentheorie wie ich sie kenne, 1998.[28]Positionen, Ehrungen und Auszeichnungen[edit]Tuttes Arbeit im Zweiten Weltkrieg und anschlie\u00dfend in der Kombinatorik brachte ihm verschiedene Positionen, Ehrungen und Auszeichnungen ein:1958 Fellow der Royal Society of Canada (FRSC);1971 Jeffery-Williams-Preis der Canadian Mathematical Society;1975 Henry Marshall Tory-Medaille der Royal Society of Canada;1977 fand zu seinen Ehren anl\u00e4sslich seines 60. Geburtstages an der University of Waterloo eine Konferenz \u00fcber Graphentheorie und verwandte Themen statt.1982 Isaak-Walton-Killam-Preis des Canada Council;1987 Fellow der Royal Society (FRS);1990\u20131996 Erster Pr\u00e4sident des Instituts f\u00fcr Kombinatorik und ihre Anwendungen;[33]1998 Ernennung zum ehrenamtlichen Direktor des Zentrums f\u00fcr angewandte kryptografische Forschung an der University of Waterloo;[34]2001 Offizier des Order of Canada (OC);2001 CRM-Fields-PIMS-Preis.2016, Ruhmeshalle der Region Waterloo[35]2017, Waterloo “William Tutte Way” Stra\u00dfennamen[36]Tutte war von 1959 bis 1960 Bibliothekar der Royal Astronomical Society of Canada, und der Asteroid 14989 Tutte (1997 UB7) wurde nach ihm benannt.[37]Aufgrund der Arbeit von Tutte im Bletchley Park benannte das kanadische Unternehmen f\u00fcr Kommunikationssicherheit 2011 zu seinen Ehren eine interne Organisation zur F\u00f6rderung der Kryptologieforschung, das Tutte-Institut f\u00fcr Mathematik und Informatik (TIMC).[38]Im September 2014 wurde Tutte in seiner Heimatstadt Newmarket, England, mit der Enth\u00fcllung einer Skulptur gefeiert, nachdem eine lokale Zeitung eine Kampagne gestartet hatte, um sein Andenken zu ehren.[39]Der Bletchley Park in Milton Keynes feierte Tuttes Arbeit mit einer Ausstellung Bill Tutte: Mathematiker + Codebrecher von Mai 2017 bis 2019, gefolgt von Vortr\u00e4gen \u00fcber sein Leben und Werk w\u00e4hrend des Bill Tutte Centenary Symposium am 14. Mai 2017.[40][41]Pers\u00f6nliches Leben und Tod[edit]Neben den beruflichen Vorteilen der Arbeit an der neuen Universit\u00e4t von Waterloo hat die l\u00e4ndlichere Umgebung von Waterloo County Bill und seine Frau Dorothea angesprochen.  Sie kauften ein Haus im nahe gelegenen Dorf West Montrose, Ontario, wo sie gerne wanderten, Zeit in ihrem Garten am Grand River verbrachten und anderen erlaubten, die wundersch\u00f6ne Landschaft ihres Grundst\u00fccks zu genie\u00dfen.Sie hatten auch ein umfassendes Wissen \u00fcber alle V\u00f6gel in ihrem Garten.  Dorothea, eine begeisterte T\u00f6pferin, war auch eine begeisterte Wanderin und Bill organisierte Wanderungen.  Selbst gegen Ende seines Lebens war Bill noch ein begeisterter Wanderer.[7][42]  Nachdem seine Frau 1994 gestorben war, zog er zur\u00fcck nach Newmarket (Suffolk), kehrte aber 2000 nach Waterloo zur\u00fcck, wo er zwei Jahre sp\u00e4ter starb.[43]  Er ist auf dem West Montrose United Cemetery begraben.[44][28]W\u00e4hlen Sie Ver\u00f6ffentlichungen aus[edit]B\u00fccher[edit]Tutte, WT (1966), Konnektivit\u00e4t in Grafiken, Mathematische Ausstellungen, 15, Toronto, Ontario: University of Toronto Press, Zbl 0146.45603Tutte, WT (1966), Einf\u00fchrung in die Theorie der Matroiden, Santa Monica, Kalifornien: RAND Corporation-Bericht R-446-PR.  Ebenfalls Tutte, WT (1971), Einf\u00fchrung in die Theorie der Matroiden, Moderne analytische und rechnerische Methoden in Naturwissenschaften und Mathematik, 37, New York: American Elsevier Publishing Company, ISBN 978-0-444-00096-5, Zbl 0231.05027Tutte, WT, ed.  (1969), J\u00fcngste Fortschritte in der Kombinatorik.  Vortr\u00e4ge der dritten Waterloo-Konferenz \u00fcber Kombinatorik, Mai 1968, New York-London: Academic Press, S. xiv + 347, ISBN 978-0-12-705150-5, Zbl 0192.33101Tutte, WT (1979), McCarthy, D.;  Stanton, RG (Hrsg.), Ausgew\u00e4hlte Arbeiten von WT Tutte, Vols.  Ich, II., Winnipeg, Manitoba: Charles Babbage-Forschungszentrum, St. Pierre, Manitoba, Kanada, S. xxi + 879, Zbl 0403.05028Tutte, WT (1984), Graphentheorie, Enzyklop\u00e4die der Mathematik und ihrer Anwendungen, 21, Menlo Park, Kalifornien: Addison-Wesley Publishing Company, ISBN 978-0-201-13520-6, Zbl 0554.05001  Nachdruck von Cambridge University Press 2001, ISBN 978-0-521-79489-3Tutte, WT (1998), Graphentheorie wie ich sie kenne, Oxford Vorlesungsreihe in Mathematik und ihren Anwendungen, 11, Oxford: Clarendon Press, ISBN 978-0-19-850251-7, Zbl 0915.05041  Nachdruck 2012, ISBN 978-0-19-966055-1Artikel[edit]Siehe auch[edit]^ In der neueren Terminologie w\u00fcrde jeder Impuls als “Bit” bezeichnet, wobei eine Markierung bin\u00e4r 1 und ein Leerzeichen bin\u00e4r 0 ist. Das gestanzte Papierband hatte ein Loch f\u00fcr eine Markierung und kein Loch f\u00fcr ein Leerzeichen.^ Aus diesem Grund wird Tuttes 1 + 2-Methode manchmal als “Double-Delta” -Methode bezeichnet.^ Die f\u00fcnf Impulse oder Bits der codierten Zeichen werden manchmal als f\u00fcnf Ebenen bezeichnet.Verweise[edit]^ ein b c WT Tutte beim Mathematics Genealogy Project^ ein b Hinsley 1993, p.  8 Harvnb-Fehler: kein Ziel: CITEREFHinsley1993 (Hilfe)^ ein b (Brzezinski 2005, S. 18) Harv-Fehler: kein Ziel: CITEREFBrzezinski2005 (Hilfe)^ ein b c d J\u00fcnger 2012^ ein b c O’Connor & Robertson 2003 ^ Johnson, Will. “Matroids” (PDF).  Abgerufen 16. Oktober 2014.^ ein b c d Hobbs, Arthur M.;  James G. Oxley (M\u00e4rz 2004). “William T. Tutte (1917\u20132002)” (PDF). Mitteilungen der American Mathematical Society. 51 (3): 322.^ Cheveley CofE Grundschule, Park Road, Cheveley, Cambridgeshire, CB8 9DF http:\/\/www.cheveley.cambs.sch.uk\/^ Smith, Cedric AB;  Abbott, Steve (M\u00e4rz 2003), “Die Geschichte von Blanche Descartes”, Das mathematische Blatt, 87 (508): 23\u201333, doi:10.1017 \/ S0025557200172067, ISSN 0025-5572, JSTOR 3620560^ ein b Gut, Michie & Timms 1945, p.  6 in 1. Einleitung: Deutscher Thunfisch^ Tutte 2006, S. 352\u2013353^ Codebrecher: Die Insidergeschichte von Bletchley Park, FH Hinsley, Alan Stripp, 1994, https:\/\/books.google.com\/books?id=j1MC2d2LPAcC&printsec=frontcover&dq=Codebreakers+:+the+inside+story+of+Bletchley+Park ,&hl=de&sa=X&redir_esc=y#v=onepage&q=Introduction%20to%20fish&f = falsch, Eine Einf\u00fchrung in den Fisch, Hinsley, S. 141\u2013148^ Verkauf, Tony, Die Lorenz-Chiffre und wie Bletchley Park sie gebrochen hatabgerufen 21. Oktober 2010^ Tutte 2006, p.  354^ Bauer 2006, p.  375^ Tutte 2006, S. 356\u2013357^ Copeland 2006, S. 348, 349^ Tutte 2006, p.  357^ Singh, Simon, Die schwarze Kammerabgerufen 28. April 2012^ Newman c.  1944 p.  387^ Carter 2004, p.  3 Harvnb-Fehler: kein Ziel: CITEREFCarter2004 (Hilfe)^ Tutte 1998, S. 7\u20138 Harvnb-Fehler: Mehrere Ziele (2 \u00d7): CITEREFTutte1998 (Hilfe)^ Gut, Michie & Timms 1945, S. 321\u2013322 in 44. Handstatistische Methoden: Einstellung – Statistische Methoden^ Budiansky 2006, S. 58\u201359 Harvnb-Fehler: kein Ziel: CITEREFBudiansky2006 (Hilfe)^ Copeland 2011^ J\u00fcnger, Dan (August 2002). “Biographie von Professor Tutte”. CMS-Hinweise.  Abgerufen 24. Juni 2018 – \u00fcber die University of Waterloo.^ Roberts, Jerry (2017), Lorenz: Hitlers streng geheimen Code im Bletchley Park brechen, Stroud, Gloucestershire: The History Press, ISBN 978-0-7509-7885-9^ ein b c d e https:\/\/uwaterloo.ca\/combinatorics-and-optimization\/about\/professor-william-t-tutte\/biography-professor-tutte^ WT Tutte.  Ein Algorithmus zum Bestimmen, ob eine gegebene bin\u00e4re Matroid grafisch ist, Verfahren der London Mathematical Society, 11(1960) 905\u2013917^ WT Tutte.  Wie zeichnet man ein Diagramm?  Proceedings of the London Mathematical Society, 13 (3): 743\u2013768, 1963.^ Steven J. Gortle;  Craig Gotsman;  Dylan Thurston.  “Diskrete Einformen auf Netzen und Anwendungen zur 3D-Netzparametrisierung”, Computergest\u00fctztes geometrisches Design23 (2006) 83\u2013112^ C. St. JA Nash-Williams, Eine Anmerkung zu einigen mathematischen Arbeiten, Graphentheorien und verwandten Themen von Professor Tutte (Hrsg. JA Bondy und US R Murty), Academic Press, New York, 1979, p.  xxvii.^ “Das Institut f\u00fcr Kombinatorik und ihre Anwendungen”.  ICA.  Archiviert von das Original am 2. Oktober 2013.  Abgerufen 28. September 2013.^ “Tutte vom kryptografischen Zentrum geehrt”.  Universit\u00e4t von Waterloo.  Abgerufen 28. September 2013.^ https:\/\/uwaterloo.ca\/combinatorics-and-optimization\/news\/bill-tutte-inducted-waterloo-region-hall-fame^ https:\/\/uwaterloo.ca\/stories\/mathematics-professor-and-wartime-code-breaker-honoured^ “Asteroid (14989) Tutte”.  Royal Astronomical Society of Canada.  14. Juni 2011. Archiviert von das Original am 4. Januar 2015.  Abgerufen 25. September 2014.^ Freeze, Colin (7. September 2011). “Das streng geheime Institut kommt aus dem Schatten, um Top-Talente zu rekrutieren.”. Der Globus und die Post.  Toronto.  Abgerufen 25. September 2014.^ “Das Bill Tutte Denkmal”.  Bill Tutte Memorial Fund.  Abgerufen 13. Dezember 2014.^ https:\/\/uwaterloo.ca\/combinatorics-and-optimization\/news\/bill-tutte-centenary-symposium-bletchley-park-0^ https:\/\/www.bletchleypark.org.uk\/news\/codebreaker-bill-tutte-to-be-celebrated-in-centenary-exhibition^ “Bill Tutte”.  Telegraph Group Limited.  Archiviert von das Original am 27. September 2013.  Abgerufen 21. Mai 2013.^ van der Vat, Dan (10. Mai 2002), “Nachruf: William Tutte”, Der W\u00e4chter, Londonabgerufen 28. April 2013^ http:\/\/geneofun.on.ca\/names\/photo\/858001Quellen[edit]Bauer, Friedrich L. (2006), Die Tiltman-Pause  Anhang 5 in Copeland 2006, S. 370\u2013377Copeland, B. Jack, Hrsg.  (2006), Colossus: Die Geheimnisse der Codebreaking-Computer von Bletchley Park, Oxford: Oxford University Press, ISBN 978-0-19-284055-4Copeland, B. Jack (2011), Koloss und der Beginn des Computerzeitalters  in Erskine & Smith 2011, S. 305\u2013327Erskine, Ralph;  Smith, Michael, Hrsg.  (2011) [2001], Die Bletchley Park Codebrecher, Biteback Publishing Ltd, ISBN 978-1-84954-078-0  Aktualisierte und erweiterte Version von Aktion an diesem Tag: Vom Brechen des R\u00e4tselcodes bis zur Geburt des modernen Computers Bantam Press 2001Gut, Jack;  Michie, Donald;  Timms, Geoffrey (1945), Allgemeiner Bericht \u00fcber Thunfisch: Mit Schwerpunkt auf statistischen Methoden, UK Public Record Office HW 25\/4 und HW 25\/5abgerufen 15. September 2010  Diese Version ist eine Faksimile-Kopie, aber es gibt eine Abschrift eines Gro\u00dfteils dieses Dokuments im PDF-Format unter: Verkauf, Tony (2001), Teil des ‘General Report on Tunny’, der Newmanry History, formatiert von Tony Sale (PDF)abgerufen 20. September 2010und ein Web-Transkript von Teil 1 unter: Ellsbury, Graham, Allgemeiner Bericht \u00fcber Thunfisch mit Schwerpunkt auf statistischen Methodenabgerufen 3. November 2010Gut, Jack (1993), R\u00e4tsel und Fisch  in Hinsley & Stripp 1993, S. 149\u2013166Hinsley, FH;  Stripp, Alan, Hrsg.  (1993) [1992], Codebrecher: Die Insider-Geschichte von Bletchley Park, Oxford: Oxford University Press, ISBN 978-0-19-280132-6O’Connor, JJ;  Robertson, EF (2003), MacTutor Biografie: William Thomas Tutte, Universit\u00e4t von St. Andrewsabgerufen 28. April 2013Tutte, WT (19. Juni 1998), Fisch und ich (PDF)abgerufen 7. April 2012  Abschrift eines Vortrags von Prof. Tutte an der University of WaterlooTutte, William T. (2006), Meine Arbeit im Bletchley Park  Anhang 4 in Copeland 2006, S. 352\u2013369Ward, Mark (27. Mai 2011), “Code-Cracking-Maschine wieder zum Leben erweckt”, BBC Newsabgerufen 28. April 2013J\u00fcnger, DH (2012), Biografische Erinnerungen von Stipendiaten der Royal Society: William Thomas Tutte.  14. Mai 1917 – 2. Mai 2002, The Royal Society, doi:10.1098 \/ rsbm.2012.0036abgerufen 28. April 2013Externe Links[edit]Professor William T. TutteWT Tutte beim Mathematics Genealogy ProjectWilliam Tutte, 84, Mathematiker und Code-Breaker, stirbt – Nachruf von Die New York TimesWilliam Tutte: Unbesungener mathematischer Mastermind – Nachruf von Der W\u00e4chterCRM-Fields-PIMS-Preis – 2001 – William T. Tutte“60 Jahre in den Netzen” – ein Vortrag (Audioaufnahme), der am 25. Oktober 2001 am Fields Institute gehalten wurde, um den Erhalt des CRM-Fields-Preises 2001 zu markierenTutte widerlegt Taits Vermutung“Bletchleys vergessene Helden”, Ian Douglas, Der t\u00e4gliche Telegraph, 25. Dezember 2012Murty, USR (2004), “Widmung: Professor WT Tutte”, Zeitschrift f\u00fcr kombinatorische Theorie, Serie B, 92 (2): 191\u2013192, doi:10.1016 \/ j.jctb.2004.08.002.Younger, DH (2004), “Widmung: Professor WT Tutte”, Zeitschrift f\u00fcr kombinatorische Theorie, Serie B, 92 (2): 193\u2013198, doi:10.1016 \/ j.jctb.2004.09.002.     (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki16\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki16\/2020\/12\/31\/wt-tutte-wikipedia\/#breadcrumbitem","name":"WT Tutte – Wikipedia"}}]}]