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

UptoLike

ВУЗ: 

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

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

Рубрика: 

§3. óÈÅÍÙ ÉÚ ÆÕÎËÃÉÏÎÁÌØÎÙÈ ÜÌÅÍÅÎÔÏ× 75
ÚÎÁÍÅÎÉÔÏÊ ÐÒÏÂÌÅÍÅ ÐÅÒÅÂÏÒÁ, ÃÅÎÔÒÁÌØÎÏÊ ÐÒÏÂÌÅÍÅ ÔÅÏÒÉÉ ÓÌÏÖÎÏÓÔÉ
×ÙÞÉÓÌÅÎÉÊ.
íÙ ÎÅ ÂÕÄÅÍ ÕÇÌÕÂÌÑÔØÓÑ × ÜÔÕ ÔÅÏÒÉÀ, Á ÐÒÉ×ÅÄ¾Í ÌÉÛØ ÎÅÓËÏÌØËÏ ×ÅÒÈ-
ÎÉÈ ÏÃÅÎÏË ÄÌÑ ËÏÎËÒÅÔÎÙÈ ÚÁÄÁÞ. ðÒÉ ÜÔÏÍ ÍÙ ÎÅ ÐÒÅÔÅÎÄÕÅÍ ÎÁ ÐÏÌÎÏÔÕ,
Á ÈÏÔÉÍ ÌÉÛØ ÐÏËÁÚÁÔØ ÎÅÓËÏÌØËÏ ÉÎÔÅÒÅÓÎÙÈ ÉÄÅÊ É ÐÒɾÍÏ×.
òÁÓÓÍÏÔÒÉÍ ÆÕÎËÃÉÀ ÓÒÁ×ÎÅÎÉÑ Ä×ÕÈ n-ÂÉÔÏ×ÙÈ ÞÉÓÅÌ. ïÎÁ ÉÍÅÅÔ 2n
ÁÒÇÕÍÅÎÔÏ× (n ÄÌÑ ÏÄÎÏÇÏ ÞÉÓÌÁ É n ÄÌÑ ÄÒÕÇÏÇÏ); ž ÚÎÁÞÅÎÉÅ ÒÁ×ÎÏ 1, ÅÓÌÉ
ÐÅÒ×ÏÅ ÞÉÓÌÏ ÂÏÌØÛÅ ×ÔÏÒÏÇÏ, É 0 × ÐÒÏÔÉ×ÎÏÍ ÓÌÕÞÁÅ.
ïÂÏÚÎÁÞÉÍ ÜÔÕ ÆÕÎËÃÉÀ Comp
n
.
ôÅÏÒÅÍÁ 25. ðÕÓÔØ B ¡ ÐÏÌÎÙÊ ÎÁÂÏÒ ÆÕÎËÃÉÊ. óÕÝÅÓÔ×ÕÅÔ ÔÁËÁÑ
ËÏÎÓÔÁÎÔÁ C, ÞÔÏ size
B
(Comp
n
) 6 Cn.
äÏËÁÚÁÔÅÌØÓÔ×Ï. úÁÍÅÔÉÍ, ÞÔÏ ÐÏÓËÏÌØËÕ × ÆÏÒÍÕÌÉÒÏ×ËÅ ÔÅÏÒÅÍÙ ÏÃÅÎ-
ËÁ ÒÁÚÍÅÒÁ ÐÒÏ×ÏÄÉÔÓÑ Ó ÔÏÞÎÏÓÔØÀ ÄÏ ËÏÎÓÔÁÎÔÙ, ÔÏ ×ÙÂÏÒ ËÏÎËÒÅÔÎÏÇÏ
ÂÁÚÉÓÁ ÎÅ ÉÍÅÅÔ ÚÎÁÞÅÎÉÑ. äÒÕÇÉÍÉ ÓÌÏ×ÁÍÉ, ÍÙ ÍÏÖÅÍ ÐÒÅÄÐÏÌÁÇÁÔØ, ÞÔÏ
ÌÀÂÏÅ ËÏÎÅÞÎÏÅ ÞÉÓÌÏ ÎÅÏÂÈÏÄÉÍÙÈ ÎÁÍ ÆÕÎËÃÉÊ × ÜÔÏÍ ÂÁÚÉÓÅ ÅÓÔØ.
óÈÅÍÁ ÓÒÁ×ÎÅÎÉÑ ÞÉÓÅÌ ÂÕÄÅÔ ÒÅËÕÒÓÉ×ÎÏÊ (ÞÔÏÂÙ ÓÒÁ×ÎÉÔØ Ä×Á ÞÉÓÌÁ,
ÍÙ ÏÔÄÅÌØÎÏ ÓÒÁ×ÎÉ×ÁÅÍ ÉÈ ÌÅ×ÙÅ É ÐÒÁ×ÙÅ ÐÏÌÏ×ÉÎÙ, Á ÚÁÔÅÍ ÏÂßÅÄÉÎÑ-
ÅÍ ÒÅÚÕÌØÔÁÔÙ). ðÒÉ ÜÔÏÍ, ËÁË ÞÁÓÔÏ ÂÙ×ÁÅÔ, ÎÁÄÏ ÕÓÉÌÉÔØ ÕÔ×ÅÒÖÄÅÎÉÅ,
ÞÔÏÂÙ ÉÎÄÕËÃÉÑ ÐÒÏÛÌÁ. á ÉÍÅÎÎÏ, ÍÙ ÂÕÄÅÍ ÓÔÒÏÉÔØ ÓÈÅÍÕ Ó 2n ×ÈÏÄÁÍÉ
x
1
, . . . , x
n
, y
1
, . . . , y
n
É Ä×ÕÍÑ ×ÙÈÏÄÁÍÉ, ËÏÔÏÒÁÑ ÕËÁÚÙ×ÁÅÔ, ËÁËÏÊ ÉÚ ÔÒ¾È
ÓÌÕÞÁÅ× x < y, x = y ÉÌÉ x > y ÉÍÅÅÔ ÍÅÓÔÏ. (úÄÅÓØ x, y ¡ ÞÉÓÌÁ, ÚÁÐÉ-
ÓÙ×ÁÅÍÏÅ × Ä×ÏÉÞÎÏÊ ÓÉÓÔÅÍÅ ËÁË x
1
. . . x
n
É y
1
, . . . , y
n
.) ä×Á ×ÙÈÏÄÎÙÈ ÂÉÔÁ
ËÏÄÉÒÕÀÔ ÞÅÔÙÒÅ ×ÏÚÍÏÖÎÏÓÔÉ, Á ÎÕÖÎÏ ÔÏÌØËÏ ÔÒÉ, ÔÁË ÞÔÏ ÅÓÔØ ÎÅËÏÔÏ-
ÒÙÊ ÚÁÐÁÓ. äÌÑ ÏÐÒÅÄÅ̾ÎÎÏÓÔÉ ÍÏÖÎÏ ÓÞÉÔÁÔØ, ÞÔÏ ÐÅÒ×ÙÊ ×ÙÈÏÄÎÏÊ ÂÉÔ
ÉÓÔÉÎÅÎ, ÅÓÌÉ ÞÉÓÌÁ ÒÁ×ÎÙ, Á ×ÔÏÒÏÊ ¡ ÅÓÌÉ x < y. ôÏÇÄÁ ×ÏÚÍÏÖÎÙ ÔÒÉ
×ÁÒÉÁÎÔÁ ÓÉÇÎÁÌÏ× ÎÁ ×ÙÈÏÄÅ: 10 (ÒÁ×ÅÎÓÔ×Ï), 01 (ÐÒÉ x < y) É 00 (ÐÒÉ x >
> y).
ïÂßÑÓÎÉÍ ÔÅÐÅÒØ, ËÁË ÓÏÂÒÁÔØ, ÓËÁÖÅÍ, ÓÈÅÍÕ ÓÒÁ×ÎÅÎÉÑ Ä×ÕÈ 16-ÒÁÚÒÑÄ-
ÎÙÈ ÞÉÓÅÌ. óÏÂÅÒ¾Í ÏÔÄÅÌØÎÏ ÓÈÅÍÕ ÓÒÁ×ÎÅÎÉÑ ÓÔÁÒÛÉÈ 8 ÒÁÚÒÑÄÏ× É ÍÌÁÄ-
ÛÉÈ 8 ÒÁÚÒÑÄÏ×. ëÁÖÄÁÑ ÉÚ ÎÉÈ ÄÁÓÔ ÏÔ×ÅÔ × ÆÏÒÍÅ Ä×ÕÈ ÂÉÔÏ×. ôÅÐÅÒØ
ÉÚ ÜÔÉÈ ÞÅÔÙÒ¾È ÂÉÔÏ× ÎÁÄÏ ÓÏÂÒÁÔØ Ä×Á. (åÓÌÉ × ÓÔÁÒÛÉÈ ÒÁÚÒÑÄÁÈ ÎÅ-
ÒÁ×ÅÎÓÔ×Ï, ÔÏ ÏÎÏ ÏÐÒÅÄÅÌÑÅÔ ÒÅÚÕÌØÔÁÔ ÓÒÁ×ÎÅÎÉÑ; ÅÓÌÉ ÓÔÁÒÛÉÅ ÒÁÚÒÑÄÙ
ÒÁ×ÎÙ, ÔÏ ÒÅÚÕÌØÔÁÔ ÓÒÁ×ÎÅÎÉÑ ÏÐÒÅÄÅÌÑÅÔÓÑ ÍÌÁÄÛÉÍÉ ÒÁÚÒÑÄÁÍÉ.) îÁ-
ÐÉÓÁÎÎÁÑ × ÓËÏÂËÁÈ ÆÒÁÚÁ ÏÐÒÅÄÅÌÑÅÔ ÂÕÌÅ×Õ ÆÕÎËÃÉÀ Ó ÞÅÔÙÒØÍÑ ÂÉÔÁÍÉ
ÎÁ ×ÈÏÄÅ É Ä×ÕÍÑ ÂÉÔÁÍÉ ÎÁ ×ÙÈÏÄÅ, É ÍÏÖÅÔ ÂÙÔØ ÒÅÁÌÉÚÏ×ÁÎÁ ÎÅËÏÔÏÒÏÊ
ÓÈÅÍÏÊ ÆÉËÓÉÒÏ×ÁÎÎÏÇÏ ÒÁÚÍÅÒÁ. ôÁËÉÍ ÏÂÒÁÚÏÍ, ÅÓÌÉ ÞÅÒÅÚ T (n) ÏÂÏÚÎÁ-
ÞÉÔØ ÒÁÚÍÅÒ ÓÈÅÍÙ, ÓÒÁ×ÎÉ×ÁÀÝÅÊ n-ÂÉÔÏ×ÙÅ ÞÉÓÌÁ, ÔÏ ÐÏÌÕÞÁÅÍ ÏÃÅÎËÕ
T (2n) 6 2T (n) + c, ÇÄÅ c ¡ ÎÅËÏÔÏÒÁÑ ËÏÎÓÔÁÎÔÁ, ÚÁ×ÉÓÑÝÁÑ ÏÔ ×ÙÂÏÒÁ ÂÁ-
ÚÉÓÁ. ïÔÓÀÄÁ ÓÌÅÄÕÅÔ, ÞÔÏ T (2
k
) 6 c
0
2
k
ÐÒÉ ÎÅËÏÔÏÒÏÍ c
0
. ÷ ÓÁÍÏÍ ÄÅÌÅ, ÄÌÑ
§3. óÈÅÍÙ ÉÚ ÆÕÎËÃÉÏÎÁÌØÎÙÈ ÜÌÅÍÅÎÔÏ×                                         75

ÚÎÁÍÅÎÉÔÏÊ ÐÒÏÂÌÅÍÅ ÐÅÒÅÂÏÒÁ, ÃÅÎÔÒÁÌØÎÏÊ ÐÒÏÂÌÅÍÅ ÔÅÏÒÉÉ ÓÌÏÖÎÏÓÔÉ
×ÙÞÉÓÌÅÎÉÊ.
   íÙ ÎÅ ÂÕÄÅÍ ÕÇÌÕÂÌÑÔØÓÑ × ÜÔÕ ÔÅÏÒÉÀ, Á ÐÒÉ×ÅÄ¾Í ÌÉÛØ ÎÅÓËÏÌØËÏ ×ÅÒÈ-
ÎÉÈ ÏÃÅÎÏË ÄÌÑ ËÏÎËÒÅÔÎÙÈ ÚÁÄÁÞ. ðÒÉ ÜÔÏÍ ÍÙ ÎÅ ÐÒÅÔÅÎÄÕÅÍ ÎÁ ÐÏÌÎÏÔÕ,
Á ÈÏÔÉÍ ÌÉÛØ ÐÏËÁÚÁÔØ ÎÅÓËÏÌØËÏ ÉÎÔÅÒÅÓÎÙÈ ÉÄÅÊ É ÐÒɾÍÏ×.
   òÁÓÓÍÏÔÒÉÍ ÆÕÎËÃÉÀ ÓÒÁ×ÎÅÎÉÑ Ä×ÕÈ n-ÂÉÔÏ×ÙÈ ÞÉÓÅÌ. ïÎÁ ÉÍÅÅÔ 2n
ÁÒÇÕÍÅÎÔÏ× (n ÄÌÑ ÏÄÎÏÇÏ ÞÉÓÌÁ É n ÄÌÑ ÄÒÕÇÏÇÏ); ž ÚÎÁÞÅÎÉÅ ÒÁ×ÎÏ 1, ÅÓÌÉ
ÐÅÒ×ÏÅ ÞÉÓÌÏ ÂÏÌØÛÅ ×ÔÏÒÏÇÏ, É 0 × ÐÒÏÔÉ×ÎÏÍ ÓÌÕÞÁÅ.
   ïÂÏÚÎÁÞÉÍ ÜÔÕ ÆÕÎËÃÉÀ Compn .
  ôÅÏÒÅÍÁ 25. ðÕÓÔØ B ¡ ÐÏÌÎÙÊ ÎÁÂÏÒ ÆÕÎËÃÉÊ. óÕÝÅÓÔ×ÕÅÔ ÔÁËÁÑ
ËÏÎÓÔÁÎÔÁ C, ÞÔÏ sizeB (Compn ) 6 Cn.
   äÏËÁÚÁÔÅÌØÓÔ×Ï. úÁÍÅÔÉÍ, ÞÔÏ ÐÏÓËÏÌØËÕ × ÆÏÒÍÕÌÉÒÏ×ËÅ ÔÅÏÒÅÍÙ ÏÃÅÎ-
ËÁ ÒÁÚÍÅÒÁ ÐÒÏ×ÏÄÉÔÓÑ Ó ÔÏÞÎÏÓÔØÀ ÄÏ ËÏÎÓÔÁÎÔÙ, ÔÏ ×ÙÂÏÒ ËÏÎËÒÅÔÎÏÇÏ
ÂÁÚÉÓÁ ÎÅ ÉÍÅÅÔ ÚÎÁÞÅÎÉÑ. äÒÕÇÉÍÉ ÓÌÏ×ÁÍÉ, ÍÙ ÍÏÖÅÍ ÐÒÅÄÐÏÌÁÇÁÔØ, ÞÔÏ
ÌÀÂÏÅ ËÏÎÅÞÎÏÅ ÞÉÓÌÏ ÎÅÏÂÈÏÄÉÍÙÈ ÎÁÍ ÆÕÎËÃÉÊ × ÜÔÏÍ ÂÁÚÉÓÅ ÅÓÔØ.
   óÈÅÍÁ ÓÒÁ×ÎÅÎÉÑ ÞÉÓÅÌ ÂÕÄÅÔ ÒÅËÕÒÓÉ×ÎÏÊ (ÞÔÏÂÙ ÓÒÁ×ÎÉÔØ Ä×Á ÞÉÓÌÁ,
ÍÙ ÏÔÄÅÌØÎÏ ÓÒÁ×ÎÉ×ÁÅÍ ÉÈ ÌÅ×ÙÅ É ÐÒÁ×ÙÅ ÐÏÌÏ×ÉÎÙ, Á ÚÁÔÅÍ ÏÂßÅÄÉÎÑ-
ÅÍ ÒÅÚÕÌØÔÁÔÙ). ðÒÉ ÜÔÏÍ, ËÁË ÞÁÓÔÏ ÂÙ×ÁÅÔ, ÎÁÄÏ ÕÓÉÌÉÔØ ÕÔ×ÅÒÖÄÅÎÉÅ,
ÞÔÏÂÙ ÉÎÄÕËÃÉÑ ÐÒÏÛÌÁ. á ÉÍÅÎÎÏ, ÍÙ ÂÕÄÅÍ ÓÔÒÏÉÔØ ÓÈÅÍÕ Ó 2n ×ÈÏÄÁÍÉ
x1, . . . , xn, y1, . . . , yn É Ä×ÕÍÑ ×ÙÈÏÄÁÍÉ, ËÏÔÏÒÁÑ ÕËÁÚÙ×ÁÅÔ, ËÁËÏÊ ÉÚ ÔÒ¾È
ÓÌÕÞÁÅ× x < y, x = y ÉÌÉ x > y ÉÍÅÅÔ ÍÅÓÔÏ. (úÄÅÓØ x, y ¡ ÞÉÓÌÁ, ÚÁÐÉ-
ÓÙ×ÁÅÍÏÅ × Ä×ÏÉÞÎÏÊ ÓÉÓÔÅÍÅ ËÁË x1 . . . xn É y1 , . . . , yn.) ä×Á ×ÙÈÏÄÎÙÈ ÂÉÔÁ
ËÏÄÉÒÕÀÔ ÞÅÔÙÒÅ ×ÏÚÍÏÖÎÏÓÔÉ, Á ÎÕÖÎÏ ÔÏÌØËÏ ÔÒÉ, ÔÁË ÞÔÏ ÅÓÔØ ÎÅËÏÔÏ-
ÒÙÊ ÚÁÐÁÓ. äÌÑ ÏÐÒÅÄÅ̾ÎÎÏÓÔÉ ÍÏÖÎÏ ÓÞÉÔÁÔØ, ÞÔÏ ÐÅÒ×ÙÊ ×ÙÈÏÄÎÏÊ ÂÉÔ
ÉÓÔÉÎÅÎ, ÅÓÌÉ ÞÉÓÌÁ ÒÁ×ÎÙ, Á ×ÔÏÒÏÊ ¡ ÅÓÌÉ x < y. ôÏÇÄÁ ×ÏÚÍÏÖÎÙ ÔÒÉ
×ÁÒÉÁÎÔÁ ÓÉÇÎÁÌÏ× ÎÁ ×ÙÈÏÄÅ: 10 (ÒÁ×ÅÎÓÔ×Ï), 01 (ÐÒÉ x < y) É 00 (ÐÒÉ x >
> y).
   ïÂßÑÓÎÉÍ ÔÅÐÅÒØ, ËÁË ÓÏÂÒÁÔØ, ÓËÁÖÅÍ, ÓÈÅÍÕ ÓÒÁ×ÎÅÎÉÑ Ä×ÕÈ 16-ÒÁÚÒÑÄ-
ÎÙÈ ÞÉÓÅÌ. óÏÂÅÒ¾Í ÏÔÄÅÌØÎÏ ÓÈÅÍÕ ÓÒÁ×ÎÅÎÉÑ ÓÔÁÒÛÉÈ 8 ÒÁÚÒÑÄÏ× É ÍÌÁÄ-
ÛÉÈ 8 ÒÁÚÒÑÄÏ×. ëÁÖÄÁÑ ÉÚ ÎÉÈ ÄÁÓÔ ÏÔ×ÅÔ × ÆÏÒÍÅ Ä×ÕÈ ÂÉÔÏ×. ôÅÐÅÒØ
ÉÚ ÜÔÉÈ ÞÅÔÙÒ¾È ÂÉÔÏ× ÎÁÄÏ ÓÏÂÒÁÔØ Ä×Á. (åÓÌÉ × ÓÔÁÒÛÉÈ ÒÁÚÒÑÄÁÈ ÎÅ-
ÒÁ×ÅÎÓÔ×Ï, ÔÏ ÏÎÏ ÏÐÒÅÄÅÌÑÅÔ ÒÅÚÕÌØÔÁÔ ÓÒÁ×ÎÅÎÉÑ; ÅÓÌÉ ÓÔÁÒÛÉÅ ÒÁÚÒÑÄÙ
ÒÁ×ÎÙ, ÔÏ ÒÅÚÕÌØÔÁÔ ÓÒÁ×ÎÅÎÉÑ ÏÐÒÅÄÅÌÑÅÔÓÑ ÍÌÁÄÛÉÍÉ ÒÁÚÒÑÄÁÍÉ.) îÁ-
ÐÉÓÁÎÎÁÑ × ÓËÏÂËÁÈ ÆÒÁÚÁ ÏÐÒÅÄÅÌÑÅÔ ÂÕÌÅ×Õ ÆÕÎËÃÉÀ Ó ÞÅÔÙÒØÍÑ ÂÉÔÁÍÉ
ÎÁ ×ÈÏÄÅ É Ä×ÕÍÑ ÂÉÔÁÍÉ ÎÁ ×ÙÈÏÄÅ, É ÍÏÖÅÔ ÂÙÔØ ÒÅÁÌÉÚÏ×ÁÎÁ ÎÅËÏÔÏÒÏÊ
ÓÈÅÍÏÊ ÆÉËÓÉÒÏ×ÁÎÎÏÇÏ ÒÁÚÍÅÒÁ. ôÁËÉÍ ÏÂÒÁÚÏÍ, ÅÓÌÉ ÞÅÒÅÚ T (n) ÏÂÏÚÎÁ-
ÞÉÔØ ÒÁÚÍÅÒ ÓÈÅÍÙ, ÓÒÁ×ÎÉ×ÁÀÝÅÊ n-ÂÉÔÏ×ÙÅ ÞÉÓÌÁ, ÔÏ ÐÏÌÕÞÁÅÍ ÏÃÅÎËÕ
T (2n) 6 2T (n) + c, ÇÄÅ c ¡ ÎÅËÏÔÏÒÁÑ ËÏÎÓÔÁÎÔÁ, ÚÁ×ÉÓÑÝÁÑ ÏÔ ×ÙÂÏÒÁ ÂÁ-
ÚÉÓÁ. ïÔÓÀÄÁ ÓÌÅÄÕÅÔ, ÞÔÏ T (2k ) 6 c0 2k ÐÒÉ ÎÅËÏÔÏÒÏÍ c0 . ÷ ÓÁÍÏÍ ÄÅÌÅ, ÄÌÑ

Страницы