|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
Сложность реализации сверхбольших перестановокдипломная работа (Бакалавр)
- Научный руководитель: Гасанов Эльяр Эльдарович
- Автор: Ковальский Алексей Станиславович
- Тип: Бакалавр
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Год защиты: 2020
- Аннотация: В работе Алексея Ковальского исследуется задача реализации перестановок при условии, что оперативной памяти хватает только на хранение 5 – 20% перестановки, а остальная перестановка хранится на внешнем носителе. Сложность вычисления перестановки измеряется как среднее значение обращений к внешнему носителю. В работе получены аналитические расчеты сложности реализации сверхбольших перестановок при некоторых ограничениях на функции распределения запросов. Реализовано несколько алгоритмов вычисления перестановок и проведен компьютерный эксперимент по оценке сложности вычисления для разных распределений запросов на значение перестановки. Эксперименты проведены для разных объемов оперативной памяти (5, 10 и 20 % от размера перестановки). Показано, что предложенные алгоритмы несравнимы и каждый из алгоритмов может быть полезен на каком-то своем потоке запросов.
- Добавил в систему: Гасанов Эльяр Эльдарович