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

UptoLike

ВУЗ: 

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

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

Рубрика: 

76 çÌÁ×Á III. ìÏÇÉËÁ ×ÙÓËÁÚÙ×ÁÎÉÊ
ÄÏÓÔÁÔÏÞÎÏ ÂÏÌØÛÏÇÏ c
0
ÍÏÖÎÏ ÄÏËÁÚÁÔØ ÐÏ ÉÎÄÕËÃÉÉ, ÞÔÏ T(2
k
) 6 c
0
2
k
− c
(ÍÙ ÄÏÌÖÎÙ ÕÓÉÌÉÔØ ÎÅÒÁ×ÅÎÓÔ×Ï, ×ÙÞÔÑ ÉÚ ÐÒÁ×ÏÊ ÞÁÓÔÉ c, ÞÔÏÂÙ ÉÎÄÕË-
ÔÉ×ÎÙÊ ÛÁÇ ÐÒÏÛ¾Ì; ÂÁÚÁ ÉÎÄÕËÃÉÉ ÏÓÔÁÅÔÓÑ ×ÅÒÎÏÊ, ÅÓÌÉ c
0
ÄÏÓÔÁÔÏÞÎÏ
×ÅÌÉËÏ).
ôÕ ÖÅ ÓÁÍÕÀ ÏÃÅÎËÕ ÍÏÖÎÏ ÏÂßÑÓÎÉÔØ É ÎÁÇÌÑÄÎÏ. îÁÛÁ ÓÈÅÍÁ ÉÍÅÅÔ ×ÉÄ
ÉÅÒÁÒÈÉÞÅÓËÏÇÏ ÄÅÒÅ×Á. îÁ ËÁÖÄÏÍ ÕÒÏ×ÎÅ ÉÚ Ä×ÕÈ Ä×ÕÈÂÉÔÏ×ÙÈ ÓÉÇÎÁÌÏ×
ÐÏÌÕÞÁÅÔÓÑ ÏÄÉÎ. ïÓÔÁ¾ÔÓÑ ×ÓÐÏÍÎÉÔØ, ÞÔÏ × ÐÏÌÎÏÍ Ä×ÏÉÞÎÏÍ ÄÅÒÅ×Å ÞÉÓÌÏ
×ÎÕÔÒÅÎÎÉÈ ×ÅÒÛÉÎ (ËÏÔÏÒÏÅ ÏÐÒÅÄÅÌÑÅÔ ÒÁÚÍÅÒ ÓÈÅÍÙ) ÎÁ ÅÄÉÎÉÃÕ ÍÅÎØÛÅ
ÞÉÓÌÁ ÌÉÓÔØÅ×. (÷ ÔÕÒÎÉÒÅ ÐÏ ÏÌÉÍÐÉÊÓËÏÊ ÓÉÓÔÅÍÅ ÞÉÓÌÏ ÉÇÒ ÎÁ ÅÄÉÎÉÃÕ
ÍÅÎØÛÅ ÞÉÓÌÁ ËÏÍÁÎÄ, ÔÁË ËÁË ÐÏÓÌÅ ËÁÖÄÏÊ ÉÇÒÙ ÏÄÎÁ ËÏÍÁÎÄÁ ×ÙÂÙ×ÁÅÔ.)
÷ÓÅ ×ÎÕÔÒÅÎÎÉÅ ×ÅÒÛÉÎÙ É ×ÓÅ ÌÉÓÔØÑ (ÇÄÅ ÓÒÁ×ÎÉ×ÁÀÔÓÑ Ä×Á ÂÉÔÁ) ÐÒÅÄ-
ÓÔÁ×ÌÑÀÔ ÓÏÂÏÊ ÓÈÅÍÙ ÏÇÒÁÎÉÞÅÎÎÏÇÏ ÒÁÚÍÅÒÁ, ÏÔËÕÄÁ É ×ÙÔÅËÁÅÔ ÏÃÅÎËÁ
T (2
k
) 6 c
0
2
k
.
ïÓÔÁÌÏÓØ ÌÉÛØ ÓËÁÚÁÔØ, ÞÔÏ ÄÅÌÁÔØ, ÅÓÌÉ ÒÁÚÍÅÒ ÞÉÓÅÌ (ËÏÔÏÒÙÊ ÍÙ ÏÂÏ-
ÚÎÁÞÁÌÉ ÞÅÒÅÚ n) ÎÅ ÅÓÔØ ÔÏÞÎÁÑ ÓÔÅÐÅÎØ Ä×ÏÊËÉ. ÷ ÜÔÏÍ ÓÌÕÞÁÅ ÍÏÖÎÏ Õ×Å-
ÌÉÞÉÔØ ÒÁÚÍÅÒ ÄÏ ÂÌÉÖÁÊÛÅÊ Ó×ÅÒÈÕ ÓÔÅÐÅÎÉ Ä×ÏÊËÉ (ÎÅ ÂÏÌÅÅ ÞÅÍ × Ä×Á
ÒÁÚÁ) É ÐÏÄÁÔØ ÎÁ ÓÔÁÒÛÉÅ ÒÁÚÒÑÄÙ ×ÈÏÄÏ× ÎÕÌÉ. ïÂÁ ÄÅÊÓÔ×ÉÑ ÐÒÉ×ÏÄÑÔ Ë
Õ×ÅÌÉÞÅÎÉÀ ÒÁÚÍÅÒÁ ÓÈÅÍÙ ÎÅ ÂÏÌÅÅ ÞÅÍ × ËÏÎÓÔÁÎÔÕ ÒÁÚ.
ðÅÒÅÊÄ¾Í Ë ÓÌÏÖÅÎÉÀ Ä×ÕÈ n-ÒÁÚÒÑÄÎÙÈ ÞÉÓÅÌ. (óÔÒÏÇÏ ÇÏ×ÏÒÑ, ÔÕÔ ×ÏÚ-
ÎÉËÁÅÔ ÎÅ ÂÕÌÅ×Á ÆÕÎËÃÉÑ, Á ÆÕÎËÃÉÑ B
n
× B
n
→ B
n+1
, ÎÏ ×ÓÅ ÎÁÛÉ ÏÐÒÅÄÅ-
ÌÅÎÉÑ ÏÞÅ×ÉÄÎÏ ÐÅÒÅÎÏÓÑÔÓÑ ÎÁ ÜÔÏÔ ÓÌÕÞÁÊ.)
ôÅÏÒÅÍÁ 26. óÕÝÅÓÔ×ÕÅÔ ÓÈÅÍÁ ÒÁÚÍÅÒÁ O(n), ÏÓÕÝÅÓÔ×ÌÑÀÝÁÑ ÓÌÏ-
ÖÅÎÉÅ Ä×ÕÈ n-ÂÉÔÏ×ÙÈ ÞÉÓÅÌ.
äÏËÁÚÁÔÅÌØÓÔ×Ï. îÁÐÏÍÎÉÍ ÓÍÙÓÌ ÏÂÏÚÎÁÞÅÎÉÑ O(n): ÎÁÍ ÎÁÄÏ ÐÏÓÔÒÏ-
ÉÔØ ÓÈÅÍÕ ÓÌÏÖÅÎÉÑ n-ÂÉÔÏ×ÙÈ ÞÉÓÅÌ, ÉÍÅÀÝÕÀ ÒÁÚÍÅÒ ÎÅ ÂÏÌÅÅ cn ÄÌÑ
ÎÅËÏÔÏÒÏÇÏ c É ÄÌÑ ×ÓÅÈ n.
÷ÓÐÏÍÎÉÍ, ËÁË ÓËÌÁÄÙ×ÁÀÔ ÞÉÓÌÁ × ÓÔÏÌÂÉË:
01 1
10 01
10 11
10 10 0
÷ÅÒÈÎÑÑ ÓÔÒÏËÁ ¡ ÂÉÔÙ ÐÅÒÅÎÏÓÁ, ÎÉÖÎÑÑ ¡ ÒÅÚÕÌØÔÁÔ. úÁÍÅÔÉÍ, ÞÔÏ ËÁ-
ÖÄÙÊ ÉÚ ÂÉÔÏ× ÐÅÒÅÎÏÓÁ ÉÌÉ ÒÅÚÕÌØÔÁÔÁ ÏÐÒÅÄÅÌÑÅÔÓÑ ÔÒÅÍÑ ÄÒÕÇÉÍÉ ÂÉ-
ÔÁÍÉ (ÂÉÔ ÒÅÚÕÌØÔÁÔÁ ÒÁ×ÅÎ ÓÕÍÍÅ Ä×ÕÈ ÂÉÔÏ× ÓÌÁÇÁÅÍÙÈ É ÂÉÔÁ ÐÅÒÅÎÏÓÁ
ÐÏ ÍÏÄÕÌÀ 2, Á ÂÉÔ ÐÅÒÅÎÏÓÁ ÒÁ×ÅÎ 1, ÅÓÌÉ ÈÏÔÑ ÂÙ Ä×Á ÉÚ ÜÔÉÈ ÔÒ¾È ÂÉÔÏ×
ÒÁ×ÎÙ 1). ðÏÜÔÏÍÕ ÍÏÖÎÏ ÓÏÓÔÁ×ÉÔØ ÓÈÅÍÕ, ËÏÔÏÒÁÑ ×ÙÞÉÓÌÑÅÔ ÜÔÉ ÂÉÔÙ
ÓÐÒÁ×Á ÎÁÌÅ×Ï É ÉÍÅÅÔ ÒÁÚÍÅÒ O(n).
76                                       çÌÁ×Á III. ìÏÇÉËÁ ×ÙÓËÁÚÙ×ÁÎÉÊ

ÄÏÓÔÁÔÏÞÎÏ ÂÏÌØÛÏÇÏ c0 ÍÏÖÎÏ ÄÏËÁÚÁÔØ ÐÏ ÉÎÄÕËÃÉÉ, ÞÔÏ T (2k ) 6 c0 2k − c
(ÍÙ ÄÏÌÖÎÙ ÕÓÉÌÉÔØ ÎÅÒÁ×ÅÎÓÔ×Ï, ×ÙÞÔÑ ÉÚ ÐÒÁ×ÏÊ ÞÁÓÔÉ c, ÞÔÏÂÙ ÉÎÄÕË-
ÔÉ×ÎÙÊ ÛÁÇ ÐÒÏÛ¾Ì; ÂÁÚÁ ÉÎÄÕËÃÉÉ ÏÓÔÁÅÔÓÑ ×ÅÒÎÏÊ, ÅÓÌÉ c0 ÄÏÓÔÁÔÏÞÎÏ
×ÅÌÉËÏ).
   ôÕ ÖÅ ÓÁÍÕÀ ÏÃÅÎËÕ ÍÏÖÎÏ ÏÂßÑÓÎÉÔØ É ÎÁÇÌÑÄÎÏ. îÁÛÁ ÓÈÅÍÁ ÉÍÅÅÔ ×ÉÄ
ÉÅÒÁÒÈÉÞÅÓËÏÇÏ ÄÅÒÅ×Á. îÁ ËÁÖÄÏÍ ÕÒÏ×ÎÅ ÉÚ Ä×ÕÈ Ä×ÕÈÂÉÔÏ×ÙÈ ÓÉÇÎÁÌÏ×
ÐÏÌÕÞÁÅÔÓÑ ÏÄÉÎ. ïÓÔÁ¾ÔÓÑ ×ÓÐÏÍÎÉÔØ, ÞÔÏ × ÐÏÌÎÏÍ Ä×ÏÉÞÎÏÍ ÄÅÒÅ×Å ÞÉÓÌÏ
×ÎÕÔÒÅÎÎÉÈ ×ÅÒÛÉÎ (ËÏÔÏÒÏÅ ÏÐÒÅÄÅÌÑÅÔ ÒÁÚÍÅÒ ÓÈÅÍÙ) ÎÁ ÅÄÉÎÉÃÕ ÍÅÎØÛÅ
ÞÉÓÌÁ ÌÉÓÔØÅ×. (÷ ÔÕÒÎÉÒÅ ÐÏ ÏÌÉÍÐÉÊÓËÏÊ ÓÉÓÔÅÍÅ ÞÉÓÌÏ ÉÇÒ ÎÁ ÅÄÉÎÉÃÕ
ÍÅÎØÛÅ ÞÉÓÌÁ ËÏÍÁÎÄ, ÔÁË ËÁË ÐÏÓÌÅ ËÁÖÄÏÊ ÉÇÒÙ ÏÄÎÁ ËÏÍÁÎÄÁ ×ÙÂÙ×ÁÅÔ.)
   ÷ÓÅ ×ÎÕÔÒÅÎÎÉÅ ×ÅÒÛÉÎÙ É ×ÓÅ ÌÉÓÔØÑ (ÇÄÅ ÓÒÁ×ÎÉ×ÁÀÔÓÑ Ä×Á ÂÉÔÁ) ÐÒÅÄ-
ÓÔÁ×ÌÑÀÔ ÓÏÂÏÊ ÓÈÅÍÙ ÏÇÒÁÎÉÞÅÎÎÏÇÏ ÒÁÚÍÅÒÁ, ÏÔËÕÄÁ É ×ÙÔÅËÁÅÔ ÏÃÅÎËÁ
T (2k ) 6 c0 2k .
   ïÓÔÁÌÏÓØ ÌÉÛØ ÓËÁÚÁÔØ, ÞÔÏ ÄÅÌÁÔØ, ÅÓÌÉ ÒÁÚÍÅÒ ÞÉÓÅÌ (ËÏÔÏÒÙÊ ÍÙ ÏÂÏ-
ÚÎÁÞÁÌÉ ÞÅÒÅÚ n) ÎÅ ÅÓÔØ ÔÏÞÎÁÑ ÓÔÅÐÅÎØ Ä×ÏÊËÉ. ÷ ÜÔÏÍ ÓÌÕÞÁÅ ÍÏÖÎÏ Õ×Å-
ÌÉÞÉÔØ ÒÁÚÍÅÒ ÄÏ ÂÌÉÖÁÊÛÅÊ Ó×ÅÒÈÕ ÓÔÅÐÅÎÉ Ä×ÏÊËÉ (ÎÅ ÂÏÌÅÅ ÞÅÍ × Ä×Á
ÒÁÚÁ) É ÐÏÄÁÔØ ÎÁ ÓÔÁÒÛÉÅ ÒÁÚÒÑÄÙ ×ÈÏÄÏ× ÎÕÌÉ. ïÂÁ ÄÅÊÓÔ×ÉÑ ÐÒÉ×ÏÄÑÔ Ë
Õ×ÅÌÉÞÅÎÉÀ ÒÁÚÍÅÒÁ ÓÈÅÍÙ ÎÅ ÂÏÌÅÅ ÞÅÍ × ËÏÎÓÔÁÎÔÕ ÒÁÚ.
   ðÅÒÅÊÄ¾Í Ë ÓÌÏÖÅÎÉÀ Ä×ÕÈ n-ÒÁÚÒÑÄÎÙÈ ÞÉÓÅÌ. (óÔÒÏÇÏ ÇÏ×ÏÒÑ, ÔÕÔ ×ÏÚ-
ÎÉËÁÅÔ ÎÅ ÂÕÌÅ×Á ÆÕÎËÃÉÑ, Á ÆÕÎËÃÉÑ Bn × Bn → Bn+1, ÎÏ ×ÓÅ ÎÁÛÉ ÏÐÒÅÄÅ-
ÌÅÎÉÑ ÏÞÅ×ÉÄÎÏ ÐÅÒÅÎÏÓÑÔÓÑ ÎÁ ÜÔÏÔ ÓÌÕÞÁÊ.)
  ôÅÏÒÅÍÁ 26. óÕÝÅÓÔ×ÕÅÔ ÓÈÅÍÁ ÒÁÚÍÅÒÁ O(n), ÏÓÕÝÅÓÔ×ÌÑÀÝÁÑ ÓÌÏ-
ÖÅÎÉÅ Ä×ÕÈ n-ÂÉÔÏ×ÙÈ ÞÉÓÅÌ.
   äÏËÁÚÁÔÅÌØÓÔ×Ï. îÁÐÏÍÎÉÍ ÓÍÙÓÌ ÏÂÏÚÎÁÞÅÎÉÑ O(n): ÎÁÍ ÎÁÄÏ ÐÏÓÔÒÏ-
ÉÔØ ÓÈÅÍÕ ÓÌÏÖÅÎÉÑ n-ÂÉÔÏ×ÙÈ ÞÉÓÅÌ, ÉÍÅÀÝÕÀ ÒÁÚÍÅÒ ÎÅ ÂÏÌÅÅ cn ÄÌÑ
ÎÅËÏÔÏÒÏÇÏ c É ÄÌÑ ×ÓÅÈ n.
   ÷ÓÐÏÍÎÉÍ, ËÁË ÓËÌÁÄÙ×ÁÀÔ ÞÉÓÌÁ × ÓÔÏÌÂÉË:
                                  011
                                  1001
                                  1011
                                 10100
÷ÅÒÈÎÑÑ ÓÔÒÏËÁ ¡ ÂÉÔÙ ÐÅÒÅÎÏÓÁ, ÎÉÖÎÑÑ ¡ ÒÅÚÕÌØÔÁÔ. úÁÍÅÔÉÍ, ÞÔÏ ËÁ-
ÖÄÙÊ ÉÚ ÂÉÔÏ× ÐÅÒÅÎÏÓÁ ÉÌÉ ÒÅÚÕÌØÔÁÔÁ ÏÐÒÅÄÅÌÑÅÔÓÑ ÔÒÅÍÑ ÄÒÕÇÉÍÉ ÂÉ-
ÔÁÍÉ (ÂÉÔ ÒÅÚÕÌØÔÁÔÁ ÒÁ×ÅÎ ÓÕÍÍÅ Ä×ÕÈ ÂÉÔÏ× ÓÌÁÇÁÅÍÙÈ É ÂÉÔÁ ÐÅÒÅÎÏÓÁ
ÐÏ ÍÏÄÕÌÀ 2, Á ÂÉÔ ÐÅÒÅÎÏÓÁ ÒÁ×ÅÎ 1, ÅÓÌÉ ÈÏÔÑ ÂÙ Ä×Á ÉÚ ÜÔÉÈ ÔÒ¾È ÂÉÔÏ×
ÒÁ×ÎÙ 1). ðÏÜÔÏÍÕ ÍÏÖÎÏ ÓÏÓÔÁ×ÉÔØ ÓÈÅÍÕ, ËÏÔÏÒÁÑ ×ÙÞÉÓÌÑÅÔ ÜÔÉ ÂÉÔÙ
ÓÐÒÁ×Á ÎÁÌÅ×Ï É ÉÍÅÅÔ ÒÁÚÍÅÒ O(n).

Страницы