✖


Jump to content

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

(Перенаправлено с TAOCP )
Не путать с «Искусством программирования для Unix» .

Искусство компьютерного программирования
Искусство компьютерного программирования, Том 1: Фундаментальные алгоритмы
Автор Дональд Кнут
Язык Английский
Жанр Научная литература
Монография
Издатель Аддисон-Уэсли
Дата публикации
1968– (книга еще не завершена)
Место публикации Соединенные Штаты
Тип носителя Распечатать ( твердый переплет )
ISBN 0-201-03801-3
519
Класс ЛК QA76.75

Искусство компьютерного программирования ( TAOCP ) — это обширная монография, написанная учёным-компьютерщиком Дональдом Кнутом , в которой представлены программирования алгоритмы и их анализ . Тома 1–5 призваны представить центральное ядро ​​компьютерного программирования для последовательных машин.

Когда Кнут начал этот проект в 1962 году, он изначально задумывал его как одну книгу из двенадцати глав. Первые три тома семитомного набора были опубликованы в 1968, 1969 и 1973 годах. Серьезная работа над четвертым томом началась в 1973 году, но была приостановлена ​​в 1977 году из-за работы над набором текста, вызванной вторым изданием. Тома 2. Написание окончательной версии Тома 4А началось от руки в 2001 году, а первый онлайн-предварительный выпуск, 2А, появился позже, в 2001 году. [1] Первая опубликованная часть Тома 4 появилась в мягкой обложке под названием Fascicle 2 в 2005 году.Том 4A в твердом переплете, объединяющий Том 4, Главы 0–4, был опубликован в 2011 году. Том 4, Глава 6 («Выполнимость») был выпущен в декабре 2015 года; Том 4, глава 5 («Математические предварительные сведения; Возврат; Танцующие ссылки») был выпущен в ноябре 2019 года.

Том 4B состоит из материала, полученного из выпусков 5 и 6. [2] Рукопись была отправлена ​​в издательство 1 августа 2022 г., том опубликован в сентябре 2022 г. [3] Глава 7, запланированная для тома 4C, стала темой выступления Кнута 3 августа 2022 года. [4]

История [ править ]

Дональд Кнут в 2005 году

Выиграв стипендию Westinghouse Talent Search , Кнут поступил в Технологический институт Кейса (ныне Университет Кейс Вестерн Резерв ), где его успеваемость была настолько выдающейся, что преподаватели проголосовали за присвоение ему степени магистра наук после получения степени бакалавра . Во время летних каникул Кнут был нанят корпорацией Берроуза для написания компиляторов , зарабатывая за летние месяцы больше, чем профессора за целый год. [5] Такие подвиги сделали Кнута предметом обсуждения на математическом факультете, в который входил Ричард С. Варга .

В январе 1962 года, когда он был аспирантом математического факультета Калифорнийского технологического института, Аддисон-Уэсли обратился к Кнуту с просьбой написать книгу о проектировании компиляторов, и он предложил более широкую область применения. В тот же день он составил список из двенадцати названий глав. Летом 1962 года он работал над компилятором FORTRAN для UNIVAC . За это время он также придумал математический анализ линейного зондирования , который убедил его представить материал с количественным подходом. После получения докторской степени. в июне 1963 года он начал работу над своей рукописью, первый вариант которой он закончил в июне 1965 года, насчитывая 3000 рукописных страниц. [6] Он предполагал, что около пяти рукописных страниц можно превратить в одну печатную страницу, но вместо этого его издатель заявил, что примерно 1 + 1 ⁄ 2 рукописных страницы переводятся на одну печатную страницу. Это означало, что у него было около 2000 печатных страниц материала, что близко соответствует размеру первых трех опубликованных томов. В этот момент Кнут получил поддержку от Ричарда С. Варги, который был научным консультантом издателя. Варга навещал Ольгу Таусски-Тодд и Джона Тодда в Калифорнийском технологическом институте . При восторженной поддержке Варги издатель принял расширенные планы Кнута. В расширенной версии книга будет опубликована в семи томах, каждый из которых будет состоять всего из одной или двух глав. [7] Из-за увеличения главы 7, которая составляла менее 100 страниц рукописи 1965 года в каждом томе. 4А с. vi, план Тома 4 с тех пор расширился и теперь включает тома 4A, 4B, 4C, 4D и, возможно, другие.

В 1976 году Кнут подготовил второе издание второго тома, потребовав его повторной верстки , но стиль шрифта, использованный в первом издании (называемый горячим шрифтом ), больше не был доступен. В 1977 году он решил потратить некоторое время на создание чего-то более подходящего. Восемь лет спустя он вернулся с T E X , который в настоящее время используется во всех томах.

Предложение так называемого чека Кнута на вознаграждение в размере «одного шестнадцатеричного доллара» (100 шестнадцатеричных центов по основанию 16 в десятичном формате равно 2,56 доллара) за любые обнаруженные ошибки, а также исправление этих ошибок в последующих печатных изданиях способствовало доведению до совершенства этой книги. и по-прежнему авторитетный характер работы даже спустя долгое время после ее первой публикации. Еще одной особенностью объемов является вариативность сложности упражнений. У Кнута даже есть числовая шкала сложности для оценки этих упражнений, варьирующаяся от 0 до 50, где 0 — тривиально, а 50 — открытый вопрос в современных исследованиях.

Посвящение Кнута гласит:

Эта серия книг с любовью посвящается
к компьютеру Type 650 после установки
Кейсский технологический институт ,
с которым я провел много приятных вечеров. [а]

Язык ассемблера в книге [ править ]

Во всех примерах в книгах используется язык под названием « Язык ассемблера MIX », который работает на гипотетическом компьютере MIX. В настоящее время, [ когда? ] компьютер MIX заменяется компьютером MMIX , который является версией RISC . Программное обеспечение, такое как GNU MDK [8] существует для обеспечения эмуляции архитектуры MIX. Кнут считает, что использование языка ассемблера необходимо для оценки скорости и использования памяти алгоритмами.

Критический ответ [ править ]

Кнут был награжден Премией Тьюринга 1974 года «за большой вклад в анализ алгоритмов […] и, в частности, за вклад в «искусство компьютерного программирования» посредством своих хорошо известных книг из непрерывной серии под этим названием». [9] Американский ученый включил эту работу в число «100 или около того книг, сформировавших век науки», имея в виду двадцатый век. [10] На обложке третьего издания первого тома цитируются слова Билла Гейтса : «Если вы думаете, что вы действительно хороший программист… прочтите книгу (Кнута) « Искусство компьютерного программирования »… Вам обязательно следует прислать мне резюме, если вы сможете прочитать ее целиком. " [11] Газета New York Times назвала его «определяющим трактатом профессии». [12]

Тома [ править ]

Завершено [ править ]

Планируется [ править ]

Краткое содержание глав [ править ]

Завершено [ править ]

1 – Фундаментальные алгоритмы Том

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

Том 3 – Сортировка и поиск [ править ]

  • Глава 5 – Сортировка
    • 5.1. Комбинаторные свойства перестановок
      • 5.1.1. Инверсии
      • 5.1.2. Перестановки мультимножества
      • 5.1.3. Бежит
      • 5.1.4. Таблицы и инволюции
    • 5.2. Внутренняя сортировка
      • 5.2.1. Сортировка по вставке
      • 5.2.2. Сортировка по обмену
      • 5.2.3. Сортировка по выбору
      • 5.2.4. Сортировка по слиянию
      • 5.2.5. Сортировка по распространению
    • 5.3. Оптимальная сортировка
      • 5.3.1. Сортировка по минимальному сравнению
      • 5.3.2. Слияние с минимальным сравнением
      • 5.3.3. Выбор минимального сравнения
      • 5.3.4. Сети для сортировки
    • 5.4. Внешняя сортировка
      • 5.4.1. Многоходовое объединение и выбор замены
      • 5.4.2. Многофазное слияние
      • 5.4.3. Каскадное слияние
      • 5.4.4. Чтение ленты задом наперед
      • 5.4.5. Осциллирующая сортировка
      • 5.4.6. Практические соображения по объединению лент
      • 5.4.7. Внешняя поразрядная сортировка
      • 5.4.8. Двухленточная сортировка
      • 5.4.9. Диски и барабаны
    • 5.5. Резюме, история и библиография
  • Глава 6 – Поиск
    • 6.1. Последовательный поиск
    • 6.2. Поиск по сравнению ключей
      • 6.2.1. Поиск упорядоченной таблицы
      • 6.2.2. Поиск в двоичном дереве
      • 6.2.3. Сбалансированные деревья
      • 6.2.4. Многосторонние деревья
    • 6.3. Цифровой поиск
    • 6.4. Хеширование
    • 6.5. Получение вторичных ключей

Том 4A – Комбинаторные алгоритмы, часть 1 [ править ]

Том 4B – Комбинаторные алгоритмы, часть 2 [ править ]

Планируется [ править ]

Тома 4C, 4D, 4E, 4F – Комбинаторные алгоритмы [13] [ редактировать ]

Том 5 – Синтаксические алгоритмы [ править ]

Том 6 – Теория контекстно-свободных языков [14] [ редактировать ]

  • Глава 11 – Математическая лингвистика [15]

Том 7 – Методы компиляции [ править ]

  • Глава 12 – Перевод языков программирования [15]

Английские издания [ править ]

Текущие выпуски [ править ]

Это текущие издания в порядке номера тома:

  • Искусство компьютерного программирования, коробочный набор томов 1–4B . (Ридинг, Массачусетс: Аддисон-Уэсли, 2023), 3904 стр. ISBN   978-0-13-793510-9 , 0-13-793510-2
    • Том 1: Фундаментальные алгоритмы . Третье издание (Ридинг, Массачусетс: Аддисон-Уэсли, 1997), xx+650 стр. ISBN   978-0-201-89683-1 , 0-201-89683-4 . Ошибки: [1] (08 января 2011 г.), [2] (2022 г., 49-е издание ). Приложение: [3] (2011).
    • Том 2: Получисловые алгоритмы . Третье издание (Ридинг, Массачусетс: Аддисон-Уэсли, 1997), xiv+762 стр. ISBN   978-0-201-89684-8 , 0-201-89684-2 . Ошибки: [4] (08 января 2011 г.), [5] (2022 г., 45-е издание). Приложение: [6] (2011).
    • Том 3: Сортировка и поиск . Второе издание (Ридинг, Массачусетс: Аддисон-Уэсли, 1998), xiv+780 стр.+раскладной. ISBN   978-0-201-89685-5 , 0-201-89685-0 . Ошибки: [7] (08 января 2011 г.), [8] (2022 г., 45-е издание). Приложение: [9] (2011).
    • Том 4А: Комбинаторные алгоритмы, Часть 1 . Первое издание (Аппер-Сэддл-Ривер, Нью-Джерси: Аддисон-Уэсли, 2011), xv+883 стр. ISBN   978-0-201-03804-0 , 0-201-03804-8 . Ошибки: [10] (2011 г.), [11] (2022 г., 22-е издание).
    • Том 4B: Комбинаторные алгоритмы, часть 2 . Первое издание (Аппер-Сэддл-Ривер, Нью-Джерси: Аддисон-Уэсли, 2023), xviii+714 стр. ISBN   978-0-201-03806-4 , 0-201-03806-4 . Опечатки: [12] (2023 г., 1-е издание).
  • Том 1, выпуск 1: MMIX — RISC-компьютер нового тысячелетия . (Аддисон-Уэсли, 14 февраля 2005 г.) ISBN   0-201-85392-2 . Исправления: [13] (16 марта 2020 г.) (будет в четвертом издании тома 1)

Предыдущие выпуски [ править ]

Полные тома [ править ]

Эти тома были заменены более новыми изданиями и упорядочены по дате.

  • Том 1: Фундаментальные алгоритмы . Первое издание, 1968 г., XXI+634 стр., ISBN   0-201-03801-3 . [16]
  • Том 2: Получисловые алгоритмы . Первое издание, 1969 г., xi+624 стр., ISBN   0-201-03802-1 . [16]
  • Том 3: Сортировка и поиск . Первое издание, 1973 г., xi+723 стр.+раскладной, ISBN   0-201-03803-X . Ошибки: [14] .
  • Том 1: Фундаментальные алгоритмы . Второе издание, 1973 г., XXI+634 стр., ISBN   0-201-03809-9 . Ошибки: [15] .
  • Том 2: Получисловые алгоритмы . Второе издание, 1981 г., xiii+ 688 стр., ISBN   0-201-03822-6 . Ошибки: [16] .
  • Искусство компьютерного программирования, тома 1–3 в коробочном наборе . Второе издание (Ридинг, Массачусетс: Аддисон-Уэсли, 1998), стр. ISBN   978-0-201-48541-7 , 0-201-48541-9
  • Искусство компьютерного программирования, коробочный набор томов 1–4А . Третье издание (Ридинг, Массачусетс: Аддисон-Уэсли, 2011), 3168 стр. ISBN   978-0-321-75104-1 , 0-321-75104-3

Сборники [ править ]

Том 4, выпуски 0–4 были переработаны и опубликованы как Том 4A.

  • Том 4, выпуск 0: Введение в комбинаторные алгоритмы и логические функции . (Addison-Wesley Professional, 28 апреля 2008 г.) vi+240pp, ISBN   0-321-53496-4 . Ошибки: [17] (1 января 2011 г.).
  • Том 4, глава 1: Побитовые приемы и методы; Бинарные диаграммы решений . (Addison-Wesley Professional, 27 марта 2009 г.) viii+260 стр., ISBN   0-321-58050-8 . Ошибки: [18] (1 января 2011 г.).
  • Том 4, глава 2: Генерация всех кортежей и перестановок . (Аддисон-Уэсли, 14 февраля 2005 г.) v + 127 стр., ISBN   0-201-85393-0 . Ошибки: [19] (1 января 2011 г.).
  • Том 4, глава 3: Создание всех комбинаций и разделов . (Аддисон-Уэсли, 26 июля 2005 г.) vi+150 стр., ISBN   0-201-85394-9 . Ошибки: [20] (1 января 2011 г.).
  • Том 4, выпуск 4: Создание всех деревьев; История комбинаторной генерации . (Аддисон-Уэсли, 06 февраля 2006 г.) vi+120 стр., ISBN   0-321-33570-8 . Ошибки: [21] (1 января 2011 г.).

Том 4, выпуски 5–6 были переработаны и опубликованы как Том 4B.

  • Том 4, выпуск 5: Математические предварительные сведения; Возврат; Танцевальные ссылки . (Аддисон-Уэсли, 22 ноября 2019 г.) xiii+382 стр., ISBN   978-0-13-467179-6 . Ошибки: [22] (27 марта 2020 г.)
  • Том 4, глава 6: Выполнимость . (Аддисон-Уэсли, 08 декабря 2015 г.) xiii+310 стр., ISBN   978-0-13-439760-3 . Ошибки: [23] (26 марта 2020 г.)

Предварительные выпуски [ править ]

Том 1

  • Предисловие 1 было переработано и опубликовано как Том 1, глава 1.

Том 4

  • Предварительные выпуски 0A , 0B и 0C были переработаны и опубликованы как том 4, глава 0.
  • Предварительные выпуски 1A и 1B были переработаны и опубликованы как том 4, глава 1.
  • Предварительные выпуски 2A и 2B были переработаны и опубликованы как том 4, глава 2.
  • Предварительные выпуски 3A и 3B были переработаны и опубликованы как том 4, глава 3.
  • Предварительные выпуски 4A и 4B были переработаны* и опубликованы как том 4, глава 4.
  • Предварительные выпуски 5A , 5B и 5C были переработаны и опубликованы как том 4, глава 5.
  • Предвыпуск 6А был переработан и опубликован как том 4, глава 6.

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

См. также [ править ]

Ссылки [ править ]

Примечания

  1. ↑ В первом издании посвящение было сформулировано немного иначе.

Цитаты

  1. ^ «заметка для ящика 3, папка 1» .
  2. ^ Веб-страница книги Pearson InformIT, вкладка «Содержимое» . Аддисон-Уэсли Профессионал. 28 сентября 2022 г. ISBN  9780201038064 .
  3. ^ Веб-страница Pearson InformIT . Аддисон-Уэсли Профессионал. 28 сентября 2022 г. ISBN  9780201038064 .
  4. ^ «CP 2022 «Ответы на все вопросы», 31 июля – 5 августа 2022 г., Хайфа, Израиль» .
  5. ^ Франа, Филип Л. (8 ноября 2001 г.). «Интервью с Дональдом Э. Кнутом» . hdl : 11299/107413 .
  6. ^ Кнут, Дональд Э. (23 августа 1993 г.). «Классика цитирования этой недели» (PDF) . Текущее содержание . п. 8.
  7. ^ Альберс, Дональд Дж. (2008). «Дональд Кнут». В Альберсе, Дональд Дж.; Александерсон, Джеральд Л. (ред.). Люди-математики: профили и интервью (2-е изд.). АК Петерс . ISBN  978-1-56881-340-0 .
  8. ^ «GNU MDK — Проект GNU — Фонд свободного программного обеспечения» . www.gnu.org . Проверено 23 октября 2022 г.
  9. ^ «Дональд Э. Кнут – лауреат премии А. М. Тьюринга» . А. М. Тьюринг . Проверено 25 января 2017 г.
  10. ^ Моррисон, Филип ; Моррисон, Филис (ноябрь – декабрь 1999 г.). «Приблизительно 100 книг, которые сформировали век науки» . Американский учёный . 87 (6). Сигма Си, Общество научных исследований. Архивировано из оригинала 20 августа 2008 г. Проверено 11 января 2008 г.
  11. ^ Вайнбергер, Мэтт. «Билл Гейтс однажды сказал: «Обязательно пришлите мне резюме», если закончите эту чертовски трудную книгу» . Бизнес-инсайдер . Проверено 13 июня 2016 г.
  12. ^ Лор, Стив (17 декабря 2001 г.). «Фрэнсис Э. Холбертон, 84 года, один из первых программистов» . Нью-Йорк Таймс . Проверено 17 мая 2010 г.
  13. ^ Д'Агостино, Сьюзен (16 апреля 2020 г.). «Ученый-компьютерщик, который не может перестать рассказывать истории» . Журнал Кванта . Проверено 26 июня 2023 г. Сейчас ему 82 года, он усердно работает над частью B четвёртого тома и ожидает, что в книге будут как минимум части от A до F.
  14. ^ «TAOCP – Планы на будущее» .
  15. ↑ Перейти обратно: Перейти обратно: а б https://www-cs-faculty.stanford.edu/~knuth/brochure.pdf . {{cite web}}: Отсутствует или пусто |title= ( помощь )
  16. ↑ Перейти обратно: Перейти обратно: а б Уэллс, Марк Б. (1973). «Обзор: Искусство компьютерного программирования, Том 1. Фундаментальные алгоритмы и Том 2. Получисловые алгоритмы Дональда Э. Кнута» (PDF) . Бюллетень Американского математического общества . 79 (3): 501–509. дои : 10.1090/s0002-9904-1973-13173-8 .

Источники

Внешние ссылки [ править ]

Retrieved from "https://en.wikipedia.org/w/index.php?title=The_Art_of_Computer_Programming&oldid=1230519356"
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 0e07c4adb9e42fe575b6d468d8d63c04__1719110940
URL1:https://arc.ask3.ru/arc/aa/0e/04/0e07c4adb9e42fe575b6d468d8d63c04.html
Заголовок, (Title) документа по адресу, URL1:
The Art of Computer Programming - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)