Алгоритмы быстрого умножения чисел: от столбика до Шенхаге-Штрассена

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

И уж конечно, никогда при написании a * b мы не задумываемся о том, как реализовано умножение чисел a и b в нашем языке. Какие вообще есть алгоритмы умножения? Это какая‑то нетривиальная задача?

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

https://habr.com/ru/articles/719648/

Алгоритмы и Структуры данных

Генеративно-состязательная нейросеть: ваша первая GAN-модель на PyTorch

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

https://proglib.io/p/generativno-sostyazatelnaya-neyroset-vasha-pervaya-gan-model-na-pytorch-2020-08-11

Алгоритмы и Структуры данных

SQL HowTo: немного математики (Advent of Code 2025, Day 1: Secret Entrance)

Сегодня стартовал Advent of Code 2025!

Осторожно, спойлеры! Не читайте, пока хотите решить задачу самостоятельно.

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

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

https://habr.com/ru/companies/tensor/articles/972046/

Алгоритмы и Структуры данных

Как свергнуть короля: формула для линейной альтернативы Трансформеру без побочных эффектов

На связи Андрей Аргаткин, руководитель научной группы исследований эффективных архитектур нейронных сетей ИМШ ВШЭ. Я хочу рассказать о нашем текущем исследовании в рамках совместного образовательного проекта с VK. В ходе исследования мы надеемся выделить волшебную формулу из недавней архитектуры DANet (1, 2) и экстраполировать её на широкий спектр других моделей, что позволит им стать такими же крутыми по качеству, но гораздо более быстрыми и эффективными, чем бессменный король мира нейронных сетей — Трансформер. Эта формула должна избавить от побочных эффектов предыдущих архитектур, пытавшихся стать ему заменой. Но сначала поговорим, зачем всё это вообще нужно.

https://habr.com/ru/companies/vk/articles/971668/

Алгоритмы и Структуры данных

SQL HowTo: генерируем строкочисла (Advent of Code 2025, Day 2: Gift Shop)

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

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

https://habr.com/ru/companies/tensor/articles/972304/

Алгоритмы и Структуры данных

«Ты не пройдёшь!»: как мы учили нейросеть искать патологии на КТ, обучая её только на норме. Наш опыт на ЛЦТ-2025

Знаете, как обычно проходят будни исследователя в AI? Сидишь, читаешь статьи, пьёшь восьмую кружку кофе и пытаешься уговорить модель наконец‑то сойтись. А потом кто‑то из коллег кидает в чат ссылку: «Ребята, тут хакатон. „Лидеры цифровой трансформации 2025“. По медицине. Пойдём?».

Ну, а мы что? Мы пошли.

Мы — это три исследователя из группы Foundation Models лаборатории «Сильный ИИ в медицине» Института AIRI. Базируемся в Москве, любим большие модели и сложные задачи. Нам достался, возможно, один из самых интересных треков: «Сервис для выявления компьютерных томографий органов грудной клетки без патологий».

https://habr.com/ru/companies/airi/articles/972104/

Алгоритмы и Структуры данных

Книга: «Разработка алгоритмов. Инженерный подход»

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

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

https://habr.com/ru/companies/piter/articles/970978/

Алгоритмы и Структуры данных

Продолжение статьи: Архитектура торгового Telegram-бота для сигналов пампов и дампов

Я решил ввести два типа сделок, зависящих от 5% и 12% сигналов. При 12% движении мы открываем позиции в контр-тренд, при 5% движении открываем позиции в продолжение тренда. Такие проценты были выведены путём довольно долгой ручной торговле. На монетках средней и маленькой капитализации это действительно рабочая стратегия. Вероятно, она основана на принципах работы ММ.

Всю эту стратегию я реализовал в телеграмм бота - с ручными настройками каждой из четырех стратегий, с фильтрами. Бот сейчас находится в тестнете и является на 100% бесплатным. Так что вы можете тестировать его не опасаясь за свои деньги - все сделки будут происходить на демо-счёте. ссылка на бота

https://habr.com/ru/articles/972562/

Алгоритмы и Структуры данных

Вероятностный анализ финансовых рынков на основе чистого OHLCV и многомодульной математической модели

Введение: зачем рынку нужна вероятностная модель
Большинство торговых систем работают детерминированно: “если RSI пересёк X — покупай”.
Но рынок — стохастическая система. Сигналы не бинарны, они вероятностны.

Это приводит к трём фундаментальным проблемам классических индикаторных систем:

https://habr.com/ru/articles/972584/

Алгоритмы и Структуры данных

Как попасть в мир олимпиадного (спортивного) программирования? Спорт для ума, который меняет мышление

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

GIGASCHOOL регулярно поддерживает чемпионаты по программированию, а также – обучающие центры. Сегодня мы обратились к директору центра олимпиадного программирования ЮУрГУ, Марине Сартасовой, с вопросом о подготовке спортсменов к соревнованиям по программированию. Разобрались, с чего начать, зачем участвовать и почему знания математики или выбор языка программирования бывают решающим фактором в победе.

https://habr.com/ru/articles/972682/

Алгоритмы и Структуры данных

Как мы учим Яндекс Карты предупреждать о манёврах: без использования LL
M, но с помощью водителей

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

Меня зовут Дмитрий, и я руковожу ML‑разработкой в команде автонавигации Яндекс Карт. Вместе с моим коллегой Альбертом Юсуповым @al-iusupov в этой статье мы поделимся историей полного переосмысления системы генерации дорожных аннотаций. Расскажем, почему решили отказаться от десятков хитрых условий в коде, а также почему заманчивая идея отдать всё на откуп большим нейросетям (VLM, LLM) провалилась. И, наконец, как пришли к элегантному решению: создали уникальный датасет с помощью сотен водителей‑экспертов и обучили быструю и точную ML‑модель, которая работает по принципу «меньше, но лучше».

https://habr.com/ru/companies/yandex/articles/972126/

Алгоритмы и Структуры данных

Как я осознал, что не умею кодить

Вчера мой скрипт завис. Процессор горел на 100%. Я убил процесс.

Я Senior Developer с 10 годами опыта. Пишу на Python, знаю Java и много модных фреймворков. Но в этот момент я понял: я не умею программировать. Точнее, я умею использовать инструменты. Но я не понимаю природу вычислений.

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

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

Возможно, и тебя тоже.

https://habr.com/ru/articles/972630/

Алгоритмы и Структуры данных

Воксельный движок всего за выходные

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

Введение
Приготовьтесь, мы совершим путь от единственного кубика до целого воксельного движка! Нам понадобится следующее:

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

API рендеринга! Выбирайте что угодно, эта статья — не туториал по рендерингу.

https://habr.com/ru/articles/965988/

Алгоритмы и Структуры данных

Машины Тьюринга, огромные числа и бобры: что у них общего?

Представьте, что кто-то даёт вам список из пяти чисел: 1, 6, 21, 107 и внезапно — 47 176 870. Догадаетесь, что будет дальше?

Если вы не угадаете, ничего страшного — практически никто не угадывает. Вот первые пять чисел «усердного бобра» — последовательности, тесно связанной с одним из самых известных и сложных вопросов теоретической информатики. Он звучит так: сколько времени может работать машина Тьюринга с некоторым набором правил, пока не остановится. Определение значений чисел «усердного бобра» — сложнейшая задача, которая уже более 60 лет привлекает поклонников как среди профессиональных математиков, так и среди любителей.

Исследователи определили первые четыре числа «усердного бобра» в 1960-х и 1970-х годах. Пятое число, BB(5), оказалось настолько большим, что установить его удалось только в прошлом году. Это выполнила команда, состоящая в основном из математиков-любителей, которые работают в онлайн-сообществе под названием Busy Beaver Challenge.

https://habr.com/ru/companies/first/articles/973502/

Алгоритмы и Структуры данных

Детальный разбор стандарта NIST SP 800-232 со схемами преобразований. Часть 2

Приветствую, Хабр! Напомню, что в августе текущего года Институт стандартов и технологий США NIST выпустил стандарт NIST SP 800-232 [1], описывающий четыре низкоресурсных криптографических алгоритма на базе семейства алгоритмов Ascon:

алгоритм аутентифицированного шифрования с присоединенными данными Ascon-AEAD128;

три алгоритма хеширования: Ascon-Hash256 (классическая хеш-функция), Ascon-XOF128 (хеш-функция с переменным размером выходного значения) и Ascon-CXOF128 (хеш-функция с кастомизацией и переменным размером выходного значения).

Данная статья из двух частей посвящена детальному обзору вышеупомянутого стандарта. В первой части статьи было подробно описано внутреннее преобразование, общее для всех стандартизованных алгоритмов, и разобрана верхнеуровневая структура алгоритма Ascon-AEAD128. В этой, заключительной, части предлагаю Вашему вниманию подробное рассмотрение структуры алгоритмов хеширования, а также обзор рекомендаций и ограничений по применению алгоритмов, описанных в NIST SP 800-232.

https://habr.com/ru/companies/aktiv-company/articles/973300/

Алгоритмы и Структуры данных

То, что обычно не показывают: как выглядит Wi-Fi взлом изнутри (схемы, примеры, анализ)

Безопасность Wi-Fi остаётся одной из тех тем, где одновременно сосуществуют мифы, неоправданные ожидания и огромное количество недопонимания. Кто-то уверен, что WPA2 и тем более WPA3 взломать невозможно, потому что «это же криптография». Кто-то считает, что всё решается набором трёх команд в Kali. И на практике обе позиции оказываются одинаково далеки от реальности. Wi-Fi — это не магия, не «сеть, работающая на духах», и не «непробиваемая защита». Это обычный протокол уровня 802.11, который живёт в открытом эфире и подчиняется вполне конкретной структуре пакетов, таймингов и встроенных процедур. Понимание этих процедур моментально показывает, что подавляющее большинство атак — не взлом, а закономерное следствие того, как устроено взаимодействие клиент ↔️ точка.

https://habr.com/ru/articles/973656/

Алгоритмы и Структуры данных

SQL HowTo: от частностей к рекурсии (Advent of Code 2025, Day 3: Lobby)

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

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

https://habr.com/ru/companies/tensor/articles/972726/

Алгоритмы и Структуры данных

WarpTrade и робастные алгоритмические стратегии

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

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

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

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

https://habr.com/ru/articles/973928/

Алгоритмы и Структуры данных

OTXform — операциональное преобразование от теории к практике

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

Теория без практики пуста, а практика без теории слепа.

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

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

Дальнейшие исследования расширили ее возможности и области применения, что в свою очередь породило несколько алгоритмов.

В данной работе я не буду рассматривать все, а только один из них.

https://habr.com/ru/articles/972638/

Алгоритмы и Структуры данных