ВВЕДЕНИЕ 3
ГЛАВА 1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ 6
1.1. Анализ предметной области и обзор существующих алгоритмов 6
1.2. Разработка основной части последовательного алгоритма 9
1.3. Разработка функции проверки квадратов 16
ГЛАВА 2. РЕАЛИЗАЦИОННАЯ ЧАСТЬ 23
2.1. Разработка параллельного алгоритма 23
2.2. Описание программы 26
ГЛАВА 3. ЭКСПЕРИМЕНТАЛЬНАЯ ЧАСТЬ 34
3.1. Тестирование программы и результаты её работы 34
3.2. Расчёт ускорения и эффективности 36
3.3. Анализ полученных результатов 38
ЗАКЛЮЧЕНИЕ 48
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 50
ПРИЛОЖЕНИЕ 1
Купить

Разбиением натурального числа nназывается представление nв виде суммы положительных целых чисел - частей или элементов разбиения. При этом их порядок, в отличие от композиций, не учитывается: два разбиения, отличающиеся только порядком слагаемых, являются равными. Разбиение принято записывать в порядке невозрастания его частей. Таким образом, разбиение с элементами a1>a2> ... >akзаписывается в каноническом виде как {ai, a2, ... , ak}.
Общее количество разбиений натурального числа nобозначается p(n). Все возможные разбиения небольших nлегко найти простым перебором. Например, для n = 6 имеем:
{6}, {5, 1}, {4, 2}, {4, 1, 1}, {3, 3}, {3, 2, 1}, {3, 1, 1, 1}, {2, 2, 2}, {2, 2, 1, 1}, {2, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1}.
Таким образом, p(6) = 11. Однако при возрастании nперебор вручную становится неэффективным: получение p(24) = 1575 или p(45) = 89134 разбиений без помощи компьютера требует расхода значительного количества времени и усилий. Вместе с тем задачи, связанные с разбиениями, регулярно встречаются в различных областях математики, в первую очередь в комбинаторике и теории чисел.
Одной из актуальных задач, связанных с разбиениями чисел, является вычисление рангов групп центральных единиц целочисленных групповых колец знакопеременных групп, используя разбиения числа. Известно [6], что ранг группы центральных единиц целочисленного группового кольца знакопеременной группы Anравен количеству разбиений числа n, удовлетворяющих следующим свойствам:
1) Все части разбиения нечётны;
2) Части разбиения попарно различны;
3) (n- k) делится на 4, где k- количество частей разбиения;
4) Произведение всех частей разбиения не является квадратом натурального числа.
Введём следующие функции для натурального аргумента п:
• r(п) - количество разбиений числа п, удовлетворяющих условиям
1) - 2);
• r4(п) - количество разбиений числа п, удовлетворяющих условиям
1) - 3);
• гапк (п) - количество разбиений числа п, удовлетворяющих условиям
1) - 4);
• sqrs (п) - количество разбиений числа п, удовлетворяющих условиям
1) - 3), но не удовлетворяющих условию 4).
На данный момент существуют алгоритмы для нахождения значений функции гапк (п), но пока нет такого, который выполняет это действие за приемлемое время. Вместе с тем, очевидно, что гапк (п) = r4(п) - sqrs(п), то есть для расчёта рангов достаточно уметь находить значений функций r4(п) и sqrs (п). В данной работе будет решена задача расчёта этих функций, причём особое внимание будет уделяться функции sqrs (п) в силу того, что условие 4 самое сложное с практической точки зрения.
Основной целью данной работы является разработка параллельного алгоритма для вычисления значений функции sqrs (п), то есть нахождение количества разбиений натурального числа п из различных нечётных натуральных слагаемых, таких, что их произведение является квадратом натурального числа, а разность между их количеством и п делится на 4.
Для достижения данной цели необходимо решить следующие задачи:
• Изучить предметную область;
• Исследовать существующие алгоритмы;
• Разработать эффективный алгоритм вычисления значений функции, определяющей количество разбиений натурального числа, состоящего из различных нечётных частей, количество которых даёт тот же остаток при делении на 4, что и их сумма, а произведение является точным квадратом;
• Распараллелить созданный алгоритм;
• На основе данного алгоритма разработать программу для определения значений функции;
• Вычислить значения функции для достаточно малых аргументов;
• Проанализировать полученные результаты и понять характер функции.
Работа содержит введение, три главы, заключение и список использованных источников.
В первой части происходит обзор предметной области и разбираются теоретические основы для достижения поставленной цели, а именно разрабатывается эффективный последовательный алгоритм и с обоснованием правильности его работы.
Во второй части происходит распараллеливание данного алгоритма и описание программы, которая создаётся на его основе.
В третьей части производится тестирование полученной программы, фиксируются результаты её работы для некоторого множества входных данных и производится анализ полученных результатов с целью понять характер поведения функции.
В заключении подводятся итоги всей работы.
Объём работы составляет 50 страниц, объём использованной литературы - 10 источников. Работа содержит 7 таблиц, 23 рисунка, 4 формулы и 3 листинга.

Купить