Дональд Кнут: як я зайнявся аналізом алгоритмів і заради цього поїхав в СРСР (37,91,97/97)

«Андрій (Єршов), уяви, як було б здорово організувати щось на зразок паломництва, де програмісти з усього світу могли б приїхати в Хорезм і відсвяткувати народження цього поняття.»
— Дональд Кнут вмовляє Єршова організувати міжнародний симпозіум

imageБатіг і Єршов

Восени 1967 р. у Санта-Барбарі була конференція математиків, можливо, це був той рік, коли я також побував на конференції в Чапел-Хіллі. Я зустрічав багатьох людей, які стимулювали мене, і було безліч цікавих проблем, які нам варто було обговорити один з одним. Але коли я дістався до конференції в Санта-Барбарі, я зрозумів, що це мій єдиний шанс зайнятися дослідженнями. Я не відвідував лекції. Я просто сидів на березі і писав свою статтю про атрибутной граматиці під час конференції. Але я відвідував обіди. Я пам'ятаю, як хтось запитав мене, чим я займаюся, і я вирішив побути програмістом, а не математиком в той момент.

— Я думаю, що я збираюся стати програмістом.
— О, так ти займаєшся чисельним аналізом?
— Не зовсім.
— Аааа, штучний інтелект.
— Ні, і не штучний інтелект.
— Тоді повинно бути ти займаєшся мовами програмування?

Нова область — аналіз алгоритмів


Іншими словами мене в підсумку попросили написати книгу про компіляторі. Насправді в той час вважалося, що програмування складається з трьох частин: чисельний аналіз, штучний інтелект та мови програмування. Стенфордський факультет також був свого роду розділений на три основних блоку. У них були три кваліфікованих іспиту тощо. Але я сказав: «Знаєте, я проводив багато досліджень в області мов програмування, був редактором журналу з мов програмування, але мій головний інтерес трохи інший». І тоді я зрозумів, що немає назви того, що цікавить мене найбільше. І як це назвати?

До того часу я написав вже 3000 сторінок «Мистецтва програмування», надрукував частина з них і був майже готовий опублікувати їх. І виявилося, що нам потрібна була математична основа для розуміння якості комп'ютерних методів. Ви хотіли знати, наскільки хороший метод, чи він може бути в два рази краще, ніж інший і т. д. Треба було сказати не просто «так, краще», але пояснити наскільки краще і чому. Тому я вирішив зробити це основною темою, яка об'єднує мої книги, знайти способи оцінки комп'ютерних переваг. Але у мене не було для нього назви.

На конференції в Санта-Барбарі я зрозумів, що якщо я збираюся пояснювати комусь в якій сфері я працюю, у мене має бути для неї назву. Тому я вирішив назвати її аналізом алгоритмів. Я пишу книгу і я можу пояснити людям, що це означає. Я поговорив зі своїм видавцем і сказав «Давай змінимо назву книги, давай назвемо її „Аналіз алгоритмів“».

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

Одного разу мене попросили провести лекцію на міжнародному конгресі обробки інформації в 1971. Я назвав лекцію як «Аналіз алгоритмів». Мене також попросили виголосити промову на міжнародній математичній конференції у Франції в 1970 і я назвав її як «Математичний аналіз алгоритмів». Я намагався просувати цей термін, щоб люди зрозуміли, чим я займаюся. І я радий повідомити, що через 10 років або близько того, в пізніх 70-х, стали з'являтися колонки в журналах і почали виходити книги під назвою «Аналіз алгоритмів».

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

Міжнародний симпозіум по алгоритмам в СРСР



Я сказав, що я хотів, щоб аналіз алгоритмів був роботою мого життя. Велика частина моєї роботи, включаючи написання «Мистецтва програмування», полягала в тому, щоб знайти спосіб визначити наскільки хороший алгоритм. Вивчення алгоритмів мені подобалося найбільше, і завжди було для мене на першому місці.

Я був радий дізнатися, що слово «алгоритм» походить від арабського Аль-Хорезмі. Зараз Хорезм — це регіон в Узбекистані, але тоді це було озеро. Я маю на увазі Аральське море, яке раніше називалося озером Хорезмі. Це частина світу, яку зовсім забули.

image

Якщо дивитися на карту Ірану, то це місце знаходиться північніше, якщо дивитися на карту Румунії, то на схід, якщо дивитися на карту Індії або Афганістану, захід, південь Росії, розумієте? Про цю частину світу просто забули. Але я з'ясував що звідти походить слово «алгоритм», Хорезм. Знаєте, є місця, де живуть вірмени і вони називають це вірменською діаспорою? У Багдаді є цілий Хорезмский квартал. І я подумав, добре, цікаво було б відвідати Хорезм одного разу. Я подивився в атлас і жахнувся. Це ж у самому серці СРСР, як я взагалі туди доберуся?!? Немає доріг, які вели прямо до цього місця.

Я сказав про це своєму другові Андрію Єршову, який приїхав з Росії, з Радянської Академії наук. Ну, він не був моїм другом в той час, я не дуже добре його знав, але він був другом Джона Маккарті і ми були на вечірці в його будинку. Я сказав Андрію: «Ти знаєш, що слово «алгоритм» походить від місця, яке перебуває в Радянському союзі? Ми повинні це якось відзначити. Уяви, як було б здорово організувати щось на зразок паломництва, де програмісти з усього світу могли б приїхати в Хорезм і відсвяткувати народження цього поняття».

І він сказав: «Звучить, як відмінна ідея!». Він повернувся додому і почав роботу по організації всього цього. Він попросив Радянську Академію наук спонсорувати міжнародний симпозіум за алгоритмами, який би тривав два тижні і відбувався в районі Хорезму.

Ще перш ніж я добрався до Хорезму, коли я тільки вийшов з літака, мене зустрічали 200 дітей, які несли квіти, і потім у мене взяли інтерв'ю для місцевого телебачення. Це був перший випадок, коли хто-небудь виявив такий інтерес до їх земель. Гостинність людей на Середньому Сході дивно. Насправді, знаєте, господарі були настільки щедрі, що я жартома попросив їх надати мені утриманку. І я впевнений, що вони б так і зробили, якщо б я не запевнив їх, що просто жартую. Ми могли б відвідати своєрідне місто-музей Хиву, звідки творець алгоритму Аль-Хорезмі ймовірно був родом.

image

Я не впевнений, але в будь-якому випадку це свого роду зберігся місто, який показує велике надбання цієї культури. Половина людей на цій конференції були з СРСР і інша половина з різних частин світу. Ми могли просто обговорювати значимість алгоритмів. Можливість влаштувати цю невелику зустріч і побачити цей куточок світу була одним з найбільших досягнень в моєму житті.

image
Д. Батіг танцює

Дивно, але ми зустріли в цьому селищі дітей різних національностей: блондинів, блакитнооких, деяких з корейської родоводу. Ми побували на бавовняних фермах і збирали бавовну. Я отримав шапку, в яких ходять люди в Хорезмі. Так що тепер, коли я працюю над алгоритмами, я можу бути належним чином одягнутий.

image

image

Чому я вибрав аналіз алгоритмів як область досліджень



За кожною написаною роботою, а я написав їх чимало, стоїть яка-небудь цікава історія. Алгоритм сам по собі став відомим, але я сам не використовував його останні 20 років. Однак він у всіх підручниках і є повчальним прикладом.

Наприклад, він хороший у використанні, коли ти намагаєшся переглянути довгий уривок з тексту, щоб знайти певне слово. Припустимо, я шукаю слово t-he(*артикль в англійській мові) або щось на зразок того. Хоча, було б нерозумно шукати це слово, давайте шукати d-i-k-r-an(*рослина дикран).

Очевидно, ти зупиняєшся на кожному місці в тексті і запитуєш себе «буква D? Відмінно. Слідом йде літера I? Добре. Далі K? Ні, це слово 'direction'(*відстань з англ.). Тоді ти переміщаєшся далі і повторюєш цей алгоритм спочатку. Це D? Ні, ми вже з'ясували, що це I. Значить потрібно переміститися ще далі. Але все не так просто. Є більш складні слова. Якщо б ми шукали слово 'didymus'(*близнюк з англ.), де дві літери D, то наш алгоритм вже б не працював.

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

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

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

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

Раптово я знайшов зачіпку. Спочатку ідея полягала в тому, щоб написати програму, яка відображала б цю загальну теорему, але вона також могла вирішити проблему пошуку в тексті. Я згадав про це в поїздці в Берклі і зустрів там Вогана Пратта. Він був тим, хто вніс найбільший вклад, я просто був тим, хто записав це згодом.

Потім ми дізналися, що та ж сама ідея відвідала Джима Морріса парою місяців раніше, але люди подивилися на його програму, не зрозуміли її і тому не взяли. У будь-якому випадку я вважаю, що це ефективний спосіб пошуку в тексті, який також дає гарне уявлення про основи інформатики. Цей спосіб став відомим і асоціюється з моїм ім'ям.

Як я вже говорив, я написав 160 робіт і за кожною з них стоїть яка-небудь цікава історія.

Переклад: Діана Шеремьева

image
А. П. Єршов серед керівників республіканських партійних і радянських органів Узбекистану на бавовняному поле.

Єршов запрошує на симпозіум Декструimage

Тези доповіді Батога на симпозіуміimage


Стаття «Наукове паломництво на Батьківщину Аль-Хорезмі»

Передмова (написано спільно А. П. Єршовим і Д. Батогом; переклад на російську мову виконаний А. П. Єршовим.)

Стаття Дональда Кнута «Алгоритми сучасної математики та обчислювальної науки», перекладена на російську мову Р. С. Цейтиным.

Фото з симпозіумуimage
Дональд Кнут

image
Стефен Кліні

image
Андрій Єршов

image
Джилл Батіг

image

image

image

image
Батіг говорить тост

image

[источник]


Матеріали з архіву Єршова: Міжнародний симпозіум «Алгоритм у сучасній математиці і її додатках»
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.