���� ������ "����������� ���������������� ����������"
������������� ������������ � ���������� ���������������� ������
���������� ���������������� ���������� - ��������� ��������, ����� �������
�������� ������ � ������ ���������� ���������������� ����������
������� ���������� ������ ������
������������� ��������� ����
��������� �������� ����������� � ������ ��������� �����
������������� ��������� ���������� �� �������� ���������� ����������
��������� � ������� �����������
����������� ����������� �������� ����������������� ����������
��������� ��� ������������ ���������
�������� ������

 

���� 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. � ��������� ������, �������� ������ �� �������� �� � ����� ��������.

����, ��������, ������� ������������ ����� �����-�� �����������, ��, ��������� � ����������� ���� ������ � ������ ����, ����� ����� ������� ��������, ������� ������� ��������� � ����� �� ���������� (� ������ ������) ��� �� "��������� ������������" ���� (� ������ �������).

�������� ���������������� ����

  1. �� ������ ������������� ���� ������������� ������������ ��������������� ����� �������:

    ����� ij - �������, ��������������, ������������������ � ������������������ ��������; xik, xjk - i-�� � j-�� �������� ������� k-��� �������.

  2. �� ����� ���� �������� ����������� ������. ��� ��������������� ��������������� ������������� �������� �������:

    yi(0) = xi , i = 0...n-1,

    ������� ����������� �� ����� ���� ������� �������� � ����� ���� ����� ����� �������� ��������. ���� � ������ yi �������� ������� �������� � ����� ������ ����.

  3. �������������� ����� ��������� ��������

    , j=0...n-1

    � ����� �������� �������

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

    ���. 10. ������������ �������

  4. ��������� ���������� �� �������� �������� ������� �� ��������� ��������. ���� �� - ������� � ������ 2, ����� (���� ������ �����������������) - �����. ��� ���� �������� ������ ������������ ����� �������, ��� ����� ����� �������� ������� ������.

������ ���� �� ����� �������� ������������� � ������ �� ������ �������������� �����. ��� ������� � ��������� �������������� ������������ ����. ��� ���� �������� ����� ���������� ������� m �� ������ ��������� ��������, �������������� ������ 0.15*n. ����� ����, ���� ��� ������ � � � ������ ������, ���, ��������, ����� ������� � ���� ������������ ����������, �� ���� ������������ �� ����� ���� ������� � �������� � ��������� �� �� ������� ������� � � ��������. ��������� ������������� ���������, ������ ������������ � ���������� �������

������ ���������

������ ��������� (Boltzmann mashine) ������ �� ������� � �������� �� ���� �������� � �������� ������� "��������������� ������" ��� ������ � ������������ ��������� ���� ������� ����������� ��������.

���� (Ackley), ������ (Hinton) � ��������� (Sejnowski) ����������� ������� ��������������� �������� � 1985 �. ������� ���� ��������, ������ ��������� ����� ������������ ���������, ������� ���������� �� ����� ���������� � ���� �������. �������� �������� ����, ����������� ��������, �������� ����������� ������� ������������ ���������.

������ ��������� ���������� ����� �������, ������� ������������ � �������� �������� ����. ��� � ��� ���������� ������, ����������� ���������� � ������� �������� � ����������� � �������� �������. ����������� ����������� ���������� ����������� ������� ����������� � ������ ������� � ���� �������. ���������������, �������� ������������ ����� ����. ��� ���������� ������������ ������� ������������� �� ������ ������������ ���������� ������ ��������.

������ ���������, ����� �� ������� �����������, ����� ���� ��� ��������� ������, � �� ������ ������������ ��� ��� �����������������. ��-�� ��������� ���������� � ��������� ��������, ������ ����� ������� ����� �������� ���������, ������� ������������� �������, ��� ����������� ����� ������������ ���������. �������� ����������� ������ ��������� ������������ � ����������� ��������, ������� ���������.

��� � � ���� ��������, ���� ����� ���� ����������� ��������� ����� ��� �������������� ������������� ����������. ����������� �� ����� ������� ����� 15 % �� ������ ���������� ��������� � ���� �������, ��� ��� �����������.

�������� ���������������� ����

  1. ���������� ���������� T, �������������� ������������� �����������.
  2. ���������� ���� ��������� ������ � ��������� ������ � ������� �������.
  3. ���� ��������� ��������� ����� � ����������� ����� ���� � ��������� ������� ������� � ������������ � ���������� �����.
  4. ���� ������� ������� �����������, ����� ����� ��������� ����� �����������.

    ���� ��������� ����� �������� � ���������� ������� �������, �� ����������� ���������� ����� ��������� ����������� �� ������ ������������� ���������:

    ��� P(c) - ����������� ��������� c � ������� �������; k - ���������, ����������� ��������� ���������, ���������� � ����������� �� ������; T - ������������� �����������.

    ���������� ��������� ����� r �� ������������ ������������� �� ���� �� �������. ���� P(c) ������, ��� r, �� ��������� �����������, � ��������� ������ �������� ���� ������������ � ����������� ��������.

    ��� ��������� ���� ����������� ������� ������ ��������� ��� � �����������, �������� ������� �������, �������� �� ���������� �� ��������� ���������.

���� 3 � 4 ����������� ��� ���� ����� ����, ���������� �������� ����������� T, ���� �� ����� ���������� ���������� ������ �������� ������� �������. � ���� ������ ������������� ������ ������� ������ � ������� �������� �����������. ���� ������ �� ���� �������� ���������� ���������, ���� ������� ������� �� ������ ���������� ��� ���� �� ���.

�������� ���������� ����������� ������ ���� ������� ���������������� ��������� �������. ��� ���� ���� �������� � ����������� ��������.

������� ����������. ������������� �������, �������������.

����������. ��������� �������� ��������.

������������. �������� ���� ����������� ���� ���������� �� ��������� ��������� ����������� ������� ������������ ���������.

�����������. ��������� ��������� ����� ����������� �� ������ ��� ��������� �����, �� � ��� ���� �������� ����� � ������������ ����� ��� ��� ���� �������� ���� ������������. ��� ����������� ��������� ���� ����������� ��������� ����� ����� �������� ��������.

���� ��������

���� �������� (Hamming) - ���������� ���� ��������. ��� ���� ���� ����������� �������� ��������� (Richard Lippman) � �������� 80-� ��. ���� �������� ��������� �������������, ������������ �� ���������� ����������� ��� �������� �������� ������, ��� ����������� ������������ ����������� ��������. ���������� �������� ������������ ��� ����� ���, ������������ ����� ����� ���������������� �������� ��������� ������������� �����. ���� ������� ������ �������� ������������ �������� ������, ������ - ����������� �������. ������ ������� ���������� ��������� �������� �������� �������, � ������� ����������� ������. � ������ �������� ������� ������� �������������� �� ����������, ��� ������� ���������� ����� ����������� �������� ��������� � ������� ������� �������� �������� �����������.

���� �������� ����� ��� ����: ������� ���� � ����������� �����, ������� ������� ��������� �������� ���������; ���� ��������� (���� ��������), � ����������� �����, ������� ������� ��������� ��� �������; �������� ����, ������� �������� ����� ����� � ���� ���������.

���� ���� ������� ������������ ������� ��������������� � ������� �������, ��������� �������������� � ���� ���������. ������ ������� ��������� � ���� ��������� �������� ������� �������������� � ������� ������� � ��� �� ����� ���� � ����� �������������� � ��������� �������. ����� �� ���� ��������� � ��������� ���� ����������� ����� �����������.

�������� ���� �������� ������ �� ����������� ��������. �� ������� ���� ��������� �������� ��������� �����, � �� ����� ��������� ���� ��������� �������� ��������� ������, � �������� ����������� ������. ����� �������� ���� �������� ������ � �������� ����������� ������� ������. ����������� �������� ���� �������� ������������ �������� ��������� ���� ����� ����������.

���. 11. ����������� ����� ���� ��������

�������� ���������������� ���� ��������

  1. �� ������ ������������� ������� ������������� ������ ���� � ������ ������������ ������� ������������� ����� ��������:

    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.

  2. �� ����� ���� �������� ����������� ������ x1, xi, xn ... �������������� ��������� �������� ������� ���� (������� ������ � ������� ��������� ����� ����):

    , j=0...m-1

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

    yj(2) = yj(1), j = 0...m-1

  3. ����������� ����� ��������� �������� ������� ����:

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

    ������������ ������� f ����� ��� ������, ������ �������� b ������ ���� ���������� �������, ����� ����� ��������� �������� ��������� �� ��������� � ���������.

  4. �����������, ���������� �� ������ �������� ������� ���� �� ��������� ��������. ���� �� - ������� � ���� 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.

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

��� AjBj - ������� � �������� ������� ���������� ���������.

������� ������� ����������� ��� ����� ������������ ���� ��������� ����� ���������� ���������.

������� � �������� ������ ����� ��������� � ����������. ��� ����� ���������� �� ��������� � ���������, ������� �� �������� ������������. ��������, ��� ��������������� ������������� ������ ���������� ��������� ��� ����� ��������� ����� ����.

������� ����������. ������������� ������, ������������� �������.

����������. ������� ��������������� ������������� ������ ������ ����������. ���� n - ���������� �������� �� ������� ����, �� ����� ��������, ������� ����� ���� ��������� � ���� �� ��������� L=n/2log2n. ���, ���� n=1024, �� ���� �������� ��������� �� ����� 25 �������.

��������������� ������������� ������ ����� ��������� ����������������� � �������� ����������������, ��������� ��������� ������.

������������

  • �� ��������� � ����������������� ������� (��������, ����� ��������), ��������������� ������������� ������ ���� ����������� ������� ���������� ����� ��������� A � B, ��� � ����� ������ ����� ������ �����������. �� ���� ����� ������������ ������������������� ������ ����� ����� ������� ����� ����������, ��� ����������������� ������.
  • ��������������� ������������� ������ - ������� ����, ������� ����� ���� ����������� � ���� ��������� ���� ��� ��������������� ��������.
  • ������� ������������ ������������� ����� ������� � �������. ���� ������ �������� � �������� ����������������.
  • ������� � ���� ����� ���� ��� �����������, ��� � �����������. ��� ����� ������� �������� ������������ ����.

���� ���������� ����������� ������

����������� �������� ����������� � ����������� � �������� 80-� ��. ��������� ���������� ���������������� ��������, ����������� �������� ������� ������, �������� ��������� �������� � �������������� ������ � ������� �������.

���� ���������� ����������� ������ ������� �� ���� ��������������� ����� ��������, ������������� ����� ������� � �������� ������. ������ ������� ����� ������ ���� ��������� ����������� ��������� ����� �� ������ ����, ������� ������������ � ������� ����, ����� ������ �� ��������� ����. ��� ������� "��������" ����� ������ � ������ ������ ��� ���������� ������� ��������� �������.

���� ��������������� ������������ � ������������� �������������, ��� �� ����� ���������� ��������� ����������� ����������. ������� ������������ ������� ����������� �������� �� ������� ����������������. ���� ��������� ���������� ���� �� ������� ������� ������ ���������� ����������� ��������� ����.

���� ART-1 ��������� �������� �������������, ����� ������� �� �������� "����������������� ������". ������ ����� ��������� ������ ������� ������ ��������� �������� ������� ��������. ��������� ������� ������ ������������ � �������� ������� ��������. �������, ��� ������� ������ "������������ �� �������" � ����������� ������� ��������, ���� ���������� �� ������� ������� �������� ������ ������. � ��������� ������ ������ ������� ������ - ������� ������� ��������. ���� ������� ����������� ��� ���� ��������� ������� ��������. ����� �������, ����� ��������� ������ � �������� ������� � ������� ��� �� �������� ������, ��� � �� ������������ ������������� ����������, ������������ ��� ��������� ������� �������� � �������� �������.

�������� ����� ���� ART-1 ������ �� ���� ��������. � ������� ���������������� ������ ����������� ������������ ������� �������� � �������� ���������. ������������ �������� ������������ ����������� � ������� ����������� ������ �������� ��������.

���� ART-1 ���������� �� ���� �������� ��������� ������� �� �������� �������� � �������, ����� ���� ���� ����������� ��������� �������� ������ � ������������ ��������� ������������ � ��������� ������������ ������������ �������� ������� � �������� ���������, ��� ���� ������� �������� "����������������� ������".

���. 13. �������� ���������� �������������� ���������/����������

�������� ���������������� ����

  1. ������������� ����:

    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 ����������, ��������� ������ ������� ������ ��������� � ����� �� ����������� ��������, ����� ��� ��������� ��������. ������� � ������� �������� ������ ������� ����� ������� ����������.

    ��� ��������� ��������� ������ ������� ������ � �������, ����, ���� ��� ������ �����������, ��������� �������������� � ������ ��������.

  2. ������������ ���� ������ ��������� �������� �������:

    ������� ������� ������������� ��������� ���� �������� ���������� ���� ��������.

  3. ���������� �������� ������������:

    �������� ������������ ����������� ����������� ��� ���� ��������, ���������� � ����, ���������� ���� ��������.

  4. ����� ������� � ���������� �������������:

    yj=max(yj)

    ��� �������� ����������� � ������� ������������ ����������.

  5. ��������� � �������:

    ;

    ���� ������� � ���� 7, ����� � ���� 6.

    �� ���� ���� ����������� ��������� ���������� ������������ �������� ������� � ������� � ���������� ��������� ������������ � ����� ��������� ��� �������� �������. �������� ��������� ������������ � �������, ��������� �� ������ ����.

    ���� �������� ��������� ������ ������, �� ������� ������ ��������� ������� ��������� ����������� �������� ������������. � ���� ������ ������� �������������� ����� ���������� �������� AND (���������� "�"). ����� ������� �������� �������� �� ���������� ���� + ������� ������.

    ���� �������� ��������� ������ ������, �� ���������, ��� ������� ������ ���������� �� ���� �������� � ��������������� ��� ����� �������. � ���� �������� ������, ���������� ������ �������, � ����������� �������� ������������� �����.

  6. ���������� ������� � ���������� ��������� ������������:

    ����� ������� � ���������� ��������� ������������ �������� ��������������� ������ ���� � ����� �� ��������� ������� � ���� 4.

  7. ��������� ������� � ���������� ��������� ������������:

    vij(t+1)=vij(t)xj

  8. ��������� ���� ����������� �� ���� 6 ��������. ����������� � ���� 2.

������� ������� � ���� ������ ��������.

����������� ����� � ������ ���������� ��� ����������� ���������� ������ ������������� �������������� �������, �� ������� ������������ ��������� ����, ��� ���������� ���������� - ���������������� �������������.

������� ���� ��������� � ������ �������� ������� ���� � ����� ������������� � �������� ���������������� ����.

������� ����������. ������������� �������, ���������� ������.

����������. �������������� ���������� ����� �������� � �������� ���������������� ����. � ���������� ���� ��������� ������������ ��������, ��������� � ���������������� ������ ����� ��������.

������������. �������� ��� �������.

�����������. ���������� ������ ART-2 � ����������� ���������� �������� ���������.