Заказать работу


Тип работы:
Предмет:
Язык работы:


ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ РАСПРЕДЕЛЕНИЯ КВАДРАТОВ В ПРОИЗВЕДЕНИЯХ РАЗБИЕНИЙ НАТУРАЛЬНЫХ ЧИСЕЛ

Работа №71044
Тип работыДипломные работы, ВКР
Предметматематика
Объем работы54
Год сдачи2017
Стоимость4325 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено 8
Не подходит работа?

Узнай цену на написание

ВВЕДЕНИЕ 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 листинга.


Возникли сложности?

Нужна помощь преподавателя?

Помощь в написании студенческих
и аспирантских работ!


В данной работе была затронута тема разбиения натуральных чисел на различные нечётные слагаемые. Особое внимание уделялось разбиениям, количество частей которых даёт тот же остаток от деления на 4, что и их сумма, а произведение частей является квадратом натурального числа. Были определены функции для количества разбиений, удовлетворяющих всем или некоторым из данных свойств.
В первой части данной работы была рассмотрена предметная область, в том числе - алгоритм Липского для порождения всех возможных разбиений натурального числа. Ввиду его непригодности для достижения цели работы возникла необходимость в разработке собственного алгоритма. Этапы разработки с необходимыми доказательствами также содержатся в теоретической части.
Во второй части был разобран один из возможных способов распараллеливания данного алгоритма, а также разработана и описана программа по данному алгоритму.
В третьей части было произведено тестирование программы и сделан окончательный вывод о правильности её работы, после чего были найдены ускорение и эффективность, в зависимости от количества процессов и аргументов функции.
Результатом работы являются разработанный параллельный алгоритм для расчёта количества квадратов в произведениях разбиений натуральных чисел, а также эффективная программа, созданная по этому алгоритму. Таким образом, основная цель работы достигнута. Также выполнены и другие задачи работы:
• Изучена предметная область;
• Исследованы существующие алгоритмы;
• Вычислены значения функции для достаточно малых аргументов;
• Проанализированные полученные результаты с целью понять характер функции.
Несмотря на полное решение всех задач работы, данные о характере поведения функции остаются гипотезами, нуждающимися в строгих математических доказательствах. Также сохраняется возможность найти более быстрый алгоритм вычисления значений функции sqrs (n), путём, например, перебора только тех разбиений, которые удовлетворяют условиям 1-3 и не удовлетворяют условию 4. Таким образом, по итогам данной работы остаются открытые вопросы, которые требуют дальнейшего изучения.



1. Эндрюс, Г. Теория разбиений. / Эндрюс Г. - М.: Наука, 1982 - 256 с.
2. Липский, В. Комбинаторика для программистов. / Липский, В. - М.: Мир, 1988 - 200 с.
3. Фултон, У. Таблицы Юнга и их приложения к теории представлений и геометрии. / Фултон, У. - МЦНМО, 2006 - 328 с.
4. Джеймс, Г. Теория представлений симметрических групп. / Джеймс, Г. - М.: Мир, 1982 - 214 с.
5. Вайнштейн, Ф. В. Разбиение чисел. / Вайнштейн, Ф. В. // Квант - М.: Наука, 1988 - №11, с. 19-25.
6. Ferraz, R. A. Simple components and central units in group rings. / Ferraz, R. A. // Journal of Algebra, 2004. - No 1, p. 191-203.
7. Макдональд, И. Симметрические функции и многочлены Холла. / Макдональд, И. — М.: Мир, 1985. — 224 с.
8. Корнеев В. Д. Параллельное программирование в MPI. / Корнеев В. Д. - Новосибирск, 2002 - 220 с.
9. Алгоритмы: построение и анализ. / Т. Кормен, Ч. Лейзерсон, Р. Ривест. - М.: Вильямс, 2005 - 1296 с.
10. Hardy G. H. An Introduction to the Theory of Numbers, 6thedition. / G. H. Hardy, E. M. Wright. - UK: Oxford University Press, 2008. - 656 p.


Работу высылаем на протяжении 30 минут после оплаты.

Пожалуйста, укажите откуда вы узнали о сайте!



© 2008-2021 Cервис помощи студентам в выполнении работ
.