Зачем мне эта математика

🧊Задача о муравье и кубе: сколько нужно шагов?

Тема случайных блужданий нас не отпускает, поэтому предлагаем решить связанную с ней задачу. Кстати, ее часто дают на собеседованиях — например, на позицию дата-аналитика.

➡️Условие
Допустим, у нас есть куб. У куба 8 вершин и 12 ребер. На одну из вершин этого куба мы посадили муравья. Он начинает двигаться случайным образом: на каждом шаге выбирает одно из трёх соседних рёбер с равной вероятностью и переходит по нему в следующую вершину.

➡️Вопрос
Сколько шагов в среднем понадобится муравью, чтобы добраться до противоположной вершины — то есть до той, которая соединена с начальной диагональю через весь куб?

Делитесь рассуждениями и ответами в комментариях, а мы опубликуем решение уже вечером!

#задача

📱Рекомендательные системы. Как они работают и где там математика

Этот пост для нас написал автор канала «Аналитика данных / Data Study», за что ему большое спасибо! Передаем микрофон гостю, а вас приглашаем в его канал. Подписывайтесь, там еще больше интересного: @data_study.

Рекомендательные системы предлагают нам контент, товары и услуги. Работают они благодаря сложным алгоритмам, за которыми стоят машинное обучение и математика.

В карточках разбираем разные подходы к построению рекомендательных систем и их применение на практике. Если заинтересовались, вот полезные ссылки по темам:

Матричная факторизация, конспекты:
🔗 Рекомендации на основе матричных разложений
🔗 Матричная факторизация

Коллаборативная фильтрация и полезные ссылки по item-based- и user-based-подходам:
🔗 Анатомия рекомендательных систем. Часть первая
🔗 Анатомия рекомендательных систем. Часть вторая

Гибридные подходы, полезные статьи:
🔗 Перевод статьи об алгоритмах рекомендательных систем
🔗 Как помочь пользователю найти то, что ему нужно

Генеративные подходы, интервью Николая Савушкина:
🔗 Рекомендательные системы моделируют поведение людей

Вот так математика помогает компаниям делать рекомендации релевантными и полезными.

#рекомендуем

📕 Бонус для тех, кто любит Пушкина

Ни для кого не новость, что любой текст на русском языке — это чередование гласных и согласных букв. Андрей Марков посмотрел на это как математик и задался вопросами: можем ли мы как-то измерить это? Оценить? Как именно устроено это чередование?

Чтобы ответить на эти вопросы, Марков провел анализ «Евгения Онегина» и, возможно, стал прервым в мире человеком, который попробовал математически подойти к анализу языка. Изучив последовательность из 20 000 букв романа, он выяснил, что:

🟠 последовательность «гласная, гласная» встречается 1104 раза;
🟠«гласная, гласная, гласная» — 115 раз;
🟠«согласная, согласная, согласная» — 505 раз. И так далее.

Доклад, кстати, назывался «Пример статистического исследования над текстом “Евгения Онегина” иллюстрирующий связь испытаний в цепь», а представил его Марков в 1913 году на физико-математическом собрании Академии наук. На картинках показываем, как выглядела часть доклада и заметки по анализу.

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

#история

🌀 Андрей Марков: человек, который приручил случайность

Настроение сегодня философское, поэтому снова порассуждаем о случайностях. А заодно расскажем о математике, который посвятил изучению этих случайностей годы.

➡️ В начале прошлого века считалось, что если знать прошлое, можно безошибочно предсказать будущее — так думал, например, математик Пьер-Симон Лаплас. Но российский математик Андрей Марков показал, что есть процессы, где только текущее состояние определяет будущее, а прошлое не имеет значения.

Представьте человека, который гуляет по городу. На каждом перекрёстке он бросает монетку, чтобы решить, куда идти: орёл — направо, решка — налево. Куда он попадёт в итоге, зависит не от того, откуда он пришёл, а от его поведения на текущем перекрёстке. Решает момент!

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

❓ Где используют марковские цепи

Марков не подозревал, что его работа ляжет в основу сервисов, которыми пользуемся мы с вами. Например, в популярных поисковиках работает PageRank: это марковская цепь, которая определяет, какие сайты должны быть в топе выдачи. Работает это так:

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

Какой бы ни была начальная страница, с которой пользователь начинает путешествовать по интернету, абсолютно любая страница имеет вероятность стать той, на которую он попадет. Чем выше вероятность, тем выше в выдаче окажется страница.

Ещё марковские цепи используют в машинном обучении — например, в генерации текста. Чтобы сгенерировать следующее слово, алгоритм смотрит на текущее слово или короткий контекст, а предысторию не учитывает.

Другой пример — распознавание речи в Siri и других ассистентах: алгоритмы прогнозируют следующее слово с помощью скрытых марковских моделей.

Никакой магии, только математика 🔮

#как_устроено

🐜 Случайные блуждания: идём куда глаза глядят

В математике, самой точной из наук, тоже есть феномены, которые кажутся нелогичными и хаотичными. Сегодня речь пойдёт об одном из них.

Представим муравья, которого опустили на лист бумаги. Он делает шаг влево, потом — вправо, потом — снова вправо, и все это — без всякой логики. Куда он придет через сто шагов? А через тысячу? Это и есть классическая задача случайного блуждания.

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

Может, вам тоже вспомнятся примеры случайных блужданий?

#как_устроено

📝 Хотите в ШАД? Тогда вот полезная рекомендация от нас

Прямо сейчас легендарная Школа анализа данных от Яндекс Образования проводит очередной набор. ШАД с 2007 года учит анализу данных, а сейчас там 50+ курсов по Data Science, большим данным и другим дисциплинам. Для студентов есть ещё и спецкурсы: например, можно дополнительно изучать беспилотные авто.

Если думаете о поступлении туда, советуем не пропустить QA-сессию 2.0.

Ходят слухи, что можно послушать её вместо любимого подкаста, пройти отбор и стать студентом. Проверим?

❓ Где и когда
В телеграм-канале «Все в ШАД!» в понедельник, 28 апреля. Подписывайтесь, чтобы не пропустить анонс и старт прямого эфира: @vse_v_shad.

❓ Что будет на QA-сессии 2.0
Эксперты из ШАД расскажут о поступлении и учёбе на программах. Вопросы можно будет оставлять прямо в комментариях.

Кстати, запись первой QA-сессии уже можно послушать в канале!

#рекомендуем

А вам когда-нибудь ставили задачи математики? 😄

#меммат

✖️ Как молодой математик бросил вызов 40-летней теории и ускорил интернет

Сегодня у нас для вас история, которая доказывает: математика поддаётся смелым.

❓Что случилось
Зимой 2025 года Эндрю Крапивин, аспирант Кембриджского университета, опубликовал статью о новом подходе к хеш-таблицам. В ней он сумел опровергнуть гипотезу Эндрю Яо и придумал, как ускорить интернет. Самое удивительное: о существовании гипотезы Эндрю не знал. А статья его стала настоящей сенсацией, и вот почему.

🗂️Что такое хеш-таблицы
Каждый раз, когда вы ищете товар в онлайн-магазине или приложение в сторе, в дело вступают хеш-таблицы. Это структуры данных, которые хранят пары «ключ-значение» и помогают находить информацию.

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

📝 Гипотеза Яо
У хеш-таблиц есть ограничения. По мере заполнения таблицы увеличивается вероятность коллизий — ситуаций, когда разные ключи указывают на одну ячейку.

В 1985 году Эндрю Яо предположил, что при высокой заполненности таблицы поиск свободной ячейки требует времени, пропорционального степени заполнения. Например, при заполненности на 99% придется проверить около 100 позиций, чтобы добавить новый элемент, а при заполненности на 99,9 — 1000 позиций.

🚀 Что придумал Крапивин
В коротком посте объяснить будет нелегко. Если сильно упрощать, Крапивин придумал новый тип хеш-таблиц. Он предложил разбивать таблицу на сегменты так, что при заполненности одного сегмента можно сразу начать искать в другом.

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

🌐 Влияние на будущее интернета
Теперь благодаря Крапивину разработчики смогут создавать более быстрые и эффективные структуры данных. Веб-страницы начнут быстрее загружаться, а онлайн-сервисы — лучше работать. Иными словами, нам с вами ускорят интернет, чтобы смотреть мемы и картинки с котами было ещё проще.

Возможно, Крапивин сделал открытие, потому что не слышал о теории Яо и не знал, что его что-то ограничивает?

#история

📏Что такое метрика и почему без неё не обойтись

Сейчас о метриках часто говорят в контексте ИТ-продуктов, но на самом деле метрика — это то, что нужно всегда, когда мы измеряем «расстояние» между объектами. Любыми! Сейчас расскажем подробнее.

❓Что такое метрика в математическом смысле
Понятие «метрика» придумали в 1910-х годах Феликс Хаусдорф и Морис Фреше. Они заложили основы метрических пространств — миров, где можно измерять «расстояния», даже если они не похожи на то, к чему мы привыкли. Например, «расстоянием» может быть разница между двумя картинками.

«Настоящая» метрика подчиняется трём правилам:

1️⃣ Неотрицательность: расстояние не может быть отрицательным.
2️⃣ Симметрия: если от A до Б — пять километров, от Б до A — столько же.
3️⃣ Неравенство треугольника: путь напрямую всегда короче суммы обходных путей или равен ей.

Метрика — не всегда привычное нам расстояние в километрах. Вот примеры:

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

🔵В музыке есть метрики, измеряющие схожесть мелодий. Именно они лежат в основе работы Shazam и помогают узнать, что за песня играет в любимом баре.

🔵В теории графов метрика может измерять, насколько «далеки» две вершины — например, по минимальному числу переходов между ними. Этот принцип лежит в основе рекомендательных систем и поиска кратчайших путей в транспортных сетях.

🔵В психологии метрики применяют, чтобы сравнивать поведенческие профили людей и узнавать, например, насколько похожи их реакции на стресс. Звучит как что-то из «Чёрного зеркала», но на самом деле полезно.

🔵В биоинформатике метрики помогают сравнивать цепочки ДНК. Это позволяет, например, построить генеалогические деревья вида и понять, кто с кем родственник в мире бактерий, растений или животных.

Метрика помогает измерить «расстояние», а в чем именно это «расстояние» будет измеряться и какие выводы поможет сделать — зависит от ситуации 😊

А вы используете метрики в работе?

#как_устроено