Практические занятия Методические указания

ɉɊȺɄɌɂɑȿɋɄɈȿ ɁȺɇəɌɂȿ ʋ 3

Ɉɰɟɧɤɚ ɫɥɨɠɧɨɫɬɢ ɚɥɝɨɪɢɬɦɨɜ

ɐɟɥɶ ɡɚɧɹɬɢɹ: ɋɮɨɪɦɢɪɨɜɚɬɶ ɢ ɡɚɤɪɟɩɢɬɶ ɩɪɚɤɬɢɱɟɫɤɢɟ ɧɚɜɵɤɢ ɨɰɟɧɤɢ ɜɪɟɦɟɧɧɨɣ ɢ ɟɦɤɨɫɬɧɨɣ ɫɥɨɠɧɨɫɬɢ ɚɥɝɨɪɢɬɦɨɜ.

Ɍɟɨɪɟɬɢɱɟɫɤɢɟ ɫɜɟɞɟɧɢɹ Ɉɫɧɨɜɧɵɦɢ ɦɟɪɚɦɢ ɫɥɨɠɧɨɫɬɢ ɚɥɝɨɪɢɬɦɚ ɹɜɥɹɸɬɫɹ ɜɪɟɦɹ,

ɧɟɨɛɯɨɞɢɦɨɟ ɞɥɹ ɟɝɨ ɪɟɚɥɢɡɚɰɢɢ, ɢ ɨɛɴɟɦ ɬɪɟɛɭɟɦɨɣ ɩɚɦɹɬɢ [6, 7]. ɉɪɢ ɷɬɨɦ ɤɚɠɞɨɦɭ ɤɥɚɫɫɭ ɡɚɞɚɱ ɦɨɠɧɨ ɫɨɩɨɫɬɚɜɢɬɶ ɱɢɫɥɨ, ɯɚɪɚɤɬɟɪɢɡɭɸɳɟɟ ɨɛɴɟɦ ɜɯɨɞɧɵɯ ɞɚɧɧɵɯ, ɤɨɬɨɪɨɟ ɩɪɢɧɹɬɨ ɧɚɡɵɜɚɬɶ ɪɚɡɦɟɪɨɦ ɜɯɨɞɚ. ɇɚɩɪɢɦɟɪ, ɜ ɡɚɞɚɱɟ ɥɨɝɢɱɟɫɤɨɝɨ ɜɵɜɨɞɚ ɧɚ ɨɫɧɨɜɟ ɦɟɬɨɞɚ ɪɟɡɨɥɸɰɢɣ ɪɚɡɦɟɪɨɦ ɜɯɨɞɚ ɫɥɟɞɭɟɬ ɫɱɢɬɚɬɶ ɱɢɫɥɨ ɞɢɡɴɸɧɤɬɨɜ ɢɫɯɨɞɧɨɝɨ ɦɧɨɠɟɫɬɜɚ, ɜ ɩɪɨɰɟɞɭɪɟ ɩɨɢɫɤɚ ɤɨɧɬɪɚɪɧɨɣ ɩɚɪɵ ɜ ɞɜɭɯ ɞɢɡɴɸɧɤɬɚɯ - ɱɢɫɥɨ ɥɢɬɟɪɚɥɨɜ ɜ ɷɬɢɯ ɞɢɡɴɸɧɤɬɚɯ ɢ ɬ.ɞ. Ɉɱɟɜɢɞɧɨ, ɱɬɨ ɫɥɨɠɧɨɫɬɶ ɚɥɝɨɪɢɬɦɚ ɹɜɥɹɟɬɫɹ ɮɭɧɤɰɢɟɣ ɪɚɡɦɟɪɚ ɜɯɨɞɚ.

ȼɪɟɦɟɧɧɨɣ ɫɥɨɠɧɨɫɬɶɸ ɚɥɝɨɪɢɬɦɚ ɧɚɡɵɜɚɟɬɫɹ ɜɪɟɦɹ, ɡɚɬɪɚɱɢɜɚɟɦɨɟ ɧɚ ɜɵɱɢɫɥɟɧɢɟ ɪɟɡɭɥɶɬɚɬɚ, ɜɵɪɚɠɟɧɧɨɟ ɤɚɤ ɮɭɧɤɰɢɹ ɪɚɡɦɟɪɚ ɜɯɨɞɚ. ȿɦɤɨɫɬɧɚɹ ɫɥɨɠɧɨɫɬɶ - ɨɛɳɚɹ ɟɦɤɨɫɬɶ ɩɚɦɹɬɢ, ɢɫɩɨɥɶɡɨɜɚɧɧɨɣ ɜ ɩɪɨɰɟɫɫɟ ɪɟɚɥɢɡɚɰɢɢ ɚɥɝɨɪɢɬɦɚ, ɤɚɤ ɮɭɧɤɰɢɹ ɪɚɡɦɟɪɚ ɜɯɨɞɚ.

ɋɥɨɠɧɨɫɬɶ ɚɥɝɨɪɢɬɦɚ ɦɨɠɟɬ ɛɵɬɶ ɪɚɡɥɢɱɧɨɣ ɢ ɩɪɢ ɮɢɤɫɢɪɨɜɚɧɧɨɦ ɪɚɡɦɟɪɟ ɜɯɨɞɚ, ɧɨ ɪɚɡɥɢɱɧɵɯ ɜɯɨɞɧɵɯ ɞɚɧɧɵɯ. ɇɚɩɪɢɦɟɪ, ɩɪɢ ɩɨɢɫɤɟ ɤɨɧɬɪɚɪɧɨɣ ɩɚɪɵ ɜ ɞɜɭɯ ɞɢɡɴɸɧɤɬɚɯ ɮɢɤɫɢɪɨɜɚɧɧɨɣ ɞɥɢɧɵ, ɤɨɧɬɪɚɪɧɵɟ ɥɢɬɟɪɚɥɵ ɦɨɝɭɬ ɨɤɚɡɚɬɶɫɹ ɩɟɪɜɵɦɢ ɢɥɢ ɩɨɫɥɟɞɧɢɦɢ ɜ ɷɬɢɯ ɞɢɡɴɸɧɤɬɚɯ. Ɉɱɟɜɢɞɧɨ, ɱɬɨ ɜɪɟɦɹ ɩɨɢɫɤɚ ɤɨɧɬɪɚɪɧɨɣ ɩɚɪɵ ɜ ɷɬɢɯ ɫɥɭɱɚɹɯ ɨɤɚɠɟɬɫɹ ɪɚɡɥɢɱɧɵɦ. ɉɨɷɬɨɦɭ ɪɚɡɥɢɱɚɸɬ ɫɥɨɠɧɨɫɬɶ ɜ ɯɭɞɲɟɦ ɢ ɜ ɫɪɟɞɧɟɦ ɫɥɭɱɚɟ.

ɋɥɨɠɧɨɫɬɶ ɜ ɯɭɞɲɟɦ ɫɥɭɱɚɟ - ɷɬɨ ɦɚɤɫɢɦɚɥɶɧɚɹ ɩɪɢ ɞɚɧɧɨɦ ɪɚɡɦɟɪɟ ɜɯɨɞɚ ɫɥɨɠɧɨɫɬɶ. ɋɪɟɞɧɹɹ ɫɥɨɠɧɨɫɬɶ - ɫɪɟɞɧɹɹ ɩɨ ɜɫɟɦ ɜɯɨɞɚɦ ɞɚɧɧɨɝɨ ɪɚɡɦɟɪɚ ɫɥɨɠɧɨɫɬɶ.

ȼɪɟɦɟɧɧɚɹ ɫɥɨɠɧɨɫɬɶ ɜ ɯɭɞɲɟɦ ɫɥɭɱɚɟ - ɷɬɨ ɮɭɧɤɰɢɹ T(n), ɪɚɜɧɚɹ ɦɚɤɫɢɦɚɥɶɧɨɣ (ɩɨ ɜɫɟɦ ɜɯɨɞɚɦ ɪɚɡɦɟɪɚ n) ɢɡ ɫɭɦɦ ɜɪɟɦɟɧ, ɡɚɬɪɚɱɟɧɧɵɯ ɧɚ ɤɚɠɞɭɸ ɫɪɚɛɨɬɚɜɲɭɸ ɤɨɦɚɧɞɭ (ɨɩɟɪɚɬɨɪ).

ȿɦɤɨɫɬɧɚɹ ɫɥɨɠɧɨɫɬɶ ɜ ɯɭɞɲɟɦ ɫɥɭɱɚɟ - ɷɬɨ ɮɭɧɤɰɢɹ S(n), ɪɚɜɧɚɹ ɦɚɤɫɢɦɚɥɶɧɨɣ (ɩɨ ɜɫɟɦ ɜɯɨɞɚɦ ɪɚɡɦɟɪɚ n) ɢɡ ɫɭɦɦ ɟɦɤɨɫɬɟɣ ɜɫɟɯ ɹɱɟɟɤ (ɷɥɟɦɟɧɬɨɜ) ɩɚɦɹɬɢ ɤ ɤɨɬɨɪɵɦ ɛɵɥɨ ɨɛɪɚɳɟɧɢɟ.

Ⱦɥɹ ɬɨɱɧɨɝɨ ɬɟɨɪɟɬɢɱɟɫɤɨɝɨ ɨɩɪɟɞɟɥɟɧɢɹ ɜɪɟɦɟɧɧɨɣ ɢ ɟɦɤɨɫɬɧɨɣ ɫɥɨɠɧɨɫɬɢ ɬɪɟɛɭɟɬɫɹ ɡɧɚɬɶ ɜɪɟɦɟɧɚ ɜɵɩɨɥɧɟɧɢɹ ɤɚɠɞɨɣ ɤɨɦɚɧɞɵ (ɨɩɟɪɚɬɨɪɚ) ɢ ɨɛɴɟɦ ɩɚɦɹɬɢ, ɢɫɩɨɥɶɡɭɟɦɵɣ ɤɚɠɞɨɣ ɩɟɪɟɦɟɧɧɨɣ. Ɍɚɤ ɤɚɤ ɷɬɢ ɡɧɚɱɟɧɢɹ ɡɚɜɢɫɹɬ ɨɬ ɤɨɧɤɪɟɬɧɨɣ ɜɵɱɢɫɥɢɬɟɥɶɧɨɣ ɦɚɲɢɧɵ, ɜ ɬɟɨɪɢɢ ɫɥɨɠɧɨɫɬɢ ɚɥɝɨɪɢɬɦɨɜ ɩɪɢɧɹɬɨ ɨɰɟɧɢɜɚɬɶ ɩɨɪɹɞɨɤ ɫɥɨɠɧɨɫɬɢ.

Ƚɨɜɨɪɹɬ, ɱɬɨ ɮɭɧɤɰɢɹ f(n) ɢɦɟɟɬ ɫɥɨɠɧɨɫɬɶ ɩɨɪɹɞɤɚ g(n), ɟɫɥɢ ɫɭɳɟɫɬɜɭɸɬ ɬɚɤɢɟ ɩɨɥɨɠɢɬɟɥɶɧɵɟ ɤɨɧɫɬɚɧɬɵ c ɢ n0, ɱɬɨ ɞɥɹ ɜɫɟɯ n t n0 , f(n) d c g(n) [7]. ɗɬɨɬ ɮɚɤɬ ɡɚɩɢɫɵɜɚɟɬɫɹ ɬɚɤ: f(n) ɟɫɬɶ O(g(n)). Ɉɛɵɱɧɨ ɪɚɫɫɦɚɬɪɢɜɚɸɬɫɹ ɩɨɥɨɠɢɬɟɥɶɧɵɟ ɮɭɧɤɰɢɢ ɧɚɬɭɪɚɥɶɧɵɯ ɱɢɫɟɥ. ɇапример, ɮɭɧɤɰɢɹ f(n) = 10 n3 ɟɫɬɶ O(n3), ɬ.ɤ. ɫɭɳɟɫɬɜɭɸɬ c=10 ɢ n0 = 1, ɞɥɹ ɤɨɬɨɪɵɯ 10 n3 d 10 n3 . ɇɟɜɟɪɧɨ, ɱɬɨ 10 n3 ɟɫɬɶ O(n2), ɬɚɤ ɤɚɤ ɞɥɹ ɥɸɛɨɝɨ ɫɤɨɥɶ ɭɝɨɞɧɨ ɛɨɥɶɲɨɝɨ ɧɚɩɟɪɟɞ ɡɚɞɚɧɧɨɝɨ ɡɧɚɱɟɧɢɹ ɤɨɧɫɬɚɧɬɵ c ɧɚɣɞɟɬɫɹ ɬɚɤɨɟ ɡɧɚɱɟɧɢɟ n0 ɚɪɝɭɦɟɧɬɚ, ɱɬɨ f(n) t c g(n) ɞɥɹ ɜɫɟɯ n t n0.

ɉɪɢ ɨɰɟɧɤɟ ɩɨɪɹɞɤɚ ɜɪɟɦɟɧɧɨɣ ɫɥɨɠɧɨɫɬɢ ɨɩɪɟɞɟɥɹɟɬɫɹ ɡɚɜɢɫɢɦɨɫɬɶ ɱɢɫɥɚ ɲɚɝɨɜ ɜ ɚɥɝɨɪɢɬɦɟ ɨɬ ɪɚɡɦɟɪɚ ɜɯɨɞɚ. ɒɚɝɨɦ ɫɱɢɬɚɟɬɫɹ ɬàêîé ɮɪɚɝɦɟɧɬ ɚɥɝɨɪɢɬɦɚ, ɜɪɟɦɹ ɪɟɚɥɢɡɚɰɢɢ ɤɨɬɨɪɨɝɨ ɧɟ ɡɚɜɢɫɢɬ ɨɬ ɪɚɡɦɟɪɚ ɜɯɨɞɚ, ɚ ɱɢɫɥɨ ɪɟɚɥɢɡɚɰɢɣ ɷɬɨɝɨ ɮɪɚɝɦɟɧɬɚ ɡɚɜɢɫɢɬ ɨɬ ɪɚɡɦɟɪɚ ɜɯɨɞɚ. ɇɚɩɪɢɦɟɪ, ɲɚɝɨɦ ɹɜɥɹɟɬɫɹ ɬɟɥɨ ɰɢɤɥɚ, ɧɟɡɚɜɢɫɢɦɨ ɨɬ ɱɢɫɥɚ ɫɨɞɟɪɠɚɳɢɯɫɹ ɜ ɧɟɦ ɨɩɟɪɚɬɨɪɨɜ, ɟɫɥɢ ɨɧɨ ɧɟ ɫɨɞɟɪɠɢɬ ɜɥɨɠɟɧɧɵɯ ɰɢɤɥɨɜ, ɚ ɩɚɪɚɦɟɬɪ ɰɢɤɥɚ ɫɜɹɡɚɧ ɫ ɪɚɡɦɟɪɨɦ ɜɯɨɞɚ.

ɉɪɢ ɨɩɪɟɞɟɥɟɧɢɢ ɩɨɪɹɞɤɚ ɟɦɤɨɫɬɧɨɣ ɫɥɨɠɧɨɫɬɢ, ɜ ɤɚɱɟɫɬɜɟ ɟɞɢɧɢɰɵ ɧɟɨɛɯɨɞɢɦɨ ɜɵɛɪɚɬɶ ɧɟɤɨɬɨɪɵɣ ɷɥɟɦɟɧɬɚɪɧɵɣ ɜ ɞɚɧɧɨɦ ɤɥɚɫɫɟ ɚɥɝɨɪɢɬɦɨɜ ɨɛɴɟɤɬ. Ɍɚɤɢɦ ɨɛɴɟɤɬɨɦ ɜ ɡɚɞɚɱɟ ɥɨɝɢɱɟɫɤɨɝɨ ɜɵɜɨɞɚ ɧɚ ɨɫɧɨɜɟ ɦɟɬɨɞɚ ɪɟɡɨɥɸɰɢɣ ɫɥɟɞɭɟɬ ɫɱɢɬɚɬɶ ɥɢɬɟɪɚɥ. ɉɪɢ ɷɬɨɦ ɬɨɱɧɵɣ ɨɛɴɟɦ ɩɚɦɹɬɢ (ɜ ɛɚɣɬɚɯ), ɡɚɧɢɦɚɟɦɨɣ ɨɞɧɢɦ ɥɢɬɟɪɚɥɨɦ, ɡɚɜɢɫɢɬ ɨɬ ɜɵɛɪɚɧɧɵɯ ɬɢɩɨɜ ɢ ɫɬɪɭɤɬɭɪ ɞɚɧɧɵɯ ɢ ɧɟ ɜɥɢɹɟɬ ɧɚ ɩɨɪɹɞɨɤ ɫɥɨɠɧɨɫɬɢ.

ɉɪɢ ɬɟɨɪɟɬɢɱɟɫɤɨɦ ɚɧɚɥɢɡɟ ɩɨɪɹɞɤɚ ɫɥɨɠɧɨɫɬɢ ɚɥɝɨɪɢɬɦɨɜ ɩɪɢɧɹɬɨ ɨɰɟɧɢɜɚɬɶ ɫɥɨɠɧɨɫɬɶ ɜ ɯɭɞɲɟɦ ɫɥɭɱɚɟ. Ɍɟɨɪɟɬɢɱɟɫɤɚɹ ɨɰɟɧɤɚ ɫɪɟɞɧɟɣ ɫɥɨɠɧɨɫɬɢ, ɤɚɤ ɩɪɚɜɢɥɨ, ɜɟɫɶɦɚ ɡɚɬɪɭɞɧɢɬɟɥɶɧɚ, ɬ.ɤ. ɩɪɟɞɩɨɥɚɝɚɟɬ ɭɱɟɬ ɜɫɟɜɨɡɦɨɠɧɵɯ ɤɨɦɛɢɧɚɰɢɣ ɜɯɨɞɧɵɯ ɞɚɧɧɵɯ ɢ ɜɟɪɨɹɬɧɨɫɬɟɣ ɢɯ ɩɨɹɜɥɟɧɢɹ. Ɉɧɚ ɦɨɠɟɬ ɛɵɬɶ ɩɨɥɭɱɟɧɚ (ɜ ɧɟɤɨɬɨɪɨɦ ɩɪɢɛɥɢɠɟɧɢɢ) ɷɤɫɩɟɪɢɦɟɧɬɚɥɶɧɵɦ ɩɭɬɟɦ ɫ ɩɨɦɨɳɶɸ ɩɪɨɝɪɚɦɦɧɨ ɪɟɚɥɢɡɨɜɚɧɧɨɝɨ ɚɥɝɨɪɢɬɦɚ [***].

ɉɪɢ ɨɰɟɧɤɟ ɫɥɨɠɧɨɫɬɟɣ ɦîãóò ɢɫɩɨɥɶɡɨɜɚɬɶɫɹ ɪɚɡɥɢɱɧɵɟ ɤɪɢɬɟɪɢɢ. Ɋɚɜɧɨɦɟɪɧɵɣ ɜɟɫɨɜɨɣ ɤɪɢɬɟɪɢɣ ɩɪɟɞɩɨɥɚɝɚɟɬ, ɱɬɨ ɤɚɠɞɚɹ ɤɨɦɚɧɞɚ

(ɨɩɟɪɚɬɨɪ) ɡɚɬɪɚɱɢɜɚɟɬ ɨɞɧɭ ɟɞɢɧɢɰɭ ɜɪɟɦɟɧɢ ɢ ɤɚɠɞɚɹ ɩɟɪɟɦɟɧɧɚɹ ɜ ɚɥɝɨɪɢɬɦɟ ɡɚɧɢɦɚɟɬ ɨɞɧɭ ɹɱɟɣɤɭ ɩɚɦɹɬɢ, ɧɟɡɚɜɢɫɢɦɨ ɨɬ ɩɪɢɧɢɦɚɟɦɵɯ ɟɣ ɡɧɚɱɟɧɢɣ.

Ʌɨɝɚɪɢɮɦɢɱɟɫɤɢɣ ɜɟɫɨɜɨɣ ɤɪɢɬɟɪɢɣ ɭɱɢɬɵɜɚɟɬ ɨɝɪɚɧɢɱɟɧɧɨɫɬɶ ɪɚɡɦɟɪɚ ɪɟɚɥɶɧɨɣ ɹɱɟɣɤɢ ɩɚɦɹɬɢ. ɉɭɫɬɶ l(i)- ɥɨɝɚɪɢɮɦɢɱɟɫɤɚɹ ɮɭɧɤɰɢɹ ɧɚ ɰɟɥɵɯ ɱɢɫɥɚɯ, ɨɩɪɟɞɟɥɟɧɧɚɹ ɫɥɟɞɭɸɳɢɦ ɨɛɪɚɡɨɦ:

§ [ log2¦ i ¦ ] + 1, ɩɪɢ i z 0;

ɨɛɪɚɛɚɬɵɜɚɟɦɵɯ ɨɩɟɪɚɧɞɨɜ ɢ ɨɩɪɟɞɟɥɹɟɬɫɹ ɡɧɚɱɟɧɢɟɦ l(i), ɝɞɟ i - ɜɟɥɢɱɢɧɚ ɨɛɪɚɛɚɬɵɜɚɟɦɨɝɨ ɞɚɧɧɨɣ ɤɨɦɚɧɞɨɣ ɨɩɟɪɚɧɞɚ.

ȼɪɟɦɟɧɧɚɹ ɫɥɨɠɧɨɫɬɶ ɩɪɢ ɥɨɝɚɪɢɮɦɢɱɟɫɤɨɦ ɜɟɫɨɜɨɦ ɤɪɢɬɟɪɢɢ. Ʌɨɝɚɪɢɮɦɢɱɟɫɤɚɹ ɜɪɟɦɟɧɧɚɹ ɫɥɨɠɧɨɫɬɶ ɨɩɟɪɚɰɢɣ ɢɧɤɪɟɦɟɧɬɚɰɢɢ ɢ ɫɪɚɜɧɟɧɢɹ ɫ ɝɪɚɧɢɱɧɵɦ ɡɧɚɱɟɧɢɟɦ ɩɚɪɚɦɟɬɪɚ ɰɢɤɥɚ ɜ ɨɫɧɨɜɧɨɣ ɩɪɨɝɪɚɦɦɟ ɧɚ i-ɨɦ ɩɪɨɯɨɞɟ ɟɫɬɶ log(i). ɋɭɦɦɚɪɧɚɹ ɫɥɨɠɧɨɫɬɶ ɷɬɢɯ ɨɩɟɪɚɰɢɣ ɧɚ ɜɫɟɯ ɩɪɨɯɨɞɚɯ ɨɫɧɨɜɧɨɣ ɩɪɨɝɪɚɦɦɵ:

n

¦ log(i) = log(n!) i=2

ȼ ɩɪɨɰɟɞɭɪɟ elem_up ɥɨɝɚɪɢɮɦɢɱɟɫɤɚɹ ɜɪɟɦɟɧɧɚɹ ɫɥɨɠɧɨɫɬɶ ɫɤɥɚɞɵɜɚɟɬɫɹ ɢɡ ɞɜɭɯ ɱɚɫɬɟɣ. ȼɨ-ɩɟɪɜɵɯ, ɪɚɛɨɬɚ ɫɨ ɫɱɟɬɱɢɤɨɦ "ɜɫɩɥɵɜɚɧɢɹ" j. Ɍɚɤ ɤɚɤ ɨɧ ɜɵɩɨɥɧɹɟɬ ɨɛɪɚɬɧɵɣ ɫɱɟɬ ɨɬ i ɞɨ 1, ɬɨ ɜɪɟɦɟɧɧɚɹ ɫɥɨɠɧɨɫɬɶ ɷɬɨɣ ɨɩɟɪɚɰɢɢ ɞɥɹ i-ɝɨ ɩɪɨɯɨɞɚ ɰɢɤɥɚ ɨɫɧɨɜɧɨɣ ɩɪɨɝɪɚɦɦɵ ɟɫɬɶ:

log(i) + log(i-1) + ... + log1 = log(i!).

Ɂɚ ɜɪɟɦɹ ɜɫɟɯ n ɩɪɨɯɨɞɨɜ:

nn

¦log(i!) = log( (i!)) .

ɩɟɪɟɫɬɚɧɨɜɤɚ). Ʌɨɝɚɪɢɮɦɢɱɟɫɤɚɹ ɫɥɨɠɧɨɫɬɶ ɷɬɨɣ ɨɩɟɪɚɰɢɢ ɨɩɪɟɞɟɥɹɟɬɫɹ ɡɧɚɱɟɧɢɹɦɢ ɷɥɟɦɟɧɬɨɜ ɦɚɫɫɢɜɚ ɢ ɪɚɜɧɚ log(Amax), ɝɞɟ Amax - ɦɚɤɫɢɦɚɥɶɧɨɟ ɡɧɚɱɟɧɢɟ ɷɥɟɦɟɧɬɨɜ ɦɚɫɫɢɜɚ. ɑɢɫɥɨ ɲɚɝɨɜ ɧɚ i-ɨɦ ɩɪɨɯɨɞɟ ɨɫɧɨɜɧɨɣ ɩɪɨɝɪɚɦɦɵ ɜ ɯɭɞɲɟɦ ɫɥɭɱɚɟ ɪɚɜɧɨ i log(Amax). Ɂɚ ɜɫɟ ɩɪɨɯɨɞɵ ɢɦɟɟɦ:

n

¦(i log(Amax)) = (n (n+1)/2) log(Amax). i=2

Ɍɨɝɞɚ ɫɭɦɦɚɪɧɚɹ ɜɪɟɦɟɧɧɚɹ ɫɥɨɠɧɨɫɬɶ ɩɪɢ ɥɨɝɚɪɢɮɦɢɱɟɫɤɨɦ ɤɪɢɬɟɪɢɢ

ɟɫɬɶ: n

log(n!) + log( (i!)) + (n (n+1)/2) log(Amax). i=1

Ɉɤɨɧɱɚɬɟɥɶɧɨ ɞɥɹ ɜɪɟɦɟɧɧɨɣ ɫɥɨɠɧɨɫɬɢ ɩɪɢ ɥɨɝɚɪɢɮɦɢɱɟɫɤɨɦ ɜɟɫɨɜɨɦ ɤɪɢɬɟɪɢɢ ɢɦɟɟɦ

n

O(MAX(log( (i!)), n2 log(Amax)). i=1

ȿɦɤɨɫɬɧɚɹ ɫɥɨɠɧɨɫɬɶ ɩɪɢ ɪɚɜɧɨɦɟɪɧɨɦ ɜɟɫɨɜɨɦ ɤɪɢɬɟɪɢɢ. Ɉɱɟɜɢɞɧɨ ɨɩɪɟɞɟɥɹɟɬɫɹ ɪɚɡɦɟɪɨɦ n ɦɚɫɫɢɜɚ, ɩɨɷɬɨɦɭ ɟɫɬɶ O(n).

ȿɦɤɨɫɬɧɚɹ ɫɥɨɠɧɨɫɬɶ ɩɪɢ ɥɨɝɚɪɢɮɦɢɱɟɫɤɨɦ ɜɟɫɨɜɨɦ ɤɪɢɬɟɪɢɢ. Ɉɩɪɟɞɟɥɹɟɬɫɹ ɫ ɨɞɧɨɣ ɫɬɨɪɨɧɵ ɪɚɡɦɟɪɨɦ ɦɚɫɫɢɜɚ ɢ ɟɝɨ ɷɥɟɦɟɧɬɨɜ, ɚ ɫ ɞɪɭɝɨɣ - ɟɦɤɨɫɬɶɸ ɫɱɟɬɱɢɤɚ:

log(n) + n log ¦Amax¦.

Ɉɤɨɧɱɚɬɟɥɶɧɨ ɢɦɟɟɦ O(n log ¦Amax¦).

ɍɩɪɚɠɧɟɧɢɹ

1. Ɉɩɪɟɞɟɥɢɬɶ ɜɪɟɦɟɧɧɭɸ ɢ ɟɦɤɨɫɬɧɭɸ ɫɥɨɠɧɨɫɬɶ ɚɥɝɨɪɢɬɦɨɜ ɪɟɲɟɧɢɹ ɫɥɟɞɭɸɳɢɯ ɡɚɞɚɱ ɩɪɢ ɪɚɜɧɨɦɟɪɧɨɦ ɢ ɥɨɝɚɪɢɮɦɢɱɟɫɤɨɦ ɜɟɫɨɜɵɯ ɤɪɢɬɟɪɢɹɯ.

ɚ) ȼɵɱɢɫɥɢɬɶ n!.

ɛ) ȼ ɦɚɫɫɢɜɟ èç n ɰɟɥɵɯ ɱɢɫɟɥ ɧɚɣɬɢ ɜɫɟ ɩɚɪɵ ɷɥɟɦɟɧɬɨɜ, ɫɭɦɦɚ ɤɨɬɨɪɵɯ ɱɟɬɧɚ ɢ ɫɮɨɪɦɢɪɨɜɚɬɶ ɧɨɜɵɣ ɦɚɫɫɢɜ ɢɡ ɷɬɢɯ ɫɭɦɦ.

â) ȼɵɱɢɫɥɢɬɶ nn.

ɝ) ȼɵɱɢɫɥɢɬɶ ɫɪɟɞɧɟɟ ɡɧɚɱɟɧɢɟ ɷɥɟɦɟɧɬɨɜ ɦɚɫɫɢɜɚ ɢɡ n ɱɢɫɟɥ. ɞ) ȼɵɱɢɫɥɢɬɶ ɱɢɫɥɨ ɪɚɡɦɟɳɟɧɢɣ A(n,m)= n!/(m! (n-m)!).

ɟ) ȼɵɱɢɫɥɢɬɶ ɦɚɤɫɢɦɚɥɶɧɨɟ ɡɧɚɱɟɧɢɟ ɜ ɦɚɫɫɢɜɟ ɱɢɫɟɥ.

ɠ) Â ɦɧɨɠɟɫɬɜɟ ɢɡ n ɞɢɡɴɸɧɤɬɨɜ ɧɚɣɬɢ ɢ ɢɫɤɥɸɱɢɬɶ ɜɫɟ ɧɚɞɫɥɭɱɚɢ. ɡ) Â ɦɧɨɠɟɫɬɜɟ ɢɡ n ɞɢɡɴɸɧɤɬɨɜ ɧɚɣɬɢ ɢ ɢɫɤɥɸɱɢɬɶ ɜɫɟ ɬɚɜɬɨɥɨɝɢɢ.

ɢ) ȼ ɦɧɨɠɟɫɬɜɟ ɢɡ n ɞɢɡɴɸɧɤɬɨɜ ɧɚɣɬɢ ɢ ɢɫɤɥɸɱɢɬɶ ɜɫɟ ɞɢɡɴɸɧɤɬɵ ɫ ɭɧɢɤɚɥɶɧɵɦɢ ɥɢɬɟɪɚɥɚɦɢ.

ɤ) ȼ ɦɚɫɫɢɜɟ èç n ɰɟɥɵɯ ɱɢɫɟɥ ɧɚɣɬɢ ɜɫɟ ɬɪɨɣɤɢ ɷɥɟɦɟɧɬɨɜ, ɜ ɤɨɬɨɪɵɯ ɫɭɦɦɚ ɞɜɭɯ ɷɥɟɦɟɧɬɨɜ ɪɚɜɧɚ ɬɪɟɬɶɟɦɭ, ɩɨɞɫɱɢɬɚɬɶ ɤɨɥɢɱɟɫɬɜɨ ɬɚɤɢɯ ɬɪɨɟɤ.

ɥ) ɍɩɨɪɹɞɨɱɢɬɶ ɦɚɫɫɢɜ èç n ɰɟɥɵɯ ɱɢɫɟɥ ɬɚɤɢɦ ɨɛɪɚɡɨɦ, ɱɬɨɛɵ ɷɥɟɦɟɧɬɵ ɫ ɱɟɬɧɵɦɢ ɢ ɧɟɱɟɬɧɵɦɢ ɡɧɚɱɟɧɢɹɦɢ ɱɟɪɟɞɨɜɚɥɢɫɶ (ɩɨɤɚ ɢɦɟɸɬɫɹ ɷɥɟɦɟɧɬɵ ɪɚɡɧɨɣ ɱɟɬɧɨɫɬɢ).

ɦ) ȼ ɦɚɫɫɢɜɟ èç n ɰɟɥɵɯ ɱɢɫɟɥ ɧɚɣɬɢ ɜɫɟ ɷɥɟɦɟɧɬɵ, ɪɚɜɧɵɟ ɤɜɚɞɪɚɬɭ ɞɪɭɝɨɝɨ ɷɥɟɦɟɧɬɚ ɦɚɫɫɢɜɚ ɢ ɫɨɫɬɚɜɢɬɶ ɦɚɫɫɢɜ ɢɡ ɷɬɢɯ ɷɥɟɦɟɧɬɨɜ.

ɧ) Â ɦɧɨɠɟɫɬɜɟ ɢɡ n ɞɢɡɴɸɧɤɬɨɜ ɧɚɣɬɢ ɢ ɢɫɤɥɸɱɢɬɶ ɜɫɟ ɨɞɢɧɚɤɨɜɵɟ ɞɢɡɴɸɧɤɬɵ.

ɉɊȺɄɌɂɑȿɋɄɈȿ ɁȺɇəɌɂȿ ʋ 4

əɡɵɤ ɥɨɝɢɤɢ ɩɪɟɞɢɤɚɬɨɜ

ɐɟɥɶ ɡɚɧɹɬɢɹ: ɉɨɥɭɱɢɬɶ ɧɚɜɵɤɢ ɮɨɪɦɚɥɶɧɨɣ ɡɚɩɢɫɢ ɪɚɫɫɭɠɞɟɧɢɣ ɫ ɢɫɩɨɥɶɡɨɜɚɧɢɟɦ ɹɡɵɤɚ ɥɨɝɢɤɢ ɩɪɟɞɢɤɚɬɨɜ.

Ɍɟɨɪɟɬɢɱɟɫɤɢɟ ɫɜɟɞɟɧɢɹ Ⱥɥɮɚɜɢɬ ɹɡɵɤɚ ɥɨɝɢɤɢ ɩɪɟɞɢɤɚɬɨɜ ɜɤɥɸɱɚɟɬ ɫɥɟɞɭɸɲɢɟ ɝɪɭɩɩɵ

ɫɢɦɜɨɥɨɜ [1, 3, 5]:

-ɩɪɟɞɦɟɬɧɵɟ ɤɨɧɫɬɚɧɬɵ: a, b, c, ...;

-ɩɪɟɞɦɟɬɧɵɟ ɩɟɪɟɦɟɧɧɵɟ: x, y, z, ...;

-ɮɭɧɤɰɢɨɧɚɥɶɧɵɟ ɫɢɦɜɨɥɵ: f, g, h, ...;

-ɩɪɟɞɢɤɚɬɧɵɟ ɫɢɦɜɨɥɵ: P, Q, R, ...;

-ɥɨɝɢɱɟɫɤɢɟ ɫɜɹɡɤɢ: , & , , o , l;

-ɤɜɚɧɬɨɪɵ: , .

Ʉɪɨɦɟ ɬɨɝɨ, ɞɥɹ ɡɚɞɚɧɢɹ ɩɨɪɹɞɤɚ ɨɩɟɪɚɰɢɣ ɦɨɝɭɬ ɢɫɩɨɥɶɡɨɜɚɬɶɫɹ ɫɤɨɛɤɢ. Ɇɧɨɠɟɫɬɜɨ D ɨɛɴɟɤɬɨɜ, ɨ ɤɨɬɨɪɵɯ ɜɟɞɟɬɫɹ ɪɚɫɫɭɠɞɟɧɢɟ, ɧɚɡɵɜɚɟɬɫɹ

ɨɛɥɚɫɬɶɸ ɢɧɬɟɪɩɪɟɬɚɰɢɢ ɹɡɵɤɚ ɥɨɝɢɤɢ ɩɪɟɞɢɤɚɬɨɜ. ɇɚɩɪɢɦɟɪ, ɨɛɥɚɫɬɶɸ ɢɧɬɟɪɩɪɟɬɚɰɢɢ ɦɨɠɟɬ ɹɜɥɹɬɶɫɹ ɦɧɨɠɟɫɬɜɨ ɜɫɟɯ ɞɟɣɫɬɜɢɬɟɥɶɧɵɯ ɱɢɫɟɥ, ɦɧɨɠɟɫɬɜɨ ɫɬɭɞɟɧɬɨɜ ɋɉɛȽɗɌɍ , ɥɢɛɨ ɥɸɛɨɟ ɞɪɭɝɨɟ ɦɧɨɠɟɫɬɜɨ ɪɟɚɥɶɧɵɯ ɢɥɢ ɦɵɫɥɢɦɵɯ ɨɛɴɟɤɬɨɜ.

ɉɪɟɞɦɟɬɧɵɟ ɤɨɧɫɬɚɧɬɵ ɫɨɨɬɜɟɬɫɬɜɭɸɬ ɤɨɧɤɪɟɬɧɵɦ ɷɥɟɦɟɧɬɚɦ ɦɧɨɠɟɫɬɜɚ D, ɚ ɩɪɟɞɦɟɬɧɵɟ ɩɟɪɟɦɟɧɧɵɟ ɦɨɝɭɬ ɩɪɢɧɢɦɚɬɶ ɡɧɚɱɟɧɢɹ ɜ ɦɧɨɠɟɫɬɜɟ D.

Ɏɭɧɤɰɢɨɧɚɥɶɧɵɟ ɫɢɦɜɨɥɵ ɫɨɨɬɜɟɬɫɬɜɭɸɬ ɮɭɧɤɰɢɹɦ ɡɚɞɚɧɧɵɦ ɧɚ ɨɛɥɚɫɬɢ ɢɧɬɟɪɩɪɟɬɚɰɢɢ. Ɏɭɧɤɰɢɨɧɚɥɶɧɵɣ ɫɢɦɜɨɥ ɜɦɟɫɬɟ ɫɨ ɫɩɢɫɤɨɦ ɚɪɝɭɦɟɧɬɨɜ ɨɛɪɚɡɭɟɬ ɮɭɧɤɰɢɨɧɚɥɶɧɭɸ ɮɨɪɦɭ. ɇɚɩɪɢɦɟɪ, ɟɫɥɢ D - ɦɧɨɠɟɫɬɜɨ ɱɢɫɟɥ, ɬɨ ɮɭɧɤɰɢɨɧɚɥɶɧɚɹ ɮɨɪɦɚ f(x, y) ɦɨɠɟɬ ɢɧɬɟɪɩɪɟɬɢɪɨɜɚɬɶɫɹ ɤɚɤ ɞɜɭɦɟɫɬɧɚɹ ɮɭɧɤɰɢɹ ɫɥɨɠɟɧɢɹ ɱɢɫɟɥ: x + y.

Ɍɟɪɦɨɦ ɹɜɥɹɟɬɫɹ ɜɫɹɤɚɹ ɩɪɟɞɦɟɬɧɚɹ ɤɨɧɫɬɚɧɬɚ, ɩɪɟɞɦɟɬɧɚɹ ɩɟɪɟɦɟɧɧɚɹ ɥɢɛɨ ɮɭɧɤɰɢɨɧɚɥɶɧɚɹ ɮɨɪɦɚ. Ⱥɪɝɭɦɟɧɬɚɦɢ ɮɭɧɤɰɢɨɧɚɥɶɧɨɣ ɮɨɪɦɵ ɦɨɝɭɬ ɛɵɬɶ ɥɸɛɵɟ ɬɟɪɦɵ, ɧɚɩɪɢɦɟɪ f(a, x, g(c, z)).

ȼɫɹɤɨɦɭ ɩɪɟɞɢɤɚɬɧɨɦɭ ɫɢɦɜɨɥɭ ɫɨɨɬɜɟɬɫɬɜɭɟɬ ɫɜɨɣɫɬɜɨ (ɨɞɧɨɦɟɫɬɧɵɣ ɩɪɟɞɢɤɚɬ) ɢɥɢ ɨɬɧɨɲɟɧɢɟ (n-ɦɟɫɬɧɵɣ ɩɪɟɞɢɤɚɬ, ɝɞɟ nt2) ɧɚ ɨɛɴɟɤɬɚɯ ɨɛɥɚɫɬɢ ɢɧɬɟɪɩɪɟɬɚɰɢɢ. ɉɪɟɞɢɤɚɬɧɚɹ ɮɨɪɦɚ (ɢɥɢ ɚɬɨɦ) - ɷɬɨ ɩɪɟɞɢɤɚɬɧɵɣ ɫɢɦɜɨɥ ɜɦɟɫɬɟ ɫɨ ɫɩɢɫɤɨɦ ɫɜɨɢɯ ɚɪɝɭɦɟɧɬɨɜ-ɬɟɪɦɨɜ. ɇɚɩɪɢɦɟɪ, ɨɬɧɨɲɟɧɢɸ “ɛɨɥɶɲɟ” ɧɚ ɦɧɨɠɟɫɬɜɟ ɱɢɫɟɥ ɦɨɠɟɬ ɛɵɬɶ ɫɨɩɨɫɬɚɜɥɟɧɚ ɞɜɭɦɟɫɬɧɚɹ ɩɪɟɞɢɤɚɬɧɚɹ ɮɨɪɦɚ P(x, y). ɉɨɫɤɨɥɶɤɭ ɩɪɢ ɩɨɞɫɬɚɧɨɜɤɟ ɩɪɟɞɦɟɬɧɵɯ ɤɨɧɫɬɚɧɬ ɩɪɟɞɢɤɚɬɧɚɹ ɮɨɪɦɚ ɩɪɢɧɢɦɚɟɬ ɡɧɚɱɟɧɢɟ T(true) ɢɥɢ F(false), ɦɨɠɧɨ ɫɱɢɬɚɬɶ, ɱɬɨ n-ɦɟɫɬɧɵɣ ɩɪɟɞɢɤɚɬ ɨɩɪɟɞɟɥɹɟɬ ɮɭɧɤɰɢɸ: Dn o {F, T}.

ɉɨɧɹɬɢɟ ɮɨɪɦɭɥɵ ɜ ɥɨɝɢɤɟ ɩɪɟɞɢɤɚɬɨɜ ɨɩɪɟɞɟɥɹɟɬɫɹ ɫɥɟɞɭɸɳɢɦ ɨɛɪɚɡɨɦ:

- ɜɫɹɤɢɣ ɚɬɨɦ ɟɫɬɶ ɮɨɪɦɭɥɚ;

P(x, y) - “x = y”.

Ɉɤɨɧɱɚɬɟɥɶɧɨ, ɡɚɩɢɲɟɦ ɮɨɪɦɭɥɭ: x y zP(f(x, y), z).

ɍɩɪɚɠɧɟɧɢɹ 1. Ɂɚɩɢɫɚɬɶ ɧɚ ɹɡɵɤɟ ɥɨɝɢɤɢ ɩɪɟɞɢɤɚɬɨɜ ɫɥɟɞɭɸɳɢɟ ɭɬɜɟɪɠɞɟɧɢɹ:

ɚ) Ⱦɥɹ ɥɸɛɵɯ ɬɪɟɯ ɱɢɫɟɥ, ɟɫɥɢ ɢɯ ɫɭɦɦɚ - ɱɟɬɧɚ, ɬɨ ɯɨɬɹ ɛɵ ɨɞɧɨ ɢɡ ɷɬɢɯ ɱɢɫɟɥ - ɱɟɬɧɨ.

ɛ) Ⱦɥɹ ɥɸɛɵɯ ɞɜɭɯ ɱɢɫɟɥ, ɫɭɦɦɚ ɤɨɬɨɪɵɯ - ɱɟɬɧɚ, ɥɢɛɨ ɨɛɚ ɫɥɚɝɚɟɦɵɯ - ɱɟɬɧɵ, ɥɢɛɨ ɨɛɚ - ɧɟɱɟɬɧɵ.

ɜ) Ⱦɥɹ ɥɸɛɵɯ ɞɜɭɯ ɱɢɫɟɥ, ɟɫɥɢ ɢɯ ɫɭɦɦɚ - ɱɟɬɧɚ, ɚ ɩɪɨɢɡɜɟɞɟɧɢɟ - ɧɟɱɟɬɧɨ, ɬɨ ɨɛɚ ɱɢɫɥɚ ɧɟɱɟɬɧɵ.

ɝ) Ⱦɥɹ ɥɸɛɵɯ ɬɪɟɯ ɱɢɫɟɥ, ɟɫɥɢ ɢɯ ɩɪɨɢɡɜɟɞɟɧɢɟ - ɧɟɱɟɬɧɨ, ɬɨ ɜɫɟ ɬɪɢ ɱɢɫɥɚ - ɧɟɱɟɬɧɵ.

ɞ) ɇɢ ɨɞɧɚ ɠɟɧɳɢɧɚ ɧɟ ɹɜɥɹɟɬɫɹ ɨɞɧɨɜɪɟɦɟɧɧɨ ɩɨɥɢɬɢɤɨɦ ɢ ɞɨɦɚɲɧɟɣ ɯɨɡɹɣɤɨɣ.

ɟ) ɇɟɤɨɬɨɪɵɟ ɠɟɧɳɢɧɵ ɨɞɧɨɜɪɟɦɟɧɧɨ ɹɜɥɹɸɬɫɹ ɸɪɢɫɬɚɦɢ ɢ ɱɥɟɧɚɦɢ ɤɨɧɝɪɟɫɫɚ.

ɠ) Ʉɚɠɞɵɣ ɜɬɨɪɨɤɭɪɫɧɢɤ ɩɪɨɱɢɬɚɥ ɯɨɬɹ ɛɵ ɨɞɧɭ ɤɧɢɝɭ.

ɡ) Ʉɬɨ-ɬɨ ɜɫɬɪɟɬɢɥ ɤɨɝɨ-ɬɨ, ɚ ɤɬɨ-ɬɨ ɬɚɤ ɧɢɤɨɝɨ ɢ ɧɟ ɜɫɬɪɟɬɢɥ. ɢ) Ʉɚɠɞɨɟ ɩɪɨɫɬɨɟ ɱɢɫɥɨ, ɧɟɪɚɜɧɨɟ ɞɜɭɦ, ɧɟɱɟɬɧɨ.

ɤ) ɋɭɳɟɫɬɜɭɸɬ ɱɢɫɥɚ, ɧɟ ɢɦɟɸɳɢɟ ɨɛɳɢɯ ɞɟɥɢɬɟɥɟɣ, ɤɪɨɦɟ ɟɞɢɧɢɰɵ. ɥ) Ⱦɜɟ ɩɪɹɦɵɟ, ɤɚɠɞɚɹ ɢɡ ɤɨɬɨɪɵɯ ɩɚɪɚɥɥɟɥɶɧɚ ɬɪɟɬɶɟɣ ɩɪɹɦɨɣ,

ɩɚɪɚɥɥɟɥɶɧɵ ɦɟɠɞɭ ɫɨɛɨɣ.

ɦ) ɋɭɞɶɹ Ⱦɠɨɧɫ ɧɟ ɜɨɫɯɢɳɚɟɬɫɹ ɧɢ ɨɞɧɢɦ ɠɭɥɢɤɨɦ.

ɧ) ȿɫɥɢ ɩɨ ɤɪɚɣɧɟɣ ɦɟɪɟ ɨɞɢɧ ɭɱɟɧɢɤ ɪɟɲɢɥ ɜɫɟ ɡɚɞɚɱɢ, ɬɨ ɤɚɠɞɭɸ ɡɚɞɚɱɭ ɪɟɲɢɥ ɩɨ ɤɪɚɣɧɟɣ ɦɟɪɟ ɨɞɢɧ ɭɱɟɧɢɤ.

ɨ) ȼ Ɇɨɫɤɜɟ ɠɢɜɟɬ ɠɟɧɳɢɧɚ, ɢɦɟɸɳɚɹ ɛɪɚɬɚ ɜ ɉɟɬɟɪɛɭɪɝɟ, ɬɨɝɞɚ ɢ ɬɨɥɶɤɨ ɬɨɝɞɚ, ɤɨɝɞɚ ɜ ɉɟɬɟɪɛɭɪɝɟ ɠɢɜɟɬ ɦɭɠɱɢɧɚ, ɢɦɟɸɳɢɣ ɫɟɫɬɪɭ ɜ Ɇɨɫɤɜɟ.

2. ɍɤɚɡɚɬɶ ɜɫɟ ɩɨɞɮɨɪɦɭɥɵ, ɚ ɬɚɤɠɟ ɨɛɥɚɫɬɢ ɞɟɣɫɬɜɢɹ ɤɜɚɧɬɢɮɢɤɚɰɢɣ, ɫɜɨɛɨɞɧɵɟ ɢ ɫɜɹɡɚɧɧɵɟ ɜɯɨɠɞɟɧɢɹ ɜɫɟɯ ɩɟɪɟɦɟɧɧɵɯ ɜ ɫɥɟɞɭɸɳɢɯ ɮɨɪɦɭɥɚɯ:

ɚ) x[( P(x) & Q(x)) o y zS(z, x, y)];

ɛ) R(w) z[S(z) l v w(P(v) & S(w))];

ɜ) x[P(x) & y(R(y) & P(y) o zS(x, u, z))]; ɝ) S(t, w) x w[(Q(x, w) o P(x)) o R(w)]; ɞ) [Q(x, y) l y zP(z, y)] o (R(y) zQ(z));

ɟ) v zP(z, v) & Q(v, y) x y(R(x) o T(x, y)); ɠ) x u( S(u, x) R(x, u) Q(t)) l z tP(x, t, z); ɡ) (P(x, w) x w(Q(x, w) & P(x, z)) o R(z, w).

ɉɊȺɄɌɂɑȿɋɄɈȿ ɁȺɇəɌɂȿ ʋ 5 ɉɪɟɨɛɪɚɡɨɜɚɧɢɟ ɮɨɪɦɭɥ ɥɨɝɢɤɢ ɩɪɟɞɢɤɚɬɨɜ

ɜ ɤɥɚɭɡɚɥɶɧɭɸ ɮɨɪɦɭ.

ɐɟɥɶ ɡɚɧɹɬɢɹ: ɩɨɥɭɱɢɬɶ ɩɪɚɤɬɢɱɟɫɤɢɟ ɧɚɜɵɤɢ ɩɪɟɨɛɪɚɡɨɜɚɧɢɹ ɮɨɪɦɭɥ ɢɫɱɢɫɥɟɧɢɹ ɩɪɟɞɢɤɚɬɨɜ ɢɡ ɫɬɚɧɞɚɪɬɧɨɣ ɮɨɪɦɵ ɜ ɤɥɚɭɡɚɥɶɧɭɸ.

Ɍɟɨɪɟɬɢɱɟɫɤɢɟ ɫɜɟɞɟɧɢɹ

ȼɥɨɝɢɤɟ ɩɪɟɞɢɤɚɬɨɜ, ɤɚɤ ɢ ɜ ɥɨɝɢɤɟ ɜɵɫɤɚɡɵɜɚɧɢɣ, ɩɪɢɜɟɞɟɧɢɟ ɮɨɪɦɭɥ

ɤɧɟɤɨɬɨɪɨɣ ɧɨɪɦɚɥɶɧɨɣ (ɤɚɧɨɧɢɱɟɫɤɨɣ) ɮɨɪɦɟ ɩɨɡɜɨɥɹɟɬ ɭɩɪɨɫɬɢɬɶ ɚɥɝɨɪɢɬɦɵ ɩɪɨɜɟɪɤɢ ɢɯ ɫɜɨɣɫɬɜ ɢ, ɜ ɤɨɧɟɱɧɨɦ ɫɱɟɬɟ, ɪɟɲɟɧɢɟ ɩɪɨɛɥɟɦɵ ɞɟɞɭɤɰɢɢ. Ɉɞɧɚɤɨ ɜ ɥɨɝɢɤɟ ɩɪɟɞɢɤɚɬɨɜ ɡɚɞɚɱɚ ɩɪɢɜɟɞɟɧɢɹ ɤ ɧɨɪɦɚɥɶɧɨɣ ɮɨɪɦɟ ɹɜɥɹɟɬɫɹ ɛɨɥɟɟ ɫɥɨɠɧɨɣ ɜɫɥɟɞɫɬɜɢɟ ɛɨɥɟɟ ɛɨɝɚɬɨɝɨ ɫɢɧɬɚɤɫɢɫɚ ɹɡɵɤɚ,

ɜ ɱɚɫɬɧɨɫɬɢ, ɢɡ-ɡɚ ɧɚɥɢɱɢɹ ɤɜɚɧɬɢɮɢɤɚɰɢɣ, ɫɜɨɛɨɞɧɵɯ ɢ ɫɜɹɡɚɧɧɵɯ ɜɯɨɠɞɟɧɢɣ ɨɞɧɨɣ ɢ ɬɨɣ ɠɟ ɩɟɪɟɦɟɧɧɨɣ ɢ ɞɪ.

ɉɪɟɨɛɪɚɡɨɜɚɧɢɟ ɮɨɪɦɭɥ ɥɨɝɢɤɢ ɩɪɟɞɢɤɚɬɨɜ ɢɡ ɫɬɚɧɞɚɪɬɧɨɣ ɮɨɪɦɵ ɜ ɤɥɚɭɡɚɥɶɧɭɸ ɜɵɩɨɥɧɹɟɬɫɹ ɜ ɬɪɢ ɷɬɚɩɚ:

1.ɉɪɟɨɛɪɚɡɨɜɚɧɢɟ ɜ ɩɪɟɞɜɚɪɟɧɧɭɸ ɮɨɪɦɭ.

2.ɉɨɥɭɱɟɧɢɟ ɡɚɦɤɧɭɬɨɣ ɮɨɪɦɵ ɢ ɫɤɨɥɟɦɢɡɚɰɢɹ.

3.ɉɪɟɨɛɪɚɡɨɜɚɧɢɟ ɦɚɬɪɢɰɵ ɜ ɄɇɎ.

ɉɪɟɞɜɚɪɟɧɧɨɣ ɮɨɪɦɨɣ ɜ ɥɨɝɢɤɟ ɩɪɟɞɢɤɚɬɨɜ ɧɚɡɵɜɚɟɬɫɹ ɬɚɤɨɟ ɩɪɟɞɫɬɚɜɥɟɧɢɟ ɮɨɪɦɭɥɵ, ɜ ɤɨɬɨɪɨɦ ɜɫɟ ɤɜɚɧɬɢɮɢɤɚɰɢɢ ɪɚɡɦɟɳɚɸɬɫɹ ɜ ɧɚɱɚɥɟ, ɚ ɡɚɬɟɦ ɫɥɟɞɭɟɬ ɮɨɪɦɭɥɚ, ɧɟ ɫɨɞɟɪɠɚɳɚɹ ɤɜɚɧɬɢɮɢɤɚɰɢɣ. Ʉɨɧɟɱɧɭɸ ɩɨɫɥɟɞɨɜɚɬɟɥɶɧɨɫɬɶ ɤɜɚɧɬɢɮɢɤɚɰɢɣ ɜ ɧɚɱɚɥɟ ɮɨɪɦɭɥɵ ɧɚɡɵɜɚɸɬ ɩɪɟɮɢɤɫɨɦ, ɚ ɧɟ ɫɨɞɟɪɠɚɳɭɸ ɤɜɚɧɬɢɮɢɤɚɰɢɣ ɮɨɪɦɭɥɭ - ɦɚɬɪɢɰɟɣ. Ɍɚɤɢɦ ɨɛɪɚɡɨɦ, ɩɪɟɞɜɚɪɟɧɧɚɹ ɮɨɪɦɚ ɢɦɟɟɬ ɜɢɞ:

.1.2....n M,

ɝɞɟ ɫɢɦɜɨɥ .i ɨɡɧɚɱɚɟɬ ɥɢɛɨ -ɤɜɚɧɬɢɮɢɤɚɰɢɸ, ɥɢɛɨ -ɤɜɚɧɬɢɮɢɤɚɰɢɸ ɞɥɹ i=1,...n, ɚ M - ɦɚɬɪɢɰɚ. Ʉɜɚɧɬɢɮɢɤɚɰɢɢ ɜ ɩɪɟɮɢɤɫɟ ɨɬɧɨɫɹɬɫɹ ɤ ɪɚɡɥɢɱɧɵɦ

ɩɪɟɞɜɚɪɟɧɧɨɣ ɮɨɪɦɵ ɞɥɹ ɩɪɨɢɡɜɨɥɶɧɨɣ ɮɨɪɦɭɥɵ ɥɨɝɢɤɢ ɩɪɟɞɢɤɚɬɨɜ ɜɤɥɸɱɚɟɬ ɫɥɟɞɭɸɳɢɟ ɲɚɝɢ:

1.ɂɫɤɥɸɱɟɧɢɟ ɫɜɹɡɨɤ ɢɦɩɥɢɤɚɰɢɢ ɢ ɷɤɜɢɜɚɥɟɧɬɧɨɫɬɢ.

2.ɉɟɪɟɢɦɟɧɨɜɚɧɢɟ (ɟɫɥɢ ɧɟɨɛɯɨɞɢɦɨ) ɫɜɹɡɚɧɧɵɯ ɩɟɪɟɦɟɧɧɵɯ ɬɚɤɢɦ

ɨɛɪɚɡɨɦ, ɱɬɨɛɵ ɧɢɤɚɤɚɹ ɩɟɪɟɦɟɧɧɚɹ ɧɟ ɢɦɟɥɚ ɛɵ ɨɞɧɨɜɪɟɦɟɧɧɨ ɫɜɨɛɨɞɧɵɯ ɢ ɫɜɹɡɚɧɧɵɯ ɜɯɨɠɞɟɧɢɣ. ɗɬɨ ɞɨɥɠɧɨ ɛɵɬɶ ɜɵɩɨɥɧɟɧɨ ɞɥɹ ɜɫɟɯ ɩɨɞɮɨɪɦɭɥ ɪɚɫɫɦɚɬɪɢɜɚɟɦɨɣ ɮɨɪɦɭɥɵ.

3.ɍɞɚɥɟɧɢɟ ɤɜɚɧɬɢɮɢɤɚɰɢɣ, ɨɛɥɚɫɬɶ ɞɟɣɫɬɜɢɹ ɤɨɬɨɪɵɯ ɧɟ ɫɨɞɟɪɠɢɬ ɜɯɨɠɞɟɧɢɣ ɤɜɚɧɬɢɮɢɰɢɪɨɜɚɧɧɨɣ ɩɟɪɟɦɟɧɧɨɣ.

4.ɋɭɠɟɧɢɟ ɨɛɥɚɫɬɢ ɞɟɣɫɬɜɢɹ ɨɬɪɢɰɚɧɢɣ ɢ ɫɧɹɬɢɟ ɞɜɨɣɧɵɯ ɨɬɪɢɰɚɧɢɣ.

ɉɪɢ ɷɬɨɦ ɩɨɦɢɦɨ ɡɚɤɨɧɨɜ ɞɟ Ɇɨɪɝɚɧɚ ɢ ɢɧɜɨɥɸɰɢɢ ɢɫɩɨɥɶɡɭɸɬɫɹ ɫɥɟɞɭɸɳɢɟ ɬɨɠɞɟɫɬɜɚ:

( xA) = x( A);( xA) = x( A).

5. ɉɟɪɟɧɨɫ ɜɫɟɯ ɤɜɚɧɬɢɮɢɤɚɰɢɣ ɜ ɧɚɱɚɥɨ ɮɨɪɦɭɥɵ. Ⱦɥɹ ɷɬɨɝɨ ɢɫɩɨɥɶɡɭɸɬɫɹ ɫɥɟɞɭɸɳɢɟ ɩɪɚɜɢɥɚ:

( xA & xB) = x(A & B); ( xA xB) = x(A B);

( xA & B) = x(A & B), ɟɫɥɢ ɮɨɪɦɭɥɚ B ɧɟ ɫɨɞɟɪɠɢɬ x; ( xA & B) = x(A & B), ɟɫɥɢ ɮɨɪɦɭɥɚ B ɧɟ ɫɨɞɟɪɠɢɬ x. ( xA B) = x(A B), ɟɫɥɢ ɮɨɪɦɭɥɚ B ɧɟ ɫɨɞɟɪɠɢɬ x; ( xA B) = x(A B), ɟɫɥɢ ɮɨɪɦɭɥɚ B ɧɟ ɫɨɞɟɪɠɢɬ x.

ɉɪɢ ɜɵɩɨɥɧɟɧɢɢ ɷɬɨɝɨ ɲɚɝɚ ɧɟɤɨɬɨɪɵɟ ɫɜɹɡɚɧɧɵɟ ɩɟɪɟɦɟɧɧɵɟ ɦɨɝɭɬ ɛɵɬɶ ɩɟɪɟɢɦɟɧɨɜɚɧɵ. ɇɚɩɪɢɦɟɪ, ɮɨɪɦɭɥɚ xP(x) & xQ(x) ɛɭɞɟɬ ɫɧɚɱɚɥɚ ɩɪɟɨɛɪɚɡɨɜɚɧɚ ɜ xP(x) & yQ(y), ɩɨɫɥɟ ɱɟɝɨ ɩɪɢɦɟɧɟɧɵ ɩɪɚɜɢɥɚ ɩɪɟɨɛɪɚɡɨɜɚɧɢɹ

ɉɪɢɦɟɪ. ɉɪɟɨɛɪɚɡɨɜɚɬɶ ɜ ɩɪɟɞɜɚɪɟɧɧɭɸ ɮɨɪɦɭ ɫɥɟɞɭɸɳɭɸ ɮɨɪɦɭɥɭ:

y x( Q(x, y) P(y)) o (R(v) & v z wS(v, z))

Ɋɟɲɟɧɢɟ.

1. ɂɫɤɥɸɱɟɧɢɟ ɫɜɹɡɨɤ ɢɦɩɥɢɤɚɰɢɢ ɢ ɷɤɜɢɜɚɥɟɧɬɧɨɫɬɢ:

y x( Q(x, y) P(y)) (R(v) & v z wS(v, z)) 2. ɉɟɪɟɢɦɟɧɨɜɚɧɢɟ.

y x( Q(x, y) P(y)) (R(v) & u z wS(u, z)) 3. ɍɞɚɥɟɧɢɟ ɧɟɧɭɠɧɵɯ ɤɜɚɧɬɢɮɢɤɚɰɢɣ:

y x( Q(x, y) P(y)) (R(v) & u zS(u, z))

4.ɋɭɠɟɧɢɟ ɨɛɥɚɫɬɢ ɞɟɣɫɬɜɢɹ ɨɬɪɢɰɚɧɢɣ ɢ ɫɧɹɬɢɟ ɞɜɨɣɧɵɯ ɨɬɪɢɰɚɧɢɣ:

y( x( Q(x, y) P(y))) (R(v) & u zS(u, z))y x( ( Q(x, y) P(y))) (R(v) & u zS(u, z))

y x( Q(x, y) & P(y)) (R(v) & u zS(u, z))y x(Q(x, y) & P(y)) (R(v) & u zS(u, z))

5.ɉɟɪɟɧɨɫ ɤɜɚɧɬɢɮɢɤɚɰɢɣ ɜ ɧɚɱɚɥɨ ɮɨɪɦɭɥɵ.

y[ x(Q(x, y) & P(y)) R(v) & u zS(u, z)]y x[Q(x, y) & P(y) R(v) & u zS(u, z)]

y x u[Q(x, y) & P(y) R(v) & zS(u, z)]y x u z[Q(x, y) & P(y) R(v) & S(u, z)]

ɉɨɥɭɱɟɧɚ ɩɪɟɞɜɚɪɟɧɧɚɹ ɮɨɪɦɚ.

ɉɪɟɞɜɚɪɟɧɧɚɹ ɮɨɪɦɚ ɜ ɨɛɳɟɦ ɫɥɭɱɚɟ ɦɨɠɟɬ ɫɨɞɟɪɠɚɬɶ ɫɜɨɛɨɞɧɵɟ ɩɟɪɟɦɟɧɧɵɟ. Ɉɞɧɚɤɨ, ɩɪɢ ɚɧɚɥɢɡɟ ɜɵɩɨɥɧɢɦɨɫɬɢ ɞɨɫɬɚɬɨɱɧɨ ɨɩɟɪɢɪɨɜɚɬɶ ɬɨɥɶɤɨ ɡɚɦɤɧɭɬɵɦɢ ɮɨɪɦɭɥɚɦɢ, ɬ.ɟ. ɮɨɪɦɭɥɚɦɢ ɧɟ ɫɨɞɟɪɠɚɳɢɦɢ ɫɜɨɛɨɞɧɵɯ ɩɟɪɟɦɟɧɧɵɯ. Ⱦɟɣɫɬɜɢɬɟɥɶɧɨ, ɟɫɥɢ A - ɮɨɪɦɭɥɚ, ɫɨɞɟɪɠɚɳɚɹ ɫɜɨɛɨɞɧɵɟ ɩɟɪɟɦɟɧɧɵɟ x0, ..., xn, ɤɨɬɨɪɚɹ (ɩɨɫɥɟ ɩɟɪɟɢɦɟɧɨɜɚɧɢɹ) ɧɟ ɫɨɞɟɪɠɢɬ ɧɢ ɨɞɧɨɝɨ ɫɜɹɡɚɧɧɨɝɨ ɜɯɨɠɞɟɧɢɹ ɷɬɢɯ ɩɟɪɟɦɟɧɧɵɯ, ɬɨ ɡɚɦɤɧɭɬɚɹ ɮɨɪɦɭɥɚx1... xnA ɜɵɩɨɥɧɢɦɚ ɬɨɝɞɚ ɢ ɬɨɥɶɤɨ ɬɨɝɞɚ, ɤɨɝɞɚ ɜɵɩɨɥɧɢɦɚ ɮɨɪɦɭɥɚ A. ɇапример, ɮормула y x[Q(x, y) & S(u, z)] ɩɨɫɥɟ ɩɪɟɨɛɪɚɡɨɜɚɧɢɹ ɜ ɡɚɦɤɧɭɬɭɸ ɮɨɪɦɭ ɩɪɢɦɟɬ ɜɢɞ: u z y x [Q(x, y)& S(u, z)].