Воспоминания Миякава

[1]

М. Миякава

«Давно мне хочется написать о некоторых людях, которых я встретил в жизни...»

(И. Г. Эренбург, «Люди, годы, жизнь»)

В один из последних дней 1975 года мы пригласили Андрея Петровича и Нину Михайловну на обед в свою квартиру в доме на Морском проспекте. В подарок от них я получил книгу Михаила Шолохова «Судьба человека». Действительно, оглядываясь мысленно назад, я замечаю, что многое в нашей жизни определяется именно судьбой.

Прошло 16 лет с тех пор, как не стало Андрея Петровича, а мой собственный  возраст уже на три года превосходит возраст, в котором он ушел. Мысленно накладывая годы, прожитые мной, на годы, прожитые им, я осознаю, насколько влиятельным и cозидательным человеком он был. Он умел видеть все таким, как оно есть на самом деле, и точно описывать вещи и явления языком, понятным другим людям. Он был вдумчивым человеком и оставил нам многое.

Я встречался с ним пять раз: в мае 1973 г., когда он первый раз был в Японии [2];  с октября 1975 г. по август 1977 г., когда наша семья жила в Академгородке; в августе 1979 г., когда я заехал к нему по пути в Сегед на конференцию; осенью 1980 г., во время его визита на конгресс IFIP в Токио [3]; 1—5 июля 1987 г., когда я был в  Новосибирске по пути с конференции по основам вычислительной теории в Казани. Два года в Академгородке — эти наиболее яркие страницы нашего семейного альбома — я провел в Вычислительном центре СО АН СССР у А. П. Ершова (я был шестым ученым из Японии, приехавшим на столь длительный срок; первые четверо были физиками, а затем  — археолог, приезжавший на 2 месяца). О своем пребывании там я написал статью в японском журнале [5].

Я хочу рассказать об исследованиях, которые я начал в Новосибирске, а закончил много позже уже в Японии, причем, с моей точки зрения, весьма эффектно. Я хочу поделиться своей удачей, корни которой —  в Академгородке.

В то время я занимался оптимизацией деревьев решений, которая во многих ситуациях оказывается связанной с «ветвлением». Типичный пример ее появления — задача распознавания образцов: например, имея набор проб крови, необходимо с помощью заданного набора тестов определить принадлежность каждой пробы к одной из четырех групп крови. Задача состоит в том, чтобы выбрать первый тест таким образом, чтобы классифицировать весь набор проб с помощью минимального числа тестов (такой тест можно назвать оптимальным); этим исследованием я и занимался, только вместо термина «тест» я использовал слово «переменная». Эта проблема является продолжением задачи об оптимальных деревьях двоичного поиска, над которой я успешно работал ранее, и поэтому я горел желанием решить ее. Однако задача оказалась сложной и не имеющей эффективных алгоритмов решения, найти которые я смутно надеялся. Но когда я поговорил об этой проблеме с Виктором Сабельфельдом, он показал мне, что она принадлежит классу CoNP (совместная с ним работа была моей единственной публикацией в Новосибирске). Я помню тот морозный день, когда я впервые услышал о NP-полных проблемах от Марка Трахтенброта, который обсуждал их с кем-то, стоя неподалеку от меня в длинной очереди в столовой ВЦ. До этого, еще в Японии, я уже слышал о NP-полноте, но не мог конкретно представить себе такие проблемы. Помимо этой задачи оптимизации я начал изучать схемы программ под руководством Володи Иткина. Но при решении ни одной из этих проблем я не сумел добиться ничего конкретного, и поэтому к концу своей новосибирской стажировки  не имел никаких результатов. Я вернулся к себе в Японию, в ETL (Электротехническую лабораторию), с пустыми руками. Это обстоятельство было для меня весьма болезненным и сильно подорвало мою самооценку (жаль, что совместные исследования с Володей оборвались из-за его внезапной смерти в 1991 г., так и не завершившись ни одной публикацией; точно так же я не успел ничего написать в соавторстве с Андреем Петровичем из-за его безвременной кончины в 1988 г.).

Период 1977—1983 гг., последовавший за моим возвращением, стал этапом наиболее мучительной борьбы в моей научной жизни. Однако в начале 1983 г. я сделал поразительную научную находку,  ярким светом озарившую мое пребывание в Академгородке и превратившую его в счастливое воспоминание. В рассказе о ней я обращаюсь к своему дневнику.

В то время, будучи научным сотрудником ETL, я занимался теорией замкнутых множеств (клонов) трехзначных логических функций, а также проблемой построения минимальной сети решений методом ветвей и границ. В первой задаче мне удалось перечислить все базисы трехзначных логических функций и доказать, что максимальное число функций в базисе, как ни странно, равно шести, а не семи и более, что неявно подразумевалось покойным профессором С. В. Яблонским в его работе 1954 года (этот результат стал одной из глав моей диссертации). Я смог доложить об этом результате на конференции в Сегеде в 1979 г. (там же я единственный раз встретился с проф. С. В. Яблонским и проф. Ю. И. Яновым, благодаря чему, как я думаю, я получил приглашение выступить с сообщением на конференции в Казани в 1987 г.). Об алгоритме для решения второй задачи я сделал доклад на 10-й конференции IFIP по системному моделированию и оптимизации, проходившей с 31 августа по 4 сентября 1987 г. в Нью-Йорке. Однако мне не удавалось опубликовать полученный результат в виде статьи в журнале (для публикации было недостаточно материала). В этой же поездке я посетил конференцию в Банфе, где встретился  с профессором Иво Г. Розенбергом. Сейчас, оглядываясь назад, я вижу, что в этот период что-то стоящее в моей жизни все же происходило, но тогда я оценивал свое будущее крайне пессимистично. Кроме того, в моей личной жизни произошло очень печальное событие, сильно повлиявшее на мою духовную жизнь: моя тетя, с которой я провел детство и с кем мы были очень близки, в возрасте 50 лет перенесла онкологическую операцию, и прогноз был наихудший. Поскольку я был молод и неопытен, я не мог смириться с ее судьбой. В своем дневнике 31 декабря 1981 г. я сделал запись: «В этом году я не сделал никаких успехов. Ничего не светило в моем сердце».

20—28 ноября 1982 г. я побывал у себя на родине в префектуре Кумамото, чтобы повидаться с тетей, и к несчастью сильно повредил колено. Последствия этой травмы остались у меня на всю жизнь. 5 декабря я долго разговаривал с тетей по телефону. Она говорила, что чувствует себя обессилевшей, и потому не сможет приехать в Цукубу на лечение. Остаток жизни она предпочла провести с семьей: у нее была единственная, очень поздняя, дочь (тогда десятилетняя). 1 января 1983 г. мне исполнилось 40 лет, и мне пришлось признать, что я уже много прожил. Я писал: «Мне хотелось бы работать с интересом; только это и останется в моей будущей жизни». Слабые успехи в профессиональной жизни постоянно меня угнетали, и я перестал испытывать удовольствие от повседневной жизни. Состояние травмированного колена ухудшилось до такой степени, что я едва мог ходить; мне приходилось постоянно консультироваться с врачами. Тосико лежала в университетской больнице с угрозой выкидыша. Одним словом, я достиг самого дна своей физической, социальной и профессиональной жизни. И в этой ситуации внезапно пришла моя находка. Я должен был написать заключительный отчет по сетям решений, чтобы, наконец, распрощаться с этой «проклятой» проблемой, да и со всей своей профессиональной карьерой. Я был в тупике и в отчаянии. 11 февраля (в день нашего национального праздника) я писал в дневнике: «Я не могу получить новых результатов в оптимизации деревьев решений», а 12 февраля  (в субботу) я написал:  «Непонятно, оптимально ли разбиение с односторонним постоянством, или нет». Впервые я обратил внимание на идею разбиения таблицы решений тестом, имеющим результатом одностороннее постоянство (я назвал такой тест «полурешающим»). Возможно,  я пришел к этому, думая о подходах динамического программирования. 13 февраля я написал что-то о словах Гегеля по поводу «оригинальности», ссылаясь на стр. 285 в книге профессора Гурия Ивановича Марчука. 15 февраля (в четверг), навестив в больнице жену, с 21:00 до 1:00 я размышлял о том, «является ли одностороннее постоянство оптимальным». 16 февраля (в среду) была прекрасная погода, но поздно вечером начался дождь. Я проработал в лаборатории 11 часов  — с 12:00 до 17:00 и с 21:30 до 3:30 (в дневнике нет записи о том, что я делал в промежутке; скорее всего, я был у жены в больнице). Затем я записал: «Я смог доказать, что разбиение с односторонним постоянством является достаточным условием оптимальности переменной. Удачный день! Сколько же лет прошло с 1975 г.?» 17 февраля (в четверг) шел дождь. Вернувшись из больницы от жены, я проработал до 0:00. Я писал: «Сегодня я послал поздравительное письмо с 8 Марта в Новосибирск».

Результат был опубликован в 1985 г. [6]. В один из декабрьских вечеров 1985 г. я поднялся на восьмой этаж Электротехнической лаборатории в библиотеку, чтобы посмотреть на свою статью (ко мне тогда приехал Иван Стойменович, и он предложил мне самому сходить и проверить). Читая длинный список новосибирских коллег, которым я выражал благодарность в статье, я понял, что моя стажировка в Новосибирске наконец закончена — через 10 лет после того, как я последний раз ступал по сибирской земле. Доказанная мной теорема почти тривиальна. На доказательство ее потребовалось всего несколько дней. Вскоре острая радость открытия (я кричал в комнате!) сменилась в моей душе чувством глубокого разочарования и печали: почему я не увидел этого еще в 1975? Что это были за годы борьбы и отчаяния? Я одновременно был зол на себя и жалел себя. Глупость! Глупо посвящать столько лет одной-единственной проблеме. Но с другой стороны, я верил и верю до сих пор, что в пережитой мною ситуации наряду с моим упрямством присутствует и некая эпистемологическая составляющая. В конце концов, я спокойно примирился с этими годами. Я рад и благодарен, что сумел получить результат. Я пришел к выводу, что это был дар небес, наблюдавших за мной все эти годы отчаянья и борьбы. Несмотря на простоту теоремы (я даже не исключал возможности, что это может быть известный результат, где-то и кем-то уже опубликованный; мне оставалось ждать отзыва рецензента, подтверждающего его оригинальность), я считаю ее одним из основных правил, определяющих оптимальное разбиение таблиц решений. На самом деле мне кажется, что в моей работе говорится, хоть и неявно, что процесс построения оптимальных деревьев решений не имеет распознаваемой структуры, и поэтому неизбежен перебор всех деревьев решений для получения оптимального. В явном виде теплые слова по поводу моего открытия я услышал от двух человек: одним был Андрей Петрович, специально приславший мне открытку из Новосибирска (3 апреля 1986 г.), а другим — ныне покойный профессор Осаму Ишии, директор отделения, в котором я работал, — чтобы поздравить, он пригласил меня в свой кабинет.

Эпилог. Мое пребывание в Новосибирске становится историей — так же, как и мои теплые воспоминания об Андрее Петровиче. Глядя на развитие вычислительных наук, а в особенности — на Интернет, появившийся на моих глазах, я понимаю, что становлюсь старым и несовременным. Я чувствую себя, как мог бы чувствовать себя Кодаю —  потерпевший крушение рыбак, проведший 10 лет (1782—1792) в Сибири до своего возвращения в Японию (роман [1] написал известный японский прозаик Ясуси Иноуэ; русский перевод мне подарила Оля Очаковская). Некоторых людей уже нет, включая Андрея Петровича и Игоря Васильевича. Я испытываю чувства, подобные тем, что описал сам Андрей в последнем абзаце [4]:

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

Тем не менее, наша жизнь продолжается. Нас окружают молодые люди. Узнав, что Таня Бульонкова, которую я видел в 1987 г. четырехлетним ребенком, переводит статью, которую я написал о ее деде [7], я почувствовал, что узы судьбы, связывающие меня с Новосибирском, все еще не порваны. [Я уверен, что довольно многие люди имели опыт находки после долгой борьбы, подобный моему. Моя тетя Митико Киндзе, которой я посвятил теорему, скончалась 19 июля 1983 г.; 1 сентября 1983 г. у меня родился сын; 7 сентября 1984 г. и 17 января 1991 г. мне оперировали колено.]

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

Список литературы

1. Y. Inoue, «Dreams about Russia (Snui o Rosii)», Bungeisyunjyusya Pub., Tokyo, 1968.
2. A. P. Ershov, S. Igarshi, T. Shimauti, S. Takasu, E. Wada, «Topics in Current Soviet Computer Science», a record of the round-table talks held on May 16, 1973 at Kyoto, Bit, 1973, Vol. 5, N 9,  P. 1022—1029.
3. A. P. Ershov, «On Futamura’s projections», Bit, 1980, Vol. 12, N 14, P. 1852—1853.
4. A. P. Ershov, «Opening Key-Note Speech» (the workshop on mixed computation held by IFIP TC2 in Denmark, October 18—24, 1987), New Generation Computing, 6 (1988) 79—86, Ohmsha Pub. and Springer-Verlag; Japanese translation: «My view on scientific researches — on partial evaluation and mixed computation», Bit, 1989,
   Vol. 21, N 12, P. 1586—1591.
5. M. Miyakawa, «A stay in Siberian Akademgorodok», Bit, 1978, Vol. 10, N 6, P. 698—704.
6. M. Miyakawa, «Optimum decision trees — An optimal variable theorem and its related applications», Acta Informatica, 1985, 22, 475—498.
7. M. Miyakawa, «A memory of Professor Ershov», Bit, 1989, Vol. 21, N 12, P. 1592—1593.

Примечание

[1] Эта часть воспоминаний написана специально для настоящего издания.

18 октября 2004. Цукуба.
Из сборника «Андрей Петрович Ершов — ученый и человек». Новосибирск, 2006 г.
Перепечатываются с разрешения редакции.