LINEBURG


<< Пред. стр.

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

ОГЛАВЛЕНИЕ

След. стр. >>

лежат на k-м слое куба. Очевидно, нулевой слой состоит из одной
вершины — <нулевой>, а n-й слой состоит только из <единичной>
вершины.
10. Сколько различных <возрастающих> путей ведут из <ну-
левой> вершины в данную вершину k-го слоя?
О т в е т: k(k?1)(k?2)·...·2·1. Это число называют <k факто-
риал> и кратко обозначают k!.

*) В честь ирландского математика, механика, физика и астронома У. Р. Га-
мильтона, подсказавшего одному книготорговцу идею головоломки — как обойти
по рёбрам все вершины правильного многогранника (например, додекаэдра) и вер-
нуться в исходную вершину. Полученные от книготорговца десять фунтов были,
вероятно, единственным гонораром знаменитого учёного за многочисленные науч-
ные труды, если не считать оклада профессора Дублинского университета.
18
1)
(111

1) 0)
1) 1)
(011 (111
(101 (110

0)
1) 0) (110
(100 (101
)
1 0)
(010
11) (011
(00

0) 0)
1) (001 (010 0)
(000 (100

0)
(000
Рис. 4

Для того чтобы решить эту задачу, достаточно <закодировать>
любой такой путь последовательностью k различных чисел, нуме-
рующих направления составляющих этот путь рёбер.
В частности, число возрастающих путей от нулевой вершины
до единичной равно n!. На любом таком пути есть единственная
вершина, принадлежащая k-му слою, и она разбивает его на две
части. Нижняя часть соединяет её с нулевой вершиной, и этот
путь — один из множества возможных путей, соединяющих её
с нулевой вершиной, которых, как мы уже знаем, ровно k!. Верх-
няя часть соединяет её с единичной вершиной, и этот путь — один
из множества возможных, которых, как легко понять по анало-
гии, в точности (n?k)!.
Поэтому множество всех возрастающих путей от нулевой верши-
ны до единичной, проходящих при этом через заданную вершину
k-го слоя, равно k! (n?k)!. Но всего возрастающих путей от нулевой
1)) 4-й слой
1))
(1 111
1111
((111
(1 11

11) 0)
11)) 10))
1) 0)
1) 1)
1)) 1)) (111 0
(011 1 ) )
01 3-й слой
111
1011 1101
((01 1 ((11 1
(1 011 (1 101
(01 (1 1
((101 ((110
(101 (110

0)
00)))
1) 0) 1100
1)) 0)) (1 10 0
) ) 2-й слой
((11 0
(1 001 (1 010
100 101
1) ((100 1 ((101 0 (11
01)) (100 (101
0)
) 0))
0101
(0 10 1
) 0)
1) (0 11 0
((01 0 0 11
1)
) ((011
(01
0011
(0 011 ( 011
((00 1
(00 1

1-й слой
0) 0)
0)) 0))
1) ) )
01)) 0010 0100
(0 010 (0 100 0)
0))
) ((001 ((010
0001 (001 (010 0)
(000 1 (1 00 0
1 00
((00 0 ((100
( 100
(00

0-й слой
0)
0))
0)
(0 00 0
0 00
((000
(000

Рис. 5
19
вершины до единичной n!, поэтому число вершин в k-м слое рав-
n!
но . Это число называется k-м биномиальным коэффици-
k! (n?k)!
ентом и обозначается кратко Ck . Далее оно нам понадобится.
n
На этом мы заканчиваем рассказ о n-мерном кубе и возвраща-
емся в заключение опять к коду Грея. Очевидно, что в нём несо-
седние вершины могут быть соседними на кубе, т. е. соединяться
в нём ребром. В некоторых приложениях, как теоретических, так
и практических, представляет интерес построение цепи или цикла
в n-мерном кубе, в которой несоседние вершины никогда не явля-
ются соседними в этом кубе. Такая цепь максимальной возможной
длины называется <змеёй в ящике>. Какова её длина, до сих пор
неизвестно. Наилучшие известные её оценки принадлежат ново-
сибирским математикам А. А. Евдокимову и А. Д. Коршунову.
Другой задачей, связанной с кодом Грея, но более простой,
является его недвоичное обобщение. Например, как построить ци-
клическую последовательность всех трёхзначных десятичных чисел
от 000 до 999, в которой каждые два соседних числа были бы
соседними ещё и в том смысле, что отличались бы ровно в одном
разряде и ровно на единицу? Несколько проще построить такую
последовательность, если считать цифры 0 и 9 также соседними,
хотя разность между ними и не равна 1. Ещё проще построить
нециклическую последовательность с теми же свойствами.
Эта задача имеет приложение к алгоритму быстрейшего вскрытия
кодового замка на дипломате, поэтому мы не приводим её решения.
Заметим, что этим методом можно вскрыть, конечно, дипломат
не только с десятичным, но и с любым k-ичным кодовым замком.
Однако при нечётном k аналога циклического кода Грея не суще-
ствует, а существует только <цепной> код Грея. Читателю предо-
ставляется возможность самому это проверить.

§ 7. КНИГА ПЕРЕМЕН, АЗБУКА МОРЗЕ, ШРИФТ БРАЙЛЯ
И АЛФАВИТНЫЕ КОДЫ
Двоичная система, по крайней мере в своей комбинаторной
ипостаси, по существу была известна в Древнем Китае. В клас-
сической книге <И-цзин> (<Книга Перемен>) приведены так на-
зываемые гексаграммы Фу-си, первая из которых имеет вид ,
а последняя (64-я) — вид , причём они расположены по кругу
и занумерованы в точном соответствии с двоичной системой (ну-
лям и единицам соответствуют сплошные и прерывистые линии).
Китайцы не поленились придумать для этих диаграмм специаль-
ные иероглифы и названия (например, первая из них называлась
<кунь>, а последняя — <цянь>, сплошной линии сопоставляется
мужское начало янь, а прерывистой линии — женское начало инь).
20
Каждая гексаграмма состоит из двух триграмм (верхней и ниж-
ней), им тоже соответствуют определённые иероглифы и названия.
Например, триграмме из трёх сплошных линий сопоставлен образ-ат-
рибут <небо, творчество>, а триграмме из трёх прерывистых линий
сопоставлен образ-атрибут <земля, податливость, восприимчивость>.
Их также принято располагать циклически, но этот цикл не явля-
ется кодом Грея.
Книга Перемен очень древняя, возможно, одна из древнейших
в мире, и кто её написал — неизвестно. Она использовалась ранее,
и используется в настоящее время, в том числе и на Западе,
для гадания. В Европе с аналогичной целью используются карты
Таро. В чём-то обе эти системы схожи, но Таро никак не связаны
с двоичной системой, поэтому о них мы говорить не будем.
Способ гадания по Книге Перемен в кратком изложении таков.
Бросается шесть раз монета (или лучше пуговица, деньги в гадании
применять не рекомендуется) и по полученным результатам (орёл
или решка) разыскивается подходящая гексаграмма (для этого на-
до заранее сопоставить орлу и решке янь или инь). По гексаграм-
ме разыскиваете соответствующий раздел Книги Перемен (имеется
перевод выдающегося синолога Ю. К. Шуцкого, неоднократно пе-
реиздававшийся в последнее время) и читаете, что там написано.
Конечно, перевод текста книги в предсказание требует опыта
и мастерства. И заниматься этим надо после соответствующей под-
готовки, в подходящем настроении, в подходящее время и в подхо-
дящем месте. Говорят, тогда предсказания почти всегда сбываются.
А может быть, просто магическим образом из множества вариантов
будущего выбирается тот, который соответствует предсказанию?
Заинтересованного читателя отсылаем к книгам Дж. Х. Брен-
нана <Таинственный И-цзин>, М.: Гранд, 2001; В. Фирсова <Кни-
га Перемен. Мистика и магия древнего Китая>, М.: Центрполи-
граф, 2002, и переходим к другой теме — азбуке для слепых.
На этом примере, в частности, хорошо видно, что многие
на первый взгляд простые идеи рождались не сразу, и своим по-
явлением обязаны усилиям многих людей. Идею использовать ре-
льефные буквы для печатания книг для слепых первым предло-
жил француз Валентен Ойи. Но выпущенные им книги успехом
не пользовались, так как слепым трудно было на ощупь отличать
сложные начертания букв друг от друга.
Капитан французской армии Шарль Барбье в 1819 году пред-
ложил печатать выпуклыми не буквы, а точки и тире (или просто
продавливать их на бумаге) и ими уже записывать буквы. Эту
систему он назвал <ночное письмо> и предлагал вовсе не для сле-
пых, а для использования в военно-полевых условиях. С появлени-
ем электрических фонариков военное значение этого изобретения
упало до нуля.
21
Слепой мальчик Луи Брайль познакомился с этой системой
в 12 лет. Она ему понравилась тем, что позволяла не только читать,
но и писать. В течение трёх лет он её усовершенствовал и создал
так называемый шрифт Брайля. В нём символы языка (буквы,
знаки препинания и цифры) кодируются комбинациями от одной
до шести выпуклых точек, расположенных в виде таблицы стан-
дартного размера с тремя строчками и двумя столбцами. Элементы
(точки) таблицы нумеруются числами 1, 2, 3 в первом столбце
сверху вниз и 4, 5, 6 во втором столбце сверху вниз. Каждая точка
либо продавливается специальной машинкой (или даже шилом)
или остаётся целой. Всего различных способов продавить выпуклые
точки в этой таблице 64 (в том числе и тот, в котором ни одна
из точек не вдавлена). При желании теперь читатель может со-
поставить каждому символу алфавита Брайля одну из гексаграмм
Книги Перемен. Вряд ли, конечно, Брайль знал об этой книге.
Вероятно, не имеет смысла описывать все символы шрифта
Брайля, тем более что после его смерти в 1852 году шрифт допол-
нялся и совершенствовался. Но несколько слов сказать, видимо,
стоит. Буква <а>, например, изображается одной выпуклой точкой
в 1-м элементе таблицы, буква <б> изображается выпуклыми точ-
ками в 1-м и 2-м элементах таблицы и т. д. Для сокращения тек-
стов некоторые часто встречающиеся слова или комбинации букв
кодируются специальными таблицами. Для того чтобы отличать
заглавную букву от строчной, перед ней ставят специальную табли-
цу, изображающую то, что сейчас называют эскейп-символом. Мно-
гие таблицы имеют несколько значений (например, буква и какой-
нибудь специальный знак или знак препинания), выбор из которых
делается в соответствии с контекстом. Цифры кодируются так же,
как и первые буквы алфавита, и, чтобы их отличать, перед по-
следовательностью цифр ставится специальный символ — признак
числа, а заканчивается число символом отмены признака числа.
Азбука Брайля по известности уступает азбуке Морзе, хотя
и применяется до сих пор в отличие от последней. Сэмюэль Морзе
известен однако не только изобретением азбуки. Он был и худож-
ником-портретистом (его картина <Генерал Лафайет> до сих пор
висит в нью-йоркском Сити-Холле*)), и одним из первых фотогра-
фов в Америке (учился делать дагерротипные фотографии у са-
мого Луи Дагерра), и политиком (он баллотировался в 1836 го-
ду на пост мэра Нью-Йорка), но самое главное его достижение —
изобретение телеграфа (а азбука Морзе понадобилась ему для ис-
пользования телеграфа). Заодно он изобрёл устройство, которое на-
зывается реле. Именно из реле спустя сто лет после Морзе были
построены первые компьютеры.
*) Известна также его картина <Человек в предсмертной агонии>, после просмо-
тра которой его приятель, известный врач, сказал: <По-моему, малярия>.
22
Начал свои работы в этом направлении он в 1832 году, запа-
тентовал своё изобретение в 1836 году, но публичная демонстрация
телеграфа произошла только 24 мая 1844 года. По телеграфной
линии, соединяющей Вашингтон с Балтимором, была успешно
передана фраза из Библии.
Точки и тире оказались самыми элементарными символами,
которые мог передавать его телеграф. Они соответствовали корот-
ким и длинным импульсам электрического тока, передаваемым
по телеграфным проводам. Длина импульса определялась нажатием
руки телеграфиста на ключ телеграфа. Приём сигнала осуществля-
ло реле, которое после появления в нём импульса тока включало
электромагнит, который либо заставлял стучать молоточек, либо
прижимал колёсико с красящей лентой к бумажной ленте, на ко-
торой отпечатывалась либо точка, либо тире в зависимости от дли-
ны импульса.
Азбука Морзе сопоставляет каждой букве алфавита последо-
вательность из точек и тире. Естественней всего использовать такие
последовательности длины 6, их всего 64 и хватит даже на русский
алфавит. Но Морзе понимал, что длину сообщения желательно
уменьшить, насколько возможно, поэтому он решил использовать
последовательности длины не более 4, их всего 2+4+8+16=30.
В русском алфавите пришлось не использовать буквы <э> и <ё>
и отождествить мягкий и твёрдый знаки. Кроме того, наиболее
часто используемым буквам он предложил давать самые короткие
коды, чтобы уменьшить среднюю длину передаваемого сообщения.
Эту идею в наше время используют с той же целью в алфавитном
кодировании.
Здесь имеет смысл ввести терминологию теории кодирования.
Определение алфавитного кодирования очень просто. Пусть, на-
пример, кодирующим алфавитом является двухбуквенный алфа-
вит, например, состоящий из символов 0, 1. Схемой алфавитного
кодирования называется отображение каждой буквы кодируемого
алфавита в некоторое слово в кодирующем алфавите (называемое
элементарным кодом), в рассматриваемом случае — последователь-
ность нулей или единиц. Пользуясь этой схемой, можно закодиро-
вать любое слово в кодируемом алфавите, заменяя в нём каждую
букву на соответствующий ей элементарный код, и превратить
исходное слово в более длинное слово в кодирующем алфавите.
Таким образом, и код Брайля, и азбука Морзе являются алфавит-
ными кодами.
Удобнее всего задать код Морзе в виде четырёхярусного двоич-
ного дерева. Из корня дерева выходят два ребра, из которых пра-
вому соответствует тире, а левому — точка. Это — рёбра первого
яруса. Из их концов тоже аналогичным образом выходят по два
ребра. Это — рёбра второго яруса. Дерево рисуем до четвёртого
23
Ш Ч Щ З Ы Ц Ь Б Й П Я Л Ю Ф Ж Х


О Г К Д В Р У С


М Н А И

Т Е


Рис. 6


яруса. Вершинам дерева (за исключением корня) приписываем
буквы алфавита (рис. 6). Тогда каждой букве можно сопоставить
последовательность точек или тире, получающуюся, если выпи-
сать друг за другом последовательность символов, сопоставленных
рёбрам дерева, образующим путь, идущий из корня к вершине
дерева, соответствующей данной букве.
Очевидно, что алфавитный код должен обладать свойством од-
нозначной декодируемости, т. е. разные слова в исходном алфавите
не могут иметь одинаковые коды. А так как процедуру деко-
дирования можно представлять как поиск разбиения закодиро-
ванного слова на элементарные коды, то это разделение должно
быть однозначным. Поэтому однозначно декодируемые коды иногда
называют разделимыми кодами. Ясно, что если все элементарные
коды имеют одинаковую длину, то код разделим и алгоритм деко-
дирования очень прост. Но если это не так, то код может и не быть
разделимым. Например, таким является код Морзе. Но между
словами телеграфисты всегда делали промежутки, поэтому никаких
проблем не возникало. Однако если промежутки между словами
выделять невозможно, приходится использовать только раздели-
мые коды. А пустую букву, изображающую промежуток между
словами, часто включают в состав алфавита, что даёт возможность
всегда иметь дело не с предложениями, а только со словами.
Понять по достаточно сложному алфавитному коду, являет-
ся ли он разделимым, бывает не просто. Известны несколько разных
алгоритмов для проверки разделимости кода. Наиболее наглядный
из них принадлежит А. А. Маркову*).
Не вдаваясь в подробности, ограничимся замечанием, что код,
у которого ни один из элементарных кодов не является началом
другого (такие коды принято называть префиксными), несомненно
является разделимым. Предоставим доказательство этой теоремы
читателю. Очевидным примером префиксного кода является лю-

*) Заинтересовавшегося этими вопросами читателя мы отсылаем к книге
А. А. Маркова <Теория алгорифмов>, М.: Наука, 1984; М.: Фазис, 1996.
24
бой код с равными длинами кодовых слов. Код Морзе префиксным
не является, что также предоставляется проверить читателю. Лю-
бой двоичный префиксный код можно задать подобно коду Морзе
с помощью двоичного дерева, не обязательно такого равномерно-
го, как у него, но при этом буквы кодируемого алфавита должны
сопоставляться только <листьям> дерева, но никак не внутренним
вершинам.
Возвращаясь к истории алфавитного кодирования, заметим,
что его корни уходят в глубь веков. Фактически первый при-
мер применения алфавитного кодирования был описан древнегре-
ческим историком Полибием. Алфавит записывался в квадратную
таблицу 5?5 и каждая буква шифровалась парой своих коорди-
нат (i, j) (номерами строки и столбца), а передаваться сообщения
могли в то время с помощью факелов — i факелов в левой руке
и j факелов в правой означали пару (i, j).
Дальнейшее развитие идеи алфавитного кодирования принад-
лежит знаменитому английскому философу, эзотерику и писателю
сэру Френсису Бэкону, который первым начал использовать двоич-
ный алфавит в качестве шифроалфавита. В криптографии, правда,
это не нашло особого применения, главным образом из-за пяти-
кратного удлинения шифртекста в сравнении с открытым текстом.
Но сам Бэкон предложил использовать его как метод, сочетающий
криптографию со стеганографией (так называется скрытие самого
факта передачи секретного сообщения).
Вместо двоичных цифр он использовал обычный алфавит,
но со шрифтами двух типов. Таким методом можно было в любом
тексте спрятать шифровку, если, конечно, шрифты были достаточно
мало различимы. Желательно при этом использовать разделимый
код. Длина зашифрованного сообщения будет в несколько раз ко-
роче, чем длина содержащего его (и одновременно маскирующего
его) текста, но если для передачи шифровки использовать книгу,
то в ней можно таким образом незаметно разместить ещё целую
книгу. Но эта красивая идея из-за дороговизны её реализации так
и не нашла применения. В наше же время её нельзя рассматривать
как серьёзный метод.
Интересно, что в XIX веке, главным образом в кругах, инте-
ресующихся наследием возникшего в средневековье тайного ми-
стического ордена розенкрейцеров, появилась идея, что Френсис

<< Пред. стр.

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

ОГЛАВЛЕНИЕ

След. стр. >>

Copyright © Design by: Sunlight webdesign