Алгоритмы *

Здравствуйте, коллеги. В конце 1960-ых годов прошлого века Ричард Фейнман прочитал в Калтехе курс лекций по общей физике. Фейнман согласился прочитать свой курс ровно один раз. Университет понимал, что лекции станут историческим событием, взялся записывать все лекции и фотографировать все рисунки, которые Фейнман делал на доске. Может быть, именно после этого у университета осталась привычка фотографировать все доски, к которым прикасалась его рука. Фотография справа сделана в год смерти Фейнмана. В верхнем левом углу написано: "What I cannot create, I do not understand". Это говорили себе не только физики, но и биологи. В 2011 году, Крейгом Вентером был создан первый в мире синтетический живой организм, т.е. ДНК этого организма создана человеком. Организм не очень большой, всего из одной клетки. Помимо всего того, что необходимо для воспроизводства программы жизнедеятельности, в ДНК были закодированы имена создателей, их электропочты, и цитата Ричарда Фейнмана (пусть и с ошибкой, ее кстати позже исправили). Хотите узнать, к чему эта прохладная тут? Приглашаю под кат, коллеги.

Демо

Вступление

Метод Уэлфорда — простой и эффективный способ для вычисления средних, дисперсий, ковариаций и других статистик. Этот метод обладает целым рядом прекрасных свойств:

• достигает отличных показателей по точности решений;
• его чрезвычайно просто запомнить и реализовать;
• это однопроходный онлайн-алгоритм, что крайне полезно в некоторых ситуациях.

Оригинальная статья Уэлфорда была опубликована в 1962 году. Тем не менее, нельзя сказать, что алгоритм сколь-нибудь широко известен в настоящее время. А уж найти математическое доказательство его корректности или экспериментальные сравнения с другими методами и вовсе нетривиально.

Настоящая статья пытается заполнить эти пробелы.

Всем привет! Меня зовут Александр, я руковожу отделом Data Team в Badoo. Сегодня я расскажу вам о том, как мы выбирали оптимальный алгоритм для вычисления квантилей в нашей распределённой системе обработки событий.

Зачем всё это надо?

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

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

Без высшей математики мы бы лишились алгоритма Шора для факторизации целых чисел в квантовых компьютерах, калибровочной теории Янга-Миллса для построения Стандартной модели в физике элементарных частиц, интегрального преобразования Радона для медицинской и геофизической томографии, моделей эпидемиологии, анализов рисков в страховании, моделей стохастического ценообразования финансовых производных, шифрования RSA, дифференциальных уравнений Навье-Стокса для прогнозирования изменений движения жидкостей и всего климата, всех инженерных разработок от теории автоматического управления до методов нахождения оптимальных решений и еще миллиона других вещей, о которых даже не задумываемся.

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

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