Вышли две новые лекции об алгоритмах, которые я читаю в Контуре: о дереве ван Эмде Боаса и об остовных деревьях с системой непересекающихся множеств.

Основная аудитория этих лекций — профессиональные программисты, как опытные, так и начинающие. В своё время они закончили математические и компьютерные факультеты, но большинство из них не участвовало в олимпиадах по спортивному программированию. Вместе с ними мы изучаем алгоритмы и структуры данных, разминая мозг по пятницам. Присоединяйтесь 😊

Плейлист со всеми видео.

Любые замечания, вопросы и хвалу пишите в комментариях к видео или ко мне в личку: @andgein.

Последние две недели непрерывно советую всем окружающим сериал «Адам портит всё» (в оригинале «Adam Ruins Everything»). Адам Коновер, который играет главного героя — Адама Коновера, в каждой 20-минутной серии развенчивает известные и не столь известные мифы. О том, почему вездесущие рамки досмотра не очень помогают безопасности, почему традиция давать чаевые не несёт почти ничего хорошего, почему трёхмесячные летние каникулы вредны для школьников и почему важно говорить с близкими о будущей смерти.

Адам постоянно даёт ссылки на научные исследования, информацию из которых он берёт. Проверять их, конечно, никто не будет, но уверенности в его правде это добавляет :) Из минусов шоу — его ориентированность на Соединённые Штаты. В основном он рассказывает, конечно, об общемировых заблуждениях и проблемах, но нередко проскальзывает какая-нибудь локальная американская специфика (как, например, рассказы о проблемах американской выборной системы, американского футбола и американских городов, построенных для автомобилей, а не людей).

Если вы ещё не смотрели «Адам портит всё», обязательно посмотрите пару серий. Они такие короткие, что их можно смотреть за завтраком, по дороге на учёбу или во время рабочего перерыва. Можно наслаждаться оригиналом на английском языке, а можно найти вполне неплохой русский дубляж (правда, по сети гуляют и видео с плохим переводом, к сожалению).

Вот несколько примеров того, что можно узнать из первого сезона:

• Дарить кольца с бриллиантами на помолвку придумали меньше 100 лет назад в рамках рекламной кампании производителя бриллиантов «De Beers» (1 серия)
• Чистокровные породы собак — это генетические монстры, созданные скучающими викторианцами (17 серия)
• Ковбои на диком западе выглядели совершенно не так, какими мы их себе представляем в современной культуре (22 серия)

Рубрика «не знал только я»

Кот-д'Ивуар переводится с французского как «Берег слоновой кости». Соответственно, Кот-д'Ивуар и берег слоновой кости — это просто одно и то же.

Кстати, с 1889 по 1985 год эту страну в России и СССР так и называли, а переименовали в современное название только по просьбе правительства самого Кот-д'Ивуара. А жителей страны они попросили называть ивуарийцами.

Лекция о X-fast trie и Y-fast trie — в некотором смысле продолжение лекции о дереве ван Эмде Боаса, потому что эти структуры данных поддерживают ровно те же операции, только делают это ещё лучше.

Приятного просмотра! 😊

В питоне есть такой очень популярный модуль — six. Его используют, когда хотят, чтобы код одинаково хорошо работал и во втором питоне, и в третьем.

Спустя несколько лет использования этого модуля, сегодня я сделал открытие — узнал, почему он так называется :)

The name, “six”, comes from the fact that 2*3 equals 6. Why not addition? Multiplication is more powerful, and, anyway, “five” has already been snatched away by the (admittedly now moribund) Zope Five project.

Новая видяшка с Андреем!

Два месяца назад я съездил в Зимнюю Математическую Школу — недельный выздной лагерь для студентов и выпускников нашего матмеха. Съездил только на один день, чтобы успеть прочитать свою лекцию и послушать пару чужих :) И вот наконец-то подъехало видео моей лекции об атаках на RSA.

В лекции я сначала рассказываю о самом алгоритме RSA, а затем об основных идеях математических атак на него. Рассматривают как неправильную генерация ключей, так и настоящие атаки: ослепление нотариуса, атаки Хастада, Винера и Копперсмита. Приятного просмотра! 😊

https://www.youtube.com/watch?v=VYr_gd7Gv3g

Почтовый юбилей 🎁

В изоляции я, как и все, перешёл на работу из дома. Из дома пишу код, веду пары и из дома же провожу мастер-классы.

Где-то месяц назад Контур позвал меня провести мастер-класс для умных школьников, а пару недель назад этот мастер-класс состоялся. Теперь же его видеозапись появилась и в интернете: https://www.youtube.com/watch?v=ikX4lwqrgN0.

В видео рассказываю про reverse engineering: как работают процессоры, как операционные системы запускают программы, и как по скомпилированной программе узнать, что она делает. Ну и, конечно, самая вкусняшка: разревёрсил парочку программок.

А я, оказывается, давно не выкладывал сюда записи своих лекций по алгоритмам. Если вы вдруг соскучились, держите:

1. Алгоритм Фараха–Колтона и Бендера — про задачи RMQ и LCA, связь между ними и небольшую магию.
2. Hash Array Mapped Trie. Хеш? Массив? Бор? На самом деле это лекция про персистентную lock-free хеш-таблицу. Такая используется, например, в Хаскеле и Скале.
3. QuickHeap — как Heap, только очень Quick! Добавляем новые элементы за аморзитированную O(1), находим минимум за O(log n).
4. Современные сортировки — рассказываю про TimSort из питона, Adaptive Left Radix Sort, Bitonic Sort и супер-быструю сортировку на GPU.
5. Вероятностные алгоритмы. Мега-интересная классика: HyperLogLog, фильтр Блума, MinHash и Count Min Sketch. Эти алгоритмы позволяют очень быстро получить неточный, но близкий к правде ответ, сэкономив годы работы компьютеров.

Вы все, конечно же, в курсе — вчера вечером к МКС стартовал пилотируемый корабль Crew Dragon от SpaceX. В честь этого хочу рассказать несколько недавно узнанных мной фактов о человеке в космосе. Возможно, #не_знал_только_я :)

1. Если бы полгода назад меня спросили, почему на МКС присутствует невесомость (все же видели космонавтов, ловящих ртом пузырики еды из тюбиков?), я бы ответил: «Ну как... Потому что станция в космосе!». Подразумевая, что притяжение Земли на станции становится ничтожным малым, гравитация исчезает, и появляется невесомость.

Но радиус Земли — ~6300 км, а высота орбиты МКС всего 400–410 км. Сила притяжения Земли убывает как квадрат расстояния, и поэтому на МКС составляет (6300 / 6700)² = 88,5% от силы притяжения на уровне моря. То есть да, космонавтов меньше прижимает к Земле, но всего на 10–12%. Откуда же тогда невесомость? Ну во-первых, не невесомость, а микрогравитация :) А во-вторых МКС летит с первой космической скоростью — примерно 8 км/c. Первая космическая — это такая скорость, при которой объект может лететь вокруг Земли и не падать. При этом вектор скорости направлен по орбите, а вот вектор ускорения — перпендикулярно вниз к Земле, поэтому для космонавтов ситуация идентична свободному падению. Отсюда и возможность летать по станции, ловить динозавриков и пользоваться едой в тюбиках.

2. Кстати, о высоте орбиты МКС. Ниже — график этой самой высоты с 1998 по 2019 годы. Вопрос: почему с 2004 по 2012 годы МКС летала сильно ниже? И почему потом обратно поднялась наверх?

Ответ, оказывается, простой. Всё дело в американских Спейс Шаттлах. Шаттлы тогда летали к МКС, но им было тяжело забираться на такую высоту — приходилось загружать их меньшим количеством полезного груза. И NASA убедило опустить МКС чуть пониже. В 2011 году программу Шаттлов закрыли, а станцию подняли обратно до уровня 400 километров. Спрашивается: а зачем её вообще было поднимать? Ведь чем ниже, тем всем будет легче и быстрее на неё летать.

Ответ снова простой: поднятие МКС с 350 до 400 километров помогает сэкономить 60% топлива, которое требуется, чтобы поддерживать станцию на нужной высоте. МКС трётся об атмосферу и немного падает со временем, а с помощью двигателей её высоту корректируют. Раньше на это требовалось 8600 килограммов топлива в год, а теперь, на высоте 400 км, только 3600!

3. Я, конечно, слышал, о космических туристах, которые платят кучу миллионов денег, чтобы слетать на МКС. Но вы знали, что с 2001 по 2009 год на МКС побывали семь космических туристов, один из которых сделал это два раза? И они ведь там прямо тусят по две недели! После 2011 года полёты туристов загнулись, правда. По крайней мере, пока.

4. В 2006 году космонавты вышли из МКС в открытый космос и запустили мячик для гольфа в сторону Земли. Сохранилось даже видео этого момента: https://www.youtube.com/watch?v=0dIPf5tDuLo. Зачем? Такая вот реклама канадского производителя шариков для гольфа — компании Element 21 Golf :) Они говорят, что таким образом отметили 35-летие известного удара командира «Аполлона 14» Алана Шепарда. В 1971 году тот, находясь на Луне, вытащил из скафандра три стерилизованных мячика для гольфа и, пользуясь одним из инструментов в качестве клюшки, сделал три удара подряд.

А вот так выглядит обычная свечка. Слева — на Земле, справа — на МКС.

Завтра выступаю на митапе от Яндекса. Буду рассказывать про последние новинки в мире питона, про обновления самого языка и фреймворков, про новые-кленовые библиотеки и интересные статьи. К рассказу прилагаются мои субъективные комментарии и немного смешных шуток.

Благодаря коронавирусу можно прийти на митап с любого устройства с ютубом или зумом, поэтому приглашаю всех желающих! Приходите, только помните, что в расписании время — московское ;)

https://events.yandex.ru/events/pytup-online-26-08-2020

Запись выступления на ютубе: https://youtu.be/zFO_PnCSxeE?t=4924

Обожаю, когда наука объясняет людям то, что они столетиями считали чудом. Эдакое торжество разума над мистикой. Из поколения в поколение люди передают друг другу сказки, приметы, былины и мифы, а потом р-раз, и вместо них приходит наука! Кто-то, конечно, все равно продолжает передавать мифы и приметы дальше по цепочке, но мы-то знаем — прогресс не остановим: когда-нибудь мы обязательно объясним и то, что сейчас выглядит максимально загадочно.

Вот, например, из простого и давно известного: дым из трубы перед дождём обязательно стелется по земле. Это знание использовали в качестве простейшей приметы многие поколения крестьян. Но логичное объяснение куда красивее просто замеченной закономерности: перед дождём, заранее, повышается влажность воздуха. Это может быть незаметно людям, но частички дыма быстро смачиваются и тяжелеют, из-за чего просто не могут подняться высоко.

Или вот зимние узоры на окнах. Всем, надеюсь, в детстве рассказывали истории про рисунки Деда Мороза и вот это всё (у детей должна быть сказка!). А раньше и взрослые наверняка верили, что эти рисунки — дыхание духа зимы или чего-нибудь такого. Ведь они такие красивые всегда! Прямо как снежинки!

Но сейчас наука знает — это всего лишь дендриты и трихиты. И учёные детально разобрались, какие условия должны присутствовать, чтобы эти рисунки появились на окне. А главное — что нужно сделать, чтобы окно зимой не приходилось отогревать прежде чем можно будет посмотреть в него :)

Так вот, к чему это я :) Как всегда, к рубрике #не_знал_только_я!

Узнал недавно, кто такая фея Моргана. Моргана — это такая волшебница из легенд о короле Артуре, его единоутробная сестра, а также по некоторым версиям мать его сына (упс, да). Ученица того самого Мерлина. Согласно разным легендам, фея Моргана пережила Артура на многие столетия и нередко учиняла приключения морякам в Ирландском море и Атлантическом океане. Моряки раз в несколько десятилетий сообщали об островах и городах, которые они видели во время плавания, некоторые из них даже наносили на карты. Но в итоге оказывалось, что никаких островов нет, а карты приходилось перерисовывать вновь. Говорят даже, что история про летучего голландца тоже относится к проделкам Морганы (ну это по одной из версий, конечно, — ведь люди обожают придумывать разные мистические версии!).

Но как же круто поступили учёные, которые научились объяснять такие природные появления и исчезновения! Они назвали эти явления в честь той самой волшебницы, с которой люди связывали эти явления на протяжении столетий — Фата-Моргана. «Фата» по-итальянски — это фея, волшебница.

Фата-Моргана — это редко встречающееся оптическое явление в атмосфере, при котором лучи света многократно преломляются в толстом пироге из по-разному нагретых слоёв атмосферы. Это такой мульти-мираж, если угодно. Мираж в мираже в мираже. Объясняет и видимые с кораблей острова, которых нет, и летающие над водой корабли.

Фата-Моргана — это урок всем нам. Урок о том, что всё, что мы считаем волшебным, рано или поздно объяснит наука. Наука — ❤️.

Завтра выступаю на митапе Яндекса. На этот раз буду рассказывать о том, как правильно собирать телеметрию — логи, метрики и трассировки. Пригодится тем, кто пишет приложения, которые больше, чем домашний телеграм-ботик.

Примеры будут на питоне, но всё то же самое заработает на всех популярных языках и со всеми популярными фреймворками.

Ну а благодаря вездесущему онлайну вы можете прийти на митап прямо из тёплой кроватки! А только сегодня действует уникальная скидка в честь Чёрной пятницы — 800%! Все равно мероприятие бесплатное :)

В общем, приходите: yandex.ru/pytup. Мой доклад начинается в 11:40 московского времени.

Обновление: запись уже на ютубе.

Йуху, зарелизили подкаст со мной и Машей Кискачи от команды ВКонтакте: https://vk.com/wall-147415323_8461! Потравили байки про CTF-соревнования и про их формат.

Я не большой фанат подкастов как формата, не умею их слушать, да и не слушаю на регулярной основе, слушаю только самое-самое избранное. Но многие люди вокруг меня их внезапно любят :) Если вы из таких, то добавляйте в свои плейлисты, включайте перед сном, во время занятия спортом или ужина.

🎧

P.S. А если вы не признаёте вконтакте как подкаст-платформу, то запись залили на все стриминговые площадки, пользуйтесь на здоровье: https://podcast.ru/1540238940