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

ВВЕДЕНИЕ 4
1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ 7
1.1. Описание исследований разбиений и проверяемых гипотез 7
1.1.1. Закономерности расположения квадратов в разбиении 7
1.1.2. Связь разбиений с целочисленными точками на эллипсе 7
1.1.3. Другие исследования 8
1.2. Разработка алгоритма 8
1.2.1. Рекуррентные формулы вычисления r1(n), r2(n) и r3(n) 8
1.2.2. Алгоритм вычисления squares(n) 9
2. РЕАЛИЗАЦИОННАЯ ЧАСТЬ 13
2.1. Реализация алгоритмов 13
2.2. Распараллеливание программы 16
2.3. Модули программы 16
2.4. Интерфейс 17
2.5. Тестирование 18
3. ЭКСПЕРИМЕНТАЛЬНАЯ ЧАСТЬ 23
3.1. Ранги 23
3.2. Закономерности расположения квадратов в разбиении 23
3.3. Распределение произведений элементов разбиений 26
3.4. Дополнение разбиений rank до squares 29
3.5. Распределение квадратов среди целых точек эллипса 31
3.6. Анализ результатов 38
ЗАКЛЮЧЕНИЕ 40
СПИСОК ЛИТЕРАТУРЫ 41
ПРИЛОЖЕНИЯ 43
Купить

Разбиением натурального числа п называется любая конечная невозрастающая последовательность натуральных чисел a1,a2, ...,ak, для которой
к
£«, = п, (1)
i=1
т.е. всякое представление числа суммой натуральных чисел [14, 22]. Разбиения, отличающиеся только порядком слагаемых, считаются эквивалентными.
Приложения теории разбиений можно найти в областях, связанных с подсчетом или классификацией дискретных объектов, таких как молекулярное или атомное строение вещества, теория чисел, комбинаторика и различных разделах алгебры, например теории представлений симметрической группы [15, 22].
Актуальность
Связь разбиений с одной из задач алгебры была опубликована Фер- разом [4] и в работах [1, 11, 12], показавших, что ранг группы центральных единиц целочисленного группового кольца знакопеременной группы степени п равен количеству разбиений, удовлетворяющих следующим условиям.
1. Все элементы разбиения различны.
2. Все элементы разбиения нечетны.
3. п = k (mod 4), где к - длина разбиения.
4. Произведение элементов разбиения не является квадратом натурального числа.
Введем следующие обозначения:
• ri(n) - число разбиений п, удовлетворяющих условию 1;
• r2(n) - число разбиений п, удовлетворяющих условиям 1-2;
• Гз(п) - число разбиений п, удовлетворяющих условиям 1-3;
• rank(n) - число разбиений п, удовлетворяющих условиям 1-4;
• squares(n) - число разбиений п, удовлетворяющих условиям 1-3 и не удовлетворяющих условию 4;
• r1mod8(n) - число разбиений п, удовлетворяющих условиям 1-3, причем P = 1 (mod 8), где P = Пк=1 ai.
Под разбиениями f (n), где f (n) - одна из выше перечисленных функций, будем понимать разбиения, удовлетворяющие условиям разбиений, чье количество равно значению f (n).
Как известно из асимптотического выражения Харди—Рамануджана [2, 5, 6] (2), число разбиений p(n) растет экспоненциально:
p(n)
Тем не менее, вычисление только значения p(n) представляет собой гораздо более легкую задачу, т.к. существует рекуррентная формула, выведенная Эйлером [22]. Так в 2014 году было вычислено значение p(1020) имеющее около 11 миллиардов цифр [7]. Главной сложностью задачи является необходимость генерации разбиений числа n для проверки необходимых условий. Значения r1(n), r2(n) и r3(n) также можно найти достаточно быстро, используя рекуррентные формулы [16, 21], по сравнению с затратами на вычисление squares(n) и rank(n). В случае с squares(n) и rank(n) условием, требующим генерации разбиений, является проверка произведения элементов на наличие квадратного корня.
В работе [16] были вычислены значения squares(n) и rank(n) до n = 1000. Дальнейшие вычисления требуют все больших ресурсов: оперативной памяти или узлов кластера для распараллеливания в зависимости от выбранного алгоритма.
Цель и задачи исследования
Основной целью работы является создание программы, вычисляющей значения r3(n), squares(n), r1mod8(n) и генерирующей разбиения этих функций для их последующего анализа. Экспоненциальный рост числа разбиений делает необходимым изучение разбиений по некоторым выделенным для них характеристикам, ввиду сложности восприятия выборки из большого числа разбиений и работы с ней. Главная задача анализа разбиений заключается в поиске закономерностей, преобладающих характеристик в их строении и связи разбиений с целочисленными точками на эллипсах. Анализ особенностей разбиений данных типов имеет ценность для разработки более эффективных алгоритмов расчета rank(n).
Задачи исследования:
• разработать и реализовать алгоритмы вычисления r1(n), r2(n), r3(n) и генерации соответствующих разбиений на основе рекуррентных формул;
• разработать и реализовать алгоритм вычисления r1modg(n) и генерации соответствующих разбиений;
• разработать и реализовать алгоритм вычисления squares(n) и генерации соответствующих разбиений;
• реализовать вычисление rank(n) на основе предыдущих алгоритмов;
• проанализировать сгенерированные разбиения и проверить гипотезы о преобладающих характеристиках в их строении;
• скомпоновать полученные результаты.
Структура и объем
Выпускная квалификационная работа состоит из введения, трех основных разделов, заключения, библиографии и 5 приложений. Объем работы составляет 42 страницы, объем библиографии - 22 наименования, объем приложений - 8 страниц.
Содержание работы
В первом разделе «Теоретическая часть» представлены описания характеристик разбиений, гипотезы об их строении, которые исследуются в третьем разделе, и разработка алгоритма для генерации требуемых разбиений на основе существующих аналогов.
Во втором разделе «Реализационная часть» описывается программная реализация алгоритмов подсчета количества и генерации разбиений, удовлетворяющих заданным условиям.
В третьем разделе «Экспериментальная часть» представлены результаты вычислительных экспериментов, проведен их анализ, проверены гипотезы, выдвинутые в первом разделе, и сделаны выводы о строении рассматриваемых разбиений и их распределении относительно разбиений с меньшим количеством условий.
В заключении приводятся основные результаты работы и подводятся итоги анализов проведенных исследований.
Купить