• Вычисление значения многочлена. Все ли тривиально в этом вопросе?

      Вычисление значения многочлена в точке является одной из простейших классических задач программирования.
      При проведении различного рода вычислений часто приходится определять значения многочленов при заданных значениях аргументов. Часто приближенное вычисление функций сводится к вычислению аппроксимирующих многочленов.
      Рядового читателя Хабрахабр нельзя назвать неискушенным в применении всяческих извращений. Каждый второй скажет, что многочлен надо вычислять по правилу Горнера. Но всегда есть маленькое «но», всегда ли схема Горнера является самой эффективной?

      Читать дальше →
    • Как устроены пакеты для проверки качества случайных последовательностей?

        Вопрос получения случайных и псевдослучайных последовательностей всегда вызывает оживленный интерес[1][2][3][и т.д.]. Часто [1],[2][и т.д.] упоминаются и пакеты статистических тестов, такие как NIST, DieHard, TestU01.

        В комментариях к статьям на Хабрахабр встречаются вопросы о том, как данные пакеты получают итоговые цифры. В целом тут нет ничего сложного – это просто статистика. Если читателю интересна магия получения данных цифр, то прошу под кат, там много буков и формул.
        Читать дальше →
        • +10
        • 8.7k
        • 3
      • Метод Санделиуса для получения случайных перестановок

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

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

          Метод описанный ниже предложен Санделиусом (М. Sandelius) еще в 1962 г. в работе [1].

          Читать дальше →
        • Что нам стоит полином Жегалкина построить…

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

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

          Чаще всего для построения полиномов Жегалкина студентам предлагаются два метода построения таких полиномов: метод неопределенных коэффициентов и метод эквивалентных преобразований.

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

          Под катом приведен один удобный алгоритм, для построения полиномов Жегалкина, который студенты воспринимают «на ура», т.к. требует только выполнение «механических действий» без применения каких-либо умственных усилий. Краткое описание метода можно найти в Википедии, но на мой взгляд по нему не совсем понятно, как быстро проводить вычисления. Мне метод известен под названием «метод треугольника Паскаля».
          Читать дальше →
        • Метод Монте-Карло и его точность

          • Tutorial
          Под метдом Монте-Карло понимается численный метод решения
          математических задач при помощи моделирования случайных величин. Представление об истории метода и простейшие примеры его применения можно найти в Википедии.

          В самом методе нет ничего сложного. Именно эта простота объясняет популярность данного метода.

          Метод имеет две основных особенности. Первая — простая структура вычислительного алгоритма. Вторая — ошибка вычислений, как правило, пропорциональна
          \sqrt{D\zeta/N}, где D\zeta — некоторая постоянная, а N — число испытаний. Ясно, что добиться высокой точности на таком пути невозможно. Поэтому обычно говорят, что метод Монте-Карло особенно эффективен при решении тех задач, в которых результат нужен с небольшой точностью.

          Однако одну и ту же задачу можно решать различными вариантами метода Монте-Карло, которым отвечают различные значения D\zeta. Во многих задачах удается значительно увеличить точность, выбрав способ расчета, которому соответствует значительно меньшее значение D\zeta.

          Читать дальше →
          • +16
          • 113k
          • 9
        • Sitemap.xml или «Делать было нечего...»

            Новогодние праздники 666+666+666+6+6+6-го года в самом разгаре. За серьезные вещи совсем не хочется браться. Зато можно заняться всякими мелочами, до которых обычно не доходят руки. Такой мелочью для меня стала генерация файлов Sitemap.xml.
            Sitemap.xml — это файл, содержащий в специальном формате ссылки на страницы сайта, которые должны быть проиндексированы поисковыми системами. Исчерпывающая информация о формате может быть найдена на Sitemaps.org.
            Давно хотелось иметь удобный инструмент для формирования данных файлов.

            Генерация Sitemap.xml
            Читать дальше →
          • Syncman — развертывание и синхронизация проектов на удаленном сервере

              Syncman
              Прежде, чем начать свой рассказ, задам один маленький вопрос: Как вы разворачиваете свои проекты сервере?
              Если вами управляется один маленький сайтик на бесплатном виртуальном хостинге, то проблемы синхронизации у вас не возникают — подключился по ftp, скопировал файлы и все. А если нужно контролировать развертывание нескольких сотен проектов (от маленьких сайтов визиток до нагруженных приложений), над которыми трудится не один десяток людей? Если позволяет квалификация, то можно использовать rsync, unison и др. Особо отчаянные могут просто обновлять рабочую копию проекта (svn, git и тд.) из репозитория. А что будут делать десятки художников, которым срочно нужно поправить вот ту маленькую картинку? Ведь для многих из них консоль — волшебный темный дремучий лес.
              Под катом описание одного решения, позволяющего сильно упростить процесс развертывания приложений.
              Читать дальше →
            • Резервное копирование веб-проектов на Яндекс.Диск

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

              Большие проекты могут позволить себе выделить целые сервера для резервного копирования. Однако, существует огромное количество небольших проектов, работающих лишь на вашем энтузиазме. Эти проекты также нуждаются в резервном копировании.

              Идея создания архивов на сервисах вроде Dropbox, Ubuntu One, Яндекс Диск, Диск Google и др. уже давно притягивала мое внимание. Десятки гигабайт бесплатного места, которое теоретически можно использовать для резервирования данных.

              Теперь эта идея получила мое первое воплощение. В качестве сервиса для создания архивов был выбран Яндекс Диск.
              Читать дальше →