Алгоритмы *

В данной статье я бы хотел объяснить работу алгоритма Прима. Алгоритм используется для нахождения минимального остовного дерева. Сам алгоритм очень прост, в статье хотел бы поделиться своей реализации на языке Go.

Предыдущая лекция.

Рандомизированные контролируемые испытания (РКИ) представляют собой наиболее объективную, прозрачную и эффективную методологию для проведения экспериментов. Они пользуются огромной популярностью и применяются в самых разных сферах, включая науку, медицину, маркетинг и технологии. С их помощью учёные и специалисты могут проверять эффективность новых методов лечения, лекарственных препаратов, продуктов или услуг, сравнивая результаты между двумя или более группами. РКИ встречаются гораздо чаще, чем может показаться на первый взгляд. Это невероятно популярный метод исследования причинно‑следственных связей. Хотя они довольно просты в реализации, их точность значительно превосходит все другие методы аппроксимации .

На это задание я наткнулся в процессе недавнего поиска работы - компания занимающаяся разработкой игр (по-моему, Lesta Games) предлагала его выполнить до отклика на HH. То есть "присылайте отклик вместе со ссылкой на ваше решение" или в этом духе. А я обожаю тестовые задания - такой шанс быстро напедалить с нуля какой-то код и потом спокойно про него забыть :) Здесь задачка была сформулирована не слишком конкретно - мне такие кажутся скорее "поводом поговорить" - поэтому любопытно обсудить подобный кейс с сообществом, знатоками и сочувствующими. Речь шла про позицию Go-разработчика - но задание достаточно language-agnostic - так что читайте смело!

В нашем веке центральное место в анализе и использовании данных занимает Data Science. Однако часто данное понятие сводят к одним лишь алгоритмам машинного обучения или даже искусственному интеллекту, преуменьшая другие важные аспекты этой области знаний.

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

Однако со временем стало ясно, что для полного понимания данных необходимо научиться объединять эти два подхода. Здесь на сцену выходит причинно‑следственный вывод (Causal Inference). Эта область Data Science помогает раскрыть причины явлений, объединяя преимущества как машинного обучения, так и эконометрики. Judea Pearl в своей статье 2021 года подчеркивает важность причинно‑следственного вывода как «ключевого элемента для достижения баланса между радикальным эмпиризмом ML и интерпретационным подходом эконометрики».

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

Недавно попался на глаза запрос, которым хотели отобрать в таблице (очевидно, для последующего удаления) все id записей интервалов, которые полностью перекрыты каким-то другим интервалом того же owner'а.

Но self-JOIN показал себя не лучшим образом...

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

Предположим к вам обратился товарищ, который хочет чтобы вы дали ему контакты принимающих решения менеджеров и топ-алгоритмистов в условном Микрософте. Зачем? После обмена репликами, где он сначала сопротивляется, выясняется что он изобрел новый алгоритм сортировки. В качестве доказательства он показывает программу на питоне, которая, по его словам, сортирует 10 чисел быстрее чем сортировка по умолчанию на питоне.

Разработка этой программы затрагивает множество разнообразных технологий для совместной работы, которые на первый взгляд невозможно соединить. Добавляют сложности взаимодействия между типами еще разные языки программирования и разные разработанные для них библиотеки, в каждой из которых разработан свой функционал. В данной статье рассмотрим способы перевода двух несвязных типов.

• Точка контакта мяча с ракеткой определяет угол отражения
• У ракеток нет ограничений по скорости
• Мяч отскакивает от верха и низа экрана

Зачем нужен метод выборки в нейросети и как устроена его внутренняя математика и алгоритм работы — об этом в статье.

Уже пять лет по улицам Москвы колесят роботы‑курьеры Яндекса, доставляя нам еду из любимых ресторанов и магазинов быстрее, чем мы успеваем проголодаться. На пути им встречается много препятствий: от безобидной клумбы, которую можно просто объехать, до восторженных детей (и иногда взрослых), от которых порой не так просто уехать.

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

Привет, меня зовут Тая, и я ML‑разработчик в команде восприятия робота‑доставщика. Сегодня я впервые детально расскажу о технологиях, благодаря которым робот‑доставщик Яндекса успешно доставляет заказы. Разберу ключевые компоненты системы, от сенсоров до алгоритмов принятия решений, и объясню, как они взаимодействуют. Из статьи вы узнаете, что происходит «под капотом» нашего робота во время его путешествий по городу.

Готовы погрузиться в мир автономной доставки?

Статья является логическим и практическим продолжением статьи про алгоритм вывода черепахи из лабиринта. Автор @demitryy сформулировал идею, но не описал практического её воплощения и в ходе оживлённой дискуссии появилось два подхода к реализации алгоритма. Один представил и воплотил на C++ пользователь @wataru, а второй, с разными видами оптимизаций, озвучил ваш покорный слуга. В статье мы увидим результат тестирования обоих подходов на C# и какие открытия для себя сделал автор.

Привет! Меня зовут Савва Степурин, я старший разработчик в группе рекомендательных продуктов в Фантехе Яндекса. Сегодня расскажу вам про то, как мы сделали «Незнакомое» для Моей волны — специальный режим для активного поиска музыкальных открытий.

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

Под катом — техническая эволюция «Незнакомого» от фильтра до отдельного продукта, описание новой модели ранжирования и многое другое.

В этой главе будут рассмотрены все необходимые аспекты для понимания механизмов работы CFG Scale, а также плюсы и минусы подхода с математическими примерами. Собрал все самое важное в одном месте без воды.

Всем привет! Это Сергей Качеев, старший разработчик в отделе сетевой инфраструктуры Yandex Infrastructure. Наша команда создаёт технологии, на которых работают сервисы Яндекса. В прошлый раз я рассказал целый сетевой детектив о том, как мы искали баг, который убивал DNS‑сервер Unbound. И сегодня я расскажу не менее интересную историю.

Мне на развитие попала XDP eBPF‑программа, которая защищает DNS‑серверы от выхода из строя под слишком большой нагрузкой (другими словами, от DDoS). На ядре 5.4 алгоритм защиты был основан на EWMA‑статистике с вероятностными дропами, которые постоянно контролировались из Control Plane. Это делало eBPF‑программу неавтономной. К тому же если Control Plane падал, то сервер оставался в состоянии последнего удачного обновления eBPF. Это нужно было исправлять — было решено заменить это всё на Token Bucket. Этот момент и будем считать отправной точкой в нашей истории.

Некоторые головоломки можно решать на SQL just for fun, а часть получается выразить на этом декларативном языке даже эффективнее других, императивных.

Попробовать сделать более наглядное решение, а заодно познакомить с некоторыми нетривиальными возможностями PostgreSQL меня натолкнул пост о решении на Python задачи Black and White.

Black and White — одна из интересных головоломок игры Puzzle Hunt Мельбурнского Университета 2010 года. По сюжету игры вы преследуете загадочного участника ТВ‑шоу в надежде раскрыть его личность. Вам удается пробраться сначала на студию, а затем и в его гримерку. Там в его одежде вы находите клочок бумаги. Одну из его сторон занимает сообщение, другую — головоломка и набор инструкций к ней.

«Разложите каждую из диаграмм ниже на полоски размером 1×1, 1×2 или 1×3 таким образом, чтобы ни одна сетка не содержала полосок с одинаковым черно‑белым паттерном, включая повороты».

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

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

Но после этого я, по инерции, решил ковыряться дальше. Факультативно, так сказать.

Всем привет! Меня зовут Алексей Староверов, я научный сотрудник группы «Embodied agents» в AIRI. К числу моих научных интересов в основном относятся алгоритмы обучения с подкреплением (RL) и их применение для робототехнических систем. В этом году в рамках конференции ICRA 2024 мы с коллегами из МФТИ представили статью на тему автономной навигации мобильных роботов, о которой я бы и хотел вам рассказать.