Алгоритмы компьютерной арифметики, Окулов С.М., Лялин А.В., Пестов О.А., Разова Е.В., 2024

Алгоритмы компьютерной арифметики, Окулов С.М., Лялин А.В., Пестов О.А., Разова Е.В., 2024.
        
   В книге речь идет о традиционных алгоритмах, которые кажутся очевидными, — об алгоритмах выполнения арифметических операций: о том, сколько тайного смысла и усилий интеллекта многих специалистов по информатике заложено в эти алгоритмы. Материал книги формирует содержательную основу деятельностного изучения алгоритмов компьютерной арифметики, чему способствует стиль изложения, синтезирующий в себе и математический материал, и формализованную запись логики работы компьютера.
Для школьников, преподавателей информатики и студентов информационно-технологических специальностей.




Система вычетов.
Операция сравнения по модулю m разбивает все множество целых чисел на m классов. При этом числа, принадлежащие одному какому-то классу, характеризуются тем, что при их делении на m получается один и тот же остаток r, т. е. все числа некоторого класса можно представить в виде m•q + r, где q — любое целое число. Кроме того, все числа одного класса имеют с модулем m один и тот же общий наибольший делитель.

Взятие по одному числу из каждого класса дает нам т чисел. При этом каждое взятое число по отношению к оставшимся числам соответствующего класса определяется как вычет, а все взятые такие числа образуют полную систему вычетов по модулю m (обозначим ее как Zm).

ОГЛАВЛЕНИЕ.
Введение. 
Часть 1. Компьютерная арифметика.
1.1. Алгоритмы целочисленной арифметики. 
Вспомогательные инструменты. 
Сложение неотрицательных целых чисел. 
Вычитание неотрицательных целых чисел.
Умножение неотрицательных целых чисел. 
Деление неотрицательных целых чисел. 
Упражнения. 
1.2. Отрицательные целые числа.
Алгоритм умножения для знаковых чисел в дополнительном коде. 
Алгоритм А. Бута.
Упражнения. 
1.3. Алгоритмы арифметики вещественных чисел.
Упражнения. 
1.4. Алгоритм Евклида. 
Переборный алгоритм.
Алгоритм, использующий разложение числа
на простые множители.
Алгоритм Евклида «с вычитанием». 
Алгоритм Евклида «с делением». 
Бинарный алгоритм Евклида.
Алгоритм Евклида для n чисел.
Временная сложность алгоритма. 
Обратная задача.
Упражнения. 
1.5. Расширенный алгоритм Евклида.
Первый вопрос.
Второй вопрос. 
Расширенный итеративный алгоритм Евклида.
Расширенный рекурсивный алгоритм Евклида.
Третий вопрос. 
Четвертый вопрос.
Упражнения. 
1.6. Алгоритмы возведения в степень.
Упражнения. 
1.7. Модулярная арифметика.
1.7.1. Элементы теории сравнений. 
Определение и свойства сравнений.
Функция Эйлера.
Система вычетов. 
Теорема Л. Эйлера.
Сравнение первой степени. 
Упражнения.
1.7.2. Китайская теорема об остатках. 
Система из двух сравнений. 
Упражнения.
1.7.3. Алгоритмы модулярной арифметики. 
Упражнения.
1.8. Сравнения второй степени.
Упражнения.
Часть 2. Алгоритмы умножения целых чисел.
2.1. Алгоритм А. А. Карацубы. 
Упражнения.
2.2. Алгоритм А. Тоома и С. Кука. 
Упражнения.
2.3. Дискретное преобразование Ж. Фурье.
Алгоритм умножения. 
Тривиальное решение.
Быстрое дискретное преобразование Ж. Фурье. 
Рекурсивная реализация вычисления FFTn(A). 
Обратное дискретное преобразование Ж. Фурье.
Умножение чисел на основе быстрого преобразования Ж. Фурье. 
Оптимизация алгоритма. 
Упражнения.
2.4. Алгоритм А. Шенхаге и Ф. Штрассена. 
Оценка временной сложности алгоритма Шенхаге–Штрассена. 
Алгоритм Шенхаге–Штрассена. 
Упражнения.
Приложения. 
Приложение 1. Система быстрого счета Я. Трахтенберга.
Упражнения.
Приложение 2. Дерево Штерна–Броко.
О нумерации рациональных чисел. 
Упражнения.
Дерево Штерна–Броко как способ нумерации положительных рациональных чисел. 
Упражнения.
Дерево Штерна–Броко как способ приближения одних рациональных чисел другими. 
Упражнения.
Дерево Штерна–Броко как система счисления для положительных рациональных чисел.
Упражнения.

Купить .





Теги: учебник по программированию :: программирование :: Окулов :: Лялин :: Пестов :: Разова :: алгоритм :: арифметика