Алгоритмы *

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

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

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

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

В клетке с координатами (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

Привет, Хабр. Меня зовут Никита Драгунов, я из команды «Интерпретируемый ИИ» лаборатории FusionBrain AIRI. У себя в группе мы активно пытаемся понять, почему большие языковые модели и другие архитектуры ведут себя так или иначе, и разрабатываем инструменты, которые помогают нам в этом разобраться.

Среди прочего нас очень заинтересовал сравнительно свежий подход, в котором предлагается перейти от генерации токенов к генерации целых предложений — Large Concept Models, LCMs. Мы углубились в эту тему и смогли предложить новый способ, как использовать идею LCM эффективнее.

О том, что мы сделали — в статье ниже.

Всем привет! Меня зовут Артём Сидоров. Я ведущий разработчик из ИТ-команды «Северстали». Сегодня хочу рассказать, как мы реализовали «Универсальный сервис по сбору телеметрии с CAN-шин на технике».

Коллектив российских ученых исследовал применение методов машинного обучения для проектирования трассерных исследований. Целью было повышение достоверности результатов по выявлению гидродинамической связи в пласте между нагнетательными и добывающими скважинами в низкопроницаемых коллекторах с самопроизвольным развитием трещин гидроразрыва пласта (автоГРП) в нагнетательных скважинах. Работа была опубликована в российском журнале «Искусственный интеллект и принятие решений» и была выполнена совместно учеными и исследователями из МФТИ (г. Москва), ООО «РН-БашНИПИнефть» (г. Уфа) и ООО «РН-Юганскнефтегаз» (г. Нефтеюганск).

Сложно следить за околонаучными темами, и понимать, что ветка эволюции научного направления пошла не туда. Сейчас случился некий бум псевдонаучного взлета LLM, и я приведу в качестве современной статьи на хабре лишь одну, но это по прежнему массовое явление. Например, в статье компании Friflex за 2024 год История LLM-агентов: 10 ярких моментов по прежнему утверждается "На смену однослойному перцептрону Розэнблатта пришел многослойный. В статье Learning representations by back-propagating errors («Обучение представлений с помощью обратного распространения ошибки») Румельхарт и Хинтон показали, что многослойный перцептрон справляется с задачами, которые были не под силу его однослойному предшественнику. Например, с XOR. ". Совершенно излишне говорить, что это полное вранье, а авторы статьи даже не потрудились открыть эту статью, чтобы её прочитать. Это стало массовым явлением, и я его наблюдаю как минимум 20 лет, я когда то написал тут на хабре цикл статей объясняющих детали, лучше всего посмотреть эту Какова роль первого «случайного» слоя в перцептроне Розенблатта. Поэтому к этому возвращаться не будем. Я не знаю почему, может это массовая культура так влияет на людей, а порог вхождения в тематику ИИ слишком сложный? Не знаю, но не важно. Чтобы продемонстрировать скорость обучения перцептрона я написал несколько реализаций перцептрона Розенблатта и выложил их на гитхабе. А затем мы коснемся LLM.

Привет, Хаброжители! Алгоритмы — это сердце программирования. От их правильного выбора зависит, будет ли программа работать мгновенно или заставит вас ждать вечность. Но как разобраться во всем этом, если вы только в начале пути?

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