Алгоритмы *

Нотация Big O («О» большое) — это способ описания производительности функции без измерения времени ее выполнения. Вместо того, чтобы засекать, сколько секунд выполняется функция от начала до конца, Big O показывает, как меняется время ее выполнения по мере увеличения размера входных данных. Этот подход помогает понять, как программа будет вести себя при разных объемах входящей информации.

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

Приветствую, Хабр!

Структура криптографических алгоритмов, названная ее авторами «губкой» (sponge), была предложена в 2007 году. С тех пор на базе структуры криптографической губки было разработано достаточно много известных криптоалгоритмов.

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

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

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

Привет! Меня зовут Серёжа Синягин, я старший разработчик в Яндекс Еде и пишу на C++. В этой статье расскажу о задаче, с которой столкнулся в работе: как мы определяем, какие рестораны доступны пользователю для заказа. По пути заглянем во внутреннюю кухню, обсудим библиотеку H3 от Uber и разберём, как устроены R‑деревья и как мы используем их у себя.

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

В этом тексте я произвел разбор решения LeetCode задачи 480. Sliding Window Median в контексте реализации на языке программирования Си.

Если Вы когда‑то учились в вузе на технической специальности или учитесь сейчас (иначе, зачем бы Вам эта статья), у Вас наверняка есть предмет, который назывался примерно так — «Методы оптимизации» / «Введение в оптимизацию» или что‑то похожее. Задачки там примерно такие: «завод производит продукцию типов, как бы произвести деталей первого типа,..., деталей k‑го и как можно дешевле». Потом рассказывалось про симплекс‑метод для задач линейного программирования и про метод Лагранжа для задач нелинейного. Про указанные выше условия где‑то упоминается, но без примеров, где‑то сразу абстрактные примеры с матрицами, а может быть Ваш препод и вовсе написал в своей методичке, мол, это выходит за рамки курса. В этой статье предлагаю аккуратно разжевать на простом примере, что такое условия ККТ.

Что нам позволяют найти условия Каруша‑Куна‑Таккера (ККТ)

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

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

Есть бесконечная плоскость, вымощенная квадратными клетками

У каждой клетки есть две координаты в виде целых чисел

Координаты от минус бесконечности до плюс бесконечности

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

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

Например, у клетки с координатами (758, -219) сумма цифр координат 7+5+8+2+1+9=32

Случай, когда рассматривается количество клеток без взаимосвязи с тем, можно ли к ним пройти или нет, рассматривать бессмысленно, т.к. существует бесконечное число клеток с координатами вида (0, 1000……000) с различным количеством нулей.

Вопрос

Сколько клеток доступно муравью при заданном N?

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

В этой статье я хотел бы вставить свои пять копеек и выразить несколько своих мыслей по этому поводу, которые накопились на небольшую статью. Основная их цель — найти способ объяснить решение этой задачи человеку, который знает тервер на самом базовом школьном уровне, и который не имеет никакой теоретико‑вероятностной интуиции (такие люди, в основном, и рождали споры в комментариях). Конечно, без базовых знаний в других областях математики не обойтись, но на мой взгляд, если такое объяснение существует, то это неплохая альтернатива классическому решению. Ибо истинное решение задачи из теорвера зачастую противоречит человеческой интуиции.

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

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

— в целом за торговую сессию;
— на уровне цены с наибольшим проведённым объёмом за сессию (POC);
— в пиковый момент сессии, в минуту, в которую прошёл наибольший объём.

...

В прошлой статье на Хабре «На дворе LLM, а книгу о перцептроне так никто и не открыл!?» я указал, что многие понятия не имеют о перцептроне Розенблатта, но пишут о нем так как будто читали оригинал. И так или иначе в комментариях прошла дискуссия, как минимум с тремя оппонентами, которые тоже находятся в разного рода не знании о перцептроне. Что только подтверждает мои слова, что это массовое явление. Поэтому даже в научной статье мне придётся этому уделить не малое внимание. Свою статью, я еще не опубликовал, да ещё полностью и не написал, хотя все эксперименты были сделаны 15 лет назад, а сейчас их нужно улучшить. Собственно, когда я сам стряхнул пыль с них, я долго не мог по программному коду понять, о чем это, что это дает, так и возникла моя мысль, что это нужно донести людям. И подумал, почему бы мне некоторые разделы будущей статьи, сразу не взять и не опубликовать тут на Хабре. Имея широкий охват, это может иметь даже большую пользу, чем публикация в модерируемом издании. Поэтому ниже я дам выдержки из своего черновика статьи «как есть», относящиеся в основном к «утерянной памяти о перцептроне», но т.к. как это часть научной статьи, настоятельно прошу при цитировании ссылаться на меня. Хотя и понимаю, что выдержки не дадут вам полного понимания проблемы, но как минимум расскажут о известных фактах и надеюсь, все же уберегут от поверхностного взгляда. Ну и мало ли — если тут найдется специалист, который публикуется на https://arxiv.org последние 5 лет, мне нужна ваша помощь с рекомендацией, свяжитесь со мной. Тогда полноценная статья выйдет быстрее.

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

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

Что такое жадный алгоритм?

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

Интересным является вопрос о погружении арифметики в n+1-значные логики Лукасевича Ł_n+1. Какая часть арифметики может быть погружена в Ł_n+1? Для функции φ(х) = m  рассматривается обратная к ней, определяемая  соотношением φ ^–1(m) = {n, φ(n) = m}, где φ(х) – функция Эйлера.

Пример, если φ(n) = 4, то это уравнение имеет ровно четыре решения φ ^–1(4) = {5, 8, 10, 12}. Гольдбахом (1690 –1764) поставлена проблема о разложении четных чисел ≥ 4 на сумму двух простых. Если это верно, то для каждого числа m найдутся простые числа р и q такие, что φ(р) + φ(q) = 2m.

Эдмунд Ландау в 1912 г. на международном конгрессе математиков в Кембридже заявил, что проблема Гольдбаха недоступна для современного состояния науки. Недоступна она и сейчас. Верифицируемость предположения Гольдбаха установлена до 4∙10¹⁴.

Делались попытки найти формулу, с помощью которой вычислялись бы (или порождались) все простые числа. Наилучший результат принадлежит Ю.В. Матиясевичу (1977), который нашел полином из 10 переменных. Асимптотическое распределение простых чисел в НРЧ, доказываемое аналитическими методами, приводится в книге К. Прахара (1967). О первых 50 млн простых чисел статья Д. Цагера (1984).
Можно считать, что впервые на проблему решения подобных уравнений обратил внимание Э. Люка (1842 – 1891). Об этом сказано в книге И.В. Арнольда (1939) «… следуя Люка, сгруппированы числа n с одним и тем же значением функции φ(n) в пределах от 1 до 100, т.е. дана таблица функции обратной по отношению φ(n).

В книге Серпинского (1968) задача №245 «Найти все натуральные числа n≤ 30, для которых φ(n) = d(n), где φ(n) – функция Эйлера, а число d(n) – число натуральных делителей числа n». Рассмотрим только случай n = 30. Делителями числа 30 являются числа 1, 2, 3, 5, 6, 10, 15 и 30, т.е. d(n = 30) = 8. Значит надо решить уравнение φ(30) = 8, где n≤ 30. Или, по-другому, найти значения для обратной функции Эйлера φ ^–1(8), т.е. определить множество {n, φ (n) = 8} для  n≤ 30. Это множество образовано числами {15, 16, 20, 24, 30}. Более того, ни для каких других n >30 φ (n) ≠ 8.

Множество значений φ ^–1(m) = Ø пусто для всех нечетных значений и многих четных значений m > 1. В первой сотне числа 14, 26, 34, 38, 50, 62, 68, 74, 76, 86, 90, 94 и 98 не являются значениями φ (n).

Всем привет! Меня зовут Алексей Майшев, я работаю Go-инженером в Авито. В этой статье рассказываю, как мы проектировали и разрабатывали кэш-библиотеку следующего поколения для Go — otter. 

Вы узнаете, чем нас не устроили текущие кэш-библиотеки в Go, какие подходы и оптимизации мы рассматривали и на каких остановились, как замеряли производительность и потребление памяти и в чём otter превосходит конкурентов. А ещё тут будет много теории — в процессе работы над библиотекой нам приходилось читать много страшных научных статей на тему кэшей.

Предыдущая часть

Часть 5: Алгоритмы – реализация и модель ошибок

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

План статьи: В этой части рассматривается практический процесс изготовления печатной платы нашего устройства.

Добрый день, уважаемые хабражители! Как и прежде меня зовут Владимир Миронов, и я занимаюсь тестированием и оценкой синтетических данных ;) Добрались, наконец-то, до четвёртой части в этом цикле статей из (прошлые статьи можно увидеть тут, тут и тут). В этот раз разберём важный момент, связанный с анализом полученных матриц смежностей по нашим графам и представлением их свойств с позиции оптимизации и унификации. В общем, поговорим про алгоритмы, обсудим чисто технические моменты и подходы к унификации данных. 

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

В теории вероятностей имеется несколько известных задач, решение которых противоречит здравому смыслу. Одна из таких задач — «Парадокс сестёр». Сейчас я изложу условие задачи, дам вам возможность подумать над ответом, а потом расскажу о том, как её решать.

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

Привет, шахматные фанаты!

В этом посте разберём, кто реально имеет шансы на успех в Grand Swiss 2025 в Самарканде. Всё по делу: рейтинг FIDE, результаты топ-турниров 2024 года, котировки букмекеров и аналитика с использованием bStresScore — показателя стрессоустойчивости игроков в критические моменты.

В предыдущей статье мы поморгали диодом. Большое дело, вообще‑то. После удобных сред разработки, вроде VSCode, CubeIDE, или продуктов JetBrains (поклонники Vim вышли из чата), Квартус не кажется очень уж дружелюбным. Плюс смена подхода к разработке: от программы к схеме. Но ничего, вроде, справились. Получается, мы погрузились в тему, наверное, на уровне «намочить ноги». Теперь, неспеша, зайдём по щиколотку.

Проект Athenix — это уникальная система мониторинга котировок с глубоким анализом объёмов торгов и прогнозами на основе искусственного интеллекта. Если вы интересуетесь финансовыми рынками, трейдингом и современными технологиями, эта статья для вас.

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

Проект предлагает практичный подход к сложностям анализа рынка — концентрируется на главном, снимая с трейдера необходимость обрабатывать сотни показателей вручную. Будут подробно рассмотрены методы обработки объёмных данных, шумоподавление с вейвлет-преобразованиями, бинарное прогнозирование и использование LSTM-нейросетей.

Эта статья будет полезна тем, кто хочет понять, как современные технологии и алгоритмы могут помочь в эффективной среднесрочной и долгосрочной торговле. Погрузитесь в мир финансового анализа будущего с Athenix!

Топологический аудит ECDSA: как найти уязвимости с одной подписью

Традиционный анализ безопасности ECDSA требует сотен подписей для выявления уязвимостей. Но что делать, когда у вас есть только одна подпись из блокчейна?

Мы разработали AuditCore — систему топологического аудита, которая анализирует безопасность ECDSA, используя лишь публичный ключ и одну реальную подпись. Система автоматически генерирует необходимое количество валидных подписей и проводит глубокий анализ пространства (u_r, u_z) как топологического тора.

Ключевые возможности:

Определение уязвимостей по топологическим инвариантам (числам Бетти)

Расчет TVI Score — количественной метрики уязвимости

Автоматическое обнаружение паттернов: фиксированный k, линейные зависимости, кластеры

Генерация необходимого количества данных для статистически значимого анализа

Система состоит из нескольких специализированных модулей:

TopologicalAnalyzer для вычисления персистентных гомологий

BettiAnalyzer для интерпретации топологических показателей

CollisionEngine для поиска коллизий

SignatureGenerator для создания валидных подписей

TCON для оценки соответствия топологии тора

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

Полная реализация доступна на GitHub: https://github.com/miroaleksej/AuditCore/tree/main/Scripts