Курсовая работа

ГЕНЕРАЦИЯ ПОЛИНОМОВ

Оглавление

Введение

Глава 1. Теоретическая часть по генерации полиномов

1.1 Теория полиномов

1.1.1 Основные определения, используемые в теории полиномов

1.1.2 Определение полинома

1.1.3 Основные свойства полиномов

1.1.4 Используемые в исследовании теоремы и их доказательства

1.2 Генерация полиномов

Глава 2. Практическая часть по генерации полиномов

2.1 Алгоритм генерации полиномов.

2.2 Написание программы, реализующей алгоритм генерации полиномов

2.2.1 Преодоление проблем, возникших при написании программы

2.2.2 Описание и пояснение некоторых частей программы

2.3 Листинг программы, реализующей алгоритм генерации полиномов

Заключение

Список использованных источников и литературы

Приложение

Введение

В данной курсовой работе рассмотрена проблема генерации полиномов (многочленов) по их введенным корням. Целью курсовой работы явилась разработка действенного алгоритма и написание на его основе программы, которая генерирует полином по его введенным корням. Проблема разработки алгоритма для генерации полиномов и написание на его основе программы является практически актуальной, так как ни для кого не секрет, что в последнее время на рынке литературы широко распространены так называемые «решебники». В них можно найти не только решения к заданиям из учебников, но и к заданиям из методической литературы, из которой учителя составляют контрольные и прочие работы для проверки знаний учащихся. В связи с этим, знания учащихся снижаются, а «успеваемость», которая перестала быть истинным критерием знаний учащегося, растет. Поэтому у учителей остается один выход – самим составлять проверочные работы. Однако временные возможности учителя ограничены, и он просто не в состоянии составить оригинальные задания на целый класс. Составленный алгоритм и программа, реализующая его, способны облегчить труд учителя в свете этой проблемы, так как за очень короткое время программный продукт способен сгенерировать полином по его введенной степени и корням. Соответственно, не прикладывая ни каких больших умственных усилий, а значит и больших временных ресурсов, учитель сможет составить множество оригинальных заданий, при этом у него останется время для других не менее важных дел.

Данная курсовая работа состоит двух глав, включающих в себя каждый несколько параграфов и подпунктов.

В первой главе приведена теоретическая часть по генерации полиномов, включающая основные понятия и определения теории полиномов, основные теоремы алгебры и теории полиномов, дающие научную основу для разработки алгоритма генерации полиномов и написании на его основе программы.

Во второй главе рассказывается об основных проблемах, с которыми я столкнулся при составлении алгоритма и написании программы, приводится алгоритм генерации полиномов, описываются некоторые важные части программы, основывающейся на алгоритме, и приводится листинг программного продукта.

В заключении говорится о проблемах, с которыми столкнулся при составлении алгоритма и написании на его основе программы и о путях усовершенствования предложенного алгоритма и программы.

Глава 1. Теоретическая часть по генерации полиномов

1.1 Теория полиномов

1.1.1 Основные определения, используемые в теории полиномов

В первой главе этот пункт можно назвать одним из важнейших, так как в его содержании будут приведены определения основных понятий алгебры и теории полиномов, без которых не представлялось бы возможным понимание всего того, о чем будет говориться в остальных параграфах и главах.

Определение 1. Множество – набор, совокупность, собрание каких-либо объектов, называемых его элементами, обладающими общим для всех них характеристическим свойством. [4, С. 382]

Определение 2. Бинарная операция – правило, по которому каждой паре (a, b) элементов множества G однозначно ставится в соответствие некоторый элемент с того же множества G. [7, С. 11]

Определение 3. Множество R, в котором заданы две бинарные операции + (сложение) и (умножение), называется полем, если выполняются следующие условия (аксиомы поля):

Сложение:

1. Коммутативность: a + b = b + a.

2. Ассоциативность: a + (b + c) = (a + b) + c.

3. Существование нуля: существует такой элемент 0,

что а + 0 = а для любого элемента а.

1. Существование противоположного: для любого элемента, а существует такой элемент (-а), что а + (-а) = 0.

Умножение:

1. Коммутативность: a ∙ b = b ∙ a.

2. Ассоциативность: a ∙ (b ∙ c) = (a ∙ b) ∙ c.

3. Существование единицы: существует такой элемент 1, что а∙1 = а для всякого элемента а.

4. Существование обратного: для любого элемента а ≠ 0 существует такой элемент а^-1, такой что а ∙ а^-1 = 1.

Сложение и умножение:

Дистрибутивность: a ∙ (b + c) = a ∙ b + а ∙ c. [2, С. 16]

Определение 4. Коммутативным кольцом называется множество, в котором выполняются аксиомы поля, кроме, может быть, требования существования обратного элемента а^-1 для любого а ≠ 0. [2, С. 23]

Определение 5. Пусть S – множество. Отображение S * S → S – закон композиции – общее название для операции, производящей из двух элементов a, b S третий элемент c S. [4, С. 279]

Определение 6. Моноид – множество G с ассоциативным законом композиции. [4, С. 386]

Определение 7. Если f(c) = 0, т.е. многочлен f(x) обращается в нуль при подстановке в него числа с вместо неизвестного, то с называется корнем многочлена f(x). [1, С. 144]

Определение 8. Ненулевой элемент кольца, произведение которого на некоторый ненулевой элемент равно нулю, называется делителем нуля. [4, С. 176]

Определение 9. Кольцо называется целостным (или областью целостности), если оно коммутативно и не содержит делителей нуля. [2, С. 26]

Определение 10. Многочлен называется приводимым в кольце многочленов, если у него существуют делители со степенью больше нуля, но меньше степени полинома, иначе неприводимым. [6, С. 54]

1.1.2 Определение полинома

В математике и ее разделах существует несколько определений такого понятия как полином. Здесь и далее будем называть полином также степенным многочленом или просто многочленом. Приведем некоторые из них.

Первое определение взято из [3, С. 60]

Пусть R – некоторое кольцо. Построим с помощью нового, не принадлежащего кольцу R, символа х выражение вида f(х) = ∑а_v x^v, в которых суммирование ведется по какому-то конечному множеству целочисленных значений индекса v≥0 и «коэффициенты» а_v принадлежат кольцу R. Такие выражения называются многочленами; символ х называется переменной, v – степенью полинома.

Второе определение взято из [7, С. 131-133]

Пусть S – некоторое множество и N – моноид натуральных чисел. Обозначим через N(S) множество функций S → N, которые равны 0 для почти всех элементов из S. Пусть х S и t N. Всякий элемент р N(S) имеет единственное представление в виде произведения

, где v: S→N – отображение, для которого v(x) = 0 при почти всех х. Такое произведение назовем примитивным многочленом и будем обозначать или просто .

Пусть А - коммутативное кольцо. Тогда можно образовать множество моноидов A[N(S)] над А, которую будем называть кольцом многочленов от S над A. По определению всякий элемент из A[N(S)] имеет единственное представление в виде линейной комбинации , где (v) пробегает все отображения множества S в N, обращающиеся в ноль для почти всех (v). Элементы из А[N(S)] называются многочленами от S над А. Элементы называются коэффициентами многочлена. Если S состоит из одного символа Х, то всякий многочлен может быть записан в виде

,

где и n – некоторое целое число ≥ 0, называющееся степенью полинома.

Ниже приведенное определение взято из [1, С. 130]

Многочленом (или полиномом) n-й степени от неизвестного х называется сумма выражений с целыми степенями:

.

Коэффициенты будем считать произвольными числами, причем старший коэффициент должен быть отличен от нуля. Для сокращенной записи многочленов употребляются символы f(x), g(x) и т.д.

В данной курсовой работе можно использовать любое из приведенных определений полинома, но в общем последнее определение полинома проще для понимания, но имеет не мене глубокий смысл, чем остальные, так как позволяет взглянуть на полином как на некоторое формальное выражение вполне определенное набором своих коэффициентов (что гораздо упрощает работу с полиномами при их генерации) с одной стороны и как на функцию от переменного Х (с точки зрения математического анализа) с другой стороны.

1.1.3 Основные свойства полиномов

1. Равенство одного полинома другому.

Два многочлена f(x) и g(x) будут считаться равными (или тождественно равными), f(x) = g(x), в том случае, если равны их коэффициенты при одинаковых степенях неизвестного. [1, С. 131]

1. Сложение и умножение полиномов.

Пусть и , где , , n, s – степени многочленов f(x) и g(x). Если n ≥ s (иначе переобозначим степени полиномов), то их суммой называется многочлен , коэффициенты которого получаются сложением коэффициентов f(x) и g(x), стоящих при одинаковых степенях переменного, т.е. , i = 0, 1, …, n. Степень суммы равна n, если n ≥ s, но при n = s она может оказаться меньше n, а именно в том случае если . [1, С. 132]

Произведением многочленов f(x) и g(x) называется многочлен , коэффициенты которого определяются следующим образом , так как , , то , поэтому степень произведения многочленов равна n + s. [1, С. 132]

1. Замкнутость относительно сложения и умножения. Исходя из первых двух свойств многочлена, очевидно, что складывая или перемножая два каких-либо многочлена от одного и того же переменного с коэффициентами из К, мы получим однозначно многочлен с коэффициентами из того же кольца К.

1.1.4 Используемые в исследовании теоремы и их доказательства

Т1. [1, С. 134]

Для любых двух многочленов f(x) и g(x) можно на найти такие многочлены q(x) и r(x), что

f(x) = g(x) ∙ q(x) + r(x), (1.1)

причем степень r(x) меньше степени g(x) или же r(x) = 0. Многочлены q(x) и r(x), удовлетворяющие этому условию определяются однозначно.

Доказательство. [1, С. 134-135]

Докажем сперва вторую половину теоремы. Пусть существуют еще многочлены q1(x) и r1(x), также удовлетворяющие равенству

f(x) = g(x) ∙ q1(x) + r1(x), (1.2)

причем степень r1(x) меньше степени g(x) или равна нулю. Приравнивая друг другу правые части равенств (1.1) и (1.2), получим:

g(x) ∙ [q(x) – q1(x)] = r1(x) – r(x).

Степень правой части этого равенства меньше степени g(x), степень же левой части была бы при больше или равна степени g(x). Поэтому должно быть q(x) – q1(x) = 0, т.е. q(x) = q1(x), а тогда и r(x) = r1(x), что и требовалось доказать.

Переходим к доказательству первой половины теоремы. Пусть многочлены f(x) и g(x) имеют соответственно степени n и s. Если n < s, то можно положить q(x) = 0, r(x) = f(x). Если же n ≥ s, то воспользуемся методом деления многочленов с действительными коэффициентами, расположенных по убывающим степеням неизвестного. Пусть

Полагая

(1.3)

мы получаем многочлен, степень которого меньше n. Обозначим эту степень через n1, а старший коэффициент многочлена f₁(x) – через а_n1. Положим, далее, если все еще n1 ≥ s,