Григорий Кабатянский: Мозг - не мышцы, но порой он ведет себя похоже
Григорий Кабатянский (род. 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 хватит.
Одна из моих хороших работ - она про коды, исправляющие всего одну ошибку. Когда мне исполнилось тридцать лет, отец подарил мне книгу. Я не могу сейчас сказать, какую именно, но хорошо помню дарственную надпись: "Ошибки в жизни не так просто исправлять, как в сигналах".