Витани Паул (Vitani Paul).

Паул Михаэл Бела Витани (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 как автор и соавтор более 220 научных реферируемых публикаций.

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

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