Полиномиальные модели, основанные на диаграммах Юнга тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Павлов, Дмитрий Алексеевич

• Павлов, Дмитрий Алексеевич
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Павлов, Дмитрий Алексеевич

Введение

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

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, сайта препринтов ПОМИ — за возможность ходить в библиотеку, не вставая с кресла.

Заключение

Список литературы диссертационного исследования кандидат физико-математических наук Павлов, Дмитрий Алексеевич, 2012 год

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.