Рекурсивный поиск в глубину недавно был использован как основа для ряда эффективных сетевых алгоритмов. Одной из наиболее ранних и основополагающей является статья [88].

3.6. Моделирование

Большие усилия сделаны для развития хороших методов и языков моделирования. Эти усилия полностью оправданы важностью имитационных моделей для практических задач. В дополнение к книге [28] мы рекомендуем [401. Оба труда содержат главы по специальным языкам моделирования. В книге [28] приведена обширная библиография, к которой следует обратиться каждому, кто серьезно интересуется этой темой.

Глава 4. Полный пример

4.1. Алгоритм построения остовного дерева минимального веса

Алгоритм, приведенный в этом разделе, впервые сформулирован в работе [80]. Существует ряд уловок, которыми можно воспользоваться для ускорения этого основного алгоритма, но после этих изменений он все же остается алгоритмом сложности 0{М). Мы предпочли пренебречь этими уловками и избежать ненужных усложнений.

Хорошее вводное обсуждение интерполяции, экстраполяции и приближения данных по методу наименьших квадратов можно найти в книгах [43] и [33].

4.2. Проверка программ

По проверке программ хорошая литература отсутствует. Нетрудно понять, почему дело обстоит так. Опубликованные описания процедур проверки обычно отражают подходы и эмпирические правила, используемые отдельными группами в «реальном мире». В некоторой степени материал этого раздела отражает наши собственные идеи и опыт. По-видимому, пройдет еще некоторое время, прежде чем какой-то конкретный набор процедур проверки станет широко принятым.

Легко читаемое, довольно полное описание проверок на правильность можно найти в книге [92]. В [99] также содержатся полезные советы. Некоторые заботятся о строгих доказательствах правильности программы, но пока что это направление исследований остается довольно бесплодным. (См. несколько ссылок в [99].)

Два простых описания проверки эффективности содержатся в исследованиях [58] и [49]. Программы, строящие профили других программ, обычно велики и сложны. Однако сильный студент может разработать и запрограммировать неплохую программу вычисления профилей (см. [27]).

4.3. Документация и обслуживание

Вопросы документирования программ и их обслуживания освещаются в работах [541, [99], [92], а также [42] и [74].

Глава 5. Алгоритмы вычислительной математики

5.1. Сортировка

Вероятно, алгоритмы сортировки являются наиболее широко изученными алгоритмами во всей машинной математике. Большая часть из того, что известно в этой области, исчерпывающе отражена в третьем томе.труда Кнута [59]. Прекрасной обзорной статьей является [69]. Другие книги в порядке возрастания трудности: [77], [75], [1].

5.2. Поиск

Исчерпьшающее обсуждение машинного поиска можно найти у Кнута [59]. Более элементарный подход содержится в книге [75].

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

Задачи вероятностного поиска требуют для своего решения изощренных математических средств - пример, приведенный в данном разделе, представляет собой редкое исключение. Описание более сложных задач можно найти в работе [18]. Ссылки на оригинальные работы Хафмана и Циммермана можно найти у Кнута [56].

5.3. Арифметические и логические выражения

Дальнейшее обсуждение арифметических выражений можно найти в работах [56], [75] и [95].

5.4. Управление страничной памятью

Есть несколько хороших источников информации по алгоритмам управления страничной памятью, в том числе [4], [19], [11].

Мы смогли только слегка коснуться темы алгоритмов, применяемых в математическом обеспечении ЭВМ (разд. 5.3 и 5.4). Компиляторы и операционные системы конструируются с использованием широкого разнообразия таких алгоритмов. К некоторым из ранее цитированных источников можно обратиться за дополнительными примерами. В их число входят все три тома Кнута [56], [57], [59], а также [47], [8], [77], [75], [11] и [95].

5.5. Параллелизм

Описание машины Иллиак IV приведено в работе [84]. Ссылки на несколько интересных статей о параллельных вычислениях можно

найти в книге [91]. Оказывается, М. Солин так и не опубликовал свой параллельный алгоритм нахождения остовного дерева минимального веса. Мы обнаружили краткое обсуждение в книге [24].

Алгоритм PARSORT взят из статьи [53]. Этот алгоритм обсуждается также в [24].

Глава 6. Математические алгоритмы

6.1. Игры и комбинаторные головоломки

Литература по играм обширна и разнообразна, и мы не сможем осветить ее в достаточной мере. Однако мы предоставим список, которого заинтересованному читателю хватит на годы.

Элементарное, полу историческое введение в магические квадраты можно найти в книге Гарднера [36]. В этой книге цитируется ряд более серьезных источников.

Регулярную колонку Гарднера «Математические игры» в журнале Scientific American не пропускает ни один энтузиаст игр. Он также опубликовал или отредактировал более дюжины книг по математическим играм и головоломкам; например, см. [37].

Игра «нимбы», рассмотренная в этом разделе, была изобретена Джеймсом Байнамом и описана Гарднером в его колонке в феврале 1974 г. Задача о тройной дуэли является классической. Гарднер [36] описывает ее возникновение. Несколько более общую и более серьезную трактовку, чем приведена здесь, можно найти в книге [32].

Существует формальная математическая теория игр, которую мы не рассматривали, поскольку этот предмет заслуживает отдельного курса в большинстве университетов. Следующие книги служат введением на нескольких различных уровнях: [97], [83], [93], [67].

Как и следовало ожидать, много усилий было направлено на анализ серьезных азартных игр. Книги [82] и [23] весьма основательны, хотя и каждая в своем роде.

Энтузиасты компьютерных игр должны обращаться к литературе по искусственному интеллекту, например к книгам [25], [76], а также к книге [86].

В книге [75] также имеется хорошая глава о машинно-ориентирс-ванных играх.

6.2. Кратчайшие пути

Проблема отыскания кратчайших путей в сетях изучалась до оскомины. Из рассмотренных в этом тексте проблем особенно основательно изучена сортировка. (Некоторые темы, как, например, поиск, слишком разнообразны, чтобы их можно было рассматривать как одну проблему.) Книга [62] содержит хорошее обсуждение, гораздо более исчерпывающее, чем то, которое мы привели здесь. Алгоритм Дейкстры впервые был сформулирован в работе [21].