AOP_Tom2 (1021737), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Каждый алгоритм должен не только находить числовое решение проблемы, но и хорошо сочетаться с внутренними операциями цифрового компьютера. В большинстве случаев человек не может оценить всю красоту подобных алгоритмов, если толька ан не владеет машинным языком компьютера.

Эффективность соответствующей компьютерной программы- -это жизненно важный фактор, который нельзя отделить ат самого алгоритма. Проблема заключается в там, чтобы найти оптимавьные способы работы компьютеров с числами, а зто включает вопросы тактики и численного анализа. Поэтому предмет данной книги, без сомнения. относится к компьютерной науке так же, как к разделам математики, занимающимся численныл1 анализом.

Некоторые математики, работающие в "высоких сферах" численного анализа, будут считать, что предлагаемые в этом томе темы относятся к сфере влияния системных программистов. А специалисты, работающие в "высоких сферах" системного программировании, наоборот, решат, что изучать рассматриваемые темы — дело численных аналитиков. На я все-таки надеюсь, что найдутся читатели, которые захотят внимательно изучить эти фундаментальные методы.

Хотя данные методы можно отнести, скорее всего, к нижнему уровню, на них основаны все грандиозные компьютерные приложения, предназначенные для решения числовых задач. Отсюда следует, насколько важно хорошо в них разобраться. В настоящем томе будет рассмотрена область, которая находится на стыке численного анализа и программирования; именно это и делает предмет книги весьма интересным. В данном томе по сравнению с другими содержится значительно больший объем математического материала; это обусловлено спецификой изучаемых тем.

Причем в большинстве случаев нужные математические темы раскрываются прямо ня страницах книги практически с нуля (или на основании результатов, доказанных в томе 1). На в некоторых разделах предполагается, чта читатель знаком с используемым материалам. В этом тамо содержатся главы 3 н 4.

Глава 3 посвящена случайным числам: здесь изучаются не только различные методы генерирования случайных чисел, но и статистические критерии случайности, а также преобразование равномерно распределенных случайных чисел в другие типы случайных величин. Последнян тема позволяет проиллюстрировать практическое применение случайных чисел. В эту главу также включен раздел, повествующий о природе самой случайности.

Глава 4 — это захватывающая история о том, какие открытия были сделаны в арифметике в результате многовекового прогресса. В ней обсуждаются различные системы представления чисел н способы преобразования одной системы в другую: рассматривается арифметика чисел с плавающей точкой, целых чисел высокой точности, рациональных дробей, полиномов н степенных рядов, а также вопросы разложения на множители и нахождения наибольших общих делителей.

Каждая из глав 3 и 4 может использоваться в качестве основы для семестрового университетского курса, причем изложение материала можно построить так, чтобы его можно было излагать на разных уровнях: как для первокурсников, так н для выпускников. В настоящее время курсы "Случайные числа" и "Арифметика" пе входят в программы многих университетов. Но я надеюсь, читатель увидит, что в этих главах в едином ключе освещается материал, имеющий реальную образовательную ценность. Мой собственный опыт подтверждает, что он служит прекрасным способом ознакомления студентов с элементарной теорией вероятности и теорией чисел.

Почти все темы, которые обычно рассматривают в таких вводных курсах, естественно возникают в связи с вопросами практического применения теории. Кроме того, обсуждение на лекциях вопросов практического использования результатов может стать той движущей силой, которая вызовет у студентов интерес к учебе н поможет понять важность и значение теории. Более того, в каждой главе содержатся упоминания о более сложных темах, которые у многих студентов вызовут интерес к дальнейшему изучению математики.

Этот том, в основном, представляет собой полную и самостоятельную кингу; исключение составляют только вопросы, касающиеся компьютера И1Х, который описывался в томе 1. В приложении Б приведены использованные в данной книге математические обозначения, которые иногда отличаются от принятых в традиционной математической литературе.

Предисловие к третьему изданию Когда в 1980 году второе издание этой книги было закончено, в ней впервые были использованы системы компьютерного набора ТБХ и ЬЛЕТЯГОМТ. А теперь я рад отметить завершение разработки этих систем возвратом к книге, нагорав вдохновила меня на их создание. Наконец-то мне удалось внести все тома в персональный компьютер и таким образом получить ее электронную версию, что позволит в дальнейшем вносить любые изменения в технологию печати и отображения на экране, Такой способ работы предоставил мне возможность сделать буквально тысячи улучшений, и я добился того, о чем так долго мечтал. В этом новом издании я смог проверить каждое слово в тексте, стараясь сохранить юношеский задор оригинальных предложений и в то же время внести ббльшую зрелость суждений.

Были добавлены десятки новых упражнений, а на десятки старых даны новые или улучшенные ответы. Изменения коснулись всего текста, но особенно это относится к разделам 3.5 (теоретнческие основы случайности), 3.6 (универсальные генераторы случайных чисел), 4.5,2 (двоичный алгоритм нахождения наибольшего общего делителя) и 4.7 (композиция и итерация степенных рядов). Ф Таким образом, работа над книгой Искусство программирования продолжается.

Исследования получнсленных алгоритмов продвигаются с феноменальной скоростью. Именно поэтому некоторые части данной книги начинаются пиктограммой ЯВ процессе построениям (это своеобразное извинение за то, что приведены не самые новые данные). Мон файлы переполнены важными материалами, которые я планирую включить в окончательное, знаменательное четвертое издание тома 2 (оно выйдет, вероятно, через 16 лет). Но сначала я должен закончить тома 4 н 5.

Я хочу, чтобы они были опубликованы сразу же, как только будут готовы к печати. Я чрезвычайно благодарен сотням людей, которые помогали мне собирать материал в течение последних 35 лет. Большая часть тяжелой работы по подготовке этого нового издания была выполнена Сильвио Леви (6!!ч!о гречу), который профессионально отредактировал электронную версию текста, а также Джеффри Олдхэмом (ое>гегеу О!4Ьаш), который конвертировал почти все оригинальные иллюстрации в формат МЕТВРОБТ. Я исправил все ошибки, которые бдительные читатели обнаружили во втором издании (а также ошибки, которых, увы, не заметил никто), и постарался избежать появления новых ошибок. Тем не менее я допускаю, что некоторые огрехи все же остались, и хотел бы пх исправить как можно скорее. Поэтому за кажду>о опечатку*, а также ошибку, относящуюся к сути излагаемого материала илн к приведенным историческим сведениям, я охотно заплачу $2,56 тому, кто первым ее найдет.

На >>>еЬ-странице, адрес которой приведен на обложке книги, содержится текущий список всех ошибок, о которых мне сообщили. П. Е. К. Сп>анфорд, Кплпфорнил Июль 1997 Когда работа над книгой прпдолжаетСя В течениЕ воСьми лЕт, то ПОяВЛЯЕтСя очень мнОго людей — коллет, нвборШиков, Стулентоа, преподавателей и друзей, которых нужно поблагодарить. но я не собираюсь освобождать их от ответственности эа ошибки, которые остались е тексте. Они должны были их исправить! Иногда они даже несут ответственность за идеи, которые е конце концов оказываются ошибочными. но я любом случае я благодарен всем своим сотоуднккам. — ЭДВАРД Ф.

КЭМПБЕЛЛ (МЛ.) (ЕОЧЧА>яО г. САМРВЕС>, о>Ч.) (1975) Оетепбй пигпегия (В числах ты найдешь покой)— зто истина дурзков; ПЕРЕ>ой ПцГПЕ>ия (В ЧИСЛаХ тЫ НайдЕШЬ ПОГИ6ЕЛЬ)— истина мудоых. — Ч. К. КОЛТОН (С. С. СО~ ТОН) (1820) Имеется я виду оригинал настоящего яадаяяя. — Лрож. рад. ПРИМЕЧАНИЯ К УПРАЖНЕНИЯМ Рейтинг Обвяснение Чрезвычайно простое упражнение, на которое можно ответить сразу же, если прочитанный материал понят. Упражнения подобного типа почти всегда можно решить 'в уме". Простая задача, которая заставляет задуматься над прочитанным, но не представляет особых трудностей. На ее решение вы затратите не больше минуты; в процессе решения могут понадобиться карандаш и бумага. Средняя задача, которая позволяет проверить, понял ли читатель основ- ные положения изложенного материала.

Чтобы получить исчерпываю- щий ответ, может понадобиться примерно 15.-20 минут. Задача умеренная сложносхи. Для ее решения может понадобиться более двух часов (а если одновременно вы смотрите телевизор, то еще больше). 80 УцгажНЕНИЯ, ПрннсдЕННЫЕ В ЭтОй СЕРИИ КНИГ, ПрЕдяаЗНаЧЕНЫ КаК ддя СаМОСтОятельной проработки, так и для семинарских занятий. Очень трудно и, наверное, просто невозможно выучить предмет, только читая теорию и не применяя ее для решения конкретных задач, которые заставляют задуматься о прочитанном.

Более того, мы лучше всего заучиваем то, до чего дошли самостоятельно, своим умом. Поэтому упражнения занимают важное место в данном издании. Я приложил немало усилий, чтобы сделать их как можно более информативными, в также отобрать задачи, которые были бы не только поучительны, но и позволяли читателю получить удовольствие от их решения. Во многих книгах простые упражнения даются вместе с исключительно сложными. Это не всегда удобно, так как читателю хочется знать заранее, сколько времени ему придется затратить на решение задач (иначе в лучшем случае он их только просмотрит). В качестве классического примера подобной ситуации можно привести книгу Ричарда Беллмана (И1спагб Вейшап) Дпнамнческое программирование (Мл Изд-во иностр. лиг..

19бО). Это очень важная, новаторская работа, но у нее есть один недостаток: в конце некоторых глав в разделе "Упражнения и научные проблемы" среди серьезных, еще нерешенных проблем приводятся простейшие вопросы. Говорят, что кто-то однажды спросил д-ра Беллмана, как отличить упражнении от научных проблем, и он ответил: "Если' вы можете решить задачу, значит, это упражнение; в противном случае это научная проблема' ! Совершенно очевидно, что в книге, подобной этой, должны быть приведены и сложные научные проблемы, и простейшие упражнения. Поэтому, чтобы читатель не ломал голову, пытаясь отличить одно от другого, были введены рейтинги, которые определяют степень сложности каждого упражнения. Эти рейтинги имеют следующее значение. 00 Достаточно сложная или трудоемкая задача, которую вполне можно включить в план семинарских занятий.

Предполагается, что студент должен справиться с ней, затратив не слишком много времени, и решение будет нетривиальным. Научная проблема, которая (насколько известно автору в момент написания книги) пока еще не получила удовлетворительного решения, хотя найти его пытались очень многие. Если вы нашли решение подобной проблемы, то опубликуйте его; более того, автор данной книги будет очень признателен, если ему сообщат решение как можно скорее (при условии, что оно правильно). Интерполируя по этой "логарифмической" шкале, можно понять, что означает любой промежуточный рейтинг.

Характеристики

Список файлов книги