WT Tutte

WT Tutte

Nació	( 14 de mayo de 1917 )14 de mayo de 1917 Newmarket, Suffolk , Inglaterra
Murió	2 de mayo de 2002 (2002-05-02)(84 años) Kitchener , Ontario, Canadá
alma mater	Trinity College, Cambridge ( Doctorado )
Conocido por	MEJOR teorema Teorema de Hanani-Tutte Ciclo periférico Tutte 12 jaulas Tutte incrustación Gráfico de Tutte Teorema de homotopía de Tutte Matriz de tutte Polinomio de Tutte Teorema de tutte Fórmula de Tutte-Berge Gráfico de Tutte-Coxeter Invariante de Tutte-Grothendieck "1 + 2 irrumpir" de Tutte Teorema de un factor de Tutte Fragmento de Tutte Teorema de vinculación de Tutte Criterio de planaridad de Tutte Método estadístico de Tutte Lema del triángulo de Tutte Teorema de representación unimodular de Tutte Teorema de la rueda de Tutte
Esposos)	Dorothea Geraldine Mitchell (m. 1949-1994, su muerte)
Premios	Premio Jeffery-Williams (1971) Medalla Henry Marshall Tory (1975) Premio Isaak-Walton-Killam (1982) Premio CRM-Fields-PIMS (2001)
Carrera científica
Los campos	Matemáticas
Instituciones	Universidad de Toronto Universidad de Waterloo
Tesis	Una teoría algebraica de gráficos ^[1] (1948)
Asesor de doctorado	Shaun Wylie ^[1]
Estudiantes de doctorado	WG Marrón Neil Robertson ^[1]

William Thomas Tutte OC FRS FRSC ( / t ʌ t / ; 14 de mayo de 1917 - 2 de mayo de 2002) fue un descifrador de códigos y matemático inglés y canadiense . Durante la Segunda Guerra Mundial , hizo un avance brillante y fundamental en el criptoanálisis del cifrado de Lorenz , un importante sistema de cifrado alemán nazi que se utilizó para comunicaciones ultrasecretas dentro de la Wehrmacht.Alto comando. La naturaleza estratégica de alto nivel de la inteligencia obtenida del avance crucial de Tutte, en el descifrado masivo de mensajes cifrados por Lorenz específicamente, contribuyó en gran medida, y quizás incluso de manera decisiva, a la derrota de la Alemania nazi. ^[2]^[3] También tuvo una serie de logros matemáticos significativos, incluido el trabajo de base en los campos de la teoría de grafos y la teoría matroide . ^[4]^[5]

La investigación de Tutte en el campo de la teoría de grafos resultó ser de notable importancia. En un momento en que la teoría de grafos todavía era un tema primitivo, Tutte comenzó el estudio de las matroides y las desarrolló hasta convertirlas en una teoría ampliando el trabajo que Hassler Whitney había desarrollado por primera vez a mediados de la década de 1930. ^[6] Aunque las contribuciones de Tutte a la teoría de grafos han influido en la teoría de grafos moderna y muchos de sus teoremas se han utilizado para seguir haciendo avances en el campo, la mayor parte de su terminología no estaba de acuerdo con su uso convencional y, por lo tanto, su terminología es no utilizado por los teóricos de grafos en la actualidad. ^[7] "Tutte la teoría de grafos avanzada a partir de un tema con un texto ( D. Kőnig's) hacia su actual estado extremadamente activo ". ^[7]

Temprana edad y educación

Tutte nació en Newmarket en Suffolk. Era el hijo menor de William John Tutte (1873-1944), jardinero de la finca, y Annie (de soltera Newell; 1881-1956), ama de llaves. Ambos padres trabajaban en los establos de Fitzroy House, donde nació Tutte. ^[5] La familia pasó algún tiempo en Buckinghamshire, el condado de Durham y Yorkshire antes de regresar a Newmarket, donde Tutte asistió a la escuela primaria de la Iglesia de Inglaterra de Cheveley ^[8] en la cercana aldea de Cheveley. ^[4] En 1927, cuando tenía diez años, Tutte ganó una beca para el Cambridge and County High School for Boys . Ocupó su lugar allí en 1928.

En 1935 ganó una beca para estudiar ciencias naturales en el Trinity College, Cambridge , donde se especializó en química y se graduó con honores de primera clase en 1938. ^[4] Continuó con la química física como estudiante de posgrado, pero se transfirió a matemáticas en el finales de 1940. ^[4] Como estudiante, él (junto con tres de sus amigos) se convirtió en uno de los primeros en resolver el problema de elevar el cuadrado al cuadrado , y el primero en resolver el problema sin un subrectangulo al cuadrado. Juntos, los cuatro crearon el seudónimo Blanche Descartes , bajo el cual Tutte publicó ocasionalmente durante años. ^[9]

Segunda Guerra Mundial

Las máquinas Lorenz SZ tenían 12 ruedas cada una con un número diferente de levas (o "pasadores").

Número de rueda	1	2	3	4	5	6	7	8	9	10	11	12
Nombre de la rueda BP ^[10]	${\ Displaystyle \ psi}$ ₁	${\ Displaystyle \ psi}$ ₂	${\ Displaystyle \ psi}$ ₃	${\ Displaystyle \ psi}$ ₄	${\ Displaystyle \ psi}$ ₅	${\ Displaystyle \ mu}$ 37	${\ Displaystyle \ mu}$ 61	${\ Displaystyle \ chi}$ ₁	${\ Displaystyle \ chi}$ ₂	${\ Displaystyle \ chi}$ ₃	${\ Displaystyle \ chi}$ ₄	${\ Displaystyle \ chi}$ ₅
Número de levas (pines)	43	47	51	53	59	37	61	41	31	29	26	23

Poco después del estallido de la Segunda Guerra Mundial , el tutor de Tutte, Patrick Duff, lo sugirió para el trabajo de guerra en el Código de Gobierno y la Escuela de Cifrado en Bletchley Park (BP). Fue entrevistado y enviado a un curso de formación en Londres antes de ir a Bletchley Park, donde se incorporó a la Sección de Investigación. Al principio, trabajó en el cifrado de Hagelin que estaba siendo utilizado por la Armada italiana. Esta era una máquina de cifrado de rotor que estaba disponible comercialmente, por lo que se conocía la mecánica de cifrado, y descifrar mensajes solo requería averiguar cómo estaba configurada la máquina. ^[11]

En el verano de 1941, Tutte fue transferido para trabajar en un proyecto llamado Fish. La información de inteligencia había revelado que los alemanes llamaban a los sistemas de transmisión de teleimpresores inalámbricos "Sägefisch" (pez sierra). Esto llevó a los británicos a utilizar el código Fish para el sistema de cifrado de teleimpresor alemán. El apodo Tunny (atún) se utilizó para el primer enlace que no era Morse, y posteriormente se utilizó para las máquinas Lorenz SZ y el tráfico que cifraron. ^[12]

La telegrafía utilizó el Alfabeto internacional de telegrafía n. ° 2 de 5 bits (ITA2). No se sabía nada sobre el mecanismo de cifrado aparte de que los mensajes estaban precedidos por un indicador de 12 letras , lo que implicaba una máquina de cifrado de rotor de 12 ruedas. El primer paso, por tanto, tenía que ser diagnosticar la máquina estableciendo la estructura lógica y, por tanto, el funcionamiento de la máquina. Tutte jugó un papel fundamental para lograr esto, y no fue hasta poco antes de la victoria aliada en Europa en 1945, que Bletchley Park adquirió una máquina de cifrado Tunny Lorenz . ^[13] Los avances de Tutte llevaron finalmente al descifrado masivo de mensajes cifrados por Tunny entre el Alto Mando Alemán (OKW)en Berlín y su ejército comanda en toda la Europa ocupada y contribuyó —quizá de manera decisiva— a la derrota de Alemania. ^[2]^[3]

Diagnóstico de la máquina de cifrado

El 31 de agosto de 1941 se enviaron dos versiones del mismo mensaje utilizando claves idénticas, lo que constituía una " profundidad ". Esto permitió a John Tiltman , el criptoanalista veterano y notablemente dotado de Bletchley Park, deducir que se trataba de un cifrado de Vernam que usa la función Exclusive Or (XOR) (simbolizada por "⊕"), y extraer los dos mensajes y, por lo tanto, obtener la clave de oscurecimiento . Después de un período infructuoso durante el cual los criptoanalistas de la Sección de Investigación intentaron averiguar cómo funcionaba la máquina Tunny, esta y algunas otras llaves fueron entregadas a Tutte, a quien se le pidió que "viera qué puede hacer con ellas". ^[14]

La máquina Lorenz SZ42 sin las cubiertas. Museo de Bletchley Park

En su curso de formación, a Tutte se le había enseñado la técnica de examen Kasiski de escribir una clave en un papel cuadriculado, comenzando una nueva fila después de un número definido de caracteres que se sospechaba que era la frecuencia de repetición de la clave. ^[15]Si este número fuera correcto, las columnas de la matriz mostrarían más repeticiones de secuencias de caracteres que el azar por sí solo. Tutte sabía que los indicadores Tunny usaban 25 letras (excluyendo la J) para 11 de las posiciones, pero solo 23 letras para la otra. Por lo tanto, probó la técnica de Kasiski en el primer impulso de los personajes clave, utilizando una repetición de 25 × 23 = 575. No observó un gran número de repeticiones de columnas con este período, pero sí observó el fenómeno en diagonal. Por lo tanto, volvió a intentarlo con 574, que se repite en las columnas. Reconociendo que los factores primos de este número son 2, 7 y 41, lo intentó nuevamente con un punto de 41 y "obtuvo un rectángulo de puntos y cruces que estaba repleto de repeticiones". ^[dieciséis]

Sin embargo, estaba claro que el primer impulso de la tecla era más complicado que el producido por una sola rueda de 41 impulsos de tecla. Tutte llamó a este componente de la clave ₁ ( chi ₁ ). Pensó que había otro componente, que era XOR-ed con esto, que no siempre cambiaba con cada nuevo carácter, y que este era el producto de una rueda a la que llamó ₁ ( psi ₁ ). Lo mismo se aplica a cada uno de los cinco impulsos ( ₁₂₃₄₅ y ₁₂₃₄₅ ). Entonces, para un solo carácter, toda la clave K constaba de dos componentes: ${\ Displaystyle \ chi}$ ${\ Displaystyle \ psi}$ ${\ Displaystyle \ chi}$ ${\ Displaystyle \ chi}$ ${\ Displaystyle \ chi}$ ${\ Displaystyle \ chi}$ ${\ Displaystyle \ chi}$ ${\ Displaystyle \ psi}$ ${\ Displaystyle \ psi}$ ${\ Displaystyle \ psi}$ ${\ Displaystyle \ psi}$ ${\ Displaystyle \ psi}$

K = ⊕

{\ Displaystyle \ chi}

{\ Displaystyle \ psi}

En Bletchley Park, los impulsos de marca fueron representados por x y los impulsos de espacio por • . ^{[nb 1]} Por ejemplo, la letra "H" se codificaría como •• x • x . ^[17] La derivación de Tutte de los componentes chi y psi fue posible por el hecho de que era más probable que los puntos fueran seguidos por puntos y que los cruces fueran seguidos por cruces. Esto fue producto de una debilidad en la configuración clave alemana, que luego eliminaron. Una vez que Tutte hizo este gran avance, el resto de la Sección de Investigación se unió para estudiar los otros impulsos y se estableció que los cinco chitodas las ruedas avanzaron con cada nuevo personaje y que las cinco ruedas psi se movieron juntas bajo el control de dos ruedas mu o "motorizadas". Durante los siguientes dos meses, Tutte y otros miembros de la Sección de Investigación elaboraron la estructura lógica completa de la máquina, con su conjunto de ruedas con levas que podrían estar en una posición (levantada) que agregara x al flujo de caracteres clave , o en la posición alternativa que agregó en • . ^[18]

Diagnosticar el funcionamiento de la máquina Tunny de esta manera fue un logro criptoanalítico verdaderamente notable que, en la cita para la inducción de Tutte como oficial de la Orden de Canadá , fue descrito como "una de las mayores hazañas intelectuales de la Segunda Guerra Mundial". ^[5]

Método estadístico de Tutte

Para descifrar un mensaje de Tunny era necesario conocer no solo el funcionamiento lógico de la máquina, sino también las posiciones de inicio de cada rotor para el mensaje en particular. Se estaba buscando un proceso que manipulara el texto cifrado o la clave para producir una distribución de frecuencia de caracteres que se apartara de la uniformidad que el proceso de cifrado pretendía lograr. Mientras estaba adscrito a la Sección de Investigación en julio de 1942, Alan Turing descubrió que la combinación XOR de los valores de los caracteres sucesivos en un flujo de texto cifrado y clave enfatizaba cualquier desviación de una distribución uniforme. El flujo resultante (simbolizado por la letra griega "delta" Δ ) se denominó diferencia porque XOR es lo mismo que la resta de módulo 2.

La razón por la que esto proporcionó un acceso a Tunny fue que, aunque la distribución de frecuencia de los caracteres en el texto cifrado no se podía distinguir de un flujo aleatorio, no sucedía lo mismo con una versión del texto cifrado a partir del cual se había obtenido el elemento chi de la clave. remoto. Este fue el caso porque donde el texto plano contenía un carácter repetido y las ruedas psi no se movían, el carácter psi diferenciado ( Δ ) sería el carácter nulo (' / ' en Bletchley Park). Cuando XOR-ed con cualquier carácter, este carácter no tiene ningún efecto. Los caracteres repetidos en el texto plano fueron más frecuentes debido a las características del alemán (EE, TT, LL y SS son relativamente comunes), ^[19] ${\ Displaystyle \ psi}$ y porque los telegrafistas repetían con frecuencia los caracteres de cambio de cifras y de cambio de letras ^[20], ya que su pérdida en un mensaje telegráfico ordinario podría dar lugar a un galimatías. ^[21]

Para citar el Informe general sobre Tunny:

Turingery introdujo el principio de que la clave diferenciada en uno, ahora llamada ΔΚ , podría proporcionar información que no se puede obtener de la clave ordinaria. Este principio Δ iba a ser la base fundamental de casi todos los métodos estadísticos de frenado y ajuste de ruedas. ^[10]

Tutte aprovechó esta amplificación de la falta de uniformidad en los valores diferenciados ^{[nb 2]} y en noviembre de 1942 había producido una forma de descubrir los puntos de partida de la rueda de la máquina Tunny que se conoció como el "método estadístico". ^[22] La esencia de este método era encontrar la configuración inicial del componente chi de la clave probando exhaustivamente todas las posiciones de su combinación con el texto cifrado y buscando evidencia de la falta de uniformidad que reflejaba las características del texto plano original. . ^[23]^[24] Porque cualquier carácter repetido en el texto plano siempre generaría • , y de manera similar ∆ ₁ ⊕ ∆ ₂ generaría • ${\ Displaystyle \ psi}$ ${\ Displaystyle \ psi}$ cada vez que las ruedas psi no se movían, y aproximadamente la mitad de las veces cuando lo hacían, un 70% en general.

Además de aplicar la diferenciación a los caracteres completos de 5 bits del código ITA2, Tutte lo aplicó a los impulsos individuales (bits). ^{[nb 3]} Los ajustes actuales de la cámara de la rueda chi deben haberse establecido para permitir que se genere la secuencia relevante de caracteres de las ruedas chi . Era totalmente impracticable generar los 22 millones de caracteres de las cinco ruedas de chi , por lo que inicialmente se limitó a 41 × 31 = 1271 de las dos primeras. Después de explicar sus hallazgos a Max Newman , Newman recibió el trabajo de desarrollar un enfoque automatizado para comparar texto cifrado y clave para buscar desviaciones de la aleatoriedad. La primera máquina se llamó Heath Robinson, pero la computadora Colossus , mucho más rápida , desarrollada por Tommy Flowers y usando algoritmos escritos por Tutte y sus colegas, pronto se hizo cargo de descifrar códigos. ^[25]^[26]^[27]

Doctorado y carrera

Tutte completó un doctorado en matemáticas de Cambridge en 1948 bajo la supervisión de Shaun Wylie , quien también había trabajado en Bletchley Park en Tunny. A finales de 1945, Tutte reanudó sus estudios en Cambridge, ahora como estudiante de posgrado en matemáticas. Publicó un trabajo que comenzó antes, uno, un artículo ahora famoso que caracteriza qué gráficos tienen una coincidencia perfecta, y otro que construye un gráfico no hamiltoniano. Luego pasó a crear una tesis doctoral innovadora, Una teoría algebraica de gráficos , sobre el tema más tarde conocido como teoría matroide. ^[28]

El mismo año, invitado por Harold Scott MacDonald Coxeter , aceptó un puesto en la Universidad de Toronto . En 1962, se trasladó a la Universidad de Waterloo en Waterloo , Ontario, donde permaneció el resto de su carrera académica. Se retiró oficialmente en 1985, pero permaneció activo como profesor emérito. Tutte fue fundamental para ayudar a fundar el Departamento de Combinatoria y Optimización en la Universidad de Waterloo.

Su carrera matemática se concentró en la combinatoria , especialmente la teoría de grafos , a la que se le atribuye haber contribuido a crear en su forma moderna, y la teoría matroide , a la que hizo profundas contribuciones; un colega lo describió como "el matemático líder en combinatoria durante tres décadas". Fue editor en jefe del Journal of Combinatorial Theory hasta que se retiró de Waterloo en 1985. ^[28] También formó parte de los consejos editoriales de varias otras revistas de investigación matemática.

Contribuciones a la investigación

El trabajo de Tutte en la teoría de grafos incluye la estructura de los espacios cíclicos y los espacios de corte , el tamaño de las coincidencias máximas y la existencia de factores k en las gráficas, y gráficas hamiltonianas y no hamiltonianas. ^[28] Refutó la conjetura de Tait , sobre la hamiltonicidad de los gráficos poliédricos , utilizando la construcción conocida como fragmento de Tutte . La prueba final del teorema de los cuatro colores hizo uso de su trabajo anterior. El polinomio gráfico que llamó "dicromato" se ha hecho famoso e influyente bajo el nombre de polinomio de Tutte. y sirve como prototipo de invariantes combinatorios que son universales para todos los invariantes que satisfacen una ley de reducción especificada.

Los primeros avances importantes en la teoría matroide fueron realizados por Tutte en su tesis doctoral de Cambridge de 1948, que formó la base de una importante secuencia de artículos publicados durante las dos décadas siguientes. El trabajo de Tutte en teoría de grafos y teoría matroide ha sido profundamente influyente en el desarrollo tanto del contenido como de la dirección de estos dos campos. ^[7] En la teoría de matroides, descubrió el teorema de homotopía altamente sofisticado y fundó los estudios de grupos de cadenas y matroides regulares , sobre los cuales demostró resultados profundos.

Además, Tutte desarrolló un algoritmo para determinar si una determinada matriz binaria es una matriz gráfica . El algoritmo hace uso del hecho de que un gráfico plano es simplemente un gráfico cuyo circuito-matroide, el dual de su enlace-matroide , es gráfico. ^[29]

Tutte escribió un artículo titulado Cómo dibujar un gráfico en el que demostró que cualquier cara en un gráfico de 3 conexiones está encerrada por un ciclo periférico . Usando este hecho, Tutte desarrolló una prueba alternativa para mostrar que cada gráfico de Kuratowski no es plano al mostrar que K ₅ y K _3,3 tienen cada uno tres ciclos periféricos distintos con un borde común. Además de usar ciclos periféricos para demostrar que las gráficas de Kuratowski no son planas, Tutte demostró que cada gráfica simple de 3 conexiones se puede dibujar con todas sus caras convexas, y diseñó un algoritmo que construye el dibujo plano resolviendo un sistema lineal. El dibujo resultante se conoce como incrustación de Tutte. El algoritmo de Tutte utiliza las asignaciones baricéntricas de los circuitos periféricos de un gráfico simple de 3 conexiones. ^[30]

Los hallazgos publicados en este artículo han demostrado ser de gran importancia porque los algoritmos que desarrolló Tutte se han convertido en métodos populares de dibujo de gráficos planos. Una de las razones por las que la incrustación de Tutte es popular es que los cálculos necesarios que realizan sus algoritmos son simples y garantizan una correspondencia uno a uno de un gráfico y su incrustación en el plano euclidiano , lo cual es importante a la hora de parametrizar. una malla tridimensional al plano en modelado geométrico. "El teorema de Tutte es la base para las soluciones a otros problemas de gráficos por computadora, como la transformación ". ^[31]

Tutte fue el principal responsable del desarrollo de la teoría de enumeración de gráficos planos, que tiene estrechos vínculos con polinomios cromáticos y dicromáticos. Este trabajo involucró algunas técnicas altamente innovadoras de su propia invención, que requieren una considerable destreza manipuladora en el manejo de series de potencia (cuyos coeficientes cuentan los tipos apropiados de gráficos) y las funciones que surgen como sus sumas, así como destreza geométrica para extraer estas series de potencia del gráfico. -Situación teórica. ^[32]

Tutte resumió su trabajo en los artículos seleccionados de WT Tutte , 1979, y en la teoría de grafos como la he conocido , 1998. ^[28]

Cargos, honores y premios

El trabajo de Tutte en la Segunda Guerra Mundial y posteriormente en combinatoria le valió varios cargos, honores y premios:

1958, miembro de la Royal Society of Canada (FRSC);
1971, premio Jeffery-Williams de la Canadian Mathematical Society ;
1975, Medalla Henry Marshall Tory por la Royal Society of Canada;
1977, se celebró una conferencia sobre teoría de grafos y temas relacionados en la Universidad de Waterloo en su honor con motivo de su sexagésimo cumpleaños;
1982, Premio Isaak-Walton-Killam del Consejo de Canadá ;
1987, miembro de la Royal Society (FRS);
1990-1996, primer presidente del Instituto de Combinatoria y sus Aplicaciones ; ^[33]
1998, Nombrado director honorario del Centro de Investigación Criptográfica Aplicada de la Universidad de Waterloo; ^[34]
2001, Oficial de la Orden de Canadá (OC);
2001, premio CRM-Fields-PIMS .
2016, Salón de la fama de la región de Waterloo ^[35]
2017, Waterloo, denominación de carreteras "William Tutte Way" ^[36]

Tutte se desempeñó como bibliotecario de la Real Sociedad Astronómica de Canadá en 1959-1960, y el asteroide 14989 Tutte (1997 UB7) recibió su nombre. ^[37]

Debido al trabajo de Tutte en Bletchley Park, el Establecimiento de Seguridad de las Comunicaciones de Canadá nombró una organización interna destinada a promover la investigación en criptología, el Instituto Tutte de Matemáticas y Computación (TIMC), en su honor en 2011. ^[38]

En septiembre de 2014, Tutte se celebró en su ciudad natal de Newmarket, Inglaterra, con la inauguración de una escultura, luego de que un periódico local comenzara una campaña para honrar su memoria. ^[39]

Bletchley Park en Milton Keynes celebró el trabajo de Tutte con una exposición Bill Tutte: Mathematician + Codebreaker de mayo de 2017 a 2019, precedida el 14 de mayo de 2017 por conferencias sobre su vida y obra durante el Simposio del Centenario de Bill Tutte. ^[40]^[41]

Vida personal y muerte

Además de los beneficios profesionales de trabajar en la nueva Universidad de Waterloo , el entorno más rural del condado de Waterloo atrajo a Bill y su esposa Dorothea. Compraron una casa en el pueblo cercano de West Montrose, Ontario, donde disfrutaron de las caminatas, pasaron tiempo en su jardín en el Grand River y permitieron que otros disfrutaran del hermoso paisaje de su propiedad.

También tenían un amplio conocimiento de todas las aves de su jardín. Dorothea, una ávida alfarera, también era una entusiasta excursionista y Bill organizaba excursiones de senderismo. Incluso cerca del final de su vida, Bill todavía era un ávido caminante. ^[7]^[42] Después de la muerte de su esposa en 1994, regresó a Newmarket (Suffolk), pero luego regresó a Waterloo en 2000, donde murió dos años después. ^[43] Está enterrado en el cementerio de West Montrose United. ^[28]^[44]

Seleccionar publicaciones

Libros

Tutte, WT (1966), Conectividad en gráficos , Exposiciones matemáticas, 15 , Toronto, Ontario: University of Toronto Press, Zbl 0146.45603
Tutte, WT (1966), Introducción a la teoría de las matroides , Santa Mónica, Calif .: Informe RAND Corporation R-446-PR. También Tutte, WT (1971), Introducción a la teoría de las matroides , Métodos analíticos y computacionales modernos en ciencia y matemáticas, 37 , Nueva York: American Elsevier Publishing Company, ISBN 978-0-444-00096-5, Zbl 0231.05027
Tutte, WT, ed. (1969), Progresos recientes en combinatoria. Actas de la tercera conferencia de Waterloo sobre combinatoria, mayo de 1968 , Nueva York-Londres: Academic Press, págs. Xiv + 347, ISBN 978-0-12-705150-5, Zbl 0192.33101
Tutte, WT (1979), McCarthy, D .; Stanton, RG (eds.), Artículos seleccionados de WT Tutte, Vols. Yo, II. , Winnipeg, Manitoba: Centro de Investigación Charles Babbage , St. Pierre, Manitoba, Canadá, págs. Xxi + 879, Zbl 0403.05028
- Volumen I: ISBN 978-0-969-07781-7
- Volumen II: ISBN 978-0-969-07782-4
Tutte, WT (1984), teoría de grafos , Enciclopedia de las matemáticas y sus aplicaciones, 21 , Menlo Park, California: Addison-Wesley Publishing Company, ISBN 978-0-201-13520-6, Zbl 0554.05001Reimpreso por Cambridge University Press 2001, ISBN 978-0-521-79489-3
Tutte, WT (1998), Teoría de grafos como la he conocido , ciclo de conferencias de Oxford sobre matemáticas y sus aplicaciones, 11 , Oxford: Clarendon Press, ISBN 978-0-19-850251-7, Zbl 0915.05041Reimpreso en 2012, ISBN 978-0-19-966055-1

Artículos

Brooks, RL ; Smith, CAB ; Stone, AH ; Tutte, WT (1940). "La disección de rectángulos en cuadrados". Duke Math. J . 7 : 312-340. doi : 10.1215 / s0012-7094-40-00718-9 .

Ver también

Geometría sistólica

Notas

↑ En terminología más reciente, cada impulso se denominaría un " bit " con una marca en binario 1 y un espacio en binario 0. La cinta de papel perforada tenía un agujero para una marca y ningún agujero para un espacio.
^ Por esta razón, el método 1 + 2 de Tutte a veces se denomina método de "doble delta".
^ Los cinco impulsos o bits de los caracteres codificados a veces se denominan cinco niveles.

Referencias

^ a b c W. T. Tutte en el Proyecto de genealogía matemática
↑ a b Hinsley y Stripp , 1993 , p. 8
↑ a b Brzezinski , 2005 , p. 18
^ a b c d Más joven de 2012
^ a b c O'Connor y Robertson 2003
^ Johnson, Will. "Matroides" (PDF) . Consultado el 16 de octubre de 2014 .
↑ a b c d Hobbs, Arthur M .; James G. Oxley (marzo de 2004). "William T. Tutte (1917-2002)" (PDF) . Avisos de la Sociedad Matemática Estadounidense . 51 (3): 322.
^ Escuela primaria Cheveley CofE, Park Road, Cheveley, Cambridgeshire, CB8 9DF http://www.cheveley.cambs.sch.uk/
^ Smith, Cedric AB; Abbott, Steve (marzo de 2003), "The Story of Blanche Descartes", The Mathematical Gazette , 87 (508): 23–33, doi : 10.1017 / S0025557200172067 , ISSN 0025-5572 , JSTOR 3620560 , S2CID 192758206
↑ a b Good, Michie y Timms , 1945 , p. 6 en 1. Introducción: Tunny alemán
^ Tutte 2006 , págs. 352–353
^ Hinsley, FH (2001) [1993]. "Introducción al pescado" . En FH Hinsley; Alan Stripp (eds.). Codebreakers: la historia interna de Bletchley Park . págs. 141-148. ISBN 0-19-280132-5.
^ Sale, Tony , The Lorenz Cipher y cómo Bletchley Park lo rompió , consultado el 21 de octubre de 2010
^ Tutte 2006 , p. 354
^ Bauer , 2006 , p. 375
^ Tutte 2006 , págs. 356–357
^ Copeland 2006 , págs. 348, 349
^ Tutte 2006 , p. 357
^ Singh, Simon , The Black Chamber , consultado el 28 de abril de 2012
^ Newman c. 1944 p. 387
^ Carter 2004 , p. 3
^ Tutte 1998 , págs. 7-8
^ Good, Michie & Timms 1945 , págs. 321–322 en 44. Métodos estadísticos manuales: Ajuste - Métodos estadísticos
↑ Budiansky , 2006 , págs. 58–59.
^ Copeland 2011
^ Younger, Dan (agosto de 2002). "Biografía del profesor Tutte" . Notas CMS . Consultado el 24 de junio de 2018 , a través de la Universidad de Waterloo.
^ Roberts, Jerry (2017), Lorenz: Rompiendo el código secreto de Hitler en Bletchley Park , Stroud, Gloucestershire: The History Press, ISBN 978-0-7509-7885-9
^ a b c d e https://uwaterloo.ca/combinatorics-and-optimization/about/professor-william-t-tutte/biography-professor-tutte
^ WT Tutte. Un algoritmo para determinar si una determinada matriz binaria es gráfica, Proceedings of the London Mathematical Society , 11 (1960) 905–917
^ WT Tutte. Cómo dibujar un gráfico. Actas de la London Mathematical Society, 13 (3): 743–768, 1963.
^ Steven J. Gortle; Craig Gotsman; Dylan Thurston. "Discrete One-Forms en mallas y aplicaciones para parametrización de mallas 3D", Diseño geométrico asistido por computadora , 23 (2006) 83–112
^ C. St. JA Nash-Williams , Una nota sobre algunos de los trabajos matemáticos del profesor Tutte, teoría de grafos y temas relacionados (eds. JA Bondy y US R Murty), Academic Press, Nueva York, 1979, p. xxvii.
^ "El Instituto de Combinatoria y sus aplicaciones" . ICA. Archivado desde el original el 2 de octubre de 2013 . Consultado el 28 de septiembre de 2013 .
^ "Tutte honrado por el centro criptográfico" . Universidad de Waterloo . Consultado el 28 de septiembre de 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
^ "Asteroide (14989) Tutte" . Real Sociedad Astronómica de Canadá. 14 de junio de 2011. Archivado desde el original el 4 de enero de 2015 . Consultado el 25 de septiembre de 2014 .
^ Freeze, Colin (7 de septiembre de 2011). "Instituto de alto secreto sale de las sombras para reclutar a los mejores talentos" . El globo y el correo . Toronto . Consultado el 25 de septiembre de 2014 .
^ "El monumento a Bill Tutte" . Fondo en memoria de Bill Tutte . Consultado el 13 de diciembre de 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. Archivado desde el original el 27 de septiembre de 2013 . Consultado el 21 de mayo de 2013 .
^ van der Vat, Dan (10 de mayo de 2002), "Obituario: William Tutte" , The Guardian , Londres , consultado el 28 de abril de 2013
^ http://geneofun.on.ca/names/photo/858001

Fuentes

Bauer, Friedrich L. (2006), La ruptura de TiltmanApéndice 5 en Copeland 2006 , págs. 370–377
Brzezinski, Zbigniew (2005), "The Unknown Victors", en Ciechanowski, Stanisław (ed.), Marian Rejewski, 1905-1980: living with the Enigma secret , Bydgoszcz, Polonia: Ayuntamiento de Bydgoszcz, págs. 15-18, ISBN 83-7208-117-4
Copeland, B. Jack , ed. (2006), Coloso: Los secretos de las computadoras de descifrado de códigos de Bletchley Park , Oxford: Oxford University Press, ISBN 978-0-19-284055-4
Copeland, B. Jack (2011), Coloso y el amanecer de la era de la informáticaen Erskine y Smith 2011 , págs. 305–327
Erskine, Ralph; Smith, Michael , eds. (2011) [2001], The Bletchley Park Codebreakers , Biteback Publishing Ltd, ISBN 978-1-84954-078-0Versión actualizada y ampliada de Action This Day: From Breaking of the Enigma Code to the Birth of the Modern Computer Bantam Press 2001
Bien, Jack ; Michie, Donald ; Timms, Geoffrey (1945), General Report on Tunny: With Emphasis on Statistical Methods , UK Public Record Office HW 25/4 y HW 25/5 , consultado el 15 de septiembre de 2010Esa versión es una copia facsímil, pero hay una transcripción de gran parte de este documento en formato '.pdf' en: Sale, Tony (2001), Parte del 'Informe general sobre Tunny', la historia de Newmanry, formateado por Tony Sale (PDF) , consultado el 20 de septiembre de 2010 , y una transcripción web de la Parte 1 en: Ellsbury, Graham, Informe general sobre Tunny con énfasis en métodos estadísticos , consultado el 3 de noviembre de 2010
Bueno, Jack (1993), Enigma y Fishen Hinsley y Stripp 1993 , págs. 149-166
Hinsley, FH ; Stripp, Alan, eds. (1993) [1992], Codebreakers: The inside story of Bletchley Park , Oxford: Oxford University Press, ISBN 978-0-19-280132-6
O'Connor, JJ; Robertson, EF (2003), MacTutor Biography: William Thomas Tutte , University of St Andrews , consultado el 28 de abril de 2013
Tutte, WT (19 de junio de 1998), Fish and I (PDF) , consultado el 7 de abril de 2012Transcripción de una conferencia impartida por el Prof. Tutte en la Universidad de Waterloo
Tutte, William T. (2006), Mi trabajo en Bletchley ParkApéndice 4 en Copeland 2006 , págs. 352–369
Ward, Mark (27 de mayo de 2011), "Code-cracking machine volvió a la vida" , BBC News , consultado el 28 de abril de 2013
Younger, DH (2012), Memorias biográficas de miembros de la Royal Society: William Thomas Tutte. 14 de mayo de 1917 - 2 de mayo de 2002 , The Royal Society, doi : 10.1098 / rsbm.2012.0036 , consultado el 28 de abril de 2013

enlaces externos

Profesor William T. Tutte
WT Tutte en el Proyecto de genealogía matemática
William Tutte, 84, matemático y descifrador de códigos, muere - Obituario de The New York Times
William Tutte: cerebro matemático anónimo - Obituario de The Guardian
Premio CRM-Fields-PIMS - 2001 - William T. Tutte
"60 Years in the Nets": conferencia (grabación de audio) impartida en el Fields Institute el 25 de octubre de 2001 con motivo de la recepción del premio CRM-Fields de 2001
La refutación de Tutte de la conjetura de Tait
"Los héroes olvidados de Bletchley" , Ian Douglas, The Daily Telegraph , 25 de diciembre de 2012
Murty, USR (2004), "Dedicación: Profesor WT Tutte", Journal of Combinatorial Theory , Serie B, 92 (2): 191-192, doi : 10.1016 / j.jctb.2004.08.002.
Younger, DH (2004), "Dedicación: Profesor WT Tutte", Journal of Combinatorial Theory , Serie B, 92 (2): 193-198, doi : 10.1016 / j.jctb.2004.09.002.

[17] En terminología más reciente, cada impulso se denominaría un " bit " con una marca en binario 1 y un espacio en binario 0. La cinta de papel perforada tenía un agujero para una marca y ningún agujero para un espacio.

[23] Por esta razón, el método 1 + 2 de Tutte a veces se denomina método de "doble delta".

[27] Los cinco impulsos o bits de los caracteres codificados a veces se denominan cinco niveles.

[MGP-1] W. T. Tutte en el Proyecto de genealogía matemática

[Hinsley_1993_8-2] Hinsley y Stripp , 1993 , p. 8

[Brzezinski_2005_18-3] Brzezinski , 2005 , p. 18

[frs-4] Más joven de 2012

[MacTutorBiog-5] O'Connor y Robertson 2003

[6] Johnson, Will. "Matroides" (PDF) . Consultado el 16 de octubre de 2014 .

[Hobbs_2004_322-7] Hobbs, Arthur M .; James G. Oxley (marzo de 2004). "William T. Tutte (1917-2002)" (PDF) . Avisos de la Sociedad Matemática Estadounidense . 51 (3): 322.

[8] Escuela primaria Cheveley CofE, Park Road, Cheveley, Cambridgeshire, CB8 9DF http://www.cheveley.cambs.sch.uk/

[9] Smith, Cedric AB; Abbott, Steve (marzo de 2003), "The Story of Blanche Descartes", The Mathematical Gazette , 87 (508): 23–33, doi : 10.1017 / S0025557200172067 , ISSN 0025-5572 , JSTOR 3620560 , S2CID 192758206

[GRoT11B6-10] Good, Michie y Timms , 1945 , p. 6 en 1. Introducción: Tunny alemán

[11] Tutte 2006 , págs. 352–353

[12] Hinsley, FH (2001) [1993]. "Introducción al pescado" . En FH Hinsley; Alan Stripp (eds.). Codebreakers: la historia interna de Bletchley Park . págs. 141-148. ISBN 0-19-280132-5.

[Sale-13] Sale, Tony , The Lorenz Cipher y cómo Bletchley Park lo rompió , consultado el 21 de octubre de 2010

[14] Tutte 2006 , p. 354

[15] Bauer , 2006 , p. 375

[16] Tutte 2006 , págs. 356–357

[18] Copeland 2006 , págs. 348, 349

[19] Tutte 2006 , p. 357

[20] Singh, Simon , The Black Chamber , consultado el 28 de abril de 2012

[21] Newman c. 1944 p. 387

[22] Carter 2004 , p. 3

[24] Tutte 1998 , págs. 7-8

[25] Good, Michie & Timms 1945 , págs. 321–322 en 44. Métodos estadísticos manuales: Ajuste - Métodos estadísticos

[26] Budiansky , 2006 , págs. 58–59.

[28] Copeland 2011

[29] Younger, Dan (agosto de 2002). "Biografía del profesor Tutte" . Notas CMS . Consultado el 24 de junio de 2018 , a través de la Universidad de Waterloo.

[30] Roberts, Jerry (2017), Lorenz: Rompiendo el código secreto de Hitler en Bletchley Park , Stroud, Gloucestershire: The History Press, ISBN 978-0-7509-7885-9

[uwaterloo.ca-31] ttps://uwaterloo.ca/combinatorics-and-optimization/about/professor-william-t-tutte/biography-professor-tutte

[32] WT Tutte. Un algoritmo para determinar si una determinada matriz binaria es gráfica, Proceedings of the London Mathematical Society , 11 (1960) 905–917

[33] WT Tutte. Cómo dibujar un gráfico. Actas de la London Mathematical Society, 13 (3): 743–768, 1963.

[34] Steven J. Gortle; Craig Gotsman; Dylan Thurston. "Discrete One-Forms en mallas y aplicaciones para parametrización de mallas 3D", Diseño geométrico asistido por computadora , 23 (2006) 83–112

[35] C. St. JA Nash-Williams , Una nota sobre algunos de los trabajos matemáticos del profesor Tutte, teoría de grafos y temas relacionados (eds. JA Bondy y US R Murty), Academic Press, Nueva York, 1979, p. xxvii.

[36] "El Instituto de Combinatoria y sus aplicaciones" . ICA. Archivado desde el original el 2 de octubre de 2013 . Consultado el 28 de septiembre de 2013 .

[37] "Tutte honrado por el centro criptográfico" . Universidad de Waterloo . Consultado el 28 de septiembre de 2013 .

[38] ttps://uwaterloo.ca/combinatorics-and-optimization/news/bill-tutte-inducted-waterloo-region-hall-fame

[39] ttps://uwaterloo.ca/stories/mathematics-professor-and-wartime-code-breaker-honoured

[40] "Asteroide (14989) Tutte" . Real Sociedad Astronómica de Canadá. 14 de junio de 2011. Archivado desde el original el 4 de enero de 2015 . Consultado el 25 de septiembre de 2014 .

[41] Freeze, Colin (7 de septiembre de 2011). "Instituto de alto secreto sale de las sombras para reclutar a los mejores talentos" . El globo y el correo . Toronto . Consultado el 25 de septiembre de 2014 .

[42] "El monumento a Bill Tutte" . Fondo en memoria de Bill Tutte . Consultado el 13 de diciembre de 2014 .

[43] ttps://uwaterloo.ca/combinatorics-and-optimization/news/bill-tutte-centenary-symposium-bletchley-park-0

[44] ttps://www.bletchleypark.org.uk/news/codebreaker-bill-tutte-to-be-celebrated-in-centenary-exhibition

[45] "Bill Tutte" . Telegraph Group Limited. Archivado desde el original el 27 de septiembre de 2013 . Consultado el 21 de mayo de 2013 .

[46] van der Vat, Dan (10 de mayo de 2002), "Obituario: William Tutte" , The Guardian , Londres , consultado el 28 de abril de 2013

[47] ttp://geneofun.on.ca/names/photo/858001

[1]