] Автор: Кнут Дональд Эрвин (Donald Ervin Knuth). Научное издание. Перевод с английского Р.М. Кузнец, О.А. Маховая, Н.В. Третьяков, Ю.В. Тюменцев, под редакцией И.А. Маховой. Художник И.И. Куликова.
(Москва: Издательство «Мир», Издательство «ACT», 2003. - Серия «Библиотека издательских технологий»)
Скан, обработка, формат Djv: ???, предоставил: Михаил, 2016
- КРАТКОЕ ОГЛАВЛЕНИЕ:
Предисловие редактора перевода (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 в историческом аспекте. Представлен богатый иллюстративный материал и приводятся листинги программ.
Как и во всех книгах Д. Кнута, весьма серьезные вопросы излагаются просто и увлекательно, что, учитывая междисциплинарную направленность книги, делает ее доступной для специалистов в разных областях науки.
Книга представляет интерес для научных работников всех специальностей, самостоятельно готовящих свои работы к публикации, для специалистов в области информатики и издательских систем, а также для математиков, интересующихся нестандартными приложениями.
«Сейчас предельно ясно, что с той скоростью с которой я пишу, я не закончу весь проект до своего девяностолетия.»
Прочитайте и оцените объем работ. И не торопите дедушку Кнута, он и так старается.
Поддержка публикации - компания Edison , которая разрабатывает корпоративные порталы и приложения для передачи видеороликов .
Volume Three of «The Art of Computer Programming» (48/97)
Третий том - о сортировке и поиске. Эта область сильно изменилась с тех пор, как я писал окончательный вариант книги. Итак я размышляю о сортировке и поиске как если бы я сейчас был в Принстоне. Вы знаете, я окончил работу над второй частью книги и я готов был приехать в Стэнфорд, но у меня постоянно появлялись новые идеи о сортировке, поскольку эта область была подвержена изменениям.
Поэтому после моего приезда в Стэнфорд мне нужно было преподавать и начинать делать совершенно новые вещи, которые я никогда не делал до этого момента. На это ушло какое-то время и я не смог закончить работу над третьей частью книги до моей поездки в Норвегию в 1972, когда у меня был академический отпуск. Вообще-то это не был настоящий академический отпуск, я его только так называю. А на самом деле это был отпуск за свой счет. Я уже три года работал в Стэнфорде и подумал, что это была бы отличная идея.
Профессора обычно работают 6 лет, потом уходят на год в академический отпуск, затем снова 6 лет работы и опять 1 год академического отпуска. Я подумал, что может я выберу 4-х годичный цикл. Я проработаю 3 года, возьму отпуск за свой счет, потом снова 3 года и затем академический отпуск. Правила Стэнфорда не препятствовали такому плану. А я получил приглашение из Университета Норвегии провести там один год в качестве приглашенного профессора и, так как мне не нужна была материальная помощь от Стэнфорда, я мог поехать туда, взяв отпуск за свой счет без всех этих проблем, связанных с оплатами.
И я любил Норвегию - мы посетили ее в 1967, верьте или нет. Это была еще одна из тех вещей, которые случились в 1967! И я влюбился в эту страну и в норвежский национальный гимн - Ja, vi elsker dette landet. Мы любим эту страну.
И я уехал в Норвегию и именно там я закончил работу над третьей частью и начал писать четвертую. В течение того года я читал лекции в университете каждую среду, в свободное время я был дома, писал книгу и читал, и проводил все остальное время со своими детьми.
И когда, в конце концов, третья часть вышла в свет, она добавила новый аспект ко всей этой идее анализа алгоритмов, потому что когда вы начинаете говорить о темах, которые описываются в третьей части, оказывается, что даже несмотря на то, что в ней описываются конкретные ситуации, сортировка, поиск - уроки, которые вы учитесь применять ко многим другим ситуациям, в ней еще очень много дополнительных тем.
И именно поэтому третья часть была особенно важна для меня. Парадигмы и методы которые мы использовали для изучения алгоритмов всех видов, казалось все они возникли в контексте сортировки. И я мог бы создать единую историю обо всем этом, но я преподаю общие принципы и одновременно могу проиллюстрировать их на примере особого предмета: сортировка и поиска.
Working on Volume Four of «The Art of Computer Programming» (49/97)
Затем я прихожу домой и думаю, ок я готов. Я буду писать четвертый том. Она о комбинаторных алгоритмах. Комбинаторный… это значит, что алгоритм оперирует неисчислимым количеством комбинаций способов выполнять действия и, как результат, существовало много, много проблем, которые люди хотели чтобы компьютеры решали за них.
Так много случаев надо было решить. Вам был нужен компьютер, чтобы сделать это, но теперь никто не мог выяснить как сделать это эффективно. А хорошая идея могла бы создать метод работающий в миллионы раз быстрее и я собирал все эти хорошие идеи, но у людей появлялись все новые и новые отличные идеи. И тогда..., есть такое понятие комбинаторные взрыв, которое означает для большинства людей, что размер проблемы увеличивается до гигантских масштабов и очень быстро.
Для меня комбинаторный взрыв означал, что исследование комбинаторных методов резко усиливалось. В 1974, 1975 и 1976, когда я работал над четвертой книгой, более чем 50% всех статей во всех технических журналах были о темах, которые описывались в ней. Другими словами это как сидеть на кипящем котле, вы не можете его контролировать. Каждый раз когда я писал что-то на одной неделе, на следующей это уже устаревало.
Вы знаете, это похоже на попытку написать книгу об интернете сегодня или что-то в этом роде. И поэтому казалось невозможным закончить четвертую книгу. Я стараюсь изо всех сил, собираю материал для нее, читаю газеты, делаю множество заметок. Наверху у меня сотни папок с этими заметками.
Когда я начал у меня было 30 папок и они были хорошо организованы, затем я создал папки под названиями Х1, Х2, Х3 и так до Х15 - не очень хорошо организованные, но просто расширения системы. А затем появился новый материал и я стал сваливать его в кучу, в надежде что однажды у меня будет время это прочесть. И я так и надеялся… Но эта область растет очень быстро.
Updating Volumes One to Three of «The Art of Computer Programming» (81/97)
Я закончил книгу «3:16», я закончил «Конкретную математику». И я все еще не могу вернуться к «Искусству программирования», потому что у меня все еще есть одно незаконченное дело и это Stanford GraphBase. Это собрание программ грамотности, которые используются для стандартных примеров, которые будут в четвертой части книги «Искусство программирования».
И чтобы сделать эту работу мне потребовалось еще несколько лет. Было необходимо выпустить эту базу до выхода самой книги, чтобы я смог закончить остальные проекты с другими людьми в разных частях света, которые способствовали написанию книги, чтобы они смогли использовать Stanford GraphBase для своей работы.
Примерно в 1995 году я смог открыть дверь той самой комнаты, куда я бросал все новые материалы для книги в течение 15 лет. Пока я работал над TeX, у меня совсем не было времени думать об этом и когда я получал что-то по почте, относящееся к четвертому, пятому или другим томам книги, я просто отправлял это в кучу, затем у меня появились коробки и еще коробки и в итоге накопилось примерно 17 футов материала в длину.
А кроме этого у меня были все те материалы, которые я собрал в предыдущие годы. Поэтому я решил, что мне нужно их все реорганизовать и на это ушел еще один год, даже больше года, чтобы просмотреть всё, каждый клочок бумаги, который попал туда, а затем отправить все в нужное место, создать компьютерный указатель, так, чтобы я мог найти все, разложить всё по тысячам маленьких папок-файлов и также скорректировать все ошибки в первого, второго и третьего томов.
Люди писали мне, сообщая об ошибках в первом, втором и третьем томах. У меня были письма с 1981, 1982 года, на которые я еще не ответил. И я выписал всем этим людям чеки с процентами с того дня. Вы знаете у меня была маленькая программа, которая вычисляла эти проценты и в ней была ошибка, поэтому я думаю, что выплатил чуть больше процентов. Но в любом случае я отослал сотни чеков и получил большой список опечаток для «Искусства компьютерного программирования» для первого, второго и третьего томов, которые я мог набрать с помощью TeX и сделать это правильно.
Все эти годы люди продолжали покупать книги на постоянной основе в книжных магазинах, они покупали издания, который вышел в 70-х годах, но уже в 30-м, в 40-м издании. И каждая из книг до сих пор продается в количестве примерно 4000 книг в год. Вторая часть была издана в 1981 года, та самая, в которой я не мог терпеть цифры, но математический материал был в порядке.
Когда вышла моя серия книг «Компьютеры и верстка», те 5 частей, все было сделано с новыми шрифтами, с соответствующим оформлением. В книге «Конкретная математика» я смог использовать новый шрифт, созданный Herman Zapf, а для книги «3:16» у меня был другой шрифт над которым я работал.
Поэтому в то время оставалась только книга «Искусство компьютерного программирования», в которой было уродливое оформление и все-равно я не хотел его исправлять. У меня заняло так много времени возвращение к написанию четвертой части, как мог я остановиться и переделывать первые три, не подождав еще немного?
На выручку пришел Silvio Levy, который живет в Беркли, который был очень активен во многих математических проектах и сейчас работает библиотекарем в Институте изучения математических наук. Он был большим фанатом TeX и совместно мы создали CWEB - систему грамотного программирования, используя C как язык программирования вместо Pascal.
Silvio решил, что он наберет первые три части книги в TeX ради общественного блага и он запросил у издательства символическую оплату, на что они конечно же легко согласились. Он, совместно со своей женой Sheila, провели исправление ошибок и они проделали изумительную работу, проверив все три части и соединив все ошибки в моем списке ошибок.
Затем у меня не заняло много времени… я имею ввиду на это ушло 3 или 4 месяца, но это ничто по сравнению с тем, сколько бы у меня ушло времени на эту работу, если бы я все делал один. И в итоге в 1997/1998 у нас было обновленное «Искусство программирования» с подходящей версткой и всеми 20 годами исправлений, которые раньше были в моих файлах, а теперь оказались включенными в текст.
Getting started on Volume Four of «The Art of Computer Programming» (82/97)
И тогда я был готов начать работу над четвертой частью. Но она до сих пор не вышла, не так ли? Так что же случилось. Ну, на самом деле, примерно 400 страниц книги уже выпущены в мягкой обложке, но для написания одной страницы мне требуется более одного дня. И я просто не в состоянии убедить себя согласиться просто на репродукцию материалов, которые я нахожу в своих файлах. Каждый раз, когда я смотрю на что-то из материалов, я вижу, что есть возможность улучшить их, и на это у меня уходит еще несколько дней.
Так что я добавляю множество материала по ходу написания четвертого тома, которого нет в литературе. Я не могу поддерживать, то что уже знаю, но те тома книги которые я сейчас пишу, я повторяю себе, что они настолько существенны, что они отличаются от томов, которые последуют за ними и что в следующем году я буду просто объединять те тома, которые не слишком-то оригинальны. Но на самом деле..., как например сегодня я закончу работу над каталогом для новой секции и это примерно 60 страниц, из которых я думаю только 15 страниц содержат информацию, которой нет в другой литературе.
Но также там есть и несколько отличающихся идей… Я не могу удержаться и не выйти за пределы источников, которыми я располагаю, когда я пишу настолько существенную часть книги. Так что сейчас предельно ясно, что с той скоростью с которой я пишу, я не закончу весь проект до своего 90-летия.
Но даже несмотря на то, что я не добавляю ничего, я не выхожу за рамки оглавления, которое я набросал в тот день в январе 1962, когда меня попросили написать книгу о компиляторах. У меня до сих пор хранится примерно такое же оглавление..., но эта область настолько увеличилась и теперь существует столь обширное количество хорошего материала, который я просто не могу не включить в книгу.
Моя жизнь сейчас преимущественно состоит из просмотра материалов для четвертого тома. Все материалы которые я продолжаю читать в библиотеке, зарождают новые идеи и я объединяю их и связываюсь с людьми со всех концов земного шара с просьбами о помощи в отладке идей и проверке того, что я все сделал верно.
Будем надеяться, что у меня получится продолжать эту работу еще долгое время. Это интересно, поскольку мне приходится объединять работы авторов, которые даже не знали о трудах друг друга и у них появляется шанс создать настоящую связь их трудов и мне нравится находить способы представления материала.
Я понимаю, что сейчас я уже старый человек и пишу уже не так оживленно, как в молодости, но у меня до сих пор есть 3000 страниц рукописи, написанной в 60-х, из которой я могу взять предложения и фразы, чтобы омолодить книгу.
И также я осознаю, что этот материал совсем не легкое чтение, люди может будут держать эту книгу в туалете или в схожем месте, а может она будет стоять на полке, просто давая понять кому-нибудь, что они могут ее понять.
К некоторым из этих материалов нет легкого пути, что-то из него по своей сути трудно, но я почти в восторге от того как все идет. Например сегодня утром я составлял оглавление и я видел те части, написание которых далось мне нелегко. Но сейчас когда они закончены, они смотрятся как отличная история и то, что я мучился с их написанием, уже не кажется мне таким очевидным.
Аннотация к книге Искусство программирования, тома 1-3
:
Многие знают, что программирование - это не только сложная умственная работа, но и творческий процесс. Автор этой книги — Дональд Эрвин Кнут — профессор Стэнфордского университета, создал множество книг по математике и компьютерной тематике. Известность ученому принес ставший знаменитым труд «Искусство программирования», первый том которого был издан более 20 лет назад. В своей книге Дональд Кнут объясняет и анализирует основные алгоритмы, используемые в программировании. Это третье издание знаменитой серии книг «Искусство программирования».
Данный релиз содержит 3 тома «Искусства программирования»:
Искусство программирования. Том 1. Основные алгоритмы.
Искусство программирования. Том 2. Получисленные алгоритмы.
Искусство программирования. Том 3. Сортировка и поиск.
Первый том серии книг Искусство программирования начинается с описания основных понятий и методов программирования. Затем автор сосредотачивается на рассмотрении информационных структур -представлении информации внутри компьютера, структурных связях между элементами данных и способах эффективной работы с ними. Для методов имитации, символьных вычислений, числовых методов и методов разработки программного обеспечения даны примеры элементарных приложений. По сравнению с предыдущим изданием добавлены десятки простых, но в то же время очень важных алгоритмов. В соответствии с современными направлениями исследований был существенно переработан также раздел математического введения.
Во втором томе представлена теория получисленных алгоритмов. В отдельные главы вынесено описание процесса генерации случайных чисел и способов работы с ними в вычислительной среде. Автор рассматривает фундаментальные понятия теории вероятности в приложении к вычислительным системам, предоставляя читателю готовые алгоритмы компьютерных программ. Особого внимания заслуживает новый метод автора генерации случайных чисел и описание алгоритмов вычисления формальных степенных рядов.
В третьем издании третьего тома содержится полный обзор классических алгоритмов сортировки и поиска. Представленная в нем информация дополняет приведенное в первомтоме обсуждение структур данных. Автор рассматривает принципы построения больших и малых баз данных, а также внутренней и внешней памяти. В книге приведена подборка тщательно проверенных компьютерных алгоритмов и представлен анализ их эффективности. Кроме того, специальный раздел посвящен методам оптимальной сортировки и описанию новой теории перестановки и универсального хэширования.
Название: Искусства программирования - том 1.
Первый том серии книг Искусство программирования начинается с описания основных понятий и методов программирования. Затем автор переходит к рассмотрению информационных структур, представлению информации внутри компьютера, структурных связей между элементами данных и способам эффективной работы с ними. Для методов имитации, символьных вычислений, числовых методов, методов разработки программного обеспечения даны примеры элементарных приложений. По сравнению с предыдущим изданием добавлены десятки простых, но в то же время очень важных алгоритмов. В соответствии с современными направлениями исследований был существенно переработан раздел математического введения.
У каждой книги своя судьба. Одни появляются незаметно и так же незаметно исчезают в потоке времени, покрываясь пылью на полках библиотек. Другие в определенный период пользуются спросом у узкого круга специалистов, пока им на смену не приходят новые справочники. Третьи, поднимаясь над временем, оказывают мощное влияние на технологическое развитие общества. Книг, относящихся к последней категории, не так уж и много. Их выход в свет - всегда праздник. Проходят годы, изменяются технологии, но новые поколения с постоянным интересом перечитывают их страницы. Именно к таким книгам относится предлагаемый читателю многотомный труд известного американского ученого Дональда Эрвина Кнута "Искусство программирования".
В чем же успех Искусства программирования Д. Э. Кнута:
Во-первых, эта книга - великолепное учебное пособие по составлению и анализу компьютерных алгоритмов. Ее разделы могут быть включены во многие университетские курсы по технологиям программирования, теории алгоритмов, дискретной математике. Книгу могут изучать и школьники старших классов, знакомые с основами программирования. В качестве основного языка записи алгоритмов автор выбрал язык машинных команд гипотетического универсального компьютера MIX. Это позволяет строить оптимальные программы с учетом особенностей вычислительных машин. Перенести MIX-программы на реальные ЭВМ или переписать их на языках высокого уровня не составляет особого труда. Логика работы программ почти всегда поясняется простыми блок-схемами.
Во-вторых, тщательно подобранный материал, вошедший в книгу, включает в себя основные фундаментальные классы алгоритмов, которые в том или ином виде наиболее часто встречаются в практике программирования.
В-третьих, немаловажным фактором успеха книги Д. Э. Кнута является энциклопедичность изложения. Профессор Кнут отличается уникальной способностью отслеживать проблему от исторических предпосылок ее зарождения до современного состояния. Многочисленные ссылки на работы старых мастеров (вплоть до времен античности), заключенные в современный контекст, создают у читателя особое чувство причастности к историческому развитию научных идей и методов.
Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Искусство программирования - том 1 - Кнут Д. Э. - fileskachat.com, быстрое и бесплатное скачивание.
Скачать djvu
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.
Краткий обзор легендарной монографии Дональда Кнута «Искусство программирования» — фундаментального труда в области компьютерных наук.
Том 1. Основные алгоритмы
Первый том является введением в основные алгоритмы и структуры данных, описывает базовые понятия и методы программирования. Здесь же рассматривается тема представления данных в памяти компьютера и эффективной работы с ними.
Книга изобилует примерами для символьных вычислений, численных методов, методов имитации и многого другого.
Примеры программ написаны на так называемом «MIX-ассемблере» — языке, предназначенном для работы на гипотетическом «MIX-компьютере». В третьем издании устаревший MIX был заменен на MMIX , для которого существует программное обеспечение, обеспечивающее его эмуляцию.
Использование языка низкого уровня отпугивает многих читателей, но сам автор небезосновательно оправдывает свой выбор. Привязка к архитектуре позволяет судить о таких характеристиках алгоритма, как скорость и сложность (т. е. использование памяти).
Том 2. Получисленные алгоритмы
Вторая книга посвящена введению в получисленные алгоритмы. Отдельный раздел посвящен арифметике, случайным числам и алгоритмам их генерации. Даются основы теории получисленных алгоритмов, подкрепленные многочисленными примерами.
Особого упоминания заслуживают предложенная Кнутом в настоящем издании новая трактовка генераторов случайных чисел, а также рассмотрение способов вычислений с помощью формальных степенных рядов.
Том 3. Сортировка и поиск
В третьем томе содержится исчерпывающий обзор классических алгоритмов сортировки и поиска. Этот материал дополняет изложенную в первой части информацию о структурах данных становясь своего рода логическим продолжением первого тома.
Здесь автор рассказывает о внутренней и внешней памяти, о построении больших и малых баз данных и работе с ними. Для всех рассмотренных в книге алгоритмов приводится сравнительный анализ их эффективности. Специальный раздел посвящен методам оптимальной сортировки и описанию новой теории перестановки и универсального хеширования.
Том 4. Комбинированные алгоритмы
Четвертый том сам по себе является многотомником. Комбинаторный поиск - богатая и важная тема, и Кнут приводит слишком много нового, интересного и полезного материала, чтобы его можно было разместить в одном или двух (а может быть, даже в трех) томах. Одна эта книга включает около 1500 упражнений с ответами для самостоятельной работы, а также сотни полезных фактов, которые вы не найдете ни в каких других публикациях.
