Вільям Татт

Народився 14 травня 1917 року в місті Ньюмаркет у Саффолку, в сім'ї садівника. Отримав ступінь бакалавра за фахом хімія в Триніті-коледж (Кембридж). В аспірантурі продовжив вивчати фізичну хімію, але перевівся на математику в кінці 1940 року. У 1941 отримав ступінь магістра.[5]

Незабаром після початку Другої світової війни учитель Татта, Партік Дафф, порекомендував його в Центр урядового зв'язку в Блечлі-Парк. Після інтерв'ю пройшов навчальні курси в Лондоні й зрештою приєднався до науково-дослідної роботи в Блечлі-Парку. Спочатку працював над однією з шифрувальних машин Гагеліна, що використовувалася італійським військово-морським флотом. Це була роторна шифрувальна машина, доступна в промислових масштабах, тому механізми кодування були заздалегідь відомі, і дешифрування повідомлень полягало тільки у визначенні конфігурації машини.[6]

Аналіз шифру Лоренца

Машина Лоренца SZ42 без верхньої кришки

31 серпня 1941 року німецький оператор надіслав повідомлення розміром 4500 знаків. Повідомлення було отримано з помилками, після чого його було передано повторно з невеликими змінами, але з тим же самим ключем. Це дозволило Джону Тільтману, ветерану Блетчлі-Парку, ідентифікувати шифр передачі як шифр Вернама, і отримати текст двох повідомлень з ключем. Після безрезультатних спроб криптоаналітиків зламати код машини, наявна інформація була передана Татту для подальшої роботи.[6] Татт почав розшифровку з використання методу Казіскі, що полягає в пошуку груп символів, які повторюються в зашифрованому тексті. За допомогою нього він встановив, що довжина ключового слова дорівнює 41 символу.[7] Цю компоненту ключа Татт назвав ${\displaystyle \chi }$₁ (хі₁). Однак, було ясно, що реалізація ключа складніша, тобто що існувала й інша компонента, яку він назвав ${\displaystyle \psi }$₁ (псі₁). Таким чином, машина складалася з ${\displaystyle \psi }$ и ${\displaystyle \chi }$ дисків, що генерували кожні п'ять біт символу. Татт з'ясував, що компоненти ключа ${\displaystyle \psi }$ та ${\displaystyle \chi }$ поєднувалися функцією XOR. Тобто для кожного символу ключ K можна було представити в такий спосіб:

K = ${\displaystyle \chi }$ ⊕ ${\displaystyle \psi }$

Після того, як Татт зробив висновок про ${\displaystyle \psi }$-компоненту, інші дослідники приєдналися до вивчення структури машини.

Протягом наступних двох місяців Татт і інші члени дослідницької групи Блетчлі-Парку відновлювали логічну структуру шифрувальної машини. [8]

Захистив докторську дисертацію з математики в Кембриджі в 1948 році під керівництвом Шона Вайлі, який також працював над машиною Танні в Блечлі-Парку. У тому ж році Татт отримав роботу в університеті Торонто на запрошення Гарольда Коксетера. У 1962 перейшов в університет Ватерлоо в Онтаріо, де пропрацював до кінця своєї академічної кар'єри. Офіційно вийшов на пенсію в 1985 році, але продовжував активну діяльність як заслужений професор. Брав участь у заснуванні Факультету комбінаторики і оптимізації в Університеті Ватерлоо. Його математична кар'єра була сконцентрована на комбінаториці, особливо на теорії графів і вивченні матроїдів.

Був головним редактором Журналу теорії комбінаторики і працював в редакційних колегіях деяких інших математичних журналів. В теорії графів Татт працював над такими проблемами, як структури циклів, максимальний розмір паросполучень, факторизація графів, гамільтонові та негамільтонові графи. Перші основні досягнення в теорії матроїдів зроблені Таттом в його дисертації в Кембриджі в 1948 році. Крім того, він активно розробляв методи і теореми побудови різних видів графів[9].

Роботи Тата протягом Другої світової війни і роботи з комбінаторики принесли йому велику кількість почестей і нагород.

• 1958 — член Королівського товариства Канади;
• 1971 — премія Джефрі-Вільямса Канадського математичного товариства;
• 1975 — медаль Генрі Маршалла Торі королівського товариства Канади;
• 1987 — член Лондонського королівського товариства;
• 1998 — призначений почесним директором Центру прикладних Криптографічних Досліджень Університету Ватерлоо[10]
• 2001 — Офіцер Ордена Канади;
• 2001 — CRM-Fields-PIMS prize.

Працював бібліотекарем в Королівському астрономічному суспільстві Канади в 1959—1960, і на його честь було названо астероїд 14989 Татт.

У 2011 році, на знак подяки за роботу Татта в Блетчлі-Парку, Центр безпеки комунікацій Канади назвав на його честь цілу організацію — Інститут математики і обчислень імені В. Т. Татта.[11]

У вересні 2014 в Ньюмаркеті, рідному місті Татта, встановлена скульптура на його честь.

Після того, як Татт прийняв запрошення на роботу від Університету Ватерлоо, він і його дружина Доротея купили будинок в сусідньому селі Вест Монтроуз, Онтаріо. Після смерті дружини в 1994, повернувся жити в рідній Ньюмаркет, але потім знову переїхав в Ватерлоо у 2000 році, де помер два роки потому.[12] Похований на кладовищі Вест Монтроуз в 2002 році.[13]

• Tutte, W. T. (1966). Connectivity in graphs. Mathematical expositions 15. Toronto, Ontario: University of Toronto Press. Zbl 0146.45603.
• Tutte, W. T. (1966). Introduction to the theory of matroids. Santa Monica, Calif.: RAND Corporation report R-446-PR.. Also Tutte, W. T. (1971). Introduction to the theory of matroids. Modern analytic and computational methods in science and mathematics 37. New York: American Elsevier Publishing Company. ISBN 978-0-444-00096-5. Zbl 0231.05027.
• Tutte, W. T., ред. (1969). Recent progress in combinatorics. Proceedings of the third Waterloo conference on combinatorics, May 1968. New York-London: Academic Press. с. xiv+347. ISBN 978-0-12-705150-5. Zbl 0192.33101.
• Tutte, W. T. (1979). У McCarthy, D.; Stanton, R. G. Selected papers of W.T. Tutte, Vols. I, II. Winnipeg, Manitoba: Charles Babbage Research Centre, St. Pierre, Manitoba, Canada. с. xxi+879. Zbl 0403.05028.
  • Volume I: ISBN 978-0-969-07781-7
  • Volume II: ISBN 978-0-969-07782-4
• Tutte, W. T. (1984). Graph theory. Encyclopedia of mathematics and its applications 21. Menlo Park, California: Addison-Wesley Publishing Company. ISBN 978-0-201-13520-6. Zbl 0554.05001. Reprinted by Cambridge University Press 2001, ISBN 978-0-521-79489-3
• Tutte, W. T. (1998). Graph theory as I have known it. Oxford lecture series in mathematics and its applications 11. Oxford: Clarendon Press. ISBN 978-0-19-850251-7. Zbl 0915.05041. Reprinted 2012, ISBN 978-0-19-966055-1

• Гіпотеза Тета (теорія графів)

• Jack Copeland. Colossus: The Secrets of Bletchley Park's Codebreaking Computers. — Oxford : Oxford University Press, 2006. — 287 с. — ISBN 978-0-19-284055-4.

• Ralph Eskrine, Michael Smith. The Bletchley Park Codebreakers. — Biteback Publishing Ltd, 2011. — ISBN 978-1-84954-078-0.

• Nigel West. Historical Dictionary of Naval Intelligence. — Scarecrow Press, 2010. — ISBN 9780810873773.

• J. O'Connor, E.F. Robertson. MacTutor Biography: William Thomas Tutte. — University of St Andrews, 2003. Процитовано 28 April 2013.

• Mark Ward. Code-cracking machine returned to life. — BBC News. Процитовано 28 April 2013.