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

§3. óÈÅÍÙ ÉÚ ÆÕÎËÃÉÏÎÁÌØÎÙÈ ÜÌÅÍÅÎÔÏ×                                 83




                   òÉÓ. 4. éÔÅÒÉÒÕÅÍÁÑ ÆÕÎËÃÉÑ ϕ.

  åÓÌÉ ×ÎÁÞÁÌÅ ÅÄÉÎÉÃÙ ÓÏÓÔÁ×ÌÑÀÔ ÂÏÌØÛÉÎÓÔ×Ï ÉÚ n ÁÒÇÕÍÅÎÔÏ× (ÎÁÐÏ-
ÍÎÉÍ, n ÎÅÞ¾ÔÎÏ), ÔÏ ÉÈ ËÁË ÍÉÎÉÍÕÍ (n + 1)/2, ÔÁË ÞÔÏ p > (n + 1)/2n =
= 1/2 + 1/(2n). ôÁËÉÍ ÏÂÒÁÚÏÍ, ÎÁÞÁÌØÎÙÊ ÄÉÓÂÁÌÁÎÓ ÓÏÓÔÁ×ÌÑÅÔ ËÁË ÍÉÎÉ-
ÍÕÍ 1/2n. á × ËÏÎÃÅ ÎÁÍ ÎÕÖÎÏ ÐÒÉÂÌÉÚÉÔØÓÑ Ë ËÒÁÀ ÏÔÒÅÚËÁ ÎÁ ÒÁÓÓÔÏÑÎÉÅ
2−n.
  éÔÁË, ÎÁÍ ÏÓÔÁÌÏÓØ ÄÏËÁÚÁÔØ ÔÁËÕÀ ÌÅÍÍÕ (ÏÔÎÏÓÑÝÕÀÓÑ ÓËÏÒÅÅ Ë ÍÁÔÅ-
ÍÁÔÉÞÅÓËÏÍÕ ÁÎÁÌÉÚÕ):
  ìÅÍÍÁ. ðÕÓÔØ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ xk ∈ [0, 1] ÚÁÄÁÎÁ ÒÅËÕÒÒÅÎÔÎÏÊ ÆÏÒ-
ÍÕÌÏÊ xk+1 = ϕ(xk ), ÇÄÅ
                            ϕ(x) = 3x2 − 2x3.
ðÕÓÔØ x0 > 1/2+1/(2n). ôÏÇÄÁ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ xk ÍÏÎÏÔÏÎÎÏ ×ÏÚÒÁÓÔÁÅÔ
É ÐÒÉÂÌÉÖÁÅÔÓÑ Ë 1 ÎÁ ÒÁÓÓÔÏÑÎÉÅ 2−n ÚÁ O(log n) ÛÁÇÏ×. [óÉÍÍÅÔÒÉÞÎÏÅ
ÕÔ×ÅÒÖÄÅÎÉÅ ×ÅÒÎÏ É ÐÒÉ x0 6 1/2 − 1/(2n).]
   éÄÅÑ ÄÏËÁÚÁÔÅÌØÓÔ×Á: ÐÏÓÍÏÔÒÉÍ ÎÁ ÆÕÎËÃÉÀ ×ÂÌÉÚÉ ÔÏÞËÉ 1/2 É Õ ËÒÁ¾×
ÏÔÒÅÚËÁ. ÷ ÔÏÞËÅ 1/2 ÐÒÏÉÚ×ÏÄÎÁÑ ÂÏÌØÛÅ 1, ÐÏÜÔÏÍÕ ÕÄÁÌÅÎÉÅ ÏÔ 1/2 ÒÁÓÔ¾Ô
ËÁË ÇÅÏÍÅÔÒÉÞÅÓËÁÑ ÐÒÏÇÒÅÓÓÉÑ, É ÔÏÞËÁ ÐÅÒÅÊÄ¾Ô ËÁËÕÀ-ÔÏ ÆÉËÓÉÒÏ×ÁÎÎÕÀ
ÇÒÁÎÉÃÕ (ÎÁÐÒÉÍÅÒ, 0,51) ÎÅ ÐÏÚÄÎÅÅ ÞÅÍ ÚÁ O(log n) ÛÁÇÏ×. úÁÔÅÍ ÐÏÔÒÅ-
ÂÕÅÔÓÑ O(1) ÛÁÇÏ×, ÞÔÏÂÙ ÄÏÊÔÉ, ÓËÁÖÅÍ, ÄÏ 0,99. ÷ ÅÄÉÎÉÃÅ ÐÅÒ×ÁÑ ÐÒÏÉÚ-
×ÏÄÎÁÑ ÆÕÎËÃÉÉ ÒÁ×ÎÁ ÎÕÌÀ, ÐÏÜÔÏÍÕ ÒÁÓÓÔÏÑÎÉÅ ÄÏ ÅÄÉÎÉÃÙ ËÁÖÄÙÊ ÒÁÚ
ÐÒÉÍÅÒÎÏ ×ÏÚ×ÏÄÉÔÓÑ × Ë×ÁÄÒÁÔ, É ÐÏÔÏÍÕ ÄÌÑ ÄÏÓÔÉÖÅÎÉÑ ÐÏÇÒÅÛÎÏÓÔÉ 2 −n
ÐÏÔÒÅÂÕÅÔÓÑ O(log n) ÛÁÇÏ× (ËÁË × ÍÅÔÏÄÅ îØÀÔÏÎÁ ÏÔÙÓËÁÎÉÑ ËÏÒÎÑ). ÷ÓÅÇÏ
ÐÏÌÕÞÁÅÔÓÑ O(log n) + O(1) + O(log n) ÛÁÇÏ×, ÞÔÏ É ÔÒÅÂÏ×ÁÌÏÓØ.