Обновить
220.17

Алгоритмы *

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

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

Процедурная генерация двухмерной полигональной карты

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

Привет Хабр ! Это моя первая статья на тему процедурной генерации. Здесь я рассмотрю конкретную задачу по генерации, её решение и опишу ключевые использованные принципы. Пишу эту статью для того, чтобы поделиться идеями и опытом, которых мне не хватало, когда я взялся за дело две недели назад. Я не буду делать полный разбор проекта, а лишь опишу и визуализирую принцип.

Читать далее

Разгон Мандельброта: SIMD с бубнами, OpenMP и CUDA

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

Построение множества Мандельброта — классический пример чрезвычайно параллельной задачи (embarrassingly parallel problem).

На первом курсе я впервые столкнулся с такой проблемой: тогда мы изучали SIMD-инструкции в курсе архитектур вычислительных систем. Эта тема сразу меня увлекла, и я захотел углубиться в дальнейшие оптимизации, но в течение семестра мне не хватало ни времени, ни знаний. Спустя год я решил восполнить этот пробел.

Вначале мы разберем наивную реализацию, поиграемся с интринсиками (intrinsics) и, не теряя переносимости, заставим компилятор генерировать нам SIMD-инструкции. Далее добавим многопоточность и в заключение обесценим все наши старания несколькими строчками на CUDA.

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

Читать далее

Как передать произвольное количество бит, передав 2 бита

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

Недавно прочитал статью на Пикабу про бесконечное сжатие, где предлагалось создать словарь 3-х байтовых блоков, и представлять информацию в виде ссылок на эти блоки. Понял что выигрыша в этом нет, но идея передавать не саму информацию, f что-то другое, меня зацепила. Начал размышлять, допустим демон на дне океана перекусывает нитку оптоволокна и смотрит как туда сюда бегут 1 и 0. Какой в них смысл? Одно и тоже. И правда как извлечь смысл из этого однообразия. А здесь вступают в игру фактор времени и договоренности. То есть добавляются дополнительные измерения о которых демон не знает. Стартовые, стоповые биты, длина пакета.

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

Читать далее

Дедупликация объявлений: как мы боремся с одинаковыми размещениями

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

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

Материал будет полезен ML-инженерам и специалистам по обработке данных, которым интересно, как мы подошли к решению этой задачи: какие методы использовали, какие проблемы возникли и как мы их преодолели.

Читать далее

Армения посреди Америки, Китая и России: отчет с EDA Connect 2025

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

Мысль, что Армения удобна тем, что соединяется и с Америкой, и с Китаем - высказал мне один из китайских участников конференции EDA Connect. А мысль, что Армения соединяется еще и с Россией - возникала естественно при просмотре докладов о логическом синтезаторе, статическом анализаторе и верификации с помощью UVM.

Помимо докладов, при конференции прошел хакатон по Verilog и FPGA, на который пришли студенты из Ереванского университета, русско-армянского университета, американо-армянского, французско-армянского, европейско-армянского, и других университетов. Занятно, что второй день хакатона проходил в комнате напротив зала, где большое начальство встречалось с Премьер-Министром Армении. Один из студентов хакатона перепутал дверь, и его перенаправила секьюрити.

Читать далее

Сортировка слиянием на CUDA

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

Я решил изучить, как повысится производительность алгоритмов сортировки при их реализации на CUDA. Моя цель — понять, как можно использовать мощь параллельных вычислений для ускорения алгоритмов сортировки.

В качестве тестового я возьму алгоритм сортировки слиянием (merge sort), потому что он удобно разбивает задачу на меньшие подзадачи с двумя равными половинами, что хорошо подходит для параллельных вычислений.
Читать дальше →

А не пора ли нам подкрепиться?

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

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

Читать далее

Камеры трясутся, шум зашкаливает, а сравнивать нужно: как справляются алгоритмы?

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

Каждый день миллионы изображений, видео и аудиофайлов загружаются в интернет. Мы смотрим фильмы, слушаем музыку, листаем соцсети, даже не задумываясь о том, какие алгоритмы стоят за тем, чтобы контент отображался корректно и не повторялся. Но что, если вам нужно сравнивать медиаконтент автоматически? Как понять, одинаковые ли две фотографии, если одна немного темнее? Как сравнить два видео, если они сняты под разными углами? А что делать, если вам нужно найти дубликат аудиофайла, но на одной записи есть шум?

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

Читать далее

Программный код в Big data и Power law

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

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

Для процессов SOC характерно отсутствие управляющих параметров и масштабная инвариантность. Универсальность сложных процессов SOC со степенным законом Power law имеет тот же характер, как и универсальность простых линейных систем, не обладающих масштабной инвариантностью, по отношению к закону нормального распределения вероятности.

Зависимость от масштаба возникает при аналого-цифровом преобразовании битов в позиционную систему счисления и проявляется в законе нормального распределения вероятности в виде дисперсии и математического ожидания. Потеря масштабной инвариантности в позиционной системе счисления компенсируется приобретением принципа причинности. Например, в Древнем Риме, где была принята непозиционная система счисления, вычисляли, что «после того - не вследствие того» и сильно удивились бы истории с падающим на Ньютона яблоком.

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

Читать далее

SQL HowTo: моделирование против подсчета (Advent of Code 2024, Day 21: Keypad Conundrum)

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

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

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

Пробуем смоделировать преобразования строк "в лоб", а потом - организовать подсчет и решить более сложную задачу в разы быстрее простой!

Читать далее

Быстрая свёртка множеств (алгоритм)

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

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

Статья будет интересна тем, кто интересуется нетривиальными, но красивыми алгоритмами!

Читать далее

Обновление SPA приложения в браузере пользователя Node/React

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

Всем привет. Мне читатели иногда присылают сообщения с одним и тем же вопросом, что ты же Software Engineer и Solution Architect, но почти все твои статьи касаются бизнеса, менеджмента, процессов, управления командами и так далее. Но нет статей технического характера, про разработку и создание разных фич (feature) для проекта. Причина по которой это происходит в том, что весь интернет забит информацией о том, как программировать, но очень мало информации о том, что именно программировать, и о том, что за пределами кодинга огромное количество нерешенных проблем, которые нивелируют весь процесс программирования. Но сегодня я расскажу об одной фиче, которая может оказаться очень полезной для многих.

Читать далее

Компактные структуры данных

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

Введение


Несколько месяцев назад в поисках идей по ускорению кода я изучал множество научных статей по computer science. Не буду притворяться, что хорошо их понимал, но меня не пугает непонятное, и я готов признать своё невежество1. Я обнаружил статью, написанную пятнадцать лет назад2, в которой было множество новых для меня концепций. Мне никак не удавалось в них разобраться.

Что же делать дальше? Можно искать другие статьи, чтобы они заполнили мои пробелы. Это рискованное предприятие, потому что они могут запутать ещё больше, но избежать этого нельзя. Я нашёл статью с нужной структурой данных, в которой упоминался исходный код с веб-сайта. Код был написан на C++, а я работаю на Rust, но решил, что всё равно стоит на него взглянуть. Однако зайдя на сайт, я не обнаружил там ресурс, поэтому я написал владельцу веб-сайта, который оказался преподавателем computer science.

Этот преподаватель (Гонсало Наварро) очень тепло меня принял и сразу же ответил мне3 4. И только в процессе общения с ним я осознал, что видел его фамилию на множестве статей в этой области. Оказалось, я познакомился с одним из специалистов мирового уровня в области компактных структур данных (succinct data structure). Невежество может завести очень далеко.

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

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

Я решил, что стоит немного о них рассказать.
Читать дальше →

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

Неизвестный библейский алгоритм кластеризации

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

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

Читать далее

Как я решал задачу 2025 года. Часть 2. Анализ интересных закономерностей

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

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

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

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

Читать далее

Как несбалансированный оптимальный транспорт помог нам сделать поиск барицентров распределений устойчивым

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

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

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

Читать далее

Доставка день в день: погружение в базовые алгоритмы поиска и назначения курьеров в Яндекс Доставке

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

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

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

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

Читать далее

Зависимость от трейдинга: как миллионы людей теряют годы и состояния на торговле

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

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

Читать далее

SQL HowTo: кратчайший путь «туда и обратно» и его самосоединение (Advent of Code 2024, Day 20: Race Condition)

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

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

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

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

Читать далее

Как я решал задачу 2025 года. Часть 1

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

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

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

2025 = 45^2 = (1+2+...+9)^2 = 1^3 + 2^3 + ... + 9^3

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

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

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

Читать далее

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