Основы компьютерной алгебры с приложениями

Научная библиотека

Научная библиотека

Основы компьютерной алгебры с приложениями

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

Монография американского специалиста описывает введение в компьютерную алгебру, основные результаты и приложения. В ней содержится материал, дополняющий литературу на русском языке по данной тематике: вычисление полиномиальных остатков, нахождение корней многочленов с высокой точностью и др. Изложение иллюстрируется большим числом примеров, дается много задач для самостоятельного решения.

Для разных специалистов, занимающихся разработкой и реализацией алгоритмов компьютерной алгебры, для аспирантов и студентов университетов.

Оглавление

ОТ ПЕРЕВОДЧИКА
ПРЕДИСЛОВИЕ
Часть I. ВВЕДЕНИЕ
1.1. Компьютерная алгебра и численный анализ
1.2 Компьютерная алгебра: точная целочисленная и полиномиальная арифметики
Списочное представление целых чисел.
Структуры данных.
Алгоритмы и их сложность.
Классические алгоритмы целочисленной арифметики и их сложность.
Списочное представление полиномов.
Классические алгоритмы полиномиальной арифметики и их сложность.
1.3 Системы компьютерной алгебры
Упражнения
Часть II. МАТЕМАТИЧЕСКИЕ ОСНОВАНИЯ И ОСНОВНЫЕ АЛГОРИТМЫ
2.1.2. Отношения эквивалентности
2.1.3. Функции и алгебраические системы
2.2. Наибольшие общие делители целых чисел
2.2.2. Алгоритм Евклида и теорема Ламе
2.2.3. Расширенный алгоритм Евклида
2.2.4. Алгоритм Евклида и цепные дроби
2.3. Разложение целых чисел на множители
2.3.2. Целые числа по модулю m и алгоритм в грекокитайской теореме об остатках
Применения линейных сравнений по модулю m.
Вычисление мультипликативных обратных.
Малая теорема Ферма (1640).
Еще раз о теореме Ферма.
Некоторые результаты из теории групп.
Уравнения по модулю некоторого числа m.
2.3.3. Тесты простоты
2.3.4. Разложение на множители больших целых чисел
2.4. Точные вычисления, использующие модулярную арифметику
Упражнения
Упражнения по программированию
Исторические замечания и литература
Глава 3. Полиномы
3.1.2. Метод Руффини-Горнера
3.1.3. Интерполяция надполем
3.1.4. Вычисления, использующие схему: (вычисление значений) – интерполяция
3.2. Наибольшие общие делители полиномов над полем
3.2.2. Алгоритм Евклида для полиномов над полем
3.2.3. Неприводимые сомножители полиномов
3.2.4. Разложение полиномов на свободные от квадратов множители
3.3. Поля Галуа GF(p^r)
3.3.2. Построение полей Галуа GF(2^r)
3.3.3. Схемы для полиномиальной арифметики в GF(2^r)
Упражнения
Упражнения по программированию
Литература
Часть III. ПРИЛОЖЕНИЯ И СОВРЕМЕННЫЕ МЕТОДЫ
Глава 4. Коды, исправляющие ошибки, и криптография
4.1.1. Коды Хэмминга
4.1.2. БЧХ-коды
4.2. Криптография — общие понятия
4.2.1. Симметричные криптосистемы (единого ключа)
4.2.2. Асимметричные криптосистемы (открытого ключа)
Упражнения
Упражнения по программированию
Литература
Глава 5. Наибольшие общие делители полиномов над целыми числами и последовательности полиномиальных остатков
5.1.1. Общий обзор классических алгоритмов PRS
5.1.2. Неклассический подход: модулярный алгоритм для наибольшего общего делителя
5.2. Метод Сильвестра-Габихта псевдоделения субрезультантных PRS
5.2.2. Результант двух полиномов
5.2.3. Алгоритм Габихта субрезультантных PRS
5.3. Метод матричной триангуляризации субрезультантных PRS
5.3.2. Гауссово исключение и результанты в формах Брюно и Труда
5.3.3. Гауссово исключение + результант в форме Сильвестра = метод матричной триангуляризации субрезультантных PRS
5.4. Эмпирическое сравнение двух методов субрезультантных PRS
Упражнения
Упражнение по программированию
Исторические замечания и литература
Глава 6. Разложение на множители полиномов над целыми числами
6.1.1. Метод Кронекера—Шуберта разложения на множители над целыми числами
6.1.2. Общая схема «окольного» метода разложения над кольцом целых чисел
6.2. Разложение на множители полиномов над конечным полем
6.2.2. Вычисление числа неприводимых полиномов над конечными полями
6.2.3. Разложение полиномов на множители разных степеней (частичное) над конечными полями
6.2.4. Алгоритм Берлекэмпа разложения на множители над конечными полями
6.3. Подъем (mod p) – разложения до разложения над целыми числами
6.3.1. Линейный и квадратичный подъем
6.3.2. Нахсмвдение истинных сомножителей над целыми числами
Упражнения
Исторические замечания и литература
Глава 7. Отделение и аппроксимация вещественных корней полиномиальных уравнений
7.2. Теорема Фурье и метод бисекций Штурма отделения вещественных корней
7.2.2. Теорема Штурма и метод бисекций Штурма отделения вещественных корней
7.2.3. Вычисление верхней (нижней) границы значений положительных корней полиномиального уравнения
7.2.4. Вычисление нижней границы расстояния между любыми двумя корнями полиномиального уравнения
7.3. Теорема Бюдана и два метода цепных дробей для отделения вещественных корней
7.3.2. Подстановки Мёбиуса и их воздействие на корни уравнения
7.3.3. Теорема Винсента: расширение и приложения
7.3.4. Два метода цепных дробей отделения вещественных корней
7.4. Эмпирическое сравнение двух методов отделения вещественных корней
7.5. Аппроксимация вещественных корней полиномиального уравнения
7.5.2. Аппроксимация вещественного корня с использованием цепных дробей
7.6. Эмпирическое сравнение двух методов аппроксимации вещественных корней
Упражнения
Упражнения по программированию
Исторические замечания и литература
ПРИЛОЖЕНИЕ. ЛИНЕЙНАЯ АЛГЕБРА