Рад сообщить, что вышел перевод отличнейшего учебника Дасгупты, Пападимитриу, Вазирани «Алгоритмы», над которым я работал последние несколько лет. В книге многие алгоритмы объяснены гораздо короче и проще, чем в других учебниках: с одной стороны, без излишнего формализа, с другой — без потери математической строгости. Откройте книгу на каком-нибудь известном вам алгоритме и убедитесь в этом. =)

В общем, угощайтесь: печатный вариант перевода, электронный вариант перевода (PDF), печатный вариант оригинала, электронный вариант оригинала (PDF).

Давным-давно, в 1996 году палмы назывались пилотами, и выпускала их компания U.S. Robotics (как и модемы). Мне удалось достать их самый ранний КПК — U.S. Robotics Pilot 5000 — с прокачанной до 1Мб памятью: да-да, в то время карманные компьютеры поддерживали апгрейд (привет Google Project Ara) — можно было получить ИК порт и больше памяти, или например модуль приема пейджинговых сообщений).

Процессор — Motorola Dragonball, работающий на частоте 16Мгц. Впрочем, этого было более чем достаточно для любых применений: в PalmOS 1.0 правильно написанные приложения были «всегда запущены» — и переключение между ними было практически мгновенным. Монохромный экран с разрешением 160x160 пикселей и без подсветки — жрал минимум энергии.

Определение

Параллельное программирование сложно. При использовании систем с общей памятью не обойтись без синхронизации доступа параллельных процессов/потоков к общему ресурсу (памяти). Для этого используются:

• блокировки (mutex);
• алгоритмы без блокировки (lockless, lock-free);
• транзакционная память.

Транзакционная память — технология синхронизации конкурентных потоков. Она упрощает параллельное программирование, выделяя группы инструкций в атомарные транзакции. Конкурентные потоки работают параллельно¹, пока не начинают модифицировать один и тот же участок памяти. К примеру, операции добавления узлов в красно-чёрное дерево (анимация в заголовке) способны работать параллельно в нескольких потоках.

Введение

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

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

Рис. 1 Стабилизация изображения иногда очень полезна.

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

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

Это перевод статьи Analysis Paralysis: Over-thinking and Knowing Too Much to Just CODE Скотта Хансельмана за 30 марта.

Прочитал сегодня пост на ArsTechnica «Я знаю слишком много чтобы программировать быстро. Что мне делать?» — это обзор вот этого вопроса на StackOverflow:

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

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

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

Для чего эта статья?

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

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

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

Продолжим разговор о нейронах-детекторах. Предположим, на зону коры посредством волновых туннелей проецируется некая информация. Каждый из проекционных пучков – это аксоны нейронов, расположенных на той зоне, которая эту информацию посылает. Проекция снимается с малого по площади участка коры. Волокна проекционного пучка, по сути, транслируют проходящие по этому участку волновые картины. То место принимающей коры, куда приходится проекция, само становится источником волн. Эти волны несут на принимающей зоне коры ту же информацию, что и волны на исходной зоне.

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

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

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

Предисловие

Года 3-4 назад судьба распорядилась так, что в руки мне попал ноутбук Asus G2S. Счастье моё длилось ровно до прошлой зимы, когда ни с того, ни с сего на экране стали появляться артефакты, особенно при запуске игрушек или «мощных» приложений, активно работающих с видеочипом. В результате оказалось, что проблема именно в нём. Nvidia для практически всей геймерской линейки G2 поставляла видеочипы с браком (отслоение контактов между самим кристаллом и подложкой), который обнаруживался лишь через пару лет интенсивной работы. Решение было однозначным – замена видеочипа. Но что делать со старым?! Ответ на этот вопрос пришёл на редкость быстро…
Много трафика под катом

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

Недавно exp131 и X4ZiM обратили внимание, что некоторые партии популярной микросхемы интерфейса USB-RS232 очень уж подозрительно одинаково глючат: в системе они определяются как обычные FT232RL, «признаются» официальным софтом, но отправляемые данные не передаются. Конечно, все мы привыкли к тому, что ошибку в первую очередь нужно искать у себя… Но что если проблема именно в микросхеме?

Фотографии микросхем: слева работает отлично, справа — глючит. Можно заметить отличие в маркировке — в рабочей микросхеме она выгравирована лазером, в нерабочей — напечатана (впрочем, это не универсальное правило, бывает и наоборот). Сначала смотрим фотографии, выводы в конце.

Вероятно многие встречались с таким вот «партизаном» при старте или завершении приложения:



Очень информативное сообщение, сразу понятна причина ошибки, место и способ ее решения.
Впрочем, если без шуток, что это вообще такое?
Конечно-же это исключение, но ни тип исключения, ни его описание нам не доступны — просто «Runtime error 217» и адрес, а дальше сами…

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

И тратил бы его в дальнейшем, если бы на днях со мной не связался Виктор Федоренков и не рассказал о своих мыслях по поводу ошибки за номером 217.

Списки книг

• 25 бесплатных книг по информатике
• Шпаргалки
• CodePlex: Список бесплатных книг
• Бесплатные технические книги
• Galileo Computing (Немецкий)
• How to Design Programs: An Introduction to Computing and Programming
• Microsoft Press: Бесплатные книги
• MindView Inc
• Проект O'Reilly's Open Books
• TechBooksForFree.com
• Theassayer.org
• Wikibooks: Программирование
• Неплохая подборка, редактируемая сообществом (JIghtuse)
• Книги на Русском (telteron)

Программирование графики

Добрый день!

Я хочу рассказать о проекте игровой консоли Nintendo Entertainment System (NES) в реализации на FPGA. На постсоветском пространстве она известна как Dendy.


Желающих посмотреть видео и поностальгировать прошу под кат.

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

С некоторой натяжкой именно так работает вращение с помощью углов Эйлера. Немного непредсказуемо и неудобно, не правда ли? Углы Эйлера имеют несколько недостатков, но есть одно особенно нехорошее свойство из-за которого вы не захотите с ними связываться. Его имя — Gimbal lock.

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

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

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

Вас ждет много анализа и немного частных производных. Код прилагается.
Прошу под кат!

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

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

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

В качестве иллюстрации поста приведу обложку другой манги из той же серии, что и книга о статистике:

Вчера, то есть 22 марта, увидел свет релиз 5 версии GitLab. GitLab — замечательный аналог таким продуктам, как GitHub, Bitbucket. Однако он устанавливается на ваш личный сервер и полностью подконтролен вам. Это отличное решение для компаний, занимающихся разработкой программного обеспечения, web студиям ну или просто тем, кто хочет иметь свой собственный git репозиторий.



Что же нового в версии 5.0? Для ознакомления с подробностями прошу под кат

Если ты всегда мечтал написать свой язык программирования — добро пожаловать. Здесь ты наверняка найдёшь для себя что-нибудь интересное.

GitHub-юзер yawnt собрал чудесную подборку ссылок для любителей драконов, языков и прочих вкусных внутренностей. А знающие камрады в комментариях наверняка поделятся с тобой и другими яствами.

Пишет yawnt следующее:

С каждым днём мне всё интереснее тема компиляторов, интерпретаторов и дизайна языков программирования в целом. И я решил поделиться с народом ссылками на собранные мной материалы (большую часть мне самому ещё предстоит прочитать :<). Надеюсь, кому-нибудь они окажутся полезными.

Я не включил (и не собираюсь) в список ссылки на официальную документацию, т. к. считаю очевидным, что первым делом следует смотреть именно туда ;P.