Прогулянки з математикою

Прогулянки з математикою

Інтерв'ю Єгора Антощенко з Григорієм Кабатянскім
"Кот Шредінгера" №7-8 2017

"Математичні прогулянки" – так називається проект, який запустив Інститут проблем передачі інформації їм. А. А. Харкевича РАН спільно з сколковского інститутом науки і технологій (Сколтех). Вчені в невимушеному форматі розповідають, чим вони займаються і де ми можемо зустріти результати їх досліджень. "КШ" вирішив прогулятися з Григорієм Кабатянскім, Радником з науки ректора Сколтеха, професором НДУ ВШЕ і головним науковим співробітником ІППІ РАН.

Григорій Кабатянскій (Нар. 1949). З відзнакою закінчив механіко-математичний факультет МГУ ім. М. В. Ломоносова. З 1971 по 1990 рік працював в НДІ автоматичної апаратури. Це був закритий інститут, пов'язаний з обороною, – в СРСР їх називали «поштовими скриньками». У 1990-му перейшов в Інститут проблем передачі інформації РАН. Як запрошений професор-дослідник виїжджав до університетів США, Франції, Великобританії, Німеччини, Нідерландів, Швеції, Норвегії та Південної Кореї. Є радником ректора Сколтеха і професором факультету комп'ютерних наук НДУ ВШЕ. Певне уявлення про наукові інтереси Кабатянского дають його роботи: «Коди для захисту авторських прав: випадок двох піратів», «Про виправлення помилок при викривлення в каналі і синдромі»,«Математика поділу секрету», «Про межі для упаковок на сфері і в просторі», «Контактні числа, коди і сферичні многочлени».

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

Москва. Вулиця Фотієва, найближча станція метро – "Університет". Прогулянка починається біля ліцею "Друга школа", де в старших класах навчався Григорій Анатолійович.

… Ні, я не був вундеркіндом. Хоча вважати і читати почав рано. До сих пір пам'ятаю книжку Г. Н. Бермана "Число і наука про нього", тому що вона допомогла мені виграти дворовий суперечка про найбільшому числі.

Я вчився в Мар'їній Гаю у звичайній школі. Після восьмого класу потрібно було кудись йти далі. І наша вчителька математики сказала мені, що є неподалік школа ім. А. М. Горького: там не тільки література, а й математика хороша. Я пішов, поговорив з учителем математики, написав перевірочну роботу. Він подивився її і сказав: "У нас, звичайно, тобі буде добре, але от є така Друга школа …" Я нічого про неї не знав. Де це, що це? Поїхав туди. Напевно, це був перший серйозний виклик в моєму житті.

Вчитися спочатку було дуже непросто. До цього я не ходив ні на які математичні гуртки і знав тільки те, чого вчили в школі.Підозрюю, що в якийсь момент я був на межі відрахування. Пам'ятаю, чудовий математик і педагог Євген Борисович Динкін ​​любив влаштовувати нам, учням математичних класів Другий школи, прогулянки на теплоході. Квитки він купував на свої гроші. Брав він не всіх, а тільки найсильніших і найслабших. У перший раз я потрапив саме як слабкий. Першу чверть якось вижив, а потім … Успіх народжує інтерес, інтерес породжує успіх, це така розкручується спіраль.

Євген Динкін (1924-2014) – математик, учень Колмогорова. Відомий роботами в області груп і алгебр Лі, а також теорії ймовірностей. Викладач і популяризатор математики; ще будучи студентом, почав організовувати гуртки для школярів. З 1954 року професор МГУ. У 1967-му за підтримку правозахисників був звільнений з університету. У 1976-му емігрував до США, де працював в Корнельському університеті.

Друга школа сильно змінила моє життя. Справа не в тому, що мене навчили тут математики та літератури, – мене навчили тому, що по-англійськи називається think differently: Думати інакше. Тут я отримав перші уроки вільнодумства.

До речі, через інакомислення Другу школу розігнали.Одного з вчителів заарештували: він був пов'язаний з дисидентами. Директора звільнили, багато вчителів в знак протесту пішли самі.

Пам'ятаю, в університеті першу догану я отримав за те, що не відвідав жодного заняття з історії КПРС. Я не любив активних комсомольців, хоча сам значився в ВЛКСМ: без цього не можна було. Коли мені виповнилося двадцять вісім років і треба було виходити з комсомолу (за віком), мені запропонували вступити в партію – для цього потрібно було рік ходити кандидатом в члени КПРС. Я запитав: "Хіба в партію є черга?" Людину, яка зі мною говорив, перекосило, але він стримався: "Припустимо, вам не подобається слово" чергу ", але, в загальному, треба рік почекати". Я кажу: "Але я вважаю себе негідним. Тому, що я рік почекаю, я не стану краще". Загалом, хвилин через десять та людина пішов, а потім мені його слова переказали: "А ви говорили, розумний. Повний ідіот! Я пропонував вступити в партію, а він відмовився".

Коли на Заході запитують, що мені більше подобається: сучасна Росія або Радянський Союз, я говорю – Радянський Союз. Це завжди дивує. А просто я тоді був молодий. Взагалі ж, я абсолютно спокійно жив в той час і живу в цьому.І немає у мене дурного бажання сказати: "Ах, якби я …" Відомо, що історія не знає умовного способу, історія конкретної людини – теж.

Мені здається, що частка "дітей" – я називаю так всіх, хто молодше двадцяти, – яким цікаво займатися наукою, константна. Але суспільство може виштовхувати їх з цього середовища: "Навіщо ти туди йдеш? Займися-ка краще чимось іншим – будеш добре жити!" А може бути навпаки: школярів мотивують, і в підсумку в науку йдуть ті, хто при інших розкладах стали б хорошими адвокатами.

От якби мої дитинство і юність припали на нинішній час, я б адвокатом і став. Це цікаво: живі люди. До того ж у хорошого адвоката повинно бути гарне логічне мислення, а воно у мене, вважаю, є. Єдине "але": хороший адвокат – він трохи обманщик …

"Невже ви не хочете бути першим?"

Йдемо в сторону Університетського проспекту. На одному з будинків вивіска "Академія єдиноборств".

… Є така розповідь у Вікторії Токарєвої. Здається, "Інструктор з плавання". Там про 18-річну дівчину, яка закохалася в зрілого чоловіка років тридцяти, який виявляється тренером з плавання. Вона запитує: "А яке у них майбутнє – у тих, хто вчить плавати?" І він видає у відповідь велику фразу: "Майбутнє в основному у тих, хто пливе". Ось в науці точно так же.Взагалі, заняття наукою – це професійний спорт. Причому математика – одиночний вид. В інших науках статті пишуть цілі колективи, три людини мінімум. А в математиці все як і раніше: першовідкривач, як правило, один.

Коли мій учитель умовляв мене на другому курсі продовжувати інтенсивно займатися математикою, він так і запитав: "Невже ви не хочете бути першим?" Я сказав, що у мене, напевно, є марнославство, але воно якесь недорозвинене. Він відповів: "Без марнославства в математиці нічого робити". Можете називати це як завгодно, але повинен бути комплекс переможця. Запам'ятовують тільки тих, хто перший що-небудь довів. Ось вони залишаються.

Так, за науку не так багато платять, як за футбол, там немає багатомільйонних гонорарів. Але в більшості видів спорту, навіть якщо прибрати призовий фонд, люди будуть з тією ж швидкістю, з тим же напором бігати і битися. Тільки за те, щоб встати на першу сходинку.

Я не кажу, що мозок – ті ж самі м'язи. Але часом він поводиться дуже схоже. Якщо ви перестаєте тренувати мозок, то все. Кращі результати в спорті досягаються приблизно так само, як і в науці. Ну і вік – до тридцяти, до сорока.А потім, як і в професійному спорті, треба зрозуміти, що, хоча ти все ще бігаєш і стрибаєш, треба починати вчити інших.

Горбачов, Єльцин і вулична математика

Перетинаємо Університетський проспект. Це саме людне місце на нашому маршруті.

… Згадалася одна задача. Вона про ситуаціях, коли математика суперечить здоровому глузду і виявляється права, а здоровий глузд – немає. Завдання стара, але в 91-му році, коли розвалювався Радянський Союз, я почув її в абсолютно новій редакції: "У Росії зараз двовладдя. Є Єльцин, і є Горбачов, а ядерний чемоданчик один. Як зробити так, щоб один без іншого не міг його відкрити і щоб якщо вже вони вирішили почати третю війну, то хоча б зробили це узгоджено? "

Уявімо, що цей чемоданчик відкривається шифром зі ста біт. І ці сто біт написані на стрічці у вигляді нуликів і одиниць.

Що підказує здоровий глузд? Якщо ви вважаєте цих двох рівними партнерами, то розріжте стрічку навпіл і віддайте її частини одному і іншому. Тоді, щоб відкрити валізку, кожному доведеться перебрати всі варіанти відсутніх п'ятдесяти біт, тобто два в п'ятдесятої ступеня варіантів.Вручну це, звичайно, не зробити, але якщо підключити КДБ з суперкомп'ютером, то, в принципі, можна. А ось два в сотої ступені не перебрати за розумний час навіть за допомогою КДБ. Але два в сотої – це тільки якщо весь ключ у одного. Але їх же двоє, я повинен поділити секрет.

Одна з тем, якими зараз займається Кабатянскій, лежить на стику математики і кріміналісткі. Мова йде про застосування кодів при знятті відбитків пальців. Найближчим часом в журналі Designs, Codes and Cryptography повинна вийти стаття "Constructions of almost secure frameproof codes with applications to fingerprinting schemes", одним з авторів якої є Кабатянскій

Виявляється, здоровий глузд не найкращий порадник. Рішення дуже просте. Потрібно одному з них, наприклад Михайлу Сергійовичу, дати абсолютно випадкові сто біт. Потім взяти наш ключ, інші сто біт, і скласти їх поразрядно – першу позицію з першої, другої з другої – з ста битами, які отримав Горбачов. Складати по модулю 2, тобто: 1 + 1 і 0 + 0 = 0, а 1 + 0 або 0 + 1 = 1. Отримана сума – це треті сто біт, які ми віддаємо Борису Миколайовичу.

Виходить, що ні у одного з них немає інформації про ключі. Сидячи порізно, вони повинні будуть перебрати сто біт. Іншого виходу немає. А коли сідають разом, то просто складають біти по модулю 2 і отримують секрет.Таку систему не зламати, принаймні поки. І головне, просто! Це те, що люблять називати вуличної математикою – ми можемо людині на вулиці пояснити завдання, і він зрозуміє, за що він, як платник податків, віддає нам гроші.

Упакувати кулі в Nвимірному просторі

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

… У мене є один хороший математичний результат. Це межа Кабатянского – Левенштейна. Звичайно, я і потім робив якісь речі, які мені самому подобаються, але вони непорівнянні за значимістю, за інтересом, який проявляють до них інші люди.

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

Взяти хоч ці апельсини. Ось як укласти їх в коробку самим компактним чином?

Все почалося з англійських кораблів, які перевозили гарматні ядра в американську колонію. Виникали різні питання, один з них був таким: якщо розташувати ядра в трюмі щільно, не потоне корабель? Або: як підрахувати, яку частку обсягу вони будуть займати при самій щільній упаковці?

З'явилася гіпотеза, що найщільнішою буде так звана гранецентрированная кубічна упаковка, – це приблизно як апельсини на вітрині лежать. Гіпотезу приписують Йогану Кеплеру, хоча насправді вона постарше. Через чотири століття, в 1998 році, цю гіпотезу довів американський математик Томас Хейлс. Доказ було виконано за допомогою комп'ютера і займає пару сотень сторінок. Щоб переконатися в його справедливості, експертам знадобилося п'ять років.

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

Володимир Левенштейн (Нар. 1935). З 1958 року по теперішній час працює в Інституті прикладної математики ім. М. В. Келдиша РАН. У 1965 році ввів поняття відстані редагування. На відміну від багатьох математичних понять, це можна досить легко пояснити. Мова про кількість операцій вставки, видалення і заміни символів, які потрібно зробити, щоб перевести одну послідовність в іншу. Наприклад, щоб перетворити "сорт" в "кіт", потрібно зробити одну заміну і одне вилучення, відстань дорівнює 2.

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

Йдемо в сторону Ломоносовського проспекту. Ззаду ледь видно "золоті мізки" – президія РАН. Попереду з туману проступає шпиль МГУ. Навколо магазини, кафе, банки.

… Взагалі-то я себе математиком не вважаю. Я просто займаюся наукою. І в цій науці використовую свої невеликі знання для вирішення цікавих завдань. Але для чистої математики вони представляють інтерес ну вкрай рідко.

Чесно кажучи, ніколи не розумів поділу математики на чисту і прикладну. Прикладні завдання – в будь-якій області – народжують завдання математичні. І хтось береться їх вирішити. Буває так: те, що він вирішив, справжнім "прикладникам" не потрібно. Але, дивлячись на це рішення, вони придумують щось інше, що вже дійсно можна використовувати.

Григорій Кабатянскій: "Математика без практичного застосування дуже швидко вихолощується. У неї залишаються тільки внутрішні мотиви самовдосконалення. Це сильно її збіднює"

З іншого боку, ті, хто займається прикладними завданнями сьогоднішнього дня, часто домагаються математичних результатів, які не можуть отримати їх колеги, начебто роблять математику майбутнього. Це як з людиною, який оглух на одне вухо або осліп на одне око.Адже він не перестає чути або бачити. Але сприйняття стає "плоским". Зникає об'ємне звучання або об'ємний зір. Так і тут. Звичайно, одному вченому важко займатися і чистою математикою, і прикладної. Але якщо в самій науці відбувається перекіс в ту або іншу сторону, це теж недобре.

Ще раз: немає ніякого поділу на чисту і прикладну математику. Є математика, яка знайшла додаток, і та, що ще не знайшла.

Як виправити помилку

Підходимо до метро "Університет". Кабатянскій дістає смартфон. щось набирає в пошуковику.

… Завжди, коли ви вмикаєте в мобільнику стандарт 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 вистачить.

Одна з моїх хороших робіт – про коди, що виправляють лише однієї помилки. Коли мені виповнилося тридцять років, батько подарував мені книгу. Я не можу зараз сказати, яку саме, але добре пам'ятаю дарчий напис: "Помилки в житті не так просто виправляти, як в сигналах".

Фото Артема Поповича


Like this post? Please share to your friends:
Залишити відповідь

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: