Π ΠΎΡΠ½ΠΎΠ²Π΅ ΠΎΡΠ΅Π½ΠΊΠΈ Π»Π΅ΠΆΠΈΡ ΠΏΡΠΎΡΠ΅ΡΡ ΡΠΎΠΏΠΎΡΡΠ°Π²Π»Π΅Π½ΠΈΡ Π·Π½Π°ΡΠ΅Π½ΠΈΠΉ ΠΊΠ°ΡΠ΅ΡΡΠ²Π΅Π½Π½ΡΡ
ΠΈΠ»ΠΈ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Π΅Π½Π½ΡΡ
Ρ
Π°ΡΠ°ΠΊΡΠ΅ΡΠΈΡΡΠΈΠΊ ΠΈΡΡΠ»Π΅Π΄ΡΠ΅ΠΌΠΎΠΉ ΡΠΈΡΡΠ΅ΠΌΡ Π·Π½Π°ΡΠ΅Π½ΠΈΡΠΌ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠΈΡ
ΡΠΊΠ°Π». ΠΡΡΠ»Π΅Π΄ΠΎΠ²Π°Π½ΠΈΠ΅ Ρ
Π°ΡΠ°ΠΊΡΠ΅ΡΠΈΡΡΠΈΠΊ ΠΏΡΠΈΠ²Π΅Π»ΠΎ ΠΊ Π²ΡΠ²ΠΎΠ΄Ρ ΠΎ ΡΠΎΠΌ, ΡΡΠΎ Π²ΡΠ΅ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΡΠ΅ ΡΠΊΠ°Π»Ρ ΠΏΡΠΈΠ½Π°Π΄Π»Π΅ΠΆΠ°Ρ ΠΊ ΠΎΠ΄Π½ΠΎΠΌΡ ΠΈΠ· Π½Π΅ΡΠΊΠΎΠ»ΡΠΊΠΈΡ
ΡΠΈΠΏΠΎΠ², ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΠ΅ΠΌΡΡ
ΠΏΠ΅ΡΠ΅ΡΠ½Π΅ΠΌ Π΄ΠΎΠΏΡΡΡΠΈΠΌΡΡ
ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΉ Π½Π° ΡΡΠΈΡ
ΡΠΊΠ°Π»Π°Ρ
.
Π€ΠΎΡΠΌΠ°Π»ΡΠ½ΠΎ ΡΠΊΠ°Π»ΠΎΠΉ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΠΊΠΎΡΡΠ΅ΠΆ ΠΈΠ· ΡΡΠ΅Ρ
ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² , Π³Π΄Π΅ X ΡΠ΅Π°Π»ΡΠ½ΡΠΉ ΠΎΠ±ΡΠ΅ΠΊΡ, Y ΡΠΊΠ°Π»Π°, Ρ Π³ΠΎΠΌΠΎΠΌΠΎΡΡΠ½ΠΎΠ΅ ΠΎΡΠΎΠ±ΡΠ°ΠΆΠ΅Π½ΠΈΠ΅ X Π½Π° Π£.
Π ΡΠΎΠ²ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ ΡΠ΅ΠΎΡΠΈΠΈ ΠΈΠ·ΠΌΠ΅ΡΠ΅Π½ΠΈΠΉ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΎ:
X = {x1, Ρ
2, …, Ρ
i, …, Ρ
n, RΡ
}
ΡΠΌΠΏΠΈΡΠΈΡΠ΅ΡΠΊΠ°Ρ ΡΠΈΡΡΠ΅ΠΌΠ° Ρ ΠΎΡΠ½ΠΎΡΠ΅Π½ΠΈΠ΅ΠΌ, Π²ΠΊΠ»ΡΡΠ°ΡΡΠ°Ρ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ ΡΠ²ΠΎΠΉΡΡΠ² Ρ
i, Π½Π° ΠΊΠΎΡΠΎΡΡΡ
Π² ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΠΈΠΈ Ρ ΡΠ΅Π»ΡΠΌΠΈ ΠΈΠ·ΠΌΠ΅ΡΠ΅Π½ΠΈΡ Π·Π°Π΄Π°Π½ΠΎ Π½Π΅ΠΊΠΎΡΠΎΡΠΎΠ΅ ΠΎΡΠ½ΠΎΡΠ΅Π½ΠΈΠ΅ RΡ
. Π ΠΏΡΠΎΡΠ΅ΡΡΠ΅ ΠΈΠ·ΠΌΠ΅ΡΠ΅Π½ΠΈΡ Π½Π΅ΠΎΠ±Ρ
ΠΎΠ΄ΠΈΠΌΠΎ ΠΊΠ°ΠΆΠ΄ΠΎΠΌΡ ΡΠ²ΠΎΠΉΡΡΠ²Ρ Ρ
i € X ΠΏΠΎΡΡΠ°Π²ΠΈΡΡ Π² ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΠΈΠ΅ ΠΏΡΠΈΠ·Π½Π°ΠΊ ΠΈΠ»ΠΈ ΡΠΈΡΠ»ΠΎ, Π΅Π³ΠΎ Ρ
Π°ΡΠ°ΠΊΡΠ΅ΡΠΈΠ·ΡΡΡΠ΅Π΅. ΠΡΠ»ΠΈ, Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, ΡΠ΅Π»ΡΡ ΠΈΠ·ΠΌΠ΅ΡΠ΅Π½ΠΈΡ ΡΠ²Π»ΡΠ΅ΡΡΡ Π²ΡΠ±ΠΎΡ, ΡΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ Ρ
i ΡΠ°ΡΡΠΌΠ°ΡΡΠΈΠ²Π°ΡΡΡΡ ΠΊΠ°ΠΊ Π°Π»ΡΡΠ΅ΡΠ½Π°ΡΠΈΠ²Ρ, Π° ΠΎΡΠ½ΠΎΡΠ΅Π½ΠΈΠ΅ RΡ
Π΄ΠΎΠ»ΠΆΠ½ΠΎ ΠΏΠΎΠ·Π²ΠΎΠ»ΡΡΡ ΡΡΠ°Π²Π½ΠΈΠ²Π°ΡΡ ΡΡΠΈ Π°Π»ΡΡΠ΅ΡΠ½Π°ΡΠΈΠ²Ρ;
Π£={Ρ (Ρ
1), …, Ρ (Ρ
n), Ry}
Π·Π½Π°ΠΊΠΎΠ²Π°Ρ ΡΠΈΡΡΠ΅ΠΌΠ° Ρ ΠΎΡΠ½ΠΎΡΠ΅Π½ΠΈΠ΅ΠΌ, ΡΠ²Π»ΡΡΡΠ°ΡΡΡ ΠΎΡΠΎΠ±ΡΠ°ΠΆΠ΅Π½ΠΈΠ΅ΠΌ ΡΠΌΠΏΠΈΡΠΈΡΠ΅ΡΠΊΠΎΠΉ ΡΠΈΡΡΠ΅ΠΌΡ Π² Π²ΠΈΠ΄Π΅ Π½Π΅ΠΊΠΎΡΠΎΡΠΎΠΉ ΠΎΠ±ΡΠ°Π·Π½ΠΎΠΉ ΠΈΠ»ΠΈ ΡΠΈΡΠ»ΠΎΠ²ΠΎΠΉ ΡΠΈΡΡΠ΅ΠΌΡ, ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠ΅ΠΉ ΠΈΠ·ΠΌΠ΅ΡΡΠ΅ΠΌΠΎΠΉ ΡΠΌΠΏΠΈΡΠΈΡΠ΅ΡΠΊΠΎΠΉ ΡΠΈΡΡΠ΅ΠΌΠ΅;
Ρ Π Π€ — Π³ΠΎΠΌΠΎΠΌΠΎΡΡΠ½ΠΎΠ΅ ΠΎΡΠΎΠ±ΡΠ°ΠΆΠ΅Π½ΠΈΠ΅ X Π½Π° Π£, ΡΡΡΠ°Π½Π°Π²Π»ΠΈΠ²Π°ΡΡΠ΅Π΅ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΠΈΠ΅ ΠΌΠ΅ΠΆΠ΄Ρ Π₯ ΠΈ Π£ ΡΠ°ΠΊ, ΡΡΠΎ {Ρ (Ρ
1), …, Ρ (Ρ
n)} € Ry ΡΠΎΠ»ΡΠΊΠΎ ΡΠΎΠ³Π΄Π°, ΠΊΠΎΠ³Π΄Π° (Ρ
i, …, Ρ
n) € RΡ
.
Π’ΠΈΠΏ ΡΠΊΠ°Π»Ρ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΠ΅ΡΡΡ ΠΏΠΎ Π€ = {Ρ1, …, Ρm}, ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Ρ Π΄ΠΎΠΏΡΡΡΠΈΠΌΡΡ
ΠΏΡΠ΅ΠΎΠ±ΡΠ°Π·ΠΎΠ²Π°Π½ΠΈΠΉ Ρ
i > Ρi.
Π ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΠΈΠΈ Ρ ΠΏΡΠΈΠ²Π΅Π΄Π΅Π½Π½ΡΠΌΠΈ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΡΠΌΠΈ, ΠΎΡ
Π²Π°ΡΡΠ²Π°ΡΡΠΈΠΌΠΈ ΠΊΠ°ΠΊ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Π΅Π½Π½ΡΠ΅, ΡΠ°ΠΊ ΠΈ ΠΊΠ°ΡΠ΅ΡΡΠ²Π΅Π½Π½ΡΠ΅ ΡΠΊΠ°Π»Ρ, ΠΈΠ·ΠΌΠ΅ΡΠ΅Π½ΠΈΠ΅ ΡΠΌΠΏΠΈΡΠΈΡΠ΅ΡΠΊΠΎΠΉ ΡΠΈΡΡΠ΅ΠΌΡ X Ρ ΠΎΡΠ½ΠΎΡΠ΅Π½ΠΈΠ΅ΠΌ RΡ
ΡΠΎΡΡΠΎΠΈΡ Π² ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠΈ Π·Π½Π°ΠΊΠΎΠ²ΠΎΠΉ ΡΠΈΡΡΠ΅ΠΌΡ Π£ Ρ ΠΎΡΠ½ΠΎΡΠ΅Π½ΠΈΠ΅ΠΌ Ry, ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠ΅ΠΉ ΠΈΠ·ΠΌΠ΅ΡΡΠ΅ΠΌΠΎΠΉ ΡΠΈΡΡΠ΅ΠΌΠ΅. ΠΡΠ΅Π΄ΠΏΠΎΡΡΠ΅Π½ΠΈΡ RΡ
Π½Π° ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π΅ Π₯ Π§ Π₯ Π² ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΠ΅ ΠΈΠ·ΠΌΠ΅ΡΠ΅Π½ΠΈΡ ΠΏΠ΅ΡΠ΅Π²ΠΎΠ΄ΡΡΡΡ Π² Π·Π½Π°ΠΊΠΎΠ²ΡΠ΅ (Π² ΡΠΎΠΌ ΡΠΈΡΠ»Π΅ ΠΈ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Π΅Π½Π½ΡΠ΅) ΡΠΎΠΎΡΠ½ΠΎΡΠ΅Π½ΠΈΡ Ry Π½Π° ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π΅ Y Π§ Y.