Теормин - шпоры, страница 4
Описание файла
PDF-файл из архива "Теормин - шпоры", который расположен в категории "". Всё это находится в предмете "математическая логика и логическое программирование" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 4 страницы из PDF
Ʌɨɝɢɱɟɫɤɨɟ ɩɪɨɝɪɚɦɦɢɪɨɜɚɧɢɟɅɨɝɢɱɟɫɤɚɹ ɩɪɨɝɪɚɦɦɚ – ɷɬɨ ɫɨɜɨɤɭɩɧɨɫɬɶ ɮɨɪɦɭɥ, ɩɪɢɱɟɦ ɩɪɨɝɪɚɦɦɚ ɩɨɡɜɨɥɹɟɬ ɞɨɤɚɡɚɬɶɢɥɢ ɨɩɪɨɜɟɪɝɧɭɬɶ ɨɛɳɟɡɧɚɱɢɦɨɫɬɶ ɮɨɪɦɭɥ, ɤɨɬɨɪɵɟ ɜ ɧɟɟ ɜɯɨɞɹɬ.Ɉɩɪɟɞɟɥɟɧɢɟ. ɏɨɪɧɨɜɫɤɢɦ ɞɢɡɴɸɧɤɬɨɦ ɧɚɡɵɜɚɟɬɫɹ ɞɢɡɴɸɧɤɬ, ɜ ɤɨɬɨɪɵɣ ɜɯɨɞɢɬ ɧɟ ɛɨɥɟɟɨɞɧɨɣ ɥɢɬɟɪɵ ɛɟɡ ɨɬɪɢɰɚɧɢɹ.Ɉɩɪɟɞɟɥɟɧɢɟ. ɏɨɪɧɨɜɫɤɚɹ ɥɨɝɢɱɟɫɤɚɹ ɩɪɨɝɪɚɦɦɚ – ɦɧɨɠɟɫɬɜɨ ɯɨɪɧɨɜɫɤɢɯ ɞɢɡɴɸɧɤɬɨɜ.3) ȼɨɡɦɨɠɧɨ ɬɪɢ ɜɚɪɢɚɧɬɚ ɜɵɱɢɫɥɟɧɢɹ:Ⱥ) Gl ? - ɭɫɩɟɲɧɨɟ ɜɵɱɢɫɥɟɧɢɟ (SLD-ɪɟɡɨɥɸɬɢɜɧɨɟ ɨɩɪɨɜɟɪɠɟɧɢɟ)Ȼ) ɛɟɫɤɨɧɟɱɧɚɹ ɩɨɫɥɟɞɨɜɚɬɟɥɶɧɨɫɬɶ – ɛɟɫɤɨɧɟɱɧɨɟ ɜɵɱɢɫɥɟɧɢɟȼ) ɨɛɧɚɪɭɠɢɜɚɟɬɫɹ, ɱɬɨ ɨɱɟɪɟɞɧɭɸ SLD-ɪɟɡɨɥɶɜɟɧɬɭ ɩɨɫɬɪɨɢɬɶ ɧɟɥɶɡɹ – ɬɭɩɢɤɨɜɨɟɜɵɱɢɫɥɟɧɢɟ.Ɉɩɪɟɞɟɥɟɧɢɟ.
Ɂɚɩɪɨɫ ɤ ɩɪɨɝɪɚɦɦɟ – ɡɚɞɚɱɚ ɩɨɢɫɤɚ ɜɫɟɯ ɩɪɚɜɢɥɶɧɵɯ ɨɬɜɟɬɨɜ ɜ ɩɪɨɝɪɚɦɦɟ.Ɉɩɪɟɞɟɥɟɧɢɟ. ɉɭɫɬɶ (G1 ,T1 ),..., (Gl 1 , Tl 1 ), ( ,Tl ) - ɭɫɩɟɲɧɨɟ ɡɚɜɟɪɲɟɧɢɟ ɡɚɩɪɨɫɚ G ɤɯɨɪɧɨɜɫɤɨɣ ɥɨɝɢɱɟɫɤɨɣ ɩɪɨɝɪɚɦɦɟ Ɋ. Ɍɨɝɞɚ ɩɨɞɫɬɚɧɨɜɤɚ T T1T 2 ...T l | y1 , y2 ,..., yn ɧɚɡɵɜɚɟɬɫɹɈɩɪɟɞɟɥɟɧɢɟ.
Ɉɬɜɟɬɨɦ ɧɚ ɡɚɩɪɨɫ G : ? C1 ,..., Cm ɫ ɰɟɥɟɜɵɦɢ ɩɟɪɟɦɟɧɧɵɦɢ x1 , x2 ,..., xnɜɵɱɢɫɥɢɦɵɦ ɨɬɜɟɬɨɦ ɧɚ ɡɚɩɪɨɫ G ɤ ɥɨɝɢɱɟɫɤɨɣ ɩɪɨɝɪɚɦɦɟ Ɋ.ɧɚɡɵɜɚɟɬɫɹ ɜɫɹɤɚɹ ɩɨɞɫɬɚɧɨɜɤɚ T^x t ;...; x t `m11mɈɩɪɟɞɟɥɟɧɢɟ. Ɉɬɜɟɬ K ɧɚ ɡɚɩɪɨɫ ɤ ɥɨɝɢɱɟɫɤɨɣ ɩɪɨɝɪɚɦɦɟ Ɋ ɧɚɡɵɜɚɟɬɫɹ ɩɪɚɜɢɥɶɧɵɦ, ɟɫɥɢɪɟɡɭɥɶɬɚɬ ɩɨɞɫɬɚɧɨɜɤɢ (C1 , C2 ,..., Cm )K ɹɜɥɹɟɬɫɹ ɥɨɝɢɱɟɫɤɢɦ ɫɥɟɞɫɬɜɢɟɦ Ɋ.Ɉɩɪɟɞɟɥɟɧɢɟ. ɗɪɛɪɚɧɨɜɫɤɚɹ ɢɧɬɟɪɩɪɟɬɚɰɢɹ I ɞɥɹ ɥɨɝɢɱɟɫɤɨɣ ɩɪɨɝɪɚɦɦɵ Ɋ ɧɚɡɵɜɚɟɬɫɹ ɟɟɦɨɞɟɥɶɸ, ɟɫɥɢ ɨɧɚ ɹɜɥɹɟɬɫɹ ɦɨɞɟɥɶɸ ɞɥɹ ɥɸɛɨɝɨ ɯɨɪɧɨɜɫɤɨɝɨ ɞɢɡɴɸɧɤɬɚ, ɜɯɨɞɹɳɟɝɨ ɜ ɧɟɟ.ɍɬɜɟɪɠɞɟɧɢɟ.
I – ɦɨɞɟɥɶ ɞɥɹ ɥɨɝɢɱɟɫɤɨɣ ɩɪɨɝɪɚɦɦɵ Ɋ ɬɨɝɞɚ ɢ ɬɨɥɶɤɨ ɬɨɝɞɚ, ɤɨɝɞɚ ɞɥɹɥɸɛɨɝɨ ɨɫɧɨɜɧɨɝɨ ɩɪɢɦɟɪɚ D0 A '0 m A '1 & A '2 &...& A 'n , ɟɫɥɢ ɥɸɛɨɟ A 'i ɩɪɢɧɚɞɥɟɠɢɬ I, ɬɨɢ A '0 ɬɚɤɠɟ ɩɪɢɧɚɞɥɟɠɢɬ I.Ʌɟɦɦɚ (ɨ ɩɟɪɟɫɟɱɟɧɢɢ ɦɨɞɟɥɟɣ): ɉɭɫɬɶ Ɋ – ɯɨɪɧɨɜɫɤɚɹ ɥɨɝɢɱɟɫɤɚɹ ɩɪɨɝɪɚɦɦɚ, ɚ Ɇ' ɢ Ɇ'' - ɟɟɦɨɞɟɥɢ. Ɍɨɝɞɚ ɷɪɛɪɚɧɨɜɫɤɚɹ ɢɧɬɟɪɩɪɟɬɚɰɢɹ Ɇ, ɹɜɥɹɸɳɚɹɫɹ ɩɟɪɟɫɟɱɟɧɢɟɦ Ɇ' ɢ Ɇ'' ɬɚɤɠɟɛɭɞɟɬ ɦɨɞɟɥɶɸ ɞɥɹ Ɋ.ɋɥɟɞɫɬɜɢɟ 1: ɩɟɪɟɫɟɱɟɧɢɟ ɩɪɨɢɡɜɨɥɶɧɨɝɨ ɱɢɫɥɚ ɦɨɞɟɥɟɣ ɞɥɹ Ɋ ɬɚɤɠɟ ɛɭɞɟɬ ɦɨɞɟɥɶɸ.ɋɥɟɞɫɬɜɢɟ 2: ɩɟɪɟɫɟɱɟɧɢɟ ɜɫɟɯ ɦɨɞɟɥɟɣ ɞɥɹ Ɋ ɬɚɤɠɟ ɛɭɞɟɬ ɟɟ ɦɨɞɟɥɶɸ.
Ɍɚɤɚɹ ɦɨɞɟɥɶ ɛɭɞɟɬɧɚɡɵɜɚɬɶɫɹ ɧɚɢɦɟɧɶɲɟɣ ɇ-ɦɨɞɟɥɶɸ (ɇɇɆ) ɢ ɨɛɨɡɧɚɱɚɬɶɫɹ ɤɚɤ M PɌɟɨɪɟɦɚ: ɉɭɫɬɶ Ɋ – ɯɨɪɧɨɜɫɤɚɹ ɥɨɝɢɱɟɫɤɚɹ ɩɪɨɝɪɚɦɦɚ, ɋ - ɨɫɧɨɜɧɨɣ ɬɟɪɦ. ɋ ɹɜɥɹɟɬɫɹɫɥɟɞɫɬɜɢɟɦ Ɋ ɬɨɝɞɚ ɢ ɬɨɥɶɤɨ ɬɨɝɞɚ, ɤɨɝɞɚ ɨɧ ɩɪɢɧɚɞɥɟɠɢɬ ɇɇɆ Ɋ.Ɉɩɪɟɞɟɥɟɧɢɟ. ɉɭɫɬɶ Ɋ – ɯɨɪɧɨɜɫɤɚɹ ɥɨɝɢɱɟɫɤɚɹ ɩɪɨɝɪɚɦɦɚ, 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 - ɥɨɝɢɱɟɫɤɚɹ ɩɪɨɝɪɚɦɦɚ.
