Конструктивизация в классификации образов

ВЕСТНИК
УДМУРТСКОГО
УНИВЕРСИТЕТА
КОМПЬЮТЕРНЫЕ НАУКИ
2008. Вып. 2
УДК 519.712 : 510.25 : 510.67
c
⃝Í. È. Êàëÿäèí
КОНСТРУКТИВИЗАЦИЯ В КЛАССИФИКАЦИИ ОБРАЗОВ
Изучаются проблемы разрешимости и вычислимости, предопределяющие концепцию конструктивизации в задачах классификации образов.
Ключевые слова: разрешимость, вычислимость, классификация образов, конструктивизация.
Введение
Конструктивизация  одна из основных и пока нерешенных проблем
фундаментальной и прикладной науки.
В настоящей статье рассматриваются проблемы разрешимости и вычислимости в классификации образов. Сформулированные критерии разрешимости определяют условия конструктивизации в описании образов,
гарантирующие с учетом мер сложности (компактность, параллелизм,
симультанность, автоматная реализуемость) эффективную вычислимость
предикатов классификации.
Ÿ 1. О проблемах в классификации образов
i=1
Mi классифицируемых (распоРассматривается множество M =
k
S
знаваемых) образов (конечных объектов) x произвольной природы.
Первым шагом при конструктивизации является формализация исходного описания образа x ∈M для перехода от физической или семантической модели к математической.
Для этого с помощью подходящей редукции ϕ : M →N⇌{0, 1, 2, . . .}
осуществляется переход (кодирование) к натуральным числам. Дальнейшая формализация выполняется на единой алгоритмической основе  теории рекурсивных функций [4].
Пусть ϕ : M →Φ, где Φ  семейство всех конечных подмножеств
множества натуральных чисел N; ⟨M, ϕ⟩ множество конструктивных
объектов; O⇌{X1, X2, . . . , Xm}  обучающая выборка известных реализаций (описаний) Xi, i ∈Im⇌{1, 2, . . . , m} образа x; X  неизвестная реализация образа x; S⇌{N1, N2, . . . , Nt}  разбиение обучающей выборки