Д. Кнут - Искусство программирования том 1 (1119450), страница 3
Текст из файла (страница 3)
В частности, я попытался проследить историю каждой темы и заложить прочный фундамент ее дальнейшего развития. Я старался использовать точную терминологию, согласованную с той, которая применяется в современных публикациях, и попытался сообщить обо всех известных идеях последовательного программирования, выделяющихся простотой и изяществом формулировок. Теперь несколько слов о математическом содержании данного многотомного издания. Материал излагается так, что он вполне доступен даже лицам со средним образованием; более сложные фрагменты они смогут просмотреть или просто опустить.
В то же время те, кто имеют склонность к математике, смогут изучить интересные математические методы, связанные с дискретной математикой. Подобная двойственность представления информации была достигнута, с одной стороны, за счет присвоения рейтинга каждому упражнению (чтобы читатель смог отличать сложные с математической точки зрения упражнения от простых), а с другой стороны, благодаря такой организации разделов, при которой главные математические результаты сформулированы перед доказательствами. Доказательства предлагается либо провести самостоятельно в кюгестве упражнений (ответы на которые приводятся в отдельном разделе), либо найти в конце раздела.
Читатель, который, главным образом, интересуется программированием, а не математикой, может прекратить чтение раздела, как только математический материал станет слишком сложным для восприятия. С другой стороны, читатель- математик найдет для себя очень много интереснейших фактов. Многие математические публикация на тему программирования были ошибочными, поэтому одна из целей данной книги — предоставить читателю правильное математическое обоснование предмета изложения. И так как и считаю себя математиком, моя прямая обязанность — правильно (насколько смогу) изложить материал с математической точки зрения.
Для чтения большей части математического материала вполне достаточно знания элементарной математики, так как почти вся остальная теория разрабатывается здесь же. Но иногда у меня возникает необходимость в более глубоких теоремах теории комплексного переменного, теории вероятностей, теории чисел и т. д, В подобных случаях я ссылаюсь на книги, содержащие подробное изложение данных тем. Самое сложное решение, которое мне пришлось принять при подготовке этих книг, касалось способа представления различных методов; Преимущества блоксхем и пошаговых описаний алгоритмов хорошо известны; эти вопросы обсуждаются в статье "Сошрп1ег-агнии г 1ожсЬаг1э" в журнале АСМ Соштитиса6опэ, Уо1, 6 (Бер1ешЬег 1963), райеэ 555-563.
Для описания любого компьютерного алгоритма необходим также формальный и точный язык. Поэтому мне нужно было решить, какой язык использовать: алгебраический, такой как А1.00Ь или гОКТКАХ, либо машинно-ориентированный. Вероятно, многие сегодняшние компьютерные специалисты не согласятся с моим решением использовать машинно-ориентированный язык, но я убедился, что это был правильный выбор. На то существуют следующие причины. а) На программиста большое влияние оказывает язык, на котором написаны программы. В настоящее время превалирует тенденция к выбору самых простых, а не самых оптимальных для компьютера конструкций языка. А программист, который знает машинно-ориентированный язык, стремится использовать более эффективные методы и таким образом создает более совершенные программы.
Ь) Все нужные нам программы, написанные на машинно-ориентированном языке, за редким исключением будут иметь небольшой размер. А это значит, что при наличии компьютера, облгдающего минимальной вычислительной мощностью, проблем с использованием таких программ у нас не возникнет.
с) Языки высокого уровня не подходят для обсуждения важных деталей, имеющих отношение к низкому уровню, таких как связь сопрограмм, генерирование случайных чисел, арифметика высокой точности и многие другие проблемы, связанные с эффективным использованием памяти. 6) Тот, кто серьезно интересуется компьютерами, должен хорошо знать машинный язык, так как он лежит в основе работы компьютера. е) Некоторое знание машинного языка необходимо в любом случае, чтобы разобраться в выходных данных программ, приведенных во многих примерах. Г) Новые алгебраические языки входят и выходят из моды приблизительно каждые пять лет, в то время как я пытаюсь говорить о "вечных истинах", С другой стороны, я признаю, что писать программы на языках высокого уровня и отлаживать эти программы значительно проще.
В сущности, начиная с 1970 года, я сам редко использовал машинный язык низкого уровня для собственных программ, так как современные компьютеры обладают большим объемом памяти и высоким быстродействием. Но для решения многих проблем, рассматриваемых в данной книге, наибольшее значение имеет искусство программирования. Например, некоторые комбинаторные вычисления нужно повторять триллионы раз, и мы сэкономим приблизительно 11,6 дней работы за счет того, что сократим время вычислений во внутреннем цикле всего на одну микросекунду. Аналогично имеет смысл приложить дополнительные усилия для написания программы, которая будет использоваться много раз в течение каждого дня на множестве компьютеров, тем более что написать эту программу нужно только один раз.
А если принять решение использовать машинно-ориентированный язык, то какому языку следует отдать предпочтение? Я мог бы выбрать язык для конкретной машины Х, но тогда те, кто используют другой компьютер, подумают, что данная книга написана только в расчете на обладателей компьютера Х. Более того, машина Л; вероятно, имеет много характерных особенностей, для которых совершенно неприменим материал данной книги, но все же его необходимо изложить. И наконец, через два года фирма — производитель машины Л' выпустит машину Х+ 1 или 10Х, и компьютер Л больше никого не будет интересовать.
Чтобы решить эту проблему, я попытался разработать "идеальный" компьютер с очень простыми правилами работы !изучить которые можно, скажем, всего за час) и очень похожий на реальные машины. Для студента нет никакой причины избегать изучения характеристик различных компьютеров; после изучения одного языка все остальные будут усваиваться гораздо легче. Кроме того, серьезный программист должен быть готов к тому, что в ходе работы ему придется сталкиваться с различными машинными языками. Поэтому остается только один недостаток использования вымышленной машины — сложность запуска написанных для нее программ.
К счастью, ва самом деле это не проблема, так как много добровольцев предложили свои услуги по написанию имитаторов гипотетической машины. Такие имитаторы идеальны для учебных целей, и работать с ними даже проще, чем с реальным компьютером. Я старался ссылаться на самые лучшие старые статьи по каждой теме, а также упоминать новые работы.
Ссылаясь на литературные источники, я использовал стандартные сокращения для названий периодических изданий, за исключением наиболее часто цитируемых журналов, для которых применялись следующие сокращения. САСМ вЂ” Сошпшшсагюпэ оГ гЬе Азвос1а1юп Гог Сошрп11пй МасЬшегу Х4СМ вЂ” Зопгпа) оГ гЬе Азэос1аг1оп 1ог Сошрпг1пя МасЫпегу Сошр. !. — ТЬе Сошрп1ег 1опгпа1 (Вг111эЬ Сошрпгег Бос1егу) МагЬ. Согпр. — МагЬеша1гсз о1 Сошршагюп АМЛХ вЂ” Ашег1свп МагЬепгаг1са1 МопгЫу ЯСОЛХР— 51АМ Зопгпа1 оп Сошрп6пя ЕОСБ — 1ЕЕЕ Бугпров1шп оп Гоцпоаг1опэ о1 Сошрпгег Бе!енсе БО11А — АСМ-51АМ Бушроэ1цш оп Ббвсгесе Ауйог11Ьшэ АТОС вЂ” АСМ Бугароэппп оп ТЬеогу оГ Сошрпс)пя Сге!!е —,1онгпа1 Йг г11е ге!не цпб алкея'ауге Ма1Ьешаг1Ь Например, "САСМ 6 (196$), 555 — 563" означает ссылку на журнал, упомянутый в одном из предыдущих абзацев этого предисловия.
Сокращение "СМагЛ' я использовал также для обозначения книги Конкретная математика, на которую есть ссылка во введении к разделу 1.2. Бблыпая часть технического материала этих книг приходится на упражнения. Если идея нетривиального упражнения принадлежала не мне, то я старался упомянуть ее автора.
Ссылки на литературу обычно даются в тексте раздела либо в ответе к упражнению. Но во многих случаях в основе упражнений лежат неопубликованные материалы, на которые нельзя дать ссылки. В течение долгих лет работы над этими книгами мне помогали многие люди, которым я благодарен от всей души.
Прежде всего, я хочу выразить благодарность моей жене Джилл ) за ее бесконечное терпение, за подготовку некоторых иллюстраций и за постоянную помощь во всем. Я признателен также Роберту В. Флойду (Р1оуп Вовег1 %'.) за то, что в 60-х годах он посвятил столько времени работе над улучшением и углублением данного материала. Тысячи других людей также оказали мне неоценимую помощь. Чтобы просто перечислить их имена, понадобилась бы еще одна такая книга! Многие из них любезно разрешили мне использовать их старые неопубликованные работы. Мои исследования в Калифорнийском технологическом институте и Станфордском университете шедро финансировались Национальным научным фондом (Ха11опа1 Бс1епсе Роппдас1оп) и департаментом морских исследований (016се оГ Хата1 НеэеагсЬ).
Издательство АсЫ1зоп-Жеэ1еу всегда оказывало мне всемерную помощь и поддержку с того самого времени, когда в 1962 году я приступил к работе над проектом. Мне кажется, что для всех этих людей лучшая благодарность — данная публикация. Она показывает, что их вклад привел к появлению книг, в которых, я надеюсь, мне удалось написать то, чего они ожидали. Предисловие к третьему изданию Потратив десять лет на разработку систем компьютерного набора МЕТЯГОНТ и ТЕХ, я теперь могу осуществить свою мечту — применить эти системы для набора книги Искусство программирования.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
