Оптимальная кодировка почтового индекса

19

МАТЕМАТИЧЕСКИЕ
РАБОТЫ ШКОЛЬНИКОВ

Здесь приведется две небольшие заметки, написанные десятикlassисками Ярославом Карповым из Ленинграда (школа № 239) и Алексадром Лобковским из Черногодовки Московской области (школа № 82) на современно разные темы. Их объединяет то, что обе статьи — «компьютерно-mатематические»: в них математические рассуждения позволяют получить интересные наблюдения только после подключения к работе ЭВМ.

Оптимальная кодировка почтового индекса

Я. Ю. КАРПОВ

Перед мной вставл вопрос: почему на конвертах используется именно такой набор цифр (рис. 1)—ведь эти кодировки можно заменить другими. Посмотрим, сколько различных наборов можно придумать (таблица 1). Всего 2×4×3×2×2×2×3×2=1152 вариантов.

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

Для характеристики различной кодировки цифр введем термин — расстояние между двумя кодировками. Расстояния должны удовлетворять таким условиям:

1. Чем больше расстояние между двумя кодировками, тем меньше вероятность того, что автомат примет одну кодировку за другую.

2. Расстояние от кодировки $A$ до кодировки $B$ должно быть равно расстоянию от кодировки $B$ до кодировки $A$.

Эти условия удовлетворяют расстояние Хемминга. В нашем случае — это количество «несовпадающих» символов в кодировках, т. е. количество несовпадших палочки.

При мер: Найдем расстояние между кодировками 5 и 2 (рис. 2). Расстояние между этими кодировками равно 5, так как у этих кодировок 5 несовпадющих палочки.

Обозначим через $p$ базовый вероятность ошибки, т. е. вероятность принятия автоматом палочки за «непалочку» или наборот. Тогда вероятность правильного распознавания одной палочки равна $1-p$.

Найдем, например, вероятность принятия цифры 6 за 0 (рис. 3). Для этого нужно, чтобы 8 палочки и два пробела были поняты автоматом правильно, а одна палочка была принята за пробел. Вероятность этого события равна $p(1-p)^{8}$.

Вообщие, при расстоянии автоматом любой цифры вероятность того, что эта цифра будет принята за другую, равна $p^{\gamma}(1-p)^{\alpha-\gamma}$, где $\gamma$ — расстояние между этими двумя кодировками по Хеммингу.

При расстоянии автоматом одной конкретной цифры $i$ вероятность того, что ее ошибочно примут за любую другую, равна

$$\sum_{j=i}^{n} p^{\gamma,j}(1-p)^{n-\gamma},$$

где $r_{i,j}$ — расстояние между цифрами $i$ и $j$.

20

Предположим, что все цифры встречются одинаково часть на любом из мест. Тогда средняя верятность неправильного распознавания какой-то цифры равна

$$P = \frac{1}{10} \sum_{i=0}^{9} \sum_{j=0}^{p_{j,i,j}} (1-p)^{9-r_{j,i,j}}.$$

Эту верятность мы и будем использовать в качестве критерия качества набора: чем она меньше, тем «лучше» набор.

Основанный на этом критерии перебор всех 1152 вариантов кодов был получен на ЭВМ ЕС-1035. Программа перебор была составлена на языке Фортран. В программе все варианты записей цифр кодировались в виде массивов, состоящих из 1 и 0, по следующему принципу (рис. 4): если в записи цифры присутствует палочка на данном месте, то в кодировке на месте с номером, указанным на схеме, будет записана 1, если нет — то 0.

Пример: Закодируем цифру 2, заданную в общичном виде (как на конвертах):

$$0, 1, 0, 0, 1, 1, 0, 0, 1.$$

Вариants кодировок цифры $i$ записывались в матрице $ki$, где количество строк равно 9, а количество столбцов совпадало с количество вариантов кодировок.

Для каждого значения базовой верятности ошибки $p$ перебирались все 1152 варианта наборов, их качество оценивалось по формуле (*), из них выбирался лучший и второй по качеству. Для этого для каждого набора формировалась матрица расстояний, которая выводилась для лучшего набора. Так как кодировки 8 и 0 имеют только по одному варианту, эти цифры не перебирались, и в вывode не участвовали.

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

$$0 < p \leq 0,3$$

напулящей кодировкой оказалась та самая, которая используется на конвертах (см. рис. 1). Так как реализная верятность ошибки распознающего автомата на почте заведomo лежит в этом пределе, то данный набор является наиболее便利ным.

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

При $p=0,4$ эти наборы меняются местами.

При увеличении верятности до 0,5 все верятности становятся равными, поэтому оченьindo, что все наборы станут одинаковыми.

Конечно, мне было бы принять, если бы моя программа выявила не принятый на почте набор, а другой: я тогда смог бы предложить заменить принятый набор на свой — лучший.

Увы! Наверное, когда на почте отбирали оптимальный набор, задачу оптимизации решали так же, как и я.

Отредакции. К своим материалам, опубликованным выше, Я. Карпов приложил распечати программы (на языке Фортран), реализующие алгоритмы, описанные в статье. Распечатики дают представление о достаточно высокой программистской культуре автора статьи. К ним имеютсяясно формулированные комментарии, позволяющие легко читать программы. Однако недостаток места, а также неудачный выбор языка (Фортран не входит в школьный курс информатики) не позволяет нам опубликовать эту часть материалов.

Авторов статей, рассчитанных на использование ЭВМ, мы просим обязать поисыть свои листингы; желательно, чтобы программы были составлены на языке Бейсик (или Раппа).