пападимитриу и алгоритм гейтса (программистское)

[avva]

People of ACM: Christos Papadimitriou

Небольшое интересное интервью с Христосом Пападимитриу, которого я лично знаю как автора любимого учебника по теории сложности (Computational Complexity 1994 года; возможно, недавний учебник Arora & Barak презвошел его, не знаю, не читал; кстати, есть мнения на эту тему?). Еще он один из соавторов отличного учебника алгоритмов (Dasgupta, Papadimitriou, Vazirani, Algorithms), и автор популярного комикса про логику и теорию множеств (!) Logicomix.

Пападимитриу упоминает, что у него был студентом Билл Гейтс, до того, как бросил учиться, чтобы основать Майкрософт. Я не знал, что они написали вместе статью:

When I was an assistant professor at Harvard, Bill was a junior. My girlfriend back then said that I had told her: "There's this undergrad at school who is the smartest person I've ever met."

That semester, Gates was fascinated with a math problem called pancake sorting: How can you sort a list of numbers, say 3-4-2-1-5, by flipping prefixes of the list? You can flip the first two numbers to get 4-3-2-1-5, and the first four to finish it off: 1-2-3-4-5. Just two flips. But for a list of n numbers, nobody knew how to do it with fewer than 2n flips. Bill came to me with an idea for doing it with only 1.67n flips. We proved his algorithm correct, and we proved a lower bound—it cannot be done faster than 1.06n flips. We held the record in pancake sorting for decades. It was a silly problem back then, but it became important, because human chromosomes mutate this way.

Two years later, I called to tell him our paper had been accepted to a fine math journal. He sounded eminently disinterested. He had moved to Albuquerque, New Mexico to run a small company writing code for microprocessors, of all things. I remember thinking: "Such a brilliant kid. What a waste."

Вот эта статья: Gates, Papadimitriou. Bounds For Sorting By Prefix Reversal. Алгоритм Гейтса несложен для понимания и вполне остроумен.

Comments

[blacklion.livejournal.com]

Two years later, I called to tell him our paper had been accepted to a fine math journal. He sounded eminently disinterested. He had moved to Albuquerque, New Mexico to run a small company writing code for microprocessors, of all things. I remember thinking: "Such a brilliant kid. What a waste."
Вот что зацепило взгляд. Ну конечно — disinterested, 2 года прошло! Надо обладать каким-то очень особым умом, что бы такие 2 года задержки не вызывали полной атрофии интереса, нет? Или это уже я мыслю как современный человек, а тогда воспринималось нормально, всё было медленно?

[netp-npokon.livejournal.com]

По-русски все же чаще пишут "Пападимитриу".

[avva.livejournal.com]

Спасибо, сейчас исправлю.

[dimrub.livejournal.com]

Прелестная история.

[p2004r.livejournal.com]

Logicomix --- а он точно популярен?

Там внутри куча картинок (описывающих всякий идеологизированный бред на тему биографии героев) и в конце (~1/6 объема) нормальный текст собственно о рассматриваемой области с несколькими определениями и объяснениями. Если это пособие "как перестать рассматривать картинки и начать читать", то это (как принято говорить сейчас) очень "мягкое введение" :)

То есть это вовсе не комикс о теории катастроф от Иен Стюарт. Тайна катастрофы.

[avva.livejournal.com]

Он точно популярен - посмотрите на кол-во рецензий на Амазоне и сравните с другими книгами на эти темы. О содержимом не могу судить, не читал.

[kray-zemli.livejournal.com]

Однажды, с одним дедушкой, повёрнутым на математике, от нефиг делать мы вычисляли число идеалов 8-мерного куба (Проблема Дедекинда, D[8]). Вернее, его уже вычислили, мы просто повторили. Если это делать в лоб, то надо перемножить матрицы D[6]xD[6]. Мы придумали хитрый алгоритм, сводящий всё к перемножению матриц D[4]xD[5], т.е. 168x7581. Это уже можно было посчитать на P-II с 64 МБ памяти. Но так ничего и не публиковали. Даже не знаю, живой он сейчас или нет. У него с сердцем проблемы были.