Парадокс двух детей Вы встретили на прогулке соседей с сыном. Известно, что у них двое детей. Какова вероятность, что второй — тоже мальчик?
Казалось бы, детская задачка, где нужно просто “вспомнить формулу”, но всё не так однозначно. Если задать этот вопрос прохожему, он, скорее всего, скажет ½. Преподаватель математики, возможно, ответит ⅓. Кто из них прав?
В каком-то смысле, правы оба. Просто каждый представляют себе свой способ, как была получена информация о ребёнке. На самом деле это и есть условие задачи. Только скрытое.
Вопреки распространенному мнению, теория вероятностей не говорит, возможна ли та или иная ситуация. Прежде чем что-то считать, придется подготовить фундамент — идеализировать наблюдение, понять, что именно мы считаем случайным и построить модель эксперимента. Без этого никакие формулы не помогут.
Парадоксы, о которых пойдет речь, — не логические ошибки. Это ситуации, в которых само понятие вероятности начинает колебаться. Они не ломают теорию, но обнажают, где она требует особенной осторожности. Именно в таких местах теория вероятностей становится особенно странной — и особенно интересной.
В этой статье — три таких истории. В первой один и тот же факт даёт разные вероятности, если по-разному устроено наблюдение. Во второй один и тот же объект может быть “случайным” множеством способов. А в третьей невозможно придумать, как сделать задачу математически строгой.
По дороге мы обсудим, что такое вероятностная модель, геометрическая вероятность и математическое ожидание. А в конце поговорим о том, почему в теории вероятностей у одной задачи могут быть несколько ответов и как с этим жить. А еще, вас ждет красивая задача — бонус для тех, кто дочитает статью до конца.
А пока — вернёмся к соседям с мальчиком. Разберемся, почему эта задачка не так проста, как кажется на первый взгляд.
Эта статья — краткая заметка о двух связанных друг с другом эмпирических правилах.
Поднимайте If вверх
Если внутри функции есть условие if, то подумайте, нельзя ли его переместить в вызывающую сторону:
// ХОРОШО
fn frobnicate(walrus: Walrus) {
... }
// ПЛОХО
fn frobnicate(walrus: Option<Walrus>) {
let walrus = match walrus {
Some(it) => it,
None => return,
};
...
}
В подобных примерах часто существуют предварительные условия: функция может проверять предусловие внутри и «ничего не делать», если оно не выполняется, или же может передать задачу проверки предварительного условия вызывающей её стороне, а при помощи типов (или assert) принудительно удовлетворить этому условию. Подъём проверок вверх, особенно в случае предварительных условий, может иметь лавинообразный эффект и привести к уменьшению общего количества проверок. Именно поэтому и возникло это правило.
Сложность текста: 2-3/5
Необходимые знания: должно быть достаточно основ теории многочленов, например, формул Виета
На случай, если современная культура окажется утерянной во времени, дам немного контекста, чтобы вы понимали, почему эта задача стоит изучения.
Интернет переполнен «математическими задачками с эмодзи». Они более-менее продуманы, поэтому в них легко запутаться, и у людей получаются разные ответы, что вызывает споры и обсуждения, делая посты виральными и так далее...
Естественно, настоящим математикам это надоело. В начале 2017 года на Reddit появился пост с заголовком «Меня утомила вся эта фейсбучная фруктовая математика. Хочет кто-нибудь придумать действительно сложную математическую задачу, чтобы побороться с этим явлением?».
Я долгое время занимаюсь построением 3D копий городов в проприетарном игровом движке на основе картографических данных. Суммарно это сложная задача, успех выполнения которой заключется в решении небольшого набора больших проблем. Одной из таких проблем является отрисовка точного ландшафта на основе реальных данных. Далее я постараюсь расказать обо всех R&D этапах и технических особенностях, с которыми пришлось столкнуться, а вконце будет несколько сравнений сгенерированного ландшафта с фотографиями реальных мест.
Показанным ниже кодом вы можете проверить на високосность год в интервале 0 ≤ y ≤ 102499 всего примерно тремя командами CPU:
bool is_leap_year_fast(uint32_t y) {
return ((y * 1073750999) & 3221352463) <= 126976;
}
Как это работает? Ответ на удивление сложен. В статье я объясню процесс; в основном он связан с забавным битовым жонглированием. В конце мы обсудим применение этого кода на практике.
Всё началось невинно. Шёл 2009 год, и я просто хотел портировать Earcut на Flash - для своей мини-игры. Тогда это сработало, но с годами стало понятно: простые решения перестают работать, как только хочешь выжать из них максимум.
И это решит 95% проблем типичного стартапа. Как-то так повелось, что по всему СНГ и его окрестностям на работу набирают зумеров с колоссальным опытом в три года, и они начинают создавать идеальные архитектуры. Да, каждый из вас, как только получает возможность взять на себя хоть малейшую ответственность, сразу вспоминает все прочитанные и не прочитанные книги и пилит свою уникальную архитектуру, непохожую ни на что.
Может кому-то это будет интересно, даст возможность лучше подготовиться; или наоборот кто-то примет решение не участвовать.
Коротко о себе: 41 год, senior software developer, стаж > 20 лет. Однако, как я понял, эти собесы все равно для всех одинаковые, так чтоб все написанное актуально и для молодежи.
Итак, угораздило меня согласиться на т. н. «Weekend Offer на позицию разработчика на Kotlin». Вообще‑то мне больше нравится Scala, и опыта по ней гораздо больше, но рекрутерша была сильно настойчива, и я решил обновить экспиренс, а возможно, и прибавку в деньгах. И вот что было дальше.
Наверное, я очень опоздал с изучением CUDA. До недавнего времени даже не знал, что CUDA — это просто C++ с небольшими добавками. Если бы я знал, что изучение её пойдёт как по маслу, я бы столько не медлил. Но, если у вас есть багаж привычек C++, то код на CUDA у вас будет получаться низкокачественным. Поэтому расскажу вам о некоторых уроках, изученных на практике — возможно, мой опыт поможет вам ускорить код.
Привет, Хабр!
Когда-то я писал веб-приложения. Решал задачи бизнеса, деплой в прод, REST, тесты, метрики, кубики. Всё было нормально. Но в какой-то момент мне стало… скучно.
Да, задачи были интересными. Команда — отличной. Но где-то внутри появилась пустота. Хотелось делать что-то настоящее. Осязаемое. Что-то, где за твоим кодом — больше, чем UI и API. Хотелось влиять на реальный мир.
Так я попал в мир электропривода.
Я астрофизик, занимаюсь исследованием астрофизических течений в окрестностях двойных звезд и экзопланет. Тема очень обширная и интересная, но сегодня статья будет немного не об этом, и даже не о том, как, собственно, это делается, а об одной маленькой, как мне казалось, проблеме, которая погрузила меня в пучины программирования, хотя изначально цель моя была от программирования избавиться, по возможности, совсем. А именно - о символьной математике и об упрощении алгебраических выражений.
Я знаю многих программистов и руководителей в IT компаниях, которые недолюбливают математиков и в частности считают их далёкими от жизни идиотами из-за их утверждений в духе "нельзя отсортировать последовательность быстрее, чем за nlogn" -- ведь это очевидным образом неверно, есть же сортировка подсчетом и radix sort. Нюанс в том, что описанное выше -- это распространённая некорректная трактовка одной из ключевых теорем об алгоритмах сортировок, корректное утверждение выглядит так: "не существует алгоритма, который бы гарантированно находил перестановку n элементов, приводящую к возрастающему порядку, быстрее чем за nlogn используя только операции попарного сравнения". В этом утверждении больше слов, оно более сложно в плане когнитивного восприятия, ключевой момент обозначил жирным шрифтом, чувствуете разницу?
В статье хочу рассказать об этой теореме и ещё о двух, на которые я наткнулся когда вел занятия по информатике в 9-11 классах будучи студентом старших курсов. Эти теоремы для меня были удивительным открытием, радовался вне себя когда вывел сам одну из них - её я не встречал ни в одном учебнике по информатике. В последствии все три теоремы были найдены в недрах Кнута, но чёрт побери, их поиск был сложнее, чем вывод!
Если я ещё не убедил Вас прочитать статью, то вот моя последняя попытка: в статье объясню почему пузырёк -- это бесполезная фигня, но внезапно практически также работающая сортировка вставками -- это супер важная сортировка, являющаяся частью std::sort в MSVC, GCC и Clang. Расскажу, каким интересным свойством оптимальности обладает сортировка выбором, являющаяся в теории такой же неэффективной как пузырёк.
Вокруг меня собралось много людей, которые уделяют время торговле на бирже. Кто-то торгует криптой, кто-то акциями, а кто-то валютой. Кто-то называет себя инвестором, кто-то – трейдером. Я часто вижу как случайные прохожие в разных городах и странах смотрят на телефоне или ноутбуке в биржевой терминал. А по ночам иногда сам пишу аналитический софт или софт для бэктестинга. До текущего момента писал. Всех этих людей объединяет наличие веры и заблуждений о рынке.
Хотелось бы прокомментировать публикацию Ильи Кабанова в Медузе по поводу новых разработок в алгоритмах хеширования: "Optimal Bounds for Open Addressing Without Reordering" (Farach-Colton, Krapivin, and Kuszmaul, 2025) и последующую "The Bathroom Model: A Realistic Approach to Hash Table Algorithm Optimization" (Wang, 2025). И особенно кликбейтное: "в перспективе метод Крапивина и его коллег может ускорить многие процессы в интернете."
Я около 7 лет очень плотно занимался темой хеш-таблиц и написал много их вариантов: Koloboke, SmoothieMap, memory-mapped вариации.
Я потерял к теме интерес с выходом гугловской SwissTable (2018), и ее фейсбучного варианта F14, которые основаны на SIMD. Они проверяют загруженность ячеек и совпадения "тега" элемента сразу блоками по 8 соседних слотов. Поэтому на любых разумных загрузках таблиц (до 90%) - "цепочка проверки" очень редко превышает 1 (то есть, одну проверку 8-элементного блока).
В этих SIMD-based алгоритмах, ухищрения и теоретические по поводу "алгоритма шагания" просто не играют никакой роли -- алгоритм шагания можно сказать отсутствует, потому что если можно вставить элемент внутри 8-элементного блока, то это и стоит сделать.
Именно эти разработки, а не Крут и не статья Yao, которую "опровергли" новые работы, стали "практическим концом теории" хеш-таблиц, на мой взгляд.
SwissTable стали стандартным алгоритмом хеш-таблиц в Расте, и, буквально в этом месяце, в Golang 1.24.
В заключение, отвечая Илье Кабанову: к "ускорению интернета" эти теоретические алгоритмы не приведут :)
в статье приведены алгоритмы обработки коротких битовых строк, обычно вмещающихся в машинное слово, в большей степени эти алгоритмы предназначены для обработки строк длины 32 или 64, но многие из них можно применять для SIMD инструкций или даже GPU.
