Рождественская лекция Йоды (Дональда Кнута)

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

Если вы не знаете о Дональде Кнута, вы, вероятно, не собираетесь присутствовать на его рождественской лекции в Стэнфордском университете. Даже если вы знаете о нем, вы можете быть удивлены, узнав, что The New York Times только что напечатала статью, которая начинается:

«В течение полувека Стэнфордский ученый-компьютерщик Дональд Кнут, который имеет небольшое сходство с Йодой — хотя и ростом 6 футов 4 дюйма и в очках — правил как духовный наставник в области алгоритмов».

Кнут? Йода? Ну, я полагаю, там продаются газеты ….

На самом деле изображение, которое у них есть в верхней части статьи, достаточно хорошо отражает эту мысль, но если бы мы использовали его здесь, они, скорее всего, отправили бы нам уведомление DHCP или как там их называли. Небольшой поиск дает еще больше доказательств того, что Кнут действительно Йода мира компьютерных наук:

Он должен выглядеть настолько удивленным, что может левитировать весь TAOCP … Это также объясняет идиосинкразию его речевых паттернов.

А если серьезно — рождественская лекция и танцевальные ссылки:

Да, это та же одежда, что и на прошлогодней рождественской лекции, и на той, что была до и … В этом вся традиция. Я должен признать, что это непросто смотреть или слушать, но я могу обещать вам, что это того стоит.

Чтобы объяснить, что такое танцевальные ссылки и связанные с ними алгоритмы, потребовалось бы слишком много времени, и у публициста из Стэнфорда явно была та же проблема:

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

Обратите внимание, что «кажется весьма важным». Посетите Википедию для более широкого обсуждения.

Как бы то ни было, для меня большая честь посидеть у ног Йоды несколько минут, даже если инструкция прошла мимо нас …