Алгоритмы *

Однажды я столкнулся с задачей генерации 128-битных случайных чисел для реализации генетического алгоритма. Из-за большой размерности задачи алгоритм гонялся долго, поэтому были повышенные требования к скорости работы. Я решил написать свой генератор специально для поставленной задачи.

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

Если вам в тягость пользоваться ГСЧ из стандартной библиотеки, у вас к нему нестандартные требования или просто охота держать под контролем весь процесс генерации случайных чисел в своем приложении, добро пожаловать под кат.

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

Сразу оговорюсь, целью данной статьи является не предоставить работающую программу на основе данного метода, а рассказать собственно про сам алгоритм, на чем он основан и в чем его преимущества.

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

Основные понятия
Изображение — отображение объекта на воспринимающие органы. То есть, описание объекта, как множество признаков. Часто объект представляется в виде вектора. Если множество признаков постоянное, то объект отождествляется с его изображением.
Образ (класс) — подмножество множества объектов или изображений.
Решающая функция — функция, на вход которой подается изображение, определяющая принадлежность объекта некоторому классу.

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

SAT уже тем хорош, что он ум в порядок приводит
Ломоносов (оригинал)

Введение

На хабре уже немало статей, посвященных проблеме P vs. NP и задаче о выполнимости логических формул (SATisfiability problem). Однако, большинство из них не отвечает на несколько самых важных вопросов. Почему эта проблема действительна важна для нас? Что будет, если её решат? Где это все вообще применяется? И почему необходимо иметь хотя бы общее представление, о чем там идет речь?



Если мы детально проанализируем наиболее заметные работы на хабре по данной теме [1, 2, 3, 4, 5, 6, 7], то заметим, что с одной стороны, люди обладающие знаниями в области вычислительной сложности не cмогут почерпнуть ничего принципиально нового в данных статьях. С другой стороны, данные статьи по-прежнему не являются общедоступными. Иллюстрация из заголовка наглядно демонстрирует проблему: тем, кому было не понятно, из неё ничего не ясно, а те, кто об этом уже слышал, в ней не нуждаются.

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

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

В этой статье я попробую показать, как обучить каскад с нуля за несколько часов, натренировав на поиск простого предмета в видеопотоке (примером будет очаровательная сова с фотографии). Все обучающие выборки и программы будут приложены.
Зачем всё это нужно? Каскад Хаара это один из простейших способов распознавания классов объектов с большой скоростью работы. К ним относятся лица и руки людей, номера автомобилей, пешеходы. Детектором Хаара просто находить животных в кадре (кстати, удивительно, что я не видел ещё ни одной автоматической кормушки для синиц на raspberry pi). К тому же, готовые реализации OpenCV есть под большинство существующих систем (даже для blackfin'a встречал). Всё это делает Хаара одним из самых удобных методов, позволяющих решать задачи видеообработки даже людям, которые никогда не работали с обработкой видео.

Привет, хабр!

Этим летом я принял участие в Научно-образовательной школе МГУ, которая проводится Московским Государственным Университетом и Лабораторией Научного Творчества СУНЦ МГУ. В этой статье я хотел бы рассказать вам о проекте, который я разработал во время школы на спецкурсе по программированию под руководством MAD_GooZe.

Для нетерпеливых

Идея проекта

Итак, у нас возникла идея сделать что-нибудь интересное, используя генетические алгоритмы. Например — попытаться генерировать красивые абстрактные изображения. К слову сказать, до начала работы над этим проектом, я был знаком с генетическими алгоритмами весьма посредственно, но пообщавшись с руководителем и почитав некоторые статьи в интернете, я ринулся в бой.

Слева — mergeSort, справа — родная сортировка. PepperFlash и 75 миллионов элементов.

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

Продолжение поста "Алгоритм Брезенхэма в приложениях реального времени".

Напомним, что речь идет написании программы вывода для лазерных сканаторов

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

В статье описывается задача сравнения оцифрованных (отсканированных) образов.

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

Главный технологический тренд мирового фондового рынка последних лет – бурное развитие так называемой алгоритмической, или высокоскоростной торговли. Теперь на биржах соревнуются не люди, а торговые роботы, совершающие сотни и тысячи операций за одну торговую сессию. Как обычно, зародившись на Западе, этот тренд уже добрался и до России – алгоритмических торговцев на Московской бирже стало очень много. Сегодня мы поговорим о перспективах развития данной области в нашей стране.

   Эта статья посвящена языку R. Он не так широко распространен на территории ex-USSR, как Matlab и тем более Python, но, безусловно, заслуживает внимания. Нельзя не отметить, что R — фактически стандарт для Data Science (хотя тут хорошо написано, что не R единым живут data scientists). Богатый синтаксис, совместимость с legacy кодом (что весьма важно в научных приложениях), удобная среда разработки RStudio и наличие огромного числа библиотек в CRAN делают R таковым.

Предисловие

Гуляя по англоязычным просторам интернета в поисках решения одной из наболевших тем на работе, наткнулся на очень интересный алгоритм под названием «Fast Threshold Clustering Algorithm». Данный алгоритм кластеризации, что примечательно, появился сравнительно недавно, а именно в ноябре этого года и автором является Дэвид Варади. Ссылка на первоисточник будет доступна в конце статьи.

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

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

Кроме того, был задан ряд провокационных вопросов, которые условно можно свести к вариации одного из двух:

1. Каковы критерии «кухни»? (вариации: вот этот брокер (имярек) кухня или нет? и пр.)
2. В чем отличия услуг ITinvest от услуг критикуемых вами кухонь?

Не желая вступать в полемику и спор с представителями форекс-сообщества (все-таки статья писалась не для них), я, тем не менее, счел себя обязанным продолжить объяснение, что такое «правильный» форекс, а также:

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

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

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

Введение

Несколько лет назад я сделал тест для программистов, который многим, скорее всего, не понравится. Если вы пишете на языке PHP, ваша любимая СУБД ― MySQL, а в качестве операционной системы вы предпочитаете Linux ― попробуйте его пройти. Заранее предупреждаю, тест своеобразный. Успешно его проходит всего несколько процентов испытуемых. Так что не стоит переживать. Если вы его не пройдете ― ничего страшного. Тест «заточен» под определенные навыки, которые требуются далеко не везде.

Получить отличный результат в тесте сложно. Поэтому некоторые испытуемые прибегают к черной магии ― пишут бота. Хорошее дело, между прочим. «Настойчивость и храбрость, отвага и удача, в беде не растеряться ― вот главная задача!» Поэтому капчи в тесте не было. Никогда. Наоборот, мне хотелось, чтобы ботов писали. Чтобы боты приходили. Чтобы тест выстоял, боты обломались, а «ботописатели» не жульничали, а учились.

В тесте 80 вопросов, из которых для каждого испытания случайным образом выбирается 25. У меня был простой (и, как потом выяснилось, абсолютно неверный) расчет. Чтобы тест нельзя было пройти, заучив или подобрав ответы, общая база вопросов изначально должна быть существенно больше, чем количество вопросов в одном испытании. Общее количество комбинаций тестов составляет число порядка 10²⁰. «Раз число такое большое, значит, и подобрать ответы будет очень сложно», ― думал я. Конечно, число сочетаний ― очень грубая оценка. Но задача автоматического подбора интуитивно казалась мне если и решаемой, то такими затратами, на которые ботописатель не пойдет. Думать так было большой ошибкой. Битву с ботами я проиграл. Дальше расскажу, почему.

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

Итак, вернемся к теме поста. Я давно хотел немного больше узнать о комплексных числах, а не только то, что корень из минус единицы равен i. Особенно вызывали интерес фигуры имеющие фрактальную структуру, хотелось понять, что это значит, и как сделать такую визуализацию. Где то на полке стояла книжка по ТФКП, а так же закончился курс по комплексному анализу на курсере, и появилось немного свободного от работы времени. Приступим.

В декабре 2013 завершились ежегодные соревнования по распознаванию визуальных образов ImageNet Large Scale Visual Recognition Challenge 2013 (ILSVRC2013), спонсируемые проектом ImageNet , который представляет собой огромную базу изображений. В настоящее время в базе имеется более 14 миллионов изображений.
Участники соревнований решали три задачи, описанные под катом.

Вы правильно поняли из названия, что это не совсем обычное описание алгоритма JPEG (формат файла я подробно описывал в статье «Декодирование JPEG для чайников»). В первую очередь, выбранный способ подачи материала предполагает, что мы ничего не знаем не только о JPEG, но и о преобразовании Фурье, и кодировании Хаффмана. И вообще, мало что помним из лекций. Просто взяли картинку и стали думать как же ее можно сжать. Поэтому я попытался доступно выразить только суть, но при которой у читателя будет выработано достаточно глубокое и, главное, интуитивное понимание алгоритма. Формулы и математические выкладки — по самому минимуму, только те, которые важны для понимания происходящего.

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

Если есть желание, то предлагаю пройти те же этапы самостоятельно параллельно со статьей. Проверить, насколько приведенные рассуждения подходят для разных изображений, попытаться внести свои модификации в алгоритм. Это очень интересно. В качестве инструмента могу порекомендовать замечательную связку Python + NumPy + Matplotlib + PIL(Pillow). Почти вся моя работа (в т. ч. графики и анимация), была произведена с помощью них.

Внимание, трафик! Много иллюстраций, графиков и анимаций (~ 10Мб). По иронии судьбы, в статье про JPEG всего 2 изображения с этим форматом из полусотни.

Открытые вакансии на должность разработчика в Яндексе есть всегда. Компания развивается, и хороших программистов не хватает постоянно. И претендентов на эти должности тоже хоть отбавляй. Главная сложность – отобрать действительно подходящих кандидатов. И в этом плане Яндекс мало чем отличается от большинства крупных IT-компаний. Так что базовые принципы, описываемые в этой статье, могут быть применимы не только к Яндексу.

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