Книги по разным темам Pages:     | 1 |   ...   | 49 | 50 | 51 | 52 | 53 |   ...   | 65 |

n-32.44. Пусть bm = cm-dm. Требуется доказать, что если bmm = 0, m=где b0,..., bn-1 числа из поля k, то b0 = b1 =... = bn-1 = 0. Многочлен g(x) = bn-1xn-1+...+b0 имеет общий корень с неприводимым многочленом f(x), поэтому g(x) делится на f(x). Но степень g(x) меньше степени f(x), поэтому g(x) = 0, т.е. b0 = b1 =... = bn-1 = 0.

Глава 33.

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

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

33.1. Вычисления некоторых чисел 33.1. Докажите, что дробь 0, 1234567891011... 0, 51504948... начинается с цифр 0, 239.

33.2. Докажите, что если квадрат числа начинается с 0, 999... 9 (девяток), то и само число начинается с 0, 999... 9 (100 девяток).

33.3. Вычислите с точностью до 0, 00001 произведение 1 1 1 1 - 1 - 1 -... 1 -.

10 102 103 33.4. Докажите, что 3, 14 < 3, 142 и 9, 86 < 2 < 9, 87.

Глава 33. Алгоритмы и вычисления 33.2. Арифметические операции. Многочлены 33.5. Дано число a. Докажите, что можно вычислить an, сделав не более 2 log2 n умножений.

33.6. Чтобы вычислить значение многочлена P (x) = anxn + + an-1xn-1 +... + a0 при x = x0, можно вычислить anxn, an-1xn-1, 0..., a1x0, а затем сложить все полученные числа и a0. Для этого потребуется 2n - 1 умножений (вычисление xk для k = 2, 3,..., n требует n - 1 умножений). Придумайте способ вычисления P (x0), требующий лишь n умножений и n сложений. (Схема Горнера) 33.7. Укажите алгоритм, позволяющий разложить данный многочлен с целыми коэффициентами на неприводимые множители (в частности, выяснить, является ли данный многочлен неприводимым).

33.3. Сортировка Задача сортировки заключается в следующем. Дана последовательность чисел a1, a2,..., an. Требуется их переставить так, чтобы они были упорядочены по возрастанию: a(1) a(2)... a(n); здесь (1),..., (n) перестановка чисел 1,..., n.

У этой задачи есть разные варианты: найти наибольшее (или наименьшее) из данных чисел; найти два наибольших числа; выяснить, есть ли среди данных чисел равные, и т.п.

33.8. Дано n попарно различных чисел. Требуется найти наибольшее из них, сравнивая за один шаг пару чисел.

а) Докажите, что это можно сделать за n - 1 шаг.

б) Докажите, что этого нельзя сделать меньше, чем за n - 1 шаг.

Известно много разных алгоритмов сортировки. Здесь мы разберём некоторые из них.

Сортировка вставками заключается в следующем. Сначала сравниваем a1 и a2 и, если надо, меняем их местами. Затем в новой последовательности сравниваем a3 и a2 (здесь a2 элемент, который стоит на 2-м месте в новой последовательности) и, если нужно, меняем их местами. Если элементы a3 и a2 пришлось поменять местами, то сравниваем a3 и a1 и т.д.

33.9. Докажите, что для сортировки вставками количество сравнеn(n - 1) ний чисел заключено между n - 1 и.

418 Глава 33. Алгоритмы и вычисления Для оценки числа сравнений, достаточных для решения различных задач сортировки часто используется результат следующей задачи.

33.10. Есть куча из n 2 камней. На первом шаге она делится примерно пополам, т.е. если n чётно, то она делится на две кучи из n - 1 n + n/2 камней, а если n нечётно, то на две кучи из и камней.

2 На втором шаге с каждой кучей, в которой есть по крайней мере два камня, повторяется то же самое и т.д. Процесс останавливается после m-го шага, когда в каждой куче остался ровно один камень. Докажите, что число m определяется неравенствами m - 1 < log2 n m.

Сортировка слияниями заключается в следующем. Предположим, что у нас уже есть две отсортированные последовательности x1 x2... xp и y1 y2... yq. Тогда по ним можно построить отсортированную последовательность всех этих чисел следующим образом. Сравним числа x1 и y1 и заберём меньшее из них (если x1 = y1, то забираем любое из этих чисел). Это будет первое число новой последовательности. Для оставшихся последовательностей (теперь в одной из них на одно число меньше) повторяем то же самое. Так находим второе число новой последовательности и т.д. Для сортировки произвольной последовательности чисел этот алгоритм слияния двух последовательностей используется следующим образом. Разобьём исходную последовательность n чисел примерно пополам, как это делается в задаче 33.10.

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

33.11. Дана последовательность из n чисел. Докажите, что для её сортировки слияниями требуется не более mn - 2m + 1 сравнений пар чисел, где число m определяется неравенствами m - 1 < log2 n m.

33.12. В последовательности из 2n чисел требуется одновременно найти наибольшее число и наименьшее.

а) Докажите, что это можно сделать, сравнив 3n - 2 пары чисел.

б) Докажите, что сравнением менее 3n - 2 пар чисел в общем случае нельзя обойтись.

33.13. В последовательности из n различных чисел требуется одновременно найти самое большое и следующее за ним по величине.

а) Докажите, что это можно сделать, сравнив n + m - 2 пары чисел, Глава 33. Алгоритмы и вычисления где целое число m определяется неравенствами m - 1 < log2 n m.

б) Докажите, что сравнением менее n + m - 2 пар чисел в общем случае нельзя обойтись.

33.4. Криптография с открытым ключом Пусть m произведение двух различных простых чисел p и q. Выберем число e так, чтобы оно было взаимно просто с p-1 и q -1. Числа m и e доступны всем желающим, а числа p и q известны только владельцу шифра. Здесь нужно сказать, что если числа p и q достаточно большие, то с практической точки зрения восстановить их по известному числу m (т.е. разложить m на простые множители) невозможно.

Теперь любой желающий может зашифровать сообщение, которое представлено натуральным числом1 x < m, следующим образом: числу x сопоставляется остаток от деления числа xe на m.

Покажем, как владелец ключа может расшифровать это сообщение.

Для расшифровки важны не исходные простые числа p и q, а натуральное число d, которое определяется следующим образом:

de 1 (mod (m)), 1 d < (m).

Здесь (m) = (p - 1)(q - 1) функция Эйлера. Существование и единственность числа d следуют из того, что e взаимно просто с (m).

Чтобы расшифровать сообщение, нужно научиться решать сравнение xe a (mod m). Если x взаимно просто с m, то согласно малой теореме Ферма x(m) 1 (mod m), поэтому ad xed x (mod m). Поэтому расшифровка сообщения состоит просто в возведении полученного сообщения в степень d (и приведении по модулю m). Легко проверить, что это остаётся верным и в том случае, когда x не взаимно просто с m, т.е. a не взаимно просто с m. Действительно, пусть НОД(a, m) = r и s = = m/r. Число m является произведением двух взаимно простых чисел, поэтому s и r это простые числа p и q. В частности, (m) делится на (s). Следовательно, de 1 (mod (s)) и ad xed x (mod s). Числа a и x делятся на простое число r, поэтому ad 0 x (mod r). Но числа r и s взаимно простые, поэтому ad x (mod m).

Для шифровки текстового сообщения нужно преобразовать его в число по стандартному правилу: пробел = 00, а = 01, б = 02,...

420 Глава 33. Алгоритмы и вычисления Решения 33.1. Пусть a = 0, 1234... 5051 и b = 0, 5150... 321. Требуется доказать, что 0, 239b a < 0, 24b. Но 0, 515 < b < 0, 516, поэтому 0, 239b < 0, 2390, 516 = = 0, 123324 < a и 0, 24b > 0, 24 0, 515 = 0, 1236 > a.

33.2. Если 0 < a < 1, то 0 < a2 < a < 1. По условию 1 > a2 0, 9.. 9.

.

Поэтому 1 > a > 0, 9.. 9 (предполагается, что число a положительно).

.

33.3. О т в е т: 0, 89001.

1 1 1 1 Пусть a = 1 - 1 -... 1 - и b = 1 -... 1 -.

10 102 105 106 Непосредственные вычисления показывают, что 1 0, 89001 + < a < 0, 89001 +.

106 Ясно, что b < 1 -. Кроме того, если 0 < x, y < 1, то 1 1 1 (1 - x)(1 - y) > 1 - x - y. Поэтому b > 1 - - -... - > 1 -.

106 107 1099 Следовательно, ab < 0, 890012 0, 999999 < 0, 890012, ab > 0, 890011 0, 999998 > 0, 890009.

33.4. Мы воспользуемся тождеством 1 4 arctg - arctg =.

5 239 (задача 11.11) и неравенствами для арктангенса, доказанными в задаче 29.46.

Из этих неравенств следует, что 1 1 > 4 - - > 0, 78514923, 4 5 3 53 1 1 1 1 < 4 - + - + < 0, 78540526.

4 5 3 53 5 55 239 3 Поэтому 3, 1405 < 3, 1416 и 9, 862 < 2 < 9, 8698.

33.5. Пусть двоичная запись числа n имеет вид a0 + a1 2 +... + am 2m, где am = 0. Тогда m log2 n < m + 1, поскольку 2m n < 2m+1. Числа m a, a2, a4,..., a2 можно вычислить, сделав m умножений. Чтобы вычислить an, нужно перемножить какой-то набор из этих чисел. Он не может включать более m+1 чисел, поэтому достаточно m умножений. Всего получаем не более 2m 2 log2 n умножений.

33.6. Пусть b1 = anx0 + an-1, b2 = b1x0 + an-2,..., bn = bn-1x0 + a0. Тогда bn = P (x0), поскольку P (x) =... (anx0 + an-1)x0 + an-2... x0 + a0.

Глава 33. Алгоритмы и вычисления 33.7. Для вычисления разложения многочлена f с целыми коэффициентами на неприводимые множители Кронекер предложил следующий алгоритм (алгоритм Кронекера). Пусть deg f = n и r = [n/2]. Если многочлен f(x) приводим, то у него есть делитель g(x) степени не выше r. Чтобы найти этот делитель g(x), рассмотрим числа cj = f(j), j = 0, 1,..., r. Если cj = 0, то x - j делитель многочлена f(x). Если же cj = 0, то g(j) делитель числа cj. Каждому набору d0,..., dr делителей чисел c0,..., cr соответствует ровно один многочлен g(x) степени не выше r, для которого g(j) = dj, j = 0, 1,..., r. А именно, r x - k g(x) = djgj(x), gj(x) =.

j - k j=0 0 k r, k =j Для каждого такого многочлена g(x) нужно проверить, будут ли его коэффициенты целыми числами и будет ли он делителем многочлена f(x).

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

33.8. а) Будем при сравнении двух чисел выбирать наибольшее. Меньшее число будем вычёркивать из списка; в дальнейших сравнениях оно участвовать не будет. Ясно, что после n - 1 сравнений в списке останется лишь одно число наибольшее.

б) Каждое сравнение отсеивает только одного претендента на звание наибольшего числа. Если сделано k сравнений, то остаются n - k претендентов на звание наибольшего числа. Поэтому если остался только один претендент, то k n - 1.

33.9. Наименьшее число сравнений будет в случае, когда числа a1, a2,..., an уже упорядочены по возрастанию. В этом случае перестановок чисел не будет вообще. Сравниваться будут числа a1 и a2, a2 и a3,..., an-и an. Наибольшее число сравнений будет в случае, когда числа a1, a2,..., an упорядочены по убыванию. В этом случае количество перестановок будет наибольшим. Количество сравнений чисел в этом случае равно 1 + 2 +... + n(n - 1) + (n - 1) =.

33.10. Индукцией по m легко доказать, что для кучи из 2m-1 + 1 камней процесс останавливается после m шагов, поскольку после первого шага б из куч содержит 2m-2 + 1 камней. Ясно также, что для кучи из 2m ольшая камней процесс тоже останавливается после m шагов.

Таким образом, для кучи из n камней процесс останавливается после m шагов тогда и только тогда, когда 2m-1 + 1 n 2m, т.е. 2m-1 < n 2m.

огарифмируя эти неравенства, получаем требуемое.

33.11. Согласно задаче 33.10 число m, которое определяется указанными неравенствами, это количество шагов, которые нужно сделать, чтобы завершилось деление последовательностей (имеются в виду шаги, при которых 422 Глава 33. Алгоритмы и вычисления делятся примерно пополам все последовательности, полученные на предыдущем шаге).

Для слияния двух отсортированных последовательностей, состоящих из p и q чисел, требуется не более p + q - 1 сравнений пар чисел. Действительно, при каждом сравнении мы забираем одно число. Кроме того, сортировка завершается после того, как из одной последовательности забраны все числа.

Но при этом в другой последовательности останется по крайней мере одно число.

После m делений примерно пополам мы имеем 2m-1 пар чисел (некоторые пары состоят из одного числа). Для слияния этих пар нужно не более n - 2m-1 сравнений (для слияния пары, состоящей из одного числа, никаких сравнений не нужно, поэтому из общего количества всех чисел вычитается количество всех пар ). Затем нужно слить 2m-2 последовательности;

для этого нужно не более n - 2m-2 сравнений и т.д. Всего получаем не более mn - 2m-1 - 2m-2 -... - 2 - 1 = mn - 2m + 1 сравнений.

33.12. а) Разобьём данные числа произвольным образом на n пар. Сравнивая числа в каждой паре, выберем n наибольших чисел и n наименьших чисел в парах. Ясно, что наибольшее число нужно искать среди выбранных n наибольших чисел. Его можно найти, сделав n - 1 сравнений (задача 33.8).

Аналогично можно найти наименьшее число (среди n выбранных наименьших чисел), сделав n - 1 сравнений.

б) Пусть после k сравнений у нас есть ak чисел, которые оказались меньше каких-то чисел и больше каких-то чисел, bk чисел, которые оказались меньше каких-то чисел, но пока не оказались больше каких-то чисел, ck чисел, которые оказались больше каких-то чисел, но пока не оказались меньше каких-то чисел, и dk чисел, которые пока не сравнивались ни с какими числами. Первоначально a0 = b0 = c0 = 0 и d0 = 2n. А когда после m сравнений найдены наибольшее число и наименьшее, bm = cm = 1, am = 2n - 2 и dm = 0.

Рассмотрим величину fk = bk + ck + dk. Ясно, что f0 = 3n и fm = 2.

Будем предполагать, что если мы прямо или косвенно знаем, что x > y, то числа x и y мы больше никогда друг с другом не сравниваем, потому что такое сравнение можно было бы просто пропустить. Достаточно доказать, что при сравнении любой пары чисел может случиться, что fk - fk+1 1. Действительно, складывая неравенства f0 -f1 1, f1 -f2 1,..., fm -fm-1 1, получаем f0 - fm m, т.е. 3n - 2 m. Требуемое утверждение доказывается прямым перебором.

1) Если сравниваются два числа из группы ak, то ничего не меняется:

fk+1 = fk.

2) Пусть сравниваются число a из группы ak и число b из группы bk.

Может случиться, что a < b. Тогда ak+1 = ak + 1 и bk+1 = bk - 1, поэтому fk - fk+1 = 1.

Pages:     | 1 |   ...   | 49 | 50 | 51 | 52 | 53 |   ...   | 65 |    Книги по разным темам