Специалисты факультета вычислительной математики и кибернетики Московского государственного университета разработали стохастическую модель для анализа временной сложности вычислительных алгоритмов, работающих с базами данных.
Новый подход к оценке производительности информационных систем
Подход, который предлагают московские специалисты, позволяет более точно оценивать поведение алгоритмов в условиях неопределённости и вариативности входных данных, характерных для практических вычислительных систем.
Отличие нового метода в том, что он не ограничивается такими оценками выполнения сценариев как «худший случай» или «средний случай», а позволяет учитывать при работе с базами данных множество случайных факторов. Для него имеет значение структура запросов, распределение данных, порядок доступа и особенности взаимодействия компонентов системы. Разработка МГУ учитывает все эти факторы с помощью стохастических моделей.
Как сообщает пресс-служба МГУ, авторы рассматривают вычислительный процесс как случайный и описывают его через вероятностные характеристики времени выполнения. Этот механизм позволяет получать не только асимптотические оценки, но и анализировать время работы алгоритмов, что даёт более точное представление о производительности систем в реальных условиях эксплуатации.
«Использование стохастических моделей позволяет более точно описывать временную сложность вычислительных задач в условиях взаимодействия с базами данных. Такой подход даёт возможность учитывать реальные сценарии работы вычислительных систем и оценивать их поведение не только в теории, но и в прикладных условиях», – отмечает Андрей Борисов, профессор кафедры математической статистики ВМК МГУ.
Поскольку повышение качества оценки алгоритмов – одна из фундаментальных задач компьютерной науки, в перспективе разработка МГУ поможет повысить эффективность инфраструктуры крупных проектов (обработка данных, интернет-сервисы, банкинг, госуслуги).
Игорь Соколов - академик РАН, декан факультета вычислительной математики и кибернетики МГУ имени М.В. ЛомоносоваДа, уровень подготовки наших программистов очень высокий. Однако надо думать о том, чтобы готовить не только программистов, но и людей, которые способны разрабатывать инструменты для программистов – операционные системы, системы управления базами данных, алгоритмические языки, компиляторы. Все, что составляет инструментарий, которым потом пользуется программист
Экспортный потенциал
Прямой экспортный потенциал разработки представляется достаточно ограниченным в силу того, что это – не программный пакет, а методологическая модель. Однако если идея будет реализована в конкретных инженерных продуктах, ситуация может измениться.
По мнению экспертов, модель может быть использована при разработке коммерческих инструментов оценки производительности, в оптимизаторах компиляторов, в инструментах APM (Application Performance Monitoring).
Внутри России модель может быть включена в образовательные программы по алгоритмам и теории сложности, а также использоваться в корпоративной аналитике для оценки и тестирования крупных проектов.
Примеры похожих исследований
Анализ поведения алгоритмических систем может быть частью научных исследований по многим смежным направлениям. Например, специалисты из того же МГУ уже несколько лет используют его для идентификации киберугроз в системах машинного обучения и моделирования их воздействия.
Другой пример связан с изучением нашей планеты. В этом году ученые МГУ вместе с коллегами из Института вычислительной математики предложили новый способ обработки данных, поступающих со спутников с задержкой. Новый подход позволит повысить точность прогнозов с использованием дистанционного зондирования Земли. Он позволяет учитывать неравномерно поступающие данные при численном моделировании динамических процессов. Предложенные методы могут использоваться при обработке данных дистанционного зондирования Земли, а также в других задачах моделирования, где требуется восстановление состояния системы по запаздывающей или неполной информации.
Прогнозы развития
Говоря в целом о значении новой разработки ВМУ МГУ, можно утверждать, что она стала важным шагом в теории оценки алгоритмов, сделав эту науку более практико-ориентированной. Дальнейшие исследования в этом направлении могут создать на основе теоретической модели конкретные практические решения – библиотеки, инструменты тестирования. Вероятно, такие разработки могут появиться уже в течение ближайших 2-3 лет. Также за счёт интереса к точному моделированию алгоритмического поведения возможна интеграция идей с искусственным интеллектом.