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

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

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

Map matching и обработка сырых данных GPS в промышленных масштабах - 1

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

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

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

Время математических приключений!

Чей прогноз погоды точнее? - 1

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

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

Меня зовут Александр Подлевских, я ведущий разработчик в компании Туту.ру, тимлид в команде «Электричек», и в этой статье я расскажу, как мы прогнозируем отклонения электричек от графика — опоздания и опережения. А ещё о том, что такое ГВЦ РЖД, как технически устроена система пригородного ж/д-транспорта, и как мы рассказываем об опозданиях пассажирам.

Как научиться предсказывать опоздания электричек - 1
Читать полностью »

Видео следующего поколения: представляем AV1 - 1AV1 — это новый универсальный видеокодек, разработанный Альянсом за открытые медиа (Alliance for Open Media). Альянс взял за основу кодек VPX от Google, Thor от Cisco и Daala от Mozilla/Xiph.Org. Кодек AV1 превосходит по производительности VP9 и HEVC, что делает его кодеком не завтрашнего, а послезавтрашнего дня. Формат AV1 свободен от любых роялти и всегда останется таковым с разрешительной лицензией свободного и открытого ПО.

Тройственная платформа


Кто следил за развитием Daala, тот знает, что после формирования Альянса за открытые медиа (AOM) Xiph и Mozilla предложили наш кодек Daala как один из базисов для нового стандарта. Кроме него, компания Google представила свой кодек VP9, а Cisco представила Thor. Идея заключалась в том, чтобы создать новый кодек в том числе на основе этих трёх решений. С того момента я не публиковал никаких демо о новых технологиях в Daala или AV1; в течение долгого времени мы мало что знали об окончательном кодеке.

Около двух лет назад AOM проголосовал за то, чтобы основать фундаментальную структуру нового кодека на базе VP9, а не Daala или Thor. Компании-члены альянса хотели в кратчайший срок получить полезный кодек без роялти и лицензирования, поэтому выбрали VP9 как наименее рискованный вариант. Я согласен с таким выбором. Хотя Daala выдвинули кандидатом, но я всё-таки думаю, что и устранение блочных артефактов трансформацией внахлёст (lapping arrpoach), и техники частотной области в Daala тогда (да и сейчас) ещё недостаточно созрели для реального развёртывания. В Daala по-прежнему оставались нерешённые технические вопросы, а выбор в качестве отправной точки VP9 решал большинство этих проблем.
Читать полностью »

Измерение уровня жидкости в топливном баке ракеты - 1

Введение

Топливо из резервуара окислителя и резервуара горючего поступает в камеру сгорания ракетного двигателя. Синхронная подача топлива в заданной пропорции обеспечивает эффективную работу ракетного двигателя.

Эффективная работа зависит от точного измерения уровня топлива в баке. Для этой цели топливный бак имеет систему управления топливом. Система представляет собой вертикальный измерительный канал с датчиками внутри канала для фиксации свободного уровня жидкости в канале [1]:

Измерение уровня жидкости в топливном баке ракеты - 2

Рисунок. Схема топливного бака. 1- резервуар, 2- топливо, 3- измерительный канал, Po — давление газа, Измерение уровня жидкости в топливном баке ракеты - 3 — уровень жидкости в канале, H — уровень жидкости в баке, r,x — координатные оси.

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

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

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

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

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

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

Врываемся в 2018 год с очередным большим релизом: выпуск версии 11.3 языка Wolfram Language и Mathematica - 1

Перевод блог-поста Стивена Вольфрама (Stephen Wolfram) "Roaring into 2018 with Another Big Release: Launching Version 11.3 of the Wolfram Language & Mathematica".


Содержание

Поток выпуска версий
Что нового?
Блокчейн
Системное моделирование
Новое в ноутбуках
Документация рабочего процесса
Инструменты для презентаций
Wolfram Чат
Удобства языка
Обновления визуализации
Чтение текста
Вычисления по лицам
Нейронные сети
Асимптотический анализ
«Элементарная» алгебра
Доказательства
Растущая база знаний
Сообщения и почта
Операции на системном уровне
Что не упоминалось
Читать полностью »

В этой статье я расскажу о реализации одного из алгоритмов расчёта глобального (переотражённого / ambient) освещения, применяемого в некоторых играх и других продуктах, — Voxel Cone Tracing (VCT). Возможно, кто-то читал старенькую статью ([VCT]) 2011 года или смотрел видео. Но статья не даёт исчерпывающих ответов на вопросы, как реализовать тот или иной этап алгоритма.

Глобальное освещение с использованием трассировки вокселей конусами - 1Глобальное освещение с использованием трассировки вокселей конусами - 2
Рендер сцены без глобального освещения, и с использованием VCT:
Читать полностью »

Ассоциативные правила, или пиво с подгузниками - 1

Введение в теорию

Обучение на ассоциативных правилах (далее Associations rules learning — ARL) представляет из себя, с одной стороны, простой, с другой — довольно часто применимый в реальной жизни метод поиска взаимосвязей (ассоциаций) в датасетах, или, если точнее, айтемсетах (itemsests). Впервые подробно об этом заговорил Piatesky-Shapiro G [1] в работе “Discovery, Analysis, and Presentation of Strong Rules.” (1991) Более подробно тему развивали Agrawal R, Imielinski T, Swami A в работах “Mining Association Rules between Sets of Items in Large Databases” (1993) [2] и “Fast Algorithms for Mining Association Rules.” (1994) [3].
Читать полностью »

В JS API Яндекс.Карт существует возможность создавать различные объекты на карте. Один из их них – многоугольник, с помощью которого можно улучшить интерактивность пользовательской карты: выделить отдельные области или отобразить местоположение неточечного объекта. К примеру, так можно показать план строительства нового квартала или зоны доставки пиццы.

У пользователей API Яндекс.Карт давно появился вопрос о добавлении подписей поверх многоугольников. Люди предлагали хитрые решения, чтобы добавить подпись на объект в нужном месте, скрыть ее, перекрасить и т.п., но такие решения получались сложными и негибкими.

К примеру, к нам пришел отдел исследований Яндекса с просьбой написать удобный инструмент для подписи многоугольников после того, как они сделали несколько исследований на карте мира.

Сколько математики нужно, чтобы подписать многоугольник в JS API Яндекс.Карт - 1
Отображения региональных слов из словаря Даля, т.е слова которые ищут значительно чаще, чем в среднем по России

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

image

Привет Хабр, сегодня я расскажу о том, как я проходил тестовое задание на летнюю стажировку в Яндекс. Эта публикация будет полезна начинающим разработчикам, любителям олимпиадного программирования, тем кто неравнодушен к С++ и Java, или просто хочет прочесть интересную статью после трудного рабочего дня.

Чего ожидать от этой статьи?

  • Introduction, о том что такое стажировки в Яндкесе, как и когда на них подать
  • Мотивация к написанию данной статьи
  • Примеры задач, моё решение и краткий разбор (Можно смело пропустить первые два пункта, и начинать именно отсюда)

Introduction

Для тех кто мало знаком с системой отбора на стажировку в Яндексе расскажу вкратце. На сайте яндекса, за несколько месяцев до лета объявляется оплачиваемая вакансия для начинающих разработчиков, в том отделе, в котором вы бы хотели работать (i.e. Яндекс.Диск, Яндекс.Алиса). По ссылке, нужно заполнить форму, о том где Вы учитесь, чем занимаетесь, какой был опыт работы, о чем писали дипломную работы итп. После заполнения формы Вам на почту присылают тестовое задание, на выполнение которого у Вас есть 6 часов, в любой день в течении недели с момента, когда Вы получили это письмо.
Читать полностью »