Математика *

Мы поговорим о модели песчаной кучи. Песок (не настоящий, модельный), пересыпаясь, создаёт вот такие картинки:



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

А ещё можно использовать эту штуку в качестве Hello world вместо игры «Жизнь».

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

В 1935 году Альберт Эйнштейн совместно с Борисом Подольским и Натаном Розеном пытались справиться с возможностью, открывшейся вместе с новыми законами квантовой физики: с «запутанностью» двух частиц, которые при этом могут быть разделены огромным расстоянием.

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

В первой части поста мы рассказали о наших популярных онлайн-курсах на Stepik, а теперь выкладываем записи открытых лекций и видеокурсов на YouTube.

Начало здесь.

Disclaimer 1

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

Disclaimer 2

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

Как мы увидели в прошлой части, режим самоизоляции достаточно эффективен, в частности он сбивает экспоненциальный рост числа заболевших до степенного и тем самым позволяет снизить нагрузку на здравоохранения до приемлемой (“flatten the curve”, ага). Тем не менее, режим самоизоляции длится очень долго, наносит огромный ущерб экономике и возникает резонный вопрос: нельзя ли обойтись пусть более жесткими, но краткосрочными мерами?

Для наглядности экспериментов я слегка модифицировал инфекционный агент, сделав его чуть менее заразным, для большей иллюстративности интересующих нас эффектов. Помимо этого, я снизил порог насыщения минздрава до 5% популяции (это все равно очень и очень много). И да, чтоб не слишком ранить чувствительные души, шанс смерти индивидуума, которому «не досталось койки», вырастает теперь в три раза, а не в десять, как раньше. Цените мой гуманизм! Остальные параметры такие же (самое важное: инкубационный период, когда пацак заразен, длится 10 дней и столько же длится период лечения).

Математики доказали, что копиями графов меньшего размера всегда можно идеально покрыть графы большего размера

8 января трое математиков опубликовали доказательство теоремы из комбинаторики, сформулированной почти 60 лет назад, известной, как гипотеза Рингеля. Грубо говоря, она предсказывает, что графы – конструкции, состоящие из точек и линий – можно идеально сложить из одинаковых частей меньшего размера.

Математики с восторгом приняли подтверждение этой гипотезы.

«Счастье в том, что эта работа решает очень старую гипотезу, которую невозможно было проверить другими методами», — сказал Гил Калай, математик из Еврейского университета в Иерусалиме, не связанный с этой работой.

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

Disclaimer 1

Я математик, НЕ ВРАЧ и не являюсь профильным специалистом-эпидемиологом, а свою последнюю научную работу на тему матмоделирования эпидемий написал без малого 20 лет назад. По всем вопросам здоровья, коронавирусов и смысла жизни консультируйтесь с лечащим врачом, не будьте глупыми людьми.

Disclaimer 2

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

Ну, а теперь — поехали! По понятным причинам, ныне изрядно подскочил интерес ко всякому пандемическому, и всевозможные математические и не очень математические модели бродят по соцсетям стаями. Число же эпидемиологов и специалистов по системам дифференциальных уравнений и вовсе превысило все мыслимые пределы. Тем не менее, во всем этом информационном буйстве странным образом обойдены молчанием перколяционные, они же стохастические имитационные, модели. Этот недостаток мы сейчас немедленно исправим. Кстати, впервые о подобных моделях (как и многом другом) я прочитал в замечательной книжке Гулда и Тобочника «Компьютерное моделирование в физике».

Coderik однажды отметил: "Фильтра Калмана много не бывает". Так же можно сказать и о теореме Байеса, ведь это с одной стороны так просто, но с другой стороны так сложно осмыслить её глубину.

Computer Science Center — это совместная инициатива Computer Science клуба при ПОМИ РАН, компании JetBrains и Школы анализа данных Яндекса.

Центр существует, чтобы дать возможность талантливым студентам и выпускникам развиваться в интересных им направлениях: Computer Science, Data Science или Software Engineering.

В этой части выкладываем записи наших популярных онлайн-курсов на Stepik и напоминаем о том, что до 11 апреля открыт новый набор в CS центр в Санкт-Петербурге и Новосибирске.

Хабр, это снова я, Алексей Рак (фото не мое). В прошлом году, помимо основной работы, мне довелось стать одним из авторов задач для кандидатов в Яндекс. Сегодня наша команда впервые за долгое время публикует на Хабре реальные задачи для разработчиков, которые устраиваются в компанию. Эти задачи использовались до февраля 2020 года при отборе на стажировку для бэкендеров. Решения проверял компьютер. Сейчас кандидатам достаются похожие задания.

Разборы и код сознательно спрятаны в спойлеры. Если вы готовитесь к собеседованиям в большие IT-компании, попробуйте решить одну или несколько задач, прежде чем смотреть разбор. Отправить решение для проверки можно на Codeforces — ответ придёт сразу же (ссылка на Codeforces и примечание). Код представлен на Python, C++ и Java. Важно: авторский «олимпиадный» код не предназначен для продакшена, он написан исходя из того, что система будет проверять его автоматически.

Наверняка каждому доводилось летать в полупустом самолете или встречаться с переносом рейса, возможно вы задумывались об оптимальности затрат и эффективности такого рейса. Сколько потенциальной прибыли недополучает авиакомпания? Действительно, рейсы бывают малоприбыльными, а иногда даже убыточными. Могут ли быть такого рода решения объяснимы с точки зрения оптимального поведения авиаперевозчика? Например, в текущей ситуации с отменой рейсов из-за COVID-19: как распределяется парк самолетов по другим направлениям, что обеспечивает локальную норму прибыли? Давайте попробуем построить динамическую модель, которая будет реагировать на внешние изменения и стремиться прийти к состоянию равновесия. В данной статье возьмем лишь небольшой набор параметров, попробуем спрогнозировать спрос, отправлять самолеты меньшей вместимости, снижать частоту рейсов когда это невыгодно.

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

Летальность — это вероятность умереть, если у пациента диагностирована болезнь. Вот цитата из научной статьи:

one of the most important epidemiologic quantities to be determined is the case fatality ratio—the proportion of cases who eventually die from the disease.

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

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

Пусть есть два игрока, A и B, которые многократно разыгрывают некоторую игру. Каждый игрок в каждом розыгрыше придерживается одной из нескольких стратегий — для простоты будем считать, что количество стратегий для обоих игроков совпадает и равняется $$. При выборе $$-й стратегии первым игроком и $$-й стратегии вторым игроком первый игрок получит выигрыш $$, а второй игрок получит такой же проигрыш — так уж устроены антагонистичные игры. Эти выигрыши можно записать в виде квадратной матрицы $$:

$$

Игроки разыгрывают игру многократно и могут использовать разные стратегии в разных розыгрышах. Смешанная стратегия — это вектор вероятностей, сопоставленных каждой из чистых стратегий игрока. Каждый игрок выбирает одну из стратегий в очередном розыгрыше в соответствии с вероятность, определённой для неё его смешанной стратегией. Если обозначить через $$ и $$ смешанные стратегии игроков, то математическое ожидание выигрыша первого игрока будет равняться

$$

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

$$

Вот поиском таких равновесий мы сейчас и займёмся.

Привет, Хабр! Продолжаем публиковать рецензии на научные статьи от членов сообщества Open Data Science из канала #article_essense. Хотите получать их раньше всех — вступайте в сообщество!

Представлены обзоры 11 статей по Computer Vision, Natural Language Processing, Reinforcement learning и другим темам.

Учёные-информатики вышли на новые рубежи в деле проверки решений задач вычислительными методами. При этом они нашли ответы на важнейшие открытые вопросы квантовой механики и чистой математики.

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



В следующем году Алан Тьюринг сформулировал первую общую теорию вычислений, и доказал, что существуют задачи, которые никогда не смогут быть решены компьютерами. 

Эти две идеи произвели революцию в тех областях наук, к которым они относятся. Кроме того, казалось, что они не имеют никакого отношения друг к другу. Но теперь доказательство MIP* = RE их скомбинировало, что привело к решению множества задач в сфере информатики, физики и математики.

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

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

Почему это важно? Попробую рассказать за пару минут.

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

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

Начинаем мы вот с этой простой картинки:

Мозг — мой давний сосед. Учитывая то, сколько времени мы провели, и сколько нам еще предстоит быть вместе, не интересоваться им — полнейшая бестактность.

Ходишь с черным ящиком внутри черепной коробки, и этот ящик понимает, что он сам себе дает такое описание. Это же очень любопытно. Если бы мне дали железку с такими возможностями, я бы все свободное время убил на то, чтобы понять, как она работает. Собственно, я и убиваю. Объект исследования всегда при мне — очень удобно. Жаль только, внутри покопаться нельзя.

Мозг записывает и обрабатывает информацию. Но как? Почему что-то хранится долго, а что-то забывается за пару дней? Как это связано с нейронами?

Можно ли, основываясь на информации из нейробиологии, построить модель мозга дающую похожее на реальный мозг поведение?

А что гадать? Давайте просто попробуем.

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

Получилось примерно так:



Под катом будет еще, берегите трафик.

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

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

TL;DR: Описан небольшой скрипт для Octave/MATLAB, позволяющий оценить ошибки расчёта углов ориентации по измерениям МЭМС акселерометров и магнитометров. На входе скрипта — параметры датчиков из даташитов (и/или погрешности калибровки). Статья может быть полезна тем, кто начинает использовать инерциальные датчики в своих устройствах. Небольшой ликбез по датчикам прилагается. Ссылка на гитхаб тоже.

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

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

Но, что мне показалось особенно интересным, это то, что новое произведение также позволяет нам «порассуждать» о таких фундаментальных вещах, как непрерывность пространства-времени. Это рассуждение, конечно, нужно рассматривать, скорее, как интеллектуальное упражнение.

Мне показалось, что этот математический ребус или, если хотите, небольшое математическое путешествие на уровне знаний первого-второго курса технического ВУЗа может заинтересовать читателей Хабра, интересующихся математикой.