• Численные методы решения систем нелинейных уравнений

      Введение


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

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

      Для численного решения применяются итерационные методы последовательных приближений (простой итерации) и метод Ньютона в различных модификациях. Итерационные процессы естественным образом обобщаются на случай системы нелинейных уравнений вида:

      (1)

      Обозначим через вектор неизвестных и определим вектор-функцию Тогда система (1) записывается в виде уравнения:

      (2)

      Теперь вернёмся к всеми любимому Python и отметим его первенство среди языков программирования, которые хотят изучать [1].



      Этот факт является дополнительным стимулом рассмотрения числительных методов именно на Python. Однако, среди любителей Python бытует мнение, что специальные библиотечные функции, такие как scipy.optimize.root, spsolve_trianular, newton_krylov, являются самым лучшим выбором для решения задач численными методами.

      С этим трудно не согласится хотя бы потому, что в том числе и разнообразие модулей подняло Python на вершину популярности. Однако, существуют случаи, когда даже при поверхностном рассмотрении использование прямых известных методов без применения специальных функций библиотеки SciPy тоже дают неплохие результаты. Иными словами, новое- это хорошо забытое старое.
      Читать дальше →
    • Решение цветных японских кроссвордов со скоростью света

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


        Размер кроссвордов может доходить до 150x150. Игрок с помощью специальных логических приемов вычисляет цвет каждой клетки. Решение может занять как пару минут на кроссвордах для начинающих, так и десятки часов на сложных головоломках.


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


        Читать дальше →
      • О формировании последовательностей в гипотезе Коллатца ( 3n+1 )

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

          Формулируется задача довольно просто:
          Берём любое натуральное число n. Если оно чётное, то делим его на 2, а если нечётное, то умножаем на 3 и прибавляем 1 (получаем 3n + 1). Над полученным числом выполняем те же самые действия, и так далее.

          Гипотеза Коллатца заключается в том, что какое бы начальное число n мы ни взяли, рано или поздно мы получим единицу.

          Алгоритмически это выглядит так:

          while (number > 1) {
          	if (number % 2 === 0) number = number / 2;
          	else number = 3 * number +1;
          }
          
          Читать дальше →
        • Численные методы решения уравнений эллиптического типа

            Введение


            Наиболее распространённым уравнением эллиптического типа является уравнение Пуассона.
            К решению этого уравнения сводятся многие задачи математической физики, например задачи о стационарном распределении температуры в твердом теле, задачи диффузии, задачи о распределении электростатического поля в непроводящей среде при наличии электрических зарядов и многие другие.

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

            Цель публикации получить решение уравнения Пуассона для граничных условий Дирихле и Неймана, исследовать сходимость релаксационного метода решения на примерах.
            Читать дальше →
            • +13
            • 3,3k
            • 5
          • Управляемые токенами реестры 1.0

            • Перевод


            Идея управляемых токенами реестров (TCR) зародилась в блокчейн-сообществе не менее года назад. По крайней мере, эта статья была опубликована автором еще в сентябре 2017 года. А недавно я был на конференции DappCon 2018 в Берлине и увидел большой интерес к этой теме, а также несколько ранних набросков на основе TCR. Поэтому предполагаю, что пик интереса еще впереди.


            Мне TCR-контракты представляются крайне интересными, поскольку они являют собой пример наиболее простой замкнутой системы, управляемой децентрализованно и на основе экономических стимулов. Если немного пофантазировать, становится понятно, что на основе этой идеи можно децентрализовать очень многое, возможно даже всё в нашей социально-экономической жизни. И это уже не просто галлюцинации сумасшедших криптанов, а вполне неплохо сформулированный протокол. Более подробно читайте под катом.

            Читать дальше →
          • CRDT: Conflict-free Replicated Data Types


              Как считать хиты страницы google.com? А как хранить счётчик лайков очень популярных пользователей? В этой статье предлагается рассмотреть решение этих задач с помощью CRDT (Conflict-free Replicated Data Types, что по-русски переводится примерно как Бесконфликтные реплицированные типы данных), а в более общем случае — задачи синхронизации реплик в распределённой системе с несколькими ведущими узлами.
              Читать дальше →
            • Учим Искусственный Интеллект играть в игру

              Доброго времени суток, дорогой читатель!

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



              Примечание: данная статья не объясняет термин "нейронная сеть" и всё, что с ним связано, а также не предоставляет базовую информацию об обучении сети методом трассировки. Рекомендуем кратко ознакомиться с этими понятиями до прочтения статьи
              Читать дальше →
              • +17
              • 7,3k
              • 6
            • Динамическое программирование в олимпиадных задачах

                Привет!

                Недавно решал задачи с архива Timus Online Judge и наткнулся на раздел под названием задачи динамического программирования. Задачи такого типа вызывают у меня особый интерес, потому что зачастую такой подход обеспечивает быстроту и элегантность решения. Что же такое — динамическое программирование?

                Динамическое программирование — это подход к решению задач, при котором происходит разбиение на подзадачи, которые «проще» в сравнении с исходной. Слово «динамический» близко по значению к «индуктивный»: предполагается, что известен ответ для какого-то значения $k$, и хочется найти ответ для $k+1$. В математике это называется индуктивным переходом, и составляет основную идею динамического программирования.

                Простые примеры


                Наиболее яркой и показательной задачей является задача вычисления $n$-ого числа последовательности Фибоначчи.
                Читать дальше →
                • +11
                • 6,3k
                • 3
              • Прореживание таймфреймов (криптовалюты, форекс, биржи)

                Некоторое время назад передо мной была поставлена задача написать процедуру, которая выполняет прореживание котировок рынка Форекс (точнее, данных таймфреймов).

                Формулировка задачи: данные поступают на вход с интервалом в 1 секунду в таком формате:

                • Название инструмента (код пары USDEUR и пр.),
                • Дата и время в формате unix time,
                • Open value (цена первой сделки в интервале),
                • High value (максимальная цена),
                • Low value (минимальная цена),
                • Close value (цена последней сделки),
                • Volume (громкость, или объём сделки).

                Необходимо обеспечить пересчёт и синхронизацию данных в таблицах: 5 сек, 15 сек, 1 мин, 5 мин, 15 мин, и т.д.

                Описанный формат хранения данных имеет название OHLC, или OHLCV (Open, High, Low, Close, Volume). Он применяется часто, по нему сразу можно построить график «Японские свечи».

                image

                Под катом я описал все варианты, какие смог придумать, как можно прореживать (укрупнять) полученные данные, для анализа, например, зимнего скачка цены биткоина, а по полученным данным вы сразу построите график «Японские свечи» (в MS Excel такой график тоже есть). На картинке выше этот график построен для таймфрейма «1 месяц», для инструмента «bitstampUSD». Белое тело свечи означает рост цены в интервале, чёрное — снижение цены, верхний и нижние фитили означают максимальную и минимальную цены, которые достигались в интервале. Фон — объём сделок. Хорошо видно, что в декабре 2017 цена вплотную приблизилась к отметке 20К.

                Решение будет приведено для двух движков БД, для Oracle и MS SQL, что, в некотором роде, даст возможность сравнить их на этой конкретной задаче (обобщать сравнение на другие задачи мы не будем).
                Читать дальше →
              • Процедурная генерация уровней


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


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


                  Внимание! Под катом много текста и "жирных" гифок.

                  Читать дальше →

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