Рубрика «Алгоритмы»

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

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

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

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

Точное вычисление средних и ковариаций методом Уэлфорда - 1

Читать полностью »

image

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

Краткое содержание первой части:
1. DSTL (научно-техническая лаборатория при министерстве обороны Великобритании) провела соревнование на Kaggle.
2. Соревнование закончилось 7 марта, результаты объявлены 14 марта.
3. Пять из десяти лучших команд — русскоговорящие, причем все они являются членами сообщества Open Data Science.
4. Призовой фонд в $100,000 разделили брутальный малазиец Kyle, команда Романа Соловьева и Артура Кузина, а также я и Сергей Мушинский.
5. По итогам были написаны блог-посты (мой пост, пост Артура, наш с Серегой пост на Kaggle), проведены выступления на митапах (мое выступление в Adroll, мое выстпление в H20.ai, выступление Артура в Yandex, выступление Евгения Некрасова в Mail.Ru Group), написан tech report на arxiv.

Организаторам понравилось качество предложенных решений, но не понравилось, сколько они за это соревнование отстегнули. В Каggle ушло $500k, в то время как призовые всего $100k.
Читать полностью »

Забавной находкой поделился сегодня пользователь fj333 с Reddit. Разбираясь в появившемся год назад проприетарном коде Qualcomm Technologies для Android, он обнаружил, что неизвестный программист решил в production-коде использовать сортировку пузырьком для того, чтобы найти… максимум в массиве.

Посмотреть исходный файл вы сможете по ссылке на Github или же под катом, а оценить его в работе может любой владелец устройства с Qualcomm Snapdragon 200 MSM8610 под управлением Android.

Как известно любому, кто знаком с алгоритмами сортировки, сортировка пузырьком — алгоритм учебный, и в промышленном коде не применяющийся в силу своей неэффективности; дело в том, что в наихудшем и среднем случаях он имеет сложность О(n2), к тому же его емкостная сложность в данном случае — O(n). Кого это не убедило — использовать сортировку пузырьком не рекомендует даже Барак Обама.

И это всё не учитывая того, что для поиска максимума хватило бы и простого перебора.
Читать полностью »

Быстрое восстановление данных. Схема бабочки для регенерирующих кодов - 1

Для кодов, описанных в предыдущей статье про восстановление данных, предполагалась постановка задачи, при которой минимизируется количество дисков, необходимых при операции восстановления. В [2] обсуждается применение сетевого кодирования к задачам хранения данных, получившее значительное внимание исследователей в последние годы. Здесь рассматривается не оптимизация количества дисков, необходимых для восстановления данных, а минимизация возникающего при этом сетевого трафика.

Предположим, что система хранения состоит из n узлов. Рассмотрим файл, состоящий из B символов поля GF(q), который кодируется в nα символов над GF(q) и распределяется по узлам, так, что каждый узел хранит α символов. Код построен таким образом, что данные могут быть целиком восстановлены по информации с k узлов. При этом для восстановления данных одного узла достаточно получить β ≤ α информации с d узлов [1,2], см. рис. 1. Величина γ = dβ называется диапазоном восстановления (repair bandwidth).
Читать полностью »

От переводчика. Перевод статьи 2007 года на arxiv.org о статистическом анализе модификации быстрой сортировки.
Наверняка найдутся люди, использующие описанный вариант интуитивно. Здесь — математическое обоснование эффективности при n <= 7 000 000

Коротко о главном

K-sort: новый алгоритм, превосходящий пирамидальную при n <=7 000 000 - 1

Ключевые слова
Внутренняя сортировка; Равномерное распределение; Средняя временная сложность; Статистический анализ; Статистическая оценка
Читать полностью »

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

Перед вами здание- склад, сгенерированное процедурно:

image
Читать полностью »

На рынке 5D платформ мы уже более 5 лет. За это время у меня накопился солидный багаж знаний, которыми решил поделиться. В первой части я хочу рассказать о проекционных системах, применяемых в этой отрасли, а так же об адаптации нашего ПО под них. Какие решения мы применяли и почему. Я сознательно не зазываю товарный знак, чтобы не сочли, что пост – это просто реклама очередной программы.
Итак. 5D – это прежде всего кинотеатр со стерео контентом. Ведь звуковые или тактильные ощущения для большинства людей не так важны, как видеоряд.
Читать полностью »

Поезда пригородного сообщение — электрички — остаются одним из самых массовых видов пассажирского транспорта в России. За год ими пользуются миллионы пассажиров, которые проезжают суммарно сотни миллиардов километров на тысячах электричек. Только в январе 2017 года, по данным столичного департамента транспорта, опубликованным в едином хранилище данных правительства Москвы (ЕХД), пассажиропоток пригородного железнодорожного транспорта составил 42,6 млн человек. Это выше на 4,1% по сравнению с показателями прошлого года.

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

Меня зовут Александр Подлевских, я ведущий инженер-разработчик компании Туту.ру, тимлид в команде электричек, и в статье расскажу про технические детали и сложности построения онлайн расписания, как все это работает, каким образом мы используем данные, предоставляемые РЖД, и как наши пользователи помогают нам поддерживать расписание в актуальном состоянии, не догадываясь об этом.

Опыт Туту.ру: Как устроено расписание электричек - 1
График движения поездов — это отображение процесса движения поезда в декартовой системе координат. В таком виде представляется график движения поездов на железной дороге.
Читать полностью »

Снимаем «4D видео» с помощью depth-сенсора и триангуляции Делоне - 1

Привет! Это заметка о небольшом хобби-проекте, которым я занимался в свободное время. Я расскажу, как с помощью несложных алгоритмов превращать карты глубины от depth-сенсоров в забавный вид контента — динамические 3D сцены (их ещё называют 4D video, volumetric capture или free-viewpoint video). Моя любимая часть в этой работе — алгоритм триангуляции Делоне, который позволяет превращать разреженные облака точек в плотную полигональную сетку. Приглашаю всех, кому интересно почитать про алгоритмы, самописные велосипеды на C++11, и, конечно же, посмотреть на трёхмерных котиков.

Для затравки: вот что получается при использовании RealSense R200: skfb.ly/6snzt (подождите несколько секунд для загрузки текстур, а затем используйте мышку, чтобы поворачивать сцену). Под катом есть ещё!
Обладатели лимитированных тарифов, будьте осторожны. В статье много разных изображений и иллюстраций.
Читать полностью »

Постквантовая реинкарнация алгоритма Диффи-Хеллмана: вероятное будущее (изогении) - 1

Сегодня мы снова поговорим про протокол Диффи-Хеллмана, но уже построенный на более необычных конструкциях — изогениях, которые признаны устойчивыми к атакам на будущем квантовом компьютере. Квантовый компьютер, который сможет удержать в связанном состоянии порядка нескольких тысяч кубит, позволит находить закрытые ключи по открытым ключам у всех используемых сейчас асимметричных криптосистем. Число кубит для взлома RSA равно удвоенному числу бит в модуле (т.е. для разложения на множители модуля RSA длиной 2048 бит потребуется 4096 кубит). Для взлома эллиптических кривых необходимы более скромные мощности «квантового железа»: для решения задачи ECDLP для кривых над простым полем (такие кривые есть и в отечественном стандарте подписи ГОСТ Р 34.10-2012 и в американском ECDSS) c модулем кривой длиной n бит требуется 6n кубит (т. е. для модуля в 256 бит надо ~ 1536 кубит, а для 512 бит ~ 3072 кубит). На днях российско-американская группа ученых установила мировой рекорд, удержав в связанном состоянии 51 кубит. Так что у нас есть еще немного времени для изучения изогений (а также решеток, кодов, multivariate и подписей, основанных на хэшах).
Кстати, изогении считаются одним из наиболее вероятных кандидатов на победу на конкурсе NIST постквантовых алгоритмов для замены RSA и эллиптических кривых в ближайшие несколько лет. Читать полностью »