Документ взят из кэша поисковой машины. Адрес оригинального документа : http://new.math.msu.su/content_root/programs/kaf/special/algebra/algalg-pan.doc Дата изменения: Mon Nov 10 08:56:21 2008 Дата индексирования: Sun Apr 10 03:22:15 2016 Кодировка: koi8-r

АЛГЕБРАИЧЕСКИЕ АЛГОРИТМЫ И ИХ СЛОЖНОСТЬ
в.н.с. Е.В. Панкратьев
. Что такое компьютерная алгебра? Примеры задач.
. Системы компьютерной алгебры.
. Проблема представления данных. Целые числа.
. Проблема представления данных. Кольца вычетов и конечные поля.
. Проблема представления данных. Рациональные числа.
. Проблема представления данных. Алгебраические числа.
. Проблема представления данных. Многочлены.
. Проблема представления данных. Рациональные функции.
. Арифметические операции с целыми числами. Быстрое умножение и деление.

. НОД целых чисел. Определение и алгоритмы вычисления.
. Расширенный алгоритм Евклида.
. Расширенный бинарный алгоритм вычисления НОД натуральных чисел.
. Многомодульная арифметика, системы вычетов по смешанному основанию,
китайская теорема об остатках.
. p-адические числа.
. Многочлены от одной переменной над полем и кольцом целых чисел.
Основные свойства, арифметические операции.
. Лемма Гаусса. Содержание многочлена, примитивные многочлены.
. Оценки для модуля корней многочлена.
. Оценки для коэффициентов делителей многочлена.
. НОД многочленов с целыми коэффициентами. Алгоритмы вычисления,
основанные на последовательностях полиномиальных остатков.
. Модулярный алгоритм вычисления НОД многочленов с целыми
коэффициентами.
. Китайская теорема об остатках для многочленов.
. Отношение редукции для многочленов. Условия слияния.
. Базисы Гребнера. Определение и основные свойства.
. Алгоритм построения базисов Гребнера.
. Авторедуцированные множества многочленов.
. Авторедуцированные базисы Гребнера.
. Многочлены Гильберта. Определение, алгоритм включения-исключения.
. Рекурсивный алгоритм вычисления многочленов Гильберта.
. Интегрирование в конечном виде. Постановка задачи. Элементарные
функции.
. Теорема Лиувилля (формулировка).
. Регулярные мономы. Структурная теорема (формулировка и примеры
применения).
. Алгоритм Риша.

Литература
1. Кнут Д. Искусство программирования. Т. 2. Получисленные алгоритмы. 3-е
издание. М.-СПб.-Киев, Вильяме, 2000.
2. Латышев В.Н. Комбинаторная теория колец. Стандартные базисы. М., изд-во
МГУ, 1987.
3. Латышев В.Н. Комбинаторная теория колец. Сложность алгебраических
алгоритмов. М., изд-во МГУ, 1988.
4. Компьютерная алгебра. Символьные и алгебраические вычисления. Под
редакцией Бухбергера, Лооса, Коллинза. М., Мир, 1986.
5. Дэвенпорт Дж., Сирэ И., Турнье Э. Компьютерная алгебра. М., Мир, 1991.
6. Акритас А. Компьютерная алгебра с приложениями. М., Мир, 1994.
7. Панкратьев Е.В. Компьютерная алгебра.
http://shade.msu.ru/~pankrat/BOOK.PS