Математическая логика и теория алгоритмов. Самохин А.В. - 200 стр.

UptoLike

ВУЗ: 

МГТУ ГА | Москва

Составители: 

Рубрика: 

200 çÌÁ×Á XIII. òÅËÕÒÓÉ×ÎÙÅ ÆÕÎËÃÉÉ
×ÁÔÅÌØÎÏÓÔÉ ÓÞÉÔÁÅÍ ÞÉÓÌÏ 1, ÎÏÍÅÒÏÍ ÏÄÎÏÜÌÅÍÅÎÔÎÏÊ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏ-
ÓÔÉ hai ÓÞÉÔÁÅÍ ÞÉÓÌÏ 2
a+1
, ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ ha, bi ÉÍÅÅÔ ÎÏÍÅÒ 2
a+1
3
b+1
,
ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ ha, b, ci ÉÍÅÅÔ ÎÏÍÅÒ 2
a+1
3
b+1
5
c+1
É ÔÁË ÄÁÌÅÅ (ÏÓÎÏ×Á-
ÎÉÑ ÓÔÅÐÅÎÅÊ ¡ ÐÒÏÓÔÙÅ ÞÉÓÌÁ). âÕÄÅÍ ÏÂÏÚÎÁÞÁÔØ ÎÏÍÅÒ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏ-
ÓÔÉ ha, b, . . . , zi ÞÅÒÅÚ [a, b, . . . , z]. üÔÁ ÎÕÍÅÒÁÃÉÑ × ÎÅËÏÔÏÒÏÍ ÓÍÙÓÌÅ ÐÒÉ-
ÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÁ. ëÏÎÅÞÎÏ, ÂÕË×ÁÌØÎÏ ÜÔÏ ÐÏÎÉÍÁÔØ ÎÅÌØÚÑ, ÔÁË ËÁË ÎÕ-
ÍÅÒÁÃÉÑ ÐÒÅÄÓÔÁ×ÌÑÅÔ ÓÏÂÏÊ ¥ÆÕÎËÃÉÀ Ó ÐÅÒÅÍÅÎÎÙÍ ÞÉÓÌÏÍ ÁÒÇÕÍÅÎÔÏ×¥.
îÏ ÒÁÚÎÙÅ Ó×ÑÚÁÎÎÙÅ Ó ÎÅÊ ÆÕÎËÃÉÉ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙ. ÷ ÞÁÓÔÎÏÓÔÉ,
ÔÁËÏ×Ù ÆÕÎËÃÉÉ
• Length(x) = ÄÌÉÎÁ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ Ó ÎÏÍÅÒÏÍ x;
• Select(i, x) = i-ÙÊ ÞÌÅÎ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ Ó ÎÏÍÅÒÏÍ x;
• Append(x, y) = ÎÏÍÅÒ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ, ËÏÔÏÒÁÑ ÐÏÌÕÞÁÅÔÓÑ ÐÒÉÐÉ-
ÓÙ×ÁÎÉÅÍ ÞÉÓÌÁ y Ë ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ Ó ÎÏÍÅÒÏÍ x.
÷ÓÅ ÜÔÉ ÆÕÎËÃÉÉ (É ÄÒÕÇÉÅ ÁÎÁÌÏÇÉÞÎÙÅ) Ó×ÏÄÑÔÓÑ Ë ÒÁÚÌÉÞÎÙÍ ÏÐÅÒÁÃÉÑÍ Ó
ÐÒÏÓÔÙÍÉ ÞÉÓÌÁÍÉ É ÍÎÏÖÉÔÅÌÑÍÉ, ËÏÔÏÒÙÅ ÍÙ × ÓÕÝÎÏÓÔÉ ÕÖÅ ÒÁÚÂÉÒÁÌÉ.
ôÅÐÅÒØ ÍÙ ÄÏËÁÖÅÍ, ÞÔÏ ÆÕÎËÃÉÑ
x 7→ H(x) = [h(0), h(1), . . ., h(x)]
ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÁ. ÷ ÓÁÍÏÍ ÄÅÌÅ, H(0) = [c], Á
H(k + 1) = Append(H(k), F (k + 1, Select(g(k + 1), H(k)))).
§5. íÁÛÉÎÙ ôØÀÒÉÎÇÁ É ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙÅ ÆÕÎË-
ÃÉÉ
íÙ ÒÁÓÓÍÏÔÒÅÌÉ ÎÅÓËÏÌØËÏ ÒÁÚÌÉÞÎÙÈ ÐÒɾÍÏ× ÐÏÓÔÒÏÅÎÉÑ ÐÒÉÍÉÔÉ×ÎÏ
ÒÅËÕÒÓÉ×ÎÙÈ ÆÕÎËÃÉÊ. ôÅÍ ÎÅ ÍÅÎÅÅ ÏÓÔÁ¾ÔÓÑ ÎÅ ×ÐÏÌÎÅ ÑÓÎÙÍ, ÎÁÓËÏÌØËÏ
ÜÔÏÔ ËÌÁÓÓ ÛÉÒÏË. óÅÊÞÁÓ ÍÙ ÐÏËÁÖÅÍ, ÞÔÏ ÏÎ ×ËÌÀÞÁÅÔ × ÓÅÂÑ ×ÓÅ ÄÏÓÔÁ-
ÔÏÞÎÏ ÂÙÓÔÒÏ ×ÙÞÉÓÌÉÍÙÅ ÆÕÎËÃÉÉ.
ôÅÏÒÅÍÁ 75. ìÀÂÁÑ ÆÕÎËÃÉÑ, ×ÙÞÉÓÌÉÍÁÑ ÎÁ ÍÁÛÉÎÅ ôØÀÒÉÎÇÁ ÎÅ ÂÏ-
ÌÅÅ ÞÅÍ ÚÁ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÏÅ (ÏÔ ÄÌÉÎÙ ×ÈÏÄÁ) ×ÒÅÍÑ, ÐÒÉÍÉÔÉ×ÎÏ
ÒÅËÕÒÓÉ×ÎÁ.
äÏËÁÚÁÔÅÌØÓÔ×Ï. îÁÐÏÍÎÉÍ, ÞÔÏ ÍÙ ÓÞÉÔÁÅÍ ×ÈÏÄÏÍ É ×ÙÈÏÄÏÍ ÍÁÛÉ-
ÎÙ ôØÀÒÉÎÇÁ ÓÌÏ×Á ÉÚ ÎÕÌÅÊ É ÅÄÉÎÉÃ. ðÏÓËÏÌØËÕ ÁÒÇÕÍÅÎÔÁÍÉ É ÚÎÁÞÅ-
ÎÉÑÍÉ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙÈ ÆÕÎËÃÉÊ Ñ×ÌÑÀÔÓÑ ÞÉÓÌÁ, ÔÅÏÒÅÍÁ ÂÕÄÅÔ
ÉÍÅÔØ ÓÍÙÓÌ, ÔÏÌØËÏ ÅÓÌÉ ÍÙ ÄÏÇÏ×ÏÒÉÍÓÑ ÏÔÏÖÄÅÓÔ×ÌÑÔØ ÞÉÓÌÁ É ÓÌÏ×Á.
ëÁË ÕÖÅ ÇÏ×ÏÒÉÌÏÓØ, ÍÙ ÏÔÏÖÄÅÓÔ×ÌÑÅÍ ÞÉÓÌÏ n ÓÏ ÓÌÏ×ÏÍ, ËÏÔÏÒÏÅ ÐÏÌÕÞÁ-
ÅÔÓÑ ÐÏÓÌÅ ÕÄÁÌÅÎÉÑ ÓÔÁÒÛÅÇÏ ÂÉÔÁ 1 × Ä×ÏÉÞÎÏÍ ÒÁÚÌÏÖÅÎÉÉ ÞÉÓÌÁ n + 1.
200                                          çÌÁ×Á XIII. òÅËÕÒÓÉ×ÎÙÅ ÆÕÎËÃÉÉ

×ÁÔÅÌØÎÏÓÔÉ ÓÞÉÔÁÅÍ ÞÉÓÌÏ 1, ÎÏÍÅÒÏÍ ÏÄÎÏÜÌÅÍÅÎÔÎÏÊ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏ-
ÓÔÉ hai ÓÞÉÔÁÅÍ ÞÉÓÌÏ 2a+1, ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ ha, bi ÉÍÅÅÔ ÎÏÍÅÒ 2a+13b+1,
ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ ha, b, ci ÉÍÅÅÔ ÎÏÍÅÒ 2a+13b+15c+1 É ÔÁË ÄÁÌÅÅ (ÏÓÎÏ×Á-
ÎÉÑ ÓÔÅÐÅÎÅÊ ¡ ÐÒÏÓÔÙÅ ÞÉÓÌÁ). âÕÄÅÍ ÏÂÏÚÎÁÞÁÔØ ÎÏÍÅÒ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏ-
ÓÔÉ ha, b, . . . , zi ÞÅÒÅÚ [a, b, . . . , z]. üÔÁ ÎÕÍÅÒÁÃÉÑ × ÎÅËÏÔÏÒÏÍ ÓÍÙÓÌÅ ÐÒÉ-
ÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÁ. ëÏÎÅÞÎÏ, ÂÕË×ÁÌØÎÏ ÜÔÏ ÐÏÎÉÍÁÔØ ÎÅÌØÚÑ, ÔÁË ËÁË ÎÕ-
ÍÅÒÁÃÉÑ ÐÒÅÄÓÔÁ×ÌÑÅÔ ÓÏÂÏÊ ¥ÆÕÎËÃÉÀ Ó ÐÅÒÅÍÅÎÎÙÍ ÞÉÓÌÏÍ ÁÒÇÕÍÅÎÔÏ×¥.
îÏ ÒÁÚÎÙÅ Ó×ÑÚÁÎÎÙÅ Ó ÎÅÊ ÆÕÎËÃÉÉ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙ. ÷ ÞÁÓÔÎÏÓÔÉ,
ÔÁËÏ×Ù ÆÕÎËÃÉÉ
    • Length(x) = ÄÌÉÎÁ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ Ó ÎÏÍÅÒÏÍ x;
    • Select(i, x) = i-ÙÊ ÞÌÅÎ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ Ó ÎÏÍÅÒÏÍ x;
    • Append(x, y) = ÎÏÍÅÒ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ, ËÏÔÏÒÁÑ ÐÏÌÕÞÁÅÔÓÑ ÐÒÉÐÉ-
      ÓÙ×ÁÎÉÅÍ ÞÉÓÌÁ y Ë ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ Ó ÎÏÍÅÒÏÍ x.
÷ÓÅ ÜÔÉ ÆÕÎËÃÉÉ (É ÄÒÕÇÉÅ ÁÎÁÌÏÇÉÞÎÙÅ) Ó×ÏÄÑÔÓÑ Ë ÒÁÚÌÉÞÎÙÍ ÏÐÅÒÁÃÉÑÍ Ó
ÐÒÏÓÔÙÍÉ ÞÉÓÌÁÍÉ É ÍÎÏÖÉÔÅÌÑÍÉ, ËÏÔÏÒÙÅ ÍÙ × ÓÕÝÎÏÓÔÉ ÕÖÅ ÒÁÚÂÉÒÁÌÉ.
   ôÅÐÅÒØ ÍÙ ÄÏËÁÖÅÍ, ÞÔÏ ÆÕÎËÃÉÑ
                        x 7→ H(x) = [h(0), h(1), . . . , h(x)]
ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÁ. ÷ ÓÁÍÏÍ ÄÅÌÅ, H(0) = [c], Á
        H(k + 1) = Append(H(k), F (k + 1, Select(g(k + 1), H(k)))). 


   §5. íÁÛÉÎÙ ôØÀÒÉÎÇÁ É ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙÅ ÆÕÎË-
    ÃÉÉ
   íÙ ÒÁÓÓÍÏÔÒÅÌÉ ÎÅÓËÏÌØËÏ ÒÁÚÌÉÞÎÙÈ ÐÒɾÍÏ× ÐÏÓÔÒÏÅÎÉÑ ÐÒÉÍÉÔÉ×ÎÏ
ÒÅËÕÒÓÉ×ÎÙÈ ÆÕÎËÃÉÊ. ôÅÍ ÎÅ ÍÅÎÅÅ ÏÓÔÁ¾ÔÓÑ ÎÅ ×ÐÏÌÎÅ ÑÓÎÙÍ, ÎÁÓËÏÌØËÏ
ÜÔÏÔ ËÌÁÓÓ ÛÉÒÏË. óÅÊÞÁÓ ÍÙ ÐÏËÁÖÅÍ, ÞÔÏ ÏÎ ×ËÌÀÞÁÅÔ × ÓÅÂÑ ×ÓÅ ÄÏÓÔÁ-
ÔÏÞÎÏ ÂÙÓÔÒÏ ×ÙÞÉÓÌÉÍÙÅ ÆÕÎËÃÉÉ.
   ôÅÏÒÅÍÁ 75. ìÀÂÁÑ ÆÕÎËÃÉÑ, ×ÙÞÉÓÌÉÍÁÑ ÎÁ ÍÁÛÉÎÅ ôØÀÒÉÎÇÁ ÎÅ ÂÏ-
ÌÅÅ ÞÅÍ ÚÁ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÏÅ (ÏÔ ÄÌÉÎÙ ×ÈÏÄÁ) ×ÒÅÍÑ, ÐÒÉÍÉÔÉ×ÎÏ
ÒÅËÕÒÓÉ×ÎÁ.
   äÏËÁÚÁÔÅÌØÓÔ×Ï. îÁÐÏÍÎÉÍ, ÞÔÏ ÍÙ ÓÞÉÔÁÅÍ ×ÈÏÄÏÍ É ×ÙÈÏÄÏÍ ÍÁÛÉ-
ÎÙ ôØÀÒÉÎÇÁ ÓÌÏ×Á ÉÚ ÎÕÌÅÊ É ÅÄÉÎÉÃ. ðÏÓËÏÌØËÕ ÁÒÇÕÍÅÎÔÁÍÉ É ÚÎÁÞÅ-
ÎÉÑÍÉ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙÈ ÆÕÎËÃÉÊ Ñ×ÌÑÀÔÓÑ ÞÉÓÌÁ, ÔÅÏÒÅÍÁ ÂÕÄÅÔ
ÉÍÅÔØ ÓÍÙÓÌ, ÔÏÌØËÏ ÅÓÌÉ ÍÙ ÄÏÇÏ×ÏÒÉÍÓÑ ÏÔÏÖÄÅÓÔ×ÌÑÔØ ÞÉÓÌÁ É ÓÌÏ×Á.
ëÁË ÕÖÅ ÇÏ×ÏÒÉÌÏÓØ, ÍÙ ÏÔÏÖÄÅÓÔ×ÌÑÅÍ ÞÉÓÌÏ n ÓÏ ÓÌÏ×ÏÍ, ËÏÔÏÒÏÅ ÐÏÌÕÞÁ-
ÅÔÓÑ ÐÏÓÌÅ ÕÄÁÌÅÎÉÑ ÓÔÁÒÛÅÇÏ ÂÉÔÁ 1 × Ä×ÏÉÞÎÏÍ ÒÁÚÌÏÖÅÎÉÉ ÞÉÓÌÁ n + 1.

Страницы