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

Составляя программу учебного курса для лаборатории математики, мы ищем возможность предложить его слушателям задачу с практическим применением. Или хотя бы показать приложения изучаемой науки. Сейчас речь о курсе «Коды и шифры»

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

Заметим, что эта постановка может не иметь ничего общего с реальным кодированием имен Игоря и Артема Чайки. Их коды – если «лсду3» и «йфяу9» вообще коды, а не случайность – могли быть получены из номера паспорта или любого другого признака персоны.

О решении

Давайте уточним, что математики называют решением.

Пример 1: решить уравнение

Вы смело беретесь за задачу и находите, что при подстановке единицы вместо x уравнение становится верным числовым равенством. Означает ли это, что «x=1» – решение уравнения? Да. Означает ли это, что вы решили уравнение? Пока что нет, поскольку есть и другие корни: x=2 и x=3. Когда вы их объедините с первым найденным и докажете, что четвертого быть не может, тогда и выйдет полное решение.

Что считаем решением задачи в нашей формулировке? Какой-нибудь алгоритм. Вот, например, сгодится этот:

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

А как насчет поиска всех способов закодировать имена граждан? Займемся комбинаторикой.

Пример 2. За барной стойкой стоит улыбающийся бармен…

… Неудачный пример. Забудьте о нем.

Пример 3. Бариста сделал двойной эспрессо, капучино маленький и большой. И ждет, когда за заказом подойдут Александр, Иннокентий и Эльдар. Он помнит, что Александру – эспрессо, Иннокентию – маленький капучино. А остальное забыл.

Но поскольку остального – людей и напитков – по одному, то соответствие устанавливается однозначно.

Пример 4. Такой же заказ, плюс добавляется морс. А к компании присоединилась Ирина. Бариста должен повторить напитки Александру с Иннокентием и снова забывает об остальном.

Сейчас соответствий людей напиткам уже может быть два:

Будем развивать процесс: добавлять готовые напитки и увеличивать компанию. Если мощность каждого из множеств равна N, все напитки разные, и бариста снова не запоминает клиентов после второго в группе, то нужно назначить (N−2) напитка (N−2)-м людям. Это делается числом способов, равным факториалу числа (N−2). Факториал натурального числа равен произведению всех чисел от единицы до этого числа:

2! = 2, 3! = 6, 4! = 24.

Факториал быстро растет с увеличением числа-аргумента. Для озвучивания вычисленного факториала числа людей, имеющих недвижимость в России, в русском языке не найдется подходящих слов.

Теперь коды

В приведенных примерах напитки аналогичны кодам. Сколько кодов может быть?

Предположим, что на каждом месте может стоять любая буква или цифра. На любом из пяти мест любой из 43 символов – 43*43*43*43*43 = 43⁵ кодов. Это число примерно равно 147 миллионам. Что-то около числа граждан нашей страны. Т.е. не исключено, что между множеством людей и кодами можно установить биекцию – взаимно однозначное соответствие. Это отображение прекрасно, потому что оно имеет обратное, которое уже кодам ставит в соответствие имя.

Не пробуйте вообразить число таких биекций.

У нас не биекция

Код «ЛСДУ3» по сфантазированному алгоритму получают несколько имен. Вот, например: «Арсен Юрьевич Жаока». Больше того, программка назначит код любой последовательности символов не длиннее 50 знаков. А значит, она исполняет роль баристы, у которого гостей заведомо больше 43⁵⁰ при длине карты напитков 43⁵.

Да что там биекция – предложенная игрушка это лишь хеш-функция.

Заключение

Друзья – иначе не обратиться к тем, кто дочитал до этого места, – учитывайте, что в этом мире живут работники отделов пиар, творческие специалисты СМИ и самые необыкновенные политики. Они любят сочинять для вас новости. Разберем пару заметок.

1) Сноб сообщает:

В Политехническом музее разгадали алгоритм превращения Артема Чайки в ЛСДУ3

Сотрудники лаборатории математики Политехнического музея выявили алгоритм, по которому имена Артема и Игоря Чаек превратились в коды из букв и цифр в Росреестре. По просьбе «Сноба» музей подготовил описание алгоритма…

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

2) Журнал Алексея Навального сожалеет и слегка драматизирует:

А у нас вот — математики Политеха расшифровали ЛСДУ3а. Точка приложения научных усилий в нашей стране. Дешифровка на службе граждан.

Расшифровка и дешифровка сильно не одно и то же. Подробности на нашем курсе осенью. И ждем новые коды из реестра:)

 —  —

Товарищи! Не выключайте критическое мышление, требуйте первоисточник и проходите не моргнув глазом мимо фраз: «В редакцию подкинули ценный алгоритм».

И спасибо

 — математикам, стерпевшим это безобразие;

 — службе новостей BBC и ТВ Дождь — они позвонили, чтобы уточнить подробности;

 — тем, кто в соцсетях на слова «раскрыто», «расшифровано», «русские учоные ого-го» реагировал в духе: «Ша уже! Что вы, хеширования не видели?» — и объяснял предметно.