В третьем издании второго тома представлено полное введение в теорию получисленных алгоритмов, причем случайным числам и арифметике посвящены отдельные главы. В книге даны основы теории получисленных алгоритмов, а также примеры этих алгоритмов. Тем самым установлено прочное связующее звено между компьютерным программированием и численным анализом. Особого упоминания заслуживают предложенная Кнутом в настоящем издании новая трактовка генераторов случайных чисел, а также рассмотрение способов вычислений с помощью формальных степенных рядов.
ОГЛАВЛЕНИЕ
ГЛАВА 3. СЛУЧАЙНЫЕ ЧИСЛА ....................
3.1. ВВЕДЕНИЕ .............................
3.2. ГЕНЕРИРОВАНИЕ РАВНОМЕРНО РАСПРЕДЕЛЕННЫХ СЛУЧАЙНЫХ ЧИСЕЛ .................................
3.2.1. Линейный конгруэнтный метод ..................
3.2.1.1. Выбор модуля ......................
3.2.1.2. Выбор множителя ....................
3.2.1.3. Потенциал .......................
3.2.2. Другие методы .........................
3.3. СТАТИСТИЧЕСКИЕ КРИТЕРИИ ...................
3.3.1. Основные критерии проверки случайных наблюдений ........
3.3.2. Эмпирические критерии .....................
*3.3.3. Теоретические критерии .....................
3.3.4. Спектральный критерий .....................
3.4. ДРУГИЕ ВИДЫ СЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ......
3.4.1. Численные распределения ....................
3.4.2. Случайные выборки и перемешивания ...............
*3.5. ЧТО ТАКОЕ СЛУЧАЙНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ ........
3.6. ВЫВОДЫ ...............................
ГЛАВА 4. АРИФМЕТИКА .......................
4.1. ПОЗИЦИОННЫЕ СИСТЕМЫ СЧИСЛЕНИЯ ..............
4.2. АРИФМЕТИКА ЧИСЕЛ С ПЛАВАЮЩЕЙ ТОЧКОЙ ..........
4.2.1. Вычисления с однократной точностью ...............
4.2.2. Точность арифметических операций с плавающей точкой ......
*4.2.3. Вычисления с удвоенной точностью ................
4.2.4. Распределение чисел в формате с плавающей точкой ........
4.3. АРИФМЕТИКА МНОГОКРАТНОЙ ТОЧНОСТИ ............
4.3.1. Классические алгоритмы .....................
*4.3.2. Модулярная арифметика .....................
*4.3.3. Насколько быстро можно выполнять умножение ..........
4.4. ПРЕОБРАЗОВАНИЕ ИЗ ОДНОЙ СИСТЕМЫ СЧИСЛЕНИЯ В ДРУГУЮ
4.5. АРИФМЕТИКА РАЦИОНАЛЬНЫХ ЧИСЕЛ ..............
4.5.1. Дроби .............................
4.5.2. Наибольший общий делитель ...................
*4.5.3. Анализ алгоритма Евклида .....................
4.5.4. Разложение на простые множители .................
4.6. ПОЛИНОМИАЛЬНАЯ АРИФМЕТИКА .................
4.6.1. Деление полиномов ........................
*4.6.2. Разложение полиномов на множители ................
4.6.3. Вычисление степеней ........................
4.6.4. Вычисление полиномов .......................
*4.7. ОПЕРАЦИИ СО СТЕПЕННЫМИ РЯДАМИ ................
ОТВЕТЫ К УПРАЖНЕНИЯМ ......................
ПРИЛОЖЕНИЕ А. ТАБЛИЦЫ ЗНАЧЕНИЙ НЕКОТОРЫХ КОНСТАНТ
A.I. Основные константы (десятичные) ..................
А.2. Основные константы (восьмеричные) .................
А.З. Гармонические числа, числа Бернулли, числа Фибоначчи .......
ПРИЛОЖЕНИЕ Б. ОСНОВНЫЕ ОБОЗНАЧЕНИЯ ............
ПРЕДМЕТНОИМЕННОЙ УКАЗАТЕЛЬ
Эта книга, автором которой является опытный преподаватель информатики, представляет собой один из лучших учебников, посвященных алгоритмам. Делая основной упор на понимание идей, а не на механическое рассмотрение работы того или иного алгоритма, автор излагает ключевые принципы и методы разработки алгоритмов так, что они могут быть применены как универсальный инструментарий для широкого диапазона задач, а не только для разработки алгоритмов. Несмотря на отсутствие громоздких математических доказательств, в книге выдержана достаточная математическая строгость.
В этой книге подробно рассмотрены структуры данных и алгоритмы, которые являются фундаментом современной методологии разработки программ. Показаны разнообразные реализации абстрактных типов данных, начиная от стандартных списков, стеков, очередей и заканчивая множествами и отображениями, которые используются для неформального описания и реализации алгоритмов.
