ОТВЕТЫ К УПРАЖНЕНИЯМ

Тебе ответом угождать не должен! ШЕЙЛОК, Венецианский купец (акт IV, сцена 1)

ПРИМЕЧАНИЯ К УПРАЖНЕНИЯМ

1. Средняя задача для читателя с математическими наклонностями.

4. См. W. J. LeVeque, Topics in Number Theory 2 (Reading, Mass.: Addison-Wesley, 1956), Chapter 3; P. Ribenboim, 13 Lectures on Fermats Last Theorem (New York: Springer-Verlag, 1979); A. Wiles, AnnaJs of Mathematics 141 (1995), 443-551.

РАЗДЕЛ 1.1

1. t a, a < b, b < с, с i- d, d i- t.

2. После первого случая выполнения шага El значения переменных m и п - это предыдущие значения п и г соответственно, а п > г.

3. Алгоритм F (Алгоритм Евклида). Даны два целых положительных числа тип. Найти их наибольший общий делитель.

F1. [Остаток от деления m/n.] Разделите от на п и пусть остатком будет т.

F2. [Это нуль?] Если m = О, то работа алгоритма завершается и ответом будет п.

F3. [Остаток от деления n/m.] Разделите п на т, и пусть остатком будет п.

F4. [Это нуль?] Если п = О, то работа алгоритма завершается и ответом будет от; в противном случае вернуться к шагу F1.

4. С помощью алгоритма Е получаем: п - 6099, 2166, 1767, 399, 171, 57. Ответ: 57.

5. Не обладает свойствами конечности, определенности и эффективности и, пожалуй, не имеет выходных данных. Относительно формы записи: отсутствуют буквы перед номерами шагов, краткие описания шагов, а также символ "".

6. Применяя алгоритм Е для п = 5 и m = 1, 2, 3, 4, 5, находим, что шаг Е1 выполняется 2, 3, 4, 3, 1 раз соответственно. Таким образом, среднее равно 2.6 = Ts.

7. Во всех случаях, за исключением конечного их числа, п > т. А если п > от, то в ходе первой итерации алгоритма Е эти числа просто меняются местами; поэтому Um = Тт + 1.

8. Пусть А = {а,Ь,с}, TV = 5. Выполнение алгоритма закончится, когда получим строку а8=""".

j dj bj aj

0 аЪ (Пустая строка) 1 2 Удалить одно а и одно b

либо перейти к 2.

1 (Пустая строка) с 0 0 Добавить с с левого края, перейти к 0.

2 а 6 2 3 Заменить все а на 6.

3 с о 3 4 Заменить все с на а.

4 6 6 0 5 Если 6 еще остались, повторить.

9. Например, можно сказать, что Сг представляет С\, если существуют функция д из 1\ в /г, функция h ш Q2 ъ Q\, переводящая Q2 в Qi, и функция j из Q2 в множество положительных целых чисел, удовлетворяющие следующим условиям.

a) Для любого элемента х из множества h метод вычислений С\ дает выходное значение у для входного X тогда и только тогда, когда существует у из Q2, для которого С2 дает выходное значение у для входа д{х) и h{y) = у.

b) Для любого q из Q2 имеет место равенство fi{h{q)) = /i(/P*"(g)), где /р*" - это j{g)-a итерация функции /2.

Например, пусть Ci-метод вычислений, определенный соотношениями (2), а Сг определяется соотношениями/г = {(m,n)}, Q2 = {(m, п, d)}, Q2 = /2UQ2U{(m, n, а,6,1)}U {(m, n, o, 6, r, 2)} и {(m, n, a, 6, r, 3)} U {(m, n, a, 6, r, 4)} U {(m, n, a, 6, 5)}. Пусть /2((m, n)) = (m,n,m,n,l); /2((m,n,d)) = (m,n,d); /2((m, n, a, 6,1)) = (m,n,a,6,ainod6,2); /2((m,n, a,6, r, 2)) = (m,n, 6), если r = 0, в противном случае (m, n, a, 6, г, 3); /2((m, n, о, 6, r, 3)) = (m,n,6,b,r,4); /2((m,n, a, 6,r,4)) = (m,n,a,r,5); /2(("i,n.a,6, 5)) = /2((m,n,a,6,1)).

Теперь пусть h{{jn,n)) =- g{{m,n)) = (m,n); h{{m,n,d)} = (d); Л((т, n.o, 6,1)) = (a,6,0,1); к{{т,п,а,Ь,г,2У) = (a,6,r,2); h{{m,n,a,b,r,3)) = (a,b,r,3); Л((7п,п,о,6,г,4)) = h(/2((m,n,a,6,r,4))); ft((m,n,a,6,5)) = (a,6,6,1); j((m,n,a,6,r,3))=j((m,n,a,6,r,4)) = 2; в остальных спучаях j{q) = 1. Тогда C2 представляет Ci.

Замечания. Конечно, весьма заманчиво попытаться дать более простое определение, например такое. Пусть д отображает Qi в Q2 и должно выполняться только следующее условие: дая любой вычисляемой последовательности a:o,a:i,... метода Ci g{xo),g(xi),... является подпоследовательностью вычистяемой последовательности метода С2, начинающейся с д{хо). Но это определение неадекватно; в приведенном выше примере в методе Ci первоначальные значения тип забываются, а в методе С2 - нет.

Если Сг представляет Ci с помощью функций д, h, j, а, Сз представляет Сг с помощью функций д, h, j, то Сз представляет Ci с помощью функций д", h", j", где

5"(а;)=5(5(а;)), h"(х) (х)) и /(?)= Е (90,

0<k<j(h(4))

если qo = q и qk+i = **"(gA;). Следовательно, определенное выше отношение является транзитивным. Если функция j ограничена, то будем говорить, что Сг непосредственно представляет Ci; это отношение также является транзитивным. Отношение "Сг представляет Ci" порождает отношение эквивалентности, при котором два метода вычислений эквивалентны тогда и только тогда, когда их функции от входных данных являются изоморфными. Отношение "Сг непосредственно представляет Ci" порождает более интересное отношение эквивалентности, которое, вероятно, отвечает интуитивно понятному представлению о том, что это "в сущности, тот же самый алгоритм".

Об альтернативном подходе к моделированию речь идет в работе R. W. Floyd, R. Beigel, The Language of Machines (Computer Science Press, 1994), раздел 3.3.

РАЗДЕЛ 1.2.1

1. (а) Докажите Р(0). (Ь) Докажите, что Р(0),.. • ,Р(п) влекут за собой Р{п + 1) для всех /г > 0.

2. Теорема не доказана для п = 2. Если во второй части доказательства принять п = 1, то придется допустить, что а~ = 1. Если это условие выполняется (т. е. а = 1), то теорема действительно справедлива.

3. На самом деле правая часть уравнения должна иметь вид 1 - 1/п. Ошибка возникает при доказательстве случая п = 1, когда левую часть нужно считать либо не имеющей смысла, либо равной нулю (поскольку есть п-1 слагаемых).

5. Если п - простое число, то очевидно, что оно является произведением простых чисел. В противном случае п разлагается на множители, т. е. п = km для некоторых к и т, 1 < к,т < п. Поскольку и /с, и m меньше п, по индукции их можно записать как произведение простых чисел. Следовательно, п является произведением простых чисел, фигурирующих в представлениях кит.

6. Используя обозначения, представленные на рис. 4, докажем, что А5 влечет Аб. Это очевидно, так как из А5 следует, что (а - qa)m + (Ь - qb)n = (ат + Ьп) - q(am + Ьп) = с - qd = г.

7. - (п - 1)2 +----(-1)"1 = 1 + 2 + • • + п = п(п + 1)/2.

8. (а) Покажем, что (п - п-)-1) + (п -п-(-3)н-----1- (п+п-1) равно п. Эта сумма равна

(1+3-(---(-(п= + п-1))-(1-(-3-(--- + (п2-п-1)) = ((пЧп)/2)-((п2-п)/2) = 71 (мы воспользовались соотношением (2)). Но требовалось дать доказательство по индукции, поэтому нужно использовать другой подход! Для п = 1 доказательство очевидно. Пусть п > 1; так как (п + 1) - (п + 1) = - п + 2п, то, сравнивая слагаемые сумм для значений параметров п + 1 и п, получаем, что (п + 1)-я сумма равна п-й сумме плюс

2п + + 2п+{п + 1) + {п + 1)-1;

п раз

.,3 , о„2 , „2 , о„ , 1 /„ , 1 \3

а это равно п + 2п + п + Зп + 1 = {п + 1). (Ь) Поскольку первое слагаемое для (п + 1)-й суммы на два больше последнего слагаемого п-й суммы, то из соотношения (2) получаем,

что 1 + 2 +----\-п равно сумме последовательных нечетных чисел от 1 до п + п - 1 =

(п(п-(-1)/2) = (1 + 2 +••• + п)

10. Для п = 10 доказательство очевидно. Если п > 10, то имеем 2"+ = 22" > (1+1/п)2", а по предположению индукции это больше, чем (1 + 1/п)п = (п + 1).

П. (-1)"(п + 1)/(4(п +1)2 + 1).

12. Единственным нетривиальным моментом такого обобщения является вычисление целого числа q на шаге Е2. Это можно сделать путем повторного вычитания, сводя задачу к выяснению, является ли u + v\/2 положительным, отрицательным или равным нулю, что уже не представляет особых проблем.

Легко показать, что если и + v\/2 = и + г;л/2, то и = и и г; = г;, так как \/2 - иррациональное число. Теперь ясно, что 1 и \/2 не имеют общего делителя, если мы определим делимость в следующем смысле: u + v\/2 делит о(и+г;\/2) тогда и только тогда, когда а - целое число. Алгоритм, обобщенный подобным образом, вычисляет регулярную цепную дробь отношений его входов (см. раздел 4.5.3).

[Замечание. Расширим понятие делимости следующим образом: будем говорить, что и + «\/2 делит а(и + v\/2) тогда и только тогда, когда а имеет вид и + v\/2, где и и v-целые числа. В этом случае существует способ обобщить алгорнт.м Е таким образом, чтобы он всегда был конечным. Действительно, если на шаге Е2 мы имеем с = u + vV2