Книга доступна студентам первого курса. Она нужна каждому, кто хочет научиться программировать.
ПРЕДИСЛОВИЕ РЕДАКТОРОВ ПЕРЕВОДА
Предлагаемая читателю книга является первым томом многотомной монографии, охватывающей почти весь спектр вопросов программирования на ЭВМ.. Три тома из семи запланированных автором уже опубликованы в США, и сейчас нет сомнения, что эта монография представляет собой совершенно незаурядное явление.
Беспрецедентна сама по себе попытка изложить вопрос в такой полноте и таком объеме с единой точки зрения и в единой терминологии, вместе с необходимыми разделами чистой (главным образом дискретной) математики. Более того, автор ставит своей целью . не просто полноту изложения, его цель много сложнее — научить читателя искусству программирования, т. е. научить его правильно, рационально мыслить об алгоритмах и программах, не привязываясь при этом к той или иной конкретной машине и в то же время постоянно сохраняя связь с машиной. С нашей точки зрения, автор успешно справился со своей задачей.
Первый том носит название «Основные алгоритмы». Выделение и кристаллизация концепции алгоритма явились выдающимся достижением математики 20-го века. Это позволило решить вопрос о разрешимости или неразрешимости целого ряда проблем из алгебры, теории чисел, геометрии и других разделов математики. Возникнув из внутренних потребностей самой математики, теория алгоритмов получила обширнейшее поле деятельности в связи с развитием ЭВМ. Именно в последние несколько десятилетий создано и изучено огромное количество конкретных алгоритмов. Сюда прежде всего относятся алгоритмы для численного решения задач физики, механики, экономики и т. п. Кроме того имеется большая семья алгоритмов, применяемых для решения нечисловых задач и в частности задач, возникающих в связи с организацией работы самих ЭВМ, Это действительно основные алгоритмы, которые составляют колоссальное научное богатство, так сказать, материальную силу, прикладной математики. Каждый такой алгоритм является орудием, которое можно многократно использовать, и поэтому существенны вопросы о выработке критериев оценки алгоритмов и способов их анализа.
К ^сожалению, достаточно развитая теория алгоритмов теоретической математики и практическая ^деятельность по конструированию и исследованию алгоритмов для ЭВМ в настоящее время свя-
Предисловие редакторов перевода
заны весьма слабо, Het сомнения, что связь эта будет расти и крепнуть, и в результате образуется ряд замечательных теорий.
Книга-Кнута является первым существенным шагом в этом отношении. Она посвящена анализу наиболее фундаментальных нечисловых алгоритмов.
Понятия и алгоритмы, описанные в первом томе,— это те понятия и алгоритмы, которыми должен владеть каждый программист. В частности это алгоритмы работы с различными информационными структурами (массивами, списками, деревьями и т. п.), алгоритмы динамического распределения памяти, сборка мусора и т. д. Автор неизменно сопровождает алгоритмы оценками их эффективности, а достаточно подробное изложение необходимых для этого сведений из теоретической математики придает книге полную самостоятельность.
Приводимые алгоритмы автор записывает некоторым полуформальным способом, достаточно удобным как для анализа, так и для восприятия человеком. В то же время программы, реализующие эти алгоритмы, он записывает на машинно-ориентированном1 языке — автокоде для некоторой гипотетической машины MIX—и тем самым получает возможность оценить качество алгоритмов также и с точки зрения их машинной реализации, ~~
Узнав о планирующемся переводе книги на русский язык, автор предупреждал нас о трудностях, с которыми столкнутся переводчики. Он не ошибся. Обилие сообщаемых, сведений, большое количество" понятий и терминов, огромное число задач, в которых пришлось детально разбираться,—все это, помноженное на красочность языка автора, доставило переводчикам изрядно хлопот. Тем не менее мы надеемся, что перевод не испортил оригинал безнадежно.
Перевод выполнен с первого издания (совсем недавно вышло 2-е издание 1-го тома). Автор любезно сообщил значительное число исправлений к первоначальному тексту, которые учтены в переводе. Мы выражаем ему свою глубокую признательность.
Предисловие автора, разделы 1.1, 1.2, 1.3.3 и 2.3 (включая ответы на задачи из этих разделов) переведены Г, П. Бабенко, остальные разделы •— Ю. М. Банковским.
К. И. Бабенко В. С. Штаркман
ПРЕДИСЛОВИЕ
К РУССКОМУ ИЗДАНИЮ
Мне очень приятно, что эта книга издается на русском языке, и я надеюсь, что она доставит тем,- кто изучает науку программирования в Советском Союзе, такое же удовольствие, с каким я читаю русскую литературу в английском переводе. Предлагаемый текст представляет собой исправленную версию оригинального американского издания, впервые опубликованного в 1968 г. Полагаю, что исправления в достаточной мере обновили материал. Многие американские идиомы было весьма трудно передать равноценным образом по-русски, и я хочу поблагодарить переводчиков и редакторов за тщательность их труда.
Стэнфорд, Калифорния 20 февраля 1974
Дональд Э. Кнут
ОГЛАВЛЕНИЕ
Предисловие редакторов перевода .................. 5
Предисловие ......... ................... -8
Процедура чтения книг этой серии ............. -....» -Щ
Замечания об упражнениях ................... -.. , 20
Глава 1. | Основные понятия
1.1. Алгоритмы ................ ....... . , -4J5
L.2. Математическое введение ...... . . . . . ...... . . ддр-
1.2.1. Математическая индукция ............... 38
1.2.2. Числа, степени и логарифмы .............. 5J0H
.2.3. Суммы и произведения ................ . 57
.2.4. Целочисленные функции и элементарная теория чисел ... ' Ш
.2.5. Перестановки и факториалы .............. JS
.2.6. Биномиальные коэффициенты ............ . 83
.2.7. Гармонические числа ................. 107
.2.8. Числа Фибоначчи ................ . . 112
.2.9. Производящие функции ................ 120
1.2.10. Анализ алгоритма .................. 129
* 1.2. 11. Асимптотические представления . . ". ......... 140
1.2.11.1. Символ О ............ ...... 140
1.2.11.2. Формула суммирования Эйлера ........ 144
1.2.11.3. Некоторые приложения ........... 150
1.3. MIX ................. . . ......... 159
.3.1. Описание MIX ................... ... 159
.3.2. Автокод машины MIX .............. ... 184
.3.3. Применение к перестановкам .............. 206
1.4. Некоторые основные методы программирования ........ . 233
.4.1. Подпрограммы .... ........... ..... 233
.4.2. Сопрограммы ..................... 242
1.4.3. Интерпретирующие программы ....... ...... 251
1.4.3.1. MIX-имитатор ................. . 253
* 1.4. 3.2. Программы трассировки ............ 266
1.4.4. Ввод и вывод .................... • 269
1.4.5. История и библиография ............ ...... 286-
Глава 2. \ Информационные структуры
2.1. Введение .
2.2. Линейные списки
2.2.1. Стеки, очереди и деки
2.2.2. Последовательное распределение
2.2.3. Связанное распределение
2.2.4. Циклические списки
2.2.5. Списки с двумя связями
2.2.6. Массивы и ортогональные списки
2.3. Деревья .
734
Оглавление
2.3.1. Прохождение бинарных деревьев............ 394
2.3.2. Представление деревьев в виде бинарных деревьев .... 414
2.3.3. Другие представления деревьев............. 432
2.3.4. Основные математические свойства деревьев....... 449
2.3.4.1. Свободные деревья............... 449
2.3.4.2. Ориентированные деревья ........... 460
2.3.4.3. "Лемма о бесконечном дереве"......... 472
2.3.4.4. Перечисление деревьев ............. 477
2.3.4.5. Длина пути .................. 491
2.3.4.6. История и библиография............ 498
2.3.5. Списки и сбор мусора................ . 500
2.4. Структуры со многими связями................ 519
2.5. Динамическое"" распределение памяти ............. 533
2.6. История и библиография................... 558
Ответы к упражнениям ....................... 568
Приложение А. Указатель обозначений................ 712
Приложение В. Таблицы числовых величин.............. 717
Именной указатель......................... 721
Предметный указатель........................ 725
Глоссарий............................... 730
Цена: 300руб.
