Разбор контрольной работы (1127255)
Текст из файла
Разбор контрольной работыОбщие комментарии по результатам проверки контрольной:1. В вычислениях присутствует большое количество арифметических ошибок. Само по себе возникновение арифметических ошибок неизбежно. Поэтому для получения правильного ответанеобходимо конечный результат, а также по возможности промежуточные результаты проверять на корректность.
В простейшем виде такая проверка на корректность есть простоеподставление ответа в условие задачи. Далее в рамках разбора решений задач указываетсяряд тестов, которыми можно пользоваться для проверок.2. В вычислениях многие не пользуются представлением элементов поля как степеней примитивного элемента. Из-за этого ряд выкладок значительно усложняется. Степенная запись позволяет легко вычислять произведение и частное элементов поля, в частности, поиск обратныхэлементов.3. В решениях мало используется расширенный алгоритм Евклида. На практике зачастую онприводит к ответу гораздо быстрее, чем альтернативные методы.
Здесь стоит упомянуть, впервую очередь, задачу поиска обратного элемента в поле и задачу поиска полинома локаторовошибок для декодирования БЧХ кода.4. Пусть w(x) – некоторый многочлен над полем. В большом числе случаев его возведение встепень wk (x) удобнее вычислять как wi (x)wj (x), где i + j = k, а не как w(x)wk−1 (x).5. Следует иметь в виду, что если многочлен f (x) не имеет корней в поле, то это не значит, чтоон неприводим.Далее разбирается решение некоторых задач из контрольной работы. Решение других задачлибо присутствует в материалах по курсу, либо очевидно получается при умении решать задачи,разбираемые ниже.Для поля F23 = F3 [x]/(−2x2 +x+2) построить таблицу соответствий между полиномиальными степенным представлением для всех ненулевых элементов поля.
С помощью данной таблицывычислить выражение1(2x)7 (2)−.2x + 1 (x)9 (x + 2)Заданное поле имеет характеристику 3. Поэтому в вычислениях в данном поле все константыследует приводить по модулю 3. В частности, многочлен, используемый для построения поля, −2x2 +x + 2 = x2 + x + 2. В заданном поле все вычисления проводятся по модулю многочлена x2 + x + 2.Следовательно, в этом полеx2 + x + 2 = 0 ⇒ x2 = −x − 2 = 2x + 1.(1)Всего в поле F23 находится 32 − 1 = 8 ненулевых элементов. Известно, что все ненулевые элементыполя могут быть представлены как αi , i = 1, .
. . , 8, где α – некоторый примитивный элемент поля.1Возьмём в качестве α элемент x и вычислим все его степени с учётом (1):x2 = 2x + 1,x3 = x · x2 = x(2x + 1) = 2x2 + x = 2(2x + 1) + x = 2x + 2,x4 = x · x3 = x(2x + 2) = 2x2 + 2x = 2(2x + 1) + 2x = 2,x5 = x · x4 = 2x,x6 = x · x5 = 2x2 = 2(2x + 1) = x + 2,x7 = x · x6 = x(x + 2) = x2 + 2x = 2x + 1 + 2x = x + 1,x8 = x · x7 = x(x + 1) = x2 + x = 2x + 1 + x = 1.Последнее свойство x8 = 1 следует из общих свойств поля и является проверкой на корректностьпроведённых вычислений.Теперь вычислим значение выражения:(x5 )7 x4(2x)7 (2)x81−= x6 − x35+4−9−6 = x6 + 2x24 = x6 + 2 = x + 2 + 2 = x + 1.−=2x + 1 (x)9 (x + 2)x2x9 x6Заметим, что в общем случае элемент x не всегда является примитивным (эквивалентно, многочлен, используемый для построения поля, не является примитивным).
В этом случае для построениятаблицы соответствий между степенным и полиномиальным представлением необходимо сначаланайти примитивный элемент – некоторый элемент, имеющий порядок pn − 1. Рассмотрим решениеследующей задачи:Для поля F23 = F3 [x]/(x2 + 1) построить таблицу соответствий между полиномиальным истепенным представлением для всех ненулевых элементов поля.В данном поле x2 + 1 = 0, т.е.
x2 = 2. Найдём порядок элемента x. Для этого достаточнопроверить степени, являющиеся делителями 32 − 1 = 8, т.е. 2 и 4:x2 = 2,x4 = (x2 )2 = 1.Следовательно, элемент x имеет порядок 4 и не является примитивным элементом. Также не являются примитивными все степени элемента x, т.е. элементы:x2 = 2,x3 = 2x,x4 = 1.Возьмём элемент x + 1 и найдём его порядок:(x + 1)2 = x2 + 2x + 1 = 2x,(x + 1)4 = (2x)2 = 2.Значит, порядок x + 1 равен 8, т.е. он является примитивным элементом.
Теперь вычислим все егостепени:α = x + 1,α2 = 2x,α3 = 2x(x + 1) = 2x + 1,α4 = (α2 )2 = 2,α5 = 2(x + 1) = 2x + 2,α6 = α2 · α4 = x,α7 = x(x + 1) = x + 2,α8 = (α4 )2 = 1.Заметим, что вычисление очередной степени αi часто бывает удобным провести как αj · αk , гдеj + k = i, а не как α · αi−1 .В фактор-кольце F3 [x]/(x4 + 1) найти все элементы главного идеала (x2 + x + 2).Сначала проверим, является ли элемент x2 + x + 2 делителем x4 + 1:x4 + 1 = (x2 + x + 2)(x2 + 2x + 2).Так как элемент, порождающий идеал, является делителем многочлена, используемого при построении фактор-кольца, то(x2 + x + 2) = {(x2 + x + 2)(ax + b), a, b ∈ F3 }.Проведём умножение:(x2 + x + 2)(ax + b) = ax3 + (a + b)x2 + (2a + b)x + 2b.Теперь можно записать все элементы идеала, перебирая все возможные значения a, b ∈ F3 :a000111222b012012012элемент идеала0x2 + x + 22x2 + 2x + 1x3 + x2 + 2xx3 + 2x2 + 2x3 + x + 12x3 + 2x2 + x2x3 + 2x + 22x3 + x2 + 1Заметим, что в полном соответствии с теорией в данном случае ненулевой элемент идеала минимальной степени совпадает с порождающим многочленом x2 + x + 2.В поле F7 [x]/(x4 + x3 + x2 + 3) найти обратный элемент для x2 + x + 3.Проще всего обратный элемент можно найти путём решения уравнения(x4 + x3 + x2 + 3)a(x) + (x2 + x + 3)b(x) = 1(2)с помощью расширенного алгоритма Евклида.
Тогда b(x) будет искомым обратным элементом.Шаги алгоритма Евклида:Шаг 0. r−2 (x) = x4 + x3 + x2 + 3, // Инициализацияr−1 (x) = x2 + x + 3,y−2 (x) = 0,y−1 (x) = 1.Шаг 1. r−2 (x) = r−1 (x)q0 (x) + r0 (x), // Делим с остатком r−2 (x) на r−1 (x)q0 (x) = x2 + 5,r0 (x) = 2x + 2,y0 (x) = y−2 (x) − y−1 (x)q0 (x) = −q0 (x) = −x2 − 5.Шаг 2. r−1 (x) = r0 (x)q1 (x) + r1 (x), // Делим с остатком r−1 (x) на r0 (x)q1 (x) = 4x,r1 (x) = 3,y1 (x) = y−1 (x) − y0 (x)q1 (x) = 1 + 4x(x2 + 5) = 4x3 + 6x + 1.Заметим, что в итерациях алгоритма нет необходимости вычислять xi (x), т.е. коэффициент приx4 + x3 + x2 + 3, т.к. нас интересует только коэффициент при x2 + x + 3, т.е.
yi (x). Алгоритмзаканчивает свою работу на шаге 2, т.к. степень очередного остатка r1 равна степени многочленав правой части (2). Однако, сам остаток r1 отличается от требуемого на константный множитель.Действительно, после шага 2 мы имеем(x4 + x3 + x2 + 3)x1 (x) + (x2 + x + 3)y1 (x) = 3.Чтобы получить решение уравнения (2), достаточно домножить последний результат на 3−1 = 5:b(x) = 5y1 (x) = 5(4x3 + 6x + 1) = 6x3 + 2x + 5.Проверим, что найденный b(x) действительно является обратным к x2 + x + 3:b(x)(x2 + x + 3) = (6x3 + 2x + 5)(x2 + x + 3) = 6x5 + 6x4 + 6x3 + 4x + 1 == 6x(−x3 − x2 − 3) + 6x4 + 6x3 + 4x + 1 = 1.В поле F25 = F5 [x]/(x2 + 3x + 3) найти обратную для матрицы3x + 4 x + 2.x + 3 3x + 2Для матриц размера 2×2 обратная матрица может быть записана как−11a bd −b=.c dad − bc −c aСначала вычислим определитель заданной матрицы с учётом x2 = 2x + 2:(3x + 4)(3x + 2) − (x + 2)(x + 3) = 4x2 + 3x + 3 − x2 − 1 = 3x2 + 3x + 2 = 3(2x + 2) + 3x + 2 = 4x + 3.Далее найдём обратный элемент к 4x + 3 путём решения уравнения(x2 + 3x + 3)a(x) + (4x + 3)b(x) = 1с помощью расширенного алгоритма Евклида:Шаг 0.
r−2 (x) = x2 + 3x + 3, // Инициализацияr−1 (x) = 4x + 3,y−2 (x) = 0,y−1 (x) = 1.Шаг 1. r−2 (x) = r−1 (x)q0 (x) + r0 (x), // Делим с остатком r−2 (x) на r−1 (x)q0 (x) = 4x + 4,r0 (x) = 1,y0 (x) = y−2 (x) − y−1 (x)q0 (x) = −q0 (x) = −4x − 4 = x + 1.В результате (4x + 3)−1 = y0 (x) = x + 1. Наконец, вычислим обратную матрицу−1 3x + 4 x + 23x + 2 4x + 3x+3 1= (x + 1)=.x + 3 3x + 24x + 2 3x + 44x3xВ конце убедимся в правильности проведённых вычислений непосредственной проверкой 3x + 4 x + 2 x + 3 1(3x + 4)(x + 3) + 4x(x + 2) 3x + 4 + 3x(x + 2)==x + 3 3x + 24x3x(x + 3)2 + 4x(3x + 2)x + 3 + 3x(3x + 2) 2 2x + x + 2 3x2 + 4x + 42(2x + 2) + x + 2 3(2x + 2) + 4x + 41===3x2 + 4x + 4 4x2 + 2x + 33(2x + 2) + 4x + 4 4(2x + 2) + 2x + 300.1Разложить на неприводимые множители многочлен f (x) = x11 +x9 +x8 +x4 +x3 +x2 +1 ∈ F2 [x].Сначала пытаемся найти корни f (x) в F2 :f (0) = 1,f (1) = 1.Значит, f (x) не имеет корней в F2 , т.е.
не имеет линейных множителей в своём разложении над F2 .Далее пытаемся найти неприводимые многочлены степени 2, являющиеся делителями f (x). НадF2 существует только один неприводимый многочлен степени 2: x2 + x + 1. При делении f (x) наx2 + x + 1, получаемf (x) = (x2 + x + 1)(x9 + x8 + x7 + x6 + x4 + x3 + x2 + x + 1).Продолжая делить дальше на x2 + x + 1, получаемx9 + x8 + x7 + x6 + x4 + x3 + x2 + x + 1 = (x2 + x + 1)(x7 + x4 + x3 + x2 + x + 1) + x.Неприводимых многочленов степени 3 над F2 всего два: x3 + x + 1 и x3 + x2 + 1. Пробуем поделитьна x3 + x + 1:x9 + x8 + x7 + x6 + x4 + x3 + x2 + x + 1 = (x3 + x + 1)(x6 + x5 + x3 + x2 + 1).Производя деления далее на многочлены третьей степени, получаемx6 + x5 + x3 + x2 + 1 = (x3 + x + 1)(x3 + x2 + x + 1) + x2 ,x6 + x5 + x3 + x2 + 1 = (x3 + x2 + 1)x3 + x2 + 1.Так как многочлен 6-ой степени x6 + x5 + x3 + x2 + 1 не имеет делителей 3-ей и меньших степеней,то он является неприводимым (если бы он имел делитель, скажем, степени 4, то у него был бы иделитель степени 6-4=2).
В итоге f (x) раскладывается какf (x) = (x2 + x + 1)(x3 + x + 1)(x6 + x5 + x3 + x2 + 1).Найти минимальное поле характеристики 3, в котором многочлен f (x) = x3 + x + 2 ∈ F3 [x]раскладывается на линейные множители.Найдём разложение многочлена на неприводимые множители над F3 . Проверяем корни в F3 :f (0) = 2,f (1) = 1,f (2) = 0.Отсюда получаем, что x3 + x + 2 = (x + 1)(x2 + 2x + 2). Многочлен x2 + 2x + 2 не имеет корня x = 2.Следовательно, он является неприводимым.Известно, что любой неприводимый многочлен f (x) степени n над конечным полем F из q элементов раскладывается на линейные множители в расширении F , построенном как F [x]/(f (x)).
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
