ALGORITMIQUE ALGÉBRIQUE
Avec exercices corrigés
Patrice NAUDIN
Maître de conférences à l'université de Bordeaux I
Claude QUITTÉ
Maître de conférences à l'université de Poitiers
MASSON, Paris, 1992
Пер. с франц. В. А. Соколова
Формат 60x90 1/16. Бумага писчая. Печать офсетная

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

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

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

Книга Патриса Нодена и Клода Китте представляет классическую алгебру — ту, которая преподаётся на уровне второго цикла университета, но в свете новой алгоритмической идеологии. Для рассматриваемой темы алгебра подходит лучше всего: алгоритмика по самой своей природе комбинаторна, а среди всех основных математических дисциплин алгебра является, несомненно, «самой комбинаторной».

Это превосходная книга, которую я ставлю в моей библиотеке на полку со священными книгами, где находятся уже два евангелия — алгоритмика по Вирту и алгоритмика по Кнуту. Теперь я обладаю третьим евангелием; кто же напишет четвёртое? Но ведь эта книга потребовала коллективной работы двух авторов — ещё одно примечательное свойство, так что может быть моя коллекция евангелий уже полна? Нет: это противоречило бы Гёделю, но это уже совсем другая история.

Франсис Сержераер

Предисловие переводчика и редактора перевода	5
Предисловие к русскому изданию	8
Предисловие	11
От авторов	16

Глава I. Алгоритмика и программирование на языке Ада	21
1 Введение в алгоритмику	22
1.1 Терминология и обозначения	22
1.2 Присваивание	23
1.3 Последовательность	24
1.4 Альтернатива	25
1.5 Итерация	28
1.6 Итерация со счётчиком или цикл «для»	28
1.7 Цикл «пока»	30
1.8 Итерация (продолжение и окончание)	31
2 Дихотомический алгоритм возведения в степень	32
2.1 Математический (или рекуррентный) подход	33
2.2 Алгоритмический подход	34
2.3 Изучение сложности алгоритма	37
3 Введение в программирование на языке Ада	39
3.1 Программа сравнения двух методов возведения в степень	39
3.2 Об использовании типов	47
3.3 Итерация в моноиде — Настраиваемые функции	51
3.3.1 Настраиваемая функция дихотомического алгоритма возведения в степень	53
3.3.2 Использование настраиваемой функции	56
3.4 Необычное использование компилятора языка Ада	61
4 Хорошее приближение к бесконечности!	63
4.1 Элементы обработки массивов в языке Ада	64
4.2 Работа с матрицами	69
4.3 Ввод-вывод матриц	76
4.4 Описание генератора биекций	78
4.5 Вычисление определителя	80
4.6 Вычисление определителя: несколько цифр	83
4.7 Перестановки конечного множества	85
4.8 Настраиваемый модуль генератора биекций	90
5 Заключение	93
Упражнения	96
Решения упражнений	119

Глава II. Евклид и основная теорема арифметики	177
1 Обобщение арифметики целых чисел	179
1.1 Делимость и неприводимые элементы	180
1.2 Что такое факториальное кольцо?	181
1.3 Обобщать арифметику целых чисел: зачем?	182
2 Элементарные свойства теории делимости	186
2.1 Существование и единственность разложения на простые множители	186
2.2 НОД и взаимно простые элементы	187
2.3 Выделяемые понятия	188
2.4 Соотношение Безу	191
3 Евклидовы кольца с точки зрения эффективности	193
3.1 Что такое евклидово кольцо?	193
3.2 Алгоритм Евклида нахождения НОД	196
3.3 Реализация в языке Ада вычисления НОД	197
3.4 Сравнение эффективности различных делений	199
3.5 Факториальность евклидовых колец без делителей нуля	200
4 Многочлены с коэффициентами из поля	202
4.1 Евклидово деление в K[X] (К — поле)	203
4.2 Неприводимые многочлены с коэффициентами из Z/pZ	205
4.3 Простой критерий неприводимости по модулю р	209
5 Кольца главных идеалов или идеалистическая точка зрения	210
5.1 Идеализация	210
5.2 Частные кольца главных идеалов	212
6 Об оптимальных алгоритмах вычисления НОД	213
6.1 Вычисление НОД двух целых чисел: теорема Ламе	213
6.2 Квазиевклидовы кольца	217
6.3 Вычисление НОД нескольких целых чисел: теорема Дирихле	220
7 Расширенный алгоритм Евклида	227
7.1 Вычисление коэффициентов Безу в квазиевклидовом кольце	227
7.2 Мажорирование коэффициентов Безу в Z	230
8 Факториальность кольца многочленов	231
9 Вместо заключения	238
Упражнения	242
Решения упражнений	270

Глава III. Модули над кольцами главных идеалов	307
1 Исключение и несколько следствий	311
1.1 Операции над строками и столбцами матрицы	311
1.2 Лемма исключения	312
1.3 Вычисление определителей	315
1.4 Модули без кручения конечного типа	317
2 Нормальная форма подгруппы группы Zⁿ	319
2.1 Исследование подгруппы nZ x mZ группы Z²	319
2.2 Изучение подгруппы a₁Z x … x a_nZ группы Zⁿ	321
2.3 Единственность нормального разложения	325
3 Вычисление образа и ядра матрицы	329
3.1 Ступенчатые матрицы	329
3.2 Вычисление образа матрицы	330
3.3 Существование решения системы линейных уравнений	336
3.4 Вычисление ядра матрицы	340
3.5 Общее решение системы линейных уравнений	341
3.6 Ранг модулей	343
4 Приведение матрицы	347
5 Модули конечного типа над кольцом главных идеалов	355
5.1 Дополнение, свобода и кручение	355
5.2 Инвариантные множители подмодуля свободного модуля	359
5.3 Инвариантные множители модуля конечного типа	366
6 Беглый обзор	368
Упражнения	373
Решения упражнений	388

Глава IV. Некоторые методы алгебраической алгоритмики	411
1 Кольцо Z/nZ	413
2 Китайская теорема об остатках	420
2.1 Различные формы китайской теоремы об остатках	420
2.2 Модулярная арифметика и смешанная система счисления	425
2.3 Умножение целых чисел методом Полларда	430
3 Группа обратимых элементов в Z/nZ	438
3.1 Порождающие Z/nZ и функция Эйлера	438
3.2 Системы криптографии с открытым ключом	440
3.2.1 Система RSA	442
3.2.2 Алгоритм рюкзака	444
3.2.3 Как разделить секрет?	447
3.3 Мультипликативные группы конечных полей	448
3.3.1 Аннулятор конечной абелевой группы	451
3.3.2 Индикатор Кармайкла	453
3.4 Группа обратимых элементов Z/p^rZ	456
3.4.1 Несколько полезных сравнений	456
3.4.2 Группа обратимых элементов Z/2^rZ	460
3.4.3 Группа обратимых элементов Z/p^rZ при нечётном р	461
4 Почти периодические последовательности	465
4.1 Одношаговый генератор	466
4.2 Генерирование при помощи линейных сравнений	470
4.3 Нахождение периода методом Брента	473
5 Квадратичные вычеты	479
5.1 Общие свойства	480
5.2 Квадратные корни: метод Цассенхауза-Кантора	485
5.3 Квадратные корни: метод Шенкса	493
6 Факторизация и простота	497
6.1 Числа Мерсенна	497
6.2 Тест на простоту Рабина-Миллера	504
6.2.1 Вероятностный алгоритм Рабина	508
6.2.2 Доказательство теоремы Рабина	510
6.3 Ро-метод Полларда факторизации чисел	516
7 Это только начало	519
Упражнения	521
Решения упражнений	543

Глава V. Дискретное преобразование Фурье	581
1 Сложность умножения двух многочленов	582
1.1 Интерполяция многочленов над полем и над кольцом	582
1.2 Вычисление значений многочленов в корнях из единицы	584
1.3 Примитивные корни из единицы	587
1.4 Дискретное преобразование Фурье и циклическая свёртка	590
1.5 Обзор различных понятий	594
2 Быстрое преобразование Фурье	594
2.1 Случай, когда порядок есть степень двойки	595
2.2 Случай, когда порядок — произвольная степень	597
2.3 Пример итеративного алгоритма	597
2.3.1 От рекурсии к итерации	598
2.3.2 Суммы Йейтса	600
3 Точное вычисление FFT: произведение многочленов	601
3.1 Реализация FFT, когда число точек есть степень 2	601
3.2 Как реализовать FFT?	603
3.3 Умножение многочленов	606
3.4 Реализация произведения многочленов	608
3.5 Вычисление преобразования Фурье	610
4 Подробное рассмотрение метода Кули и Тьюки	615
4.1 Метод Кули-Тьюки для произведения двух множителей	616
4.2 Итерация метода Кули-Тьюки	621
4.2.1 Сложность итерационного метода Кули-Тьюки	622
4.2.2 Формулы для итераций по методу Кули-Тьюки	623
5 Метод Гуда	627
5.1 Исследование примера 15 = 3 х 5	627
5.2 Теорема Гуда	629
6 Вычисление семейства билинейных форм	633
6.1 Некоторые напоминания, определения и основные свойства	634
6.2 Тензорный ранг произведения двух многочленов	637
6.3 Пример: циклическая свертка порядка 4	641
6.4 Семейство билинейных форм и трилинейные формы	642
6.5 Пример: циклическая свёртка порядка 4 (продолжение)	644
7 Малые схемы для дискретного преобразования Фурье	647
7.1 DFT порядка р и СС порядка р - 1 (метод Рейдера)	647
7.2 Комбинация схем Рейдера и Гуда	650
7.2.1 Подробное изучение DFT₃	650
7.2.2 Снова DFT₅	652
8 От FFT к тензорному произведению	655
Упражнения	659
Решения упражнений	673

Литература	699
Литература, добавленная к русскому изданию	708
Алфавитный указатель	709
Обозначения	714

Книги на ту же тему

Простая одержимость: Бернхард Риман и величайшая нерешённая проблема в математике, Дербишир Д., 2010
Теория алгоритмов: основные открытия н приложения, Успенский В. А., Семёнов А. Л., 1987
Арифметика. Алгоритмы. Сложность вычислений: Популярное введение в теорию чисел и арифметическую теорию сложности, Гашков С. Б., Чубариков В. Н., 1996
Коды и математика (рассказы о кодировании), Аршинов М. Н., Садовский Л. Е., 1983
Элементы криптографии (Основы теории зашиты информации): Учебное пособие для университетов и пед. вузов, Нечаев В. И., 1999
Коды, исправляющие ошибки, Питерсон У. У., Уэлдон Э. Д., 1976
Программирование на языке Ада, Вегнер П., 1983

elapsed time 0.022 sec

/Наука и Техника/Математика

ОГЛАВЛЕНИЕ

Книги на ту же тему