Алгоритмы *

Я знаю многих программистов и руководителей в IT компаниях, которые недолюбливают математиков и в частности считают их далёкими от жизни идиотами из-за их утверждений в духе "нельзя отсортировать последовательность быстрее, чем за nlogn" -- ведь это очевидным образом неверно, есть же сортировка подсчетом и radix sort. Нюанс в том, что описанное выше -- это распространённая некорректная трактовка одной из ключевых теорем об алгоритмах сортировок, корректное утверждение выглядит так: "не существует алгоритма, который бы гарантированно находил перестановку n элементов, приводящую к возрастающему порядку, быстрее чем за nlogn используя только операции попарного сравнения". В этом утверждении больше слов, оно более сложно в плане когнитивного восприятия, ключевой момент обозначил жирным шрифтом, чувствуете разницу?

В статье хочу рассказать об этой теореме и ещё о двух, на которые я наткнулся когда вел занятия по информатике в 9-11 классах будучи студентом старших курсов. Эти теоремы для меня были удивительным открытием, радовался вне себя когда вывел сам одну из них - её я не встречал ни в одном учебнике по информатике. В последствии все три теоремы были найдены в недрах Кнута, но чёрт побери, их поиск был сложнее, чем вывод!

Если я ещё не убедил Вас прочитать статью, то вот моя последняя попытка: в статье объясню почему пузырёк -- это бесполезная фигня, но внезапно практически также работающая сортировка вставками -- это супер важная сортировка, являющаяся частью std::sort в MSVC, GCC и Clang. Расскажу, каким интересным свойством оптимальности обладает сортировка выбором, являющаяся в теории такой же неэффективной как пузырёк.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Введение

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

В продолжение части 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 не самый подходящий для этого язык, зато мы рассмотрим его различные возможности, о которых вы могли и не подозревать.

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