Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 2
Текст из файла (страница 2)
Надеемся. что читатель не будет удивлен, найдя ссылки иа главы 7, 8 и последующие не вошедшие в предлагаемые три тома главы. Мы вместе с автором надеемся, что очень скоро оии будут опубликованы н, безусловно, сразу же появятся в русском переводе в качестве продолжения этого издании. Счедует также обратить внимание на далеко не всегда стандартные обозначения, которымн пользуется автор. Так же. как и определения, эти обозначения могут появиться в 1-м томе, а вводиться во 2-м. Поэтому без указателя обозначений пользоваться книгой было бы чрезвычайно трудно.
Хочу также обратить внимание на запись 1М. где а— некоторое высказывание. Эта запись встречается в формулах, а иногда и в тексте, и обозначает величину, равную индикатору а. — Профессор И. В. Козаченко ПРЕДИСЛОВИЕ Дорогая ОФелия! Мне плохо от этих чисел: я не способен сосчитать мои станки — Гамлет (экт и, сцена 2, строка 120) Алгоритмы, описываемые в этой книге, имеют непосредственное отношение к числам. Я считаю, что их справедливо называют полрчпслеинььмп, так как онн находятся иа границе между численными и символьными методами.
Каждый алгоритм должен не тгьчько находить числовое решение проблемы, но и хорошо сочетаться с внутренними операциями цифрового компьютера. В большинстве случаев человек не может оценить всю красоту подобных алгоритмов, если только он не владеет машинным языком компьютера. Эффективность соответствующей компьютерной программы — это жизненно важный фактор, который нельзя отделить от самого алгоритма. Проблема заключается в том, чтобы найти оптимальные способы работы компьютеров с числами, а это включает вопросы тактики к численного анализа.
Поэтому предмет данной книги, без сомнения, относится к кампьютерной науке тэк же, как к разделам математики, занимающимся численным анализом, Некоторые математики, работающие в "высоких сферах" численного анализа, бупут считать, что предлагаемые в этом томе темы относятся к сфере влияния системных программистов. А специалясты, работающие в "высоких сферах" системного программирования, наоборот, решат, что изучать рассматриваемые темы — дело численных аналитиков. Но я все-такн надеюсь, что найдутся читатели, которые захотят внимательно изучить зти фундаментальные методы. Хотя данные методы можно отнести, скорее всего, к нижнему уровню, на них основаны все грандиозные компьютерные приложения, предназначенные для решения числовых задач. Отсюда следует, насколько важно хорошо в ннх разобраться.
В настоящем томе будет рассмотрена область, которая находится на стыке численного анализа и программирования; именно это и делает предмет книги весьма интересным. В данном томе по сравнению с другими содержится значительно больший объем математического материыа; это обусловлено спецификой изучаемых тем. Причем в большинстве случаев нужные математические темы раскрываются прямо на страницах книги практически с нуля ~или на основании результатов, доказанных в томе 1). Но в некоторых разделах предполагается, что читатель знаком с используемым материалом. В этом томе содержатся главы 3 и 4. Глава 3 посвящена случайным числам: здесь изучаются не только различные методы генерирования случайных чисел, но и статистические критерии случайности, а также преобразование равномерно распределенных случайных чисел в другие типы случайных величин.
Последняя тема позволяет проиллюстрировать практическое применение случайных чисел. В зту главу также включен раздел, повествующий о природе самой случайности. Глава 4 — зто захватывающая история о том, какие открытия были сделаны в арифметике и результате многовекового прогресса. В ией обсуждаются различные системы представления чисел и способы преобразования одной системы в другую; рассматривается арифметика чисел с плавающей точкой, целых чисел высокой точности, рациональных дробей, полиномов и степенных рядов, а также вопросы разложения на множителя и нахождения наибольших общих делителей.
Каждая из глав 3 и 4 может использоваться в качестве основы для семестрового университетского курса, причем изложение материала можно построить так, чтобы его можно было излагать иа разных уровнях: как для первокурсников, так и для выпускников. В настоящее время курсы "Случайные числа" и "Арифметика" не вхолят в программы многих университетов. Но я надеюсь, читатель увкдит, что в этих главах в едином ключе освещается материал, имеющий реальную образовательную ценность. Мой собственный опыт подтверждает, что он служит прекрасным способом ознакомления студентов с элементарной теорией вероятности и теорией чисел.
Почти все темы, которые обычно рассматривают в таких вводных курсах, естественно возникают в связи с вопросами практического применения теории. Кроме того, обсуждение иа лекциях вопросов практического использования результатов может стать той движущей силой, которая вызовет у студентов интерес к учебе и поможет понять важность и значение теории. Более того, в каждой главе содержатся упоминания о более сложных темах, которые у многих студентов вызовут интерес к дальнейшему изучению математики. Этот том, в основном, представляет собой полную и самостоятельную книгу; исключение составляют только вопросы, касающиеся компьютера М1Х, который описывался в томе 1.
В приложении В приведены использованные в данной книге математические обозначения, которые иногда отличаются от принятых в традиционной математической литературе. Предисловие к третьему изданию Когда в 1990 году второе издание этой книги было закончено, в ней впервые были использованы системы компьютерного набора ТВХ и ьэЕтйГОмт. А теперь я рад отметить завершение разработки этих систем возвратом к книге„которая вдохновила меня на их создание.
Наконец-то мне удалось внести все тома в персональный компьютер и таким образом получить ее электронную версию, что позволит в дальнейшем вносить любые изменения в технологию печати и отображения на экране, Такой способ работы предоставил мне возможность сделать буквально тысячи улучшений, и я добился того, о чем так долго мечтал. В этом новом издании я смог проверить каждое слово в тексте, стараясь сохранить юношеский задор оригинальных предложений и в то же время внести ббльшую зрелость суждений.
Выли добавлены десятки новых упражнений, а на десятки старых даны новые илн улучшенные ответы. Изменения коснулись всего текста, но особенно зто относится к разделам З.а (теоретические основы случайности), 3.6 (универсальные генераторы случайных чисел), 4.5.2 (дноичный алгоритм нахождения наибольшего общего делителя) и 4,7 (композиция и итерация степенных рядов). Ф. Таким образом, работа над книгой Искусство программпроаанин продолжается. Исследования получнсленных алгоритмов продвигаются с феноменальной скоростью. Именно поэтому некоторые части данной книги начинаются пиктограммой яВ процессе построения" (зто своеобразное извинение за то, что приведены не самые новые данные). 54ои файлы переполнены важными материалами, которые я планирую включить в окончательное„знаменательное четвертое издание тома 2 (оно выйдет., вероятно, через 16 лет).
Но сначала я должен закончить тома 4 н 5. Я хочу, чтобы они были опубликованы сразу же, как только будут готовы к печати. Я чрезнычайно благодарен сотням людей, которые помогали мне собирать матерпал а течение последних 35 лет. Большая часть тяжелой работы по подготовке этого ноиого издания была выполнена Сильнио Леви (Р1!У[о?,еуу), который профессионально отредактировал электронную версию текста, а также Джеффри Олдхзмом (деКегеу 0[бЬат), который коинертнровал почти нсе оригинальные иллюстрации а формат МЕТПРОБТ. Я исправил все ошибки, которые бдительные читатели обнаружили ео втором издании (а также ошибкя, которых, уиы, не заметил никто), и постарался избежать появления новых ошибок.
Тем не менее я допускаю, что некоторые огрехи нсе же остались, и хотел бы их испраяить как можно скорее. Поэтому за каждую опечатку*, а также ошибку, относящуюся к сути излагаемого материала нли к приведенным историческим снедениям, я охотно заплачу $2,56 тому, кто первым ее найдет. На ЖеЬ-странице, адрес которой приведен на обложке кикги, содержится текущий список всех ошибок, о которых мне сообщили. В. В.
К. Спюнйзорд, Калцфарння Июль 2997 Когда работа над хннгой продояжаегая е течеНнЕ ЕОСьмн лЕт, ГО появляетСЯ очень много людей — коллег, наборшняоя, студентов, препалэяатеяей н друэеу, которых нузяно поблагодарить. Но я не собираюсь осеобозкпать нх от огеетсгяенности зэ ошибки, которые остались и тексте. Онн должны были нх исправить! Иногда онн даже несут огяетстяенность за идеи, котоРые и конце концов оказгнвэюгся ошнбочнын». но в любом случае я благодарен всем своим сотрудникам, — ЭДВАРД аз. КЭМПБЕЛЛ (Мя,) (ЕРЧЧАй0 Е. САМРВЕсс, зй.) (1йтб) Оегепий пигпегиз [В числах ты найдешь покой)— Эгп нСГННа ДУРахае; Оерегбй пигпегиэ [В числах ты найдешь погибель)— истина мудрых.
— Ч. К. КОЛТОН (С. С. СО1 ТОМ) (1820) ' Имеется в виду оригинал яастояязяго издания. — Прим. рад ПРИМЕЧАНИЯ К УПРАЖНЕНИЯМ Рейтине Обааснеиие Чрезвычайно простое упражнение, на которое можно ответить сразу же, если прочитанный материал понят. Упражнения подобного типа почти всегда можно решить "в уме". Простая задача„которая заставляет задуматься над прочитанным, но не представляет особых трудностей. На ее решение вы затратите не болыпе минутьц в процессе решения могут понадобиться карандаш и бумага.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
