ΠΠ½ΠΎΠ³ΠΎΠΏΡΠΈΠ·Π½Π°ΠΊΠΎΠ²ΡΠ΅ ΠΎΠ±ΡΠ΅ΠΊΡΡ Ai, i=1,…, n ΠΎΠ±ΡΡΠ½ΠΎ ΠΏΡΠΈΠ½ΡΡΠΎ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»ΡΡΡ ΠΊΠ°ΠΊ Π²Π΅ΠΊΡΠΎΡΡ ΠΈΠ»ΠΈ ΠΊΠΎΡΡΠ΅ΠΆΠΈ qi=(qi1e1,…, qimem) Π² ΠΏΡΠΎΡΡΡΠ°Π½ΡΡΠ²Π΅.
Q=Q1…Qm,.
Π³Π΄Π΅ Qs={qses} - Π½Π΅ΠΏΡΠ΅ΡΡΠ²Π½Π°Ρ ΠΈΠ»ΠΈ Π΄ΠΈΡΠΊΡΠ΅ΡΠ½Π°Ρ ΡΠΊΠ°Π»Π° s-Π³ΠΎ ΠΏΡΠΈΠ·Π½Π°ΠΊΠ°, es=1hs, s=1,…, m. Π‘ΠΈΡΡΠ°ΡΠΈΡ ΡΡΡΠ΅ΡΡΠ²Π΅Π½Π½ΡΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ ΡΡΠ»ΠΎΠΆΠ½ΡΠ΅ΡΡΡ, Π΅ΡΠ»ΠΈ ΠΎΠ΄Π½ΠΎΠΌΡ ΠΈ ΡΠΎΠΌΡ ΠΆΠ΅ ΠΎΠ±ΡΠ΅ΠΊΡΡ Ai ΠΌΠΎΠΆΠ΅Ρ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΠΎΠ²Π°ΡΡ Π½Π΅ ΠΎΠ΄ΠΈΠ½, Π° Π½Π΅ΡΠΊΠΎΠ»ΡΠΊΠΎ m-ΠΌΠ΅ΡΠ½ΡΡ
Π²Π΅ΠΊΡΠΎΡΠΎΠ² Ρ ΡΠ°Π·Π»ΠΈΡΠ°ΡΡΠΈΠΌΠΈΡΡ Π·Π½Π°ΡΠ΅Π½ΠΈΡΠΌΠΈ ΠΏΡΠΈΠ·Π½Π°ΠΊΠΎΠ². ΠΠΎΠ΄ΠΎΠ±Π½ΡΠ΅ ΡΠΈΡΡΠ°ΡΠΈΠΈ Π²ΠΎΠ·Π½ΠΈΠΊΠ°ΡΡ, Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, ΠΊΠΎΠ³Π΄Π° ΠΎΠ±ΡΠ΅ΠΊΡ Ai ΠΎΡΠ΅Π½ΠΈΠ²Π°Π΅ΡΡΡ k Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΡΠΌΠΈ ΡΠΊΡΠΏΠ΅ΡΡΠ°ΠΌΠΈ ΠΏΠΎ m ΠΊΡΠΈΡΠ΅ΡΠΈΡΠΌ, ΠΈΠ»ΠΈ ΠΊΠΎΠ³Π΄Π° Π½Π΅ΠΎΠ±Ρ
ΠΎΠ΄ΠΈΠΌΠΎ ΠΎΠ΄Π½ΠΎΠ²ΡΠ΅ΠΌΠ΅Π½Π½ΠΎ ΡΡΠ΅ΡΡΡ m ΠΏΠ°ΡΠ°ΠΌΠ΅ΡΡΠΎΠ² ΠΎΠ±ΡΠ΅ΠΊΡΠ° Ai, ΠΈΠ·ΠΌΠ΅ΡΠ΅Π½Π½ΡΡ
k ΡΠ°Π·Π»ΠΈΡΠ½ΡΠΌΠΈ ΡΠΏΠΎΡΠΎΠ±Π°ΠΌΠΈ. Π ΡΠ°ΠΊΠΈΡ
ΡΠ»ΡΡΠ°ΡΡ
ΠΎΠ±ΡΠ΅ΠΊΡ Ai ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»ΡΠ΅ΡΡΡ Π² m-ΠΌΠ΅ΡΠ½ΠΎΠΌ ΠΏΡΠΎΡΡΡΠ°Π½ΡΡΠ²Π΅ Q ΡΠΆΠ΅ Π½Π΅ ΠΎΠ΄Π½ΠΈΠΌ Π²Π΅ΠΊΡΠΎΡΠΎΠΌ qi, Π° Π³ΡΡΠΏΠΏΠΎΠΉ, ΡΠΎΡΡΠΎΡΡΠ΅ΠΉ ΠΈΠ· k Π²Π΅ΠΊΡΠΎΡΠΎΠ² {qi(1),…, qi(k)} Π²ΠΈΠ΄Π° qi(j)=(qi1e1(j),…, qimem (j)), j=1,…, k, ΠΊΠΎΡΠΎΡΠ°Ρ Π΄ΠΎΠ»ΠΆΠ½Π° ΡΠ°ΡΡΠΌΠ°ΡΡΠΈΠ²Π°ΡΡΡΡ ΠΊΠ°ΠΊ Π΅Π΄ΠΈΠ½ΠΎΠ΅ ΡΠ΅Π»ΠΎΠ΅. ΠΡΠΈ ΡΡΠΎΠΌ, ΠΎΡΠ΅Π²ΠΈΠ΄Π½ΠΎ, ΠΈΠ·ΠΌΠ΅ΡΠ΅Π½Π½ΡΠ΅ ΡΠ°Π·Π½ΡΠΌΠΈ ΡΠΏΠΎΡΠΎΠ±Π°ΠΌΠΈ Π·Π½Π°ΡΠ΅Π½ΠΈΡ ΠΏΠ°ΡΠ°ΠΌΠ΅ΡΡΠΎΠ², ΠΊΠ°ΠΊ ΠΈ ΠΈΠ½Π΄ΠΈΠ²ΠΈΠ΄ΡΠ°Π»ΡΠ½ΡΠ΅ ΠΎΡΠ΅Π½ΠΊΠΈ, Π΄Π°Π½Π½ΡΠ΅ ΡΠΊΡΠΏΠ΅ΡΡΠ°ΠΌΠΈ, ΠΌΠΎΠ³ΡΡ Π±ΡΡΡ ΠΏΠΎΡ
ΠΎΠΆΠΈΠΌΠΈ, ΡΠ°Π·Π»ΠΈΡΠ°ΡΡΠΈΠΌΠΈΡΡ ΠΈ Π΄Π°ΠΆΠ΅ ΠΏΡΠΎΡΠΈΠ²ΠΎΡΠ΅ΡΠΈΠ²ΡΠΌΠΈ, ΡΡΠΎ Π² ΡΠ²ΠΎΡ ΠΎΡΠ΅ΡΠ΅Π΄Ρ ΠΌΠΎΠΆΠ΅Ρ ΠΏΡΠΈΠ²ΠΎΠ΄ΠΈΡΡ ΠΊ Π½Π΅ΡΡΠ°Π²Π½ΠΈΠΌΠΎΡΡΠΈ m-ΠΌΠ΅ΡΠ½ΡΡ
Π²Π΅ΠΊΡΠΎΡΠΎΠ² qi(j), Ρ
Π°ΡΠ°ΠΊΡΠ΅ΡΠΈΠ·ΡΡΡΠΈΡ
ΠΎΠ΄ΠΈΠ½ ΠΈ ΡΠΎΡ ΠΆΠ΅ ΠΎΠ±ΡΠ΅ΠΊΡ Ai.
Π‘ΠΎΠ²ΠΎΠΊΡΠΏΠ½ΠΎΡΡΡ ΡΠ°ΠΊΠΈΡ
«ΡΠΎΡΡΠ°Π²Π½ΡΡ
» ΠΎΠ±ΡΠ΅ΠΊΡΠΎΠ² ΠΌΠΎΠΆΠ΅Ρ ΠΈΠΌΠ΅ΡΡ Π² ΠΏΡΠΎΡΡΡΠ°Π½ΡΡΠ²Π΅ Q ΡΠ»ΠΎΠΆΠ½ΡΡ ΡΡΡΡΠΊΡΡΡΡ, Π΄ΠΎΡΡΠ°ΡΠΎΡΠ½ΠΎ ΡΡΡΠ΄Π½ΡΡ Π΄Π»Ρ Π°Π½Π°Π»ΠΈΠ·Π°. ΠΠ΅ΠΏΡΠΎΡΡΠΎ Π²Π²Π΅ΡΡΠΈ Π² ΡΡΠΎΠΌ ΠΏΡΠΎΡΡΡΠ°Π½ΡΡΠ²Π΅ ΠΈ ΠΌΠ΅ΡΡΠΈΠΊΡ Π΄Π»Ρ ΠΈΠ·ΠΌΠ΅ΡΠ΅Π½ΠΈΡ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠΉ ΠΌΠ΅ΠΆΠ΄Ρ ΠΎΠ±ΡΠ΅ΠΊΡΠ°ΠΌΠΈ. Π£ΠΊΠ°Π·Π°Π½Π½ΡΠ΅ ΡΡΡΠ΄Π½ΠΎΡΡΠΈ ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡΠ΅ΠΎΠ΄ΠΎΠ»Π΅ΡΡ, Π΅ΡΠ»ΠΈ Π²ΠΎΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡΡΡ ΠΈΠ½ΡΠΌ ΡΠΏΠΎΡΠΎΠ±ΠΎΠΌ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½ΠΈΡ ΠΌΠ½ΠΎΠ³ΠΎΠΏΡΠΈΠ·Π½Π°ΠΊΠΎΠ²ΡΡ
ΠΎΠ±ΡΠ΅ΠΊΡΠΎΠ², ΠΎΡΠ½ΠΎΠ²Π°Π½Π½ΡΠΌ Π½Π° ΡΠΎΡΠΌΠ°Π»ΠΈΠ·ΠΌΠ΅ ΠΌΡΠ»ΡΡΠΈΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ² [ΠΠ΅ΡΡΠΎΠ²ΡΠΊΠΈΠΉ, 2003], ΠΊΠΎΡΠΎΡΡΠΉ ΠΏΠΎΠ·Π²ΠΎΠ»ΡΠ΅Ρ ΠΎΠ΄Π½ΠΎΠ²ΡΠ΅ΠΌΠ΅Π½Π½ΠΎ ΡΡΠ΅ΡΡΡ ΡΠ°Π·Π»ΠΈΡΠ½ΡΠ΅ ΠΊΠΎΠΌΠ±ΠΈΠ½Π°ΡΠΈΠΈ Π·Π½Π°ΡΠ΅Π½ΠΈΠΉ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Π΅Π½Π½ΡΡ
ΠΈ ΠΊΠ°ΡΠ΅ΡΡΠ²Π΅Π½Π½ΡΡ
ΠΏΡΠΈΠ·Π½Π°ΠΊΠΎΠ², Π° ΡΠ°ΠΊΠΆΠ΅ ΠΈΡ
ΠΌΠ½ΠΎΠ³ΠΎΠ·Π½Π°ΡΠ½ΠΎΡΡΡ. ΠΠ²Π΅Π΄Π΅ΠΌ Π²ΠΌΠ΅ΡΡΠΎ ΠΏΡΡΠΌΠΎΠ³ΠΎ ΠΏΡΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΡ m ΡΠΊΠ°Π» ΠΏΡΠΈΠ·Π½Π°ΠΊΠΎΠ² Q=Q1…Qm ΠΎΠ±ΠΎΠ±ΡΠ΅Π½Π½ΡΡ ΡΠΊΠ°Π»Ρ ΠΏΡΠΈΠ·Π½Π°ΠΊΠΎΠ² — ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ G=Q1…Qm, ΡΠΎΡΡΠΎΡΡΠ΅Π΅ ΠΈΠ· m Π³ΡΡΠΏΠΏ ΠΏΡΠΈΠ·Π½Π°ΠΊΠΎΠ², ΠΈ ΠΏΡΠ΅Π΄ΡΡΠ°Π²ΠΈΠΌ ΠΎΠ±ΡΠ΅ΠΊΡ Ai Π² ΡΠ°ΠΊΠΎΠΌ ΡΠΈΠΌΠ²ΠΎΠ»ΠΈΡΠ΅ΡΠΊΠΎΠΌ Π²ΠΈΠ΄Π΅:
Ai = {kAi(q11)?q11,…, kAi(q1h1)?q1h1,…, kAi(qm1)?qm1,…, kAi(qmhm)?qmhm}. (1).
Π³Π΄Π΅ ΡΠΈΡΠ»ΠΎ kAi(qses) ΡΠΊΠ°Π·ΡΠ²Π°Π΅Ρ, ΡΠΊΠΎΠ»ΡΠΊΠΎ ΡΠ°Π· ΠΏΡΠΈΠ·Π½Π°ΠΊ qsesQs Π²ΡΡΡΠ΅ΡΠ°Π΅ΡΡΡ Π² ΠΎΠΏΠΈΡΠ°Π½ΠΈΠΈ ΠΎΠ±ΡΠ΅ΠΊΡΠ° Ai, Π·Π½Π°ΠΊ? ΠΎΠ±ΠΎΠ·Π½Π°ΡΠ°Π΅Ρ ΠΊΡΠ°ΡΠ½ΠΎΡΡΡ Π²Ρ
ΠΎΠΆΠ΄Π΅Π½ΠΈΡ ΠΏΡΠΈΠ·Π½Π°ΠΊΠ° qses. ΠΠ°ΠΏΡΠΈΠΌΠ΅Ρ, ΠΏΡΠΈ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡΠΈΡΠ΅ΡΠΈΠ°Π»ΡΠ½ΠΎΠΉ ΠΎΡΠ΅Π½ΠΊΠ΅ ΠΎΠ±ΡΠ΅ΠΊΡΠ° Ai Π½Π΅ΡΠΊΠΎΠ»ΡΠΊΠΈΠΌΠΈ ΡΠΊΡΠΏΠ΅ΡΡΠ°ΠΌΠΈ ΡΠΈΡΠ»ΠΎ kAi(qses) ΡΠ°Π²Π½ΠΎ ΡΠΈΡΠ»Ρ ΡΠΊΡΠΏΠ΅ΡΡΠΎΠ², Π΄Π°Π²ΡΠΈΡ
ΠΎΠ±ΡΠ΅ΠΊΡΡ Ai ΠΎΡΠ΅Π½ΠΊΡ qses ΠΏΠΎ ΠΊΡΠΈΡΠ΅ΡΠΈΡ Qs. ΠΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ G Ρ
Π°ΡΠ°ΠΊΡΠ΅ΡΠΈΠ·ΡΠ΅Ρ ΡΠ²ΠΎΠΉΡΡΠ²Π° ΡΠΎΠ²ΠΎΠΊΡΠΏΠ½ΠΎΡΡΠΈ ΠΎΠ±ΡΠ΅ΠΊΡΠΎΠ² A={A1,…, An}. ΠΠ±ΡΠ΅ΠΊΡ Ai ΠΌΠΎΠΆΠ½ΠΎ Π·Π°ΠΏΠΈΡΠ°ΡΡ ΠΈ Π±ΠΎΠ»Π΅Π΅ ΠΊΠΎΠΌΠΏΠ°ΠΊΡΠ½ΠΎ ΠΊΠ°ΠΊ Ai={kAi(x1)?x1,…, kAi(xh)?xh}, ΠΎΠΏΡΠ΅Π΄Π΅Π»ΠΈΠ² ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° G={x1,…, xh} ΡΠ»Π΅Π΄ΡΡΡΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ:
x1=q11, x2=q12,…,=q1h1,.
=q21,…,=q2h2,…,.
=qm1,…,=qmhm,.
Π³Π΄Π΅ h=h1+…+hm. Π’Π°ΠΊΠ°Ρ Π·Π°ΠΏΠΈΡΡ ΠΎΠ±ΡΠ΅ΠΊΡΠ° Ai ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»ΡΠ΅Ρ Π΅Π³ΠΎ ΠΊΠ°ΠΊ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Ρ ΠΏΠΎΠ²ΡΠΎΡΡΡΡΠΈΠΌΠΈΡΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΠΌΠΈ xjG ΠΈΠ»ΠΈ ΠΌΡΠ»ΡΡΠΈΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ. Π€ΡΠ½ΠΊΡΠΈΡ ΡΠΈΡΠ»Π° ΡΠΊΠ·Π΅ΠΌΠΏΠ»ΡΡΠΎΠ² ΠΌΡΠ»ΡΡΠΈΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° kA:GZ+={0,1,2,…} ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΠ΅Ρ ΠΊΡΠ°ΡΠ½ΠΎΡΡΡ Π²Ρ
ΠΎΠΆΠ΄Π΅Π½ΠΈΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ° xiG Π² ΠΌΡΠ»ΡΡΠΈΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π.