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

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




Дерево Штерна-Броко.
Дерево Штерна-Броко впервые появилось в работах немецкого математика Мориса Штерна (1858 г.) и французского часовщика Ахилла Броко (1860 г.). Считается, что они открыли его независимо друг от друга, — отсюда и название.

Рассмотрим дерево Штерна-Броко:
1) как способ выписать или пронумеровать все положительные рациональные числа: именно это интересовало Штерна — его исследование было чисто теоретическим, в нем приводились теоремы и доказательства;
2) как способ приближения одних рациональных чисел другими: об этом говорил Броко — его статья носила практический характер, в ней давались советы по выбору шестеренок для часовых механизмов;
3) как систему счисления для положительных рациональных чисел: она вполне могла бы использоваться в компьютерах, но, к сожалению, для выполнения в ней арифметических операций нет быстрых алгоритмов.

ОГЛАВЛЕНИЕ.
Введение. 
Часть 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. Дерево Штерна–Броко.
О нумерации рациональных чисел. 
Упражнения.
Дерево Штерна–Броко как способ нумерации положительных рациональных чисел. 
Упражнения.
Дерево Штерна–Броко как способ приближения одних рациональных чисел другими. 
Упражнения.
Дерево Штерна–Броко как система счисления для положительных рациональных чисел.
Упражнения.

Купить .








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