Как стать автором
Поиск
Написать публикацию
Обновить
103.51

Алгоритмы *

Все об алгоритмах

Сначала показывать
Порог рейтинга
Уровень сложности

Мечтают ли диффузионки о 3D-алайнменте, или что мы планируем рассказать на грядущей ICLR

Уровень сложностиСложный
Время на прочтение4 мин
Количество просмотров893

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

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

Читать далее

Как Яндекс запускает роботов-доставщиков в новых районах и городах

Время на прочтение12 мин
Количество просмотров5.2K

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

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

Читать далее

Эпилог. Создание ботов для торговли криптовалютами и акциями (часть третья, заключительная)

Уровень сложностиПростой
Время на прочтение9 мин
Количество просмотров11K

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

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

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

Читать далее

Симуляция воды над рельефом

Уровень сложностиПростой
Время на прочтение18 мин
Количество просмотров4.3K

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

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

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

Читать далее

От каскадных моделей до картинок в 4к: как эволюционировали диффузионки

Время на прочтение19 мин
Количество просмотров6.7K

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

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

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

Читать далее

SQL HowTo: динамическое программирование (Advent of Code 2024, Day 19: Linen Layout)

Уровень сложностиПростой
Время на прочтение9 мин
Количество просмотров1.2K

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

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

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

Читать далее

Ну заяц погоди! Или противоракетная оборона для самых маленьких евреев и не только. Часть 2

Уровень сложностиПростой
Время на прочтение12 мин
Количество просмотров4.2K

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

Читать далее

Реализация постквантовых алгоритмов на Java и Go

Время на прочтение4 мин
Количество просмотров4K


В последнее время в СМИ много публикаций о новых квантовых компьютерах, которые представляют угрозу для современной криптографии. Например, недавно Google сообщила о разработке квантового процессора Willow, который в специально сформулированной задаче превышает производительность самого мощного суперкомпьютера в септиллион раз (септиллион = 1025).

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

Сортируем сотни млн строк в разы быстрее библиотечных алгоритмов. А не замахнуться ли нам на ммм… на O(n)?

Уровень сложностиСредний
Время на прочтение14 мин
Количество просмотров16K

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

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

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

Читать далее

О новых алгоритмах хеш-таблиц

Время на прочтение1 мин
Количество просмотров17K

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

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

Читать далее

Кривая эластичности в девелопменте и почему её не существует

Время на прочтение5 мин
Количество просмотров1.1K

Когда речь заходит об ожиданиях от динамического ценообразования (ДЦО), многие застройщики представляют себе безотказную машину, которая 24/7 мониторит спрос, в реальном времени выдаёт оптимальные цены, обеспечивает максимальную прибыль и заставляет конкурентов нервно курить в сторонке. Но, увы, суровая реальность напоминает, что не всё в жизни так просто.

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

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

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

Читать далее

Как эффективно бороться с галлюцинациями нейросетей

Уровень сложностиСредний
Время на прочтение5 мин
Количество просмотров3.9K

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

Читать далее

Как пройти алгоритмическое собеседование: полный гид по алгоритмам, сложностям и стратегиям

Время на прочтение31 мин
Количество просмотров44K

Не тратьте время на задачи – сначала разберитесь в основах. В статье:

1. Как проходят собеседования (ВАЖНО!)
2. Big O, оценка сложности алгоритмов
3. Популярные техники: два указателя, DFS, динамическое программирование и другие
4. Какие задачи решать, чтобы пройти в Яндекс

Читаем, практикуемся, получаем оффер!

Читать далее

Ближайшие события

Структуры данных для подготовки к собеседованиям по алгоритмам

Уровень сложностиСредний
Время на прочтение32 мин
Количество просмотров19K

Хочешь пройти собеседование в Яндекс? Без этих структур данных не обойтись!

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

Готов ли ты к техническому интервью? Проверь себя!

Читать далее

Самые быстрые алгоритмы распределенного и асинхронного обучения (с точки зрения теории)

Уровень сложностиСложный
Время на прочтение9 мин
Количество просмотров4.8K

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

За последние 2 года нам удалось сделать несколько открытий в асинхронных методах оптимизации, которые мы изложили в 5 статьях [1–5] на NeurIPS и ICLR. В этой статье я расскажу, в чём заключаются особенности распределённого обучения и что нового привнесли в него мы с точки зрения теории.

Читать далее

Алгоритмы манипуляций с битами

Уровень сложностиСредний
Время на прочтение13 мин
Количество просмотров17K

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

Читать далее

Я заставил новую модель Claude 3.7 Sonnet пройти собес по алгоритмам

Уровень сложностиПростой
Время на прочтение5 мин
Количество просмотров8.1K

Недавно в мире GenAI появились захватывающие новости: компания Anthropic представила новую языковую модель Claude 3.7 Sonnet. Эта модель объединяет в себе высокую скорость реакции и способности "глубокого" рассуждения (deep reasoning), что делает её одной из самых универсальных и продвинутых моделей на рынке коммерческих LLM. Благодаря инновационному подходу к гибридноcти, Claude 3.7 Sonnet способна как быстро отвечать на запросы, так и предоставлять подробное пошаговое обоснование своих выводов в зависимости от выбранного режима.

Читать далее

После прочтения сжечь. Или алгоритмы обработки данных вслепую (oblivious)

Уровень сложностиСредний
Время на прочтение10 мин
Количество просмотров2K

То есть:

Привет, Хабр! Я – Петр, эксперт по ML/AI (и не только) в Skillbox (и не только), а ещё – CEO межбанковской скоринговой платформы Bloomtech. Так уж вышло, что я неплохо разбираюсь в разных PET (Privacy-Enhancing Technologies) и уже писал на хабре про совместные конфиденциальные вычисления. Сегодня повышаю градус и рассказываю про магию следующего порядка: слепую (забывчивую) передачу или oblivious transfer. Как обычно, на примере.    

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

Читать далее

Почему QR-коды в верхнем регистре меньше, чем в нижнем?

Уровень сложностиПростой
Время на прочтение2 мин
Количество просмотров18K

Взгляните на эти два QR-кода. Отсканируйте их, если хотите: обещаю, в них нет ничего опасного.

Слева HTTPS://EDENT.TEL/ в верхнем регистре, а справа — https://edent.tel/ в нижнем.

Можно чётко заметить, что слева QR-код «меньше», то есть в нём меньше битов данных. Оба ведут на один и тот же URl, единственное различие заключается в регистре.

Что здесь происходит?

Читать далее

SQL HowTo: поиск пути и дихотомия (Advent of Code 2024, Day 18: RAM Run)

Уровень сложностиПростой
Время на прочтение8 мин
Количество просмотров1.2K

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

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

Сегодня напишем для решения простую реализацию алгоритма Ли и дихотомии.

Читать далее

Вклад авторов