ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ ИДЕНТИФИКАЦИИ ГЕОМЕТРИЧЕСКИХ ОБЪЕКТОВ НА РЕШЕТКЕ Н.Ю. Золотых Нижегородский государственный университет им. Н.И.Лобачевского Рассматриваются параллельные алгоритмы идентификации гео-
метрических объектов, заданных на целочисленной решетке. Произ-
вольное подмножество c точек n-мерного k-значного гиперкуба
E k n ={0,1, ... , k − 1}
n , где n ≥ 2, k ≥ 2, назовем объектом. Произвольное
семейство C таких подмножеств назовем классом объектов. Одна из
задач точного машинного обучения (machine learning) заключается в
идентификации объекта c из заданного класса C с помощью вопросов
оракулу вида `x ∈ c?', где x – точка, произвольно выбираемая из E k n .
Поставленная задача легко сводится к задаче расшифровки дискретной
функции из некоторого класса (см., например, [1], приложение 1 и
библиографию).
Для идентификации используется машина UPRAM с p процессо-
рами [2]. За один шаг на такой машине возможно параллельное обра-
щение к оракулу в p точках.
Обозначим через HALFSPACE
k n множество объектов c, для каждо-
го из которых найдутся действительные числа a 0
, a 1
, ..., a n , такие, что
