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

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

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

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

В работе описаны дальнейшие перспективы по исследованию данного направления.

В статье описаны некоторые методы взаимодействия графической системы X Windows System с аппаратным обеспечением. На примере архитектуры EXA рассмотрены основные операции аппаратного 2D-ускорения.

Для исследования производительности было проведено тестирование Xorg с помощью утилиты x11perf версии 1.5. Тестирование проводилось в 5 режимах с использованием аппаратного 2D-ускорения и без. На основании результатов тестирования можно сделать вывод, что использование аппаратного 2D-ускорения с EXA оправдано в случаях, когда планируется использование изображений с высоким разрешением или есть необходимость снизить загрузку центрального процессора.

Тестирование производительности с отключенным взаимодействием с аппаратной частью (2D GPU + dummy EXA) показало, что использование EXA существенно влияет на скорость выполнения тестов, поскольку только на определенном наборе тестов драйвер 2D GPU + dummy EXA показывает лучший результат относительно драйвера modesetting.

Следует отметить, что использование EXA c DRM-стеком требует дополнительного исследования, так как при использовании DRM-стека с опцией EXA_MIXED_PIXMAPS в большинстве случаев операции масштабирования, копирования pixmap, заливки сплошным цветом и т.д. осуществляются на CPU. В определенных ситуациях отсутствие этой опции может привести к ряду графических артефактов в виде неперерисовывающихся областей изображения при обновлении кадрового буфера.

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

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

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

В процессе тестирования измерялось быстродействие метода и точность работы. Результаты тестирования показали быстродействие примерно 2 cекунды на двух выборках и точность в пределах 97 %. Данные исследования связаны с разработкой и реализацией модуля для потоковой идентификации людей по видеопотоку, где очень важна скорость реакции метода, а также его точность.