Дональд кнут искусство программирования. Кнут дональд эрвин

«Сейчас предельно ясно, что с той скоростью с которой я пишу, я не закончу весь проект до своего девяностолетия.»

Прочитайте и оцените объем работ. И не торопите дедушку Кнута, он и так старается.

Поддержка публикации - компания Edison , которая разрабатывает корпоративные порталы и приложения для передачи видеороликов .

Volume Three of «The Art of Computer Programming» (48/97)

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

Поэтому после моего приезда в Стэнфорд мне нужно было преподавать и начинать делать совершенно новые вещи, которые я никогда не делал до этого момента. На это ушло какое-то время и я не смог закончить работу над третьей частью книги до моей поездки в Норвегию в 1972, когда у меня был академический отпуск. Вообще-то это не был настоящий академический отпуск, я его только так называю. А на самом деле это был отпуск за свой счет. Я уже три года работал в Стэнфорде и подумал, что это была бы отличная идея.

Профессора обычно работают 6 лет, потом уходят на год в академический отпуск, затем снова 6 лет работы и опять 1 год академического отпуска. Я подумал, что может я выберу 4-х годичный цикл. Я проработаю 3 года, возьму отпуск за свой счет, потом снова 3 года и затем академический отпуск. Правила Стэнфорда не препятствовали такому плану. А я получил приглашение из Университета Норвегии провести там один год в качестве приглашенного профессора и, так как мне не нужна была материальная помощь от Стэнфорда, я мог поехать туда, взяв отпуск за свой счет без всех этих проблем, связанных с оплатами.

И я любил Норвегию - мы посетили ее в 1967, верьте или нет. Это была еще одна из тех вещей, которые случились в 1967! И я влюбился в эту страну и в норвежский национальный гимн - Ja, vi elsker dette landet. Мы любим эту страну.

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

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

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

Working on Volume Four of «The Art of Computer Programming» (49/97)

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

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

Для меня комбинаторный взрыв означал, что исследование комбинаторных методов резко усиливалось. В 1974, 1975 и 1976, когда я работал над четвертой книгой, более чем 50% всех статей во всех технических журналах были о темах, которые описывались в ней. Другими словами это как сидеть на кипящем котле, вы не можете его контролировать. Каждый раз когда я писал что-то на одной неделе, на следующей это уже устаревало.

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

Когда я начал у меня было 30 папок и они были хорошо организованы, затем я создал папки под названиями Х1, Х2, Х3 и так до Х15 - не очень хорошо организованные, но просто расширения системы. А затем появился новый материал и я стал сваливать его в кучу, в надежде что однажды у меня будет время это прочесть. И я так и надеялся… Но эта область растет очень быстро.

Updating Volumes One to Three of «The Art of Computer Programming» (81/97)

Я закончил книгу «3:16», я закончил «Конкретную математику». И я все еще не могу вернуться к «Искусству программирования», потому что у меня все еще есть одно незаконченное дело и это Stanford GraphBase. Это собрание программ грамотности, которые используются для стандартных примеров, которые будут в четвертой части книги «Искусство программирования».

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

Примерно в 1995 году я смог открыть дверь той самой комнаты, куда я бросал все новые материалы для книги в течение 15 лет. Пока я работал над TeX, у меня совсем не было времени думать об этом и когда я получал что-то по почте, относящееся к четвертому, пятому или другим томам книги, я просто отправлял это в кучу, затем у меня появились коробки и еще коробки и в итоге накопилось примерно 17 футов материала в длину.

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

Люди писали мне, сообщая об ошибках в первом, втором и третьем томах. У меня были письма с 1981, 1982 года, на которые я еще не ответил. И я выписал всем этим людям чеки с процентами с того дня. Вы знаете у меня была маленькая программа, которая вычисляла эти проценты и в ней была ошибка, поэтому я думаю, что выплатил чуть больше процентов. Но в любом случае я отослал сотни чеков и получил большой список опечаток для «Искусства компьютерного программирования» для первого, второго и третьего томов, которые я мог набрать с помощью TeX и сделать это правильно.

Все эти годы люди продолжали покупать книги на постоянной основе в книжных магазинах, они покупали издания, который вышел в 70-х годах, но уже в 30-м, в 40-м издании. И каждая из книг до сих пор продается в количестве примерно 4000 книг в год. Вторая часть была издана в 1981 года, та самая, в которой я не мог терпеть цифры, но математический материал был в порядке.

Когда вышла моя серия книг «Компьютеры и верстка», те 5 частей, все было сделано с новыми шрифтами, с соответствующим оформлением. В книге «Конкретная математика» я смог использовать новый шрифт, созданный Herman Zapf, а для книги «3:16» у меня был другой шрифт над которым я работал.

Поэтому в то время оставалась только книга «Искусство компьютерного программирования», в которой было уродливое оформление и все-равно я не хотел его исправлять. У меня заняло так много времени возвращение к написанию четвертой части, как мог я остановиться и переделывать первые три, не подождав еще немного?

На выручку пришел Silvio Levy, который живет в Беркли, который был очень активен во многих математических проектах и сейчас работает библиотекарем в Институте изучения математических наук. Он был большим фанатом TeX и совместно мы создали CWEB - систему грамотного программирования, используя C как язык программирования вместо Pascal.

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

Затем у меня не заняло много времени… я имею ввиду на это ушло 3 или 4 месяца, но это ничто по сравнению с тем, сколько бы у меня ушло времени на эту работу, если бы я все делал один. И в итоге в 1997/1998 у нас было обновленное «Искусство программирования» с подходящей версткой и всеми 20 годами исправлений, которые раньше были в моих файлах, а теперь оказались включенными в текст.

Getting started on Volume Four of «The Art of Computer Programming» (82/97)

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

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

Но также там есть и несколько отличающихся идей… Я не могу удержаться и не выйти за пределы источников, которыми я располагаю, когда я пишу настолько существенную часть книги. Так что сейчас предельно ясно, что с той скоростью с которой я пишу, я не закончу весь проект до своего 90-летия.

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

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

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

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

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

К некоторым из этих материалов нет легкого пути, что-то из него по своей сути трудно, но я почти в восторге от того как все идет. Например сегодня утром я составлял оглавление и я видел те части, написание которых далось мне нелегко. Но сейчас когда они закончены, они смотрятся как отличная история и то, что я мучился с их написанием, уже не кажется мне таким очевидным.

Юрий Романов

10 января 1938 года в Милуоки (штат Висконсин, США) родился Дональд Эрвин Кнут . Сегодня ему исполнилось 76 лет. В биографии его нет длинного перечня названий городов и стран, где он жил и работал. Математик по образованию, в 1960-м окончил Кейсовский технологический институт, через три года в Калифорнийском технологическом институте стал доктором математики, а с 1968 года преподавал в Стэнфордском университете, профессор.

В 1990 году досрочно уходит на пенсию, чтобы полностью посвятить себя главному делу, которое он для себя избрал, - написанию фундаментальной монографии «The Art of Computer Programming», из семи запланированных томов которой свет увидели пока лишь три и первая часть четвёртого.

Сегодня Дональд Кнут является почётным профессором информатики Стэнфорда и ряда университетов разных стран мира, в том числе Санкт-Петербургского. Удостоен премии Ассоциации вычислительной техники имени Грейс Мюррей Хоппер, престижнейшей премии Тьюринга, имеет Национальную медаль США за научные заслуги, является лауреатом премии Харви, премии Киото, премии Института инженеров по электротехнике и электронике, а также премии Математической ассоциации США. Кнут издал 19 монографий и 160 статей.
Является создателем программ для издательской подготовки математических публикаций TEX и METAFONT. В прошлом году занимал 37-е место в списке наиболее цитируемых авторов в области компьютерных наук по версии системы индексирования научных публикаций CiteSeer.

Что интересно при таком обилии официальных знаков признания: отношение к мэтру со стороны представителей математического сообщества и программистов далеко от, казалось бы, ожидаемого – восторженного. Разумеется, в нём нет непочтительности или сомнений в ценности сделанного и значимости заслуг. Но есть нечто от переживаний студентов или даже школьников, которым… слишком много задали на дом. А ведь кроме «своих», айтишников, есть имеются спецы в области патентных прав и участники перманентной «битвы» сторонников проприетарного и свободного ПО, у которых свои резоны соглашаться или не соглашаться с доводами Дональда Кнута… На фоне всей этой бурлящей пестроты слов, взглядов, точек зрения и оценок того, о чем говорит и пишет наш юбиляр, очень хочется задать всего один вопрос. Кто вы, профессор Кнут?

Математик? Книга «Конкретная математика. Основание информатики», написанная в соавторстве Дональдом Кнутом, Рональдом Грэхэмом и Ореном Паташником, как известно, создана на базе одноимённого курса лекций для Стэнфордского университета. Значительная часть её в той или иной мере повторяет содержание главы «Математическое введение» первого тома «Искусства программирования». Слова «конкретная математика» – игра даже не слов, а понятий, которую очень любит профессор Кнут. Это и комбинация КОНтинуальной и дисКРЕТНОЙ математики. Здесь и ненавязчивый посыл в адрес целевой аудитории: это книга для практиков, решающих конкретные задачи. Тут и противопоставление математики прикладной и абстрактной…

Но что важно - это не фундаментальный математический труд, предпосланный желающим изучить предмет. Это - фундаментальный учебник. Несколько фраз из Введения: «Что же в действительности представляет собой конкретная математика? Это осмысленное оперирование математическими формулами с использованием определённых наборов методов решения задач… Предпочтение здесь будет отдаваться технической стороне дела, а не теоремам существования и комбинаторным рассуждениям». В книгу помещено около 500 заданий для самостоятельного решения (кстати, с аккуратным перечислением их авторов и источников).

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

Программист? В 1960 году «свежеиспечённый» бакалавр математики Дональд Кнут вплотную занялся программированием. Причём без дураков. Системное программирование - что может быть круче? Он настолько успешно справился с проектом по созданию компилятора ALGOL-а, что в 1962-м издательство Addison–Wesley предложило ему написать книгу о компиляторах. В это же время он начинает активную преподавательскую деятельность в должности ассистента профессора Калифорнийского технологического института.

В процессе работы над книгой сама концепция издания претерпела коренные изменения. Автора больше не интересовала частная проблема создания компиляторов. При поддержке издательства он начинает подготовку семитомной монографии «Искусство программирования». В 1965 году вышел из печати первый том… Трёхтомник Кнута оказался бестселлером Addison–Wesley. Двухтысячный тираж каждого тома расходился за месяц, начиная с первого издания и далее - в продолжение десяти лет. Книги были переведены на 5 иностранных языков, включая русский. На молодого профессора буквально обрушилась слава. А в 1979 году он получает из рук президента Картера Национальную медаль в области науки…

Именно тогда Дональд Кнут берет «тайм-аут» и вновь - на пять лет - возвращается в программирование. Результатом стали TEX и METAFONT, а также – попутно – новая концепция программирования, получившая название «Literate Programming». («Грамотное программирование». Часто можно встретить некорректный перевод «Литературное программирование»… Ох уж этот профессор - любитель каламбуров и непереводимых названий…)

В 1986 году на торжественном приёме в Addison–Wesley Кнут заявил, что на завершение оставшихся четырёх томов ему потребуется два десятилетия. Через тринадцать лет, в 1999-м, он сообщил, что намерен вплотную заняться следующими двумя томами, а для повышения актуальности монографии запланировал переписать все описания и примеры, данные в книгах на языке ассемблера «морально устаревшего» виртуального компьютера MIX 1009, на язык более современного RISC-процессора MMIX 2009. С этой целью Дональд Кнут разработал архитектуру этого виртуального процессора, написал симулятор и ассемблер.

Что интересно: все без исключения тома «Искусства программирования» были восприняты публикой с величайшим пиететом. Наличие «Кнута» в домашней библиотеке каждого программиста стало считаться само собой разумеющимся. Но лишь немногие разработчики ПО действительно извлекают пользу из этих книг. Причина? Да та же самая: там все построено на принципе практического обучения. Нужно решать задачки… Короче говоря, по некоторым оценкам, на сотню владельцев «Кнута» реально проштудировавших эти книги найдётся едва ли десяток… Как по поводу этого шутил (шутил ли?) Билл Гейтс, наверное, все помнят.

Однажды в интервью Питеру Сейбелу, автору книги «Кодеры за работой. Размышления о ремесле программиста», Дональд Кнут признался: «Я узнал очень много нового… В частности, как много ресурсов мозга съедает разработка ПО. Я не мог одновременно преподавать на полную ставку и полноценно заниматься разработкой ПО. Но я мог преподавать на полную ставку и полноценно заниматься написанием книг»…

Это намёк к нашему второму вопросу…

Борец за свободу “софта”? В 1994 году Дональд Кнут вернулся к вопросу о взаимоотношениях программирования и математики с неожиданной стороны. Совместно с другими учёными он пытался инициировать процесс пересмотра патентной практики в США, касающейся патентования программного обеспечения. Не получилось… Ни в этот раз, ни в 2009-м, когда он вновь попытался повлиять на патентную политику, на этот раз - в Европе. Тем не менее гражданская позиция профессора Кнута, несомненно, заслуживает уважения.

Она предельно ясно выражена в его письме в адрес Комиссара по патентам и товарным знакам Вашингтона (округ Колумбия), где, в частности, говорится:

«Я хотел бы попросить вас пересмотреть текущую политику предоставления патентов на вычислительные процессы… В 1945–1980 годах было принято считать, что патентное право не относится к программному обеспечению. Однако теперь выясняется, что некоторые люди получили патенты на алгоритмы, имеющие большое практическое значение (например, сжатия Зива и RSA-шифрования с открытым ключом), что в настоящее время юридически ограничивает других программистов в использовании этих алгоритмов… Я боюсь, это изменение будет вредно для общества.

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

Идея принятия законов, какие-то алгоритмы относящих к математике, а какие-то - нет, напоминает мне попытки в XIX веке в штате Индиана принять закон, что отношение длины окружности к её диаметру равно в точности 3, а не примерно 3,1416… Или церковное постановление о том, что Солнце вращается вокруг Земли. Представляете, что произойдёт, если отдельные юристы запатентуют свои методы защиты и если судьи Верховного суда смогут запатентовать свои прецеденты? Сегодня я твёрдо уверен, что тенденция к патентованию алгоритмов приносит пользу небольшому числу адвокатов и изобретателей и серьёзно вредит подавляющему большинству людей, которые хотят делать какие-то полезные вещи с помощью компьютеров…»

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

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

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

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

- Виктор Штонда, Геннадий Петриковец, Алексей Орлович, издатели

О книге "Искусство программирования"

У каждой книги своя судьба. Одни появляются незаметно и так же незаметно исчезают в потоке времени, покрываясь пылью на полках библиотек. Другие в определенный период пользуются спросом у узкого круга специалистов, пока им на смену не приходят новые справочники. Третьи, поднимаясь над временем, оказывают мощное влияние на технологическое развитие общества. Книг, относящихся к последней категории, не так уж и много. Их выход в свет - всегда праздник. Проходят годы, изменяются технологии, но новые поколения с постоянным интересом перечитывают их страницы. Именно к таким книгам относится предлагаемый читателю многотомный труд известного американского ученого Дональда Эрвина Кнута "Искусство программирования"

Прошло почти 30 лет со времени первого издания в 1972 году в США этой книги. Она была переведена на большинство языков мира, в том числе и на русский. К настоящему времени на территории стран СНГ трехтомник Д. Э. Кнута стал библиографической редкостью. В 1998 году в США вышло третье издание "Искусства программирования" В нем сохранена последовательность изложения материала прежних версий, но значительно расширен список ссылок, в который включены свежие и наиболее важные результаты, добавлены новые упражнения и комментарии, устранены неточности. Учитывая популярность во всем мире "Искусства программирования", давно следовало ожидать появления нового переводного издания на русском языке, которое вы и держите в руках.

В чем же успех "Искусства программирования" Д. Э. Кнута?

Во-первых, эта книга - великолепное учебное пособие по составлению и анализу компьютерных алгоритмов. Ее разделы могут быть включены во многие университетские курсы по технологиям программирования, теории алгоритмов, дискретной математике. Книгу могут изучать и школьники старших классов, знакомые с основами программирования. В качестве основного языка записи алгоритмов автор выбрал язык машинных команд гипотетического универсального компьютера MIX. Это позволяет строить оптимальные программы с учетом особенностей вычислительных машин. Перенести MIX-программы на реальные ЭВМ или переписать их на языках высокого уровня не составляет особого труда. Логика работы программ почти всегда поясняется простыми блок-схемами.

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

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

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

Список составляющих успеха "Искусства программирования" можно легко продолжить.

Автор этих строк прослушал курс "Искусство программирования" в изложении профессора Кнута в 1976-1977 годах во время стажировки в Станфордском университете. Тогда формировалась алгоритмическая основа технологий программирования, у истоков которой стоял Д. Э. Кнут. Было много обсуждений, семинаров, творческих замыслов.

Значительные книги всегда связаны с судьбой автора. Дональд Эрвин Кнут начал работу над "Искусством программирования" в 1962 году. Продолжает ее и сейчас. У него много планов. Впереди новые тома "Искусства программирования" которых с нетерпением ждут читатели.

- Профессор Анатолий Анисимов

От редактора перевода

Со времени первого издания книги "Искусство программирования" Д. Э. Кнута прошло около 25 лет. Тем не менее книга не только не устарела, но по-прежнему остается основным руководством по искусству программирования, книгой, по которой учатся понимать суть и особенности этого искусства.

За эти годы на английском языке вышло уже третье издание 1-го и 2-го томов, а также второе издание 3-го тома. Автор внес в них значительные изменения и существенные дополнения. Достаточно сказать, что число упражнений практически удвоилось, а многие упражнения, включенные в предыдущие издания (особенно ответы к ним), модифицированы. Существенно дополнены и переделаны многие главы и разделы, исправлены неточности и опечатки, добавлены многочисленные новые ссылки на литературу, использованы теоретические результаты последних лет.

Значительно преобразилась глава 3, особенно разделы 3.5 и 3.6, а также разделы 4.5.2, 4.7, 5.1.4, 5.3, 5.4.9, 6.2.2, 6.4, 6.5 и др.

Естественно, возникла необходимость в новом издании книги.

Перевод выполнен по третьему изданию 1-го и 2-го томов и второму изданию 3-го тома. Кроме того, учтены дополнения и исправления, любезно предоставленные автором.

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

Из-за обилия материала (часто мало связанного между собой) невозможно построить книгу так, чтобы различные понятия и определения вводились сразу же при первом упоминании о них. Поэтому в главе 1 могут обсуждаться без ссылок понятия, строгие определения которых приводятся в 3-м томе. Именно поэтому так велика роль предметного указателя, без которого понимание книги было бы существенно затруднено. Надеемся, что читатель не будет удивлен, найдя ссылки на главы 7, 8 и последующие не вошедшие в предлагаемые три тома главы. Мы вместе с автором надеемся, что очень скоро они будут опубликованы и, безусловно, сразу же появятся в русском переводе в качестве продолжения этого издания.

Следует также обратить внимание на далеко не всегда стандартные обозначения, которыми пользуется автор. Так же, как и определения, эти обозначения могут появиться в 1-м томе, а вводится во 2-м. Поэтому без указателя обозначений пользоваться книгой было бы чрезвычайно трудно. Хочу также обратить внимание на запись [А], где А - некоторое высказывание. Эта запись встречается в формулах, а иногда и в тексте, и обозначает величину, равную индикатору А.

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

ПРЕДИСЛОВИЕ

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

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

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

• Перевод

«Я должен был закончить книгу, прежде чем родится мой сын. Теперь ему 40 лет, и я до сих пор не закончил её.»

На третий год моего пребывания в университете меня попросили провести пару занятий о компьютерах. Группка людей сказала, что в Caltech (Калифорнийском технологическом институте) не учат ничему, что связанно с компьютерами.В это время я консультировал Burroughs. «Так почему бы тебе не провести пару занятий в университете?» - спросили меня. Так я провел занятие всего один раз, и прежде чем закончить университет, они решили нанять меня в качестве доцента, сразу после его окончания учебы.

Обычно в университет не берут на работу собственных выпускников, за исключением MIT. Но как вы знаете, считается нехорошо делать инбридинг (кровосмешение), потому что отделение может увязнуть в одной философии, а они хотят «свежей крови». Но Caltech счел меня достаточно странным и чуждым «по крови», и это было положительным доводом, чтобы нанять меня.

Как зародилась идея книги

(1:04)Тем временем, в январе 1962 года, был мой второй курс в университете и первый год брака с супругой. Мы поженились летом 1961. Я и Джилл прожили 6 месяцев в блаженстве. Мы провели медовый месяц и потом у нас было еще немного времени, что бы побыть вдвоем, пока я не погрузился в написание книги по computer science.

В январе 1962, редактор из Addison-Wesley пригласил меня на обед, и сказал: «Мы хотели бы предложить вам написать книгу о компиляторах». (Компиляторы - это то, чем я занимался для Burroughs весь предыдущий год.)

Addison-Wesley - американское издательство, специализирующееся на компьютерной литературе, ранее также выпускавшее литературу по естественным наукам. Принадлежит к медиа-концерну Pearson.

«Вас рекомендовали нам как того, кто умеет писать компиляторы, и вы думаете о написании книги?» Раньше я работал на всякие газеты и журналы, написал несколько статей. Мне всегда нравилось писать. И вот издатель моих любимых учебников, Addison-Wesley, просит меня написать книгу.

(3:00) Я сразу пошел домой и записал название 12-и глав и подумал, что было бы неплохо, если книга будет именно такой. Я думал, что смогу закончить книгу довольно быстро. У меня есть письмо, которое я написал в 1964 году в ответ на приглашение в один университет: «Я, к сожалению, не могу посетить Стэнфордский университет в этом году, потому что я должен закончить книгу, прежде чем родится мой сын.

Теперь ему 40 лет, и я до сих пор не закончил книгу… Я хотел бы её закончить быстрей, но понятия не имел как и сколько времени мне еще потребуется. Меня попросили написать книгу о компиляторах, но я сказал: «Минуточку, есть куча вещей, которые происходят в компьютерном программировании, о которых вы тоже должны знать». И они сказали, что не против, если в книге будут освещены и другие темы, касающиеся программирования.

Книгу мы решили назвать «Искусство программирования» (The Art of Computer Programming). Издателям понравилось название.

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

Я счел только одного кандидата достойным для такой работы, который напишет не предвзято, - себя.

Недооценка размера книг

Черновик оглавления содержал 12 глав. С первого дня я начал заполнять главу за главой и писать больше материала, а тем временем computer science стремительно развивалась. Оказалось, я очень сильно недооценил, насколько может продлиться работа. В конце написания, я посмотрел на свои заметки, они все были написаны вручную, и мне казалось, что моих заметок намного больше, чем чем сама книга. На самом деле я… я дошел до конца главы 12 у меня было 3000 страниц. А я всего планировал 64-65 глав…

У меня накопилось 3000 рукописных страниц. Я написал в Addison-Wesley и спросил, не возражает ли они, если я дополню книгу материалами, которые я откопал. На что мне ответили: «Давай».

(1:36) 3000 страниц. Я взял печатную машинку и начал печатать. В первой главе было 400 страниц машинного текста и это через два интервала. Кстати, я печатал на IBM Selectric. В то время это было одна из лучших пишущих машинок. Как мне сказали позже, я был первым частным, а не корпоративным покупателем такой машинки. Прелесть в том, что в ней был реализован «буфер». То есть вы могли вводить новую букву, пока предыдущие еще не были напечатаны. Впервые я увидел такую машинку на выставке и попробовал напечатать пару предложений. Я был восхищен. И так я купил себе Selectric и использовал ее для моей диссертации в Калифорнийском технологическом институте. Я как будто был человеком-за-клавиатурой: я играл на фортепиано, на саксофоне, так что это был просто еще одна машина с клавишами.

(3:50) Я начал печатать, набрал первую главу из двенадцати, и отправил её в Addison-Wesley, сказав: «Вот первая глава моей книги». Потом я получил письмо от человека, который вообще-то был первым редактором, кто говорил со мной в 1962. Но это был 1966, думаю, к этому моменту у меня было уже 3000 страниц плюс набираемая глава. И теперь я снова слышал того же парня, но его повысили на три ступени в компании за это время, так что теперь он был на пути наверх. И, знаете, он говорил: «Что происходит? Ваша книга, Дон, вы понимаете, что ваша книга займёт больше 2000 страниц?»

Что? Я думал, у меня шесть или семь сотен страниц в книге. Я сказал, знаете, я подумал: «Я же годами читал книги. Как вы можете говорить мне, что эта книга будет такой длинной?» Так что я вернулся к “Thomas"s Calculus” (учебник по матану), оригинальной книге, которую я обожал на первом курсе в колледже, и напечатал.

Я чувствовал, что пять страниц, которые я печатаю, превратятся в одну страницу в книге, но они сказали: «Нет, нет, полторы к одному». Я не мог поверить. Так что я взял “Thomas"s Calculus” и напечатал 2 страницы оттуда на моей печатной машинке. Точно, три страницы машинописного текста превратились в две.

У меня была книга в три раза большая, чем я рассчитывал. Не удивительно, что у меня ушло столько времени, чтобы закончить эту вещь. Но потом они сказали: «Никто не сможет осилить эту книгу». Знаете, у всех издателей есть страшилки про профессоров, которые шлют им манускрипты в 10 томов об истории яиц или вроде того, и они просто лежат. И вот как они собираются обойти эту проблему?

Выпуск первого тиража

Я прилетел в Массачусетс, чтобы обсудить наши дальнейшие планы. Ребята из издательства сказали: «Ну, мы придумаем что-нибудь», хотя они уже успели показать эту главу нескольким людям, которым она очень даже понравилась, и особо не сомневались в ней. Однако во время ланча я заметил у своего тогдашнего редактора - Норма Стэтона - в личных заметках пометку «строгое ограничение в бюджете» или что-то типа того. Он, видимо, хотел мягко подвести меня к этой новости, и предложил… То есть, они предложили, не заморачиваться с написанием ответов к упражнениям, а вместо профессиональных иллюстраций вставить те, которые я сам рисовал в рукописи. Ребята сказали, что «очарованны» ими. Я тогда, честно, подумал, что они пьяны или под кайфом. «Нет уж», - сказал я, - «знаете, почему мне нравится «Addison-Wesley»? Потому что качество их книг именно такое, каким должно быть - великолепное, а иллюстрации в них - на должном уровне. И именно поэтому я подписывал с вами контракт, ребята!» После этого разговора, мой редактор подошел ко мне и сказал:

«Ты был бесстрашен и настойчив, стоя перед директором кампании, молодец, мальчик!»

И все в таком духе. Тогда они решили напечатать эту книгу в трех томах, но затем их мнение изменилось, и они решили выпустить ее уже в семи томах… В общем, был утвержден план публикации книги «Искусство программирования» в семи томах. И мы до сих пор официально придерживаемся этого плана, но за последние 30 лет было выпущено только 3 тома. Сейчас же я работаю над четвертым.

Computer science - очень обширная область, и те 3000 страниц что я написал ранее охарактеризовывали ее состояние лишь на 1965 год. Но с тех пор прошло немало времени, я изучил некоторые другие ее аспекты, которые тоже стоило включить в книгу. Таким образом прошло еще несколько стадий. Также ребята попросили меня не включать в книгу ответы к упражнениям; задумывалось, что они будут публиковаться отдельно, в мягкой обложке, а печататься будут на машинке. Однако редакторы, все же, решили печатать ответы вместе с остальным текстом. И вот наконец в 1968 году первый том был выпущен. И оценивался он, мягко говоря, дорого - в целых 32$! Когда остальные книги по компьютерным наукам стоили от силы 10$. И что поразительно, в первый же год книга обрела большой успех, 50 университетов утвердили ее как учебное пособие. И хотя читать ее было непросто, это доказывало, что в этой области давно уже не хватало книг именно такого типа.

Вот так и началась история «Искусства программирования». В 1968 я впервые получил копии первого тома. С тех пор было продано еще около 400 000 экземпляров на английском языке и гораздо больше - на других языках. Я не мог поверить, что эта книга станет настолько популярной. Но если бы в 1962 году я знал, что в свои 68 я все еще буду продолжать работать над ней, я бы точно отказался от этой затеи. Если честно, я вообще думал, что закончу в 1965 году, прямо перед рождением моего сына.

To be continued...

Перевод: Алена Карнаухова, Катя Шершнёва и Никита Гладышев

Список 97 видеороликов с историями Дональда Кнута

1.
2.
3.
4. My parents" finances
5. Interests in high school
6. Being a nerd of nerds at high school
7.
8. The Potrzebie System of Weights and Measures
9.
11. University life: my basketball management system
12. University life: the fraternity system
13. Meeting my wife Jill
14. Bible study at university and a time of personal challenge
15. Extra-curricular activities at Case
16. Taking graduate classes at Case
17. Physics, welding, astronomy and mathematics
18. My maths teacher at Case and a difficult problem
19. My interest in graphs and my first experience of a computer
20. How I got interested in programming
21. Learning how to program on the IBM 650
22. Writing a tic-tac-toe program
23. Learning about Symbolic Optimum Assembly programs
24. The Internal Translator
25. Adding more features to RUNCIBLE
26. Wanting to be a teacher and why I chose to go to Caltech
27. Writing a compiler for the Burroughs Corporation
28. Working for the Burroughs Corporation
29. Burroughs Corporation
30. My interest in context-free languages
31. Getting my PhD and the problem of symmetric block designs with…
32. Finding a solution to an open problem about projective planes
33.
34. 1967: a turbulent year
35. Work on attribute grammars and the Knuth-Bendix Algorithm
36. Being creative in the forest
37. A new field: analysis of algorithms
38.
39.
40.
41.
42.
43. The emergence of computer science as an academic subject
44. I want to do computer science instead of arguing for it
45. A year doing National Service in Princeton
46. Moving to Stanford and wondering whether I"d made the right choice
47. Designing the house in Stanford
48. Volume Three of The Art of Computer Programming
49. Working on Volume Four of The Art of Computer Programming
50. Poor quality typesetting on the second edition of my book
51. Deciding to make my own typesetting program
52. Working on my typesetting program
53. Mathematical formula for letter shapes
54. Research into the history of typography
55. Working on my letters and problems with the S
56. Figuring out how to typeset and the problem with specifications
57. Working on TeX
58. Why the designer and the implementer of a program should be the…
59. Converting Volume Two to TeX
60. Writing a users" manual for TeX
61. Giving the Gibbs lecture on my typography work
62. Developing Metafont and TeX
63. Why I chose not to retain any rights to TeX and transcribed it to…
64. Tuning up my fonts and getting funding for TeX
65. Problems with Volume Two
66. Literate programming
67. Re-writing TeX using the feedback I received
68. The importance of stability for TeX
69. LaTeX and ConTeXt
70. A summary of the TeX project
71. A year in Boston
72. Writing a book about the Bible
73. The most beautiful 3:16 in the world
74. Chess master playing at Adobe Systems
75. Giving a lecture series on science and religion at MIT
76. Back to work at Stanford and taking early retirement
77. Taking up swimming to help me cope with stress
78. My graduate students and my 64th birthday
79. My class on Concrete Mathematics
80. Writing a book on my Concrete Mathematics class
81. Updating Volumes One to Three of The Art of Computer Programming
82. Getting started on Volume Four of «The Art of Computer…
83. Two final major research projects
84. My love of writing and a lucky life
85. Coping with cancer
86. Honorary doctorates
87. The importance of awards and the Kyoto Prize
88. Pipe organ music is one of the great pleasures of life
89. The pipe organ in my living room
90. Playing the organs
91. An international symposium on algorithms in the Soviet Union
92. The Knuth-Morris-Pratt algorithm
93.
94. My children: John
95. My children: Jenny
96. Working on a series of books of my collected papers
97. Why I chose analysis of algorithms as a subject

Поддержка публикации - компания Edison Добавить метки