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

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

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

Остаток от деления рейтинга на 5 показывает, какой объем рутинной работы потребуется для решения данной-задачи. Таким образом, для решения упражнения с рейтингом 24 может потребоваться больше времени, чем для упражнения с рейтингом 25, но для последнего необходим более творческий подход.

Автор очень старался правильно присвоить рейтинги упражнениям, но тому, кто составляет задачи, трудно предвидеть, насколько сложными они окажутся для кого-то другого. К тому же одному человеку некая задача может показаться простой, а другому - сложной. Таким образом, определение рейтингов - дело достаточно субъективное и относительное. Я надеюсь, что рейтинги помогут вам получить правильное представление о степени трудности задач, но их следует воспринимать в качестве ориентира, а не в качестве абсолюта.

Эта книга написана для читателей с различным уровнем математической подготовки и научного кругозора, поэтому некоторые упражнения рассчитаны исключительно на тех, кто серьезно интересуется математикой или занимается ею профессионально. Если рейтингу предшествует буква М, значит, математические понятия и обоснования используются в упражнении в большей степени, чем это необходимо тому, кто интересуется в основном программированием алгоритмов. Если же упражнение отмечено буквами НМ, то для его решения необходимо знание высшей математики в большем объеме, чем дается в настоящей книге. Но пометка НМ совсем необязательно означает, что упражнение трудное.

Перед некоторыми упражнениями стоит стрелка которая означает, что они особенно поучительны и их очень рекомендуется выполнить. Само собой разумеется, никто не ожидает, что читатель (или студент) будет решать все задачи, поэтому наиболее важные из них и были выделены. Но это ни в коем случае не означает, что другие упражнения выполнять не стоит! Каждый читатель должен хотя бы попытаться решить все задачи, рейтинг которых меньше или равен 10. Стрелки помогут выбрать задачи с более высокими рейтингами, которые следует решать в первую очередь.

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

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

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

УПРАЖНЕНИЯ

► 1. [00] Что означает рейтинг М207

2. [10] Какое значение для читателя имеют упражнения, которые приводятся в учебниках?

3. [Ц] Докажите, что 13 = 2197. Обобщите ответ. (Скучных задач, подобных этой, автор старался избегать.)

4. [НМ45] Докажите, что если п - целое число, п > 2, то уравнение х" -Ь г/" = z" неразрешимо в целых положительных числах х, у, z.

Мы обсудили этот вопрос со всех сторон. Перед нами факты, изложенные систематично и по порядку.

- ЭРКЮЛЬ ПУАРО (HERCULE POIROT), Убийство в восточном экспрессе (1934)

ОСНОВНЫЕ ПОНЯТИЯ

Многие не сведущие в математике люди думают, что поскольку назначение аналитической машины Бэббиджа (ВаЬЬаде) - выдавать результаты в численном виде, то природа происходящих в ней процессов должна быть арифметической и численной, а не алгебраической и аналитической. Но они ошибаются. Машина может упорядочивать и комбинировать числовые Значения так же, как и буквы или любые другие символы общего характера. В сущности, при выполнении соответствующих условий она могла бы выдавать результаты и в алгебраическом виде.

АВГУСТА АДА (AUGUSTA ADA), графиня Лавлейс* (Lovelace) (1844)

Прошу вас, ради всего святого, сначала научитесь простому и только потом переходите к сложному.

- ЭПИКТЕТ (EPICTETUS), Беседы iv.i

1.1. АЛГОРИТМЫ

Понятие алгоритм является основным для всей области компьютерного программирования, поэтому начать мы должны с тщательного анализа этого термина. Слово "алгоритм" (algorithm) (иногда используется устаревшее слово "алгорифм".- Прим. перев.) уже само по себе представляет большой интерес. На первый взгляд может показаться, будто кто-то собирался написать слово "логарифм" (logarithm), но случайно переставил первые четыре буквы. Этого слова еще не было в издании словаря Websters New World Dictionary, вышедшем в 1957 году. Мы находим там только устаревшую форму "algorism" - старинное слово, которое означает "выполнение арифметических действий с помощью арабских цифр". В средние века абакисты считали на абаках (счетных досках), а алгоритмики использовали "algorism". В эпоху Возрождения происхождение этого слова оказалось забытым. Одни лингвисты того времени пытались объяснить его значение путем сочетания

• Дочь великого английского поэта Дж. Г. Байрона, которую считают основоположницей программирования. Большинство идей и принципов программированиядля аналитической машины Бэббиджа было рассмотрено в ее книге "Комментарии". Прим. перев.