Прогулки с математикой

Прогулки с математикой

// Григорий Кабатянский: биты, коды, ошибки и упаковка апельсинов в многомерном пространстве
Авторы: Егор Антощенко

«Математические прогулки» — так называет­ся проект, который запустил Институт проблем передачи информации им. А. А. Харкевича РАН совместно со Сколковским ­институтом науки и технологий (Сколтех). Учёные в непринуждённом формате рассказывают, чем они занимаются и где мы можем встретить результаты их исследований. «КШ» решил прогуляться с Григорием Кабатянским, советником по науке ректора Сколтеха, профессором НИУ ВШЭ и главным научным сотрудником ИППИ РАН.

Григорий Кабатянский (род. 1949). С отличием окончил механико-​математический факультет МГУ им. М. В. Ломоносова. С 1971 по 1990 год работал в НИИ автоматической аппаратуры. Это был закрытый институт, связанный с обороной, — в СССР их называли «почтовыми ящиками». В 1990-м перешёл в Институт проблем передачи информации РАН. Как приглашённый профессор-​исследователь выезжал в университеты США, Франции, Великобритании, Германии, Нидерландов, Швеции, Норвегии и Южной Кореи. Является советником ректо­ра Сколтеха и профессором факультета компьютерных наук НИУ ВШЭ. Некоторое представление о научных интересах Кабатянского дают его работы: «Коды для защиты авторских прав: случай двух пиратов», «Об исправлении ошибок при искажениях в канале и синдроме», «Математика разделения секрета», «О границах для упаковок на сфере и в пространстве», «Контактные числа, коды и сферические мно­го­чле­ны».

Успех рождает интерес, интерес рождает успех

// Москва. Улица Фотиевой, ближайшая станция метро — «Университет». Прогулка начинается у лицея «Вторая школа», где в старших классах учился Григорий Анатольевич.

...Нет, я не был вундеркиндом. Хотя считать и читать начал рано. До сих пор помню книжку Г. Н. Бермана «Число и наука о нём», потому что она помогла мне выиграть дворовый спор о самом большом числе.

Я учился в Марьиной Роще в обычной школе. После восьмого класса нужно было куда-то идти дальше. И наша учительница математики сказала мне, что есть неподалёку школа им. А. М. Горького: там не только литература, но и математика хорошая. Я пошёл, побеседовал с учителем математики, написал проверочную работу. Он посмотрел её и сказал: «У нас, конечно, тебе будет хорошо, но вот есть такая Вторая школа...» Я ничего про неё не знал. Где это, что это? Поехал туда. Наверное, это был первый серьёзный вызов в моей жизни.

Учиться поначалу было очень непросто. До этого я не ходил ни на какие математические кружки и знал только то, чему учили в школе. Подозреваю, что в какой‑то момент я был на грани отчисления. Помню, замечательный математик и педагог Евгений Борисович Дынкин любил устраивать нам, ученикам математических классов Второй школы, прогулки на теплоходе. Билеты он покупал на свои деньги. Брал он не всех, а только самых сильных и самых слабых. В первый раз я попал именно как слабый. Первую четверть как-то выжил, а потом... Успех рождает интерес, интерес рождает успех, это такая раскручивающаяся спираль.

Евгений Дынкин (1924–2014) — математик, ученик Кол­могорова. Известен работами в области групп и алгебр Ли, а также теории вероятностей. Преподаватель и популяризатор математики; ещё будучи студентом, начал организовывать кружки для школьников. С 1954 года профессор МГУ. В 1967-м за поддержку правозащитников был уволен из университета. В 1976-м эмигрировал в США, где работал в Корнелльском университете.

Вторая школа сильно изменила мою жизнь. Дело не в том, что меня научили здесь математике и литературе, — меня научили тому, что по-английски называется think differently: думать иначе. Здесь я получил первые уроки свободомыслия.

Кстати, из-за инакомыслия Вторую школу разогнали. Одного из учителей арестовали: он был связан с диссидентами. Директора уволили, многие учителя в знак протеста ушли сами.

Помню, в университете первый выговор я получил за то, что не посетил ни одного занятия по истории КПСС. Я не любил активных комсомольцев, хотя сам числился в ВЛКСМ: без этого было нельзя. Когда мне исполнилось двадцать восемь лет и надо было выходить из ­комсомола (по возрасту), мне предложили вступить в партию — для этого нужно было год ходить кандидатом в члены КПСС. Я спросил: «Разве в партию есть очередь?» Человека, который со мной говорил, перекосило, но он сдержался: «Допустим, вам не нравится слово „очередь“, но, в общем, надо год подождать». Я говорю: «Но я считаю себя недостойным. Оттого, что я год подожду, я не стану лучше». В общем, минут через десять тот человек ушёл, а потом мне его слова пересказали: «А вы говорили, умный. Полный идиот! Я предлагал вступить в партию, а он отказался».

Когда на Западе спрашивают, что мне больше нравится: современная Россия или Советский Союз, я говорю — Советский Союз. Это всегда удивляет. А просто я тогда был молодой. Вообще же, я совершенно спокойно жил в том времени и живу в этом. И нет у меня глупого желания сказать: «Ах, если бы я...» Известно, что ­история не знает сослагательного наклонения, история конкретного человека — тоже.

Мне кажется, что доля «детей» — я называю так всех, кто моложе двадцати, — которым интересно заниматься наукой, константна. Но общество может выталкивать их из этой среды: «Зачем ты туда идёшь? Займись-ка лучше чем-то другим — будешь хорошо жить!» А может быть наоборот: школьников мотивируют, и в итоге в науку идут те, кто при других раскладах стали бы хорошими адвокатами.

Вот если бы мои детство и юность пришлись на нынешнее время, я бы адвокатом и стал. Это интересно: живые люди. К тому же у хорошего адвоката должно быть хорошее логическое мышление, а оно у меня, полагаю, есть. Единственное «но»: хороший адвокат — он немного обманщик...

«Неужели вы не хотите быть первым?»

// Идём в сторону Университетского проспекта. На одном из домов вывеска «Академия единоборств».

...Есть такой рассказ у Виктории Токаревой. Кажется, «Инструктор по плаванию». Там про 18-летнюю девушку, влюбившуюся в ­зрелого мужчину лет тридцати, который оказывается тренером по плаванию. Она спрашивает: «А какое у них будущее — у тех, кто учит плавать?» И он выдаёт в ответ великую фразу: «Будущее в основном у тех, кто плывёт». Вот в науке точно так же. Вообще, занятие наукой — это профессиональный спорт. Причём математика — одиночный вид. В других науках статьи пишут целые коллективы, три человека минимум. А в математике всё по-прежнему: первооткрыватель, как правило, один.

Когда мой учитель уговаривал меня на втором курсе продолжать интенсивно заниматься математикой, он так и спросил: «Неужели вы не хотите быть первым?» Я сказал, что у меня, наверное, есть тщеславие, но оно какое-то недоразвитое. Он ответил: «Без тщеславия в математике нечего делать». Можете называть это как угодно, но должен быть комплекс победителя. Запоминают только тех, кто первый что-либо доказал. Вот они остаются.

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

Я не говорю, что мозг — те же самые мышцы. Но порой он ведёт себя очень похоже. Если вы перестаёте трени­ровать мозг, то всё. Лучшие результаты в спорте достигаются примерно так же, как и в науке. Ну и возраст — до тридцати, до сорока. А потом, как и в профессиональном спорте, надо понять, что, хотя ты всё ещё бегаешь и прыгаешь, надо начинать учить других.

Горбачёв, Ельцин и уличная математика

// Пересекаем Университетский проспект. Это самое людное место на нашем маршруте.

...Вспомнилась одна задача. Она о ситуациях, когда математика противоречит здравому смыслу и оказывается права, а здравый смысл — нет. Задача старая, но в 91-м году, когда разваливался Советский Союз, я услышал её в совершенно новой редакции: «В России сейчас двоевластие. Есть Ельцин, и есть Горбачёв, а ядерный чемоданчик один. Как сделать так, чтобы один без другого не мог его открыть и чтобы если уж они решили начать третью войну, то хотя бы сделали это согласованно?»

Представим, что этот чемоданчик открывается шифром из ста бит. И эти сто бит написаны на ленточке в виде ноликов и единиц.

Что подсказывает здравый смысл? Если вы считаете этих двоих равными партнёрами, то разрежьте ленточку пополам и отдайте её части одному и другому. Тогда, чтобы открыть чемоданчик, каждому придётся перебрать все варианты недостающих пятидесяти бит, то есть два в пятидесятой степени вариантов. ­Вручную это, конечно, не сделать, но если подключить КГБ с суперкомпьютером, то, в принципе, можно. А вот два в со­той степени не перебрать за разумное время даже с помощью КГБ. Но два в сотой — это только если весь ключ у одного. Но их же двое, я должен поделить секрет.

Оказывается, здравый смысл не лучший советчик. Решение очень простое. Нужно одному из них, например Михаилу Сергеевичу, дать совершенно случайные сто бит. Потом взять наш ключ, другие сто бит, и сложить их поразрядно — первую позицию с первой, вторую со второй — со ста битами, которые получил Горбачёв. Складывать по модулю 2, то есть: 1 + 1 и 0 + 0 = 0, а 1 + 0 или 0 + 1 = 1. Полученная сумма — это третьи сто бит, ­которые мы отдаём Борису Николаевичу.

Получается, что ни у одного из них нет информации о ключе. Сидя порознь, они должны будут перебрать сто бит. Другого выхода нет. А когда садятся вместе, то просто складывают биты по модулю 2 и получают секрет. Такую систему не взломать, по крайней мере пока. И главное, просто! Это то, что любят называть уличной математикой — мы можем человеку на улице объ­яснить задачу, и он поймёт, за что он, как налогоплательщик, отдаёт нам деньги.

Упаковать шары в N-мерном пространстве

// Киоск с фруктами. На прилавке яблоки, апельсины, груши. Продавец старается разложить товар так, чтобы он выглядел привлекательнее.

...У меня есть один хороший математический результат. Это граница Кабатянского — Левенштейна. Конечно, я и потом делал какие-то вещи, которые мне самому нравятся, но они несравнимы по значимости, по интересу, который проявляют к ним другие люди.

Результат относится к области чистой математики, а появился он потому, что и Левенштейн, и я занимались кодами, то есть математикой прикладной. Перед нами встала задача, существующая уже четыре столетия. Это, конечно, не теорема Ферма, но тоже очень заметная вещь.

Владимир Левенштейн (род. 1935). С 1958 года по настоящее время работает в Институте прикладной математики им. М. В. Келдыша РАН. В 1965 году ввёл понятие ­расстояния редактирования. В отличие от многих математических понятий, это ­можно достаточно легко объяснить. Речь о коли­честве операций вставки, удаления и замены символов, которые нужно совершить, чтобы перевести одну последовательность в другую. Например, чтобы превратить «сорт» в «кот», нужно совершить одну замену и одно удаление, расстояние равно 2.

Взять хоть эти апельсины. Вот как уложить их в коробку самым компактным образом?

Всё началось с английских кораблей, которые перевозили пушечные ядра в американскую колонию. Возникали разные вопросы, один из них был таким: если расположить ядра в трюме плотно, не потонет ли корабль? Или: как подсчитать, какую долю объёма они будут занимать при самой плотной упаковке?

Появилась гипотеза, что самой плотной будет так называемая гранецентрированная кубическая упаковка, — это примерно как апельсины на витрине лежат. Гипо­тезу приписывают Иоганну Кеплеру, хотя на самом деле она постарше. Спустя четыре столетия, в 1998 году, эту гипотезу доказал американский математик ­Томас ­Хейлс. Доказательство было выполнено с помощью компьютера и занимает пару сотен страниц. Чтобы убедиться в его справедливости, экспертам понадобилось пять лет.

Ну а мы с Левенштейном в 1978 году рассматривали обобщение этой задачи на случай многомерного пространства, используя технику, придуманную для кодов.

Математика: чистая и прикладная

// Идём в сторону Ломоносовского проспекта. Сзади едва видны «золотые мозги» — президиум РАН. Впереди из тумана проступает шпиль МГУ. Вокруг магазины, кафе, банки.

...Вообще-то я себя математиком не считаю. Я просто занимаюсь наукой. И в этой науке использую свои небольшие знания для решения интересных задач. Но для чистой математики они представляют интерес ну крайне редко.

Честно говоря, никогда не понимал деления математики на чистую и прикладную. Прикладные задачи — в любой области — рождают задачи математические. И кто-то берётся их решить. Бывает так: то, что он решил, настоящим «прикладникам» не нужно. Но, глядя на это решение, они придумывают что-то другое, что уже действительно можно использовать.

С другой стороны, те, кто занимается прикладными задачами сегодняшнего дня, часто добиваются матема­тических результатов, которые не могут получить их коллеги, вроде бы делающие математику будущего. Это как с человеком, который оглох на одно ухо или ослеп на один глаз. Он ведь не перестаёт слышать или видеть. Но восприятие становится «плоским». Исчезает объёмное звучание или объёмное зрение. Так и здесь. Конечно, одному учёному трудно заниматься и чистой математикой, и прикладной. Но если в самой науке происходит перекос в ту или иную сторону, это тоже нехорошо.

Ещё раз: нет никакого деления на чистую и прикладную математику. Есть математика, которая нашла приложе­ние, и та, что ещё не нашла.

Как исправить ошибку

// Подходим к метро «Университет». Кабатянский достаёт смартфон. Что-то набирает в поисковике.

...Всегда, когда вы включаете в мобильнике стандарт LTE, срабатывает код, который исправляет ошибки. Без этого вы остались бы на уровне связи 3G. Там тоже были коды, но слабенькие. А здесь сложные, хорошо продуманные, с непростыми алгоритмами исправления ошибок.

Есть проблема: ненадёжная передача сигнала, ненадёжное хранение битов информации. Как избежать ошибок? Самое простое, что делает любой человек, разговаривая по телефону в условиях плохой связи, — он повторяет слова. Если этого мало, проговаривает каждую букву: «К — Константин», «О — Ольга», «Т — Тамара». Это простейшее кодирование. Не самое мудрое, не очень эффективное, но наглядно показывает, что происходит: мы берём и запихиваем нужную информацию в гораздо более длинную последовательность.

Представьте, что кто-то посылает вам информацию, передавая бит 0 сигналом +1, а бит 1 — сигналом —1. В канале передачи есть шум, и вы можете получить не 1 или —1, а, допустим, 0,01. Вы не понимаете, как поступить, и склоняетесь к варианту вообще стереть этот ­символ. Или пришло 0,2. Скорее всего, полагаете вы, передавали +1. Но, возможно, вы ошибаетесь: это был —1, просто шума в этот момент было больше, чем вы думали. Тут современная математика говорит: «Я теперь ­скажу вам, чтобы вы передавали не просто информацию, а с приписанными к ней дополнительными (избыточными или проверочными) символами, и тогда будет вам ­счастье». В том смысле, что ошибки появляться будут, но вы сможете их исправить.

Объясню на примере. У нас есть поток битов: нулей и единиц. Нам важно правильно передать его, даже если при передаче происходят ошибки. И тут в действие вступа­ют коды. Самый известный — код Хэмминга (7,4). Поче­му семь и почему четыре, сейчас объясню. Мы берём этот поток и режем на кусочки по четыре бита. За ­каждыми четырьмя битами пишем три проверочных по специаль­ному правилу — это кодовый блок, и передаём блоки один за другим. Теперь, если при передаче информации в блоке произошла ошибка, мы её исправим.

Похоже на известную олимпиадную задачку. Некто загадал число X от единицы до миллиона. Мы хотим отгадать X, задавая вопросы, ответом на которые будет «да» или «нет». Сколько минимально понадобится вопросов? Правильный ответ: 20. Почему? Вы берёте миллион, делите пополам и спрашиваете: это в первых пятистах тысячах? Если да, то делите 500 000 пополам и повторяете вопрос применительно к половинкам этого числа. Если нет, то проделываете эту операцию со вторыми пятьюстами тысячами. И так далее. А что, если вопросы задаются не по очереди, а сразу? Сколько тогда нужно вопросов? Ответ: столько же! Например, мы спрашиваем (i+1)‑м вопросом, чему равна i‑я позиция Xi двоичного представления числа X. Тогда, зная ответы, мы находим загаданное число.

Ну вот, (7,4)-код работает почти так же. Из четырёх битов можно составить не так много кодовых слов: два в четвёртой степени — 16. А слов из семи битов — два в седьмой, 128. Если произошла одна ошибка, то кодовое слово не получится. Проверочные символы помогут узнать, в каком месте допущена ошибка. А поскольку сообщение записано в виде нулей и единиц, мы точно исправим её. Вариантов-то немного.

Кстати, одна из моих последних работ — про задачу Улама о лжеце. Как я уже говорил, чтобы угадать число от одного до миллиона, нужно двадцать вопросов. А что, если отвечавший один раз соврал: вместо «да» сказал «нет» или наоборот? Тогда потребуется двадцать пять вопросов.

Хорошо, а дальше? Как это будет происходить с числом до миллиарда или до триллиона? Если я загадаю число, которое записывается N битами, то, чтобы его угадать, понадобится N вопросов. А сколько нужно доба­вить в случае ошибки? Ответ удивительный: к N вопросам нужно добавить логарифм N. Первое решение нас к этому не приводит. Кажется, что должна быть весомая добавка к числу вопросов, но на деле за одного лжеца доплачиваешь не так много. Более того, если вы знаете, что соврать он может не более пяти раз, то пяти логарифмов N хватит.

Одна из моих хороших работ — про коды, исправляющие всего одну ошибку. Когда мне исполнилось тридцать лет, отец подарил мне книгу. Я не могу сейчас сказать, какую именно, но хорошо помню дарственную надпись: «Ошибки в жизни не так просто исправлять, как в сигналах».

 

Опубликовано в журнале «Кот Шрёдингера» №7-8 (33-34) за июль-август 2017 г.

Подписаться на «Кота Шрёдингера»