Аннотация доклада.

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

Аннотация доклада.

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

Аннотация доклада.

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

Аннотация доклада.

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

Аннотация доклада.

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

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

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

Аннотация доклада.

Исследование графов автоматами является корневой задачей во многих приложениях. К таким приложениям относятся верификация и тестирование программных и аппаратных систем, а также исследование сетей, в том числе сети интернета и GRID на основе формальных моделей. Модель системы или сети, в конечном счёте, сводится к графу переходов, свойства которого нужно исследовать. За последние годы размер реально используемых систем и сетей и, следовательно, размер их моделей и, следовательно, размер исследуемых графов непрерывно растёт. Проблемы возникают тогда, когда исследование графа одним автоматом (компьютером) либо требует недопустимо большого времени, либо граф не помещается в памяти одного компьютера, либо и то, и другое. Поэтому возникает задача параллельного и распределённого исследования графов. Эта задача формализуется как задача исследования графа коллективом автоматов (несколькими параллельно работающими компьютерами с достаточной суммарной памятью).

Предлагается алгоритм обхода заранее неизвестного ориентированного графа неограниченной группой параллельно работающих конечных автоматов, перемещающихся по дугам графа и взаимодействующих друг другом с помощью обмена сообщениями. Работа начинается с одного автомата в начальной вершине графа. Автомат, находящийся в некоторой вершине графа, может 1) генерировать другой автомат в той же вершине графа, 2) перемещаться по дуге, выходящей из этой вершины, 3) послать сообщение другому автомату по его адресу. Время работы описываемого алгоритма в худшем случае ограничено O(m+nd), где n — число вершин графа, m — число его дуг, d — диаметр графа, представленная оценка достигается на некотором семействе графов.

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

Аннотация доклада.

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

Первый алгоритм решает задачу обхода графа и выполняет разметку графа с помощью изменения состояний автоматов в вершинах. Время работы алгоритма O(n/k+d), где n – число вершин графа, d – диаметр графа, а k – «ёмкость» дуги как число сообщений, которые могут одновременно передаваться по дуге.

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

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

Предлагается алгоритм мониторинга динамически меняющегося графа, задача которого сбор полной информации о графе в каждой его вершине. Понятно, что если граф постоянно меняется, то мы не можем гарантировать, что описания текущего состояния всех его дуг отражены во всех его вершинах: сообщения о последних изменениях дуг просто «не дошли» до некоторых вершин. Поэтому требуется только, чтобы через время T₀ после изменения дуги все вершины графа «узнали» об этом или более позднем изменении дуги. Если после данного изменения дуга больше не меняется, по крайней мере, в течение времени T₀, то во всех вершинах графа будет одинаковое (и верное) описание этой дуги. Время работы алгоритма T₀ = O(d).

Для динамически меняющегося графа также разработаны алгоритмы разметки графа и параллельного вычисления функции. Время работы алгоритма разметки O(n). Время вычисления функции O(n²/w), где w ≤ n-1 – задаваемый извне параметр, которому прямо пропорциональны размер памяти автомата и сообщений в алгоритме вычисления функции.

Аннотация доклада.

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

Для лаконизации предлагается использовать информацию о связях между классами объектно-ориентированной (ОО) модели данных, на которой основана ООБД. Нами был использован подход к ООБД, описанный в стандарте ODMG 3.0, а конкретно следующие элементы: объект, литерал (literal), тип объекта, состояние (атрибуты и отношения), привязка (binding) к языку программирования Java. Такие элементы как идентификация, именование, создание, поведение, привязки к языкам C++ и Smalltalk нами не использовались.

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