Алгоритмы *

Привет, Хабр! Меня зовут Георгий Семёнов, в VK я занимаюсь разработкой в команде инфраструктуры рекомендательных систем, а в Университете ИТМО начинаю свой аспирантский путь в области децентрализованных коллаборативных сред.

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

Если вы учились программировать в конце 80x-начале 90х, то наверняка делали это на ZX Spectrum, БК-0010 или MSX. Во всех этих компьютерах был встроенный язык програмирования. Кто-то начинал сразу с машинных кодов Радио-86РК. В любом случае первыми программами скорее всего были игры.

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

Работа со строками в С++ - зачастую больная боль.

Однако за 25 лет я сумел найти лекарство от этой боли и после 13 лет разработки и испытаний готов поделиться им со всеми страждущими.

simstr — библиотека для использования строк в C++, в которой пишется легко и удобно, а выполняется быстро и оптимально.

Решение первого соревнования на kaggle титаник с помощью библиотеки от яндекса catboost. Два способа: обычная модель и второй: с перебором гиперпараметров с помощью randomizedsearch. Сравнение результатов.

Библиотека функций к Script-fu

В принципе реализация представленная в файле obj4.scm и описанная ранее, меня вполне устраивала. Я реализовал там всё что хотел от объектной системы: определения классов и обобщённых функций, множественное наследование, статические поля класса. Но вот какое-то маленькое зёрнышко сомнения, мешало мене оставить этот проект. А всё ли я сделал для ускорения работы системы? И дело даже не в том, что какие то нехорошие люди из проекта GIMPа обрезали возможность для Script-fu загружать расширения, что не даёт возможности быстро рассчитать хеш-код символов(а то и вовсе заменить хеш-таблицы сишной реализацией). Нет. Для себя я спокойно перекомпилирую Script-fu и буду пользоваться всеми преимуществами предоставляемыми настоящей tinyscheme. Но что же можно сделать ещё, чтобы улучшить скорость работы ОО системы? А может и не только скорость.

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

Так родился APL — сначала как академический инструмент для описания алгоритмов в книгах (например, в его работе "A Programming Language" 1962 г.), постепенно эволюционировавший в исполняемый язык.

Но причём здесь 2025-й год спросите вы?

Data Science: APL опередил NumPy/Pandas на 40 лет — матричные операции здесь вшиты в ядро.

Обучение: Лучший способ понять SVD или преобразование Фурье — записать их в APL.

Прототипирование: Проверить идею можно быстрее, чем ChatGPT сгенерирует ответ.

Почему об этом мало говорят? 

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

Все примеры — на Python. В предыдущей статье я показывал написание бота и бектест кода, который просто выдаёт сухие сделки и реализованную прибыль в %. Однако существует много разных параметров и переменных стратегии, без которых ее использование обычно убыточно.

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

Привет, Хабр! Сегодня я расскажу про реализацию матричного умножения и особенности разработки для GPU. Познакомлю вас с устройством GPU, объясню, чем отличается программирование от привычного для CPU, какие нюансы нужно учитывать для эффективной реализации операций GEMM. А затем сравним производительность разных подходов к реализации.

Образовательные программы компьютерных наук и информатики обязательно включают курс алгоритмов, это элегантные решения сложных проблем. Например, одна из самых интересных проблем комбинаторной оптимизации — задача коммивояжёра (TSP, travelling salesman problem). Суть в поиске самого выгодного маршрута, проходящего через указанные точки ровно по одному разу. Сложность задачи при точном решении брутфорсом составляет O(n!). И для неё тоже придумано несколько элегантных алгоритмов. Хотя поиск самого эффективного продолжается до сих пор.

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

Привет! При решении контестов я нашёл интересную задачу по теме динамического программирования.
Постановка задачи: Необходимо найти наибольшую общую возрастающую подпоследовательность двух массивов.

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

Полный разбор создания алгоритмического трейдинг-бота с использованием индикатора Bollinger Bands, кластерных сигналов и API Bybit. 1700% прибыли за год использования.

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

Если бы меня попросили назвать слово, которое лучше всего подходит для прогноза осадков, я бы с уверенностью выбрал «сложность». В осадках она подстерегает нас всюду: от способов прогнозирования до оценки качества полученного прогноза. Потому в научных статьях про нейросетевой прогноз погоды (GraphCast, Pangu Weather, Aurora и т. д.) осадки или совсем не участвуют, или прогнозируются раз в 6 часов без упоминания о метриках. Либо же создаётся локальная модель под регион (например, MetNet для США).

В Яндекс Погоде мы используем множество ML‑моделей в рамках наших технологий прогноза Метеум и OmniCast, постоянно их улучшаем и постепенно заменяем на более продвинутые, повышая качество прогноза для наших пользователей. Недавно мы научились прогнозировать грозы, а до этого — улучшили прогноз температуры за счёт использования пользовательских метеостанций.

Меня зовут Стефеев Дмитрий, я разработчик группы ML и качества прогноза в Яндекс Погоде. Сегодня я и моя команда хотим представить новые модели для прогноза осадков и рассказать, почему мы на них перешли и как этот переход повлиял на качество.

С развитием всемирной паутины особую популярность набирают децентрализованные системы, основанные на одноранговых (P2P, пиринговых — эти термины являются синонимичными) сетях. В отличие от традиционных централизованных клиент-серверных моделей, где центральным звеном выступает сервер, обслуживающий клиентов, в одноранговых (децентрализованных) сетях все участники равноправны — здесь отсутствует иерархия и выделенный сервер. Любой участник сети может обмениваться информацией с любым другим, при условии соблюдения правил, или протоколов, используемых в таких сетях.

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

В основе любой ИНС — инерциальный измерительный модуль (IMU). Типичный IMU включает три взаимно перпендикулярных акселерометра и три гироскопа, иногда ещё три магнитометра (dewesoft.com). Акселерометры измеряют специфическую силу — разницу между истинным ускорением и ускорением свободного падения. Гироскопы измеряют угловую скорость. Магнитометры оценивают вектор магнитного поля Земли и позволяют корректировать курс. Такой 9‑осевой датчик иногда называют «AHRS» — системой ориентации и направления (attitude and heading reference system). В нашем проекте используется MEMS‑IMU с 6 степенями свободы и встроенным термодатчиком.

Условия задачи

Сценарий:  

У нас есть e-commerce платформа, состоящая из:

• веб-приложения,

• брокера сообщений,

• бэкенда.

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

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

Проблема:  

Клиенты могут:

• добавлять несколько товаров в корзину одновременно,

• отправлять несколько заказов.

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

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

Необходимо:

• Выявить процессы, которые происходят,  

• На основе этих процессов отобразить схему (sequence diagram) взаимодействия,  

• Предложить 2 способа оптимизации, чтобы избавиться от текущих проблем. 

Переходим к решению ⬇️

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

В своей практике я столкнулся с необходимостью повышения качества генерации без постоянного ручного контроля и затратных этапов дообучения. Это подтолкнуло меня к идее нового подхода — Semantic Error Correction Loop (SECL), представляющего собой само исправляющийся итеративный пайплайн с внутренней оценкой качества и семантической уверенности.

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

Несколько лет назад я посмотрел отличную презентацию от Дирка. В ней он описывал теорему о разделяющей оси, пролегающей между выпуклыми многогранниками (видео, слайды). Примерно на 18 минуте (слайд 29) он заводит речь о наложении гауссовых отображений выпуклых многогранников — как они помогают найти грани разности Минковского для этих многогранников.

В статье описывается старинная головоломка, русский вариант которой известен под названием «меледá». Решение этой головоломки тесно связано с информатикой. Здесь и первое в истории практическое использование двоичной системы счисления, рекурсивные алгоритмы, рекуррентные соотношения и др.

Головоломка, в России называемая старинным словом «меледá», состоит из замкнутой проволочной «вилки» («челнока»), имеющей вид длинной шпильки для волос и воткнутой обоими свободными концами в рукоятку, и нескольких колец, связанных между собой довольно сложным образом (см. рис. 1). Задача состоит в том, чтобы снять всю систему колец с вилки или надеть её обратно. 

Файловая система во встраиваемых решениях — критическое звено. От её выбора зависят надёжность, детерминированность и задержки всей системы.

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

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

Я протестировал четыре файловые системы на платформе MC80 с внешней OSPI NOR Flash и разработал специализированный драйвер вместо стандартного из FSP — с полноценной поддержкой OSPI и RTOS.