Алгоритмы *

Введение

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

В продолжение части 1 привожу анализ заполнений квадрата со стороной 45 квадратиками размера от 1 до 9 (1x1 - 1 шт., 2x2 - 2 шт., 3x3 - 3 шт., ..., 9x9 - 9 шт.).

Начнём с простого. Несложно показать, что квадратик размера 1 не может стоять у границы и даже на расстоянии 1 от границы. Этот факт я учитывал при поиске вариантов, чтобы немного сократить перебор.

Если выстроить квадратики размера 9 вдоль двух соседних «стенок», то мы сведём задачу поиска заполнения к задаче для . Таким образом получается, что около 4% заполнений для получаются напрямую из заполнений для (у нас есть 4 способа выбрать 2 соседние «стенки»).

Привет! Меня зовут Милена Газдиева, я являюсь научным сотрудником Института AIRI, а также инженером-исследователем и аспиранткой Сколтеха. Мои научные интересы лежат в области разработки генеративных моделей на основе оптимального транспорта (optimal transport, ОТ) и их приложений к различных задачам. Мы с коллегами добились успехов в повышении устойчивости таких моделей, и одна из наших статей по этой теме была принята на престижную конференцию по искусственному интеллекту ICLR 2025, которая в этом году будет проходить в Сингапуре. Сегодня я расскажу об этой работе, в рамках которой мы разработали метод оценки барицентров (взвешенных средних) распределений, устойчивый к различным выбросам и дисбалансам в данных.

Что это означает и зачем нужно — читайте далее.

Всем привет! Меня зовут Сергей Хорошеньких, я руковожу службой исследований и разработки в Яндекс Доставке. Наша команда изучает и внедряет алгоритмы, которые повышают операционную эффективность сервиса.

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

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

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

В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.

Возможно, SQL не самый подходящий для этого язык, зато мы рассмотрим его различные возможности, о которых вы могли и не подозревать.

Дважды применяем волновой алгоритм для нахождения единственного кратчайшего пути и самосоединение для поиска "читов".

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

Равенства следующие:

Некоторые, возможно, ещё помнят, что в углублённой школьной (или вузовской) программе встречалось равенство . Собственно, оно тут и применяется. Кстати, согласно Википедии, это равенство называется тождеством Никомаха, древнегреческого математика (около 60-120 гг. н.э.).

На основе этих равенств можно сформулировать задачу:

Сколько существует способов расположить 1 квадратик со стороной 1, 2 квадратика со стороной 2, 3 квадратика со стороной 3, … , 8 квадратиков со стороной 8, 9 квадратиков со стороной 9 в квадрате со стороной 45, чтобы они не пересекались?

Всем привет, меня зовут Евгений Мунин. Я Senior ML Engineer в Ad Tech в платформе ставок для рекламы и автор ТГ канала ML Advertising. В данной статье мы поговорим об одном из способов повышения узнаваемости брендов в спорте, а точнее виртуальной рекламе. Разберем размещение рекламных баннеров на видео и напишем пример на Python и OpenCV, где разместим логотип Adidas с использованием алгоритма детектирования ключевых точек SIFT и гомографии для искажения баннера под перспективу.

Некоторое время назад я попробовал найти формальное доказательство безопасной работы с памятью, которое реализовано в Rust, но так и не смог его найти. После чего у меня сложилось впечатление, что доказательство в формальном виде и вовсе отсутствует, а вся концепция безопасного управления памятью на основе "владения и заимствования" формально не доказана и держится только на честном слове.

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

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

Привет, Хабр! Меня зовут Нина, я работаю инженером исследователем в AIRI, где мы с моими коллегами активно исследуем возможности генеративного ИИ. Особое место в нашей рабочей повестке занимает применение диффузионных моделей к различным задачам.

Не так давно мы получили приятную новость: нашу статью по семантическое выравнивание при генерации 3D‑моделей приняли на ICLR. В ней мы нашли способ, как построить выровненную генерацию 3D‑объектов, используя гайданс предобученной диффузионной модели, чтобы сделать редактирование или гибридизацию более надёжными. В этой статье хотелось бы кратко пересказать суть нашей работы.

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

Но несмотря на такой большой объём работ, весь процесс весьма интересный. Именно о нём я и расскажу в этой статье. Под катом — история о том, как мы поставили робота «на колёса» в Казахстане, показывали ему город для записи данных и учили объезжать арыки.

Предыдущий пост: https://habr.com/ru/articles/677290/

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

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

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

Я одержим генерацией рельефа, играми на основе сеток, симуляциями и тому подобным. И часто во всём этом присутствует вода, или, по крайней мере, её присутствие кажется естественным.

Допустим, вы генерируете карту для стратегической игры, но не хотите, чтобы границы карты были заполнены непроходимой пустотой (как в олдскульных RTS). Разве не будет здорово, если граница будет заполнена водой, как на этой карте из одного моего заброшенного проекта?

На дворе 2025 год. Генерацией картинок и видео в интернете больше никого не удивишь. Генеративный контент повсюду, а его качество настолько высоко, что бывает трудно отличить синтетическую картинку от реальной.

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

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

В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.

Возможно, SQL не самый подходящий для этого язык, зато мы рассмотрим его различные возможности, о которых вы могли и не подозревать.

Используем динамическое программирование для подсчета количества вариантов размещений.

Продолжение статьи, созданной в процессе решения задачи о погоне, для школьников. Очков Валерий Федорович, предложил мне решить методом структурного моделирования задачу погони волка за зайцем. И в первой части именно эта задача подробно и разобрана. Многие читатели справедливо спрашивали, а причем здесь евреи и ракеты?  В этой части я покажу, как можно связать школьную задачу про бегающего по кругу зайца с израильской противоракетной системой купол. 

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

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

И, рассуждая совсем о другой проблеме, но где имеет место быть сортировка большого количества объектов, в плане алгоритма сортировки объектов, меня осенило. Быстренько проверил кодом — ого, работает! Рассчитываю, что вам понравится.

Хотелось бы прокомментировать публикацию Ильи Кабанова в Медузе по поводу новых разработок в алгоритмах хеширования: "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.

В заключение, отвечая Илье Кабанову: к "ускорению интернета" эти теоретические алгоритмы не приведут :)