Алгоритмы *

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

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

Для обеспечения безопасности передаваемых данных, как правило, используется протокол SSL (Secure Sockets Layer). Кроме того, если система представляет собой приложение, доступ в него может быть защищен логином и паролем. Для повышения безопасности может использоваться ЭЦП (Электронно-Цифровая Подпись) – бинарная последовательность данных, формируемая криптографическим алгоритмом.

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

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

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



Кому интересно прошу под кат…

На этой неделе я начал читать бакалаврам Академического университета базовый курс по алгоритмам. Начинал я совсем с основ, и чтобы тем, кто с базовыми алгоритмами уже знаком, было чем заняться, я в начале пары сформулировал две, наверное, самые свои любимые задачки по алгоритмам. Давайте и с вами ими поделюсь. Решение одной из них даже под катом подробно расскажу. Но не отказывайте себе в удовольствии и не заглядывайте сразу под кат, а попытайтесь решить задачи самостоятельно. Обещаю, что у обеих задач есть достаточно простые решения, не подразумевающие никаких специальных знаний по алгоритмам. Это, конечно, не означает, что эти решения просто найти, но после пары один из студентов подошёл и рассказал правильное решение первой задачи. =) Если же вам интересно посмотреть на начало курса или порешать больше разных задач — приходите к нам на (бесплатный) онлайн-курс, который начнётся 15 сентября.

Задача 1. Дан массив A длины (n+1), содержащий натуральные числа от 1 до n. Найти любой повторяющийся элемент за время O(n), не изменяя массив и не используя дополнительной памяти.

Сразу поясню. В условии не говорится, что каждое число от 1 до n встречается в массиве, поэтому повторяющихся элементов там может быть сколько угодно (если бы все числа входили по разу, а одно — дважды, то задача была бы гораздо проще). Ограничение на использование дополнительной памяти означает, что нельзя заводить дополнительный массив линейной длины, но можно заводить переменные.

Задача 2. Дана матрица nxn, содержащая попарно различные натуральные числа. Требуется найти в ней локальный минимум за время O(n).

Локальным минимумом матрицы называется элемент, который меньше всех своих четырёх соседей (или трёх, если этот элемент лежит на границе; или двух, если это угловой элемент). Обратите внимание, что от нас требуется линейное по n время, хотя в матрице квадратичное по n число элементов. Поэтому мы предполагаем, что матрица уже считана в память. И нам нужно найти в ней локальный минимум, обратившись лишь к линейному количеству её ячеек.

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

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

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

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

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

Часть 1

Техники сжатия данных

Для сжатия данных придумано множество техник. Большинство из них комбинируют несколько принципов сжатия для создания полноценного алгоритма. Даже хорошие принципы, будучи скомбинированы вместе, дают лучший результат. Большинство техник используют принцип энтропийного кодирования, но часто встречаются и другие – кодирование длин серий (Run-Length Encoding) и преобразование Барроуза-Уилера (Burrows-Wheeler Transform).

Привет, Хабр. Подумал, кому-нибудь пригодится параллельная сортировка с относительно простой реализацией и высокой производительностью на платформе CUDA. Таковой является сортировка методом пузырька. Под катом приведено объяснение и код, который может пригодиться (а может и нет… ). Сразу скажу, что представленная прога является бенчмарком по сравнению производительности на GPU и CPU. Если тебе не жалко, читатель, то скомпилируй ее, пожалуйста, и положи результаты расчета в комменты этой статьи. Это не для науки. Просто интересно =)

Здравствуйте, меня зовут Дмитрий Карловский и я… клиент-сайд разработчик. За плечами у меня 8 лет поддержки самых различных сайтов и веб-приложений: от никому не известных интернет-магазинов, до таких гигантов как Яндекс. И всё это время я не только фигачу в продакшн, но и точу топор, чтобы быть на самом острие технологий. А теперь, когда вы знаете, что я не просто хрен с горы, позвольте рассказать вам про один архитектурный приём, которым я пользуюсь последний год.

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

Осторожно: чтение может вызвать вывих мозга, приступ холивара, а также бессонные ночи рефакторинга.

Добрый день, всем!

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

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

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

Добрый день уважаемый читатель, вашему вниманию предоставляется проект разработки системы сенсорного управления мини-дирижаблем.
Задачей управления является движение дирижабля по линии. Также была реализована простая система дистанционного управления.
Объектом управления является мини-дирижабль разработанный на кафедре ЭиМ, ТТИ ЮФУ.


Рисунок 1 — Общий вид мини-дирижабля.

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

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

Из выступления Max Little (основателя PVI) на конференции TED в 2012 году.

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

В данной статье будет рассказано о проекте Parkinson Voice Initiative, посвященному ранней диагностике Болезни Паркинсона по голосу (успешность распознавания составляет 98,6± 2.1% за 30 секунд по телефонному разговору).
Будет произведено сравнение точности используемых в нем алгоритмов выбора особенностей (ВО) – Feature Selection Algorithm – LASSO, mRMR, RELIEF, LLBFS.

Битва между Random Forest (RF) и Supported Vector Machine (SVM) за звание лучшего анализатора в данного рода приложениях.

Начало

Читая статьи по синтезу и распознаванию речи, нашел упоминание о том, что при болезни изменяется голос. Проверив очевидность факта, что я не первый догадался использовать распознавание речи для диагностики болезней (первые клиницисты определили некоторые features — особенности еще в 40-х годах прошлого века, записывая на магнитофонную ленту, а потом вручную анализируя), пошел по ссылкам Гугла. Одна из первых указывала на проект PVI.

Как часто вам приходится вводить в интерфейс какой-либо программы/web-сервиса дробные значения? Если часто, то, вероятно, вы сталкивались с неадекватным поведением таких полей. Я, например, довольно регулярно бьюсь лбом об абсолютно тупые формы. Хотите знать, почему ввод дробных значений может довести до белого каления, и что с этим делать? Добро пожаловать по кат.

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

Ранее система показывала неплохие результаты, но разработчики могли управлять 10-100 роботами одновременно, не более. Теперь команда достигла очередного успеха: самоорганизовать удалось уже более 1000 роботов, если быть точным, то 1024. Сами роботы называются Kilobots (собственно, все логично).

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

Аперитив

Всем, наверное, известно, как посчитать количество бит в числе. Например, подойдут следующие два способа:

while (n)
{
    ++count;
    n &= (n-1);
}

while (n)
{
    if (n&1)
        ++count;
    n >>= 1;
}

Упражнение: какое в среднем количество операций будет выполнено в первой и во второй реализации?

Блюдо

Пусть у нас есть n-битное число вида 2^i. Нам необходимо найти i за O(1).
Как это сделать? Пусть n = 2^k. Построим последовательность де Брёйна (de Bruijn) над алфавитом {0,1} для подстрок длины k.

Что такое последовательность де Брёйна?

Конечно, до коммунального рая нам пока далеко, но позитивные сдвиги все-же намечаются. Сегодня я расскажу о том, как электронными системами управления отоплением в моем многоквартирном доме было сэкономлено 124 тысячи рублей кровных денег жильцов в отопительном сезоне 2013-2014 года. Как только это случилось — все стали довольны, но по началу эта история была практически детективной.

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

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

Одной из наиболее популярных техник для построения персонализированных рекомендательных систем (RS, чтобы не путать с ПиСи) является коллаборативная фильтрация. Коллаборативная фильтрация бывает двух типов: user-based и item-based. User-based часто используется в качестве примера построения персонализированных RS [на хабре, в книге Т.Сегаран,...]. Тем не менее, у user-based подхода есть существенный недостаток: с увеличением количества пользователей RS линейно увеличивается сложность вычисления персонализированной рекомендации.

Когда количество объектов для рекомендаций большое, затраты на user-based подход могут быть оправданы. Однако во многих сервисах, в том числе и в ivi.ru, количество объектов в разы меньше количества пользователей. Для таких случаев и придуман item-based подход.

В этой статье я расскажу, как за несколько минут можно создать полноценную персонализированную RS на основе item-based подхода.

Пару лет назад на Хабре проскакивало две статьи, в которых упоминался интересный алгоритм. Статьи, правда, были написаны нечитабильно. В стилистике «новости»(1, 2), но ссылка на сайт присутствовала, подробно можно было разобраться на месте (алгоритм за авторством MIT). А там была магия. Абсолютно волшебный алгоритм, позволяющий увидеть незримое. Оба автора на Хабре этого не заметили и сфокусировались на том, что алгоритм позволял увидеть пульс. Пропустив самое главное.



Алгоритм позволял усиливать движения, невидные глазу, показать вещи, которые никто никогда не видел живьём. Видео чуть выше – презентация c сайта MIT второй части алгоритма. Микросаккады, которые приведены начиная с 29ой секунды, раньше наблюдались только как отражения установленных на зрачках зеркалах. А тут они видны глазами.
Пару недель назад я опять натолкнулся на те статьи. Мне сразу стало любопытно: а что народ сделал за эти два года готового? Но… Пустота. Это определило развлечение на следующие полторы недели. Хочу сделать такой же алгоритм и разобраться, что с ним можно сделать и почему его до сих пор нет в каждом смартфоне, как минимум для измерения пульса.

В статье будет много матана, видео, картинок, немного кода и ответы на поставленные вопросы.

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