ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΠΠ΅ΠΉΠΊΡΡΡΡ
Π 20 Π². Π·Π°Π΄Π°ΡΠΈ, ΡΠ²ΡΠ·Π°Π½Π½ΡΠ΅ Ρ Π³ΡΠ°ΡΠ°ΠΌΠΈ, Π½Π°ΡΠ°Π»ΠΈ Π²ΠΎΠ·Π½ΠΈΠΊΠ°ΡΡ Π½Π΅ ΡΠΎΠ»ΡΠΊΠΎ Π² ΡΠΈΠ·ΠΈΠΊΠ΅, Ρ ΠΈΠΌΠΈΠΈ, ΡΠ»Π΅ΠΊΡΡΠΎΡΠ΅Ρ Π½ΠΈΠΊΠ΅ Π±ΠΈΠΎΠ»ΠΎΠ³ΠΈΠΈ, ΡΠΊΠΎΠ½ΠΎΠΌΠΈΠΊΠ΅, ΡΠΎΡΠΈΠΎΠ»ΠΎΠ³ΠΈΠΈ ΠΈ Ρ. Π΄., Π½ΠΎ ΠΈ Π²Π½ΡΡΡΠΈ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΠΊΠΈ, Π² ΡΠ°ΠΊΠΈΡ ΡΠ°Π·Π΄Π΅Π»Π°Ρ , ΠΊΠ°ΠΊ ΡΠΎΠΏΠΎΠ»ΠΎΠ³ΠΈΡ, Π°Π»Π³Π΅Π±ΡΠ°, ΡΠ΅ΠΎΡΠΈΡ Π²Π΅ΡΠΎΡΡΠ½ΠΎΡΡΠ΅ΠΉ, ΡΠ΅ΠΎΡΠΈΡ ΡΠΈΡΠ΅Π». Π Π½Π°ΡΠ°Π»Π΅ 20 Π². Π³ΡΠ°ΡΡ ΡΡΠ°Π»ΠΈ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡΡΡ Π΄Π»Ρ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½ΠΈΡ Π½Π΅ΠΊΠΎΡΠΎΡΡΡ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΈΡ ΠΎΠ±ΡΠ΅ΠΊΡΠΎΠ² ΠΈ ΡΠΎΡΠΌΠ°Π»ΡΠ½ΠΎΠΉ ΠΏΠΎΡΡΠ°Π½ΠΎΠ²ΠΊΠΈ ΡΠ°Π·Π»ΠΈΡΠ½ΡΡ Π΄ΠΈΡΠΊΡΠ΅ΡΠ½ΡΡ Π·Π°Π΄Π°Ρ; ΠΏΡΠΈ ΡΡΠΎΠΌ Π½Π°ΡΡΠ΄Ρ… Π§ΠΈΡΠ°ΡΡ Π΅ΡΡ >
ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΠΠ΅ΠΉΠΊΡΡΡΡ (ΡΠ΅ΡΠ΅ΡΠ°Ρ, ΠΊΡΡΡΠΎΠ²Π°Ρ, Π΄ΠΈΠΏΠ»ΠΎΠΌ, ΠΊΠΎΠ½ΡΡΠΎΠ»ΡΠ½Π°Ρ)
Π’ΠΠ’Π£ ΠΠΎΠ½ΡΡΠΎΠ»ΡΠ½Π°Ρ ΡΠ°Π±ΠΎΡΠ° ΠΏΠΎ Π΄ΠΈΡΡΠΈΠΏΠ»ΠΈΠ½Π΅ «ΠΠ°ΡΠ΅ΠΌΠ°ΡΠΈΠΊΠ° Π§Π°ΡΡΡ II»
Π’Π΅ΠΌΠ°: «ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΠΠ΅ΠΉΠΊΡΡΡΡ»
- ΠΠ²Π΅Π΄Π΅Π½ΠΈΠ΅
- Π’Π΅ΠΎΡΠΈΡ Π³ΡΠ°ΡΠΎΠ² ΠΊΠ°ΠΊ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΈΠΉ Π°ΠΏΠΏΠ°ΡΠ°Ρ Π΄Π»Ρ ΡΠ΅ΡΠ΅Π½ΠΈΡ Π·Π°Π΄Π°Ρ
- ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΠΠ΅ΠΉΠΊΡΡΡΡ
- Π‘ΠΏΠΈΡΠΎΠΊ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΠΌΠΎΠΉ Π»ΠΈΡΠ΅ΡΠ°ΡΡΡΡ
ΠΠ°ΠΆΠ΄ΡΠΉ ΡΠ΅Π»ΠΎΠ²Π΅ΠΊ Π΅ΠΆΠ΅Π΄Π½Π΅Π²Π½ΠΎ, Π½Π΅ Π²ΡΠ΅Π³Π΄Π° ΠΎΡΠΎΠ·Π½Π°Π²Π°Ρ ΡΡΠΎ, ΡΠ΅ΡΠ°Π΅Ρ ΠΏΡΠΎΠ±Π»Π΅ΠΌΡ: ΠΊΠ°ΠΊ ΠΏΠΎΠ»ΡΡΠΈΡΡ Π½Π°ΠΈΠ±ΠΎΠ»ΡΡΠΈΠΉ ΡΡΡΠ΅ΠΊΡ, ΠΎΠ±Π»Π°Π΄Π°Ρ ΠΎΠ³ΡΠ°Π½ΠΈΡΠ΅Π½Π½ΡΠΌΠΈ ΡΡΠ΅Π΄ΡΡΠ²Π°ΠΌΠΈ. ΠΠ°ΡΠΈ ΡΡΠ΅Π΄ΡΡΠ²Π° ΠΈ ΡΠ΅ΡΡΡΡΡ Π²ΡΠ΅Π³Π΄Π° ΠΎΠ³ΡΠ°Π½ΠΈΡΠ΅Π½Ρ. ΠΠ΅ ΡΡΡΠ΄Π½ΠΎ Π²ΡΠΈΠ³ΡΠ°ΡΡ ΡΡΠ°ΠΆΠ΅Π½ΠΈΠ΅, ΠΈΠΌΠ΅Ρ Π°ΡΠΌΠΈΡ Π² 10 ΡΠ°Π· Π±ΠΎΠ»ΡΡΡΡ, ΡΠ΅ΠΌ Ρ ΠΏΡΠΎΡΠΈΠ²Π½ΠΈΠΊΠ°. ΠΠΎ ΡΠ°ΠΊΠΎΠΉ ΠΈΠ·Π±ΡΡΠΎΠΊ ΡΠ΅ΡΡΡΡΠΎΠ² Π±ΡΠ²Π°Π΅Ρ Π½Π΅ Π²ΡΠ΅Π³Π΄Π°. Π§ΡΠΎΠ±Ρ Π΄ΠΎΡΡΠΈΡΡ Π½Π°ΠΈΠ±ΠΎΠ»ΡΡΠ΅Π³ΠΎ ΡΡΡΠ΅ΠΊΡΠ°, ΠΈΠΌΠ΅Ρ ΠΎΠ³ΡΠ°Π½ΠΈΡΠ΅Π½Π½ΡΠ΅ ΡΡΠ΅Π΄ΡΡΠ²Π°, Π½Π°Π΄ΠΎ ΡΠΎΡΡΠ°Π²ΠΈΡΡ ΠΏΠ»Π°Π½, ΠΈΠ»ΠΈ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ Π΄Π΅ΠΉΡΡΠ²ΠΈΠΉ. Π’Π΅ΠΎΡΠΈΡ Π³ΡΠ°ΡΠΎΠ² ΡΠ°ΡΡΠΌΠ°ΡΡΠΈΠ²Π°Π΅Ρ ΡΠΈΡΠΎΠΊΠΈΠΉ ΠΊΡΡΠ³ Π·Π°Π΄Π°Ρ Ρ Π΅Π΄ΠΈΠ½ΠΎΠΉ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΎΠΉ ΠΌΠΎΠ΄Π΅Π»ΡΡ, ΠΎΠ½Π° Π½Π°Ρ ΠΎΠ΄ΠΈΡΡΡ ΡΠ΅ΠΉΡΠ°Ρ Π² ΡΠ°ΠΌΠΎΠΌ ΡΠ°ΡΡΠ²Π΅ΡΠ΅. ΠΠ±ΡΡΠ½ΠΎ Π΅Ρ ΠΎΡΠ½ΠΎΡΡΡ ΠΊ ΡΠΎΠΏΠΎΠ»ΠΎΠ³ΠΈΠΈ (ΠΏΠΎΡΠΎΠΌΡ ΡΡΠΎ Π²ΠΎ ΠΌΠ½ΠΎΠ³ΠΈΡ ΡΠ»ΡΡΠ°ΡΡ ΡΠ°ΡΡΠΌΠ°ΡΡΠΈΠ²Π°ΡΡΡΡ Π»ΠΈΡΡ ΡΠΎΠΏΠΎΠ»ΠΎΠ³ΠΈΡΠ΅ΡΠΊΠΈΠ΅ ΡΠ²ΠΎΠΉΡΡΠ²Π° Π³ΡΠ°ΡΠΎΠ²), ΠΎΠ΄Π½Π°ΠΊΠΎ ΠΎΠ½Π° ΠΏΠ΅ΡΠ΅ΡΠ΅ΠΊΠ°Π΅ΡΡΡ ΡΠΎ ΠΌΠ½ΠΎΠ³ΠΈΠΌΠΈ ΡΠ°Π·Π΄Π΅Π»Π°ΠΌΠΈ ΡΠ΅ΠΎΡΠΈΠΈ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ², ΠΊΠΎΠΌΠ±ΠΈΠ½Π°ΡΠΎΡΠ½ΠΎΠΉ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΠΊΠΈ, Π°Π»Π³Π΅Π±ΡΡ, Π³Π΅ΠΎΠΌΠ΅ΡΡΠΈΠΈ, ΡΠ΅ΠΎΡΠΈΠΈ ΠΌΠ°ΡΡΠΈΡ, ΡΠ΅ΠΎΡΠΈΠΈ ΠΈΠ³Ρ, ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΎΠΉ Π»ΠΎΠ³ΠΈΠΊΠΈ ΠΈ ΠΌΠ½ΠΎΠ³ΠΈΡ Π΄ΡΡΠ³ΠΈΡ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΈΡ Π΄ΠΈΡΡΠΈΠΏΠ»ΠΈΠ½.
ΠΠΎΠ»Π»Π°Π½Π΄ΡΠΊΠΈΠΉ ΡΡΠ΅Π½ΡΠΉ ΠΠ΄ΡΠ³Π΅Ρ ΠΠ°ΠΉΠ± ΠΠ΅ΠΉΠΊΡΡΡΠ° (1930;2002) Π²Π½Π΅Ρ Π±ΠΎΠ»ΡΡΠΎΠΉ Π²ΠΊΠ»Π°Π΄ Π² ΡΠ°Π·Π²ΠΈΡΠΈΠ΅ Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΡ ΠΈ ΡΠ΅ΠΎΡΠΈΡ Π³ΡΠ°ΡΠΎΠ². ΠΠ·Π²Π΅ΡΡΠ½ΠΎΡΡΡ ΠΠ΅ΠΉΠΊΡΡΡΠ΅ ΠΏΡΠΈΠ½Π΅ΡΠ»ΠΈ Π΅Π³ΠΎ ΡΠ°Π±ΠΎΡΡ Π² ΠΎΠ±Π»Π°ΡΡΠΈ ΠΏΡΠΈΠΌΠ΅Π½Π΅Π½ΠΈΡ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΎΠΉ Π»ΠΎΠ³ΠΈΠΊΠΈ ΠΏΡΠΈ ΡΠ°Π·ΡΠ°Π±ΠΎΡΠΊΠ΅ ΠΊΠΎΠΌΠΏΡΡΡΠ΅ΡΠ½ΡΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌ. Π Π°ΡΡΠΊΠ°Π·ΡΠ²Π°ΡΡ ΠΎΠ± ΡΡΠΎΠΌ ΡΠ΅Π»ΠΎΠ²Π΅ΠΊΠ΅ ΠΌΠΎΠΆΠ½ΠΎ ΠΎΡΠ΅Π½Ρ Π΄ΠΎΠ»Π³ΠΎ ΠΈ ΠΌΠ½ΠΎΠ³ΠΎ. ΠΠΎΠΆΠ½ΠΎ ΠΏΠ΅ΡΠ΅ΡΠΈΡΠ»ΡΡΡ Π½Π°ΡΡΠ½ΡΠ΅ ΡΠ΅Π³Π°Π»ΠΈΠΈ, Π·Π²Π°Π½ΠΈΡ ΠΈ ΡΡΠ΅ΠΏΠ΅Π½ΠΈ, Π±Π΅ΡΠΊΠΎΠ½Π΅ΡΠ½ΠΎ ΠΏΠΎΠ²ΡΠΎΡΡΡΡ ΡΠ»ΠΎΠ²Π° «Π½Π΅ΠΎΡΠ΅Π½ΠΈΠΌΡΠΉ Π²ΠΊΠ»Π°Π΄» ΠΈ «ΠΎΡΠ½ΠΎΠ²ΠΎΠΏΠΎΠ»ΠΎΠΆΠ½ΠΈΠΊ». ΠΠ½ ΡΠ²Π»ΡΠ»ΡΡ ΠΎΠ΄Π½ΠΈΠΌ ΠΈΠ· Π³Π»Π°Π²Π½ΡΡ ΡΠ°Π·ΡΠ°Π±ΠΎΡΡΠΈΠΊΠΎΠ² ΡΠ·ΡΠΊΠ° ALGOL. Π’Π°ΠΊΠΆΠ΅ Π΅ΠΌΡ ΠΏΡΠΈΠ½Π°Π΄Π»Π΅ΠΆΠΈΡ ΠΈΠ΄Π΅Ρ ΠΏΡΠΈΠΌΠ΅Π½Π΅Π½ΠΈΡ «ΡΠ΅ΠΌΠ°ΡΠΎΡΠΎΠ²» Π΄Π»Ρ ΡΠΈΠ½Ρ ΡΠΎΠ½ΠΈΠ·Π°ΡΠΈΠΈ ΠΏΡΠΎΡΠ΅ΡΡΠΎΠ² Π² ΠΌΠ½ΠΎΠ³ΠΎΠ·Π°Π΄Π°ΡΠ½ΡΡ ΡΠΈΡΡΠ΅ΠΌΠ°Ρ ΠΈ Π°Π»Π³ΠΎΡΠΈΡΠΌ Π½Π°Ρ ΠΎΠΆΠ΄Π΅Π½ΠΈΡ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠ΅Π³ΠΎ ΠΏΡΡΠΈ Π½Π° ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠΌ Π³ΡΠ°ΡΠ΅ Ρ Π½Π΅ΠΎΡΡΠΈΡΠ°ΡΠ΅Π»ΡΠ½ΡΠΌΠΈ Π²Π΅ΡΠ°ΠΌΠΈ ΡΡΠ±Π΅Ρ, ΠΈΠ·Π²Π΅ΡΡΠ½ΡΠΉ ΠΊΠ°ΠΊ ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΠΠ΅ΠΉΠΊΡΡΡΡ. Π 1972 Π³ΠΎΠ΄Ρ Π·Π° ΡΠ²ΠΎΠΉ Π²ΠΊΠ»Π°Π΄ Π² ΡΠ°Π·Π²ΠΈΡΠΈΠ΅ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΎΠ½Π½ΡΡ ΡΠ΅Ρ Π½ΠΎΠ»ΠΎΠ³ΠΈΠΉ ΠΠ΅ΠΉΠΊΡΡΡΠ° Π±ΡΠ» ΡΠ΄ΠΎΡΡΠΎΠ΅Π½ ΠΏΡΠ΅ΠΌΠΈΠΈ Π’ΡΡΡΠΈΠ½Π³Π°, ΠΊΠΎΡΠΎΡΡΡ Π½Π°Π·ΡΠ²Π°ΡΡ Π°Π½Π°Π»ΠΎΠ³ΠΎΠΌ ΠΠΎΠ±Π΅Π»Π΅Π²ΡΠΊΠΎΠΉ ΠΏΡΠ΅ΠΌΠΈΠΈ Π² ΠΎΠ±Π»Π°ΡΡΠΈ ΠΊΠΎΠΌΠΏΡΡΡΠ΅ΡΠΎΠ².
ΠΠ΄Π΅ΡΡ ΡΡΠ°Π·Ρ ΡΠΌΠ΅ΡΡΠ½ΠΎ Π±ΡΠ΄Π΅Ρ ΠΏΡΠΈΠ²Π΅ΡΡΠΈ Π½Π΅ΡΠΊΠΎΠ»ΡΠΊΠΎ ΡΡΠ°Π³ΠΌΠ΅Π½ΡΠΎΠ² ΠΈΠ· Π²ΠΎΡΠΏΠΎΠΌΠΈΠ½Π°Π½ΠΈΠΉ ΠΠ΅ΠΉΠΊΡΡΡΡ. ΠΠΎ-ΠΏΠ΅ΡΠ²ΡΡ , Π°Π»Π³ΠΎΡΠΈΡΠΌ ΡΡΠΎΡ ΡΠΎΠ·Π΄Π°Π²Π°Π»ΡΡ Π½Π΅ ΠΈΠ· ΠΏΡΠΎΡΡΠΎΠ³ΠΎ Π»ΡΠ±ΠΎΠΏΡΡΡΡΠ²Π°, Π° Π΄Π»Ρ ΡΠ΅ΡΠ΅Π½ΠΈΡ Π²ΠΏΠΎΠ»Π½Π΅ ΠΊΠΎΠ½ΠΊΡΠ΅ΡΠ½ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ, Π° ΠΈΠΌΠ΅Π½Π½ΠΎ, — ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·Π°ΡΠΈΠΈ Π΄Π»ΠΈΠ½Ρ ΠΏΡΠΎΠ²ΠΎΠ΄Π½ΠΈΠΊΠΎΠ² Π½Π° Π°Π½Π°Π»ΠΎΠ³Π΅ «ΠΌΠ°ΡΠ΅ΡΠΈΠ½ΡΠΊΠΎΠΉ ΠΏΠ»Π°ΡΡ» Π½ΠΎΠ²ΠΎΠ³ΠΎ ΡΠ°Π·ΡΠ°Π±Π°ΡΡΠ²Π°Π΅ΠΌΠΎΠ³ΠΎ ΠΊΠΎΠΌΠ°Π½Π΄ΠΎΠΉ ΠΊΠΎΠΌΠΏΡΡΡΠ΅ΡΠ° X1, ΡΠ°ΠΊ ΡΡΠΎ Π»Π°Π²ΡΠΎΠ²ΡΠΉ Π²Π΅Π½ΠΎΠΊ ΡΠΎΠ·Π΄Π°ΡΠ΅Π»Ρ ΠΏΠ΅ΡΠ²ΠΎΠΉ «ΡΡΠΈΠ»ΠΈΡΡ Π²ΡΠ΅Ρ Π²ΡΠ΅ΠΌΠ΅Π½ ΠΈ Π½Π°ΡΠΎΠ΄ΠΎΠ²» ΠΊΠ»Π°ΡΡΠ° CAD-CAE ΠΠ΅ΠΉΠΊΡΡΡΠ΅ ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡΠΈΡΠ²Π°ΠΈΠ²Π°ΡΡ ΡΠΌΠ΅Π»ΠΎ. Π Π²ΠΎΡ «Π²ΠΎ-Π²ΡΠΎΡΡΡ » Π»ΡΡΡΠ΅ ΡΠΊΠ°Π·Π°ΡΡ ΡΠ»ΠΎΠ²Π°ΠΌΠΈ ΡΠ°ΠΌΠΎΠ³ΠΎ ΠΠ΅ΠΉΠΊΡΡΡΡ: «ΠΠ° ΠΌΠ½ΠΎΠ³ΠΎ Π»Π΅Ρ ΠΈ Π² ΡΠΈΡΠΎΠΊΠΈΡ ΠΊΡΡΠ³Π°Ρ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΏΠΎΠΈΡΠΊΠ° ΠΊΡΠ°ΡΡΠ°ΠΉΡΠ΅Π³ΠΎ ΠΏΡΡΠΈ Π±ΡΠ» ΠΎΡΠ½ΠΎΠ²Π½ΡΠΌ ΠΈΡΡΠΎΡΠ½ΠΈΠΊΠΎΠΌ ΠΌΠΎΠ΅ΠΉ ΡΠ»Π°Π²Ρ, ΡΡΠΎ ΠΌΠ½Π΅ Π²ΡΠ΅Π³Π΄Π° ΠΊΠ°Π·Π°Π»ΠΎΡΡ ΡΡΡΠ°Π½Π½ΡΠΌ — Π²Π΅Π΄Ρ ΠΎΠ½ Π±ΡΠ» ΡΠΎΠ·Π΄Π°Π½ Π΄Π°ΠΆΠ΅ Π±Π΅Π· ΠΊΠ°ΡΠ°Π½Π΄Π°ΡΠ° ΠΈ Π±ΡΠΌΠ°Π³ΠΈ, Π·Π° ΡΠ°ΡΠΊΠΎΠΉ ΠΊΠΎΡΠ΅ Π½Π° ΡΠΎΠ»Π½Π΅ΡΠ½ΠΎΠΉ ΡΠ΅ΡΡΠ°ΡΠ΅ ΠΊΠ°ΡΠ΅ Π² ΠΠΌΡΡΠ΅ΡΠ΄Π°ΠΌΠ΅» .
Π’Π΅ΠΎΡΠΈΡ Π³ΡΠ°ΡΠΎΠ² ΠΊΠ°ΠΊ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΈΠΉ Π°ΠΏΠΏΠ°ΡΠ°Ρ Π΄Π»Ρ ΡΠ΅ΡΠ΅Π½ΠΈΡ Π·Π°Π΄Π°Ρ
Π’ΠΠΠ ΠΠ― ΠΠ ΠΠ€ΠΠ — ΡΡΠΎ ΠΎΠ±Π»Π°ΡΡΡ Π΄ΠΈΡΠΊΡΠ΅ΡΠ½ΠΎΠΉ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΠΊΠΈ, ΠΎΡΠΎΠ±Π΅Π½Π½ΠΎΡΡΡΡ ΠΊΠΎΡΠΎΡΠΎΠΉ ΡΠ²Π»ΡΠ΅ΡΡΡ Π³Π΅ΠΎΠΌΠ΅ΡΡΠΈΡΠ΅ΡΠΊΠΈΠΉ ΠΏΠΎΠ΄Ρ ΠΎΠ΄ ΠΊ ΠΈΠ·ΡΡΠ΅Π½ΠΈΡ ΠΎΠ±ΡΠ΅ΠΊΡΠΎΠ². ΠΡΠ½ΠΎΠ²Π½ΠΎΠΉ ΠΎΠ±ΡΠ΅ΠΊΡ ΡΠ΅ΠΎΡΠΈΠΈ Π³ΡΠ°ΡΠΎΠ²-Π³ΡΠ°Ρ ΠΈ Π΅Π³ΠΎ ΠΎΠ±ΠΎΠ±ΡΠ΅Π½ΠΈΡ.
ΠΠ΅ΡΠ²ΡΠ΅ Π·Π°Π΄Π°ΡΠΈ ΡΠ΅ΠΎΡΠΈΠΈ Π³ΡΠ°ΡΠΎΠ² Π±ΡΠ»ΠΈ ΡΠ²ΡΠ·Π°Π½Ρ Ρ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ΠΌ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΈΡ ΡΠ°Π·Π²Π»Π΅ΠΊΠ°ΡΠ΅Π»ΡΠ½ΡΡ Π·Π°Π΄Π°Ρ ΠΈ Π³ΠΎΠ»ΠΎΠ²ΠΎΠ»ΠΎΠΌΠΎΠΊ (Π·Π°Π΄Π°ΡΠ° ΠΎ ΠΠ΅Π½ΠΈΠ³ΡΠ±Π΅ΡΠ³ΡΠΊΠΈΡ ΠΌΠΎΡΡΠ°Ρ , Π·Π°Π΄Π°ΡΠ° ΠΎ ΡΠ°ΡΡΡΠ°Π½ΠΎΠ²ΠΊΠ΅ ΡΠ΅ΡΠ·Π΅ΠΉ Π½Π° ΡΠ°Ρ ΠΌΠ°ΡΠ½ΠΎΠΉ Π΄ΠΎΡΠΊΠ΅, Π·Π°Π΄Π°ΡΠΈ ΠΎ ΠΏΠ΅ΡΠ΅Π²ΠΎΠ·ΠΊΠ°Ρ , Π·Π°Π΄Π°ΡΠ° ΠΎ ΠΊΡΡΠ³ΠΎΡΠ²Π΅ΡΠ½ΠΎΠΌ ΠΏΡΡΠ΅ΡΠ΅ΡΡΠ²ΠΈΠΈ ΠΈ Π΄ΡΡΠ³ΠΈΠ΅).
ΠΠ΄Π½ΠΈΠΌ ΠΈΠ· ΠΏΠ΅ΡΠ²ΡΡ ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΠΎΠ² Π² ΡΠ΅ΠΎΡΠΈΠΈ Π³ΡΠ°ΡΠΎΠ² ΡΠ²ΠΈΠ»ΡΡ ΠΊΡΠΈΡΠ΅ΡΠΈΠΉ ΡΡΡΠ΅ΡΡΠ²ΠΎΠ²Π°Π½ΠΈΡ ΠΎΠ±Ρ ΠΎΠ΄Π° Π²ΡΠ΅Ρ ΡΠ΅Π±Π΅Ρ Π³ΡΠ°ΡΠ° Π±Π΅Π· ΠΏΠΎΠ²ΡΠΎΡΠ΅Π½ΠΈΠΉ, ΠΏΠΎΠ»ΡΡΠ΅Π½Π½ΡΠΉ Π. ΠΠΉΠ»Π΅ΡΠΎΠΌ ΠΏΡΠΈ ΡΠ΅ΡΠ΅Π½ΠΈΠΈ Π·Π°Π΄Π°ΡΠΈ ΠΎ ΠΠ΅Π½ΠΈΠ³ΡΠ±Π΅ΡΠ³ΡΠΊΠΈΡ ΠΌΠΎΡΡΠ°Ρ . ΠΠΎΡ ΠΏΠ΅ΡΠ΅ΡΠΊΠ°Π· ΠΎΡΡΡΠ²ΠΊΠ° ΠΈΠ· ΠΏΠΈΡΡΠΌΠ° ΠΠΉΠ»Π΅ΡΠ° ΠΎΡ 13 ΠΌΠ°ΡΡΠ° 1736 Π³ΠΎΠ΄Ρ: «ΠΠ½Π΅ Π±ΡΠ»Π° ΠΏΡΠ΅Π΄Π»ΠΎΠΆΠ΅Π½Π° Π·Π°Π΄Π°ΡΠ° ΠΎΠ± ΠΎΡΡΡΠΎΠ²Π΅, ΡΠ°ΡΠΏΠΎΠ»ΠΎΠΆΠ΅Π½Π½ΠΎΠΌ Π² Π³ΠΎΡΠΎΠ΄Π΅ ΠΠ΅Π½ΠΈΠ³ΡΠ±Π΅ΡΠ³Π΅ ΠΈ ΠΎΠΊΡΡΠΆΠ΅Π½Π½ΠΎΠΌ ΡΠ΅ΠΊΠΎΠΉ, ΡΠ΅ΡΠ΅Π· ΠΊΠΎΡΠΎΡΡΡ ΠΏΠ΅ΡΠ΅ΠΊΠΈΠ½ΡΡΠΎ 7 ΠΌΠΎΡΡΠΎΠ².
Π‘ΠΏΡΠ°ΡΠΈΠ²Π°Π΅ΡΡΡ, ΠΌΠΎΠΆΠ΅Ρ Π»ΠΈ ΠΊΡΠΎ-Π½ΠΈΠ±ΡΠ΄Ρ Π½Π΅ΠΏΡΠ΅ΡΡΠ²Π½ΠΎ ΠΎΠ±ΠΎΠΉΡΠΈ ΠΈΡ , ΠΏΡΠΎΡ ΠΎΠ΄Ρ ΡΠΎΠ»ΡΠΊΠΎ ΠΎΠ΄Π½Π°ΠΆΠ΄Ρ ΡΠ΅ΡΠ΅Π· ΠΊΠ°ΠΆΠ΄ΡΠΉ ΠΌΠΎΡΡ. Π ΡΡΡ ΠΆΠ΅ ΠΌΠ½Π΅ Π±ΡΠ»ΠΎ ΡΠΎΠΎΠ±ΡΠ΅Π½ΠΎ, ΡΡΠΎ Π½ΠΈΠΊΡΠΎ Π΅ΡΠ΅ Π΄ΠΎ ΡΠΈΡ ΠΏΠΎΡ Π½Π΅ ΡΠΌΠΎΠ³ ΡΡΠΎ ΠΏΡΠΎΠ΄Π΅Π»Π°ΡΡ, Π½ΠΎ Π½ΠΈΠΊΡΠΎ ΠΈ Π½Π΅ Π΄ΠΎΠΊΠ°Π·Π°Π», ΡΡΠΎ ΡΡΠΎ Π½Π΅Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ.
ΠΠΎΠΏΡΠΎΡ ΡΡΠΎΡ, Ρ ΠΎΡΡ ΠΈ Π±Π°Π½Π°Π»ΡΠ½ΡΠΉ, ΠΏΠΎΠΊΠ°Π·Π°Π»ΡΡ ΠΌΠ½Π΅, ΠΎΠ΄Π½Π°ΠΊΠΎ, Π΄ΠΎΡΡΠΎΠΉΠ½ΡΠΌ Π²Π½ΠΈΠΌΠ°Π½ΠΈΡ ΡΠ΅ΠΌ, ΡΡΠΎ Π΄Π»Ρ Π΅Π³ΠΎ ΡΠ΅ΡΠ΅Π½ΠΈΡ Π½Π΅Π΄ΠΎΡΡΠ°ΡΠΎΡΠ½Ρ Π½ΠΈ Π³Π΅ΠΎΠΌΠ΅ΡΡΠΈΡ, Π½ΠΈ Π°Π»Π³Π΅Π±ΡΠ°, Π½ΠΈ ΠΊΠΎΠΌΠ±ΠΈΠ½Π°ΡΠΎΡΠ½ΠΎΠ΅ ΠΈΡΠΊΡΡΡΡΠ²ΠΎ. ΠΠΎΡΠ»Π΅ Π΄ΠΎΠ»Π³ΠΈΡ ΡΠ°Π·ΠΌΡΡΠ»Π΅Π½ΠΈΠΉ Ρ Π½Π°ΡΠ΅Π» Π»ΡΠ³ΠΊΠΎΠ΅ ΠΏΡΠ°Π²ΠΈΠ»ΠΎ, ΠΎΡΠ½ΠΎΠ²Π°Π½Π½ΠΎΠ΅ Π½Π° Π²ΠΏΠΎΠ»Π½Π΅ ΡΠ±Π΅Π΄ΠΈΡΠ΅Π»ΡΠ½ΠΎΠΌ Π΄ΠΎΠΊΠ°Π·Π°ΡΠ΅Π»ΡΡΡΠ²Π΅, Ρ ΠΏΠΎΠΌΠΎΡΡΡ ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ ΠΌΠΎΠΆΠ½ΠΎ Π²ΠΎ Π²ΡΠ΅Ρ Π·Π°Π΄Π°ΡΠ°Ρ ΡΠ°ΠΊΠΎΠ³ΠΎ ΡΠΎΠ΄Π° ΡΠΎΡΡΠ°Ρ ΠΆΠ΅ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΠΈΡΡ, ΠΌΠΎΠΆΠ΅Ρ Π»ΠΈ Π±ΡΡΡ ΡΠΎΠ²Π΅ΡΡΠ΅Π½ ΡΠ°ΠΊΠΎΠΉ ΠΎΠ±Ρ ΠΎΠ΄ ΡΠ΅ΡΠ΅Π· ΠΊΠ°ΠΊΠΎΠ΅ ΡΠ³ΠΎΠ΄Π½ΠΎ ΡΠΈΡΠ»ΠΎ ΠΈ ΠΊΠ°ΠΊ ΡΠ³ΠΎΠ΄Π½ΠΎ ΡΠ°ΡΠΏΠΎΠ»ΠΎΠΆΠ΅Π½Π½ΡΡ ΠΌΠΎΡΡΠΎΠ² ΠΈΠ»ΠΈ Π½Π΅ ΠΌΠΎΠΆΠ΅Ρ". ΠΠ΅Π½ΠΈΠ³ΡΠ±Π΅ΡΠ³ΡΠΊΠΈΠ΅ ΠΌΠΎΡΡΡ ΡΡ Π΅ΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΈ ΠΌΠΎΠΆΠ½ΠΎ ΠΈΠ·ΠΎΠ±ΡΠ°Π·ΠΈΡΡ ΡΠ°ΠΊ (ΡΠΈΡ.1):
Π ΠΈΡ. 1. ΠΠ΅Π½ΠΈΠ³ΡΠ±Π΅ΡΠ³ΡΠΊΠΈΠ΅ ΠΌΠΎΡΡΡ Π½Π° ΠΊΠ°ΡΡΠ΅, ΠΈ Π² Π²ΠΈΠ΄Π΅ Π³ΡΠ°ΡΠ°.
Π ΡΠ΅ΡΠ΅Π΄ΠΈΠ½Π΅ 19 Π². ΠΏΠΎΡΠ²ΠΈΠ»ΠΈΡΡ ΡΠ°Π±ΠΎΡΡ, Π² ΠΊΠΎΡΠΎΡΡΡ ΠΏΡΠΈ ΡΠ΅ΡΠ΅Π½ΠΈΠΈ ΠΏΡΠ°ΠΊΡΠΈΡΠ΅ΡΠΊΠΈΡ Π·Π°Π΄Π°Ρ Π±ΡΠ»ΠΈ ΠΏΠΎΠ»ΡΡΠ΅Π½Ρ ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΡ, ΠΎΡΠ½ΠΎΡΡΡΠΈΠ΅ΡΡ ΠΊ ΡΠ΅ΠΎΡΠΈΠΈ Π³ΡΠ°ΡΠΎΠ². Π’Π°ΠΊ, Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, Π. ΠΠΈΡΡ Π³ΠΎΡ ΠΏΡΠΈ ΡΠΎΡΡΠ°Π²Π»Π΅Π½ΠΈΠΈ ΠΏΠΎΠ»Π½ΠΎΠΉ ΡΠΈΡΡΠ΅ΠΌΡ ΡΡΠ°Π²Π½Π΅Π½ΠΈΠΉ Π΄Π»Ρ ΡΠΎΠΊΠΎΠ² ΠΈ Π½Π°ΠΏΡΡΠΆΠ΅Π½ΠΈΠΉ Π² ΡΠ»Π΅ΠΊΡΡΠΈΡΠ΅ΡΠΊΠΎΠΉ ΡΡ Π΅ΠΌΠ΅ ΠΏΡΠ΅Π΄Π»ΠΎΠΆΠΈΠ» ΠΏΠΎ ΡΡΡΠ΅ΡΡΠ²Ρ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»ΡΡΡ ΡΠ°ΠΊΡΡ ΡΡ Π΅ΠΌΡ Π³ΡΠ°ΡΠΎΠΌ ΠΈ Π½Π°Ρ ΠΎΠ΄ΠΈΡΡ Π² ΡΡΠΎΠΌ Π³ΡΠ°ΡΠ΅ ΠΎΡΠ½ΠΎΠ²Π½ΡΠ΅ Π΄Π΅ΡΠ΅Π²ΡΡ, Ρ ΠΏΠΎΠΌΠΎΡΡΡ ΠΊΠΎΡΠΎΡΡΡ Π²ΡΠ΄Π΅Π»ΡΡΡΡΡ Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎ Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΡΠ΅ ΡΠΈΡΡΠ΅ΠΌΡ ΠΊΠΎΠ½ΡΡΡΠΎΠ². Π. ΠΡΠ»ΠΈ, ΠΈΡΡ ΠΎΠ΄Ρ ΠΈΠ· Π·Π°Π΄Π°Ρ ΠΏΠΎΠ΄ΡΡΠ΅ΡΠ° ΡΠΈΡΠ»Π° ΠΈΠ·ΠΎΠΌΠ΅ΡΠΎΠ² ΠΏΡΠ΅Π΄Π΅Π»ΡΠ½ΡΡ ΡΠ³Π»Π΅Π²ΠΎΠ΄ΠΎΡΠΎΠ΄ΠΎΠ², ΠΏΡΠΈΡΠ΅Π» ΠΊ Π·Π°Π΄Π°ΡΠ°ΠΌ ΠΏΠ΅ΡΠ΅ΡΠΈΡΠ»Π΅Π½ΠΈΡ ΠΈ ΠΎΠΏΠΈΡΠ°Π½ΠΈΡ Π΄Π΅ΡΠ΅Π²ΡΠ΅Π², ΠΎΠ±Π»Π°Π΄Π°ΡΡΠΈΡ Π·Π°Π΄Π°Π½Π½ΡΠΌΠΈ ΡΠ²ΠΎΠΉΡΡΠ²Π°ΠΌΠΈ, ΠΈ ΡΠ΅ΡΠΈΠ» Π½Π΅ΠΊΠΎΡΠΎΡΡΠ΅ ΠΈΠ· Π½ΠΈΡ .
Π 20 Π². Π·Π°Π΄Π°ΡΠΈ, ΡΠ²ΡΠ·Π°Π½Π½ΡΠ΅ Ρ Π³ΡΠ°ΡΠ°ΠΌΠΈ, Π½Π°ΡΠ°Π»ΠΈ Π²ΠΎΠ·Π½ΠΈΠΊΠ°ΡΡ Π½Π΅ ΡΠΎΠ»ΡΠΊΠΎ Π² ΡΠΈΠ·ΠΈΠΊΠ΅, Ρ ΠΈΠΌΠΈΠΈ, ΡΠ»Π΅ΠΊΡΡΠΎΡΠ΅Ρ Π½ΠΈΠΊΠ΅ Π±ΠΈΠΎΠ»ΠΎΠ³ΠΈΠΈ, ΡΠΊΠΎΠ½ΠΎΠΌΠΈΠΊΠ΅, ΡΠΎΡΠΈΠΎΠ»ΠΎΠ³ΠΈΠΈ ΠΈ Ρ. Π΄., Π½ΠΎ ΠΈ Π²Π½ΡΡΡΠΈ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΠΊΠΈ, Π² ΡΠ°ΠΊΠΈΡ ΡΠ°Π·Π΄Π΅Π»Π°Ρ , ΠΊΠ°ΠΊ ΡΠΎΠΏΠΎΠ»ΠΎΠ³ΠΈΡ, Π°Π»Π³Π΅Π±ΡΠ°, ΡΠ΅ΠΎΡΠΈΡ Π²Π΅ΡΠΎΡΡΠ½ΠΎΡΡΠ΅ΠΉ, ΡΠ΅ΠΎΡΠΈΡ ΡΠΈΡΠ΅Π». Π Π½Π°ΡΠ°Π»Π΅ 20 Π². Π³ΡΠ°ΡΡ ΡΡΠ°Π»ΠΈ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡΡΡ Π΄Π»Ρ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½ΠΈΡ Π½Π΅ΠΊΠΎΡΠΎΡΡΡ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΈΡ ΠΎΠ±ΡΠ΅ΠΊΡΠΎΠ² ΠΈ ΡΠΎΡΠΌΠ°Π»ΡΠ½ΠΎΠΉ ΠΏΠΎΡΡΠ°Π½ΠΎΠ²ΠΊΠΈ ΡΠ°Π·Π»ΠΈΡΠ½ΡΡ Π΄ΠΈΡΠΊΡΠ΅ΡΠ½ΡΡ Π·Π°Π΄Π°Ρ; ΠΏΡΠΈ ΡΡΠΎΠΌ Π½Π°ΡΡΠ΄Ρ Ρ ΡΠ΅ΡΠΌΠΈΠ½ΠΎΠΌ «Π³ΡΠ°Ρ» ΡΠΏΠΎΡΡΠ΅Π±Π»ΡΠ»ΠΈΡΡ ΠΈ Π΄ΡΡΠ³ΠΈΠ΅ ΡΠ΅ΡΠΌΠΈΠ½Ρ, Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, ΠΊΠ°ΡΡΠ°, ΠΊΠΎΠΌΠΏΠ»Π΅ΠΊΡ, Π΄ΠΈΠ°Π³ΡΠ°ΠΌΠΌΠ°, ΡΠ΅ΡΡ, Π»Π°Π±ΠΈΡΠΈΠ½Ρ. ΠΠΎΡΠ»Π΅ Π²ΡΡ ΠΎΠ΄Π° Π² ΡΠ²Π΅Ρ Π² 1936 Π³ΠΎΠ΄Ρ ΠΌΠΎΠ½ΠΎΠ³ΡΠ°ΡΠΈΠΈ Π. ΠΡΠ½ΠΈΠ³Π° ΡΠ΅ΡΠΌΠΈΠ½ «Π³ΡΠ°Ρ» ΡΡΠ°Π» Π±ΠΎΠ»Π΅Π΅ ΡΠΏΠΎΡΡΠ΅Π±ΠΈΡΠ΅Π»ΡΠ½ΡΠΌ, ΡΠ΅ΠΌ Π΄ΡΡΠ³ΠΈΠ΅. Π ΡΡΠΎΠΉ ΡΠ°Π±ΠΎΡΠ΅ Π±ΡΠ»ΠΈ ΡΠΈΡΡΠ΅ΠΌΠ°ΡΠΈΠ·ΠΈΡΠΎΠ²Π°Π½Ρ ΠΈΠ·Π²Π΅ΡΡΠ½ΡΠ΅ ΠΊ ΡΠΎΠΌΡ Π²ΡΠ΅ΠΌΠ΅Π½ΠΈ ΡΠ°ΠΊΡΡ. Π 1936 Π³ΠΎΠ΄Ρ Π²ΡΡΠ»Π° Π½Π΅Π±ΠΎΠ»ΡΡΠ°Ρ Π±ΡΠΎΡΡΡΠ° ΠΠΉΡΡΠ΅Π½Π° ΠΡΠ΅, ΡΠΎΠ΄Π΅ΡΠΆΠ°ΡΠ°Ρ Π±Π»Π΅ΡΡΡΡΠ΅Π΅ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΡΠ½ΠΎΠ΅ Π²Π²Π΅Π΄Π΅Π½ΠΈΠ΅ Π² ΡΠ΅ΠΎΡΠΈΡ Π³ΡΠ°ΡΠΎΠ². Π 1962 Π³ΠΎΠ΄Ρ Π² ΠΠ½Π³Π»ΠΈΠΈ Π±ΡΠ»Π° ΠΈΠ·Π΄Π°Π½Π° ΠΊΠ½ΠΈΠ³Π° ΡΡΠ°Π½ΡΡΠ·ΡΠΊΠΎΠ³ΠΎ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΠΊΠ° ΠΠ»ΠΎΠ΄Π° ΠΠ΅ΡΠΆΠ° «Π’Π΅ΠΎΡΠΈΡ Π³ΡΠ°ΡΠΎΠ² ΠΈ Π΅Ρ ΠΏΡΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅». ΠΠ±Π΅ ΠΊΠ½ΠΈΠ³ΠΈ, Π±Π΅Π·ΡΡΠ»ΠΎΠ²Π½ΠΎ, ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»ΡΡΡ ΠΈΠ½ΡΠ΅ΡΠ΅Ρ Π΄Π»Ρ Π»ΡΠ±ΠΈΡΠ΅Π»Π΅ΠΉ Π·Π°Π½ΠΈΠΌΠ°ΡΠ΅Π»ΡΠ½ΠΎΠΉ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΠΊΠΈ. Π‘ΠΎΡΠ½ΠΈ ΠΈΠ·Π²Π΅ΡΡΠ½ΡΡ Π³ΠΎΠ»ΠΎΠ²ΠΎΠ»ΠΎΠΌΠΎΠΊ, Π½Π° ΠΏΠ΅ΡΠ²ΡΠΉ Π²Π·Π³Π»ΡΠ΄ Π½Π΅ ΠΈΠΌΠ΅ΡΡΠΈΡ Π½ΠΈΡΠ΅Π³ΠΎ ΠΎΠ±ΡΠ΅Π³ΠΎ Π΄ΡΡΠ³ Ρ Π΄ΡΡΠ³ΠΎΠΌ, Π»Π΅Π³ΠΊΠΎ ΡΠ΅ΡΠ°ΡΡΡΡ Ρ ΠΏΠΎΠΌΠΎΡΡΡ ΡΠ΅ΠΎΡΠΈΠΈ Π³ΡΠ°ΡΠΎΠ².
Π 20−30-Ρ Π³ΠΎΠ΄Π°Ρ 20 Π². ΠΏΠΎΡΠ²ΠΈΠ»ΠΈΡΡ ΠΏΠ΅ΡΠ²ΡΠ΅ ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΡ, ΠΎΡΠ½ΠΎΡΡΡΠΈΠ΅ΡΡ ΠΊ ΠΈΠ·ΡΡΠ΅Π½ΠΈΡ ΡΠ²ΠΎΠΉΡΡΠ² ΡΠ²ΡΠ·Π½ΠΎΡΡΠΈ, ΠΏΠ»Π°Π½Π°ΡΠ½ΠΎΡΡΠΈ, ΡΠΈΠΌΠΌΠ΅ΡΡΠΈΠΈ Π³ΡΠ°ΡΠΎΠ², ΠΊΠΎΡΠΎΡΡΠ΅ ΠΏΡΠΈΠ²Π΅Π»ΠΈ ΠΊ ΡΠΎΡΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΡ ΡΡΠ΄Π° Π½ΠΎΠ²ΡΡ Π½Π°ΠΏΡΠ°Π²Π»Π΅Π½ΠΈΠΉ Π² ΡΠ΅ΠΎΡΠΈΠΈ Π³ΡΠ°ΡΠΎΠ².
ΠΠ½Π°ΡΠΈΡΠ΅Π»ΡΠ½ΠΎ ΡΠ°ΡΡΠΈΡΠΈΠ»ΠΈΡΡ ΠΈΡΡΠ»Π΅Π΄ΠΎΠ²Π°Π½ΠΈΡ ΠΏΠΎ ΡΠ΅ΠΎΡΠΈΠΈ Π³ΡΠ°ΡΠΎΠ² Π² ΠΊΠΎΠ½ΡΠ΅ 40-Ρ — Π½Π°ΡΠ°Π»Π΅ 50-Ρ Π³ΠΎΠ΄ΠΎΠ², ΠΏΡΠ΅ΠΆΠ΄Π΅ Π²ΡΠ΅Π³ΠΎ Π² ΡΠΈΠ»Ρ ΡΠ°Π·Π²ΠΈΡΠΈΡ ΠΊΠΈΠ±Π΅ΡΠ½Π΅ΡΠΈΠΊΠΈ ΠΈ Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΠΎΠΉ ΡΠ΅Ρ Π½ΠΈΠΊΠΈ. ΠΠ»Π°Π³ΠΎΠ΄Π°ΡΡ ΡΠ°Π·Π²ΠΈΡΠΈΡ Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΠΎΠΉ ΡΠ΅Ρ Π½ΠΈΠΊΠΈ, ΠΈΠ·ΡΡΠ΅Π½ΠΈΡ ΡΠ»ΠΎΠΆΠ½ΡΡ ΠΊΠΈΠ±Π΅ΡΠ½Π΅ΡΠΈΡΠ΅ΡΠΊΠΈΡ ΡΠΈΡΡΠ΅ΠΌ, ΠΈΠ½ΡΠ΅ΡΠ΅Ρ ΠΊ ΡΠ΅ΠΎΡΠΈΠΈ Π³ΡΠ°ΡΠΎΠ² Π²ΠΎΠ·ΡΠΎΡ, Π° ΠΏΡΠΎΠ±Π»Π΅ΠΌΠ°ΡΠΈΠΊΠ° ΡΠ΅ΠΎΡΠΈΠΈ Π³ΡΠ°ΡΠΎΠ² ΡΡΡΠ΅ΡΡΠ²Π΅Π½Π½ΡΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ ΠΎΠ±ΠΎΠ³Π°ΡΠΈΠ»Π°ΡΡ. ΠΡΠΎΠΌΠ΅ ΡΠΎΠ³ΠΎ, ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΠ΅ ΠΠΠ ΠΏΠΎΠ·Π²ΠΎΠ»ΠΈΠ»ΠΎ ΡΠ΅ΡΠ°ΡΡ Π²ΠΎΠ·Π½ΠΈΠΊΠ°ΡΡΠΈΠ΅ Π½Π° ΠΏΡΠ°ΠΊΡΠΈΠΊΠ΅ ΠΊΠΎΠ½ΠΊΡΠ΅ΡΠ½ΡΠ΅ Π·Π°Π΄Π°ΡΠΈ, ΡΠ²ΡΠ·Π°Π½Π½ΡΠ΅ Ρ Π±ΠΎΠ»ΡΡΠΈΠΌ ΠΎΠ±ΡΠ΅ΠΌΠΎΠΌ Π²ΡΡΠΈΡΠ»Π΅Π½ΠΈΠΉ, ΠΏΡΠ΅ΠΆΠ΄Π΅ Π½Π΅ ΠΏΠΎΠ΄Π΄Π°Π²Π°Π²ΡΠΈΠ΅ΡΡ ΡΠ΅ΡΠ΅Π½ΠΈΡ. ΠΠ»Ρ ΡΡΠ΄Π° ΡΠΊΡΡΡΠ΅ΠΌΠ°Π»ΡΠ½ΡΡ Π·Π°Π΄Π°Ρ ΡΠ΅ΠΎΡΠΈΠΈ Π³ΡΠ°ΡΠΎΠ² Π±ΡΠ»ΠΈ ΡΠ°Π·ΡΠ°Π±ΠΎΡΠ°Π½Ρ ΠΌΠ΅ΡΠΎΠ΄Ρ ΠΈΡ ΡΠ΅ΡΠ΅Π½ΠΈΡ, Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, ΠΎΠ΄ΠΈΠ½ ΠΈΠ· ΡΠ°ΠΊΠΈΡ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠ² ΠΏΠΎΠ·Π²ΠΎΠ»ΡΠ΅Ρ ΡΠ΅ΡΠ°ΡΡ Π·Π°Π΄Π°ΡΠΈ ΠΎ ΠΏΠΎΡΡΡΠΎΠ΅Π½ΠΈΠΈ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΏΠΎΡΠΎΠΊΠ° ΡΠ΅ΡΠ΅Π· ΡΠ΅ΡΡ. ΠΠ»Ρ ΠΎΡΠ΄Π΅Π»ΡΠ½ΡΡ ΠΊΠ»Π°ΡΡΠΎΠ² Π³ΡΠ°ΡΠΎΠ² (Π΄Π΅ΡΠ΅Π²ΡΡ, ΠΏΠ»ΠΎΡΠΊΠΈΠ΅ Π³ΡΠ°ΡΡ ΠΈ Ρ. Π΄.), ΠΊΠΎΡΠΎΡΡΠ΅ ΠΈΠ·ΡΡΠ°Π»ΠΈΡΡ ΠΈ ΡΠ°Π½Π΅Π΅, Π±ΡΠ»ΠΎ ΠΏΠΎΠΊΠ°Π·Π°Π½ΠΎ, ΡΡΠΎ ΡΠ΅ΡΠ΅Π½ΠΈΡ Π½Π΅ΠΊΠΎΡΠΎΡΡΡ Π·Π°Π΄Π°Ρ Π΄Π»Ρ Π³ΡΠ°ΡΠΎΠ² ΠΈΠ· ΡΡΠΈΡ ΠΊΠ»Π°ΡΡΠΎΠ² Π½Π°Ρ ΠΎΠ΄ΡΡΡΡ ΠΏΡΠΎΡΠ΅, ΡΠ΅ΠΌ Π΄Π»Ρ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ»ΡΠ½ΡΡ Π³ΡΠ°ΡΠΎΠ² (Π½Π°Ρ ΠΎΠΆΠ΄Π΅Π½ΠΈΠ΅ ΡΡΠ»ΠΎΠ²ΠΈΠΉ ΡΡΡΠ΅ΡΡΠ²ΠΎΠ²Π°Π½ΠΈΡ Π³ΡΠ°ΡΠΎΠ² Ρ Π·Π°Π΄Π°Π½Π½ΡΠΌΠΈ ΡΠ²ΠΎΠΉΡΡΠ²Π°ΠΌΠΈ, ΡΡΡΠ°Π½ΠΎΠ²Π»Π΅Π½ΠΈΠ΅ ΠΈΠ·ΠΎΠΌΠΎΡΡΠΈΠ·ΠΌΠ° Π³ΡΠ°ΡΠΎΠ² ΠΈ Π΄Ρ.).
Π₯Π°ΡΠ°ΠΊΡΠ΅ΡΠΈΠ·ΡΡ ΠΏΡΠΎΠ±Π»Π΅ΠΌΠ°ΡΠΈΠΊΡ ΡΠ΅ΠΎΡΠΈΠΈ Π³ΡΠ°ΡΠΎΠ², ΠΌΠΎΠΆΠ½ΠΎ ΠΎΡΠΌΠ΅ΡΠΈΡΡ, ΡΡΠΎ Π½Π΅ΠΊΠΎΡΠΎΡΡΠ΅ Π½Π°ΠΏΡΠ°Π²Π»Π΅Π½ΠΈΡ Π½ΠΎΡΡΡ Π±ΠΎΠ»Π΅Π΅ ΠΊΠΎΠΌΠ±ΠΈΠ½Π°ΡΠΎΡΠ½ΡΠΉ Ρ Π°ΡΠ°ΠΊΡΠ΅Ρ, Π΄ΡΡΠ³ΠΈΠ΅ — Π±ΠΎΠ»Π΅Π΅ Π³Π΅ΠΎΠΌΠ΅ΡΡΠΈΡΠ΅ΡΠΊΠΈΠΉ. Π ΠΏΠ΅ΡΠ²ΡΠΌ ΠΎΡΠ½ΠΎΡΡΡΡΡ, Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, Π·Π°Π΄Π°ΡΠΈ ΠΎ ΠΏΠΎΠ΄ΡΡΠ΅ΡΠ΅ ΠΈ ΠΏΠ΅ΡΠ΅ΡΠΈΡΠ»Π΅Π½ΠΈΠΈ Π³ΡΠ°ΡΠΎΠ² Ρ ΡΠΈΠΊΡΠΈΡΠΎΠ²Π°Π½Π½ΡΠΌΠΈ ΡΠ²ΠΎΠΉΡΡΠ²Π°ΠΌΠΈ, Π·Π°Π΄Π°ΡΠΈ ΠΎ ΠΏΠΎΡΡΡΠΎΠ΅Π½ΠΈΠΈ Π³ΡΠ°ΡΠΎΠ² Ρ Π·Π°Π΄Π°Π½Π½ΡΠΌΠΈ ΡΠ²ΠΎΠΉΡΡΠ²Π°ΠΌΠΈ. ΠΠ΅ΠΎΠΌΠ΅ΡΡΠΈΡΠ΅ΡΠΊΠΈΠΉ (ΡΠΎΠΏΠΎΠ»ΠΎΠ³ΠΈΡΠ΅ΡΠΊΠΈΠΉ) Ρ Π°ΡΠ°ΠΊΡΠ΅Ρ Π½ΠΎΡΡΡ ΠΌΠ½ΠΎΠ³ΠΈΠ΅ ΡΠΈΠΊΠ»Ρ Π·Π°Π΄Π°Ρ ΡΠ΅ΠΎΡΠΈΠΈ Π³ΡΠ°ΡΠΎΠ², Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, Π³ΡΠ°ΡΠΎΠ² ΠΎΠ±Ρ ΠΎΠ΄Ρ, Π³ΡΠ°ΡΠΎΠ² ΡΠΊΠ»Π°Π΄ΠΊΠΈ. Π‘ΡΡΠ΅ΡΡΠ²ΡΡΡ Π½Π°ΠΏΡΠ°Π²Π»Π΅Π½ΠΈΡ, ΡΠ²ΡΠ·Π°Π½Π½ΡΠ΅ Ρ ΡΠ°Π·Π»ΠΈΡΠ½ΡΠΌΠΈ ΠΊΠ»Π°ΡΡΠΈΡΠΈΠΊΠ°ΡΠΈΡΠΌΠΈ Π³ΡΠ°ΡΠΎΠ², Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, ΠΏΠΎ ΡΠ²ΠΎΠΉΡΡΠ²Π°ΠΌ ΠΈΡ ΡΠ°Π·Π»ΠΎΠΆΠ΅Π½ΠΈΡ.
Π ΡΠ΅ΠΎΡΠΈΠΈ Π³ΡΠ°ΡΠΎΠ² ΡΡΡΠ΅ΡΡΠ²ΡΡΡ ΡΠΏΠ΅ΡΠΈΡΠΈΡΠ΅ΡΠΊΠΈΠ΅ ΠΌΠ΅ΡΠΎΠ΄Ρ ΡΠ΅ΡΠ΅Π½ΠΈΡ ΡΠΊΡΡΡΠ΅ΠΌΠ°Π»ΡΠ½ΡΡ Π·Π°Π΄Π°Ρ. ΠΠ΄ΠΈΠ½ ΠΈΠ· Π½ΠΈΡ ΠΎΡΠ½ΠΎΠ²Π°Π½ Π½Π° ΡΠ΅ΠΎΡΠ΅ΠΌΠ΅ ΠΎ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠΌ ΠΏΠΎΡΠΎΠΊΠ΅ ΠΈ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠΌ ΡΠ°Π·ΡΠ΅Π·Π΅, ΡΡΠ²Π΅ΡΠΆΠ΄Π°ΡΡΠ΅ΠΉ, ΡΡΠΎ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΡΠΉ ΠΏΠΎΡΠΎΠΊ, ΠΊΠΎΡΠΎΡΡΠΉ ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡΠΎΠΏΡΡΡΠΈΡΡ ΡΠ΅ΡΠ΅Π· ΡΠ΅ΡΡ ΠΈΠ· Π²Π΅ΡΡΠΈΠ½Ρ U Π² Π²Π΅ΡΡΠΈΠ½Ρ V, ΡΠ°Π²Π΅Π½ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠΉ ΠΏΡΠΎΠΏΡΡΠΊΠ½ΠΎΠΉ ΡΠΏΠΎΡΠΎΠ±Π½ΠΎΡΡΠΈ ΡΠ°Π·ΡΠ΅Π·ΠΎΠ², ΡΠ°Π·Π΄Π΅Π»ΡΡΡΠΈΡ Π²Π΅ΡΡΠΈΠ½Ρ U ΠΈ V. ΠΡΠ»ΠΈ ΠΏΠΎΡΡΡΠΎΠ΅Π½Ρ ΡΠ°Π·Π»ΠΈΡΠ½ΡΠ΅ ΡΡΡΠ΅ΠΊΡΠΈΠ²Π½ΡΠ΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ Π½Π°Ρ ΠΎΠΆΠ΄Π΅Π½ΠΈΡ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΏΠΎΡΠΎΠΊΠ°.
Π Π΅Π·ΡΠ»ΡΡΠ°ΡΡ ΠΈ ΠΌΠ΅ΡΠΎΠ΄Ρ ΡΠ΅ΠΎΡΠΈΠΈ Π³ΡΠ°ΡΠΎΠ² ΠΏΡΠΈΠΌΠ΅Π½ΡΡΡΡΡ ΠΏΡΠΈ ΡΠ΅ΡΠ΅Π½ΠΈΠΈ ΡΡΠ°Π½ΡΠΏΠΎΡΡΠ½ΡΡ Π·Π°Π΄Π°Ρ ΠΎ ΠΏΠ΅ΡΠ΅Π²ΠΎΠ·ΠΊΠ°Ρ , Π΄Π»Ρ Π½Π°Ρ ΠΎΠΆΠ΄Π΅Π½ΠΈΡ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΡΡ ΡΠ΅ΡΠ΅Π½ΠΈΠΉ Π·Π°Π΄Π°ΡΠΈ ΠΎ Π½Π°Π·Π½Π°ΡΠ΅Π½ΠΈΡΡ , Π΄Π»Ρ Π²ΡΠ΄Π΅Π»Π΅Π½ΠΈΡ «ΡΠ·ΠΊΠΈΡ ΠΌΠ΅ΡΡ» ΠΏΡΠΈ ΠΏΠ»Π°Π½ΠΈΡΠΎΠ²Π°Π½ΠΈΠΈ ΠΈ ΡΠΏΡΠ°Π²Π»Π΅Π½ΠΈΠΈ ΡΠ°Π·ΡΠ°Π±ΠΎΡΠΎΠΊ ΠΏΡΠΎΠ΅ΠΊΡΠΎΠ², ΠΏΡΠΈ ΡΠΎΡΡΠ°Π²Π»Π΅Π½ΠΈΠΈ ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΡΡ ΠΌΠ°ΡΡΡΡΡΠΎΠ² Π΄ΠΎΡΡΠ°Π²ΠΊΠΈ Π³ΡΡΠ·ΠΎΠ², Π° ΡΠ°ΠΊΠΆΠ΅ ΠΏΡΠΈ ΠΌΠΎΠ΄Π΅Π»ΠΈΡΠΎΠ²Π°Π½ΠΈΠΈ ΡΠ»ΠΎΠΆΠ½ΡΡ ΡΠ΅Ρ Π½ΠΎΠ»ΠΎΠ³ΠΈΡ, ΠΏΡΠΎΡΠ΅ΡΡΠΎΠ², Π² ΠΏΠΎΡΡΡΠΎΠ΅Π½ΠΈΠΈ ΡΠ°Π·Π»ΠΈΡΠ½ΡΡ Π΄ΠΈΡΠΊΡΠ΅ΡΠ½ΡΡ ΡΡΡΡΠΎΠΉΡΡΠ², Π² ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΠΈ ΠΈ Ρ. Π΄.
Π Π°Π·Π²ΠΈΡΠΈΠ΅ ΡΠ΅ΠΎΡΠΈΠΈ Π³ΡΠ°ΡΠΎΠ² Π² ΠΎΡΠ½ΠΎΠ²Π½ΠΎΠΌ ΠΎΠ±ΡΠ·Π°Π½ΠΎ Π±ΠΎΠ»ΡΡΠΎΠΌΡ ΡΠΈΡΠ»Ρ Π²ΡΠ΅Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΡΡ ΠΏΡΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΠΉ. ΠΠΎ-Π²ΠΈΠ΄ΠΈΠΌΠΎΠΌΡ, ΠΈΠ· Π²ΡΠ΅Ρ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΈΡ ΠΎΠ±ΡΠ΅ΠΊΡΠΎΠ² Π³ΡΠ°ΡΡ Π·Π°Π½ΠΈΠΌΠ°ΡΡ ΠΎΠ΄Π½ΠΎ ΠΈΠ· ΠΏΠ΅ΡΠ²ΡΡ ΠΌΠ΅ΡΡ Π² ΠΊΠ°ΡΠ΅ΡΡΠ²Π΅ ΡΠΎΡΠΌΠ°Π»ΡΠ½ΡΡ ΠΌΠΎΠ΄Π΅Π»Π΅ΠΉ ΡΠ΅Π°Π»ΡΠ½ΡΡ ΡΠΈΡΡΠ΅ΠΌ.
ΠΡΠ°ΡΡ Π½Π°ΡΠ»ΠΈ ΠΏΡΠΈΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ ΠΏΡΠ°ΠΊΡΠΈΡΠ΅ΡΠΊΠΈ Π²ΠΎ Π²ΡΠ΅Ρ ΠΎΡΡΠ°ΡΠ»ΡΡ Π½Π°ΡΡΠ½ΡΡ Π·Π½Π°Π½ΠΈΠΉ: ΡΠΈΠ·ΠΈΠΊΠ΅, Π±ΠΈΠΎΠ»ΠΎΠ³ΠΈΠΈ, Ρ ΠΈΠΌΠΈΠΈ, ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΠΊΠ΅, ΠΈΡΡΠΎΡΠΈΠΈ, Π»ΠΈΠ½Π³Π²ΠΈΡΡΠΈΠΊΠ΅, ΡΠΎΡΠΈΠ°Π»ΡΠ½ΡΡ Π½Π°ΡΠΊΠ°Ρ , ΡΠ΅Ρ Π½ΠΈΠΊΠ΅ ΠΈ Ρ. ΠΏ. ΠΠ°ΠΈΠ±ΠΎΠ»ΡΡΠ΅ΠΉ ΠΏΠΎΠΏΡΠ»ΡΡΠ½ΠΎΡΡΡΡ ΡΠ΅ΠΎΡΠ΅ΡΠΈΠΊΠΎ-Π³ΡΠ°ΡΠΎΠ²ΡΠ΅ ΠΌΠΎΠ΄Π΅Π»ΠΈ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΡΡΡΡ ΠΏΡΠΈ ΠΈΡΡΠ»Π΅Π΄ΠΎΠ²Π°Π½ΠΈΠΈ ΠΊΠΎΠΌΠΌΡΠ½ΠΈΠΊΠ°ΡΠΈΠΎΠ½Π½ΡΡ ΡΠ΅ΡΠ΅ΠΉ, ΡΠΈΡΡΠ΅ΠΌ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΊΠΈ, Ρ ΠΈΠΌΠΈΡΠ΅ΡΠΊΠΈΡ ΠΈ Π³Π΅Π½Π΅ΡΠΈΡΠ΅ΡΠΊΠΈΡ ΡΡΡΡΠΊΡΡΡ, ΡΠ»Π΅ΠΊΡΡΠΈΡΠ΅ΡΠΊΠΈΡ ΡΠ΅ΠΏΠ΅ΠΉ ΠΈ Π΄ΡΡΠ³ΠΈΡ ΡΠΈΡΡΠ΅ΠΌ ΡΠ΅ΡΠ΅Π²ΠΎΠΉ ΡΡΡΡΠΊΡΡΡΡ.
ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΠΠ΅ΠΉΠΊΡΡΡΡ
ΠΠ»Π³ΠΎΡΠΈΠΌΡΠΌ ΠΠ΅ΠΌΠΉΠΊΡΡΡΡ (Dijkstra's algorithm) — Π°Π»Π³ΠΎΡΠΈΡΠΌ Π½Π° Π³ΡΠ°ΡΠ°Ρ , ΠΈΠ·ΠΎΠ±ΡΠ΅ΡΡΠ½Π½ΡΠΉ Π½ΠΈΠ΄Π΅ΡΠ»Π°Π½Π΄ΡΠΊΠΈΠΌ ΡΡΠ΅Π½ΡΠΌ Π. ΠΠ΅ΠΉΠΊΡΡΡΠΎΠΉ Π² 1959 Π³ΠΎΠ΄Ρ. ΠΠ°Ρ ΠΎΠ΄ΠΈΡ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠ΅Π΅ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠ΅ ΠΎΡ ΠΎΠ΄Π½ΠΎΠΉ ΠΈΠ· Π²Π΅ΡΡΠΈΠ½ Π³ΡΠ°ΡΠ° Π΄ΠΎ Π²ΡΠ΅Ρ ΠΎΡΡΠ°Π»ΡΠ½ΡΡ . ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΡΠ°Π±ΠΎΡΠ°Π΅Ρ ΡΠΎΠ»ΡΠΊΠΎ Π΄Π»Ρ Π³ΡΠ°ΡΠΎΠ² Π±Π΅Π· ΡΡΠ±Π΅Ρ ΠΎΡΡΠΈΡΠ°ΡΠ΅Π»ΡΠ½ΠΎΠ³ΠΎ Π²Π΅ΡΠ°. ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΡΠΈΡΠΎΠΊΠΎ ΠΏΡΠΈΠΌΠ΅Π½ΡΠ΅ΡΡΡ Π² ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΠΈ ΠΈ ΡΠ΅Ρ Π½ΠΎΠ»ΠΎΠ³ΠΈΡΡ , Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, Π΅Π³ΠΎ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅Ρ ΠΏΡΠΎΡΠΎΠΊΠΎΠ» OSPF Π΄Π»Ρ ΡΡΡΡΠ°Π½Π΅Π½ΠΈΡ ΠΊΠΎΠ»ΡΡΠ΅Π²ΡΡ ΠΌΠ°ΡΡΡΡΡΠΎΠ². ΠΠ·Π²Π΅ΡΡΠ΅Π½ ΡΠ°ΠΊΠΆΠ΅ ΠΏΠΎΠ΄ Π½Π°Π·Π²Π°Π½ΠΈΠ΅ΠΌ «Π‘Π½Π°ΡΠ°Π»Π° ΠΡΠ°ΡΡΠ°ΠΉΡΠΈΠΉ ΠΡΡΡ» (Shortest Path First).
ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΠΠ΅ΠΉΠΊΡΡΡΡ ΡΠ΅ΡΠ°Π΅Ρ Π·Π°Π΄Π°ΡΡ ΠΎ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠΈΡ ΠΏΡΡΡΡ ΠΈΠ· ΠΎΠ΄Π½ΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ Π΄Π»Ρ Π²Π·Π²Π΅ΡΠ΅Π½Π½ΠΎΠ³ΠΎ ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠ³ΠΎ Π³ΡΠ°ΡΠ° G = (V, E) Ρ ΠΈΡΡ ΠΎΠ΄Π½ΠΎΠΉ Π²Π΅ΡΡΠΈΠ½ΠΎΠΉ s, Π² ΠΊΠΎΡΠΎΡΠΎΠΌ Π²Π΅ΡΠ° Π²ΡΠ΅Ρ ΡΡΠ±Π΅Ρ Π½Π΅ΠΎΡΡΠΈΡΠ°ΡΠ΅Π»ΡΠ½Ρ ((u, v)? 0 Π΄Π»Ρ Π²ΡΠ΅Ρ (u, v) E). Π ΡΠ»ΡΡΠ°Π΅, ΠΊΠΎΠ³Π΄Π° ΡΠ΅Π±ΡΠ° Π³ΡΠ°ΡΠ° Π½Π΅ ΡΠ°Π²Π½Ρ, ΡΠ΅Π»Π΅ΡΠΎΠΎΠ±ΡΠ°Π·Π½ΠΎ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ ΡΡΠΎΡ Π°Π»Π³ΠΎΡΠΈΡΠΌ.
Π€ΠΎΡΠΌΡΠ»ΠΈΡΠΎΠ²ΠΊΠ° Π·Π°Π΄Π°ΡΠΈ. ΠΠΌΠ΅Π΅ΡΡΡ Π³ΡΠ°Ρ. ΠΠ΅ΠΊΠΎΡΠΎΡΠ°Ρ Π΅Π³ΠΎ Π²Π΅ΡΡΠΈΠ½Π° ΠΎΠ±ΠΎΠ·Π½Π°ΡΠ΅Π½Π° ΠΊΠ°ΠΊ Π²Π΅ΡΡΠΈΠ½Π° 1. ΠΠ΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ Π½Π°ΠΉΡΠΈ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠ΅ ΠΏΡΡΠΈ ΠΎΡ Π²Π΅ΡΡΠΈΠ½Ρ 1 Π΄ΠΎ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΈΠ· Π²Π΅ΡΡΠΈΠ½ Π³ΡΠ°ΡΠ°. ΠΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠΌ ΠΏΡΡΡΠΌ Π±ΡΠ΄Π΅ΠΌ Π½Π°Π·ΡΠ²Π°ΡΡ ΠΏΡΡΡ Ρ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠΉ ΡΡΠΌΠΌΠΎΠΉ ΡΠ΅Π½ Π²Π΄ΠΎΠ»Ρ ΠΏΡΡΠΈ. Π¦Π΅Π½ΠΎΠΉ Π½Π°Π·ΠΎΠ²Π΅ΠΌ Π½Π΅ΠΎΡΡΠΈΡΠ°ΡΠ΅Π»ΡΠ½ΠΎΠ΅ ΡΠΈΡΠ»ΠΎ ΡΠ²Π»ΡΡΡΠ΅Π΅ΡΡ Π²Π΅ΡΠΎΠΌ ΡΠ΅Π±ΡΠ°.
ΠΠ΄Π΅Ρ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°. ΠΠ΄Π΅Ρ ΠΎΡΠ½ΠΎΠ²ΡΠ²Π°Π΅ΡΡΡ Π½Π° ΡΠ»Π΅Π΄ΡΡΡΠ΅ΠΌ ΠΎΡΠ΅Π²ΠΈΠ΄Π½ΠΎΠΌ ΡΡΠ²Π΅ΡΠΆΠ΄Π΅Π½ΠΈΠΈ: ΠΡΡΡΡ ΠΏΠΎΡΡΡΠΎΠ΅Π½ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠΉ ΠΏΡΡΡ ΠΈΠ· Π²Π΅ΡΡΠΈΠ½Ρ Π° Π² Π²Π΅ΡΡΠΈΠ½Ρ B. Π ΠΏΡΡΡΡ Π²Π΅ΡΡΠΈΠ½Π° B ΡΠ²ΡΠ·Π°Π½Π° Ρ Π½Π΅ΠΊΠΎΡΠΎΡΡΠΌ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎΠΌ Π²Π΅ΡΡΠΈΠ½ i. ΠΠ±ΠΎΠ·Π½Π°ΡΠΈΠΌ ΡΠ΅ΡΠ΅Π· Ci - ΡΠ΅Π½Ρ ΠΏΡΡΠΈ ΠΈΠ· Π²Π΅ΡΡΠΈΠ½Ρ B Π² Π²Π΅ΡΡΠΈΠ½Ρ i. ΠΡΠ±Π΅ΡΠ΅ΠΌ ΠΈΠ· Ci ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΡ Π²Π΅Π»ΠΈΡΠΈΠ½Ρ. Π’ΠΎΠ³Π΄Π° ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅ ΠΏΡΠΎΠ΄ΠΎΠ»ΠΆΠ΅Π½ΠΈΠ΅ ΠΏΡΡΠΈ ΠΈΠ· ΡΠΎΡΠΊΠΈ B ΠΏΠΎΠΉΠ΄ΡΡ ΡΠ΅ΡΠ΅Π· Π²ΡΠ±ΡΠ°Π½Π½ΡΡ Π²Π΅Π»ΠΈΡΠΈΠ½Ρ.
ΠΡΠΎ ΡΡΠ²Π΅ΡΠΆΠ΄Π΅Π½ΠΈΠ΅ Π΄Π΅ΠΉΡΡΠ²ΠΈΡΠ΅Π»ΡΠ½ΠΎ Π½Π΅ ΡΡΠ΅Π±ΡΠ΅Ρ Π΄ΠΎΠΊΠ°Π·Π°ΡΠ΅Π»ΡΡΡΠ²Π°. Π ΠΈΠ· Π½Π΅Π³ΠΎ Π²ΡΡΠ΅ΠΊΠ°Π΅Ρ ΠΎΡΠ΅Π½Ρ ΡΠ΅ΡΡΡΠ·Π½ΠΎΠ΅ ΡΠ»Π΅Π΄ΡΡΠ²ΠΈΠ΅. ΠΡΡΡΡ Π΅ΡΡΡ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½ ΡΠ΅ΡΠ΅Π· ΠΊΠΎΡΠΎΡΡΠ΅ ΡΠΆΠ΅ ΠΏΡΠΎΡ ΠΎΠ΄ΡΡ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠ΅ ΠΏΡΡΠΈ. Π’Π°ΠΊΠΎΠ΅ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π³Π°ΡΠ°Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎ Π΅ΡΡΡ, ΡΡΠΎ Π²Π΅ΡΡΠΈΠ½Π° 1. Π£ΡΠ²Π΅ΡΠΆΠ΄Π΅Π½ΠΈΠ΅ ΡΡΠΎΡΠΌΡΠ»ΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠ΅ Π²ΡΡΠ΅ Π΄Π°ΡΡ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡΡ Π΄ΠΎΠ±Π°Π²Π»ΡΡΡ ΠΊ ΡΠΆΠ΅ ΡΡΡΠ΅ΡΡΠ²ΡΡΡΠ΅ΠΌΡ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Ρ Π²Π΅ΡΡΠΈΠ½ (Π±ΡΠ΄Π΅ΠΌ Π΄Π°Π»Π΅Π΅ Π½Π°Π·ΡΠ²Π°ΡΡ ΠΈΡ Π²ΡΠ΄Π΅Π»Π΅Π½Π½ΡΠΌΠΈ) Π΅ΡΠ΅ ΠΎΠ΄Π½Ρ Π²Π΅ΡΡΠΈΠ½Ρ, Π° ΡΠ°ΠΊ ΠΊΠ°ΠΊ Π² Π³ΡΠ°ΡΠ΅ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½ ΠΊΠΎΠ½Π΅ΡΠ½ΠΎ, ΡΠΎ Π·Π° ΠΊΠΎΠ½Π΅ΡΠ½ΠΎΠ΅ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΠ°Π³ΠΎΠ² Π²ΡΠ΅ Π²Π΅ΡΡΠΈΠ½Ρ Π³ΡΠ°ΡΠ° ΠΎΠΊΠ°ΠΆΡΡΡΡ Π²ΡΠ΄Π΅Π»Π΅Π½Π½ΡΠΌΠΈ, Π° ΡΡΠΎ ΠΈ Π±ΡΠ΄Π΅Ρ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ΠΌ.
Π‘ΡΡΠ½ΠΎΡΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΠΠ΅ΠΉΠΊΡΡΡΡ ΠΈ Π·Π°ΠΊΠ»ΡΡΠ°Π΅ΡΡΡ Π² ΠΏΡΠΎΡΠ΅Π΄ΡΡΠ΅ Π΄ΠΎΠ±Π°Π²Π»Π΅Π½ΠΈΡ Π΅ΡΠ΅ ΠΎΠ΄Π½ΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ ΠΊ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Ρ Π²ΡΠ΄Π΅Π»Π΅Π½Π½ΡΡ . ΠΡΠ° ΠΏΡΠΎΡΠ΅Π΄ΡΡΠ° ΡΠΎΡΡΠΎΠΈΡ ΠΈΠ· Π΄Π²ΡΡ ΡΠ°Π³ΠΎΠ²:
1. Π‘ΡΡΠΎΠΈΠΌ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½ ΠΈΠ½ΡΠΈΠ΄Π΅Π½ΡΠ½ΡΡ Π²ΡΠ΄Π΅Π»Π΅Π½Π½ΡΠΌ ΠΈ Π½Π°Ρ ΠΎΠ΄ΠΈΠΌ ΡΡΠ΅Π΄ΠΈ ΠΈΡ Π²Π΅ΡΡΠΈΠ½Ρ Ρ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠ΅ΠΉ ΡΠ΅Π½ΠΎΠΉ. ΠΠ°ΠΉΠ΄Π΅Π½Π½Π°Ρ Π²Π΅ΡΡΠΈΠ½Π° Π΄ΠΎΠ±Π°Π²Π»ΡΠ΅ΡΡΡ Π² ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π²ΡΠ΄Π΅Π»Π΅Π½Π½ΡΡ .
2. Π‘ΡΡΠΎΠΈΠΌ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½ ΠΈΠ½ΡΠΈΠ΄Π΅Π½ΡΠ½ΡΡ Π²ΡΠ΄Π΅Π»Π΅Π½Π½ΡΠΌ ΠΈ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΠ΅ΠΌ Π΄Π»Ρ Π½ΠΈΡ Π½ΠΎΠ²ΡΠ΅ ΡΠ΅Π½Ρ. ΠΠΎΠ²Π°Ρ ΡΠ΅Π½Π° Π²Π΅ΡΡΠΈΠ½Ρ ΡΡΠΎ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½Π°Ρ ΡΠ΅Π½Π° ΠΏΡΡΠΈ ΠΎΡ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° Π²ΡΠ΄Π΅Π»Π΅Π½Π½ΡΡ Π²Π΅ΡΡΠΈΠ½ Π΄ΠΎ Π΄Π°Π½Π½ΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ. Π‘ΡΡΠΎΠΈΡΡΡ Π½ΠΎΠ²Π°Ρ ΡΠ΅Π½Π° ΡΠ°ΠΊ:
a. ΠΠ»Ρ Π½Π΅Π²ΡΠ΄Π΅Π»Π΅Π½Π½ΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ Π²ΠΎ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π΅ Π²ΡΠ΄Π΅Π»Π΅Π½Π½ΡΡ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΠ΅ΡΡΡ ΠΏΠΎΠ΄ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½ ΠΈΠ½ΡΠΈΠ΄Π΅Π½ΡΠ½ΡΡ Π΄Π°Π½Π½ΠΎΠΉ.
b. ΠΠ»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ Π²ΡΠ΄Π΅Π»Π΅Π½Π½ΠΎΠΉ ΠΏΠΎΠ΄ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΠ΅ΡΡΡ ΡΠ΅Π½Π° ΠΏΡΡΠΈ Π΄ΠΎ Π΄Π°Π½Π½ΠΎΠΉ.
c. ΠΠΏΡΠ΅Π΄Π΅Π»ΡΠ΅ΡΡΡ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½Π°Ρ ΡΠ΅Π½Π°. ΠΡΠ° ΡΠ΅Π½Π° ΠΈ ΡΡΠ°Π½ΠΎΠ²ΠΈΡΡΡ ΡΠ΅Π½ΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ.
ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΡΠ°Π±ΠΎΡΠ°Π΅Ρ Ρ Π΄Π²ΡΠΌΡ ΡΠΈΠΏΠ°ΠΌΠΈ ΡΠ΅Π½: ΡΠ΅Π½ΠΎΠΉ ΡΠ΅Π±ΡΠ° ΠΈ ΡΠ΅Π½ΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ. Π¦Π΅Π½Ρ ΡΠ΅Π±Π΅Ρ ΡΠ²Π»ΡΡΡΡΡ ΠΏΠΎΡΡΠΎΡΠ½Π½ΠΎΠΉ Π²Π΅Π»ΠΈΡΠΈΠ½ΠΎΠΉ. Π¦Π΅Π½Ρ ΠΆΠ΅ Π²Π΅ΡΡΠΈΠ½ ΠΏΠΎΡΡΠΎΡΠ½Π½ΠΎ ΠΏΠ΅ΡΠ΅ΡΡΠΈΡΡΠ²Π°ΡΡΡΡ. Π‘ΠΌΡΡΠ» ΡΡΠΈΡ ΡΠ΅Π½ ΡΠ°Π·Π»ΠΈΡΠ΅Π½. Π¦Π΅Π½Π° ΡΠ΅Π±ΡΠ° ΡΡΠΎ ΡΠ΅Π½Π° ΠΏΠ΅ΡΠ΅Ρ ΠΎΠ΄Π° ΠΈΠ· Π²Π΅ΡΡΠΈΠ½Ρ Π² Π²Π΅ΡΡΠΈΠ½Ρ ΡΠΎΠ΅Π΄ΠΈΠ½ΡΠ½Π½ΡΡ ΡΡΠΈΠΌ ΡΠ΅Π±ΡΠΎΠΌ. Π ΡΠ΅Π½Π° Π²Π΅ΡΡΠΈΠ½Ρ ΡΡΠΎ ΡΠ΅Π½Π° ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΏΡΡΠΈ. ΠΡΡ ΠΎΠ΄Π½ΠΎ Π²Π°ΠΆΠ½ΠΎΠ΅ Π·Π°ΠΌΠ΅ΡΠ°Π½ΠΈΠ΅ ΠΊΠ°ΡΠ°Π΅ΡΡΡ ΠΏΠ΅ΡΠ΅ΡΡΠ΅ΡΠ° ΠΏΡΠ΅Π΄Π²Π°ΡΠΈΡΠ΅Π»ΡΠ½ΡΡ ΡΠ΅Π½. Π€Π°ΠΊΡΠΈΡΠ΅ΡΠΊΠΈ, Π΅ΡΡΡ ΡΠΌΡΡΠ» ΠΏΠ΅ΡΠ΅ΡΡΠΈΡΡΠ²Π°ΡΡ ΠΏΡΠ΅Π΄Π²Π°ΡΠΈΡΠ΅Π»ΡΠ½ΡΠ΅ ΡΠ΅Π½Ρ ΡΠΎΠ»ΡΠΊΠΎ Π΄Π»Ρ ΡΠ΅Ρ Π²Π΅ΡΡΠΈΠ½ ΠΊΠΎΡΠΎΡΡΠ΅ ΡΠ²ΡΠ·Π°Π½Ρ Ρ Π²Π΅ΡΡΠΈΠ½ΠΎΠΉ Π΄ΠΎΠ±Π°Π²Π»Π΅Π½Π½ΠΎΠΉ Π²ΠΎ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π²ΡΠ΄Π΅Π»Π΅Π½Π½ΡΡ Π½Π° ΠΏΠΎΡΠ»Π΅Π΄Π½Π΅ΠΌ ΡΠ°Π³Π΅, ΡΠ°ΠΊ ΠΊΠ°ΠΊ Π΄Π»Ρ Π΄ΡΡΠ³ΠΈΡ Π²Π΅ΡΡΠΈΠ½ Π½Π΅Ρ ΠΏΡΠΈΡΠΈΠ½ ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΡ ΠΏΡΠ΅Π΄Π²Π°ΡΠΈΡΠ΅Π»ΡΠ½ΠΎΠΉ ΡΠ΅Π½Ρ.
ΠΠ·Π²Π΅ΡΡΠ½ΠΎ, ΡΡΠΎ Π²ΡΠ΅ ΡΠ΅Π½Ρ (Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, ΠΏΡΠΎΠΊΠ»Π°Π΄ΠΊΠΈ ΠΏΡΡΠΈ ΠΈΠ»ΠΈ ΠΏΡΠΎΠ΅Π·Π΄Π°) Π½Π΅ΠΎΡΡΠΈΡΠ°ΡΠ΅Π»ΡΠ½Ρ. ΠΠ°ΠΉΡΠΈ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΡΡ ΡΡΠΎΠΈΠΌΠΎΡΡΡ ΠΏΡΡΠΈ 1->i Π΄Π»Ρ Π²ΡΠ΅Ρ i=1. n Π·Π° Π²ΡΠ΅ΠΌΡ O (n2).
Π ΠΏΡΠΎΡΠ΅ΡΡΠ΅ ΡΠ°Π±ΠΎΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° Π½Π΅ΠΊΠΎΡΠΎΡΡΠ΅ Π³ΠΎΡΠΎΠ΄Π° Π±ΡΠ΄ΡΡ Π²ΡΠ΄Π΅Π»Π΅Π½Π½ΡΠΌΠΈ (Π² Π½Π°ΡΠ°Π»Π΅ — ΡΠΎΠ»ΡΠΊΠΎ Π³ΠΎΡΠΎΠ΄ 1, Π² ΠΊΠΎΠ½ΡΠ΅ — Π²ΡΠ΅). ΠΡΠΈ ΡΡΠΎΠΌ:
Π΄Π»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ Π²ΡΠ΄Π΅Π»Π΅Π½Π½ΠΎΠ³ΠΎ Π³ΠΎΡΠΎΠ΄Π° i Ρ ΡΠ°Π½ΠΈΡΡΡ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠ°Ρ ΡΡΠΎΠΈΠΌΠΎΡΡΡ ΠΏΡΡΠΈ 1->i; ΠΏΡΠΈ ΡΡΠΎΠΌ ΠΈΠ·Π²Π΅ΡΡΠ½ΠΎ, ΡΡΠΎ ΠΌΠΈΠ½ΠΈΠΌΡΠΌ Π΄ΠΎΡΡΠΈΠ³Π°Π΅ΡΡΡ Π½Π° ΠΏΡΡΠΈ, ΠΏΡΠΎΡ ΠΎΠ΄ΡΡΠ΅ΠΌ ΡΠΎΠ»ΡΠΊΠΎ ΡΠ΅ΡΠ΅Π· Π²ΡΠ΄Π΅Π»Π΅Π½Π½ΡΠ΅ Π³ΠΎΡΠΎΠ΄Π°;
Π΄Π»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ Π½Π΅Π²ΡΠ΄Π΅Π»Π΅Π½Π½ΠΎΠ³ΠΎ Π³ΠΎΡΠΎΠ΄Π° i Ρ ΡΠ°Π½ΠΈΡΡΡ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠ°Ρ ΡΡΠΎΠΈΠΌΠΎΡΡΡ ΠΏΡΡΠΈ 1->i, Π² ΠΊΠΎΡΠΎΡΠΎΠΌ Π² ΠΊΠ°ΡΠ΅ΡΡΠ²Π΅ ΠΏΡΠΎΠΌΠ΅ΠΆΡΡΠΎΡΠ½ΡΡ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΡΡΡΡ ΡΠΎΠ»ΡΠΊΠΎ Π²ΡΠ΄Π΅Π»Π΅Π½Π½ΡΠ΅ Π³ΠΎΡΠΎΠ΄Π°.
ΠΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π²ΡΠ΄Π΅Π»Π΅Π½Π½ΡΡ Π³ΠΎΡΠΎΠ΄ΠΎΠ² ΡΠ°ΡΡΠΈΡΡΠ΅ΡΡΡ Π½Π° ΠΎΡΠ½ΠΎΠ²Π°Π½ΠΈΠΈ ΡΠ»Π΅Π΄ΡΡΡΠ΅Π³ΠΎ Π·Π°ΠΌΠ΅ΡΠ°Π½ΠΈΡ: Π΅ΡΠ»ΠΈ ΡΡΠ΅Π΄ΠΈ Π²ΡΠ΅Ρ Π½Π΅Π²ΡΠ΄Π΅Π»Π΅Π½Π½ΡΡ Π³ΠΎΡΠΎΠ΄ΠΎΠ² Π²Π·ΡΡΡ ΡΠΎΡ, Π΄Π»Ρ ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ Ρ ΡΠ°Π½ΠΈΠΌΠΎΠ΅ ΡΠΈΡΠ»ΠΎ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎ, ΡΠΎ ΡΡΠΎ ΡΠΈΡΠ»ΠΎ ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΈΡΡΠΈΠ½Π½ΠΎΠΉ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠ΅ΠΉ ΡΡΠΎΠΈΠΌΠΎΡΡΡΡ. Π ΡΠ°ΠΌΠΎΠΌ Π΄Π΅Π»Π΅, ΠΏΡΡΡΡ Π΅ΡΡΡ Π±ΠΎΠ»Π΅Π΅ ΠΊΠΎΡΠΎΡΠΊΠΈΠΉ ΠΏΡΡΡ. Π Π°ΡΡΠΌΠΎΡΡΠΈΠΌ ΠΏΠ΅ΡΠ²ΡΠΉ Π½Π΅Π²ΡΠ΄Π΅Π»Π΅Π½Π½ΡΠΉ Π³ΠΎΡΠΎΠ΄ Π½Π° ΡΡΠΎΠΌ ΠΏΡΡΠΈ — ΡΠΆΠ΅ Π΄ΠΎ Π½Π΅Π³ΠΎ ΠΏΡΡΡ Π΄Π»ΠΈΠ½Π½Π΅Π΅! (ΠΠ΄Π΅ΡΡ ΡΡΡΠ΅ΡΡΠ²Π΅Π½Π½Π° Π½Π΅ΠΎΡΡΠΈΡΠ°ΡΠ΅Π»ΡΠ½ΠΎΡΡΡ ΡΠ΅Π½.)
ΠΠΎΠ±Π°Π²ΠΈΠ² Π²ΡΠ±ΡΠ°Π½Π½ΡΠΉ Π³ΠΎΡΠΎΠ΄ ΠΊ Π²ΡΠ΄Π΅Π»Π΅Π½Π½ΡΠΌ, ΠΌΡ Π΄ΠΎΠ»ΠΆΠ½Ρ ΡΠΊΠΎΡΡΠ΅ΠΊΡΠΈΡΠΎΠ²Π°ΡΡ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΡ, Ρ ΡΠ°Π½ΠΈΠΌΡΡ Π΄Π»Ρ Π½Π΅Π²ΡΠ΄Π΅Π»Π΅Π½Π½ΡΡ Π³ΠΎΡΠΎΠ΄ΠΎΠ². ΠΡΠΈ ΡΡΠΎΠΌ Π΄ΠΎΡΡΠ°ΡΠΎΡΠ½ΠΎ ΡΡΠ΅ΡΡΡ Π»ΠΈΡΡ ΠΏΡΡΠΈ, Π² ΠΊΠΎΡΠΎΡΡΡ Π½ΠΎΠ²ΡΠΉ Π³ΠΎΡΠΎΠ΄ ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΏΠΎΡΠ»Π΅Π΄Π½ΠΈΠΌ ΠΏΡΠ½ΠΊΡΠΎΠΌ ΠΏΠ΅ΡΠ΅ΡΠ°Π΄ΠΊΠΈ, Π° ΡΡΠΎ Π»Π΅Π³ΠΊΠΎ ΡΠ΄Π΅Π»Π°ΡΡ, ΡΠ°ΠΊ ΠΊΠ°ΠΊ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΡ ΡΡΠΎΠΈΠΌΠΎΡΡΡ ΠΏΡΡΠΈ Π² Π½ΠΎΠ²ΡΠΉ Π³ΠΎΡΠΎΠ΄ ΠΌΡ ΡΠΆΠ΅ Π·Π½Π°Π΅ΠΌ.
ΠΡΡΠ³ΠΈΠΌΠΈ ΡΠ»ΠΎΠ²Π°ΠΌΠΈ, ΠΊΠ°ΠΆΠ΄ΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Π΅ ΠΈΠ· V ΡΠΎΠΏΠΎΡΡΠ°Π²ΠΈΠΌ ΠΌΠ΅ΡΠΊΡ — ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅ ΠΈΠ·Π²Π΅ΡΡΠ½ΠΎΠ΅ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠ΅ ΠΎΡ ΡΡΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ Π΄ΠΎ a. ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΡΠ°Π±ΠΎΡΠ°Π΅Ρ ΠΏΠΎΡΠ°Π³ΠΎΠ²ΠΎ — Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΡΠ°Π³Π΅ ΠΎΠ½ «ΠΏΠΎΡΠ΅ΡΠ°Π΅Ρ» ΠΎΠ΄Π½Ρ Π²Π΅ΡΡΠΈΠ½Ρ ΠΈ ΠΏΡΡΠ°Π΅ΡΡΡ ΡΠΌΠ΅Π½ΡΡΠ°ΡΡ ΠΌΠ΅ΡΠΊΠΈ. Π Π°Π±ΠΎΡΠ° Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° Π·Π°Π²Π΅ΡΡΠ°Π΅ΡΡΡ, ΠΊΠΎΠ³Π΄Π° Π²ΡΠ΅ Π²Π΅ΡΡΠΈΠ½Ρ ΠΏΠΎΡΠ΅ΡΠ΅Π½Ρ.
ΠΠ½ΠΈΡΠΈΠ°Π»ΠΈΠ·Π°ΡΠΈΡ. ΠΠ΅ΡΠΊΠ° ΡΠ°ΠΌΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ a ΠΏΠΎΠ»Π°Π³Π°Π΅ΡΡΡ ΡΠ°Π²Π½ΠΎΠΉ 0, ΠΌΠ΅ΡΠΊΠΈ ΠΎΡΡΠ°Π»ΡΠ½ΡΡ Π²Π΅ΡΡΠΈΠ½ — Π±Π΅ΡΠΊΠΎΠ½Π΅ΡΠ½ΠΎΡΡΠΈ. ΠΡΠΎ ΠΎΡΡΠ°ΠΆΠ°Π΅Ρ ΡΠΎ, ΡΡΠΎ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΡ ΠΎΡ a Π΄ΠΎ Π΄ΡΡΠ³ΠΈΡ Π²Π΅ΡΡΠΈΠ½ ΠΏΠΎΠΊΠ° Π½Π΅ΠΈΠ·Π²Π΅ΡΡΠ½Ρ. ΠΡΠ΅ Π²Π΅ΡΡΠΈΠ½Ρ Π³ΡΠ°ΡΠ° ΠΏΠΎΠΌΠ΅ΡΠ°ΡΡΡΡ ΠΊΠ°ΠΊ Π½Π΅ΠΏΠΎΡΠ΅ΡΠ΅Π½Π½ΡΠ΅.
Π¨Π°Π³ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°. ΠΡΠ»ΠΈ Π²ΡΠ΅ Π²Π΅ΡΡΠΈΠ½Ρ ΠΏΠΎΡΠ΅ΡΠ΅Π½Ρ, Π°Π»Π³ΠΎΡΠΈΡΠΌ Π·Π°Π²Π΅ΡΡΠ°Π΅ΡΡΡ. Π ΠΏΡΠΎΡΠΈΠ²Π½ΠΎΠΌ ΡΠ»ΡΡΠ°Π΅ ΠΈΠ· Π΅ΡΠ΅ Π½Π΅ ΠΏΠΎΡΠ΅ΡΠ΅Π½Π½ΡΡ Π²Π΅ΡΡΠΈΠ½ Π²ΡΠ±ΠΈΡΠ°Π΅ΡΡΡ Π²Π΅ΡΡΠΈΠ½Π° u, ΠΈΠΌΠ΅ΡΡΠ°Ρ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΡ ΠΌΠ΅ΡΠΊΡ. ΠΡ ΡΠ°ΡΡΠΌΠ°ΡΡΠΈΠ²Π°Π΅ΠΌ Π²ΡΠ΅Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΡΠ΅ ΠΌΠ°ΡΡΡΡΡΡ, Π² ΠΊΠΎΡΠΎΡΡΡ u ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΏΡΠ΅Π΄ΠΏΠΎΡΠ»Π΅Π΄Π½ΠΈΠΌ ΠΏΡΠ½ΠΊΡΠΎΠΌ. ΠΠ΅ΡΡΠΈΠ½Ρ, ΡΠΎΠ΅Π΄ΠΈΠ½Π΅Π½Π½ΡΠ΅ Ρ Π²Π΅ΡΡΠΈΠ½ΠΎΠΉ u ΡΠ΅Π±ΡΠ°ΠΌΠΈ, Π½Π°Π·ΠΎΠ²Π΅ΠΌ ΡΠΎΡΠ΅Π΄ΡΠΌΠΈ ΡΡΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ. ΠΠ»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΡΠΎΡΠ΅Π΄Π° ΡΠ°ΡΡΠΌΠΎΡΡΠΈΠΌ Π½ΠΎΠ²ΡΡ Π΄Π»ΠΈΠ½Ρ ΠΏΡΡΠΈ, ΡΠ°Π²Π½ΡΡ ΡΡΠΌΠΌΠ΅ ΡΠ΅ΠΊΡΡΠ΅ΠΉ ΠΌΠ΅ΡΠΊΠΈ u ΠΈ Π΄Π»ΠΈΠ½Ρ ΡΠ΅Π±ΡΠ°, ΡΠΎΠ΅Π΄ΠΈΠ½ΡΡΡΠ΅Π³ΠΎ u Ρ ΡΡΠΈΠΌ ΡΠΎΡΠ΅Π΄ΠΎΠΌ. ΠΡΠ»ΠΈ ΠΏΠΎΠ»ΡΡΠ΅Π½Π½Π°Ρ Π΄Π»ΠΈΠ½Π° ΠΌΠ΅Π½ΡΡΠ΅ ΠΌΠ΅ΡΠΊΠΈ ΡΠΎΡΠ΅Π΄Π°, Π·Π°ΠΌΠ΅Π½ΠΈΠΌ ΠΌΠ΅ΡΠΊΡ ΡΡΠΎΠΉ Π΄Π»ΠΈΠ½ΠΎΠΉ. Π Π°ΡΡΠΌΠΎΡΡΠ΅Π² Π²ΡΠ΅Ρ ΡΠΎΡΠ΅Π΄Π΅ΠΉ, ΠΏΠΎΠΌΠ΅ΡΠΈΠΌ Π²Π΅ΡΡΠΈΠ½Ρ u ΠΊΠ°ΠΊ ΠΏΠΎΡΠ΅ΡΠ΅Π½Π½ΡΡ ΠΈ ΠΏΠΎΠ²ΡΠΎΡΠΈΠΌ ΡΠ°Π³.
ΠΠΎΡΠΊΠΎΠ»ΡΠΊΡ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΠ΅ΠΉΠΊΡΡΡΡ Π²ΡΡΠΊΠΈΠΉ ΡΠ°Π· Π²ΡΠ±ΠΈΡΠ°Π΅Ρ Π΄Π»Ρ ΠΎΠ±ΡΠ°Π±ΠΎΡΠΊΠΈ Π²Π΅ΡΡΠΈΠ½Ρ Ρ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠ΅ΠΉ ΠΎΡΠ΅Π½ΠΊΠΎΠΉ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠ΅Π³ΠΎ ΠΏΡΡΠΈ, ΠΌΠΎΠΆΠ½ΠΎ ΡΠΊΠ°Π·Π°ΡΡ, ΡΡΠΎ ΠΎΠ½ ΠΎΡΠ½ΠΎΡΠΈΡΡΡ ΠΊ ΠΆΠ°Π΄Π½ΡΠΌ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°ΠΌ.
ΠΠΏΠΈΡΠ΅ΠΌ Π±ΠΎΠ»Π΅Π΅ ΠΏΠΎΠ΄ΡΠΎΠ±Π½ΠΎ ΡΡ Π΅ΠΌΡ ΡΠ°Π±ΠΎΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΠΠ΅ΠΉΠΊΡΡΡΡ.
ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅Ρ ΡΡΠΈ ΠΌΠ°ΡΡΠΈΠ²Π° ΠΈΠ· N (= ΡΠΈΡΠ»Ρ Π²Π΅ΡΡΠΈΠ½ ΡΠ΅ΡΠΈ) ΡΠΈΡΠ΅Π» ΠΊΠ°ΠΆΠ΄ΡΠΉ. ΠΠ΅ΡΠ²ΡΠΉ ΠΌΠ°ΡΡΠΈΠ² A ΡΠΎΠ΄Π΅ΡΠΆΠΈΡ ΠΌΠ΅ΡΠΊΠΈ Ρ Π΄Π²ΡΠΌΡ Π·Π½Π°ΡΠ΅Π½ΠΈΡ: 0 (Π²Π΅ΡΡΠΈΠ½Π° Π΅ΡΠ΅ Π½Π΅ ΡΠ°ΡΡΠΌΠΎΡΡΠ΅Π½Π°) ΠΈ 1 (Π²Π΅ΡΡΠΈΠ½Π° ΡΠΆΠ΅ ΡΠ°ΡΡΠΌΠΎΡΡΠ΅Π½Π°); Π²ΡΠΎΡΠΎΠΉ ΠΌΠ°ΡΡΠΈΠ² B ΡΠΎΠ΄Π΅ΡΠΆΠΈΡ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΡ — ΡΠ΅ΠΊΡΡΠΈΠ΅ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠΈΠ΅ ΡΠ°Ρ — ΡΡΠΎΡΠ½ΠΈΡ ΠΎΡ Π΄ΠΎ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠ΅ΠΉ Π²Π΅ΡΡΠΈΠ½Ρ; ΡΡΠ΅ΡΠΈΠΉ ΠΌΠ°ΡΡΠΈΠ² Ρ ΡΠΎΠ΄Π΅ΡΠΆΠΈΡ Π½ΠΎΠΌΠ΅ΡΠ° Π²Π΅ΡΡΠΈΠ½ — k-ΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ Π‘ [k] Π΅ΡΡΡ Π½ΠΎΠΌΠ΅Ρ ΠΏΡΠ΅Π΄ΠΏΠΎΡΠ»Π΅Π΄Π½Π΅ΠΉ Π²Π΅ΡΡΠΈΠ½Ρ Π½Π° ΡΠ΅ΠΊΡΡΠ΅ΠΌ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠ΅ΠΌ ΠΏΡΡΠΈ ΠΈΠ· Vi Π² Vk. ΠΠ°ΡΡΠΈΡΠ° ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠΉ D [i, k] Π·Π°Π΄Π°Π΅Ρ Π΄Π»ΠΈΠ½Ρ Π΄ΡΠ³Π΅ D [i, k]; Π΅ΡΠ»ΠΈ ΡΠ°ΠΊΠΎΠΉ Π΄ΡΠ³ΠΈ Π½Π΅Ρ, ΡΠΎ D [i, k] ΠΏΡΠΈΡΠ²Π°ΠΈΠ²Π°Π΅ΡΡΡ Π±ΠΎΠ»ΡΡΠΎΠ΅ ΡΠΈΡΠ»ΠΎ Π, ΡΠ°Π²Π½ΠΎΠ΅ «ΠΌΠ°ΡΠΈΠ½Π½ΠΎΠΉ Π±Π΅ΡΠΊΠΎΠ½Π΅ΡΠ½ΠΎΡΡΠΈ» .
Π’Π΅ΠΏΠ΅ΡΡ ΠΌΠΎΠΆΠ½ΠΎ ΠΎΠΏΠΈΡΠ°ΡΡ:
1. (ΠΈΠ½ΠΈΡΠΈΠ°Π»ΠΈΠ·Π°ΡΠΈΡ). Π ΡΠΈΠΊΠ»Π΅ ΠΎΡ 1 Π΄ΠΎ N Π·Π°ΠΏΠΎΠ»Π½ΠΈΡΡ Π½ΡΠ»ΡΠΌΠΈ ΠΌΠ°ΡΡΠΈΠ² A; Π·Π°ΠΏΠΎΠ»Π½ΠΈΡΡ ΡΠΈΡΠ»ΠΎΠΌ i ΠΌΠ°ΡΡΠΈΠ² C; ΠΏΠ΅ΡΠ΅Π½Π΅ΡΡΠΈ i-Ρ ΡΡΡΠΎΠΊΡ ΠΌΠ°ΡΡΠΈΡΡ D Π² ΠΌΠ°ΡΡΠΈΠ² B, A [i]: =1; C [i]: =0 (i — Π½ΠΎΠΌΠ΅Ρ ΡΡΠ°ΡΡΠΎΠ²ΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ)
2. (ΠΎΠ±ΡΠΈΠΉ ΡΠ°Π³). HΠ°ΠΉΡΠΈ ΠΌΠΈΠ½ΠΈΠΌΡΠΌ ΡΡΠ΅Π΄ΠΈ Π½Π΅ΠΎΡΠΌΠ΅ΡΠ΅Π½Π½ΡΡ (Ρ.Π΅. ΡΠ΅Ρ k, Π΄Π»Ρ ΠΊΠΎΡΠΎΡΡΡ A [k] =0); ΠΏΡΡΡΡ ΠΌΠΈΠ½ΠΈΠΌΡΠΌ Π΄ΠΎΡΡΠΈΠ³Π°Π΅ΡΡΡ Π½Π° ΠΈΠ½Π΄Π΅ΠΊΡΠ΅ j, Ρ. Π΅. B [j] <=B [k] ΠΠ°ΡΠ΅ΠΌ Π²ΡΠΏΠΎΠ»Π½ΡΡΡΡΡ ΡΠ»Π΅Π΄ΡΡΡΠΈΠ΅ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΈ: A [j]: =1; Π΅ΡΠ»ΠΈ B [k] >B [j] +D [j, k], ΡΠΎ (B [k]: =B [j] +D [j, k]; C [k]: =j) (Π£ΡΠ»ΠΎΠ²ΠΈΠ΅ ΠΎΠ·Π½Π°ΡΠ°Π΅Ρ, ΡΡΠΎ ΠΏΡΡΡ Vi. Vk Π΄Π»ΠΈΠ½Π½Π΅Π΅, ΡΠ΅ΠΌ ΠΏΡΡΡ Vi. Vj Vk). (ΠΡΠ»ΠΈ Π²ΡΠ΅ A [k] ΠΎΡΠΌΠ΅ΡΠ΅Π½Ρ, ΡΠΎ Π΄Π»ΠΈΠ½Π° ΠΏΡΡΠΈ ΠΎΡ Vi Π΄ΠΎ Vk ΡΠ°Π²Π½Π° B [k]. Π’Π΅ΠΏΠ΅ΡΡ Π½Π°Π΄ΠΎ) ΠΏΠ΅ΡΠ΅ΡΠΈΡΠ»ΠΈΡΡ Π²Π΅ΡΡΠΈΠ½Ρ, Π²Ρ ΠΎΠ΄ΡΡΠΈΠ΅ Π² ΠΊΡΠ°ΡΡΠ°ΠΉΡΠΈΠΉ ΠΏΡΡΡ).
3. (Π²ΡΠ΄Π°ΡΠ° ΠΎΡΠ²Π΅ΡΠ°). (ΠΡΡΡ ΠΎΡ Vi Π΄ΠΎ Vk Π²ΡΠ΄Π°Π΅ΡΡΡ Π² ΠΎΠ±ΡΠ°ΡΠ½ΠΎΠΌ ΠΏΠΎΡΡΠ΄ΠΊΠ΅ ΡΠ»Π΅Π΄ΡΡΡΠ΅ΠΉ ΠΏΡΠΎΡΠ΅Π΄ΡΡΠΎΠΉ:)
1. z: =C [k];
2. ΠΡΠ΄Π°ΡΡ z;
3. z: =C [z]. ΠΡΠ»ΠΈ z = Π, ΡΠΎ ΠΊΠΎΠ½Π΅Ρ, ΠΈΠ½Π°ΡΠ΅ ΠΏΠ΅ΡΠ΅ΠΉΡΠΈ ΠΊ 3.2.
ΠΠ»Ρ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° Π½ΡΠΆΠ½ΠΎ N ΡΠ°Π· ΠΏΡΠΎΡΠΌΠΎΡΡΠ΅ΡΡ ΠΌΠ°ΡΡΠΈΠ² B ΠΈΠ· N ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ², Ρ. Π΅. Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΠ΅ΠΉΠΊΡΡΡΡ ΠΈΠΌΠ΅Π΅Ρ ΠΊΠ²Π°Π΄ΡΠ°ΡΠΈΡΠ½ΡΡ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡ: O (n2).
ΠΠΈΠΆΠ΅ ΠΏΡΠΈΠ²Π΅Π΄Π΅Π½Π° Π±Π»ΠΎΠΊ-ΡΡ Π΅ΠΌΠ° Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΠΠ΅ΠΉΠΊΡΡΡΡ (ΡΠΌ. ΡΠΈΡ.2).
Π ΠΈΡ. 2. ΠΠ»ΠΎΠΊ-ΡΡ Π΅ΠΌΠ° Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΠΠ΅ΠΉΠΊΡΡΡΡ
Π Π½Π°ΡΠ°Π»Π΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠ΅ Π΄Π»Ρ Π½Π°ΡΠ°Π»ΡΠ½ΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ ΠΏΠΎΠ»Π°Π³Π°Π΅ΡΡΡ ΡΠ°Π²Π½ΡΠΌ Π½ΡΠ»Ρ, Π° Π²ΡΠ΅ ΠΎΡΡΠ°Π»ΡΠ½ΡΠ΅ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΡ Π·Π°ΠΏΠΎΠ»Π½ΡΡΡΡΡ Π±ΠΎΠ»ΡΡΠΈΠΌ ΠΏΠΎΠ»ΠΎΠΆΠΈΡΠ΅Π»ΡΠ½ΡΠΌ ΡΠΈΡΠ»ΠΎΠΌ (Π±ΠΎΠΌΠ»ΡΡΠΈΠΌ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΠ³ΠΎ ΠΏΡΡΠΈ Π² Π³ΡΠ°ΡΠ΅). ΠΠ°ΡΡΠΈΠ² ΡΠ»Π°Π³ΠΎΠ² Π·Π°ΠΏΠΎΠ»Π½ΡΠ΅ΡΡΡ Π½ΡΠ»ΡΠΌΠΈ. ΠΠ°ΡΠ΅ΠΌ Π·Π°ΠΏΡΡΠΊΠ°Π΅ΡΡΡ ΠΎΡΠ½ΠΎΠ²Π½ΠΎΠΉ ΡΠΈΠΊΠ».
ΠΠ° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΡΠ°Π³Π΅ ΡΠΈΠΊΠ»Π° ΠΌΡ ΠΈΡΠ΅ΠΌ Π²Π΅ΡΡΠΈΠ½Ρ Ρ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠΌ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠ΅ΠΌ ΠΈ ΡΠ»Π°Π³ΠΎΠΌ ΡΠ°Π²Π½ΡΠΌ Π½ΡΠ»Ρ. ΠΠ°ΡΠ΅ΠΌ ΠΌΡ ΡΡΡΠ°Π½Π°Π²Π»ΠΈΠ²Π°Π΅ΠΌ Π² Π½Π΅ΠΉ ΡΠ»Π°Π³ Π² 1 ΠΈ ΠΏΡΠΎΠ²Π΅ΡΡΠ΅ΠΌ Π²ΡΠ΅ ΡΠΎΡΠ΅Π΄Π½ΠΈΠ΅ Ρ Π½Π΅ΠΉ Π²Π΅ΡΡΠΈΠ½Ρ. ΠΡΠ»ΠΈ Π² Π½Π΅ΠΉ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠ΅ Π±ΠΎΠ»ΡΡΠ΅, ΡΠ΅ΠΌ ΡΡΠΌΠΌΠ° ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΡ Π΄ΠΎ ΡΠ΅ΠΊΡΡΠ΅ΠΉ Π²Π΅ΡΡΠΈΠ½Ρ ΠΈ Π΄Π»ΠΈΠ½Ρ ΡΠ΅Π±ΡΠ°, ΡΠΎ ΡΠΌΠ΅Π½ΡΡΠ°Π΅ΠΌ Π΅Π³ΠΎ. Π¦ΠΈΠΊΠ» Π·Π°Π²Π΅ΡΡΠ°Π΅ΡΡΡ ΠΊΠΎΠ³Π΄Π° ΡΠ»Π°Π³ΠΈ Π²ΡΠ΅Ρ Π²Π΅ΡΡΠΈΠ½ ΡΡΠ°Π½ΠΎΠ²ΡΡΡΡ ΡΠ°Π²Π½Ρ 1.
ΠΡΠ΅Π²Π΄ΠΎΠΊΠΎΠ΄ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΠΠ΅ΠΉΠΊΡΡΡΡ
ΠΠ±ΠΎΠ·Π½Π°ΡΠ΅Π½ΠΈΡ
V — ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½ Π³ΡΠ°ΡΠ°
E — ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ ΡΠ΅Π±Π΅Ρ Π³ΡΠ°ΡΠ°
w [ij] - Π²Π΅Ρ (Π΄Π»ΠΈΠ½Π°) ΡΠ΅Π±ΡΠ° ij
a — Π²Π΅ΡΡΠΈΠ½Π°, ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΡ ΠΎΡ ΠΊΠΎΡΠΎΡΠΎΠΉ ΠΈΡΡΡΡΡ
U — ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ ΠΏΠΎΡΠ΅ΡΠ΅Π½Π½ΡΡ Π²Π΅ΡΡΠΈΠ½
d [u] - ΠΏΠΎ ΠΎΠΊΠΎΠ½ΡΠ°Π½ΠΈΠΈ ΡΠ°Π±ΠΎΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΡΠ°Π²Π½ΠΎ Π΄Π»ΠΈΠ½Π΅ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠ΅Π³ΠΎ ΠΏΡΡΠΈ ΠΈΠ· a Π΄ΠΎ Π²Π΅ΡΡΠΈΠ½Ρ u
p [u] - ΠΏΠΎ ΠΎΠΊΠΎΠ½ΡΠ°Π½ΠΈΠΈ ΡΠ°Π±ΠΎΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΡΠΎΠ΄Π΅ΡΠΆΠΈΡ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠΈΠΉ ΠΏΡΡΡ ΠΈΠ· a Π² u
ΠΡΠ΅Π²Π΄ΠΎΠΊΠΎΠ΄ (ΡΠ·ΡΠΊ ΠΎΠΏΠΈΡΠ°Π½ΠΈΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°)
ΠΡΠΈΡΠ²ΠΎΠΈΠΌ
ΠΠ»Ρ Π²ΡΠ΅Ρ ΠΎΡΠ»ΠΈΡΠ½ΡΡ ΠΎΡ a
ΠΏΡΠΈΡΠ²ΠΎΠΈΠΌ
ΠΠΎΠΊΠ°
ΠΡΡΡΡ — Π²Π΅ΡΡΠΈΠ½Π° Ρ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠΌ d [v]
ΠΠ»Ρ Π²ΡΠ΅Ρ ΡΠ°ΠΊΠΈΡ , ΡΡΠΎ
Π΅ΡΠ»ΠΈ d [u] > d [v] + w [vu] ΡΠΎ
ΠΈΠ·ΠΌΠ΅Π½ΠΈΠΌ
ΠΈΠ·ΠΌΠ΅Π½ΠΈΠΌ
ΠΠΎΠΊΠ°Π·Π°ΡΠ΅Π»ΡΡΡΠ²ΠΎ ΠΊΠΎΡΡΠ΅ΠΊΡΠ½ΠΎΡΡΠΈ
ΠΡΡΡΡ l (v) — Π΄Π»ΠΈΠ½Π° ΠΊΡΠ°ΡΡΠ°ΠΉΡΠ΅Π³ΠΎ ΠΏΡΡΠΈ ΠΈΠ· Π²Π΅ΡΡΠΈΠ½Ρ a Π² Π²Π΅ΡΡΠΈΠ½Ρ v. ΠΠΎΠΊΠ°ΠΆΠ΅ΠΌ ΠΏΠΎ ΠΈΠ½Π΄ΡΠΊΡΠΈΠΈ, ΡΡΠΎ Π² ΠΌΠΎΠΌΠ΅Π½Ρ ΠΏΠΎΡΠ΅ΡΠ΅Π½ΠΈΡ Π»ΡΠ±ΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ z, d (z) =l (z).
ΠΠ°Π·Π°. ΠΠ΅ΡΠ²ΠΎΠΉ ΠΏΠΎΡΠ΅ΡΠ°Π΅ΡΡΡ Π²Π΅ΡΡΠΈΠ½Π° a. Π ΡΡΠΎΡ ΠΌΠΎΠΌΠ΅Π½Ρ d (a) =l (a) =0.
Π°Π»Π³ΠΎΡΠΈΡΠΌ Π΄Π΅ΠΉΠΊΡΡΡΠ° Π³ΡΠ°Ρ ΡΠΉΠ»Π΅Ρ Π¨Π°Π³. ΠΡΡΠΊΠ°ΠΉ ΠΌΡ Π²ΡΠ±ΡΠ°Π»ΠΈ Π΄Π»Ρ ΠΏΠΎΡΠ΅ΡΠ΅Π½ΠΈΡ Π²Π΅ΡΡΠΈΠ½Ρ. ΠΠΎΠΊΠ°ΠΆΠ΅ΠΌ, ΡΡΠΎ Π² ΡΡΠΎΡ ΠΌΠΎΠΌΠ΅Π½Ρ d (z) =l (z). ΠΠ»Ρ Π½Π°ΡΠ°Π»Π° ΠΎΡΠΌΠ΅ΡΠΈΠΌ, ΡΡΠΎ Π΄Π»Ρ Π»ΡΠ±ΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ v, Π²ΡΠ΅Π³Π΄Π° Π²ΡΠΏΠΎΠ»Π½ΡΠ΅ΡΡΡ (Π°Π»Π³ΠΎΡΠΈΡΠΌ Π½Π΅ ΠΌΠΎΠΆΠ΅Ρ Π½Π°ΠΉΡΠΈ ΠΏΡΡΡ ΠΊΠΎΡΠΎΡΠ΅, ΡΠ΅ΠΌ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠΈΠΉ ΠΈΠ· Π²ΡΠ΅Ρ ΡΡΡΠ΅ΡΡΠ²ΡΡΡΠΈΡ ). ΠΡΡΡΡ P — ΠΊΡΠ°ΡΡΠ°ΠΉΡΠΈΠΉ ΠΏΡΡΡ ΠΈΠ· a Π² z, y — ΠΏΠ΅ΡΠ²Π°Ρ Π½Π΅ΠΏΠΎΡΠ΅ΡΡΠ½Π½Π°Ρ Π²Π΅ΡΡΠΈΠ½Π° Π½Π° P, x — ΠΏΡΠ΅Π΄ΡΠ΅ΡΡΠ²ΡΡΡΠ°Ρ Π΅ΠΉ (ΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎ, ΠΏΠΎΡΠ΅ΡΡΠ½Π½Π°Ρ). ΠΠΎΡΠΊΠΎΠ»ΡΠΊΡ ΠΏΡΡΡ P ΠΊΡΠ°ΡΡΠ°ΠΉΡΠΈΠΉ, Π΅Π³ΠΎ ΡΠ°ΡΡΡ, Π²Π΅Π΄ΡΡΠ°Ρ ΠΈΠ· a ΡΠ΅ΡΠ΅Π· x Π² y, ΡΠΎΠΆΠ΅ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠ°Ρ, ΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎ l (y) =l (x) +w (xy). ΠΠΎ ΠΏΡΠ΅Π΄ΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΈΡ ΠΈΠ½Π΄ΡΠΊΡΠΈΠΈ, Π² ΠΌΠΎΠΌΠ΅Π½Ρ ΠΏΠΎΡΠ΅ΡΠ΅Π½ΠΈΡ Π²Π΅ΡΡΠΈΠ½Ρ x Π²ΡΠΏΠΎΠ»Π½ΡΠ»ΠΎΡΡ d (x) =l (x), ΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎ, Π²Π΅ΡΡΠΈΠ½Π° y ΡΠΎΠ³Π΄Π° ΠΏΠΎΠ»ΡΡΠΈΠ»Π° ΠΌΠ΅ΡΠΊΡ Π½Π΅ Π±ΠΎΠ»ΡΡΠ΅ ΡΠ΅ΠΌ d (x) +w (xy) =l (x) +w (xy) =l (y). Π‘Π»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎ, d (y) =l (y). Π‘ Π΄ΡΡΠ³ΠΎΠΉ ΡΡΠΎΡΠΎΠ½Ρ, ΠΏΠΎΡΠΊΠΎΠ»ΡΠΊΡ ΡΠ΅ΠΉΡΠ°Ρ ΠΌΡ Π²ΡΠ±ΡΠ°Π»ΠΈ Π²Π΅ΡΡΠΈΠ½Ρ z, Π΅Ρ ΠΌΠ΅ΡΠΊΠ° ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½Π° ΡΡΠ΅Π΄ΠΈ Π½Π΅ΠΏΠΎΡΠ΅ΡΡΠ½Π½ΡΡ , ΡΠΎ Π΅ΡΡΡ. ΠΠΎΠΌΠ±ΠΈΠ½ΠΈΡΡΡ ΡΡΠΎ Ρ, ΠΈΠΌΠ΅Π΅ΠΌ d (z) =l (z), ΡΡΠΎ ΠΈ ΡΡΠ΅Π±ΠΎΠ²Π°Π»ΠΎΡΡ Π΄ΠΎΠΊΠ°Π·Π°ΡΡ.
ΠΠΎΡΠΊΠΎΠ»ΡΠΊΡ Π°Π»Π³ΠΎΡΠΈΡΠΌ Π·Π°ΠΊΠ°Π½ΡΠΈΠ²Π°Π΅Ρ ΡΠ°Π±ΠΎΡΡ, ΠΊΠΎΠ³Π΄Π° Π²ΡΠ΅ Π²Π΅ΡΡΠΈΠ½Ρ ΠΏΠΎΡΠ΅ΡΠ΅Π½Ρ, Π² ΡΡΠΎΡ ΠΌΠΎΠΌΠ΅Π½Ρ d=l Π΄Π»Ρ Π²ΡΠ΅Ρ Π²Π΅ΡΡΠΈΠ½ Π‘Π»ΠΎΠΆΠ½ΠΎΡΡΡ ΡΠ°Π±ΠΎΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΠΠ΅ΠΉΠΊΡΡΡΡ Π‘Π»ΠΎΠΆΠ½ΠΎΡΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΠΠ΅ΠΉΠΊΡΡΡΡ Π·Π°Π²ΠΈΡΠΈΡ ΠΎΡ ΡΠΏΠΎΡΠΎΠ±Π° Π½Π°Ρ ΠΎΠΆΠ΄Π΅Π½ΠΈΡ Π²Π΅ΡΡΠΈΠ½Ρ v, Π° ΡΠ°ΠΊΠΆΠ΅ ΡΠΏΠΎΡΠΎΠ±Π° Ρ ΡΠ°Π½Π΅Π½ΠΈΡ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° Π½Π΅ΠΏΠΎΡΠ΅ΡΠ΅Π½Π½ΡΡ Π²Π΅ΡΡΠΈΠ½ ΠΈ ΡΠΏΠΎΡΠΎΠ±Π° ΠΎΠ±Π½ΠΎΠ²Π»Π΅Π½ΠΈΡ ΠΌΠ΅ΡΠΎΠΊ. ΠΠ±ΠΎΠ·Π½Π°ΡΠΈΠΌ ΡΠ΅ΡΠ΅Π· n ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½, Π° ΡΠ΅ΡΠ΅Π· m — ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΠ΅Π±Π΅Ρ Π² Π³ΡΠ°ΡΠ΅ G.
Π ΠΏΡΠΎΡΡΠ΅ΠΉΡΠ΅ΠΌ ΡΠ»ΡΡΠ°Π΅, ΠΊΠΎΠ³Π΄Π° Π΄Π»Ρ ΠΏΠΎΠΈΡΠΊΠ° Π²Π΅ΡΡΠΈΠ½Ρ Ρ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠΌ d [v] ΠΏΡΠΎΡΠΌΠ°ΡΡΠΈΠ²Π°Π΅ΡΡΡ Π²ΡΠ΅ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½, Π° Π΄Π»Ρ Ρ ΡΠ°Π½Π΅Π½ΠΈΡ Π²Π΅Π»ΠΈΡΠΈΠ½ d — ΠΌΠ°ΡΡΠΈΠ², Π²ΡΠ΅ΠΌΡ ΡΠ°Π±ΠΎΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° Π΅ΡΡΡ O (n2 + m). ΠΡΠ½ΠΎΠ²Π½ΠΎΠΉ ΡΠΈΠΊΠ» Π²ΡΠΏΠΎΠ»Π½ΡΠ΅ΡΡΡ ΠΏΠΎΡΡΠ΄ΠΊΠ° n ΡΠ°Π·, Π² ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΠΈΠ· Π½ΠΈΡ Π½Π° Π½Π°Ρ ΠΎΠΆΠ΄Π΅Π½ΠΈΠ΅ ΠΌΠΈΠ½ΠΈΠΌΡΠΌΠ° ΡΡΠ°ΡΠΈΡΡΡ ΠΏΠΎΡΡΠ΄ΠΊΠ° n ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΉ, ΠΏΠ»ΡΡ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΠ΅Π»Π°ΠΊΡΠ°ΡΠΈΠΉ (ΡΠΌΠ΅Π½ ΠΌΠ΅ΡΠΎΠΊ), ΠΊΠΎΡΠΎΡΠΎΠ΅ Π½Π΅ ΠΏΡΠ΅Π²ΠΎΡΡ ΠΎΠ΄ΠΈΡ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Π° ΡΠ΅Π±Π΅Ρ Π² ΠΈΡΡ ΠΎΠ΄Π½ΠΎΠΌ Π³ΡΠ°ΡΠ΅.
ΠΠ»Ρ ΡΠ°Π·ΡΠ΅ΠΆΠ΅Π½Π½ΡΡ Π³ΡΠ°ΡΠΎΠ² (ΡΠΎ Π΅ΡΡΡ ΡΠ°ΠΊΠΈΡ , Π΄Π»Ρ ΠΊΠΎΡΠΎΡΡΡ m ΠΌΠ½ΠΎΠ³ΠΎ ΠΌΠ΅Π½ΡΡΠ΅ n2) Π½Π΅ΠΏΠΎΡΠ΅ΡΠ΅Π½Π½ΡΠ΅ Π²Π΅ΡΡΠΈΠ½Ρ ΠΌΠΎΠΆΠ½ΠΎ Ρ ΡΠ°Π½ΠΈΡΡ Π² Π΄Π²ΠΎΠΈΡΠ½ΠΎΠΉ ΠΊΡΡΠ΅, Π° Π² ΠΊΠ°ΡΠ΅ΡΡΠ²Π΅ ΠΊΠ»ΡΡΠ° ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ Π·Π½Π°ΡΠ΅Π½ΠΈΡ d [i], ΡΠΎΠ³Π΄Π° Π²ΡΠ΅ΠΌΡ ΠΈΠ·Π²Π»Π΅ΡΠ΅Π½ΠΈΡ Π²Π΅ΡΡΠΈΠ½Ρ ΠΈΠ· U ΡΡΠ°Π½Π΅Ρ log n, ΠΏΡΠΈ ΡΠΎΠΌ, ΡΡΠΎ Π²ΡΠ΅ΠΌΡ ΠΌΠΎΠ΄ΠΈΡΠΈΠΊΠ°ΡΠΈΠΈ d [i] Π²ΠΎΠ·ΡΠ°ΡΡΠ΅Ρ Π΄ΠΎ log n. Π’Π°ΠΊ ΠΊΠ°ΠΊ ΡΠΈΠΊΠ» Π²ΡΠΏΠΎΠ»Π½ΡΠ΅ΡΡΡ ΠΏΠΎΡΡΠ΄ΠΊΠ° n ΡΠ°Π·, Π° ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΠ΅Π»Π°ΠΊΡΠ°ΡΠΈΠΉ Π½Π΅ Π±ΠΎΠ»ΡΡΠ΅ m, ΡΠΊΠΎΡΠΎΡΡΡ ΡΠ°Π±ΠΎΡΡ ΡΠ°ΠΊΠΎΠΉ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΠΈ O (n*log n + m*log n).
ΠΡΠ»ΠΈ Π΄Π»Ρ Ρ ΡΠ°Π½Π΅Π½ΠΈΡ Π½Π΅ΠΏΠΎΡΠ΅ΡΠ΅Π½Π½ΡΡ Π²Π΅ΡΡΠΈΠ½ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ ΡΠΈΠ±ΠΎΠ½Π°ΡΡΠΈΠ΅Π²Ρ ΠΊΡΡΡ, Π΄Π»Ρ ΠΊΠΎΡΠΎΡΠΎΠΉ ΡΠ΄Π°Π»Π΅Π½ΠΈΠ΅ ΠΏΡΠΎΠΈΡΡ ΠΎΠ΄ΠΈΡ Π² ΡΡΠ΅Π΄Π½Π΅ΠΌ Π·Π° O (log n), Π° ΡΠΌΠ΅Π½ΡΡΠ΅Π½ΠΈΠ΅ Π·Π½Π°ΡΠ΅Π½ΠΈΡ Π² ΡΡΠ΅Π΄Π½Π΅ΠΌ Π·Π° O (1), ΡΠΎ Π²ΡΠ΅ΠΌΡ ΡΠ°Π±ΠΎΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΡΠΎΡΡΠ°Π²ΠΈΡ O (n*log n + m).
Π Π΅ΡΠ΅Π½ΠΈΠ΅ Π·Π°Π΄Π°ΡΠΈ:
Π£ΡΠ»ΠΎΠ²ΠΈΠ΅ Π·Π°Π΄Π°ΡΠΈ: ΠΠ°ΠΉΡΠΈ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠΈΠΉ ΠΏΡΡΡ ΠΎΡ Π²Π΅ΡΡΠΈΠ½Ρ 1 ΠΊ Π²Π΅ΡΡΠΈΠ½Π΅ 6 ΡΠ»Π΅Π΄ΡΡΡΠ΅Π³ΠΎ Π³ΡΠ°ΡΠ° (ΡΠΈΡ.3):
Π ΠΈΡ. 3. ΠΡΡ ΠΎΠ΄Π½ΡΠ΅ Π΄Π°Π½Π½ΡΠ΅
Π Π΅ΡΠ΅Π½ΠΈΠ΅: ΠΠ°ΠΆΠ΄ΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Π΅ Π³ΡΠ°ΡΠ° ΡΠΎΠΏΠΎΡΡΠ°Π²ΠΈΠΌ ΠΌΠ΅ΡΠΊΡ — ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅ ΠΈΠ·Π²Π΅ΡΡΠ½ΠΎΠ΅ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠ΅ ΠΎΡ ΡΡΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ Π΄ΠΎ Π²Π΅ΡΡΠΈΠ½Ρ 1. ΠΠ΅ΡΠΊΠ° ΡΠ°ΠΌΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ 1 ΠΏΠΎΠ»Π°Π³Π°Π΅ΡΡΡ ΡΠ°Π²Π½ΠΎΠΉ 0, ΠΌΠ΅ΡΠΊΠΈ ΠΎΡΡΠ°Π»ΡΠ½ΡΡ Π²Π΅ΡΡΠΈΠ½ — Π±Π΅ΡΠΊΠΎΠ½Π΅ΡΠ½ΠΎΡΡΠΈ. ΠΡΠΎ ΠΎΡΡΠ°ΠΆΠ°Π΅Ρ ΡΠΎ, ΡΡΠΎ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΡ ΠΎΡ Π²Π΅ΡΡΠΈΠ½Ρ 1 Π΄ΠΎ Π΄ΡΡΠ³ΠΈΡ Π²Π΅ΡΡΠΈΠ½ ΠΏΠΎΠΊΠ° Π½Π΅ΠΈΠ·Π²Π΅ΡΡΠ½Ρ. ΠΡΠ΅ Π²Π΅ΡΡΠΈΠ½Ρ Π³ΡΠ°ΡΠ° ΠΏΠΎΠΌΠ΅ΡΠ°ΡΡΡΡ ΠΊΠ°ΠΊ Π½Π΅ΠΏΠΎΡΠ΅ΡΡΠ½Π½ΡΠ΅.
ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΡΠ°Π±ΠΎΡΠ°Π΅Ρ ΠΏΠΎΡΠ°Π³ΠΎΠ²ΠΎ — Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΡΠ°Π³Π΅ ΠΎΠ½ «ΠΏΠΎΡΠ΅ΡΠ°Π΅Ρ» ΠΎΠ΄Π½Ρ Π²Π΅ΡΡΠΈΠ½Ρ ΠΈ ΠΏΡΡΠ°Π΅ΡΡΡ ΡΠΌΠ΅Π½ΡΡΠ°ΡΡ ΠΌΠ΅ΡΠΊΠΈ.
ΠΠ° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΡΠ°Π³Π΅ ΠΈΠ· Π΅ΡΡ Π½Π΅ ΠΏΠΎΡΠ΅ΡΡΠ½Π½ΡΡ Π²Π΅ΡΡΠΈΠ½ Π²ΡΠ±ΠΈΡΠ°Π΅ΡΡΡ Π²Π΅ΡΡΠΈΠ½Π° u, ΠΈΠΌΠ΅ΡΡΠ°Ρ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΡ ΠΌΠ΅ΡΠΊΡ. ΠΡ ΡΠ°ΡΡΠΌΠ°ΡΡΠΈΠ²Π°Π΅ΠΌ Π²ΡΠ΅Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΡΠ΅ ΠΌΠ°ΡΡΡΡΡΡ, Π² ΠΊΠΎΡΠΎΡΡΡ u ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΏΡΠ΅Π΄ΠΏΠΎΡΠ»Π΅Π΄Π½ΠΈΠΌ ΠΏΡΠ½ΠΊΡΠΎΠΌ.
ΠΠ΅ΡΡΠΈΠ½Ρ, Π² ΠΊΠΎΡΠΎΡΡΠ΅ Π²Π΅Π΄ΡΡ ΡΡΠ±ΡΠ° ΠΈΠ· u, Π½Π°Π·ΠΎΠ²Π΅ΠΌ ΡΠΎΡΠ΅Π΄ΡΠΌΠΈ ΡΡΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ. ΠΠ»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ Π½Π΅ΠΏΠΎΡΠ΅ΡΡΠ½Π½ΠΎΠ³ΠΎ ΡΠΎΡΠ΅Π΄Π° Π²Π΅ΡΡΠΈΠ½Ρ u ΡΠ°ΡΡΠΌΠΎΡΡΠΈΠΌ Π½ΠΎΠ²ΡΡ Π΄Π»ΠΈΠ½Ρ ΠΏΡΡΠΈ, ΡΠ°Π²Π½ΡΡ ΡΡΠΌΠΌΠ΅ Π·Π½Π°ΡΠ΅Π½ΠΈΠΉ ΡΠ΅ΠΊΡΡΠ΅ΠΉ ΠΌΠ΅ΡΠΊΠΈ u ΠΈ Π΄Π»ΠΈΠ½Ρ ΡΠ΅Π±ΡΠ°, ΡΠΎΠ΅Π΄ΠΈΠ½ΡΡΡΠ΅Π³ΠΎ u Ρ ΡΡΠΈΠΌ ΡΠΎΡΠ΅Π΄ΠΎΠΌ. ΠΡΠ»ΠΈ ΠΏΠΎΠ»ΡΡΠ΅Π½Π½ΠΎΠ΅ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ Π΄Π»ΠΈΠ½Ρ ΠΌΠ΅Π½ΡΡΠ΅ Π·Π½Π°ΡΠ΅Π½ΠΈΡ ΠΌΠ΅ΡΠΊΠΈ ΡΠΎΡΠ΅Π΄Π°, Π·Π°ΠΌΠ΅Π½ΠΈΠΌ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ ΠΌΠ΅ΡΠΊΠΈ ΠΏΠΎΠ»ΡΡΠ΅Π½Π½ΡΠΌ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ΠΌ Π΄Π»ΠΈΠ½Ρ. Π Π°ΡΡΠΌΠΎΡΡΠ΅Π² Π²ΡΠ΅Ρ ΡΠΎΡΠ΅Π΄Π΅ΠΉ, ΠΏΠΎΠΌΠ΅ΡΠΈΠΌ Π²Π΅ΡΡΠΈΠ½Ρ u ΠΊΠ°ΠΊ ΠΏΠΎΡΠ΅ΡΠ΅Π½Π½ΡΡ ΠΈ ΠΏΠΎΠ²ΡΠΎΡΠΈΠΌ ΡΠ°Π³ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°.
Π¨Π°Π³ 1. (ΡΠΌ. ΡΠΈΡ.4) ΠΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΡ ΠΌΠ΅ΡΠΊΡ ΠΈΠΌΠ΅Π΅Ρ Π²Π΅ΡΡΠΈΠ½Π° 1. ΠΡ ΡΠΎΡΠ΅Π΄ΡΠΌΠΈ ΡΠ²Π»ΡΡΡΡΡ Π²Π΅ΡΡΠΈΠ½Ρ 2 ΠΈ 3.
ΠΠ΅ΡΠ²ΡΠΉ ΠΏΠΎ ΠΎΡΠ΅ΡΠ΅Π΄ΠΈ ΡΠΎΡΠ΅Π΄ Π²Π΅ΡΡΠΈΠ½Ρ 1 — Π²Π΅ΡΡΠΈΠ½Π° 2, ΠΏΠΎΡΠΎΠΌΡ ΡΡΠΎ Π΄Π»ΠΈΠ½Π° ΠΏΡΡΠΈ Π΄ΠΎ Π½Π΅Ρ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½Π°. ΠΠ»ΠΈΠ½Π° ΠΏΡΡΠΈ Π² Π½Π΅Ρ ΡΠ΅ΡΠ΅Π· Π²Π΅ΡΡΠΈΠ½Ρ 1 ΡΠ°Π²Π½Π° ΡΡΠΌΠΌΠ΅ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠ΅Π³ΠΎ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΡ Π΄ΠΎ Π²Π΅ΡΡΠΈΠ½Ρ 1, Ρ. Π΅ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ Π΅Ρ ΠΌΠ΅ΡΠΊΠΈ, ΠΈ Π΄Π»ΠΈΠ½Ρ ΡΠ΅Π±ΡΠ°, ΠΈΠ΄ΡΡΠ΅Π³ΠΎ ΠΈΠ· 1-ΠΎΠΉ Π² 2-ΡΡ, ΡΠΎ Π΅ΡΡΡ 0 + 3 = 3. ΠΡΠΎ ΠΌΠ΅Π½ΡΡΠ΅ ΡΠ΅ΠΊΡΡΠ΅ΠΉ ΠΌΠ΅ΡΠΊΠΈ Π²Π΅ΡΡΠΈΠ½Ρ 2, Π±Π΅ΡΠΊΠΎΠ½Π΅ΡΠ½ΠΎΡΡΠΈ, ΠΏΠΎΡΡΠΎΠΌΡ Π½ΠΎΠ²Π°Ρ ΠΌΠ΅ΡΠΊΠ° 2-ΠΉ Π²Π΅ΡΡΠΈΠ½Ρ ΡΠ°Π²Π½Π° 3.
ΠΠ½Π°Π»ΠΎΠ³ΠΈΡΠ½ΡΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ ΠΏΠΎΠ»ΡΡΠ°Π΅ΠΌ Π½ΠΎΠ²ΡΡ ΠΌΠ΅ΡΠΊΡ 3-ΠΉ Π²Π΅ΡΡΠΈΠ½Ρ, ΡΠ°Π²Π½ΡΡ 4.
ΠΡΠ΅ ΡΠΎΡΠ΅Π΄ΠΈ Π²Π΅ΡΡΠΈΠ½Ρ 1 ΠΏΡΠΎΠ²Π΅ΡΠ΅Π½Ρ. Π’Π΅ΠΊΡΡΠ΅Π΅ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠ΅ Π΄ΠΎ Π²Π΅ΡΡΠΈΠ½Ρ 1 ΡΡΠΈΡΠ°Π΅ΡΡΡ ΠΎΠΊΠΎΠ½ΡΠ°ΡΠ΅Π»ΡΠ½ΡΠΌ ΠΈ ΠΏΠ΅ΡΠ΅ΡΠΌΠΎΡΡΡ Π½Π΅ ΠΏΠΎΠ΄Π»Π΅ΠΆΠΈΡ (ΡΠΎ, ΡΡΠΎ ΡΡΠΎ Π΄Π΅ΠΉΡΡΠ²ΠΈΡΠ΅Π»ΡΠ½ΠΎ ΡΠ°ΠΊ, Π²ΠΏΠ΅ΡΠ²ΡΠ΅ Π΄ΠΎΠΊΠ°Π·Π°Π» Π. ΠΠ΅ΠΉΠΊΡΡΡΠ°).
ΠΡΡΠ΅ΡΠΊΠ½Π΅ΠΌ Π΅Ρ ΠΈΠ· Π³ΡΠ°ΡΠ°, ΡΡΠΎΠ±Ρ ΠΎΡΠΌΠ΅ΡΠΈΡΡ, ΡΡΠΎ ΡΡΠ° Π²Π΅ΡΡΠΈΠ½Π° ΠΏΠΎΡΠ΅ΡΠ΅Π½Π°.
Π ΠΈΡ. 4. Π¨Π°Π³ 1.
Π¨Π°Π³ 2. (ΡΠΌ. ΡΠΈΡ.5) ΠΠ»ΠΈΠΆΠ°ΠΉΡΠ΅ΠΉ ΠΈΠ· Π½Π΅ΠΏΠΎΡΠ΅ΡΠ΅Π½Π½ΡΡ Π²Π΅ΡΡΠΈΠ½ ΡΠ²Π»ΡΠ΅ΡΡΡ Π²Π΅ΡΡΠΈΠ½Π° 2 Ρ ΠΌΠ΅ΡΠΊΠΎΠΉ 3. Π‘Π½ΠΎΠ²Π° ΠΏΡΡΠ°Π΅ΠΌΡΡ ΡΠΌΠ΅Π½ΡΡΠΈΡΡ ΠΌΠ΅ΡΠΊΠΈ ΡΠΎΡΠ΅Π΄Π΅ΠΉ Π²ΡΠ±ΡΠ°Π½Π½ΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ, ΠΏΡΡΠ°ΡΡΡ ΠΏΡΠΎΠΉΡΠΈ Π² Π½ΠΈΡ ΡΠ΅ΡΠ΅Π· 2-Ρ Π²Π΅ΡΡΠΈΠ½Ρ.
Π‘ΠΎΡΠ΅Π΄ΡΠΌΠΈ Π²Π΅ΡΡΠΈΠ½Ρ 2 ΡΠ²Π»ΡΡΡΡΡ Π²Π΅ΡΡΠΈΠ½Ρ 1 ΠΈ 4. ΠΠ΅ΡΡΠΈΠ½Π° 1 ΡΠΆΠ΅ ΠΏΠΎΡΠ΅ΡΠ΅Π½Π°. Π Π°ΡΡΠΌΠΎΡΡΠΈΠΌ Π²Π΅ΡΡΠΈΠ½Ρ 4. ΠΡΠ»ΠΈ ΠΈΠ΄ΡΠΈ Π² Π½Π΅Ρ ΡΠ΅ΡΠ΅Π· 2, ΡΠΎ Π΄Π»ΠΈΠ½Π° ΡΠ°ΠΊΠΎΠ³ΠΎ ΠΏΡΡΠΈ Π±ΡΠ΄Π΅Ρ ΡΠ°Π²Π½Π° 3 + 5 = 8. ΠΡΠΈΡΠ²Π°ΠΈΠ²Π°Π΅ΠΌ Π΅ΠΉ ΠΌΠ΅ΡΠΊΡ 8.
ΠΠΎΠΌΠ΅ΡΠ°Π΅ΠΌ Π²Π΅ΡΡΠΈΠ½Ρ 2 ΠΊΠ°ΠΊ ΠΏΠΎΡΠ΅ΡΠ΅Π½Π½ΡΡ.
Π ΠΈΡ. 5. Π¨Π°Π³ 2.
Π¨Π°Π³ 3. (ΡΠΌ. ΡΠΈΡ.6) Π Π°ΡΡΠΌΠΎΡΡΠΈΠΌ Π²Π΅ΡΡΠΈΠ½Ρ 3. ΠΠ΅ ΡΠΎΡΠ΅Π΄ΡΠΌΠΈ ΡΠ²Π»ΡΡΡΡΡ Π²Π΅ΡΡΠΈΠ½Ρ 1, 4 ΠΈ 5.
ΠΠ΅ΡΡΠΈΠ½Π° 1 ΡΠΆΠ΅ ΠΏΠΎΡΠ΅ΡΠ΅Π½Π°.
Π‘Π»Π΅Π΄ΡΡΡΠΈΠΉ ΡΠΎΡΠ΅Π΄ Π²Π΅ΡΡΠΈΠ½Ρ 3 — Π²Π΅ΡΡΠΈΠ½Π° 4, ΡΠ°ΠΊ ΠΈΠΌΠ΅Π΅Ρ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΡ ΠΌΠ΅ΡΠΊΡ ΠΈΠ· Π½Π΅ΠΏΠΎΡΠ΅ΡΡΠ½Π½ΡΡ Π²Π΅ΡΡΠΈΠ½. ΠΡΠ»ΠΈ ΠΈΠ΄ΡΠΈ Π² Π½Π΅Ρ ΡΠ΅ΡΠ΅Π· 3, ΡΠΎ Π΄Π»ΠΈΠ½Π° ΡΠ°ΠΊΠΎΠ³ΠΎ ΠΏΡΡΠΈ Π±ΡΠ΄Π΅Ρ ΡΠ°Π²Π½Π° 4 + 2 = 6. ΠΡΠΎ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ ΠΌΠ΅Π½ΡΡΠ΅ ΡΠ΅ΠΊΡΡΠ΅ΠΉ ΠΌΠ΅ΡΠΊΠΈ, ΠΏΠΎΡΡΠΎΠΌΡ ΠΌΠ΅Π½ΡΠ΅ΠΌ ΠΌΠ΅ΡΠΊΡ ΡΠ΅ΡΠ²Π΅ΡΡΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ Π½Π° 6.
Π Π°ΡΡΠΌΠΎΡΡΠΈΠΌ Π²Π΅ΡΡΠΈΠ½Ρ 5. ΠΡΠ»ΠΈ ΠΈΠ΄ΡΠΈ Π² Π½Π΅Ρ ΡΠ΅ΡΠ΅Π· 3, ΡΠΎ Π΄Π»ΠΈΠ½Π° ΡΠ°ΠΊΠΎΠ³ΠΎ ΠΏΡΡΠΈ Π±ΡΠ΄Π΅Ρ ΡΠ°Π²Π½Π° 4 + 3 = 7. ΠΡΠΈΡΠ²Π°ΠΈΠ²Π°Π΅ΠΌ Π΅ΠΉ ΠΌΠ΅ΡΠΊΡ 7. ΠΠΎΠΌΠ΅ΡΠΈΠΌ ΡΡΡΠ΅Π»ΠΊΠΎΠΉ ΠΏΡΡΡ ΠΎΡ Π²Π΅ΡΡΠΈΠ½Ρ 1 ΠΊ Π²Π΅ΡΡΠΈΠ½Π΅ 4 Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠ΅ΠΉ Π΄Π»ΠΈΠ½Ρ.
ΠΠΎΠΌΠ΅ΡΠ°Π΅ΠΌ Π²Π΅ΡΡΠΈΠ½Ρ 3 ΠΊΠ°ΠΊ ΠΏΠΎΡΠ΅ΡΠ΅Π½Π½ΡΡ.
Π ΠΈΡ. 6. Π¨Π°Π³ 3
Π¨Π°Π³ 4. (ΡΠΌ. ΡΠΈΡ.7) Π Π°ΡΡΠΌΠΎΡΡΠΈΠΌ Π²Π΅ΡΡΠΈΠ½Ρ 4. ΠΠ΅ ΡΠΎΡΠ΅Π΄ΡΠΌΠΈ ΡΠ²Π»ΡΡΡΡΡ Π²Π΅ΡΡΠΈΠ½Ρ 2, 3, 5 ΠΈ 6.
ΠΠ΅ΡΡΠΈΠ½Ρ 2 ΠΈ 3 ΡΠΆΠ΅ ΠΏΠΎΡΠ΅ΡΠ΅Π½Ρ.
Π Π°ΡΡΠΌΠΎΡΡΠΈΠΌ Π²Π΅ΡΡΠΈΠ½Ρ 5. ΠΡΠ»ΠΈ ΠΈΠ΄ΡΠΈ Π² Π½Π΅Ρ ΡΠ΅ΡΠ΅Π· 4, ΡΠΎ Π΄Π»ΠΈΠ½Π° ΡΠ°ΠΊΠΎΠ³ΠΎ ΠΏΡΡΠΈ Π±ΡΠ΄Π΅Ρ ΡΠ°Π²Π½Π° 6 + 6 = 12. ΠΠΎ ΡΡΠΎ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ Π±ΠΎΠ»ΡΡΠ΅ ΡΠ΅ΠΊΡΡΠ΅ΠΉ ΠΌΠ΅ΡΠΊΠΈ, ΠΏΠΎΡΡΠΎΠΌΡ ΠΌΠ΅ΡΠΊΡ Π²Π΅ΡΡΠΈΠ½Ρ 5 Π½Π΅ ΠΌΠ΅Π½ΡΠ΅ΠΌ. ΠΠΎΠΌΠ΅ΡΠΈΠΌ ΡΡΡΠ΅Π»ΠΊΠΎΠΉ ΠΏΡΡΡ ΠΎΡ Π²Π΅ΡΡΠΈΠ½Ρ 1 ΠΊ Π²Π΅ΡΡΠΈΠ½Π΅ 5 Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠ΅ΠΉ Π΄Π»ΠΈΠ½Ρ.
Π Π°ΡΡΠΌΠΎΡΡΠΈΠΌ Π²Π΅ΡΡΠΈΠ½Ρ 6. ΠΡΠ»ΠΈ ΠΈΠ΄ΡΠΈ Π² Π½Π΅Ρ ΡΠ΅ΡΠ΅Π· 4, ΡΠΎ Π΄Π»ΠΈΠ½Π° ΡΠ°ΠΊΠΎΠ³ΠΎ ΠΏΡΡΠΈ Π±ΡΠ΄Π΅Ρ ΡΠ°Π²Π½Π° 6 + 8 = 14. ΠΡΠΈΡΠ²Π°ΠΈΠ²Π°Π΅ΠΌ Π΅ΠΉ ΠΌΠ΅ΡΠΊΡ 14.
ΠΠΎΠΌΠ΅ΡΠ°Π΅ΠΌ Π²Π΅ΡΡΠΈΠ½Ρ 4 ΠΊΠ°ΠΊ ΠΏΠΎΡΠ΅ΡΠ΅Π½Π½ΡΡ.
Π ΠΈΡ. 7. Π¨Π°Π³ 4
Π¨Π°Π³ 5. (ΡΠΌ. ΡΠΈΡ.8) Π Π°ΡΡΠΌΠΎΡΡΠΈΠΌ Π²Π΅ΡΡΠΈΠ½Ρ 5. ΠΠ΅ ΡΠΎΡΠ΅Π΄ΡΠΌΠΈ ΡΠ²Π»ΡΡΡΡΡ Π²Π΅ΡΡΠΈΠ½Ρ 3, 4 ΠΈ 6.
ΠΠ΅ΡΡΠΈΠ½Ρ 3 ΠΈ 4 ΡΠΆΠ΅ ΠΏΠΎΡΠ΅ΡΠ΅Π½Ρ.
Π Π°ΡΡΠΌΠΎΡΡΠΈΠΌ Π²Π΅ΡΡΠΈΠ½Ρ 6. ΠΡΠ»ΠΈ ΠΈΠ΄ΡΠΈ Π² Π½Π΅Ρ ΡΠ΅ΡΠ΅Π· 5, ΡΠΎ Π΄Π»ΠΈΠ½Π° ΡΠ°ΠΊΠΎΠ³ΠΎ ΠΏΡΡΠΈ Π±ΡΠ΄Π΅Ρ ΡΠ°Π²Π½Π° 7 + 9 = 16 < 14, Π·Π½Π°ΡΠΈΡ, ΠΌΠ΅ΡΠΊΡ Π²Π΅ΡΡΠΈΠ½Ρ 6 Π½Π΅ ΠΌΠ΅Π½ΡΠ΅ΠΌ. ΠΠΎΠΌΠ΅ΡΠΈΠΌ ΡΡΡΠ΅Π»ΠΊΠΎΠΉ ΠΏΡΡΡ ΠΎΡ Π²Π΅ΡΡΠΈΠ½Ρ 1 ΠΊ Π²Π΅ΡΡΠΈΠ½Π΅ 6 Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠ΅ΠΉ Π΄Π»ΠΈΠ½Ρ.
ΠΠΎΠΌΠ΅ΡΠ°Π΅ΠΌ Π²Π΅ΡΡΠΈΠ½Ρ 5 ΠΊΠ°ΠΊ ΠΏΠΎΡΠ΅ΡΠ΅Π½Π½ΡΡ.
Π ΠΈΡ. 8. Π¨Π°Π³ 5.
Π£ ΡΠ΅Π»Π΅Π²ΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ 6 Π½Π΅ ΠΎΡΡΠ°Π»ΠΎΡΡ Π½Π΅ΠΏΠΎΡΠ΅ΡΠ΅Π½Π½ΡΡ ΡΠΎΡΠ΅Π΄Π΅ΠΉ. ΠΠ»Π³ΠΎΡΠΈΡΠΌ Π·Π°ΠΊΠΎΠ½ΡΠ΅Π½.
ΠΡΠ²Π΅Ρ: ΠΡΠ°ΡΡΠ°ΠΉΡΠΈΠΉ ΠΏΡΡΡ ΠΎΡ Π²Π΅ΡΡΠΈΠ½Ρ 1 ΠΊ Π²Π΅ΡΡΠΈΠ½Π΅ 6: 1−3-4−6, Π΅Π³ΠΎ Π΄Π»ΠΈΠ½Π° 14.
Π‘ΠΏΠΈΡΠΎΠΊ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΠΌΠΎΠΉ Π»ΠΈΡΠ΅ΡΠ°ΡΡΡΡ
1. ΠΠ½Π°Π½ΠΈΠΉ Π. ΠΠ΅Π²ΠΈΡΠΈΠ½ ΠΠ»Π°Π²Π° 9. ΠΠ°Π΄Π½ΡΠ΅ ΠΌΠ΅ΡΠΎΠ΄Ρ: ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΠΠ΅ΠΉΠΊΡΡΡΡ // ΠΠ»Π³ΠΎΡΠΈΡΠΌΡ: Π²Π²Π΅Π΄Π΅Π½ΠΈΠ΅ Π² ΡΠ°Π·ΡΠ°Π±ΠΎΡΠΊΡ ΠΈ Π°Π½Π°Π»ΠΈΠ· = Introduction to The Design and Analysis of Aigorithms. — Π.: «ΠΠΈΠ»ΡΡΠΌΡ», 2006. — Π‘.189−195.
2. Π’ΠΎΠΌΠ°Ρ Π₯. ΠΠΎΡΠΌΠ΅Π½, Π§Π°ΡΠ»ΡΠ· Π. ΠΠ΅ΠΉΠ·Π΅ΡΡΠΎΠ½, Π ΠΎΠ½Π°Π»ΡΠ΄ Π. Π ΠΈΠ²Π΅ΡΡ, ΠΠ»ΠΈΡΡΠΎΡΠ΄ Π¨ΡΠ°ΠΉΠ½ ΠΠ»Π³ΠΎΡΠΈΡΠΌΡ: ΠΏΠΎΡΡΡΠΎΠ΅Π½ΠΈΠ΅ ΠΈ Π°Π½Π°Π»ΠΈΠ· = Introduction to Algorithms. — 2-Π΅ ΠΈΠ·Π΄. — Π.: «ΠΠΈΠ»ΡΡΠΌΡ», 2006. — Π‘.1296.
3. ΠΡΠ·Π½Π΅ΡΠΎΠ² Π. Π., Π‘Π°ΠΊΠΎΠ²ΠΈΡ Π. Π., Π₯ΠΎΠ»ΠΎΠ΄ Π. Π. «ΠΡΡΡΠ°Ρ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΠΊΠ°. ΠΠ°ΡΠ΅ΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΎΠ΅ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅», ΠΠΈΠ½ΡΠΊ, ΠΡΡΠ΅ΠΉΡΠ°Ρ ΡΠΊΠΎΠ»Π°, 2001 Π³.
4. ΠΡΠ°ΡΡ Π. Π‘., Π§ΡΠΏΡΡΠ½ΠΎΠ² Π. Π. «ΠΡΠ½ΠΎΠ²Ρ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΠΊΠΈ ΠΈ Π΅Π΅ ΠΏΡΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΡ Π² ΡΠΊΠΎΠ½ΠΎΠΌΠΈΡΠ΅ΡΠΊΠΎΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠ²Π°Π½ΠΈΠΈ», ΠΠ·Π΄Π°ΡΠ΅Π»ΡΡΡΠ²ΠΎ «ΠΠ΅Π»ΠΎ», ΠΠΎΡΠΊΠ²Π° 2001 Π³.
5. Π. Π. ΠΡΠΌΠ°ΠΊΠΎΠ² «ΠΠ±ΡΠΈΠΉ ΠΊΡΡΡ Π²ΡΡΡΠ΅ΠΉ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΠΊΠΈ Π΄Π»Ρ ΡΠΊΠΎΠ½ΠΎΠΌΠΈΡΡΠΎΠ²», ΠΠΎΡΠΊΠ²Π°, ΠΠ½ΡΡΠ°-Π, 2000 Π³.
6. ΠΠ΅Π»ΠΎΠ² Π’Π΅ΠΎΡΠΈΡ ΠΡΠ°ΡΠΎΠ², ΠΠΎΡΠΊΠ²Π°, «ΠΠ°ΡΠΊΠ°», 1968.
7. ΠΠ΅ΡΠ΅Π΄ΠΎΠ² Π. Π., ΠΡΠΈΠΏΠΎΠ²Π° Π. Π. ΠΡΡΡ Π΄ΠΈΡΠΊΡΠ΅ΡΠ½ΠΎΠΉ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΠΊΠΈ. — Π.: ΠΠ·Π΄Π°ΡΠ΅Π»ΡΡΡΠ²ΠΎ ΠΠΠ, 1992.
8. ΠΡΠ΅ Π. Π’Π΅ΠΎΡΠΈΡ Π³ΡΠ°ΡΠΎΠ². — Π.: ΠΠ°ΡΠΊΠ°, 1980.
9. ΠΡΠΌΠ°Π³ΠΈΠ»ΠΎΠ² Π . Π‘., ΠΠ°Π»ΠΈΠ½ΠΊΠΈΠ½ Π. Π. ΠΠ°ΡΠ΅ΡΠΈΠ°Π»Ρ ΠΊ ΠΏΡΠ°ΠΊΡΠΈΡΠ΅ΡΠΊΠΈΠΌ Π·Π°Π½ΡΡΠΈΡΠΌ ΠΏΠΎ ΠΊΡΡΡΡ: ΠΠΈΡΠΊΡΠ΅ΡΠ½Π°Ρ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΠΊΠ° ΠΏΠΎ ΡΠ΅ΠΌΠ΅: ΠΠ»Π³ΠΎΡΠΈΡΠΌΡ Π½Π° Π³ΡΠ°ΡΠ°Ρ . — Π.: ΠΠΠ’Π£, 1995
10. Π‘ΠΌΠΎΠ»ΡΡΠΊΠΎΠ² Π. Π .
ΠΠ²Π΅Π΄Π΅Π½ΠΈΠ΅
Π² ΡΠ΅ΠΎΡΠΈΡ Π³ΡΠ°ΡΠΎΠ². Π.: ΠΠΠ’Π£, 1992
11. ΠΠ΅ΠΉΠΊΡΡΡΠ° Π. ΠΠΈΡΡΠΈΠΏΠ»ΠΈΠ½Π° ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΡ = A discipline of programming. — 1-Π΅ ΠΈΠ·Π΄. — Π.: ΠΠΈΡ, 1978. — Π‘.275.
12. ΠΠ°Π» Π£., ΠΠ΅ΠΉΠΊΡΡΡΠ° Π., Π₯ΠΎΠΎΡ Π. Π‘ΡΡΡΠΊΡΡΡΠ½ΠΎΠ΅ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ = Structured Programming. — 1-Π΅ ΠΈΠ·Π΄. — Π.: ΠΠΈΡ, 1975. — Π‘.247.
13. E. W. Dijkstra. A note on two problems in connexion with graphs. // Numerische Mathematik. V.1 (1959), P.269−271