���� 7. ������������� ��������� ���������� �� ��������
���������� ���������� (�����������)
���� ���������� ���������������
(Counter�ropagation)
������ ����-������� (Robert Hecht-Nielsen) ���������� ����
�ounter�ropagation ��� �������� ��� ����������� �����������������
���� �������� � �������������� �������� �����. ���� �������������
��� ������� ������� �������������, ��� ����������� ����� �������� �
������� ��������. �������� ��� ���� �ounter�ropagation ������ ��
���� � ������������ ���������� �������.
������ ���� ��������� �� ���. 7. ���������������� ����
CounterPropagation ����� ��� ����: ������� ����, ������������������
����� �������� � �������� ����, ������������ ������� "������" ���
��������� ������� ����� ����������. ���� ���� �������� �����
����������.

���. 7. ���� ���������� ��������������� ���
�������� ������
������ ���� �ounter�ropagation �������� �� �����������������
����������� ����� ������� � �������� ������. ������ ��������� ��
������� ���� ��� ��������� ������������� �� �������� ����, ��������
���� ���������� ��������� �������������� ������� ������ � ����������
�������� ������������� �� ������� ���� ����. ��-�� ������
��������-����������������� ������ ���������� ���� �������� ����
��������. ����� ������������� ���������� ���������������� �������
�ounter�ropagation, ����� ���������� ���� ���� ���� �������
��������������� �� �������� � ��������� ����.
� ���� ���������� ��������������� ���������� ��� ���������:
������������������ ����� �������� � ������ ���������� (Grossberg
Outstar). ��������� ����, ������������ ������ �������������� ���
������������ �����, ����� ������ � ����� �� �����������, ���
���������� ���������. ���������, ��� � ����� ������ ���������
���������� ������� ������ ������������� ��������� ���������
����������� ����������. ������ ������� �������� ������� �������� ��
��� ������� ���� ��������. ���� ����� (wmn)
������������ ������� W. ������ ������ ���� �������� �������� ��
����� ��������� ���� ����������. ���� ������ (vnp)
������������ ������� ����� V.
� �������� �������� ���� ���������� ��������������� �������
������� ������������� � ���������������� ��������� ���������
(��������� ��� �����������). ����� �������� ���� ��������� ��������
�������, ������� �������� ������� ��������. ���������� �����������
���� ���� ����������� �������� ���������� �����, ����� �������
������ �������� ��� ����������.
�������� ����
� ���������� ������������ ���� ����������� ����������� ���������
��������� ������� �������. ����� ������ ������ ����� ��������������
��� ������������ ����������� �������� �������, ������� ������
�������������.
��� �������� ���� �������� �� ���� �������� ������� ������ �
����������� ��� ��������� ������������ � ��������� ����� ����
��������.
��������� ������������ �������� ����� �������� ����� �������
�������� � �������� �����. ������ � ������������ ���������
���������� ������������ ��������� "�����������" � ��� ����
����������� (������� ������ ������������ � ��������).
w�=wc+r(x-wc)
��� w� - ����� �������� ����, ������� ���������
������� ��������� x � ���������� ��������, w� -
���������� �������� ����, r - ����������� �������� ��������, �������
������� ������ ��������� 0.7 � ����� ���������� ����������� �
�������� ��������. ��� ��������� ������ ������� ��������� ���� ���
�������� ������� �������� � ������� ���� ��� ������� � �������������
��������.
������ ���, ��������� � ��������-����������� ��������, ����������
��������������� �������� ����� ��� ��������� � ��������� �����, �
�������� �� �����������. ����������� ��������� ������������ ��������
����� ����� � ��������������� ��������� �������� ����.
��������� ��������� ����� ��������� ����� ������� ����� �����
������� ��������, � ���� ������ ���� ��������� ������������ ����
������ �������� ��� ������ �� ���. ���� ����� ������� ��������
����������� ������� ��������, ��� ��� ����������.
������ ���� �������� �������� �� ����� �������� ���� ����������.
����� �������� ����������� ��� ���������� ����� ������� ����
��������. ������ ��� �������������� ���� � ��� ������, ���� ���
����������� � �������� ��������, ��� ����� ��������� �����. ��������
��������� ����� ��������������� �������� ����� ����� � �����������
������� ������� ����������. �������� ���� ���������� - ��� ��������
"� ��������", �������� ���������� �������� �������� ������.
�������������� �����
� ����� ���������� ����� ���� �������� ������������� �� �������
"���������� �������� ���". ��� ������� �������� ������� ���� �
������ ���� ������ �������� ������ ���������� �������, ��� ������
������ ����. ���� ���������� ������������� � ������� ������. ���
����� �������� ���������� ������ ������� ���� ��������. ���� ����
�������� ������������� ���, ��� ���� ���� ����� ��������� �������, �
������ ��������� ����, �� ������ ������ ���� ���������� ������
�������� ����, ������� ��������� ���� ������ � ������������ ��������
��������, ��� ����� ������� �� ����.
� ������ ������ ���� ���������� ��������������� ���� �����������
�������� �������� ������� �� ������� � ��������. ���� ���� ���������
�������� ������ � �������� ��������������� ��������.
������� ����������. ������������� �������, ��������������
������� (������������� ������), ������ ������ (� ��������).
����������. ���� �� ���� ����������� ������� ������
������������� (������ �����������). � ���� ���� ����������� ��������
����� � �������� ���������������� �����������. � ����������� ������
����� ������� ������� ������ ������������� ����� ����������� ����
���������� ���������������.
������������
- ���� ���������� ��������������� ������. ��� ���� �����������
�������� �������������� �������� �� ��������� ������� ��������.
������� �������, ��� ��� ��������� ���� ����������� ����, ���
�������� ��������� ������� ������ ����� ��������� � ������
��������� �������� �������, ��������� 1/k, k - ����� ��������
��������.
- ���� ������ ������. ����� �������� �� ��������� � ��������
���������������� ����� ���� � 100 ��� ������.
- �� ����� ������������ ������� ����������� ���� ����������
��������������� ����������� ����������� ����������� �����������.
- ���� ������� ��� ����������, ��� ����� ������� ���������
�������������.
- ���� ���� ����������� ������� ������� � �������� � ���, ���
������� ���������� ��� ������� ������������ �����.
�����������. ���� ���������� ��������������� �����
����������� ��������� ����������� ��������� �������� �������������
�����.
- ��� ��������� ������������� �������� ����������� ����������
���� �� ������� ��������.
- ��� ���� ����� ��������� ������������� �������� -
�������������� ������� ������� "������� ��������������". ����
������ ���������� ����������� ����, ��� 1/k (k - ����� ��������
��������), �� ��� �������� ����������� �����, ����� ��� �����
������� � ������ ��������.
- ����� "������ ������������", ��� ������� ��� ������� ��������
������� ������������ ���� ���� ������ ��������, ����� ����
����������� "����� ������������", ��� ������������� �������� �����
������ �������� ��������, ������� ���������� ������, �����
���������� ���� �������� ������� � ���� ����������. ���� �����
�������� �������� �����������, ������������� �����.
������������� ���������
����.
������������� ��������� ���� ���� ����������� ��������� �������
(Donald Specht). ��� ������� ����������� ���� ������� ������������ �
���� ������� : "������������� ��������� ���� ��� �������������"
(Probabilistic Neural Networks for Classification) 1988,
"����������� ��� ������������� ������ � ������������� ���������
����" (Mapping or Associative Memory and Probabilistic Neural
Networks) 1990 �.
������ ���� ����� ����������������, ��� ������ �����������
�������������� �������� � ������������� ������. ������������� ����
������ ��������� ������� ��������� �����������, �� �����
��������������� ��� ��������� �������� ������ � ������ �����
������������ ������. ��� �������� ������� � ���������� �����������
������ ������������� ������� � �������� ������.
������ ������ ��������� ����������� ��������� � �������
����������� ����������. ������� ���������� �� �������� ������
����������, ������ ����������� ���� ��� ������� ������ (��������, ��
��������� ����� 6 ����� ����� �������� � ������� � ����� ������ �
�����). ����������� ���������� �������������� �� �������:
������������ ������ ����������� �� ��������� ����������� ������, ��
���� ���� ����������� ��������� ��������� ����������� �������������
���������� ������ �� ��������� ������.
��� ������� ����� ������������� ����� ������� ���������
����������� ��� ������� ������, �������� ����� ����� �����������
�������������� � ������ ������� � ������� ������ � �����������, ���
������� ��������� ����������� ����� �������.
������ ��������� ����������� � ���� �������� �� ������� �������.
���� ������ ���������� � ������ ����� ������������, ����� � ����
����� ���� ������������ ��������� �����������. �������� �� �����
������������� �����, ���������������, ��� � ���� ����� ���������
����������� �������. ����� ���������� ������� ������� ������� �
������ ���������, � �� ���� ��������� �� ���� ������� ����������� �
��������� � ����. � ������ ������� ������ � �����, ������� ��������
������� �������, ���������� ��������� ������� �������, ����� ��� ���
������������ � � ���������� ���������� ������ ��� ����� ���������
�����������. ���� � �������� ������� ������� ����� ����������������
������� (�����������). ���� ������� ����������� ���������� ���������
��������, ����� ����� ���� ������� ����������� � �������� ���������
�����������.
������������� ���� ����� ��� ����: �������, ���������� �
��������. ���������� �������� ������� �� ������ �� ������ ������.
������ �� ��� ����� ����������� ������� � ������� � ���� �������.
������� ������ �������� ���� �������� �������. �������� �������
�������� ���� � ����������� ����������, ����������� � ��� ������ �
������������ ������ ���� ���������, ������������� � ��� ������.
�������� �������� �������� ���������� ��������������� �������
������� ����������� �������������� ��������������� �������.

���. 8. ������� ���������� ��������
�����
������������. �������� ������������� ��������� ����
������� �����, ��� �ack�ropagation. ����������� ���� �������� ��
������, ��������� ��� ���������� �������� � ���� ��� ���������
������, ������� ����� ������ � ����� �������� ��������.
�����������. ������� ������ ������������� ��������� ����
����� �����������. �����������, ��� ��������� ������� � ���������
��������� �������� �� ���������� �� ���� ����������� ���������
(��������� �����������). ��������, ���� ����� ���� ����� ��������
�������� 2%, �� � ��������� ��������� ��� ����, ���������������
�����������, ������� ����� ������ ���� 2%. ���� �� ���������
����������� ���������� �� ��������� � ��������� �������, ���� �����
�������� �������� ���������. ��� ����� ������, ����� ��������������
������������ ��� ������ �������.
���� ��������
���� ������� ������� ���������� ���� ������������� ���� � 1982 �.
� ������������ �������� ����. � ����� �������� � ������ ������� �
�������������, ��� ������� ��������� ����������� ��� ���� ��������.
���� ���������� �� �������� ������ ������������ ������. ���������
���������� ��� ����� ���� ���� �������� �������������, ���
������������ �� ������ ������ � ������ ������ �����������.
���� �������� ���������� ��� ����: �������, ���� �������� �
�������� ����. ������ ���� ����� ���������� ���������� ��������.
����� ���� �������� ������������ � ������� ��������������� ��������
�������� ���� ����� ������������ ���� ����������. ������ ����
�������� �������������� �� ������ ���� �������� ���� ��������, ��
����������� ������ ����, � ����� � ��������������� ��������� �
�������� ����. � ������ ����������������, ���� ���������� ������ ��
�������� ���� ����� ������������� ���� ���������� � ���� ��������.
���� �������� ����������, ���� �� ����� ��������� ������������
���������� ������, � ������� ��������� ���� ���������� �� ��������
����. ��� ��������� �������� ������, ��� �������������������� �
����.
�������� ���� �������� �������, ����� ��������� ����� ���
����������� �� ������� � �������� ����� ������������. �����������
�������� ���� �������� ������������ �������� ��������� ���� �����
����������. ���������� ���������� ���� ������ ����� ���������
�������� � ������������ �������. ��� ����������� �������� ����
��������������� ���� "����-�����" ������ ���������� ����� �����.
���� ���� �������� ������������ ��� ������, ���������� �� ������
��� ����� ��� ������� �����������. ��-������, ����� �������, �������
����� ���� ��������� � ����� �������������� �������� ������
������������. ���� ����������� ������� ����� ����������, ���� �����
�������� � ������ ��������������� ������, ��������� �� ����
������������������� �������, ��� �� �������� ������.
������� ������� ������ ��� ���� �������������� 15% �� �����
�������� � ���� ��������. ������ ������������ ��������� ���� ��, ���
���� �������� ����� ����� ������������, ���� ��������� �������
�������� ������� ��������. ������� ������ ��������� ������������,
���� �� ����������� �� ������� ����� � ���� �������� � ����������
������� ������ �� ���������� ���������. ��� �������� ����� ����
������ ������� ��������� �������� ����� ������������� �����
�����.
����������� ����� ���� �������� ��������� �� ���. 9.

���. 9. ����������� ����� ���� ��������
������, �������� ������ ����� � �������� ������������� ������,
��� �������, ������������� ���. �������� ��������� ���������� �����
�������� �������� (�����������, �������� ���������, ������ ������,
������� ��������� ������������ ������� ��� ��������������
���������). ���� ������ ����� � ����������� �������, ���������������
�� �� ����, �������� ("����������" �� ��������� ����������)
��������������� ������� ��� "���� �����" � ���, ��� ������� ������
�� �������� �� ������ �� ��������. � ����� ������, ����� ������
����� ���� ������ �������� x1,
��, �n..., n - �����
�������� � ���� � �������� ������� � �������� ��������. ������
������� xi ��������� ��� +1, ��� -1. ���������
������, ������� ��������� k-�� �������, ����� Xk,
� ��� ����������, ��������������, - xik,
k=0, ..., m-1, m - ����� ��������. ���� ����
���������� (��� "����������") ������������ ������� �� ������
������������� �� ������, �� ������ ����� ��������� ������ ���, ��
���� Y = Xk, ��� Y - ������ ��������
�������� ����: y1, yi,
yn. � ��������� ������, �������� ������ �� ��������
�� � ����� ��������.
����, ��������, ������� ������������ ����� �����-�� �����������,
��, ��������� � ����������� ���� ������ � ������ ����, ����� �����
������� ��������, ������� ������� ��������� � ����� �� ���������� (�
������ ������) ��� �� "��������� ������������" ���� (� ������
�������).
�������� ���������������� ����
- �� ������ ������������� ���� ������������� ������������
��������������� ����� �������:

����� i � j - �������, ��������������,
������������������ � ������������������ ��������; xik,
xjk - i-�� � j-�� �������� �������
k-��� �������.
- �� ����� ���� �������� ����������� ������. ��� ���������������
��������������� ������������� �������� �������:
yi(0) = xi , i = 0...n-1,
������� ����������� �� ����� ���� ������� �������� � ����� ����
����� ����� �������� ��������. ���� � ������ yi
�������� ������� �������� � ����� ������ ����.
- �������������� ����� ��������� ��������
,
j=0...n-1
� ����� �������� �������

��� f - ������������ ������� � ���� ���������, ���������
�� ���. 10.

���. 10. ������������ �������
- ��������� ���������� �� �������� �������� ������� �� ���������
��������. ���� �� - ������� � ������ 2, ����� (���� ������
�����������������) - �����. ��� ���� �������� ������ ������������
����� �������, ��� ����� ����� �������� ������� ������.
������ ���� �� ����� �������� ������������� � ������ �� ������
�������������� �����. ��� ������� � ��������� ��������������
������������ ����. ��� ���� �������� ����� ���������� ������� m ��
������ ��������� ��������, �������������� ������ 0.15*n. ����� ����,
���� ��� ������ � � � ������ ������, ���, ��������, ����� ������� �
���� ������������ ����������, �� ���� ������������ �� ����� ����
������� � �������� � ��������� �� �� ������� ������� � � ��������.
��������� ������������� ���������, ������ ������������ � ����������
�������
������ ���������
������ ��������� (Boltzmann mashine) ������ �� ������� � ��������
�� ���� �������� � �������� ������� "��������������� ������" ���
������ � ������������ ��������� ���� ������� ����������� ��������.
���� (Ackley), ������ (Hinton) � ��������� (Sejnowski)
����������� ������� ��������������� �������� � 1985 �. ������� ����
��������, ������ ��������� ����� ������������ ���������, �������
���������� �� ����� ���������� � ���� �������. �������� ��������
����, ����������� ��������, �������� ����������� �������
������������ ���������.
������ ��������� ���������� ����� �������, ������� ������������ �
�������� �������� ����. ��� � ��� ���������� ������, �����������
���������� � ������� �������� � ����������� � �������� �������.
����������� ����������� ���������� ����������� ������� ����������� �
������ ������� � ���� �������. ���������������, ��������
������������ ����� ����. ��� ���������� ������������ �������
������������� �� ������ ������������ ���������� ������ ��������.
������ ���������, ����� �� ������� �����������, ����� ���� ���
��������� ������, � �� ������ ������������ ��� ���
�����������������. ��-�� ��������� ���������� � ��������� ��������,
������ ����� ������� ����� �������� ���������, ������� �������������
�������, ��� ����������� ����� ������������ ���������. ��������
����������� ������ ��������� ������������ � ����������� ��������,
������� ���������.
��� � � ���� ��������, ���� ����� ���� ����������� ���������
����� ��� �������������� ������������� ����������. ����������� ��
����� ������� ����� 15 % �� ������ ���������� ��������� � ����
�������, ��� ��� �����������.
�������� ���������������� ����
- ���������� ���������� T, �������������� �������������
�����������.
- ���������� ���� ��������� ������ � ��������� ������ � �������
�������.
- ���� ��������� ��������� ����� � ����������� ����� ���� �
��������� ������� ������� � ������������ � ���������� �����.
- ���� ������� ������� �����������, ����� ����� ��������� �����
�����������.
���� ��������� ����� �������� � ���������� ������� �������, ��
����������� ���������� ����� ��������� ����������� �� ������
������������� ���������:

��� P(c) - ����������� ��������� c � ������� �������; k -
���������, ����������� ��������� ���������, ���������� �
����������� �� ������; T - ������������� �����������.
���������� ��������� ����� r �� ������������ ������������� ��
���� �� �������. ���� P(c) ������, ��� r, �� ���������
�����������, � ��������� ������ �������� ���� ������������ �
����������� ��������.
��� ��������� ���� ����������� ������� ������ ��������� ��� �
�����������, �������� ������� �������, �������� �� ���������� ��
��������� ���������.
���� 3 � 4 ����������� ��� ���� ����� ����, ���������� ��������
����������� T, ���� �� ����� ���������� ���������� ������ ��������
������� �������. � ���� ������ ������������� ������ ������� ������ �
������� �������� �����������. ���� ������ �� ���� ��������
���������� ���������, ���� ������� ������� �� ������ ���������� ���
���� �� ���.
�������� ���������� ����������� ������ ���� �������
���������������� ��������� �������. ��� ���� ���� �������� �
����������� ��������.
������� ����������. ������������� �������, �������������.
����������. ��������� �������� ��������.
������������. �������� ���� ����������� ���� ���������� ��
��������� ��������� ����������� ������� ������������ ���������.
�����������. ��������� ��������� ����� ����������� ��
������ ��� ��������� �����, �� � ��� ���� �������� ����� �
������������ ����� ��� ��� ���� �������� ���� ������������. ���
����������� ��������� ���� ����������� ��������� ����� �����
�������� ��������.
���� ��������
���� �������� (Hamming) - ���������� ���� ��������. ��� ���� ����
����������� �������� ��������� (Richard Lippman) � �������� 80-� ��.
���� �������� ��������� �������������, ������������ �� ����������
����������� ��� �������� �������� ������, ��� �����������
������������ ����������� ��������. ���������� �������� ������������
��� ����� ���, ������������ ����� ����� ���������������� ��������
��������� ������������� �����. ���� ������� ������ ��������
������������ �������� ������, ������ - ����������� �������. ������
������� ���������� ��������� �������� �������� �������, � �������
����������� ������. � ������ �������� ������� ������� ��������������
�� ����������, ��� ������� ���������� ����� ����������� ��������
��������� � ������� ������� �������� �������� �����������.
���� �������� ����� ��� ����: ������� ���� � ����������� �����,
������� ������� ��������� �������� ���������; ���� ��������� (����
��������), � ����������� �����, ������� ������� ��������� ���
�������; �������� ����, ������� �������� ����� ����� � ����
���������.
���� ���� ������� ������������ ������� ��������������� � �������
�������, ��������� �������������� � ���� ���������. ������ �������
��������� � ���� ��������� �������� ������� �������������� � �������
������� � ��� �� ����� ���� � ����� �������������� � ���������
�������. ����� �� ���� ��������� � ��������� ���� ����������� �����
�����������.
�������� ���� �������� ������ �� ����������� ��������. �� �������
���� ��������� �������� ��������� �����, � �� ����� ��������� ����
��������� �������� ��������� ������, � �������� ����������� ������.
����� �������� ���� �������� ������ � �������� ����������� �������
������. ����������� �������� ���� �������� ������������ ��������
��������� ���� ����� ����������.

���. 11. ����������� ����� ���� ��������
�������� ���������������� ���� ��������
- �� ������ ������������� ������� ������������� ������ ���� �
������ ������������ ������� ������������� ����� ��������:
Wik=xIk/2,
i=0...n-1, k=0...m-1
bk = n / 2, k = 0...m-1
����� xik - i-�� �������
k-��� �������.
������� ������������ ���������� �������� � ������ ���� �����
������� ��������� �������� 0 < v < 1/m. ������ �������,
��������� � ��� �� ������� ����� ��� +1.
- �� ����� ���� �������� ����������� ������
x1, xi, xn
... �������������� ��������� �������� ������� ���� (�������
������ � ������� ��������� ����� ����):
, j=0...m-1
����� ����� ��������� �������� �������������� �������� �������
������� ����:
yj(2) = yj(1), j
= 0...m-1
- ����������� ����� ��������� �������� ������� ����:

� �������� �� �������:

������������ ������� f ����� ��� ������, ������ �������� b
������ ���� ���������� �������, ����� ����� ��������� ��������
��������� �� ��������� � ���������.
- �����������, ���������� �� ������ �������� ������� ���� ��
��������� ��������. ���� �� - ������� � ���� 3. ����� - �����.
���� ������ ���� �������� ��������: ���������������� ���� ��� ��
������ ���� ���������� ��� ������� �������������, ���� ������ ��
������������ � ����, ������� ������ ���� ����� ���� ������ ��������
�� ����.
���� �������� ����� ��� ����������� ��� ����� ��������. ���
�������� ����� ����������� �����������, ���� ����������� ������� ���
�������� ���������� � ������������. ��� ���������������� ����
�������� ����� ������� ���������� ��������, ��������� ������� ����
������� ���� ���� ������ �� �����, ������ ������� �� ������ �������
����. �, � ����� ������, ���� �������� �� �������� �� ������������
�������������, ������� ����� ��������� � ���� ��������. � �����,
���� �������� ������� � ������, ��� ���� ��������.
��������������� �������������
������
��� ������� ������ ���� ����������� ������ ����� (Bart Kosko) �
��������� ������ ��������. ��������� ������ ������� ������ ��
��������, ������� ������������ ��� ���������� �������. ������� ����
��������, ����� �������������� ����������� ������ ������ ������,
������������ ��������� �����, ��������������� � ���.
�� ���. 12 ������� ������ ��������������� ������������� ������.
��� ����� ������� ������, ������� ���� �������. ��� ������� ����
���������� �� ���� ��������� ������������� ��������� ������ �
������������ ��������� ������ ������� ��������. ������� ����
��������� ��������� ����� �����. ������� � �������� ���� ����� ���
���������� ������� ����� � ����������� ���������� �� ����.
������� ���� ����������� ��� ����������� ��������������� ���
��������. ���� �� ���� ���� ��������� ����������� ������ ������,
������� ���� ���������� �� ���������� ����������� ���������
����������, ��� �������� ��������� ��������� ���������� � �� ������
������������ ����� �� ���������� ���������. ������� ���� ��������,
��������������� ������������� ������ ��������������� � �������������
����������� ���������� ������, ���� ��������� ����������� �������
������, ������� �� ��� � ������� ���������� ���������.
��������������� ������������� ������ ��������� �
������������������� ������. ������� ������ ��������� �� ���� �����
��������, � ��������������� �������� ������ ������������� �� ������
������ ��������. ������� ������ ������������� � ���������.
��� ���������: ���� �������� �����������������. ������� �����
����� ���� ������������ ��� ��������� �����, �� �� ����� ����
������������ � ������ �������. � ���� �������� ������������
����������� ��������� ������������� ������, � ������� ��������
������ ���������� �� ������ ��� �� ��������, �� ������� ���������
������� ������.
��������������� ������������� ������, ��� � ���� ��������,
�������� � ���������, ����������� ���������� �������� �������,
�������� �� ������������ �����.
���������� ����� ��������������� ������������� ������. �������
������ A �������������� �������� ����� W ����, � ���������� ����
������������� ������ �������� �������� ���� B. ������ B
�������������� ����������������� �������� WT ����� ����, �������
����������� �������, �������������� ����� ������� ������ A. ����
������� ����������� �� ��� ���, ���� ���� �� ��������� �����������
���������, � ������� �� ������ A, �� ������ B �� ����������.

���. 12. ���������������� ������������� ������
������� � ����� 1 � 2 �������������, ��� � � ������ ����������,
�������� ����� ���������� ������ � �������� ������������ ������� F:
��� � ��������� �����:
B=F(AW)
��� B - ������ �������� �������� �������� ���� 2, A - ������
�������� �������� �������� ���� 1, W - ������� ����� ������ �����
������ 1 � 2, F - ������������ �������.
���������
A=F(BWT),
��� WT �������� ������������� ������� W.
� �������� ������������ ������� ������������ ������������
��������.
���� 0 �� ������ ���������� � �� ����� ������. �� - ����
��������� ������������� �������� �������� ���� 2 � ���������
������� WT.
������� ��� ���������� �������� ������������� �����:

��� Aj � Bj - ������� �
�������� ������� ���������� ���������.
������� ������� ����������� ��� ����� ������������ ���� ���������
����� ���������� ���������.
������� � �������� ������ ����� ��������� � ����������. ��� �����
���������� �� ��������� � ���������, ������� �� ��������
������������. ��������, ��� ��������������� ������������� ������
���������� ��������� ��� ����� ��������� ����� ����.
������� ����������. ������������� ������, �������������
�������.
����������. ������� ��������������� ������������� ������
������ ����������. ���� n - ���������� �������� �� ������� ����, ��
����� ��������, ������� ����� ���� ��������� � ���� �� ���������
L=n/2log2n. ���, ���� n=1024,
�� ���� �������� ��������� �� ����� 25 �������.
��������������� ������������� ������ ����� ���������
����������������� � �������� ����������������, ��������� ���������
������.
������������
- �� ��������� � ����������������� ������� (��������, �����
��������), ��������������� ������������� ������ ���� �����������
������� ���������� ����� ��������� A � B, ��� � ����� ������ �����
������ �����������. �� ���� ����� ������������ �������������������
������ ����� ����� ������� ����� ����������, ��� �����������������
������.
- ��������������� ������������� ������ - ������� ����, �������
����� ���� ����������� � ���� ��������� ���� ��� ���������������
��������.
- ������� ������������ ������������� ����� ������� � �������.
���� ������ �������� � �������� ����������������.
- ������� � ���� ����� ���� ��� �����������, ��� � �����������.
��� ����� ������� �������� ������������ ����.
���� ���������� �����������
������
����������� �������� ����������� � ����������� � �������� 80-�
��. ��������� ���������� ���������������� ��������, �����������
�������� ������� ������, �������� ��������� �������� �
�������������� ������ � ������� �������.
���� ���������� ����������� ������ ������� �� ����
��������������� ����� ��������, ������������� ����� ������� �
�������� ������. ������ ������� ����� ������ ���� ���������
����������� ��������� ����� �� ������ ����, ������� ������������ �
������� ����, ����� ������ �� ��������� ����. ��� ������� "��������"
����� ������ � ������ ������ ��� ���������� ������� ���������
�������.
���� ��������������� ������������ � ������������� �������������,
��� �� ����� ���������� ��������� ����������� ����������. �������
������������ ������� ����������� �������� �� �������
����������������. ���� ��������� ���������� ���� �� ������� �������
������ ���������� ����������� ��������� ����.
���� ART-1 ��������� �������� �������������, ����� ������� ��
�������� "����������������� ������". ������ ����� ��������� ������
������� ������ ��������� �������� ������� ��������. ���������
������� ������ ������������ � �������� ������� ��������. �������,
��� ������� ������ "������������ �� �������" � ����������� �������
��������, ���� ���������� �� ������� ������� �������� ������ ������.
� ��������� ������ ������ ������� ������ - ������� ������� ��������.
���� ������� ����������� ��� ���� ��������� ������� ��������. �����
�������, ����� ��������� ������ � �������� ������� � ������� ��� ��
�������� ������, ��� � �� ������������ ������������� ����������,
������������ ��� ��������� ������� �������� � �������� �������.
�������� ����� ���� ART-1 ������ �� ���� ��������. � �������
���������������� ������ ����������� ������������ ������� �������� �
�������� ���������. ������������ �������� ������������ ����������� �
������� ����������� ������ �������� ��������.
���� ART-1 ���������� �� ���� �������� ��������� ������� ��
�������� �������� � �������, ����� ���� ���� ����������� ���������
�������� ������ � ������������ ��������� ������������ � ���������
������������ ������������ �������� ������� � �������� ���������, ���
���� ������� �������� "����������������� ������".

���. 13. �������� ���������� ��������������
���������/����������
�������� ���������������� ����
- ������������� ����:
vij(0)=1;Wij(0)=1/(1+N)
0� i � N-1; 0�
j � M-1; 0� b � 1;
��� wij(t) - ������������� ��� �����
�� i-�� ������� ������� ���� � j-�� ������� ������� ���� � ������
������� t, vij(t) - ������������� ���
����� �� j-�� ������� ������� ���� � i-�� ������� ������� ���� �
������ ������� t, b - �������� ������.
���� vij(t) �
wij(t) ���������� �������, ����������
������� j.
����� b ����������, ��������� ������ ������� ������ ��������� �
����� �� ����������� ��������, ����� ��� ��������� ��������.
������� � ������� �������� ������ ������� ����� �������
����������.
��� ��������� ��������� ������ ������� ������ � �������, ����,
���� ��� ������ �����������, ��������� �������������� � ������
��������.
- ������������ ���� ������ ��������� �������� �������:
������� ������� ������������� ��������� ���� ��������
���������� ���� ��������.
- ���������� �������� ������������:

�������� ������������ ����������� ����������� ��� ����
��������, ���������� � ����, ���������� ���� ��������.
- ����� ������� � ���������� �������������:
yj=max(yj)
��� �������� ����������� � ������� ������������ ����������.
- ��������� � �������:
;

���� ������� � ���� 7, ����� � ���� 6.
�� ���� ���� ����������� ��������� ���������� ������������
�������� ������� � ������� � ���������� ��������� ������������ �
����� ��������� ��� �������� �������. �������� ���������
������������ � �������, ��������� �� ������ ����.
���� �������� ��������� ������ ������, �� ������� ������
��������� ������� ��������� ����������� �������� ������������. �
���� ������ ������� �������������� ����� ���������� �������� AND
(���������� "�"). ����� ������� �������� �������� �� ����������
���� + ������� ������.
���� �������� ��������� ������ ������, �� ���������, ���
������� ������ ���������� �� ���� �������� � ��������������� ���
����� �������. � ���� �������� ������, ���������� ������ �������,
� ����������� �������� ������������� �����.
- ���������� ������� � ���������� ��������� ������������:
����� ������� � ���������� ��������� ������������ ��������
��������������� ������ ���� � ����� �� ��������� ������� � ����
4.
- ��������� ������� � ���������� ��������� ������������:
vij(t+1)=vij(t)xj

- ��������� ���� ����������� �� ���� 6 ��������. ����������� �
���� 2.
������� ������� � ���� ������ ��������.
����������� ����� � ������ ���������� ��� �����������
���������� ������ ������������� �������������� �������, �� �������
������������ ��������� ����, ��� ���������� ���������� -
���������������� �������������.
������� ���� ��������� � ������ �������� ������� ���� �
����� ������������� � �������� ���������������� ����.
������� ����������. ������������� �������, ����������
������.
����������. �������������� ���������� ����� �������� �
�������� ���������������� ����. � ���������� ���� ���������
������������ ��������, ��������� � ���������������� ������ �����
��������.
������������. �������� ��� �������.
�����������. ���������� ������ ART-2 � �����������
���������� �������� ���������.
|