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

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

Вклад в науку

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

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

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

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

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

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

Ученики

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

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

Примечания