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