Publication: Разработка модифицированного интервального алгоритма поиска простых чисел
Дата
2016
Авторы
Варыханов, С. С.
Journal Title
Journal ISSN
Volume Title
Издатель
Аннотация
Аннотация Дипломный проект посвящён модификации и реализации интервального алгоритма поиска простых чисел в заданном диапазоне, а также возможность работы с числами произвольной разрядности. Для ускорения поиска применяется многопоточное программирование для многоядерных процессоров и технология параллельных вычислений на видеокарте NVIDIA CUDA. Во время дипломного проектирования изучен и модифицирован интервальный алгоритм генерации простых чисел для работы с числами большой разрядности, а также добавлен новый режим поиска с заданной вероятностью. Найдены функции сложности модифицированного алгоритма для различных режимов работы. Реализована библиотека функций для работы с числами большой разрядности. Реализованы две версии программы поиска простых чисел в заданном интервале для выполнения на CPU и GPU. Для каждой программы есть версия для работы с числами произвольной разрядности, а также для чисел, размер которых не превышает 64 бит. В первой главе рассматриваются алгоритмы поиска простых чисел и проверки числа на простоту, также там подробно рассматривается k-индексный алгоритм, на модификации которого основана данная дипломная работа, также присутствует краткое описание технологии NVIDIA CUDA. Вторая глава посвящена модификации интервального алгоритма и оценки его сложности при различных входных диапазонах поиска. Введён режим поиска простых чисел с заданной вероятностью и исследована возможность применения кольцевой факторизации для ускорения поиска простых чисел. Также описываются методы и алгоритмы для работы с числами большой разрядности. Третья глава посвящена описанию процесса проектирования и разработки программ поиска простых чисел в интервале, а также процессу отладки, проверке достоверности результатов и тестированию скорости их работы. В заключении описаны результаты дипломного проектирования. Пояснительная записка содержит 209 страниц, 19 рисунков, 29 таблиц и 3 приложения.
Описание
Уровень образования: бакалавриат; Код направления/специальности: 09.03.01; Группа: К06-12с
Ключевые слова
ВКР , Выпускная квалификационная работа
Цитирование
Варыханов, С. С. Разработка модифицированного интервального алгоритма поиска простых чисел : Выпускная квалификационная работа, бакалавриат, 09.03.01 / С. С. Варыханов ; рук. работы Васильев Н.П., 2016