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