LINEBURG


<< Пред. стр.

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

ОГЛАВЛЕНИЕ

След. стр. >>

Бэкон, которого считали розенкрейцером, является настоящим
автором пьес Шекспира. Начали искать подтверждение этого
в шифрах, которые мог оставить Бэкон в своих книгах, а также
в первом знаменитом издании пьес Шекспира. Было, естественно,
найдено много таких, якобы зашифрованных фрагментов. Серьёзные
исследователи, правда, замечали, что в любом длинном тексте можно
при желании и некоторых натяжках найти короткие фрагменты,
25
напоминающие шифры. Но у сторонников авторства Бэкона стрем-
ление доказать это криптографическим методом приняло форму мании.
Американский миллионер Фабиан даже создал в начале XX века
на свои деньги лабораторию криптоанализа, которая занималась
только подобными исследованиями.
Фабиан нанял на работу дипломированного генетика Уильяма
Фридмана, сына эмигрантов из России. Через некоторое время
Фридман уже возглавлял у Фабиана и лабораторию генетики,
и лабораторию криптоанализа. Доказать авторство Бэкона он не смог,
более того, он впоследствии опубликовал книгу, где опровергал
возможность такого криптографического доказательства. Но он
не на шутку увлёкся криптографией и своей подчинённой Элизабет
Смит, с которой обвенчался в 1917 году. Они стали самой знаменитой
супружеской парой в истории криптографии. После вступления
Америки в войну у него с супругой появилась серьёзная работа
по правительственным заказам. После войны он ушёл от Фабиана,
и стал главным криптографом войск связи.

§ 8. ФОТОПЛЁНКА И ШТРИХ-КОД
Рассмотрим теперь некоторые примеры реального применения
двоичного кодирования в современной технике.
Как автоматические фотоаппараты узнают светочувствительность
заправленной в них плёнки? Её измеряют в некоторых единицах, и вся
выпускаемая сейчас в мире плёнка имеет одно из 24 стандартных
значений светочувствительности. Эти значения кодируются некото-
рым стандартным образом наборами из нулей и единиц, естественно,
длины 5. На поверхности кассеты для плёнки нанесены 12 квадратиков
чёрного или серебристого цвета, образующих прямоугольник 2?6.
Квадратики его верхней части мысленно занумеруем от 1 до 6,
начиная слева. Квадратики нижней части аналогично занумеруем
от 7 до 12. Серебристые квадратики — это просто металлическая
поверхность кассеты, она проводит ток, который с контакта внутри
аппарата подаётся на первый квадрат (он всегда серебристый).
Чёрные квадраты покрыты краской, не проводящей ток.
Когда плёнка вставляется в аппарат, шесть его контактов со-
прикасаются с шестью первыми квадратиками, и с квадратиков
со 2-го по 6-й снимается информация — нуль, если квадратик
чёрный и ток по соответствующему контакту не идёт, и единица
в противном случае. Вся информация о светочувствительности
плёнки заключена в квадратиках со 2-го по 6-й. В остальных ква-
дратиках заключена информация о числе кадров в плёнке и т. п.
Ещё на поверхности кассеты можно увидеть штрих-код. Это так
называемый универсальный код продукта, он сейчас ставится на всех
продаваемых товарах. Для чего он нужен и как его прочитать?
26
Нужен он только для автоматического занесения информации
в кассовый аппарат. Сам штрих-код состоит из тридцати чёрных
полос переменной толщины, разделённой промежутками тоже
переменной толщины. Толщина полос может принимать четыре
значения от самой тонкой до самой толстой. Такую же толщину
могут иметь и промежутки. Когда по сканеру проводят штрих-кодом,
он воспринимает каждую чёрную полоску как последовательность
единиц длины от одной до четырёх, и также воспринимает проме-
жутки между полосами, но при этом вместо единиц сканер видит
нули. Полностью весь штрих-код сканер воспринимает как после-
довательность из 95 цифр 0 или 1 (их давно уже принято назы-
вать битами). Что же содержит этот код? Он кодирует 13-разряд-
ное десятичное число, совершенно открыто написанное под самим
штрих-кодом. Если сканер не смог распознать штрих-код, то это
число кассир вводит в аппарат вручную. Штрих-код нужен лишь
для облегчения распознавания сканером изображения. Распозна-
вать цифры, к тому же повёрнутые боком, может только сложная
программа распознавания на универсальном компьютере, да и то
не очень надёжно, а не кассовый аппарат.
Какую же информацию содержит это 13-значное число? Этот
вопрос к математике никакого отношения не имеет. Первая цифра
задаёт тип товара, например, у товаров переменного веса она равна 2.
Следующие пять цифр — это код производителя, а следующие
пять цифр — код самого продукта в принятой этим производителем
кодировке. Последняя цифра — это код проверки. Он однозначно
вычисляется по предыдущим 12 цифрам следующим образом. Нужно
сложить все цифры с нечётными номерами, утроить сумму, к ней
прибавить сумму оставшихся цифр, а полученный результат вычесть
из ближайшего (большего) кратного 10 числа.
А вот 95-битный код, соответствующий штрих-коду, более
интересен. Он содержит в себе только указанное 12-значное число
(контрольная цифра в самом штрих-коде не содержится), но с боль-
шой избыточностью. Первые три бита в нём, так же, как и по-
следние — это всегда 101. Они нужны только для того, чтобы ска-
нер смог определить ширину полосы, соответствующей одному би-
ту (ведь размеры штрих-кода на разных упаковках могут быть раз-
ными) и настроиться на распознавание. В центре кода всегда стоит
комбинация 01010, а левая и правая части кода состоят каждая
из шести блоков по семь битов и содержат информацию о левых
шести и правых шести из данных 12 десятичных цифр. Централь-
ная комбинация позволяет, в частности, отличать поддельные или
плохо напечатанные коды.
Цифры 13-значного кода кодируются в левой и правой частях
штрих-кода по-разному. В левой половине каждая цифра коди-
руется семёркой битов, начинающейся с 0 и заканчивающейся 1
27
согласно следующей таблице:
=0001101=0, =0111101=3, =0111011=7,
=0011001=1, =0100011=4, =0110111=8,
=0010011=2, =0110001=5, =0001011=9.
=0101111=6,
В правой половине каждая цифра кодируется семёркой битов, на-
чинающейся с 1 и заканчивающейся 0 согласно таблице, кото-
рая получается из вышеприведённой, если в ней нули заменить
на единицы и единицы на нули (это переход к дополнительному
коду). Можно заметить, что каждый из кодов в таблице содержит
нечётное число единиц и ровно две группы рядом стоящих единиц
и ровно две группы рядом стоящих нулей. Это означает, что каж-
дая цифра соответствует двум соседним полосам на штрих-коде.
Но более важно то обстоятельство, что все десять кодов таблицы,
будучи прочитанными не слева направо, а справа налево, будут от-
личаться от любого из кодов таблицы, прочитанного правильным
образом. Очевидно, таблица для правой половины кода обладает
теми же свойствами, только число единиц в каждом коде чётное.
Такая избыточная (не четырёхбитовая, а семибитовая) табли-
ца кодов нужна для того, чтобы сканер мог правильно прочитать
штрих-код и в случае, когда код направляют в него <вверх но-
гами>. Как сканер может отличать одно направление от другого?
По чётности или нечётности числа единиц в первом же прочитан-
ном семибитовом блоке, идущем после комбинации 101. При пра-
вильном направлении оно будет нечётным, а при обратном напра-
влении — чётным. Перепутать же коды, прочитанные слева, и ко-
ды, прочитанные справа, согласно свойству таблицы, невозможно.
Если же в каком-то из семибитовых блоков нарушено правиль-
ное чередование нулей и единиц в первом и последнем битах или
ему не соответствует чётность числа единиц, то штрих-код при-
знаётся поддельным или плохо пропечатанным.

§ 9. ЗАДАЧИ О ПЕРЕЛИВАНИЯХ
На одной из Всесоюзных математических олимпиад была пред-
ложена следующая задача. В три сосуда налито по целому числу
литров воды. В любой сосуд разрешается перелить столько воды,
сколько в нём уже содержится, из любого другого сосуда. Каждый
из сосудов может вместить всю имеющуюся в них воду. Докажите,
что можно несколькими переливаниями освободить один из сосудов.
В её решении неожиданно на первый взгляд применяется дво-
ичная система. Так как задача оказалась очень трудной (на олим-
пиаде её никто не решил), мы приведём здесь это решение. В нём
используются две идеи. Первая из них заключается в том, что если
будет найден алгоритм переливания, после применения которого ми-
28
нимальный объём воды, содержащейся в одном из сосудов, умень-
шается, то, повторяя многократно этот алгоритм, мы опорожним
один из сосудов. Эта идея не такая простая, как может показать-
ся. Ведь это не что иное, как метод бесконечного спуска П. Ферма.
Идея применения двоичной системы лежит в основе этого алго-
ритма уменьшения минимума. Пусть в сосудах A, B, C находится
a?b?c литров воды. Разделим b на a с остатком, b=aq+r,
0?r<a и предложим алгоритм, после применения которого в со-
суде B останется r литров. Для этого представим q в виде суммы
различных степеней двойки: q=2d1 +...+2dk . Выливая из сосуда C
воду d1 раз подряд в сосуд A, получим в нём 2d1 a литров, а вы-
ливая после этого в него 2d1 a литров из сосуда B, получаем в нём
b?2d1 a=a(q?2d1 )+r=a(2d2 +...+2dk )+r литров. Аналогично,
выливая из сосуда C воду d2 ?d1 ?1 раз подряд в сосуд A, а потом
выливая в него воду из сосуда B, получаем в нём a(2d2 +...+2dk )+
+r?2d2 a=a(2d3 +...+2dk )+r литров. Повторяя эту процедуру, по-
лучим, что в конце концов в сосуде B окажется r литров воды.
Нужно ещё заметить, что во время каждой процедуры из сосу-
да C выливалось меньше воды, чем из сосуда B, так как 2+22 +...
...+2l?1 <2l . Поэтому всего из сосуда C вылито воды меньше, чем
из B, значит оба они не опорожнятся раньше времени, и алгоритм
работает корректно.
Приведённую выше задачу можно обобщить и на большее
количество сосудов. Применив к любым трём из них указанный
алгоритм, один из сосудов опорожним. Повторяя эту процедуру
ещё раз, опорожним ещё один сосуд и т. д., пока не останутся
заполненными только два сосуда.
Предоставляем читателю самостоятельно выяснить, что будет
происходить, если продолжить переливания с двумя оставшимися
сосудами.
Выше указывалось, что при решении некоторых задач о пе-
реливаниях можно использовать аддитивные цепочки. Предлага-
ем читателю для самостоятельного решения одну из таких задач.
11. Как быстрее всего наполнить флягу 85 литрами моло-
ка, пользуясь однолитровым черпаком, если есть ещё одна та-
кая же фляга и весы, способные только сравнивать массы фляг?
Классические задачи о переливаниях выглядят несколько по-
другому, и метод их решения не связан с двоичной системой.
Примером такой задачи, решение которой по преданию послу-
жило знаменитому французскому математику Пуассону толчком
к выбору его профессии, является вопрос о том, как, имея полные
сосуды в 3 и 5 литров и пустой 8-литровый сосуд, отмерить ров-
но 4 литра. Читателю предоставляется возможность самостоятель-
но придумать метод решения подобных задач за наименьшее ко-
личество переливаний.
29
§ 10. ИГРА <НИМ>
Двоичная система находит неожиданное применение при ана-
лизе известной игры <Ним>. Происхождение её, так же, как и шах-
мат, покрыто туманом. Возможно, она была изобретена в Китае.
Состоит она в следующем: на столе лежит несколько кучек спи-
чек, и два игрока по очереди выбирают одну из кучек и забирают
из неё сколько угодно спичек (хоть все); выигрывает тот, кто заби-
рает последнюю (есть вариант игры, в котором забравший послед-
нюю проигрывает). Эпизод с этой игрой неоднократно повторяется
в известном французском фильме <Прошлым летом в Мариенбаде>.
Игра <Ним> являлась излюбленной темой математических
кружков в МГУ. Иногда она представлялась в виде гонки несколь-
ких пешек от одного края доски доски до другого. Читатель сам
сможет сформулировать правила игры в таком её представлении.
При игре с одной кучкой, очевидно, побеждает начинающий.
При игре с двумя кучками начинающий побеждает не всегда.
12. Докажите, что выигрывающей позицией является позиция
с двумя равными кучками. Игрок, сумевший после своего хода
попасть в такую позицию, всегда сможет выиграть.
В случае трёх и более кучек описание выигрышной позиции
не так просто. Алгоритм распознавания выигрышной позиции следу-
ющий. Нужно количество спичек в каждой кучке записать в двоичной
системе, и вычислить сумму по модулю 2 полученных двоичных
наборов (далее для краткости будем называть её ним-суммой).
Для этого вначале нужно вычислить покомпонентную сумму этих
наборов, т. е. найти сумму всех младших разрядов, потом сумму
следующих за ними разрядов (отсутствующие разряды заменяются
нулями) и т. д., и записать полученные суммы в виде (возможно,
недвоичного) набора, а потом каждую его компоненту заменить
на остаток от деления на 2. Если получится набор из одних нулей,
то позиция выигрышная.
Например, если в кучках было 3, 7, 12, 17 спичек, то поком-
понентно складывать придётся наборы
11 (=3)
+
111 (=7)
1100 (=12)
10001 (=17)
11223
Ним-сумма равна 11001, поэтому позиция является проигрыш-
ной для того, кто в неё попал после своего хода. Причина в том,
что противник может сделать ход, которым он попадёт в позицию
с нулевой ним-суммой. Для этого он может оставить в последней
кучке число спичек, равное в двоичной записи ним-суммы наборов
30
10001 и 11001, т. е. 01000. Тогда ним-сумма чисел, образующих новую
позицию, будет равна нулевому набору, так как эта сумма будет отли-
чаться от прежней суммы 11001 прибавлением к ней по модулю 2 набо-
ра 11001, что даёт в результате, очевидно, нулевой набор. Поскольку
01000=8, из последней кучки надо взять 17?8=9 спичек.
13. Докажите в общем случае, что из позиции с ненулевой
ним-суммой за один ход можно попасть в позицию с нулевой
ним-суммой, а из позиции с нулевой ним-суммой любой ход ведёт
к позиции с ненулевой ним-суммой.
Теперь ясно, что тот, кто первый попал в позицию с нулевой
ним-суммой, дальше при любой игре противника при своём ходе
опять сможет попасть в такую же позицию, и в конце концов он
возьмёт последнюю спичку.
Указанная выигрышная стратегия поддаётся для реализации даже
на специализированных машинах. Одна из таких машин была вы-
ставлена после войны в Берлине на английской выставке и с успехом
конкурировала с находящимся рядом бесплатным пивным залом.
Знаменитый английский математик Алан Тьюринг вспоминал о том,
как популярность этой машины повысилась ещё больше после
победы над тогдашним бундесминистром экономики Л. Эрхардом.
Читателю предоставляем возможность найти выигрышную
стратегию при игре ним в поддавки.
Более интересная модификация игры ним получается, если огра-
ничить число спичек, которые можно взять за один раз, например,
числом 10. Тогда интерес представляет даже игра с одной кучкой
спичек. Эту игру изобрёл в XVII веке французский математик
Баше де Мезириак, написавший кстати, одну из первых в Европе
книг по занимательной математике. Читатель может попробовать
сам придумать для неё выигрышную стратегию.

§ 11. Д. И. МЕНДЕЛЕЕВ И ТРОИЧНАЯ СИСТЕМА
Когда мы рассматривали задачу о взвешивании с помощью
гирь, мы предположили, что груз лежит на одной чашке, а гири —
на другой. Но если разрешить класть гири на обе чашки весов, то
ответ в задаче об оптимальной системе разновесок изменится. Оп-
тимальной теперь будет система из гирек с массами, образованны-
ми степенями тройки. Этой задачей интересовался Д. И. Менделеев
в бытность свою председателем Российской палаты мер и весов*).

*) Менделеев имел широкие интересы как в чистой, так и в прикладной науке.
Он занимался, например, и экономикой, и демографией, известны его исследования
об оптимальной концентрации спирта в воде при производстве водки, по просьбе
генштаба он раскрыл состав артиллерийского пороха, используемого немецкой ар-
мией. Отвечая на один вопрос Менделеева, А. А. Марков написал знаменитую ра-
боту об оценке производной многочлена через величину его максимального значе-
ния на отрезке.
31
Оказалось, что частный случай этой задачи был опубликован
в книге Баше де Мезириака в XVII веке, а ранее был известен
Фибоначчи. Спрашивалось, какое наименьшее число гирь нужно
иметь, чтобы можно было взвесить любой груз от 1 до 40 г. Опти-
мальным оказался набор гирь 1, 3, 9, 27 г. Для того чтобы взве-
сить груз в n г, надо представить число n в виде суммы a0 +3a1 +
+9a2 +27a3 , где ai =0, ±1 (i=0, 1, 2, 3). Тогда для его взвеши-
вания достаточно на чашку вместе с грузом положить все гири,
массы которых входят в эту сумму со знаком минус, а на противо-
положную чашку положить все гири, массы которых входят в эту
сумму со знаком плюс.
Но как найти такую сумму? Один из возможных способов
решения этой задачи основан на сведении её к представлению
числа n+40 в виде суммы b0 +3b1 +9b2 +27b3 , где bi =0, 1, 2
(i=0, 1, 2, 3). Мы уже знаем, что эта задача равносильна предста-
влению числа n+40 в троичной системе n+40=(b0 b1 b2 b3 )3 . Один
из алгоритмов её решения заключается в том, что на правую чашку
весов кладутся вначале самые тяжёлые гири, потом гири меньшего
веса и т. д. Например, этот алгоритм для числа 40 даёт разложение
40=27+9+3+1. Если мы уравновесили массу n+40 г, поло-
жив на чашку bi гирь массы 3i (i=0, 1, 2, 3), то перекладывая
на другую чашку по одной гире каждой массы, мы уравновесим
n г. На алгебраическом языке это означает, что будет получено
равенство n=a0 +3a1 +9a2 +27a3 , ai =bi ?1 (i=0, 1, 2, 3). Оче-
видно, что при этом ai =0, ±1 (i=0, 1, 2, 3). Верно и обратное,
а именно, из разложения n=a0 +3a1 +9a2 +27a3 , ai =0, ±1
(i=0, 1, 2, 3) можно получить разложение n+40=b0 +3b1 +9b2 +
+27b3 , bi =0, 1, 2 (i=0, 1, 2, 3). Поэтому из известной нам един-
ственности представления n+40=b0 +3b1 +9b2 +27b3 , bi =0, 1, 2
(i=0, 1, 2, 3), означающей единственность записи данного числа
в троичной системе, вытекает единственность представления n=
=a0 +3a1 +9a2 +27a3 , ai =0, ±1 (i=0, 1, 2, 3), означающая един-
ственность записи данного числа в так называемой уравновешенной
троичной системе, n=(a0 a1 a2 a3 )3 .
Эта система способна составить некоторую конкуренцию дво-
ичной системе как по простоте арифметических алгоритмов, так
и по количеству применений в математических задачах. Удобным
её свойством является то, что для изменения знака у представляе-
мого числа достаточно изменить знаки у всех его цифр.
В общем виде доказанные выше утверждения можно записать
следующим образом.
Любое целое число от ?(3n ?1)/2 до (3n ?1)/2 может быть
однозначно представлено в виде 3n?1 bn?1 +...+3b1 +b0 , где bi =
=0, ±1. Для того чтобы взвесить любой груз от 1 до (3n ?1)/2 г
за одно взвешивание, достаточно иметь гири 1, 3, 9, ..., 3n?1 г.
32
Читатель легко докажет всё это самостоятельно, если заметит,
что (3n ?1)/2=1+3+32 +...+3n?1 , другими словами, троичная
запись числа (3n ?1)/2 состоит из одних единиц.
Докажем, что меньшего количества гирь недостаточно, и пред-
ложенная система для грузов от 1 до (3n ?1)/2 г оптимальна. До-
пустим, что есть система из n?1 гирь с массами g1 , ..., gn?1 , по-
зволяющая взвесить любой из этих грузов. Это значит, что любое
число m от ?(3n ?1)/2 до (3n ?1)/2 можно представить в виде
алгебраической суммы a1 g1 +...+an?1 gn?1 , ai =0, ±1, (i=1, ...
..., n?1). Но таких сумм ровно 3n?1 , так как каждое слагаемое
входит в неё с одним из трёх возможных коэффициентов. Но 3n?1
меньше общего числа различных грузов, равного 3n .
14. Покажите, что оптимальная система гирь для взвешивания
грузов от 1 до (3n ?1)/2 определена однозначно.
15. Докажите, что для взвешивания любого груза от 1 до m г,
n?1 ?1)/2<m?(3n ?1)/2, наименьшее количество гирь рав-
(3
но n, а в случае m<(3n ?1)/2 выбор гирь неоднозначен.
Уравновешенная троичная система, кроме указанного выше
свойства, обладает ещё несколькими удобными свойствами. Напри-
мер, для выполнения округления в этой системе достаточно просто
отбросить лишние цифры. В неуравновешенной системе, даже дво-
ичной, округление выполняется не так просто. Так же просто, как
и в уравновешенной системе, производится сравнение чисел по ве-
личине, но не нужно обращать при этом внимание на знак числа.
Кстати, знак числа в этой системе определяется знаком старшей
ненулевой цифры, и не нужно использовать специальный знако-
вый бит, как в двоичной системе. А таблицы сложения, умноже-
ния и деления почти так же просты, как и в двоичной системе.
Вычитание же просто сводится к сложению со сменой знака у вы-
читаемого. При записи чисел в этой системе удобно вместо ?1
писать 1. Так как таблица умножения и деления совсем просты,
приведём только таблицу сложения:
1+1=11, 1+1=00, 1+1=11,
1+0=01, 1+0=01.
Умножение, как и деление, тоже сводится к перемене знака и сло-
жению. Другим достоинством троичной системы является то, что
запись в ней имеет длину на одну треть меньше, чем в двоичной.
Видимо, благодаря им троичная уравновешенная система была
положена в основу советского компьютера <Сетунь>, построенного
в конце 1950-х годов.
Однако широкого распространения она не получила, так как
всё же элементная база компьютеров, как того времени, так и со-
временных, остаётся двоичной, а битовое представление троичной
системы даже длиннее, чем двоичной.
33
Уравновешенная система может быть рассмотрена и для любого
натурального основания, правда, при чётном основании запись в ней
перестаёт быть однозначной. Преимуществом уравновешенных
систем является то, что в них записываются и отрицательные
числа без знака минус перед записью, а также то, что таблица
умножения в этих системах в сравнении с обычными примерно
в четыре раза короче, как отметил О. Л. Коши.
16. Запишите число (1234567890)10 в уравновешенной деся-
тичной системе счисления.
Утверждение следующей задачи на первый взгляд кажется
ложным, однако присмотритесь к ней повнимательнее.
17. Докажите, что любое ненулевое целое число имеет един-
ственное знакопеременное двоичное представление 2?0 ?2?1 +...
...+(?1)k 2?k , где ?0 <?1 <...<?k.
Десятичную запись чисел можно преобразовать в запись, со-
стоящую из цифр 0, ±1, ±2, ±3, ±4, ±5, заменяя все цифры,
большие 5 на их дополнения до 10, взятые с противоположным
знаком, и делая при этом единичный перенос в следующий раз-
ряд. Сложение и умножение таких записей можно делать так же,
как и обычных, только при этом переносы в следующие разряды
могут быть отрицательными. Оценки для числа операций при этом
не улучшатся, но сами операции в некотором смысле станут проще,
так как для их выполнения достаточно помнить таблицу умноже-
ния 5?5. Например, перемножим числа 89 и 98. Запишем первое
из них как (1 ?1 ?1), а второе — (1 0 ?2). Умножаем столбиком:

<< Пред. стр.

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

ОГЛАВЛЕНИЕ

След. стр. >>

Copyright © Design by: Sunlight webdesign