Новый учебный год только начался, а нам уже есть что написать про ABBYY Labs.

На этот раз студенты были поделены на 2 группы для параллельной работы над 2 проектами с рабочими названиями «LingvoGames» и «Q&A». Первый проект — мобильное приложение под Android. Более того, игра! Про неё обязательно будет отдельный пост после того, как она попадёт в топ Google Play. А второй — это не «квешенс и ансверс», как вы могли бы подумать. Хотя постойте-ка…

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

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

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

Введение

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

Оглавление (на данный момент)

Часть 1. Описание, операции, применения.
Часть 2. Ценная информация в дереве и множественные операции с ней.
Часть 3. Декартово дерево по неявному ключу.
To be continued...

Очень сильное колдунство

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

Вспомним-ка еще раз структуру дерамиды. В ней есть ключ x, по которому дерамида есть дерево поиска, случайный ключ y, по которому дерамида есть куча, а также, возможно, какая-то пользовательская информация с (cost). Давайте совершим невозможное и рассмотрим дерамиду… без ключей x. То есть у нас будет дерево, в котором ключа x нет вообще, а ключи y — случайные. Соответственно, зачем оно нужно — вообще непонятно :)

На самом деле расценивать такую структуру стоит как декартово дерево, в котором ключи x все так же где-то имеются, но нам их не сообщили. Однако клянутся, что для них, как полагается, выполняется условие двоичного дерева поиска. Тогда можно представить, что эти неизвестные иксы суть числа от 0 до N-1 и неявно расставить их по структуре дерева:

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

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

С первого дня пользования меня очень интересовал вопрос — как же на обычном емкостном экране, которые воспринимает только определенную площадь прикосновения удалось добиться работы тонкого стилуса, да еще с кнопкой и несколькими степенями нажатия?

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

Другие части: Часть 1. Часть 3..

Данный пост — продолжение рассказа «Жизнь в эпоху «тёмного» кремния». В предыдущей части рассказывалось о том, что такое «тёмный» кремний и почему он появился. Также рассматривались два из четырех основных подходов, позволяющих микроэлектронике процветать в эпоху «темного» кремния. Было рассказано о роли новых открытий в области технологии производства, о том, как повысить энергоэффективность за счет параллелизма, а также, почему уменьшение площади процессорного кристалла, видится маловероятным. В этот раз на повестке дня следующий подход.

Другие части: Часть 2. Часть 3.

Пока продолжение рассказа о коммуникационных фабриках по не зависящим от меня причинам откладывается, хотелось бы осветить другую тему.
С 8 по 12 октября в Подмосковье проходила крупнейшая в России конференция, посвященная проблемам разработки микро- и наноэлектронных систем. И хоть сама конференция оставила скорее негативное впечатление, но одно из выступлений выделялось из общей массы и, вероятно, будет интересно уважаемым читателям. Речь об аналитическом докладе «Life with «dark» silicon. Power and termal problems in future platforms», который представлял Mike Kishinevsky (Principal Engineer, Strategic CAD Labs, Intel Corp.). Я постараюсь рассказать об основных идеях этого доклада, используя материалы конференции и сторонние источники.

От переводчика: недавно я купил часы с лазерным проектором и прочёл в инструкции привычную фразу: «Запрещено ремонтировать самостоятельно». Раньше в инструкциях писали, что при самостоятельном ремонте производитель отказывается от гарантийных обязательств. Это наглость, но можно понять. Сейчас они прямо запрещают разбирать устройство, даже не объясняя почему. То есть просто выкинь и купи новое. Полный беспредел потребительской культуры.

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

1. Постановка задачи

Полный взвешенный граф из 500 вершин задан матрицей смежности.
Необходимо найти гамильтонов цикл в этом графе как можно меньшей суммарной стоимости.

0. Оглавление

• 1. Предисловие
• 2. Хак eMMC памяти HTC Desire HD с целью изменения идентификационной информации телефона
• 3. Создание телефона-оборотня с использованием криптографии
• 4. Ложная безопасность: обзор угроз несанкционированного доступа к данным
• 5. Заключение

1. Предисловие

Мобильные гаджеты стали неотъемлемой частью нашей повседневной жизни, мы доверяем им свои самые сокровенные тайны, а утрата такого устройства может привести к серьезным последствиям. Сегодня много внимания уделяется освещению вопросов мобильной безопасности: проводятся конференции, встречи, крупные игроки выпускают комплексные продукты для персональной и корпоративной защиты мобильных устройств. Но насколько такие средства эффективны, когда устройство уже утрачено? Насколько комфортны они в повседневном использовании – постоянные неудобства с дополнительным ПО, повышенный расход батареи, увеличенный риск системных ошибок. Какие советы можно дать беспокоящимся за сохранность своих мобильных данных? Не хранить ничего важного на смартфоне? Тогда зачем он такой нужен – не птичек же в космос отправлять, в самом деле?
Сегодня я хочу поговорить с вами об устройствах под управлением ОС Android, созданной глубокоуважаемой мною компанией Google. В качестве примера я использую неплохой смартфон прошлых лет от компании HTC – Desire HD. Почему его? Во-первых, именно с него мы начали свою исследовательскую деятельность в области безопасности Android-устройств, во-вторых – это все еще актуальный смартфон с полным набором функций среднестатистического гуглофона. Он поддерживает все версии Android, в нем стандартный взгляд HTC на организацию файловой системы и стандартная же раскладка разделов внутренней памяти. В общем, идеальный тренажер для защиты и нападения.
С этим докладом я выступил на вот-вот только прошедшей конференции ZeroNights 2012 и теперь хочу презентовать его хабрасообществу. Надеюсь он будет вам интересен и даже немного полезен.

Железо, сертифицированное в Microsoft, как совместимое с Windows 8, обязательно должно поддерживать технологию «безопасной загрузки» UEFI secure boot, которая не позволяет загружать неподписанный код. Это создаёт большие проблемы всем, кто захочет поставить на сертифицированное железо отличную от Windows ОС. Консорциум Linux Foundation в октябре этого года объявил о том, что все дистрибутивы Linux смогут воспользоваться универсальным предзагрузчиком, который будет подписан корпорацией Microsoft и позволит относительно безболезненно загружать альтернативные системы.

Загрузчик давно написан и отлажен, но пока что не подписан Microsoft. Почему? Путь к получению заветного сертификата с ключом оказался необычайно длинным и тернистым. О том, как это происходило, рассказывает в своём блоге член совета Linux Foundation Джеймс Боттомли.

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

Векторное изображение на рассеянных кривых

Долгое время возможности векторной графики были ограничены только линейными и круговыми градиентами, в результате чего можно было создавать лишь «плоские» изображения с определённым набором фигур. Настоящим прорывом стали смешанные градиенты (gradient mesh), которые впервые сделали векторную графику фотореалистичной. Группа французских исследователей под руководством Александрины Орзан (Alexandrina Orzan) из Технологического института в Гренобле в 2008 году сделала следующий шаг на пути развития векторной графики. Они разработали инструменты для генерации векторной графики на рассеянных кривых (diffusion curves), в том числе программу для автоматической конвертации растровых изображений в векторные.

Недавно на хабре появилась неплохая статья про вычисление N-ного числа фибоначи за O(log N) арифметических операций. Разумный вопрос, всплывший в комментариях, был: «зачем это может пригодиться на практике». Само по себе вычисление N-ого числа фибоначи может и не очень интересно, однако подход с матрицами, использованный в статье, на практике может применяться для гораздо более широкого круга задач.

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

loop 1000000000
  loop 1000000000
    loop 1000000000
      a += 1
      b += a
    end
  end
end
end

Незамедлительно выведет a = 1000000000000000000000000000, b = 500000000000000000000000000500000000000000000000000000, несмотря на то, что если бы программа выполнялась наивно, интерпретатору необходимо было бы выполнить октиллион операций.

— А нет ли у тебя скрипта, который две тыщи раз кликнет по кнопке «добавить»? — спросил меня наш Инженер по тестированию.
— Нет… —сказал я, — но что-нибудь придумаем.

Писать скрипт — это как-то скучно и неспортивно. Поэтому я решил сделать мышь. Но не простую, а прокачанную:

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

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

Ниже показан результат обработки реального размытого изображения (не с синтетическим размытием). Исходное изображение было получено камерой Canon 500D с объективом EF 85mm/1.8. Фокусировка была выставлена вручную, чтобы получить размытие. Как видно, текст совершенно не читается, лишь угадывается диалоговое окно Windows 7.



И вот результат обработки:



Практически весь текст читается достаточно хорошо, хотя и появились некоторые характерные искажения.

Под катом подробное описание проблем деконволюции, способов их решения, а также множество примеров и сравнений. Осторожно, много картинок!

На днях, гуляя по багтрекеру gcc наткнулся на интересный баг, в нем используется сразу несколько возможностей C++11:

• std::function — механизм для создания функторов — объектов функций
• non static member initialisation — механизм для инициализации членов класса вне конструктора
• lambda — тут и так все ясно. Исчерпывающие статьи были здесь.

Анализируя этот баг, я подумал, что теперь можно удобно реализовать методы как first class citizens

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

Я уже писал, как собирал Maximite.

Вчера как-то был настрой, и решил я поставить туда RetroBSD.

RetroBSD — это настоящий UNIX, являющийся наследником 2.11BSD и предназначенный для встраиваемых систем с фиксированной структурой памяти. На текущий момент работает на микроконтроллере Microchip PIC32 с 128 килобайтами памяти и 512 килобайтами Flash. Данный процессор позволяет разделять адресное пространство ядра и пользовательских процессов.

RetroBSD обеспечивает защиту памяти ядра, используя аппаратные возможности микропроцессора, полноценную вытесняющую многозадачность, POSIX API (fork, exec, wait4 и т.д.). Можно писать программы прямо на устройстве, так как есть компилятор С. Ядро системы прошивается в кристалл, а файловая система загружается с SD-карты.

RetroBSD поддерживает не только аппаратуру Maximite, но и ряд альтернативных устройств на базе PIC32 (chipKIT Max32, Sparkfun UBW32, Microchip Explorer 16, Microchip PIC32 USB/Ethernet Starter Kit, Olimex Duinomite, Duinomite-Mini и Duinomite-Mega, eflightworks).

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

Торжественный момент включения, и…