67749

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

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

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

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

Русский

2014-09-14

461 KB

6 чел.

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.  Почему операции сложения и вычитания в расширении поля  совпадают?


 

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

76373. Международные валютно-финансовые и кредитные отношения 87 KB
  Цена единицы национальной валюты выраженная в единицах иностранной валюты называется валютный обменный курс exchnge rte. Валютный курс играет важную роль в развитии международной торговли и движении капитала. Таким образом с помощью валютных курсов производители и потребители приводят цены на товары в сопоставимый вид и формируют на этой основе международные потоки товаров. Фиксирование курса национальной денежной единицы по отношению к иностранным денежным единицам принято называть валютной котировкой currency quottion.
76374. Платежный баланс. Понятие и структура платежного баланса 75.5 KB
  В этом случае итальянская фирма осуществила продажу а Сбербанк покупку российских активов банковского депозита на сумму в 1000 долл и эта сделка будет отражена в российских счетах движения капитала. Такая операция создает две компенсирующие бухгалтерские записи в платежном балансе РФ: Кредит Дебет Покупка принтера текущий счет российский импорт 1000 долл Продажа банковского депозита осуществляемая Сбербанком счет движения капитала экспорт российских активов 1000 долл 2. Поэтому когда вы расплачиваетесь за свой обед за...
76375. Мировой рынок. Конъюнктура мирового рынка. Ценообразование в международной торговле 64.5 KB
  В зависимости от уровня конкретной цены на конкретный товар зависит решение тех или иных проблем возникающих у продавца: возмещение понесенных издержек производства и обращения товара доходность производства данного товара и его реализации появление новых стимулов для расширения внешнеэкономических связей или их свертывания. Цены в международной торговле как и внутри страны зависят от конкретной рыночной ситуации соотношения спроса и предложения но здесь оказывает влияние более широкий круг участников влияющих на конъюнктуру и...
76376. Мировое хозяйство и международные экономические отношения 50.5 KB
  Международные экономические отношения МЭО система хозяйственных связей между национальными экономиками отдельных стран соответствующими субъектами хозяйствования. МЭО особая сфера деятельности основанная на международном разделении труда. МЭО объективно вытекают из процесса разделения труда международной специализации производства и науки интенационализации хозяйственной жизни. Становление и развитие МЭО определяются усилением взаимосвязи и взаимозависимости экономик отдельных стран.
76377. Формирование мирового хозяйства и МРТ 78.5 KB
  Финикийские и греческие торговцы не только торговали по всему Средиземноморью собственными и приобретенными в других странах товарами но и оказывали услуги перевозя чужие грузы и иноземных пассажиров. Район Средиземноморья и Черного моря вместе с прилегающими странами Западной Азии стал тем регионом мира где еще в глубокой древности зародилось ядро МХ. Экономика различных стран становилась более открытой: в 1913 экспорт европейских стран составлял 14 их ВВП против 55 в 1830г. Тогда впервые возникла мировая система мирохозяйственных...
76378. Теория международной торговли с позиции предложения товаров и услуг 221.5 KB
  Теория международной торговли Тема 4. Теория международной торговли с позиции предложения товаров и услуг Торговля является традиционной и древнейшей формой МЭО. Меркантилизм Экономическая мысль на протяжении по крайней мере трех последних столетий пытается теоретически осмыслить проблемы международной торговли и ответить на следующие вопросы: Почему страны торгуют А точнее что определяет какие товары следует импортировать и какие экспортировать Как международная торговля влияет на производство и потребление в каждой стране Как...
76379. Взаимодействие спроса и предложения в международной торговле. Формирование мировой цены 80 KB
  Теория международной торговли в частности теория сравнительных преимуществ утверждает что в результате развития внешнеторговых отношений все участвующие в них страны получают выигрыш в виде прироста общего благосостояния. С другой стороны выигрыш от внешней торговли который получает страна в целом распределяется внутри страны между потребителями и производителями экспортерами и импортерами также не поровну. Выигрыш от внешней торговли Распределение выигрыша от международной торговли как внутри страны так и между странами в конечном...
76380. Международная торговля, распределение доходов и экономический рост 47 KB
  Увеличение производства в отраслях ориентированных на экспорт и сокращению производства в отраслях конкурирующих с импортом. Теория Хекшера-Олина дает возможность оценить последствия развития внешней торговли для владельцев различных факторов производства рабочих землевладельцев собственников капитала и др. поскольку изменения относительных цен на товары приводит к росту вознаграждения одних факторов производства за счет других. Изменение спроса на факторы производства и доходов в краткосрочном периоде Напомним что теория...
76381. Понятие и основные характеристики конституционного строя России 35.5 KB
  Конституционный строй в широком смысле совокупность экономических политических социальных правовых идеологических общественных отношений возникающих в связи с организацией высших органов власти государственного устройства взаимоотношениями человека и государства а также гражданского общества и государства. Элементы конституционного строя РФ: 1 республиканская форма правления; 2 суверенитет РФ; 3 права и свободы личности; 4 источник власти многонациональный народ России; 5 верховенство Конституции РФ и федерального...