Витани, Паул

Системы Линденмайера, также называемые Л-системами, которыми Паул Витани занимался будучи аспирантом, представляют собой системы переписывания, родственные формальным грамматикам[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]. В дискретной геометрии — решил задачу о треугольнике Хайлбронна в случае случайного равномерного распределения точек по окружности[28][29].

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

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

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