«Андрей (Ершов), представь, как было бы здорово организовать что-то вроде паломничества, где программисты со всего мира могли бы приехать в Хорезм и отпраздновать рождение этого понятия.»
— Дональд Кнут уговаривает Ершова организовать международный симпозиум
Кнут и Ершов
Осенью 1967 в Санта-Барбаре была конференция математиков, возможно, это был тот же год, когда я также побывал на конференции в Чапел-Хилле. Я встречал многих людей, которые стимулировали меня, и было множество интересных проблем, которые нам стоило обсудить друг с другом. Но когда я добрался до конференции в Санта-Барбаре, я понял, что это мой единственный шанс заняться исследованиями. Я не посещал лекции. Я просто сидел на берегу и писал свою статью об атрибутной грамматике прямо во время конференции. Но я посещал обеды. Я помню, как кто-то спросил меня, чем я занимаюсь и я решил побыть программистом, а не математиком в тот момент.
— Я думаю, я собираюсь стать программистом.
— О, так ты занимаешься численным анализом?
— Не совсем.
— Аааа, искусственный интеллект.
— Нет, и не искусственный интеллект.
— Тогда должно быть ты занимаешься языками программирования?
Другими словами меня в итоге попросили написать книгу о компиляторе. На самом деле в то время считалось, что программирование состоит из трех частей: численный анализ, искусственный интеллект и языки программирования. Стэндфордский факультет также был своего рода разделен на три основных блока. У них были три квалифицированных экзамена и тому подобное. Но я сказал «Знаете, я проводил много исследований в области языков программирования, был редактором журнала по языкам программирования, но мой главный интерес немного другой». И тогда я понял, что нет названия тому, что интересует меня больше всего. И как это назвать?
К тому времени я написал уже 3000 страниц «Искусства программирования», напечатал часть из них и был почти готов опубликовать их. И оказалось, что нам нужна была математическая основа для понимания качества компьютерных методов. Вы хотели знать, насколько хорош метод, может ли он быть в два раза лучше, чем другой и т.д. Нужно было сказать не просто «да, лучше», но объяснить насколько лучше и почему. Поэтому я решил сделать это основной темой, объединяющей мои книги, найти способы оценки компьютерных достоинств. Но у меня не было для него названия.
На конференции в Санта-Барбаре я понял, что если я собираюсь объяснять кому-то в какой сфере я работаю, у меня должно быть для нее название. Поэтому я решил назвать её анализом алгоритмов. Я пишу книгу и я могу объяснить людям, что это значит. Я поговорил со своим издателем и сказал «Давай изменим название книги, давай назовем ее “Анализ алгоритмов”».
Эту идею не одобрили, но я в любом случае решил, что это будет моей карьерой, что я сосредоточусь в основном на анализе алгоритмов. Это значит, что я буду определять насколько хорош тот или иной алгоритм или компьютерный метод.
Однажды меня попросили провести лекцию на международном конгрессе обработки информации в 1971. Я озаглавил лекцию как «Анализ алгоритмов». Меня также попросили произнести речь на международной математической конференции во Франции в 1970 и я озаглавил ее как «Математический анализ алгоритмов». Я пытался продвигать этот термин, чтобы люди поняли, чем я занимаюсь. И я рад сообщить, что спустя 10 лет или около того, в поздних 70-ых, стали появляться колонки в журналах и начали выходить книги под названием «Анализ алгоритмов».
На самом деле, несмотря на то, что моим издателям не нравилось это название, довольно немногие книги имеют подобный заголовок. Но мне нужно было как-то назвать область, в которой я работаю. Если бы кто-то попросил меня объяснить, что это на самом деле значит, я бы сказал, что это просто то, чем я интересуюсь.
Я сказал, что я хотел, чтобы анализ алгоритмов был работой моей жизни. Большая часть моей работы, включая написание «Искусства программирования», заключалась в том, чтобы найти способ определить насколько хорош алгоритм. Изучение алгоритмов нравилось мне больше всего, и всегда было для меня на первом месте.
Я был рад узнать, что слово «алгоритм» произошло от арабского Аль-Хорезми. Сейчас Хорезм — это регион в Узбекистане, но тогда это было озеро. Я имею в виду Аральское море, которое раньше называлось озером Хорезми. Это часть мира, которую совершенно забыли.
Если смотреть на карту Ирана, то это место находится севернее, если смотреть на карту Румынии, то восточнее, если смотреть на карту Индии или Афганистана, то западнее, юг России, понимаете? Про эту часть мира просто забыли. Но я выяснил что оттуда произошло слово «алгоритм», Хорезм. Знаете, есть места, где живут армяне и они называют это армянской диаспорой? В Багдаде есть целый Хорезмский квартал. И я подумал, ладно, было бы интересно посетить Хорезм однажды. Я посмотрел в атлас и ужаснулся. Это же в самом сердце СССР, как я вообще туда доберусь?!? Нет дорог, которые вели бы прямо к этому месту.
Я сказал об этом своему другу Андрею Ершову, который приехал из России, из Советской Академии наук. Ну, он не был моим другом в то время, я не очень хорошо его знал, но он был другом Джона Маккарти и мы были на вечеринке в его доме. Я сказал Андрею: «Ты знаешь, что слово «алгоритм» произошло от места, которое находится в Советском союзе? Мы должны это как-нибудь отметить. Представь, как было бы здорово организовать что-то вроде паломничества, где программисты со всего мира могли бы приехать в Хорезм и отпраздновать рождение этого понятия».
И он сказал: «Звучит, как отличная идея!». Он вернулся домой и начал работу по организации всего этого. Он попросил Советскую Академию наук спонсировать международный симпозиум по алгоритмам, который бы длился две недели и проходил бы в районе Хорезма.
Еще прежде чем я добрался до Хорезма, когда я только вышел с самолета, меня встречали 200 детей, которые несли цветы, и затем у меня взяли интервью для местного телевидения. Это был первый случай, когда кто-либо проявил такой интерес к их землям. Гостеприимство людей на Среднем Востоке удивительно. На самом деле, знаете, хозяева были настолько щедрые, что я в шутку попросил их предоставить мне содержанку. И я уверен, что они бы так и сделали, если бы я не заверил их, что просто шучу. Мы могли бы посетить своеобразный город-музей Хиву, откуда создатель алгоритма Аль-Хорезми вероятно был родом.
Я не уверен, но в любом случае это своего рода сохранившийся город, который показывает великое достояние этой культуры. Половина людей на этой конференции были из СССР и другая половина с разных частей света. Мы могли просто обсуждать значимость алгоритмов. Возможность устроить эту небольшую встречу и увидеть этот уголок мира была одним из величайших достижений в моей жизни.
Д. Кнут танцует
Удивительно, но мы встретили в этом поселке детей разных национальностей: блондинов, голубоглазых, некоторых с корейской родословной. Мы побывали на хлопковых фермах и собирали хлопок. Я получил шапку, в которых ходят люди в Хорезме. Так что теперь, когда я работаю над алгоритмами, я могу быть подобающе одет.
За каждой написанной работой, а я написал их немало, стоит какая-нибудь интересная история. Алгоритм сам по себе стал известным, но я сам не использовал его последние 20 лет. Однако он во всех учебниках и является поучительным примером.
Например он хорош в использовании, когда ты пытаешься просмотреть длинный отрывок из текста, чтобы найти определенное слово. Предположим, я ищу слово t-h-e(*артикль в английском языке) или что-то вроде того. Хотя, было бы глупо искать это слово, давайте искать d-i-k-r-a-n(*растение дикран).
Очевидно, ты останавливаешься на каждом месте в тексте и спрашиваешь себя «Это буква D? Отлично. Следом идет буква I? Хорошо. Дальше K? Нет, это слово 'direction'(*расстояние с англ.). Тогда ты перемещаешься дальше и повторяешь этот алгоритм сначала. Это D? Нет, мы уже выяснили, что это I. Значит нужно переместиться еще дальше. Но все не так просто. Есть более сложные слова. Если бы мы искали слово 'didymus'(*близнец с англ.), где две буквы D, то наш алгоритм уже бы не работал.
У профессора в Беркли, Стива Кука, есть удивительная теорема на этот счет. Он утверждает, что если бы мы взяли некий очень ограниченный по своим возможностям компьютер и если мы могли бы написать программу, которая решала бы проблему, для этого тупого компьютера вне зависимости от того насколько медленно работала бы эта программа, значит существует быстрый способ написать эту же программу для нормального компьютера.
Другими словами мы берем определенный компьютер с ограниченными возможностями и если на нем можно решить проблему, то существует быстрый способ сделать это на нормальном компьютере. Единственная проблема, которую стоило бы решить с этим компьютером, это возможность определить является ли набор букв палиндромом и провернуть то же самое в цепочке палиндромов.
Мне было просто любопытно. На самом деле никого не интересует конкатенация палиндромов. Согласно теореме Кука, если существует способ решить эту проблему на этом забавном компьютере, то существует и быстрый способ распознать эти связи палиндромов на обычном компьютере. Но я не мог придумать какой-нибудь хороший способ сделать это на нормальном компьютере, мне казалось, что это будет гораздо сложнее.
Я был довольно хорошим программистом, но вот эта теорема утверждала, что есть способ сделать это, а я не мог придумать как. Я впервые был в такой своего рода тупиковой ситуации и не мог перестать думать об этом. Я потратил день и вечер, чтобы подробно расписать на доске теорию Кука и найти, наконец, быстрый способ воплотить это в жизнь на компьютере.
Внезапно я нашел зацепку. Изначально идея заключалась в том, чтобы написать программу, которая отражала бы эту общую теорему, но она также могла решить проблему поиска в тексте. Я упомянул об этом в поездке в Беркли и встретил там Вогана Пратта. Он был тем, кто внес самый больший вклад, я просто был тем, кто записал это впоследствии.
Потом мы узнали, что та же самая идея посетила Джима Морриса парой месяцев раннее, но люди посмотрели на его программу, не поняли её и поэтому не взяли. В любом случае я считаю, что это эффективный способ поиска в тексте, который также дает хорошее представление об основах информатики. Этот способ стал известным и ассоциируется с моим именем.
Как я уже говорил, я написал 160 работ и за каждой из них стоит какая-нибудь интересная история.
Перевод: Диана Шеремьёва
А. П. Ершов среди руководителей республиканских партийных и советских органов Узбекистана на хлопковом поле.
Статья «Научное паломничество на Родину Аль-Хорезми»
Предисловие (написано совместно А.П. Ершовым и Д. Кнутом; перевод на русский язык выполнен А.П. Ершовым.)
Статья Дональда Кнута «Алгоритмы в современной математике и вычислительной науке», переведенная на русский язык Г.С. Цейтиным.
Материалы из архива Ершова: Международный симпозиум «Алгоритм в современной математике и ее приложениях»
— Дональд Кнут уговаривает Ершова организовать международный симпозиум
Осенью 1967 в Санта-Барбаре была конференция математиков, возможно, это был тот же год, когда я также побывал на конференции в Чапел-Хилле. Я встречал многих людей, которые стимулировали меня, и было множество интересных проблем, которые нам стоило обсудить друг с другом. Но когда я добрался до конференции в Санта-Барбаре, я понял, что это мой единственный шанс заняться исследованиями. Я не посещал лекции. Я просто сидел на берегу и писал свою статью об атрибутной грамматике прямо во время конференции. Но я посещал обеды. Я помню, как кто-то спросил меня, чем я занимаюсь и я решил побыть программистом, а не математиком в тот момент.
— Я думаю, я собираюсь стать программистом.
— О, так ты занимаешься численным анализом?
— Не совсем.
— Аааа, искусственный интеллект.
— Нет, и не искусственный интеллект.
— Тогда должно быть ты занимаешься языками программирования?
Коротко рассказываем о гибкой методологии разработки программного обеспечения (Agile), которую мы используем на проектах в EDISON Software Development Centre.
Новая область — анализ алгоритмов
Другими словами меня в итоге попросили написать книгу о компиляторе. На самом деле в то время считалось, что программирование состоит из трех частей: численный анализ, искусственный интеллект и языки программирования. Стэндфордский факультет также был своего рода разделен на три основных блока. У них были три квалифицированных экзамена и тому подобное. Но я сказал «Знаете, я проводил много исследований в области языков программирования, был редактором журнала по языкам программирования, но мой главный интерес немного другой». И тогда я понял, что нет названия тому, что интересует меня больше всего. И как это назвать?
К тому времени я написал уже 3000 страниц «Искусства программирования», напечатал часть из них и был почти готов опубликовать их. И оказалось, что нам нужна была математическая основа для понимания качества компьютерных методов. Вы хотели знать, насколько хорош метод, может ли он быть в два раза лучше, чем другой и т.д. Нужно было сказать не просто «да, лучше», но объяснить насколько лучше и почему. Поэтому я решил сделать это основной темой, объединяющей мои книги, найти способы оценки компьютерных достоинств. Но у меня не было для него названия.
На конференции в Санта-Барбаре я понял, что если я собираюсь объяснять кому-то в какой сфере я работаю, у меня должно быть для нее название. Поэтому я решил назвать её анализом алгоритмов. Я пишу книгу и я могу объяснить людям, что это значит. Я поговорил со своим издателем и сказал «Давай изменим название книги, давай назовем ее “Анализ алгоритмов”».
Эту идею не одобрили, но я в любом случае решил, что это будет моей карьерой, что я сосредоточусь в основном на анализе алгоритмов. Это значит, что я буду определять насколько хорош тот или иной алгоритм или компьютерный метод.
Однажды меня попросили провести лекцию на международном конгрессе обработки информации в 1971. Я озаглавил лекцию как «Анализ алгоритмов». Меня также попросили произнести речь на международной математической конференции во Франции в 1970 и я озаглавил ее как «Математический анализ алгоритмов». Я пытался продвигать этот термин, чтобы люди поняли, чем я занимаюсь. И я рад сообщить, что спустя 10 лет или около того, в поздних 70-ых, стали появляться колонки в журналах и начали выходить книги под названием «Анализ алгоритмов».
На самом деле, несмотря на то, что моим издателям не нравилось это название, довольно немногие книги имеют подобный заголовок. Но мне нужно было как-то назвать область, в которой я работаю. Если бы кто-то попросил меня объяснить, что это на самом деле значит, я бы сказал, что это просто то, чем я интересуюсь.
Международный симпозиум по алгоритмам в СССР
Я сказал, что я хотел, чтобы анализ алгоритмов был работой моей жизни. Большая часть моей работы, включая написание «Искусства программирования», заключалась в том, чтобы найти способ определить насколько хорош алгоритм. Изучение алгоритмов нравилось мне больше всего, и всегда было для меня на первом месте.
Я был рад узнать, что слово «алгоритм» произошло от арабского Аль-Хорезми. Сейчас Хорезм — это регион в Узбекистане, но тогда это было озеро. Я имею в виду Аральское море, которое раньше называлось озером Хорезми. Это часть мира, которую совершенно забыли.
Если смотреть на карту Ирана, то это место находится севернее, если смотреть на карту Румынии, то восточнее, если смотреть на карту Индии или Афганистана, то западнее, юг России, понимаете? Про эту часть мира просто забыли. Но я выяснил что оттуда произошло слово «алгоритм», Хорезм. Знаете, есть места, где живут армяне и они называют это армянской диаспорой? В Багдаде есть целый Хорезмский квартал. И я подумал, ладно, было бы интересно посетить Хорезм однажды. Я посмотрел в атлас и ужаснулся. Это же в самом сердце СССР, как я вообще туда доберусь?!? Нет дорог, которые вели бы прямо к этому месту.
Я сказал об этом своему другу Андрею Ершову, который приехал из России, из Советской Академии наук. Ну, он не был моим другом в то время, я не очень хорошо его знал, но он был другом Джона Маккарти и мы были на вечеринке в его доме. Я сказал Андрею: «Ты знаешь, что слово «алгоритм» произошло от места, которое находится в Советском союзе? Мы должны это как-нибудь отметить. Представь, как было бы здорово организовать что-то вроде паломничества, где программисты со всего мира могли бы приехать в Хорезм и отпраздновать рождение этого понятия».
И он сказал: «Звучит, как отличная идея!». Он вернулся домой и начал работу по организации всего этого. Он попросил Советскую Академию наук спонсировать международный симпозиум по алгоритмам, который бы длился две недели и проходил бы в районе Хорезма.
Еще прежде чем я добрался до Хорезма, когда я только вышел с самолета, меня встречали 200 детей, которые несли цветы, и затем у меня взяли интервью для местного телевидения. Это был первый случай, когда кто-либо проявил такой интерес к их землям. Гостеприимство людей на Среднем Востоке удивительно. На самом деле, знаете, хозяева были настолько щедрые, что я в шутку попросил их предоставить мне содержанку. И я уверен, что они бы так и сделали, если бы я не заверил их, что просто шучу. Мы могли бы посетить своеобразный город-музей Хиву, откуда создатель алгоритма Аль-Хорезми вероятно был родом.
Я не уверен, но в любом случае это своего рода сохранившийся город, который показывает великое достояние этой культуры. Половина людей на этой конференции были из СССР и другая половина с разных частей света. Мы могли просто обсуждать значимость алгоритмов. Возможность устроить эту небольшую встречу и увидеть этот уголок мира была одним из величайших достижений в моей жизни.
Д. Кнут танцует
Удивительно, но мы встретили в этом поселке детей разных национальностей: блондинов, голубоглазых, некоторых с корейской родословной. Мы побывали на хлопковых фермах и собирали хлопок. Я получил шапку, в которых ходят люди в Хорезме. Так что теперь, когда я работаю над алгоритмами, я могу быть подобающе одет.
Почему я выбрал анализ алгоритмов как область исследований
За каждой написанной работой, а я написал их немало, стоит какая-нибудь интересная история. Алгоритм сам по себе стал известным, но я сам не использовал его последние 20 лет. Однако он во всех учебниках и является поучительным примером.
Например он хорош в использовании, когда ты пытаешься просмотреть длинный отрывок из текста, чтобы найти определенное слово. Предположим, я ищу слово t-h-e(*артикль в английском языке) или что-то вроде того. Хотя, было бы глупо искать это слово, давайте искать d-i-k-r-a-n(*растение дикран).
Очевидно, ты останавливаешься на каждом месте в тексте и спрашиваешь себя «Это буква D? Отлично. Следом идет буква I? Хорошо. Дальше K? Нет, это слово 'direction'(*расстояние с англ.). Тогда ты перемещаешься дальше и повторяешь этот алгоритм сначала. Это D? Нет, мы уже выяснили, что это I. Значит нужно переместиться еще дальше. Но все не так просто. Есть более сложные слова. Если бы мы искали слово 'didymus'(*близнец с англ.), где две буквы D, то наш алгоритм уже бы не работал.
У профессора в Беркли, Стива Кука, есть удивительная теорема на этот счет. Он утверждает, что если бы мы взяли некий очень ограниченный по своим возможностям компьютер и если мы могли бы написать программу, которая решала бы проблему, для этого тупого компьютера вне зависимости от того насколько медленно работала бы эта программа, значит существует быстрый способ написать эту же программу для нормального компьютера.
Другими словами мы берем определенный компьютер с ограниченными возможностями и если на нем можно решить проблему, то существует быстрый способ сделать это на нормальном компьютере. Единственная проблема, которую стоило бы решить с этим компьютером, это возможность определить является ли набор букв палиндромом и провернуть то же самое в цепочке палиндромов.
Мне было просто любопытно. На самом деле никого не интересует конкатенация палиндромов. Согласно теореме Кука, если существует способ решить эту проблему на этом забавном компьютере, то существует и быстрый способ распознать эти связи палиндромов на обычном компьютере. Но я не мог придумать какой-нибудь хороший способ сделать это на нормальном компьютере, мне казалось, что это будет гораздо сложнее.
Я был довольно хорошим программистом, но вот эта теорема утверждала, что есть способ сделать это, а я не мог придумать как. Я впервые был в такой своего рода тупиковой ситуации и не мог перестать думать об этом. Я потратил день и вечер, чтобы подробно расписать на доске теорию Кука и найти, наконец, быстрый способ воплотить это в жизнь на компьютере.
Внезапно я нашел зацепку. Изначально идея заключалась в том, чтобы написать программу, которая отражала бы эту общую теорему, но она также могла решить проблему поиска в тексте. Я упомянул об этом в поездке в Беркли и встретил там Вогана Пратта. Он был тем, кто внес самый больший вклад, я просто был тем, кто записал это впоследствии.
Потом мы узнали, что та же самая идея посетила Джима Морриса парой месяцев раннее, но люди посмотрели на его программу, не поняли её и поэтому не взяли. В любом случае я считаю, что это эффективный способ поиска в тексте, который также дает хорошее представление об основах информатики. Этот способ стал известным и ассоциируется с моим именем.
Как я уже говорил, я написал 160 работ и за каждой из них стоит какая-нибудь интересная история.
Перевод: Диана Шеремьёва
А. П. Ершов среди руководителей республиканских партийных и советских органов Узбекистана на хлопковом поле.
Ершов приглашает на симпозиум Дейкстру
Тезисы доклада Кнута на симпозиуме
Статья «Научное паломничество на Родину Аль-Хорезми»
Предисловие (написано совместно А.П. Ершовым и Д. Кнутом; перевод на русский язык выполнен А.П. Ершовым.)
Статья Дональда Кнута «Алгоритмы в современной математике и вычислительной науке», переведенная на русский язык Г.С. Цейтиным.
Фото с симпозиума
Материалы из архива Ершова: Международный симпозиум «Алгоритм в современной математике и ее приложениях»
Читать еще
- Дональд Кнут: Я сидел на задних партах и травил шутки, а учителя смирились и не часто били по заднице (1,2,3,7/97)
- Дональд Кнут: «Мой совет молодым» (93/97) и «Ощущая потребность самоутвердиться» (9/97)
- «Сюрреальные числа»: Я творил шесть дней, а на седьмой отдыхал (40,41,42/97)
- Дональд Кнут: Как создавалось «Искусство программирования» (33,38,39/97)
- Социальная Архитектура: стратагемы для успеха open source проектов
Список 97 видеороликов с историями Дональда Кнута
Плейлист на Youtube
1. Family history
2. Learning to read and school
3. My mother
4. My parents' finances
5. Interests in high school
6. Being a nerd of nerds at high school
7. My sense of humor
8. The Potrzebie System of Weights and Measures
9. Feeling the need to prove myself
11. University life: my basketball management system
12. University life: the fraternity system
13. Meeting my wife Jill
14. Bible study at university and a time of personal challenge
15. Extra-curricular activities at Case
16. Taking graduate classes at Case
17. Physics, welding, astronomy and mathematics
18. My maths teacher at Case and a difficult problem
19. My interest in graphs and my first experience of a computer
20. How I got interested in programming
21. Learning how to program on the IBM 650
22. Writing a tic-tac-toe program
23. Learning about Symbolic Optimum Assembly programs
24. The Internal Translator
25. Adding more features to RUNCIBLE
26. Wanting to be a teacher and why I chose to go to Caltech
27. Writing a compiler for the Burroughs Corporation
28. Working for the Burroughs Corporation
29. Burroughs Corporation
30. My interest in context-free languages
31. Getting my PhD and the problem of symmetric block designs with…
32. Finding a solution to an open problem about projective planes
33. Inception of The Art of Computer Programming
34. 1967: a turbulent year
35. Work on attribute grammars and the Knuth-Bendix Algorithm
36. Being creative in the forest
37. A new field: analysis of algorithms
38. The Art of Computer Programming: underestimating the size of the...
39. The successful first release of The Art of Computer Programming
40. Inspiration to write Surreal Numbers
41. Writing Surreal Numbers in a hotel room in Oslo
42. Finishing the Surreal Numbers
43. The emergence of computer science as an academic subject
44. I want to do computer science instead of arguing for it
45. A year doing National Service in Princeton
46. Moving to Stanford and wondering whether I'd made the right choice
47. Designing the house in Stanford
48. Volume Three of The Art of Computer Programming
49. Working on Volume Four of The Art of Computer Programming
50. Poor quality typesetting on the second edition of my book
51. Deciding to make my own typesetting program
52. Working on my typesetting program
53. Mathematical formula for letter shapes
54. Research into the history of typography
55. Working on my letters and problems with the S
56. Figuring out how to typeset and the problem with specifications
57. Working on TeX
58. Why the designer and the implementer of a program should be the…
59. Converting Volume Two to TeX
60. Writing a users' manual for TeX
61. Giving the Gibbs lecture on my typography work
62. Developing Metafont and TeX
63. Why I chose not to retain any rights to TeX and transcribed it to…
64. Tuning up my fonts and getting funding for TeX
65. Problems with Volume Two
66. Literate programming
67. Re-writing TeX using the feedback I received
68. The importance of stability for TeX
69. LaTeX and ConTeXt
70. A summary of the TeX project
71. A year in Boston
72. Writing a book about the Bible
73. The most beautiful 3:16 in the world
74. Chess master playing at Adobe Systems
75. Giving a lecture series on science and religion at MIT
76. Back to work at Stanford and taking early retirement
77. Taking up swimming to help me cope with stress
78. My graduate students and my 64th birthday
79. My class on Concrete Mathematics
80. Writing a book on my Concrete Mathematics class
81. Updating Volumes One to Three of The Art of Computer Programming
82. Getting started on Volume Four of «The Art of Computer…
83. Two final major research projects
84. My love of writing and a lucky life
85. Coping with cancer
86. Honorary doctorates
87. The importance of awards and the Kyoto Prize
88. Pipe organ music is one of the great pleasures of life
89. The pipe organ in my living room
90. Playing the organs
91. An international symposium on algorithms in the Soviet Union
92. The Knuth-Morris-Pratt algorithm
93. My advice to young people
94. My children: John
95. My children: Jenny
96. Working on a series of books of my collected papers
97. Why I chose analysis of algorithms as a subject
1. Family history
2. Learning to read and school
3. My mother
4. My parents' finances
5. Interests in high school
6. Being a nerd of nerds at high school
7. My sense of humor
8. The Potrzebie System of Weights and Measures
9. Feeling the need to prove myself
11. University life: my basketball management system
12. University life: the fraternity system
13. Meeting my wife Jill
14. Bible study at university and a time of personal challenge
15. Extra-curricular activities at Case
16. Taking graduate classes at Case
17. Physics, welding, astronomy and mathematics
18. My maths teacher at Case and a difficult problem
19. My interest in graphs and my first experience of a computer
20. How I got interested in programming
21. Learning how to program on the IBM 650
22. Writing a tic-tac-toe program
23. Learning about Symbolic Optimum Assembly programs
24. The Internal Translator
25. Adding more features to RUNCIBLE
26. Wanting to be a teacher and why I chose to go to Caltech
27. Writing a compiler for the Burroughs Corporation
28. Working for the Burroughs Corporation
29. Burroughs Corporation
30. My interest in context-free languages
31. Getting my PhD and the problem of symmetric block designs with…
32. Finding a solution to an open problem about projective planes
33. Inception of The Art of Computer Programming
34. 1967: a turbulent year
35. Work on attribute grammars and the Knuth-Bendix Algorithm
36. Being creative in the forest
37. A new field: analysis of algorithms
38. The Art of Computer Programming: underestimating the size of the...
39. The successful first release of The Art of Computer Programming
40. Inspiration to write Surreal Numbers
41. Writing Surreal Numbers in a hotel room in Oslo
42. Finishing the Surreal Numbers
43. The emergence of computer science as an academic subject
44. I want to do computer science instead of arguing for it
45. A year doing National Service in Princeton
46. Moving to Stanford and wondering whether I'd made the right choice
47. Designing the house in Stanford
48. Volume Three of The Art of Computer Programming
49. Working on Volume Four of The Art of Computer Programming
50. Poor quality typesetting on the second edition of my book
51. Deciding to make my own typesetting program
52. Working on my typesetting program
53. Mathematical formula for letter shapes
54. Research into the history of typography
55. Working on my letters and problems with the S
56. Figuring out how to typeset and the problem with specifications
57. Working on TeX
58. Why the designer and the implementer of a program should be the…
59. Converting Volume Two to TeX
60. Writing a users' manual for TeX
61. Giving the Gibbs lecture on my typography work
62. Developing Metafont and TeX
63. Why I chose not to retain any rights to TeX and transcribed it to…
64. Tuning up my fonts and getting funding for TeX
65. Problems with Volume Two
66. Literate programming
67. Re-writing TeX using the feedback I received
68. The importance of stability for TeX
69. LaTeX and ConTeXt
70. A summary of the TeX project
71. A year in Boston
72. Writing a book about the Bible
73. The most beautiful 3:16 in the world
74. Chess master playing at Adobe Systems
75. Giving a lecture series on science and religion at MIT
76. Back to work at Stanford and taking early retirement
77. Taking up swimming to help me cope with stress
78. My graduate students and my 64th birthday
79. My class on Concrete Mathematics
80. Writing a book on my Concrete Mathematics class
81. Updating Volumes One to Three of The Art of Computer Programming
82. Getting started on Volume Four of «The Art of Computer…
83. Two final major research projects
84. My love of writing and a lucky life
85. Coping with cancer
86. Honorary doctorates
87. The importance of awards and the Kyoto Prize
88. Pipe organ music is one of the great pleasures of life
89. The pipe organ in my living room
90. Playing the organs
91. An international symposium on algorithms in the Soviet Union
92. The Knuth-Morris-Pratt algorithm
93. My advice to young people
94. My children: John
95. My children: Jenny
96. Working on a series of books of my collected papers
97. Why I chose analysis of algorithms as a subject
