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

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

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


С В.А. Любецким (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) не содержит никаких кванторов; алгебраическая система с коэффициентами в кольце, разрешимая в расширении, разрешима и в самом кольце. Для чисел характерен переход от их маленькой части – поля рациональных чисел к его расширению (алгебраически-замкнутому или вещественно-замкнутому). Для многих групп и колец можно определить такой же переход (который называется модельным компаньоном). Сформулируем проблему. Для любой аксиоматики Т модельным компаньоном называется аксиоматика Т*, для которой любая формула приводится к указанному выше виду, и взаимно модель одной из этих аксиоматик вкладывается в модель другой. Вместо «модель аксиоматики S» говорят S-модель. Пусть для кольца К все его локализации (фактор-кольца К/(р·К), где р – простой идеал в булевой алгебре центральных идемпотентов) являются Т-моделями; будут ли модельным компаньоном таких колец кольца, у которых все их локализации Т*-модели; будет ли аксиоматизируем класс колец с Т*-локализациями.
c) Пример: период колебаний с бесконечно малой амплитудой нелинейного маятника бесконечно близок к периоду колебаний линейного маятника с той же амплитудой, что получается методом ломаных Эйлера с бесконечно малым шагом. Здесь для студента может быть интересно уже само понятие бесконечно малого вещественного числа. Интересно, что бесконечномерное пространство можно погрузить в конечномерное, у которого размерность – бесконечно большое натуральное число; и изучать его как конечномерное пространство. Проблема: можно ли эффективно описать такие числа, т.е. описать нестандартное расширение поля вещественных чисел, что связано с несколько загадочным понятием ультрафильтра и ультрастепени.
Известно несколько вариантов нестандартного анализа; выше говорилось о том, в котором «пределы заменяются на нестандартные числа»: например, последовательность {1/n} – одна бесконечно малая, а {1/n2} – другая меньшая бесконечно малая. В других своих вариантах нестандартный анализ (тогда называемый булевозначным или гейтинговозначным) позволяет изображать спектральные (самосопряжённые и нормальные) операторы в бесконечномерных гильбертовых (и более общих) пространствах вещественными и комплексными числами (как в символическом исчислении Хевисайда). Проблема в том, что так представленные алгебры операторов обязательно коммутативны. Переход к некоммутативному случаю является проблемой и, по-видимому, требует некоммутативного аналога булевой алгебры.