📄Работа №80018
Тема: РАСПРЕДЕЛЕНИЕ КВАДРАТОВ В ПРОИЗВЕДЕНИЯХ РАЗБИЕНИЙ НАТУРАЛЬНЫХ ЧИСЕЛ
Тип работы
Магистерская диссертация
Предмет
информатика
Объем:
41 листов
Год:
2016
Просмотров:
140
4855
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
ВВЕДЕНИЕ 5
1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ 9
1.1. Анализ предметной области и обзор существующих алгоритмов 9
1.2. Разработка базового алгоритма 11
1.3. Разработка параллельного алгоритма 15
2. РЕАЛИЗАЦИОННАЯ ЧАСТЬ 17
3. ЭКСПЕРИМЕНТАЛЬНАЯ ЧАСТЬ 22
3.1. Исследование ускорения алгоритма 22
3.2. Анализ полученных результатов 25
ЗАКЛЮЧЕНИЕ 38
ЛИТЕРАТУРА 39
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 и приведены различные графики ускорения алгоритма.
В заключении приводятся основные результаты работы.
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.
Были решены следующие задачи:
- проанализирована предметная область и аналогичные алгоритмы для разбиения целых чисел;
- разработан последовательный алгоритм поиска числа искомых разбиений;
- разработана параллельная версия разработанного алгоритма;
- реализована программа для подсчета требуемых квадратов в разбиениях;
- проанализированы полученные результаты, время выполнения алгоритмов и ускорение.
Публикации по теме работы
Алеев Р.Ж., Семенихина П.Н. Использование суперкомпьютера «Торнадо- ЮУрГУ» для задач, связанных с разбиениями натуральных чисел // Параллельные вычислительные технологии (ПаВТ’2016): труды международной научной конференции (28 марта - 1 апреля 2016 г., г. Архангельск). - Челябинск: Издательский центр ЮУрГУ, 2016. - С. 752.
ИЛИ
Поиск аналога
📕 Список литературы
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.