Отправить другу/подруге по почте ссылку на эту страницуВариант этой страницы для печатиНапишите нам!Карта сайта!Помощь. Как совершить покупку…
московское время18.07.24 05:43:26
На обложку
Итоги науки и техники: Физика плазмы. Том 5авторы — Шафранов В. Д., ред.
Год 1762авторы — Искюль С. Н.
Исследования по истории физики и механики. 2001авторы — Идлис Г. М., ред.
б у к и н и с т и ч е с к и й   с а й т
Новинки«Лучшие»Доставка и ОплатаМой КнигоПроводО сайте
Книжная Труба   поиск по словам из названия
В ВЕСЕННЕ-ЛЕТНЕ-ОСЕННЕЕ ВРЕМЯ ВОЗМОЖНЫ И НЕМИНУЕМЫ ЗАДЕРЖКИ ПРИ ОБРАБОТКЕ ЗАКАЗОВ
Авторский каталог
Каталог издательств
Каталог серий
Моя Корзина
Только цены
Рыбалка
Наука и Техника
Математика
Физика
Радиоэлектроника. Электротехника
Инженерное дело
Химия
Геология
Экология
Биология
Зоология
Ботаника
Медицина
Промышленность
Металлургия
Горное дело
Сельское хозяйство
Транспорт
Архитектура. Строительство
Военная мысль
История
Персоны
Археология
Археография
Восток
Политика
Геополитика
Экономика
Реклама. Маркетинг
Философия
Религия
Социология
Психология. Педагогика
Законодательство. Право
Филология. Словари
Этнология
ИТ-книги
O'REILLY
Дизайнеру
Дом, семья, быт
Детям!
Здоровье
Искусство. Культурология
Синематограф
Альбомы
Литературоведение
Театр
Музыка
КнигоВедение
Литературные памятники
Современные тексты
Худ. литература
NoN Fiction
Природа
Путешествия
Эзотерика
Пурга
Спорт

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

Алгебраическая алгоритмика (с упражнениями и решениями) — Ноден П., Китте К.
Алгебраическая алгоритмика (с упражнениями и решениями)
Учебное издание
Ноден П., Китте К.
год издания — 1999, кол-во страниц — 720, ISBN — 5-03-003318-1, 2-225-82703-6, тираж — 5000, язык — русский, тип обложки — мягк., издательство — Мир
КНИГА СНЯТА С ПРОДАЖИ
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. Бумага писчая. Печать офсетная
ключевые слова — алгоритм, алгебр, евклид, итерац, рекуррентн, компилятор, арифмет, многочлен, поллард, rsa, абелев, кармайкл, цассенхауза-кантор, рабина-миллер, факторизац, йейтс, fft, кули-тьюк, dft

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

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

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

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

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

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

ОГЛАВЛЕНИЕ

Предисловие переводчика и редактора перевода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/pZ205
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 Мажорирование коэффициентов Безу в Z230
8 Факториальность кольца многочленов231
9 Вместо заключения238
Упражнения242
Решения упражнений270
 
Глава III. Модули над кольцами главных идеалов307
1 Исключение и несколько следствий311
1.1 Операции над строками и столбцами матрицы311
1.2 Лемма исключения312
1.3 Вычисление определителей315
1.4 Модули без кручения конечного типа317
2 Нормальная форма подгруппы группы Zn319
2.1 Исследование подгруппы nZ x mZ группы Z2319
2.2 Изучение подгруппы a1Z x … x anZ группы Zn321
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/nZ413
2 Китайская теорема об остатках420
2.1 Различные формы китайской теоремы об остатках420
2.2 Модулярная арифметика и смешанная система счисления425
2.3 Умножение целых чисел методом Полларда430
3 Группа обратимых элементов в Z/nZ438
3.1 Порождающие Z/nZ и функция Эйлера438
3.2 Системы криптографии с открытым ключом440
    3.2.1 Система RSA442
    3.2.2 Алгоритм рюкзака444
    3.2.3 Как разделить секрет?447
3.3 Мультипликативные группы конечных полей448
    3.3.1 Аннулятор конечной абелевой группы451
    3.3.2 Индикатор Кармайкла453
3.4 Группа обратимых элементов Z/prZ456
    3.4.1 Несколько полезных сравнений456
    3.4.2 Группа обратимых элементов Z/2rZ460
    3.4.3 Группа обратимых элементов Z/prZ при нечётном р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, когда число точек есть степень 2601
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 х 5627
5.2 Теорема Гуда629
6 Вычисление семейства билинейных форм633
6.1 Некоторые напоминания, определения и основные свойства634
6.2 Тензорный ранг произведения двух многочленов637
6.3 Пример: циклическая свертка порядка 4641
6.4 Семейство билинейных форм и трилинейные формы642
6.5 Пример: циклическая свёртка порядка 4 (продолжение)644
7 Малые схемы для дискретного преобразования Фурье647
7.1 DFT порядка р и СС порядка р - 1 (метод Рейдера)647
7.2 Комбинация схем Рейдера и Гуда650
    7.2.1 Подробное изучение DFT3650
    7.2.2 Снова DFT5652
8 От FFT к тензорному произведению655
Упражнения659
Решения упражнений673
 
Литература699
Литература, добавленная к русскому изданию708
Алфавитный указатель709
Обозначения714

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

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

Напишите нам!© 1913—2013
КнигоПровод.Ru
Рейтинг@Mail.ru работаем на движке KINETIX :)
elapsed time 0.021 secработаем на движке KINETIX :)