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

Серия: "Развитие интеллекта школьников"

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

Содержание:

Введение...... 5 Часть 1. Компьютерная арифметика...... 9 1. 1. Алгоритмы целочисленной арифметики...... 9 Вспомогательные инструменты...... 10 Сложение неотрицательных целых чисел...... 12 Вычитание неотрицательных целых чисел...... 15 Умножение неотрицательных целых чисел...... 18 Деление неотрицательных целых чисел...... 21 Упражнения...... 22 1. 2. Отрицательные целые числа...... 24 Алгоритм умножения для знаковых чисел в дополнительном коде...... 27 Алгоритм А. Бута...... 30 Упражнения...... 33 1. 3. Алгоритмы арифметики вещественных чисел...... 34 Упражнения...... 48 1. 4. Алгоритм Евклида...... 49 Переборный алгоритм...... 50 Алгоритм, использующий разложение числа на простые множители...... 50 Алгоритм Евклида «c вычитанием»...... 54 Алгоритм Евклида «с делением»...... 56 Бинарный алгоритм Евклида...... 57 Алгоритм Евклида для n чисел...... 59 Временн&# 225;я сложность алгоритма...... 60 Обратная задача...... 62 Упражнения...... 62 1. 5. Расширенный алгоритм Евклида...... 71 Первый вопрос...... 72 Второй вопрос...... 74 Расширенный итеративный алгоритм Евклида...... 74 Расширенный рекурсивный алгоритм Евклида...... 77 Третий вопрос...... 80 Четвертый вопрос...... 82 Упражнения...... 86 1. 6. Алгоритмы возведения в степень...... 102 Упражнения...... 110 1. 7. Модулярная арифметика...... 113 1. 7. 1. Элементы теории сравнений...... 113 Определение и свойства сравнений...... 113 Функция Эйлера...... 115 Система вычетов...... 118 Теорема Л. Эйлера...... 125 Сравнение первой степени...... 126 Упражнения...... 128 1. 7. 2. Китайская теорема об остатках...... 130 Система из двух сравнений...... 131 Упражнения...... 146 1. 7. 3. Алгоритмы модулярной арифметики...... 150 Упражнения...... 156 1. 8. Сравнения второй степени...... 157 Упражнения...... 165 Часть 2. Алгоритмы умножения целых чисел...... 167 2. 1. Алгоритм А. А. Карацубы...... 167 Упражнения...... 173 2. 2. Алгоритм А. Тоома и С. Кука...... 176 Упражнения...... 185 2. 3. Дискретное преобразование Ж. Фурье...... 186 Алгоритм умножения...... 187 Тривиальное решение...... 189 Быстрое дискретное преобразование Ж. Фурье...... 189 Рекурсивная реализация вычисления FFT_n(A)...... 194 Обратное дискретное преобразование Ж. Фурье...... 196 Умножение чисел на основе быстрого преобразования Ж. Фурье...... 201 Оптимизация алгоритма...... 203 Упражнения...... 211 2. 4. Алгоритм А. Шенхаге и Ф. Штрассена...... 215 Оценка временн&# 243;й сложности алгоритма Шенхаге–Штрассена...... 220 Алгоритм Шенхаге–Штрассена...... 221 Упражнения...... 224 Приложения...... 225 Приложение 1. Система быстрого счета Я. Трахтенберга...... 225 Упражнения...... 238 Приложение 2. Дерево Штерна–Броко...... 240 О нумерации рациональных чисел...... 240 Упражнения...... 244 Дерево Штерна–Броко как способ нумерации положительных рациональных чисел...... 252 Упражнения...... 261 Дерево Штерна–Броко как способ приближения одних рациональных чисел другими...... 271 Упражнения...... 276 Дерево Штерна–Броко как система счисления для положительных рациональных чисел...... 277 Упражнения...... 282

Издательство: "БИНОМ. Лаборатория знаний" (2015)

ISBN: 9785996323630