«Искусство программирования» — обзор легендарной серии книг


Оглавление (нажмите, чтобы открыть):

Серия «Искусство программирования»

Кнут – великий современный математик и теоретик программирования. Его «Искусство программирования для ЭВМ», «Конкретная математика» – просто образцы математической элегантности, строгости и привлекательности.

    • О компании
    • Контакты
    • Служба поддержки
    • Возврат
    • © ООО «ЛитРес»
    • Активировать купон
    • Публичная оферта
    • Политика обработки
      персональных данных
    • Согласие на получение рассылки
  • Сотрудничество
    • Издательствам
    • Авторам
    • Библиотекам
    • Партнёрам
    • Вебмастерам
  • Что почитать?
    • Бестселлеры
    • Скоро в продаже
    • Популярные авторы
    • Интервью с авторами
    • ЛитРес: Истории
    • ЛитРес в соц.сетях
    • Чтобы воспользоваться акцией, добавьте нужные книги в корзину. Сделать это можно на странице каждой книги, либо в общем списке:

      1. Нажмите на многоточие
        рядом с книгой
      2. Выберите пункт
        «Добавить в корзину»

      Лучшие книги Дональда Кнута

      ISBN: 5-8459-0080-8, 0-201-89683-4
      Год издания: 2007
      Издательство: Вильямс
      Серия: Искусство программирования
      Язык: Русский

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

      Первый том серии книг `Искусство программирования` начинается с описания основных понятий и методов программирования. Затем автор сосредоточивается на рассмотрении информационных…

      ISBN: 978-5-8459-1588-7, 0-201-55802-5
      Год издания: 2010
      Издательство: Вильямс
      Язык: Русский

      В основу данной книги положен одноименный курс лекций Станфордского университета. Название «конкретная математика» происходит от слов «КОНтинуальная» и «дисКРЕТНАЯ» математика. Назначение данной книги — обеспечить читателя техникой оперирования с дискретными объектами, что совершенно необходимо для математиков, работающих в области информатики. Книга ориентирована в первую очередь на практиков (хотя и теоретики найдут в ней много полезного), и изобилует массой конкретных примеров и упражнений. Конкретность изложения абстрактного материала — еще одно пояснение названия книги. Широта охвата столь различных тем в одной книге могла бы вызвать подозрения в некоторой легковесности, если бы не имена ее авторов — известных американских математиков. Тем не менее слово «легкий» к книге вполне применимо, так как стиль изложения достаточно далек от сухого академизма. Как признаются сами авторы, они считают математику развлечением, и они сделали все, чтобы читатели книги получили от ее прочтения не только знания, но и удовольствие.

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

      В основу данной книги положен одноименный курс лекций Станфордского университета. Название «конкретная математика» происходит от слов «КОНтинуальная» и «дисКРЕТНАЯ» математика.…

      ISBN: 5-8459-0082-4, 0-201-89685-0
      Год издания: 2005
      Издательство: Вильямс
      Серия: Искусство программирования
      Язык: Русский

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

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

      ISBN: 5-8459-0081-6, 0-201-89684-2
      Год издания: 2005
      Издательство: Вильямс
      Язык: Русский

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

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

      ISBN: 978-5-9963-1541-3
      Год издания: 2014
      Издательство: Бином. Лаборатория знаний
      Язык: Русский

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

      Для студентов, преподавателей и всех любителей математики.

      Захватывающая приключенческо-математическая история от известного и блестящего автора Дональда Кнута. Двое героев случайно находят камень с древними письменами и открывают для…

      ISBN: 978-5-8459-1744-7, 978-0-201-03804-0
      Год издания: 2012
      Издательство: Вильямс
      Язык: Русский

      Эта книга представляет собой том 4А, поскольку сам том 4 является многотомником. Комбинаторный поиск — богатая и важная тема, и Кнут приводит слишком много нового, интересного и полезного материала, чтобы его можно было разместить в одном или двух (а может быть, даже в трех) томах. Одна эта книга включает около 1500 упражнений с ответами для самостоятельной работы, а также сотни полезных фактов, которые вы не найдете ни в каких других публикациях. Том 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А. В этом долгожданном новом томе старый мастер уделяет внимание как ряду своих издавна любимых тем — широкословным вычислениям и комбинаторной генерации (исчерпывающему перечислению фундаментальных комбинаторных объектов, таких как перестановок, разбиений или деревьев), так и более поздним увлечениям, таким как бинарные диаграммы решений. Признаки качества, отличающие его прежние тома, проявились и в новом томе: детальное описание основ, иллюстрация хорошо подобранными примерами, иногда экскурсы в более эзотеричные темы и задачи на острие ведущихся исследований; безупречный стиль изложения, приправленный долей юмора; обширные наборы упражнений — все с решениями или полезными указаниями; должное внимание историческим вопросам; реализация множества алгоритмов в его классическом пошаг

      Эта книга представляет собой том 4А, поскольку сам том 4 является многотомником. Комбинаторный поиск — богатая и важная тема, и Кнут приводит слишком много нового, интересного и…

      «Искусство программирования» — обзор легендарной серии книг

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

      To be continued.

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

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

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

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

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

      В качестве признанного эксперта по созданию компиляторов , в 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,


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

      Что можно приготовить из кальмаров: быстро и вкусно

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

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

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

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

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

      ] Автор: Кнут Дональд Эрвин (Donald Ervin Knuth). Научное издание. Перевод с английского Р.М. Кузнец, О.А. Маховая, Н.В. Третьяков, Ю.В. Тюменцев, под редакцией И.А. Маховой. Художник И.И. Куликова.
      (Москва: Издательство «Мир», Издательство «ACT», 2003. — Серия «Библиотека издательских технологий»)
      Скан, обработка, формат Djv: . предоставил: Михаил, 2020

      • КРАТКОЕ ОГЛАВЛЕНИЕ:
        Предисловие редактора перевода (5).
        Предисловие (11).
        Ссылки на источники (16).
        Глава 1. Компьютерная типография (19).
        Глава 2. Математическая типография (36).
        Глава 3. Верстка абзацев (79).
        Глава 4. Сочетание текстов, читаемых справа налево и слева направо (167).
        Глава 5. Рецепты и дроби (187).
        Глава 6. Логотип системы TEX в различных шрифтах (192).
        Глава 7. Генерирование избранных страниц (194).
        Глава 8. Макро, написанные для Джил (196).
        Глава 9. Задача на субботнее утро (205).
        Глава 10. Упражнения к книге TEX: The Program (207).
        Глава 11. Мини-указатели для самодокументированных программ (235).
        Глава 12. Виртуальные шрифты. Развлечение для настоящих мастеров (256).
        Глава 13. Буква S (273).
        Глава 14. Мое первое знакомство с индийской письменностью (293).
        Глава 15. Концепция меташрифта (296).
        Глава 16. Уроки METRFONT»a (321).
        Глава 17. AMS Euler — новый математический шрифт (344).
        Глава 18. Набор книги Concrete Mathematics (369).
        Глава 19. Из опыта преподавания программирования на METAFONT»e (381).
        Глава 20. Меташрифт Punk (393).
        Глава 21. Шрифты для дискретных полутонов (415).
        Глава 22. Оцифровка полутонов посредством диффузии точки (447).
        Глава 23. Заметки об оцифровке углов (469).
        Глава 24. TEXDR.AFT (477).
        Глава 25. TEX.ONE (506).
        Глава 26. TEX»овские инкунабулы (539).
        Глава 27. Пиктограммы для TEX»a и METAFONT»a (552).
        Глава 28. Компьютеры и книгоиздание (559).
        Глава 29. Новые версии TEX»a и METRFONT»a (567).
        Глава 30. Будущее TEX»a и METRFONT»a (576).
        Глава 31. Вопросы и ответы, I (578).
        Глава 32. Вопросы и ответы, II (604).
        Глава 33. Вопросы и ответы, III (625).
        Глава 34. Последние ошибки TEX»а (651).
        Предметный указатель (659).

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

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

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

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

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

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

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

    • Программирование ,
    • Профессиональная литература
      • Перевод

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

      To be continued.

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

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

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

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

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

      В качестве признанного эксперта по созданию компиляторов , в 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,

      Рецензии на книгу « Искусство программирования. Том 1. Основные алгоритмы » Дональд Кнут

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

      «Если вы считаете себя действительно хорошим программистом, прочтите книгу «Искусство программирования» Д.Кнутa. Вам определенно следует прислать мне резюме, если Вы прочли эту книгу до конца» — Билл Гейтс (с)

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

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

      Искусство программирования дональд э кнут. «Искусство программирования» — обзор легендарной серии книг

      ] Автор: Кнут Дональд Эрвин (Donald Ervin Knuth). Научное издание. Перевод с английского Р.М. Кузнец, О.А. Маховая, Н.В. Третьяков, Ю.В. Тюменцев, под редакцией И.А. Маховой. Художник И.И. Куликова.
      (Москва: Издательство «Мир», Издательство «ACT», 2003. — Серия «Библиотека издательских технологий»)
      Скан, обработка, формат Djv: . предоставил: Михаил, 2020

      • КРАТКОЕ ОГЛАВЛЕНИЕ:
        Предисловие редактора перевода (5).
        Предисловие (11).
        Ссылки на источники (16).
        Глава 1. Компьютерная типография (19).
        Глава 2. Математическая типография (36).
        Глава 3. Верстка абзацев (79).
        Глава 4. Сочетание текстов, читаемых справа налево и слева направо (167).
        Глава 5. Рецепты и дроби (187).
        Глава 6. Логотип системы TEX в различных шрифтах (192).
        Глава 7. Генерирование избранных страниц (194).
        Глава 8. Макро, написанные для Джил (196).
        Глава 9. Задача на субботнее утро (205).
        Глава 10. Упражнения к книге TEX: The Program (207).
        Глава 11. Мини-указатели для самодокументированных программ (235).
        Глава 12. Виртуальные шрифты. Развлечение для настоящих мастеров (256).
        Глава 13. Буква S (273).
        Глава 14. Мое первое знакомство с индийской письменностью (293).
        Глава 15. Концепция меташрифта (296).
        Глава 16. Уроки METRFONT»a (321).
        Глава 17. AMS Euler — новый математический шрифт (344).
        Глава 18. Набор книги Concrete Mathematics (369).
        Глава 19. Из опыта преподавания программирования на METAFONT»e (381).
        Глава 20. Меташрифт Punk (393).
        Глава 21. Шрифты для дискретных полутонов (415).
        Глава 22. Оцифровка полутонов посредством диффузии точки (447).
        Глава 23. Заметки об оцифровке углов (469).
        Глава 24. TEXDR.AFT (477).
        Глава 25. TEX.ONE (506).
        Глава 26. TEX»овские инкунабулы (539).
        Глава 27. Пиктограммы для TEX»a и METAFONT»a (552).
        Глава 28. Компьютеры и книгоиздание (559).
        Глава 29. Новые версии TEX»a и METRFONT»a (567).
        Глава 30. Будущее TEX»a и METRFONT»a (576).
        Глава 31. Вопросы и ответы, I (578).
        Глава 32. Вопросы и ответы, II (604).
        Глава 33. Вопросы и ответы, III (625).
        Глава 34. Последние ошибки TEX»а (651).
        Предметный указатель (659).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

      Искусство программирования том 1 основные алгоритмы. «Искусство программирования» — обзор легендарной серии книг

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

      ] Автор: Кнут Дональд Эрвин (Donald Ervin Knuth). Научное издание. Перевод с английского Р.М. Кузнец, О.А. Маховая, Н.В. Третьяков, Ю.В. Тюменцев, под редакцией И.А. Маховой. Художник И.И. Куликова.
      (Москва: Издательство «Мир», Издательство «ACT», 2003. — Серия «Библиотека издательских технологий»)
      Скан, обработка, формат Djv: . предоставил: Михаил, 2020

      • КРАТКОЕ ОГЛАВЛЕНИЕ:
        Предисловие редактора перевода (5).
        Предисловие (11).
        Ссылки на источники (16).
        Глава 1. Компьютерная типография (19).
        Глава 2. Математическая типография (36).
        Глава 3. Верстка абзацев (79).
        Глава 4. Сочетание текстов, читаемых справа налево и слева направо (167).
        Глава 5. Рецепты и дроби (187).
        Глава 6. Логотип системы TEX в различных шрифтах (192).
        Глава 7. Генерирование избранных страниц (194).
        Глава 8. Макро, написанные для Джил (196).
        Глава 9. Задача на субботнее утро (205).
        Глава 10. Упражнения к книге TEX: The Program (207).
        Глава 11. Мини-указатели для самодокументированных программ (235).
        Глава 12. Виртуальные шрифты. Развлечение для настоящих мастеров (256).
        Глава 13. Буква S (273).
        Глава 14. Мое первое знакомство с индийской письменностью (293).
        Глава 15. Концепция меташрифта (296).
        Глава 16. Уроки METRFONT»a (321).
        Глава 17. AMS Euler — новый математический шрифт (344).
        Глава 18. Набор книги Concrete Mathematics (369).
        Глава 19. Из опыта преподавания программирования на METAFONT»e (381).
        Глава 20. Меташрифт Punk (393).
        Глава 21. Шрифты для дискретных полутонов (415).
        Глава 22. Оцифровка полутонов посредством диффузии точки (447).
        Глава 23. Заметки об оцифровке углов (469).
        Глава 24. TEXDR.AFT (477).
        Глава 25. TEX.ONE (506).
        Глава 26. TEX»овские инкунабулы (539).
        Глава 27. Пиктограммы для TEX»a и METAFONT»a (552).
        Глава 28. Компьютеры и книгоиздание (559).
        Глава 29. Новые версии TEX»a и METRFONT»a (567).
        Глава 30. Будущее TEX»a и METRFONT»a (576).
        Глава 31. Вопросы и ответы, I (578).
        Глава 32. Вопросы и ответы, II (604).
        Глава 33. Вопросы и ответы, III (625).
        Глава 34. Последние ошибки TEX»а (651).
        Предметный указатель (659).

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

      «Искусство программирования» — обзор легендарной серии книг. #[email protected]

      «Искусство программирования» — обзор легендарной серии книг — Библиотека программиста

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

      Комментарии (9)

      Скай Ларсен

      теперь бы ещё краткое содержание

      Олександр Кріль

      Николай Говоров

      Скай, оно на фото

      Александр Переверзев

      Скай, Кнут обещал сделать краткое содержание после 5 го тома. Сделать 1-5 для студентов.

      Константин Сидякин

      Актуальность всего этого для 90% программистов под вопросом. Найти бы время к документации по фреймворкам. Зачем Кнут питонистам, вебщикам или мобильным разработчикам?

      Виктор Берментьев

      Хорошая стопка мукулатуры

      Денис Борисов

      Александр, это тебе в МДК И БОРЩ рекламу подавать надо.

      Сергей Романов

      Александр, 10 из 10!

      Mynameis Denis

      Константин, согласен, если нет цели для роста, если есть те, кто платит за средненькую работу средненькие деньги, и нет желания оттачивать мастерство, то книги не нужны, достаточно stack overflow.

      О проекте

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

      ForCoder

      Навазние: Искусство программирования, тома 1-3
      Автор: Дональд Эрвин Кнут
      Издательство:
      Год: 2007
      Страниц: 720, 832, 824
      Язык: Русский
      Размер: 18.1
      Формат: djvu

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

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

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

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


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

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

      20,425 просмотров всего, 4 просмотров сегодня

      Искусство программирования дональд э кнут. «Искусство программирования» — обзор легендарной серии книг

      ] Автор: Кнут Дональд Эрвин (Donald Ervin Knuth). Научное издание. Перевод с английского Р.М. Кузнец, О.А. Маховая, Н.В. Третьяков, Ю.В. Тюменцев, под редакцией И.А. Маховой. Художник И.И. Куликова.
      (Москва: Издательство «Мир», Издательство «ACT», 2003. — Серия «Библиотека издательских технологий»)
      Скан, обработка, формат Djv: . предоставил: Михаил, 2020

      • КРАТКОЕ ОГЛАВЛЕНИЕ:
        Предисловие редактора перевода (5).
        Предисловие (11).
        Ссылки на источники (16).
        Глава 1. Компьютерная типография (19).
        Глава 2. Математическая типография (36).
        Глава 3. Верстка абзацев (79).
        Глава 4. Сочетание текстов, читаемых справа налево и слева направо (167).
        Глава 5. Рецепты и дроби (187).
        Глава 6. Логотип системы TEX в различных шрифтах (192).
        Глава 7. Генерирование избранных страниц (194).
        Глава 8. Макро, написанные для Джил (196).
        Глава 9. Задача на субботнее утро (205).
        Глава 10. Упражнения к книге TEX: The Program (207).
        Глава 11. Мини-указатели для самодокументированных программ (235).
        Глава 12. Виртуальные шрифты. Развлечение для настоящих мастеров (256).
        Глава 13. Буква S (273).
        Глава 14. Мое первое знакомство с индийской письменностью (293).
        Глава 15. Концепция меташрифта (296).
        Глава 16. Уроки METRFONT»a (321).
        Глава 17. AMS Euler — новый математический шрифт (344).
        Глава 18. Набор книги Concrete Mathematics (369).
        Глава 19. Из опыта преподавания программирования на METAFONT»e (381).
        Глава 20. Меташрифт Punk (393).
        Глава 21. Шрифты для дискретных полутонов (415).
        Глава 22. Оцифровка полутонов посредством диффузии точки (447).
        Глава 23. Заметки об оцифровке углов (469).
        Глава 24. TEXDR.AFT (477).
        Глава 25. TEX.ONE (506).
        Глава 26. TEX»овские инкунабулы (539).
        Глава 27. Пиктограммы для TEX»a и METAFONT»a (552).
        Глава 28. Компьютеры и книгоиздание (559).
        Глава 29. Новые версии TEX»a и METRFONT»a (567).
        Глава 30. Будущее TEX»a и METRFONT»a (576).
        Глава 31. Вопросы и ответы, I (578).
        Глава 32. Вопросы и ответы, II (604).
        Глава 33. Вопросы и ответы, III (625).
        Глава 34. Последние ошибки TEX»а (651).
        Предметный указатель (659).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

      Мастер Йода рекомендует:  Использование SSE вместо WebSockets для однонаправленного потока данных через HTTP2
Добавить комментарий