• Криптография русского крестьянина

    • Перевод

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

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

    Умножение методом русских крестьян


    Если вы не знали о нём раньше, то это довольно любопытный подход к умножению, который не требует запоминания таблиц умножения — для него достаточно способности удваивать и делить пополам целые числа. Не очень понятно, как он относится к русским крестьянам: похоже, так же, как «датская сдоба» к Дании. Этот метод был известен ещё древним египтянам, которые явно жили намного раньше русских крестьян.

    Общее описание метода просто, но не слишком информативно. Тем не менее, давайте начнём с него.
    Читать дальше →
  • Рубрика «Читаем статьи за вас». Октябрь — Ноябрь 2017


      Привет, Хабр! По традиции, представляем вашему вниманию дюжину рецензий на научные статьи от членов сообщества Open Data Science из канала #article_essense. Хотите получать их раньше всех — вступайте в сообщество ODS!


      Статьи выбираются либо из личного интереса, либо из-за близости к проходящим сейчас соревнованиям. Напоминаем, что описания статей даются без изменений и именно в том виде, в котором авторы запостили их в канал #article_essence. Если вы хотите предложить свою статью или у вас есть какие-то пожелания — просто напишите в комментариях и мы постараемся всё учесть в дальнейшем.


      Статьи на сегодня:

      Читать дальше →
      • +61
      • 7,9k
      • 4
    • Решение задачи оптимизации многоступенчатых ракет


        Введение

        Методы нелинейной оптимизации широко применяются при проектировании машин и механизмов. Указанные методы применяются и в ракетостроении, например, для оптимизации многоступенчатых ракет [1].

        Многоступенчатая ракета — это аппарат, в котором части конструкции отделяются во время полета, придавая оставшейся части ракеты дополнительную скорость. Трёхступенчатая ракета схематически показана на рисунке.



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

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

        Характеристики многоступенчатой ракеты можно описать двумя уравнениями. Первое уравнение для коэффициента полезной нагрузки ракеты:



        где: W1– полезный вес ракеты ;WN –начальный вес ракеты до отделения ступеней.
        Читать дальше →
        • +31
        • 8,1k
        • 8
      • Короткое плечо совпадения

        • Перевод
        Джеймс Тэнтон разбрасывается задачками по теории чисел с той же щедростью, с которой Джон Д. Рокфеллер раздавал десятицентовики. Я уже писал об одной из задач Тэнтона. Спустя несколько недель моё внимание привлёк этот твит о факториалах и квадратах и уже не давал мне покоя:

        Tweet reads: 4!+1 = 25, a square number. 5!+1 = 121, a square number. Another example? Two more examples?

        «4!+1 = 25, квадрат числа. 5!+1 = 121, тоже квадрат числа. Можете привести ещё один пример? Ещё два примера?»

        С помощью ручки и бумаги легко показать, что $6!$ не подходит. Факториал $6!$ — это $1 \times 2 \times 3 \times 4 \times 5 \times 6 = 720$; прибавив $1$, получим число $721$, которое не является квадратом. (Оно раскладывается на множители как $7 \times 103$.) С другой стороны, $7!$ равно $5040$, а прибавив $1$, мы получим $5041$, что равно $71^2$. Это даёт нам очень милое уравнение:
        Читать дальше →
      • Винеровский хаос или Еще один способ подбросить монетку

        • Tutorial

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

        • Первый «вау-эффект» я испытал от Центральной предельной теоремы. Берем кучу случайных величин, устремляем их количество в бесконечность и получаем нормальное распределение. И совсем неважно как распределены эти величины, неважно, будь это подбрасывания монетки или капли дождя на стекле, вспышки на Солнце или остатки кофейной гущи, результат будет всегда один — их сумма всегда стремится к нормальности. Разве что, нужно потребовать их независимость и существование дисперсии (позднее я узнал, что существует теорема и для экстремальных тяжелохвостых распределений с бесконечной дисперсией). Тогда этот парадокс долго не давал мне заснуть.
        • В какой-то момент учебы в университете такие предметы как дискретная математика и функциональный анализ слились вместе и всплыли в теорвере под видом выражения «почти наверное». Стандартный пример: вы случайно выбираете число от 0 до 1. С какой вероятностью вы ткнёте в рациональное число (привет, функция Дирихле)? Спойлер: 0. Ноль, Карл! Бесконечное множество не имеет никакой силы, если оно счетно. У вас бесконечное число вариантов, но вы не выберете ни один из них. Вы не выберете 0, или 1, или 1/2, или 1/4. Вы и не выберете 3/2.

          Да-да, что выбрать 1/2, что выбрать 3/2, вероятность нулевая. Вот только в 3/2 вы не ткнёте точно, таковы условия, а в 1/2 вы не попадёте ну… «почти наверное». Концепция «почти всюду»/«почти наверное» забавляет математика, а обывателя заставляет крутить пальцем у виска. Многие ломают себе мозг в попытке классифицировать нули, но результат того стоит.
        • Третий по счёту, но не по силе, «вау-эффект» настиг уже на переходе в advanced level
        Читать дальше →
      • Сверточная сеть на python. Часть 1. Определение основных параметров модели


          Несмотря на то, что можно найти не одну статью, объясняющую принцип метода обратного распространения ошибки в сверточных сетях (раз, два, три, четыре, пять и даже дающих “интуитивное” понимание — шесть), мне, тем не менее, никак не удавалось полностью понять эту тему. Кажется, что авторы недостаточно внимания уделяют обычным примерам либо же опускают какие-то хорошо понятные им, но не очевидные другим особенности, и весь материал по этой причине становится неподъемным. Мне хотелось разложить все по полочкам для самого себя и в итоге конспекты вылились в статью. Я постарался исключить все недостатки существующих объяснений и надеюсь, что эта статья ни у кого не вызовет вопросов или недопониманий. И, может, следующий новичок, который, также как и я, захочет во всем разобраться, потратит уже меньше времени.
          Читать дальше →
          • +14
          • 8,1k
          • 9
        • AdBlock похитил этот баннер, но баннеры не зубы — отрастут

          Подробнее
          Реклама
        • Вечерний мехмат МГУ

            В статье хочу поделиться опытом поступления и обучения на отделелении второго высшего образования на мехмате МГУ. Он же — инженерный поток или вечернее отделение. В свое время очень была нужна информация, но подробных отзывов в инете было очень мало.
            Читать дальше →
            • +20
            • 7,4k
            • 8
          • Вероятностная интерпретация классических моделей машинного обучения

            • Перевод

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


            Читать дальше →
          • Разбираемся, что же там нового открыли в задаче о ферзях

              Пару месяцев назад появилась занятная статья с анализом классической задачи о расстановке ферзей на шахматной доске (см. детали и историю ниже). Задача невероятно известная и вся уже рассмотрена под микроскопом, поэтому было удивительно, что появилось что-то действительно новое.


              image
              Сможете поставить ещё шесть? А найти все решения?
              (картинка из статьи)


              Далее, к сожалению, произошла какая-то совершенно невразумительная история из цепочки вот таких вот превращений:



              Стоит отметить, что пять наугад открытых ссылок на русском ещё меньше проясняли картину происходящего.


              Я тут подумал — надо бы кому-то эту странную цепочку прервать и нормальным языком изложить суть событий.


              О чём пойдёт речь:


              Читать дальше →
            • Метод Уэлфорда и многомерная линейная регрессия

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


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


                Читать дальше →
                • +12
                • 4,9k
                • 7
              Самое читаемое