Сотрудники факультета вычислительной математики и кибернетики Московского государственного университета им. М.В. Ломоносова создали вероятностную модель для изучения временной сложности вычислительных алгоритмов, применяемых в базах данных. Данная методика дает возможность точнее определять характеристики работы алгоритмов в ситуациях, когда входные данные отличаются неопределенностью и изменчивостью, что типично для реальных вычислительных систем.
Результаты исследования опубликованы в Международный журнал по компьютерным и системным наукам .
Традиционные подходы к определению временной сложности обычно основываются на детерминированных оценках и предполагают предсказуемые сценарии работы алгоритмов. Но при анализе баз данных и распределенных систем на время выполнения оказывают значительное влияние непредсказуемые факторы, такие как структура запросов, распределение данных, последовательность доступа и особенности взаимодействия между компонентами системы. В рамках новой работы предложено использовать стохастические модели для учета данных факторов.
В работе авторы представляют вычислительный процесс как случайный и характеризуют его вероятностными показателями, определяющими время его выполнения. Это позволяет не только вычислять асимптотические значения, но и определять распределение времени, затрачиваемого алгоритмами, что обеспечивает более детальное понимание производительности систем при реальном использовании.
«Применение стохастических моделей позволяет точнее воспроизводить временную зависимость вычислительных задач, возникающую при взаимодействии с базами данных. Это дает возможность учитывать фактические сценарии функционирования вычислительных систем и оценивать их характеристики как в теоретических, так и в практических ситуациях» , — отмечает Андрей Борисов, профессор кафедры математической статистики ВМК МГУ.
Разработанная модель способна оказаться полезной при создании и совершенствовании алгоритмов обработки данных, а также при оценке эффективности информационных систем. В таких системах важно учитывать не только минимальное и среднее время отклика, но и вероятность возникновения задержек. Полученные в ходе исследования данные будут полезны специалистам, работающим в сфере теории алгоритмов, анализа данных и разработки вычислительных систем, предназначенных для обработки больших объемов информации.
Информация предоставлена пресс-службой МГУ