Knuth D.E. / Кнут Д. - Искусство программирования / The Art of Computer Programming [2002, PDF, RUS]. Книги кнута


Когда же, наконец, выйдет четвертый том / Блог компании Edison / Хабр

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

Прочитайте и оцените объем работ. И не торопите дедушку Кнута, он и так старается.Поддержка публикации — компания 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-х, из которой я могу взять предложения и фразы, чтобы омолодить книгу.

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

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

Читать еще

  • Дональд Кнут: Я сидел на задних партах и травил шутки, а учителя смирились и не часто били по заднице (1,2,3,7/97)
  • Дональд Кнут: «Мой совет молодым» (93/97) и «Ощущая потребность самоутвердиться» (9/97)
  • «Сюрреальные числа»: Я творил шесть дней, а на седьмой отдыхал (40,41,42/97)
  • Дональд Кнут: Как создавалось «Искусство программирования» (33,38,39/97)
  • Дональд Кнут: Когда же, наконец, выйдет четвертый том
  • Дональд Кнут: Как я провел лето с компьютером, а не с девушками (19,20,21,22/97)

habr.com

Knuth D.E. / Кнут Д.

Искусство программирования / The Art of Computer Programming

Год выпуска: 2002Автор: Дональд Кнут / Donald E. KnuthЖанр: Документация по языкам програмированияИздательство: ВильямсФормат: PDFКачество: Отсканированные страницыКоличество страниц: Том 1 = 682 стр.; Том 2 = 788 стр.; Том 3 = 800 стр.Язык книг: русскийОбложки книг:Код:

Код:

Кнут Д. - Искусство программирования том 1 (3-е издание) - 2001ОГЛАВЛЕНИЕ

         От издателей русского перевода               1         О книге "Исскуство программирования"         2         От редактора перевода                        4         Предисловие                                  5

Глава 1  ОСНОВНЫЕ ПОНЯТИЯ                            19

1.1      АЛГОРИТМЫ                                   19, 28

1.2      МАТЕМАТИЧЕСКОЕ ВВЕДЕНИЕ                     291.2.1    Математическая индукция                     30, 381.2.2    Числа, степени и логарифмы                  41, 461.2.3    Суммы и произведения                        48, 55, 581.2.4    Целочисленные функции и элементарная                                        теория чисел 60, 631.2.5    Перестановки и факториалы                   67, 721.2.6    Биноминальные коэффициенты                  74      А. Факториальное представление                 77      В. Свойство симметрии                          77      С. Внесение-вынесение                          77      D. Формула сложения                            78      E. Формулы суммирования                        78      F. Биноминальная теорема                       79      G. Обращение верхнего индекса                  80      H. Упрощение произведений                      81      I. Суммы произведений                          81, 921.2.7    Гармонические числа                         97, 1001.2.8    Числа Фибоначчи                            101, 1061.2.9    Производящие функции                       110      A. Сложение                                   111      В. Сдвиг                                      111      С. Умножение                                  111      D. Замена переменной z                        112      E. Дифференцирование и интегрирование         113      F. Известные производящие функции             113      G. Представление коэффициента                 115, 1171.2.10   Анализ алгоритма                           119, 1281.2.11   Асимптотические представления              1301.2.11.1 Символ О                                   130, 1341.2.11.2 Формула суммирования Эйлера                135, 1391.2.11.3 Применение асимптотических формул          140, 145

1.3      MIX                                        1481.3.1    Описание MIX                               148, 1661.3.2    Язык ассемблера компьютера MIX             170, 182, 1831.3.3    Применение к перестановкам                 190, 209

1.4      НЕКОТОРЫЕ ФУНДАМЕНТАЛЬНЫЕ МЕТОДЫ                                   ПРОГРАММИРОВАНИЯ 2131.4.1    Подпрограммы                               213, 2201.4.2    Сопрограммы                                221, 2281.4.3    Программы-интерпретаторы                   2291.4.3.1  Имитатор MIX                               231, 2401.4.3.2  Программы трассировки                      240, 2421.4.4    Ввод и вывод                               243, 2551.4.5    История и библиография                     258

Глава 2  ИНФОРМАЦИОННЫЕ СТРУКТУРЫ                   262

2.1      ВВЕДЕНИЕ                                   262, 267

2.2      ЛИНЕЙНЫЕ СПИСКИ                            2682.2.1    Стеки, очереди и списки                    268, 2722.2.2    Последовательное распределение             274, 2822.2.3    Связанное распределение                    286, 3012.2.4    Циклические списки                         306, 3112.2.5    Дважды связанные списки                    313, 3302.2.6    Массивы и ортогональные списки             332, 339

2.3      ДЕРЕВЬЯ                                    343, 3522.3.1    Обход бинарных деревьев                    353, 3672.3.2    Представление деревьев в виде бинарных                                           деревьев 371, 3832.3.3    Другие представления деревьев              386, 3972.3.4    Основные математические свойства деревьев  4012.3.4.1  Свободные деревья                          401, 4082.3.4.2  Ориентированные деревья                    411, 4162.3.4.3  Лемма о бесконечном дереве                 422, 4242.3.4.4  Перечисление деревьев                      426, 4362.3.4.5  Длина пути                                 440, 4452.3.4.6  История и библиография                     447, 4492.3.5    Списки и "сборка мусора"                   450, 464

2.4      МНОГОСВЯЗНЫЕ СТРУКТУРЫ                     467, 476

2.5      ДИНАМИЧЕСКОЕ ВЫДЕЛЕНИЕ ПАМЯТИ              479, 498

2.6      ИСТОРИЯ И БИБЛИОГРАФИЯ                     503

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

Код:

Код:

Кнут Д. - Искусство программирования том 2 (3-е издание) - 2001ОГЛАВЛЕНИЕ

        От издателей русского перевода                1        О книге "Искусство программирования"          2        От редактора перевода                         4        Предисловие                                   5        Предисловие к третьему изданию                6        Примечания к упражнениям                      8

Глава 3 СЛУЧАЙНЫЕ ЧИСЛА                              11

3.1     ВВЕДЕНИЕ                                     11, 17

3.2     ГЕНЕРИРОВАНИЕ РАВНОМЕРНО РАСПРЕДЕЛЁННЫХ                                СЛУЧАЙНЫХ ЧИСЕЛ      213.2.1   Линейный конгруэнтный метод                  21, 223.2.1.1 Выбор модуля                                 23, 263.2.1.2 Выбор множителя                              28, 333.2.1.3 Потенциал                                    35, 373.2.2   Другие методы                                38, 49

3.3     СТАТИСТИЧЕСКИЕ КРИТЕРИИ                      543.3.1   Основные критерии проверки случайных                                         наблюдений  55     А. Критерий "хи-квадрат"                        55     В. Критерий Колмогорова-Смирнова                61     С. История, библиография и теория               68, 713.3.2   Эмпирические критерии                        74     А. Критерий равномерности (критерий частот)     75     В. Критерий серий                               75     С. Критерий интервалов                          76     D. Покер-критерий (критерий разбиений)          77     E. Критерий собирания купонов                   78     F. Критерий перестановок                        79     G. Критерий монотонности                        80     H. Критерий "максимум-t"                        84     I. Критерий конфликтов                          84     J. Критерий промежутков между днями рождений    85     K. Критерий сериальной корреляции               87     L. Критерий подпоследовательностей              87     M. Исторические замечания и дальнейшее                                       обсуждение    88, 903.3.3   Теоретические критерии                       95, 105, 1073.3.4   Спектральный критерий                       108     А. Идеи, служащие обоснованием критерия        108     В. Дальнейшее исследование критерия            112     С. Обоснование вычислительных методов          113     D. Как выполнить спектральный критерий         117     E. Рейтинги различных генераторов              120     F. Связь с критерием серий                     125     G. Историческая справка                        130, 131

3.4     ДРУГИЕ ВИДЫ СЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ   1353.4.1   Численные распределения                     135     А. Случайный выбор из ограниченного множества  135     В. Общие методы для непрерывных распределений  137     С. Нормальное распределение                    138     D. Показательное распределение                 149     E. Другие непрерывные распределения            150     F. Важные целочисленные распределения          153     G. Для дальнейшего чтения                      155, 1563.4.2   Случайные выборки и перемешивания           160, 164

3.5     ЧТО ТАКОЕ СЛУЧАЙНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ      167     А. Вводные замечания                           167     B. %-распределённые последовательности         170     С. Эквивалентно ли понятие %-распределённости                              понятию случайности?  177     D. Существование случайных последовательностей 182     E. Случайные конечные последовательности       187     F. Псевдослучайные числа                       190     G. Выводы, история и библиография              197, 200

3.6     ВЫВОДЫ                                      205, 210

Глава 4 АРИФМЕТИКА                                  216

4.1     ПОЗИЦИОННЫЕ СИСТЕМЫ СЧИСЛЕНИЯ               217, 233

4.2     АРИФМЕТИКА ЧИСЕЛ С ПЛАВАЮЩЕЙ ТОЧКОЙ         2394.2.1   Вычисления с однократной точностью          239     А. Обозначения чисел с плавающей точкой        239     В. Нормализованные вычисления                  240     С. Аппаратная реализация арифметических            действий над числами с плавающей точкой 249     D. История и библиография                      251, 2534.2.2   Точность арифметических операций с                                   плавающей точкой 256     А. Аксиоматический подход                      257     В. Арифметические действия над      ненормализованными числами с плавающей точкой 265     С. Арифметика интервалов                       267     D. История и библиография                      268, 2694.2.3   Вычисления с удвоенной точностью            273, 2804.2.4   Распределение чисел в формате с плавающей                                             точкой 281     А. Программы сложения и вычитания              281     В. Дробные части                               282, 291

4.3     АРИФМЕТИКА МНОГОКРАТНОЙ ТОЧНОСТИ            2944.3.1   Классические алгоритмы                      294        История и библиография                      308, 3114.3.2   Модулярная арифметика                       315, 3234.3.3   Насколько быстро можно выполнить умножение  325     А. Цифровые методы                             326     В. Модулярный метод                            334     С. Умножение при помощи дискретного                               преобразования Фурье 337     D. Деление                                     343     E. Умножение в реальном времени                345, 348

4.4     ПРЕОБРАЗОВАНИЕ ИЗ ОДНОЙ СИСТЕМЫ СЧИСЛЕНИЯ В                                             ДРУГУЮ 351     A. Четыре основных метода                      351     В. Преобразование с однократной точностью      352     С. Вычисления вручную                          355     D. Преобразование чисел с плавающей точкой     358     E. Преобразование с многократной точностью     359     F. История и библиография                      359, 360

4.5     АРИФМЕТИКА РАЦИОНАЛЬНЫХ ЧИСЕЛ               3634.5.1   Дроби                                       363, 3654.5.2   Наибольший общий делитель                   367        Алгоритм Евклида                            368        Бинарный метод                              371        Обобщения                                   375        Вычисление с высокой точностью              379        Анализ бинарного алгоритма                  382, 3874.5.3   Анализ алгоритма Евклида                    391        Связь с цепными дробями                     391        Наихудший случай                            394        Приближённая модель                         395        Непрерывная модель                          396, 4084.5.4   Разложение на простые множители             415        Деление и разложение на множители           415        Разложение на простые множители с              использованием псевдослучайных циклов 420        Метод Ферма                                 423        Проверка принадлежности чисел к простым     427        Усовершенствованные методики проверки                     принадлежности чисел к простым 431        Разложение на простые множители при помощи                                      цепных дробей 434        Теоретическая верхняя граница               439        Другие подходы                              440        Секретные множители                         442        Самые большие известные простые числа       446, 451

4.6     ПОЛИНОМИНАЛЬНАЯ АРИФМЕТИКА                  459, 4614.6.1   Деление полиномов                           461        Области единственного разложения на                                          множители 462        Наибольшие общие делители                   465        Алгоритм Коллинза                           469, 4764.6.2   Разложение полиномов на множители           480        Разложение по модулю p                      480        Алгоритм N (Алгоритм ядра)                  485        Разложение с различными степенями           489        Разложение над кольцом целых чисел          491        Наибольшие общие делители                   495        Полиномы от многих переменных               497, 4974.6.3   Вычисление степений                         503        Уменьшение количества операций умножения    505        Аддитивные цепочки                          507        Специальные классы цепочек                  509        Значения l(n) для специальных n             510        Асимптотические значения                    513        Звёздные цепочки                            515        Графическое представление                   522, 5244.6.4   Вычисление полиномов                        528        Правило Горнера                             529        Табулирование значений полинома             531        Производные и замена переменной             532        Адаптация коэффициентов                     533        Цепочки полиномов                           537        Билинейные формы                            549, 558

4.7     ОПЕРАЦИИ СО СТЕПЕННЫМИ РЯДАМИ               569        Итерация рядов                              574, 577

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

Код:

Код:

Кнут Д. - Искусство программирования том 3 (2-е издание) - 2001ОГЛАВЛЕНИЕ

        От издателей русского перевода                1        О книге "Искусство программирования"          2        От редактора перевода                         4        Предисловие                                   5        Предисловие ко второму изданию                6        Примечания к упражнениям                      8

Глава 5 СОРТИРОВКА                                   12, 16, 17

5.1     КОМБИНАТОРНЫЕ СВОЙСТВА ПЕРЕСТАНОВОК          225.1.1   Инверсии                                     22, 285.1.2   Перестановки мультимножества                 33, 425.1.3   Серии                                        46, 565.1.4   Диаграммы и инволюции                        59, 76

5.2     ВНУТРЕННЯЯ СОРТИРОВКА                        85        Сортировка посредством подсчёта              87, 915.2.1   Сортировка путём вставок                     92        Метод простых вставок                        92        Бинарные и двухпутевые вставки               94        Метод Шелла                                  95        Анализ метода Шелла                          98        Вставка в список                            108        Сортировка с вычислением адреса             111, 1155.2.2   Обменная сортировка                         119        Метод пузырька                              119        Анализ метода пузырька                      121        Модификация метода пузырька                 123        Параллельная сортировка Бэтчера             124        Быстрая сортировка                          127        Анализ метода быстрой сортировки            132        Обменная поразрядная сортировка             137        Асимптотические методы                      143, 1485.2.3   Сортировка посредством выбора               153        Усовершенствования простого выбора          155        Выбор из дерева                             156        Пирамидальная сортировка                    160        Наибольший из включённый первым исключается 164        Связанное представление приоритетных                                           очередей 165        Сравнение методов работы с приоритетными                                          очередями 166        Анализ пирамидальной сортировки             168, 1715.2.4   Сортировка методом слияния                  174, 1835.2.5   Сортировка методом распределения            185, 194

5.3     ОПТИМАЛЬНАЯ СОРТИРОВКА                      1975.3.1   Сортировка с минимальным числом сравнений   197        Оптимизация в наихудшем случае              199        Более глубокий анализ                       204        Среднее число сравнений                     209, 2115.3.2   Слияние с минимальным числом сравнений      214        Определение нижних оценок                   216        Верхние оценки                              220, 2225.3.3   Выбор с минимальным числом сравнений        225, 2355.3.4   Сети сортировки                             238        Сети с минимальным числом сравнений         244        Сети с минимальным выбором                  246        Битонная сортировка                         249        Сети выбора                                 250, 253, 263

5.4     ВНЕШНЯЯ СОРТИРОВКА                          267, 2715.4.1   Многопутевое слияние и выбор с замещением   271        Дерево "проигравших"                        272        Получение начальных значений серий                    посредством выбора с замещением 274        Преобразование серий с задержкой            278        Натуральный выбор                           279        Анализ выбора с замещением                  280, 2825.4.2   Многофазное слияние                         287        Более детальный анализ                      293        А как обстоит дело с временем перемотки?    299        Расщепление лент                            301, 3055.4.3   Каскадное слияние                           308        Начальное распределение серий               309        Анализ каскадного слияния                   314        Модификация каскадной сортировки            318, 3185.4.4   Чтение ленты в обратном направлении         320        Обратное чтение в многофазном слиянии       321        Оптимальные схемы слияния                   323, 329, 3315.4.5   Осциллирующая сортировка                    333        Прямое чтение                               336, 3395.4.6   Практическая реализация слияния на лентах   339        Как работает НМЛ                            339        Сравнительный анализ схем слияния           346        Оценка времени выполнения                   355        Несколько дополнительных замечаний          361        Слияние с меньшим числом буферов            366, 3685.4.7   Внешняя поразрядная сортировка              369        Обратное чтение                             373        Имеет ли поразрядная сортировка преимущество                                     перед слиянием 374, 3745.4.8   Сортировка с двумя лентами                  375        Применение быстрой сортировки               367        Поразрядная сортировка                      378        Имитация дополнительных лент                379        Одноленточная сортировка                    380, 3835.4.9   Диск и барабаны                             384        Способы сокращения времени ожидания         386        Барабаны: случай, когда поиск не нужен      386        Влияние времени поиска                      389        Подробности об оптимальных деревьях         393        Ещё один способ распределения буферов       395        Использование сцепления                     396        Пересмотренный вариант прогнозирования      397        Использование нескольких дисков             398        Рандомизированное разделение                399        Поможет ли сортировка ключей?               402, 404

5.5     РЕЗЮМЕ, ИСТОРИЯ И БИБЛИОГРАФИЯ              409        Ранние разработки                           413        Последние достижения                        419, 420

Глава 6 ПОИСК

6.1     ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК                      426        Частота обращений                           429        "Самоорганизующийся файл"                   432        Поиск на ленте с неравными записями         433, 435

6.2     ПОИСК ПУТЁМ СРАВНЕНИЯ КЛЮЧЕЙ                4396.2.1   Поиск в упорядоченной таблице               439        Бинарный поиск                              439        Представление в виде дерева                 441        Дальнейший анализ бинарного поиска          443        Важное изменение                            444        Поиск Фибоначчи                             447        Интерполяционный поиск                      449        История и библиография                      450, 4536.2.2   Поиск по бинарному дереву                   456        А как насчёт наихудшего варианта?           460        Сорировка путём вставки в дерево            461        Удаление                                    462        Частота обращений                           465        Оптимальные бинарные деревья поиска         466        Оптимальные деревья и энтропия              473        Алгоритм Гарсия-Воча                        477        История и библиография                      484, 4856.2.3   Сбалансированные деревья                    489        Представление линейных списков              502        Удаление, конктенация и другие операции     504        Альтернативы AVL-деревьям                   507, 5106.2.4   Сильноветвящиеся деревья                    513        В-деревья                                   515        Усовершенствования и изменения              518, 522

6.3     ЦИФРОВОЙ ПОИСК                              524        Бинарный цифровой поиск                     528        Итоги анализа                               539, 539

6.4     ХЕШИРОВАНИЕ                                 546        Хеш-функция                                 548        Разрешение коллизий методом "цепочек"       554        Разрешение коллизий методом окрытой                                          адресации 559        Изменение Брента                            565        Удаления                                    567        Анализ алгоритмов                           568        Анализ оптимальности                        573        Внешний поиск                               575        Сравнение методов                           579        История                                     581, 583

6.5     ВЫБОРКА ПО ВТОРИЧНЫМ КЛЮЧАМ                 594        Инвертированные файлы                       596        Геометрические данные                       598        Составные атрибуты                          602        Бинарные атрибуты                           603        Кодирование методом наложения               605        Комбинаторное хеширование                   609        Обобщённые лучи (tries)                     612        Сбалансированные схемы                      612        Краткая история и библиография              614, 615

        ПРИЛОЖЕНИЕ А        ТАБЛИЦЫ ЗНАЧЕНИЙ НЕКОТОРЫХ КОНСТАНТ         620

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

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

Описание:Искусство программирования (англ. The Art of Computer Programming) — фундаментальная монография известного американского математика и специалиста в области компьютерных наук Дональда Кнута, посвященная рассмотрению и анализу важнейших алгоритмов, используемых в информатике. В 1999 году книга была признана одной из двенадцати лучших физико-математических монографий столетия.Проект написания книги был начат автором в 1962. Изначально планировалось выпустить её одним томом, но объём материала оказался столь большим, что количество томов было увеличено до семи. Первые три тома были изданы достаточно быстро: том 1 в 1968, том 2 в 1969, и том 3 в 1973, после чего последовал перерыв до февраля 2005 года, в котором автор опубликовал первую часть четвёртого тома. Было принято решение выпускать остальные части четвёртого тома приблизительно по две в год, после чего официально издать весь четвёртый том.

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

Дональд Эрвин Кнут (англ. Donald Ervin Knuth, родился 10 января 1938) — американский учёный, почётный профессор Стэнфордского университета и нескольких других университетов в разных странах, иностранный член Российской академии наук, преподаватель и идеолог программирования, автор 19 монографий (в том числе ряда классических книг по программированию) и более 160 статей, разработчик нескольких известных программных технологий. Автор всемирно известной серии книг, посвящённой основным алгоритмам и методам вычислительной математики, а также создатель настольных издательских систем TEX и METAFONT, предназначенных для набора и вёрстки книг, посвящённых технической тематике (в первую очередь — физико-математических).

Более подробно -> http://ru.wikipedia.org/wiki/%D0%94._%D0%9A%D0%BD%D1%83%D1%82

За предоставленные оглавления книг спасибо Alexandr_1977!

загрузка...

rutorka.net

Как создавалось «Искусство программирования» (33,38,39/97) / Блог компании Edison / Хабр

«Я должен был закончить книгу, прежде чем родится мой сын. Теперь ему 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 видеороликов с историями Дональда КнутаПлейлист на Youtube

1. Family history 2. Learning to read and school 3. My mother 4. My parents' finances 5. Interests in high school 6. Being a nerd of nerds at high school 7. My sense of humor 8. The Potrzebie System of Weights and Measures 9. Feeling the need to prove myself 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. Inception of The Art of Computer Programming 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. The Art of Computer Programming: underestimating the size of the... 39. The successful first release of The Art of Computer Programming 40. Inspiration to write Surreal Numbers 41. Writing Surreal Numbers in a hotel room in Oslo 42. Finishing the Surreal Numbers 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. My advice to young people 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, которая разрабатывает веб-интерфейс для управления радио-релейной станцией, а так же проектирует и разрабатывает ПО для записи и анализа вариабельности сердечного ритма.

habr.com

Дональд Кнут / Хабр

Дональд Эрвин Кнут — американский учёный, почётный профессор Стэнфордского университета и нескольких других университетов в разных странах, преподаватель и идеолог программирования, автор 19 монографий (в том числе ряда классических книг по программированию) и более 160 статей, разработчик нескольких известных программных технологий. Автор всемирно известной серии книг, посвящённой основным алгоритмам и методам вычислительной математики, а также создатель настольных издательских систем TEX и METAFONT, предназначенных для набора и вёрстки книг, посвящённых технической тематике (в первую очередь — физико-математических). Дональд Кнут родился 10 января 1938 года в Милуоки (штат Висконсин)-Его отец преподавал бухгалтерский учет в университете и занимался также дома, в подвале, печатным делом. Ребенком Кнут с удовольствием играл с калькулятором отца, который мог перемножать десятизначные числа, но у него уходило от десяти до двадцати секунд, чтобы напечатать ответ.

Кнут вспоминает, как он пытался извлечь квадратный корень из десяти, пытался и ошибся. Открыв, что ответ находится между 3,16 и 3,17, он сделал заключение, что число должно иметь истинное значение п, а не 3,14, как говорилось в его учебнике. Вскоре он понял, что его заключение было ошибочным.

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

Физика также ему нравилась, и он разрывается между ней и музыкой — он серьезно обучался игре на пианино, сам написал несколько произведений. Кнут признает, что у него комплекс неполноценности. Это объясняет, говорит он, то, что он всегда много работал. В старших классах Милуокской лютеранской высшей школы он беспокоился, что низкие оценки по математике могут помешать его поступлению в колледж, но это была непонятная озабоченность, поскольку он закончил школу с самым высоким коэффици-ентом за все времена — 97,5%.

В 1956 году он поступил в Кейский Технологический институт в Кливленде. На первом году обучения он занялся высшей математикой. Снова из-за страха, что не справится, Кнут в дополнительное время с рвением изучал дифференциальное и интегральное исчисление и аналитическую геометрию.

Во время каникул после первого курса Кнут впервые занялся работой с компьютером. У него было задание на лето — построить графики для статистиков Кейса. В соседней комнате находилась новая машина IBM 650. Кнут так загорелся ею, что посвятил «Искусство программирования» компьютеру IBM 650, установленному в Кэйском технологическом институте, в память о многих приятных вечерах. Некоторые из его преподавателей советовали ему держаться в стороне от компьютеров, утверждая, что это ни к чему хорошему не приведет. Но любопытство взяло верх, он проводил ночи напролет с компьютером.

Кнут с легкостью оставил физику. Его лабораторные работы, казалось, не приносили удовлетворения, он ронял детали на пол и часто оказывался последним. Сварка оказалась катастрофой: при росте 6 футов и 4 дюйма он был слишком высоким для сварочных столов, и ему невозможно было наблюдать за работой, кроме того, очки ему не подходили.

Кнут добился успехов, используя компьютер для оценки игры баскетбольной команды, менеджером которой он являлся. Он выработал сложную формулу для ранжирования игроков, рассчитывая вклад каждого в игру, не только по количеству очков, которые он принес команде. Кнут обычно сидел за компьютером IBM 650 и подводил статистику игры, в то время, когда тренер стоял рядом. Используя программу Д. Кнута, тренер мог определить Истинный вклад каждого в игру и в соответствии с этим использовать игроков. Оказалось также, что данная программа стимулировала игроков работать с большей отдачей. В 1960 году Кэйский институт выиграл чемпионат лиги, а магическая формула Кнута неожиданно была опубликована в «Walter Cronkite's Sunday» и в «Newsweek».

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

В январе 1962 года издательство «Addison-Wesley» предложило Кнуту написать книгу по компиляторам. Он принял это предложение.

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

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

Проведя напряженные дни и ночи над реализацией семитомного проекта, Кнут испытал несколько приступов язвы летом 1967 года. Как вспоминает он, это случилось на середине «алгоритма Евклида», на 333 странице второго тома.

Данные издания, как оказалось, имели наибольший спрос из всех книг, продаваемых «Addison-Wesley». В середине 80-х годов две тысячи экземпляров каждого из трех томов расходились в течение месяца, и эта цифра не менялась с середины 70-х годов. Работа была переведена на китайский, румынский, японский, испанский и русский, планировалось издание на португальском и венгерском. Кнут становится все более знаменитым: в 1979 г. в возрасте 41 года он получает из рук президента Дж. Картера Национальную медаль в области науки за свою работу по алгоритмам.

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

Может показаться неправдоподобным, но Д. Кнут также пишет фантастические вещи. Его новелла «Сюрреалистические числа: как два бывших студента занялись чистой математикой и нашли полное счастье» была опубликована в издательстве «Addison-Wesley» в 1974 году. В книге рассказывается об исследовании новой системы чисел, открытой в Кэмбриджском университете Дж. Конвэем. Кнут узнал о данной системе от самого Конвэя в 1972 году. Один журналист отметил, что впервые значимое открытие в математике описывается сначала в научной фантастике. Кнут написал данную книгу не для того, чтобы проповедовать теорию Конвэя, а чтобы объяснить, как человек может создать такую теорию.

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

Кнут изобрел ТеХ, первую издательскую систему, а также METAFONT, систему, которая использует классическую математику для придания внешнего вида шрифтам. ТеХ был назван одним из наиболее важных изобретений в истории печатания книг. Некоторые сравнивали его по значению с Библией Иоганна Гуттенберга, что смутило Кнута.

ТеХ позволяет наборной машине размещать буквы и знаки на странице со значительной гибкостью и эстетичным качеством.

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

Кнут ввел обе программы в открытое пользование: ни он, ни Стэнфордский университет не заработали на них ни гроша. Он написал программы, как он говорит, из любви к книгам и для достижения необходимой эстетики.

Когда Кнут сверстал второй том «Искусства программирования», используя METAFONT и ТеХ, результат был лучше, но не идеальным. Плохо получались числа. Так он потратил еще пять лет, работая с лучшими дизайнерами по графике, для того, чтобы создать новые системы и наиболее полно использовать их потенциал. Летом 1986 года разработки Кнута по типографии были завершены, и вышел пятитомник «Компьютеры и набор знаков». Первый том посвящен ТеХ; второй содержит полный источник кодов ТеХ; третий и четвертый, соответственно, посвящены METAFONT и полному источнику кодов для него; пятый том содержит 500 с лишним примеров программирования по METAFONT.

В 1986 году на приеме в издательстве «Addison-Wesley», устроенном в его честь, ему задали вопрос: «Будет ли завершен его семитомник, будут ли дописаны четыре недостающих тома?» Он ответил, что их написание заняло бы еще двадцать лет.

Прошло тринадцать лет. В 1999 году профессор Кнут заявил, что к существующим трем томам он намерен добавить еще два тома. Кроме того, он решил заменить виртуальную модель компьютера MIX 1009 (модель, похожую на реальные компьютеры конца 60-х — начала 70-х годов), на языке которого написаны большинство алгоритмов первых трех томов, на новую модель — 64-разрядный процессор MMIX 2009 с RISC-архитектурой. В следующих изданиях «Искусство программирования» примеры будут приводиться на языке ассемблера MMIX.

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

Номер 2009 является средним арифметическим номеров четырнадцати процессоров. В их числе — CRAY I, IBM 701, Alpha 21264, MIPS 4000, StrongArm 110, Sparc 64 и др. Логическая модель MMIX довольно подробно описывает поведение настоящего процессора. Например, для каждой команду указано число тактов, требующихся для выполнения, определено поведение процессора в таких ситуациях, как неверное предсказание ветвления или промах кэша. В модели имеется набор изменяемых параметров, поэтому на самом деле MMIX — это целое семейство совместимых процессоров. Профессор Кнут намерен реализовать метасимулятор для всего семейства, чтобы можно было менять параметры модели и исследовать поведение программ.

Дональд Кнут уже разработал архитектуру процессора, простой симулятор и ассемблер. Первая редакция описания набора команд была опубликована в феврале, а четвертая редакция введения в MMIX вышла в конце июня. Теперь предстоит перенос всего накопленного программного фонда старого MIX на новый RISC-процессор MMIX. Дональд Кнут приглашает к сотрудничеству добровольцев со всего мира, прежде всего студентов.

habr.com

О книгах Дональда Кнута | Блог Хеллера

Хватит о политике, пока меня не посадили. Лучше о книгах.

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

О контенте. Первый том вообще не нужен. Значительная его часть посвящена ассемблеру MIX. Он конечно язык сравнительно простой, но объяснять алгоритмы на примере ассемблерного, а не псевдокода, как-то не правильно на мой взгляд (тем более что современные настоящие ассемблеры даже проще, чем кнутовский). Я лично прочитал про сам MIX, но дальше все, где этот язык фигурировал, пропускал, потому что дикая дурь. Может быть конечно во времена, когда Кнут писал книгу, это и было оправданно, но сегодня это выглядит как крайне неудачный ход.

Еще в первом томе есть немного математики и немного про деревья. Математическая составляющая тоже не особо радует — на 90% это «синтаксическая математика», где все сводится к механическим операциям. Действительно интересных задач почти нет. Да и в общем-то математика там очень детская и какая-то несерьезная. Книга излагает лишь несколько простейших результатов о сочетаниях и сравнениях по модулю на школьном уровне. Из-за этого поверхностного знакомства с математикой многие доказательства оказываются на порядок сложнее, чем они могли бы быть. Даже базовые вещи вроде O-нотации описываются в главах со звездочкой и практически не используются. (Как я понимаю, книга писалась для первого курса и продвинутых школьников).

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

Существенно, что многие алгоритмы даются просто «как есть», а потом уже каким-нибудь формальным методом доказывается (чаще по индукции), что эти алгоритмы работают как надо. Тоже мало приятного, так как идея, которая приводит к алгоритму, не раскрывается, ну а стало быть и понимание принципа алгоритма не может считаться полным.

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

Вторая половина второго тома посвящена работе с полиномами. Ну, наверное кому-то оно надо, но не мне.

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

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

В общем, не советую.

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

heller.ru

Кнут Дональд Эрвин. Искусство программирования. Том 4 А. Комбинаторные алгоритмы. Часть 1

Искусство программирования. Том 4 А. Комбинаторные алгоритмы. Часть 1

Эта книга представляет собой том 4 А, поскольку сам том 4 является многотомником. Комбинаторный поиск - богатая и важная тема, и Кнут приводит слишком много нового, интересного и полезного материала, чтобы его можно было разместить в одном или двух (а может быть, даже в трех) томах. Одна эта книга включает около 1500 упражнений с ответами для самостоятельной работы, а также сотни полезных фактов, которые вы не найдете ни в каких других публикациях. Том 4 А определенно должен занять свое место на полке рядом с первыми тремя томами этой классической работы в библиотеке каждого серьезного программиста. В этом томе рассматриваются методы, позволяющие компьютерам эффективно работать с задачами гигантского размера. Рассматриваемый материал начинается с булевых функций и технологий и трюков работы с битами, затем всесторонне рассматривается генерация всех кортежей и перестановок, всех сочетаний и разбиений, и всех деревьев. Этот многотомный труд широко известен как полное изложение информатики. В течение десятилетий первые три тома служили бесценным источником информации по теории ипрактике программирования для студентов, теоретиков и практиков. Ученые восхищались красотой и изяществом анализа Кнута, в то время как практикующие программистыуспешно применяли его "поваренную книгу" для решения ежедневных задач. Об авторе Дональд Э. Кнут - автор всемирно известной серии книг, посвященной основным алгоритмам и методам вычислительной математики, а также создатель настольных издательских систем TEX и METAFONT, предназначенных для верстки физико-математической литературы. Его перу принадлежат 26 книг и более 160 статей. Дональд Кнут является почетным профессором Станфордского университета в области программирования и вычислительной математики. В настоящее время он полностью занят написанием новых книг серии Искусство программирования. Работу над первым томом он начал еще в 1962 году, сразу после окончания Калифорнийского технологического института (California Institute of Technology). Профессор Кнут удостоен многочисленных премий и наград, среди которых можно отметить ACM Turing Award, Medal of Science президента Картера и ASM Steele Prize за серию научно-популярных статей. В ноябре 1996 года Дональд Кнут был удостоен престижной награды Kyoto Prize в области передовых технологий. Отзывы Уровень первых трех томов столь высок, и в них проявлено столь широкое и глубокое знакомство с искусством программирования, что вполне достаточным обзором будущих томов будет краткое" Вышел том n Искусства программирования Кнута" .- Data Processing Digest Вышел том n Искусства программирования Кнута, где n = 4 А. В этом долгожданном новом томе старый мастер уделяет внимание как ряду своих издавна любимых тем - широкословным вычислениям и комбинаторной генерации (исчерпывающему перечислению фундаментальных комбинаторных объектов, таких как перестановок, разбиений или деревьев), так и более поздним увлечениям, таким как бинарные диаграммы решений. Признаки качества, отличающие его прежние тома, проявились и в новом томе: детальное описание основ, иллюстрация хорошо подобранными примерами, иногда экскурсы в более эзотеричные темы и задачи на острие ведущихся исследований; безупречный стиль изложения, приправленный долей юмора; обширные наборы упражнений - все с решениями или полезными указаниями; должное внимание историческим вопросам; реализация множества алгоритмов в его классическом пошаговом стиле. На каждой странице книги имеется удивительное количество информации. Очевидно, Кнут долго и тщательно размышлял о том, какие результаты являются наиболее центральными и важными, и о том, как наиболее интуитивно понятно и кратко изложить этот материал. Поскольку области, охваченные этим томом, увеличились с момента первых черновых заметок о них просто взрывным образом, это просто удивительно - как он сумел втиснуть столь тщательное рассмотрение в такой небольшой объем.-Фрэнк Раски, (Frank Ruskey), факультет информатики университета Виктории (Department of Computer Science, University of Victoria)

Издательство: "Вильямс" (2016)

ISBN: 978-5-8459-1980-9

Купить за 6050 руб в Лабиринте

dic.academic.ru

Книга - кнут - Большая Энциклопедия Нефти и Газа, статья, страница 1

Книга - кнут

Cтраница 1

Книга Кнута является первым существенным шагом в этом отношении. Она посвящена анализу наиболее фундаментальных нечисловых алгоритмов.  [1]

Книги Кнута ( Knuth) покрывают анализ средней производительности более полно и являются официальным источником определенных свойств многих алгоритмов. Книги Тонне, Баэ-Ят ( Gonnet, Baez-Yates) и Кормен, Лейзерсон, Ривест ( Cormen, Leisorson, Rivest) являются более современными работами. Обе они включают обширный список ссылок на исследовательскую литературу.  [2]

Книги Кнута ( Knuth), в особенности 1 - й и 3 - й тома, остаются авторитетным источником информации по свойствам элементарных структур данных.  [3]

Книга Кнута [ 1973а ] представляет собой энциклопедическое руководство по методам сортировки. Хейдиан, Соубел [1969] и Пратт, Яо [1973] исследуют число сравнений, необходимое для нахождения некоторых порядковых статистик.  [4]

В книге Кнута [9] обсуждается более сложный аддитивный метод.  [5]

Хотя чтение любой части книги Кнута доставляет массу удовольствия, представляется, чго обсуждаемому вопросу наиболее соответствует материал разд.  [6]

Раздел 4.1 второго тома книги Кнута содержит основательное введение в позиционные числовые системы и их историю. В главе 2 первого тома этой книги кратко изложено почти все, что известно о списках, стеках, очередях и деревьях.  [7]

В настоящее время лучшим пособием по структурам данных является книга Кнута ( Knuth D.  [8]

ЕЕцямн по практическому крнмскгцию - K - n Jti: vi4cCKHc MLIOJIM подробна изложены н книге Кнута. Более новые метолы описаны в других книгам в них же при РОДЯТСЯ ссылки на л ругую литературу.  [9]

Алгоритм Тоома - - Кука весьма сложен, поэтому мы не будем подробно объяснять его; за этим можно обратиться к книге Кнута. Все же необходимо сообщить основные идеи и обозначения. Длинные числа должны быть как-то представлены; будем писать [ р, и ] ] для обозначения числа и из р битов. Вероятно, внутреннее представление [ р, и ] будет некоторой разновидностью списка или цепочки.  [10]

Книга Грэм, Кнут, Паташник ( Graham, Knuth, Patshnik) рассказывает об областях математики, которые обычно встречаются при анализе алгоритмов; этот же материал разбросан и в упомянутых ранее книгах Кнута. Книга Седжвика и Флажоле представляет собой исчерпывающее введение в предмет.  [11]

Материал, изложенный там, представляет собой энциклопедический подход к проблеме в целом. Раздел 5.5 книги Кнута содержит отличное сравнение методов сортировки и краткую историю предмета сортировки.  [12]

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

Простейший способ реализации механизма посылки / получения - воспользоваться, если это возможно, соответствующим механизмом базовой вычислительной системы. Если необходимо построить свой собственный механизм, то в работе Кнотта [11] можно найти примеры сопряжений, а в книге Кнута [12] - - соответствующие алгоритмы.  [14]

Страницы:      1

www.ngpedia.ru