Математика *

В прошлый раз мы загрузили данные из файла, разобрали их в структуру, получили уравнения треков движения ТС и графически отобразили эти данные: Часть 1

В данной статье одним из методов найдем статистически точку, в окрестностях которой пересекаются треки движения ТС.

Бытует мнение, что только 10% программистов способны написать двоичный поиск. Это мнение мы испытывать не будем, но что насчёт квадратного уравнения?

Поставим задачу конкретнее: решение квадратного уравнения вида ax²+bx+c=0 с целочисленными коэффициентами. На вход подаются три целых числа в рамках int (коэффициенты a, b и c). Программа должна всегда выдавать результат.
Казалось бы, плёвое дело: пять минут и готово! И вот спустя те самые пять минут имеем на выходе следующий код:

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

Вот так выглядит доказательство от противного того, что полином всегда имеет комплексные решения:



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

Взглянуть на ленту можно здесь.

Постановка задачи

Имеется система, размещаемая над дорожным полотном, включающая в себя видеокамеру. Известны разрешение видеокамеры и углы обзора. Относительно дорожного полотна видеокамера устанавливается следующим образом: сверху над любой из полос движения, сбоку от дорожного полотна не далее, чем 3 метра от края ближайшей контролируемой полосы движения. Количество одновременно контролируемых полос движения — не более 4. Видеокамера производит фотографирование зоны контроля с определенной частотой кадров. Все сделанные кадры поступают на вход системы распознавания номерных знаков. Результатом проезда транспортного средства (далее по тексту -ТС) является трек с координатами центра рамки номерного знака ТС в виде:

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

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

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

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

Введение

Зачем это вообще надо? В науке и около нее очень часто возникает задача предсказания какого-то неизвестного параметра объекта исходя из известных параметров этого объекта (предикторов) и большого набора похожих объектов, так называемой учебной выборки. Пример. Вот мы выбираем на базаре яблоко. Его можно описать такими предикторами: красность, вес, количество червяков. Но как потребителей нас интересует вкус, измеренный в попугаях по пятибалльной шкале. Из жизненного опыта нам известно, что вкус с приличной точностью равен 5*красность+2*вес-7*количество червяков. Вот про поиск такого рода зависимостей мы и побеседуем. Чтобы обучение пошло легче, попробуем предсказать вес девушки исходя из ее 90/60/90 и роста.

Этот пост поможет вам выкрутиться из довольно-таки щекотливой ситуации. Скажем, вы заперты в комнате, у вас есть моток ниток и иголка, и от вас настойчиво требуют посчитать приблизительное значение числа Пи, используя лишь эти предметы, ну, всякое бывает, знаете. Так вот, сегодня слушая на курсере курс по матану Пенсильванского университета, я вдруг узнал, как это сделать. Вот чего я и предположить не мог, так это того, что число Пи скрывается и тут. Оказалось, что корни этого вопроса уходят аж в 18 век, когда Жорж-Луи Леклерк де Бюффон поставил себе следующую задачу: «предположим, пол сделан из деревянных полосок двух цветов, они чередуются; какова вероятность того, что брошенная иголка упадет так, что будет пересекать линию состыковки двух полосок?» Симуляцию этого процесса и ответ на вопрос можно найти под катом.

Намедни прочел интересную статью про рейтинги. В качестве практического руководства ее не рекомендую использовать (почему смотрите в комментариях к ней), однако, чтиво интересное и натолкнуло меня на одну мысль.
Допустим у нас есть рейтинг от 1 до 5. И некоторые оценки накручены, некоторые пользователи наобум поставили. Как отфильтровать зерна от плевел?

В компании Intel разрабатывают не только ПО для «внешних» потребителей — пишутся и программы, которые используются только внутри Intel. Среди них довольно много средств для численного моделирования различных физических процессов, протекающих при изготовлении процессоров — ведь именно последние и являются основной продукцией Интела. В этих программах, конечно, широко используются различные методы вычислительной математики и физики.
Вот некоторое время назад мне понадобилось программно решать одно уравнение методом Ньютона. Казалось бы, все просто, но для этого надо уметь вычислять производную левой части уравнения. Эта левая часть у меня была довольно сложная — даже просто вычисление ее значений в программе было разбросано по нескольким функциям, — и перспектива вычислять производную на бумажке меня не радовала. Перспектива воспользоваться каким-нибудь пакетом символьных вычислений меня радовала не больше — перенабирать все формулы, содержащие к тому же несколько частных случаев, далеко не очень приятно. Вариант вычислять производную численно как разность значений функции в двух соседних точках, деленную на соответствующее приращение независимой переменной, чреват потерей точности и вообще необходимостью подбирать подходящее приращение этой переменной.
Подумав некоторое время, я применил следующий подход. Потом я узнал, что он называется «автоматические дифференцирование», для него существует довольно обширная литература на английском, и ряд библиотек — но на русском я нашел только некоторые научные статьи про применение этого метода, и пост на Хабрахабре, в котором все рассказывается через смесь дуальных и комплексных чисел, и понять который с ходу, на мой взгляд, тяжело. С другой стороны, для понимания и практического применения автоматического дифференцирования не нужны никакие дуальные числа, и этот подход я тут и изложу.

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

В качестве введения

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

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

В данной и следующей статье я показываю как выбрать для обработки качественных и количественных данных правильные тесты и реализовать их в R. Данные методы позволяют получить реальное представление об объекте, процессе или явлении по какому-либо параметру, т.е. позволяют сказать «хорошо» или «плохо». Они не потребуют глубоких знаний программирования и статистики, и пригодятся людям различного рода деятельности.

Заинтересовались? Добро пожаловать под кат!

В интернете, в том числе и на хабре, можно найти много информации про фильтр Калмана. Но тяжело найти легкоперевариваемый вывод самих формул. Без вывода вся эта наука воспринимается как некое шаманство, формулы выглядят как безликий набор символов, а главное, многие простые утверждения, лежащие на поверхности теории, оказываются за пределами понимания. Целью этой статьи будет рассказать об этом фильтре на как можно более доступном языке.
Фильтр Калмана — это мощнейший инструмент фильтрации данных. Основной его принцип состоит в том, что при фильтрации используется информация о физике самого явления. Скажем, если вы фильтруете данные со спидометра машины, то инерционность машины дает вам право воспринимать слишком быстрые скачки скорости как ошибку измерения. Фильтр Калмана интересен тем, что в каком-то смысле, это самый лучший фильтр. Подробнее обсудим ниже, что конкретно означают слова «самый лучший». В конце статьи я покажу, что во многих случаях формулы можно до такой степени упростить, что от них почти ничего и не останется.

В своей статье я хотел бы рассказать о теории относительности. Эта теория не требуется в представлении. С самого своего создания она была окутана ореолом тайны, поскольку полностью подрывает наши привычные представления о пространстве и времени. Все мы в школе учили формулы теории относительности, но мало кто действительно понимал их. И это не удивительно, ведь человеку, чтобы по-настоящему понять какую-то теорию во всей её красоте, полноте и непротиворечивости, не достаточно знать формулы. Нужно иметь какой-то визуальный ориентир, нужна динамика, чтобы было что-то, что можно повертеть в руках. Я решил восполнить этот пробел и написал небольшую программку, в которой можно «повертеть в руках» пространство-время. Мы, как настоящие исследователи, с помощью небольших экспериментов попытаемся выяснить основные свойства этой загадочной материи.
Под катом много картинок (и ни одной формулы).

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

Уильямс Джей, «Герои Ниоткуда»

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

На хабре уже много-много-много раз писали про игру «Жизнь». Совсем недавно была удивительная статья Жизнь на плоскости Лобачевского. Но игра «Жизнь» является частным случаем т. н. клеточных автоматов. Существует много других клеточных автоматов совсем не похожих на игру «Жизнь», но тем не менее очень интересных. Про некоторые из них и хочется рассказать здесь.

Начнём с того, что рассмотрим ряд клеток, в которых, кроме одной, находятся нули:

... 0  1  0  0  0  0  0  0 ...

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

... 0  1  0  0  0  0  0  0 ...
... 0  1  1  0  0  0  0  0 ...
... 0  1  2  1  0  0  0  0 ...
... 0  1  3  3  1  0  0  0 ...
... 0  1  4  6  4  1  0  0 ...
... 0  1  5 10 10  5  1  0 ...
... 0  1  6 15 20 15  6  1 ...

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

... 0  1  0  0  0  0  0  0 ...
... 0  1  1  0  0  0  0  0 ...
... 0  1  0  1  0  0  0  0 ...
... 0  1  1  1  1  0  0  0 ...
... 0  1  0  0  0  1  0  0 ...
... 0  1  1  0  0  1  1  0 ...
... 0  1  0  1  0  1  0  1 ...

Интересно? Читаем дальше!

Различные реализации игры «Жизнь» описывались на Хабре уже неоднократно. В этой статье, в качестве продолжения этой темы, рассматривается ещё один её вариант: в качестве игрового поля используется регулярная решётка на плоскости Лобаческого. Описываются общие методы использования плоскости Лобачевского в программах и необходимые для этого математические приёмы.
Как возникла плоскость Лобачевского, достаточно известно. В позапрошлом веке господа Гаусс, Лобачевский и Бойяи, проживавшие примерно в одно время в разных странах тогдашней Европы, задумались, что будет, если отменить пятый постулат Евклида и заменить его на противоположную аксиому. Оказалось, что не случится ничего плохого, и никаких противоречий не возникнет. Заметная часть последующего изучения неевклидовой геометрии была посвящена выяснению того, кто из них у кого украл идею этой самой геометрии.
Менее известно, что несмотря на «отрицательный» способ определения неевклидовой геометрии (вместо того, чтобы сказать, что через точку проходит ровно одна прямая, не пересекающая данную, мы говорим, что таких прямых может быть сколько угодно), мы, тем не менее, получаем систему теорем и формул, не менее стройную, чем та, что есть в евклидовой геометрии. И одновременно, у нас есть гораздо большее разнообразие геометрических фигур, в том числе, разбиений плоскости на правильные многоугольники.

Математики из распределённого проекта по поиску простых чисел GIMPS объявили об обнаружении нового простого числа Мерсенна. Это важное событие для математического сообщества, потому что до сих пор было известно только 47 таких чисел, последнее было найдено в июне 2009 года.

48-е простое число Мерсенна — 2^57.885.161-1, с 17.425.170 десятичными разрядами. См. полную запись числа в текстовом формате.

Числа Мерсенна имеют вид 2ⁿ-1, где n — натуральное число. Простые числа Мерсенна являются самыми большими простыми числами, известными науке. Предыдущий мировой рекорд принадлежал числу 2^43.112.609-1, имеющему 12.978.189 десятичных разрядов.

Топология — довольно красивое, звучное слово, очень популярное в некоторых нематематических кругах, заинтересовало меня еще в 9 классе. Точного представления конечно же я не имел, тем не менее, подозревал, что все завязано на геометрии.