Алгоритмы *

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

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

Так, энтузиасты писали на sed мастермайнд (на наши деньги — «Быки и коровы»), сокобан, сапер и даже шахматы. Я упоролся несколько сильнее и написал игру с неполной информацией, псевдослучайной генерацией расстановок и ходов и достаточно сильным противником. Причем реализованный алгоритм позволяет усилить его еще больше, изменив буквально пару строк. Насколько я могу видеть по гитхабу, у меня получился один из самых масштабных на сегодняшний день проектов (если не самый масштабный) среди всей этой адской эзотерики.

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

Сперва я просто хотел показать, какие клевые вещи можно реализовать самыми минимальными средствами, но в итоге получился большой пошаговый гайд. Для тех, кому результат интереснее процесса, в конце статьи есть ссылка на гитхаб, чтобы сразу посмотреть, что получилось. Остальные — наливайте чайку и добро пожаловать под кат!

Всем привет. Я сделал бесплатную обучающую платформу shlyk.tech с упором на визуализацию идей и структур. Графы, системы счисления, логику, комбинаторику, индукцию здесь можно потрогать, покрутить, прошагать и понять, почему оно так работает.

Когда вы загружаете фотографии на Яндекс Диск, они не просто лежат в облаке: ML‑модели анализируют снимки, группируют их в альбомы и выбирают хайлайты для фотоленты в Яндекс Диске. Но чтобы улучшать такую систему, нужно уметь измерять качество её работы. И здесь начинается проблема: модель выбирает «красивые» и «удачные» кадры, а эстетика — вещь субъективная. Одному важны насыщенные цвета, другому — композиция, третьему — эмоции и лица в кадре. Если попросить асессоров ставить оценки от 1 до 10, мы быстро получим не объективную шкалу, а смесь личных вкусов, разной строгости и шума.

Поэтому мы подошли к задаче не как к обычной разметке, а как к исследованию. Вместо абсолютных оценок использовали шахматный подход. Каждая фотография стала «игроком», который соревнуется с другими по 16 признакам эстетики — цветам, фокусу, геометрии, эмоциональности и другим параметрам. Это позволило получить не просто рейтинг кадров, а инструмент для анализа того, какие визуальные признаки учитывают ML‑модели Диска.

Всем привет! Я Всеволод Мещеряков из службы разметки Yandex Crowd Solutions. Мы собираем и размечаем фото, видео, тексты — в общем, готовим данные, на которых учатся ML‑модели. В этой статье расскажу, как подход из мира шахмат помог нам связать субъективное восприятие фотографий с математическими оценками и сделать фотоленту Яндекс Диска ещё красивее.

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

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

Задача, которая стояла перед командой: автоматизировать этот осмотр. Убрать человека из точки принятия решения и выдавать вердикт «грузить / не грузить» по объективным числам, а не по взгляду грузчика.

Требования заказчика сразу задали высокую планку. Нужно мерить три габарита: ширину свободного прохода, высоту от пола до горизонтальной балки, длину — и находить посторонние предметы внутри кузова. Пороги жёсткие: ширина меньше 2,43 м — отказ, высота меньше 2,60 м — отказ, длина меньше 8 м — отказ. Зазор между «входит» и «не входит» — 2 см: паллета шириной 2,40 м идёт впритык, и выступающий на стойке крючок, съедающий эти 2 см, делает кузов непригодным. То есть мерить надо с точностью лучше сантиметра — и не у ворот, а на всей глубине кузова, до 15 м от точки установки.

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

Меня зовут Александра Атаман, я QA‑инженер в команде веба Яндекс Такси. В этой статье я расскажу, как мы оптимизировали процесс формирования регрессионного тестирования для ручного прогона, внедрив систему весов для тест‑кейсов. Этот подход помогает прицельно отбирать наиболее «опасные» сценарии: самые старые, забагованные или потенциально проблемные.

Я поделюсь техническими деталями реализации, логикой распределения весов и результатами нашего эксперимента. Спойлер: ожидания не во всём совпали с реальностью — но именно этот опыт оказался для нас самым ценным.

Представьте себе задачу, условия которой можно объяснить восьмилетнему ребенку ровно за тридцать секунд. А теперь представьте, что эта же самая задача десятилетиями заставляет сдаваться величайших математиков современности. Гипотеза Коллатца (или проблема «3x+1») доказывает поразительную вещь: за самыми элементарными арифметическими правилами может скрываться абсолютно непредсказуемый хаос и бесконечная сложность. Разбираемся, в чем подвох этой задачи, почему Пауль Эрдёш предлагал за её решение деньги из своего кармана и как с ней справляются современные суперкомпьютеры.

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

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

Люди тоже их создают. Для меня один из самых удивительных паттернов, которые мы придумали — это дороги.

Иногда я представляю инопланетян из далёких галактик, которые откроют Землю уже спустя много времени после нашего ухода. Леса, снова занятые природой, города, превратившиеся в развалины; однако между ними всё равно заметен слабый паттерн — сеть дорог. Мне нравится думать, что они будут чувствовать то же самое, что и я, когда смотрю на природные паттерны: «Ого, кто-то действительно это продумал».

Градостроительные симуляторы и их дороги

Должен сказать, что дороги восхищали меня с детства.

До сих пор помню, как в возрасте шести-семи лет впервые играл в SimCity 2000. Я понял не особо многое и не знал, что такое зонирование, налоги и спрос. Но дороги сразу меня восхитили.

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

Развязки. Перекрёстки с круговым движением. Эстакады. Сужения полос. Замечал каждую мелочь.

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

В предыдущей части была рассмотрена предыстория комплексных чисел: от их первого открытия до понимания и умения их широко использовать в науке прошли сотни лет. Комплексные числа впервые возникли как артефакт вычислений в работе Кардано 1545-го года и вплоть до конца XVIII века их статус оставался нестабильным, шли научные дискуссии об уместности их употребления и интерпретации.

Современные изложения теории комплексных чисел выглядят «магически» и непонятно для многих людей именно потому, что, как правило, разрыв между непониманием XVIII века и теориями XIX века не покрыт. Сначала предлагается изучить основы теории комплексных чисел в том виде, в которой они были сформулированы в середине XVIII века, а потом сразу делается скачок к теориям, созданным в середине XIX века.

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

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

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

Размытие — базовый строительный блок множества эффектов постобработки в видеоиграх, без него не обходятся красивые современные GUI. Оно используется в эффектах Depth of Field, Bloom или панелях с эффектом матового стекла современных пользовательских интерфейсов.

Эффект Bloom — один из множества способов применения алгоритмов размытия

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

В оригинале статьи техники размытия реализованы в реальном времени благодаря использованию GPU и возможностям WebGL браузера.

Надвигающаяся угроза со стороны заточенных на криптографию квантовых компьютеров заставила срочно менять действующие примитивы асимметричной криптографии — обмен ключами (ECDH) и цифровые подписи (RSA, ECDSA, EdDSA) — которые уязвимы для квантового алгоритма Шора. Однако существующих симметричных методов криптографии (AES, SHA-2, SHA-3) или уровней их стойкости это не коснулось. ccc

В индустрии бытует заблуждение, что квантовые компьютеры вдвое ослабят безопасность симметричных ключей, и для обеспечения того же 128-битного уровня защиты потребуется перейти на 256-битные ключи. Это неточная интерпретация ускорения, которое несут в себе квантовые алгоритмы. Она не отражена ни в одном из нормативных стандартов и рискует отвлечь внимание от реально необходимой работы по переходу к постквантовой системе криптографии. Обычно это заблуждение происходит из недопонимания применимости другого квантового метода — алгоритма Гровера.

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

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

Сегодня я разберу исследование LLM-Independent Adaptive RAG: Let the Question Speak for Itself, в котором ученые из MWS AI, AIRI, Сколтеха и еще нескольких университетов предлагают решение этой проблемы через новый подход к adaptive retrieval, когда RAG запускается не автоматом, а только при необходимости, и для этого не нужна LLM.

Привет, Хабр! Меня зовут Иван Воробьев,  я работаю в команде рекомендаций VK Видео, AI VK. В данной статье хочу рассказать, как и зачем я переделывал систему построения I2I-рекомендаций. Поговорим о том, какие решения были поставлены в её основу, насколько они оправдались, а также причём тут якори и как они связаны со свежестью рекомендаций. 

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

Год назад я рассказывал, как Яндекс Карты научились учитывать рельеф и лестницы при построении пешеходных маршрутов. Но альтернативные варианты по-прежнему выглядели для пользователя как просто «ещё один путь, только дольше» — и люди не раздумывая выбирали самый быстрый. Теперь у каждого альтернативного маршрута появилось имя и характер: например, «Быстрый», «Прогулочный», «Оживлённый» или «Без лестниц».

Простые категории посчитать несложно. А вот «Прогулочный» и «Оживлённый» — это субъективные характеристики: в хорошую погоду хочется пройти через парк или вдоль набережной, а в тёмное время — по освещённым улицам, подальше от дворов и промзон. Для этого с помощью LLM мы обучили легковесную модель, которую и применили в сервисе. Как именно — читайте в статье. Сам путь разработки оказался совсем не «Быстрым» и далеко не «Прогулочным» — с тупиками и неожиданными поворотами там, где их не ждали.

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

Проверяем, может ли GPU-планировщик MPPI-Generic работать без глобального планера. Самодельный симулятор, контроллер с приоритетом угловой скорости, сравнение с State Lattice и RPP vs MPPI, справился, но есть нюансы.

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

Во многом красота математики заключается в том, что благодаря произвольному выбору можно связать две кажущиеся далёкими концепции. Впервые я увидел этот паттерн в вопросе на Math Stack Exchange. Его задал пользователь dwymark, а ответил на него Грег Мартин; вопрос связан с распределением простых чисел, а также с рациональными аппроксимациями .

Этот пользователь баловался с созданием графиков данных в полярных координатах, то есть нанесением точек в 2D-пространстве, но не по обычным координатам XY, а по расстоянию от точки начала координат, обычно называемому (радиус), и по углу прямой относительно горизонтали, обычно называемому «тета», .

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

Привет, Хабр! Меня зовут Алексей Васильев, я тимлид команды «Рекомендательные системы и персонализация» Sber AI Lab — Центра практического искусственного интеллекта Сбера. В нашей команде мы занимаемся исследованиями в области рекомендаций на последовательностях (sequential recommendations). Например, прослушивания музыки или просмотры карточек товаров можно представить как последовательность взаимодействий пользователя. А для моделирования последовательностей, как мы знаем, отлично подходят трансформеры: популярные варианты в рекомендациях — SASRec и BERT4Rec. Эти модели прекрасно справляются с задачей рекомендаций на основе взаимодействий, но они ничего не знают о самих товарах.

Допустим, пользователь покупает безлактозный йогурт и растительный сыр. У нас сразу появляется гипотеза: возможно, пользователь не переносит лактозу. Однако для sequential‑модели это не очевидный факт, а статистический паттерн, который нужно выучить из взаимодействий. Если данных мало, товары редкие или связи между ними плохо представлены в истории, то такой смысл легко потерять.

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

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

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

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

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

Для контроля за метриками в системе Monium существует механизм алертов. Проблема в том, что для многих рядов сложно заранее определить разрешённые пороги. А для некоторых рядов сделать это попросту невозможно. В результате контролировать такие временные ряды было довольно нетривиальной задачей.

Мы в команде ML Research в Городских сервисах Яндекса давно поняли, что руками такие системы не масштабируются. Нужна автоматика, которая сама фиксирует нормальное поведение метрики и засекает отклонения. Звучит как задача для тяжёлого ML, однако на бенчмарках мы доказали, что простая авторегрессия обгоняет сложные модели.

Давайте вместе пройдём путь от «Почему пороги не работают?» до рабочей системы детекции аномалий в общеяндексовой системе Monium и наблюдения за 800+ городами в Яндекс Такси с бенчмарками и конкретными цифрами.