AOP_Tom3 (1021738), страница 20
Текст из файла (страница 20)
На 1ЪеЬ-странице, адрес которой приведен на обложке книги, содержится текущий список всех найденных ошибок и их исправлений, о которых мне сообщили. ПРИМЕЧАНИЯ К УПРАЖНЕНИЯМ Рейтинг Обвяснение Чрезвычайно простое упражнение, на которое можно ответить сразу же, если прочитанный материал понят. Упражнения подобного типа почти всегда можно решить "в уме". Простая задача, которая заставляет задуматься над прочитанным, но не представляет особых трудностей. На ее решение вы затратите не больше минуты; в процессе решения могут понадобиться карандаш и бумага. Средняя задача, которая позволяет проверить, понял ли читатель основ- ные положения изложенного материала.
Чтобы получить исчерпываю- щий ответ, может понадобиться примерно 15-2б минут. Задача умеренной сложности. Для ее решения может понадобиться более двух часов (а если одновременно вы смотрите телевизор, то еще больше). 00 10 Э0 Упгажнкния, приведенные в этой серии книг, предназначены как для самостоятельной проработки, так и для семинарских занятий.
Очень трудно и, наверное, просто невозможно выучить предмет, только читая теорию и не применяя ее для решения конкретных задач, которые заставляют задуматься о прочитанном. Более того, мы лучше всего заучиваем то, до чего дошли самостоятельно, своим умом. Поэтому упражнения занимают важное место в данном издании. Я приложил немало усилий, чтобы сделать их как можно более информативными, а также отобрать задачи, которые были бы не только поучительны, но и позволяли читателю получить удовольствие от их решения. Во многих книгах простые упражнения даются вместе с исключительно сложными.
Это не всегда удобно, так как читателю хочется знать заранее, сколько времени ему придется затратить на решение задач (иначе в лучшем случае он их только просмотрит). В качестве классического примера подобной ситуации можно привести книгу Ричарда Беллмана (ВйсЬагд Вейпзап) Динамическое программирование (У1с Изд-во иностр.
лиг., 1960). Это очень важная, новаторская работа, ио у нее есть один недостаток: в конце некоторых глав в разделе "Упражнения и научные проблемы" среди серьезных, еще нерешенных проблем приводятся простейшие вопросы. Говорят, что кто-то однажды спросил д-ра Беллмана, как отличить упражнения от научных проблем, и он ответил: "Если вы можете решить задачу, значит, это упражнение; в противном случае это научная проблема". Совершенно очевидно, что в книге, подобной этой, должны быть приведены и сложные научные проблемы, и простейшие упражнения. Поэтому, чтобы читатель не ломал голову, пытаясь отличить одно от другого, были введены рейтинги, которые определяют степень сложности каждого упражнения. Эти рейтинги имеют следующее значение. Достаточно сложная или трудоемкая задача, которую вполне можно вклкэчить в план семинарских занятий. Предполагается, что студент должен справиться с ней, затратив не слив~ком много времени, н решение будет нетривиальным.
Научная проблема, которая (насколько известно автору в момент написания книги) пока еще не получила удовлетворительного решения, хотя найти его пытались очень многие. Если вы нашли решение подобной проблемы, то опубликуйте его; более того, автор данией книги будет очень признателен, если ему сообщат решение как можно скорее (при условии, что оно правильно). Иитерполируя по этой "логарифмической" шкале, можно понять, что означает любой промежуточный рейтинг. Например, рейтинг 17 говорит о том, что упражнение немного проще, чем задача средней гложности. Если задача с рейтингом 50 будет впоследствии решена каким-либо читателем, то в следующих изданиях данной книги и в списке ошибок, опубликованных в 1шегпег, она может иметь рейтинг 45 (адрес %еб-страницы приводится на обложке книги).
Остаток от деления рейтинга на 5 показывает, какой объем рутинной раГюты потребуется для решения данной задачи. Таким образом, для выполнения упражнения с рейтингом 84 может потребоваться больше времени, чем для упражнения с рейтингом 55, ио для последнего необходим более творческий подход. Автор очень старался правильно присвоить рейтинги упражнениям, но тому, кто составляет задачи, трудно предвидеть, насколько сложнымн они окажутся для кого-то другого.
К тому же одному человеку некая задача может показаться простой, а другому — сложной. Таким образом, определение рейтингов — дело достаточно субъективное и относительное. Я надеюсь, что рейтинги помогут вам получить правильное представление о степени трудности задач, но их следует воспринимать в качестве ориентира„ а не в качестве абсолюта. Эта книга написана для читателей с различным уровнем математической подготовки и научного кругозора, поэтому некоторые упражнения рассчитаны исключительно на тех, кто серьезно интересуется математикой или занимается ею профессионально.
Если рейтингу предшествует буква М, значит, математические понятия и обоснования используются в упражнении в большей степени, чем это необходимо тому, кто интересуется в основном программированием алгоритмов. Если же упражнение отмечено буквами НМ, то для его решения необходимо знание высшей математики в большем объеме, чем дается в настоящей книге. Но пометка НМ совсем необязательно означает, что упражнение трудное.
Перед некоторыми упражнениями стоит стрелка "»", которая означает, что они особенно поучительны и их очень рекомендуется выполнить. Само собой разумеется, никто не ожидает, что читатель (нля студент) будет решать все задачи, поэтому наиболее важные из ких и были выделены. Но это ни в коем случае не означает, что другие упражнения выполнять не стоит! Каждый читатель должен хотя бы попытаться решить все задачи, рейтинг которых меньше или равен 10.
Стрелки помогут выбрать задачи с более высокими рейтингами, которые следует решать в первую очередь. К большинству упражнений приведены ответы, помещенные в отдельном разделе в конце книги. Пожалуйста, пользуйтесь ими разумно: ответ смотрите только Условные обозначения 00 Простейшее (ответ дать немедленно) )0 Простое (иа одну минуту) 00 Средней трудности (на четверть часа) 00 Повышенной трудности эб Высокой трудности 00 Научная проблема Рекомендуется М С математическим уклоном НМ Требует знания высшей математики УПРАЖНЕНИЯ 1. [00) Что означает рейтинг МЯО? 2.
(10) Какое значение для читателя имеют упражнения, которые приводятся в учебниках? 3. (НМэ5) Докажите, что если и — целое число, и > 2, то уравнение х" + у" = х" неразрешимо в целых положительных числах х, у, ш двух часов ежедневных упдажиений... достаточно, чтобы и клячу обучить этой Оаботе. — м. х.
мдхон (м. н. мднсм), выездка лошадей (тле наяву ногае воок) (лвьв) после того, как приложите все усилии, чтобы решить задачу самостоятельно, либо если у вас совершенно нет времени на ее решение. Ответ будет поучителен и полезен для вас только в там случае, если вы ознакомитесь с ннм после того, как найдете свое решение или изрядно потрудитесь над задачей.
Ответы к задачам излагаются очень кратко и схематично, так как предполагается, что читатель честно пытался решить задачу собственными силами. Иногда в приведенном решении дается меньше информации, чем спрашивалось, но чаще бывает наоборот. Вполне возможно, что полученный вами ответ окажется лучше того, который помещен в книге, или вы найдете ошибку в ответе.
В таком случае автор бьш бы очень признателен, если бы вы как можно скорее подробно сообщили ему об этом; тогда в последующих изданиях книги будет опубликовано более удачное решение, а также нгая его автора. Решая задачи, вы, как правило, можете пользоваться ответами к предыдущим упражнениям, за исключением случаев, когда это будет оговорено особо. Рейтинги упражнениям присваивались в расчете именно на это, и вполне возможно, что рейтинг упражнения и + 1 ниже рейтинга упражнения и, даже если результат упражнения и является его частным случаем. в5.1.
КОМБИНАТОРНЫЕ СВОЙСТВА ПЕРЕСТАНОВОК Пквкстлиовкой конечного множества называется некоторое расположение его элементов в ряд. Перестановки особенно важны при изучении алгоритмов сортировки, так как они служат для представления неупорядоченных исходных данных. Чтобы исследовать эффективность различных методов сортировки, нужно уметь подсчитывать количество перестановок, которые вынуждают повторять некоторый шаг алгоритма определенное число раз.
54ы уже не раз встречались с перестановками в предыдущих главах. Например, в разделе 1.2.5 обсуждались два основных теоретических метода построения п! перестановок и объектов; в разделе 1.3.3 были проанализированы некоторые алгоритмы, связанные с цяклической структурой и мультиплнкативными свойствами перестановок; в разделе 3.3.2 изучались нх серии монотонности. Цель настоящего параграфа - .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
