• /
• Кафедры /
• Кафедра информатики /
• Научно-исследовательская работа /

Кафедра информатики

Научно-исследовательская работа

На кафедре проводятся исследования по теории алгоритмов, теории моделей, математической лингвистике, базам данных, Web-разработке и другие.

Основные направления исследований и результаты

Математическая логика и теория алгоритмов

Изучаются языки первого порядка и их неэлементарные расширения, рассматриваются выразительные возможности соответствующих теорий, их разрешимость и алгоритмическая сложность.

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

Математическая лингвистика

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

• Определена нормальная форма для классов КГЗ (категориальных грамматик зависимостей) и ммКГЗ (мультимодальных КГЗ), аналогичная нормальной форме Грейбах для КС-грамматик, и установлена возможность эффективного приведения всякой КГЗ и ммКГЗ к этой нормальной форме.
• Доказаны свойства замкнутости для классов КГЗ-и ммКГЗ-языков относительно операций объединения, пересечения с регулярными языками, неукорачивающего гомоморфизма, обращения гомоморфизма и конкатенации. Установлено, что класс ммКГЗ-языков также замкнут относительно усечённой итерации и образует абстрактное семейство языков.
• Доказано, что любой КГЗ-язык можно представить как проекцию пересечения КС-языка и скобочного языка, состоящего из слов, проекции которых на каждый тип скобок являются правильными скобочными словами.
• Построено расширение автоматов с магазинной памятью (МП-автоматов) - МП-автоматы с независимыми счётчиками. Эти автоматы дополняют обычные МП-автоматы конечным числом целочисленных счётчиков. Их отличие от машин Минского состоит в отсутствии проверки счётчиков на ноль. Доказано, что МП-автоматы с независимыми счётчиками без пустых циклов распознают в точности КГЗ-языки.
• Показано, что класс ммКГЗ-языков содержит неполулинейные языки, в отличие от класса КС-языков.
• Доказано, что проблема принадлежности слова ммКГЗ-языку является NP-полной для конкретной ммКГЗ.
• Определено обобщение систем переходов на случай предложений с непроективными зависимостями. Реализован алгоритм для анализа предложений за один проход с использованием систем переходов.
• Определены МП-автоматы со стеками независимых счётчиков и доказано, что автоматы без пустых циклов распознают в точности ммКГЗ-языки.
• Определены (m, n)-жёсткие категориальные грамматики. Построен алгоритм, который по грамматике G и числам m, n определяет, является ли G (m, n)-жёсткой.
• Доказано, что в классе (m, n)-жёстких языков существует бесконечная иерархия, а также что класс (m, n)-жёстких языков несравним с классом регулярных языков.
• Доказано, что для (m, n)-жёстких категориальных грамматик зависимостей проблема принадлежности разрешима за полиномиальное время.

Базы данных

Изучаются как теоретические вопросы, связанные с выразительными возможностями языков запросов, так и вопросы практического применения СУБД и разработки приложений для них. Рассматриваются как классические реляционные модели хранения данных, так и другие варианты: noSQL-СУБД, гетерогенные базы данных и т.д.

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

Web-технологии

Изучаются как вопросы практической разработки Web-приложений, так и связанные теоретические вопросы: оценки качестваWeb-сервисов, анализ больших социальных сетей и т.д.

• Решена проблема моделирования работы Web-сервиса (рост области определения результирующей случайной величины) с помощью группирующей случайной величины.
• Построена модель качества Web-сервиса, которая основана на вероятностном подходе и рассматривает 5 базовых структурных  конструкций, каждая из которых организует сервисы-компоненты уникальным образом.
• Реализован программный продукт, который позволяет рассчитать качество композитного Web-сервиса.
• Построена модель структуры данных для хранения «постов» в социальных сетях, реализованная для Postgres и MongoDB. Получена оценка производительности БД с помощью созданной модели.
• Реализован программный продукт, который реализует модель БД, и позволяет рассчитать различные параметры Postgres и MongoDB при использовании их в социальных сетях

Математическое моделирование бизнес-процессов

• Для описания иерархических систем управления введён графический язык иерархических типизированных диаграмм HTD (The Hierarchical Typified Diagrams Language, HTD-язык). Введен новый тип диаграмм – канонические диаграммы, исключающие из рассмотрения изоморфные диаграммы в языке HTD. Это позволяет графически однозначно описывать иерархические бизнес-процессы. Предложено решение задачи контроля выводимости канонической диаграммы, строящейся после каждого действия оператора. Доказано, что по существующему в алгебре D выражению V можно однозначно построить диаграмму К тогда и только тогда, когда К – каноническая диаграмма.
• Предложен генетический алгоритм многокритериальной оптимизационной задачи распределения ресурсов сотрудников контактного центра, что позволяет оперативно составлять расписания, учитывающие ограничения как на входящий трафик, так и на наличие у сотрудников различных типов рабочих смен и нескольких навыков. Для решения задачи нахождения оптимального решения системы ограничений использования доступных ресурсов предложен модифицированный генетический алгоритм, представляющий соединение канонического и genitor генетических алгоритмов. Введены критерии проверки вырождения популяции, контроль количества скрещиваний и мутаций, проведена оптимизация вычисления разряженных матриц, так как в реальных условиях количество различных классов навыков достаточно невелико.

Выпускники кафедры, имеющие ученую степень:

• Дадеркин Дмитрий Ольгердович, Математический институт РАН, 1989, кандидат физико-математических наук
• Архангельский Дмитрий Авенирович, Математический институт РАН, 1993, кандидат физико-математических наук
• Дудаков Сергей Михайлович, Московский госуниверситет им.Ломоносова, 2000 кандидат физико-математических наук, 2007, доктор физико-математических наук
• Рыбкин Владимир Александрович, Тверской госуниверситет, 2000, кандидат физико-математических наук
• Дехтярь Александр Михайлович, Мерилендский университет, 2000, PhD
• Сорокин Сергей Владимирович, Тверской госуниверситет, 2004, кандидат физико-математических наук
• Солдатенко Илья Сергеевич, Тверской госуниверситет, 2009, кандидат физико-математических наук
• Новикова Виктория Николаевна, Тверской госуниверситет, 2010, кандидат физико-математических наук
• Карлов Борис Николаевич, Ярославский госуниверситет им.Демидова, 2012, кандидат физико-математических наук
• Снятков Алексей Сергеевич, Ярославский госуниверситет им.Демидова, 2012, кандидат физико-математических наук
• Золотов Александр Сергеевич, Приволжский (Казанский) федеральный университет, 2017, кандидат физико-математических наук