Проект написания книги был начат автором в . Изначально планировалось выпустить её одним томом, но объём материала оказался столь большим, что количество томов было увеличено до семи. Первые три тома были изданы достаточно быстро: том 1 в 1968 году , том 2 в 1969 году , и том 3 в 1973 году , после чего последовал перерыв до февраля 2005 года , в котором автор опубликовал первую часть четвёртого тома. Было принято решение выпускать остальные части четвёртого тома приблизительно по две в год отдельными выпусками, после чего официально издать весь четвёртый том. На протяжении 2005-2009 годов были изданы выпуски 0, 1, 2, 3 и 4, а в 2011 году был выпущен том 4А, в который вошла информация из этих выпусков. Также в 2005 году был выпущен выпуск 1 «MMIX - RISC-компьютер для нового тысячелетия», информация из которого войдёт в новое, четвёртое издание первого тома. В 2015 году был издан выпуск 6 Satisfiability , представляющий собой среднюю треть будущего тома 4B.

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

Энциклопедичный YouTube

• 1 / 5

  В качестве признанного эксперта по созданию компиляторов , в 1962 году Кнут начал писать книгу по их проектированию. Вскоре он осознал, что охват материала должен быть намного шире. В июне 1965 года он закончил написание первой версии того, что он изначально хотел издать одной книгой из двенадцати разделов. Объём рукописного текста составил 3000 страниц. По расчётам Кнута, этот объём должен был уместиться на 600 страницах печатного текста, но, как сообщил ему его издатель, реальный объём составил бы 2000 страниц. В связи с этим структура книги была пересмотрена в пользу нескольких томов, по 1-2 раздела каждый. С тех пор, в связи с постоянным ростом материала, было решено, что четвёртый том также будет разбит на отдельные книги: 4A, 4B, 4C, а возможно, и 4D. Но и это разделение по-видимому не будет окончательным, так как разделы 7.1 и 7.2.1 уже в сумме занимают более 650 страниц.

  В 1976 году Кнут подготовил второе издание второго тома, что потребовало повторного набора . Но типографское оформление (монотипия), использовавшееся в первом издании, к этому моменту уже было недоступно. Чтобы избежать подобных огорчений в будущем, в 1977 году Кнут начал разрабатывать собственную типографскую систему компьютерного набора. По его расчётам, работа должна была занять не более шести месяцев, но потребовалось около десяти лет, прежде чем она была завершена . Система получила название TeX , и в настоящее время используется для верстки всех томов «Искусства программирования». Кроме того, впоследствии, TeX стал фактическим стандартом для написания статей и монографий по естественным наукам.

  Как и другие книги Кнута, «Искусство программирования» отмечена его «фирменным знаком»: за каждую ошибку, найденную в тексте, автор выплачивает один шестнадцатеричный доллар , то есть $2,56 (0x100 центов , в системе счисления по основанию 16). Другой отличительной особенностью книги является обилие упражнений для самостоятельного выполнения, разной степени сложности, начиная от простых задачек «для разогрева» и заканчивая открытыми проблемами. Сложность каждого упражнения оценена по числовой шкале от 0 до 50. Так, в ранних изданиях числом 50 была отмечена Великая теорема Ферма , но в третьем издании эта оценка «девальвировала» до 45, так как к этому моменту её доказательство уже перестало быть открытой проблемой.

  Сводка условных обозначений для третьего тома, 1978 год «Сортировка и поиск» (слева - оценка, справа - краткое объяснение)

  • Чёрный треугольник - Рекомендуется
  • М - С математическим уклоном
  • ВМ - Требует знания «высшей математики»
  • 00 - Требует немедленного ответа
  • 10 - Простое (на 1 минуту)
  • 20 - Средней трудности (на 15 мин)
  • 30 - Повышенной трудности
  • 40 - Для «матпрактикума»
  • 50 - Исследовательская проблема

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

  • Том 1. Основные алгоритмы.
    • Глава 1. Основные понятия.
    • Глава 2. Информационные структуры.
  • Том 2. Получисленные алгоритмы.
    • Глава 3. Случайные числа.
    • Глава 4. Арифметика.
  • Том 3. Сортировка и поиск.
    • Глава 5. Сортировка.
    • Глава 6. Поиск.
  • Том 4. Комбинаторные алгоритмы.
    • Глава 7. Комбинаторный поиск.
    • Глава 8. Рекурсия.
  • Том 5. Синтаксические алгоритмы.
    • Глава 9. Лексикографический поиск.
    • Глава 10. Синтаксический поиск.
  • Том 6. Теория языков.
  • Том 7. Компиляторы.

  Фактически эта схема была реализована вплоть до третьего тома включительно.

  В настоящий момент издан том 4А, который содержит первые разделы 7 главы. Новые разделы планируется первоначально издавать отдельными выпусками (приблизительно по 128 страниц), ориентировочно по два выпуска в год (перед выходом тома 4А подобным образом были изданы выпуски 0, 1, 2, 3 и 4).

  Машинно-ориентированный язык примеров

  Примеры программ, приведённые в книге, используют «MIX-ассемблер», предназначенный для работы на гипотетическом MIX-компьютере. В третьем издании морально устаревший MIX был заменён на MMIX , имеющий полноценную RISC -архитектуру. Существует программное обеспечение , обеспечивающее эмуляцию (M)MIX-машины на стандартных IBM-совместимых компьютерах. GNU Compiler Collection имеет возможность компиляции C/C++ кода на целевую архитектуру MMIX.

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

  Критика

  Основной чертой монографии Кнута, выгодно отличающей её от других книг, посвящённых программированию, является исключительно высоко поднятая планка качества материала и академичности изложения, а также глубина анализа рассматриваемых вопросов. Благодаря этому она стала настоящим бестселлером и настольной книгой каждого профессионального программиста . Журнал American Scientist включил «Искусство программирования» в список 12 лучших физико-математических монографий XX-го столетия вместе с работами Дирака по квантовой механике , Эйнштейна по теории относительности , Рассела и Уайтхеда по основаниям математики и немногочисленными другими .

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

  Издания

  Оригинальные

  Третье (текущее)

  В порядке возрастания номеров томов:

  • Volume 1: Fundamental Algorithms . Third Edition (Reading, Massachusetts: Addison-Wesley, 1997), xx+650pp. ISBN 0-201-89683-4
  • Volume 1, Fascicle 1: MMIX - A RISC Computer for the New Millennium . (Addison-Wesley, February 14, 2005) ISBN 0-201-85392-2 (will be in the fourth edition of volume 1)
  • Volume 2: Seminumerical Algorithms . Third Edition (Reading, Massachusetts: Addison-Wesley, 1997), xiv+762pp. ISBN 0-201-89684-2
  • Volume 3: Sorting and Searching . Second Edition (Reading, Massachusetts: Addison-Wesley, 1998), xiv+780pp.+foldout. ISBN 0-201-89685-0
  • Volume 4A: Combinatorial Algorithms, Part 1 (Upper Saddle River, New Jersey: Addison-Wesley, 2011), xvi+883pp. ISBN 0-201-03804-8
  • Volume 4, Fascicle 6: Satisfiability . (Addison-Wesley Professional, 2015), xiii+310pp. ISBN 978-0-13-439760-3

  Предыдущие

  По дате публикации:

  • Volume 1 , first edition, 1968. 634pp. ISBN 0-201-03801-3 .
  • Volume 2 , first edition, 1969, xi+624pp, ISBN 0-201-03802-1 .
  • Volume 3 , first edition, 1973, xi+723pp+centerfold, ISBN 0-201-03803-X
  • Volume 1 , second edition, 1973, xiii+634pp, ISBN 0-201-03809-9 .
  • Volume 2 , second edition, 1981, xiii+ 688pp. ISBN 0-201-03822-6 .
  • Volume 4, Fascicle 2: Generating All Tuples and Permutations , (Addison-Wesley, February 14, 2005) v+127pp, ISBN 0-201-85393-0
  • Volume 4, Fascicle 3: Generating All Combinations and Partitions . (Addison-Wesley, July 26, 2005) vi+150pp, ISBN 0-201-85394-9
  • Volume 4, Fascicle 4: Generating all Trees - History of Combinatorial Generation , (Addison-Wesley, February 6, 2006) vi+120pp, ISBN 0-321-33570-8
  • Volume 4, Fascicle 0: Introduction to Combinatorial Algorithms and Boolean Functions , (Addison-Wesley Professional, April 28, 2008) vi+240pp, ISBN 0-321-53496-4
  • Volume 4, Fascicle 1: Bitwise tricks & techniques; Binary Decision Diagrams (Addison-Wesley Professional, March 27, 2009) viii+260pp,
  27 декабря 2011 в 13:32

  Искусство программирования?

  • Программирование

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

  Начало

  Так сложилось, что на текущем месте работы программисты предоставлены самим себе. То есть, конечно, кодят на благо предприятия, но совершенно бесконтрольно, вплоть до отсутствия банального тестера. ТЗ даже на «тяжелые» программы редко превышает объема в три листа А4 (один из которых - подписи всех причастных).

  Звонки по поводу проблем с ПО направляются напрямую программистам. С этого всё и началось.
  
  Я обратил внимание, что количество звонков моему коллеге (человеку, работающему по специальности и конкретно на этом месте дольше меня на несколько лет) на порядок (без преувеличений) превышает количество звонков по моему ПО. При этом звонки как правило более «тяжелые». Распространенность и трудоемкость наших продуктов примерно одинакова.

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

  Опус о творческих личностях

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

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

  Действия таких людей имеют определенный вектор, но его параметры задаются не числами с плавающей точкой, а направлением «зюйд-зюйд-вест». Это касается не только походов в магазин (покупать что-то по списку с такими людьми просто нереально), но и вообще всего, включая творчество.

  При работе над произведением художник/музыкант обычно начинает с этого самого «вектора зюйд-зюйд-вест» - с определенного настроения, концепции (рожденной внутри или выданной заказчиком, это в данном случае не столь важно). Конечный результат, в большинстве случаев, представляется весьма смутно. Справедливости ради отметим, что это - львиная доля удовольствия от творчества - делать как делается. Это, в сущности, и есть попытка «выразить себя».

  Творческие программисты

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

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

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

  Мораль сей басни

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

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

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

  Краткий обзор легендарной монографии Дональда Кнута «Искусство программирования» — фундаментального труда в области компьютерных наук.
  

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

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

  Книга изобилует примерами для символьных вычислений, численных методов, методов имитации и многого другого.

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

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

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

  

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

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

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

  

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

  Здесь автор рассказывает о внутренней и внешней памяти, о построении больших и малых баз данных и работе с ними. Для всех рассмотренных в книге алгоритмов приводится сравнительный анализ их эффективности. Специальный раздел посвящен методам оптимальной сортировки и описанию новой теории перестановки и универсального хеширования.

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

  

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

  Название: Искусства программирования - том 1.

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

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

  Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
  Скачать книгу Искусство программирования - том 1 - Кнут Д. Э. - fileskachat.com, быстрое и бесплатное скачивание.

  Скачать djvu
  Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.

  Аннотация к книге Искусство программирования, тома 1-3 :
  Многие знают, что программирование - это не только сложная умственная работа, но и творческий процесс. Автор этой книги — Дональд Эрвин Кнут — профессор Стэнфордского университета, создал множество книг по математике и компьютерной тематике. Известность ученому принес ставший знаменитым труд «Искусство программирования», первый том которого был издан более 20 лет назад. В своей книге Дональд Кнут объясняет и анализирует основные алгоритмы, используемые в программировании. Это третье издание знаменитой серии книг «Искусство программирования».

  Данный релиз содержит 3 тома «Искусства программирования»:

  Искусство программирования. Том 1. Основные алгоритмы.
  Искусство программирования. Том 2. Получисленные алгоритмы.
  Искусство программирования. Том 3. Сортировка и поиск.

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

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

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