Лекция Александра Степанова “Наибольшая общая мера: последние 2500 лет”
Сегодня в офисе Яндекса на Парке Культуры состоялась первая из двух лекций Александра Степанова. Называлась она “Наибольшая общая мера: последние 2500 лет”. Буду откровенен. Как и очень многие я шел на эту лекцию за пачкой чего-нибудь модного с тегами “C++, STL, мета-программирование, тамада, услуги”, чтобы меня научили в сто первый раз как !на самом деле! нужно писать программы, чтобы, во-первых, проблем в принципе не возникало, а, во-вторых, чтобы если и возникало, то исключительно на стадии компиляции, потому что там в нашей божественной обобщенной системе типов не проканало, и еще заодно показали бы, что аж древние вавилоняне знали про стратегии, а древние китайцы изобрели <boost/variant.hpp> за три тысячи лет до европейцев. Мне стыдно, но я шел именно за этим. Выдали же мне совсем другого и намного больше.
Я не стану пересказывать содержание лекции, потому что это все равно кто-нибудь сделает, да и сами слайды доступны тут на русском и на английском, хочу просто поделиться некоторыми, на мой взгляд важными, моментами. Один из центральных объектов лекции – очень простая вещь – алгоритм Евклида и его история на протяжении 2500 лет оказались далеко не такими простыми, какими кажутся на первый взгляд.
Почему первая “реализация” алгоритма была основана не на делении с остатком, а на вычитании? Почему у древних греков не было нуля? Почему два эти вопроса связаны? Почему они имеют значение? Зачем вообще вперся этот алгоритм Евклида? Действительно, не имея представлении об истории математики и причинно-следственных отношениях в череде важных открытий, трудно не только ответить и на эти, и на куда более сложные вопросы, но тяжело даже оценить значимость происходящего и вообще многое понять. И если эти вопросы кажутся вам простыми, то полистайте слайды, дальше будет не так просто. Интересная оптимизация алгоритма Евклида (уже того, который на делении), использующая четность/нечетность чисел, оказывается, работает не только для чисел. Для многочленов “четность” можно определить как наличие нуля в качестве корня, и все будет работать. Грязный хак оказался не таким уж хаком, а верно подмеченной деталью, поддающейся обобщению. Для комплексных чисел уже можно делить не на 2, а на (внезапно) 1 + i и неспроста! Потому что и 2, и 1 + i – это наименьшие простые числа! Дальше там еще предлагалось что-то для каких-то таинственных колец да пространств, я в этом не очень силен.
Степанов подчеркнул значение математической культуры в программировании, а также математическую природу программирования, кое-что поругал, кое-что похвалил. Интернет уже оброс, наверное, апокрифами по мотивам этой лекции, в которых авторы хихикают и в качестве мощных, привлекающих внимание эпиграфов приводят вырванные из контекста лекции цитаты вроде: “Алексадрэску – дрянь!!”. Да, Степанов говорил сегодня и такое. Но всё это имело, на мой взгляд, следующий смысл: Алексадрэску дрянь и вреден для тебя, если ты не понимаешь куда более глубинных, важных математических основ того самого обобщения, и не стоит читать Алексадрэску, если ты еще не прочел Эвклида. То есть, он так и сказал, даже еще мощнее – не стоит читать Кнута, если не читал Евклида. К концу лекции это утверждение уже не казалось мне таким уж безумным.
“Каждый алгоритм (если он действительно работает) хороший, и его можно обобщить, даже если вы этого не видите” (неточная цитата). Я уже почти готов в это поверить. В общем, талант к здравому и корректном обобщению действительно имеет много общего с такими простыми, “природными” математическими примерами. О корректности, и о том, насколько это было важно, тоже было сказано.
Помимо обобщений много было просто о науке в целом, её разобщении, цинизме в рядах молодежи по отношению ко многому. Да, цинизма в нас через край, но это иначе называется, просто постмодерн успел докатиться и до науки. Вот еще, что важно по-моему – про оторванность теории от практики. О том, что действительно реальные, физические, рабочие модели и высокие там теории должны материализоваться в чем-то едином. Началось это с разговора об указателях – надо ли давать знать о них программисту? Где проходит грань между здравой инкапсуляцией и ненужным сокрытием “машины”, приводящим к неэффективности, как, например, в паскале, где на указателях не определена операция сравнения? Это, на мой взгляд, сложный вопрос, хотя конкретно насчет указателей кто-то вспомнил про хеширование ссылок в java/clr.
Сам Степанов оказался очень эрудированным человеком и произвел очень приятное впечатление, во-первых, потому что всю лекцию сквозь очень простые слайды сквозила мощь и мудрость, а с другой потому что он не боялся говорить, что думает, и с большой охотой отвечал на вопросы и делился мнением.После доклада все пошли на крышу офиса и продолжили разговоры о науке и судьбе России. Жаль, что мне пришлось бежать домой и взводить курок.
В общем, я написал отстой какой-то, судя по всему, лучше вы качните слайдов или дождитесь, пока выложат запись лекции. Я всю ночь не спал, мне простительно. Читал, между прочим, общую алгебру, теорию категорий да решал задачки.
Если вы дочитали до сюда, то вот вам отличная задача: дан многочлен f(x) с неотрицательными целыми коэффициентами, степень его неизвестна. Вы можете спрашивать, чему равно f(a), вам будут отвечать. За сколько вопросов вы точно узнаете все коэффициенты этого многочлена?
