Архив   Авторы  
Авраам Трахтман сегодня работает в университете Бар-Илан (на фото)

Графское это дело
Общество и наукаТехнология

Наш бывший соотечественник решил математическую проблему, которая не поддавалась ученым в течение четырех десятилетий

 

Вокруг имени этого ученого в математических кругах немало шума. Наш бывший соотечественник Авраам Трахтман, живущий в Израиле, решил задачу «раскраски дорог», над которой ломали головы ученые многих стран. Сейчас он, пожалуй, самый невозмутимый человек из всех, комментирующих открытие. И пусть Моше Каве, президент университета Бар-Илан, где работает герой дня, говорит, что этим достижением может гордиться страна, пусть коллеги, раздавая интервью, называют его «блестящим математиком с очень высоким IQ», сам он ко всему относится философски. «Ну какая может быть реакция окружающих? Обычная, - отвечает он на вопрос «Итогов». - Решил задачу - значит, молодец».

Впрочем, история Авраама Трахтмана не так уж обычна. «Как правило, серьезные математические открытия делают ученые в начале научной карьеры. На седьмом десятке это редкость», - говорит главный научный сотрудник отдела математической логики Математического института им. Стеклова РАН член-корреспондент РАН Лев Беклемишев. Аврааму Трахтману 63 года. И его долгий взлет объясняется просто: было время подождать.

До 1984 года Трахтман работал сотрудником Уральского политехнического института, где и получил ученую степень. В Израиле он с 1992 года и, как многие эмигранты, поначалу брался за любое дело: несколько месяцев служил охранником в магазине, нанимался учителем-почасовикомЕ Над научной проблемой, за решение которой его сегодня чествуют, он начал работать десять лет назад. И сегодня признается, что сделал открытие почти случайно. «Это в некотором роде побочный продукт, - говорит он. - Я размышлял над очень близкой задачей, так называемой задачей Черны. Но в результате нашел решение проблемы «раскраски дорог».

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

Теория графов стала активно развиваться в последние полвека - как раз из-за потребности моделировать на компьютере все что угодно, от климатических процессов до последовательности движений какого-нибудь персонажа в анимации. Впрочем, основные ее задачи по-прежнему принадлежат работе мысли и решаются «из головы», с помощью карандаша и листка бумаги. Более того, считается, что именно в этой области, относящейся к сфере дискретной математики, нужна особая «придумка», оригинальность подходов. Ведь к каждой задаче здесь нужно подобрать свой особенный, ни на что не похожий ключ.

Первой математической проблемой такого рода была вошедшая во все хрестоматии задача о семи мостах Кенигсберга, которую знаменитый математик Эйлер сумел решить еще в 1736 году. Считается, что тогда он впервые применил принципы теории графов. Издавна среди жителей города была распространена загадка: можно ли прогуляться по всем мостам, не пользуясь ни одним из них дважды? Эйлер впервые построил «сеть» из точек и соединяющих их ребер и доказал, что это невозможно. Другая, не менее известная задача, названная проблемой «четырех красок», была предложена математиком Госри в 1852 году. Следовало доказать, что всякую расположенную на сфере карту можно раскрасить четырьмя красками так, чтобы любые два соседних государства имели на этой карте разные цвета. Как ни проста была задача на вид, она не сдавалась математикам больше столетия. Лишь в 1976 году ее удалось решить, да и то с натяжкой. Это была первая крупная математическая теорема, для доказательства которой применили компьютер. Поэтому некоторые ученые отнеслись к доказательству с недоверием. Лишь позже, когда математики предложили другие алгоритмы решения и скорректировали ошибки, компьютерное доказательство, хотя и со скрипом, признали.

Поначалу казалось, что такая же судьба ожидает и еще одну задачу из области теории графов, сформулированную в 1970 году тремя математиками, одним израильским и двумя американскими. Нужно было доказать, что для любой системы возможно отыскать «синхронизирующее слово» - такую последовательность связей между вершинами графа, которая позволяла бы синхронным образом приводить систему в единое состояние. «Важно, что именно синхронно, - комментирует Трахтман. - Тут как в облаве на волков, нужно всем выступать одновременно. Чтобы никто не убежал».

Дабы наглядно объяснить, как работает «синхронизирующее слово», и придумали термин «раскраска дорог». Представим себе, например, что одна из вершин нашей сети имеет желтый цвет. Чтобы добраться до нее из любого места, достаточно следовать вдоль ребер графа, выбирая последовательность «синий-синий-красный, синий-синий-красный» и так далее. А вот последовательность «синий-красный-красный, синий-красный-красный» обязательно выведет нас из любого места сети к другой вершине.

Суть задачи можно раскрыть и так. Предположим, например, что мы попали в незнакомый город, в котором к тому же разыгралась снежная буря и не видно ни одной таблички с названиями улиц, ни одного дорожного указателя. Мы не знаем, где конкретно находимся, но должны вырулить на машине к определенному месту. Мы звоним другу, и он ободряет: «Не волнуйтесь, я буду рассказывать, куда и где свернуть». Постепенно, вслепую, следуя лишь указаниям «налево, снова налево, теперь направо», мы добираемся до цели. Так работает «синхронизирующее слово». И доказать, что его можно найти, оказалось возможным через 37 лет после того, как была поставлена задача: для крупных математических проблем не такой уж долгий срок. Решение удалось найти без компьютера, в лучших традициях - с помощью ручки и листка бумаги.

Математик решил проблему «раскраски дорог» еще в сентябре 2007 года, однако все это время рецензенты из «Израильского математического журнала» оценивали решение, проверяя, нет ли в нем ошибки. Теперь, когда известно, что примерно через месяц публикация об открытии появится в этом авторитетном научном журнале, решение задачи поместили на сайте в Интернете: каждый желающий может ознакомиться с доказательством и попытаться его опровергнуть. «Процесс верификации математического открытия - довольно сложная вещь, - признает Лев Беклемишев. - Ни один компьютер здесь не поможет. Исследовать доказательства автора приходится долго, «вживаясь» в логику его умозаключений и одновременно проверяя, все ли из них верны. Если такой солидный журнал объявил о публикации, думаю, что особых сомнений нет».

Хотя сам математик не очень хочет говорить о том, где будет применяться его открытие, подчеркивая, что занимался лишь теоретическими изысканиями, уже ясно, что решение проблемы пригодится, например, для оптимизации работы Интернета. «Что вы говорите, неужели и там сработает?» - искренне удивляется Трахтман, который признается, что об этом не думал. Однако его коллега Стюарт Марголис уверен, что именно в Интернете новое открытие найдет важное применение. «Представим себе, что где-то в Сети затерялось письмо, - объясняет Марголис. - Синхронизирующие инструкции помогут посланию, как мышке сквозь лабиринт, проследовать туда, где его ждут. Работа Авраама доказывает, что с помощью таких инструкций всегда возможно найти путь туда, куда нужно». Другой пример - решение проблемы безопасности в компьютерных программах. Например, если случилась какая-то ошибка, синхронизирующая инструкция всегда переведет систему в безопасное состояние. «Кроме того, это вообще поможет лучше узнать устройство графов как объектов», - говорит Лев Беклемишев.

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

Добавить в:  Memori  |  BobrDobr  |  Mister Wong  |  MoeMesto  |  Del.Icio.Us  |  Google Bookmarks  |  News2.ru  |  NewsLand.ru

Политика и экономика

Что почем
Те, которые...

Общество и наука

Телеграф
Культурно выражаясь
Междометия
Спецпроект

Дело

Бизнес-климат
Загранштучки

Автомобили

Новости
Честно говоря

Искусство и культура

Спорт

Парадокс

Анекдоты читателей

Анекдоты читателей
Популярное в рубрике
Яндекс цитирования NOMOBILE.RU Семь Дней НТВ+ НТВ НТВ-Кино City-FM

Copyright © Журнал "Итоги"
Эл. почта: itogi@7days.ru

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

Согласно ФЗ от 29.12.2010 №436-ФЗ сайт ITOGI.RU относится к категории информационной продукции для детей, достигших возраста шестнадцати лет.

Партнер Рамблера