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

UptoLike

ВУЗ: 

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

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

Рубрика: 

78 çÌÁ×Á III. ìÏÇÉËÁ ×ÙÓËÁÚÙ×ÁÎÉÊ
É, ÎÁËÏÎÅÃ, ×ÏÓØÍÉÚÎÁÞÎÙÅ:
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
y
1
y
2
y
3
y
4
y
5
y
6
y
7
y
8
ôÁËÉÍ ÏÂÒÁÚÏÍ, ÄÌÑ ÓÕÆÆÉËÓÏ× ÄÌÉÎÙ 8, 4, 2 É 1 ÒÅÚÕÌØÔÁÔÙ ÓÒÁ×ÎÅÎÉÑ ÕÖÅ
ÅÓÔØ. äÌÑ ÓÕÆÆÉËÓÁ ÄÌÉÎÙ 6 ÒÅÚÕÌØÔÁÔ ÍÏÖÎÏ ÐÏÌÕÞÉÔØ, ËÏÍÂÉÎÉÒÕÑ ÒÅ-
ÚÕÌØÔÁÔ ÓÒÁ×ÎÅÎÉÑ x
3
x
4
y
3
y
4
É x
5
x
6
x
7
x
8
y
5
y
6
y
7
y
8
. ðÏÓÌÅ ÜÔÏÇÏ Õ ÎÁÓ ÅÓÔØ
ÉÎÆÏÒÍÁÃÉÑ Ï ÓÕÆÆÉËÓÁÈ ×ÓÅÈ Þ¾ÔÎÙÈ ÄÌÉÎ, É ÓÏÅÄÉÎÑÑ Å¾ Ó ÉÎÆÏÒÍÁÃÉ-
ÅÊ Ó ÐÅÒ×ÏÇÏ ÜÔÁÐÁ, ÐÏÌÕÞÁÅÍ Ó×ÅÄÅÎÉÑ ÐÒÏ ×ÓÅ ÓÕÆÆÉËÓÙ. îÁÐÒÉÍÅÒ, ÄÌÑ
ÓÒÁ×ÎÅÎÉÑ ÓÕÆÆÉËÓÏ× ÄÌÉÎÙ 7, ÔÏ ÅÓÔØ x
2
. . . x
8
É y
2
. . . y
8
, ÍÙ ÓÏÅÄÉÎÑÅÍ ÒÅ-
ÚÕÌØÔÁÔÙ ÓÒÁ×ÎÅÎÉÑ x
2
É y
2
Ó ÒÅÚÕÌØÔÁÔÁÍÉ ÓÒÁ×ÎÅÎÉÑ ÓÕÆÆÉËÓÏ× ÄÌÉÎÙ 6,
ÔÏ ÅÓÔØ x
3
. . . x
8
É y
3
. . . y
8
.
÷ ÏÂÝÅÍ ÓÌÕÞÁÅ ËÁÒÔÉÎÁ ÔÁËÁÑ: ÐÏÓÌÅ ¥ÓÕÖÁÀÝÅÇÏÓÑ ÄÅÒÅ×Á¥ ÍÙ ÓÔÒÏÉÍ
¥ÒÁÓÛÉÒÑÀÝÅÅÓÑ¥; ÚÁ k ÛÁÇÏ× ÄÏ ËÏÎÃÁ ÍÙ ÚÎÁÅÍ ÒÅÚÕÌØÔÁÔÙ ÓÒÁ×ÎÅÎÉÑ
×ÓÅÈ ÓÕÆÆÉËÓÏ×, ÄÌÉÎÙ ËÏÔÏÒÙÈ ËÒÁÔÎÙ 2
k
. üÔÏ ÄÅÒÅ×Ï ÉÍÅÅÔ ÒÁÚÍÅÒ O(n)
É ÇÌÕÂÉÎÕ O(log n), ÞÔÏ ÚÁ×ÅÒÛÁÅÔ ÄÏËÁÚÁÔÅÌØÓÔ×Ï.
úÁÄÁÞÁ 115. ðÏËÁÖÉÔÅ, ÞÔÏ ×ÙÞÉÔÁÎÉÅ Ä×ÕÈ n-ÂÉÔÏ×ÙÈ ÞÉÓÅÌ ÐÏ ÍÏ-
ÄÕÌÀ 2
n
×ÙÐÏÌÎÑÅÔÓÑ ÓÈÅÍÏÊ ÒÁÚÍÅÒÁ O(n) É ÇÌÕÂÉÎÙ O(log n). (õËÁÚÁÎÉÅ:
×ÙÞÉÔÁÎÉÅ ÌÅÇËÏ Ó×ÏÄÉÔÓÑ Ë ÓÌÏÖÅÎÉÀ, ÅÓÌÉ ÚÁÍÅÎÉÔØ ÎÕÌÉ ÎÁ ÅÄÉÎÉÃÙ É
ÎÁÏÂÏÒÏÔ.)
ôÅÐÅÒØ ÚÁÊ;ÍÓÑ ÕÍÎÏÖÅÎÉÅÍ. óÈÅÍÁ ÕÍÎÏÖÅÎÉÑ Ä×ÕÈ n-ÒÁÚÒÑÄÎÙÈ ÞÉÓÅÌ
ÉÍÅÅÔ 2n ×ÈÏÄÏ× (ÐÏ n ÄÌÑ ËÁÖÄÏÇÏ ÍÎÏÖÉÔÅÌÑ) É 2n ×ÙÈÏÄÏ× ÄÌÑ ÐÒÏÉÚ×Å-
ÄÅÎÉÑ.
ðÏÓÍÏÔÒÉÍ, ËÁËÉÅ ÏÃÅÎËÉ ÄÁ¾Ô ÏÂÙÞÎÙÊ ÓÐÏÓÏ ÕÍÎÏÖÅÎÉÑ ÞÉÓÅÌ ÓÔÏÌ-
ÂÉËÏÍ. ÷ Î¾Í ÕÍÎÏÖÅÎÉÅ Ä×ÕÈ n-ÒÁÚÒÑÄÎÙÈ ÞÉÓÅÌ Ó×ÏÄÉÔÓÑ Ë ÓÌÏÖÅÎÉÀ n
ËÏÐÉÊ ÐÅÒ×ÏÇÏ ÞÉÓÌÁ (ÞÁÓÔÉÞÎÏ ÚÁÍÅξÎÎÙÈ ÎÁ ÎÕÌÉ × ÚÁ×ÉÓÉÍÏÓÔÉ ÏÔ ÃÉÆÒ
×ÔÏÒÏÇÏ ÞÉÓÌÁ) ÓÏ ÓÄ×ÉÇÁÍÉ.
ðÏÌÕÞÅÎÉÅ ÜÔÉÈ ËÏÐÉÊ ÔÒÅÂÕÅÔ ÓÈÅÍÙ ÒÁÚÍÅÒÁ O(n
2
) (ÏÂÝÅÅ ÞÉÓÌÏ ÃÉÆÒ
× ËÏÐÉÑÈ) É ÇÌÕÂÉÎÙ O(1). óÌÏÖÅÎÉÅ Ä×ÕÈ 2n-ÒÁÚÒÑÄÎÙÈ ÞÉÓÅÌ ÍÙ ÍÏÖÅÍ
×ÙÐÏÌÎÉÔØ Ó ÐÏÍÏÝØÀ ÓÈÅÍÙ ÒÁÚÍÅÒÁ O(n) É ÇÌÕÂÉÎÙ O(log n), ÔÁË ÞÔÏ
ÎÅÏÂÈÏÄÉÍÙÅ n−1 ÓÌÏÖÅÎÉÊ ÍÏÖÎÏ ×ÙÐÏÌÎÉÔØ ÓÈÅÍÏÊ ÒÁÚÍÅÒÁ O(n
2
) É ÇÌÕ-
ÂÉÎÙ O(log
2
n) (ÅÓÌÉ ÓËÌÁÄÙ×ÁÔØ ÓÎÁÞÁÌÁ ÐÏÐÁÒÎÏ, ÐÏÔÏÍ ÒÅÚÕÌØÔÁÔÙ ÓÎÏ×Á
ÐÏÐÁÒÎÏ É Ô. Ä.). ïËÁÚÙ×ÁÅÔÓÑ, ÜÔÏÔ ÒÅÚÕÌØÔÁÔ ÍÏÖÎÏ ÕÌÕÞÛÉÔØ. îÁÉÂÏÌÅÅ
ÜËÏÎÏÍÎÙÅ ÓÐÏÓÏÂÙ ÏÓÎÏ×ÁÎÙ ÎÁ ÐÒÅÏÂÒÁÚÏ×ÁÎÉÉ æÕÒØÅ . ó ÉÈ ÐÏÍÏÝØÀ,
ÎÁÐÒÉÍÅÒ, ÍÏÖÎÏ ÐÏÓÔÒÏÉÔØ ÓÈÅÍÕ ÕÍÎÏÖÅÎÉÑ n-ÂÉÔÏ×ÙÈ ÞÉÓÅÌ, ÉÍÅÀÝÕÀ
ÒÁÚÍÅÒ n log
c
n.
üÔÉ ÍÅÔÏÄÙ ÄÁÌÅËÏ ×ÙÈÏÄÑÔ ÚÁ ÒÁÍËÉ ÎÁÛÅÇÏ ÏÂÓÕÖÄÅÎÉÑ, ÎÏ Ä×Á ÕÌÕÞ-
ÛÅÎÉÑ ÍÙ ÐÒÉ×ÅľÍ.
78                                             çÌÁ×Á III. ìÏÇÉËÁ ×ÙÓËÁÚÙ×ÁÎÉÊ

É, ÎÁËÏÎÅÃ, ×ÏÓØÍÉÚÎÁÞÎÙÅ:
                               x1 x2 x3 x4 x5 x6 x7 x8
                               y1 y2 y3 y4 y5 y6 y7 y8
ôÁËÉÍ ÏÂÒÁÚÏÍ, ÄÌÑ ÓÕÆÆÉËÓÏ× ÄÌÉÎÙ 8, 4, 2 É 1 ÒÅÚÕÌØÔÁÔÙ ÓÒÁ×ÎÅÎÉÑ ÕÖÅ
ÅÓÔØ. äÌÑ ÓÕÆÆÉËÓÁ ÄÌÉÎÙ 6 ÒÅÚÕÌØÔÁÔ ÍÏÖÎÏ ÐÏÌÕÞÉÔØ, ËÏÍÂÉÎÉÒÕÑ ÒÅ-
ÚÕÌØÔÁÔ ÓÒÁ×ÎÅÎÉÑ x3x4 y3 y4 É x5x6x7 x8 y5y6 y7 y8 . ðÏÓÌÅ ÜÔÏÇÏ Õ ÎÁÓ ÅÓÔØ
ÉÎÆÏÒÍÁÃÉÑ Ï ÓÕÆÆÉËÓÁÈ ×ÓÅÈ Þ¾ÔÎÙÈ ÄÌÉÎ, É ÓÏÅÄÉÎÑÑ Å¾ Ó ÉÎÆÏÒÍÁÃÉ-
ÅÊ Ó ÐÅÒ×ÏÇÏ ÜÔÁÐÁ, ÐÏÌÕÞÁÅÍ Ó×ÅÄÅÎÉÑ ÐÒÏ ×ÓÅ ÓÕÆÆÉËÓÙ. îÁÐÒÉÍÅÒ, ÄÌÑ
ÓÒÁ×ÎÅÎÉÑ ÓÕÆÆÉËÓÏ× ÄÌÉÎÙ 7, ÔÏ ÅÓÔØ x2 . . . x8 É y2 . . . y8, ÍÙ ÓÏÅÄÉÎÑÅÍ ÒÅ-
ÚÕÌØÔÁÔÙ ÓÒÁ×ÎÅÎÉÑ x2 É y2 Ó ÒÅÚÕÌØÔÁÔÁÍÉ ÓÒÁ×ÎÅÎÉÑ ÓÕÆÆÉËÓÏ× ÄÌÉÎÙ 6,
ÔÏ ÅÓÔØ x3 . . . x8 É y3 . . . y8 .
   ÷ ÏÂÝÅÍ ÓÌÕÞÁÅ ËÁÒÔÉÎÁ ÔÁËÁÑ: ÐÏÓÌÅ ¥ÓÕÖÁÀÝÅÇÏÓÑ ÄÅÒÅ×Á¥ ÍÙ ÓÔÒÏÉÍ
¥ÒÁÓÛÉÒÑÀÝÅÅÓÑ¥; ÚÁ k ÛÁÇÏ× ÄÏ ËÏÎÃÁ ÍÙ ÚÎÁÅÍ ÒÅÚÕÌØÔÁÔÙ ÓÒÁ×ÎÅÎÉÑ
×ÓÅÈ ÓÕÆÆÉËÓÏ×, ÄÌÉÎÙ ËÏÔÏÒÙÈ ËÒÁÔÎÙ 2k . üÔÏ ÄÅÒÅ×Ï ÉÍÅÅÔ ÒÁÚÍÅÒ O(n)
É ÇÌÕÂÉÎÕ O(log n), ÞÔÏ ÚÁ×ÅÒÛÁÅÔ ÄÏËÁÚÁÔÅÌØÓÔ×Ï.
   úÁÄÁÞÁ 115. ðÏËÁÖÉÔÅ, ÞÔÏ ×ÙÞÉÔÁÎÉÅ Ä×ÕÈ n-ÂÉÔÏ×ÙÈ ÞÉÓÅÌ ÐÏ ÍÏ-
ÄÕÌÀ 2n ×ÙÐÏÌÎÑÅÔÓÑ ÓÈÅÍÏÊ ÒÁÚÍÅÒÁ O(n) É ÇÌÕÂÉÎÙ O(log n). (õËÁÚÁÎÉÅ:
×ÙÞÉÔÁÎÉÅ ÌÅÇËÏ Ó×ÏÄÉÔÓÑ Ë ÓÌÏÖÅÎÉÀ, ÅÓÌÉ ÚÁÍÅÎÉÔØ ÎÕÌÉ ÎÁ ÅÄÉÎÉÃÙ É
ÎÁÏÂÏÒÏÔ.)
   ôÅÐÅÒØ ÚÁÊ;ÍÓÑ ÕÍÎÏÖÅÎÉÅÍ. óÈÅÍÁ ÕÍÎÏÖÅÎÉÑ Ä×ÕÈ n-ÒÁÚÒÑÄÎÙÈ ÞÉÓÅÌ
ÉÍÅÅÔ 2n ×ÈÏÄÏ× (ÐÏ n ÄÌÑ ËÁÖÄÏÇÏ ÍÎÏÖÉÔÅÌÑ) É 2n ×ÙÈÏÄÏ× ÄÌÑ ÐÒÏÉÚ×Å-
ÄÅÎÉÑ.
   ðÏÓÍÏÔÒÉÍ, ËÁËÉÅ ÏÃÅÎËÉ ÄÁ¾Ô ÏÂÙÞÎÙÊ ÓÐÏÓÏ ÕÍÎÏÖÅÎÉÑ ÞÉÓÅÌ ÓÔÏÌ-
ÂÉËÏÍ. ÷ Î¾Í ÕÍÎÏÖÅÎÉÅ Ä×ÕÈ n-ÒÁÚÒÑÄÎÙÈ ÞÉÓÅÌ Ó×ÏÄÉÔÓÑ Ë ÓÌÏÖÅÎÉÀ n
ËÏÐÉÊ ÐÅÒ×ÏÇÏ ÞÉÓÌÁ (ÞÁÓÔÉÞÎÏ ÚÁÍÅξÎÎÙÈ ÎÁ ÎÕÌÉ × ÚÁ×ÉÓÉÍÏÓÔÉ ÏÔ ÃÉÆÒ
×ÔÏÒÏÇÏ ÞÉÓÌÁ) ÓÏ ÓÄ×ÉÇÁÍÉ.
   ðÏÌÕÞÅÎÉÅ ÜÔÉÈ ËÏÐÉÊ ÔÒÅÂÕÅÔ ÓÈÅÍÙ ÒÁÚÍÅÒÁ O(n2) (ÏÂÝÅÅ ÞÉÓÌÏ ÃÉÆÒ
× ËÏÐÉÑÈ) É ÇÌÕÂÉÎÙ O(1). óÌÏÖÅÎÉÅ Ä×ÕÈ 2n-ÒÁÚÒÑÄÎÙÈ ÞÉÓÅÌ ÍÙ ÍÏÖÅÍ
×ÙÐÏÌÎÉÔØ Ó ÐÏÍÏÝØÀ ÓÈÅÍÙ ÒÁÚÍÅÒÁ O(n) É ÇÌÕÂÉÎÙ O(log n), ÔÁË ÞÔÏ
ÎÅÏÂÈÏÄÉÍÙÅ n − 1 ÓÌÏÖÅÎÉÊ ÍÏÖÎÏ ×ÙÐÏÌÎÉÔØ ÓÈÅÍÏÊ ÒÁÚÍÅÒÁ O(n2) É ÇÌÕ-
ÂÉÎÙ O(log2 n) (ÅÓÌÉ ÓËÌÁÄÙ×ÁÔØ ÓÎÁÞÁÌÁ ÐÏÐÁÒÎÏ, ÐÏÔÏÍ ÒÅÚÕÌØÔÁÔÙ ÓÎÏ×Á
ÐÏÐÁÒÎÏ É Ô. Ä.). ïËÁÚÙ×ÁÅÔÓÑ, ÜÔÏÔ ÒÅÚÕÌØÔÁÔ ÍÏÖÎÏ ÕÌÕÞÛÉÔØ. îÁÉÂÏÌÅÅ
ÜËÏÎÏÍÎÙÅ ÓÐÏÓÏÂÙ ÏÓÎÏ×ÁÎÙ ÎÁ ÐÒÅÏÂÒÁÚÏ×ÁÎÉÉ æÕÒØÅ . ó ÉÈ ÐÏÍÏÝØÀ,
ÎÁÐÒÉÍÅÒ, ÍÏÖÎÏ ÐÏÓÔÒÏÉÔØ ÓÈÅÍÕ ÕÍÎÏÖÅÎÉÑ n-ÂÉÔÏ×ÙÈ ÞÉÓÅÌ, ÉÍÅÀÝÕÀ
ÒÁÚÍÅÒ n logc n.
   üÔÉ ÍÅÔÏÄÙ ÄÁÌÅËÏ ×ÙÈÏÄÑÔ ÚÁ ÒÁÍËÉ ÎÁÛÅÇÏ ÏÂÓÕÖÄÅÎÉÑ, ÎÏ Ä×Á ÕÌÕÞ-
ÛÅÎÉÑ ÍÙ ÐÒÉ×ÅľÍ.

Страницы