Василий Александрович Любецкий

Василий Александрович Любецкий

д.ф.-м.н., профессор
кафедра математической логики и теории алгоритмов
Механико-математический факультет
Московский государственный университет им. М.В.Ломоносова


С В.А. Любецким (lyubetsk@iitp.ru) можно сотрудничать по трём темам, которые объединяются (как ни покажется удивительным, на первый взгляд) понятием когнитивные науки:
1) «Математическая биология. Биоинформатика» (ВАКовские специальности 03.01.09 и 01.01.06, 05.13.17), включая сюда
1а) «Трудные задачи дискретной оптимизации»; и
2) «Теория множеств, теория моделей и нестандартный анализ» (ВАКовская специальность 01.01.06).
Заметим, что можно заниматься направлением 1а независимо от всякой биологии, хотя в 1а, как и в направлениях Вычисления на суперкомпьютерах, Большие данные, решаются чисто математичесие задачи, широко применяемые в направлении 1.
Ниже подробнее говорится о направлениях 1, 1а, 2, к которым относятся и исследования В.А. Любецкого, подробнее см. http://lab6.iitp.ru/ru/pub/.

1) Модели и алгоритмы в биоинформатике
Исследование направлено на создание и изучение математических и компьютерных моделей функционирования живой клетки (в первую очередь, процессов транскрипции и трансляции). А также – на создание моделей эволюции этих процессов, генов, белков, видов и т.д. На этой основе моделируются геномно обусловленные болезни; изучается задача компьютерной сборки (секвенирования) геномов. В качестве примера исследования приведём нашу гипотезу: "пониженная способность к регенерации и развитый передний мозг у человека возникли благодаря утрате генов, присутствующих у лягушки" – и действительно такие гены найдены нами с помощью алгоритмического и компьютерного анализов.
Это направление можно выразить тезисом, который несколько десятков лет назад казался невозможным, но сейчас кажется общепринятым: «ЖИВОЕ можно изучать с помощью МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ и АЛГОРИТМОВ (программ, суперкомпьютеров, баз данных, больших данных и т.п.)». Математическая сторона этой работы основана на решении чисто математических трудных задач дискретной оптимизации, которые можно решать, не касаясь самих приложений.

1а) примеры Трудных задач дискретной оптимизации:

  1. Даны n натуральных чисел, можно ли разбить их множество на две части с одинаковыми суммами чисел в каждой части.
  2. Даны два графа a и b и список естественных операций над графами, какова кратчайшая последовательность операций, преобразующая a в b.
  3. Как определить/вычислить расстояние между графами.
  4. Что такое средний граф для данного набора графов.
  5. Описать смену режимов в функционировании динамических систем определённых типов (важных в биологии), см. презентацию.

Во всех случаях нужно найти низкой степени полиномиальный (практически – линейный) вычислительный алгоритм, который решает задачу. Важную роль в исследовании играют программирование для суперкомпьютеров (распределённых вычислительных систем) и создание/использование больших данных, в частности, Целочисленное линейное программирование.

2) Теория множеств, теория моделей и нестандартный анализ
Исследование направлено на изучение случайных точек/чисел и абсолютно неразрешимых проблем. Случайная точка (в частности, число) определяется как такая, которая не может быть локализована в пространстве с помощью простого описания (например, «прибором»). Абсолютная неразрешимость означает, что проблему нельзя решить в рамках теории, которая вмещает все рассуждения, – общей теории множеств; при этом не предполагаются ограничения на метод решения (например, не требуется алгоритмичности и т.п.). Такие проблемы встречаются среди очень простых вопросов об измеримости и топологии простых множеств вещественных чисел. Также большую важность имеет изучение взаимоотношений этих проблем между собой, которое даёт совершенно неожиданные результаты. Например, для проективных множеств измеримость, оказывается, влечёт топологическое свойство Бэра, что кажется очень удивительным.
Родственное исследование ведётся вокруг того наблюдения, что в определённом смысле все несчётные мощности равноценны. А также – вокруг модельно полных аксиоматик, которые подобны аксиомам вещественных и комплексных чисел. Оказывается, что хорошо известные из школы свойства этих чисел и их взаимоотношений воспроизводятся на совершенно не похожих на числа кольцах.
Приведём примеры таких проблем и результатов вокруг вещественных и комплексных чисел, которые таят трудные и неожиданные логические проблемы.
a) Например, существует вещественное число h, для которого множество Q+h (рациональные числа Q, сдвинутые на h) обладает (в модели теории множеств) необычными свойствами; в частности, Q+h описывается простой явно указанной формулой, но ни один его элемент не описывается вообще никакой формулой. Сформулируем проблему. Для проективных множеств, связаны ли свойства: измеримость по Лебегу, свойство Бэра, канторово подмножество.
b) Пример. Описаны обширные классы групп и колец со свойствами, характерными для указанных чисел: эквивалентными преобразованиями любую формулу можно привести к виду ∃xφ(x), где φ(x) не содержит никаких кванторов; алгебраическая система с коэффициентами в кольце, разрешимая в расширении, разрешима и в самом кольце. Для указанных чисел характерен переход от их маленькой части – поля рациональных чисел к его расширению (алгебраически-замкнутому или вещественно-замкнутому). Для многих групп и колец можно определить такой же переход (который называется модельным компаньоном). Сформулируем проблему. Для любой аксиоматики Т модельным компаньоном называется аксиоматика Т*, для которой любая формула приводится к указанному выше виду, и взаимно модель одной аксиоматики вкладывается в модель другой. Пусть для кольца К моделями для Т являются все его локализации (фактор-кольца К/(р·К), где р – простой идеал в булевой алгебре центральных идемпотентов); будут ли модельным компаньоном таких колец кольца, для которых моделями для Т* являются все их локализации; будет ли аксиоматизируем класс колец с Т*-локализациями.
c) Пример: период колебаний с бесконечно малой амплитудой нелинейного маятника бесконечно близок к периоду колебаний линейного маятника с той же амплитудой, что получается методом ломаных Эйлера с бесконечно малым шагом. Здесь для студента может быть интересно уже само понятие бесконечно малого вещественного числа. Проблема: можно ли эффективно описать такие числа, т.е. описать нестандартное расширение поля вещественных чисел, что связано с несколько загадочным понятием ультрафильтра и ультрастепени.