Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 3
Текст из файла (страница 3)
Средняя задача, которая позволяет проверить, понял лн читатель основ- ные положения изложенного материала. Чтобы получить исчерпываю- щий ответ, может понадобиться примерно 15-20 минут. Задача умереннои сложиоати. Для ее решения может понадобиться более двух часов (а если одновременно вы смотрите телевизор, то еще бсльше). 10 Упгажнпиия, приведенные в втой серии книг, предназначены как ддя самостоятельной проработки, так и для семинарских занятий. Очень трудно и, наверное, просто невозможно выучить предмет, только читая теорию и не применяя ее для решения конкретных задач, которые заставляют задуматься о прочитанном.
Более того, мы лучше всего заучиваем то, до чего дошли самостоятельно, своим умом, Позтому упражнения занимают важное место в данном издании. Я приложил немало усилий, чтобы сделать их как можно более информативными, а также отобрать задачи, которые были бы не только поучительны, но и позволяли читателю получить удовольствие от их решения. Во многих книгах простые упражнения даются вместе с исключительно сложшями. Это не всегда удобно, так как читателю хочется знать заранее, сколько времени ему придется затратить на решение задач (иначе в лучшем случае он их только просмотрит). В качестве классического примера подобной ситуации можно привести книгу Ричарда Беллмана (В1спагб ВеИпип) Динамическое программирование (М.: Изд-во иностр.
лиг., 1960), Это очень важная, новаторская работа, но у нее есть один недостаток: в конце некоторых глав в разделе "Упражнения н научные проблемы" среди серьезных, еще нерешенных проблем приводится простейшие вопросы. Говорят, что кто-то однажды спросил д-ра Беллмана, как отличить упражнения от научных проблем, и он ответил: "Если'вы можете решить задачу, значит, зто упражнение; в противном случае зто научная проблема". Совершенно очевидно, что в книге, подобной втой, должны быть приведены и сложные научные проблемы, и простейшие упражнения.
Поэтому, чтобы читатель не ломал голову, пытаясь отличить одно от другого, были введены рейтинги, которые определяют степень сложности каждого упражнения. Эти рейтинги имеют следующее значение. Достаточно сложная илн трудоемкая задача, которую вполне можно включить в план семинарских занятий. Предполагается, что студент должен справиться с ней, затратив не слишком много времени, и решение будет нетривиальным. Научная проблема, которая (насколько известно автору в момент написанкя книги) пока еще не получила удовлетворительного решения, хотя найти его пытались очень многие. Если вы нашли решение подобной проблемы, то опубликуйте его; более того, автор данной книги будет очень признателен, если ему сообщат решение как можно скорее (при условии, что оно правильно).
Интерполируя по втой "логарифмической" шкале, можно понять, что означает любой промежуточный рейтинг. Например, рейтинг 17 говорит о том, что упражнение немного проще, чем задача средней сложности, Если задача с рейтингом И будет впоследствии решена каким-либо читателем, то в следующих изданиях данной книги и в списке ошибок, опубликованных в 1псегпес, оиа может иметь рейтинг 4Б (адрес ЖеЬ-страницы приводится на обложке кпиги). Остаток от деления рейтинга на 5 показывает, какой объем рутинной работы потребуется для решения данной задачи. Таким образом, для выполнения упражнения с рейтингом 24 может потребоваться больше времени, чем для упражнения с рейтингом йб, но для последнего несбходим более творческий подход. Автор очень старался правильно присвоить рейтинги упражнениям, но тому, кто составляет задачи, трудно предвидеть, насколько сложнымн они окажутся для кого-то другого.
К тому же одному человеку некая задача может показаться простой, а другому — сложаой. Таким образом, определение рейтингов — дело достаточно субъективное и относительное, Я надеюсь, что рейтинги помогут вам получить правильное представление о степени трудности задач, но нх следует воспринимать в качестве ориентира, а не в качестве абсолюта, Эта книга написана для читателей с различным уровнем математической подготовки и научного кругозора, поэтому некоторые упражнения рассчитаны исключительно на тех, кто серьезно интересуется математикой илн занимается ею профессионально.
Если рейтингу предшествует буква М, значит, математические понятия и обоснования используются в упражнении в большей степени, чем это необходимо тому, кто интересуется в основном программированием алгоритмов. Если же упражнение отмечено буквами НМ, то для его решения необхолимо знание высшей математики в большем объеме, чем дается в настоящей книге.
Но пометка НМ совсем необязательно означает, что упражнение трудное. Перед некоторымн упражнениями стоит стрелка "ь", которая означает, что они особенно поучительны и их очень рекомендуется выполнить. Само собой разумеется, никто не ожидает, что читатель (или студент) будет решать есе задачи, поэтому наиболее важные из них и были вьщелеиы. Но зто ни в коем случае не означает, что другие упражнения выполнять не стоит! Каждый читатель должен хотя бы попытаться решить все задачи, рейтинг которых меньше нли равен 10.
Стрелки помогут выбрать задачи с более высокими рейтингами, которые следует решать в первую очередь. К большинству упражнений приведены ответы, помещенные в отдельном разделе в конце книги. Пожалуйста, пользуйтесь ими разумно: ответ смотрите только после того, как приложите все усилия, чтобы решить задачу самостоятельно, либо если у вас совершенно нет времени на ее решение. Ответ будет поучителен н полезен для вас только в том случае, если вы ознакомитесь с ним после того, квк найдете свое решение или изрядно потрудитесь над задачей. Ответы к задачам излагаются очень кратко и схематично, так как предполагается, что читатель честно пытался решить задачу собственными силамн.
Иногда в приведенном решении лается меньше информации, чем спрашивалось, но чаще бывает наоборот, Вполне возможно, что полученный вами ответ окажется лучше того, который помещен в книге, или вы найдете ошибку в ответе. В таком случае автор был бы очень признателен, если бы вы как можно скорее подробно сообщили ему об этом; тогда в последующих изданиях книги будет опубликовано более удачное решение, а также имя его автора. Решая задачи, вы„как правило, можете пользоваться ответами к предыдущим упражнениям, за исключением случаев, когда это будет оговорено особо.
Рейтинги упражнениям присваивались в расчете именно иа это, и вполне возмсскно, что рейтинг упражнения и + 1 ниже рейтинга упражнения и, даже если результат упражнения и является его частным случаем. УПРАЖНЕНИЯ 1. (00) Что означает рейтинг М807 2. ~10) Какое значение лля читателя имеют упражнения, которые приводятся в учебниках? 3 )ул) Леонард Эйлер (1 еовцагб Еи)ег) в 1772 году предположил, что уравнение ил+я~+ В~ = г' не имеет решения в целых положительных числах, но Ноам Элкис (Хоалп Ейбее) доказал в 1987 голу, что сушествует бесконечное множество решений ~см. Маги. Сошр.
51 (1988), 825-835). Найдите все целочисленные решения, такие, что О < ш < х < р < х < 10е, 4. ~М50) Докажите, что если н — целое число, и > 4, то уравнение лн'-~-я + Вч и лн неразрешимо в целых положительных числах ш, х, у, л. упражнения — лучший инструмент познания. — РОБЕР Г РЕКОРД (йОВЕйТ йЕСОйОЕ), тле уклетлгоне ог иигге (1887) ГЛАВА З СЛУЧАЙНЫЕ ЧИСЛА Каждый, кто использует арифметические методы генерирования случайных чисел, безусловно, грешна — джОн ФОн неймАн (ЗОни мОН иецмАНН) (1951) О еероятност» «ель «то забудет, обманшиком вовек не будек — ДЖОН ГЕЙ (ЗОНН ЕАЗА) (1727) Достаточно лишь нес«аль«их лучей севта, чтобы ломочь людям в совершенствовании их 'стохастических" слособностей.
— ДЖОН ОУЭН (СОНМ ОЧЧЕМ) (1662) 3.1. ВВЕДЕНИЕ Числа, которые выбираются случайным образом, находят множество полезных применений. а) Моделирование. При использовании компьютера для моделирования естественных явлений случайные числа нужны для того, чтобы сделать эти модели похожими на реальные явления. Моделирование применяется во многих областях, начиная от исследований в ядерной физике (где частицы испытывают случайные столкновения) и заканчивая исследованием операций (где люди прибывают, например, в аэропорт через случайные промежутки времени).
Ь) Выборочный мееод. Часто бывает невозможно исследовать все варианты, но случайная выборка обеспечивает понимание того, что можно назвать «типичным" поведением. с) гтцслеинмй анализ. Для решения сложных задач численного анализа была разработана остроумная техника, использующая случайные чисаа. Об этом ивлисано несколько книг. б) Комиьюшериое программирование. Случайные величины являются хорошим источником данных для тестирования эффективности компьютерных алгоритмов. Более важно то, что они играют решающую роль прн использовании рандомиэированных алгоритмов, которые часто намного превосходят своих детерминированных двойников.
В этой сернн книг нас, в первую очередь, интересует именно такое применение случайных чисел, Этим объясняется то, что случайные числа рассматриваются уже здесь, в главе 3, прежде чем появится большинство других компьютерных алгоритмов. е) Принятие решений. Говорят, что многие администраторы прнннмают решения, бросая монету, игральную кость либо каким-нибудь другим подобным способом. Сплетничают, что некоторые профессора в колледжах ставят оценки, используя тот же метод. Иногда важно принять полностью "беспристрастное" решение.
Случайность является также важной частью оптимальных стратегий в теории матричных игр. 1) Эстетика. Небольшая добавка случайности оживляет музыку и компьютерную графику. Например, рисунок ПППППППП „„„,„„,„,„„, ПППППППП ПППППППП,ы„,'„'", „'„"',",",'" '","„„ч„ПППППППП ПППППППП '" ' ' ПППППППП 1См. 1У, Е. КпигЬ, ВиП. Ашег. Маго, Бос. 1 (1979), 369.) к) Развлечения. Многие считают, что они замечательно проводят время, бросая игральные костя, тасуя колоду карт, вращая колесо рулеткя и т. п. Такие традиционные способы использования случайных чисел получили название метод МонтеКарло.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
