Математика *

Образовательные программы компьютерных наук и информатики обязательно включают курс алгоритмов, это элегантные решения сложных проблем. Например, одна из самых интересных проблем комбинаторной оптимизации — задача коммивояжёра (TSP, travelling salesman problem). Суть в поиске самого выгодного маршрута, проходящего через указанные точки ровно по одному разу. Сложность задачи при точном решении брутфорсом составляет O(n!). И для неё тоже придумано несколько элегантных алгоритмов. Хотя поиск самого эффективного продолжается до сих пор.

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

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

Что такое Закон больших чисел — и действительно ли он объясняет, почему вероятности «работают»? В этой статье мы разбираемся с этим шаг за шагом: начинаем с конкретных задач, выводим неравенство Чебышёва, формулируем и доказываем ЗБЧ — аккуратно и строго.

В финале обсуждаем, что ЗБЧ на самом деле утверждает, и почему он не доказывает принцип, на котором построена вся теория. А ещё — подготовим почву для разговора о Центральной Предельной Теореме.

В мире существует множество производителей диванов, например: Poltrona Frau, Ligne Roset, Minotti, Edra, COR, W. SCHILLIG (все эти производители из Европы), некоторые из них занимаются изготовлением мебели уже очень давно. Их диваны иногда получают собственные названия, поэтические и оригинальные. Есть также много выдающихся дизайнеров мебели, для спроектированных ими диванов помимо собственного названия также часто указывается имя дизайнера, например, диван "Ма джонг" Ханса Хопфера. Однако мне хотелось бы рассказать о диване, названном в честь математика, сконструировавшего его теоретически. Не уверен, что существуют воплощения этого дивана в виде реального предмета мебели, но он является довольно известным среди ученых, да и просто любителей математических головоломок

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

«Это огромный триумф. Но вместо того, чтобы закрыть дверь, это доказательство открывает дюжину других», — говорит Дэвид Бен-Цви из Техасского университета в Остине, который не принимал участия в работе.

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

Несколько лет назад я посмотрел отличную презентацию от Дирка. В ней он описывал теорему о разделяющей оси, пролегающей между выпуклыми многогранниками (видео, слайды). Примерно на 18 минуте (слайд 29) он заводит речь о наложении гауссовых отображений выпуклых многогранников — как они помогают найти грани разности Минковского для этих многогранников.

Недавно я прочёл книгу «Кому нужна математика?» Нелли Литвак и Андрея Райгородского — и она меня по-настоящему зацепила. Это короткие, живые рассказы о том, как математика помогает решать важные и неожиданные задачи: от составления расписаний до защиты интернет-трафика. В этом посте я перескажу три истории из книги, которые особенно меня удивили

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

Как оптимально составлять расписания с помощью раскрасок графов?

Знакомы с правильными раскрасками графов? Существуют и много других видов раскрасок. Мы рассказываем про дефектные раскраски — мощный инструмент для решения задач составления расписаний. В статье представлены результаты работы команды в рамках Большой математической мастерской в НГУ.

Что мы сделаем в статье:
⠀⠀⠀— Объясним связь между двумя задачами: задачи раскраски графов и задачи составления расписания.
⠀⠀⠀— Рассмотрим как вершинные, так и реберные раскраски.
⠀⠀⠀— Укажем как жадные, так и точные алгоритмы решения задачи.
⠀⠀⠀— Расскажем некоторые важные свойства раскрасок.
⠀⠀⠀— Дадим оценки хроматическим числам и индексам.

Вам знакомо такое выражение: 1 доллар — тому кто придумал, 2 — тому кто сделал и 10 — тому кто продал? Думаю, каждый прочувствовал на себе все «прелести» капитализма и у каждого есть мнение на этот счет. Реалистичный, взрослый взгляд на все это состоит в понимании простой истины: мир — это рынок, а идеи и их реализация — все это убытки до тех пор пока нет продаж. Но на самом деле продажи — это просто наука и как любая наука она обладает внутренними, очень глубокими проблемами и очень сильными противоречиями. Обо всем этом и пойдет речь в данной статье.

Перечитал давний доклад академика Арнольда В.И. о сложности последовательностей нулей и единиц, в которй он использует монады для определения сложности.

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

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

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

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

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

Большое количество расчётных задач, в которых использован этот приём, представлено в первом русском учебнике геодезии [1]. Приведу пример — задачу определения высоты далеко расположенной горы QP с учётом кривизны земного шара (см. рис. 1).

Прошлым летом в свет вышла новая архитектура нейронных сетей под названием Kolmogorov-Arnold Networks (KAN). На момент выхода статьи про KAN эта новость произвела фурор в мире машинного обучение, так как KAN показывала существенный прирост в качестве аппроксимации различных сложных функций. Ошибка новых сетей падает значительно быстрее при увеличении числа параметров. Однако, за все приходится платить, и цена таких маленьких значений функции ошибки - медленное обучение: KAN обучается примерно в 10 раз медленнее, чем старый добрый MLP. Из всего этого возникает вопрос: насколько все же уместно использование новой архитектуры вместо привычных всем MLP?

В данной статье будет найдена функция, которая может быть реализована с помощью двухслойного KAN полиномиальной ширины, но не может быть приближена никакой двухслойной ReLU MLP сетью с полиномиальной шириной

Мой первый опыт публикации и рассказ о том, как я за четыре недели сделал рабочую альфа-версию покер-бота. В проекте использованы методы Монте-Карло, компьютерное зрение (YOLO), Python и инструменты вроде Cursor и Roboflow.

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

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

В компьютерных RPG часто бывает три концовки: добрая, злая и true ending. В данном случае реальная жизнь повторяет за геймдевом, и в истории бесконечности все эти сюжетные ветки также присутствуют. Под катом я расскажу, в чём их смысл и какие персонажи класса «математик» прошли игру «Жизнь» с этими концовками.

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

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

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

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

Сейчас на Хабре много пишут о галлюцинировании нейронных сетей и больших языковых моделей в частности. Хорошим введением в эту тему, написанным с философских позиций, мне представляется текст уважаемого Дэна Рычковского @DZRobo «Когда ИИ закрывает глаза: путешествие между воображением и галлюцинациями». Базовое техническое погружение в тему вы найдёте в статье уважаемой @toppal «Причины возникновения галлюцинаций LLM», это перевод академической статьи специалистов Харбинского технологического института, опубликованной в конце 2024 года. Действительно, в большинстве источников галлюцинации ИИ рассматривают либо в негативном ключе, либо как неизбежный побочный эффект, связанный с попытками «вшить» синтетический аналог воображения в вычислительную сеть.

Я же хочу остановиться на менее известном аспекте работы нейронок, в котором галлюцинации могут восприниматься как положительная и даже необходимая часть работы алгоритма. Речь пойдёт об искусственном повышении размерности данных, подаваемых на вход в нейросеть, и о том, к чему такая практика может приводить. Наиболее известное проявление такого эффекта известно в англоязычных источниках под названием «проклятие размерности» (curse of dimensionality).