Федеральное агентство по образованию

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
Государственное образовательное учреждение
высшего профессионального образования
«Уральский государственный университет им. А.М. Горького»
Факультет математико-механический
Кафедра вычислительной математики
КОМПЬЮТЕРНАЯ АЛГЕБРА
Программа дисциплины
(Стандарт ОПД.В.03.02)
Екатеринбург
2009
I. Введение
Цель дисциплины.
Целью курса «Компьютерная алгебра» является обеспечение базовой
подготовки студентов в области компьютерной алгебры, знакомство с
основными понятиями и техникой символьных вычислений.
Задачи дисциплины:
дать представление об основных алгоритмах точной компьютерной
арифметики (целые, рациональные и модулярные числа, полиномы);
дать представление о компьютерной реализации символьных вычислений
средствами языка LISP;
дать навыки работы в системах компьютерной алгебры на примере
системы GAP.
Место дисциплины в системе высшего профессионального образования (какие
дисциплины используются в качестве основы для данной и для каких
используется данная дисциплина).
Курс опирается на знания, полученные студентами в рамках дисциплин «Языки
и технологии программирования», «Дискретная математика» и «Общая
алгебра».
Требования к уровню освоения содержания курса
В результате изучения дисциплины студент должен знать:
особенности символьных вычислений как методологии точного решения
вычислительных задач;
тенденции и перспективы развития инструментальных средств
компьютерной алгебры.
Студент должен уметь:
строить модели задач, используя парадигму компьютерной алгебры;
овладеть базовыми навыками работы в системе GAP.
Методическая новизна курса (новые методики, формы работы, авторские
приемы в преподавании курса).
Методическая новизна курса состоит в том, что он сочетает изложение
теоретических и алгоритмических основ компьютерной алгебры с
практическим освоением техники символьных вычислений.
II. Содержание курса
1. Разделы курса, темы, их краткое содержание
1) Сравнительный анализ методов компьютерной алгебры и
вычислительной математики. Ретроспектива и перспектива развития
компьютерной алгебры. Знакомство с системой GAP.
2) Сущность символьных вычислений. Lisp-машина как универсальный
вычислитель для символьных вычислений. Основные элементы языка Lisp:
Атомы, списки, выражения. Цикл read-val-print. Общая схема символьных
вычислений. Правила переписывания.
3) Понятие канонической и нормальной формы представления данных.
Примеры алгоритмической неразрешимости построения нормальной формы.
Каноническая форма представления целых и рациональных чисел, колец
вычетов и конечных полей, алгебраических чисел.Трансцендентные числа и
возможность работы с ними. Каноническая форма представления многочленов
и рациональных функций.
4) Арифметика целых чисел. Быстрое умножение (алгоритмы Карацубы,
Тоома-Кука, Шёнхаге-Штрассена). Быстрое деление методом «разделяй и
властвуй». Модулярная арифметика.
5) Конечные поля. Основные факты о их строении. Вычисления в
конечных полях. Алгоритмы поиска неприводимого многочлена над простым
конечным полем.
6) Полиномиальная арифметика. Алгоритмы вычисления наибольшего
общего делителя для целых чисел и многочленов.
7) Оценки Коши и Лиувилля для коэффициентов делителя многочленов от
одной переменной. Алгоритмы Кронекера факторизации многочленов от одной
и многих переменных. Алгоритмы факторизации многочленов с
использованием комплексных и вещественных корней.
8) Основные алгоритмы вычислительной теории чисел. Проверка
простоты числа. Алгоритмы факторизации натуральных чисел.
2. Темы лабораторных занятий
1) Символьное дифференцирование многочленов.
2) Символьное упрощение многочленов.
3) Символьное дифференцирование трансцендентных выражений.
4) Символьное упрощение трансцендентных выражений.
5) Реализация алгоритмов вычисления НОД для целых чисел.
6) Реализация алгоритмов вычисления НОД для многочленов.
7) Факторизация многочленов от одной переменной.
8) Факторизация натуральных чисел.
III. Распределение часов курса по темам и видам работ
Общая трудоемкость дисциплины – 8 зачетных единицы.
Учебный план, часов
№
Аудиторные заня- Самосто
Итого
п/
Тема, раздел
тия
япо
п
темам
лекции лаборат тельная
работа
орные
1
2
3
4
Сравнительный анализ методов
компьютерной алгебры и
вычислительной математики.
Ретроспектива и перспектива
развития компьютерной
алгебры. Знакомство с системой
GAP.
Сущность символьных
вычислений. Lisp-машина как
универсальный вычислитель
для символьных вычислений.
Основные элементы языка Lisp:
Атомы, списки, выражения.
Цикл read-val-print. Общая
схема символьных вычислений.
Правила переписывания.
Понятие канонической и
нормальной формы
представления данных.
Примеры алгоритмической
неразрешимости построения
нормальной формы.
Каноническая форма
представления целых и
рациональных чисел, колец
вычетов и конечных полей,
алгебраических
чисел.Трансцендентные числа и
возможность работы с ними.
Каноническая форма
представления многочленов и
рациональных функций.
Арифметика целых чисел.
Быстрое умножение (алгоритмы
Карацубы, Тоома-Кука,
Шёнхаге-Штрассена). Быстрое
деление методом «разделяй и
властвуй». Модулярная
арифметика.
2
2
2
6
4
4
2
10
6
6
2
14
6
6
2
14
5
6
7
8
Конечные поля. Основные
факты о их строении.
Вычисления в конечных полях.
Алгоритмы поиска
неприводимого многочлена над
простым конечным полем.
Полиномиальная арифметика.
Алгоритмы вычисления
наибольшего общего делителя
для целых чисел и многочленов.
Оценки Коши и Лиувилля для
коэффициентов делителя
многочленов от одной
переменной. Алгоритмы
Кронекера факторизации
многочленов от одной и многих
переменных. Алгоритмы
факторизации многочленов с
использованием комплексных и
вещественных корней.
Основные алгоритмы
вычислительной теории чисел.
Проверка простоты числа.
Алгоритмы факторизации
натуральных чисел.
Итого:
6
6
2
14
2
2
2
6
2
2
2
6
2
2
1
5
30
30
15
75
IV. Форма итогового контроля
Экзамен.
V. Учебно-методическое обеспечение курса
1. Рекомендуемая литература (основная)
1. Тан К. Ш.; Ахмолин В. И. (переводчик)Кобельков Г. М. (ред.)Чудов С. В.
(переводчик). Символьный C++: Введение в компьютерную алгебру с
использованием объектно-ориентированного программирования.
монография. Мир, 2001.
2. Тан Киат Ши; Стиб Вилли-Ханс; Харди Йорик. Символьный C++:
Введение в компьютерную алгебру с использованием объектноориентированного программирования. учебник. , 2001.
3. Коблиц Н. Курс теории чисел и криптографии / Пер. с англ. – М: ТВП,
2001. – 254 с.
4. Кузнецов М. И. и др. Компьютерная алгебра. - Н. Новгород: Изд-во
Нижегород. гос. ун-та, 2002. – 223 с.
5. Панкратьев Е. В. Элементы компьютерной алгебры. – М.: БИНОМ, 2007.
– 248 с.
2. Рекомендуемая литература (дополнительная)
1. Олифер В.. Сетевые операционные системы. учебник. Питер, 2008.
2. Акритас А. Основы компьютерной алгебры с приложениями / Пер. с англ.
– М.: Мир, 1994. – 544 с.
3. Боревич З. И., Шафаревич И. Р. Теория чисел. – 3-е изд., доп. – М.: Наука,
1985. – 504 с.
4. Компьютерная алгебра. Символьные и алгебраические вычисления / Пер.
с англ. / Под ред. Б. Бухбергера, Дж. Коллинза, Р. Лооса. – М.: Мир, 1986.
– 392 с.
5. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. – М.:
МЦНМО, 2003. – 328 с.
6. Грегори Р., Кришнамурти Е. Безошибочные вычисления. Методы и
приложения / Пер с англ. – М.: Мир, 1988. – 208 с.
7. Дэвенпорт Дж., Сирэ И., Турнье Э. Компьютерная алгебра: символьные и
алгебраические вычисления / Пер. с англ. – М.: Мир, 1991. – 350 с.
3. Перечень обучающих, контролирующих компьютерных программ,
кино- и телефильмов, мультимедиа и т.п.
Компилятор Gnu Common Lisp.
Система компьютерной алгебры GAP 4.
VI. Ресурсное обеспечение (если требуется)
Компьютерные классы.