Мой любимый автор книг по математике Очков Валерий Федорович предложил задачу для среды SimInTech. На самом деле он вызвал меня на дуэль и предложил выяснить, кто лучше сделает решение определенной задачи в виде структурной схемы.
Задача связана с остойчивостью судна, а значит с нахождением центра масс, тела погруженного в жидкость. Поэтому на картинке Пифагор объясняет Архимеду как найти площадь путем обстрела мишени.
В недавней статье про Закон больших чисел мы оценивали вероятность больших отклонений с помощью неравенства Чебышёва. Для тысячи бросков монетки оно даёт границу 2,5% для отклонения в 100 и более орлов. Мне стало интересно, насколько это близко к правде.
Я написал симуляцию и проверил — сначала на сотне прогонов, потом на тысяче, потом на ста тысячах. Ни одного такого исхода. Реальная вероятность оказалась меньше 5 ⋅ 10⁹ — катастрофически меньше, чем 2,5% из оценки Чебышёва. Именно это стало поводом для написания статьи.
Мы хотим понять, как связано число испытаний, отклонение и вероятность. Если зафиксировать отклонение, какова вероятность его превышения? Если зафиксировать вероятность, каким должно быть допустимое отклонение? И, наконец, если заданы и вероятность, и отклонение, то сколько испытаний нужно провести, чтобы с заданной вероятностью уложиться в эти рамки?
В этой статье мы начнём с эксперимента и дойдём до строгой экспоненциальной оценки, которая работает для любого числа испытаний. По дороге докажем оценку Чернова и выведем частный случай неравенства Хёффдинга и разберём, как они устроены.
Такие оценки широко используются в прикладной математике. Нам важно заранее знать, сколько испытаний провести, чтобы с частота с заданной точностью приблизилась к истинной вероятности события.
Например, для расчёта необходимого числа наблюдений, достаточных чтобы с заданной вероятностью обнаружить статистически значимое отклонение. Зная допустимую вероятность ошибки и величину эффекта, можно заранее понять, сколько данных нужно собрать, чтобы выводы были обоснованными.
Разница между прогнозами, которые дают неравенство Чебышёва и экспоненциальные оценки, может быть колоссальной!
В поиске решения сложной задачи, часто помогает определённая организованность. Например, вы можете разбить задачу на части и сначала решить самые простые. Но такая сортировка имеет свою цену. В итоге вы можете потратить слишком много времени на то, чтобы расставить части по порядку.
Эта дилемма особенно актуальна для одной из самых знаковых проблем в информатике: поиска кратчайшего пути от определённой начальной точки сети до всех остальных точек. Это похоже на усовершенствованную версию задачи, которую приходится решать при каждом переезде: поиск оптимального маршрута от нового дома до работы, спортзала и супермаркета.
"Кратчайший путь — это прекрасная задача, которую может понять любой человек в мире», — говорит Миккель Торуп, специалист по информатике из Университета Копенгагена.
Всем привет. Сегодня хочу затронуть тему матана, чтобы показать как его можно применять на реальных задачах. Думаю каждый, кто учил матан часто задавался вопросами: «Где это вообще пригодится?», «Зачем это нужно?», «Как это может помочь?» и т. д. Так вот, чтобы эти вопросы отпали раз и навсегда предлагаю свой топ-5 алгоритмов из курса матана с конкретными примерами их применения в работе.
Если вдруг автомобильный дилер скажет про свои автомобили, что у них под капотом двигатель, цикл которого состоит из двух изотерм и двух адиабат и коэффициент полезного действия .., короче «Цикл Карно — идеальный термодинамический цикл». То вы наверно покрутите у виска пальцем (к счастью не все покрутят и некоторые поймут и выслушают, может даже потом объяснят тем, кто хочет слушать) и пойдёте к другому. Но эти слова — правда и ничего кроме правды, но она вам не нужна.
Но вот это «звук винтажного двигателя V-8 „давно считался призывным вызовом „Мустанга“, готового к спариванию“ (mating call of Mustang), новая система обработки и усиления звука „спортивна и энергична“, обеспечивает „более изящное рычание“ и „низкочастотное ощущение всемогущества“» — полная туфта всего лишь для почёсывания ЧСВ потенциального покупателя и на качество движения никак не влияет.
Вот сейчас то же самое, слово в слово происходит в ИТ с его хайпом вокруг ИИ.
Будучи ребёнком 1990-х годов, я не мог обойти стороной игру-бестселлер «Тетрис». Созданный в 1984 году российским программистом Алексеем Пажитновым, «Тетрис» быстро стал блокбастером, и за прошедшие годы в него сыграли сотни миллионов человек. Я сам часами играл в него на Game Boy, пытаясь расположить падающие фигуры так, чтобы они как можно плотнее заполняли игровое поле. Со временем игры эти блоки начинают падать все быстрее и быстрее, и мои большие пальцы едва успевали за управлением игрой.
В принципе, все игры — даже такие разные, как Candy Crush Saga, Magic: The Gathering и Wordle, — можно изучать с точки зрения математики. Но «Тетрис» имеет много особых связей с математикой. Например, цель игры сильно напоминает геометрические задачи о паркете, в которых вы определяете, можно ли покрыть область бесконечно большим набором плиток без зазоров.
В 1957 году, когда компьютеры программировались на машинных кодах и ассемблере, канадский учёный Кеннет Айверсон задумался: как сделать описание алгоритмов столь же строгим, как математические формулы, но при этом ещё и сделать интерактивном исполняемым? Да-да, интерактивный язык в 60-х, задолго до пайтона, перла и тикля.
Так родился APL — сначала как академический инструмент для описания алгоритмов в книгах (например, в его работе "A Programming Language" 1962 г.), постепенно эволюционировавший в исполняемый язык.
Но причём здесь 2025-й год спросите вы?
Data Science: APL опередил NumPy/Pandas на 40 лет — матричные операции здесь вшиты в ядро.
Обучение: Лучший способ понять SVD или преобразование Фурье — записать их в APL.
Прототипирование: Проверить идею можно быстрее, чем ChatGPT сгенерирует ответ.
Почему об этом мало говорят?
Образовательные программы компьютерных наук и информатики обязательно включают курс алгоритмов, это элегантные решения сложных проблем. Например, одна из самых интересных проблем комбинаторной оптимизации — задача коммивояжёра (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 веке логарифмов для замены при расчётах умножения и деления.
