Алгоритмы *

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

Введение

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

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

Введение

В алгоритмическом трейдинге при создании механических торговых систем (МТС) очень важен вопрос времени жизни торговых алгоритмов. Да, и найти их в принципе достаточно сложно. В условиях постоянно меняющегося рынка рано или поздно наступает момент, когда даже самый совершенный и прибыльный алгоритм начинает приносить убытки. И его нужно, что называется, «подкручивать» или оптимизировать под текущие условия рынка. Одними из самых распространенных являются торговые системы (ТС), работающие со свечными графиками с их многообразием индикаторов для технического анализа.

Всем привет!

15 января открылась регистрация участников ежегодного конкурса разработчиков – «Родная речь-2014». Победитель получит 120 000 рублей, серебряный призер – iPhone 5, а финалист, занявший третье место, – iPad 4.

Заполнить заявку самостоятельно или от имени команды можно на сайте деловой сети Marketing to Innovation, Education, Science, оказывающей конкурсу техническую поддержку.

Процедура регистрации подробно описана в инструкции.

В предыдущей части были освещены общедоступные вопросы, касающиеся SAT и P-NP: история проблемы, интуитивные определения классов и задач, указаны основные приложения SAT и основные последствия, в случаи решения P ?= NP (там же можно найти достаточное число ссылок на различный материал для самостоятельного изучения тематики).

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



картинка из статьи Boolean Satisfiability: From Theoretical Hardness to Practical Success (Communications of ACM)

Требуемые знания: знакомство с методами линейного программирования, методы решения транспортной задачи(особенно метод потенциалов).

Год назад, на третьем курсе в качестве одной из лабораторных работ по курсу «Методы оптимизации» мне задали реализовать решение транспортной задачи, но с одним небольшим условием: перевозки происходят партиями. Это значит, что теперь, в отличие от классической постановки, оплачивается перевозка партии товаров (e.g. 10 штук), и, даже если Вам надо перевезти 11 штук, Вы заплатите за две партии(в один трейлер 11 штук не влезут). Казалось бы, мелкое дополнение, однако как теперь решать задачу, да хотя бы как её формализовать? Как студенту кафедры прикладной математики, мне было не привыкать, что великий google.ru чего-то не знает, но каково же было моё удивление, когда ни его старший брат — англоязычный google, ни тьма перебранных мной книг по теории оптимизации не смогли ответить на этот вопрос.

Пролог

Друзья, всем привет! Недавно начал изучать помехоустойчивые коды и моделировать процесс их работы, и понял что по-человечески написанных топиков по этой теме совсем немного, а точнее мало. Мудрёные книги есть, но на то они и мудрёные, что на их изучение нужно время, а порой нужно получить какие-то базовые знания и представления по теме, за совсем сжатый промежуток времени. Как пример, могу привести статью по кодам Хэмминга, она мне здорово помогла, когда я только начинал возиться с кодами. Так же доступно подобные коды описаны здесь.

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

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

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

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

В статье мы постараемся классифицировать злокачественную опухоль груди от доброкачественной основываясь на наборе данных взятом отсюда. Как бы странно не звучало, но точность не будет главным приоритетом в этот раз, так как уже есть довольно хорошие решения с упором именно на точность, что и понятно, ведь от данных тестов зависит жизнь человека. Например в 2012 году Бриттани Венгер победила в конкурсе Google Science Fair с проектом cloud4cancer.appspot.com, который был обучен именно по выше указанному набору.

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

где Z₀ и Z₁ — искомые значения, s = u² + v², а u и v — равномерно распределенные на отрезке (-1, 1) случайные величины, подобранные таким образом, чтобы выполнялось условие 0 < s < 1.
Многие используют эти формулы, даже не задумываясь, а многие даже и не подозревают об их существовании, так как пользуются готовыми реализациями. Но есть люди, у которых возникают вопросы: «Откуда взялась эта формула? И почему получается сразу пара величин?». Далее я постараюсь дать наглядный ответ на эти вопросы.

Сегодня мы завершаем новогоднюю серию постов, посвященных лекциям Школы анализа данных. Последний по порядку, но никак не по важности курс — «Алгоритмы и структуры данных поиска».

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

Мы учли то, о чём нас просили в комментариях к прошлым курсам — теперь при желании можно не только смотреть/скачивать лекции по отдельности, но и загрузить всё разом в виде открытой папки на Яндекс.Диске. Кстати — в предыдущих постах тоже появились такие же апдейты (вот ссылки для удобства: «машинное обучение», «дискретный анализ и теория вероятностей», «параллельные и распределённые вычисления»).



Лекции читает Максим Александрович Бабенко, заместитель директора отделения computer science, ассистент кафедры математической логики и теории алгоритмов механико-математического факультета МГУ им. М. В. Ломоносова, кандидат физико-математических наук.

Данная статья посвящена широко известному методу Монте-Карло, который основан на теории вероятностей и математической статистике, в физике элементарных частиц. Так же, я расскажу, как можно разыгрывать дискретные и непрерывные случайные величины методом Неймана, а на закуску посмотрим, как применять ММК в ФЭЧ.

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

Доброго времени суток.

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

Доброго Нового Года!

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

Пусть имеется набор N из n целых положительных чисел от 1 до n.
Самоочевидно, что для хранения n чисел необходимо иметь n ячеек. Вне зависимости от порядка, в котором числа будут записаны.

Исходный массив

3

5

2

1

8

4

7

6

9

10

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

Упорядоченный массив

1

2

3

4

5

6

7

8

9

10

Доброго времени суток.

Пост и код приведённый ниже, предназначен не столько для использования алгоритма в рабочих целях, сколько для того, чтобы понять, как алгоритм fuzzy c-means работает и возможно, дать толчок к реализации этого алгоритма на других языках либо для усовершенствования приведённого кода и его дальнейшего использования в рабочих целях.

Доброго времени суток читатель. Сегодняшний пост будет посвящен вычислению приближенного значения фрактальной размерности плоского изображения, которая тесно связано с размерности Минковского. Это интересно как минимум по двум причинам. Во-первых оказывается, что размерность ограниченного множества в метрическом пространстве может быть не только целым числом, но и любым неотрицательным. Во-вторых значение размерности контура изображения (а это ограниченное множество в метрическом пространстве) является хорошим признаком. В рамках сегодняшнего поста не предусмотрено исследование робастности этого признака, но давайте рассмотрим показательный пример. Множество различных характеристик клеток опухолей молочной железы, полученное в результате анализа снимков тонкоигольной пункционной биопсии. Множество данных состоит из 30 признаков (поля таблицы) с пометкой злокачественная или доброкачественная опухоль, и одним из признаков является как раз фрактальная размерность ядер клеток опухоли. Под катом вас ждет объяснение смысла фрактальной размерности множества, по возможности доступным языком, алгоритм вычисления приближенного значения этой размерности, его реализация на c# и ряд примеров с картинками. Возможно вы открыли этот пост только из-за картинки справа, это изображение я позаимствовал из инстаграмма Jennifer Selter, и в конце мы вычислим фрактальную размерность, так сказать филейной части Дженифер. Хочется кстати вас попросить ответить на пару вопросов в конце поста.

От переводчика:

Под «капотом» следует перевод небольшого, но крайне полезного текстового файла "%UPX_SOURCE%\doc\filter.txt". В приведенном пути под UPX_SOURCE подразумевается файловый путь до исходных кодов к UPX версии 3.91.

Документ описывает достаточно важный аспект работы UPX называемый «фильтрацией» и при анализе упакованных с помощью UPX файлов крайне важно понимать как это работает. Все что описано про UPX также применимо и к другим упаковщикам.

Основная цель перевода это попытка помочь тем программистам кто пишет статические распаковщики исполняемых файлов. Другими словами эта информация будет полезной практикующим reverse-engineer-ам. Под статичеческим распаковщиком понимаю программу которая поданный на вход упакованный или запротекченный исполняемый файл анализирует и создает на выходе файл, как будто бы тот создан каким-либо компилятором. Особенностью такого типа распаковщиков в том что он работает исключительно на знании структуры защиты или упаковки файла, т.е. без применения «сброса дампа», «востановления импорта» и др. типов «читерства».

Понимание процесса фильтрации помогает при изучении упакованных файлов к примеру с помощью UPX, RLPack и др. В упакованных файла можно встретить код, где делаются некоторые «магические действиями» с маш. инструкциями переходов байты 0xE8, 0xE9 и др. Этой «магией» как раз и является «фильтрация». Она направлена на улучшение степени сжатия исполняемого файла.

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

Многие из нас сталкивались в своей работе с СУБД. На текущий момент базы данных в том или ином виде окружают нас повсюду, начиная с мобильных телефонов и заканчивая социальными сетями, в число которых входит и любимый нами хабр. Реляционные СУБД являются наиболее распространенными представителями семейства СУБД, и большинство из них являются транзакционными.
В институте нас заставляли заучивать определение ACID и стоящие за ним свойства, но почему-то стороной обходились подробности реализации этой парадигмы. В данной статье я постараюсь частично заполнить этот пробел, рассказав о MVCC, которая используется в таких СУБД как Oracle, Postgres, MySQL, etc. и является весьма простой и наглядной.

Введение

Известно, что компьютер может оперировать числами, количество бит которых ограниченно. Как правило, мы привыкли работать с 32-х и 64-х разрядными целыми числами, которым на платформе .NET соответствуют типы Int32 (int) и Int64 (long) соответственно.

А что делать, если надо представить число, такое как, например, 29! = 8841761993739701954543616000000? Такое число не поместится ни в 64-х разрядный, ни тем более 32-х разрядный тип данных. Именно для работы с такими большими числами существует длинная арифметика.

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

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

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

def customlogic(params):
    return params[0] and params[1] and not params[5] and params[11] or params[2] and not params[3] or params[0] and params[5] and not params[6] or params[7] and not params[8]

В конце статьи алгоритм проверяется на данных полученных из реального мира.