Искусство программирования, том 1. Основные алгоритмы

— Профессор Ю. В. Козаченко

ПРЕДИСЛОВИЕ

Уважаемые читатели! Вы держите в руках книгу,

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

Теперь без тени сомнения мы можем сказать, что если вы будете следовать инструкциям, то каждое блюдо будет получаться у вас таким же, как и у нас, даже если раньше вы никогда не занимались приготовлением пищи.
— Поваренная книга Мак-Колла (1963)

ПРОЦЕСС подготовки программ для цифрового компьютера—это очень увлекательное занятие. И дело не только в том, что оно оправдывает себя с экономической и научной точек зрения; оно может вызвать также эстетические переживания, подобные тем, которые испытывают творческие личности при написании музыки или стихов. Вы держите в руках первый том многотомного издания, цель которого—дать читателю разнообразные знания и умения, из которых и состоит ремесло программиста.

Последующие главы не являются введением в компьютерное программирование; предполагается, что вы уже имеете некоторый опыт в этой области. На самом деле предъявляемые к читателю требования очень просты; тем не менее начинающему программисту потребуются время и практика, чтобы понять, что собой представляет цифровой компьютер. Итак, читатель должен иметь:

a) некоторое представление о том, как работает цифровой компьютер с хранимой программой; при этом необязательно разбираться в электронике, главное— понимать, каким образом команды можно сохранять в памяти компьютера, и затем последовательно их выполнять;

b) способность ставить задачу с помощью четких и определенных терминов, понятных компьютеру (у компьютеров нет разума, присущего человеку, поэтому они делают в точности то, что им приказывают, не больше и не меньше; именно этот факт обычно труднее всего уяснить начинающим пользователям);

c) знание самых простых компьютерных методов, таких как организация циклов (повторное выполнение некоторого набора команд), а также использование подпрограмм и переменных с индексами;

d) знание распространенных компьютерных терминов, например "память", "регистры", "биты", "плавающая точка", "переполнение", "программное обеспечение"; большинство терминов, которые не определены в тексте, поясняются в алфавитном указателе в конце каждого тома.

Эти четыре условия, вероятно, можно объединить в одном требовании: читатель должен иметь опыт написания и отладки по меньшей мере четырех программ хотя бы для одного компьютера.

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

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

Тему этих книг можно сформулировать следующим образом: "Нечисленный анализ". Компьютеры обычно ассоциируются с решением численных задач, таких как нахождение корней уравнения, численное интерполирование, интегрирование и т. д. Но в этом трехтомнике подобные темы не рассматриваются (за исключением случаев, когда это необходимо сделать по ходу изложения). Численное компьютерное программирование—необычайно интересная и бурно развивающаяся область;

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

Результаты исследований в области нечисленного анализа разбросаны по многим техническим журналам. Моя цель состояла в том, чтобы извлечь из этого огромного объема информации только фундаментальные методы, которые можно применять в разнотипных ситуациях программирования. Я попытался обобщить выбранную информацию, чтобы получить то, что в большей или меньшей степени можно назвать "теорией", а также показать, как применять эту теорию при решении различных практических задач.

Конечно, "нечисленный анализ" —крайне неудачное название для данной области науки. Оно неудачно прежде всего потому, что содержит только отрицание другого понятия; гораздо лучше было бы выбрать более содержательный термин, не имеющий приставки "не". Название "обработка информации" охватывает более широкую область, чем рассматриваемый здесь материал, а "методы программирования" —более узкую. Я считаю, что для темы, освещаемой в данных книгах, самым подходящим является название анализ алгоритмов, которое можно расшифровать как "теория свойств некоторых компьютерных алгоритмов".

Полный набор книг, озаглавленный как Искусство программирования, имеет следующую основную структуру.

Том 1. Основные алгоритмы

Глава 1. Основные понятия Глава 2. Информационные структуры

Том 2. Получисленные алгоритмы

Глава 3. Случайные числа Глава 4. Арифметика

Том 3. Сортировка и поиск

Глава 5. Сортировка Глава 6. Поиск

Том 4. Комбинаторные алгоритмы

Глава 7. Комбинаторный поиск Глава 8. Рекурсия

Том 5. Синтаксические алгоритмы

Глава 9. Лексикографический поиск Глава 10. Синтаксический анализ

В томе 4 рассматривается очень большая тема, поэтому на самом деле он состоит из трех отдельных книг (томов 4А, 4В и 4С). Планируется также выпуск двух дополнительных томов по более специализированным темам: том 6, Теория языков (глава 11), и том 7, Компиляторы (глава 12).

Я приступил к этой работе в 1962 году с намерением написать единственную книгу, содержащую все перечисленные главы, но вскоре понял, что необходимо глубоко рассматривать выбранные темы, а не просто "скользить по поверхности". В результате получился текст такого объема, что материала каждой главы оказалось более чем достаточно для изучения в течение одного университетского семестра. И стало ясно, что необходимо разбить материал на несколько отдельных томов. Я знаю, что книга, содержащая только одну-две главы, выглядит довольно странно, но решил сохранить первоначальную нумерацию глав, чтобы упростить перекрестные ссылки. Планируется выпуск сокращенного варианта томов 1-5, который будет служить более общим справочником и/или учебником для студентов; в нем будет содержаться основная часть материала данных томов, а более специальная информация будет опущена. В сокращенном издании будет сохранена такая же нумерация глав, как и в полном.

Том 1 можно рассматривать как "пересечение" полного набора глав, в том смысле, что он содержит основные сведения, которые используются во всех остальных книгах. С другой стороны, тома 2-5 можно читать независимо один от другого. Том 1—это не только справочник, который необходимо использовать как пособие при чтении других томов; он может служить также университетским учебником либо пособием для самообразования по теме структуры данных (основное внимание следует уделить главе 2) или дискретная математика (основное внимание следует уделить разделам 1.1, 1.2, 1.3.3 и 2.3.4), или программирование на языке машинных команд (основное внимание следует уделить разделам 1.3 и 1.4).

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

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

Теперь несколько слов о математическом содержании данного многотомного издания. Материал излагается так, что он вполне доступен даже лицам со средним образованием; более сложные фрагменты они смогут просмотреть или просто опустить. В то же время те, кто имеют склонность к математике, смогут изучить интересные математические методы, связанные с дискретной математикой. Подобная двойственность представления информации была достигнута, с одной стороны, за счет присвоения рейтинга каждому упражнению (чтобы читатель смог отличать сложные с математической точки зрения упражнения от простых), а с другой стороны, благодаря такой организации разделов, при которой главные математические результаты сформулированы перед доказательствами. Доказательства предлагается либо провести самостоятельно в качестве упражнений (ответы па которые приводятся в отдельном разделе), либо найти в конце раздела.

Читатель, который, главным образом, интересуется программированием, а не математикой, может прекратить чтение раздела, как только математический материал станет слишком сложным для восприятия. С другой стороны, читатель-математик найдет для себя очень много интереснейших фактов. Многие математические публикации на тему программирования были ошибочными, поэтому одна из целей данной книги—предоставить читателю правильное математическое обоснование предмета изложения. И так как я считаю себя математиком, моя прямая обязанность—правильно (насколько смогу) изложить материал с математической точки зрения.

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

Самое сложное решение, которое мне пришлось принять при подготовке этих книг, касалось способа представления различных методов. Преимущества блок-схем и пошаговых описаний алгоритмов хорошо известны; эти вопросы обсуждаются в статье "Computer-Drawn Flowcharts" в журнале АСМ Communications, Vol. 6 (September 1963), pages 555-563. Для описания любого компьютерного алгоритма необходим также формальный и точный язык. Поэтому мне нужно было решить, какой язык использовать: алгебраический, такой как ALGOL или FORTRAN, либо машинно-ориентированный. Вероятно, многие сегодняшние компьютерные специалисты не согласятся с моим решением использовать машинно-ориентированный язык, но я убедился, что это был правильный выбор. На то существуют следующие причины.

a) На программиста большое влияние оказывает язык, на котором написаны программы. В настоящее время превалирует тенденция к выбору самых простых, а не самых оптимальных для компьютера конструкций языка. А программист, который знает машинно-ориентированный язык, стремится использовать более эффективные методы и таким образом создает более совершенные программы.

b) Все нужные нам программы, написанные на машинно-ориентированном языке, за редким исключением будут иметь небольшой размер. А это значит, что при наличии компьютера, обладающего минимальной вычислительной мощностью, проблем с использованием таких программ у нас не возникнет.

c) Языки высокого уровня не подходят для обсуждения важных деталей, имеющих отношение к низкому уровню, таких как связь сопрограмм, генерирование случайных чисел, арифметика высокой точности и многие другие проблемы, связанные с эффективным использованием памяти.

d) Тот, кто серьезно интересуется компьютерами, должен хорошо знать машинный язык, так как он лежит в основе работы компьютера.

e) Некоторое знание машинного языка необходимо в любом случае, чтобы разобраться в выходных данных программ, приведенных во многих примерах.

f) Новые алгебраические языки входят и выходят из моды приблизительно каждые пять лет, в то время как я пытаюсь говорить о "вечных истинах".

С другой стороны, я признаю, что писать программы на языках высокого уровня и отлаживать эти программы значительно проще. В сущности, начиная с 1970 года, я сам редко использовал машинный язык низкого уровня для собственных программ, так как современные компьютеры обладают большим объемом памяти и высоким быстродействием. Но для решения многих проблем, рассматриваемых в данной книге, наибольшее значение имеет искусство программирования. Например, некоторые комбинаторные вычисления нужно повторять триллионы раз, и мы сэкономим приблизительно 11,6 дней работы за счет того, что сократим время вычислений во внутреннем цикле всего на одну микросекунду. Аналогично имеет смысл приложить дополнительные усилия для написания программы, которая будет использоваться много раз в течение каждого дня на множестве компьютеров, тем более что написать эту программу нужно только один раз.

А если принять решение использовать машинно-ориентированный язык, то какому языку следует отдать предпочтение? Я мог бы выбрать язык для конкретной машины X, но тогда те, кто используют другой компьютер, подумают, что данная книга написана только в расчете на обладателей компьютера X. Более того, машина X, вероятно, имеет много характерных особенностей, для которых совершенно неприменим материал данной книги, но все же его необходимо изложить. И наконец, через два года фирма—производитель машины Х выпустит машину Х+1 или 10Х, и компьютер Х больше никого не будет интересовать.

Чтобы решить эту проблему, я попытался разработать "идеальный" компьютер с очень простыми правилами работы (изучить которые можно, скажем, всего за час) и очень похожий на реальные машины. Для студента нет никакой причины избегать изучения характеристик различных компьютеров; после изучения одного языка все остальные будут усваиваться гораздо легче. Кроме того, серьезный программист должен быть готов к тому, что в ходе работы ему придется сталкиваться с различными машинными языками. Поэтому остается только один недостаток использования вымышленной машины—сложность запуска написанных для нее программ. К счастью, на самом деле это не проблема, так как много добровольцев предложили свои услуги по написанию имитаторов гипотетической машины. Такие имитаторы идеальны для учебных целей, и работать с ними даже проще, чем с реальным компьютером.

Я старался ссылаться на самые лучшие старые статьи по каждой теме, а также упоминать новые работы. Ссылаясь на литературные источники, я использовал стандартные сокращения для названий периодических изданий, за исключением наиболее часто цитируемых журналов, для которых применялись следующие сокращения.

САСМ — Communications of the Association for Computing Machinery

JACM — Journal of the Association for Computing Machinery

Сотр. J. — The Computer Journal (British Computer Society)

Math. Сотр. — Mathematics of Computation

AMM — American Mathematical Monthly

SICOMP — SIAM Journal on Computing

FOCS — IEEE Symposium on Foundations of Computer Science

SODA — ACM-SIAM Symposium on Discrete Algorithms

STOC — ACM Symposium on Theory of Computing

Crelle — Journal fur die reine und angewandte Mathematik

Например, "САСМ 6 (1963), 555-563" означает ссылку на журнал, упомянутый в одном из предыдущих абзацев этого предисловия. Сокращение "CMatA" я использовал также для обозначения книги Конкретная математика, на которую есть ссылка во введении к разделу 1.2.

Большая часть технического материала этих книг приходится на упражнения. Если идея нетривиального упражнения принадлежала не мне, то я старался упомянуть ее автора. Ссылки на литературу обычно даются в тексте раздела либо в ответе к упражнению. Но во многих случаях в основе упражнений лежат неопубликованные материалы, на которые нельзя дать ссылки.

В течение долгих лет работы над этими книгами мне помогали многие люди, которым я благодарен от всей души. Прежде всего, я хочу выразить благодарность моей жене Джилл ) за ее бесконечное терпение, за подготовку некоторых иллюстраций и за постоянную помощь во всем. Я признателен также Роберту В. Флойду (Floyd Robert W.) за то, что в 60-х годах он посвятил столько времени работе над улучшением и углублением данного материала. Тысячи других людей также оказали мне неоценимую помощь. Чтобы просто перечислить их имена, понадобилась бы еще одна такая книга! Многие из них любезно разрешили мне использовать их старые неопубликованные работы. Мои исследования в Калифорнийском технологическом институте и Станфордском университете щедро финансировались Национальным научным фондом (National Science Foundation) и департаментом морских исследований (Office of Naval Research). Издательство Addison-Wesley всегда оказывало мне всемерную помощь и поддержку с того самого времени, когда в 1962 году я приступил к работе над проектом. Мне кажется, что для всех этих людей лучшая благодарность—данная публикация. Она показывает, что их вклад привел к появлению книг, в которых, я надеюсь, мне удалось написать то, чего они ожидали.

Предисловие к третьему изданию

Потратив десять лет на разработку систем компьютерного набора METAFONT и TEX, я теперь могу осуществить свою мечту—применить эти системы для набора книги Искусство программирования. Наконец-то мне удалось внести полный текст этой книги в персональный компьютер и таким образом получить ее электронную версию, что позволит в дальнейшем вносить любые изменения в технологию печати и отображения на экране. Такой способ работы дал мне возможность сделать буквально тысячи улучшений; я добился того, о чем так долго мечтал.

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

Таким образом, работа над книгой "Искусство программирования" продолжается. Именно поэтому некоторые части данной книги начинаются пиктограммой "В процессе построения" (это своеобразное извинение за то, что приведены не самые новые данные). Мои папки переполнены важными материалами, которые я планирую включить в окончательное, славное четвертое издание тома 1; оно выйдет, вероятно, через 15 лет. Но сначала я должен закончить тома 4 и 5. Я хочу, чтобы они были опубликованы сразу же, как только будут готовы к печати.

Большая часть тяжелой работы по подготовке этого нового издания была выполнена Филлис Винклер (Phyllis Winkler) и Сильвио Леви (Silvio Levy), которые профессионально набирали и редактировали текст второго издания, а также Джеффри Олдхэмом (Jeffrey Oldham), который конвертировал почти все оригинальные иллюстрации в формат METAP0ST. Я исправил все ошибки, которые бдительные читатели (Бэрри) обнаружили во втором издании (а также ошибки, которые, увы, не заметил никто), и постарался избежать появления новых ошибок в новом материале. Тем не менее я допускаю, что некоторые огрехи все же остались, и хотел бы исправить их как можно скорее. Поэтому за каждую опечатку*, а также ошибку, относящуюся к сути излагаемого материала или к приведенным историческим сведениям, я охотно заплачу $2,56 тому, кто первым ее найдет. На Web-странице, адрес которой приведен на обороте титульной страницы, содержится текущий список всех ошибок, о которых мне сообщили**.

* Имеется в виду оригинал настоящего издания. — Прим. ред.
** Ошибки, известные на момент подготовки русского издания, были исправлены. —Прим. ред.

D. Е. К.
Станфорд, Калифорния
Апрель 1997

За последние двадцать лет мир изменился.
— Билл Гейтс (Bill Gates) (1995)

ОГЛАВЛЕНИЕ

ГЛАВА 1. ОСНОВНЫЕ ПОНЯТИЯ ................................................ 27
    1.1. АЛГОРИТМЫ ....................................................... 27
    1.2. МАТЕМАТИЧЕСКОЕ ВВЕДЕНИЕ ......................................... 37
        1.2.1. Математическая индукция ................................... 38
        1.2.2. Числа, степени и логарифмы ................................ 49
        1.2.3. Суммы и произведения ...................................... 56
        1.2.4. Целочисленные функции и элементарная теория чисел ......... 68
        1.2.5. Перестановки и факториалы ................................. 75
        1.2.6. Биномиальные коэффициенты ................................. 82
        1.2.7. Гармонические числа ....................................... 105
        1.2.8. Числа Фибоначчи ........................................... 109
        1.2.9. Производящие функции ...................................... 118
        1.2.10. Анализ алгоритма ......................................... 127
        *1.2.11. Асимптотические представления ........................... 138
            *1.2.11.1. Символ О .......................................... 138
            *1.2.11.2. Формула суммирования Эйлера ....................... 143
            *1.2.11.3. Применение асимптотических формул ................. 148
    1.3. MIX ............................................................. 156
        1.3.1. Описание MIX .............................................. 156
        1.3.2. Язык ассемблера компьютера MIX ............................ 178
        1.3.3. Применение к перестановкам ................................ 198
    1.4. НЕКОТОРЫЕ ФУНДАМЕНТАЛЬНЫЕ МЕТОДЫ ПРОГРАММИРОВАНИЯ ............... 221
       1.4.1. Подпрограммы ............................................... 221
       1.4.2. Сопрограммы ................................................ 229
       1.4.3. Программы-интерпретаторы ................................... 237
           1.4.3.1. Имитатор MIX ......................................... 239
           *1.4.3.2. Программы трассировки ............................... 248
       1.4.4. Ввод и вывод ............................................... 251
       1.4.5. История и библиография ..................................... 266

ГЛАВА 2. ИНФОРМАЦИОННЫЕ СТРУКТУРЫ ........................................ 271
       2.1. ВВЕДЕНИЕ ..................................................... 271
       2.2. ЛИНЕЙНЫЕ СПИСКИ .............................................. 277
           2.2.1. Стеки, очереди и деки .................................. 277
           2.2.2. Последовательное распределение ......................... 283
           2.2.3. Связанное распределение ................................ 295
           2.2.4. Циклические списки ..................................... 315
           2.2.5. Дважды связанные списки ................................ 322
           2.2.6. Массивы и ортогональные списки ......................... 341
       2.3. ДЕРЕВЬЯ ...................................................... 352
           2.3.1. Обход бинарных деревьев ................................ 362
           2.3.2. Представление деревьев в виде бинарных деревьев ........ 380
           2.3.3. Другие представления деревьев .......................... 395
           2.3.4. Основные математические свойства деревьев .............. 410
               2.3.4.1. Свободные деревья ................................ 410
               2.3.4.2. Ориентированные деревья .......................... 420
               *2.3.4.3. Лемма о бесконечном дереве ...................... 431
               *2.3.4.4. Перечисление деревьев ........................... 435
               2.3.4.5. Длина пути ....................................... 449
               *2.3.4.6. История и библиография .......................... 456
          2.3.5. Списки и "сборка мусора" ................................ 459
     2.4. МНОГОСВЯЗНЫЕ СТРУКТУРЫ ......................................... 476
     2.5. ДИНАМИЧЕСКОЕ ВЫДЕЛЕНИЕ ПАМЯТИ .................................. 488
     2.6. ИСТОРИЯ И БИБЛИОГРАФИЯ ......................................... 512

ОТВЕТЫ К УПРАЖНЕНИЯМ ..................................................... 521

ПРИЛОЖЕНИЕ А. ТАБЛИЦЫ ЗНАЧЕНИЙ НЕКОТОРЫХ КОНСТАНТ ........................ 683
A.I. Основные константы (десятичные) ..................................... 683
А.2. Основные константы (восьмеричные) ................................... 684
А.З. Значения гармонических чисел, чисел Бернулли и чисел Фибоначчи ...... 685

ПРИЛОЖЕНИЕ Б. ОСНОВНЫЕ ОБОЗНАЧЕНИЯ ....................................... 687

ПРЕДМЕТНО-ИМЕННОЙ УКАЗАТЕЛЬ .............................................. 692

Copyright © 1992-2019 Издательская группа "Диалектика-Вильямс"