Дональд Кнут — автор «Искусства программирования» и великий мастер ордена программистов Земли
Уже совсем скоро – 10 января гранд-мастеру программирования исполнится 84 года, а он считает, что для окончания основного труда его жизни «Искусства программирования» ему необходимо еще 25 лет. Дай бог ему здоровья, сил и ясный ум, а со всем остальным он точно справится сам. Кстати, рост у него не как у мастера Йоды – 190 см, вот здесь хорошо видно по плечам, хотя он, конечно, сильно сутулится.
На Хабре писали про Кнута предостаточно, потому ограничусь здесь моими любимыми цитатами и одной замечательной историей из его жизни, про которую здесь почему-то еще не упоминали.
Именно ее я поведал своим ученикам на самых первых уроках программирования лет 20 назад (да, был такой период, когда я преподавал в техническом лицее в маленьком провинциальном городке у полярного круга). Зачем же я ее рассказал? Чтобы объяснить, какие именно качества необходимы будущему программисту, хотя в нашей истории нет ни единого слова ни о программировании, ни о компьютерах.
«Дональд Кнут был младше вас, сидящих здесь в классе, ему едва ли исполнилось 14 лет, когда он услышал, как по ТВ объявили о конкурсе местной кондитерской компании: предлагалось из букв использованных в названии нового шоколадного батончика «Гигантские батончики Циглера» («Ziegler’s Giant Bar») составить наибольшее количество слов. Приз для победителя держали в тайне, но как обещали, он точно должен быть весьма ценным. Игры в слова, настолки типа скрэббла, до сих популярны в США и являются традиционным семейным досугом. Потому многие любители настольных игр, конечно же, тут же подписались на участие в конкурсе.
Поразмыслив Дональд тоже решил принять участие. Что он мог противопоставить компании (семье) из 5-6 друзей заядлых игроков- «монстров скрэббла», которые за считанные минуты могли составить десятки слов, а за один только вечер уж точно не менее нескольких сотен слов в сумме?
Если на короткой дистанции в 2-3 дня у него точно нет ни единого шанса, то на длинной – в две недели он вполне может победить, просто потому что примерно знал, как именно его соперники будут действовать. Каждый из игроков станет составлять список слов самостоятельно в течение определенного времени, затем они соберутся в одной большой комнате и начнут по очереди их зачитывать, при этом каждый игрок будет вычеркивать у себя уже прозвучавшие слова. В конце все полученные незачеркнутые слова будут занесены (переписаны) в основной список. На второй и третий день количество таких слов уменьшится в разы. При этом все больше времени станет уходить на сверку новых слов с предыдущим списком. Очевидно, что скорость роста основного списка будет неуклонно и быстро падать с каждым днем.
Так каким же образом Дональд мог обогнать целую команду таких игроков?
Только если выберет иной путь к достижению цели. И он делает это: зачем составлять слова из данного набора букв, когда можно проверять готовый список слов на наличие в нем этих самых букв?!
Если взять достаточно полный словарь английского языка, то база для поиска слов будет просто огромной, а, следовательно, итоговый результат должен быть заметно лучше чем у «монстров скрэббла». Тем более, что такой словарь у Дональда, а точнее у его отца – владельца типографии, был: New Standard Unabridged Dictionary of the English Language, Funk & Wagnalls. Замечательный двухтомник — всего навсего на две тысячи страниц.
Что же такое словарь? Это, по сути, список всех слов в алфавитном порядке. Значит, отпадает одна из главных проблем – проверка найденных слов на уникальность, поскольку в словаре изначально нет повторов. Скорость поиска слов таким методом хоть изначально не слишком высока, но будет практически постоянной все две недели, не снижаясь к концу срока.
Идея использовать словарь, конечно же, замечательная, но как ее осуществить? Каким образом перебрать более 50 тысяч слов на наличие в них определенного набора букв за столь короткий срок? Кнут в воспоминаниях не описывает своего алгоритма, но, уверен, мы сами сможем восстановить его, используя его упоминания про закладки и карточки.
Для начала Дональд аккуратно выписывает буквы из фразы «Ziegler’s Giant Bar», удаляя повторы и размещая их в алфавитном порядке (11 букв). На втором листе он выписывает все буквы невходящие в эту фразу так же в алфавитном порядке (15 букв). Затем вносит закладки в словарь по начальным буквам, которых нет в ключевой фразе. На этом этапе таким образом он исключает для будущего анализа, не менее 30 тысяч слов. Потом приступает к делу, составляя карточки с сочетаниями первых и вторых букв, пропуская ровно так же слова, у которых вторые буквы не входят в ключевую фразу. Уже на этом этапе у него остается всего около 10 тысяч слов. Поскольку словарь, напоминаю, упорядочен по алфавиту, натыкаясь, например, на третью букву невходящую в список, он листает словарь, пока эта или предыдущие по порядку буквы в словах не сменятся.
Тем не менее, такой кропотливый труд требует много времени, и с началом второй недели до окончания конкурса, понимая, что он катастрофически не успевает закончить перебор всех слов, Дональд отпрашивается с уроков на неделю, сославшись на сильные боли в животе, и запирается дома в подвале на восемь часов в день и больше, анализируя и выписывая полученные слова.
Итог его работы за две недели – четыре с половиной тысячи слов!
Ни один из других участников не составил более двух тысяч слов, у самих судей на руках изначально – список всего из двух с половиной тысяч. Такого результата от долговязого 13-летнего школьника не ожидал никто. Его пригласили на телепередачу, где торжественно вручили главный приз – телевизор и большую коробку шоколадных батончиков. Телевизор достался школе, а батончики он раздал своим одноклассникам».
Так какие же качества будущего программиста продемонстрировал Дональд Кнут в данной истории?
Первое: умение выполнить постановку задачи. То, чему в школе, да зачастую и в университетах не учат в принципе. Вспомните формулировки задач в учебниках: вот вам необходимые и достаточные данные для решения, а теперь решайте задачу и получите ответ. В жизни так не бывает. Ты получаешь задание, а вот постановку задачи ты должен сделать сам, как, впрочем, определить и найти нужные данные для ее решения. В нашем случае задание: «Составить как можно больше слов из данного набора букв», он свел к очень конкретно поставленной задаче: «Найти все слова в словаре Funk&Wagnalls, полностью состоящих из данного набора букв».
Второе: вместо того, чтобы действовать и сразу же приступить к поиску этих слов в словаре, он сначала разработал алгоритм отсеивания слов, неподходящих к требованиям задачи. К сожалению, у многих программистов умение остановиться и подумать, прежде чем начать стучать по клавиатуре, напрочь отстутствует, они предпочитают, как я это называю, «думать руками» – кодят сразу: «Хрен ли здесь думать – прыгать надо!» И это, уж извините, очень плохо.
Третье: хотя постановка задачи и разработка алгоритма решения задачи весьма интересны и очень важны, но занимают они в самом лучшем случае лишь 5% от затраченного времени и сил в процессе решения той или иной задачи. Остальное – рутина: реализация алгоритма с учетом особенностей языка программирования, доводка программы до рабочего состояния, затем тестирование, бесконечное вылавливание блох (исправление багов) в программе. Без огромного упорства и концентрации на предмете в программировании абсолютно точно нечего делать. Именно эти свойства и продемонстрировал нам тринадцатилетней подросток, работая без выходных две недели в подвале своего дома, просто потому что решил довести дело, за которое взялся, до конца. Увы, если у вас «шило в заднице» — программирование не для вас, каким бы острым и быстрым умом вы не обладаете.
После знакомства с основными понятиями и операторами языка программирования, давал ученикам эту задачу, как одну из начальных после освоения азов, причем исходный словарь они должны были найти сами. При желании можете раскрыть спойлер и посмотреть.
Ziegler’s Giant Bar
20 лет назад я использовал Турбо-Паскаль для обучения программированию, но здесь приведу образцы программ на Python. В файле-словаре Wordbook.txt все слова записаны в одну колонку без пробелов в начале и в конце слов.
with open("c:\wordbook.txt", "r") as file1: mn_zgbar=set("zieglersgiantbar") i=0 # итерация по строкам словаря for line in file1: if line[len(line)-1]=='\n': line=line[:len(line)-1] #line = line.replace('\n','') mn_line=set(line) if mn_zgbar >= mn_line: # проверка вхождения букв слова в ключевую фразу i+=1 print(i,' ', line)Но использовать операции с множествами, конечно же, нечестно, ведь программа должна быть написана учениками, еще не знакомыми с ними.
Вот вам такой вариант:
with open("c:\wordbook.txt", "r") as file1: zgbar="abegilnrstz" i=0 # итерация по строкам словаря for line in file1: if line[len(line)-1]=='\n': line=line[:len(line)-1] k=0 flag=False while kНу и на закуску мои любимые цитаты Дональда Кнута. Добавляйте в комментариях свои!
Остерегайтесь ошибок в приведенном выше коде; я только доказал его правильность, но не проверял его.
Случайные числа не должны генерироваться случайным образом выбранным методом.
Наука - это знание, которое мы так хорошо понимаем, что можем обучить ему компьютер; а если мы не понимаем до конца, как с этим справляться - это искусство.
В этом смысле мы должны постоянно стремиться превратить каждое искусство в науку: в процессе этого мы продвигаем дальше искусство.
Давайте изменим наше традиционное отношение к построению программ: вместо того, чтобы воображать, что наша основная задача - указывать компьютеру, что ему делать, давайте сосредоточимся на объяснении людям того, что мы хотим, чтобы компьютер делал.
Я предполагаю, что Бог существует, и рад, что это невозможно доказать. [Потому что] я бы проверил доказательство один раз, а потом тут же его забыл бы, ведь иначе я никогда не смог бы рассуждать о духовных вещах и тайнах. И, думаю, моя жизнь была бы очень неполной.
Дата-центр ITSOFT — размещение и аренда серверов и стоек в двух дата-центрах в Москве. За последние годы UPTIME 100%. Размещение GPU-ферм и ASIC-майнеров, аренда GPU-серверов, лицензии связи, SSL-сертификаты, администрирование серверов и поддержка сайтов.
- профессия программиста
- биографии гиков
- биография
Читали ли вы монографию Дональда Кнута «Искусство программирования»?
Хотелось бы узнать есть ли люди которые прочли «Капитал» Маркса «Искусство программирования» полностью и обсудить в комментариях значимость сборника на сегодняшний день.
- не читал 329 (39%) ********************************************************************************************************************************************************************************************************************************************************************************************************************************
- пытался читать 166 (20%) *****************************************************************************************************************************************************************
- прочитал не полностью 121 (14%) *********************************************************************************************************************
- что это такое? 114 (13%) **************************************************************************************************************
- не читал сам, но всем рекомендую 91 (11%) ****************************************************************************************
- полностью прочитал 21 (2%) ********************
- полностью прочитал и выполнил все упражнения 9 (1%) ********
Всего голосов: 851
MaxPower ★★
14.10.20 07:10:35 MSK
Проверено: unfo ( 29.11.20 00:59:05 MSK )
← 1 2 3 →
Значимость сборника весьма элементарно осознать. Чем больше тех кто не читал, тех кто «ненужно» и т.д. - тем дороже можно себя читавшего продать.
nikitos ★★★
( 02.12.20 11:33:44 MSK )
Не читал, но осуждаю
frost_ii ★★★★★
( 02.12.20 16:04:11 MSK )
Люблю такие топики за каминг-ауты типа
«какая-то графомания да ещё с каким-то ассемблером в качестве примеров». Ну и традиционные обвинения в идолопоклонстве.
Совершенно безошибочно выдаёт людей, забаненных в «математическом» юморе.
В этом году их должно быть ещё больше, чем в прошлые разы.
LamerOk ★★★★★
( 02.12.20 16:29:31 MSK )
Книги впечатляющие, только про программирование там ничего нет. Это скорее кибернетика-математика. Строчить код на Java++ эти книги не научат, так что лоровцам они ни к чему, это видно из комментариев в треде.
hotpil ★★★★
( 02.12.20 20:03:25 MSK )
Не читал. Читают те, кого дрочат теорией на собесах?
Она поможет быстрее деливерить фичи и импрувить экспириэнс кастомеров?
anonymous8 ★★
( 02.12.20 21:17:35 MSK )
Считаю что лучше посвятить время на документацию по POSIX и например CORBA, чем мучить себя этим «Житием».
splinter ★★★★★
( 02.12.20 22:28:54 MSK )
не читал сам, но всем рекомендую
не читал, но осуждаю :3
actionless ★★★★★
( 04.12.20 12:54:14 MSK )
Ответ на: комментарий от WitcherGeralt 29.11.20 16:32:56 MSK
чем читать псевдронаучные труды графоманов, лучше почитать какой-то нибудь интересный научпоп или худлит.
Научпоп и худлит это и есть труды графоманов.
Действительно достойна внимания только каноническая литература по C и Unix
Вот это действительно не нужно. Си и Unix’у можно и обезьяну обучить, только вот без трудов Кнута эта обезьяна будет писать говнокод.
Reset ★★★★★
( 04.12.20 14:27:17 MSK )
Каюсь, я 4й том прочитал не полностью 🙁
Reset ★★★★★
( 04.12.20 14:27:58 MSK )
Ответ на: комментарий от splinter 02.12.20 22:28:54 MSK
Вот на кой хрен? Тем более читать документацию по такому устаревшему говну мамонта как CORBA ?
Reset ★★★★★
( 04.12.20 14:29:32 MSK )
Ответ на: комментарий от LamerOk 02.12.20 16:29:31 MSK
Я считаю, что все кто так пишет профнепригодны и их надо гнать из профессии.
Reset ★★★★★
( 04.12.20 14:37:37 MSK )
Ответ на: комментарий от anonymous8 02.12.20 21:17:35 MSK
Кастомеры разные бывают…
spqr ★★★
( 04.12.20 21:00:52 MSK )
Ответ на: комментарий от Sahas 29.11.20 10:39:26 MSK
где вариант «не читал, но осуждаю».
Мой вариант. Перепишут примеры на си, тогда и приходите. Ковыряться в вымышленном асме нет никакого желания.
ox55ff ★★★★★
( 04.12.20 21:32:55 MSK )
Ответ на: комментарий от ox55ff 04.12.20 21:32:55 MSK
Ковыряться в вымышленном асме нет никакого желания.
Можно попробовать читать текст алгоритмов и графы смотреть. Асм там нужен для возможности сравнения алгоритмов, а не чтобы был.
xaizek ★★★★★
( 05.12.20 01:52:59 MSK )
Пытался читать - ниасилил.
Потому, как это «Война и мир».
Bioreactor ★★★★★
( 05.12.20 16:13:34 MSK )
Изза комбинаторики и читал. Непомню какой том. Не осилил , но всем рекомендую.
nioelumiijke ★
( 07.12.20 21:58:15 MSK )
А он её разве дописал.
BattleCoder ★★★★★
( 08.12.20 09:57:30 MSK )
У меня в универе в группе был чел, который на первом курсе дико понтовался тем, что прочитал означенные талмуды. Ходил дико гордый собой. Не знаю, чего он там мог понять, учитывая математическую подготовку бывшего школьника. Вылетел, правда, после третьего курса, проявив полное непонимание матаппарата линейной теории автоматического управления даже на уровне модели вход-выход (передаточные функции и вот это вот всё).
Alden ★★★
( 08.12.20 14:34:56 MSK )
Ответ на: комментарий от Alden 08.12.20 14:34:56 MSK
Может и правда прочитал, но ничего не понял что он там прочитал
Int64 ★★★
( 08.12.20 18:17:30 MSK )
Ответ на: комментарий от WitcherGeralt 29.11.20 16:32:56 MSK
Да там вопрос скорее зачем тебе знать алгоритмы сортировки, когда даже в C++ все это в стандартной либе есть. А вот в 68 году сидели и реализовывали все с нуля, пока в 90-ые STL не появилось.
tz4678 ★★
( 09.12.20 19:58:18 MSK )
Имплаинг все кругом погромизды, яблоку плюнуть негде, попадешь в погромизда. Узнал об этом вашем монографе из опроса, не читал, не собираюсь.
justin_case ★
( 09.12.20 21:50:56 MSK )
Ответ на: комментарий от tz4678 09.12.20 19:58:18 MSK
Чтобы на собеседованиях увернно на дебильные вопросы отвечать.
WitcherGeralt ★★
( 09.12.20 21:51:56 MSK )
Первый том начал читать лет пять назад, но я тогда не работал еще программистом, меня начальник отчитал, и я бросил. Кстати сейчас можно и прочитать
nightsinger ★
( 12.12.20 15:21:13 MSK )
20 с хвостиком лет назад наш преподаватель регулярно отсылала к его трудам. Но тогда был один экземпляр на факультет.
И это пожалуй лучший вариант её использование. Т.е. преподаватель читает лекции и периодически отсылает прочитать или сделать что-то из трудов Кнута.
AlexVR ★★★★★
( 12.12.20 21:40:44 MSK )
Ответ на: комментарий от tz4678 09.12.20 19:58:18 MSK
зачем тебе знать алгоритмы сортировки, когда даже в C++ все это в стандартной либе есть
A зачем знать таблицу умножения когда есть калькулятор?
Зачем уметь интегрировать/дифференцировать когда есть wolfram alpha?
Зачем уметь паять когда есть клеммники?
Зачем уметь читать когда есть фильмы и аудиокниги?
Этот список можно продолжать довольно долго… «Видишь ли, мой друг, все люди делятся на два сорта: те, у кого револьвер заряжен есть знания теории, и те, кто копают.»(с)
AntonI ★★★★
( 13.12.20 15:46:02 MSK )
Ответ на: комментарий от AntonI 13.12.20 15:46:02 MSK
это разные вещи. без оных трудов вполне успешно можно программировать, а без таблицы умножения и умения читать жить будет сложновато. диалектика. некорректные сравнения
tz4678 ★★
( 14.12.20 11:29:36 MSK )
Ответ на: комментарий от tz4678 09.12.20 19:58:18 MSK
А вот прилетит астероид, уничтожит все экземпляры STL (и труды Кнута), и потом такие, как ты, сортировать больше не смогут, ибо не изучили в своё время.
Harald ★★★★★
( 14.12.20 11:52:22 MSK )
Ответ на: комментарий от tz4678 14.12.20 11:29:36 MSK
Без таблицы умножения и умения читать жить ничуть не сложнее чем программировать без знания алгоритмов - умножать умеет калькулятор, указатели в ТЦ давно перешли на пиктограммы.
Другой вопрос в качестве жизни (и кода) - и то и то будет плохим, причем ты сам этого не будешь осознавать.
Нет ничего практичнее хорошей теории, это верно для всех областей человеческой деятельности.
AntonI ★★★★
( 14.12.20 12:43:53 MSK )
Ответ на: комментарий от Harald 14.12.20 11:52:22 MSK
Да и без астероида с-но как только появится не вполне стандартная задача он её сольет. Да и стандартные будет решать так себе…
AntonI ★★★★
( 14.12.20 12:45:03 MSK )
Ответ на: комментарий от AntonI 14.12.20 12:45:03 MSK
Если упадет астероид, то и программисты будут не нужны. Как алгоритмы сортировки (заучивание последовательности действий) помогут в решении нестандартных задач? А если решение задачи описано до тебя в чем ее нестандартность? В реальной жизни ты берешь кучу готовых либ, а потом тяп-ляп и в продакшен. Ты ж там питон мучаешь, студент, сам должен понимать, что твои имплементации алгоритмов всегда будут работать медленее нативных. А если ты их использовать на своем похапэ не можешь, то и зачем они тебе? Ты язык не тот выбрал. В питоне даже паттернам применение сложно найти, ну кроме producer-consumer и пр до которых сам дойдешь даже книг не читая.
tz4678 ★★
( 14.12.20 13:14:32 MSK )
- нихуя не понял, но очень интересно
пс. осилил где-то треть бетонной математики, еще в универе.
vvviperrr ★★★★★
( 14.12.20 13:31:24 MSK )
Последнее исправление: vvviperrr 14.12.20 13:43:26 MSK (всего исправлений: 1)
Ответ на: комментарий от tz4678 14.12.20 13:14:32 MSK
Если упадет астероид, то и программисты будут не нужны.
А вдруг один программист выживет. И придут к нему люди такие «напиши нам все програмы, чтобы мы могли возродить Цивилизацию», а он такой «сорри, я Кнута в детстве не читал»
Harald ★★★★★
( 14.12.20 14:15:32 MSK )
Ответ на: комментарий от tz4678 14.12.20 13:14:32 MSK
Как алгоритмы сортировки (заучивание последовательности действий) помогут в решении нестандартных задач?
Любая нестандартная задача является комбинацией стандартных задач меньшего уровня сложности
Harald ★★★★★
( 14.12.20 14:18:16 MSK )
Ответ на: комментарий от tz4678 14.12.20 13:14:32 MSK
Как алгоритмы сортировки (заучивание последовательности действий) помогут в решении нестандартных задач?
Заучивание вообще в таких вещах мало помогает. А вот понимание того как эти алгоритмы работают расширит твое сознание и позволит решать задачи более эффективно. Примерно затем же в хороших вузах на первых курсах грузят матаном - я знаю очень немного людей которые этим матаном реально в жизни потом пользуются (сам, будучи физиком и прикладным математиком, использую в работе оттуда очень немного) - но этот матан позволяет сформировать правильный образ мышления. Это как ОФП для горнолыжника - ты можешь им не заниматься, но тогда ты никогда не сможешь хорошо кататься, тебя сломает в первом же агрессивном повороте.
Ты ж там питон мучаешь, студент, сам должен понимать, что твои имплементации алгоритмов всегда будут работать медленее нативных.
Во первых я уже давно не студент а студентов мучаю. Во вторых некоторое время назад на питоне порвали фклочья метапроговскую сишную поделку по поиску вхождений строк, и наверное могли бы порвать какую нить тупую реализацию на STL - именно за счет понимания алгоритмов. Мысль человеческую обогнать невозможно.
Таджик со стройки тоже не умеет читать и считать (для строительства домов ему это нинада). Если спросить его чем он недоволен - он будет ругать шайтан-прораба, да, который его опять обсчитал. Если спросить чем помочь - попросит денег или новые пассатижи что бы удобнее было арматуру вязать. Тяп-ляп и в продакшен!
AntonI ★★★★
( 14.12.20 14:46:21 MSK )
Последнее исправление: AntonI 14.12.20 14:47:02 MSK (всего исправлений: 1)
Читали ли вы монографию Дональда Кнута «Искусство программирования»?
Хотелось бы узнать есть ли люди которые прочли «Капитал» Маркса «Искусство программирования» полностью и обсудить в комментариях значимость сборника на сегодняшний день.
- не читал 329 (39%) ********************************************************************************************************************************************************************************************************************************************************************************************************************************
- пытался читать 166 (20%) *****************************************************************************************************************************************************************
- прочитал не полностью 121 (14%) *********************************************************************************************************************
- что это такое? 114 (13%) **************************************************************************************************************
- не читал сам, но всем рекомендую 91 (11%) ****************************************************************************************
- полностью прочитал 21 (2%) ********************
- полностью прочитал и выполнил все упражнения 9 (1%) ********
Всего голосов: 851
MaxPower ★★
14.10.20 07:10:35 MSK
Проверено: unfo ( 29.11.20 00:59:05 MSK )
← 1 2 3 →
«Выполнил все упражнения» Шо, и теорему Ферма доказал самостоятельно?
Не хватает пункта «прочитал все тома, включая неизданные»
gns ★★★★★
( 29.11.20 10:15:35 MSK )
Для тру-лоровца не может быть другого варианта, кроме
не читал сам, но всем рекомендую
Im_not_a_robot ★★★★★
( 29.11.20 10:28:28 MSK )
Последнее исправление: Im_not_a_robot 29.11.20 10:28:38 MSK (всего исправлений: 1)
где вариант «не читал, но осуждаю».
Sahas ★★★★★
( 29.11.20 10:39:26 MSK )
Ответ на: комментарий от gns 29.11.20 10:15:35 MSK
Не хватает пункта «прочитал все тома, включая неизданные»
«Я там был, Толкин наврал, всё было совсем не так» (с) народ
hobbit ★★★★★
( 29.11.20 13:44:34 MSK )
Зачем её читать? Её на полку ставят.
Pacmu3ka
( 29.11.20 14:25:05 MSK )
Пытался читать несколько раз. Пока до таких трудов я ещё не дорос, в итоге каждый раз бросал читать.
lucentcode ★★★★★
( 29.11.20 15:53:39 MSK )
Не читал, но осуждаю 🙂
bryak ★★★★
( 29.11.20 15:57:05 MSK )
полностью прочитал и выполнил все упражнения – 1
Царь себе новый аккаунт завёл, не иначе.
значимость сборника на сегодняшний день.
Книга даёт довольно цельный обзор крупных классов задач и методов их решения, демонстрируя в некоторой степени эволюцию понимания проблематики и как это отражается в соответствующих алгоритмах. В общем в дополнении к изучению существующих алгоритмов и их оценке можно получить представление и о подходах решения на примерах, так сказать.
Вышесказанное не отменяет того, что Кнут больше математик и читать книги не так уж и просто и очень медленно.
xaizek ★★★★★
( 29.11.20 15:57:53 MSK )
По такому случаю, где посоветуете скачать самый актуальный вариант?
question4 ★★★★★
( 29.11.20 16:05:01 MSK )
Последнее исправление: question4 29.11.20 16:05:14 MSK (всего исправлений: 1)
Ответ на: комментарий от gns 29.11.20 10:15:35 MSK
Не хватает пункта «прочитал все тома, включая неизданные»
no-such-file ★★★★★
( 29.11.20 16:06:20 MSK )
А смысл всю эту воду целиком вычитывать? Достаточно какой-нибудь обзорной статьи. In my not so humble opinion, чем читать псевдронаучные труды графоманов, лучше почитать какой-то нибудь интересный научпоп или худлит.
Для программирования куда полезней документацию и код читать, не забывая их же и писать, а не это. Действительно достойна внимания только каноническая литература по C и Unix, остальное опционально.
WitcherGeralt ★★
( 29.11.20 16:32:56 MSK )
Ответ на: комментарий от WitcherGeralt 29.11.20 16:32:56 MSK
читать псевдронаучные труды графоманов
сжечь бесполезного неуча!
Harald ★★★★★
( 29.11.20 16:48:56 MSK )
Ответ на: комментарий от Pacmu3ka 29.11.20 14:25:05 MSK
И к полке намертво приклеивают! 🙂
gns ★★★★★
( 29.11.20 17:24:59 MSK )
Ответ на: комментарий от WitcherGeralt 29.11.20 16:32:56 MSK
Ну Вы комиксы почитайте для начала что-ли.
gns ★★★★★
( 29.11.20 17:27:29 MSK )
Ответ на: комментарий от gns 29.11.20 17:27:29 MSK
Комиксы читаю, на этот счёт не волнуйся.
WitcherGeralt ★★
( 29.11.20 17:34:14 MSK )
Ответ на: комментарий от Harald 29.11.20 16:48:56 MSK
Фанат, или просто набрасываешь?
WitcherGeralt ★★
( 29.11.20 17:34:39 MSK )
Последнее исправление: WitcherGeralt 29.11.20 17:35:04 MSK (всего исправлений: 1)
Сборник однозначно нужный, хотя бы из-за тематики - чтобы ИТ наводнялось не похапэхами-самоучками, а людьми с высшим образованием и широким кругозором. Но вот ОБЯЗАН ли ты читать весь этот словесный понос. не уверен.
Понимаете, кто бы вы ни были, вряд ли вы тратите свою жизнь на меценатство и бесплатный «культпросвет» задротов! Дональд написал КНИГУ, коммерческое изделие, баблоносный сборник. Не думаю, что его целью было лаконично описать все проблемы, чтобы поняла даже кухарка. Скорее, «дедушка - старый, ему всё равно» - он может себе позволить растекаться мыслью по древу, даже если мысль не несёт ВООБЩЕ НИКАКОЙ пользы для понимания темы! Ведь главное - объём.
Я уверен, что ВСЮ серию «Исск.п-я» можно уместить в один 200-страничный том. А вместо этого дедушка натрындел на СЕМЬ(!) томов.
Ну и как проф.программист, скажу: ДАЛЕКО не все его темы нужны ИТшнику. Та же комбинаторика (в моей практике) практически не встечается. Сортировка? Буквально на уровне вызова Sort().
Отсюда и вывод: если вы - студент и некуда девать время в дороге - берите и читайте, можно даже по диагонали. Главное - понять с высоты птичьего полёта разнообразие ИТ проблем. Ну а когда конкретно припрёт применять алгоритм, всегда можно взять отдельную главу и вдумчиво перечитать.
Ну а профессионалам книга не особо поможет - скорее всего, все главы вы уже проходили в институте и в сети 100% есть материал куда более лаконичный и полезный, чем мысли дедушки времён 1970-ых.
На сегодня даже алгоритмы сжатия прыгнули далеко вперёд, что уж говорить про многозвенную архитектуру или ORM! Хотите быть на острие - читайте современников. Ну а для эрудиции положите пару томов Кнута в туалет - нет-нет, да прочтёте главу-другую! 🙂
Искусство программирования, том 1. Основные алгоритмы
Первый том серии книг Искусство программирования начинается с описания основных понятий и методов программирования. Затем автор сосредотачивается на рассмотрении информационных структур — представлении информации внутри компьютера, структурных связях между элементами данных и о способам эффективной работы с ними. Для методов имитации, символьных вычислений, числовых методов, методов разработки программного обеспечения даны примеры элементарных приложений. По сравнению с предыдущим изданием, добавлены десятки простых, но в то же время очень важных алгоритмов. В соответствии с современными направлениями исследований был существенно переработан также раздел математического введения.
Посетить официальную страницу: книги
Книга обсуждается в отдельном сообщении в блоге Виктора Штонда
формат 70x100/16; 2015, 2 кв.; Вильямс.
Понравилась книга? Порекомендуйте её друзьям и коллегам:
- Алгоритмические трюки для программистов, 2-е издание, Генри С. Уоррен
- Алгоритмы: построение и анализ, 3-е издание, Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн
- Конкретная математика. Математические основы информатики, 2-е издание, Рональд Л. Грэхем, Дональд Э. Кнут, Орен Паташник
- Безопасное программирование на C и C++, 2-е издание, Роберт С. Сикорд
- Python. Карманный справочник, 5-е издание, Марк Лутц
- Искусство программирования, том 4А. Комбинаторные алгоритмы , часть 1, Дональд Эрвин Кнут
- Искусство тестирования программ, 3-е издание, Гленфорд Майерс, Том Баджетт, Кори Сандлер
- Алгоритмы на Java, 4-е издание, Роберт Седжвик, Кевин Уэйн
- Начала программирования, Александр Степанов, Пол Мак-Джонс
- Алгоритмы на C++. Фундаментальные алгоритмы и структуры данных. 2 книги в одной !, Роберт Седжвик
- Введение в информационный поиск, Кристофер Д. Маннинг, Прабхакар Рагхаван, Хайнрих Шютце
- C++ для чайников, 6-е издание, Стефан Рэнди Дэвис
- Искусство программирования, том 2. Получисленные алгоритмы, 3-е издание, Дональд Э. Кнут
- Искусство программирования, том 3. Сортировка и поиск, 2-е издание, Дональд Э. Кнут
Предисловие
Введение
Глава 1. ОСНОВНЫЕ ПОНЯТИЯ
1.1. АЛГОРИТМЫ
1.2. МАТЕМАТИЧЕСКОЕ ВВЕДЕНИЕ
1.2.1. Математическая индукция
1.2.2. Числа, степени и логарифмы
1.2.3. Суммы и произведения
1.2.4. Целочисленные функции и элементарная теория чисел
1.2.5. Перестановки и факториалы
1.2.6. Биномиальные коэффициенты
1.2.7. Гармонические числа
1.2.8. Числа Фибоначчи
1.2.9. Производящие функции
1.2.10.Анализ алгоритма
*1.2.11.Асимптотические представления
*1.2.11.1. Символ O
*1.2.11.2. Формула суммирования Эйлера
*1.2.11.3. Применение асимптотических формул
1.3. MIX
1.3.1. Описание MIX
1.3.2. Язык ассемблера компьютера MIX
1.3.3. Применение к перестановкам
1.4. НЕКОТОРЫЕ ФУНДАМЕНТАЛЬНЫЕ МЕТОДЫ ПРОГРАММИРОВАНИЯ
1.4.1. Подпрограммы
1.4.2. Сопрограммы
1.4.3. Программы-интерпретаторы
1.4.3.1. Имитатор MIX
*1.4.3.2. Программы трассировки
1.4.4. Ввод и вывод
1.4.5. История и библиография
Глава 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. ДЕРЕВЬЯ
2.3.1. Обход бинарных деревьев
2.3.2. Представление деревьев в виде бинарных деревьев
2.3.3. Другие представления деревьев
2.3.4. Основные математические свойства деревьев
2.3.4.1. Свободные деревья
2.3.4.2. Ориентированные деревья
*2.3.4.3. Лемма о бесконечном дереве
*2.3.4.4. Перечисление деревьев
2.3.4.5. Длина пути
*2.3.4.6. История и библиография
2.3.5. Списки и “сборка мусора”
2.4. МНОГОСВЯЗНЫЕ СТРУКТУРЫ
2.5. ДИНАМИЧЕСКОЕ ВЫДЕЛЕНИЕ ПАМЯТИ
2.6. ИСТОРИЯ И БИБЛИОГРАФИЯ
ОТВЕТЫ К УПРАЖНЕНИЯМ
ПРИЛОЖЕНИЕ A. ТАБЛИЦЫ ЗНАЧЕНИЙ НЕКОТОРЫХ КОНСТАНТ
A.1. Основные константы (десятичные)
A.2. Основные константы (восьмеричные)
A.3. Значения гармонических чисел, чисел Бернулли и чисел Фибоначчи
ПРИЛОЖЕНИЕ Б. ОСНОВНЫЕ ОБОЗНАЧЕНИЯ
От издателей русского перевода
На мировом рынке компьютерной литературы существует множество книг, предназначенных для обучения основным алгоритмам и используемых при программировании. Их довольно много, и они в значительной степени конкурируют между собой. Однако среди них есть особая книга. Это трехтомник "Искусство программирования" Д. Э. Кнута, который стоит вне всякой конкуренции, входит в золотой фонд мировой литературы по информатике и является настольной книгой практически для всех, кто связан с программированием.
Мы как издатели видим ценность книги в том, что она предназначена не столько для обучения технике программирования, сколько для обучения, если это возможно, "искусству" программирования, предлагает массу рецептов усовершенствования программ и, что самое главное, учит самостоятельно находить эти рецепты.
Ни для кого не секрет, что наши программисты являются одними из наиболее высококвалифицированных специалистов в мире. Они достойно представляют за рубежом отечественную школу программирования и информатики, которая внесла значительный вклад в формирование фундаментальных основ компьютерных наук. Для сохранения такого уровня и продвижения вперед необходимо своевременное издание на русском языке книг, отражающих основные мировые достижения в этой области. Трехтомник "Искусство программирования" Д. Э. Кнута — одна из таких книг.
Мы гордимся тем, что библиотеки программистов, преподавателей, студентов, старшеклассников и многих других пополнятся этой классической книгой и что тем самым мы внесем свой вклад в формирование более глубокого понимания основ компьютерных наук. Мы глубоко убеждены, что книга "Искусство программирования" Д. Э. Кнута способна приблизить человека к совершенству. Надеемся, наше издание на русском языке этой замечательной книги еще раз подтвердит, что истинные ценности с годами не устаревают.
— Виктор Штонда, Геннадий Петриковец, Алексей Орлович, издатели
О книге "Искусство программирования"
У каждой книги своя судьба. Одни появляются незаметно и так же незаметно исчезают в потоке времени, покрываясь пылью на полках библиотек. Другие в определенный период пользуются спросом у узкого круга специалистов, пока им на смену не приходят новые справочники. Третьи, поднимаясь над временем, оказывают мощное влияние на технологическое развитие общества. Книг, относящихся к последней категории, не так уж и много. Их выход в свет — всегда праздник. Проходят годы, изменяются технологии, но новые поколения с постоянным интересом перечитывают их страницы. Именно к таким книгам относится предлагаемый читателю многотомный труд известного американского ученого Дональда Эрвина Кнута "Искусство программирования"
Прошло почти 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)
ОГЛАВЛЕНИЕ
ГЛАВА 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 Издательская группа "Диалектика-Вильямс"