Математика *

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

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

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

• Когда может потребоваться резервуарное сэмплирование.

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

• Простой способ реализации резервуарного сэмплирования на случай, если вам оно понадобится.

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

Этими словами заканчивалось письмо Эвариста Галуа, написанное для своего друга Огюста Шевалье за два дня до его смерти от полученных на дуэли ран на 21 году жизни. Ни Якоби, ни Гаусс в его теоремах не разобрались, зато спустя 15 лет разобрался Жозеф Лиувилль и опубликовал работы Галуа, ставшие впоследствии фундаментом современной алгебры, известные сейчас как теория Галуа. В статье расскажу про одну из частей этой теории - поля Галуа, получившая настолько повсеместное применение в криптографии и избыточном кодировании, что Intel и AMD выпустили набор процессорных расширений для эффективной реализации операций над этими полями.

Заметка! Если вам довелось использовать/реализовывать поля Галуа, то большая часть статьи для вас скорее всего будет не интересна, но возможно в последних разделах будет что-то для вас новое.

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

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

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

Давайте начнём с чего-то близкого нам: цен на недвижимость. Большие дома стоят больше, маленькие — меньше. Подобный паттерн можно заметить даже без анализа: чем больше места, тем дороже.

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

Взаимное движение цены и размера как будто предсказуемо. Однако оно не ограничено фиксированными шагами или категориями, их масштаб скользит. Дом может стоить 180 тысяч, 305 тысяч или иметь какую-то промежуточную цену.

Теперь представьте, что вы продаёте свой дом. Его площадь 1850 квадратных футов (~172 квадратных метра) — больше среднего, но явно не особняк. Вы видели, почём продаются дома в вашем районе, но цены колеблются. Какой будет справедливая цена?

Я бы хотел, чтобы это была книга. Но пока это не книга. Просто статьёй тоже не назвать. Трактат? Слишком громко сказано, наверное. Я не знаю, что это. Просто начните читать предисловие.

Помните, как долго выполняется сложение на бумаге?

¹¹ ¹
6876
+ 3406
------
10282

Начиная с единиц, мы складываем 6 + 6 = 12, записываем 2 и переносим 1. Затем пошагово двигаемся влево, пока складываемые разряды не закончатся.

При реализации сложения больших чисел (например, от 2⁶⁴ и выше) обычно пишут код, похожий на этот алгоритм. Любопытно здесь то, что существует простой трюк, позволяющий существенно ускорить этот процесс на современных CPU.

Но сначала я задам вопрос: почему сложение столбиком мы начинаем с самого младшего разряда? Почему бы не начать слева?

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

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

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

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

Я написал на C++ прототип для собственного движка, а потом решил, что будет интересно попробовать запустить его в браузере при помощи WebGPU API. Он заработал на удивление хорошо, позволяя создавать подобные симуляции.

В посте я расскажу, как он устроен внутри.

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

Что объединяет частицу в воде, биржевой курс и кота Барсика, бродящего по району в поисках ларька с рыбой?

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

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

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

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

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

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

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

Привет, меня зовут Диана. Я математик и автор хабраблога МТС. В прошлый раз рассказывала о поверехностях второго порядка, а сегодня хочу обсудить изящную топологичекую теорему, у которой есть внезапные приложения в жизни — географии, экономике и политике. Ее следы можно найти в алгоритмах дележки, когда нужно распределять по долям какой-то неоднородный ресурс — данные, вычислительные мощности, бюджет. Например, с ее помощью можно разделить участки земли между фермерами, учитывая разные параметры: площадь, тип почвы, удаленность от дороги и прочее. Она такая немножко Сейлор Мун — за добро и справедливость.

Этот пост мог бы иметь кликбейтное название в духе «На противоположной стороне Земли сейчас такая же погода, как у вас!», но это не совсем верно. Почему — объясню ниже. А пока предлагаю разобраться с официальными формулировками и переложить их на понятный язык. Еще в тексте будут ссылки на связанные проблемы, которые научат нас грамотно резать бутерброды и причесывать ежей — в общем, надеюсь, получилось познавательно!

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

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

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

Казалось бы, детская задачка, где нужно просто “вспомнить формулу”, но всё не так однозначно. Если задать этот вопрос прохожему, он, скорее всего, скажет ½. Преподаватель математики, возможно, ответит ⅓. Кто из них прав?

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

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

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

В этой статье — три таких истории. В первой один и тот же факт даёт разные вероятности, если по-разному устроено наблюдение. Во второй один и тот же объект может быть “случайным” множеством способов. А в третьей невозможно придумать, как сделать задачу математически строгой.

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

А пока — вернёмся к соседям с мальчиком. Разберемся, почему эта задачка не так проста, как кажется на первый взгляд.

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

Можно сразу отбросить никчёмную аналогию с вибрирующими полями как разновидность псевдонаучной фантастики, но идея универсального архива всех возможных текстов, наглядно представленная Хорхе Луисом Борхесом в рассказе «Вавилонская библиотека», подозрительно напоминает гипотезу цифровой мультивселенной – Конечного ансамбля всех математически возможных миров. А если углубиться в метафизику, мы непременно придём к платоновскому миру идей, в котором все вечные истины и прообразы вещей существуют независимо от нашего желания и веры. Чем тогда ясновидящие хуже математиков, которые верят, что доказательства теорем приходят им свыше? Чем античный миф о мойрах, плетущих нити судьбы, уступает релятивистской теории блок-вселенной, где вся ваша жизнь записана в виде пучка мировых линий? А гипотеза математической Вселенной Макса Тегмарка – разве это не предельный платонизм? Так может, вообще не существует ничего, кроме мира идей, а наша материальная действительность – всего лишь иллюзия? Или нам следует лучше разобраться с тем, как работают поисковые алгоритмы Вавилонской библиотеки?

Сложность текста: 2-3/5

Необходимые знания: должно быть достаточно основ теории многочленов, например, формул Виета

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

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

Естественно, настоящим математикам это надоело. В начале 2017 года на Reddit появился пост с заголовком «Меня утомила вся эта фейсбучная фруктовая математика. Хочет кто-нибудь придумать действительно сложную математическую задачу, чтобы побороться с этим явлением?».

Представьте себе мяч, который летит и упруго отскакивает от наклонной плоскости под углом 45°. Интуитивно понятно, что при абсолютно упругом ударе без трения он подчиняется тому же правилу, что и световой луч: угол падения равен углу отражения. То есть траектория мяча после удара симметрична траектории до удара относительно перпендикуляра к поверхности в точке. Этот факт существенно упрощает анализ движения – вместо того чтобы рассматривать изломанную траекторию с отражениями, можно воспользоваться принципом зеркального отображения.

Суть принципа в том, что каждый отскок о плоскость можно заменить продолжением движения мяча по прямой линии в “зеркальном” пространстве...

Diva Philippica, vox ubi coelica nunc Ciceronis?
Pax ubi civibus atque rebellibus ira Catonis?
Nunc ubi Regulus aut ubi Romulus aut ubi Remus?
Stat Roma pristina nomine, nomina nuda tenemus.

Божество филиппик, где ныне небесный голос Цицерона?
Мир где для граждан, а для мятежников где гнев Катона?
Где же Регул, где Ромул, где Рем?
От Рима осталось лишь имя. Имена, что мы держим — пустые.

Отсылкой к последней строке этого стихотворения Бернарда Клюнийского заканчивается "Имя розы" - знаменитый роман итальянского писателя-постмодерниста, философа и медиевиста Умберто Эко. В этом произведении одной из сюжетных линий идёт спор монахов-схоластов об истинности реализма и номинализма или, иначе говоря, о реальности абстрактных идей и математических структур. Именно об этом философском споре, растянувшемся на тысячелетия, я и хотел бы поговорить в своём сегодняшнем эссе. Последние слова великолепного стихотворения, которое в полном варианте на языке оригинала можно послушать здесь, дали название не только роману Умберто Эко, но и этому посту. Nomina nuda tenemus - "имена, что мы держим, пустые".

Что вы скажете, если я расскажу вам, что знаю метод разложения чисел на множители, который не так сложен, как алгоритмы QS и GNFS, основывается не на магии, а на логике и простых арифметических принципах, легко реализуется, его легко распараллелить для ускорения вычислений, он не требует много памяти и при этом зачастую в разы эффективнее метода Ферма́? Заинтересовало?

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

Примеры, объяснения, таблицы — всё на месте. Даже если вы забыли, что такое , вы всё равно поймёте, как это работает.