• Интерполяционный многочлен на произвольных функциях

      Введение


      Приветствую, уважаемые читатели! Сегодня предлагаю поразмышлять о следующей задачке:

      Дано $n$ пар точек на плоскости $(x_1;y_1),...,(x_n;y_n)$. Все $x_i$ различны. Необходимо найти многочлен $M(x)$ такой, что $M(x_i)=y_i$, где $i\in\{1,...,n\}$

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

      «Почему окольными путями?» — спросите вы. Ответ традиционный: это статья является продолжением серии статей дилетантского характера про математику, целью которых является популяризация математического мира.
      Читать дальше →
    • Решаем задачу нахождения длины наибольшей возрастающей подпоследовательности

      • Tutorial

      Содержание:

      Последовательность Фибоначчи O (n)
      Решение за O(n ^ 2)
      Бинарный поиск O(log n)
      Решение за O(n * log n)


      Задача


      "Найти длину самой большой возрастающей подпоследовательности в массиве."


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


      На пальцах


      Есть последовательность:


      5, 10, 6, 12, 3, 24, 7, 8


      Вот примеры подпоследовательностей:


      10, 3, 8
      5, 6, 3


      А вот примеры возрастающих подпоследовательностей:


      5, 6, 7, 8
      3, 7, 8


      А вот примеры возрастающих подпоследовательностей наибольшей длины:


      5, 6, 12, 24
      5, 6, 7, 8

      Читать дальше →
    • Машинное обучение: анализ временных рядов Azure Machine Learning для поиска аномалий

      • Перевод
      Обнаружение аномалий — одна из важнейших функций для решений в области «интернета вещей» (IoT), которые собирают и анализируют временные изменения в потоке данных от различных датчиков. Во многих случаях поток данных со временем не претерпевает значительных изменений. Однако если они появляются, это чаще всего означает, что в системе возникла аномалия, способная нарушить её работу. В этой статье я расскажу, как использовать модуль Time Series Anomaly Detection сервиса машинного обучения Azure Machine Learning для определения аномальных показателей датчиков.

      Читать дальше →
      • +11
      • 3,3k
      • 1
    • Автоматный практикум — 1. Пример «Дисплей», разработка ОА и УА

        Тесты в предыдущей статье убедительно показали высокую эффективность «автоматной» реализации примера «Дисплей» по сравнению с условно названной «неавтоматной» версией. Вкратце итог: обе реализации автоматные, но разница в эффективности многократна и глубинная причина видится в том, что вариант А1 («автоматный») изначально проектировался как автомат, а вариант А2 («неавтоматный») нет. Не столько автоматная реализация, сколько автоматное проектирование является основой высокой эффективности. Для простых алгоритмов автоматные реализации получаются сами собой. Есть смысл говорить о том, что автоматное программирование, это не столько реализация программы в виде конечного автомата, сколько автоматное проектирование, фундаментом которого является конструктивная декомпозиция. Я несколько раз касался темы автоматного проектирования и конструктивной декомпозиции, но чтобы раскрыть эту тему нужны практические примеры. В этой и следующих нескольких статьях я проведу практикум, покажу процесс автоматного проектирования, пытаясь по возможности приводить ход рассуждений присущих автоматному проектированию.
        Читать дальше →
      • Трёхмерная графика с нуля. Часть 2: растеризация

        • Перевод
        image


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

        К сожалению, эта простота имеет свою цену: низкую производительность. Несмотря на то, что существует множество способов оптимизации и параллелизации трассировщиков лучей, они всё равно остаются слишком затратными с точки зрения вычислений для выполнения в реальном времени; и хотя оборудование продолжает развиваться и становится быстрее с каждым годом, в некоторых областях применения необходимы красивые, но в сотни раз быстрее создаваемые изображения уже сегодня. Из всех этих областей применения самыми требовательными являются игры: мы ожидаем рендеринга отличной картинки с частотой не менее 60 кадров в секунду. Трассировщики лучей просто с этим не справятся.

        Тогда как это удаётся играм?

        Ответ заключается в использовании совершенно иного семейства алгоритмов, которое мы исследуем во второй части статьи. В отличие от трассировки лучей, которая получалась из простых геометрических моделей формирования изображений в человеческом глазе или в камере, сейчас мы будем начинать с другого конца — зададимся вопросом, что мы можем отрисовать на экране, и как отрисовать это как можно быстрее. В результате мы получим совершенно другие алгоритмы, которые создают примерно похожие результаты.
        Читать дальше →
        • +36
        • 11,4k
        • 2
      • Космическая съёмка Земли


          Cпутниковый снимок в ложных цветах (зелёный, красный, ближний инфракрасный) с пространственным разрешением 3 метра и наложенной маской зданий из OpenStreetMap (спутниковая группировка PlanetScope)

          Привет, Хабр! Мы постоянно расширяем источники данных, которые используем для аналитики, поэтому решили добавить ещё и спутниковые снимки. У нас аналитика по спутниковым снимкам полезна в продуктах для предпринимательства и инвестиций. В первом случае статистика по геоданным поможет понять, в каком месте стоит открывать торговые точки, во втором позволяет анализировать деятельность компаний. Например, для строительных компаний можно посчитать, сколько за месяц было построено этажей, для сельскохозяйственных компаний — сколько гектаров урожая взошло и т.д.

          В этой статье я постараюсь дать примерное представление о космической съёмке Земли, расскажу о трудностях, с которыми можно столкнуться, начиная работу со спутниковыми снимками: предварительная обработка, алгоритмы для анализа и библиотеки Python для работы со спутниковыми снимками и геоданными. Так что все, кому интересна область компьютерного зрения, добро пожаловать под кат!
          Читать дальше →
        • AdBlock похитил этот баннер, но баннеры не зубы — отрастут

          Подробнее
          Реклама
        • Коллективный портрет участников конкурса MERC-2017

            Подходит к концу наш первый конкурс по машинному обучению и анализу данных — Multimodal Emotion Challenge Recognition (MERC-2017) на площадке Datacombats. В этом посте мы хотели бы представить небольшой анализ аудитории, своеобразный коллективный «портрет».


            Читать дальше →
          • Задачи планирования и программирование в ограничениях

            • Tutorial
            Когда у тебя в запасе много популярных инструментов вроде JAVA, Python, Ruby, PHP, C#, C++ и других, чувствуешь себя почти всемогущим. Стандартный подход в разработке рулит. Но только до тех пор, пока не столкнешься с определенным типом задач.
            
 
            Подумайте, как правильно написать программу, которая оптимально…

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

            image
            Читать дальше →
            • +19
            • 8,2k
            • 5
          • fiber — легковесные процессы для Arduino


              А давайте притащим мир большого программирования в Arduino!


              Любая программа, а тем более программа близкая к аппаратуре (а какие еще на arduino бывают?) при рассмотрении представляет собой множество параллельно работающих ветвей.


              При этом в реальной жизни обработка большинства вещей в реальном времени не требуется. Достаточно иметь нечто похожее на реальное время.


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


              А вот если мы программируем скажем регулятор ШИМ (не рассматриваем аппаратные способы), то тут нам возможно потребуется считать каждый такт процессора, чтобы обеспечить приемлемую точность регулирования.


              Если рассмотреть структуру произвольного сложного программно-аппаратного проекта в том числе на Arduino, то увидим, что задач требующих "реального" (с жесткими требованиями) реалтайма — меньшинство, а большинству задач достаточно условного реалтайма.


              Программирование реального реалтайма — это как правило прерывания и аппаратные хитрости. В этой статье поговорим о программировании реалтайма условного.

              Читать дальше →
            • Голосуем за школьное обучение информатике


                (Источник)

                Как известно, истина в математике и естествознании не определяется голосованием. Это относится и к информатике (computer science – CS). Несмотря на это, по одной из самых острых проблем CS: $P =? NP$ уже проводилось несколько голосований, в которых участвовали ведущие мировые эксперты:
                На начало 2000-х гг. большинство математиков считают, что эти классы не равны. Согласно опросу, проведённому в 2002 году среди 100 учёных, 61 человек считает, что ответ — «не равны», 9 — «равны», 22 затруднились ответить и 8 считают, что гипотеза не выводима из текущей системы аксиом и, таким образом, не может быть доказана или опровергнута.
                (Википедия )
                Воспользуемся этим примером и предложим опрос по наиболее острым вопросам школьной информатики, которые выявило недавнее обсуждение.
                Читать дальше →
              Самое читаемое