Рубрика «математика»

Параллельная сортировка данных в GPU - 1

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

GIF

Параллельная сортировка данных в GPU - 2

Введение

Если вы изучали теорию вычислительных машин в 80-х или 90-х, есть вероятность, что вы упорно пытались понять, что же некоторые разработчики находят восхитительного в алгоритмах сортировки. То, что поначалу кажется незначительной задачей, оказывается краеугольным камнем Computer Science.

Но что же такое «алгоритм сортировки»? Представьте, что у вас есть список чисел. Алгоритм сортировки — это программа, получающая этот список и изменяющая порядок чисел в нём. Понятие алгоритмов сортировки часто вводится при изучении вычислительной сложности — ещё одной обширной области знания, которую я подробно рассмотрю в будущих статьях. Существует бесконечное количество способов сортировки списка элементов, и каждая стратегия обеспечивает свой собственный уникальный компромисс между затратами и скоростью.
Читать полностью »

Цель: взломать шифр Хилла

Доброго времени суток, уважаемые читатели! Сегодня я хотел поделиться способом, который помог мне вскрыть текст, зашифрованный методом Хилла. Что такое метод Хилла описывать не буду: до меня уже постарались опытные умельцы донести особенности данного способа. Ссылка на пост.

Что имеем?

Скажу сразу, что на руках не имелось ни открытого текста, ни ключа. Было известно, что текст длинной 6286 символов был зашифрован матрицей 7 х 7. Поэтому для нашего же удобства, мы разобьем текст на 898 строчек по 7 символов. В тексте не содержатся буквы 'ё' и 'ъ'. В целях благоразумства, я не буду приводить весь зашифрованный текст, а лишь его часть:

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

На вид бессмысленная ерунда, пока что…

Как будем ломать?

Рассмотрим атаку «грубой силой». Выше было оговорено, что из алфавита исключены две буквы, поэтому все линейные комбинации при шифровании (как и при дешифровке) берутся по mod 31 (учитывая, что это простое число, текст становится чуть более безопасным).
Если рассматривать перебор обратных матриц-ключей, то всего нам придется перебрать $inline$31^{49} $inline$ комбинаций (это число примерно умещается в 75 знаков). Поэтому такой способ исключается моментально, хотя! Если из этого множества можно было бы каким-нибудь более-менее быстрым способом перебрать подмножество невырожденных матриц, то возможно задача облегчилась бы. К сожалению я такого способа не знаю и не уверен, что такой вообще существует!
Читать полностью »

Анализ публикаций на Хабрахабре за 2017 год. Статистика, полезные находки и рейтинги - 1

Подходит к концу 2017 год. Пришло время подвести некоторые итоги. Каким был этот год на Хабрахабре? Чтобы ответить на этот вопрос мы, в Cloud4Y, решили собрать статистику по всем публикациям за прошедший с начала года период. В этой статье мы расскажем о том, что показалось нам наиболее интересным.

С 1 января по 18:00 22 декабря 2017 года на Хабрахабре было опубликовано 10684 поста, которые посмотрели около 123 миллионов раз! Мы не включили в счёт 46 мегапостов и публикации, которые были скрыты или перенесены на Geektimes. В среднем в месяц публиковалось около 900 постов, а рекордным стал март.

Анализ публикаций на Хабрахабре за 2017 год. Статистика, полезные находки и рейтинги - 2
Читать полностью »

Сверточная сеть на python. Часть 3. Применение модели - 1

Это заключительная часть статей о сверточных сетях. Перед прочтением рекомендую ознакомиться с первой и второй частями, в которых рассматриваются слои сети и принципы их работы, а также формулы, которые отвечают за обучение всей модели. Сегодня мы рассмотрим особенности и трудности, с которыми можно столкнуться при тестировании вручную написанной на python сверточной сети, применим написанную сеть к датасету MNIST и сравним полученные результаты с библиотекой tensorflow.
Читать полностью »

Пеленгский фермер Бух'ерик разводит хрякоплюхов. Эти животные размножаются так быстро, что их поголовье ежедневно возрастает в 3 раза. Но, начиная со второго дня, на ферму повадилась нападать стая страшных зверей долбогрызов, каждый вечер пожирающих вдвое больше хрякоплюхов, чем их было в предыдущий день. Сколько хрякоплюхов будет у фермера на 7-й вечер, если вначале их было 10?

Вывод формулы n-ного члена для рекуррентной последовательности на примере задачи из квеста Амнезия - 1

Вы спросили у гаальца, что он думает по поводу этой задачки. После некоторого размышления тот ответил:
— В начале было 10 хрякоплюхов. В первый день они размножились, и к началу второго дня их стало 30. Во второй день они опять размножились (их стало 90), но вечером пришли долбогрызы и съели вдвое больше хрякоплюхов, чем было вчера (в первый день), т.е. 20 штук. Итого, в начале третьего дня получаем 70 хрякоплюхов. Мне кажется, что, продолжая решать таким образом, можно вычислить число хрякоплюхов в любой день.

Это задача из игры «Космические Рейнджеры 2», квест Амнезия.
Попробуем вывести формулу для количества хрякоплюхов на n-ный день, и посчитать для примера количество хрякоплюхов на 32-й день.
Читать полностью »

«Есть запахи, которые вы не можете ощущать, длины волн света, которые вы не видите, звуки, которые вы не можете услышать,… есть мысли, о которых вы не можете думать.»

imageПривет.
Помните офигенную статью «Вы и ваша работа» (+219, 1928 в закладки, 328k прочтений)?

Так вот у Хэмминга (да, да, самоконтролирующиеся и самокорректирующиеся коды Хэмминга) есть целая книга, написанная по мотивам его лекций. Давайте ее переведем, ведь мужик дело говорит.

Это книга не просто про ИТ, это книга про стиль мышления невероятно крутых людей. «Это не просто заряд положительного мышления; в ней описаны условия, которые увеличивают шансы сделать великую работу.»

Кто хочет помочь с переводом — пишите в личку или на почту magisterludi2016@yandex.ru

Глава 24. Квантовая механика

(за перевод спасибо Нате Блянкинштейн)

Большинство физиков в настоящее время считают, что у них есть базовое описание Вселенной [хотя в настоящее время они признают, что 90-99% Вселенной находится в форме «темной материи», о которой они не знают ничего кроме того, что она испытывает гравитацию]. Вы должны понимать, что во всей науке есть только описания того, как что-то происходит, и ничего о том, почему это происходит. Ньютон дал нам формулу, выражающую как работает гравитация, и он не делал никаких гипотез ни о том, чем она является, ни через какую среду она работает, не говоря уже о том, почему она работает. На самом деле он даже не верил в «дальнодействие».

Причины обсуждать квантовую механику, КМ, такие:

  1. это фундаментальная физика,
  2. она имеет много неожиданных интеллектуальных следствий и
  3. дает ряд моделей для работы.

В конце XIX — начале XX века физика столкнулась с рядом проблем. Среди них были следующие:
Читать полностью »

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

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

Все методы моделирования данного исследования представлены на программном языке Python. Этот язык является распространённым инструментов в сфере научных исследований и сфере обучения.

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

Данная статья посвящена собственной реализации (солвер Joker FEM) метода конечных элементов для систем уравнений диффузии-реакции.

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

Читать полностью »

Проблематика вопроса сформулирована в предыдущей статье.

А именно: как оценить влияние определенного допущения модели Блэка-Шоулза на расчетную величину премии по европейскому опциону? Допущения о том, что цена торгуемого актива имеет логнормальное распределение. Как альтернативу расчета по формуле Блэка-Шоулза я использовал подход — прогнозирование выплат покупателю опциона методом Монте-Карло. На вход программе я подавал:

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

В каждом случае я рассчитал премию опциона по формуле Б-Ш и методом Монте-Карло. Сравнил результаты и сделал(?) выводы:
Расчет премии по опциону методом Монте-Карло vs формула Блэка-Шоулза - 1

Читать полностью »

Кривые Безье и Пикассо - 1

Пабло Пикассо в своей студии на фоне картины «Кухня», фотография Херберта Листа.

Художник и простота

Одни из самых любимых мной работ Пабло Пикассо — это его линейные рисунки. Он изобразил на некоторых из них животных: сову, верблюда, бабочку и т.д. Эта работа под названием «Собака» висит на моей стене:

Кривые Безье и Пикассо - 2

(Можете перейти к интерактивному демо, в которой мы воссоздали «Собаку» с помощью представленных в статье математических расчётов)

Эти рисунки чрезвычайно просты, но каким-то образом им удаётся глубоко тронуть зрителя. Они создают впечатление простоты композиции и реализации. Одно движение руки и подпись создают настоящий шедевр! Рисунок одновременно кажется и небрежной импровизацией, и точно подобранной увертюрой в симфонии изящества.Читать полностью »