Дискретная математика. Часть II

Министерство образования и науки Российской Федерации
Уральский федеральный университет
имени первого Президента России Б. Н. Ельцина

Б. М. Веретенников, В. И. Белоусова, А. Б. Веретенников

ДИСКРЕТНАЯ 
МАТЕМАТИКА

Часть II

Учебное пособие

Рекомендовано методическим советом
Уральского федерального университета
для студентов вуза, обучающихся
по всем направлениям подготовки бакалавриата
и специалитета ИРИТ-РтФ

Екатеринбург
Издательство Уральского университета
2017

УДК 519(075.8)
ББК 22.176А73
          В31

Рецензенты:
кафедра прикладной математики ФГБОУ ВО «Уральский государственный экономический университет» (завкафедрой, канд. физ.мат. наук, доц. Ю. Б. Мельников);
канд. физ.-мат. наук, ст. науч. сотр. И. Н. Белоусов (Институт математики и механики УрО РАН)

Научный редактор — канд. физ.-мат. наук, доц. Н. В. Чуксина

 
Веретенников, Б. М.
В31    Дискретная математика : учебное пособие / Б. М. Веретенников, В. И. Белоусова, А. Б. Веретенников. — Екатеринбург : Изд-во 
Урал. ун-та, 2017. — Ч. II. — 84 с.

ISBN 978-5-7996-2165-0 (ч. II)
ISBN 978-5-7996-1195-8

Данное учебное пособие является продолжением учебного пособия 
«Дискретная математика», Ч. I (авторы: Б. М. Веретенников, В. И. Белоусова). Работа включает в себя следующие разделы дискретной математики: 
многочлены над конечными полями, коды, исправляющие ошибки и элементы теории графов. Предлагаются упражнения для самостоятельного решения. Пособие предназначено для студентов инженерных направлений 
и специальностей ИРИТ–РтФ УрФУ.
Библиогр.: 8 назв. Табл. 3. Рис. 12.

УДК 519(075.8)
ББК 22.176А73

ISBN 978-5-7996-2165-0 
© Уральский федеральный
ISBN 978-5-7996-1195-8 
     университет, 2017

Оглавление

Глава I  
Многочлены над конечными полями .......................................... 5
§ 1. Обзор общей теории многочленов ..................................... 5
§ 2. Теория сравнений для многочленов и примеры 
        построения полей небольшого составного порядка ......... 9
§ 3. Основные теоремы о многочленах над конечными 
        полями ...............................................................................12

Глава II  
Коды, исправляющие ошибки ...................................................22
§ 1. Линейные коды .................................................................22

1.2. Вычисление проверочной матрицы с помощью 
        систематической порождающей матрицы .................24
1.3. Дуальные коды ............................................................27
1.4. Примеры специальных кодов .....................................28
        Упражнения для самостоятельной подготовки .........29
§ 2. Линейные коды, исправляющие ошибки .........................30

2.1. Декодирование линейных кодов с помощью 
        смежных классов .........................................................31
2.2. Декодирование с помощью синдромов ......................34
2.3. Код Хэмминга и расширенный код Хэмминга ..........38
2.5. Циклические коды ......................................................43
2.6. Нахождение систематической порождающей 
        матрицы циклического кода.......................................48
2.7. Специальный вид проверочной матрицы 
        циклического кода ......................................................50
2.8. Коды, порожденные элементами из расширения 
        основного поля ...........................................................51
2.9. Коды БЧХ ....................................................................53
2.10. Примеры кодов БЧХ .................................................54
2.11. Декодирование кодов БЧХ........................................56

Оглавление

Глава III  
Элементы теории графов ...........................................................62
§ 1. Основные понятия теории графов ....................................62
        1.1. Матрицы графов .........................................................67
§ 2. Алгоритмы на графах.........................................................71

2.1. Поиск в глубину ..........................................................71
2.2. Поиск в ширину ..........................................................73
2.3. Минимальный остов графа .........................................74
2.4. Наибольшее паросочетание в двудольном графе ......79

Список литературы ..................................................................82

Глава I.  
Многочлены над конечными полями

§ 1. Обзор общей теории многочленов

Напомним, что многочленом степени n над полем F  называется выражение f x
( ) вида a x
a x
a
n
n
n
0
1
1
+
+
+

, где все aj лежат 

в F, причем a0
0
№ . В частности, многочлен степени 0 над F  — 
это элемент F, причем степень нулевого многочлена считается 
равной (
).
-Ґ  При этом a0 называется старшим коэффициентом, 
а a xn
0
 называется старшим членом f x
( ). Будем обозначать 

deg ( )
f x  как степень f x
( ).

Складываются и умножаются многочлены по обычным 
школьным правилам, из чего следует, что deg
( ) ( )
deg ( )
f x g x
f x
(
) =
+
 

g
( ) ( )
deg ( )
deg ( ).
f x g x
f x
g x
(
) =
+

Теорема 1. Множество всех многочленов над полем F  является ассоциативным коммутативным кольцом с единицей, причем это целостное кольцо главных идеалов.
Эта теорема была доказана в части I данного пособия. Напомним, что коммутативное кольцо R называется целостным, 
если из того, что a b
R
, О  и ab = 0 всегда следует, что a или b равны нулю. Заметим, что в данном пособии понятие идеала не используется, хотя в литературе встречается изложение основ теории алгебраического кодирования с широким применением 
этого понятия.
Кольцо всех многочленов над полем F  обозначается F x
[ ].

Глава I. Многочлены над конечными полями 

Теорема 2. Для любых многочленов f x
( ) и g x
( ) из F x
[ ] при 

g x
( ) № 0 существует единственный многочлен r x
( ) из F x
[ ] такой, 
что f x
g x
q x
r x
( )
( )
( )
( )
=
Ч
+
 для некоторого q x
( ) из F x
[ ], причем 

deg ( )
deg ( ).
r x
g x
<

Заметим, что r x
( ) называется остатком при делении f x
( ) на 

g x
( ), а q x
( ) — частным.
Определение. Пусть f x
( ) и g x
( ) — многочлены из F x
[ ] 
и хотя бы один из них не равен 0. Тогда наибольшим общим делителем называется нормированный многочлен из F x
[ ] наибольшей степени, который без остатка делит f x
( ) и g x
( ).

Практически наибольший общий делитель f x
( ) и g x
( ), который будем в дальнейшем обозначать f x
g x
( ), ( ) ,
(
)  находится 
с помощью алгоритма Евклида, описанного в части I данного 
пособия.
Очень важной является следующая теорема.
Теорема 3. Пусть f x
( ) и g x
( ) — многочлены из F x
[ ] и d x
( ) их 
наибольший общий делитель. Тогда найдутся такие многочлены u x
( ) и v x
( ) из F x
[ ], что f x u x
g x v x
d x
( ) ( )
( ) ( )
( ).
+
=

Нахождение многочленов u x
( ) и v x
( ) осуществляется с помощью модифицированного алгоритма Евклида, описанного 
также в части I пособия.
Определение. Многочлены f x
( ) и g x
( ) из F x
[ ] называются 
взаимно простыми, если их наибольший общий делитель равен 1.

Теорема 4. Пусть f x
g x
h x
F x
( ), ( ), ( )
[ ].
О
 тогда имеют место 
следующие утверждения:
1) f x
( ) и g x
( ) взаимно простые тогда и только тогда, когда 
существуют такие многочлены u x
( ) и v x
( ) над F, что f x u x
g x v x
( ) ( )
( ) ( )
+
=1
 

f x u x
g x v x
( ) ( )
( ) ( )
;
+
=1

2) f x
h x
g x
h x
f x g x
h x
( ), ( )
,
( ), ( )
( ) ( ), ( )
;
(
) =
=
(
) Ю (
) =
1
1
1

§ 1. Обзор общей теории многочленов

3) f x g x
h x
g x
h x
f x
h x
( ) ( )
( ),
( ), ( )
( )
( );


(
) = Ю
1

4) f x
g x
f x
h x
g x
h x
f x
g x h x
( )
( ), ( )
( ),
( ), ( )
( )
( ) ( ).



(
) = Ю
1

Здесь запись f x
g x
( )
( )

 означает, что f x
( ) делится на g x
( ) без 
остатка. В дальнейшем этот факт мы часто будем обозначать 
так: g x
f x
g x
f x
( )|
( )
( )делит
( ) .
(
)

Определение. Элемент α из F  называется корнем многочлена f x
( ) из F x
[ ], если f ( )
,
a = 0  т. е. при подстановке в выражение 
для f x
( ) элемента α вместо x в итоге получается 0.

Теорема 5 (Безу). Если α — корень многочлена f x
( ), то f x
( ) 
делится на (
)
x -a  без остатка.
Следствие 1. Любой многочлен f x
( ) степени n і1 над полем 

F  имеет не более n различных корней.
Определение. Поле F  называется алгебраически замкнутым, 
если любой многочлен над F  степени і1 имеет корень в F .

Пример. Поля  и  не являются алгебраически замкнутыми, так как, например, x 2
1
+  не имеет корней в , зато поле  
алгебраически замкнуто (это утверждение называется основной теоремой алгебры).
Теорема 6. Пусть F  — алгебраически замкнутое поле  
и f x
F x
f x
( )
[ ], deg ( )
.
О
і1  Тогда f x
a
x
x
n
( )
(
)
(
),
=
ј
0
1
a
a
 где a0 — 
старший коэффициент f x
( ), n
f x
= deg ( ).

Определение. Элемент α из F  называется корнем кратности k 
многочлена f x
( ) из F, если f x
x
g x
k
( )
(
)
( )
=
-a
 и g( )
.
a № 0

С учетом этого определения получаем следствие к теореме 6.
Следствие 2. Любой многочлен f x
( ) степени і1 над алгебраически замкнутым полем F  представим в виде f(x) = 

f x
a
x
x
k
r
kr
( )
(
)
(
) ,
=
ј
0
1

1
b
b
 где элементы bi — попарно различные 
корни f x
( ) кратностей ki соответственно.
Определение. Пусть f x
F x
( )
[ ].
О
 Тогда f x
( ) неприводим над 

F, если f x
( ) нельзя представить в виде f x
g x h x
( )
( ) ( ),
=
 где g x
( ) 

Глава I. Многочлены над конечными полями 

и h x
( ) — многочлены степеней і1 над F . В противном случае 

f x
( ) называется приводимым над F .

Примеры. Ясно, что любой многочлен первой степени неприводим, но существуют неприводимые многочлены степени >1. 
Например, квадратный вещественный трехчлен неприводим 
над  тогда и только тогда, когда его дискриминант меньше 
нуля. Однако над алгебраически замкнутым полем все неприводимые многочлены имеют степени 1.

Теорема 7. Любой многочлен f x
( ) степени і1 над полем F  
представим в виде f x
g
x
g
x
r
( )
( )
( ),
=
ј
1
 где все g x
i( ) неприводимы над F  и данное представление однозначно с точностью 
до перестановки сомножителей и их умножения на ненулевые 
элементы из F .

Формула для f x
( ) в теореме 7 называется неприводимым разложением f x
( ) над полем F .

Пример. (
)(
)
(
)(
)
2
2 3
6
3
3 2
4
x
x
x
x
+
+
=
+
+
 — неприводимые разложения многочлена f x
x
x
( ) =
+
+
6
18
12
2
 над .

Теорема 8. Пусть f x
( ) — многочлен над полем F  степени 2 
или 3. Тогда f x
( ) неприводим над F  тогда и только тогда, когда f x
( ) имеет корень в F .

С помощью этой теоремы можно получить все неприводимые многочлены над F2 степеней 2, 3 и 4. А именно, существует единственный неприводимый многочлен степени 2: x
x
2
1
+
+ , 
два неприводимых многочлена степени 3: x
x
3
1
+
+  и x
x
3
2
1
+
+  
и три неприводимых многочлена степени 4: x
x
4
1
+
+ , x
x
4
3
1
+
+ , 

x
x
x
x
4
3
2
1
+
+
+
+ . Доказательство имеется в части I данного пособия.
В качестве еще одного примера использования теоремы 
8 найдем все нормированные неприводимые многочлены степени 2 над F3.

Пусть многочлен f x
x
x
( ) =
+
+
2
a
b неприводим над F3. Тогда 

b =1 или b = 2.