67749

АРИФМЕТИКА МНОГОЧЛЕНОВ

Лабораторная работа

Математика и математический анализ

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

Русский

2014-09-14

461 KB

5 чел.

PAGE   \* MERGEFORMAT 5

Лабораторная работа № 4

Тема: АРИФМЕТИКА МНОГОЧЛЕНОВ

Цель работы – изучить основные понятия, необходимые для обоснования модульной арифметики и операций в расширениях конечных полей.

Краткие теоретические сведения.

1. Многочлены над полем.

Многочлен над полем  – это функция вида , где , . Целое число  называется степенью многочлена и обозначается . Числа  называются коэффициентами,  – свободным членом. Областью изменения аргумента  является поле . Умножение и сложение являются операциями в поле. Константы (элементы поля ) рассматриваются как многочлены нулевой степени.

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

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

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

Определение. Если для многочленов  и  в кольце  существуют такие многочлены  и , что многочлен  можно представить в виде

где степень многочлена  не больше степени многочлена  (), то говорят, что многочлен  делится на многочлен  с остатком.

2. Делимость многочленов

При делении многочленов с остатком применяют ту же терминологию, что и для целых чисел: многочлен  называется делимым, многочлен  – делителем, многочлен  – неполным частным, а многочлен  – остатком.

На практике деление с остатком для двух заданных многочленов выполняется аналогично делению многозначных чисел – "углом".

В частном случае, когда делитель  является приведённым линейным двучленом, т.е. , применяется схема Горнера.

Положим

.

Приравняв коэффициенты в обеих частях последнего равенства, получим:

Обычно процесс деления на линейный двучлен оформляют в виде таблицы:

3. Алгоритм Евклида для многочленов

Многочлен  называется общим делителем многочленов  и , если он является делителем каждого из них.

Общий делитель многочленов  и , который делится на любой общий делитель этих многочленов, называется наибольшим общим делителем (НОД) многочленов  и . Обозначается символом  или .

Обычно в качестве  выбирается нормированный многочлен.

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

Для определения НОД двух многочленов используется аналог классического алгоритма Евклида для чисел.

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

;

;

;

....................................................

;

.

Последний отличающийся от нуля остаток и будет наибольшим общим делителем многочленов  и .

Теорема (о линейном представлении НОД двух многочленов). Для любых двух многочленов и  из  существует наибольший общий делитель , который можно представить в виде:

,

где .

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

.

Для определения линейного представления НОД двух многочленов используется аналог расширенного алгоритма Евклида для чисел.

4. Многочлены над полем .

Сложение и умножение в поле  определяется следующими таблицами

+

0

1

х

0

1

0

0

1

0

0

0

1

1

0

1

0

1

Если многочлен  неприводим, то остатки от деления всех многочленов из  на  образуют поле  относительно операций умножения и сложения многочленов с коэффициентами из . Поле  является расширением . Количество его элементов равно . Равенство в поле  является сравнением вида . Элемент, обратный  вычисляется как многочлен  из уравнения , поскольку все многочлены степени меньшей  взаимно просты с .

Если многочлену , , поставить в соответствие вектор , то операции в поле  можно интерпретировать как операции над векторами – расширенными числами, правые крайние координаты которых принадлежат .

5. Неприводимость многочленов

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

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

Как простых чисел в , так и неприводимых многочленов над произвольным полем  существует бесконечное множество.

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

Порядок выполнения работы.

1. Изучить краткие теоретические сведения о свойствах многочленов.

2. Пользуясь схемой Горнера, вычислить :

  1.  ,   ;
    1.  ,   ;
    2.  ,   ;
    3.  ,  ;
    4.  ,   ;
    5.  ,  ;
    6.  , ;
    7.  , ;
    8.  ,   ;
    9.  ,  ;
  2.  ,  ;
  3.  ,  ;
  4.  ,  ;
  5.  ,  ;
  6.  ,  ;
  7.  ,  ;
  8.  ,  ;
  9.  ,   ;
  10.  ,  ;
  11.  ,  ;
  12.  ,  ;
  13.  ,   ;
  14.  ,  ;
  15.  ,  ;
  16.  , .

3. С помощью расширенного алгоритма Евклида найти линейное представление наибольшего общего делителя многочленов  и :

  1.  ,
  2.  ,
  3.  ,
  4.  ;
  5.  ,
  6.  ,
  7.  ,
  8.  ,
  9.  ,
  10.  ,
  11.  
  12.  
  13.  
  14.  
  15.  
  16.  
  17.  
  18.  
  19.  
  20.  
  21.  
  22.  ;
  23.  ;
  24.  ;
  25.  .

4. С помощью расширенного алгоритма Евклида найти линейное представление наибольшего общего делителя многочленов  и  над полем .

1

2

3

4

5

6

7

8

9

10

11

12

13

4

5

8

6

5

6

5

7

4

6

6

7

7

3

4

4

1

3

5

1

3

2

3

4

2

4

14

15

16

17

18

19

20

21

22

23

24

25

6

8

6

7

8

9

8

7

9

8

5

8

2

5

5

6

3

5

2

5

4

1

2

5

4. Составить отчет, приобщив туда полученные результаты.

Требования к отчету.

В отчете должны быть приведены:

1. Краткие сведения об изученных свойствах многочленов.

2. Решения своего варианта с необходимыми пояснениями.

3. Ответы на контрольные вопросы.

Контрольные вопросы.

  1.  Что такое многочлен?
    1.  Что такое многочлен над полем?
      1.  Как найти НОД двух многочленов?
      2.  Как найти линейное представление НОД двух многочленов?
      3.  Почему вычеты по модулю приводимого над  многочлена не образуют поле?
      4.  Почему операции сложения и вычитания в расширении поля  совпадают?


 

А также другие работы, которые могут Вас заинтересовать

34392. Квотирование, лицензирование, валютное регулирование экспорта и импорта 25 KB
  Квотирование К – установление количественных ограничений квот на ввоз и вывоз товаров. Лицензирование Л: для ввоза вывоза определенных товаров требуется получить установленный документ лицензию. Число квотированных товаров по мере приближения цен к мировым снижается. Кроме того лицензированию подлежат экспорт и импорт специфических товаров: товаров и технологий военного и двойного назначения ядерных материалов драгоценных металлов и камней наркотических и психотронных средств ядов.
34393. Определение эффективности ВЭС 29 KB
  Эффективность экспорта продукции Ээ определяется соотношением валютной выручки Вэ к затратам на экспорт Зэ. Если Ээ 1 то экспорт продукции экономически выгоден Ээ = Вэ Зэ. Эффективность импорта продукции Эи определяется соотношением затрат на производство импортозамещающих товаров Зи к валютным расходам на приобретение импортных товаров Ви Эи = Зи Ви. На основе расчетов эффективности экспорта и импорта делается вывод о целесообразности поставок продукции в ту или иную страну и импорта товаров.
34394. Промышленные комплексы. Проблемы их функционирования в современных условиях. Реструктуризация промышленности 34 KB
  Строительство основа строительного комплекса особенностями которого являются длительный период производства продукции и большие затраты трудовых материальных и финансовых ресурсов. Особое внимание при этом предусматривается уделять модернизации наукоемкого сектора промти экспортно ориентированным отраслям и импортозамещающим производствам созданию и развитию производств основанных на прогрессивных технологиях. Предусматриваются следующие важнейшие меропр: реформирование системы гос п п завершение приватизации малых п п и...
34395. Прогнозирование и планирование объема и структуры промышленного производства 33 KB
  На заключительном этапе формируются плановый объем и структура выпуска промышленной продукции с учетом спроса возможностей производства и обеспечения производственными ресурсами. Обосновывается и устанавливается заказ на поставку важнейших видов продукции для государственных нужд. Для прогнозирования спроса и объема производства конкретных видов продукции хорошие результаты дает метод Дельфи . Путем анкетного опроса группы ученых и специалистов по данной проблеме формируется информация по выпуску каждого вида продукции по годам которая...
34396. Сущность и содержание прогнозирования. Роль и характер прогнозов 44.5 KB
  Прогнозирование это процесс разработки прогноза построенный на вероятностном научно обоснованном суждении о перспективах развития объекта в будущем его возможном состоянии и альтернативных путях его достижения. Социальноэкономическое прогнозирование является способом предвидения представления о будущем обусловленном закономерностями общественного развития и действием разнообразных и разнонаправленных факторов в прогнозируемом периоде. В соответствии с Законом О государственном прогнозировании и программах социальноэкономического...
34397. Сущность планирования. Директивное, индикативное, стратегическое планирование, их характеристика 47 KB
  При формировании рыночных отношений в Республике Беларусь необходимо видение перспектив ее экономического и социального развития. Планирование это процесс принятия управленческого решения основанный на обработке исходной информации и включающий в себя определение и научную постановку целей средств и путей их достижения посредством сравнительной оценки альтернативных вариантов и выбора наиболее приемлемого из них в ожидаемых условиях развития. Суть планирования состоит не в разработке и доведении многочисленных показателей до...
34398. Предмет курса, его место в системе экономических наук 27 KB
  Пип – наука изучающая экие теории и законы применительно к конкретным условиям производства их специфические проявления в важнейших процессах прва закономерностях темпов и пропорциях с тем чтобы в результате этого изучения с учетом достижений НТП передового опыта обосновать объемы темпы и пропорции общественного производства в целях наиболее эффективного развития экономики. Задача курса состоит в рассмотрении комплекса теоретических методологических организационных вопросов пип экономики на современном этапе. Теория пип является...
34399. Исторический аспект развития прогнозирования и планирования 26 KB
  Экономическая мысль совершая поиск путей становления системы планирования испытывала колебания вступала в противоборство допуская ошибки и избавляясь от них под влиянием реальных явлений хозяйственной жизни. Рассмотрим становление и совершенствование прогнозирования и планирования в бывшем СССР и развитых зарубежных странах. Первый долгосрочный план который представляет интерес с точки зрения общей методологии планирования это план ГОЭЛРО государственный план электрификации России разработанный в 1920 г.
34400. Развитие и особенности ПИП в зарубежных странах (США, Япония, Франция и др.) 45.5 KB
  Для США характерно стратегическое планирование суть которого состоит в выборе главных приоритетов развития национальной экономики ведущую роль в реализации которых играет государство. Основным источником займов на цели разработки и освоения новой технологии является Японский банк развития. Направления стратегического развития разрабатываются в виде целевых государственных программ и сопровождаются комплексом различных финансовых льгот и преференций стимулирующих их реализацию. Она представляет собой модель будущего развития экономики...