ВВЕДЕНИЕ 5
1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ 9
1.1. Анализ предметной области и обзор существующих алгоритмов 9
1.2. Разработка базового алгоритма 11
1.3. Разработка параллельного алгоритма 15
2. РЕАЛИЗАЦИОННАЯ ЧАСТЬ 17
3. ЭКСПЕРИМЕНТАЛЬНАЯ ЧАСТЬ 22
3.1. Исследование ускорения алгоритма 22
3.2. Анализ полученных результатов 25
ЗАКЛЮЧЕНИЕ 38
ЛИТЕРАТУРА 39
Разбиением натурального числа называется его представление в виде суммы натуральных слагаемых [11]. Разбиения считаются одинаковыми, если они различаются только порядком слагаемых. Разбиение с элементами а1, ..., ак обозначается как [а1л, ак]. Например, для 5 имеем разбиения:
5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1.
Пусть p(n) обозначает количество всех разбиений натурального числа n. Для небольших n легко вычислить p(n), просто выписав все разбиения. Например, p(5) = 7. Все 7 разбиений числа 5 представлены выше. Однако получить таким способом, скажем, p(100) = 190 569 292 или p(200) = 3 972 999 029 388 без помощи компьютера немыслимо. Таким образом, основная трудность работы с разбиениями больших чисел состоит в том, что число их растет экспоненциально. Вопросы, связанные с разбиениями, очень часто встречаются в комбинаторике, теории чисел, алгебре и других областях математики.
Актуальность
Одной из актуальных задач, связанных с разбиениями чисел, является вычисление рангов групп центральных единиц целочисленных групповых колец знакопеременных групп, используя разбиения натурального числа.
Из результата Р. Ферраза и [1, 3, 8, 9, 16, 18] следует, что ранг группы I/(Z(ZAn)) центральных единиц целочисленного группового кольца знакопеременной группы Ап равен количеству разбиений а1 + —+ ак натурального числа п, удовлетворяющих следующим свойствам:
1) atнечетно, 1
2) at A a.j, при i Ay;
3) п = к (mod4);
4) Пк=1а[ не является квадратом натурального числа.
Введем следующие обозначения для данного натурального числа п:
- г(п) - количество разбиений, удовлетворяющих условиям 1)-2);
- r(mod4)(ri) -количество разбиений, удовлетворяющих
условиям 1)-3);
- Г(1 mOd8)(ri)- это подмножество r(mod4)(ri), для которого n = 1 (mod 8);
- squares(ri)- количество разбиений, удовлетворяющих условиям 1)-3), но неудовлетворяющих условию 4);
- rank(ri)- количество разбиений, удовлетворяющих условиям 1)4) .
Данное исследование посвящено вопросу о числе разбиений, произведение элементов которых даёт квадрат натурального числа (т.е. условие 4) не выполняется), причем элементы должны быть различными нечетными числами, и число элементов разбиения должно быть сравнимо по модулю 4 с исходным числом. Легко понять, что четвертое условие самое трудоемкое.
Существует не один алгоритм вычисления рангов, например, описанные в [6], [7] и [13]. Для получения общих знаний о поведении функции squares(n) важно исследовать влияние отдельных вышеприведенных условий на ранги.
Для поиска количества squares(ri)было решено придумать алгоритм, разработать на основе этого алгоритма программу, оценить количество искомых квадратов, найти закономерности в поведении функции squares(ri).
В связи с экспоненциальным ростом числа разбиений n трудно дать оценку количеству разбиений, удовлетворяющих требуемым условиям. Для этого разрабатывается параллельный алгоритм для запуска на многоядерных сопроцессорах суперкомпьютера «Торнадо ЮУрГУ», который позволит достичь больших ri.
Цель и задачи
Основной целью работы является создание программы поиска количества состоящих из различных нечетных чисел разбиений, произведение элементов которых дает квадрат натурального числа, причем число элементов разбиения должно быть сравнимо по модулю 4 с исходным числом.
Для достижения поставленной цели необходимо решить следующие задачи:
- проанализировать предметную область;
- изучить существующие алгоритмы;
- разработать эффективный алгоритм поиска количества разбиений, произведение элементов которых дает квадрат натурального числа, причем элементы должны быть различными нечетными числами, а число элементов разбиения должно быть сравнимо по модулю 4 с исходным числом;
- распараллелить разработанный алгоритм;
- реализовать программу для подсчета требуемых квадратов в разбиениях на основе параллельного алгоритма;
- проанализировать полученные результаты, понять характер функции squares(n)и найти закономерности в ее поведении.
Структура и объем работы
Работа состоит из введения, трех основных разделов, заключения и библиографии. Объем работы составляет 38 страниц, объем библиографии - 20 наименований.
Содержание работы
В первом разделе представлены предметная область и разработанные на основе существующих алгоритмы для поиска требуемых квадратов в разбиениях натуральных чисел.
Во втором разделе описана реализация алгоритма поиска количества разбиений, произведение элементов которых дает квадрат натурального числа, причем элементы разбиения должны быть нечетными различными числами, а число элементов разбиения сравнимо по модулю 4 с исходным числом, и приведены полученные данные для ряда чисел.
В третьем разделе описаны полученные результаты, проведен анализ поведения искомых квадратов в зависимости от n и приведены различные графики ускорения алгоритма.
В заключении приводятся основные результаты работы.
Результатом работы является параллельный алгоритм, вычисляющий количество разбиений, произведение элементов которых дает квадрат натурального числа, причем элементы разбиения должны быть различными нечетными числами, число элементов разбиения сравнимо по модулю 4 с исходным числом, а также приведены полученные данные для ряда больших п.
Были решены следующие задачи:
- проанализирована предметная область и аналогичные алгоритмы для разбиения целых чисел;
- разработан последовательный алгоритм поиска числа искомых разбиений;
- разработана параллельная версия разработанного алгоритма;
- реализована программа для подсчета требуемых квадратов в разбиениях;
- проанализированы полученные результаты, время выполнения алгоритмов и ускорение.
Публикации по теме работы
Алеев Р.Ж., Семенихина П.Н. Использование суперкомпьютера «Торнадо- ЮУрГУ» для задач, связанных с разбиениями натуральных чисел // Параллельные вычислительные технологии (ПаВТ’2016): труды международной научной конференции (28 марта - 1 апреля 2016 г., г. Архангельск). - Челябинск: Издательский центр ЮУрГУ, 2016. - С. 752.
