Всем, доброго времени суток.

По сути, к реализации этой маленькой автоматизации меня сподвигла лень.

Собственно, с чего все началось.

У меня есть ноутбук с установленной gentoo, и i3wm оконным менеджером. Так же есть несколько мониторов(дома, на работе и т д). Разрешения на всех мониторах разные, способы подключения тоже (VGA, HDMI, DVI) разные. Активно, использую первые два.

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

xrandr --auto

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

--mode

И хотя, в xrandr для каждого монитора у меня есть несколько вариантов разрешений, есть одно (максимальное для данного монитора, которое удовлетворяет), но на каждом мониторе оно разное(так как сами мониторы разные).

Потому пришлось искать решение…

В последнее время параллельные вычисления прочно входят в жизнь, в частности, с использованием GPU.

Здесь было много статей на эту тему, поэтому ограничусь лишь поверхностным описанием технологии. GPGPU — использование графических процессоров для задач общего назначения, т.е. не связанных напрямую с рендерингом. Пример — библиотека Nvidia PhysX для расчёта физики в некоторых современных играх. Эта технология выгодна тем, что GPU хороши на параллельном выполнении с множеством потоков. Правда, потоков должно быть много, иначе производительность сильно упадет. Ещё из-за особенностей работы с памятью приходится несколько хитрить с передачей данных из оперативной памяти в видеопамять. Известные реализации: CUDA (Nvidia, только для видеокарт), OpenCL (Khronos Group, для гетерогенных систем) и AMD FireStream. Здесь будет обсуждаться только OpenCL.

Итак, приступим к практике. В качестве языка основной программы выберем Python. Он, конечно, не очень быстр сам по себе, зато отлично работает как «клей» — во многих применениях основной расчёт идёт в OpenCL, а код на Python только «подносит патроны». Существует отличная библиотека PyOpenCL, которой и будем пользоваться.

Есть такая интересная задача — построение 3D структуры по набору изображений (фотографий) — Structure from Motion. Как её можно решить? После некоторых размышлений приходит на ум такой алгоритм. Найдём на всех изображениях характерные особенности (точки), сопоставим их друг с другом и триангуляцией найдём их трёхмерные координаты. Тут правда есть проблема — неизвестно положение камер при съёмке. Можно ли их найти? Вроде можно. Действительно, пусть у нас N точек на кадре и M кадров. Тогда неизвестных будет 3 * N (трёхмерные координаты точек) + 6 * (M — 1) (координаты камер (вместо 6 может стоять другое число, но сути это не меняет)). Уравнений же у нас 2 * M * N (у каждой точки на каждом изображении есть две координаты). Выходит, что уже для двух изображений и 6 точек задачка разрешима. Под катом описание принципиальной схемы решения задачи SfM (по возможности без формул — но со ссылками для вдумчивого изучения).

Продолжаем разговор. Прошлая статья была переходной от предыдущего цикла о графических моделях вообще (часть 1, часть 2, часть 3, часть 4) к новому мини-циклу о тематическом моделировании: мы поговорили о сэмплировании как методе вывода в графических моделях. А теперь мы начинаем путь к модели латентного размещения Дирихле (latent Dirichlet allocation) и к тому, как все эти чудесные алгоритмы сэмплирования применяются на практике. Сегодня – часть первая, в которой мы поймём, куда есть смысл обобщать наивный байесовский классификатор, и заодно немного поговорим о кластеризации.

Введение

В computer science из года в год все более популярной становится тема обработки естественного языка. Из-за огромного количества задач, где требуется подобный анализ, сложно переоценить необходимость автоматической обработки текстовых документов.

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

Отметим, что приводимые подходы применимы не только к текстам, а вообще к любым объектам, которые можно представить в виде символьных последовательностей, например, какие-нибудь макромолекулы (ДНК, РНК, протеины) из генетики. Всего мы рассмотрим 4 метода:

1. Признаковое описание.
2. Попарное наложение (выравнивание) текстов.
3. Формирование профиля и скрытой марковской модели.
4. Представление фрагментами.

Итак, приступим.

И снова здравствуйте! Сегодня я продолжаю серию статей в блоге Surfingbird, посвящённую разным методам рекомендаций, а также иногда и просто разного рода вероятностным моделям. Давным-давно, кажется, в прошлую пятницу летом прошлого года, я написал небольшой цикл о графических вероятностных моделях: первая часть вводила основы графических вероятностных моделей, во второй части было несколько примеров, часть 3 рассказывала об алгоритме передачи сообщений, а в четвёртой части мы кратко поговорили о вариационных приближениях. Цикл заканчивался обещанием поговорить о сэмплировании — ну что ж, не прошло и года. Вообще говоря, в этом мини-цикле я поведу речь более предметно о модели LDA и о том, как она помогает нам делать рекомендации текстового контента. Но сегодня начну с того, что выполню давнее обещание и расскажу о сэмплировании в вероятностных моделях — одном из основных методов приближённого вывода.

Баста карапузики, кончилися танцы.

В предыдущей части мы детально рассмотрели «читерские» приёмы обхода «защит» (скрытие SSID, MAC-фильтрация) и защит (WPS) беспроводных сетей. И хотя работает это в половине случаев, а иногда и чаще — когда-то игры заканчиваются и приходится браться за тяжёлую артиллерию. Вот тут-то между вашей личной жизнью и взломщиком и оказывается самое слабое звено: пароль от WPA-сети.

В статье будет показан перехват рукопожатия клиент-точка доступа, перебор паролей как с помощью ЦП, так и ГП, а кроме этого — сводная статистика по скоростям на обычных одиночных системах, кластерах EC2 и данные по разным типам современных GPU. Почти все они подкреплены моими собственным опытом.

К концу статьи вы поймёте, почему ленивый 20-значный пароль из букв a-z на пару солнц более стоек, чем зубодробительный 8-значный, даже использующий все 256 значений диапазона.

Оглавление:
1) Матчасть
2) Kali. Скрытие SSID. MAC-фильтрация. WPS
3) WPA. OpenCL/CUDA. Статистика подбора

«В 1997 году Deep Blue обыграл в шахматы Каспарова.
В 2011 Watson обставил чемпионов Jeopardy.
Сможет ли ваш алгоритм в 2013 году отличить Бобика от Пушистика?»

Эта картинка и предисловие — из челленджа на Kaggle, который проходил осенью прошлого года. Забегая вперед, на последний вопрос вполне можно ответить «да» — десятка лидеров справилась с заданием на 98.8%, что на удивление впечатляет.

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

Доброго времени суток. Этот топик рассчитан на тех, кто имеет представление об ограниченных машинах Больцмана (restricted Boltzmann machine, RBM) и их использовании для предобучения нейронных сетей. В нем мы рассмотрим особенности применения ограниченных машин Больцмана для работы с изображениями, взятыми из реального мира, поймем, почему стандартные типы нейронов плохо подходят для этой задачи и как их улучшить, а также немного пораспознаем выражения эмоций на человеческих лицах в качестве эксперимента. Те, кто представления o RBM не имеет, могут его получить, в частности, отсюда:

Реализация Restricted Boltzmann machine на c#,
Предобучение нейронной сети с использованием ограниченной машины Больцмана

Одним вечером я наткнулся на статью о реализации одномерного клеточного автомата с помощью комонад, однако материал неполон и немного устарел, в связи с чем решил написать русскоязычную адаптацию (заодно рассмотрев двумерные клеточные автоматы на примере Game of Life):

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

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



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

Что такое «Инверсная кинематика»?

Задачей инверсной кинематики является поиск такого набора конфигураций сочленений, который обеспечил бы максимально мягкое, быстрое и точное движение к заданным точкам. Однако, множество существующих ныне методов страдают от таких недостатков как высокая вычислительная сложность и неестественность результирующих поз. В этой статье описан новый (вероятно, на момент написания статьи — 2010 г.) эвристический метод под названием «Метод прямого и обратного следования» ( Forward and Backward Reaching Inverse Kinematics, далее просто FABRIK),
FABRIK избегает использования вращений и матриц в пользу непосредственного получения точки на прямой. Благораря этому, дело обходится всего несколькими итерациями, имеет низкую стоимость вычислений и визуально естественную позу в результате. FABRIK так-же без проблем справляется с наложением ограничений а так-же использованием нескольких цепей и/или конечных точек. Именно об этом методе этот пост.

Canyon View
You are at the top of Great Canyon on its west wall. From here there is a marvelous view of the canyon and parts of the Frigid River upstream. Across the canyon, the walls of the White Cliffs join the mighty ramparts of the Flathead Mountains to the east. Following the Canyon upstream to the north, Aragain Falls may be seen, complete with rainbow. The mighty Frigid River flows out from a great dark cavern. To the west and south can be seen an immense forest, stretching for miles around. A path leads northwest. It is possible to climb down into the canyon here.

Содержание:
Приветствие
Часть 1 — Преддверие
Часть 2 — Лес
Часть 3 — Поляна
Часть 4 — Вид каньона
Часть 5 — Зал

Часть 4,
в которой мы займёмся рефакторингом, реализуем пару действий, узнаем о pattern matching и рекурсии, а так же сделаем из квеста настоящую программу.

Поскольку побеждать Великий Китайский Роскомнадзор наша штука для обхода блокировок в интернете пока не особенно научилась, а рассказать что-нибудь странное про свою работу все равно хочется, расскажу про реимплементацию похожего на Readability алгоритма при помощи Node.js и Бэйцзинского технологического института.

Что это вообще такое

Readability — это радикальное продолжение идеи AdBlock убирать с веб-сайтов лишние элементы. Там, где AdBlock старается снести только самые бесполезные для пользователя вещи (в основном рекламу), Readability удаляет заодно скрипты, стили, навигацию и все остальное ненужное. Раньше такой вид страницы называли «версия для печати», хотя на самом-то деле текст предназначен для чтения (отсюда название Readability – «Удобочитаемость»).

Лирическое отступление про парсеры

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

Для мониторинга IT-инфраструктуры мы используем множество инструментов, в том числе:

• Zabbix — о нем написано немало статей здесь на хабре. Нам очень нравятся его возможности низкоуровневого обнаружения, но его возможности визуализации данных оставляют желать лучшего.
• Graphite — система, которая хранит данные и имеет удобный интерфейс для их отображения. Сейчас мы импортируем в нее метрики из Zabbix и храним историю.
• Shinken — система мониторинга, которая основана на Nagios и написана на языке Python. Сейчас мы присматриваемся к ней. Нам нравится то, что в нее очень просто импортировать данные из системы документации сети Netdot (о ней я уже писал ранее), а также она легко интегрируется с Graphite.

Можно долго обсуждать преимущества/недостатки тех или иных систем мониторинга, но я хочу остановиться только на одном вопросе — выявлении аномалий. Когда в вашей системе мониторинга количество метрик измеряется сотнями, отследить аномальное поведение одной или нескольких из них не составляет труда. Но когда количество метрик измеряется десятками или сотнями тысяч, вопрос автоматического выявления аномалий становится актуальным. Ни один администратор или группа администраторов не в состоянии вручную отследить поведение сложной системы, состоящей из сотен устройств.
Инженеры из Etsy в свое время столкнулись с этой проблемой и разработали свой инструмент для обнаружения и корреляции аномалий. Называется он Kale и состоит из двух частей:

• Skyline
• Oculus

В левой руке Морфеуса лежит 7 синих и 3 красных таблетки, а в правой 5 синих и 8 красных. Вы закрываете глаза и берете таблетку — она оказывается красной, однако вы не знаете из какой руки ее взяли. Какова вероятность, что вы взяли ее из правой руки?

17 апреля 1761 — день смерти Томаса Байеса.
Под катом результаты того, что есть в рунете, помимо стандартных вещей типа Теорема Байеса, Байесовская сеть, Наивный байесовский классификатор , Байесовская фильтрация спама

Я не умею программировать на объектно-ориентированных языках. Не научился. После 5 лет промышленного программирования на Java я всё ещё не знаю, как создать хорошую систему в объектно-ориентированном стиле. Просто не понимаю.

Я пытался научиться, честно. Я изучал паттерны, читал код open source проектов, пытался строить в голове стройные концепции, но так и не понял принципы создания качественных объектно-ориентированных программ. Возможно кто-то другой их понял, но не я.

И вот несколько вещей, которые вызывают у меня непонимание.

Перед прочтением статьи рекомендую посмотреть посты про splay-деревья (1) и деревья по неявному ключу (2, 3, 4)

Динамические деревья (link/cut trees) мало освещены в русскоязычном интернете. Я нашел только краткое описание на алголисте. Тем не менее эта структура данных очень интересна. Она находится на стыке двух областей: потоки и динамические графы.

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

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

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

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

UPD: в текст внесены некоторые изменения с целью сделать его более понятным. Смысловая составляющая осталась прежней.

Вступление

Возможно, у этой системы найдутся приложения не только
в роли логического исчисления. (Алонзо Чёрч, 1932)

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

В этом посте я расскажу о новой и (как мне кажется) относительно малоизвестной фиче C++ - reference-qualified member functions. Расскажу о правилах перегрузки таких функций, а также, в качестве примера использования, расскажу, как с помощью ref-qualified функций можно попытаться улучшить схему управления ресурсами, реализуемую с помощью другой идиомы С++ — RAII.