Математика *

Сколько нужно бит, чтобы представить одно число из континуума ℵ₁ чисел?

Ответ: ℵ₀ бит.

Сколько нужно бит, чтобы представить одно число из счётного множества ℵ₀ чисел?

Ответ: ℵ₋₁ бит.

Произвольное число из континуума (почти все они трансцендентные) требует бесконечно бит для представления, а произвольное число из счётного множества (натуральные, целые, рациональные) требует непременно конечно бит.

Коротко говоря, ℵ₋₁ это достаточно.

В разработке ПО произведение двух целых чисел часто вычисляется до фиксированного количества битов с переполнением. Возьмём для примера 8-битные целые. Если умножить 127 на 127, то мы получим число 1 в виде 8-битного беззнакового целого с переполнением. Реальное полное произведение равно 16129. Для представления 16129 обычно используются 16 бит точности.

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

В первой статье я высказал простую идею: если вычисление можно свести к конечной таблице операции, его можно проверять, а не угадывать. То есть его можно свести не к "модель выдала вероятность 0,67", а просто открыть таблицу и сказать: вот ячейка, вот результат, rc=0.

Эта статья — прямое продолжение первой статьи (сейчас у меня на руках значительно отличающаяся рабочая модель ИИ-движка). Но сразу честно: я не собираюсь раскрывать здесь внутреннюю кухню "GALO AI". Ни устройство нейрона, ни приватные маршруты мышления. Покажу только основополагающую математику, вернее, маленькую конечную структуру, которую можно взять руками, прогнать скриптом и попытаться сломать контрпримером.

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

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

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

Во многом красота математики заключается в том, что благодаря произвольному выбору можно связать две кажущиеся далёкими концепции. Впервые я увидел этот паттерн в вопросе на Math Stack Exchange. Его задал пользователь dwymark, а ответил на него Грег Мартин; вопрос связан с распределением простых чисел, а также с рациональными аппроксимациями .

Этот пользователь баловался с созданием графиков данных в полярных координатах, то есть нанесением точек в 2D-пространстве, но не по обычным координатам XY, а по расстоянию от точки начала координат, обычно называемому (радиус), и по углу прямой относительно горизонтали, обычно называемому «тета», .

В четвертой части мы начали изучение задачи классификации и разобрали метод kNN.

Мы уже дошли до той точки, когда можем построить худо-бедно работающий классификатор. Но если нас спросят: “а насколько хорошо он работает?”,
то максимум, что мы пока сможем ответить — что-то вроде: “ну... на тестовой выборке модель правильно ответила в p% случаев”.

С одной стороны, как гласит древняя пословица: лучше иметь 500 рублей, чем 200. Но гарантирует ли высокий p% качество модели?

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

Аннотация. В статье рассматривается физическая основа измерений Ekahau Sidekick и механизм применяемого RSSI‑offset с позиций теории антенн, теории шума радиоприёмных устройств, статистической теории сигналов и стандартов IEEE 802.11. Показано, что scalar RSSI‑offset является линейным сдвигом уровня и не моделирует ни реальный SNR клиентского устройства, ни структуру QAM‑созвездия, ни алгоритм rate adaptation, ни роуминговое поведение. Помимо пяти независимых физических и системных причин неточности, рассматриваются системные упрощения Ekahau, касающиеся MIMO‑усиления, многолучёвости, оценки airtime и визуализации SNR. Приведены верифицированные численные оценки погрешности для конкретных сценариев и практические рекомендации.

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

Переворачивающимися при умножении числами я назвал такие числа a и b с одинаковым количеством цифр, что выполняется равенство:

a ∙ b = concat(reverse(b), reverse(a)),

где операция reverse записывает разряды числа в обратном порядке, а операция concat соединяет два числа в одно. Например, выполняются такие равенства:

218252 ∙ 837281 = 182738 252812
43275098 ∙ 77535533 = 33553577 89057234
47208027 ∙ 56843862 = 26834865 72080274
и т. д.

Алгоритмы нахождения переворачивающихся чисел приведены в оригинальной статье и комментариях к ней.

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

В третьей части мы закончили с линейной регрессией. Теперь пора перейти к задаче классификации․

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

Заменив самое фундаментальное понятие в топологии, Питер Шольце и Дастин Клаузен сделали первый шаг в гораздо более масштабной программе по изучению того, почему числа ведут себя именно так.

Как понять смущающую интуицию задачу за секунду - метод экстремальных параметров.

Бывало ли у вас такое - вы смотрите на условие задачи, логику алгоритма или даже жизненную ситуацию, интуиция кричит: «Здесь всё очевидно!», а строгая логика, тесты или реальность упрямо показывают совершенно другой результат?

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

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

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

Новость «ИИ опроверг важную гипотезу Эрдёша» нашумела, в том числе на Хабре. Но всем, кроме математиков, по громким заголовкам сложно понять масштаб события. Что это значит: революцию в науке или мелкую разовую удачу? Как это правильно оценить?

Мы в Kodik занимаемся не математикой, а редактором кода с ИИ. Но именно поэтому такие истории интересны и нам: они позволяют наблюдать не только очередной виток хайпа вокруг LLM, но и постепенный заход ИИ в области, которые ещё недавно считались слишком сложными для подобных систем.

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

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

Парадокс Протагора и Эватла

Знаменитый философ и учитель софистики Протагор обучил юношу Эватла юриспруденции. Ученик обещал заплатить за обучение, но только если выиграет свой первый судебный процесс. Однако после окончания учебы Эватл не стал браться за дела и платить отказался. Тогда учитель подал на него в суд.

Спор:

Аргументация Протагора: Если Эватл проиграет суд, то он обязан заплатить по решению суда. Если Эватл выиграет суд, он выиграет свой первый процесс, а значит, обязан заплатить по условиям их изначального договора. Вывод учителя: при любом исходе ученик должен отдать деньги. Контраргументация Эватла: Если я выиграю суд, то по решению суда я ничего не должен платить. Если я проиграю суд, то я не выполнил условие договора (не выиграл свой первый процесс), а значит, по контракту я тоже ничего не должен платить. Вывод ученика: я не должен платить ни при каком исходе.

Рассуждения:

Логическая ошибка кроется в интерпретации фразы «выиграл процесс». У Протагора: «выиграть процесс» — это просто сам факт победы в суде (успешный исход дела). У Эватла: «выиграть процесс» — это значит освободиться от уплаты. Эватл подменяет понятия. Он считает, что если он выиграл суд, значит, он не должен платить по договору. Но одно не исключает другое: он может выиграть суд и при этом быть обязанным выплатить гонорар, потому что суд доказал его статус выигравшего дело (тем самым активировав договор).

Если рассматривать парадокс с точки зрения судебного права, то он возникает из-за смешения двух разных юрисдикций: условий частного контракта (договора) и власти судебного решения (закона). В логике этот софизм решается так:

У вас есть две веревки и коробок спичек. Каждая веревка сгорает ровно за 1 час. При этом они горят неравномерно (например, первая половина может сгореть за 5 минут, а остаток — за 55 минут). Как с помощью этих веревок отмерить ровно 45 минут?

Решение: Поджигаем первую веревку с обоих концов одновременно, а вторую веревку — только с одного конца. Первая веревка полностью сгорит ровно через 30 минут (так как пламя встретится). В этот самый момент поджигаем второй конец второй веревки. Ей оставалось гореть 30 минут с одного конца, но с двух концов она сгорит в два раза быстрее — за 15 минут. Итого: 30 + 15 = 45 минут.

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

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

Привет, Хабр! Меня зовут Андрей Басов, я руководитель команды технической поддержки стрима корпоративных продуктов и сервисов в MWS, занимаюсь технической поддержкой и сопровождением продуктов линейки Partner Experience Platform.

В прошлом материале я рассказал о том, как мы с коллегами попробовали искать аномалии в логах наших систем с помощью методов машинного обучения. Сейчас мы провели работу над ошибками, все переработали (архитектуру, математический аппарат), внедрили генеративную LLM и Principal Component Analysis — и в итоге создали новую систему анализа жизни продуктов, которая самостоятельно балансирует, обучается, выявляет аномалии, паттерны и даже заглядывает в будущее.

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

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

Представьте семинар у физиков или математиков. Идёт автоматическая запись лекции, а затем распознавание речи в аккуратный текст. В большинстве мест современные ASR-системы справятся неплохо. Но значительная часть такой записи будет состоять из фраз вроде «интеграл от икс в квадрате до бесконечности», «сумма по i от единицы до n» или «производная по t от функции f».

Формально голос может быть распознан правильно. В расшифровке даже могут появляться отдельные символы вроде +, π или x. Но если человек произносит длинную формулу, результат почти всегда превращается в линейную фразу, читать которую физически больно. Хочется другого: чтобы система сразу понимала, где обычный текст, где математическое выражение, и выдавала не «один делить на икс плюс два», а корректный LaTeX-код, например, \frac{1}{x+2} или \frac{1}{x}+2, в зависимости от смысла.

Эта задача называется Speech-to-LaTeX или S2L: преобразование озвученных математических выражений и предложений в формальную LaTeX-запись. В отличие от обычного speech-to-text, здесь нужно распознать не только слова, но и структуру: дроби, индексы, степени, пределы, суммы, интегралы, скобки, вложенные выражения и границы формул.

Например, фраза «два делить на пи» в обычной расшифровке может остаться как «2 делить на π». Но в LaTeX она должна стать \frac{2}{\pi}. Именно такой формат нужен для статей, учебников, конспектов, Overleaf и других LaTeX-редакторов.

Несмотря на прогресс в automatic speech recognition (ASR), задача прямого преобразования озвученной математики в LaTeX долго оставалась почти неразработанной. Более того, нормальных открытых датасетов с человеческими аудиозаписями для такой задачи практически не было. В нашей работе мы попытались закрыть этот пробел: собрали открытый двуязычный датасет и сравнили несколько подходов к Speech-to-LaTeX. В статье, которую мы представили на ICLR 2026, описан датасет из более чем 66 тысяч человеческих аудиозаписей и 571 тысячи синтетических аудиозаписей на английском и русском языках. 

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

Логическим продолжением будет изучение (не побоюсь этого слова) сердца машинного обучения: градиентного спуска.

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

Как я улучшил универсальный код Элиаса 1975 года, заменив длину на popcount — и получил 36% экономии на метаданных. С бенчмарками! Картинка на обложке кринжовая, но тут вроде так принято? 😅