автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Полиномиальные модели, основанные на диаграммах Юнга

На правах рукописи

Павлов Дмитрий Алексеевич

Полиномиальные модели, основанные на диаграммах Юнга

05.13.18 Математическое моделирование, численные методы п комплексы программ

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

, с "013

Санкт-Петербург 2013

005049934

Работа выполнена в Санкт-Петербургском государственном политехническом университете.

Нау ч н ы й руководител ь

кандидат физ.-мат. наук, доцент Васильев Николай Николаевич

Официальные оппоненты:

Ведущая организация

доктор физ.-мат. наук, профессор Гердт Владимир Петрович Объединённый институт ядерных иссл дований, начальник сектора

кандидат физ.-мат. наук, доцент Зобнин Алексей Игоревич Московский государственный унивсрс тст имени М.В.Ломоносова, доцент

Санкт-Петербургский институт инфо матики и автоматизации Российско академии наук

Защита состоится «22» февраля 2013 г. в 15 час. 30 мин. на заседании диссертационного совета Д212.203.28 в Российском университете дружбы народов по адресу: г.Москва, ул. Орджоникидзе, д. 3.

С диссертацией можно ознакомиться в Научной библиотеке Российского университета дружбы народов но адресу: 117198, Москва, ул. Миклухо-Маклая, С.

Автореферат разослан «_» января 2013 г.

Учёный секретарь диссертационного совета

М.Б.Фомин

Общая характеристика работы

Актуальность работы. Во многих прикладных исследованиях встречаются задачи, связанные с полиномиальными моделями и системами полиномиальных уравнении. Например, к таким задачам относится задача нахождения дробного факторного плана и задача нахождения множества моделей, пдентнфицпрумых заданным планом [1) в теории планирования эксперимента.

Микробиология также нуждается в полиномиальных моделях, чтобы по экспериментальным данным находить закономерности в процессах, проистекающих в живых клетках [2]. Возможность прямого наблюдения химических реакции 1! клетке исключена: реакции происходят с огромной частотой и не поддаются визуальному анализу. Однако, есть техническая возможность измерять уровень присутствия в клетке какого-либо вещества или белка в фиксированные моменты времени. В ¡юли математической модели изучаемого процесса выступает динамическая система с дискретным временем, состояние которой определяется уровнем присутствия различных белков п веществ. Несколько этапов измерении, выполненных подряд, дают таблицу состоянии этой системы. Состояние системы меняется в результате химических реакции.

Природу процессов, происходящих в клетке, принято представлять в форме т.н. биохимической сети. Биохимическая сеть кодирует зависимости между объектами-участниками происходящего процесса. Для получения информации о зависимостях требуется определить функции перехода между состояниями. В известных работах в данной области параметры состояния системы представляются дискретными величинами, чаще всего булевыми (есть белок А / нет белка А, есть вещество В / нет вещества В, и т.д.). Функции перехода между состояниями, таким образом, являются функциями в конечном поле. Следовательно, они являются полиномами, и задача сводится к построению полиномиальной модели зависимости состояния системы от состояния её в предыдущий момент времени.

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

тс [1] но планированию эксперимента, для получения множества полиномиальных моделей используются методы алгебраической статистики, возникшей в 1990 году [3|. В основе этих методов лежит связь полиномиальных моделей с нульмерными полиномиальными идеалами, п с особыми базисами этих идеалов базисами Грёбнера, которые были придуманы в 1905 г. для символьного решения систем полиномиальных уравнений.

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

Целью диссертационной работы является создание инструмента для разработки и анализа полиномиальных моделей биохимических и других природных процессов. Новый инструмент, в отличие от имеющихся, позволит находить все без исключений полиномиальные модели, согласующиеся с исходными данными.

Математический аппарат, использованный для достижения поставленной цели, имеет 1! своей основе диаграммы Юнга простые математические объекты, которые имеют прямое отношение к теории базисов Грёбнера. Например, в статье [4] построение базиса Грёбнера основано на построении диаграммы Юнга, мономы которой порождают факторалгебру нульмерного идеала.

Переход от базисов Грёбнера к диаграммам Юнга позволил разработать алгоритм полного перебора полиномиальных моделей. Создание этого алгоритма было невозможно без решения ряда частных практических задач:

• Разработка алгоритмов для осуществления разнообразных операций с диаграммами Юнга.

• Исследование связи диаграмм Юнга с мономиальными упорядочениями и базисами Грёбнера.

• Формулирование задач алгебраической статистики в 'терминах диаграмм Юнга.

Методы исследования. В работе использованы методы вычислительной коммутативной и компьютерной алгебры, теории базисов Грёбнера, теории представлений, методы математического моделирования, ком-

бинаторныс методы дискрстноП математики, методы вычислительной математики. Для реализации алгоритмом используется среда программирования Common Lisp, а также пакеты компьютерных прикладных программ Maxima п GFan.

На защиту выносятся следующие основные результаты:

• Предложен алгоритм, позволяющий эффективно осуществлять построение и анализ полиномиальных моделей различных природных процессов. Алгоритм основан на новом подходе к комбинаторике диаграмм Юнга, также предложенном и диссертации. Детально рассмотрено применение алгоритма в теории биохимических сетей. Решена задача построения биохимической сети процесса, происходящего в живой клетке (такого, как метаболизм лактозы пли транедукция различных сигналов), по набору последовательных дискретных состояний, полученных экспериментально. Доказана корректность работы алгоритма и показан синтетический пример, демонстрирующий его преимущества перед имеющимися алгоритмами.

• Разработанный алгоритм применен 'также и теории планирования эксперимента: решена задача нахождения статистического веера (statistical fan) полиномиальных моделей, идентифицируемых за,данным планом эксперимента. (Из предыдущих работ были известны лишь алгоритмы нахождения алгебраического веера, algebraic fan). С помощью численного эксперимента исследованы отличия статистического веера от алгебраического для известных планов экнеримента (Бокса-Бенкена, Бокса-Уилсона) г, пространствах различной размерности.

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

• Реализованы алгоритмы для перебора 'таблиц Юнга произвольной размерности, соответствующих слабодопустимым, выпуклым и стро-годопустпмым конечным мономиальным упорядочениям; найдено и доказано соответствие между конечными строгодопустимыми упорядочениями и начальными сегментами сигнатурных последовательностей.

• В 'теорию базисов Грсбнсра введено понятие расширенного универсального базиса Грёбнера (EUGB): конструкции, не зависящей от строгого упорядочения мономов. Разработан алгоритм вычисления

ЕиСВ. Доказано несовпадение в общем случае 1ЮВ с Е1ЮВ. Обнаружено явление «сильной ненётеровостн» полиномиальном редукции относительно набора полиномов, независящее от выбора конкретного полинома для деления.

• Реализован алгоритм порождения случайных двумерных диаграмм Юнга, распределённых по мере Плашнереля. Проведены эксперименты по нахождению мат. ожидания и максимума нормализованной размерности неприводимых представлений.

• Реализован алгоритм порождения случайных ¿-мерных диаграмм Юнга, распределенных по мерс Ричардсона. Предложен численный метод вычисления предельной формы многомерных диаграмм Юнга, а также численный метод анализа сходимости фронта диаграммы к предельной форме.

Научная новизна. Следующие результаты, полученные в диссертации, являются новыми:

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

• Представлены не опубликованные ранее алгоритмы для перебора таблиц Юнга произвольной размерности, соответствующих выпуклым и строгодоиустимым конечным мономиальным упорядочениям.

• Введено новое понятие расширенного универсального базиса Грёбнс-ра (Е1ЮВ) и разработан алгоритм вычисления Е1ЮВ.

• Обнаружено явление «сильной ненётеровостн» полиномиальной редукции.

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

Теоретическая значимость проделанной работы заключается прежде всего в том, что разработанные алгоритмы применяются и могут применяться в дальнейшем для установления и проверки различных гипотез пз теории представлений и теории базисов Грёбнера; так, используя метод, предложенный в диссертации, автору удалось найти контрпример к оши-

бочно доказанной теореме в препринте статьи [5].

Другим значимым теоретическим результатом работы можно считать открытие явлении «сильной ненётсровостп».

Апробация работы. Основные результаты работы докладывались и обсуждались на:

• Международной конференции по полиномиальной компьютерной алгебре (РСА) (ММИ имени Эйлера, Санкт-Петербург, 2008, 2009, 2011);

• Международном рабочем совещании но компьютерной алгебре (Дубна, 2008);

• Семинаре по теории представлений и динамическим системам (ПОМП, Санкт-Петербург, 2009).

• Научном семинаре кафедры прикладной математики (ФМФ СПбГПУ, Санкт-Петербург, 2009)

• Международной конференции по параллельной компьютерной алгебре (Тамбов, 2010)

• Научном семинаре в РУДН (Москва, 2012).

Достоверность результатов. Полученные в диссертации результаты обоснованы корректным использованием математических методов вычислительно!! коммутативной алгебры п комбинаторики. Достоверность подтверждается сопоставлением с результатами, доступными I! открытой печати.

Публикации. Материалы диссертации опубликованы в 5 статьях в рецензируемых журналах [1 5|, рекомендованных ВАК РФ для опубликования результатов кандидатских диссертаций.

Личный вклад автора. Работы [1, 3, 4] выполнены в соавторстве. Вклад соискателя I! них заключается в:

• Разработке и реализации алгоритмов

• Проведении численного моделирования случайных процессов на диаграммах Юнга.

Структура и объем диссертации. Диссертация состоит из введения, пяти глав, заключения, списка цитируемой литературы и 'трёх приложений. Объем диссертации составляет 143 страницы (из них 13 занимают приложения). Кроме основного текста диссертация содержит 24 рисунка и список литературы из 89 наименований.

Содержание работы

Во введении обоснована ак туальность диссертационной работы, сформулирована цель и аргументирована научная новизна исследований, нред-

ставлены выносимые на защиту результаты и положения.

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

Диаграмма Юнга это конечный набор прямоугольных ячеек, составленных в строки, выровненные по левому краю, число клеток в которых нестрого убывает. Размер диаграммы количество клеток в ней обозначается п.

Рис. 1. Диаграмма Юнга размера п = 14

Иначе диаграмму Юнга можно определить как конечный убывающий (нижний) идеал в решетке Ж>о х 2>о, то есть множество, содержащее вместе с каждой клеткой все меньшие её в смысле частичного порядка. Такое определение тривиально обобщается на случай многомерной решётки 2>(). В работе будет идти речь о (¿-мерных диаграммах Юнга; при этом для классических двумерных диаграмм индекс размерности может быть опущен.

Таблицей Юнга в данной работе называется стандартная таблица Юнга, то есть диаграмма Юнга, заполненная числами от 1 до п таким образом, что числа возрастаю']' по строкам и по столбцам; иначе говоря, таблица Юнга есть путь в решетке диаграмм Юнга, начинающийся с пустой диаграммы и кончающийся в данной диаграмме. Многомерные таблицы Юнга являются тривиальным обобщением, как и диаграммы Юнга.

12

5 7 13 14

2 6 8 11

1 3 4 9 10 |

Рис. 2. Таблица Юнга

Рассмотрим полиномиальную функцию/ 6 К[х 1,. .., #,/] от (I аргументов, пусть нас интересуют лишь её значения в точках ? = {рь ... С К'1. Нетрудно показать, что множество полиномов, равных нулю на всех точках Т, образует идеал; обозначим его Очевидно, любая функция

из множества {/ + 1(3^)} имеет те же значения в точках Т, что и /: V/' = / + Л, к € 1(Т) VР, е Т /'Ы = /Ы

Верно н обратное: если значения двух полиномов совпадают на всех 'точках из Т, то их разность принадлежит 1(Т):

Следовательно, набор значении в 'точках Т задаёт класс эквивален'тности в факторалгебре Л'[;гь ..., х,}\11{7). Рассмотрим полиномиальную модель некоторого процесса у = ¡(х\,..., :г,/), построенную по измеренным результатам этого процесса в точках Т. Вид полиномиальной модели будет варьироваться в зависимости от 'того, какой мономпальныи базис для фак-торалгебры будет выбран. Размерность факторалгебры т.е. количество мономов в любом её мономиальном базисе совпадает с количеством точек |.Г|, -то есть факторалгебра идеала является конечно-порождённой, а сам идеал, соответственно, является нульмерным.

Среди полиномиальных моделей принято выделять т.н. полные полиномиальные модели, т.е. такие, которые вместе с каждым термом содержат все его дели гели:

у = /(.ть ..., .г,,) 6 Л'[:гь ..., .г,,] е 8ирр(/) => I е 8ирр(/).

Неполные полиномиальные модели, как правило, не представляют интереса при решении прикладных задач; в диссертации им также не уделяется внимания.

Заметим, что набор термов полной полиномиальной модели представляет собой диаграмму Юнга, и термы являются линейно-независимыми в Размер диаграммы равен количеству точек то есть конечен; следовательно, всего полиномиальных моделей, которые могут быть построены на точках Т, не больше, чем диаграмм Юнга размера , 'т.е. конечное число.

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

Классическая 'теория базисов Грёбнсра основана на рассмотрении допустимых упорядочений мономов. Любой базис Грёбнсра подразумевает некоторое конкретное допустимое .упорядочение (или семейство упорядочений), на котором основан алгоритм редукции полиномов относительно идеала. Однако, классическая 'теория может быть обобщена различными способами на некоторые другие упорядочения, не являющиеся допустимыми. Мы рассматриваем слабодопустимые упорядочения, согласованные только с делением мономов.

Обозначим 21 некоторый идеал в бесконечномерном векторном пространстве полиномов К\х\,... ,£,/].

Определение 1. Мы будем называть мономы {?тг,} линейно-независимыми относительно $1, сели нсрссс.чсннс их линейной оболочки с 21 состоит из нулевого полинома:

£({т,-}) П 21 = {0}

(Множество {//(,} не обязательно конечно.) С обозначает линейную оболочку множества в векторном пространстве Л'[:сь ... ,

Определение 2. Коп деалом в называется множество мономов, которые не делятся ни на одни моном из заданного конечного набора Б с т.е. дополнение до возрастающего идеала в решётке мономов. Будем говорить, что коидеал построен на множестве мономов Б. Коидеал, построенный на старших членах базиса Грёбнера, порождает факторалгебру идеала. Коидеал может быть как конечным, так и бесконечным.

Обозначим <3 факторалгебру идеала 21: О — А'[;Гь ... ,.г,/]/21. Множество мономов Ж'1{) лежит в К[хх,..., я,/]; таким образом, каждый моном г 6 Ж'>() имеет канонический образ в С,).

Обозначим (7^(21) базис Грёбнера идеала 21, соответствующий допустимому упорядочению -<. Обозначим 1ЮВ(21) универсальный базис Грёбнера объединение базисов Грёбнера для всех возможных допустимых упорядочений. Веером Грёбнера (СгбЬпсг £ап) называется ансамбль всех базисов Грёбнера.

Мономы из коидеала, построенного на старших членах какого-либо базиса Грёбнера С^(21), являются линейно-независимыми в идеале 21; более того, добавление любого монома в коидеал образует множество мономов, линейно-зависимых в 21. В алгоритме ГСЬМ [4] данное обстоятельство используется для нахождения базиса Грёбнера нульмерного идеала.

Определение 3. Диаграммой ЮшаК(/) С Ж'10 полинома / 6 К[х1,... называется множество мономов-делителей термов /.

Для каждого полинома / е 1ГСВ(21) верно следующее:

сШп(£(Г(/))П21) = 1 (1)

Это не достаточное условие на принадлежность иСВ(ЭД); однако оно выгодно отличается тем, что не содержит никаких требований ни на допустимое упорядочение, ни на полное упорядочение. Речь идёт только о частичном отношении делимости.

Определение 4. Мы определяем расширенный универсальный базис Грёб-

пера EUGB(21) полиномиального идеалаШ как набор нссх полиномов, удовлетворяющих (1), уникальных с точностью до множителя.

UGB(2l) содержится в EUGB(2t). Однако, в EUGB(2t) могут существовать и другие базисы 21, отсутствующие в веере Грёбнера, т.к. в EUGB(2l) нет никаких условии на «допустимость» мономиального упорядочения.

Теорема 1. E(;G'B(2l) в общем случае не совпадает с UGB(21).

Не всякий базис может использоваться для редукции полиномов; для того, чтобы отношение редукции было нётероиым, т.е. для того, чтобы последовательность редукций гарантированно заканчивалась, необходимым условием является следующее: факторалгебра Q должна порождаться мономами коидеала, построенного на старших членах базиса. Кроме того, необходимо правило выбора полинома для редукции, которое бы гарантировало отсутствие «петель». В работе [G] показано, что для недопустимого упорядочения молено uaiimu циклическую последовательность редукций.

Если набор полиномов из EUGB(2I) порождает идеал, но соответствующий коидеал не порождает факторалгебру, то для некоторых полиномов из идеала редукция не завершится никогда, вне .зависимости от правил редукции. Это явление названо «сильной ненётеровостью».

Теорема 2. Существуют такой набор полиномов {J7}, и полином g £ (F), для которых имеет место явление сильной ненётсроности, т.е. редукция g относительно {Г} никогда не завершается.

Примеры EUGB и сильной ненетсровости, а также алгоритм нахождения EUGB приведены в диссертации.

Результаты первой главы опубликованы в работах [2, 4, 5].

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

Рассмотрим таблицу Юнга как убывающий идеал в решётке Z>0, с некоторым порядком, определённым на элементах решётки; так, чтобы нумерация ячеек соответствовала упорядочению. Если интерпретировать элементы решётки как мономы, то упорядочение будет соответствовать некоторому конечному отрезку слабодопустимого мономиального упорядочения [1], заданного частичным отношением делимости мономов:

V a, b, u £ Z>„ а = bu а b (2)

В теории базисов Грёбнера используются полные допустимые упорядочения мономов (admissible monomial ordcrings), которые согласуются не только с делимостью мономов, но и с умножением на моном:

V a, b, u G Z>„ а -< b au -< bu (3)

Такие упорядочения позволяют осуществлять редукцию полином а относительно заданного базиса полиномиального идеала. Нётсровость отношения редукции гарантирует, что последовательность редукции любого полинома завершится.

Определение 5. Конечное мономиальное упорядочение называется слабодопустимым (строгодопустимым). сслп оно является началом некоторого бесконечного слабодоиустимого (допустимого) упорядочения.

Алгоритм перебора слабодопустимых упорядочении приведён в диссертации, а результаты подсчёта количества таблиц Юнга по этому алгоритму приведены в приложении Б.1. В двумерном случаете же результаты можно получить, применив известную рекурсивную формулу. Следует отмстить, что перебор - задача более общая, чем простои подсчёт таблиц Юнга; задача подсчёта таблиц Юнга напрямую в этой работе не ставилась.

Алгоритмы перебора конечных выпуклых и строгодонустимых упорядочений, являющиеся расширениями алгоритма перебора конечных слабодопустимых упорядочений, приведены в диссертации. Результаты подсчёта количества этих упорядочений для d = 2,3 приведены в приложениях Б.2 и Б.З.

Благодаря сравнению результатов подсчёта с находящимися в печати источниками, удалось открыть связь строгодонустимых упорядочений с с и г н ату р н ы м и н осл сдо в ател ь н остя м и :

Теорема 3. Каждому начальному сегменту сигнатурной последовательности {с,} соответствует одно и только одно конечное строгодопустимос упорядочение мономов в Ж>0 размера п.

Определение сигнатурной последовательности и доказательство теоремы приведены в тексте диссертации. Результаты второй главы опубликованы в работе [1|.

Третья глава, основываясь на математическом аппарате первых двух глав, предлагает новый подход к построению полиномиальных моделей. Демонстрируется применимость нового подхода в двух прикладных областях: построение исчерпывающего множества полиномиальных моделей биохимического процесса в живой клетке, а также построение исчерпывающего множества полиномиальных моделей, идентифицируемых заданным пла-

ном эксперимента.

Рассмотрим проблему построения полиномиальных моделей на примере процесса метаболизма лактозы в клетке кишечной палочки (Е. Coli).

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

В этом процессе участвуют пять объектов: лактозный оперон (М), бста-галакепдаза (В), аллолактоза (А), лактоза (L), и бета-галактозид-иермеаза (Р). Все эти объекты (i) имеют количественную природу и поддаются измерению, и (И) влияют друг на друга. Модель описанного процесса пред-

[»ГТ5-......

Рис. 3. Схема метаболизма лактозы в клетке Е. Coli, ставляст собой дискретную динамическую систему, состояние которой описывается пятью параметрами (M,B,A,L,P), каждый из которых выражает уровень активности соответствующего объекта в клетке. Параметры выбираются дискретными, и эволюция системы определяется полиномиальными функциями перехода:

М' = fM{M,B,A,L,P) L' = fb(M,B,A,L,P) В' = fB(M,B,A,L,P) Р' = fp(M, В, А, L, Р) А' = fA(M,B,A,L,P) Здесь переменные со ш трихами обозначают состояние системы на один период времени позже. Считается, что в течение одного периода времени происходят химические реакции и система меняет состояние. Исследовательская задача заключается в том, чтобы по переходам вида

{(Мк, Вк, А,, L,, Р,) (М'к, В[, А[„ 4, PI)}, к = 1..N построить граф зависимостей, подобный рис. 3.

Для каждого * € {М,В,А,Ь,Р} существует множество полиномов {/*''}, принадлежащих одному классу вычетов в факторалгебре нульмерного идеала 1(3-) = /{(Л/д., В^, Л*-, Ьд-, -Ра )}). Следовательно, но одной и той же цепочке в общем случае можно построить более одной полиномиальной модели, графы зависимостей которых будут различаться. Для исчерпывающего решения прикладной задачи требуется перебрать все возможные модели с их графами зависимостей.

Метод, изложенный в [2], реализует вышеописанный принцип путем построения произвольной начальной модели и последующего перебора базисов Грёбнера идеала 21 с помощью алгоритма GFa.ii. На каждом базисе строится модель, состоящая из многочленов начальной модели, взятых по модулю многочленов базиса. Модели, которые могут быть найдены описанным методом, ограничены мономиальными базисами, которые лежат «под старшими членами» базисов Грёбнера идеала 21. Однако, существуют множества мономов, линейно-независимых в 21 и порождающих Сне соответствующие какому-либо базису Грёбнера. Полиномиальные модели, построенные на таких множествах, будут неизбежно пропущены при переборе веера Грёбнера. Алгоритм перебора полиномиальных моделей, разработанный в диссертации и основанный на комбинаторике диаграмм Юнга, позволяет избавиться от этого недостатка.

Алгоритм основан на переборе слабодопустимых упорядочений порядка N (гл. 2) с модификациями. Описание алгоритма приведено в диссертации.

Каждая диаграмма Юнга У размера Лг, полученная в ходе работы алгоритма, представляет собой набор мономов, линейно-независимых в/(7г). На этих мономах и строится полиномиальная модель исследуемой динамической системы. Коэффициенты к каждой функции перехода выводятся из заданной таблицы переходов. В результате работы алгоритма все полиномиальные модели, не противоречащие таблице переходов, будут найдены.

Продемонстрируем на примере превосходство предложенного в диссертации алгоритма полного перебора полиномиальных моделей над алгоритмом перебора, основанном на веере Грёбнера. Рассмотрим следующую дискретную динамическую систему с четырьмя булевыми параметрами х, у, г, ги:

/Х(х,у,г,и}) = хг /.(х,у,г,ы) = л

(4)

1п(х,у,г,ш) = угг /„.(.г ,у,г,и>) = т Данная система является синтетической, т.е. не основанной на каком-либо

физическом или биологическом процессе, и намеренно сделана максимально простои для изучения. Рассмотрим следующую таблицу переходов:

(0,0,0,0) -»• (0,0,0,0) (0,1,1,1) -> (0,1,1,1) (0,0,1,0) -> (0,0,1,0) (1,0,0,0)->(0,0,0,0) (0,0,1,1) -> (0,0,1,1) (1,0,1,1) (1,0,1,1) (0,1,0,0) —(0, 0,0,0) (1,1,0, 0) -4 (0, 0,0,0) Идеал многочленов в ^[х, у, г, ш], равных нулю на точках из первой и третьей колонок таблицы 5, имеет два базиса Грсбнера:

х2 + х, у1 + у, г2 + г, и>2 + ш, гш + ю, уг + уш, хг + хги, хую х1 + х, у2 + у, г2 + г, н>2 + ш, гт + ш, ут + у г, хш + хг, хуг Эти базисы формируют наборы мономов-остатков: {1 ,х,у,г,и>, ху,хю, уи;} и {1, х, у, г, ш, ху, хг, уг} соответственно. Функции перехода, построенные на мономах из первого набора, выглядят так:

/,.(х, у, г, и') = хи> /:(х, у, г, ш) = г

/и(х, у, г, т) = ую /,„(х, у, г, ш) = м

Функции перехода, построенные на мономах пз второго набора: /,.(х, у, г, ш) = хг /:(х, у, г, ю) = г

/,,(х, у, г, ш) = уг /н,(х, у, г, ю) = ш

Легко видеть, что изначальная комбинация (4) с помощью базисов Грсбнера найдена не была. Алгоритм, представленный в диссертации, выдаст для данной задачи четыре результата: кроме двух указанных, ещё две диаграммы Юнга, линейно-независимых в 1{Т)\

{1,х,у,г,ш,ху,хг,уи>} (6)

{1 ,х,у,г,ш,ху,уг,хш} (7)

Функции перехода, построенные на мономах пз диаграммы (С), совпадают с исходными функциями (4). В диссертации также описан случай, когда не комбинация функций, а конкретная функция, найденная представленным алгоритмом, не может быть найдена с помощью базисов Грсбнера.

Второй областью приложений алгоритма, изложенного в главе 3, является планирование эксперимента. Пусть задан некоторый план эксперимента: Т = {рь-.-Рдт} С К'1 (./V количество экспериментов). Мы рассматриваем линейную регрессионную модель У = Рв + е, матрица плана которого -Рухп содержит значения термов / в точках Т, а вектор У содержит значения откликов в этих точках.

Ги = 8"РР(/) = {¿ь ...,£„}

Полиномиальная модель / называется идентифицируемой, если rank(F) = п. В этом случае, если N = п, вектор коэффициентов (в) идентифицируемой модели однозначно определяется по откликам (У) в'точках измерений. В случае N > п для идентифицируемой модели можно вычислить наилучшую линейную несмещённую (HJIH) оценку:

в = ((FT F)'1 FT)Y

В 199G году было замечено [3], что полные идентифицируемые полиномиальные модели имеют непосредственную связь с базисами Грёбнсра полиномиальных идеалов. Предположим на время, что N = щ в данном случае модель считается идентифицируемой, если det(F) ф 0.

Идентифицируемая модель является набором мономов, лпнейно-неза-висимых в Из этого следует, что полная иден тифицируемая модель

(диаграмма Юнга) может быть получена как конечный коидеал «под старшими членами» какого-либо базиса Грёбнсра/(J7).

Множество таких моделей было названо «алгебраическим веером», по аналогии с веером Грёбнсра (Grobncr fan). Полный ансамбль идентифицируемых моделей т.н. статистический веер в общем случае может быть шире, чем алгебраический. В диссертации предложен алгоритм нахождения статистического веера он был описан выше как алгоритм перебора полных полиномиальных моделей.

Обоснование вышеизложенных рассуждений для случая N > п приведено в тексте диссертации. Также для некоторых часто используемых планов приведены примеры подсчитанных «статистических вееров» и подчёркнуто их отличие от алгебраических. Например, план Бокса-Бенксна, представляющий собой набор точек в серединах рёбер трехмерного куба, имеет 12 «алгебраических» идентифицируемых полных моделей. «Статистический» веер содержит на две модели больше. Эти и другие примеры приведены более подробно в тексте диссертации.

Результаты третьей главы были представлены на конференции РСА в Санкт-Петербурге в 2011 I'. и на семинаре в РУДН в 2012 г.

Четвёртая глава посвящена исследованию разработанного метода с целью его применения в других задачах. Рассказывается о задачах -теории представлений симметрической группы 5„, связанных с диаграммами Юнга, а также о марковских процессах наращивания диаграммы.

Двумерные диаграммы Юнга соответствуют неприводимым представлениям S„, а количество таблиц диаграммы равно размерности соответствующего представления. Размерность неприводимого представления Л £ Sn обозначим /А. Следующая естественная нормировка размерности дпа-

грамм с п клетками позволяет изучать асимптотику размерности при п стремящемся к бесконечности:

c(\es„) = ^\n^= (8)

sjn yjn\

Будем называть коэффициент с(А) нормализованной размерностью.

Для поиска неприводимого представления Sn максимальной размерности необходим перебор двумерных диаграмм Юнга размера?!, который в свою очередь наиболее эффективно реализуется перебором разбиений числа п. Для подсчёта размерности представления /А по диаграмме известна т.н. «формула крюков». Таким образом удалось найти тахЛе6; /А для всех п до 130 включительно.

В приложении А.1 приведены полученные значения нормализованных м акси мал ьн ых размерностей.

Также в главе 4 рассматривается асимптотика случайных диаграмм Юнга, с рассмотрением двух мер на множестве диаграмм: меры Планшсрс-ля, которая впервые была введена в [7], и меры Ричардсона, связь которой с марковским процессом поведения частицы в пространстве{0,1}ж раскрывается в [8].

Вероятность диаграммы А € S„ по мере Планшсреля равна /¿Г1(А) = ^j-. Одно из применений известного алгоритма RSK - порождение случайных по мере Планшсреля диаграмм Юнга. Используя метод Монте-Карло, RSK и формулу крюков, удалось достаточно точно вычислить математическое ожидание и дисперсию нормализованной размерности диаграммы по мере Планшсреля. В приложении А.2 приведены полученные значения мат. ожидания. Есть основания полагать, что эта характеристика имеет предел при п —» оо.

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

Результаты четвёртой главы опубликованы в работе [3].

В пятой главе раскрываются подробности реализации алгоритмов, изложенных в первых четырёх главах. Описаны использованные структуры данных; приведена справка по созданным программным модулям, а также фрагменты кода на языке Common Lisp. Исходные тексты некоторых консольных программ, использующих описанные модули, приведены в приложении В.

В Заключении сформулированы основные результаты диссертации.

Список публикаций

[1] Васильев Н. Н., Павлов Д. А. Перечисление конечных мономиальных упорядочении и комбинаторика универсальных базисов Грёбнера // Программирование. 2009. № 2. С. 150 1С1.

[2] Павлов Д. Алгоритм построения расширенного универсального базиса Грёбнера П Научно-Техническис Ведомости СПбГПУ. 2008. Т. G5, № 5. С. 179 183.

[3] Всршик А. М., Павлов Д. А. Численные эксперименты в задачах асимптотической теории представлений /7 Записки научных семинаров ПОМП. 2009. Т. 3GG, № 4.

[4| Васильев Н. Н., Павлов Д. А. Сильная ненётсровость полиномиальной редукции // Записки научных семинаров ПОМП. 2009. Т. 373. С. 73 7G.

[5] Павлов Д. А. Паралельное вычисление расширенных универсальных базисов Грёбнера // Вестник ТамГУ. 2010. Т. 15. С. 1405 1412.

Цитированная литература

[1| Riccomagno Е., Caboara М., Pistonc G., Wynn Н. P. The fan of an experimental design /',/ SCU Research Report. 1997. Vol. 10.

[21 Dimitrova E. S., Jarrali A. S., Laubenbacher R., Stiglcr B. A Grobncr fan method for biochemical network modeling /7 Proceedings of the 2007 international symposium on Symbolic and algebraic computation. ISSAC '07.

New York, NY, USA: ACM, 2007. P. 122 12G.

[3] Pistone G., Wynn H. P. Generalised confounding with Grobncr bases // Biomctrica. - 199G. Vol. 83. P. 653 GGG.

[4] Faugerc J.-C., Gianni P., Lazard D., Mora T. Efficient computation of zc-ro-dimcnsional Grobncr bases by change of ordering /'/ Journal of Symbolic Computation. 1993. Vol. 4, no. 1G. P. 329 344.

[51 Kreuzer M., Poulissc H. Subideal Border Bases /'/ Mathematics of Computation. 2011. Vol. 80. P. 1135 1154.

[6[ Reeves A., Sturmfcls B. A Note on Polynomial Reduction // Journal of Symbolic Computation. 1993. Vol. 1G. P. 273 277.

[7[ Вершик A. M., Керов С. В. Асимптотика меры Планшсреля симметрической группы и предельная форма таблиц Юнга /'/' Функциональный анализ и его приложения. 1977. Т. 6, № 233. С. 1024 1027.

[8[ Rost Н. Non-equilibrium behaviour of a many particle process: Density profile and local equilibria /7 Probability Theory and Related Fields. 1981. Vol. 1, no. 58. P. 41 53.

1G

Павлов Дмитрий Алексеевич (Россия) Полиномиальные модели, основанные на диаграммах Юнга

Аннотация

В работе изучаются методы построения полиномиальных моделей, основанные на комбинаторике диаграмм Юнга. Связь между диаграммами Юнга и нульмерными полиномиальными идеалами позволила разработать оригинальный подход к построению дискретных динамических систем, соответствующих каким-либо природным процессам. Частным случаем такой системы, рассмотренным в диссертации, являются биохимические сети в модели живой клетки. Разработанный алгоритм комбинаторного перебора полиномиальных моделей был также применён в теории планирования эксперимента. (Предыдущие алгоритмы такого рода были основаны на базисах Гребнера и не гарантировали выдачу полного результата.) В диссертации представлен пакет программ, реализующий разработанный алгоритм, а также предоставляющий ряд дополнительных возможностей по исследованию комбинаторики диаграмм Юнга.

Dmitry Pavlov (Russia) Polynomial models based on Young diagrams

Abstract

We study methods for building of polynomial models. In particular, we study methods that are based on the combinatorics of Young diagrams. A known connection between Young diagrams and zero-dimensional polynomial ideals has allowed to develop an original approach to research of discrete dynamical systems for various natural processes. An example of those, given in the present work, are biochemical networks of the living cell. A special algorithm for enumeration of polynomial models was developed. The algorithm was also applied in the area of experimental design. (Existing algorithms were based on Grobner bases and did not guarantee to have all possible models in the output.) The algorithm is implemented in a software package, which also provides additional functionality for research related to the combinatorics of Young diagrams.

Подписано в печать 14.01.2013. Формат 60x84/16. Печать цифровая. Усл. печ. л. 1,0. Тираж 100. Заказ 10180Ь.

Отпечатано с готового оригинал-макета, предоставленного автором, в типографии Издательства Политехнического университета. 195251, Санкт-Петербург, Политехническая ул., 29. Тел.:(812)550-40-14 Тел./факс: (812) 297-57-76

Введение

Обзор литературы.

0.1. Диаграммы и таблицы Юнга.

0.2. Полиномиальные идеалы и базисы Грёбнера.

0.3. Полные полиномиальные модели

0.4. Комбинаторика диаграмм Юнга.

Актуальность работы. Во многих прикладных исследованиях встречаются задачи, связанные с полиномиальными моделями и системами полиномиальных уравнений. Например, к таким задачам относится задача нахождения дробного факторного плана и задача нахождения множества моделей, идентифицирумых заданным планом [1] в теории планирования эксперимента.

Микробиология также нуждается в полиномиальных моделях, чтобы по экспериментальным данным находить закономерности в процессах, проистекающих в живых клетках [2]. Возможность прямого наблюдения химических реакций в клетке исключена: реакции происходят с огромной частотой и не поддаются визуальному анализу. Однако, есть техническая возможность измерять уровень присутствия в клетке какого-либо вещества или белка в фиксированные моменты времени. В роли математической модели изучаемого процесса выступает динамическая система с дискретным временем, состояние которой определяется уровнем присутствия различных белков и веществ. Несколько этапов измерений, выполненных подряд, дают таблицу состояний этой системы. Состояние системы меняется в результате химических реакций.

Природу процессов, происходящих в клетке, принято представлять в форме т.н. биохимической сети. Биохимическая сеть кодирует зависимости между объектами-участниками происходящего процесса. Для получения информации о зависимостях требуется определить функции перехода между состояниями. В известных работах в данной области параметры состояния системы представляются дискретными величинами, чаще всего булевыми (есть белок А / нет белка А, есть вещество В / нет вещества В, и т.д.). Функции перехода между состояниями, таким образом, являются функциями в конечном поле. Следовательно, они являются полиномами, и задача сводится к построению полиномиальной модели зависимости состояния системы от состояния её в предыдущий момент времени.

При исследовании клетки нередки ситуации, когда на основании конкретных экспериментальных данных можно построить более одной полиномиальной модели, которая бы согласовалась с этими данными. Важным для исследований является вопрос: как получить все возможные модели, согласующиеся с экспериментальными данными? Аналогичный вопрос поднимается в теории планирования эксперимента: как получить полное множество полиномиальных моделей, идентифицируемым заданным экспериментальным планом? В работах по биохимическим системам, как и в работе [1] по планированию эксперимента, для получения множества полиномиальных моделей используются методы алгебраической статистики, возникшей в 1996 году [3]. В основе этих методов лежит связь полиномиальных моделей с нульмерными полиномиальными идеалами, и с особыми базисами этих идеалов — базисами Грёбнера, которые были придуманы в 1965 г. для символьного решения систем полиномиальных уравнений.

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

Целью диссертационной работы является создание инструмента для разработки и анализа полиномиальных моделей биохимических и других природных процессов. Новый инструмент, в отличие от имеющихся, позволит находить все без исключений полиномиальные модели, согласующиеся с исходными данными.

Математический аппарат, использованный для достижения поставленной цели, имеет в своей основе диаграммы Юнга — простые математические объекты, которые имеют прямое отношение к теории базисов Грёб-нера. Например, в статье [4] построение базиса Грёбнера основано на построении диаграммы Юнга, мономы которой порождают факторалгебру нульмерного идеала.

Переход от базисов Грёбнера к диаграммам Юнга позволил разработать алгоритм полного перебора полиномиальных моделей. Создание этого алгоритма было невозможно без решения ряда частных практических задач:

• Разработка алгоритмов для осуществления разнообразных операций с диаграммами Юнга. в Исследование связи диаграмм Юнга с мономиальными упорядочениями и базисами Грёбнера.

• Формулирование задач алгебраической статистики в терминах диаграмм Юнга.

Методы исследования. В работе использованы методы вычислительной коммутативной и компьютерной алгебры, теории базисов Грёбнера, теории представлений, методы математического моделирования, комбинаторные методы дискретной математики, методы вычислительной математики. Для реализации алгоритмов используется среда программирования Common Lisp, а также пакеты компьютерных прикладных программ Maxima и GFan.

На защиту выносятся следующие основные результаты:

• Предложен алгоритм, позволяющий эффективно осуществлять построение и анализ полиномиальных моделей различных природных процессов. Алгоритм основан на новом подходе к комбинаторике диаграмм Юнга, также предложенном в диссертации. Детально рассмотрено применение алгоритма в теории биохимических сетей. Решена задача построения биохимической сети процесса, происходящего в живой клетке (такого, как метаболизм лактозы или трансдукция различных сигналов), по набору последовательных дискретных состояний, полученных экспериментально. Доказана корректность работы алгоритма и показан синтетический пример, демонстрирующий его преимущества перед имеющимися алгоритмами.

• Разработанный алгоритм применен также в теории планирования эксперимента: решена задача нахождения статистического веера (statistical fan) полиномиальных моделей, идентифицируемых заданным планом эксперимента. (Из предыдущих работ были известны лишь алгоритмы нахождения алгебраического веера, algebraic fan). С помощью численного эксперимента исследованы отличия статистического веера от алгебраического для известных планов экперимента (Бокса-Бенкена, Бокса-Уилсона) в пространствах различной размерности.

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

• Реализованы алгоритмы для перебора таблиц Юнга произвольной размерности, соответствующих слабодопустимым, выпуклым и стро-годопустимым конечным мономиальным упорядочениям; найдено и доказано соответствие между конечными строгодопустимыми упорядочениями и начальными сегментами сигнатурных последовательностей.

• В теорию базисов Грёбнера введено понятие расширенного универсального базиса Грёбнера (EUGB): конструкции, не зависящей от строгого упорядочения мономов. Разработан алгоритм вычисления EUGB. Доказано несовпадение в общем случае UGB с EUGB. Обнаружено явление «сильной ненётеровости» полиномиальной редукции относительно набора полиномов, не зависящее от выбора конкретного полинома для деления.

• Реализован алгоритм порождения случайных двумерных диаграмм Юнга, распределённых по мере Планшереля. Проведены эксперименты по нахождению мат. ожидания и максимума нормализованной размерности неприводимых представлений.

• Реализован алгоритм порождения случайных d-мерных диаграмм Юнга, распределённых по мере Ричардсона. Предложен численный метод вычисления предельной формы многомерных диаграмм Юнга, а также численный метод анализа сходимости фронта диаграммы к предельной форме.

Научная новизна. Следующие результаты, полученные в диссертации, являются новыми:

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

• Представлены не опубликованные ранее алгоритмы для перебора таблиц Юнга произвольной размерности, соответствующих выпуклым и строгодопустимым конечным мономиальным упорядочениям.

• Введено новое понятие расширенного универсального базиса Грёбне-ра (EUGB) и разработан алгоритм вычисления EUGB. в Обнаружено явление «сильной ненётеровости» полиномиальной редукции.

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

Теоретическая значимость проделанной работы заключается прежде всего в том, что разработанные алгоритмы применяются и могут применяться в дальнейшем для установления и проверки различных гипотез из теории представлений и теории базисов Грёбнера; так, используя метод, предложенный в диссертации, автору удалось найти контрпример к ошибочно доказанной теореме в препринте статьи [5].

Другим значимым теоретическим результатом работы можно считать открытие явления «сильной ненётеровости».

Апробация работы. Основные результаты работы докладывались и обсуждались на:

• Международной конференции по полиномиальной компьютерной алгебре (РСА) (ММИ имени Эйлера, Санкт-Петербург, 2008, 2009, 2011);

• Международном рабочем совещании по компьютерной алгебре (Дубна, 2008);

• Семинаре по теории представлений и динамическим системам (ПОМИ, Санкт-Петербург, 2009).

• Научном семинаре кафедры прикладной математики (ФМФ СПбГПУ,

Санкт-Петербург, 2009)

• Международной конференции по параллельной компьютерной алгебре (Тамбов, 2010) в Научном семинаре в РУДН (Москва, 2012).

Достоверность результатов. Полученные в диссертации результаты обоснованы корректным использованием математических методов вычислительной коммутативной алгебры и комбинаторики. Достоверность подтверждается сопоставлением с результатами, доступными в открытой печати.

Публикации. Материалы диссертации опубликованы в 5 статьях в рецензируемых журналах [6-10], рекомендованных ВАК РФ для опубликования результатов кандидатских диссертаций.

Личный вклад автора. Работы [6, 8, 9] выполнены в соавторстве. Вклад соискателя в них заключается в:

• Разработке и реализации алгоритмов

• Проведении численного моделирования случайных процессов на диаграммах Юнга.

Структура и объем диссертации. Диссертация состоит из введения, пяти глав, заключения, списка цитируемой литературы и трёх приложений. Объем диссертации составляет 143 страницы (из них 13 занимают приложения). Кроме основного текста диссертация содержит 24 рисунка и список литературы из 89 наименований.

Основные результаты, полученные в диссертации

Итоги сделанной работе уже были подведены во вступлении, воспроизведём их здесь:

• Предложен алгоритм, позволяющий эффективно осуществлять построение и анализ полиномиальных моделей различных природных процессов. Алгоритм основан на новом подходе к комбинаторике диаграмм Юнга, также предложенном в диссертации. Детально рассмотрено применение алгоритма в теории биохимических сетей. Решена задача построения биохимической сети процесса, происходящего в живой клетке (такого, как метаболизм лактозы или трансдукция различных сигналов), по набору последовательных дискретных состояний, полученных экспериментально. Доказана корректность работы алгоритма и показан синтетический пример, демонстрирующий его преимущества перед имеющимися алгоритмами.

• Разработанный алгоритм применен также в теории планирования эксперимента: Решена задача нахождения полного веера (statistical fan) полиномиальных моделей, идентифицируемых заданным планом эксперимента. (Из предыдущих работ были известны лишь алгоритмы нахождения алгебраического веера, algebraic fan). С помощью численного эксперимента исследованы отличия полного веера от алгебраического для известных экспериментальных планов (Бокса-Бенкена, Бокса-Уилсона) в пространствах различной размерности.

• Реализованы алгоритмы для перебора таблиц Юнга произвольной размерности, соответствующих слабодопустимым, выпуклым и стро-годопустимым конечным мономиальным упорядочениям; на основании полученных числовых последовательностей найдено и доказано соответствие между конечными строгодопустимыми упорядочениями и начальными сегментами сигнатурных последовательностей.

• В теорию базисов Грёбнера введено понятие расширенного универсального базиса Грёбнера (Е11СВ): конструкции, не зависящей от строгого упорядочения мономов. Разработан алгоритм вычисления Е1ЮВ. Доказано несовпадение в общем случае 1ЮВ с Е11СВ. Обнаружено явление «сильной ненётеровости» полиномиальной редукции относительно набора полиномов, не зависящее от выбора конкретного полинома для деления. Это явление, имеющее место при некоторых недопустимых упорядочениях, было названо «сильной ненёте-ровостыо». Обнаруженный результат является уточнением результата [31] о «слабой» ненётеровости.

• Реализован алгоритм порождения случайных двумерных диаграмм Юнга, распределённых по мере Планшереля. Повторены и расширены до больших п эксперименты по нахождению мат. ожидания [67] и максимума [66] нормализованной размерности неприводимых представлений Зп.

• Реализован алгоритм порождения случайных ¿-мерных диаграмм Юнга, распределённых по мере Ричардсона. Предложен численный метод вычисления предельной формы многомерных диаграмм Юнга, а также численный метод анализа сходимости фронта диаграммы к предельной форме.

Благодарности

Автор выражает свою искреннюю признательность H.H. Васильеву за поставленные задачи и чуткое руководство, за постоянную поддержку и математическую интуицию.

Неоценимой в процессе работы над четвёртой главой была помощь

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

Третья глава не была бы написана без К. Усевича, благодаря которому автор познакомился с теорией планирования эксперимента и узнал о её связи с полиномиальной алгеброй.

Автор благодарит также: С. Шлосмана и А. Буфетова за любезно предоставленные статьи; Ю. А. Блинкова, В. П. Гердта, В. В. Корняка, А. Зобнина, Г. И. Малашонка, Е. Горячко, Ф. Петрова, Н. Цилевич, В. А. Пальмова, С.В. Стахова, A.A. Иванкова за ценные замечания и дискуссии на докладах и вне их; В. Е. Клавдиева, И. В. Штурца, С. Ю. Жукова, Ф. А. Новикова,

B. А. Галинского и Т. И. Курсиш за годы учёбы и участие.

За заботу и развитие автор признателен родителям, всем родственникам и отдельно дяде Мише и семье Минаевых.

Автор передаёт привет друзьям по походам: Н. Комлеву, И. Васильевой, их дочери Надежде, А. Бавыкину, В. Иващенко, В. Куликову, JI. Ма-лофеевой, В. Рыбко.

Автор бы ничего не сделал без поддержки своих друзей. Алексей, Валя, Денис, Дима, Женя, Игорь, Коля, Олег, Паша, спасибо вам.

Автор благодарен свой жене Даше за доброту, терпение и постоянную помощь во время работы.

Благодарности за программы

Об этом не принято говорить,'но программы действительно иногда помогают людям, и подчас их помошь незаменима. Автор благодарен создателям:

SBCL — за прекрасную реализацию Common Lisp; GNU Emacs и SLIME — за текстовый редактор и среду разработки; Шрифта Terminus и цветовой схемы charcoal-black — за то, что не болят глаза;

GFan — за знакомство с удивительными свойствами базисов Грёбне-ра;

Т^Ки ВТ^К— за компьютерную типографию;

Debian GNU/Linux — за операционную систему, на которой работает всё вышеперечисленное;

Google, Google Books, Google Scholar, Gigapedia.org, MathNet.ru, сайта препринтов ПОМИ — за возможность ходить в библиотеку, не вставая с кресла.

Заключение

1. Riccomagno Е., Caboara М., Pistone G., Wynn H. P. The fan of an experimental design // SCU Research Report. - 1997. - Vol. 10.

2. Pistone G., Wynn H. P. Generalised confounding with Grobner bases // Biometrica. 1996. - Vol. 83. - P. 653-666.

3. Faugere J.-C., Gianni P., Lazard D., Mora T. Efficient computation of zero-dimensional Grobner bases by change of ordering // Journal of Symbolic Computation. 1993. - Vol. 4, no. 16. - P. 329-344.

4. Kreuzer M., Poulisse H. Subideal Border Bases // Mathematics of Computation. 2011. - Vol. 80. - P. 1135-1154.

5. Васильев H. H., Павлов Д. А. Перечисление конечных мономиальных упорядочений и комбинаторика универсальных базисов Грёбнера // Программирование. 2009. - № 2. - С. 150-161.

6. Павлов Д. Алгоритм построения расширенного универсального базиса Грёбнера // Научно-Технические Ведомости СПбГПУ. 2008. - Т. 65, № 5. - С. 179-183.

7. Вершик А. М., Павлов Д. А. Численные эксперименты в задачах асимптотической теории представлений // Записки научных семинаров ПОМИ. 2009. - Т. 366, № 4.

8. Васильев Н. Н., Павлов Д. А. Сильная ненётеровость полиномиальной редукции // Записки научных семинаров ПОМИ. 2009. - Т. 373. -С. 73-76.

9. Павлов Д. А. Паралельное вычисление расширенных универсальных базисов Грёбнера // Вестник ТамГУ. 2010. - Т. 15. - С. 1405-1412.

10. Кокс Д., Литтл Д., О'Ши Д. Идеалы, многообразия и алгоритмы. Введение в вычислительные аспекты алгебраической геометрии и коммутативной алгебры. Москва: Мир, 2000. - ISBN: 5-03-003320-3.

11. Фултон У. Таблицы Юнга и их приложения к теории представлений и геометрии. Москва: МЦНМО, 2006. - ISBN: 5-94057-165-4.

12. Young A. On Quantitative Substitutional Analysis // Proc. London Math. Soc. 1928. - Vol. 2, no. 28. - P. 255-292.

13. Макдональд И. Симметрические функции и многочлены Холла. -Москва: Мир, 1984.

14. Вершик А. М., Керов С. В. Асимптотика меры Планшереля симметрической группы и предельная форма таблиц Юнга // Функциональный анализ и его приложения. 1977. - Т. 6, № 233. - С. 1024-1027.

15. Hilbert D. Uber die Theorie der algebraischen Formen // Math. Ann. -1890. Bd. 36. - S. 473-534.

16. Buchberger B. An Algorithm for Finding the Basis Elements in the Residue Class Ring Modulo a Zero Dimensional Polynomial Ideal: Ph. D. thesis / Mathematical Institute, University of Innsbruck, Austria. 1965.

17. Хованский А. Г., Чулков С. П. Геометрия полугруппы Z>0. Приложения к комбинаторике, алгебре и дифференциальным уравнениям. -Москва: МЦНМО, 2006. 2222 с. - ISBN: 5-94057-243-Х.

18. Collart S., Kalkbrener М., Mall D. Converting Bases with the Grobner Walk // J. Symb. Comput. 1997. - Vol. 24. - P. 465-469.

19. Tran Q.-N. A Fast Algorithm for Grobner Basis Conversion and its Applications //J. Symb. Comput. 2000. - Vol. 30. - P. 451-467.

20. Faugere J.-C. A new efficient algorithm for computing Grobner bases (F4) // Journal of Pure and Applied Algebra. 1999. - Vol. 139, no. 1. -P. 61-88.

21. Faugere J.-C. A new efficient algorithm for computing Grobner bases without reduction to zero (F5) // Proceedings of the 2002 international symposium on Symbolic and algebraic computation. New York: ACM, 2002. - P. 75-83.

22. Gerdt V. P., Blinkov Y. A. Involutive Bases of Polynomial Ideals // Mathematics and Computers in Simulation. 1998. - Vol. 45. - P. 519-452.

23. Gerdt V. P., Blinkov Y. A. Minimal involutive bases // Mathematics and Computers in Simulation. 1998. - Vol. 45, no. 5.

24. Robbiano L. Term ordering on the polynomial ring // Proceedings of EU-ROCAL '85 (Linz). Vol. 204 of Lecture Notes in Computer Science. -Springer, 1985. - P. 513-517.

25. Mora Т., Robbiano L. The Grobner fan of an ideal // Journal of Symbolic Computation. 1988. - Vol. 988, no. 6. - P. 183-208.

26. Jensen A. N. Gfan, a software system for Grobner fans and tropical varieties. - URL: http://www.math.tu-berlin.de/~jensen/software/ gf an/gf an. html.

27. Fukuda K., Jensen A. N., Lauritzen N., Thomas R. The generic Grobner walk // Journal of Symbolic Computation. 2007. - Vol. 42, no. 3. -P. 298-312.

28. Avis D., Fukuda K. Reverse Search for Enumeration // Discrete App. Math. 1993. - Vol. 65. - P. 21-46.

29. Васильев H. Выпуклые мономиальные упорядочения, многомерные диаграммы Юнга и базисы Грёбнера // Совместное заседание Семинара по вычислительной и прикладной математике ЛИТ и Семинара по компьютерной алгебре ВМК и НИИЯФ МГУ.- Дубна: 2006.

30. Reeves A., Sturmfels В. A Note on Polynomial Reduction // Journal of Symbolic Computation. 1993. - Vol. 16. - P. 273-277.

31. Стенли P. Перечислительная комбинаторика. Москва: Мир, 1990.

32. Euler L. De partitione numerorum // Novi Commentarii academiae scien-tiarum Petropolitanae. 1750. - Vol. 3. - P. 125-169.

33. Hardy G. H., Ramanujan S. Asymptotic formulae in combinatory analysis // Proc. London Math. Soc. 1918. - Vol. 17. - P. 76-92.

34. Rademacher H. On the partition function p(n) // Proc. London Math. Soc. 1937. - Vol. 43. - P. 241-254.

35. Кнут Д. Э. Искусство программирования, т. 4. Генерация всех сочетаний и разбиений. Санкт-Петербург: Вильяме, 2007.

36. MacMahon P. A. Combinatory Analysis. Cambridge: Cambridge University Press, 1916.

37. Wilson D. W. 10001 terms of OEIS sequence A000041. - URL: http: //www.research.att.com/~nj as/sequences/b000041.txt.

38. Hardy G. H., Wright E. M. An Introduction to the Theory of Numbers. -Oxford: Clarendon, 1938.

39. Andrews G. E. The Theory of Partitions. University Park, Pennsylvania: Pennsylvania State University, 1976.

40. Wright E. M. Asymptoci Partition Formulae I. Plane Partitions // Quarterly Journal of Mathematics. 1931. - no. 2. - P. 177-189.

41. Bressoud D. M. Proofs and Confirmations: The Story of the Alternating-Sign Matrix Conjecture. Cambridge: Cambridge University Press, 1999.

42. Noe T. D. URL: http://www.research.att.com/~njas/sequences/ b000219.txt.

43. Atkin A. O. L., Bratley P., McDonald I. G., McKay J. K. S. Some computations for m-dimensional partitions // Proc. Camb. Phil. Soc.- 1967. Vol. 63. - P. 1097-1100.

44. Mustonen V., Rajesh R. Numerical Estimation of the Asymptotic Behaviour of Solid Partitions of an Integer //J. Phys. A: Math. Gen. -2003. Vol. 36. - P. 6651-6659.

45. Bhatia D. P., Prasad M. A., Arora D. Asymptotic results for the number of multidimensional partitions of an integer and directed compact animals //

46. Journal of Physics A: Mathematical and General. 1997. - Vol. 30. -P. 2281-2285.

47. Шлосман С. Б. Конструкция Вульфа в статистической механике и комбинаторике // Успехи Математических Наук. 2001. - Т. 56, № 4(340).- С. 97-128.

48. McKay J. К. S. Partitions in natural order // Communications of the ACM. 1970. - Vol. 13, no. 1.

49. Bender E. A., Knuth D. E. Enumeration of plane partitions // Journal of Combinatorial Theory, Series A. 1972. - Vol. 13. - P. 40-54.

50. Knuth D. E. A Note on Solid Partitions // Mathematics of Computation.- 1970. Vol. 24, no. 112. - P. 855-961.

51. Skiena S. Implementing Discrete Mathematics. Redwood City, CA: Addison-Wesley, 1990. - ISBN: 0201509431.

52. Muir T. On Self-Conjugate Permutations // Proc. Royal Soc. Edinburgh.- 1889. Vol. 17. - P.,7-22.

53. Number of self-inverse permutations on n letters, also known as involutions; number of Young tableaux with n cells. URL: http://research.att. com/~njas/sequences/A000085.

54. Vasiliev N. Monomial Orderings, Young Diagrams and Grobner Bases // Proceedings of the International Conference "Computer Algebra in Scientific Computing" (CASC). Technical University of Munchen, 2003.

55. Mayr E., Meyer A. The complexity of the word problem for commutative semigroups and polynomial ideals // Adv. Math. 1982. - Vol. 46. -P. 305-329.

56. Lazard D. Gröbner Bases, Gaussian elimination and resolution of systems of algebraic equations // Proceedings of the European Computer Algebra Conference on Computer Algebra (EUROCAL). London, UK: Springer-Verlag, 1983. - P. 146-156.

57. Sloane N. J. A. The On-Line Encyclopedia of Integer Sequences. - URL: http://www.research.att.com/~nj as/sequences/index.html

58. Adams-Watters F. T. Number of initial segments of signature sequences of length n. - URL: http://research.att.com/~njas/sequences/ A163823.

59. Kimberling C. Fractal Sequences and Interspersions // Ars Combinatoria. 1997. - Vol. 45. - P. 157-168.

60. Ермаков С. M., Жиглявский А. А. Математическая теория оптимального эксперимента. Москва: Наука, 1987.

61. Maruri-Aguilar H. Universal Gröbner Bases for Designs of Experiments // Rend. Istit. Mat. Univ. Trieste. 2005. - Vol. 37. - P. 95-119.

62. Möller H. M., Buchberger B. The Construction of Multivariate Polynomials with Preassigned Zeros // European Conference on Computer Algebra. -1982. P. 24-31.

63. Caboara M., Robbiano L. Families of Estimable Terms // Proceedings ofthe 2001 international symposium on Symbolic and algebraic computation. ACM New York, 2001.

64. Usevich K. Polynomial-exponential 2D data models, Hankel-block-Hankel matrices and zero-dimensional ideals // Proceedings of the International Conference on Polynomial Computer Algebra (PCA). EIMI, St. Petersburg, Russia, 2011.

65. McKay J. The Largest Degrees of Irreducible Characters of the Symmetric Group // Math. Сотр. 1976. - Vol. 30, no. 135. - P. 624-631.

66. Вершик A. M., Грибов А. В., Керов С. В. Эксперименты по вычислению размерности типичного представления симметрической группы // Записки научн. семин. ЛОМИ. 1983. - Т. 123. - С. 152-154.

67. Rost Н. Non-equilibrium behaviour of a many particle process: Density profile and local equilibria // Probability Theory and Related Fields. -1981. Vol. 1, no. 58. - P. 41-53.

68. Richardson D. Random growth in a tesselation // Proc. Cambridge Phil. Soc. 1973. - Vol. 74. - P. 515-528.

69. Wulff G. Zur frage der geschwindigkeit des wachsturms under auflosung der kristallflachen // Z. Kristallogr. 1901. - Bd. 34. - S. 449-530.

70. Shlosman S. Applications of the Wulff Construction to the Number Theory // Journal of Mathematical Sciences. 2007. - Vol. 126, no. 2. -P. 1128-1132.

71. Ferrari P. L., Spohn H. Step Fluctuations for a Faceted Crystal // Journal of Statistical Physics. 2004. - Vol. 112, no. 1-2. - P. 1-46.

72. Вершик А. М., Керов С. В. Асимптотика максимальной и типичной размерностей неприводимых представлений симметрической группы // Функциональный анализ и его приложения. 1985. - № 1. -С. 25-36.

73. Cerf R., Kenyon R. The Low-Temperature Expansion of the Wulff Crystal in the 3D Ising Model // Communications in Mathematical Physics. -2001. Vol. 222, no. 1. - P. 147-179.

74. Okounkov A., Reshetikhin N. Correlation function of Schur process with application to local geometry of a random 3-dimensional Young diagram // J. Amer. Math. Soc. 2003. - Vol. 16. - P. 581-603.

75. Rajesh R., Dhar D. An Exactly Solvable Anisotropic Directed Percolation Model in Three Dimensions // Phys. Rev. Lett. 1998. - Vol. 81. -P. 1646-1649.

76. Вершик A. M. Предельное распределение энергии квантового идеального газа с точки зрения теории разбиений натуральных чисел // Успехи математических наук. 1997. - Т. 52, № 2 (314).

77. Robinson G. On the Representations of the Symmetric Group // American Journal of Mathematic. 1938. - Vol. 60, no. 3. - P. 745-760.

78. Schensted C. Longest increasing and decreasing subsequences // Canadian Journal of Math. 1961. - Vol. 13. - P. 179-191.

79. Knuth D. E. Permutations, matrices, and generalized Young tableaux // Pacific J. Math. 1970. - Vol. 34, no. 3. - P. 709-727.

80. Vershik A. M., Tsilevich N. V. Induced representations of the infinite symmetric group // Pure Appl. Math. Quart. 2007. - Vol. 3, no. 4. -P. 1005-1026.

81. Specht W. O. L. Die irreduziblen Darstellungen der symmetrischen Gruppe // Mathematische Zeitschrift. 1935. - Bd. 39.

82. Вершик А. M., Окуньков А. Ю. Индуктивный способ изложения теории представлений симметрических групп // Успехи математических наук. 1996. - Т. 51, № 308. - С. 153-154.

83. Baer R. М., Brock Р. Natural Sorting over Permutation Spaces // Math. Comp. 1968. - Vol. 22. - P. 385-410.

84. Frame J. S., de В. Robinson G., Thrall R. M. The Hook Graphs of the Symmetric Group // Canadian Journal of Mathematics. 1954. - Vol. 6. - P. 316-324.

85. Greene C., Nijenhuis A., Wilf H. S. A Probabilistic Proof of a Formula for the Number of Young Tableaux of a Given Shape // Advances in Mathematics. 1979. - Vol. 31. - P. 104-109.

86. Bufetov A. I. On the Vershik-Kerov Conjecture Concerning the Shan-non-Macmillan-Breiman Theorem for the Plancherel Family of Measures on the Space of Young Diagrams. - 2012. - URL: http: //arxiv. org/ abs/1001.4275.

87. Olejarz J., Krapivsky P. L., Redner S., Mallick K. Growth Inside a Corner: The Limiting Interface Shape // Phys. Rev. Lett. 2012. —Jan. -Vol. 108. - P. 016102. - URL: http://link.aps.org/doi/10.1103/ PhysRevLett.108.016102.89. URL: http://www.sbcl.org.