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

UptoLike

ВУЗ: 

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

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

Рубрика: 

74 çÌÁ×Á III. ìÏÇÉËÁ ×ÙÓËÁÚÙ×ÁÎÉÊ
ÓÈÅÍÁ ÍÏÖÅÔ ÂÙÔØ ÏÐÉÓÁÎÁ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØÀ ÉÚ N ÐÒÉÓ×ÁÉ×ÁÎÉÊ, ×ÙÒÁ-
ÖÁÀÝÉÈ ÏÄÎÕ ÉÚ ÐÅÒÅÍÅÎÎÙÈ ÞÅÒÅÚ ÐÒÅÄÙÄÕÝÉÅ. äÌÑ ËÁÖÄÏÇÏ ÐÒÉÓ×ÁÉ×Á-
ÎÉÑ ÅÓÔØ ÎÅ ÂÏÌÅÅ 3(N + n)
2
×ÁÒÉÁÎÔÏ× (ÔÒÉ ÔÉÐÁ ÏÐÅÒÁÃÉÊ ¡ ËÏÎßÀÎËÃÉÑ,
ÄÉÚßÀÎËÃÉÑ, ÏÔÒÉÃÁÎÉÅ, É ËÁÖÄÙÊ ÉÚ ÎÅ ÂÏÌÅÅ ÞÅÍ Ä×ÕÈ ÁÒÇÕÍÅÎÔÏ× ×ÙÂÉ-
ÒÁÅÔÓÑ ÓÒÅÄÉ ÎÅ ÂÏÌÅÅ ÞÅÍ N +n ×ÁÒÉÁÎÔÏ×). ïÔÓÀÄÁ ÌÅÇËÏ ÐÏÌÕÞÉÔØ ÏÃÅÎËÕ
2
O(N log N)
ÎÁ ÞÉÓÌÏ ×ÓÅÈ ÆÕÎËÃÉÊ ÓÌÏÖÎÏÓÔÉ ÎÅ ÂÏÌÅÅ N (ÓÞÉÔÁÑ N > n).
÷ÓÅÇÏ ÂÕÌÅ×ÙÈ ÆÕÎËÃÉÊ Ó n ÁÒÇÕÍÅÎÔÁÍÉ ÉÍÅÅÔÓÑ 2
2
n
. éÚ ÓÒÁ×ÎÅÎÉÑ ÜÔÉÈ
ÆÏÒÍÕÌ ×ÉÄÎÏ, ÞÔÏ ÞÔÏ ÐÒÉ c < 2 É ÐÒÉ ÄÏÓÔÁÔÏÞÎÏ ÂÏÌØÛÉÈ n ÂÕÌÅ×Ù
ÆÕÎËÃÉÉ ÓÌÏÖÎÏÓÔÉ ÍÅÎØÛÅ c
n
ÓÏÓÔÁ×ÌÑÀÔ ÍÅÎØÛÉÎÓÔ×Ï, ÔÁË ËÁË 2
O(c
n
log c
n
)
ÍÎÏÇÏ ÍÅÎØÛÅ 2
2
n
.
úÁÄÁÞÁ 113. ðÒÏ×ÅÄÉÔÅ ×ÔÏÒÕÀ ÞÁÓÔØ ÒÁÓÓÕÖÄÅÎÉÑ ÂÏÌÅÅ ÐÏÄÒÏÂÎÏ É
ÐÏËÁÖÉÔÅ, ÞÔÏ ÐÒÉ ÎÅËÏÔÏÒÏÍ ε > 0 ÓÌÏÖÎÏÓÔØ ÂÏÌØÛÉÎÓÔ×Á ÂÕÌÅ×ÙÈ
ÆÕÎËÃÉÊ Ó n ÁÒÇÕÍÅÎÔÁÍÉ ÎÅ ÍÅÎØÛÅ ε2
n
/n.
÷ÅÒÈÎÀÀ ÏÃÅÎËÕ × ÔÅÏÒÅÍÅ 24 ÍÏÖÎÏ ÕÓÉÌÉÔØ É ÐÏËÁÚÁÔØ, ÞÔÏ ÓÌÏÖÎÏÓÔØ
ÌÀÂÏÊ ÂÕÌÅ×ÏÊ ÆÕÎËÃÉÉ n ÁÒÇÕÍÅÎÔÏ× ÎÅ ÐÒÅ×ÏÓÈÏÄÉÔ O(2
n
/n).
úÁÄÁÞÁ 114. ( Á) ðÏËÁÖÉÔÅ, ÞÔÏ ×ÏÚÍÏÖÎÏ ÐÏÓÔÒÏÉÔØ ÓÈÅÍÕ ÒÁÚÍÅ-
ÒÁ O(2
m
) Ó 2
m
×ÙÈÏÄÁÍÉ, ÒÅÁÌÉÚÕÀÝÕÀ ×ÓÅ 2
m
×ÏÚÍÏÖÎÙÈ ËÏÎßÀÎËÔÏ×
ÄÌÉÎÙ m (ÄÌÑ ËÁÖÄÏÇÏ ¡ Ó×ÏÊ ×ÙÈÏÄ). (õËÁÚÁÎÉÅ: ÔÁËÕÀ ÓÈÅÍÕ ÍÏÖÎÏ
ÐÏÓÔÒÏÉÔØ ÉÎÄÕËÔÉ×ÎÏ.) ( Â) ðÏËÁÖÉÔÅ, ÞÔÏ ÍÏÖÎÏ ÐÏÓÔÒÏÉÔØ ÓÈÅÍÕ
ÒÁÚÍÅÒÁ O(2
2
m
) Ó 2
2
m
×ÙÈÏÄÁÍÉ, ÒÅÁÌÉÚÕÀÝÕÀ ×ÓÅ 2
2
m
ÂÕÌÅ×ÙÈ ÆÕÎËÃÉÊ m
ÁÒÇÕÍÅÎÔÏ×. (õËÁÚÁÎÉÅ: ÜÔÕ ÓÈÅÍÕ ÔÁËÖÅ ÍÏÖÎÏ ÐÏÓÔÒÏÉÔØ ÉÎÄÕËÔÉ×-
ÎÏ.) ( ×) ðÕÓÔØ ϕ(x
1
, . . . , x
k
, y
1
, . . . , y
l
) ¡ ÂÕÌÅ×Á ÆÕÎËÃÉÑ, ÁÒÇÕÍÅÎÔÙ ËÏ-
ÔÏÒÏÊ ÒÁÚÂÉÔÙ ÎÁ Ä×Å ÇÒÕÐÐÙ. ðÏËÁÖÉÔÅ, ÞÔÏ Å¾ ÍÏÖÎÏ ÚÁÐÉÓÁÔØ × ×É-
ÄÅ ÄÉÚßÀÎËÃÉÉ 2
k
ÞÌÅÎÏ×, ËÁÖÄÙÊ ÉÚ ËÏÔÏÒÙÈ ÉÍÅÅÔ ×ÉÄ C(x
1
, . . . , x
k
) ∧
∧ D(y
1
, . . . , y
l
), ÇÄÅ C ¡ ËÏÎßÀÎËÔ, Á D ¡ ÐÒÏÉÚ×ÏÌØÎÁÑ ÂÕÌÅ×Á ÆÕÎËÃÉÑ.
÷Ù×ÅÓÔÉ ÏÔÓÀÄÁ ÕÐÏÍÑÎÕÔÕÀ ×ÙÛÅ ÏÃÅÎËÕ O(2
n
/n). (õËÁÚÁÎÉÅ: ÒÁÚÕÍÎÏ
ÐÏÌÏÖÉÔØ k = n − log n + c, l = log n − c.)
ôÅÏÒÅÍÁ 24, ÏÄÎÁËÏ, ÎÉÞÅÇÏ ÎÅ ÇÏ×ÏÒÉÔ Ï ÓÌÏÖÎÏÓÔÉ ËÏÎËÒÅÔÎÙÈ ÂÕÌÅ×ÙÈ
ÆÕÎËÃÉÊ. óÉÔÕÁÃÉÑ ÚÄÅÓØ ÔÁËÏ×Á. åÓÔØ ÒÁÚÎÏÏÂÒÁÚÎÙÅ ÍÅÔÏÄÙ É ÐÒɾÍÙ
ÐÏÌÕÞÅÎÉÑ ×ÅÒÈÎÉÈ ÏÃÅÎÏË. îÏ ÐÒÏ ÎÉÖÎÉÅ ÏÃÅÎËÉ ÎÅÉÚ×ÅÓÔÎÏ ÐÒÁËÔÉÞÅ-
ÓËÉ ÎÉÞÅÇÏ. ðÒÏ ÍÎÏÇÉÅ ÆÕÎËÃÉÉ ÍÙ ÐÏÄÏÚÒÅ×ÁÅÍ, ÞÔÏ ÉÈ ÓÌÏÖÎÏÓÔØ ×ÅÌÉËÁ
(ÜËÓÐÏÎÅÎÃÉÁÌØÎÏ ÚÁ×ÉÓÉÔ ÏÔ ÞÉÓÌÁ ×ÈÏÄÏ×), ÎÏ ÄÏËÁÚÁÔØ ÜÔÏ ÐÏËÁ ÎÅ ÕÄÁ¾Ô-
ÓÑ. ÷ÅÓØÍÁ ÎÅÔÒÉ×ÉÁÌØÎÙÅ ÉÄÅÉ ÐÏÚ×ÏÌÑÀÔ ÄÏËÁÚÙ×ÁÔØ ÜËÓÐÏÎÅÎÃÉÁÌØÎÙÅ
ÎÉÖÎÉÅ ÏÃÅÎËÉ ÄÌÑ ÎÅËÏÔÏÒÙÈ ÓÐÅÃÉÁÌØÎÙÈ ËÌÁÓÓÏ× ÓÈÅÍ, ÎÁÐÒÉÍÅÒ, ÓÈÅÍ
ÉÚ ÍÏÎÏÔÏÎÎÙÈ ÜÌÅÍÅÎÔÏ× ÉÌÉ ÓÈÅÍ ÏÇÒÁÎÉÞÅÎÎÏÊ ÇÌÕÂÉÎÙ (ÉÓÐÏÌØÚÕÀÝÉÈ
ÜÌÅÍÅÎÔÙ é É éìé Ó ÐÒÏÉÚ×ÏÌØÎÙÍ ÞÉÓÌÏÍ ×ÈÏÄÏ×). ðÏÌÕÞÅÎÉÅ ÜËÓÐÏÎÅÎ-
ÃÉÁÌØÎÙÈ ÏÃÅÎÏË ÄÌÑ ÂÏÌÅÅ ÏÂÝÉÈ ÓÈÅÍ ¡ ÏÄÉÎ ÉÚ ×ÏÚÍÏÖÎÙÈ ÐÏÄÈÏÄÏ× Ë
74                                           çÌÁ×Á III. ìÏÇÉËÁ ×ÙÓËÁÚÙ×ÁÎÉÊ

ÓÈÅÍÁ ÍÏÖÅÔ ÂÙÔØ ÏÐÉÓÁÎÁ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØÀ ÉÚ N ÐÒÉÓ×ÁÉ×ÁÎÉÊ, ×ÙÒÁ-
ÖÁÀÝÉÈ ÏÄÎÕ ÉÚ ÐÅÒÅÍÅÎÎÙÈ ÞÅÒÅÚ ÐÒÅÄÙÄÕÝÉÅ. äÌÑ ËÁÖÄÏÇÏ ÐÒÉÓ×ÁÉ×Á-
ÎÉÑ ÅÓÔØ ÎÅ ÂÏÌÅÅ 3(N + n)2 ×ÁÒÉÁÎÔÏ× (ÔÒÉ ÔÉÐÁ ÏÐÅÒÁÃÉÊ ¡ ËÏÎßÀÎËÃÉÑ,
ÄÉÚßÀÎËÃÉÑ, ÏÔÒÉÃÁÎÉÅ, É ËÁÖÄÙÊ ÉÚ ÎÅ ÂÏÌÅÅ ÞÅÍ Ä×ÕÈ ÁÒÇÕÍÅÎÔÏ× ×ÙÂÉ-
ÒÁÅÔÓÑ ÓÒÅÄÉ ÎÅ ÂÏÌÅÅ ÞÅÍ N +n ×ÁÒÉÁÎÔÏ×). ïÔÓÀÄÁ ÌÅÇËÏ ÐÏÌÕÞÉÔØ ÏÃÅÎËÕ
2O(N log N ) ÎÁ ÞÉÓÌÏ ×ÓÅÈ ÆÕÎËÃÉÊ ÓÌÏÖÎÏÓÔÉ ÎÅ ÂÏÌÅÅ N (ÓÞÉÔÁÑ N > n).
   ÷ÓÅÇÏ ÂÕÌÅ×ÙÈ ÆÕÎËÃÉÊ Ó n ÁÒÇÕÍÅÎÔÁÍÉ ÉÍÅÅÔÓÑ 22 . éÚ ÓÒÁ×ÎÅÎÉÑ ÜÔÉÈ
                                                       n


ÆÏÒÍÕÌ ×ÉÄÎÏ, ÞÔÏ ÞÔÏ ÐÒÉ c < 2 É ÐÒÉ ÄÏÓÔÁÔÏÞÎÏ ÂÏÌØÛÉÈ n ÂÕÌÅ×Ù
                                                                    n   n
ÆÕÎËÃÉÉ ÓÌÏÖÎÏÓÔÉ ÍÅÎØÛÅ cn ÓÏÓÔÁ×ÌÑÀÔ ÍÅÎØÛÉÎÓÔ×Ï, ÔÁË ËÁË 2O(c log c )
ÍÎÏÇÏ ÍÅÎØÛÅ 22 .
                   n




  úÁÄÁÞÁ 113. ðÒÏ×ÅÄÉÔÅ ×ÔÏÒÕÀ ÞÁÓÔØ ÒÁÓÓÕÖÄÅÎÉÑ ÂÏÌÅÅ ÐÏÄÒÏÂÎÏ É
ÐÏËÁÖÉÔÅ, ÞÔÏ ÐÒÉ ÎÅËÏÔÏÒÏÍ ε > 0 ÓÌÏÖÎÏÓÔØ ÂÏÌØÛÉÎÓÔ×Á ÂÕÌÅ×ÙÈ
ÆÕÎËÃÉÊ Ó n ÁÒÇÕÍÅÎÔÁÍÉ ÎÅ ÍÅÎØÛÅ ε2n /n.
  ÷ÅÒÈÎÀÀ ÏÃÅÎËÕ × ÔÅÏÒÅÍÅ 24 ÍÏÖÎÏ ÕÓÉÌÉÔØ É ÐÏËÁÚÁÔØ, ÞÔÏ ÓÌÏÖÎÏÓÔØ
ÌÀÂÏÊ ÂÕÌÅ×ÏÊ ÆÕÎËÃÉÉ n ÁÒÇÕÍÅÎÔÏ× ÎÅ ÐÒÅ×ÏÓÈÏÄÉÔ O(2n/n).
   úÁÄÁÞÁ 114. ( Á) ðÏËÁÖÉÔÅ, ÞÔÏ ×ÏÚÍÏÖÎÏ ÐÏÓÔÒÏÉÔØ ÓÈÅÍÕ ÒÁÚÍÅ-
ÒÁ O(2m ) Ó 2m ×ÙÈÏÄÁÍÉ, ÒÅÁÌÉÚÕÀÝÕÀ ×ÓÅ 2m ×ÏÚÍÏÖÎÙÈ ËÏÎßÀÎËÔÏ×
ÄÌÉÎÙ m (ÄÌÑ ËÁÖÄÏÇÏ ¡ Ó×ÏÊ ×ÙÈÏÄ). (õËÁÚÁÎÉÅ: ÔÁËÕÀ ÓÈÅÍÕ ÍÏÖÎÏ
ÐÏÓÔÒÏÉÔØ ÉÎÄÕËÔÉ×ÎÏ.) ( Â) ðÏËÁÖÉÔÅ, ÞÔÏ ÍÏÖÎÏ ÐÏÓÔÒÏÉÔØ ÓÈÅÍÕ
ÒÁÚÍÅÒÁ O(22 ) Ó 22 ×ÙÈÏÄÁÍÉ, ÒÅÁÌÉÚÕÀÝÕÀ ×ÓÅ 22 ÂÕÌÅ×ÙÈ ÆÕÎËÃÉÊ m
                   m      m                                     m


ÁÒÇÕÍÅÎÔÏ×. (õËÁÚÁÎÉÅ: ÜÔÕ ÓÈÅÍÕ ÔÁËÖÅ ÍÏÖÎÏ ÐÏÓÔÒÏÉÔØ ÉÎÄÕËÔÉ×-
ÎÏ.) ( ×) ðÕÓÔØ ϕ(x1, . . . , xk , y1, . . . , yl ) ¡ ÂÕÌÅ×Á ÆÕÎËÃÉÑ, ÁÒÇÕÍÅÎÔÙ ËÏ-
ÔÏÒÏÊ ÒÁÚÂÉÔÙ ÎÁ Ä×Å ÇÒÕÐÐÙ. ðÏËÁÖÉÔÅ, ÞÔÏ Å¾ ÍÏÖÎÏ ÚÁÐÉÓÁÔØ × ×É-
ÄÅ ÄÉÚßÀÎËÃÉÉ 2k ÞÌÅÎÏ×, ËÁÖÄÙÊ ÉÚ ËÏÔÏÒÙÈ ÉÍÅÅÔ ×ÉÄ C(x1, . . . , xk ) ∧
∧ D(y1, . . . , yl ), ÇÄÅ C ¡ ËÏÎßÀÎËÔ, Á D ¡ ÐÒÏÉÚ×ÏÌØÎÁÑ ÂÕÌÅ×Á ÆÕÎËÃÉÑ.
÷Ù×ÅÓÔÉ ÏÔÓÀÄÁ ÕÐÏÍÑÎÕÔÕÀ ×ÙÛÅ ÏÃÅÎËÕ O(2n /n). (õËÁÚÁÎÉÅ: ÒÁÚÕÍÎÏ
ÐÏÌÏÖÉÔØ k = n − log n + c, l = log n − c.)
   ôÅÏÒÅÍÁ 24, ÏÄÎÁËÏ, ÎÉÞÅÇÏ ÎÅ ÇÏ×ÏÒÉÔ Ï ÓÌÏÖÎÏÓÔÉ ËÏÎËÒÅÔÎÙÈ ÂÕÌÅ×ÙÈ
ÆÕÎËÃÉÊ. óÉÔÕÁÃÉÑ ÚÄÅÓØ ÔÁËÏ×Á. åÓÔØ ÒÁÚÎÏÏÂÒÁÚÎÙÅ ÍÅÔÏÄÙ É ÐÒɾÍÙ
ÐÏÌÕÞÅÎÉÑ ×ÅÒÈÎÉÈ ÏÃÅÎÏË. îÏ ÐÒÏ ÎÉÖÎÉÅ ÏÃÅÎËÉ ÎÅÉÚ×ÅÓÔÎÏ ÐÒÁËÔÉÞÅ-
ÓËÉ ÎÉÞÅÇÏ. ðÒÏ ÍÎÏÇÉÅ ÆÕÎËÃÉÉ ÍÙ ÐÏÄÏÚÒÅ×ÁÅÍ, ÞÔÏ ÉÈ ÓÌÏÖÎÏÓÔØ ×ÅÌÉËÁ
(ÜËÓÐÏÎÅÎÃÉÁÌØÎÏ ÚÁ×ÉÓÉÔ ÏÔ ÞÉÓÌÁ ×ÈÏÄÏ×), ÎÏ ÄÏËÁÚÁÔØ ÜÔÏ ÐÏËÁ ÎÅ ÕÄÁ¾Ô-
ÓÑ. ÷ÅÓØÍÁ ÎÅÔÒÉ×ÉÁÌØÎÙÅ ÉÄÅÉ ÐÏÚ×ÏÌÑÀÔ ÄÏËÁÚÙ×ÁÔØ ÜËÓÐÏÎÅÎÃÉÁÌØÎÙÅ
ÎÉÖÎÉÅ ÏÃÅÎËÉ ÄÌÑ ÎÅËÏÔÏÒÙÈ ÓÐÅÃÉÁÌØÎÙÈ ËÌÁÓÓÏ× ÓÈÅÍ, ÎÁÐÒÉÍÅÒ, ÓÈÅÍ
ÉÚ ÍÏÎÏÔÏÎÎÙÈ ÜÌÅÍÅÎÔÏ× ÉÌÉ ÓÈÅÍ ÏÇÒÁÎÉÞÅÎÎÏÊ ÇÌÕÂÉÎÙ (ÉÓÐÏÌØÚÕÀÝÉÈ
ÜÌÅÍÅÎÔÙ é É éìé Ó ÐÒÏÉÚ×ÏÌØÎÙÍ ÞÉÓÌÏÍ ×ÈÏÄÏ×). ðÏÌÕÞÅÎÉÅ ÜËÓÐÏÎÅÎ-
ÃÉÁÌØÎÙÈ ÏÃÅÎÏË ÄÌÑ ÂÏÌÅÅ ÏÂÝÉÈ ÓÈÅÍ ¡ ÏÄÉÎ ÉÚ ×ÏÚÍÏÖÎÙÈ ÐÏÄÈÏÄÏ× Ë

Страницы