LINEBURG


<< Пред. стр.

страница 2
(всего 7)

ОГЛАВЛЕНИЕ

След. стр. >>

?(1)=0, ?(2n)=?(2n+1)=?(n)+1.
Однако для доказательства справедливости этих правил полезно,
конечно, воспользоваться двоичной системой, после чего они ста-
новятся почти очевидными.
Докажем полезное и простое неравенство ?(n+1)??(n)+1. Оно
очевидно превращается в равенство, если n чётно, так как тогда
его двоичная запись заканчивается нулём. Если же эта двоичная
запись заканчивается k единицами, перед которыми стоит нуль,
то двоичная запись числа n+1 заканчивается k нулями, перед ко-
торыми стоит единица (а старшие биты остаются без изменения,
если они есть). Для того, чтобы в этом убедиться, достаточно вы-
полнить прибавление 1 к n в двоичной системе. В обоих рассмо-
тренных случаях ?(n+1)??(n)+1.
Из доказанного неравенства следует, что
?(n+1)+?(n+1)??(n)+?(n)+1.
Действительно, если 2k?1 <n+1<2k, то ?(n+1)=k?1=?(n),
и из неравенства ?(n+1)??(n)+1 следует нужная нам оценка.
Если же n+1=2k , то ?(n+1)=k=?(n)+1, ?(n+1)=1, ?(n)=k,
откуда следует, что ?(n+1)+?(n+1)=k+1?2k=?(n)+?(n)+1.
Справедливо также равенство
?(2n)+?(2n)=?(n)+?(n)+1,
которое сразу следует из равенств ?(2n)=?(n), ?(2n)=?(n)+1.
Выше было показано, что число операций умножения, исполь-
зованных для возведения в степень n на калькуляторе с одной
ячейкой памяти, не больше чем ?(n)+?(n)?1. При n=1, 2 оче-
видно, что меньшим числом операций обойтись нельзя. Покажем,
что и в общем случае это так, если только не обновлять содержи-
мое ячейки памяти, т. е. кроме возведения в квадрат всегда ис-
пользовать только умножение на основание степени.
Допустим противное, а именно, что для вычисления указан-
ным образом xn при некотором n оказалось достаточно l<?(n)+
+?(n)?1 операций. Выберем среди таких чисел n наименьшее чи-
сло и обозначим его также n. Если последняя операция в рас-
сматриваемом вычислении была возведение в квадрат, то n чётно,
и для вычисления xn/2 достаточно l?1<?(n)+?(n)?2=?(n/2)+
+?(n/2)?1 операций, поэтому минимальным числом с рассматри-
ваемым свойством не может быть n, что ведёт к противоречию.
Аналогично получается противоречие и в случае, когда последней
операцией было умножение на x. Действительно, тогда согласно
доказанному выше неравенству для вычисления xn?1 достаточно
l?1<?(n)+?(n)?2??(n?1)+?(n?1)?1 операций.
10
Но если обновлять содержимое ячейки памяти, то указанный
выше метод вычисления x1000 можно улучшить. Для этого можно
применить так называемый метод множителей. Идея этого метода
заключается в следующем. Заметим, что если мы умеем возводить
в степень n за l(n) операций и возводить в степень m за l(m)
операций, то можно после того, как закончено вычисление xn ,
занести его в ячейку памяти и далее вычислить xnm =(xn )m за l(m)
операций, используя тот же метод, что и для вычисления xm .
Тогда общее число операций будет равно l(nm)=l(n)+l(m).
Вычисляя x5 старым методом за ?(5)+?(5)?1=3 операции
(с помощью последовательности x, x2 , x4 =(x2 )2 , x5 =(x4 )x) и при-
меняя два раза метод множителей, получаем, что l(125)=3l(5)=
=9. Выполняя ещё три возведения в квадрат, получаем l(1000)=
=l(125)+3=12. Старый же метод требовал ?(1000)+?(1000)?1=
=9+6?1=14 операций.
Читателю может показаться, что мы слишком много внима-
ния уделили такому специальному и не слишком важному вопро-
су, как быстрое выполнение возведения в степень. Лет тридцать
назад это замечание было бы справедливым. Но в середине 1970-x
годов почти одновременно и независимо группой американских ма-
тематиков (У. Диффи, М. Хеллман, Р. Ривест, А. Шамир, П. Ад-
леман) и группой английских криптографов (К. Кокс, М. Вильям-
сон, Д. Эллис) были открыты первые алгоритмы криптографии
с открытым ключом*). Благодаря этим алгоритмам теперь частные
лица могут обмениваться секретной информацией по общедоступ-
ным каналам связи (например, по Интернету) без боязни, что их
сообщения прочтут не только конкуренты, но и спецслужбы. Воз-
никшее направление в криптографии быстро превратилось в по-
пулярную область математических исследований, которой уже по-
священы многочисленные журналы и книги. И во многих самых
распространённых алгоритмах важную роль играет операция воз-
ведения в степень.
§ 3. АДДИТИВНЫЕ ЦЕПОЧКИ И ФЛЯГИ С МОЛОКОМ
Назовём аддитивной цепочкой любую начинающуюся с 1 по-
следовательность натуральных чисел a0 =1, a1 , ..., am , в которой
каждое число является суммой каких-то двух предыдущих чисел
(или удвоением какого-то предыдущего числа). Обозначим l(n) наи-
меньшую длину аддитивной цепочки, заканчивающейся числом n
(длиной цепочки a0 =1, a1 , ..., am называем число m).
Например, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 — адди-
тивная цепочка, 1, 2, 3, 5, 7, 14 — минимальная цепочка для 14,
*) Англичане сделали это раньше, но им, как сотрудникам секретной крипто-
графической службы, было запрещено опубликовать свои результаты в открытой
печати.
11
т. е. l(14)=5. Аддитивные цепоч-
ки можно изображать в виде ори-
ентированного графа, в котором
1 2 3 5 7 14 в вершину a идут рёбра от вершин
i
aj , ak , если ai =aj +ak (в случае,
Рис. 1
если такое представление неод-
нозначно, выбираем любое из них и рисуем только два ребра).
Если из какой-то вершины выходит только одно ребро, то для крат-
кости можно <склеить> эту вершину с той вершиной, в которую
ведёт это ребро. Граф для предыдущего примера показан на рис. 1.
Можно считать, что все числа в цепочке разные, так как этого
легко достичь просто удаляя из неё повторяющиеся числа, и что
эти числа расположены в цепочке в порядке возрастания.
Очевидно, что наименьшее число умножений, необходимое для
возведения в n-ю степень, равно l(n).
Приведённый выше метод построения аддитивных цепочек на-
зывается двоичным (или бинарным). Фактически этим методом бы-
ло доказано, что справедливо неравенство l(n)??(n)+?(n)?1. Ме-
тодом множителей легко доказать неравенство l(nm)?l(n)+l(m).
7. Докажите нижнюю оценку: l(n)??(n).
Из этой оценки следует, что l(2n )=n.
Интересно, что бинарный метод был по существу известен
древним индусам, потом был переоткрыт арабскими математиками,
задача о точном вычислении функции l(n) появилась в одном
французском журнале в 1894 году, потом заново была переоткрыта
в 1930-е годы и неоднократно переоткрывалась в дальнейшем,
но до сих пор в общем случае не решена.
По существу, наилучшая из известных общих верхних оценок
была доказана в 1930-е годы А. Брауэром и имеет вид
# A
C ?(?(?(n))) !
!,
1 !
l(n)??(n) 1+
(?(?(n)))2 
+
?(?(n))
где C>0 — некоторая константа.
Не каждую аддитивную цепочку можно вычислить на кальку-
ляторе с одной ячейкой памяти, не используя для запоминания
промежуточных результатов собственную голову (фактически, такие
калькуляторы имеют две ячейки памяти, так одна из них содер-
жит число, изображаемое в данный момент на дисплее). Укажем,
как можно определить необходимое число ячеек памяти для вы-
числения данной аддитивной цепочки. Для этого введём понятия
ширины (а заодно и глубины) аддитивной цепочки.
Пусть дана произвольная цепочка a0 =1, a1 , ..., aL =n. Сопо-
ставим каждому её элементу два числа. Первое из них назовём
глубиной элемента, а второе — номером ячейки, хранящей это чи-
сло. Для элемента a0 первое число положим равным нулю, а вто-
12
рое — единице. Будем далее последовательно вычислять эти числа
для элементов цепочки. Пусть они уже вычислены для всех эле-
ментов от a0 до ak . Составим список номеров ячеек, содержащих
те элементы цепочки, которые ещё могут быть использованы для
вычисления последующих элементов. Найдём наименьшее число,
не входящее в этот список, и присвоим его элементу ak+1 в каче-
стве номера ячейки (возможно, она использовалась ранее, но те-
перь уже свободна). Пусть ak+1 =ai +aj , i, j?k. Если D(ai ), D(aj ) —
значения глубины элементов ai , aj , то положим D(ak+1 ) на едини-
цу большим максимального из чисел D(ai ), D(aj ). Шириной S це-
почки назовём число использованных ячеек (равное наибольшему
из использованных номеров ячеек). Глубиной D цепочки назовём
глубину её последнего элемента.
8. Докажите, что ak ?2D(ak ) и D??(n). Докажите, что бинар-
ный метод можно модифицировать так, чтобы длина цепочки
не изменилась, а глубина стала бы равна ?(n).
Если цепочка имеет ширину S, то её можно представить в виде
вычисления на калькуляторе с S?1 ячейками памяти (кроме основ-
ной, содержащей число, изображаемое в данный момент на дисплее)
или в виде компьютерной программы, использующей S ячеек памяти.
Можно ещё представить эту цепочку в виде способа, как налить
в данную флягу n литров молока из цистерны, если первоначально
в ней был один литр и кроме неё имеется S таких же пустых фляг
и весы, способные только сравнивать веса двух фляг между собой.
Для этого сопоставим S фляг ячейкам памяти рассматриваемой
цепочки, а одну флягу оставим запасной. Тогда любую операцию
с ячейками памяти вида xk =xi +xj можно выполнить, выливая
в случае необходимости k-ю флягу в цистерну, потом наливая
запасную флягу до уровня i-й фляги и сливая её содержимое в k-ю
флягу, если k=i, и делая аналогичную процедуру для индекса j.
Естественно, что аналогичным образом на языке <переливаний>
можно представить и программу с командами, использующими не толь-
ко сложение, но и вычитание xk =xi ?xj . Поэтому понятие аддитив-
ной цепочки можно обобщить, разрешив использовать вычитание.
Для вычисления степеней такие цепочки также можно выпол-
нять на калькуляторе, если кроме умножения использовать и де-
ление. Известно, что в среднем это не даёт существенной выгоды,
но в некоторых случаях число используемых операций уменьшается.
Например, вычислить x1000 можно с помощью следующей
цепочки: 1, 2, 4, 8, 16, 32, 31, 62, 124, 125, 250, 500, 1000.

§ 4. КРАТКАЯ ИСТОРИЯ ДВОИЧНОЙ СИСТЕМЫ
Некоторые идеи, лежащие в основе двоичной системы, по су-
ществу были известны в Древнем Китае. Об этом свидетельствует
13
классическая книга <И-цзин> (<Книга Перемен>), о которой речь
пойдёт позже.
Идея двоичной системы была известна и древним индусам.
В Европе двоичная система, видимо, появилась уже в новое время.
Об этом свидетельствует система объёмных мер, применяемая англий-
скими виноторговцами: два джилла = полуштоф, два полуштофа =
пинта, две пинты = кварта, две кварты = потл, два потла = галлон,
два галлона = пек, два пека = полубушель, два полубушеля =
= бушель, два бушеля = килдеркин, два килдеркина = баррель,
два барреля = хогзхед, два хогзхеда = пайп, два пайпа = тан.
Читатели исторических романов, видимо, знакомы с пинтами
и квартами. Частично эта система дожила и до нашего времени
(нефть и бензин до сих пор меряют галлонами и баррелями).
И в английских мерах веса можно увидеть двоичный принцип.
Так, фунт (обычный, не тройский) содержит 16 унций, а унция —
16 дрэмов. Тройский фунт содержит 12 тройских унций. В английских
аптекарских мерах веса, однако, унция содержит восемь дрэмов.
Пропагандистом двоичной системы был знаменитый Г. В. Лейб-
ниц (получивший, кстати, от Петра I звание тайного советника).
Он отмечал особую простоту алгоритмов арифметических действий
в двоичной арифметике в сравнении с другими системами и при-
давал ей определённый философский смысл. Говорят, что по его
предложению была выбита медаль с надписью <Для того, чтобы
вывести из ничтожества всё, достаточно единицы>. Известный со-
временный математик Т. Данциг о нынешнем положении дел ска-
зал: <Увы! То, что некогда возвышалось как монумент монотеиз-
му, очутилось в чреве компьютера>. Причина такой метаморфозы
не только уникальная простота таблицы умножения в двоичной
системе, но и особенности физических принципов, на основе кото-
рых работает элементная база современных ЭВМ (впрочем, за по-
следние 40 лет она неоднократно менялась, но двоичная система
и булева алгебра по-прежнему вне конкуренции).

§ 5. ПОЧЕМУ ДВОИЧНАЯ СИСТЕМА УДОБНА?
Главное достоинство двоичной системы — простота алгорит-
мов сложения, вычитания умножения и деления. Таблица умноже-
ния в ней совсем не требует ничего запоминать: ведь любое число,
умноженное на нуль равно нулю, а умноженное на единицу рав-
но самому себе. И при этом никаких переносов в следующие раз-
ряды, а они есть даже в троичной системе. Таблица деления сво-
дится к двум равенствам 0/1=0, 1/1=1, благодаря чему деление
столбиком многозначных двоичных чисел делается гораздо проще,
чем в десятичной системе, и по-существу сводится к многократно-
му вычитанию.
14
Таблица сложения как ни странно чуть сложнее, потому что
1+1=10 и возникает перенос в следующий разряд. В общем ви-
де операцию сложения однобитовых чисел можно записать в виде
x+y=2w+v, где w, v — биты результата. Внимательно посмотрев
на таблицу сложения, можно заметить, что бит переноса w — это
просто произведение xy, потому что он равен единице лишь когда
x и y равны единице. А вот бит v равен x+y, за исключением
случая x=y=1, когда он равен не 2, а 0. Операцию, с помощью
которой по битам x, y вычисляют бит v, называют по-разному.
Мы будем использовать для неё название <сложение по модулю 2>
и символ ?. Таким образом, сложение битов выполняется факти-
чески не одной, а двумя операциями.
Если отвлечься от технических деталей, то именно с помощью
этих операций и выполняются все операции в компьютере.
Для выполнения сложения однобитовых чисел делают обыч-
но даже специальный логический элемент с двумя входами x, y
и двумя выходами w, v, как бы составленный из элемента умно-
жения (его часто называют конъюнкцией, чтобы не путать с умно-
жением многозначных чисел) и элемента сложения по модулю 2.
Этот элемент часто называют полусумматором.

§ 6. ХАНОЙСКАЯ БАШНЯ, КОД ГРЕЯ И ДВОИЧНЫЙ n-МЕРНЫЙ КУБ
Далее мы рассмотрим несколько интересных задач, в решении
которых помогает знание двоичной системы. Начнём мы с задач,
в которых используется только одна, самая простая, из лежащих
в её основе идей — идея чисто комбинаторная и почти не связанная
с арифметикой.
Первая из них — это <Ханойская башня>. Головоломку под
таким названием придумал французский математик Эдуард Люка
в XIX веке.
На столбик нанизаны в порядке убывания размеров n круглых
дисков с дырками в центре в виде детской игрушечной пирамидки.
Требуется перенести эту пирамидку на другой столбик, пользуясь
третьим вспомогательным столбиком (рис. 2). За один ход разре-
шается переносить со столбика на столбик один диск, но класть
больший диск на меньший
нельзя. Спрашивается,
за какое наименьшее ко-
личество ходов это можно
сделать. Ответом в этой за-
даче служит уже извест-
ное нам <индийское число>
2n ?1. Люка в своей книге
Рис. 2
приводит якобы известную
15
легенду о том, что монахи в одном из монастырей Ханоя зани-
маются перенесением на другой столбик пирамидки, состоящей
из 64 дисков. Когда они закончат работу, кончится жизнь Брах-
мы*). Видно, ждать придётся долго.
Решение этой головоломки сильно облегчается, если знать, что
такое код Грея. Кодом Грея порядка n называется любая цикличе-
ская последовательность всех наборов из нулей и единиц длины n,
в которой два соседних набора отличаются ровно в одной компо-
ненте. Примером кода Грея порядка 3 является последовательность
трёхразрядных наборов 000, 001, 011, 010, 110, 111, 101, 100.
9. Докажите, что длина кода Грея порядка n равна 2n .
Если занумеровать компоненты каждого набора справа налево
(при этом последняя, т. е. самая правая компонента получит но-
мер 1), и начинать код Грея с нулевого набора, то его можно за-
писать короче, если вместо очередного набора писать только номер
компоненты, в которой он отличается от предшествующего набо-
ра. Например, указанный выше код Грея можно коротко записать
в виде последовательности семи чисел 1, 2, 1, 3, 1, 2, 1. В общем
случае длина подобной последовательности равна 2n ?1. Указан-
ная краткая запись позволяет догадаться, как можно строить коды
Грея дальше. Например, Грея порядка 4 можно задать последова-
тельностью 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1. Она получается,
если мы повторим два раза последовательность, определяющую код
Грея порядка 3, разделив оба экземпляра этой последовательности
числом 4. Далее поступаем аналогично, т. е. последовательность
длины 2n ?1, определяющую код Грея порядка n, дублируем, раз-
делив оба дубля числом n+1. Полученная последовательность дли-
ны 2(2n ?1)+1=2n+1 ?1 будет определять код Грея порядка n+1.
Легко видеть, что эта последовательность, так же, как и пре-
дыдущая, не изменяется, если её выписать в обратном порядке.
Последовательности (или слова) с таким свойством называются
палиндромами. Например, одним из самых известных русских па-
линдромов является предложение (символы пробела, естественно,
игнорируются)
А РОЗА УПАЛА НА ЛАПУ АЗОРА.
Нам понадобится это свойство кода Грея порядка n+1, а также
то обстоятельство, что все числа этой последовательности, кроме
среднего, не больше n. Это означает, что если с её помощью мы
начнём выписывать последовательность наборов длины n+1, на-
чиная с нулевого, то первые 2n ?1 наборов будут начинаться с нуля,
так как (n+1)-я компонента никогда в них не будет меняться.
*) Приблизительный западный аналог — это конец света, но на Востоке считают,
что после этого рождается новый Брахма, и всё циклически повторяется сначала,
от золотого века до нашей Кали-Юги, которой и заканчивается цикл.
16
Остальные же компоненты будут образовывать наборы длины n,
и они будут чередоваться в том же порядке, что и в коде Грея
порядка n, поэтому получится некоторая перестановка всех 2n на-
боров длины n+1, начинающихся с нуля. Потом в её последнем
наборе этот нуль будет заменён на единицу (это определяется тем,
что в середине последовательности стоит число n+1), далее эта
единица меняться не будет, а будет меняться в каждом очередном
наборе длины n+1 только одна из последних n компонент, и эти
компоненты образуют код Грея порядка n, выписанный в обратном
порядке, и закончится он нулевым набором. Сама же построенная при
этом последовательность наборов длины n+1 будет образовывать
перестановку всех наборов длины n+1, начинающихся с единицы, а её
последним набором будет набор 10...0. Таким образом, построенная
последовательность состоит из 2n различных наборов и может быть
превращена в циклическую, т. е. является кодом Грея порядка n+1.
Код Грея можно наглядно изобразить на n-мерном двоичном
кубе. Сам этот куб служит для наглядного представления множества
всех наборов длины n из нулей и единиц. Наборы изображаются
точками и называются вершинами куба. Два набора, отличающие-
ся только в одной компоненте, называются соседними и образуют
ребро куба. Номер этой компоненты называется направлением ре-
бра. Куб можно нарисовать на плоскости так, что все рёбра будут
изображены отрезками, соединяющими их вершины, причём рёбра
одного направления будут изображены равными и параллельны-
ми отрезками (поэтому такие рёбра называют тоже параллельны-
ми). Например, четырёхмерный куб можно изобразить на плоско-
сти так, как показано на рис. 3.
Код Грея на многомерном кубе можно изобразить в виде последова-
тельности вершин, в которой каждые две соседние вершины соединя-
ются рёбрами. Такие последовательности вершин принято называть
путями. Но код Грея изобра-
жается путём, у которого пер-
вая и последняя вершина тоже
соединяются ребром. Такие пу-
ти естественно называть цикла-
ми. Однако код Грея — не про-
сто цикл, а цикл проходящий
через все вершины куба. Такие
циклы (а их можно искать
не только на многомерном ку-
бе, но и на любом графе*))
называются гамильтоновыми
*) Граф — это произвольное множе-
ство вершин, некоторые из которых
Рис. 3
соединены рёбрами.
17
циклами*), а графы, у которых они есть — гамильтоновыми гра-
фами. Вопрос о том, какие графы гамильтоновы, а какие нет, ока-
зался чрезвычайно трудным и не решён удовлетворительно по сей
день. Ему можно посвятить отдельную книгу, и такие книги уже
написаны, поэтому мы прекращаем разговор на эту тему и возвра-
щаемся к многомерному кубу.
Для того, чтобы изобразить код Грея на приведённом на рис. 3
изображении n-мерного куба рядом с вершинами следует написать
их имена — соответствующие им наборы из нулей и единиц. Сделать
это можно, например, таким образом. Самой нижней вершине сопо-
ставим набор из одних нулей. Рёбрам сопоставим номера их направ-
лений, например, направлению самого правого ребра, выходящего
из <нулевой> вершины, сопоставим номер 1, и т. д., а направлению
самого левого такого ребра — номер n. Далее сопоставляем остав-
шимся вершинам куба имена с помощью следующего алгоритма.
Если какой-то вершине имя уже присвоено и, поднимаясь из неё
вверх по какому-нибудь ребру, скажем, направления k, попадаем
в новую, пока безымянную, вершину, то ей присваиваем имя, кото-
рое получается из имени прежней вершины заменой k-й компо-
ненты (которая была нулём) на противоположную (т. е. единицу).
Если же мы попали в вершину, имя которой уже было присвоено
ранее, то можно ничего не делать, так как если мы попробуем
всё же сопоставить ей имя согласно указанному правилу, то оно
совпадёт с уже присвоенным именем. Очевидно, самой верхней
вершине будет присвоен набор из одних единиц. Результат работы
описанного алгоритма для четырёхмерного куба показан на рис. 4.
Читателю предоставляется возможность самому решить голо-
воломку Люка и обнаружить её связь с кодом Грея, а мы займём-
ся другим вопросом.
Бросается в глаза на изображениях многомерного куба, что все
вершины, имена которых содержат заданное число единиц, ска-
жем k, лежат на одной прямой (рис. 5). Говорят, что эти вершины

<< Пред. стр.

страница 2
(всего 7)

ОГЛАВЛЕНИЕ

След. стр. >>

Copyright © Design by: Sunlight webdesign