• Оценивание пространственной ориентации, или Как не бояться фильтров Махони и Маджвика

    • Tutorial

    О чём речь


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

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

    image
    Читать дальше →
  • Что такое логическое программирование и зачем оно нам нужно


      У того, кто в детстве не писал на Прологе — нет сердца, а у того, кто пишет на нём сегодня — нет мозгов. (оригинал)

      Если вас всегда терзали мучительные сомнения — что за фигня это Логическое Программирование (ЛП) и вообще зачем оно нужно? То это статья для вас.


      Можно по-разному разделить языки программирования на группы (часто их называют парадигмами программирования), например, вот так:


      • структурное: программа разбивается на блоки — подпрограммы (изолированные друг от друга), а основными элементами управления являются последовательность команд, ветвление и цикл.
      • объектно-ориентированное: задача моделируется в виде объектов, которые отправляют друг другу сообщения. Объекты обладают свойствами и методами. Абстракция. Инкапсуляция. Полиморфизм. Ну в общем, все в курсе.
      • функциональное: базовым элементом является функция и сама задача моделируется в виде функции, а, точнее, чаще всего в виде их композиции, если f(.) и g(.) — это функции, то f(g(.)) — это их композиция.
      • логическое: вот тут, как правило, начинается феерия — если про первые три написаны сотни статей, книг, обзоров, презентаций и учебников, то здесь мы в лучшем случае видим что-то про Prolog и разработки времён Pink Floyd и Procol Harum (ну хоть с музыкой им тогда повезло) и на этом история заканчивается.

      Вот эту оплошность я и собираюсь сегодня исправить.


      Важнейший тезис этой статьи:


      Логическое программирование != Prolog.

      И вообще последний вам скорее всего не нужен. А вот первое вполне может быть.


      Структура статьи:


      • Что такое Пролог и почему он вам скорее всего не нужен
      • Зачем оно надо, или краткое введение в Answer Set Programming
      • Решаем задачи на ASP
      • Комбинаторная оптимизация
      • Вероятностное ЛП: ProbLog
      • ЛП на классической логике FO(.) и IDP
      • Sketched Answer Set Programming
      • Экспериментальный анализ
      • Тестирование и корректность программ
      • Заключение
      Читать дальше →
    • Новогоднее соревнование CS центра 2018

        Введение


        Уже в октябре 2018 мы с радостью вспомнили адвент-календарь с задачами 2017 года (условия здесь) и начали думать, что можно сделать в этом году. Из нескольких достойных идей выбрали вариант, в котором подберём разноплановые «цепляющие» задачи, объединенные красивой новогодней историей.

        Оставалось всего ничего: собственно, подобрать задачи, сочинить историю, сделать сайт с лидербордом, красивый и крепко провязанный с Яндекс.Контестом, и запуститься в начале декабря :-)

        Результат


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

        В результате получилось:


        Интересные факты и истории


        780 участников зарегистрировались, 333 человека приступили к решению, 203 человека сдали успешно хотя бы две задачи.

        Изначально мы оценили чистое время на решение всех задач в семь дней для неподготовленного участника и в два дня для очень опытного (aka свежий выпускник CS центра). Первый правильно решивший все одиннадцать задач помощник Деда Мороза уложился примерно в сутки, ещё двое справились на вторые!

        Письмо одного из участников: «Добрый день! Из-за вашего контеста я остановил работу офиса (40 человек) конкретно второй задачей про кофе деда мороза, дайте еще подсказку пожалуйста. Мы все очень мучаемся.»

        Разбор задач


        Читать дальше →
      • Искусственные нейронные сети выращивают навигационные клетки как в мозге

        • Перевод


        Наличие способности находить короткий путь, самый прямой из точки «А» в точку «Б» не выглядит сегодня впечатляющим тестом разумности. Тем не менее, согласно новому отчету, который был опубликован в журнале Nature некоторое время назад, в котором исследователи рассказали о своей навигационной системе искусственного интеллекта, способность исследовать сложные симулированные пространства и находить кратчайший маршрут к цели, ставит системы такого рода на один уровень с человеком и другими животными.
        Читать дальше →
        • +17
        • 5,7k
        • 1
      • Использование графов для решения разреженных систем линейных уравнений

          Прелюдия


          Численное решение линейных систем уравнений является незаменимым шагом во многих сферах прикладной математики, инженерии и IT-индустрии, будь то работа с графикой, расчёт аэродинамики какого-нибудь самолёта или оптимизация логистики. Модная нынче «машинка» без этого тоже не особо бы продвинулась. Причём решение линейных систем, как правило, сжирает наибольший процент из всех вычислительных затрат. Понятно, что эта критическая составляющая требует максимальной оптимизации по скорости.

          Часто работают с т.н. разреженными матрицами — теми, у которых нулей на порядки больше остальных значений. Такое, например, неизбежно, если имеешь дело с уравнениями в частных производных или с какими-нибудь другими процессами, в которых возникающие элементы в определяющих линейных соотношениях связаны лишь с «соседями». Вот возможный пример разреженной матрицы для известного в классической физике одномерного уравнения Пуассона $-\phi^{''} = f$ на равномерной сетке (да, пока в ней нулей не так много, но при измельчении сетки их будет будь здоров!):

          $\begin{pmatrix}2 & -1 & 0 & 0 & 0\\ -1 & 2 & -1 & 0 & 0\\ 0 & -1 & 2 & -1 & 0 \\ 0 & 0 & -1 & 2 & -1 \\ 0 & 0 & 0 & -1 & 2\end{pmatrix}$


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

          Вступление


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

          В результате напишем простенький архиватор. Об этом уже была статья на Хабре, но без практической реализации. Теоретический материал текущего поста взят из школьных уроков информатики и книги Роберта Лафоре «Data Structures and Algorithms in Java». Итак, все под кат!
          Читать дальше →
        • Подготовка к собеседованию в компании большой пятерки

            По моим впечатлениям очень многих людей интересует тема подготовки к собеседованиям в топ технические компании, поэтому решил вместо личных ответов написать одну статью на которую в дальнейшем буду ссылаться. Всем кому интересен процесс самого собеседования, вещи на которые нужно обращать внимание, как готовиться и к чему готовиться — добро пожаловать под кат.
            Читать дальше →
          • Реверс-инжиниринг. История. Моя


              Всем привет,


              На этот раз статья будет не технической (хотя в ней и будут попадаться какие-то технические термины/моменты), а скорее автобиографической, если так можно выразиться. Эта статья о том, как я докатился до такой жизни пришёл в реверс-инжиниринг, что читал, чем интересовался, где применял, и т.д. И, я почему-то уверен, что моя история будет иметь множество отличий от твоей. Поехали…

              Читать дальше →
            • Фильтр Калмана для минимизации энтропийного значения случайной погрешности с не Гауссовым распределением

              • Tutorial

              Введение


              На Habr математическое описание работы фильтра Калмана и особенности его применения рассматривались в следующих публикациях [1÷10]. В публикации [2] в простой и доходчивой форме рассмотрен алгоритм работы фильтра Калмана (ФК) в модели «пространства состояний», Следует отметить, что исследование систем контроля и управления во временной области с помощью переменных состояния широко используется в последнее время благодаря простоте проведения анализа [11].

              Публикация [8] представляет значительный интерес именно для обучения. Очень эффективен методический приём автора, который начал свою статью с рассмотрения распределения случайной погрешности Гаусса, рассмотрел алгоритм ФК и закончил простой итерационной формулой для подбора коэффициента усиления ФК. Автор ограничился рассмотрением распределения Гаусса мотивируя это тем, что при достаточно больших $n$ (многократных измерений) закон распределения суммы случайных величин стремится к распределению Гаусса.

              Теоретически такое утверждение, безусловно, справедливо, однако на практике число измерений в каждой точке диапазона не может быть очень большим. Сам R. E. Kalman получил результаты о минимуме ковариации фильтра на базе ортогональных проекций, без предположения о гауссовости ошибок измерений [12].

              Целью настоящей публикации является исследование возможностей фильтра Калмана для минимизации энтропийного значения случайной погрешности с не Гауссовым распределением.
              Для оценки эффективности фильтра Калмана при идентификации закона распределения или суперпозицией законов по экспериментальным данным воспользуемся информационная теорией измерений основанной на теории информации К. Шеннона, согласно которой информация, подобно физической величине, может быть измерена и оценена.
              Читать дальше →
            • Сжимаем список IP-адресов наилучшим образом

              • Tutorial


              Как-то я прочитал на Хабре статью про настройку BGP на роутере. Инструкции оттуда можно использовать для настройки домашнего роутера так, чтобы трафик на определённые IP-адреса шёл через другой канал. Однако здесь есть проблема: список IP-адресов может быть очень большим.

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

            Самое читаемое