Витани, Паул

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Паул Витани
Paul Vitányi
Паул Витани в 2005
Паул Витани в 2005
Дата рождения 21 июня 1944(1944-06-21) (79 лет)
Место рождения Будапешт
Страна
Научная сфера информатика
Место работы CWI, UvA
Альма-матер Свободный университет Амстердама
Учёная степень
доктор философии (PhD) по математике [1]
Учёное звание профессор
Научный руководитель Яко де Баккер,
Арто Саломаа[2]
Ученики Рональд Крамер,
Петер Грюнвальд,
Рональд де Волф[2]
Награды и премии Рыцарь Великого креста, академик, CWI Fellow
Автограф Есть в документах, связанных с Паулом Витани в архиве академика Ершова
Сайт homepages.cwi.nl/~paulv

Паул Михаэл Бела Витани (Paul Michael Béla Vitányi) — выдающийся нидерландский учёный в области теоретической информатики, теории алгоритмов и вычислительной сложности, профессор университета Амстердама и научный сотрудник Центра математики и информатики. Витани по матери голландец, а по отцу венгр.

Паул Витани получил диплом инженера в 1971 году в Делфтском техническом университете, в том же году поступил в аспирантуру в Математический центр в Амстердаме, где работает и до сих пор (сейчас этот НИИ называется «Центр математики и информатики»). Диссертацию доктора философии по теме «Системы Линденмайера: структура, языки и функции роста»[2] он защитил в 1978 в Свободном университете Амстердама и вскоре стал во главе свежесозданной кафедры, которую вывел на мировой уровень в области квантовых вычислений, распределённых алгоритмов, алгоритмической теории информации и обратимых адиабатических вычислений. В 2003 удостоился перевода на должность почётного научного сотрудника (CWI Fellow)[3]. В 2005 получил высший профессорский ранг (hoogleraar 1[4]) в крупнейшем в Нидерландах университете. В 2007 посвящён в рыцари ордена Нидерландского льва[5]. В 2011 выбран в члены Европейской академии наук[4]. Как и многие учёные его уровня, Паул Витани выполнял много редакционной работы в крупных журналах своей тематики и часто приглашался на конференции и рабочие встречи для пленарных докладов[6].

Вклад в науку[править | править код]

Системы Линденмайера, также называемые Л-системами, которыми Паул Витани занимался будучи аспирантом, представляют собой системы переписывания, родственные формальным грамматикам[7] и отличающиеся прежде всего тем, что на каждом шаге вывода правило применяется не к одному избранному (нетерминальному) символу, а ко всем символам строки одновременно. Изначально Л-системы были предложены ботаником Аристидом Линденмайером для моделирования развития одноклеточных организмов и прочих ветвящихся структур. Витани рассматривал их с формальной точки зрения и прояснил многие моменты, касающиеся классов языков, порождаемых Л-системами, а также использования нетерминалов и гомоморфизмов. В частности, он показал, что если в детерминированных Л-системах (то есть таких, где дерево вывода не ветвится) рассматривать семейство расширений (языков, порождаемых нетерминалами), то оно не будет полностью содержать класс регулярных языков, но его замыкание по побуквенному гомоморфизму эквивалентно классу рекурсивно перечислимых языков[8]. Он также показал, что взятие расширения, фактически сводящееся к теоретико-множественному пересечению языка с множеством терминалов (алфавитом), во многих случаях на практике эквивалентно рассмотрению строк, инвариантных переписыванию — то есть продемонстрировал связь стабилизирующегося морфогенеза с теорией формальных языков[9].

Существенный вклад Паул Витани совместно с коллегой Мингом Ли внёс в теорию колмогоровской сложности, в том числе написав книгу «Введение в колмогоровскую сложность и её применения»[10] (издания в 1993, 1997, 2008). Сама концепция колмогоровской сложности существовала задолго до него (предложена независимо Соломоноффом и Колмогоровым в 1960-е) и сводится к утверждению, что существует некоторая абстрактная описательная сложностью любой строки, равная длине минимальной программы, которая эту строку может выдать (для простоты можно считать языком программы машину Тьюринга, хотя это не обязательно: нужно просто зафиксировать какой-то универсальный язык описания или кодирования). Такая сложностью строки, да и любого другого объекта, представляет собой абсолютный, часто недостижимый, минимальный объём информации, которую строка или объект могут занимать без особых уловок вроде отказа от универсальности. Колмогоровская сложность — удобная теоретическая абстракция, зачастую бесполезная на практике, потому что она доказуемо невычислима. Паул Витани был одним из первых, кто смог найти ей практическое применение в теории автоматов или анализе алгоритмов. Книге предшествовали его отдельные работы по раскрашиванию графов с ограниченной точностью, алгоритмическому сравнению ленты, очереди и стека, пересмотре иерархии Хомского, связь худших сценариев с усреднёнными и пр. Принцип кратчайшего описания был сформулирован Витани, Ли и их учениками как абстракция, основанная на теореме Байеса и колмогоровской сложности, был получен ряд выводов практического свойства — например, что сжатие данных представляет собой лучшую стратегию приближения к кратчайшей длине описания данных или передаваемого сообщения[11]. На практике это позволяет заменять абстрактное, сложное и невычислимое понятие описательной сложности его аппроксимацией в виде длины сжатого каким-нибудь доступным архиватором сообщения.

В вычислительной теории Паул Витани ввёл понятие локальности вычислений и показал, что уход от фон Неймановских последовательных вычислений общей проблемы не решает, потому что само вычисление происходит в каком-то определённом месте, и его результаты должны быть переданы в другое место для хранения или продолжения вычислений — и эта коммуникация отнимает время и место, что следует отражать в реалистичных моделях непоследовательных вычислений[12]. Колмогоровская сложность пригодилась и в оценке нагрузки на сети различных топологий от различных алгоритмов с помощью так называемого метода несжимаемости[13]. Метод похож на существенно более простой принцип Дирихле и основан прежде всего на том, что графов с высокой колмогоровской сложностью настолько больше, чем графов с малой, что случайные графы будут с близкой к единице вероятностью сложными по Колмогорову[14]. Вообще, информация в любом объекте для Витани делится на две части: существенную (которая задаёт регулярность объекта) и несущественную (стохастические дополнения). Относительный объём существенной информации он называет мерой изощрённости, а объекты, для которых она максимальна, абсолютно нестохастическими[15].

Исследования теории информации, сложности и сжатия неминуемо привели Паула Витани к метрикам, измеряющим информационное расстояние между объектами (строками, документами, языками, изображениями и т. п.): он и его ученики предложили метод кластерного анализа, основанный на сжатии данных[16]; предложили нормированное информационное расстояние[17] и нормированное расстояние сжатия[18] как меры того, насколько сложно преобразовать один объект в другой; реализовали так называемую меру сходства по гуглу как семантическую метрику, основанную на количестве хитов в Google у одного термина, другого и их комбинации[19]; расширили понятие информационного расстояния с пар слов на конечные списки (фактически отказавшись от отношений в пользу гиперграфов)[20]; разработали ряд методов автоматического выведения значения неизвестных слов исходя из их информационной схожести с известными словами[21][22]. Некоторые предложенные им методы кластерного анализа настолько хороши, что работают во много раз быстрее аналогов — например, иерархическая кластеризация с помощью алгоритма восхождения к вершине и параллельного генетического программирования требует только матрицу расстояний и строит дендрограмму из 60-80 объектов за несколько часов, тогда как альтернативные подходы ограничены 20-30 объектами или требуют нескольких лет для проведения вычислений[23]. Те же методы кластерного анализа в применении к музыке могут с высокой надёжностью определять жанр и классифицировать произведения по композиторам[24].

В генетическом программировании Паул Витани предложил основанный на быстро смешивающихся цепях Маркова метод, сходящийся с близкой к единице вероятностью даже на малых популяциях, тогда как альтернативные ему методы страдают от случайно расходящейся эволюции[25]. В обратимых вычислениях — доказал возможность обратимой симуляции необратимых вычислений в субэкспоненциальное время и в субквадратичными затратами памяти[26]. В теории игр — обобщил задачу о разорении игрока на большее число игроков[27]. В дискретной геометрии — решил задачу о треугольнике Хайлбронна[en] в случае случайного равномерного распределения точек по окружности[28][29].

Паул Витани входит в список наиболее продуктивных учёных каталога DBLP как автор и соавтор почти 250 научных реферируемых публикаций[30].

Ученики[править | править код]

Под руководством Паула Витани защитились[2][31]:

  • Джон Тромп, «Аспекты алгоритмов и сложности», 1993
  • Яп-Хенк Хупман, «Синхронизация связи и отказоустойчивость», 1996
  • Рональд Крамер, «Модульное проектирование безопасных и при этом практичных криптографических протоколов», 1997
  • Петер Грюнвальд, «Принцип кратчайшего описания и доказательства в условиях неопределённости», 1998
  • Барбара Терхал, «Квантовые алгоритмы и квантовая запутанность», 1999
  • Рональд де Волф, «Квантовые вычисления и коммуникационая сложность», 2001
  • Вим ван Дам, «К вопросу о квантовой теории вычислений», 2002
  • Хайн Рёриг, «Сложность квантовых запросов и распределённые вычисления», 2004
  • Руди Килибраси, «Статический вывод путём сжатия данных», 2007
  • Стейвен де Рой, «Выбор модели кратчайшего описания: задачи и осложнения», 2008
  • Ваутер Колен-Вайкстра, «Эффективное сочетание стратегий. Высококачественные решения на основе спорных советов», 2011

Примечания[править | править код]

  1. ↑ Paul Vitányi: Lindenmayer Systems: Structure, Languages, and Growth Functions, 1978.
  2. ↑ 1 2 3 4 Paul Michael Bela Vitanyi Архивная копия от 22 января 2015 на Wayback Machine в Mathematics Genealogy Project.
  3. ↑ Paul Vitányi has been appointed CWI Fellow Архивная копия от 1 декабря 2014 на Wayback Machine, ERCIM News No. 53, April 2003.
  4. ↑ 1 2 Academy of Europe: Vitanyi Paul Архивная копия от 22 января 2015 на Wayback Machine.
  5. ↑ Paul Vitányi ontvangt koninklijke onderscheiding Архивная копия от 22 января 2015 на Wayback Machine.
  6. ↑ Some distinguished lectures, keynote lectures, invited lectures, tutorials Архивная копия от 1 декабря 2014 на Wayback Machine.
  7. ↑ L-Systems — математическая красота растений Архивная копия от 22 января 2015 на Wayback Machine.
  8. ↑ Paul M. B. Vitányi: Deterministic Lindenmayer Languages, Nonterminals and Homomorphisms. Theoretical Computer Science 2(1): 49-71 (1976).
  9. ↑ Paul M. B. Vitányi, Adrian Walker: Stable String Languages of Lindenmayer Systems. Information and Control 37(2): 134—149 (1978).
  10. ↑ An Introduction to Kolmogorov Complexity and Its Applications (Texts in Computer Science) Архивная копия от 29 августа 2018 на Wayback Machine на Amazon.
  11. ↑ Paul M. B. Vitányi, Ming Li: Minimum description length induction, Bayesianism, and Kolmogorov complexity. IEEE Transactions on Information Theory 46(2): 446—464 (2000)
  12. ↑ Paul M. B. Vitányi: Locality, Communication, and Interconnect Length in Multicomputers. SIAM J. Comput. 17(4): 659—672 (1988)
  13. ↑ Tao Jiang, Ming Li, Paul M. B. Vitányi: The Incompressibility Method. SOFSEM 2000: 36-53
  14. ↑ Harry Buhrman, Ming Li, John Tromp, Paul M. B. Vitányi: Kolmogorov Random Graphs and the Incompressibility Method. SIAM J. Comput. 29(2): 590—599 (1999).
  15. ↑ Paul M. B. Vitányi: Meaningful Information. IEEE Transactions on Information Theory 52(10): 4617-4626 (2006)
  16. ↑ Rudi Cilibrasi, Paul M. B. Vitányi: Clustering by compression Архивная копия от 13 октября 2008 на Wayback Machine. IEEE Transactions on Information Theory 51(4): 1523—1545 (2005)
  17. ↑ Charles H. Bennett, Péter Gács, Ming Li, Paul M. B. Vitányi, Wojciech H. Zurek: Information Distance. IEEE Transactions on Information Theory 44(4): 1407—1423 (1998)
  18. ↑ Sebastiaan A. Terwijn, Leen Torenvliet, Paul M. B. Vitányi: Nonapproximability of the normalized information distance. Journal of Computer and System Sciences 77(4): 738—742 (2011)
  19. ↑ Rudi Cilibrasi, Paul M. B. Vitányi: The Google Similarity Distance. IEEE Trans. Knowl. Data Eng. 19(3): 370—383 (2007)
  20. ↑ Paul M. B. Vitányi: Information Distance in Multiples. IEEE Transactions on Information Theory 57(4): 2451—2456 (2011)
  21. ↑ Rudi Cilibrasi, Paul M. B. Vitányi: Similarity of Objects and the Meaning of Words Архивная копия от 11 октября 2008 на Wayback Machine. TAMC 2006: 21-45
  22. ↑ Rudi Cilibrasi, Paul M. B. Vitányi: Automatic Meaning Discovery Using Google Архивная копия от 22 января 2015 на Wayback Machine. Kolmogorov Complexity and Applications 2006
  23. ↑ Rudi Cilibrasi, Paul M. B. Vitányi: A New Quartet Tree Heuristic for Hierarchical Clustering Архивная копия от 22 января 2015 на Wayback Machine. Theory of Evolutionary Algorithms 2006
  24. ↑ Rudi Cilibrasi, Paul M. B. Vitányi, Ronald de Wolf: Algorithmic Clustering of Music. WEDELMUSIC 2004: 110—117
  25. ↑ Paul M. B. Vitányi: A Discipline of Evolutionary Programming. Theoretical Computer Science 241(1-2): 3-23 (2000)
  26. ↑ Harry Buhrman, John Tromp, Paul M. B. Vitányi: Time and Space Bounds for Reversible Simulation. ICALP 2001: 1017—1027
  27. ↑ Kazuyuki Amano, John Tromp, Paul M. B. Vitányi, Osamu Watanabe: On a Generalized Ruin Problem. RANDOM-APPROX 2001: 181—191
  28. ↑ Tao Jiang, Ming Li, Paul M. B. Vitányi: The Expected Size of Heilbronn’s Triangles. IEEE Conference on Computational Complexity 1999: 105—113
  29. ↑ Tao Jiang, Ming Li, Paul M. B. Vitányi: The average-case area of Heilbronn-type triangles. Random Structures and Algorithms 20(2): 206—219 (2002)
  30. ↑ Most Prolific DBLP Authors Архивировано 13 февраля 2009 года..
  31. ↑ Past Ph.D. Students Архивная копия от 1 декабря 2014 на Wayback Machine.
Источник — https://ru.wikipedia.org/w/index.php?title=Витани,_Паул&oldid=130207892