Ретро Бит 1-10 - Сева Сотх
— Здравствуйте, меня зовут Дональд Кнут и я программист, — начал он с шутки.
Сколько же в этом человеке научной харизмы. Великий ученый стартовал своё выступление и я как отрубился, растворился в доводах и тезисах. Еще и тема, как на заказ, интересная оказалась — алгоритмы выравнивания текста для наилучшего расположения на странице. Строки, абзацы, кегли, система Метафонт для генерации шрифтов. Всё то, с чем он столкнулся при разработке типографского “Ти-Экса”. Точнее, сегодня я узнал, что правильно говорить “тех”, со звуком “ха” в конце.
— Я ничего не понял, но этот чувак нереально круто говорит, — шепотом высказался Эдди, когда возникла небольшая пауза — докладчик решил попить воды. — Так и хочется дослушать, а потом перед тыковкой выпендриться — типа я умный и научные слова знаю.
Группа вела себя тихо и смирно, оделись ребята более-менее прилично, в чистые рубашки. И никто их не узнал. Вполне типичные молодые студенты, среди тех тоже встречаются патлатые и бородатые.
И, наконец, настал важный момент.
— Сейчас я готов ответить на абсолютно любые ваши вопросы, — произнес математик.
Я решительно встал в очередь к микрофону. И, что удивительно, вслед за мной пошла Линда. Как настоящий джентльмен, пропустил девушку вперед. Очень уж интересно стало, что она хочет спросить у легенды.
Пришлось подождать, пока Кнут ответит опередившим нас академикам. Обстоятельно и не торопясь, с математической точностью. Ни о чем не жалею, хотя нога от долгого стояния на месте начала ныть.
— Здравствуйте, мистер Кнут! Я Линда Ким, художница из студии “Каналья Геймс”, — девушка изо всех сил старалась звучать позвонче, но старая астма-не-астма, как назло, заставила ее говорить в привычной хрипящей манере.
— Каналья Геймс, знакомое название. Ваша игра 2048 лишила меня сна на несколько ночей, мисс. Очень изящная демонстрация экспоненциального роста. Я даже высчитал теоретически максимальный размер плитки — два в семнадцатой степени, возможный в том случае, если игроку улыбнется удача.
ШОК! Обладатель премии Тьюринга играл в нашу игру. И ему, черт подери, понравилось.
— Спасибо, это всё придумал Крис… основатель студии. Вот он, следующий в очереди, — Линда очень мило покраснела. — Но спросить я хотела о другом…
— Подождите несколько секунд, Линда.
Кнут достал из кармана брюк чековую книжку и выписал чек.
— Здесь ровно 2048 центов, — сказал он. — Пожалуйста, передайте юной мисс. Достойная награда за прекрасное упражнение для ума. Только попрошу вас, поступите, как остальные — не обналичивайте чек. Я раздал их столько, что рискую обанкротиться в случае, если все обратятся в банк. Простите, вы хотели задать вопрос.
— Спасибо огромное за чек, — еще больше смутилась девушка, — мы поместим его в рамочку. Мой вопрос… не ожидала, что вы геймер… скажите, вашу систему Метафонт кто-то использует для создания текстовых квестов? Возможно ли ее лицензировать?
— Боюсь, для работы Метафонт потребуется мощный университетский мейнфрейм. Если ваша компания располагает доступом к такому, обратитесь к любому из моих ассистентов, вам запишут копию исходных кодов, они распространяются свободно.
— Спасибо, мистер Кнут. Боюсь, покупка мейнфрейма нам пока не по карману, — еще сильнее смутилась Линда и уступила мне место.
— Здравствуйте, сэр, — настала моя очередь. — Крис Коламбус, студия Каналья Геймс. Но мой вопрос не об играх. Скажите, как вы относитесь к концепции патентования алгоритмов?
После первоначального приступа скупости я для себя уже решил не быть жадной задницей. Игры и так принесут достаточно, чтобы я ни в чем не нуждался. Так для чего извращаться, патентуя математику? Однако почему бы и не спросить мнение великого человека? Оно для меня важно, несмотря на то, что есть собственное.
— Категорически отрицательно. Именно поэтому я никогда не пытался и не попытаюсь запатентовать ни ТеХ, ни МЕТАФОНТ — я передал их в общественное достояние. Алгоритмы принадлежат человечеству.
— Благодарю, сэр. Мне было важно услышать вашу позицию.
Решение принято и обжалованию не подлежит! К Ктулху патенты на софт! Но это не означает, что я позволю себя беспрепятственно грабить.
— А теперь прошу прощения у всех присутствующих, я отниму еще немного вашего времени. Доктор Кнут, пожалуйста, оцените следующие улучшения алгоритма быстрой сортировки: первое — использование тройного ветвления. Делить данные на большие, меньшие и равные опорному. Равные элементы не обрабатывать рекурсивно.
Второе — следить за глубиной рекурсии и в плохих случаях переходить к пирамидальной сортировке, гарантируя тем самым конечное время работы на любых данных.
Третье — маленькие хвосты массивов сортировать вставками, как более оптимальным для них методом.
Кнут несколько секунд смотрел на меня поверх очков. Сердитым математик не выглядел. Скорее задумчивым, как если бы запустил в голове отладчик и мысленно прогонял код.
— Ваши предложения выглядят разумно, молодой человек, — наконец сказал он. — Во всяком случае, каждое из них направлено против реальной слабости быстрой сортировки.
Захотелось отыскать на трибунах Стерлинга и показать ему средний палец. Но что-то я “светило” не замечал. Видимо, слушать младшего по возрасту Кнута для него необязательно.
— Однако, — продолжил Кнут, — алгоритм не существует в виде набора хороших намерений. Его нужно формализовать, указать точные критерии перехода к другим методикам и провести измерения. Только после этого можно говорить, что у вас есть что-то большее, чем идея.
— Понял, сэр. Вот там, на трибунах, моя папка, где вся проделанная работа, включая замеры производительности для критичных случаев. Мне будет лестно, если вы взглянете на нее, если найдете время.
— Постараюсь ознакомиться. Кто ваш научный руководитель, Крис?
— Мне помогал с методикой тестирования Сэм Гарланд, аспирант из Беркли, где я вольнослушатель. Наверное, не очень корректно с моей стороны отнимать время у следующих докладчиков.
Я отсалютовал Сэму, нашарив его взглядом на трибуне, и двинулся на своё место.
— Ты