WT Tutte - W. T. Tutte

WT Tutte
WT Tutte.jpg
Nascer ( 14/05/1917 )14 de maio de 1917
Newmarket, Suffolk , Inglaterra
Faleceu 2 de maio de 2002 (02/05/2002)(com 84 anos)
Kitchener , Ontário, Canadá
Alma mater Trinity College, Cambridge ( PhD )
Conhecido por
Cônjuge (s) Dorothea Geraldine Mitchell (m. 1949–1994, sua morte)
Prêmios
Carreira científica
Campos Matemática
Instituições University of Toronto
University of Waterloo
Tese An Algebraic Theory of Graphs  (1948)
Orientador de doutorado Shaun Wylie
Alunos de doutorado

William Thomas Tutte OC FRS FRSC ( / t ʌ t / ; 14 de maio de 1917 - 2 de maio de 2002) foi um decifrador de códigos e matemático inglês e canadense . Durante a Segunda Guerra Mundial , ele fez um avanço brilhante e fundamental na criptoanálise da cifra Lorenz , um importante sistema de cifras alemão nazista usado para comunicações ultrassecretas dentro do Alto Comando da Wehrmacht . A natureza estratégica de alto nível da inteligência obtida a partir da descoberta crucial de Tutte, na descriptografia em massa das mensagens criptografadas por Lorenz, especificamente, contribuiu muito, e talvez até de forma decisiva, para a derrota da Alemanha nazista. Ele também teve uma série de realizações matemáticas significativas, incluindo trabalhos básicos nos campos da teoria dos grafos e da teoria matróide .

A pesquisa de Tutte no campo da teoria dos grafos provou ser de notável importância. Em uma época em que a teoria dos grafos ainda era um assunto primitivo, Tutte começou o estudo das matróides e as desenvolveu em uma teoria expandindo a partir do trabalho que Hassler Whitney havia desenvolvido pela primeira vez em meados da década de 1930. Embora as contribuições de Tutte para a teoria dos grafos tenham sido influentes para a teoria dos grafos moderna e muitos de seus teoremas tenham sido usados ​​para continuar fazendo avanços no campo, a maior parte de sua terminologia não estava de acordo com seu uso convencional e, portanto, sua terminologia não é usada por teóricos de grafos hoje. "Tutte avançou a teoria dos grafos de um assunto com um texto ( D. Kőnig ) em direção ao seu atual estado extremamente ativo."

Infância e educação

Tutte nasceu em Newmarket em Suffolk. Ele era o filho mais novo de William John Tutte (1873–1944), um jardineiro de propriedade, e Annie ( nascida Newell; 1881–1956), uma governanta. Ambos os pais trabalhavam nos estábulos da Fitzroy House, onde Tutte nasceu. A família passou algum tempo em Buckinghamshire, County Durham e Yorkshire antes de retornar a Newmarket, onde Tutte frequentou a escola primária da Igreja Cheveley da Inglaterra, na vila próxima de Cheveley. Em 1927, quando tinha dez anos, Tutte ganhou uma bolsa de estudos para Cambridge e County High School for Boys . Ele assumiu seu lugar lá em 1928.

Em 1935, ele ganhou uma bolsa para estudar ciências naturais no Trinity College, Cambridge , onde se especializou em química e se formou com honras de primeira classe em 1938. Ele continuou com a química física como aluno de graduação, mas transferiu-se para a matemática no final de 1940 Como estudante, ele (junto com três de seus amigos) foi um dos primeiros a resolver o problema da quadratura do quadrado e o primeiro a resolver o problema sem um sub-retângulo quadrado. Juntos, os quatro criaram o pseudônimo Blanche Descartes , sob o qual Tutte publicou ocasionalmente durante anos.

Segunda Guerra Mundial

As máquinas Lorenz SZ tinham 12 rodas, cada uma com um número diferente de cames (ou "pinos").
Número da roda 1 2 3 4 5 6 7 8 9 10 11 12
Nome da roda BP 1 2 3 4 5 37 61 1 2 3 4 5
Número de cames (pinos) 43 47 51 53 59 37 61 41 31 29 26 23

Logo após a eclosão da Segunda Guerra Mundial , o tutor de Tutte, Patrick Duff, o sugeriu para trabalhar na guerra no Código do Governo e na Escola Cypher em Bletchley Park (BP). Ele foi entrevistado e enviado para um curso de treinamento em Londres antes de ir para Bletchley Park, onde ingressou na Seção de Pesquisa. No início, ele trabalhou na cifra de Hagelin que estava sendo usada pela Marinha italiana. Esta era uma máquina de criptografia de rotor que estava disponível comercialmente, então a mecânica da criptografia era conhecida, e descriptografar as mensagens só exigia descobrir como a máquina estava configurada.

No verão de 1941, Tutte foi transferido para trabalhar em um projeto chamado Fish. Informações de inteligência revelaram que os alemães chamavam os sistemas de transmissão de teleimpressora sem fio de "Sägefisch" (peixe-serra). Isso levou os britânicos a usar o código Fish para o sistema de cifras do teleprinter alemão. O apelido Tunny (atum) foi usado para o primeiro link não Morse e, posteriormente, para as máquinas Lorenz SZ e o tráfego que elas codificaram.

A telegrafia usou o Alfabeto de Telegrafia Internacional de 5 bits (ITA2). Nada se sabia sobre o mecanismo de codificação, a não ser que as mensagens eram precedidas por um indicador de 12 letras , o que implicava uma máquina de criptografia de rotor de 12 rodas. O primeiro passo, portanto, tinha que ser diagnosticar a máquina estabelecendo a estrutura lógica e, portanto, o funcionamento da máquina. Tutte desempenhou um papel fundamental nessa conquista, e foi pouco antes da vitória dos Aliados na Europa em 1945 que Bletchley Park adquiriu uma máquina de criptografia Tunny Lorenz . Os avanços de Tutte acabaram por levar à decodificação em massa de mensagens criptografadas por Tunny entre o Alto Comando Alemão (OKW) em Berlim e seus comandos do exército em toda a Europa ocupada e contribuíram - talvez de forma decisiva - para a derrota da Alemanha.

Diagnosticando a máquina de cifragem

Em 31 de agosto de 1941, duas versões da mesma mensagem foram enviadas usando chaves idênticas, o que constituiu uma " profundidade ". Isso permitiu a John Tiltman , veterano e criptoanalista notavelmente talentoso de Bletchley Park, deduzir que se tratava de uma cifra Vernam que usa a função Exclusive Or (XOR) (simbolizada por "⊕") e extrair as duas mensagens e, portanto, obter a chave obscurecida . Depois de um período infrutífero durante o qual criptoanalistas da Seção de Pesquisa tentaram descobrir como a máquina Tunny funcionava, esta e algumas outras chaves foram entregues a Tutte, que foi convidado a "ver o que você pode fazer com elas".

A máquina Lorenz SZ42 com as tampas removidas. Museu Bletchley Park

Em seu curso de treinamento, Tutte aprendera a técnica do exame Kasiski de escrever uma chave em papel quadrado, iniciando uma nova linha após um número definido de caracteres que se suspeitava ser a frequência de repetição da chave. Se esse número estivesse correto, as colunas da matriz mostrariam mais repetições de sequências de caracteres do que apenas o acaso. Tutte sabia que os indicadores Tunny usavam 25 letras (excluindo J) para 11 das posições, mas apenas 23 letras para a outra. Ele então experimentou a técnica de Kasiski no primeiro impulso dos personagens-chave, usando uma repetição de 25 × 23 = 575. Ele não observou um grande número de repetições de coluna com este período, mas observou o fenômeno na diagonal. Ele, portanto, tentou novamente com 574, que apareceu repetições nas colunas. Reconhecendo que os fatores primos deste número são 2, 7 e 41, ele tentou novamente com um período de 41 e "obteve um retângulo de pontos e cruzes repleto de repetições".

Estava claro, entretanto, que o primeiro impulso da chave era mais complicado do que aquele produzido por uma única roda de 41 impulsos chave. Tutte chamou esse componente da chave de 1 ( chi 1 ). Ele percebeu que havia outro componente, que era XOR-ed com isso, que nem sempre mudava a cada novo personagem, e que era o produto de uma roda que ele chamou de 1 ( psi 1 ). O mesmo se aplica a cada um dos cinco impulsos ( 1 2 3 4 5 e 1 2 3 4 5 ). Portanto, para um único caractere, toda a chave K consistia em dois componentes:

K =

No Bletchley Park, os impulsos de marca eram representados por x e os impulsos espaciais por . Por exemplo, a letra "H" seria codificada como •• x • x . A derivação de Tutte dos componentes chi e psi foi possibilitada pelo fato de que os pontos eram mais prováveis ​​de serem seguidos por pontos, e as cruzes eram mais prováveis ​​de serem seguidas por cruzes. Este foi o produto de uma fraqueza na configuração-chave alemã, que mais tarde eles eliminaram. Depois que Tutte fez essa descoberta, o resto da Seção de Pesquisa se juntou para estudar os outros impulsos, e foi estabelecido que todas as cinco rodas chi avançavam com cada novo personagem e que as cinco rodas psi se moviam juntas sob o controle de dois rodas mu ou "motorizadas". Nos dois meses seguintes, Tutte e outros membros da Seção de Pesquisa elaboraram a estrutura lógica completa da máquina, com seu conjunto de rodas com cames que poderiam estar em uma posição (elevada) que adicionasse x ao fluxo de personagens principais , ou na posição alternativa adicionada em .

Diagnosticar o funcionamento da máquina Tunny desta forma foi uma conquista criptanalítica verdadeiramente notável que, na citação para a indução de Tutte como oficial da Ordem do Canadá , foi descrita como "um dos maiores feitos intelectuais da Segunda Guerra Mundial".

Método estatístico de Tutte

Para descriptografar uma mensagem Tunny, era necessário conhecimento não apenas do funcionamento lógico da máquina, mas também das posições iniciais de cada rotor para a mensagem específica. Procurava-se então um processo que manipulasse o texto cifrado ou chave para produzir uma distribuição de frequência de caracteres que partisse da uniformidade que o processo de cifragem pretendia atingir. Enquanto estava destacado para a Seção de Pesquisa em julho de 1942, Alan Turing descobriu que a combinação XOR dos valores de caracteres sucessivos em um fluxo de texto cifrado e chave enfatizava qualquer desvio de uma distribuição uniforme. O fluxo resultante (simbolizado pela letra grega "delta" Δ ) foi chamado de diferença porque XOR é o mesmo que a subtração do módulo 2.

O motivo pelo qual isso forneceu um caminho para Tunny foi que, embora a distribuição de frequência de caracteres no texto cifrado não pudesse ser distinguida de um fluxo aleatório, o mesmo não era verdade para uma versão do texto cifrado do qual o elemento chi da chave tinha sido removido. Esse era o caso porque onde o texto simples continha um caractere repetido e as rodas psi não se moviam, o caractere psi diferenciado ( Δ ) seria o caractere nulo (' / ' em Bletchley Park). Quando XOR-ed com qualquer caractere, este caractere não tem efeito. Os caracteres repetidos no texto simples eram mais frequentes devido às características do alemão (EE, TT, LL e SS são relativamente comuns) e porque os telegrafistas frequentemente repetiam os caracteres de deslocamento de números e letras como sua perda em uma mensagem telegráfica comum pode levar a rabiscos.

Para citar o Relatório Geral sobre Tunny:

Turingery introduziu o princípio de que a chave diferenciada em um, agora chamada de ΔΚ , poderia produzir informações que não podiam ser obtidas na chave comum. Este princípio Δ seria a base fundamental de quase todos os métodos estatísticos de quebra e ajuste de rodas.

Tutte explorou essa amplificação da não uniformidade nos valores diferenciados e, em novembro de 1942, produziu uma maneira de descobrir os pontos de partida da roda da máquina Tunny que ficou conhecida como "Método Estatístico". A essência desse método era encontrar as configurações iniciais do componente chi da chave, tentando exaustivamente todas as posições de sua combinação com o texto cifrado e procurando evidências da não uniformidade que refletia as características do texto simples original. Porque quaisquer caracteres repetidos no texto simples sempre gerariam e, da mesma forma, ∆ 1 ⊕ ∆ 2 geraria sempre que as rodas psi não se movessem, e cerca de metade das vezes quando o faziam - cerca de 70% no geral.

Além de aplicar a diferenciação aos caracteres completos de 5 bits do código ITA2, Tutte a aplicou aos impulsos (bits) individuais. As configurações atuais do came da roda chi precisavam ser estabelecidas para permitir que a sequência relevante de caracteres das rodas chi fosse gerada. Era totalmente impraticável gerar os 22 milhões de caracteres de todas as cinco rodas chi , então inicialmente foi limitado a 41 × 31 = 1271 das duas primeiras. Depois de explicar suas descobertas a Max Newman , Newman recebeu a tarefa de desenvolver uma abordagem automatizada para comparar o texto cifrado e a chave para procurar desvios da aleatoriedade. A primeira máquina foi apelidada de Heath Robinson , mas o computador Colossus , muito mais rápido , desenvolvido por Tommy Flowers e usando algoritmos escritos por Tutte e seus colegas, logo assumiu o comando da quebra de códigos.

Doutorado e carreira

Tutte completou um doutorado em matemática em Cambridge em 1948 sob a supervisão de Shaun Wylie , que também havia trabalhado em Bletchley Park em Tunny. No final de 1945, Tutte retomou seus estudos em Cambridge, agora como estudante de graduação em matemática. Ele publicou alguns trabalhos iniciados anteriormente, um agora famoso artigo que caracteriza quais gráficos têm uma correspondência perfeita e outro que constrói um gráfico não hamiltoniano. Ele elaborou uma tese de doutorado inovadora, “An Algebraic Theory of Graphs” (Texto Completo), sobre o assunto mais tarde conhecido como teoria matróide.

No mesmo ano, a convite de Harold Scott MacDonald Coxeter , ele aceitou um cargo na Universidade de Toronto . Em 1962, mudou-se para a Universidade de Waterloo em Waterloo , Ontário, onde permaneceu pelo resto de sua carreira acadêmica. Ele se aposentou oficialmente em 1985, mas permaneceu ativo como professor emérito. Tutte ajudou a fundar o Departamento de Combinatória e Otimização da Universidade de Waterloo.

Sua carreira matemática concentrou-se em combinatória , especialmente teoria dos grafos , que ele é creditado como tendo ajudado a criar em sua forma moderna, e teoria matróide , para a qual fez contribuições profundas; um colega o descreveu como "o matemático líder em combinatória por três décadas". Ele foi editor-chefe do Journal of Combinatorial Theory até se aposentar de Waterloo em 1985. Ele também atuou no conselho editorial de várias outras revistas de pesquisa matemática.

Contribuições de pesquisa

O trabalho de Tutte em teoria dos grafos inclui a estrutura de espaços de ciclo e espaços de corte , o tamanho das correspondências máximas e a existência de fatores k em gráficos e gráficos hamiltonianos e não hamiltonianos. Ele refutou a conjectura de Tait , sobre a Hamiltonicidade dos gráficos poliédricos , usando a construção conhecida como fragmento de Tutte . A prova final do teorema das quatro cores fez uso de seu trabalho anterior. O polinômio de gráfico que ele chamou de "dicromato" tornou-se famoso e influente sob o nome de polinômio de Tutte e serve como o protótipo de invariantes combinatórios que são universais para todos os invariantes que satisfazem uma lei de redução especificada.

Os primeiros avanços importantes na teoria dos matróides foram feitos por Tutte em sua tese de doutorado em Cambridge de 1948, que formou a base de uma importante sequência de artigos publicados nas duas décadas seguintes. O trabalho de Tutte em teoria dos grafos e teoria matróide tem sido profundamente influente no desenvolvimento tanto do conteúdo quanto da direção desses dois campos. Na teoria matróide, ele descobriu o altamente sofisticado teorema da homotopia e fundou os estudos de grupos em cadeia e matróides regulares , sobre os quais provou resultados profundos.

Além disso, Tutte desenvolveu um algoritmo para determinar se uma dada matróide binária é uma matróide gráfica . O algoritmo faz uso do fato de que um gráfico planar é simplesmente um gráfico cujo circuito-matróide, o dual de sua ligação-matróide , é gráfico.

Tutte escreveu um artigo intitulado How to Draw a Graph no qual ele provou que qualquer face em um gráfico de 3 conexões está envolvida por um ciclo periférico . Usando esse fato, Tutte desenvolveu uma prova alternativa para mostrar que todo grafo de Kuratowski é não-planar, mostrando que K 5 e K 3,3 têm, cada um, três ciclos periféricos distintos com uma aresta comum. Além de usar ciclos periféricos para provar que os gráficos de Kuratowski não são planos, Tutte provou que todo gráfico simples de 3 conexões pode ser desenhado com todas as suas faces convexas e desenvolveu um algoritmo que constrói o desenho do plano resolvendo um sistema linear. O desenho resultante é conhecido como incorporação de Tutte . O algoritmo de Tutte faz uso dos mapeamentos baricêntricos dos circuitos periféricos de um gráfico 3-conectado simples.

As descobertas publicadas neste artigo provaram ser muito significativas porque os algoritmos que Tutte desenvolveu se tornaram métodos populares de desenho de gráficos planares. Uma das razões pelas quais a incorporação de Tutte é popular é que os cálculos necessários que são realizados por seus algoritmos são simples e garantem uma correspondência um a um de um gráfico e sua incorporação no plano euclidiano , o que é importante na parametrização uma malha tridimensional para o plano na modelagem geométrica. "O teorema de Tutte é a base para soluções para outros problemas de computação gráfica, como metamorfose ."

Tutte foi o principal responsável pelo desenvolvimento da teoria da enumeração de grafos planares, que tem ligações estreitas com polinômios cromáticos e dicromáticos. Este trabalho envolveu algumas técnicas altamente inovadoras de sua própria invenção, exigindo considerável destreza manipulativa no manuseio de séries de potências (cujos coeficientes contam tipos apropriados de gráficos) e as funções decorrentes de suas somas, bem como destreza geométrica em extrair essas séries de potências do gráfico -Situação teórica.

Tutte resumiu seu trabalho em Selected Papers of WT Tutte , 1979, e em Graph Theory como eu a conheci , 1998.

Cargos, honras e prêmios

O trabalho de Tutte na Segunda Guerra Mundial e, posteriormente, em combinatória lhe rendeu vários cargos, honras e prêmios:

Tutte serviu como bibliotecário para a Royal Astronomical Society of Canada em 1959–1960, e o asteroide 14989 Tutte (1997 UB7) foi nomeado em sua homenagem.

Por causa do trabalho de Tutte em Bletchley Park, o Communications Security Establishment do Canadá nomeou uma organização interna destinada a promover a pesquisa em criptologia, o Tutte Institute for Mathematics and Computing (TIMC), em sua homenagem em 2011.

Em setembro de 2014, Tutte foi comemorado em sua cidade natal, Newmarket, na Inglaterra, com a inauguração de uma escultura, após um jornal local iniciar uma campanha para homenagear sua memória.

Bletchley Park em Milton Keynes celebrou o trabalho de Tutte com a exposição Bill Tutte: Matemático + Codebreaker de maio de 2017 a 2019, precedida em 14 de maio de 2017 por palestras sobre sua vida e obra durante o Simpósio do Centenário Bill Tutte.

Vida pessoal e morte

Além dos benefícios de carreira de trabalhar na nova Universidade de Waterloo , o ambiente mais rural do condado de Waterloo atraiu Bill e sua esposa Dorothea. Eles compraram uma casa na vila próxima de West Montrose, Ontário, onde gostavam de fazer caminhadas, passar o tempo em seu jardim no Grand River e permitir que outras pessoas desfrutassem da bela paisagem de sua propriedade.

Eles também tinham um amplo conhecimento de todos os pássaros de seu jardim. Dorothea, uma oleira ávida, também era uma grande caminhante e Bill organizou caminhadas. Mesmo perto do fim de sua vida, Bill ainda era um caminhante ávido. Depois que sua esposa morreu em 1994, ele voltou para Newmarket (Suffolk), mas voltou para Waterloo em 2000, onde morreu dois anos depois. Ele está enterrado no cemitério West Montrose United.

Selecione as publicações

Livros

  • Tutte, WT (1966), Connectivity in graphs , Mathematical expositions, 15 , Toronto, Ontario: University of Toronto Press, Zbl  0146.45603
  • Tutte, WT (1966), Introdução à teoria dos matróides , Santa Monica, Califórnia: RAND Corporation report R-446-PR. Também Tutte, WT (1971), Introdução à teoria dos matróides , Métodos analíticos e computacionais modernos em ciências e matemática, 37 , Nova York: American Elsevier Publishing Company, ISBN 978-0-444-00096-5, Zbl  0231.05027
  • Tutte, WT, ed. (1969), Recent progress in combinatorics. Proceedings of the 3rd Waterloo conference on combinatorics, May 1968 , New York-London: Academic Press, pp. Xiv + 347, ISBN 978-0-12-705150-5, Zbl  0192.33101
  • Tutte, WT (1979), McCarthy, D .; Stanton, RG (eds.), Selected papers of WT Tutte, Vols. I, II. , Winnipeg, Manitoba: Charles Babbage Research Centre , St. Pierre, Manitoba, Canadá, pp. Xxi + 879, Zbl  0403.05028
  • Tutte, WT (1984), teoria dos grafos , Enciclopédia da matemática e suas aplicações, 21 , Menlo Park, Califórnia: Addison-Wesley Publishing Company, ISBN 978-0-201-13520-6, Zbl  0554.05001Reimpresso por Cambridge University Press 2001, ISBN  978-0-521-79489-3
  • Tutte, WT (1998), teoria dos grafos como a conheci , série de palestras de Oxford em matemática e suas aplicações, 11 , Oxford: Clarendon Press, ISBN 978-0-19-850251-7, Zbl  0915.05041Reimpresso em 2012, ISBN  978-0-19-966055-1

Artigos

Veja também

Notas

Referências

Fontes

links externos