Важнейшие результаты исследований ИПМИ в 2013 г.

2013 г.
1. Исследовано предельное поведение числа петель вершин и общего числа петель случайного конфигурационного графа, моделирующего структуру и динамику развития современных сложных сетей телекоммуникаций (ИПМИ КарНЦ РАН, д.ф.-м.н. проф. Ю.Л. Павлов).
Направление 1 – Теоретическая математика

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

2. Разработан подход и спроектирована архитектура системы автоматизированного построения общецелевой лексической онтологии на основе онлайн-словаря (ИПМИ КарНЦ РАН, к.т.н. А.А. Крижановский).
Направление 7 – Информационно-вычислительные системы и среды в науке и образовании

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

3. Разработаны математические модели процесса работы с M FIFO-очередями и LIFO-стеками, на базе которых решена задача Р. Седжвика нахождения формул для вероятности исключения из пустой очереди и для математического ожидания длины очереди на N-м шаге и построены алгоритмы оптимального управления рассмотренными структурами данных (ИПМИ КарНЦ РАН, д.ф.-м.н. проф. А.В. Соколов).
Направление 5 – Теоретическая информатика и дискретная математика

Аннотация: Разработаны математические модели процесса работы с M FIFO-очередями и LIFO-стеками в случае их последовательного и связанного представления. Построены алгоритмы оптимального управления стеками и очередями. Решена задача, поставленная Р. Седжвиком, которая заключается в следующем. Рассмотрена система из M FIFO-очередей в памяти одного уровня. На каждом нечетном шаге дискретного времени в одну из очередей с равными вероятностями 1/M происходит включение элемента, а на каждом четном шаге - исключение элемента. Получены аналитические формулы для вероятности исключения из пустой очереди и для средней длины очереди на N-м шаге. Разработаны математические и имитационные модели процесса работы c двумя параллельными FIFO-очередями и решается задача оптимального разбиения общей памяти для двух FIFO-очередей в случае их последовательного циклического представления в предположении, что на нечетном шаге допускаются операции включения элементов в одну из очередей, а на четном шаге - операции исключения элементов из очередей, причем, наряду с последовательным, возможно и параллельное выполнение операций с очередями с заданными вероятностями. В качестве критерия оптимальности рассмотрена минимальная доля потерянных при переполнении памяти элементов очередей на бесконечном времени. Для решения поставленных задач используется аппарат управляемых случайных блужданий, регулярных и поглощающих цепей Маркова, система Intel® Math Kernel Library PARDISO. Анализируются результаты численных экспериментов. Вычисления производились с помощью кластера КарНЦ РАН.