Алгоритмы *

Вчера (27 ноября) Хабр устроил «Авторский огонёк».

Было очень интересно, и меня задело одно утверждение докладчика. Оно заключалось в том, что ИИ может помочь писать простые куски кода, но не работает со сложными вещами. Таким образом, большие языковые модели уподобляются программисту-джуну.

Решил с утра накатать об этом статью, опираясь на свои знания и опыт в вычислительной математике (в прошлом занимался моделированием, а последние несколько лет преподаю вычислительную математику в МФТИ), оцените, что получилось.

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

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

Fizz Buzz — это игра с числами, которая стала неожиданно популярной в мире компьютерного программирования в качестве простой проверки базовых навыков. Правила игры просты: игроки вслух произносят по порядку числа, начиная с единицы. Если число делится на 3, игрок должен сказать вместо него «Fizz». Если число делится на 5, он должен сказать «Buzz». Если оно делится и на 3, и на 5, игрок говорит «FizzBuzz». Вот типичная программа на Python, выводящая нужную последовательность:

for n in range(1, 101):

if n % 15 == 0:

print('FizzBuzz')

elif n % 3 == 0:

print('Fizz')

elif n % 5 == 0:

print('Buzz')

else:

print(n)

А вот её вывод: fizz-buzz.txt. Можно ли усложнить эту программу? Слова «Fizz», «Buzz» и «FizzBuzz» повторяются в этой последовательности периодически. А что ещё у нас есть периодического? Тригонометрические функции! Возможно, нам удастся при помощи этих функций закодировать все четыре правила последовательности в выражении в аналитическом виде. Именно эту задачу мы и исследуем в статье, получив в конце дискретный ряд Фурье, который может получить любое целочисленное n и выбрать для печати соответствующий текст.

В программировании мы привыкли торговаться временем против памяти, но есть ещё один, менее очевидный, компромисс — между тем, что система в принципе умеет выражать, и тем, что о ней потом вообще можно строго сказать. Машины Тьюринга, PDA и DFA, Rust и Python, SAT и SMT, системы типов, макросы и метапрограммирование — всё это разные точки в одной и той же решётке «выразительность против разрешимости», просто по разным осям.

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

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

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

В статье описано как эту задачу решать действительно быстро - за линейную сложность.

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

Разбираем, как привычные «найди максимум при таких-то условиях» превращаются в компактные декларативные модели, зачем вообще нужны такие упражнения, что они говорят о собеседованиях и о нашем отношении к алгоритмам — и где у подхода с MiniZinc/constraint solving проходят естественные границы.

Привет, Хабр! За последний год стало ясно, что использование нескольких LLM в агентном режиме приносит существенно больше пользы, чем простая сумма их компьюта по отдельности. Гибкость, распределение ролей и активное взаимодействие моделей позволяет достичь значительных успехов в самых различных задачах, включая создание полезных цифровых ассистентов.

Построением таких систем заняты многие команды по всему миру. Чтобы ускорить прогресс в этом направлении и помочь коллегам, мы в группе «Мультимодальные архитектуры ИИ» AIRI создали новый фреймворк под названием MAESTRO — Multi‑Agent Ecosystem of Task Reasoning and Orchestration. Мы представили его на конференции AI Journey 2025, которая прошла в Москве на прошлой неделе.

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

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

Чтобы глубже и результативнее понять градиентный шум, мы сначала изучим его одномерную версию (в литературе этот случай обычно не рассматривается), а затем медленно пойдём вверх по лестнице измерений в сторону усложнения задачи. Эту тему мы будем рассматривать с точки зрения графического процессора (GPU), а не с точки зрения обычного ЦП. Все примеры кода и анимации, приведённые в этой статье, реализованы на WebGL2/GLSL (надеюсь, это будет не слишком сильно сказываться на производительности). Примеры должны работать на большинстве современных устройств.

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

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

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

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

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

Игра - Лабиринт

Не откладывая задачу в долгий ящик, представляю Вам прототип игры "Лабиринт".  На рисунке 1, представлен пример поля лабиринта, основанного на CCA. Справа от поля имеется легенда с описанием цветов ячеек.

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

В статье я расскажу про виртуальную очередь заказов, которую мы сделали в приложении Яндекс Go. Напомню кратко, как устроен поиск водителей в Такси, поговорим про предпосылки внедрения очереди, посмотрим на то, как устроена очередь и, наконец, обсудим результаты. 

Привет, Хабр!

Cегодня поговорим о, наверное, самом серьезном этапе собеседования — live‑coding. На этом этапе вас просят писать код в реальном времени, под пристальным взглядом интервьюера.

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

Постановка проблемы. Современные промышленные предприятия требуют принципиально новых решений, направленных на прогнозирование отказов работы оборудования и своевременное устранение нештатных аварийных ситуаций, управления затратами на ремонт, а также оптимизации и улучшения стратегий технического обслуживания. Существующие автоматизированные системы прогнозируемого обслуживания имеют различные функциональные ограничения. Это требует разработки новых архитектурных решений для создания интеллектуальных систем, способных обрабатывать большие объемы разнородных данных в режиме реального времени, прогнозировать отказы с высокой точностью и оптимизировать процессы плана обслуживания, в тесной взаимосвязи с работой устройств промышленного Интернета вещей в условиях использования новых технологий периферийного искусственного интеллекта. Данная работа посвящена исследованию возможности применения большой языковой модели OpenThinker2-32B, как вспомогательного инструмента для автоматизированной системы прогнозируемого обслуживания многостадийных технологических процессов. Данная модель может быть использована в реализации следующих функций автоматизированной системы: анализ исторических данных; прогнозирование оставшегося срока службы оборудования; подготовка данных для снижения факторов неопределенности данных для улучшения прогнозов; подготовка экспертных заключений; оптимизация расписаний по техническому обслуживанию промышленного оборудования.

Цель работы. Изучить возможность применения и адаптации большой языковой модели OpenThinker2-32B, как дополнительного и вспомогательного инструмента, применяемого для повышения эффективности работы автоматизированных систем прогнозируемого обслуживания многостадийных технологических процессов для малых и средних промышленных предприятий. Это позволит решить следующие задачи: выполнить анализ исторических данных; с помощью алгоритмов, разработанных на основе теории свидетельств Демпстера-Шафера снизить факторы неопределенности произвести прогнозирование отказов, а также подготовить экспертные рекомендации по оптимизации расписаний и процессов технического обслуживания промышленного оборудования. Также необходимо разработать алгоритмы информационного взаимодействия для каждой из задач, и определить положение большой языковой модели в предложенной концепции конвергентной архитектуры автоматизированной системы прогнозируемого обслуживания для повышения точности прогнозов и возможности ее интеграции с экспертными, аналитическими, прогнозными системами и системами поддержки принятия решений.

Обожаю игры серии GTA (все, кроме четвертой части). Я бы даже сказал, что многое в них прекрасно: разнообразие сюжетных миссий, выбор транспорта, классные диалоги, тонкая ирония, саркастичный юмор, высмеивание проблем общества, свобода действий, возможность устроить локальный апокалипсис. Однако все это портит поведение ботов-водителей, которые словно намеренно бросаются наперерез игроку, чтобы усложнить ему жизнь. Но так ли это? Действительно ли поведение NPC на дорогах GTA заскриптовано так, чтобы мешать геймерам? Прошу под кат — в поисках правды будем подглядывать за ботами и залезать туда, куда Рокстары не хотят нас пускать.

Краткое и доступное руководство по базовым алгоритмам на графах: BFS, DFS, топологической сортировке и алгоритму Дейкстры. Чёткие объяснения, примеры и код на C++ — для тех, кто хочет быстро и уверенно освоить фундамент графовых алгоритмов.

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

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

В этой статье я расскажу основные особенности очистки памяти и рассмотрю, как она взаимосвязана с командой TRIM. Детали под катом.

Задача Эдсгера Дейкстры о философах – великая задача великого программиста. Уж сколько лет, а она актуальна. Решая ее, прикасаешься к этому величию. И вот, перефразируя известное, «давно не было такого и вот опять», можно познакомиться с ее «новым прочтением» на Хабре[1].

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

Познакомился с проблемой обедающих философов – Dinning Philosopher Problem (DPP), я более двадцати лет тому назад (про DPP см. [2]). Результатом стала статья, в которой философы выполняли поставленную задачу, как минимум, не хуже, чем классические алгоритмы сортировок[3]. Позднее был сделан доклад на конференции по параллельным вычислениям в Саратове, где на суд научной общественности была предъявлена модель автоматных параллельных вычислений и пример ее приложения - задача Дейкстры[4].  

Замечание 1. В рамках обсуждения статьи на Хабре было проигнорировано  предложение поручить сортировку философам. Зря, конечно, т.к. надо же как-то убедиться, что предлагаемое решение работает хотя бы в первом приближении. К примеру, тот же DeepSeek, моментально выдавший свое решение DPP, так и не смог заставить их сортировать.

Не знаю, считается ли данная задача решенной, но то, с чем я знаком, по большей части беглое рассмотрение проблем, которые она отражает. У задачи есть теория, которая представлена монографией Хоара[5], или моделями сетей Петри у Питерсона[6] и В.Е. Котова[7] или другими подобными публикациям. Но, повторюсь, все это по большей части достаточно краткий анализ свойств модели и/или даже конкретного решения. Статья на Хабре из этой же серии. Все это ни как не окончательное решение описываемых ею проблем параллелизма. Правда, может, [авторами] вопрос так и не ставился, но все же ответ на него весьма желательно иметь.

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

Приветствую! Я, Егор Ершов, руководитель группы «Цветовая вычислительная фотография» в AIRI и заведующий сектором репродукции и синтеза цвета ИППИ РАН, продолжаю выкладывать статьи по мотивам своих лекций по вычислительной фотографии. Наша глобальная задача, напомню, разобраться, как сделать так, чтобы камера сотового телефона достаточно хорошо смогла уловить цвета, а монитор или принтер — их передать. 

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

Приятного чтения!