РАБОЧИЙ УЧЕБНЫЙ ПЛАН

ЭЛЕМЕНТЫ АБСТРАКТНОЙ И КОМПЬЮТЕРНОЙ АЛГЕБРЫ

4м курс дневного отделения, 16 часов лекций, 12 часов практических занятий,

контрольная работа, коллоквиум, экзамен.

СПИСОК ЛИТЕРАТУРЫ

1. А. Акритас. Основы компьютерной алгебры с приложениями. М.: Мир, 1994.

2. Г. Биркгоф, Т. Барти. Современная прикладная алгебра. М.: Мир, 1976.

3. Д. Дэвенпорт, И. Сирэ, Э. Турнье. Компьютерная алгебра. М.: Мир, 1991.

4. . Алгебра и теория чисел. М.: Высшая школа, 1979.

5. . Курс высшей алгебры. М.: Наука, 1975.

6. , . Элементы абстрактной и компьютерной
алгебры. М. Академия, 2004.

7. . Лекции по алгебре. М.: Наука, 1984.

8. , , . Сборник задач по алгебре и теории чисел. М.: Просвещение, 1993.

План ЛЕКЦИЙ

ЛЕКЦИИ 1, 2. Кольцо и поле.

Фактор-кольцо. Характеристика кольца. Минимальный многочлен алгебраического элемента. Простое расширение поля. Конечное поле.

ЛЕКЦИИ 3, 4, 5. Теория кодирования.

Блочный код. Двоичный симметричный канал. Групповой код. Матричный код. Код Хэмминга. Полиномиальный код. Код Боуза-Чоудхури-Хоккенгема.

ЛЕКЦИЯ 6. Криптография.

Симметричные и асимметричные криптосистемы.

КОЛЛОКВИУМ по материалу лекций 1-6.

ЛЕКЦИИ 7, 8. Компьютерная алгебра.

Представление символьных данных в компьютере. Алгоритмы и их сложность. Алгоритмы символьных преобразований.

План ПРАКТИЧЕСКИХ ЗАНЯТИЙ

ЗАНЯТИЕ 1. Группа.

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

2. Доказать, что группа из задач 1 изоморфна аддитивной группе действительных чисел.

НЕ нашли? Не то? Что вы ищете?

3. Доказать, что множество из четырех подстановок , , , является группой относительно операции композиции подстановок. Составить таблицу Кэли. Ответ: таблица Кэли композиции элементов этой группы имеет вид:

e

a

b

c

e

e

a

b

c

a

a

b

c

e

b

b

c

e

a

c

c

e

a

b

4. Найти порядки элементов:

а) в группе . Ответ: 4.

б) 30 в группе . Ответ: 9.

5. Найти порядки всех элементов группы из задачи 3. Является ли эта группа циклической? Ответ: , , . Группа является циклической.

6. Построить фактор-группу:

а) Аддитивной группы по подгруппе . Ответ: искомая фактор-группа состоит из пяти смежных классов и изоморфна группе .

б) Аддитивной группы по подгруппе . Ответ: искомая фактор-группа состоит из трех смежных классов и изоморфна группе .

ЗАНЯТИЕ 2. Кольцо и поле.

1. Доказать, что множество матриц вида является коммутативным кольцом с единицей относительно операций сложения и умножения матриц. Найти все делители нуля. Ответ: делителями нуля являются матрицы вида .

2. Доказать, что множество чисел вида является полем относительно операций сложения и умножения действительных чисел.

3. Доказать, что множество матриц вида является полем относительно операций сложения и умножения матриц.

4. Доказать, что поле из задачи 2 изоморфно полю из задачи 3.

5. Доказать, что множество из четырех матриц , , , с элементами из является полем относительно операций сложения и умножения матриц. Составить таблицы Кэли сложения и умножения элементов этого поля. Ответ: таблицы Кэли имеют вид:

6. Построить фактор-кольцо Кольца по главному идеалу . Ответ: таблицы Кэли сложения и умножения элементов этого фактор-кольца имеют вид:

ЗАНЯТИЕ 3. Простое алгебраическое расширение поля.

1. Найти многочлен с целыми коэффициентами, корнем которого является следующее число:

а) . Ответ: .

б) . Ответ: .

в) . Ответ: .

2. Составить уравнение с рациональными коэффициентами, корнем которого является :

а) . Ответ: .

б) . Ответ: .

3. Избавиться от иррациональности в знаменателе дроби:

а) . Ответ: .

б) . Ответ: .

КОНТРОЛЬНАЯ РАБОТА по материалу занятий 1-3.

ЗАНЯТИЕ 4. Блочный код. Матричный код.

1. Пусть по двоичному симметричному каналу передаются блок длины 14.

а) Какова вероятность того, что ровно 5 символов будут приняты не верно? Ответ: .

б) Какова вероятность того, что не более чем 5 символов будут приняты не верно?
Ответ: .

в) Сколько существует блоков, отличающихся от данного не более чем в 4 позициях?
Ответ: .

2. Дан (8,9)-код с проверкой на четность. Какова вероятность того, что не будет обнаружена ошибка при передачи блока длины 9? Ответ: .

3. Дан матричный (3,6)-код, порожденный матрицей .

а) Найти матрицу проверки четности. Ответ: .

б) Выписать все кодовые слова. Ответ: 111001.

в) Составить таблицу декодирования. Ответ:

000000

100011

010101

001111

110110

101100

011010

111001

100000

000011

110101

101111

010110

001100

111010

011001

010000

110011

000101

011111

100110

111100

001010

101001

001000

101011

011101

000111

111110

100100

010010

110001

000100

100111

010001

001011

110010

101000

011110

111101

000010

100001

010111

001101

110100

101110

011000

111011

000001

100010

010100

001110

110111

101101

011011

111000

110000

010011

100101

111111

000110

011100

101010

001001

г) Какова вероятность не обнаружить ошибку при передаче блока длины 6?
Ответ: .

д) Какова вероятность верного декодирования? Ответ: .

е) Пусть принято слово 110010 и допущена одна ошибка. Какое слово было передано?
Ответ: 110110.

ЗАНЯТИЕ 5. Полиномиальный код. Код Боуза-Чоудхури-Хоккенгема.

1. Дан полиномиальный (3,7)-код, порожденный многочленом .

а) Найти кодирующую матрицу. Ответ: .

б) Найти матрицу проверки четности. Ответ: .

в) Выписать все кодовые слова. Ответ: 0 1 0 0 1 1 0 1010011.

2. Доказать, что многочлен является примитивным.

3. Найти кодирующий многочлен для БЧХ-кода с длиной кодовых слов 15 и расстоянием 5 между ними. В качестве элемента порядка 15 из поля Галуа взять корень многочлена Ответ: .

ЗАНЯТИЕ 6. Криптография.

1. Используя модулярный шифр с n=7 и k=17 для 33-буквенного алфавита, зашифруйте слово УНИВЕРСИТЕТ. Ответ: ШПНЮТДКНСТС.

2. Используя слово СТУДЕНТ как ключ в коде Виженера, зашифруйте слово УНИВЕРСИТЕТ. Ответ: ЕАЬЁЙЮДЪЕШЦ.

3. С помощью матрицы шифрования для 33-буквенного алфавита, зашифруйте слово УНИВЕРСИТЕТ. Найдите и сделайте проверку. Ответ: ЮШЛЕШДИАЦИТ.

4. Используя криптосистему рюкзака дешифруйте сообщение 15, 75, 52, 97, 2, 55, 29, 52, 41, 23, 41, зная секретную информацию , m=111, n=55. Ответ: УНИВЕРСИТЕТ.

5. Для каждой из следующих задач рюкзака определите, является ли последовательность супервозрастающей и сколько решений она имеет:

а) {2, 3, 6, 17, 33, 67}, n=41. Ответ: 41=2+6+33.

б) {1, 3, 5, 11, 23, 47}, n=69. Ответ: нет решений.

в) {2, 3, 6, 12, 22, 49}, n=61. Ответ: 61=12+49.

ОСНОВНЫЕ ТЕОРЕТИЧЕСКИЕ ВОПРОСЫ

1. Фактор-кольцо.

2. Характеристика кольца.

3. Минимальный многочлен алгебраического элемента.

4. Простое расширение поля.

5. Свойства конечного поля.

6. Число элементов конечного поля.

7. Строение конечного поля.

8. Блочный код. Двоичный симметричный канал.

9. Коды обнаруживающие и исправляющие ошибки.

10. Групповой код.

11. Таблица декодирования.

12. Матричный код.

13. Код Хэмминга.

14. Полиномиальный код.

15. Код Боуза-Чоудхури-Хоккенгема.

16. Симметричные криптосистемы.

17. Асимметричные криптосистемы.

18. Представление символьных данных в компьютере.

19. Алгоритмы и их сложность.

20. Целочисленная компьютерная арифметика.

21. Полиномиальная компьютерная арифметика.

Коллоквиум проводится по вопросам 1-17.

Лектор:

кандидат физ.-мат. наук, доцент______________________