Алгоритмы *

Ученики начальной школы могут заучивать таблицу умножения однозначных чисел, но простого запоминания будет недостаточно, когда учитель задаст задачу на умножение трёхзначных чисел. Здесь требуется алгоритм: учеников учат выстраивать числа друг над другом и умножать каждую цифру нижнего числа на каждую цифру верхнего. На протяжении тысячелетий математики считали это самым быстрым способом умножения, пока в 1960 году 23-летний молодой человек не сделал шокирующее открытие, которое привело к загадке, остающейся неразгаданной до сих пор.

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

Чтобы понять суть этого «узкого места», обратите внимание на то, как «школьный» алгоритм справляется с увеличением размера чисел. При умножении двух двузначных чисел выполняется четыре однозначных умножения. Если перейти к паре трёхзначных чисел, то потребуется девять однозначных умножений. Нагрузка растёт пропорционально квадрату количества разрядов (n², где n — количество разрядов в умножаемых числах). При анализе подобного алгоритма компьютерные учёные не измеряют скорость в секундах, поскольку она зависит от аппаратного обеспечения. Вместо этого они подсчитывают количество вычислительных шагов. Они также игнорируют второстепенные детали, такие как время, необходимое для переноса единицы при умножении. Когда числа становятся достаточно большими, эти низкоуровневые операции перестают иметь значение, поскольку их полностью затмевают более ресурсоёмкие операции. Информатики обозначают количество шагов с помощью так называемой нотации «большого O»: например, алгоритм, который учат в начальной школе, требует O(n²) шагов, что читается как «порядка n в квадрате». В общих чертах, если числа в два раза длиннее, для выполнения алгоритма требуется в четыре раза больше вычислительной работы. Если числа в тысячу раз длиннее, требуется в миллион (1 000 в квадрате) раз больше работы.

Привет, Хаброжители! На протяжении всей своей истории человечество неустанно искало способы решать задачи, прикладывая как можно меньше усилий. Люди всегда стремились создавать инструменты и автоматизировать повторяющиеся действия, чтобы выживать и экономить силы. Здесь некоторые могут поспорить, заявив, что человек умен, ищет возможности совершенствования, умеет творчески решать задачи и создавать произведения искусства в области литературы, музыки и т.п. Но второе обновленное издание «Грокаем алгоритмы искусственного интеллекта» не ставит целью обсуждение философской сути бытия. Оно дает обзор методов искусственного интеллекта, которые можно применять для решения прикладных задач.

Этот значок на компьютере моего коллеги выглядит лучше

Как-то я общался с коллегой у него за компьютером и заметил, что логотип выглядит не совсем так, как моём компьютере. На компьютере коллеги он казался тоньше и больше походил на исходное изображение. Он имел размер 15px; на картинке выше показана его увеличенная версия.

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

Если прищуриться или отойти подальше, то изображение из Chrome выглядит толще. Это немного странно, но если заменить картинку на SVG, то проблема исчезнет. Однако мне всё равно стало любопытно: почему она вообще так рендерится?

Я провёл исследование и обнаружил в Chrome изящную оптимизацию, используемую для рендеринга JPEG в мелком масштабе.

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

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

Итак, если Спелке показывает, что человеку для этого нужно врожденное ядро знаний, то как с этим справляются ИИ? 
Способна ли нейросеть самостоятельно выделить объекты из огромного числа пикселей, построить внутренний физический движок и предсказать, куда упадет брошенный мяч, не зная формулы ? 

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

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

Заметная доля пользователей X предпочитает называть сайт микроблогов по старинке — Twitter. Другая неискоренимая вредная привычка — чтение алгоритмической ленты. Чтобы увеличить охват микроблога, было бы неплохо хотя бы в общих чертах разобраться, как работает рекомендательный алгоритм, а затем рассмотреть все основные коэффициенты. Этим в данной статье мы и займёмся.

Недавно я читала материалы о сжатии данных, и меня внезапно озарила безумная мысль: по сути своей, алгоритмы сжатия и LLM предназначены для решения одной и той же задачи.

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

Здравствуйте, друзья, меня зовут Ерохин Кирилл, я программист-любитель, а по совместительству популяризатор российского программного и аппаратного обеспечения, и в этом сентябре я провожу второе (теперь ежегодное) соревнование по алгоритмическому программированию на C/C++ для платформы Эльбрус (e2k), для студентов и выпускников со всей России «Кубок СЭРПАС 2026». Сегодня мне нужно дать участникам соревнования пример оптимизации кода под процессор Эльбрус-8СВ, а Хабр мне в этом поможет, ему не впервой.

Представьте: через ваш сервер проходит 10 миллионов запросов в минуту. Каждый запрос содержит метку (например, ID пользователя, IP-адрес или поисковый запрос). Руководство просит: «А давайте посмотрим, кто из пользователей самый активный?». Задача выглядит простой, пока вы не осознаете, что хранить HashMap из 10 миллионов ключей в оперативной памяти — это сотни мегабайт, а если ключи — длинные строки, то и гигабайты.

Вероятностные структуры данных решают такие задачи без гигантских кластеров. В прошлых статьях мы разобрали, как с помощью HyperLogLog считать количество уникальных элементов, а с помощью Фильтра Блума — проверять наличие элемента. Сегодня мы закроем триаду и поговорим об алгоритме, который отвечает на вопрос «А сколько раз этот элемент встречался?» с фиксированной памятью в пару килобайт и строгой вероятностной гарантией.

И это — Count-Min Sketch! Структура, которая лежит в основе анализа потоков в базах данных (от ClickHouse до BigQuery) и сетевых протоколов. Мы разберем её математику, реализуем на чистом C с использованием MurmurHash3 и проведем бенчмарки.

Привет, Хабр! На связи финалист ICPC и гроссмейстер codeforces MachineSolution. В прошлой своей статье я писал о том, как подготовиться к соревнованию. Но что делать, если время подготовки прошло, как писать саму олимпиаду? “Просто бери и решай задачи” - скажет кто-то, но будет прав лишь отчасти. У некоторых соревнований есть свои особенности и, как следствие, особые стратегии написания. И заключительный этап всероссийской олимпиады школьников по информатике не лишён своих отличительных черт.

Всероссийская олимпиада школьников по праву считается мерилом олимпиадных способностей школьников и, хотя взять диплом даже регионального этапа ВсОШ дано не каждому, всероссом называют именно заключительный этап и готовятся к нему. Мало кто из сильных олимпиадников не хочет “взять всеросс” - то есть выиграть диплом призёра заключительного этапа. Помимо поступления в любой ВУЗ без экзаменов он сам по себе является ценной наградой и подтверждением своих способностей и признания результата долгих тренировок. Более того, не так много людей стремятся к диплому победителя - настолько сложно и почётно в этой олимпиаде стать хотя бы призёром! Заветные дипломы по информатике каждый год получают всего 200-300 человек из миллионов школьников. Моя история с этой олимпиадой не самая сказочная - в свои школьные годы я пожертвовал подготовкой к информатике ради подготовки к математике. Да, в итоге я занял 7 место на финале математики и почти стал победителем, но на информатике выступил, мягко говоря, ужасно - даже не близко к призёрам. Поэтому мне стало интересно написать зеркало ВсОШ по информатике за 2026 год, чтобы проверить, как сильно я вырос в олимпиадах и на что способен.

В этой статье я постараюсь объяснить, как работает биткоин. Без аналогий с добычей золота и прочих глупостей.

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

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

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

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

В его составные части входит:

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

Приветствуем, Хабр.

Не секрет, что большие языковые модели и, в частности, трансформеры (GPT) серьезно повлияли на работу программиста, привели к автоматизации многих рутинных задач, значительно удешевили проверку концепций и эксперименты при разработке новых продуктов. Коренные изменения произошли не только в разработке, но и во взаимодействии пользователя с ботами, агентами, поисковыми системами. Промпт-инжиниринг буквально за полтора года превратился из искусства в ремесло, которое способен освоить и подросток. Мы хотим очертить ближайшие перспективы выхода книг из типографии и планы на обозримое будущее — на наших верфях и уже практически на стапелях готовится целый флот литературы, ориентированной на работу с искусственным интеллектом.

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

Через несколько дней (говно)кода стало много — вменяемого сервиса не получилось.

Один BFS принимал map[string][]string. DFS жил на другом типе графа. В одной реализации направленность задавалась на уровне графа, в другой вытекала из того, как было записано ребро. Опции существовали, но их комбинации не образовывали понятной политики. Result types возвращали срезы и числа, однако я не мог внятно ответить, что именно они гарантируют.

Проблема была не в том, что LLM «не умеет BFS». Я попросил реализации раньше, чем сформулировал общий контракт данных. Генератор заполнил пустые места правдоподобными допущениями — которые, очевидно, не совпали в разных кусках кода.

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

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

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

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

Цель видна только через камеру, детектор отдает рамку, дальномера нет. В какой-то момент цель уходит из кадра на три четверти секунды, и ее надо продолжать вести вслепую. Классический фильтр Калмана в этой ситуации теряет цель в 84% эпизодов. Наш трекер теряет ее в 18% и возвращает в центр кадра в 80%.

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

Текст будет полезен аналитикам и продакт-менеджерам, которые работают с ценообразованием, субсидиями, промомеханиками и любыми задачами оптимизации бюджета при ограничениях.

Привет, читатель!

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

Всем привет! Меня зовут Алина Бабенко, я acting DS-менеджер в Авито. Наша команда занимается моделями монетизации в поиске и рекомендациях: мы оцениваем ожидаемую выручку от действий пользователей и используем её в ранжировании. В этой статье я расскажу, какие модели используем для расчёта ожидаемой выручки, как оцениваем их качество, а также зачем корректируем ставки.

Материал будет полезен дата-сайентистам и тимлидам, которые работают с монетизацией на маркетплейсах и в сервисах для объявлений.

Допустим, вы пишете программу для обработки изображений. Программа получает изображение, преобразует его в значения с плавающей запятой, выполняет обработку и сохраняет изменённые пиксели на диск в виде 8-битных цветов. Сегодня я хочу рассмотреть вопрос преобразования целых значений в значения с плавающей запятой. Существует два решения, которые на Python и NumPy выглядят так:

Стандартное деление на 255

pixels = img / 255.0
result = process(pixels)
output = np.trunc(result * 255 + 0.5)

Альтернативное деление на 256

pixels = (img + 0.5) / 256.0
result = process(pixels)
output = np.trunc(result * 256)

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

# Ограничение и преобразование в 8 бит
output_8bit = output.clip(0, 255).astype(np.uint8)

В стандартном случае целочисленный 0 соответствует 0.0, а 255 соответствует 1.0. Это работает абсолютно нормально и именно так всё реализовано в GPU. В альтернативном случае прибавляется смещение на 0,5 и деление происходит на 256, поэтому целочисленный 0 соответствует 0.5/256=0.001953125. Это неудобно, потому что код обработки изображений, например, без знания константы не сможет обнаруживать чёрные пиксели. Из‑за этого мы привязываем логику к 8-битным значениям, даже если вычисления выполняются с плавающей запятой. В стандартном решении всегда можно предполагать, что чёрный соответствует 0.0.

Однако некоторых программистов всё равно притягивает альтернативное решение. В чём дело? Чем оно им так нравится?

Привет! Сейчас покажу штуку, которую я довольно долго доводил до ума, и мне кажется, она может пригодиться не только мне.

Задача звучит скучно: нагенерировать тестовые карточки людей. Пол, имя, диагноз. Скучно ровно до того момента, пока не посмотришь, что получилось: