close

Вход

Забыли?

вход по аккаунту

?

Об одном существенном условии в распознавании конечных множеств.

код для вставкиСкачать
Известия Института математики и информатики. Ижевск. 2006. №2(36)
УДК 519.517
c В. А. Белоусов, Н. И. Калядин
ОБ ОДНОМ СУЩЕСТВЕННОМ УСЛОВИИ
В РАСПОЗНАВАНИИ КОНЕЧНЫХ МНОЖЕСТВ1
Ключевые слова: распознавание, классифицирующая функция, эталлоные множества.
Abstract. Condition which increase the efficiancy of finite sets recognition
is made.
В работе указано существенное условие, наложенное на исходные данные (конечные множества), при выполнении которого удаётся эффективнее распознавать исходные множества по сравнению с комбинаторным (переборным) алгоритмом сравнения множеств.
Пусть имеется основное множество M ⇋ {X1 , X2 , ..., Xm } из
m конечных множеств Xi , i = 1, m, m > 2;
S ⇋ {N1 , N2 , ..., Nt }
— разбиение на t > 2 классов множества M ; f : Im → It —
классифицирующая функция, распределяющая номера элементов
основного множества M по номерам классов из S,
Im ⇋ {1, 2, ..., m},
It ⇋ {1, 2, ..., t}.
Обозначим через Pi (X) характеристическую функцию
1, если X ∈ Ni ;
Pi (X) =
0, в противном случае;
1
Работа выполнена при финансовой поддержке РФФИ (гранты 03-01-00255, 04-01-96016).
113
индексные множества Dj :
Dj ⇋ {i : f (i) = j},
j = 1, t;
Ek — эталонные множества, полученные по алгоритму эталонирования [1], k = 1, t.
Пусть
T
1, если Ei X 6= ∅, i = 1, t,
Ri (X) ⇋
0, в противном случае;

T
 1, если Ei
Xk 6= ∅,
k∈Dj
qij ⇋
 0, в противном случае.
Л е м м а 1.
Пусть (∀i ∈ It )(∀X ∈ M )[X 6= ∅]. Тогда
(∀X ∈ M )[Pi (X) ⇒ Ri (X)].
Т е о р е м а 1.
Пусть (∀X ∈ M )[X 6= ∅].
Если
(∀i 6= j ∈ It )[qij = 1 ⇒ qji = 0], то
_
[Pi (X) = Ri (X)&¬(
Rj (X)&qij )].
j∈It \{i}
Д о к а з а т е л ь с т в о.
( → ). Пусть X ∈ Ni , то есть Pi (X) = 1 .
Покажем, что
W
Rj (X)&qij )] = 1.
[Pi (X) = Ri (X)&¬(
j∈It \{i}
В самом деле (∀i ∈ It )(∀X ∈ M )[Pi (X) ⇒ Ri (X)] в силу леммы W1. Отсюда Ri (X) = 1 , то есть Ei ∩ X 6= ∅ . Покажем, что
Rk (X)&qik ) = 0 . Тогда, если (∀i 6= j)[Rj (X) = 0] , то
(
k∈It \{i}
W
Rk (X)&qik ) = 0 независимо от qik , k ∈ It \ {i} .
(
k∈It \{i}
114
противное,
T, а значит
S то есть (∃i 6= j)[Rj (X) = 1]
TПредположим
S
Xk 6= ∅ ,
Xk . Следовательно, Ei
Xk 6= ∅ . Но X ⊆
X
k∈Dj
k∈Dj
k∈Dj
то есть qij = 1 .
По условию теоремы имеем qij = 0 . Значит (Rj (X)&qij ) = 0 .
Пусть j1 , j2 , .., jk , ..., jr все такие индексы, что Rjk (X) = 1 ,
(k = 1, r) . Отсюда (Rjk (X)&qijk ) = 0 по тем же соображениям.
С другой стороны, для j ∈ It \ {j1 , j2 , ..jr , i} (Rj (X)&qij ) = 0
в силу того, что Rj (X) = 0 . W
Rj (X)&qij ) = 0 .
Отсюда следует, что (
j∈It \{i}
Поэтому заключаем, что
Ri (X)&¬(
_
Rj (X)&qij ) = 1.
j∈It \{i}
( ← ). Положим, что Pi (X) = 0 . Покажем, что тогда
_
Rj (X)&qij ) = 0.
Ri (X)&¬(
j∈It \{i}
Возможны два случая: 1)Ri (X) =W0 ; 2)Ri (X) = 1 .
В первом случае Ri (X)&¬(
Rj (X)&qij ) = 0 независимо
j∈It \{i}
от qij . Рассмотрим второй случай.
T
Положим, что Ri (X) = 1 , то есть Ei X 6= ∅ . Поскольку
Pi (X) = 0 , а S ⇋ {N1 , N2 , ..., Nt } — разбиение на t (t > 2) классов исходного множества M , то существует такое j 6= i , что
Pj (X) = 1 . Тогда в силу леммы 1 Rj (X) = 1 . Но X ⊆ ∪ Xk .
k∈Dj
T S
Xk 6= ∅ , то есть qij = 1 . Отсюда
Отсюда Ei
k∈Dj
Rj (X)&qij = 1,
то есть (
W
Rk (X)&qik ) = 1 . Следовательно,
k∈It \{i}
Ri (X)&¬(
_
Rj (X)&qij ) = 0.
j∈It \{i}
115
Объединяя прямое и обратное доказательство убеждаемся в
справедливости теоремы 1.
Анализ применимости условия (∀i 6= j ∈ Im )[qij = 1 ⇒ qji = 0]
в ранней работе авторов [2] при определении классов разбиения
конечных семейств конечных множеств показал: оно может являться самостоятельным и существенным условием в распознавании конечних множеств [3], что и отражено в теореме 1.
Список литературы
1. Белоусов В.А., Калядин Н.И. Алгоритм построения эталонных множеств при сильном слипании множеств в обучении//
Тез. второй междунар. конф. «Математические алгоритмы».
Н.Новгород: Изд-во ННГУ, 1995. С. 8.
2. Белоусов В.А., Калядин Н.И. О некоторых классах разбиений конечных семейств конечных множеств// Автоматические устройства учета и контроля: Межвуз. сб. ИМИ. Ижевск,
1976. Вып. 11. С. 84-94.
3. Белоусов В.А., Калядин Н.И. О задаче классификации множеств натуральных чисел// Тез. докл. III конф. РОАИ.
Н.Новгород, 1997. Ч.I. С. 94-97.
116
Документ
Категория
Без категории
Просмотров
3
Размер файла
87 Кб
Теги
условия, конечный, существенных, множества, одной, распознавание
1/--страниц
Пожаловаться на содержимое документа