ΠΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΡΠΉ ΠΏΡΠΎΡΠ΅ΡΡ ΠΈ Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΡΠ΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ
![ΠΠΎΠ½ΡΡΠΎΠ»ΡΠ½Π°Ρ: ΠΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΡΠΉ ΠΏΡΠΎΡΠ΅ΡΡ ΠΈ Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΡΠ΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ](https://niscu.ru/work/1702427/cover.png)
ΠΠ±ΡΡΠ½ΠΎ ΠΏΠΎΡΡΡΠΎΠ΅Π½ΠΈΠ΅ ΡΠΈΡΠ»Π΅Π½Π½ΠΎΠ³ΠΎ ΠΌΠ΅ΡΠΎΠ΄Π° ΡΠ°Π·Π±ΠΈΠ²Π°ΡΡ Π½Π° Π΄Π²Π° ΡΡΠ°ΠΏΠ°: ΡΠΎΡΠΌΡΠ»ΠΈΡΠΎΠ²ΠΊΡ Π΄ΠΈΡΠΊΡΠ΅ΡΠ½ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ ΠΈ ΡΠ°Π·ΡΠ°Π±ΠΎΡΠΊΠ° Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°, ΠΏΠΎΠ·Π²ΠΎΠ»ΡΡΡΠ΅Π³ΠΎ ΠΎΡΡΡΠΊΠ°ΡΡ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ Π΄ΠΈΡΠΊΡΠ΅ΡΠ½ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ. Π ΡΡΠΎΠΌ ΡΠ»ΡΡΠ°Π΅ Π³ΠΎΠ²ΠΎΡΡΡ, ΡΡΠΎ ΠΏΡΠΎΠΈΠ·ΠΎΡΠ»Π° Π΄ΠΈΡΠΊΡΠ΅ΡΠΈΠ·Π°ΡΠΈΡ ΠΈΡΡ ΠΎΠ΄Π½ΠΎΠΉ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ. ΠΠ°ΠΏΡΠΈΠΌΠ΅Ρ, Π·Π°ΠΌΠ΅Π½Π° ΡΠΈΡΡΠ΅ΠΌΡ Π΄ΠΈΡΡΠ΅ΡΠ΅Π½ΡΠΈΠ°Π»ΡΠ½ΡΡ ΡΡΠ°Π²Π½Π΅Π½ΠΈΠΉ ΡΠ°Π·Π½ΠΎΡΡΠ½ΡΠΌΠΈ Π°Π»Π³Π΅Π±ΡΠ°ΠΈΡΠ΅ΡΠΊΠΈΠΌΠΈ ΡΡΠ°Π²Π½Π΅Π½ΠΈΡΠΌΠΈ. Π―ΡΠ½ΠΎ, ΡΡΠΎ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ Π΄ΠΈΡΠΊΡΠ΅ΡΠ½ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ… Π§ΠΈΡΠ°ΡΡ Π΅ΡΡ >
ΠΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΡΠΉ ΠΏΡΠΎΡΠ΅ΡΡ ΠΈ Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΡΠ΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ (ΡΠ΅ΡΠ΅ΡΠ°Ρ, ΠΊΡΡΡΠΎΠ²Π°Ρ, Π΄ΠΈΠΏΠ»ΠΎΠΌ, ΠΊΠΎΠ½ΡΡΠΎΠ»ΡΠ½Π°Ρ)
Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΡΠΉ ΠΏΡΠΎΡΠ΅ΡΡ ΠΈ Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΡΠ΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ
Π‘ΠΎΠ΄Π΅ΡΠΆΠ°Π½ΠΈΠ΅ ΠΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΡΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΡΡΠ΅ΠΊΡΠΈΠ²Π½ΠΎΡΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² ΠΈ ΠΎΡΠ΅Π½ΠΊΠ° ΠΈΡ Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΠΎΠΉ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΠΈ ΠΠΎΠ΄Π΅Π»Ρ Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΠΎΠ³ΠΎ ΠΏΡΠΎΡΠ΅ΡΡΠ° ΠΠ»Π°ΡΡΠΈΡΠΈΠΊΠ°ΡΠΈΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² ΠΏΠΎ Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΠΎΠΉ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΠΈ Π‘ΡΡΠ°ΡΠ΅Π³ΠΈΡ Π΄ΡΠ±Π»ΠΈΡΠΎΠ²Π°Π½ΠΈΡ (ΡΠ°ΡΡΠ΅ΠΏΠ»Π΅Π½ΠΈΡ). ΠΡΠΈΠ½ΡΠΈΠΏ «ΡΠ°Π·Π΄Π΅Π»ΡΠΉ ΠΈ Π²Π»Π°ΡΡΠ²ΡΠΉ».
ΠΠ±ΡΠΈΠ΅ ΡΠ²ΠΎΠΉΡΡΠ²Π° Π±Π°Π·ΠΎΠ²ΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² ΡΠΈΡΡΠΎΠ²ΠΎΠΉ ΠΎΠ±ΡΠ°Π±ΠΎΡΠΊΠΈ ΡΠΈΠ³Π½Π°Π»ΠΎΠ² ΠΡΠΈΠΌΠ΅ΡΡ ΠΠΈΡΠ΅ΡΠ°ΡΡΡΠ°
ΠΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΡΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ
ΠΡΠΎΡΠ΅ΡΡ ΠΏΠΎΡΡΡΠΎΠ΅Π½ΠΈΡ Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΡΠΈΡΡΠΎΠ²ΠΎΠΉ ΠΎΠ±ΡΠ°Π±ΠΎΡΠΊΠΈ ΡΠΈΠ³Π½Π°Π»ΠΎΠ² Π²ΠΎ ΠΌΠ½ΠΎΠ³ΠΎΠΌ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΠ΅ΡΡΡ ΡΠΈΡΠ»Π΅Π½Π½ΡΠΌ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠΌ, ΠΏΠΎΠ΄ ΠΊΠΎΡΠΎΡΡΠΌ ΠΏΠΎΠ½ΠΈΠΌΠ°Π΅ΡΡΡ ΡΠ°ΠΊΠ°Ρ ΠΈΠ½ΡΠ΅ΡΠΏΡΠ΅ΡΠ°ΡΠΈΡ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΎΠΉ ΠΌΠΎΠ΄Π΅Π»ΠΈ, ΠΊΠΎΡΠΎΡΠ°Ρ Π΄ΠΎΡΡΡΠΏΠ½Π° Π΄Π»Ρ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΠΈ Π½Π° Π·Π°Π΄Π°Π½Π½ΡΡ ΡΡΠ΅Π΄ΡΡΠ²Π°Ρ ΠΎΠ±ΡΠ°Π±ΠΎΡΠΊΠΈ (ΠΠΠ, ΡΠΈΡΡΠΎΠ²ΡΠ΅ ΡΠΈΠ³Π½Π°Π»ΡΠ½ΡΠ΅ ΠΏΡΠΎΡΠ΅ΡΡΠΎΡΡ, ΠΊΠΎΠ½ΡΡΠΎΠ»Π»Π΅ΡΡ). ΠΡΠΈ ΠΏΠ΅ΡΠ΅Ρ ΠΎΠ΄Π΅ ΠΎΡ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΎΠΉ ΠΌΠΎΠ΄Π΅Π»ΠΈ ΠΊ ΡΠΈΡΠ»Π΅Π½Π½ΠΎΠΌΡ ΠΌΠ΅ΡΠΎΠ΄Ρ Π²ΠΎΠ·Π½ΠΈΠΊΠ°ΡΡ ΠΏΠΎΠ³ΡΠ΅ΡΠ½ΠΎΡΡΠΈ, Π½Π°Π·ΡΠ²Π°Π΅ΠΌΡΠ΅ ΠΏΠΎΠ³ΡΠ΅ΡΠ½ΠΎΡΡΡΡ ΠΌΠ΅ΡΠΎΠ΄Π°, ΡΠ²ΡΠ·Π°Π½Π½ΡΠ΅ Ρ ΡΠΎΡΠ½ΠΎΡΡΡΡ ΠΏΡΠΈΠ±Π»ΠΈΠΆΠ΅Π½ΠΈΡ. ΠΡΠ΄Π΅Π»ΡΡΡ ΠΏΠΎΠ³ΡΠ΅ΡΠ½ΠΎΡΡΡ Π΄ΠΈΡΠΊΡΠ΅ΡΠΈΠ·Π°ΡΠΈΠΈ ΠΈ ΠΏΠΎΠ³ΡΠ΅ΡΠ½ΠΎΡΡΡ ΠΎΠΊΡΡΠ³Π»Π΅Π½ΠΈΡ.
ΠΠ±ΡΡΠ½ΠΎ ΠΏΠΎΡΡΡΠΎΠ΅Π½ΠΈΠ΅ ΡΠΈΡΠ»Π΅Π½Π½ΠΎΠ³ΠΎ ΠΌΠ΅ΡΠΎΠ΄Π° ΡΠ°Π·Π±ΠΈΠ²Π°ΡΡ Π½Π° Π΄Π²Π° ΡΡΠ°ΠΏΠ°: ΡΠΎΡΠΌΡΠ»ΠΈΡΠΎΠ²ΠΊΡ Π΄ΠΈΡΠΊΡΠ΅ΡΠ½ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ ΠΈ ΡΠ°Π·ΡΠ°Π±ΠΎΡΠΊΠ° Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°, ΠΏΠΎΠ·Π²ΠΎΠ»ΡΡΡΠ΅Π³ΠΎ ΠΎΡΡΡΠΊΠ°ΡΡ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ Π΄ΠΈΡΠΊΡΠ΅ΡΠ½ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ. Π ΡΡΠΎΠΌ ΡΠ»ΡΡΠ°Π΅ Π³ΠΎΠ²ΠΎΡΡΡ, ΡΡΠΎ ΠΏΡΠΎΠΈΠ·ΠΎΡΠ»Π° Π΄ΠΈΡΠΊΡΠ΅ΡΠΈΠ·Π°ΡΠΈΡ ΠΈΡΡ ΠΎΠ΄Π½ΠΎΠΉ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ. ΠΠ°ΠΏΡΠΈΠΌΠ΅Ρ, Π·Π°ΠΌΠ΅Π½Π° ΡΠΈΡΡΠ΅ΠΌΡ Π΄ΠΈΡΡΠ΅ΡΠ΅Π½ΡΠΈΠ°Π»ΡΠ½ΡΡ ΡΡΠ°Π²Π½Π΅Π½ΠΈΠΉ ΡΠ°Π·Π½ΠΎΡΡΠ½ΡΠΌΠΈ Π°Π»Π³Π΅Π±ΡΠ°ΠΈΡΠ΅ΡΠΊΠΈΠΌΠΈ ΡΡΠ°Π²Π½Π΅Π½ΠΈΡΠΌΠΈ. Π―ΡΠ½ΠΎ, ΡΡΠΎ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ Π΄ΠΈΡΠΊΡΠ΅ΡΠ½ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ ΠΎΡΠ»ΠΈΡΠ°Π΅ΡΡΡ ΠΎΡ ΠΈΡΡ ΠΎΠ΄Π½ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ. Π Π°Π·Π½ΠΎΡΡΡ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠΈΡ ΡΠ΅ΡΠ΅Π½ΠΈΠΉ ΠΈ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΠΏΠΎΠ³ΡΠ΅ΡΠ½ΠΎΡΡΡΡ Π΄ΠΈΡΠΊΡΠ΅ΡΠΈΠ·Π°ΡΠΈΠΈ.
ΠΡ ΠΎΠ΄Π½ΡΠ΅ Π΄Π°Π½Π½ΡΠ΅ ΠΏΡΠΈ ΡΠΈΡΡΠΎΠ²ΠΎΠΉ ΠΎΠ±ΡΠ°Π±ΠΎΡΠΊΠΈ ΡΠ°ΡΡΠΎ Π·Π°Π΄Π°ΡΡΡΡ Π½Π΅ ΡΠΎΡΠ½ΠΎ, Π° Ρ ΠΎΠΊΡΡΠ³Π»Π΅Π½ΠΈΠ΅ΠΌ. Π ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΠ΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ Π±ΡΠ΄Π΅Ρ ΠΎΡΠ»ΠΈΡΠ°ΡΡΡΡ ΠΎΡ ΡΠ΅ΡΠ΅Π½ΠΈΡ Π΄ΠΈΡΠΊΡΠ΅ΡΠΈΠ·ΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ. Π Π΅Π·ΡΠ»ΡΡΠΈΡΡΡΡΠ°Ρ ΠΏΠΎΠ³ΡΠ΅ΡΠ½ΠΎΡΡΡ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΠΏΠΎΠ³ΡΠ΅ΡΠ½ΠΎΡΡΡΡ ΠΎΠΊΡΡΠ³Π»Π΅Π½ΠΈΡ. ΠΠ΅Π»ΠΈΡΠΈΠ½Π° ΡΡΠΎΠΉ ΠΏΠΎΠ³ΡΠ΅ΡΠ½ΠΎΡΡΠΈ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΠ΅ΡΡΡ Π΄Π²ΡΠΌΡ ΡΠ°ΠΊΡΠΎΡΠ°ΠΌΠΈ: ΡΠΎΡΠ½ΠΎΡΡΡ. ΠΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½ΠΈΡ Π²Π΅ΡΠ΅ΡΡΠ²Π΅Π½Π½ΡΡ (ΠΊΠΎΠΌΠΏΠ»Π΅ΠΊΡΠ½ΡΡ ) ΡΠΈΡΠ΅Π» ΠΈ ΡΡΠ²ΡΡΠ²ΠΈΡΠ΅Π»ΡΠ½ΠΎΡΡΡΡ Π΄Π°Π½Π½ΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΠΊ ΠΏΠΎΠ³ΡΠ΅ΡΠ½ΠΎΡΡΡΠΌ ΠΎΠΊΡΡΠ³Π»Π΅Π½ΠΈΡ.
Π’ΡΠ΅Π±ΠΎΠ²Π°Π½ΠΈΡ ΠΊ Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΡΠΌ ΠΌΠ΅ΡΠΎΠ΄Π°ΠΌ. ΠΠΎΠΆΠ½ΠΎ Π²ΡΠ΄Π΅Π»ΠΈΡΡ Π΄Π²Π΅ Π³ΡΡΠΏΠΏΡ ΡΡΠ΅Π±ΠΎΠ²Π°Π½ΠΈΠΉ ΠΊ ΡΠΈΡΠ»Π΅Π½Π½ΡΠΌ ΠΌΠ΅ΡΠΎΠ΄Π°ΠΌ. ΠΠ΅ΡΠ²Π°Ρ Π³ΡΡΠΏΠΏΠ° ΡΠ²ΡΠ·Π°Π½Π° Ρ Π°Π΄Π΅ΠΊΠ²Π°ΡΠ½ΠΎΡΡΡΡ Π΄ΠΈΡΠΊΡΠ΅ΡΠ½ΠΎΠΉ ΠΌΠΎΠ΄Π΅Π»ΠΈ ΠΈΡΡ ΠΎΠ΄Π½ΠΎΠΉ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΎΠΉ Π·Π°Π΄Π°ΡΠ΅, Π²ΡΠΎΡΠ°Ρ Π³ΡΡΠΏΠΏΠ° — Ρ ΡΠ΅Π°Π»ΠΈΠ·ΡΠ΅ΠΌΠΎΡΡΡΡ ΡΠΈΡΠ»Π΅Π½Π½ΠΎΠ³ΠΎ ΠΌΠ΅ΡΠΎΠ΄Π° Π½Π° ΡΡΠ΅Π΄ΡΡΠ²Π°Ρ ΡΠΈΡΡΠΎΠ²ΠΎΠΉ ΠΎΠ±ΡΠ°Π±ΠΎΡΠΊΠΈ. ΠΡΠ½ΠΎΠ²Π½ΡΠΌ ΠΏΡΠ΅ΠΏΡΡΡΡΠ²ΠΈΠ΅ΠΌ Π΄Π»Ρ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΠΈ ΠΊΠΎΡΡΠ΅ΠΊΡΠ½ΠΎ ΠΏΠΎΡΡΠ°Π²Π»Π΅Π½Π½ΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΎΠ³ΡΠ°Π½ΠΈΡΠ΅Π½Π½ΡΠΉ ΠΎΠ±ΡΠ΅ΠΌ Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΠΎΠΉ ΠΏΠ°ΠΌΡΡΠΈ, ΠΎΠ³ΡΠ°Π½ΠΈΡΠ΅Π½Π½ΡΠ΅ ΡΠ΅ΡΡΡΡΡ Π²ΡΠ΅ΠΌΠ΅Π½ΠΈ ΡΡΠ΅ΡΠ°. Π Π΅Π°Π»ΡΠ½ΡΠ΅ Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΡΠ΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ Π΄ΠΎΠ»ΠΆΠ½Ρ ΡΡΠΈΡΡΠ²Π°ΡΡ ΡΡΠΈ ΠΎΠ±ΡΡΠΎΡΡΠ΅Π»ΡΡΡΠ²Π°, Ρ. Π΅. ΠΎΠ½ΠΈ Π΄ΠΎΠ»ΠΆΠ½Ρ Π±ΡΡΡ ΡΠΊΠΎΠ½ΠΎΠΌΠΈΡΠ½ΡΠΌΠΈ ΠΊΠ°ΠΊ ΠΏΠΎ ΡΠΈΡΠ»Ρ Π°ΡΠΈΡΠΌΠ΅ΡΠΈΡΠ΅ΡΠΊΠΈΡ Π΄Π΅ΠΉΡΡΠ²ΠΈΠΉ, ΡΠ°ΠΊ ΠΈ ΠΏΠΎ ΡΡΠ΅Π±ΡΠ΅ΠΌΠΎΠΌΡ ΠΎΠ±ΡΠ΅ΠΌΡ ΠΏΠ°ΠΌΡΡΠΈ.
ΠΡΡΠ΅ΠΊΡΠΈΠ²Π½ΠΎΡΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² ΠΈ ΠΎΡΠ΅Π½ΠΊΠ° ΠΈΡ Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΠΎΠΉ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΠΈ
ΠΠΎΠΏΡΠΎΡΡ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΠΈ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² ΠΈ ΡΡΡΡΠΎΠΉΡΡΠ² ΡΠ²Π»ΡΡΡΡΡ ΠΎΡΠ½ΠΎΠ²ΠΎΠΏΠΎΠ»Π°Π³Π°ΡΡΠΈΠΌΠΈ Π² ΡΠΈΡΡΠΎΠ²ΠΎΠΉ ΠΎΠ±ΡΠ°Π±ΠΎΡΠΊΠΈ ΡΠΈΠ³Π½Π°Π»ΠΎΠ². ΠΠΎΠ½ΡΡΠΈΠ΅ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΠΈ ΠΈΠΌΠ΅Π΅Ρ ΡΠ»ΠΎΠΆΠ½ΡΡ ΠΈΡΡΠΎΡΠΈΡ ΡΠ°Π·Π²ΠΈΡΠΈΡ. ΠΠΎΠ½ΡΡΠΈΠ΅ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΠΈ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΡΠ°ΠΊΠΆΠ΅ Π΄ΠΎΠΏΡΡΠΊΠ°Π΅Ρ ΡΠ°Π·Π»ΠΈΡΠ½ΡΠ΅ ΡΡΠ°ΠΊΡΠΎΠ²ΠΊΠΈ. ΠΠΎΠ³ΡΡ ΡΡΠΈΡΡΠ²Π°ΡΡΡΡ ΠΈΠ»ΠΈ Π½Π΅ ΡΡΠΈΡΡΠ²Π°ΡΡΡΡ ΡΠ°ΠΊΠΈ ΡΠ°ΠΊΡΠΎΡΡ, ΠΊΠ°ΠΊ ΡΠ°Π·ΠΌΠ΅Ρ ΠΌΠ°ΡΠΈΠ½Π½ΠΎΠ³ΠΎ ΡΠ»ΠΎΠ²Π°, Π΅ΠΌΠΊΠΎΡΡΡ ΠΏΠ°ΠΌΡΡΠΈ, ΡΠ°Π·Π»ΠΈΡΠΈΠ΅ Π² Π΄Π»ΠΈΡΠ΅Π»ΡΠ½ΠΎΡΡΠΈ Π²ΡΠΏΠΎΠ»Π½ΡΠ΅ΠΌΡΡ ΠΊΠΎΠΌΠ°Π½Π΄ ΠΈ Ρ. Π΄.
ΠΠ·Π²Π΅ΡΡΠ΅Π½ ΡΡΠ΄ ΠΌΠΎΠ΄Π΅Π»Π΅ΠΉ Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΠΎΠ³ΠΎ ΠΏΡΠΎΡΠ΅ΡΡΠ°, ΠΏΠΎΠ·Π²ΠΎΠ»ΡΡΡΠΈΡ ΡΠ°ΡΠΊΡΡΡΡ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡ ΠΎΡΠ΄Π΅Π»ΡΠ½ΡΡ Π·Π°Π΄Π°Ρ ΠΈ ΡΡΠ°Π²Π½ΠΈΡΡ ΡΠ°Π·Π»ΠΈΡΠ½ΡΠ΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ.
ΠΠΎΠ΄Π΅Π»Ρ Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΠΎΠ³ΠΎ ΠΏΡΠΎΡΠ΅ΡΡΠ°
Π°Π»Π³ΠΎΡΠΈΡΠΌ Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΡΠΉ ΡΠΈΡΡΠΎΠ²ΠΎΠΉ ΡΠΈΠ³Π½Π°Π»
ΠΠ΅Π²Π΅ΡΠ²ΡΡΠ°ΡΡΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ° (ΠΠ). ΠΡΠ΅Π΄ΡΡΠ°Π²Π»ΡΠ΅Ρ ΡΠΎΠ±ΠΎΠΉ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ Π±Π΅Π· ΡΠΈΠΊΠ»ΠΎΠ², Π² ΠΊΠΎΡΠΎΡΠΎΠΉ ΡΠΈΠΊΠ» Π·Π°ΠΌΠ΅Π½ΡΠ΅ΡΡΡ ΠΊΠΎΠΏΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ΠΌ ΠΏΠΎΠ²ΡΠΎΡΡΡΡΠ΅ΠΉΡΡ ΠΊΠΎΠΌΠ°Π½Π΄Ρ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠ΅Π΅ ΡΠΈΡΠ»ΠΎ ΡΠ°Π·. Π§ΠΈΡΠ»ΠΎ ΡΠ°Π³ΠΎΠ² ΡΠ°ΠΊΠΎΠΉ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ ΠΊΠ°ΠΊ ΡΡΠ½ΠΊΡΠΈΠΈ Π²ΡΠ΅ΠΌΠ΅Π½ΠΈ ΠΎΡ ΡΠ°Π·ΠΌΠ΅ΡΠ° Π²Ρ ΠΎΠ΄Π° N Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΠΎΠΉ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡΡ, Π° ΡΠΈΡΠ»ΠΎ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ , ΡΡΠ°ΡΡΠ²ΡΡΡΠΈΡ Π² Π²ΡΡΠΈΡΠ»Π΅Π½ΠΈΡΡ — Π΅ΠΌΠΊΠΎΡΡΠ½ΠΎΠΉ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡΡ
ΠΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅. ΠΡΡΡΡ Π·Π°Π΄Π°Π½Ρ:
1) Π½Π°Π±ΠΎΡ Π²Ρ ΠΎΠ΄Π½ΡΡ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ
2) ΠΏΠΎΠ»Π΅ F (ΠΈΠ»ΠΈ ΠΊΠΎΠ»ΡΡΠΎ K);
3) ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π±Π°Π·ΠΈΡΠ½ΡΡ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΉ
Π³Π΄Π΅ — Π±ΠΈΠ½Π°ΡΠ½ΡΠ΅ Π°ΡΠΈΡΠΌΠ΅ΡΠΈΡΠ΅ΡΠΊΠΈΠ΅ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΈ,
— ΡΠ½Π°ΡΠ½Π°Ρ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΡ ΡΠΌΠ½ΠΎΠΆΠ΅Π½ΠΈΡ Π½Π° ΡΠ»Π΅ΠΌΠ΅Π½Ρ ΠΏΠΎΠ»Ρ (ΠΊΠΎΠ»ΡΡΠ°).
ΠΠ΅Π²Π΅ΡΠ²ΡΡΠ°ΡΡΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ° ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»ΡΠ΅Ρ ΡΠΎΠ±ΠΎΠΉ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎΡΡΡ ΡΡΡΠΎΠΊ (ΠΊΠΎΠΌΠ°Π½Π΄), l-Ρ ΠΈΠ· ΠΊΠΎΡΠΎΡΡΡ ΠΈΠΌΠ΅Π΅Ρ Π²ΠΈΠ΄
Π³Π΄Π΅
ΠΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅
1) Π΄Π»Ρ Π»ΡΠ±ΠΎΠΉ Π±Π°Π·ΠΈΡΠ½ΠΎΠΉ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΈ ΠΈΠ· ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° P ΡΠΈΠΊΡΠΈΡΡΠ΅ΡΡΡ ΡΠΈΡΠ»ΠΎ (f), Π½Π°Π·ΡΠ²Π°Π΅ΠΌΠΎΠ΅ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡΡ ΡΡΠΎΠΉ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΈ;
2) Π‘Π»ΠΎΠΆΠ½ΠΎΡΡΡΡ ΠΠ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΡΡΠΌΠΌΠ° Π²ΡΠ΅Ρ (f) ΠΏΠΎ Π²ΡΠ΅ΠΌ ΡΡΡΠΎΠΊΠ°ΠΌ ΡΡΠΎΠΉ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ;
3) ΠΡΡΡΡ (f) = 1, f P. Π’ΠΎΠ³Π΄Π° ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠ°Ρ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡ ΡΠ°Π²Π½Π° ΡΠΈΡΠ»Ρ Π²ΡΠ΅Ρ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΉ ΠΠ ΠΈ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΡΠΎΡΠ°Π»ΡΠ½ΠΎΠΉ (Ct);
4) ΠΡΡΡΡ (+) = 1, Π° Π΄Π»Ρ Π²ΡΠ΅Ρ ΠΎΡΡΠ°Π»ΡΠ½ΡΡ (f) = 0. Π‘ΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠ°Ρ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ Π°Π΄Π΄ΠΈΡΠΈΠ²Π½ΠΎΠΉ (Ca);
5) ΠΡΡΡΡ () = (/) = 1, Π° ΠΎΡΡΠ°Π»ΡΠ½ΡΠ΅ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΈ Π½Π΅ ΡΡΠΈΡΡΠ²Π°ΡΡΡΡ. Π‘Π»ΠΎΠΆΠ½ΠΎΡΡΡ ΡΠ°ΠΊΠΎΠ³ΠΎ ΡΠΎΠ΄Π° Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΠΌΡΠ»ΡΡΠΈΠΏΠ»ΠΈΠΊΠ°ΡΠΈΠ²Π½ΠΎΠΉ (Cm).
ΠΡΠΈΠΌΠ΅ΡΡ
1) ΡΠΎΡΠ°Π»ΡΠ½Π°Ρ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΡΡΡ ΠΏΡΠΈ Π°Π½Π°Π»ΠΈΠ·Π΅ ΠΌΠ°ΡΡΠΈΡΠ½ΡΡ ΠΏΡΠΎΡΠ΅ΡΡΠΎΠ², Π² ΠΊΠΎΡΠΎΡΡΡ Π²ΡΠ΅ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΈ ΠΎΡΠ΅Π½ΠΈΠ²Π°ΡΡΡΡ ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²ΠΎ;
2) Π°Π΄Π΄ΠΈΡΠΈΠ²Π½Π°Ρ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡ ΡΠ²Π»ΡΠ΅ΡΡΡ Ρ ΠΎΡΠΎΡΠΈΠΌ ΠΊΡΠΈΡΠ΅ΡΠΈΠ΅ΠΌ ΠΏΡΠΈ ΠΎΠ±ΡΠ°Π±ΠΎΡΠΊΠ΅ Π±ΠΈΠ½Π°ΡΠ½ΡΡ ΠΈΠ»ΠΈ ΡΡΠΎΠΈΡΠ½ΡΡ Π΄Π°Π½Π½ΡΡ , ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ ΠΊΠΎΡΠΎΡΡΡ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»ΡΡΡΡΡ Π² Π°Π»ΡΠ°Π²ΠΈΡΠ°Ρ {0,1}, {1,-1}, {1,0,-1}.
3) ΠΡΠ»ΡΡΠΈΠΏΠ»ΠΈΠΊΠ°ΡΠΈΠ²Π½Π°Ρ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΡΡΡ, ΠΊΠΎΠ³Π΄Π° ΠΎΠΏΠ΅ΡΠ°ΡΠΈΡ ΡΠΌΠ½ΠΎΠΆΠ΅Π½ΠΈΡ ΡΡΡΠ΅ΡΡΠ²Π΅Π½Π½ΠΎ ΠΌΠ΅Π΄Π»Π΅Π½Π½Π΅Π΅ (Π΄ΠΎΡΠΎΠΆΠ΅) ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΈ ΡΠ»ΠΎΠΆΠ΅Π½ΠΈΡ.
ΠΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ ΠΠ°ΡΠ΅ΡΡΠ²ΠΎ (ΡΡΡΠ΅ΠΊΡΠΈΠ²Π½ΠΎΡΡΡ) Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΠΎΡΠ΅Π½ΠΈΠ²Π°Π΅ΡΡΡ Π°ΡΠΈΠΌΠΏΡΠΎΡΠΈΡΠ΅ΡΠΊΠΎΠΉ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡΡ, Ρ. Π΅. ΠΏΠΎΡΡΠ΄ΠΊΠΎΠΌ ΡΠΎΡΡΠ° ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΠΈ ΠΊΠ°ΠΊ ΡΡΠ½ΠΊΡΠΈΠΈ ΠΎΡ ΡΠΈΡΠ»Π° Π²Ρ ΠΎΠ΄ΠΎΠ² N ΠΏΡΠΈ Π½Π΅ΠΎΠ³ΡΠ°Π½ΠΈΡΠ΅Π½Π½ΠΎΠΌ ΡΠΎΡΡΠ΅ N Π±Π΅Π· ΡΡΠ΅ΡΠ° ΠΌΡΠ»ΡΡΠΈΠΏΠ»ΠΈΠΊΠ°ΡΠΈΠ²Π½ΡΡ ΠΊΠΎΠ½ΡΡΠ°Π½Ρ.
ΠΠ°ΠΏΡΠΈΠΌΠ΅Ρ, Π΅ΡΠ»ΠΈ N Π²Ρ ΠΎΠ΄Π½ΡΡ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ ΠΎΠ±ΡΠ°Π±Π°ΡΡΠ²Π°ΡΡΡΡ Π·Π° Π²ΡΠ΅ΠΌΡ cN 2, Π³Π΄Π΅ c — Π½Π΅ΠΊΠΎΡΠΎΡΠ°Ρ ΠΏΠΎΡΡΠΎΡΠ½Π½Π°Ρ, ΡΠΎ Π°ΡΠΈΠΌΠΏΡΠΎΡΠΈΡΠ΅ΡΠΊΠ°Ρ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡ ΡΡΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° Π΅ΡΡΡ O (N 2), Π³ΠΎΠ²ΠΎΡΡΡ «ΠΏΠΎΡΡΠ΄ΠΊΠ° N 2».
ΠΠ»Π°ΡΡΠΈΡΠΈΠΊΠ°ΡΠΈΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² ΠΏΠΎ Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΠΎΠΉ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΠΈ
Π Π·Π°Π²ΠΈΡΠΈΠΌΠΎΡΡΠΈ ΠΎΡ ΠΏΠΎΡΡΠ΄ΠΊΠ° ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΠΈ ΠΈ Π²ΠΈΠ΄Π° ΡΠ΅Π·ΡΠ»ΡΡΠΈΡΡΡΡΠΈΡ Π΄Π°Π½Π½ΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ ΠΎΠ±ΡΠ°Π±ΠΎΡΠΊΠΈ ΠΌΠΎΠΆΠ½ΠΎ ΠΎΡΠ½Π΅ΡΡΠΈ ΠΊ ΡΠ΅ΡΡΡΠ΅ΠΌ ΡΡΠΎΠ²Π½ΡΠΌ.
1) ΠΊ ΠΏΠ΅ΡΠ²ΠΎΠΌΡ ΡΡΠΎΠ²Π½Ρ ΠΎΡΠ½ΠΎΡΡΡΡΡ Π±Π°Π·ΠΎΠ²ΡΠ΅ Π°ΡΠΈΡΠΌΠ΅ΡΠΈΡΠ΅ΡΠΊΠΈΠ΅ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΈ. Π‘ΡΠΈΡΠ°Π΅ΡΡΡ, ΡΡΠΎ ΠΈΡ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡ O (1), Ρ ΠΎΡΡ ΠΎΠ½ΠΈ ΠΎΡΠ»ΠΈΡΠ°ΡΡΡΡ ΠΏΠΎ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΠΈ Π±ΠΈΡΠΎΠ²ΡΡ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΉ. ΠΠ°ΠΏΡΠΈΠΌΠ΅Ρ, ΡΠΌΠ½ΠΎΠΆΠ΅Π½ΠΈΠ΅ Π΄Π²ΡΡ m — ΡΠ°Π·ΡΡΠ΄Π½ΡΡ ΡΠΈΡΠ΅Π» Ρ ΡΠΈΠΊΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠΉ ΡΠΎΡΠΊΠΎΠΉ ΡΡΠ΅Π±ΡΠ΅Ρ O (m 2) Π±ΠΈΡΠΎΠ²ΡΡ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΉ, Π° ΡΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅ — O (m);
2) ΠΊΠΎ Π²ΡΠΎΡΠΎΠΌΡ ΡΡΠΎΠ²Π½Ρ ΠΎΡΠ½ΠΎΡΡΡΡΡ ΡΠΊΠ°Π»ΡΡΠ½ΡΠ΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ Ρ Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΠΎΠΉ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡΡ O (N). ΠΡΠΎΡ ΡΡΠΎΠ²Π΅Π½Ρ Π²ΠΊΠ»ΡΡΠ°Π΅Ρ Π² ΡΠ΅Π±Ρ Π²ΡΡΠΈΡΠ»Π΅Π½ΠΈΠ΅ ΡΠΊΠ°Π»ΡΡΠ½ΠΎΠ³ΠΎ ΠΏΡΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΡ N — ΠΊΠΎΠΌΠΏΠΎΠ½Π΅Π½ΡΠ½ΡΡ Π²Π΅ΠΊΡΠΎΡΠΎΠ², Π²ΡΡΠΈΡΠ»Π΅Π½ΠΈΠ΅ Π·Π½Π°ΡΠ΅Π½ΠΈΡ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠ° ΠΏΠΎ ΡΡ Π΅ΠΌΠ΅ ΠΠΎΡΠ½Π΅ΡΠ°, ΡΠΈΠ»ΡΡΡΠ°ΡΠΈΡ Ρ ΠΠΠ₯ (Π² ΡΠ°ΡΡΠ½ΠΎΡΡΠΈ ΡΠΈΡΠ»Π΅Π½Π½ΠΎΠ΅ ΠΈΠ½ΡΠ΅Π³ΡΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΠΈ Π΄ΠΈΡΡΠ΅ΡΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅);
3) Π ΡΡΠ΅ΡΡΠ΅ΠΌΡ ΡΡΠΎΠ²Π½Ρ ΠΎΡΠ½ΠΎΡΡΡΡΡ Π²Π΅ΠΊΡΠΎΡΠ½ΡΠ΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΠΈ O (N 2). Π‘ΡΠ΄Π° Π²ΠΊΠ»ΡΡΠ°ΡΡΡΡ ΡΠΌΠ½ΠΎΠΆΠ΅Π½ΠΈΠ΅ ΠΌΠ°ΡΡΠΈΡΡ Π½Π° Π²Π΅ΠΊΡΠΎΡ Π΄Π»Ρ Π²ΡΡΠΈΡΠ»Π΅Π½ΠΈΡ Π»ΠΈΠ½Π΅ΠΉΠ½ΡΡ ΠΏΡΠ΅ΠΎΠ±ΡΠ°Π·ΠΎΠ²Π°Π½ΠΈΠΉ (Π€ΡΡΡΠ΅, ΠΠ°Π½ΠΊΠ΅Π»Ρ-Π’Π΅ΠΏΠ»ΠΈΡΠ° ΠΈ Π΄Ρ), Π²ΡΡΠΈΡΠ»Π΅Π½ΠΈΠ΅ ΡΠ²Π΅ΡΡΠΊΠΈ Π²Π΅ΠΊΡΠΎΡΠΎΠ² (ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠΎΠ²) (ΠΈΡ ΡΠΏΠ΅ΠΊΡΡΠΎΠ² ΠΈ ΠΊΠΎΡΡΠ΅Π»ΡΡΠΈΠΉ), ΡΠΈΠ»ΡΡΡΠ°ΡΠΈΡ Ρ ΠΠΠ₯ ΠΈ Ρ. Π΄. ΠΠ΅ΠΊΠΎΡΠΎΡΡΠ΅ ΠΈΠ· ΡΡΠΈΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² (Π΄Π»Ρ ΡΠ»ΡΡΠ°Ρ ΡΠΏΠ΅ΡΠΈΠ°Π»ΡΠ½ΡΡ ΠΌΠ°ΡΡΠΈΡ) ΠΌΠΎΠΆΠ½ΠΎ ΡΠ»ΡΡΡΠΈΡΡ Π΄ΠΎ ΠΎΡΠ΅Π½ΠΊΠΈ O (N log N).ΠΡΠΈΠΌΠ΅ΡΠΎΠΌ ΡΠ²Π»ΡΠ΅ΡΡΡ Π±ΡΡΡΡΠΎΠ΅ ΠΏΡΠ΅ΠΎΠ±ΡΠ°Π·ΠΎΠ²Π°Π½ΠΈΠ΅ Π€ΡΡΡΠ΅ (ΠΠΠ€).
4) ΠΠ»Π³ΠΎΡΠΈΡΠΌΡ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΠΈ O (N 3) ΡΠΎΡΡΠ°Π²Π»ΡΡΡ ΡΠ΅ΡΠ²Π΅ΡΡΡΠΉ ΡΡΠΎΠ²Π΅Π½Ρ. ΠΡΠΎ — ΠΌΠ°ΡΡΠΈΡΠ½ΠΎΠ΅ ΠΏΡΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠ΅, Π²ΡΡΠΈΡΠ»Π΅Π½ΠΈΠ΅ ΡΠΎΠ±ΡΡΠ²Π΅Π½Π½ΡΡ Π·Π½Π°ΡΠ΅Π½ΠΈΠΉ ΠΈ Π²Π΅ΠΊΡΠΎΡΠΎΠ², ΠΏΡΡΠΌΡΠ΅ ΠΌΠ΅ΡΠΎΠ΄Ρ ΡΠ΅ΡΠ΅Π½ΠΈΡ ΡΠΈΡΡΠ΅ΠΌ ΡΡΠ°Π²Π½Π΅Π½ΠΈΠΉ, ΡΠΈΠ½Π³ΡΠ»ΡΡΠ½ΠΎΠ΅ ΡΠ°Π·Π»ΠΎΠΆΠ΅Π½ΠΈΠ΅ ΠΈ ΠΎΠ±ΡΠ°ΡΠ΅Π½ΠΈΠ΅ ΠΌΠ°ΡΡΠΈΡΡ, ΡΠ°ΠΊΡΠΎΡΠΈΠ·Π°ΡΠΈΡ ΠΌΠ°ΡΡΠΈΡΡ, ΠΌΠ΅ΡΠΎΠ΄ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠΈΡ ΠΊΠ²Π°Π΄ΡΠ°ΡΠΎΠ², ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ Π·Π°Π΄Π°Ρ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΡ, Π½Π°Ρ ΠΎΠΆΠ΄Π΅Π½ΠΈΠ΅ ΠΏΡΡΠ΅ΠΉ Π² Π³ΡΠ°ΡΠ΅, ΡΠΈΠ»ΡΡΡΠ°ΡΠΈΡ ΠΏΠΎ ΠΠ°Π»ΠΌΠ°Π½Ρ ΠΈ Ρ. Π΄.
Π‘ΡΡΠ°ΡΠ΅Π³ΠΈΡ Π΄ΡΠ±Π»ΠΈΡΠΎΠ²Π°Π½ΠΈΡ (ΡΠ°ΡΡΠ΅ΠΏΠ»Π΅Π½ΠΈΡ). ΠΡΠΈΠ½ΡΠΈΠΏ «ΡΠ°Π·Π΄Π΅Π»ΡΠΉ ΠΈ Π²Π»Π°ΡΡΠ²ΡΠΉ»
ΠΡΠ±Π΅ΡΠ΅ΠΌ ΠΎΠ±ΡΠ΅ΠΌ Π·Π°Π΄Π°ΡΠΈ N Π² ΠΊΠ°ΡΠ΅ΡΡΠ²Π΅ ΠΏΠ°ΡΠ°ΠΌΠ΅ΡΡΠ° ΠΈ ΡΠ°Π·ΠΎΠ±ΡΠ΅ΠΌ Π·Π°Π΄Π°ΡΡ Π½Π° Π΄Π²Π΅ ΠΏΠΎΠ΄Π·Π°Π΄Π°ΡΠΈ ΠΎΠ±ΡΠ΅ΠΌΠ° (N / 2) ΡΠΎΠΉ ΠΆΠ΅ ΡΠ°ΠΌΠΎΠΉ ΡΡΡΡΠΊΡΡΡΡ, ΡΡΠΎ ΠΈ ΠΈΡΡ ΠΎΠ΄Π½Π°Ρ Π·Π°Π΄Π°ΡΠ°. ΠΡΠ»ΠΈ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ ΡΡΠΈΡ ΠΏΠΎΠ΄Π·Π°Π΄Π°Ρ ΠΌΠΎΠΆΠ½ΠΎ ΡΠΊΠΎΠΌΠ±ΠΈΠ½ΠΈΡΠΎΠ²Π°ΡΡ Π² ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ ΠΈΡΡ ΠΎΠ΄Π½ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ, ΡΠΎ ΠΏΠΎΠ»ΡΡΠ°Π΅ΡΡΡ ΡΡΡΠ΅ΠΊΡΠΈΠ²Π½ΡΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ.
Π‘ΡΡΠ°ΡΠ΅Π³ΠΈΡ Π΄ΡΠ±Π»ΠΈΡΠΎΠ²Π°Π½ΠΈΡ ΠΌΠΎΠΆΠ΅Ρ ΠΏΡΠΈΠΌΠ΅Π½ΡΡΡΡΡ ΠΏΡΠΈ Π»ΡΠ±ΠΎΠΌ N, ΡΠ°ΠΊ ΠΊΠ°ΠΊ Π»ΡΠ±ΠΎΠ΅ N ΠΌΠΎΠΆΠ½ΠΎ ΡΠ²Π΅Π»ΠΈΡΠΈΡΡ Π΄ΠΎ Π±Π»ΠΈΠΆΠ°ΠΉΡΠ΅Π³ΠΎ Π΄Π²ΠΎΠΈΡΠ½ΠΎ — ΡΠ°ΡΠΈΠΎΠ½Π°Π»ΡΠ½ΠΎΠ³ΠΎ Π·Π½Π°ΡΠ΅Π½ΠΈΡ (Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, Π΄ΠΎΠ±Π°Π²Π»Π΅Π½ΠΈΠ΅ΠΌ Π½ΡΠ»Π΅Π²ΡΡ ΠΊΠΎΠΎΡΠ΄ΠΈΠ½Π°Ρ Π²ΠΎ Π²Ρ ΠΎΠ΄Π½ΠΎΠΉ Π²Π΅ΠΊΡΠΎΡ Π΄Π°Π½Π½ΡΡ ).
ΠΠ±ΡΠΈΠ΅ ΡΠ²ΠΎΠΉΡΡΠ²Π° Π±Π°Π·ΠΎΠ²ΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² ΡΠΈΡΡΠΎΠ²ΠΎΠΉ ΠΎΠ±ΡΠ°Π±ΠΎΡΠΊΠΈ ΡΠΈΠ³Π½Π°Π»ΠΎΠ²
ΠΠ°Π΄Π°ΡΠ° ΡΠΈΡΡΠΎΠ²ΠΎΠΉ ΠΎΠ±ΡΠ°Π±ΠΎΡΠΊΠΈ ΡΠΈΠ³Π½Π°Π»ΠΎΠ² Π·Π°ΠΊΠ»ΡΡΠ°Π΅ΡΡΡ Π² ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠΈ Π½Π΅ΠΊΠΎΡΠΎΡΡΡ ΠΏΠ°ΡΠ°ΠΌΠ΅ΡΡΠΎΠ² ΡΠΈΠ³Π½Π°Π»ΠΎΠ² Π½Π° ΠΎΡΠ½ΠΎΠ²Π΅ Π°Π½Π°Π»ΠΈΠ·Π° ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎΡΡΠΈ Π·Π½Π°ΡΠ΅Π½ΠΈΠΉ (ΠΎΡΡΡΠ΅ΡΠΎΠ²) x[nT], Π³Π΄Π΅ n = 0,1,…, N — 1; T — ΠΈΠ½ΡΠ΅ΡΠ²Π°Π» Π΄ΠΈΡΠΊΡΠ΅ΡΠΈΠ·Π°ΡΠΈΠΈ ΡΠΈΠ³Π½Π°Π»Π°, ΠΏΡΠΈ n < 0, x = 0. Π Π±ΠΎΠ»ΡΡΠΈΠ½ΡΡΠ²Π΅ ΡΠ°Π΄ΠΈΠΎΡΠ΅Ρ Π½ΠΈΡΠ΅ΡΠΊΠΈΡ ΠΏΡΠΈΠΌΠ΅Π½Π΅Π½ΠΈΠΉ ΠΈΡΡΠ»Π΅Π΄ΡΠ΅ΠΌΡΠΉ ΡΠΈΠ³Π½Π°Π» Π³Π΅Π½Π΅ΡΠΈΡΡΠ΅ΡΡΡ ΠΈΠ»ΠΈ ΠΎΡΡΠ°ΠΆΠ°Π΅ΡΡΡ ΠΎΡ ΠΊΠ°ΠΊΠΎΠ³ΠΎ-Π»ΠΈΠ±ΠΎ ΠΎΠ±ΡΠ΅ΠΊΡΠ° (ΡΠ΅Π»ΠΈ). ΠΠ°ΠΏΡΠ°Π²Π»Π΅Π½ΠΈΠ΅, Ρ ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ ΠΏΡΠΈΡ ΠΎΠ΄ΠΈΡ ΡΡΠΎΡ ΡΠΈΠ³Π½Π°Π», ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΠ΅Ρ ΠΌΠ΅ΡΡΠΎΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅ ΠΎΠ±ΡΠ΅ΠΊΡΠ°. ΠΠ°Π΄Π΅ΡΠΆΠΊΠ° ΠΌΠ΅ΠΆΠ΄Ρ ΠΏΠΎΡΡΠ»ΠΊΠΎΠΉ ΡΠΈΠ³Π½Π°Π»Π° ΠΈ ΠΏΡΠΈΠ΅ΠΌΠΎΠΌ ΠΎΡΡΠ°ΠΆΠ΅Π½Π½ΠΎΠ³ΠΎ ΡΠΈΠ³Π½Π°Π»Π° ΠΏΠΎΠ·Π²ΠΎΠ»ΡΠ΅Ρ ΡΡΠ΄ΠΈΡΡ ΠΎ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠΈ Π΄ΠΎ ΠΎΠ±ΡΠ΅ΠΊΡΠ°, Π° ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ ΡΠ°ΡΡΠΎΡΡ — ΠΎ ΡΠΊΠΎΡΠΎΡΡΠΈ Π΅Π³ΠΎ Π΄Π²ΠΈΠΆΠ΅Π½ΠΈΡ. ΠΠ½ΠΎΠ³Π΄Π°, ΡΡΠΎΠ±Ρ ΠΏΠΎΠ»ΡΡΠΈΡΡ Π½ΡΠΆΠ½ΡΡ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΡ, Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ ΡΡΠ°Π²Π½ΠΈΡΡ ΠΏΠ°ΡΠ°ΠΌΠ΅ΡΡΡ ΡΠΈΠ³Π½Π°Π»Π° Ρ Π·Π°Π΄Π°Π½Π½ΡΠΌΠΈ ΠΈΠ»ΠΈ Π²ΡΡΠΈΡΠ»Π΅Π½Π½ΡΠΌΠΈ Π² ΠΏΡΠΎΡΠ΅ΡΡΠ΅ ΠΎΠ±ΡΠ°Π±ΠΎΡΠΊΠΈ Π²Π΅Π»ΠΈΡΠΈΠ½Π°ΠΌΠΈ (ΠΏΠΎΡΠΎΠ³Π°ΠΌΠΈ). ΠΠΎΠ»ΡΡΠΈΠ½ΡΡΠ²ΠΎ ΠΏΠ°ΡΠ°ΠΌΠ΅ΡΡΠΎΠ² ΡΠΈΠ³Π½Π°Π»Π° ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΠ΅ΡΡΡ Ρ ΠΏΠΎΠΌΠΎΡΡΡ Π²ΡΠ΄Π΅Π»Π΅Π½ΠΈΡ ΠΈΠ· Π½Π΅Π³ΠΎ ΡΠΎΡΡΠ°Π²Π»ΡΡΡΠΈΡ Ρ Π·Π°Π΄Π°Π½Π½ΡΠΌΠΈ Ρ Π°ΡΠ°ΠΊΡΠ΅ΡΠΈΡΡΠΈΠΊΠ°ΠΌΠΈ. ΠΡΠΎΡ ΠΏΡΠΎΡΠ΅ΡΡ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΡΠΈΠ»ΡΡΡΠ°ΡΠΈΠ΅ΠΉ.
Π‘ΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ ΡΡΠΈ ΠΎΡΠ½ΠΎΠ²Π½ΡΡ ΠΊΠ»Π°ΡΡΠ° Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² ΡΠΈΠ»ΡΡΡΠ°ΡΠΈΠΈ :
1. Π‘Π²Π΅ΡΡΠΊΠ°.
2. Π Π΅ΠΊΡΡΡΠΈΡ.
3. ΠΡΠ΅ΠΎΠ±ΡΠ°Π·ΠΎΠ²Π°Π½ΠΈΠ΅ Π€ΡΡΡΠ΅.
ΠΡΠΈ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ Π½Π°Π·ΡΠ²Π°ΡΡΡΡ Π±Π°Π·ΠΎΠ²ΡΠΌΠΈ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°ΠΌΠΈ ΠΎΠ±ΡΠ°Π±ΠΎΡΠΊΠΈ ΡΠΈΠ³Π½Π°Π»ΠΎΠ². ΠΠΎ Π²ΡΠ΅Ρ Π±Π°Π·ΠΎΠ²ΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°Ρ ΠΎΠ±ΡΠ°Π±ΠΎΡΠΊΠΈ ΡΠΈΠ³Π½Π°Π»ΠΎΠ² ΠΎΡΠ½ΠΎΠ²Π½ΡΠΌΠΈ Π°ΡΠΈΡΠΌΠ΅ΡΠΈΡΠ΅ΡΠΊΠΈΠΌΠΈ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΡΠΌΠΈ ΡΠ²Π»ΡΡΡΡΡ ΡΠΌΠ½ΠΎΠΆΠ΅Π½ΠΈΠ΅ ΠΈ ΡΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅ ΡΠΈΡΠ΅Π». ΠΡΠΈ ΡΡΠΎΠΌ Π² Π±ΠΎΠ»ΡΡΠΈΠ½ΡΡΠ²Π΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² ΡΡΠΈ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΈ ΡΠ²Π»ΡΡΡΡΡ ΡΠΎΡΡΠ°Π²Π»ΡΡΡΠΈΠΌΠΈ Π² ΡΠΊΠ°Π»ΡΡΠ½ΠΎΠΌ ΡΠΌΠ½ΠΎΠΆΠ΅Π½ΠΈΠΈ Π²Π΅ΠΊΡΠΎΡΠΎΠ² Π²ΠΈΠ΄Π°
.
Π’Π°ΠΊΡΡ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΡ ΠΈΠ½ΠΎΠ³Π΄Π° Π½Π°Π·ΡΠ²Π°ΡΡ Π±Π°Π·ΠΎΠ²ΠΎΠΉ ΠΌΠΈΠΊΡΠΎΠΎΠΏΠ΅ΡΠ°ΡΠΈΠ΅ΠΉ.
Π‘ΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ ΠΌΠ½ΠΎΠ³ΠΎ ΡΠ°Π·Π½ΡΡ ΡΠΏΠΎΡΠΎΠ±ΠΎΠ² ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΠΈ Π±Π°Π·ΠΎΠ²ΠΎΠΉ ΠΌΠΈΠΊΡΠΎΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΈ. Π Π°Π·Π½ΡΠ΅ ΡΠΏΠΎΡΠΎΠ±Ρ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡ ΡΠ°Π·Π½ΡΠΌ ΡΡ Π΅ΠΌΠ°ΠΌ ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΡ Π²ΡΡΠΈΡΠ»Π΅Π½ΠΈΠΉ Π²ΠΎ Π²ΡΠ΅ΠΌΠ΅Π½ΠΈ ΠΈ Π² ΠΏΡΠΎΡΡΡΠ°Π½ΡΡΠ²Π΅.
ΠΠ°Π·ΠΎΠ²ΡΠ΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ ΠΎΠ±ΡΠ°Π±ΠΎΡΠΊΠΈ ΡΠΈΠ³Π½Π°Π»ΠΎΠ² ΠΎΡΠ½ΠΎΡΡΡΡΡ ΠΊ ΡΠΈΠΏΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² Ρ ΠΈΠ½ΡΠ΅Π½ΡΠΈΠ²Π½ΡΠΌ Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΡΠΌ ΠΏΡΠΎΡΠ΅ΡΡΠΎΠΌ. ΠΡΠΎ ΠΎΠ·Π½Π°ΡΠ°Π΅Ρ, ΡΡΠΎ ΠΎΠ½ΠΈ Ρ Π°ΡΠ°ΠΊΡΠ΅ΡΠΈΠ·ΡΡΡΡΡ Π²ΡΡΠΎΠΊΠΈΠΌ ΠΎΡΠ½ΠΎΡΠ΅Π½ΠΈΠ΅ΠΌ ΡΠΈΡΠ»Π° Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΡΡ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΉ ΠΊ ΡΠΈΡΠ»Ρ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΉ Π²Π²ΠΎΠ΄Π° — Π²ΡΠ²ΠΎΠ΄Π°.
ΠΡΠΈΠΌΠ΅Ρ. Π£ΠΌΠ½ΠΎΠΆΠ΅Π½ΠΈΠ΅ ΠΌΠ°ΡΡΠΈΡΡ Π½Π° Π²Π΅ΠΊΡΠΎΡ. ΠΡΡΡΡ A — ΠΌΠ°ΡΡΠΈΡΠ° m n, Π° x — Π²Π΅ΠΊΡΠΎΡ Π΄Π»ΠΈΠ½Ρ n. Π’ΠΎΠ³Π΄Π°
Π³Π΄Π΅ aj — j — Ρ ΡΡΡΠΎΠΊΠ° ΠΌΠ°ΡΡΠΈΡΠ° A, Π° — ΡΠΊΠ°Π»ΡΡΠ½ΠΎΠ΅ ΠΏΡΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠ΅ Π²Π΅ΠΊΡΠΎΡΠΎΠ².
Π’Π°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, ΠΏΡΠΎΡΠ΅ΡΡ ΡΠΌΠ½ΠΎΠΆΠ΅Π½ΠΈΡ ΠΌΠ°ΡΡΠΈΡΡ Π½Π° Π²Π΅ΠΊΡΠΎΡ ΡΠ²ΠΎΠ΄ΠΈΡΡΡ ΠΊ Π²ΡΡΠΈΡΠ»Π΅Π½ΠΈΡ m ΡΠΊΠ°Π»ΡΡΠ½ΡΡ ΠΏΡΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠΉ.
ΠΡΠΈΠΌΠ΅Ρ. Π‘Π»ΠΎΠΆΠ΅Π½ΠΈΠ΅ ΡΠ΅Π»ΡΡ ΡΠΈΡΠ΅Π». ΠΡΡΡΡ Π½Π΅ΠΎΡΡΠΈΡΠ°ΡΠ΅Π»ΡΠ½ΡΠ΅ ΡΠ΅Π»ΡΠ΅ ΡΠΈΡΠ»Π° a ΠΈ b Π·Π°Π΄Π°Π½Ρ Π² ΡΠΈΡΡΠ΅ΠΌΠ΅ ΡΡΠΈΡΠ»Π΅Π½ΠΈΡ Ρ ΠΎΡΠ½ΠΎΠ²Π°Π½ΠΈΠ΅ΠΌ B:
a = (an — 1, an — 2, …, a0) B = an — 1 B n — 1 + an — 2 B n — 2 +… + a1 B 1 + a0 ,
b = (bn — 1, bn — 2, …, b0) B = bn — 1 B n — 1 + bn — 2 B n — 2 +… + b1 B 1 + b0 ,
Π³Π΄Π΅ 0 ai, bi < B. ΠΠ»Ρ ΡΠ΄ΠΎΠ±ΡΡΠ²Π° ΡΡΠΈΡΠ°Π΅ΠΌ, ΡΡΠΎ ΠΎΠ±Π° ΡΠΈΡΠ»Π° ΠΈΠΌΠ΅ΡΡ ΡΠ°Π²Π½ΡΡ Π΄Π»ΠΈΠ½Ρ, ΠΏΡΠΈ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎΡΡΠΈ ΡΡΠ°ΡΡΠΈΠ΅ ΡΠ°Π·ΡΡΠ΄Ρ ΠΌΠ΅Π½ΡΡΠ΅Π³ΠΎ ΡΠΈΡΠ»Π° Π·Π°ΠΏΠΎΠ»Π½ΡΠ΅ΠΌ Π½ΡΠ»ΡΠΌΠΈ.
ΠΠ»Π³ΠΎΡΠΈΡΠΌ. Π‘Π»ΠΎΠΆΠ΅Π½ΠΈΠ΅ ΡΠ΅Π»ΡΡ ΡΠΈΡΠ΅Π».
ΠΡ ΠΎΠ΄. Π¦Π΅Π»ΡΠ΅ ΡΠΈΡΠ»Π° a = (an — 1, an — 2, …, a0) B, b = (bn — 1, bn — 2, …, b0) B .
ΠΡΡ ΠΎΠ΄. Π‘ΡΠΌΠΌΠ° Ρ = a + b = (cn, cn — 1, …, c0) B .
1. ΠΠΎΠ»ΠΎΠΆΠΈΡΡ s 0.
2. ΠΠ»Ρ i = 0, 1, …, n — 1 Π²ΡΠΏΠΎΠ»Π½ΠΈΡΡ ΡΠ»Π΅Π΄ΡΡΡΠΈΠ΅ Π΄Π΅ΠΉΡΡΠ²ΠΈΡ.
2.1. ΠΡΡΠΈΡΠ»ΠΈΡΡ t ai + bi + s.
2.2. ΠΠΎΠ»ΠΎΠΆΠΈΡΡ,
3. ΠΠΎΠ»ΠΎΠΆΠΈΡΡ cn s.
4. Π Π΅Π·ΡΠ»ΡΡΠ°Ρ: Ρ = (cn, cn — 1, …, c0) B.
ΠΠ΅ΡΠ΅ΠΌΠ΅Π½Π½Π°Ρ s ΠΎΠ·Π½Π°ΡΠ°Π΅Ρ ΠΏΠ΅ΡΠ΅Π½ΠΎΡ Π² ΡΡΠ°ΡΡΠΈΠΉ ΡΠ°Π·ΡΡΠ΄. Π‘Π»ΠΎΠΆΠ½ΠΎΡΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΡΠ°Π²Π½Π° (n).
ΠΡΠΈΠΌΠ΅Ρ. Π£ΠΌΠ½ΠΎΠΆΠ΅Π½ΠΈΠ΅ ΡΠ΅Π»ΡΡ ΡΠΈΡΠ΅Π».
ΠΠ»Π³ΠΎΡΠΈΡΠΌ. Π£ΠΌΠ½ΠΎΠΆΠ΅Π½ΠΈΠ΅ ΡΠ΅Π»ΡΡ ΡΠΈΡΠ΅Π» «Π² ΡΡΠΎΠ»Π±ΠΈΠΊ».
ΠΡ ΠΎΠ΄. Π¦Π΅Π»ΡΠ΅ ΡΠΈΡΠ»Π° a = (an — 1, an — 2, …, a0) B, b = (bn — 1, bn — 2, …, b0) B, 0
ΠΡΡ ΠΎΠ΄. ΠΡΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠ΅ c = a b = (c2n — 1, c2n — 2, …, c0) B.
1. ΠΠ»Ρ i = 0,1,…, n — 1 ΠΏΠΎΠ»ΠΎΠΆΠΈΡΡ ci 0.
2. ΠΠ»Ρ i = 0,1,…, n — 1 Π²ΡΠΏΠΎΠ»Π½ΠΈΡΡ ΡΠ»Π΅Π΄ΡΡΡΠΈΠ΅ Π΄Π΅ΠΉΡΡΠ²ΠΈΡ.
2.1. ΠΠ»Ρ j = 0,1,…, n — 1:
2.1.1. ΠΠΎΠ»ΠΎΠΆΠΈΡΡ s 0.
2.1.2. ΠΡΡΠΈΡΠ»ΠΈΡΡ t ci+j + aibj + s, ci+j t (modB), /
2.2. ΠΠΎΠ»ΠΎΠΆΠΈΡΡ ci+n s.
3. Π Π΅Π·ΡΠ»ΡΡΠ°Ρ: Ρ = (cn, cn — 1, …, c0) B.
ΠΠΎ Π²Π½Π΅ΡΠ½Π΅ΠΌ ΡΠΈΠΊΠ»Π΅ ΡΡΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° Π²ΡΡΠΈΡΠ»ΡΡΡΡΡ ΡΠ°ΡΡΠΈΡΠ½ΡΠ΅ ΠΏΡΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΡ
ai (bn — 1, bn — 2, …, b0) B,
Π° Π²ΠΎ Π²Π½ΡΡΡΠ΅Π½Π½Π΅ΠΌ — ΠΏΡΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΡ aibj.
Π‘Π»ΠΎΠΆΠ½ΠΎΡΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΡΠ°Π²Π½Π° (n2).
ΠΡΠΈΠΌΠ΅Ρ. ΠΡΡΠΈΡΠ»Π΅Π½ΠΈΠ΅ Π½Π°ΠΈΠ±ΠΎΠ»ΡΡΠ΅Π³ΠΎ ΠΎΠ±ΡΠ΅Π³ΠΎ Π΄Π΅Π»ΠΈΡΠ΅Π»Ρ. ΠΠ»Ρ Π²ΡΡΠΈΡΠ»Π΅Π½ΠΈΡ Π½Π°ΠΈΠ±ΠΎΠ»ΡΡΠ΅Π³ΠΎ ΠΎΠ±ΡΠ΅Π³ΠΎ Π΄Π΅Π»ΠΈΡΠ΅Π»Ρ (ΠΠΠ) ΠΏΡΠΈΠΌΠ΅Π½ΡΠ΅ΡΡΡ ΡΠΏΠΎΡΠΎΠ± ΠΏΠΎΠ²ΡΠΎΡΠ½ΠΎΠ³ΠΎ Π΄Π΅Π»Π΅Π½ΠΈΡ Ρ ΠΎΡΡΠ°ΡΠΊΠΎΠΌ, Π½Π°Π·ΡΠ²Π°Π΅ΠΌΡΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠΌ ΠΠ²ΠΊΠ»ΠΈΠ΄Π° ΠΠ»Π³ΠΎΡΠΈΡΠΌ. ΠΡΡΠΈΡΠ»Π΅Π½ΠΈΠ΅ ΠΠΠ ΠΏΠΎ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ ΠΠ²ΠΊΠ»ΠΈΠ΄Π°.
ΠΡ ΠΎΠ΄. Π¦Π΅Π»ΡΠ΅ ΡΠΈΡΠ»Π° a, b; 0< b a.
ΠΡΡ ΠΎΠ΄. Π§ΠΈΡΠ»ΠΎ d = ΠΠΠ (a, b).
1. ΠΠΎΠ»ΠΎΠΆΠΈΡΡ r0 a, ri b, i 1.
2. ΠΠ°ΠΉΡΠΈ ΠΎΡΡΠ°ΡΠΎΠΊ ri+1 ΠΎΡ Π΄Π΅Π»Π΅Π½ΠΈΡ ri-1 Π½Π° ri.
3. ΠΡΠ»ΠΈ ri+1 = 0Π± ΡΠΎ ΠΏΠΎΠ»ΠΎΠΆΠΈΡΡ d ri. Π ΠΏΡΠΎΡΠΈΠ²Π½ΠΎΠΌ ΡΠ»ΡΡΠ°Π΅ ΠΏΠΎΠ»ΠΎΠΆΠΈΡΡ ii+1 ΠΈ Π²Π΅ΡΠ½ΡΡΡΡΡ Π½Π° ΡΠ°Π³ 2.
4. Π Π΅Π·ΡΠ»ΡΡΠ°Ρ: d.
Π‘Π»ΠΎΠΆΠ½ΠΎΡΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΠΠ²ΠΊΠ»ΠΈΠ΄Π° ΡΠ°Π²Π½Π° (log2a).
ΠΡΠΈΠΌΠ΅Ρ. Π£ΠΌΠ½ΠΎΠΆΠ΅Π½ΠΈΠ΅ Π² ΠΊΠ»Π°ΡΡΠ°Ρ Π²ΡΡΠ΅ΡΠΎΠ². ΠΠ»Π³ΠΎΡΠΈΡΠΌ, ΠΏΡΠ΅Π΄Π»ΠΎΠΆΠ΅Π½Π½ΡΠΉ Π. Π¨Π΅Π½Ρ Π°Π³Π΅, ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅Ρ ΠΊΠΈΡΠ°ΠΉΡΠΊΡΡ ΡΠ΅ΠΎΡΠ΅ΠΌΡ ΠΎΠ± ΠΎΡΡΠ°ΡΠΊΠ°Ρ .
Π’Π΅ΠΎΡΠ΅ΠΌΠ°. ΠΡΠ»ΠΈ ΡΠ΅Π»ΡΠ΅ ΡΠΈΡΠ»Π° m0, m1, …, mk-1 ΠΏΠΎΠΏΠ°ΡΠ½ΠΎ Π²Π·Π°ΠΈΠΌΠ½ΠΎ ΠΏΡΠΎΡΡΡ, ΡΠΎ ΠΊΠ°ΠΆΠ΄ΠΎΠΌΡ ΡΠ΅Π»ΠΎΠΌΡ ΡΠΈΡΠ»Ρ a, 0 a < M, Π³Π΄Π΅ M = m0 m1 … mk-1, Π΅Π΄ΠΈΠ½ΡΡΠ²Π΅Π½Π½ΡΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ ΠΌΠΎΠΆΠ½ΠΎ ΡΠΎΠΏΠΎΡΡΠ°Π²ΠΈΡΡ Π½Π°Π±ΠΎΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² a0, a1, …, ak-1 ΠΊΠ»Π°ΡΡΠΎΠ² Π²ΡΡΠ΅ΡΠΎΠ² ΠΏΠΎ ΠΌΠΎΠ΄ΡΠ»ΡΠΌ mi, Π³Π΄Π΅ ai a (mod mi), 0 i < k .
Π‘ΡΠΌΠΌΠ΅, ΡΠ°Π·Π½ΠΎΡΡΠΈ ΠΈ ΠΏΡΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΡ ΡΠΈΡΠ΅Π» ΠΏΠΎ ΠΌΠΎΠ΄ΡΠ»Ρ M ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡ ΡΡΠΌΠΌΡ, ΡΠ°Π·Π½ΠΎΡΡΠΈ ΠΈ ΠΏΡΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΡ ΠΏΠΎ ΠΌΠΎΠ΄ΡΠ»ΡΠΌ mi.
ΠΡΠ»ΠΈ a = (a0, a1, …, ak-1), b = (b0, b1, …, bk-1), ΡΠΎ
a + b (mod M) = (c0, c1, …, ck-1);
a — b (mod M) = (d0, d1, …, dk-1);
a b (mod M) = (e0, e1, …, ek-1);
Π³Π΄Π΅
ci= ai + bi (mod mi);
di= ai — bi (mod mi);
ei= ai bi (mod mi);
i = 0, 1, …, k — 1.
ΠΠ°ΠΈΠ±ΠΎΠ»Π΅Π΅ ΡΡΡΠ΄ΠΎΠ΅ΠΌΠΊΠΎΠΉ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠ΅ΠΉ ΠΏΡΠΈ Π²ΡΡΠΈΡΠ»Π΅Π½ΠΈΡΡ Π² ΠΊΠ»Π°ΡΡΠ°Ρ Π²ΡΡΠ΅ΡΠΎΠ² ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½ΠΈΠ΅ ΡΠΈΡΠ»Π° Π² ΠΊΠ»Π°ΡΡΠ°Ρ Π²ΡΡΠ΅ΡΠΎΠ² ΠΈ ΠΎΠ±ΡΠ°ΡΠ½ΠΎΠ΅ Π²ΠΎΡΡΡΠ°Π½ΠΎΠ²Π»Π΅Π½ΠΈΠ΅ ΠΏΠΎ ΠΊΠΈΡΠ°ΠΉΡΠΊΠΎΠΉ ΡΠ΅ΠΎΡΠ΅ΠΌΠ΅ ΠΎΠ± ΠΎΡΡΠ°ΡΠΊΠ°Ρ .
ΠΡΠΈΠΌΠΏΠΎΡΠΈΡΠ΅ΡΠΊΠ°Ρ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΡΠΌΠ½ΠΎΠΆΠ΅Π½ΠΈΡ ΡΠΈΡΠ΅Π» Π² ΠΊΠ»Π°ΡΡΠ°Ρ Π²ΡΡΠ΅ΡΠΎΠ² ΡΠ°Π²Π½Π° (k logk). ΠΡΠ°ΠΊΡΠΈΡΠ΅ΡΠΊΠΈ Π΄Π°Π½Π½ΡΠΉ ΠΌΠ΅ΡΠΎΠ΄ ΡΠΌΠ½ΠΎΠΆΠ΅Π½ΠΈΡ ΡΡΡΠ΅ΠΊΡΠΈΠ²Π½Π΅Π΅, ΡΠ΅ΠΌ ΡΠΌΠ½ΠΎΠΆΠ΅Π½ΠΈΠ΅ «Π² ΡΡΠΎΠ»Π±ΠΈΠΊ», Π»ΠΈΡΡ ΡΠΎΠ³Π΄Π°, ΠΊΠΎΠ³Π΄Π° Π΄Π»ΠΈΠ½Π° ΡΠΎΠΌΠ½ΠΎΠΆΠΈΡΠ΅Π»Π΅ΠΉ ΠΏΡΠ΅Π²ΡΡΠ°Π΅Ρ ΡΠ°Π·ΡΡΠ΄Π½ΠΎΡΡΡ ΠΏΡΠΎΡΠ΅ΡΡΠΎΡΠ° Π² Π΄Π΅ΡΡΡΠΊΠΈ ΡΠ°Π·.
ΠΠ°ΠΌΠ΅ΡΠΈΠΌ, ΡΡΠΎ Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ Π±ΡΡΡΡΡΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΡΠΌΠ½ΠΎΠΆΠ΅Π½ΠΈΡ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅Ρ Π±ΡΡΡΡΠΎΠ΅ ΠΏΡΠ΅ΠΎΠ±ΡΠ°Π·ΠΎΠ²Π°Π½ΠΈΠ΅ Π€ΡΡΡΠ΅.
1. ΠΠΎΡΠ΅Π² Π. Π. ΠΠΈΠΊΡΠΎΠΏΡΠΎΡΠ΅ΡΡΠΎΡΠ½ΡΠ΅ ΡΡΡΡΠΎΠΉΡΡΠ²Π° ΠΎΠ±ΡΠ°Π±ΠΎΡΠΊΠΈ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΈ. ΠΠ»Π³ΠΎΡΠΈΡΠΌΡ ΡΠΈΡΡΠΎΠ²ΠΎΠΉ ΠΎΠ±ΡΠ°Π±ΠΎΡΠΊΠΈ: Π£ΡΠ΅Π±. ΠΏΠΎΡΠΎΠ±ΠΈΠ΅ Π΄Π»Ρ Π²ΡΠ·ΠΎΠ². — ΠΠ½.: ΠΡΡ. ΡΠΊ., 1990. 132 Ρ.
2. ΠΡ ΠΎ Π., Π₯ΠΎΠΏΠΊΡΠΎΡΡ ΠΠΆ., Π£Π»ΡΠΌΠ°Π½ ΠΠΆ. ΠΠΎΡΡΡΠΎΠ΅Π½ΠΈΠ΅ ΠΈ Π°Π½Π°Π»ΠΈΠ· Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ².- Π.: ΠΠΈΡ, 1979.
3. Π‘Π°ΠΌΡΠΎΠ½ΠΎΠ² Π. Π., ΠΠ»ΠΎΡ ΠΎΠ² Π. Π., Π€ΠΈΠ»ΠΎΠ½Π΅Π½ΠΊΠΎ Π. Π. ΠΠΎΠΌΠΏΡΡΡΠ΅ΡΠ½Π°Ρ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΠΊΠ° (ΠΎΡΠ½ΠΎΠ²Π°Π½ΠΈΠ΅ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΊΠΈ).- Π ΠΎΡΡΠΎΠ² Π½Π° ΠΠΎΠ½Ρ: «Π€Π΅Π½ΠΈΠΊΡ», 2002. — 512 Ρ.