Теормин (2006) (мини) (1162021), страница 4
Текст из файла (страница 4)
ɋ ɹɜɥɹɟɬɫɹɫɥɟɞɫɬɜɢɟɦ Ɋ ɬɨɝɞɚ ɢ ɬɨɥɶɤɨ ɬɨɝɞɚ, ɤɨɝɞɚ ɨɧ ɩɪɢɧɚɞɥɟɠɢɬ ɇɇɆ Ɋ.Ɉɩɪɟɞɟɥɟɧɢɟ. ɉɭɫɬɶ Ɋ – ɯɨɪɧɨɜɫɤɚɹ ɥɨɝɢɱɟɫɤɚɹ ɩɪɨɝɪɚɦɦɚ, D A0 m A1 & A2 &...& An ɧɟɤɨɬɨɪɨɟ ɟɟ ɩɪɨɝɪɚɦɦɧɨɟ ɭɬɜɟɪɠɞɟɧɢɟ, G : ? C1 ,..., Cm - ɡɚɩɪɨɫ, ɚ ɩɟɪɟɫɟɱɟɧɢɟ ɮɨɪɦɚɥɶɧɵɯɩɚɪɚɦɟɬɪɨɜ ( VarD ) ɫ ɮɚɤɬɢɱɟɫɤɢɦɢ ( VarG ) ɩɭɫɬɨ. ɉɭɫɬɶ Ci - ɩɨɞɰɟɥɶ ɡɚɩɪɨɫɚ G, ɚT ɇɈɍ (ɋi , A0 ) . Ɍɨɝɞɚ ɡɚɩɪɨɫ G ' : ?(C1 ,..., Ci 1 , A1 , A2 ,..., An , Ci 1 ,..., Cm )T , ɩɨɥɭɱɟɧɧɵɣ ɢɡ Gɡɚɦɟɧɨɣ Ci ɧɚ A1 , A2 ,..., An ɢ ɩɨɫɥɟɞɭɸɳɟɣ ɭɧɢɮɢɤɚɰɢɟɣ, ɧɚɡɵɜɚɟɬɫɹ SLD-ɪɟɡɨɥɶɜɟɧɬɨɣɡɚɩɪɨɫɚ G ɢ ɩɪɨɝɪɚɦɦɧɨɝɨ ɭɬɜɟɪɠɞɟɧɢɹ D ɫ ɇɈɍ T .
ɉɪɢ ɷɬɨɦ Ci ɧɚɡɵɜɚɟɬɫɹ ɜɵɞɟɥɟɧɧɨɣɩɨɞɰɟɥɶɸ, ɚ D – ɚɤɬɢɜɢɡɢɪɨɜɚɧɧɵɦ ɩɪɨɝɪɚɦɦɧɵɦ ɭɬɜɟɪɠɞɟɧɢɟɦ.15Ɉɩɪɟɞɟɥɟɧɢɟ. ɉɭɫɬɶ Ɋ – ɯɨɪɧɨɜɫɤɚɹ ɥɨɝɢɱɟɫɤɚɹ ɩɪɨɝɪɚɦɦɚ. Ɍɨɝɞɚ ɦɧɨɠɟɫɬɜɨɦ ɭɫɩɟɯɨɜ Ɋɛɭɞɟɬ ɧɚɡɵɜɚɬɶɫɹ ɫɥɟɞɭɸɳɟɟ ɦɧɨɠɟɫɬɜɨ SuccP - ɷɬɨ ɦɧɨɠɟɫɬɜɨ ɜɫɟɯ ɚɬɨɦɚɪɧɵɯ ɡɚɩɪɨɫɨɜ,ɢɦɟɸɳɢɯ ɭɫɩɟɲɧɨɟ SLD-ɪɟɡɨɥɸɬɢɜɧɨɟ ɜɵɱɢɫɥɟɧɢɟ ( A BP - ɷɪɛɪɚɧɨɜɫɤɨɦɭ ɛɚɡɢɫɭ Ɋ).Ɉɩɪɟɞɟɥɟɧɢɟ. ɉɭɫɬɶ 2BP - ɦɧɨɠɟɫɬɜɨ ɜɫɟɯ ɩɨɞɦɧɨɠɟɫɬɜ BP (ɦɧɨɠɟɫɬɜɨ ɜɫɟɯ ɷɪɛɪɚɧɨɜɫɤɢɯɢɧɬɟɪɩɪɟɬɚɰɢɣ). Ɉɩɟɪɚɬɨɪɨɦ ɧɟɩɨɫɪɟɞɫɬɜɟɧɧɨɝɨ ɫɥɟɞɨɜɚɧɢɹ ɞɥɹ ɥɨɝɢɱɟɫɤɨɣ ɩɪɨɝɪɚɦɦɵ Ɋɧɚɡɵɜɚɟɬɫɹ ɮɭɧɤɰɢɹ TP : 2 BP o 2 BP , ɬɚɤɚɹ, ɱɬɨ ɞɥɹ ɥɸɛɨɝɨ ɩɨɞɦɧɨɠɟɫɬɜɚ BP (ɨɛɨɡɧɚɱɢɦ ɟɝɨI) TP ( I ) { A : A BP ; A m A1 , A2 ,..., An } , ɝɞɟ Ⱥi ɩɪɢɧɚɞɥɟɠɢɬ I – ɬ.ɟ. ɜɫɟ ɬɨ, ɱɬɨ ɫɥɟɞɭɟɬ ɢɡɢɧɬɟɪɩɪɟɬɚɰɢɢ I ɩɨ ɩɪɚɜɢɥɚɦ ɥɨɝɢɱɟɫɤɨɣ ɩɪɨɝɪɚɦɦɵ Ɋ.ɍɬɜɟɪɠɞɟɧɢɟ. Ⱦɥɹ ɨɩɟɪɚɬɨɪɚ ɧɟɩɨɫɪɟɞɫɬɜɟɧɧɨɝɨ ɫɥɟɞɨɜɚɧɢɹ ɜɵɩɨɥɧɹɸɬɫɹ ɫɜɨɣɫɬɜɚ:I1 I 2 TP ( I1 ) TP ( I 2 )TP ( I1 I 2 ) TP ( I1 ) TP ( I 2 )I BP ; I | P TP ( I ) IɈɩɪɟɞɟɥɟɧɢɟ.
ɂɧɬɟɪɩɪɟɬɚɰɢɹ I ɧɚɡɵɜɚɟɬɫɹ ɧɟɩɨɞɜɢɠɧɨɣ ɬɨɱɤɨɣ ɨɩɟɪɚɬɨɪɚɧɟɩɨɫɪɟɞɫɬɜɟɧɧɨɝɨ ɫɥɟɞɨɜɚɧɢɹ, ɟɫɥɢ ɜɵɩɨɥɧɹɟɬɫɹ ɪɚɜɟɧɫɬɜɨ TP ( I ) I . Ɇɧɨɠɟɫɬɜɨ ɜɫɟɯɧɟɩɨɞɜɢɠɧɵɯ ɬɨɱɟɤ ɨɩɟɪɚɬɨɪɚ ɧɟɩɨɫɪɟɞɫɬɜɟɧɧɨɝɨ ɫɥɟɞɨɜɚɧɢɹ ɨɛɨɡɧɚɱɢɦ ɤɚɤ f pPɈɩɪɟɞɟɥɟɧɢɟ. I 0 ɧɚɡɵɜɚɟɬɫɹ ɧɚɢɦɟɧɶɲɟɣ ɧɟɩɨɞɜɢɠɧɨɣ ɬɨɱɤɨɣ ɨɩɟɪɚɬɨɪɚ TP , ɟɫɥɢɜɵɩɨɥɧɹɸɬɫɹ 2 ɫɜɨɣɫɬɜɚ:1) I 0 - ɧɟɩɨɞɜɢɠɧɚɹ ɬɨɱɤɚ ɨɩɟɪɚɬɨɪɚ TP ;2) ɞɥɹ ɥɸɛɨɣ ɞɪɭɝɨɣ ɧɟɩɨɞɜɢɠɧɨɣ ɬɨɱɤɢ I ɜɵɩɨɥɧɹɟɬɫɹ ɫɜɨɣɫɬɜɨ I 0 I .ɇɚɢɦɟɧɶɲɚɹ ɧɟɩɨɞɜɢɠɧɚɹ ɬɨɱɤɚ ɨɛɨɡɧɚɱɚɟɬɫɹ ɤɚɤ lf pP .Ɍɟɨɪɟɦɚ (ɨ ɧɟɩɨɞɜɢɠɧɵɯ ɬɨɱɤɚɯ).
ȼ ɯɨɪɧɨɜɫɤɨɣ ɥɨɝɢɱɟɫɤɨɣ ɩɪɨɝɪɚɦɦɟ Ɋ ɜɫɟɝɞɚfɫɭɳɟɫɬɜɭɟɬ ɧɚɢɦɟɧɶɲɚɹ ɧɟɩɨɞɜɢɠɧɚɹ ɬɨɱɤɚ, ɢ lf pP*TiP( )M P (ɬ.ɟ. ɧɚɢɦɟɧɶɲɚɹɌɟɨɪɟɦɚ (ɤɨɪɪɟɤɬɧɨɫɬɢ ɨɩɟɪɚɰɢɨɧɧɨɣ ɫɟɦɚɧɬɢɤɢ): ɉɭɫɬɶ Ɋ – ɯɨɪɧɨɜɫɤɚɹ ɥɨɝɢɱɟɫɤɚɹɩɪɨɝɪɚɦɦɚ, G – ɡɚɩɪɨɫ ɤ ɧɟɣ, T - ɜɵɱɢɫɥɟɧɧɵɣ ɨɬɜɟɬ ɧɚ ɡɚɩɪɨɫ G ɤ Ɋ. Ɍɨɝɞɚ ɜɵɱɢɫɥɟɧɧɵɣɨɬɜɟɬ T - ɷɬɨ ɩɪɚɜɢɥɶɧɵɣ ɨɬɜɟɬ.ɋɥɟɞɫɬɜɢɟ. SuccP M P (ɬ.ɟ. ɦɧɨɠɟɫɬɜɨ ɭɫɩɟɯɨɜ ɹɜɥɹɟɬɫɹ ɩɨɞɦɧɨɠɟɫɬɜɨɦ ɧɚɢɦɟɧɶɲɟɣɷɪɛɪɚɧɨɜɫɤɨɣ ɦɨɞɟɥɢ).Ɉɩɪɟɞɟɥɟɧɢɟ.
ɉɭɫɬɶ Ɋ – ɯɨɪɧɨɜɫɤɚɹ ɥɨɝɢɱɟɫɤɚɹ ɩɪɨɝɪɚɦɦɚ, G0 - ɡɚɩɪɨɫ ɤ Ɋ. Ɍɨɝɞɚ ɤɜɚɡɢSLD-ɪɟɡɨɥɸɬɢɜɧɵɦ ɜɵɱɢɫɥɟɧɢɟɦ ɡɚɩɪɨɫɚ G0 ɤ Ɋ ɧɚɡɵɜɚɟɬɫɹ ɩɨɫɥɟɞɨɜɚɬɟɥɶɧɨɫɬɶ ɩɚɪ(G '1 , T '1 ),..., (G 'n , T 'n ), (G 'n 1 , T 'n 1 ) , ɤɨɬɨɪɚɹ ɭɞɨɜɥɟɬɜɨɪɹɟɬ ɬɪɟɛɨɜɚɧɢɸ: ɟɫɥɢ? C1 ,..., Ci 1 , Ci , Ci 1 ,..., Cm , D : A0 m A1 ,..., Ak P ɢ T 'n - ɩɪɨɢɡɜɨɥɶɧɵɣ ɭɧɢɮɢɤɚɬɨɪ Ci ɢA0 , ɬɨ G 'n ?(C1 ,..., Ci 1 , A1 ,..., Ak , Ci 1 ,..., Cm )T 'n .Ɂɚɦɟɬɢɦ, ɱɬɨ SLD-ɪɟɡɨɥɸɬɢɜɧɨɟ ɜɵɱɢɫɥɟɧɢɟ – ɱɚɫɬɧɵɣ ɫɥɭɱɚɣ ɤɜɚɡɢ-SLD-ɪɟɡɨɥɸɬɢɜɧɨɝɨɜɵɱɢɫɥɟɧɢɹ, ɩɨɷɬɨɦɭ ɤɨɪɪɟɤɬɧɨɫɬɶ ɤɜɚɡɢ-SLD-ɪɟɡɨɥɸɬɢɜɧɨɝɨ ɜɵɱɢɫɥɟɧɢɹ ɩɪɟɞɫɬɚɜɥɹɟɬɫɨɛɨɣ ɨɬɞɟɥɶɧɭɸ ɬɟɨɪɟɦɭ.G 'n 1Ɍɟɨɪɟɦɚ (ɨ ɤɜɚɡɢ-SLD-ɪɟɡɨɥɸɬɢɜɧɵɯ ɜɵɱɢɫɥɟɧɢɹɯ): ȿɫɥɢ ɚɬɨɦ ɋ ɜɯɨɞɢɬ ɜ ɧɚɢɦɟɧɶɲɭɸɷɪɛɪɚɧɨɜɫɤɭɸ ɢɧɬɟɪɩɪɟɬɚɰɢɸ ( C M P ), ɬɨ ɡɚɩɪɨɫ G0 : ? C ɢɦɟɟɬ ɭɫɩɟɲɧɨɟ ɤɜɚɡɢ-SLDɪɟɡɨɥɸɬɢɜɧɨɟ ɜɵɱɢɫɥɟɧɢɟ.ɋɥɟɞɫɬɜɢɟ.
ȿɫɥɢ C1 , C2 ,..., Cn M P , ɬɨ ɡɚɩɪɨɫ G : ? C1 , C2 ,..., Cn ɢɦɟɟɬ ɭɫɩɟɲɧɨɟ ɤɜɚɡɢ-SLDɪɟɡɨɥɸɬɢɜɧɨɟ ɜɵɱɢɫɥɟɧɢɟ.Ʌɟɦɦɚ (ɨ ɩɨɞɴɟɦɟ ɞɥɹ SLD-ɪɟɡɨɥɸɰɢɣ): ɉɭɫɬɶ G – ɡɚɩɪɨɫ ɤ ɯɨɪɧɨɜɫɤɨɣ ɥɨɝɢɱɟɫɤɨɣɩɪɨɝɪɚɦɦɟ Ɋ, K - ɤɨɧɟɱɧɚɹ ɩɨɞɫɬɚɧɨɜɤɚ, ɚ ɡɚɩɪɨɫ GK ɢɦɟɟɬ ɭɫɩɟɲɧɨɟ ɤɜɚɡɢ-SLD-ɪɟɡɨɥɸɬɢɜɧɨɟ ɜɵɱɢɫɥɟɧɢɟ GK ,(G '1 ,T '1 ),..., ( ,T 'n ) .
Ɍɨɝɞɚ ɡɚɩɪɨɫ G ɢɦɟɟɬ ɭɫɩɟɲɧɨɟ SLDɪɟɡɨɥɸɬɢɜɧɨɟ ɜɵɱɢɫɥɟɧɢɟ G, (G1 ,T1 ),..., ( , T n ) , ɩɪɢɱɟɦ ɫɭɳɟɫɬɜɭɟɬ ɬɚɤɚɹ ɤɨɧɟɱɧɚɹɩɨɞɫɬɚɧɨɜɤɚ U , ɱɬɨ KT '1 T '2 ...T 'n T1T 2 ...T n U . ɂɧɚɱɟ ɝɨɜɨɪɹ, ɪɟɡɭɥɶɬɚɬ ɱɚɫɬɧɨɝɨ ɫɥɭɱɚɹɡɚɩɪɨɫɚ ɞɥɹ ɤɜɚɡɢ-SLD-ɪɟɡɨɥɸɬɢɜɧɨɝɨ ɜɵɱɢɫɥɟɧɢɹ – ɷɬɨ ɪɟɡɭɥɶɬɚɬ ɱɚɫɬɧɨɝɨ ɫɥɭɱɚɹ ɡɚɩɪɨɫɚɞɥɹ SLD-ɪɟɡɨɥɸɬɢɜɧɨɝɨ ɜɵɱɢɫɥɟɧɢɹ.Ɍɟɨɪɟɦɚ (ɨ ɩɨɥɧɨɬɟ; ɜɚɧ ɗɦɞɟɧɚ): ȿɫɥɢ ɚɬɨɦ C M P , ɬɨ C SuccP .Ɍɟɨɪɟɦɚ (ɨ ɩɨɥɧɨɬɟ; Ʉɥɚɪɤɚ): ɉɭɫɬɶ G – ɡɚɩɪɨɫ ɤ ɯɨɪɧɨɜɫɤɨɣ ɥɨɝɢɱɟɫɤɨɣ ɩɪɨɝɪɚɦɦɟ Ɋ, T ɩɪɚɜɢɥɶɧɵɣ ɨɬɜɟɬ ɧɚ G. Ɍɨɝɞɚ ɫɭɳɟɫɬɜɭɟɬ ɜɵɱɢɫɥɟɧɧɵɣ ɨɬɜɟɬ K , ɬɚɤɨɣ, ɱɬɨ ɞɥɹ ɧɟɤɨɬɨɪɨɣɤɨɧɟɱɧɨɣ ɩɨɞɫɬɚɧɨɜɤɢ U ɜɵɩɨɥɧɹɟɬɫɹ ɪɚɜɟɧɫɬɜɨ T KU (ɬ.ɟ.
ɥɸɛɨɣ ɩɪɚɜɢɥɶɧɵɣ ɨɬɜɟɬɹɜɥɹɟɬɫɹ ɱɚɫɬɧɵɦ ɫɥɭɱɚɟɦ ɧɟɤɨɬɨɪɨɝɨ ɜɵɱɢɫɥɟɧɧɨɝɨ ɨɬɜɟɬɚ).Ɇɚɲɢɧɚ Ɍɶɸɪɢɧɝɚ:Ɉɩɪɟɞɟɥɟɧɢɟ. Ʌɟɧɬɨɱɧɵɣ ɚɥɮɚɜɢɬ A {a0 ,..., an } - ɷɬɨ ɦɧɨɠɟɫɬɜɨ ɞɨɩɭɫɬɢɦɵɯ ɡɧɚɱɟɧɢɣɹɱɟɟɤ ɩɚɦɹɬɢ (ɫɢɦɜɨɥ a0 ɧɚɡɵɜɚɟɬɫɹ ɩɭɫɬɵɦ). ɋɥɨɜɨ ɜ ɚɥɮɚɜɢɬɟ Ⱥ ɧɚɡɵɜɚɟɬɫɹ ɥɟɧɬɨɱɧɵɦɫɥɨɜɨɦ.Ɉɩɪɟɞɟɥɟɧɢɟ. Ⱥɥɮɚɜɢɬ ɫɨɫɬɨɹɧɢɣ Q {q 0 , q1 ,..., qm ,...} - ɷɬɨ ɦɧɨɠɟɫɬɜɨ ɫɨɫɬɨɹɧɢɣ, ɩɪɢɱɟɦɫɨɫɬɨɹɧɢɟ q0 ɧɚɡɵɜɚɟɬɫɹ ɡɚɤɥɸɱɢɬɟɥɶɧɵɦ, ɚ ɫɨɫɬɨɹɧɢɟ q1 - ɧɚɱɚɥɶɧɵɦ.i 01716Ɇɚɬɟɦɚɬɢɱɟɫɤɚɹ ɥɨɝɢɤɚ, ɫɜɨɞɤɚ ɨɩɪɟɞɟɥɟɧɢɣ.
(ɫ) 2006 GrGr (grgr@later.ru)Ɇɚɬɟɦɚɬɢɱɟɫɤɚɹ ɥɨɝɢɤɚ, ɫɜɨɞɤɚ ɨɩɪɟɞɟɥɟɧɢɣ. (ɫ) 2006 GrGr (grgr@later.ru)Ɇɚɬɟɦɚɬɢɱɟɫɤɚɹ ɥɨɝɢɤɚ, ɫɜɨɞɤɚ ɨɩɪɟɞɟɥɟɧɢɣ. (ɫ) 2006 GrGr (grgr@later.ru)Ɉɩɪɟɞɟɥɟɧɢɟ. Ʌɟɧɬɨɱɧɚɹ ɤɨɧɮɢɝɭɪɚɰɢɹ – ɷɬɨ ɬɪɨɣɤɚ d w1 , q, w2 ! , ɝɞɟ w1 - ɥɟɧɬɨɱɧɨɟɫɥɨɜɨ, ɤɨɬɨɪɨɟ ɹɜɥɹɟɬɫɹ ɫɨɞɟɪɠɢɦɵɦ ɥɟɧɬɵ ɫɥɟɜɚ ɨɬ ɨɛɨɡɪɟɜɚɟɦɨɣ ɹɱɟɣɤɢ, q - ɬɟɤɭɳɟɟɫɨɫɬɨɹɧɢɟ ɦɚɲɢɧɵ Ɍɶɸɪɢɧɝɚ, w2 - ɫɥɨɜɨ, ɫɨɫɬɨɹɳɟɟ ɢɡ ɫɚɦɨɣ ɹɱɟɣɤɢ ɢ ɫɨɞɟɪɠɢɦɨɝɨ ɥɟɧɬɵɫɩɪɚɜɚ ɨɬ ɧɟɟ.Ɉɩɪɟɞɟɥɟɧɢɟ. Ʉɨɦɚɧɞɚ ɦɚɲɢɧɵ Ɍɶɸɪɢɧɝɚ – ɷɬɨ ɩɹɬɟɪɤɚ q, a, b, q ', D ! , ɝɞɟ q ɢ q' –ɫɨɫɬɨɹɧɢɹ, a, b – ɫɢɦɜɨɥɵ ɢɡ ɚɥɮɚɜɢɬɚ Ⱥ, D {L, R} .Ɉɩɪɟɞɟɥɟɧɢɟ. ȼɵɱɢɫɥɟɧɧɵɣ ɨɬɜɟɬ, ɩɨɥɭɱɟɧɧɵɣ ɜ ɪɟɡɭɥɶɬɚɬɟ R-ɜɵɱɢɫɥɟɧɢɹ ɧɚɡɵɜɚɟɬɫɹ Rɜɵɱɢɫɥɟɧɧɵɦ ɨɬɜɟɬɨɦ.Ɍɟɨɪɟɦɚ.
ɋɬɪɚɬɟɝɢɹ ɨɛɯɨɞɚ ɜ ɲɢɪɢɧɭ – ɩɨɥɧɚɹ, ɫɬɪɚɬɟɝɢɹ ɨɛɯɨɞɚ ɜ ɝɥɭɛɢɧɭ ɫ ɜɨɡɜɪɚɬɨɦ –ɧɟɩɨɥɧɚɹ.Ʌɟɦɦɚ (ɩɟɪɟɤɥɸɱɚɬɟɥɶɧɚɹ): ɉɭɫɬɶ Ɋ – ɯɨɪɧɨɜɫɤɚɹ ɥɨɝɢɱɟɫɤɚɹ ɩɪɨɝɪɚɦɦɚ, G0 - ɡɚɩɪɨɫ ɤɈɩɪɟɞɟɥɟɧɢɟ. Ɉɩɟɪɚɬɨɪ ɨɬɫɟɱɟɧɢɹ (ɫɚt) – ɷɬɨ 0-ɦɟɫɬɧɵɣ ɩɪɟɞɢɤɚɬ ɫɨ ɫɥɟɞɭɸɳɟɣɨɩɟɪɚɰɢɨɧɧɨɣ ɫɟɦɚɧɬɢɤɨɣ:ɉɭɫɬɶ ɜ ɥɨɝɢɱɟɫɤɨɣ ɩɪɨɝɪɚɦɦɟ ɊG0ɢɦɟɟɬɫɹ ɩɪɨɝɪɚɦɦɧɨɣ ɭɬɜɟɪɠɞɟɧɢɟD : A0 m A1 ,..., Ai ,!, Ai 1 ,..., An , G0 ɡɚɩɪɨɫ ɤ ɷɬɨɣ ɩɪɨɝɪɚɦɦɟ. ɋɬɪɨɢɦ*ɞɟɪɟɜɨ SLD-ɪɟɡɨɥɸɬɢɜɧɵɯ ɜɵɱɢɫɥɟɧɢɣ.* - ɷɬɨ ɩɚɪɧɚɹ ɦɟɬɤɚ, ɤɨɬɨɪɚɹ ɨɡɧɚɱɚɟɬ,G1 ? A '0 , C1 ,..., Ck : ɇɈɍ ( A '0 , A0 ) T ɱɬɨ ɧɚɫ ɫ ɦɨɦɟɧɬɚ ɟɟ ɩɨɹɜɥɟɧɢɹDɢɧɬɟɪɟɫɭɟɬ ɬɨɥɶɤɨ ɨɞɧɚ ɚɥɶɬɟɪɧɚɬɢɜɚ.ɋɨɨɬɜɟɬɫɬɜɟɧɧɨ, ɩɨɫɥɟ ɜɬɨɪɨɝɨG2 ?( A1 ,..., Ai ,!, Ai 1 ,..., An , C1 ,..., Ck )Tɩɨɹɜɥɟɧɢɹ * ɜɟɬɜɥɟɧɢɟ ɫɧɨɜɚɪɚɡɪɟɲɚɟɬɫɹ.Ɉɬɤɚɬ ɩɪɢ ɷɬɨɦ ɩɪɨɢɡɜɨɞɢɬɫɹ ɜɜɟɪɲɢɧɭ, ɩɪɟɞɲɟɫɬɜɭɸɳɭɸ ɩɟɪɜɨɦɭ* G3 ?!, A 'i 1 ,..., A 'n , C '1 ,..., C 'kɩɨɹɜɥɟɧɢɸ * .Ɍɟɨɪɟɦɚ ɩɨɥɧɨɬɵ ɞɥɹ SLDɪɟɡɨɥɸɬɢɜɧɨɝɨ ɜɵɱɢɫɥɟɧɢɹ ɫ ɨɩɟɪɚɰɢɟɣG4 ? A 'i 1 ,..., A 'n , C '1 ,..., C 'kɨɬɫɟɱɟɧɢɹ ɧɟ ɜɵɩɨɥɧɹɟɬɫɹ.Ɉɩɪɟɞɟɥɟɧɢɟ.
Ɇɚɲɢɧɨɣ Ɍɶɸɪɢɧɝɚ ɧɚɡɵɜɚɟɬɫɹ ɬɪɨɣɤɚ T A, QT , 3T ! , ɝɞɟ Ⱥ – ɥɟɧɬɨɱɧɵɣɚɥɮɚɜɢɬ, QT – ɤɨɧɟɱɧɨɟ ɩɨɞɦɧɨɠɟɫɬɜɨ ɦɧɨɠɟɫɬɜɚ ɫɨɫɬɨɹɧɢɣ, ɉɌ – ɦɧɨɠɟɫɬɜɨ ɤɨɦɚɧɞ.ȼɚɠɧɨɟ ɨɝɪɚɧɢɱɟɧɢɟ: ɞɥɹ ɥɸɛɨɝɨ ɫɨɫɬɨɹɧɢɹ, ɨɬɥɢɱɧɨɝɨ ɨɬ ɡɚɤɥɸɱɢɬɟɥɶɧɨɝɨ, ɢ ɫɢɦɜɨɥɚ ɢɡɥɟɧɬɨɱɧɨɝɨ ɚɥɮɚɜɢɬɚ ɫɭɳɟɫɬɜɭɟɬ ɟɞɢɧɫɬɜɟɧɧɚɹ ɤɨɦɚɧɞɚ.Ɉɩɪɟɞɟɥɟɧɢɟ.
Ɉɬɧɨɲɟɧɢɟɦ ɧɟɩɨɫɪɟɞɫɬɜɟɧɧɨɝɨ ɩɟɪɟɯɨɞɚ ɧɚɡɵɜɚɟɬɫɹ ɨɬɧɨɲɟɧɢɟ T : D o E ,*ɝɞɟ D , E - ɫɨɫɬɨɹɧɢɹ ɦɚɲɢɧɵ Ɍɶɸɪɢɧɝɚ. Ɉɛɨɡɧɚɱɢɦ a o E ɬɪɚɧɡɢɬɢɜɧɨɟ ɡɚɦɵɤɚɧɢɟTɨɬɧɨɲɟɧɢɹ ɧɟɩɨɫɪɟɞɫɬɜɟɧɧɨɝɨ ɩɟɪɟɯɨɞɚ.Ⱦɥɹ ɤɚɠɞɨɣ ɦɚɲɢɧɵ Ɍɶɸɪɢɧɝɚ ɨɩɪɟɞɟɥɢɦ ɮɭɧɤɰɢɸ FT : q1 o q0 , ɩɪɢɱɟɦ ɟɫɥɢ D - ɧɚɱɚɥɶɧɚɹɤɨɧɮɢɝɭɪɚɰɢɹ, ɬɨ FT (D ) E ɬɨɝɞɚ ɢ ɬɨɥɶɤɨ ɬɨɝɞɚ, ɤɨɝɞɚ E - ɡɚɤɥɸɱɢɬɟɥɶɧɚɹ ɤɨɧɮɢɝɭɪɚɰɢɹ,*ɢ a oE .TɌɟɡɢɫ ɑɺɪɱɚ: Ⱦɥɹ ɥɸɛɨɣ ɮɭɧɤɰɢɢ M : q1 o q0 ɫɭɳɟɫɬɜɭɟɬ ɚɥɝɨɪɢɬɦ ɜɵɱɢɫɥɟɧɢɹ ɷɬɨɣɮɭɧɤɰɢɢ ɬɨɝɞɚ ɢ ɬɨɥɶɤɨ ɬɨɝɞɚ, ɤɨɝɞɚ M FT ɞɥɹ ɧɟɤɨɬɨɪɨɣ ɦɚɲɢɧɵ Ɍɶɸɪɢɧɝɚ.ȼɜɟɞɟɦ ɞɨɩɨɥɧɢɬɟɥɶɧɵɟ ɨɛɨɡɧɚɱɟɧɢɹ: nil – 0-ɦɟɫɬɧɵɣ ɮɭɧɤɰɢɨɧɚɥɶɧɵɣ ɫɢɦɜɨɥ (ɤɨɧɫɬɚɧɬɚ),x - 2-ɦɟɫɬɧɵɣ ɮɭɧɤɰɢɨɧɚɥɶɧɵɣ ɫɢɦɜɨɥ, ɢ ɜɜɟɞɟɦ ɨɬɨɛɪɚɠɟɧɢɟ ɦɧɨɠɟɫɬɜɚ ɦɚɲɢɧ Ɍɶɸɪɢɧɝɚɧɚ ɦɧɨɠɟɫɬɜɨ ɥɨɝɢɱɟɫɤɢɯ ɩɪɨɝɪɚɦɦ: Compile : T o PɌɟɨɪɟɦɚ.
ɉɭɫɬɨ Ɍ – ɦɚɲɢɧɚ Ɍɶɸɪɢɧɝɚ, Compile(T ) P - ɥɨɝɢɱɟɫɤɚɹ ɩɪɨɝɪɚɦɦɚ. Ɍɨɝɞɚ ɞɥɹɥɸɛɨɣ ɧɚɱɚɥɶɧɨɣ ɤɨɧɮɢɝɭɪɚɰɢɢ D 0 ai1 ,..., aik ; q1 ; b j1 ,..., b jn ! ɫɭɳɟɫɬɜɭɟɬ ɡɚɤɥɸɱɢɬɟɥɶɧɚɹ*ɤɨɧɮɢɝɭɪɚɰɢɹ E 0 a 'l1 ,..., a 'lm ; q0 ; b 'r1 ,..., b 'rt ! , ɬɚɤɚɹ, ɱɬɨ a o E , ɬɨɝɞɚ ɢ ɬɨɥɶɤɨ ɬɨɝɞɚ,Tɤɨɝɞɚ ɡɚɩɪɨɫ GD 0 : ? R (x( aik , x( aik 1 ,..., ( ai1 , nil )...), q1 , x(b j1 ,..., (b jn , nil )...)) ɢɦɟɟɬ ɭɫɩɟɲɧɨɟ SLDɪɟɡɨɥɸɬɢɜɧɨɟ ɜɵɱɢɫɥɟɧɢɟ ɫ ɨɬɜɟɬɨɦK^ u x(a ' , x(...(a ' , nil)...) ; v q ; w x(b ' , x(...(b ' , nil)...))` .lml10r1rtɌɟɨɪɟɦɚ (ɑɺɪɱɚ; ɨ ɧɟɪɚɡɪɟɲɢɦɨɫɬɢ ɩɪɨɛɥɟɦɵ ɨɛɳɟɡɧɚɱɢɦɨɫɬɢ ɞɥɹ ɤɥɚɫɫɢɱɟɫɤɨɣɥɨɝɢɤɢ ɩɪɟɞɢɤɚɬɨɜ): ɇɟ ɫɭɳɟɫɬɜɭɟɬ ɚɥɝɨɪɢɬɦɚ, ɤɨɬɨɪɵɣ ɞɥɹ ɥɸɛɨɣ ɮɨɪɦɭɥɵ M ɩɨɡɜɨɥɹɥɛɵ ɩɪɨɜɟɪɢɬɶ ɟɟ ɨɛɳɟɡɧɚɱɢɦɨɫɬɶ, ɬ.ɟ. ɧɟ ɫɭɳɟɫɬɜɭɟɬ ɚɥɝɨɪɢɬɦɚ, ɤɨɬɨɪɵɣ ɜɵɞɚɜɚɥ ɛɵ ɧɚɜɵɯɨɞɟ 1, ɟɫɥɢ ɮɨɪɦɭɥɚ M ɨɛɳɟɡɧɚɱɢɦɚ, ɢ 0 ɜ ɩɪɨɬɢɜɧɨɦ ɫɥɭɱɚɟ.Ɉɩɪɟɞɟɥɟɧɢɟ.
ɉɪɚɜɢɥɨɦ ɜɵɛɨɪɚ ɩɨɞɰɟɥɟɣ ɧɚɡɵɜɚɟɬɫɹ ɨɬɨɛɪɚɠɟɧɢɟ R : ? C1 ,..., Cn o Ci (ɬ.ɟ.ɨɬɨɛɪɚɠɟɧɢɟ, ɩɨɤɚɡɵɜɚɸɳɟɟ, ɤɚɤɨɣ ɚɬɨɦ ɞɨɥɠɟɧ ɛɵɬɶ ɜɵɛɪɚɧ ɧɚ ɬɟɤɭɳɟɦ ɷɬɚɩɟɜɵɱɢɫɥɟɧɢɹ).Ɉɩɪɟɞɟɥɟɧɢɟ. SLD-ɪɟɡɨɥɸɬɢɜɧɨɟ ɜɵɱɢɫɥɟɧɢɟ ɧɚɡɵɜɚɟɬɫɹ R-ɜɵɱɢɫɥɟɧɢɟɦ, ɟɫɥɢ ɧɚ ɤɚɠɞɨɦɲɚɝɟ ɜɵɱɢɫɥɟɧɢɹ ɨɱɟɪɟɞɧɚɹ ɩɨɞɰɟɥɶ ɜɵɛɢɪɚɟɬɫɹ ɩɨ ɩɪɚɜɢɥɭ R.18ɧɟɣ, ɩɭɫɬɶ ɬɚɤɠɟ ɢɦɟɟɬɫɹ SLD-ɪɟɡɨɥɸɬɢɜɧɨɟ ɜɵɱɢɫɥɟɧɢɟ G0 , (G1 ,T1 ),..., ( , T n ) , ɩɪɢɱɟɦ G1 ɢG2 - ɷɬɚɩɵ SLD-ɪɟɡɨɥɸɬɢɜɧɨɝɨ ɜɵɱɢɫɥɟɧɢɹ, ɧɚ ɤɨɬɨɪɵɯ i-ɚɹ ɩɨɞɰɟɥɶ ɛɵɥɚ ɪɚɫɤɪɵɬɚ ɩɨɩɪɚɜɢɥɭ D1 ɢ D2 ɫɨɨɬɜɟɬɫɬɜɟɧɧɨ. Ɍɨɝɞɚ ɫɭɳɟɫɬɜɭɟɬ SLD-ɪɟɡɨɥɸɬɢɜɧɨɟ ɜɵɱɢɫɥɟɧɢɟG0 , (G '1 ,T '1 ), (G '2 , T '2 ),..., ( ,T 'n ) , ɬɚɤɨɟ, ɱɬɨ ɧɚ ɷɬɚɩɟ G '1 ɪɚɫɤɪɵɬɢɟ ɩɪɨɢɫɯɨɞɢɥɨ ɩɨ ɩɪɚɜɢɥɭD2 , ɚ ɧɚ ɷɬɚɩɟ G '2 - ɩɨ ɩɪɚɜɢɥɭ D1 , ɩɪɢ ɷɬɨɦ ɞɥɹ ɜɵɱɢɫɥɟɧɧɵɯ ɨɬɜɟɬɨɜ K ɢ K ' ɫɭɳɟɫɬɜɭɸɬɤɨɧɟɱɧɵɟ ɩɨɞɫɬɚɧɨɜɤɢ U ɢ U ' , ɬɚɤɢɟ, ɱɬɨ K K ' U ' , K ' KU .Ɍɟɨɪɟɦɚ: ɉɭɫɬɶ Ɋ – ɯɨɪɧɨɜɫɤɚɹ ɥɨɝɢɱɟɫɤɚɹ ɩɪɨɝɪɚɦɦɚ, G – ɡɚɩɪɨɫ ɤ ɧɟɣ, R ɢ R' – ɪɚɡɥɢɱɧɵɟɩɪɚɜɢɥɚ ɜɵɛɨɪɚ.
Ɍɨɝɞɚ ɟɫɥɢ K - R-ɜɵɱɢɫɥɢɦɵɣ ɨɬɜɟɬ ɧɚ G ɤ Ɋ, ɬɨ ɫɭɳɟɫɬɜɭɟɬ ɬɚɤɨɣ R'ɜɵɱɢɫɥɢɦɵɣ ɨɬɜɟɬ K ' , ɬɚɤɨɣ, ɱɬɨ K K ' U ' ɢ K ' KU ɞɥɹ ɧɟɤɨɬɨɪɵɯ ɤɨɧɟɱɧɵɯ ɩɟɪɟɫɬɚɧɨɜɨɤ(ɩɟɪɟɢɦɟɧɨɜɚɧɢɣ) U ɢ U ' .Ɍɟɨɪɟɦɚ (ɫɢɥɶɧɨɣ ɩɨɥɧɨɬɵ): ɉɭɫɬɶ G – ɡɚɩɪɨɫ ɤ ɯɨɪɧɨɜɫɤɨɣ ɥɨɝɢɱɟɫɤɨɣ ɩɪɨɝɪɚɦɦɟ Ɋ, R –ɩɪɚɜɢɥɨ ɜɵɛɨɪɚ, T - ɩɪɚɜɢɥɶɧɵɣ ɨɬɜɟɬ ɧɚ G ɤ Ɋ. Ɍɨɝɞɚ ɫɭɳɟɫɬɜɭɟɬ R-ɜɵɱɢɫɥɢɦɵɣ ɨɬɜɟɬ K ,ɬɚɤɨɣ, ɱɬɨ T KU , ɝɞɟ U - ɤɨɧɟɱɧɚɹ ɩɨɞɫɬɚɧɨɜɤɚ (ɩɟɪɟɢɦɟɧɨɜɚɧɢɟ).Ɉɩɪɟɞɟɥɟɧɢɟ. ɉɭɫɬɶ G – ɡɚɩɪɨɫ ɤ ɯɨɪɧɨɜɫɤɨɣ ɥɨɝɢɱɟɫɤɨɣ ɩɪɨɝɪɚɦɦɟ Ɋ, ɜ ɤɨɬɨɪɨɣ ɜɫɟɩɪɨɝɪɚɦɦɧɵɟ ɭɬɜɟɪɠɞɟɧɢɹ ɭɩɨɪɹɞɨɱɟɧɵ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
