Алгоритмы *

Двоичная куча (binary heap) — это структура данных, которая представляет собой бинарное дерево, удовлетворяющее определённым условиям:

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

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

В комментариях к моим статьям регулярно встречаются возражения по поводу понятия «модель числа» – это какой-то оксюморон, фантазии автора и др.
В ответ могу только заметить, что в математике имеют дело с натуральными (N), целыми (Z), рациональными (Q), вещественными (R) и комплексными (С) числами. Приведенные термины по существу называют модели чисел с четко различимыми свойствами и допустимыми операциями в каждом из множеств названных чисел. Соотношения между этими моделями задается  включением левого (меньшего) в правое (большее) множество чисел N ⸦ Z ⸦ Q ⸦ R ⸦ C.
Главными операциями над множествами чисел в таких моделях являются сложение (+) и умножение (×), обратными к которым являются операции вычитания (–) и факторизация (×^-1).

Для факторизации еще не введен обозначающий ее символ (мной использована операция обратная к символу произведения). Заметим, что обратимость даже главных операций возможна не в любой из моделей. Так операция вычитания не является допустимой для натуральных чисел. Если при вычитании  уменьшаемое меньше вычитаемого, то результат – (разность) не определен в множестве N натуральных чисел.

Когда мы представляем число из некоторого множества суммой слагаемых а + b, то, изменяя значения а и b так, чтобы сумма их оставалась постоянной, мы задаем аддитивное представление конкретного числа или его аддитивную (линейную) модель. Такая списочная многострочная модель (СММ) допустима во всех известных множествах. Совокупность сумм для N = х + у, где х и у – переменные модели, с накладываемыми на них ограничениями, задает модель числа N. А распределение делителей числа в натуральном ряде задается законом распределения делителей (ЗРД) числа.

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

Привет, Хабр! Меня зовут Георгий Семёнов, в 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), представляющего собой само исправляющийся итеративный пайплайн с внутренней оценкой качества и семантической уверенности.