\input style
\chapno=5\subchno=4
\chapnotrue

%%438
\htable{Рюакхжю 1}%
{Уюпюйрепхярхйх норхлюкэмнцн депебю $A_m(n)$, $k_m(n)$ опх $\alpha=\beta=1$}%
{$n=#$\hfill&
\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&
\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&
\hfill$\,#\,$\hfill&$n=#$\hfill\cr
\omit
  & m=1 &  m=2 & m=3 & m=4 & m=5 & m=6 & m=7 & m=8 & m=9 & m=10& m=11& m=12& \hbox{Нохяюмхе депебю}\cr
1 &  0,0&      &     &     &     &     &     &     &     &     &     &     &-         & 1\cr
2 &  6,2&  0,1 &     &     &     &     &     &     &     &     &     &     &1:1       & 2\cr
3 & 12,3&  6,1 &  0,1&     &     &     &     &     &     &     &     &     &1:1:1     & 3\cr
4 & 20,4& 12,1 &  6,1&  0,1&     &     &     &     &     &     &     &     &1:1:1:1   & 4\cr
5 & 30,5& 18,2 & 12,1&  6,1&  0,1&     &     &     &     &     &     &     &1:1:1:1:1 & 5\cr
6 & 42,2& 24,3 & 18,1& 12,1&  6,1&  0,1&     &     &     &     &     &     & 3:3      & 6\cr
7 & 52,3& 32,3 & 24,1& 18,1& 12,1&  6,1&  0,1&     &     &     &     &     & 1:3:3    & 7\cr
8 & 62,3& 40,4 & 30,2& 24,1& 18,1& 12,1&  6,1&  0,1&     &     &     &     & 2:3:3    & 8\cr
9 & 72,3& 50,4 & 36,3& 30,1& 24,1& 18,1& 12,1&  6,1&  0,1&     &     &     & 3:3:3    & 9\cr
10& 84,3& 60,5 & 44,3& 36,1& 30,1& 24,1& 18,1& 12,1&  6,1&  0,1&     &     & 3:3:4    &10\cr
11& 96,3& 72,4 & 52,3& 42,2& 36,1& 30,1& 24,1& 18,1& 12,1&  6,1&  0,1&     & 3:4:4    &11\cr
12&108,3& 82,4 & 60,4& 48,3& 42,1& 36,1& 30,1& 24,1& 18,1& 12,1&  6,1&  0,1& 4:4:4    &12\cr
13&121,4& 92,4 & 70,4& 56,3& 48,1& 42,1& 36,1& 30,1& 24,1& 18,1& 12,1&  6,1& 3:3:3:4  &13\cr
14&134,4&102,5 & 80,4& 64,3& 54,2& 48,1& 42,1& 36,1& 30,1& 24,1& 18,1& 12,1& 3:3:4:4  &14\cr
15&147,4&114,5 & 90,5& 72,3& 60,3& 54,1& 48,1& 42,1& 36,1& 30,1& 24,1& 18,1& 3:4:4:4  &15\cr
16&160,4&124,7 &102,4& 80,4& 68,3& 60,1& 54,1& 48,1& 42,1& 36,1& 30,1& 24,1& 4:4:4:4  &16\cr
17&175,4&134,8 &112,4& 90,4& 76,3& 66,2& 60,1& 54,1& 48,1& 42,1& 36,1& 30,1& 4:4:4:5  &17\cr
18&190,4&144,9 &122,4&100,4& 84,3& 72,3& 66,1& 60,1& 54,1& 48,1& 42,1& 36,1& 4:4:5:5  &18\cr
19&205,4&156,9 &132,5&110,4& 92,3& 80,3& 72,1& 66,1& 60,1& 54,1& 48,1& 42,1& 4:5:5:5  &19\cr
20&220,4&168,9 &144,4&120,5&100,4& 88,3& 78,2& 72,1& 66,1& 60,1& 54,1& 48,1& 5:5:5:5  &20\cr
21&236,5&180,9 &154,4&132,4&110,4& 96,3& 84,3& 78,1& 72,1& 66,1& 60,1& 54,1& 4:4:4:4:5&21\cr
22&252,3&192,10&164,4&142,4&120,4&104,3& 92,3& 84,1& 78,1& 72,1& 66,1& 60,1& 4:9:9    &22\cr
23&266,3&204,11&174,5&152,4&130,4&112,3&100,3& 90,2& 84,1& 78,1& 72,1& 66,1& 5:9:9    &23\cr
24&282,3&216,12&186,5&162,5&140,4&120,4&108,3& 96,3& 90,1& 84,1& 78,1& 72,1& 5:9:10   &24\cr
25&296,3&229,12&196,7&174,4&150,5&130,4&116,3&104,3& 96,1& 90,1& 84,1& 78,1& 7:9:9    &25\cr
}
Мюь бшбнд бшпюфемхъ~$(2)$ онйюгшбюер, врн бяецдю, йнцдю хяонкэгсчряъ 
$P+1$~пюбмшу астепнб, асдер хлерэ леярн яннрмньемхе~$\alpha\le\beta$. 
Опедекэмши яксвюи~$\alpha=\beta$, онйюгюммши б рюак.~1 х мю пхя.~93, 
бнгмхйюер рнцдю, йнцдю рпеасеряъ лхмхлхгхпнбюрэ яюлн бпелъ онхяйю 
аегнрмняхрекэмн йн бпелемх оепедювх.

Бепмеляъ й мюьеи оепбнмювюкэмни гюдюве. Лш еые ме пюяялнрпекх, йюй 
онксвхрэ мювюкэмше нрпегйх; аег янблеыемхъ времхъ/гюохях/бшвхякемхи 
бшанп я гюлеыемхел репъер мейнрнпше хг ябнху опехлсыеярб. Бнглнфмн, мюл 
якедсер гюонкмхрэ бяч бмсрпеммчч
\picture{Пхя. 93. Норхлюкэмши яоняна якхъмхъ 22 мювюкэмшу нрпегйнб пюбмни 
дкхмш, еякх б ренпеле М $\alpha=\beta$. Щрю яуелю лхмхлхгхпсер бпелъ 
онхяйю опх опедонкнфемхъу, опхбедьху й тнплске (2).
}
оюлърэ, нрянпрхпнбюрэ ее х бшбеярх пегскэрюр; йюфдсч хг рюйху ноепюжхи 
ббндю х бшбндю лнфмн бшонкмхрэ я ндмхл онхяйнл. Хкх, бнглнфмн, ксвье 
хяонкэгнбюрэ, яйюфел, 20\% оюлърх йюй йнлахмхпнбюммши астеп ббндю/бшбндю 
х бшонкмърэ бшанп я гюлеыемхел. Щрн рпеасер б оърэ пюг анкэье онхяйнб 
(днонкмхрекэмн опхлепмн 60~я!), мн слемэьюер вхякн мювюкэмшу нрпегйнб 
ян~100 дн~64; слемэьемхе асдер еые анкее пегйхл, еякх ббндмши тюик сфе 
онврх сонпъднвем.

Еякх лш пеьхкх ме хяонкэгнбюрэ бшанп я гюлеыемхел, рн норхлюкэмне депебн 
дкъ $S=100$, $\alpha=0.00145$, $\beta=0.01545$ 
[ял. (2)] нйюгшбюеряъ беяэлю опнгюхвеяйхл. Щрн опнярн 10-осребне якхъмхе, 
бшонкмъелне гю дбю опнундю он дюммшл. Бшдекъъ 30~я мю бмсрпеммчч 
янпрхпнбйс (яйюфел, 100~ашярпшу янпрхпнбнй), онксвюел, врн мювюкэмши 
пюяопедекхрекэмши опнунд, гюмхлюер опхлепмн
$2{1\over2}$~лхм, ю йюфдши опнунд якхъмхъ гюмхлюер онврх 5~лхм; б хрнце
хлеел $12.4$~лхм. Еякх лш пеьхкх хяонкэгнбюрэ бшанп я гюлеыемхел, рн 
норхлюкэмне депебн дкъ $S=64$ нйюгшбюеряъ ндхмюйнбн мехмрепеямшл (дбю 
опнундю 8-осребнцн якхъмхъ); мювюкэмши пюяопедекхрекэмши опнунд гюмхлюер 
опхлепмн $3{1\over2}$~лхм, йюфдши опнунд якхъмхъ---нйнкн $4{1\over2}$~лхм, 
нжемйю наыецн бпелемх янярюбкъер 12.6~лхм.
%%440
Бяонлмхл, врн б нанху щрху лерндюу тюйрхвеяйх онкмнярэч 
хяйкчвюеряъ янблеыемхе времхъ/гюохях/бшвхякемхи, врнаш хлерэ анкэьхе 
астепш (я жекэч слемэьемхъ бпелемх онхяйю). Мх ндмю хг щрху нжемнй ме 
бйкчвюер бпелъ, йнрнпне лнфер онрпеанбюрэяъ дкъ ноепюжхи йнмрпнкэмнцн времхъ.

Мю опюйрхйе онякедмхи опнунд якхъмхъ нйюгшбюеряъ нркхвмшл нр нярюкэмшу; 
мюопхлеп, бшбндмше дюммше вюярн педюйрхпсчряъ х/хкх гюохяшбючряъ мю кемрс.
 Б рюйху яксвюъу депебн, хгнапюфючыее яуелс якхъмхъ, якедсер бшахпюрэ я 
хяонкэгнбюмхел б йнпмебнл сгке хмнцн йпхрепхъ норхлюкэмнярх.

\section *Дпсцни яоняна пюяопедекемхъ астепнб. Дюбхд~Щ.~Тепцчянм сйюгюк 
[{\sl CACM,\/} {\bf 14} (1971), 476--478], врн лнфмн слемэьхрэ 
бпелъ онхяйю, еякх ме декюрэ бяе астепш ндмнцн пюглепю. Рю фе лшякэ х 
опхлепмн б рн фе бпелъ опхькю б цнкнбс еые меяйнкэйхл кхжюл 
[S.~J.~Waters, {\sl Comp.~J.,\/} {\bf 14} (1971), 109--112; 
Ewing~S.~Walker, Software Age, {\bf 4} (August-September, 1970), 16--17].

Опедонкнфхл, врн лш бшонкмъел вершпеуосребне якхъмхе нрпегйнб пюбмни 
дкхмш~$L_0$, хлеъ оюлърэ б $M$~кхреп. Еякх лш пюгдекхл оюлърэ мю пюбмше 
астепш пюглепю~$B=M/5$, рн мюл онрпеасеряъ нйнкн $L_0/B$~онхяйнб дкъ 
йюфднцн ббндмнцн тюикю х $4L_0/B$~онхяйнб дкъ бшбндю, врн б яслле дюер 
$8L_0/B = 40L_0/M$~онхяйнб. Мн еякх лш хяонкэгсел вершпе астепю ббндю 
пюглепю~$M/6$ х ндхм астеп бшбндю пюглепю~$M/3$, рн мюл онрпеасеряъ 
бяецн кхьэ нйнкн $4\times(6L_0/M)+4\times(3L_0/M)=36L_0/M$~онхяйнб! 
Бпелемю оепедювх б нанху яксвюъу ндхмюйнбш, рюй врн лш мхвецн ме 
онрепъел нр щрнцн хглемемхъ.

Б наыел яксвюе опедонкнфхл, врн лш унрхл якхрэ нрянпрхпнбюммше тюикш, 
хлечыхе дкхмш~$L_0$,~\dots, $L_p$, б нрянпрхпнбюммши тюик 
дкхмш~$L_{P+1}=L_1+\cdots+L_P$, х опедонкнфхл, врн дкъ $k\hbox{-цн}$тюикю 
хяонкэгсеряъ астеп пюглепю~$B_k$. Рнцдю
$$
B_1+\cdots+B_P+B_{P+1}=M,
\eqno(6)
$$
цде $M$---наыхи на╝ел мюкхвмни бмсрпеммеи оюлърх. Вхякн онхяйнб асдер 
опхакхгхрекэмн пюбмн
$$
{L_1\over B_1}+\cdots+{L_P\over B_P}+{L_{P+1}\over B_{P+1}}.
\eqno(7)
$$
Оношрюеляъ лхмхлхгхпнбюрэ щрс бекхвхмс опх сякнбхх~(6), явхрюъ дкъ 
сднаярбю, врн $B_k$ ме наъгюмш ашрэ жекшлх. Еякх сбекхвхрэ~$B_j$ 
мю~$\delta$ х слемэьхрэ~$B_k$ мю рс фе меанкэьсч бекхвхмс, рн вхякн 
онхяйнб хглемхряъ мю
$$
{L_j\over B_j+\delta}-{L_j\over B_j}+{L_k\over B_k-\delta}-{L_k\over B_k} 
=\left({L_k\over B_k(B_k-\delta)}-{L_j\over B_j(B_j+\delta)}\right)\delta,
$$
р.~е., пюяопедекемхе лнфмн сксвьхрэ, еякх $L_j/B^2_j\ne L_k/B^2_k$. 
Якеднбюрекэмн,
%% 441
лш онксвхл лхмхлюкэмне вхякн онхяйнб, рнкэйн еякх
$$
{L_1\over B^2_1}=\cdots={L_P\over B^2_P}={L_{P+1}\over B^2_{P+1}}.
\eqno(8)
$$
Рюй йюй лхмхлсл наъгюрекэмн ясыеярбсер, нм днкфем днярхцюрэяъ опх
$$
B_k=\sqrt{L_k}M/(\sqrt{L_1}+\cdots+\sqrt{L_{P+1}}),\quad 1\le k\le P+1,
\eqno(9)
$$
оняйнкэйс щрн едхмярбеммше гмювемхъ~$B_1$,~\dots, $B_{P+1}$, 
сднбкербнпъчыхе ндмнбпелеммн~(6) х~(8). Ондярюмнбйю щрху гмювемхи 
б~(7) дюер беяэлю опнярсч тнплскс дкъ наыецн вхякю онхяйнб:
$$
(\sqrt{L_1}+\cdots+\sqrt{L_{P+1}})^2/M,
\eqno(10)
$$
йнрнпсч лнфмн япюбмхрэ я вхякнл $(P+1)(L_1+\cdots+L_{P+1})/M$,
 онксвючыхляъ б рнл яксвюе, еякх бяе астепш пюбмш он дкхме.
Бшхцпшь пюбем~$\sum_{1\le j<k\le P+1}(\sqrt{L_j}-\sqrt{L_k})^2/M$   
янцкюямн соп.~1.2.3-31. Й янфюкемхч, тнплскю (10) ме цндхряъ дкъ опнярнцн 
нопедекемхъ норхлюкэмни яуелш якхъмхъ, йюй б ренпеле~K (яп.~я соп.~14).

\section Днонкмхрекэмше яннапюфемхъ. Еякх хяонкэгсчряъ дбю 
дхяйнбшу сярпниярбю (ндмн дкъ времхъ х ндмн дкъ гюохях), рн лнфмн 
янблеярхрэ вюярэ бпелемх гюохях жемни днонкмхрекэмнцн астепю бшбндю. 
Еякх хяонкэгсеряъ лернд "опнцмнгхпнбюмхъ" (р.~е.~лш ялнрпхл мю онякедмхи 
йкчв б йюфднл астепе ббндю, врнаш нопедекхрэ, йюйни астеп оепбшл 
нябнандхряъ), рн лнфмн янблеярхрэ вюярэ бпелемх времхъ. Й янфюкемхч, 
опнярюъ опнжедспю яхмупнмхгюжхх, бпнде опнжедспш б юкцнпхрле 5.4.6F, ме 
наеяоевхбюер меопепшбмнцн ббндю/бшбндю, рюй йюй лемъчыееяъ бпелъ 
времхъ нгмювюер, врн ноепюжхх ббндю х бшбндю ме асдср нйюмвхбюрэяъ б ндмн 
бпелъ. Рнвмши на╝ел янблеыемхи рпсдмн нжемхрэ, х, бнглнфмн, ксвье 
опнлндекхпнбюрэ опнжеяя якхъмхъ, врнаш мюирх йнмярюмрш~$\alpha$ х~$\beta$ 
дкъ опхакхфеммнцн бпелемх якхъмхъ, йюй б ренпеле~H.

Еякх лш хяонкэгсел "окюбючыхе" астепш (ме опхохяюммше й йнмйпермнлс тюикс),
 рн нмх днкфмш ашрэ ндмнцн пюглепю, х рнцдю мекэгъ опхлемърэ опхбедеммсч 
бшье реумхйс пюяопедекемхъ астепнб; лнфмн рнкэйн бшапюрэ астепш бшбндю 
анкэье, вел астепш ббндю. Еякх хяонкэгсеряъ $2P$~астепнб ббндю 
(блеярн~$P$), лш янблеыюел гмювхрекэмсч днкч бпелемх ббндю, ндмюйн 
сдбюхбюел бпелъ онхяйю х, бнглнфмн, мхвецн ме бшхцпюел; он-бхдхлнлс, 
ксвье бяецн хлерэ $P+1$ хкх $P+2$~астепнб ббндю.
Реоепэ вхрюрекч днкфмн ашрэ ъямн, врн мхйюйни верйни ярпюрецхх дкъ 
норхлюкэмни янпрхпнбйх мю дхяйюу ме пюгпюанрюмн;
вхякн бнглнфмшу бюпхюмрнб гмювхрекэмн опебшьюер вхякн ярпюрецхи. йнрнпше 
ашкх опнюмюкхгхпнбюмш ренперхвеяйх. Унръ ренпхъ,
%%442
пюгбхрюъ б щрнл осмйре, дюер мейнрнпше онкегмше опедярюбкемхъ, бяе 
еые рпеасеряъ гмювхрекэмши на╝ел щйяоепхлемрюкэмшу хяякеднбюмхи.

\section *Ондпнамее на норхлюкэмшу депебэъу. Б ренпелюу~H х~K хмрепеямн 
пюяялнрперэ йпюимхи яксвюи~$\beta=0$, меялнрпъ мю рн врн опюйрхвеяйхе 
яхрсюжхх нашвмн опхбндър й оюпюлерпюл~$0\le\alpha\le\beta$. Йюйне депебн я 
$n$~кхярэълх хлеер мюхлемэьсч бнглнфмсч дкхмс яреоеммнцн осрх? Кчаношрмн, 
врн б щрнл яксвюе мюхксвьхл нйюгшбюеряъ рпеуосребне якхъмхе.

\proclaim Ренпелю L. Дкхмю яреоеммнцн осрх депебю я $n$~кхярэълх мхйнцдю 
ме лемэье, вел
$$
f(n)=\cases{
3qn+2(n-3^q), & еякх $2\cdot 3^{q-1}\le n\le 3^q$;\cr
3qn+4(n-3^q), & еякх $3^q\le n\le 2\cdot 3^q$.\cr
}
\eqno(11)
$$
Репмюпмше депебэъ~$\cJ_n$, нопедекеммше опюбхкюлх
\picture{Пхясмнй мю ярп. 442}
хлечр лхмхлюкэмсч дкхмс яреоеммнцн осрх.

\proof. Бюфмн гюлерхрэ, врн $f (n)$---бшосйкюъ тсмйжхъ, р. е.
$$
f(n+1)-f(n)\ge f(n)-f(n-1) \rem{опх бяеу $n\ge2$}.
\eqno(13)
$$
Щрн ябниярбн ясыеярбеммн ббхдс якедсчыеи келлш.

\proclaim Келлю Я. тсмйжхъ~$g(n)$, нопедекеммюъ мю онкнфхрекэмшу жекшу 
вхякюу, сднбкербнпъер сякнбхч
$$
\min_{1\le k\le n} (g(k)+g(n-k))=g(\floor{n/2})+g(\ceil{n/2}), 
\quad n\ge 2,
\eqno (14)
$$
рнцдю х рнкэйн рнцдю, йнцдю нмю бшосйкюъ.

\proof. Еякх $g(n+1)-g(n)<g(n)- g(n-1)$ опх мейнрнпнл~$n>2$, рн хлеел 
$g(n+1)+g(n-1)<g(n)+g(n)$, врн опнрхбнпевхр~(14). Напюрмн, еякх~(13) 
хлеер леярн дкъ~$g$ 
х~$1\le k<n-k$, рн б яхкс 
бшосйкнярх~$g(k+1)+g(n-k-1)\le g(k)+g(n-k)$.\proofend

Онякедмчч вюярэ днйюгюрекэярбю келлш Я лнфмн пюяопнярпюмхрэ мю 
кчане~$m\ge2$ х онйюгюрэ, врн
$$
\min_{n_1+\cdots+n_m=n\atop n_1, \ldots, n_m\ge 1}
 (g(n_1)+\cdots+g(n_m))=g(\floor{n/m})+g(\floor{(n+1)/m})+\cdots
+g(\floor{(n+m-1)/m}),
\eqno(15)
$$
%%443
еякх $g$~бшосйкю. Осярэ
$$
f_m(n)=f(\floor{n/m})+f(\floor{(n+1)/m})+\cdots+f(\floor{(n+m-1)/m}).
$$
Днйюгюрекэярбн ренпелш~L гюбепьюеряъ днйюгюрекэярбнл рнцн, 
врн $f_3(n)+3n=f(n)$ х~$f_m(n)+mn\ge f(n)$ опх бяеу~$m\ge2$ (ял.~соп.~11).\proofend

Ашкн аш нвемэ унпньн, еякх аш норхлюкэмше депебэъ бяецдю уюпюйрепхгнбюкхяэ 
рюй фе верйн, йюй б ренпеле~L. Мн пегскэрюрш дкъ $\alpha=\beta$, йнрнпше 
лш бхдхл б рюак.~1, онйюгшбючр, врн тсмйжхъ~$A_1(n)$ ме бяецдю бшосйкю. Мю 
яюлнл деке рюак.~1 днярюрнвмн, врнаш нопнбепцмсрэ анкэьхмярбн опняршу 
опедонкнфемхи на норхлюкэмшу депебэъу! Лш, ндмюйн, лнфел яоюярх вюярэ 
ренпелш~L дкъ яксвюъ опнхгбнкэмшу~$\alpha$ х~$\beta$. Л.~Ькчлаепцеп 
х Ф.~Бхиелюм онйюгюкх, врн \emph{бшянйху} онпъдйнб якхъмхъ бяецдю лнфмн 
хгаефюрэ.

\proclaim Ренпелю M. Еякх дюмш~$\alpha$ х~$\beta$, йюй б ренпеле~H, рн 
ясыеярбсер норхлюкэмне депебн, б йнрнпнл яреоемэ кчанцн сгкю ме опебняундхр
$$
d(\alpha, \beta)=\ceil{\min_{k\ge1}\left(k+\left(1+{1\over k}\right)
\left(1+{\beta\over\alpha}\right)\right)}.
\eqno(17)
$$

\proof. Осярэ $n_1$,~\dots, $n_m$---онкнфхрекэмше жекше вхякю, рюйхе, врн 
$n_1+\cdots+n_m=n$, $A(n_1)+\cdots+A(n_m)= A_m(n)$, 
$n_1\le \ldots \le n_m$, х опедонкнфхл, врн $m\ge d(\alpha, \beta)+1$. 
Осярэ $k$---рн гмювемхе, опх йнрнпнл днярхцюеряъ лхмхлсл б (17); онйюфел, врн
$$
\alpha n(m-k)+\beta n+A_{m-k}(n)\le \alpha m n +\beta n+A_m(n),
\eqno(18)
$$
х, якеднбюрекэмн, лхмхлсл б (4) бяецдю днярхцюеряъ опх мейнрнпнл
$m\le d(\alpha, \beta)$.

Он нопедекемхч, оняйнкэйс $m\ge k+2$, лш днкфмш хлерэ
$$
\eqalign{
A_{m-k}(n) &\le A_1(n_1+\cdots+n_{k+1})+A_1(n_{k+2})+\cdots
+A_1(n_m)\le\cr
&\le \alpha(n_1+\cdots+n_{k+1})(k+1)+\beta(n_1+\cdots+n_{k+1})+\cr
&\phantom{\le}+A_1(n_1)+\cdots+A_1(n_m)=\cr
&=(\alpha(k+1)+\beta)(n_1+\cdots+n_{k+1})+A_m(n)\le\cr
&\le(\alpha(k+1)+\beta)(k+1)n/m+A_m(n),\cr
}
$$
нрячдю (18) кецйн бшбндхряъ. (Рыюрекэмне пюяялнрпемхе щрнцн 
днйюгюрекэярбю онйюгшбюер, врн нжемйю~(17) ъбкъеряъ "мюхксвьеи хг 
бнглнфмшу" б рнл ялшяке, врн мейнрнпше норхлюкэмше депебэъ днкфмш хлерэ 
сгкш яреоемх~$d(\alpha, \beta)$; ял. соп.~13.) \proofend

Онярпнемхе б ренпеле~K рпеасер $O(N^2)$~ъвеей оюлърх х $O(N^2\log 
N)$~ьюцнб дкъ бшвхякемхъ $A_m(n)$ опх $1\le m\le n\le N$, a
%%444
б ренпеле~M онйюгюмн, врн рпеасеряъ рнкэйн $O(N)$~ъвеей х $O(N^2)$~ьюцнб. 
Ькчлаепцеп х Бхиелюм нрйпшкх еые меяйнкэйн нвемэ хмрепеямшу ябниярб 
норхлюкэмшу депебэеб 
[Optimal disk merge patterns, {\sl Acta Informatica,\/} {\bf 3} (1973), 25--36].

\section Хяонкэгнбюмхе яжеокемхъ. Л. Ю. Цнрж 
[{\sl CACM,\/} {\bf 6} (1963), 245--248]
опедкнфхк хмрепеямши яоняна, опх йнрнпнл нрдекэмше днпнфйх ябъгшбючряъ 
блеяре х акюцндюпъ щрнлс хяйкчвюеряъ онхяй опх бшбнде. Дкъ пеюкхгюжхх ецн 
хдех рпеасеряъ онврх мебннапюгхлши мюанп опнцпюлл, сопюбкъчыху дхяйюлх, 
мн яюлю хдеъ, йпнле янпрхпнбйх, опхлемхлю бн лмнцху дпсцху гюдювюу, х 
онщрнлс нмю лнфер опхбеярх й беяэлю жеммшл лерндюл наыецн мюгмювемхъ.

Хдеъ опнярю. Блеярн пюглеыемхъ днпнфей онякеднбюрекэмн бмсрпх жхкхмдпнб 
дхяйю лш ябъгшбюел ху блеяре х упюмхл яохяйх ябнандмнцн опнярпюмярбю он 
ндмнлс дкъ йюфднцн жхкхмдпю. Йнцдю опхундхр бпелъ бшбеярх днпнфйс 
хмтнплюжхх, лш гюохяшбюел ее б рейсыхи жхкхмдп (б рнр, цде нйюгюкяъ 
депфюрекэ цнкнбнй), еякх щрнр жхкхмдп ме онкнм. Опх щрнл бпелъ 
онхяйю нашвмн ябндхряъ мю мер.

Гдеяэ мюя ондярепецюер кнбсьйю. Декн б рнл, врн лш ме лнфел гюохяшбюрэ 
яяшкйс мю якедсчысч днпнфйс бмсрпх яюлни днпнфйх, оняйнкэйс менаундхлюъ 
дкъ щрнцн хмтнплюжхъ б мсфмши лнлемр ме хгбеярмю. (Лш лнцкх аш, еякх щрн 
мюя сярпнхр, гюохяшбюрэ яяшкйс мю опедшдсысч днпнфйс х мю 
якедсчыел опнунде вхрюрэ тюик б напюрмнл мюопюбкемхх.) Лнфмн 
упюмхрэ нрдекэмсч рюакхжс юдпеянб ябъгх дкъ днпнфей йюфднцн тюикю,
 бнглнфмн, вюярхвмн мю яюлнл дхяйе. Яохяйх ябнандмнцн-опнярпюмярбю лнфмн 
йнлоюйрмн опедярюбхрэ я онлныэч ахрнбшу рюакхж, цде 1000~ахрнб сйюгшбючр 
гюмърнярэ хкх мегюмърнярэ 1000~днпнфей.

\qsection Онлнфер кх янпрхпнбйю йкчвеи? Еякх гюохях дкхммше, ю йкчвх 
йнпнрйхе, беяэлю гюлюмвхбн янгдюрэ мнбши тюик, янярнъыхи рнкэйн хг йкчвеи 
блеяре я онпъдйнбшлх мнлепюлх, нопедекъчыхлх ху оепбнмювюкэмне онкнфемхе б 
тюике. Оняке янпрхпнбйх щрнцн тюикю йкчвеи лнфмн гюлемхрэ йкчвх 
онякеднбюрекэмшлх вхякюлх~$1$, $2$,~\dots. Гюрел щрнр мнбши тюик лнфмн 
нрянпрхпнбюрэ он онкнфемхч б оепбнмювюкэмнл тюике, х лш онксвхл 
сднамне нохяюмхе рнцн, йюй "пюярюянбюрэ" гюохях, врнаш оепепюглеярхрэ ху б 
рпеаселнл онпъдйе.

Яуелюрхвеяйх опедярюбхл опнжеяя рюй:
\halign{
#\hfill&#\hfill\cr
a) хяундмши тюик           & $(K_1, I_1)$ $(K_2, I_2)$ \dots $(K_N, I_N)$ дкхммши;\cr
b) йкчвебни тюик          & $(K_1, 1)$ $(K_2, 2)$ \dots $(K_N, N)$ йнпнрйхи;\cr
c) нрянпрхпнбюммши (b)& $(K_{p_1}, p_1)$ $(K_{p_2}, p_2)$\dots $(K_{p_N}, p_N)$ йнпнрйхи;\cr
%%445
d) нрпедюйрхпнбюммши (я) & $(1, p_1)$ $(2, p_2)$ \dots $(N, p_N)$ йнпнрйхи;\cr
e) нрянпрхпнбюммши   (d)&  $(q_1, 1)$ $(q_2, 2)$ \dots $(q_N, N)$ йнпнрйхи;\cr
f) нрпедюйрхпнбюммши (a) & $(q_1, I_1)$  $(q_2, I_2)$ \dots $(q_N, I_n)$ дкхммши.\cr
}

\noindent Гдеяэ $p_j=k$ рнцдю х рнкэйн рнцдю, йнцдю $q_k=j$; дбю 
опнжеяяю янпрхпнбйх б ярюдхъу (c) х (c) япюбмхрекэмн ашярпше (хмнцдю лнфмн 
нанирхяэ бмсрпеммеи янпрхпнбйни), рюй йюй гюохях ме якхьйнл дкхммше. Мю 
ярюдхх (f) лш ябекх гюдювс й янпрхпнбйе тюикю, йкчвх йнрнпнцн---опнярн вхякю 
$\{1, 2,~\ldots, N\}$; йюфдюъ гюохяэ реоепэ нопедекъер б рнвмнярх рн леярн,
йсдю ее якедсер оепелеярхрэ.

Опнакелю бмеьмецн оепепюглеыемхъ, нярючыюъяъ оняке ярюдхх (f), йюферяъ 
мю оепбши бгцкъд рпхбхюкэмни, мн тюйрхвеяйх нмю нвемэ якнфмю, х бяе еые ме 
мюидемн мх ндмнцн деиярбхрекэмн унпньецн юкцнпхрлю (ясыеярбеммн ксвьецн, 
вел янпрхпнбйю). Лш, нвебхдмн, лнцкх аш бшонкмхрэ оепепюглеыемхе гю 
$N$~ьюцнб, оепелеыюъ бяъйхи пюг он ндмни гюохях; дкъ 
днярюрнвмн анкэьнцн~$N$ щрн ксвье, вел $N\log N$ б лерндюу янпрхпнбйх. 
Мн $N$ мхйнцдю ме ашбюер рюйхл анкэьхл; $N$ онхяйнб опнярн мепеюкэмш!

Й нрпедюйрхпнбюммшл гюохяъл лнфмн щттейрхбмн опхлемърэ йюйни-кхан лернд 
онпюгпъдмни янпрхпнбйх, рюй йюй йкчвх хлечр ярпнцн пюбмнлепмне 
пюяопедекемхе. Мю лмнцху бшянйняйнпнярмшу ЩБЛ я бшянйняйнпнярмшлх 
оепхтепхимшлх сярпниярбюлх бпелъ бшвхякемхи дкъ бняэлхосребнцн 
пюяопедекемхъ гмювхрекэмн лемэье, вел бпелъ бшвхякемхи дкъ 
бняэлхосребнцн якхъмхъ; якеднбюрекэмн, пюяопедекхрекэмюъ янпрхпнбйю 
лнфер ашрэ мюхксвьеи хг бяеу опнжедсп (ял.~о.~5.4.7, ю рюйфе соп.~17).

Мн, он-бхдхлнлс, аеяялшякеммн опнбндхрэ янпрхпнбйс йкчвеи кхьэ дкъ рнцн,
 врнаш бшонкмхрэ гюрел онкмсч янпрхпнбйс! Ндмю хг опхвхм менфхдюммни 
рпсдмнярх опнакелш бмеьмецн оепепюглеыемхъ ашкю нрйпшрю П.~С.~Ткниднл, 
йнрнпши мюьек мерпхбхюкэмсч мхфмчч цпюмхжс дкъ вхякю онхяйнб, рпеаселшу,
 врнаш оепеярюбхрэ гюохях б дхяйнбнл тюике 
[Complexity of Computer Computations (New York, Plenum, 1972), 105--109].

Пегскэрюр Ткнидю сднамн нохяюрэ, бняонкэгнбюбьхяэ юмюкнцхеи я кхтрнл, 
йюй б о.~5.4.8; мю щрнр пюг лш унрхл мюирх цпютхй пюанрш кхтрю, 
лхмхлхгхпсчыхи вхякн нярюмнбнй, ю ме опнидеммне пюяярнъмхе. (Лхмхлхгюжхъ 
вхякю \emph{нярюмнбнй} ме бонкме щйбхбюкемрмю мюунфдемхч юкцнпхрлю 
оепепюглеыемхъ я лхмхлюкэмшл вхякнл онхяйнб, рюй йюй ндмю нярюмнбйю 
на╝едхмъер бунд б кхтр я бшунднл хг мецн; ндмюйн пюгмхжю ме якхьйнл бекхйю,
  х лш бняонкэгселяъ йпхрепхел лхмхлхгюжхх нярюмнбнй, врнаш онъямхрэ 
нямнбмше хдех.)
%% 446
Асдел хяонкэгнбюрэ тсмйжхч "дхяйпермни щмрпнохх"
$$
F(n)=\sum_{1<k\le n}(\ceil{\log_2 k}+1)=B(n)+n-1
=n\ceil{\log_2 n}-2^{\ceil{\log_2 n}}+n,
\eqno(19)
$$
цде $B(n)$ еярэ тсмйжхъ "ахмюпмни бярюбйх" (ял. тнплскс (5.3.1-3)). 
Янцкюямн (5.3.1-33), тсмйжхъ $F(n)$ еярэ ме врн хмне, йюй лхмхлюкэмюъ 
дкхмю бмеьмецн осрх ахмюпмнцн депебю я $n$~кхярэълх, х  
$$
n\log_2 n\le F(n)\le n\log_2 n+0.0861n.
\eqno(20)
$$
Рюй йюй $F (n)$ бшосйкю х сднбкербнпъер 
сякнбхч~$F(n)=n+F(\floor{n/2})+F(\ceil{n/2})$, рн он келле~C
$$
F(n)\le F(k)+F(n-k)+n \rem{опх $0\le k\le n$.}
\eqno(21)
$$
Щрн яннрмньемхе бшрейюер рюйфе хг опедярюбкемхъ $F$ б бхде дкхмш бмеьмецн 
осрх; б дюкэмеиьел нмн нйюферяъ пеьючыхл тюйрнл.

Йюй х б о.~5.4.8, лш асдел опедонкюцюрэ, врн кхтр блеыюер $b$~векнбей, 
йюфдши щрюф блеыюер $c$~векнбей х хлееряъ $n$~щрюфеи. Осярэ $s_{ij}$---вхякн 
кчдеи, мюундъыхуяъ б дюммши лнлемр мю щрюфе~$i$ х ярпелъыхуяъ оноюярэ мю 
щрюф~$j$. Он нопедекемхч 
\emph{нжемйю янблеярмнярх} кчанцн пюяонкнфемхъ кчдеи б гдюмхх 
еярэ~$\sum_{1\le i,j\le n} F(s_{ij})$.

Опедонкнфхл, мюопхлеп, врн $b=c=n=6$ х врн оепбнмювюкэмн 36~векнбей 
якедсчыхл напюгнл пюяопедекемш лефдс щрюфюлх:
{\obeyspaces
$$
\vbox{
\line{\tt\indent \]\]\]\]\]\]}
\line{\tt\indent 123456 123456 123456 123456 123456 123456 \hfill \rm (22)}
}
$$
}
Кхтр осяр х мюундхряъ мю щрюфе 1; "\]" нангмювюер ябнандмне леярн. Мю 
йюфднл щрюфе мюундхряъ векнбей, ярпелъыхияъ оноюярэ мю опнхгбнкэмши щрюф,
 онщрнлс бекхвхмш~$s_{ij}$. пюбмш~1 х нжемйю янблеярмнярх пюбмю~0. Еякх 
реоепэ кхтр нрбегер 6~векнбей мю щрюф~2, рн лш онксвхл пюяонкнфемхе
{\obeyspaces
$$
\vbox{
\line{\tt\indent        123456}
\line{\tt\indent \]\]\]\]\]\] 123456 123456 123456 123456 123456 \hfill 
\rm (23)}
}
$$
}
х нжемйю янблеярмнярх ярюмер пюбмю $6F(0)+24F(1)+6F(2)=12$. Дносярхл, 
кхтр оепебегер |1|, |1|, |2|, |3|, |3|, |4| мю щрюф~3:
{\obeyspaces
$$
\vbox{
\line{\tt\indent               112334}
\line{\tt\indent \]\]\]\]\]\] 245566 123456 123456 123456 123456 \hfill 
\rm (24)}
}
$$
}
%%447
Нжемйю янблеярмнярх хглемхкюяэ дн $4F(2)+2F(3)=18$. Йнцдю йюфдши векнбей 
асдер б йнмже йнмжнб оепебегем й ябнелс леярс мюгмювемхъ, нжемйни 
янблеярмнярх асдер $6F(6)=96$.

Ткнид гюлерхк, врн нжемйю янблеярмнярх мхйнцдю ме сбекхвхбюеряъ анкэье, 
вел мю $b+c$ гю ндмс нярюмнбйс, рюй йюй лмнфеярбн хг $s$~кчдеи я пюбмшл 
мюгмювемхел, на╝едхмъъяэ я юмюкнцхвмшл лмнфеярбнл лнымнярх~$s'$, 
сбекхвхбюер нжемйс мю $F(s+s')-F(s)-F(s')\le s+s'$. Рюйхл напюгнл, хлеел 
якедсчыхи пегскэрюр.

\proclaim Ренпелю~F. Осярэ $t$---нопедекеммюъ бшье нжемйю янблеярмнярх 
мювюкэмнцн пюяонкнфемхъ кчдеи. Кхтр днкфем ядекюрэ он йпюимеи лепе
$$
\ceil{(nF(c)-t)/(b+c)}
$$
нярюмнбнй, врнаш днярюбхрэ бяеу кчдеи й ху леярс мюгмювемхъ.\endmark


Ятнплскхпсел щрнр пегскэрюр опхлемхрекэмн й дхяйюл. Дносярхл, хлееряъ 
$N$~гюохяеи он $B$ б йюфднл акнйе, х опедонкнфхл, врн бн бмсрпеммеи 
оюлърх ндмнбпелеммн онлеыюеряъ $M$~гюохяеи. Опх йюфднл времхх я дхяйю ндхм 
акнй оепемняхряъ б мюлърэ, ю опх йюфдни гюохях ндхм акнй онлеыюеряъ мю 
дхяй, х $s_{ij}$ еярэ вхякн гюохяеи б акнйе~$i$, опхмюдкефюыху 
акнйс~$j$. Еякх $N\ge B^2$, рн ясыеярбсер мювюкэмне пюяонкнфемхе, дкъ 
йнрнпнцн бяе $s_{ij}\le 1$, х, якеднбюрекэмн, дкъ оепепюглеыемхъ 
гюохяеи менаундхлн опнвхрюрэ он йпюимеи лепе 
$(N/B)F(B)/M\approx (N \log_2 B)/M$~акнйнб. (Еякх $B$ бекхйн, рн 
лмнфхрекэ~$\log_2 B$ декюер щрс мхфмчч нжемйс мерпхбхюкэмни, мн еякх $B=1$,
 рн мхфмчч нжемйс, нвебхдмн, лнфмн сксвьхрэ.)

\excercises
\ex[M22] Б рейяре на╝ъямъеряъ лернд, я онлныэч йнрнпнцн япедмее 
бпелъ нфхдюмхъ, рпеаселне дкъ времхъ днкх~$x$ днпнфйх, слемэьюеряъ 
я~${1\over2}$ 
дн~${1\over2}(1-x^2)$~нанпнрнб. Щрн лхмхлюкэмн бнглнфмне бпелъ, йнцдю 
хлееряъ ндхм депфюрекэ цнкнбнй. Йюйнбн яннрберярбсчыее лхмхлюкэмне бпелъ 
нфхдюмхъ, еякх хлечряъ \emph{дбю} депфюрекъ цнкнбнй, пюгмеяеммше мю 
$180^\circ$ (б опедонкнфемхх, врн б кчани лнлемр дюммше лнфер оепедюбюрэ 
рнкэйн ндхм хг депфюрекеи)?

\ex[M30] (Щ.~Ц.~Йнмуеил.) Жекэ щрни гюдювх---хяякеднбюрэ, мю 
йюйне пюяярнъмхе днкфем оепелеярхрэяъ депфюрекэ цнкнбнй бн бпелъ якхъмхъ 
тюикнб, пюяонкнфеммшу "нпрнцнмюкэмн" й жхкхмдпюл Дносярхл, хлееряъ 
$P$~тюикнб, йюфдши хг йнрнпшу яндепфхр $L$~акнйнб гюохяеи, х опедонкнфхл,
врн оепбши акнй йюфднцн тюикю мюундхряъ мю жхкхмдпе~1, брнпни---мю 
жхкхмдпе~2 х р~д Дбхфемхел депфюрекъ цнкнбнй бн бпелъ якхъмхъ сопюбкъер 
нрмняхрекэмши онпъднй онякедмху йкчвеи йюфднцн акнйю; якеднбюрекэмн, 
лнфмн хгнапюгхрэ яхрсюжхч якедсчыхл яонянанл, сднамшл дкъ люрелюрхвеяйни
%%448
хмрепоперюжхх. Пюяялнрпхл лмнфеярбн хг $PL$ сонпъднвеммшу оюп
$$
\matrix{
(a_{11},1) & (a_{21},1) & \ldots & (a_{P1},1) \cr
(a_{12},2) & (a_{22},2) & \ldots & (a_{P2},2) \cr
\vdots & \vdots & & \vdots \cr
(a_{1L},L) & (a_{2L},L) & \ldots & (a_{PL},L) \cr
}
$$
цде лмнфеярбн $\{\, a_{ij} \mid 1\le i\le P, 1\le j\le L\,\}$ 
яннрберярбсер лмнфеярбс вхяек $\{\,1, 2, \ldots, PL\,\}$ б мейнрнпнл 
онпъдйе х $a_{ij}<a_{i,j+1}$ опх $1\le j<L$ (ярпнйх опедярюбкъчр жхкхмдпш, 
ярнкажш---хяундмше тюикш). Нрянпрхпсел оюпш он ху оепбшл йнлонмемрюл, х 
осярэ онксвхбьеияъ онякеднбюрекэмнярэч асдер $(1, j_1)$ $(2, j_2)$ \dots{} 
$(PL, j_{PL})$. Онйюфхре, врн еякх бяе $(PL)!/L!^P$ бнглнфкшу 
мюанпнб~$a_{ij}$ пюбмнбепнърмш, рн япедмее гмювемхе
$$
\abs{j_2-j_1}+\abs{j_3-j_2}+\cdots+\abs{j_{PL}-j_{PL-1}}
$$
пюбмн
$$
(L-1)\left(1+(P-1)2^{2L-2}/\perm{2L}{L}\right).
$$
[\emph{Сйюгюмхе:} ял. соп. 5.2.1-14 ] Гюлерхл, врн опх  $L\to\infty$ щрн 
гмювемхе юяхлорнрхвеяйх пюбмн ${1\over4}(P-1)L\sqrt{\pi L}$.

\ex[Л15] Опедонкнфхл, врн нцпюмхвеммши пюглеп бмсрпеммеи оюлърх декюер 
мефекюрекэмшл $10\hbox{-осребне}$ якхъмхе. Йюй лнфмн хглемхрэ 
пейсппемрмше яннрмньемхъ (3), (4), (5), врнаш $A_1(n)$ ярюкн лхмхлюкэмшл 
гмювемхел~$\alpha D(\cJ)+\beta E(\cJ)$ япедх бяеу депебэеб~$\cJ$ я 
$n$~кхярэълх, ме хлечыху сгкнб яреоемх, анкэьеи вел~9?

\rex[Л21] (a) Бшбедхре тнплскс, юмюкнцхвмсч (2), дкъ бпелемх бшонкмемхъ 
$P\hbox{-осребнцн}$ якхъмхъ $L$~кхреп, еякх хяонкэгсеряъ бхднхглемеммюъ 
тнплю йбюдпюрхвмнцн пюяопедекемхъ астепнб%
\note{1}{Ял. рюйфе тнплскс (9).---{\sl Опхл. пед.\/}}: бяе $P$~астепнб ббндю 
днкфмш хлерэ пюбмше дкхмш, ю пюглеп астепю бшбндю якедсер бшапюрэ рюй, 
врнаш лхмхлхгхпнбюрэ бпелъ онхяйю.

(b) Онйюфхре, врн онярпнемхе б ренпеле~K лнфмн хглемхрэ рюй, врн 
онксвхряъ яуелю якхъмхъ, йнрнпюъ асдер норхлюкэмни б ялшяке бюьеи 
тнплскш хг вюярх~(a).

\ex[Л20] Еякх хяонкэгсчряъ дбю дхяйю, опхвел времхе я ндмнцн янблеыюеряъ 
я гюохяэч мю дпсцни, рн лш ме лнфел опхлемърэ яуелс якхъмхъ, онднамсч 
опедярюбкеммни мю пхя.~93, рюй йюй мейнрнпше кхярэъ мюундъряъ мю вермшу 
спнбмъу, ю дпсцхе мю мевермшу. Онйюфхре, йюй хглемхрэ онярпнемхе б 
ренпеле~K, врнаш онксвюкхяэ норхлюкэмше депебэъ я свернл нцпюмхвемхъ, 
врн бяе кхярэъ мюундъряъ мю вермшу спнбмъу хкх бяе мю мевермшу.

\rex[22] Мюидхре депебн, норхлюкэмне б ялшяке соп.~6, еякх~$n=23$ 
х~$\alpha=\beta=1$. (Бнглнфмн, с бюя онъбхряъ фекюмхе опхаецмсрэ й онлных ЩБЛ.)

\rex[Л24] Еякх дкхмш мювюкэмшу нрпегйнб ме пюбмш, рн мюхксвьюъ 
яуелю якхъмхъ (б ялшяке ренпелш~H) лхмхлхгхпсер $\alpha D(\cJ)+\beta 
E(\cJ)$, цде $D(\cJ)$ х~$E(\cJ)$ реоепэ опедярюбкъчр янани бгбеьеммше 
дкхмш осреи: йюфднлс кхярс депебю опхохяшбючряъ беяю $w_1$,~\dots, $w_n$ 
(яннрберярбсчыхе дкхмюл мювюкэмшу нрпегйнб), ю ясллш яреоемеи х дкхмш 
осреи слмнфючряъ мю яннрберярбсчыхе беяю. Мюопхлеп, еякх $\cJ$---депебн, 
опедярюбкеммне мю пхя.~92, рн 
онксвхл $D(\cJ)=6w_1+6w_2+7w_3+9w_4+9w_5+7w_6+4w_7+4w_8$, 
$E (\cJ)=2w_1+2w_2+2w_3+3w_4+3w_5+2w_6+w_7+w_8$.

Днйюфхре, врн опх мейнрнпнл $k$ бяецдю ясыеярбсер норхлюкэмюъ яуелю, б 
йнрнпни оепбшлх якхбючряъ $k$ \emph{яюлшу йнпнрйху нрпегйнб}.

%%449

\ex[49] Ясыеярбсер, кх юкцнпхрл, йнрнпши опх гюдюммшу $\alpha$, $\beta$ х 
беяюу~$w_1$,~\dots, $w_n$ мюундхр норхлюкэмше б ялшяке соп.~7 депебэъ, 
гюрпювхбюъ рнкэйн $O(n^c)$~ьюцнб опх мейнрнпнл~$c$?

\ex[M49] (Ькчлаепцеп х Бхиелюм.) Бепмн кх, врн дкъ бяеу $n$, $\alpha$ х~$\beta$
ясыеярбсчр норхлюкэмше б ялшяке ренпелш~H депебэъ я $n$~кхярэълх, с 
йнрнпшу бяе кхярэъ мюундъряъ яюлне анкэьее мю дбсу яняедмху спнбмъу? 
Еякх $\alpha$ х~$\beta$ тхйяхпнбюмш, ясыеярбсер кх вхякн $m$, рюйне, врн 
дкъ бяеу днярюрнвмн анкэьху $n$ хлеер леярн $A_1(n)=\alpha mn+\beta 
n+A_m(n)$? (Наю щрх опедонкнфемхъ ашкх опнбепемш б яксвюе~$\alpha/\beta\ge 4$.)

\ex[БЛ49] Йюйнбн юяхлорнрхвеяйне онбедемхе $A_1(n)$ опх $n\to\infty$ 
опх гюдюммшу $\alpha$ х~$\beta$?

\ex[Л29] Б нангмювемхъу (11) х~(16) днйюфхре, врн $f_m(n) + mn\ge 
f(n)$ опх бяеу $m$, $n\ge 2$, х нопедекхре бяе рхо, опх йнрнпшу хлеер 
леярн пюбемярбн.

\ex[25] Днйюфхре, врн опх бяеу $n>0$ ясыеярбсер депебн я $n$~кхярэълх х 
лхмхлюкэмни дкхмни яреоеммнцн осрх (11), бяе кхярэъ йнрнпнцн пюяонкнфемш 
мю ндмнл спнбме.

\ex[M24] Онйюфхре, врн опх $2\le n \le d(\alpha,\beta)$ едхмярбеммни 
мюхксвьеи яуелни якхъмхъ б ялшяке ренпелш~H ъбкъеряъ $n\hbox{-осребне}$ 
якхъмхе. 
(Яп. я тнплскни (17).)

\ex[40] Опх хяонкэгнбюмхх йбюдпюрхвмнцн лерндю пюяопедекемхъ астепнб бпелъ 
онхяйю дкъ -яуелш якхъмхъ мю пхя.~92 асдер опнонпжхнмюкэмн
$(\sqrt{2}+\sqrt{4}+\sqrt{1}+\sqrt{1}+\sqrt{8})^2
+(\sqrt{1}+\sqrt{1}+\sqrt{2})^2+\sqrt{1}+\sqrt{2}
+(\sqrt{1}+\sqrt{4})^2+(\sqrt{1}+\sqrt{1}+\sqrt{2})^2$; 
щрн гмювемхе опедярюбкъер янани ясллс
бекхвхм $(\sqrt{n_1}+\cdots+\sqrt{n_m}+\sqrt{n_1+\cdots+n_m})^2$ он бяел 
бмсрпеммхл сгкюл, цде онддепебэъ щрху сгкнб хлечр 
$(n_1, \ldots, n_m)$~кхярэеб. 
Мюохьхре опнцпюллс дкъ ЩБЛ, йнрнпюъ онпнфдюер депебэъ я 
лхмхлюкэмшл бпелемел онхяйю, хлечыхе $1$, $2$, $3$, \dots{} кхярэеб, 
хяонкэгсъ дкъ нжемйх бпелемх онхяйю щрс тнплскс.

\ex[M22] Онйюфхре, врн лнфмн меяйнкэйн сяхкхрэ ренпелс~F, еякх 
кхтр оепбнмювюкэмн осяр х еякх $nF(c)\ne t$: б щрнл яксвюе менаундхлн ме 
лемее $\ceil{(nF(c)+b-t)/(b+c)}$~нярюмнбнй.

\ex[23] (П.~С.~Ткнид.) Мюидхре цпютхй пюанрш кхтрю, оепебнгъыхи бяеу кчдеи 
хг~(22) й ху леярюл мюгмювемхъ гю~12 хкх лемэьее вхякн нярюмнбнй. (Б~(23) 
онйюгюмн онкнфемхе оняке ндмни, ю ме оняке дбсу нярюмнбнй.)

\ex[25] (А.~Р.~Аеммер х Ю.~В.~Люй-Йеккюп, 1971.) Пюяялнрпхл якедсчыхи 
лернд я янпрхпнбйни йкчвеи, опнделнмярпхпнбюммши мю опхлепе тюикю я 10 йкчвюлх:
\medskip
\item{a)} Хяундмши тюик: $(50, I_0)$ $(08, I_1)$ $(51, I_2)$ $(06, I_3)$ $(90, I_4)$ $(17, I_5)$ $(89, I_6)$ $(27, I_7)$ $(65, I_8)$ $(42, I_9)$.

\item{b)} Тюик йкчвеи: $(50, 0)$ $(08, 1)$ $(51, 2)$ $(06, 3)$ $(90, 4)$ $(17, 5)$ $(89, 6)$ $(27, 7)$ $(65, 8)$ $(42, 9)$.

\item{c)} Нрянпрхпнбюммши (b): $(06, 3)$ $(08, 1)$ $(17, 5)$ $(27, 7)$ $(42, 9)$ $(50,0)$ $(51,2)$ $(65, 8)$ $(89, 6)$ $(90, 4)$.

\item{d)} Опхябюхбюмхе мнлепнб ъыхйнб: $(3, 3)$ $(3, 9)$ $(2, 1)$ $(2, 5)$ $(2, 7)$ $(2, 8)$ $(1, 0)$ $(1, 2)$ $(1, 4)$ $(1, 6)$.

\item{e)} Нрянпрхпнбюммши (d): $(1, 0)$ $(2, 1)$ $(1, 2)$ $(3, 3)$ $(1, 4)$ $(2, 5)$ $(1, 6)$ $(2, 7)$ $(2, 8)$ $(3, 9)$.

\item{f)} (a), пюяопедекеммши он ъыхйюл я хяонкэгнбюмхел (e):
\itemitem{Ъыхй 1:} $(50, I_0)$ $(51, I_2)$ $(90, I_4)$ $(89, I_6)$.
\itemitem{Ъыхй 2:} $(08, I_1)$ $(17, I_5)$ $(27, I_7)$ $(65, I_8)$.
\itemitem{Ъыхй 3:} $(06, I_3)$ $(42, I_9)$.
\item{g)} Пегскэрюр бшанпю я гюлеыемхел (ямювюкю вхрюеряъ ъыхй~3, 
гюрел ъыхй~2, гюрел ъыхй~1): $(06, I_3)$ $(08, I_1)$ $(17, I_5)$ $(27, I_7)$ $(42, I_9)$ $(50, I_0)$ $(51, I_2)$ $(65, I_8)$ $(89, I_6)$ $(90, I_4)$.
\medskip
\noindent Мнлепю ъыхйнб мю ьюце~(d) опхябюхбючряъ осрел опхлемемхъ й~(я) 
\emph{бшанпю я гюлеыемхел яопюбю мюкебн б сашбючыел} онпъдйе он брнпни йнлонмемре.
%%450
Мнлеп ъыхйю---щрн мнлеп нрпегйю. Б опхбедеммнл опхлепе хяонкэгсеряъ бшанп я 
гюлеыемхел рнкэйн я дбслъ щкелемрюлх б депебе; дкъ бшанпю я гюлеыемхел 
б~(d) х~(g) днкфем хяонкэгнбюрэяъ ндхмюйнбши пюглеп депебю бшанпю. Гюлерхл,
 врн яндепфхлне ъыхйнб ме наъгюрекэмн сонпъднвемн.

Днйюфхре, врн щрнр лернд асдер янпрхпнбюрэ, р. е. врн бшанп я гюлеыемхел 
б (g) напюгсер кхьэ ндхм нрпегнй. (Щрнр лернд слемэьюер вхякн ъыхйнб, 
рпеаселне нашвмни янпрхпнбйни йкчвеи оняпедярбнл пюяопедекемхъ, нянаеммн 
еякх хяундмше дюммше сфе б яхкэмни яреоемх сонпъднвемш.)

\rex[25] Мейнрнпше яхярелш опеднярюбкъчр опнцпюллхярюл 
\emph{бхпрсюкэмсч оюлърэ:} лнфмн охяюрэ опнцпюллш, хяундъ хг опедонкнфемхъ,
 врн хлееряъ нвемэ анкэьюъ бмсрпеммъъ оюлърэ, яонянамюъ блеярхрэ бяе 
дюммше. Щрю оюлърэ пюгдекемю мю ярпюмхжш, х кхьэ мелмнцхе хг мху 
деиярбхрекэмн мюундъряъ бн бмсрпеммеи оюлърх б кчани лнлемр бпелемх, 
нярюкэмше фе упюмъряъ мю дхяйюу хкх аюпюаюмюу. Опнцпюллхярс ме мсфмн 
бмхйюрэ бн бяе щрх ондпнамнярх, рюй йюй яхярелю яюлю нан бяел гюанрхряъ: 
мнбше ярпюмхжш юбрнлюрхвеяйх бшгшбючряъ б оюлърэ, йнцдю нмх мсфмш.

Лнфер онйюгюрэяъ, врн онъбкемхе бхпрсюкэмни оюлърх опхбндхр й нрлхпюмхч 
лернднб бмеьмеи янпрхпнбйх, рюй йюй щрю пюанрю лнфер ашрэ бшонкмемю 
опнярн я онлныэч лернднб, пюгпюанрюммшу дкъ бмсрпеммеи 
янпрхпнбйх. Пюгаепхре щрс яхрсюжхч. Онвелс яоежхюкэмн пюгпюанрюммши лернд 
бмеьмеи янпрхпнбйх лнфер нйюгюрэяъ ксвье опхлемемхъ наыеи реумхйх 
ондйювйх ярпюмхж й лерндс бмсрпеммеи янпрхпнбйх?


\subchap{ПЕГЧЛЕ. ХЯРНПХЪ Х АХАКХНЦПЮТХЪ} % 5.5
Реоепэ, йнцдю лш онврх днярхцкх йнмжю щрни нвемэ дкхммни цкюбш, ярнхр 
"нрянпрхпнбюрэ" мюханкее бюфмше тюйрш хг вхякю хгсвеммшу.

Юкцнпхрл янпрхпнбйх---щрн опнжедспю, йнрнпюъ пенпцюмхгсер тюик гюохяеи рюйхл 
напюгнл, врнаш йкчвх нйюгюкхяэ б бнгпюярючыел онпъдйе. Акюцндюпъ рюйнлс 
сонпъднвеммнлс пюяонкнфемхч цпсоохпсчряъ гюохях я пюбмшлх йкчвюлх, 
ярюмнбхряъ бнглнфмни щттейрхбмюъ напюанрйю лмнцху тюикнб, 
нрянпрхпнбюммшу он ндмнлс йкчвс, янгдюеряъ нямнбю дкъ 
щттейрхбмшу юкцнпхрлнб бшанпйх х анкее саедхрекэмн бшцкъдър днйслемрш,
 ондцнрнбкеммше я онлныэч ЩБЛ.

\emph{Бмсрпеммъъ янпрхпнбйю} хяонкэгсеряъ б реу яксвюъу, йнцдю бяе гюохях 
онлеыючряъ б ашярпни бмсрпеммеи оюлърх люьхмш. Лш хгсвхкх я пюгмни 
яреоемэч дерюкхгюжхх анкее дбсу деяърйнб юкцнпхрлнб бмсрпеммеи янпрхпнбйх, 
мн мюл, мюбепмне, ашкн аш йсдю яонйнимее, еякх аш лш ме гмюкх рюй лмнцн 
пюгкхвмшу ондунднб й щрни гюдюве! Хгсвемхе бяеу щрху лернднб ашкн опхърмшл 
бпелъопнбнфдемхел. Мн реоепэ оепед мюлх аегпюднярмюъ 
оепяоейрхбю---опедярнхр мю деке пеьхрэ, йюйни лернд якедсер хяонкэгнбюрэ б 
рни хкх хмни йнмйпермни яхрсюжхх.

Ашкн аш опейпюямн, еякх аш рнкэйн ндхм хкх дбю лерндю янпрхпнбйх 
опебняундхкх бяе нярюкэмше аегнрмняхрекэмн й опхкнфемхч хкх хяонкэгселни 
люьхме. Мю яюлнл фе деке йюфдши лернд хлеер ябнх янаярбеммше, ндмнлс елс 
опхясыхе днярнхмярбю. Мюопхлеп, лернд осгшпэйю (юкцнпхрл~5.2.2Б) ме хлеер 
ъпйн бшпюфеммшу опехлсыеярб, рюй йюй бяецдю лнфмн мюирх ксвьхи яоняна 
ядекюрэ рн, врн нм декюер; мн дюфе щрнр лернд оняке яннрберярбсчыецн 
нанаыемхъ нйюгшбюеряъ онкегмшл дкъ янпрхпнбйх я дбслъ кемрюлх (ял. 
о.~5.4.8). Хрюй, опхундхл й гюйкчвемхч, врн онврх бяе юкцнпхрлш 
гюяксфхбючр рнцн, врнаш н мху онлмхкх, рюй йюй ясыеярбсчр опхкнфемхъ, б 
йнрнпшу нмх нйюгшбючряъ беяэлю унпньхлх.

Б якедсчыел йпюрйнл нагнпе нябеыючряъ нямнбмше юяоейрш мюханкее бюфмшу 
юкцнпхрлнб бмсрпеммеи янпрхпнбйх, я йнрнпшлх лш бярпевюкхяэ. (Йюй нашвмн,
 $N$ нгмювюер вхякн гюохяеи б тюике.)

%%452

1. {\sl Пюяопедекъчыхи ондявер.\/} Юкцнпхрл~5.2D нвемэ онкегем, еякх 
дхюоюгнм йкчвеи мебекхй. Лернд сярнивхб (ме хглемъеряъ онпъднй гюохяеи я 
пюбмшлх йкчвюлх), мн рпеасеряъ оюлърэ дкъ явервхйнб х $2N$~гюохяеи. Ндмю 
хг лндхтхйюжхи, щйнмнлъыюъ $N$ хг щрху гюохяеи жемни сярнивхбнярх, 
бярпевюеряъ б соп. 5.2-13.

2. {\sl Опнярше бярюбйх.\/} Юкцнпхрл 5.2.1S мюханкее опняр 
дкъ опнцпюллхпнбюмхъ, ме рпеасер днонкмхрекэмнцн опнярпюмярбю х бонкме 
щттейрхбем опх люкшу~$N$ (яйюфел, опх $N\le 25$). Опх анкэьху~$N$ нм 
ярюмнбхряъ мебшмняхлн ледкеммшл, еякх рнкэйн хяундмше дюммше ме нйюфсряъ 
япюгс онврх сонпъднвеммшлх.

3. {\sl Янпрхпнбйю я сашбючыхл ьюцнл.\/} Юкцнпхрл 5.2.1D (лернд Ьеккю) рюй 
фе днбнкэмн опнярн опнцпюллхпсеряъ, хяонкэгсер лхмхлюкэмши на╝ел оюлърх х 
днбнкэмн щттейрхбем опх слепеммн анкэьху~$N$ (яйюфел, опх $N\le 1000$).

4. {\sl Бярюбйх б яохянй.\/} Юкцнпхрл 5.2.1L нямнбюм мю рни фе хдее, врн х 
опнярше бярюбйх, х онщрнлс цндхряъ рнкэйн опх меанкэьху~$N$. Йюй х б 
дпсцху лерндюу янпрхпнбйх яохяйнб, б мел акюцндюпъ ноепюжхъл ян яяшкйюлх 
щйнмнлхряъ ярнхлнярэ оепелеыемхъ дкхммшу гюохяеи; щрн нянаеммн сднамн, 
йнцдю гюохях хлечр оепелеммсч дкхмс хкх ъбкъчряъ вюярэч дпсцху ярпсйрсп дюммшу.

5. {\sl Янпрхпнбйю я бшвхякемхел юдпеяю\/} щттейрхбмю, еякх йкчвх 
 ондвхмъчряъ хгбеярмнлс (нашвмн пюбмнлепмнлс) гюйнмс пюяопедекемхъ; 
бюфмеиьхлх бюпхюмрюлх щрнцн ондундю ъбкъчряъ \emph{бярюбйх б меяйнкэйн яохяйнб}
(юкцнпхрл 5.2.1Л) х йнлахмхпнбюммюъ онпюгпъдмюъ янпрхпнбйю ян 
бярюбйюлх Люйкюпемю (пюяялнрпеммюъ б йнмже о.~5.2.5). Дкъ онякедмецн 
лерндю днярюрнвмн хлерэ $O(\sqrt{N})$ днонкмхрекэмшу ъвеей оюлърх.

6. {\sl Налеммюъ янпрхпнбйю ян якхъмхел.\/} Юкцнпхрл 5.2.2Л (лернд 
Ащрвепю) х пндярбеммши елс юкцнпхрл \emph{ахрнммни 
янпрхпнбйх} (соп.~5.3.4-10) онкегмш, еякх лнфмн ндмнбпелеммн 
бшонкмърэ анкэьне вхякн япюбмемхи.

7. {\sl Налеммюъ янпрхпнбйю я пюгдекемхел\/} (лернд Унюпю, 
ьхпнйн хгбеярмши йюй \emph{ашярпюъ янпрхпнбйю}). Юкцнпхрл 5.2.2Q, бепнърмн,
 яюлши онкегмши смхбепяюкэмши юкцнпхрл бмсрпеммеи янпрхпнбйх, оняйнкэйс 
нм рпеасер нвемэ люкн оюлърх х ноепефюер ябнху йнмйспемрнб он япедмелс 
бпелемх бшонкмемхъ мю анкэьхмярбе бшвхякхрекэмшу люьхм. Ндмюйн б 
мюхусдьел яксвюе нм лнфер пюанрюрэ нвемэ ледкеммн. Онщрнлс, еякх 
бепнърмнярэ меяксвюимшу дюммшу днярюрнвмн бекхйю, опхундхряъ 
рыюрекэмн бшахпюрэ пюгдекъчыхи щкелемр. Еякх бшахпюеряъ ледхюмю хг рпеу 
щкелемрнб (йюй опедкюцюеряъ б соп. 5.2.2-55), рн рюйне
%%453
онбедемхе, йюй б мюхусдьел яксвюе, ярюмнбхряъ йпюиме люкнбепнърмшл х, 
йпнле рнцн, меяйнкэйн слемэьюеряъ япедмее бпелъ пюанрш.

8.~{\sl Опнярни бшанп.\/} Юкцнпхрл~5.2.3S днбнкэмн опняр х нянаеммн 
ондундхр б яксвюе, йнцдю хлееряъ яоежхюкэмне нанпсднбюмхе дкъ ашярпнцн 
онхяйю мюхлемэьецн щкелемрю б яохяйе.

9.~{\sl Охпюлхдюкэмюъ янпрхпнбйю.\/} Юкцнпхрл~5.2.4М опх лхмхлюкэмшу 
рпеанбюмхъу оюлърх наеяоевхбюер днярюрнвмн бшянйсч яйнпнярэ янпрхпнбйх; 
йюй япедмее бпелъ пюанрш, рюй х люйяхлюкэмне бпелъ опхлепмн бдбне анкэье 
япедмецн бпелемх ашярпни янпрхпнбйх.

10.~{\sl  Якхъмхе яохяйнб.\/} Юкцнпхрл~5.2.4L нясыеярбкъер янпрхпнбйс 
яохяйнб, опх йнрнпни, рюй фе йюй х опх охпюлхдюкэмни янпрхпнбйе, 
наеяоевхбюеряъ беяэлю бшянйюъ яйнпнярэ дюфе б мюхусдьел яксвюе, йпнле 
рнцн, щрнр лернд сярнивхб он нрмньемхч й пюбмшл йкчвюл.

11.~{\sl  Онпюгпъдмюъ янпрхпнбйю я хяонкэгнбюмхел юкцнпхрлю\/} 5.2.5R---щрн 
ме врн хмне, йюй янпрхпнбйю яохяйнб, йнрнпюъ опхелкелю дкъ йкчвеи, кхан 
нвемэ йнпнрйху, кхан хлечыху менашвмши онпъднй кейяхйнцпютхвеяйнцн 
япюбмемхъ. Блеярн яяшкнй лнфмн опхлемхрэ пюяопедекъчыхи ондявер 
(осмйр~1 мюьецн нагнпю); рюйюъ опнжедспю онрпеасер опнярпюмярбю дкъ 
$2N$~гюохяеи х дкъ рюакхжш, явервхйнб, мн акюцндюпъ опнярнре бмсрпеммецн 
жхйкю нмю нянаеммн унпнью дкъ ябепуашярпшу ЩБЛ---"онфхпюрекэмхж вхяек", 
хлечыху ноепефючыее сопюбкемхе. (\emph{Опеднярепефемхе.} Онпюгпъдмсч 
янпрхпнбйс ме якедсер хяонкэгнбюрэ опх люкшу~$N$.)

12.~{\sl  Янпрхпнбйю бярюбйюлх х якхъмхел\/} (ял.~о.~5.3.1) 
мюханкее опхелкелю опх нвемэ люкшу~$N$ б "опълнкхмеимшу" 
опнцпюллюу. Мюопхлеп, щрнр лернд нйюгюкяъ аш ондундъыхл б реу 
опхкнфемхъу, цде рпеасеряъ янпрхпнбюрэ лмнцн цпсоо хг оърх хкх 
ьеярх гюохяеи.

13.  Лнцср ясыеярбнбюрэ х цхапхдмше лерндш, на╝едхмъчыхе ндхм хкх анкее хг 
опхбедеммшу бшье лернднб. Мюопхлеп, йнпнрйхе ондтюикш, бнгмхйючыхе опх 
ашярпни янпрхпнбйе, лнфмн янпрхпнбюрэ якхъмхел х бярюбйюлх.

14. Х мюйнмеж, дкъ пеюкхгюжхх аегшлъммнцн лерндю, бярперхбьецняъ б 
нрбере й соп.~5.2.1-3, рпеасеряъ, он-бхдхлнлс, йпюрвюиьюъ хг бнглнфмшу 
опнцпюлл янпрхпнбйх. Мн япедмее бпелъ пюанрш рюйни опнцпюллш 
опнонпжхнмюкэмн~$N^3$, р.~е.~щрн яюлюъ ледкеммюъ опнцпюллю янпрхпнбйх б ймхце!

Опнярпюмярбеммше х бпелеммше уюпюйрепхярхйх лмнцху хг щрху лернднб, 
гюопнцпюллхпнбюммшу дкъ \MIX, ябедемш б рюак.~1.
%%454
\picture{Рюакхжю 1, ярп. 454}
Бюфмн хлерэ б бхдс, врн вхякю б щрни рюакхже ъбкъчряъ кхьэ цпсашлх 
онйюгюрекълх нрмняхрекэмнцн бпелемх янпрхпнбйх. Нмх опхлемхлш рнкэйн й 
ндмни ЩБЛ, х опедонкнфемхъ, йюяючыхеяъ хяундмшу дюммшу, дюкейн ме дкъ бяеу 
опнцпюлл юаянкчрмн опюбнлепмш. Япюбмхрекэмше рюакхжш, онднамше щрни, 
опхбндхкхяэ бн лмнцху пюанрюу, мн ме мюидеряъ рюйху дбсу юбрнпнб,
 йнрнпше опхькх аш й ндхмюйнбшл бшбндюл! Рел ме лемее сйюгюмхъ н бпелемх 
пюанрш онгбнкъчр нжемхрэ унръ аш онпъднй яйнпнярх, йнрнпсч якедсер нфхдюрэ 
нр йюфднцн юкцнпхрлю опх янпрхпнбйе гюохяеи хг ндмнцн якнбю, рюй йюй 
\MIX---днбнкэмн рхохвмюъ люьхмю.

Ярнкаеж "опнярпюмярбн" б рюак.~1 яндепфхр мейнрнпсч хмтнплюжхч н 
йнкхвеярбе бяонлнцюрекэмни оюлърх, хяонкэгселни йюфдшл юкцнпхрлнл, б 
едхмхжюу дкхмш гюохях. Гдеяэ асйбни~$\varepsilon$ нангмювемю днкъ гюохях, 
рпеаселюъ дкъ ндмнцн онкъ ябъгх; рюй, мюопхлеп, $N(1+\varepsilon)$ 
нгмювюер, врн лернд рпеасер опнярпюмярбн дкъ $N$~гюохяеи х $N$~онкеи ябъгх.

Б юяхлорнрхвеяйху япедмху х люйяхлюкэмшу бпелемюу, яндепфюыхуяъ б 
рюак.~1, свхршбючряъ рнкэйн цкюбмше вкемш, днлхмхпсчыхе опх анкэьху~$N$ б 
опедонкнфемхх яксвюимшу хяундмшу дюммшу; $c$~нангмювюер опнхгбнкэмсч 
йнмярюмрс. Щрх тнплскш лнцср хмнцдю ббеярх б гюаксфдемхе, онщрнлс 
сйюгюмн рюйфе тюйрхвеяйне бпелъ пюанрш опнцпюллш дкъ дбсу йнмйпермшу 
онякеднбюрекэмняреи хяундмшу дюммшу. Яксвюи $N=16$, нрмняхряъ й 
ьеярмюджюрх йкчвюл, рюй вюярн онъбкъбьхляъ б опхлепюу \S~5.2, ю яксвюи 
$N=1000$ нрмняхряъ й онякеднбюрекэмнярх $K_1$, $K_2$,~\dots, $K_{1000}$, 
нопедекеммни тнплскюлх
$$
K_0=0; \quad K_{n+1}=(3141592621K_n+2113148651)\bmod 10^{10}.
$$
Дкъ онксвемхъ уюпюйрепхярхй йюфднцн юкцнпхрлю, опедярюбкеммнцн б рюакхже,
 хяонкэгнбюкюяэ бонкме "бшянйнйювеярбеммюъ" \MIX-опнцпюллю, вюярн я свернл 
сянбепьемярбнбюмхи, опедкнфеммшу б сопюфмемхъу. Пюглеп аюирю опх 
бшонкмемхх щрху опнцпюлл опхмър пюбмшл 100.

Дкъ \emph{бмеьмеи янпрхпнбйх} менаундхлш лерндш, нркхвючыхеяъ нр лернднб 
бмсрпеммеи янпрхпнбйх, онрнлс врн б щрнл яксвюе опедонкюцюеряъ 
хяонкэгнбюмхе япюбмхрекэмн опняршу ярпсйрсп дюммшу х анкэьне бмхлюмхе 
сдекъеряъ слемэьемхч бпелемх ббндю/бшбндю. Б о.~5.4.6 пюяялюрпхбючряъ 
хмрепеямше лерндш, пюгбхрше дкъ кемрнвмни янпрхпнбйх, ю б о.~5.4.9 
наясфдюеряъ хяонкэгнбюмхе дхяйнб х аюпюаюмнб.

Йнмевмн, янпрхпнбйю---ме едхмярбеммне яндепфюмхе щрни цкюбш. Оносрмн лш 
сгмюкх лмнцн н рнл, йюй пюанрюрэ ян ярпсйрспюлх дюммшу, йюй напюыюрэяъ я 
бмеьмеи оюлърэч х йюй юмюкхгхпнбюрэ юкцнпхрлш, х, мюбепмне, лш сгмюкх 
мелмнфйн х н рнл, йюй нрйпшбюрэ мнбше юкцнпхрлш.
%%456

\section Пюммхе пюгпюанрйх. Онхяй хярнвмхйю янбпелеммшу лернднб 
янпрхпнбйх бнгбпюыюер мюя б 19-е~ярнкерхе, йнцдю ашкх хгнаперемш оепбше 
люьхмш дкъ янпрхпнбйх. Б Янедхмеммшу Ьрюрюу оепеохяэ бяеу цпюфдюм 
опнбндхряъ йюфдше 10~кер, х сфе й 1880~ц. опнакелю напюанрйх нцпнлмшу он 
на╝елс дюммшу оепеохях ярюкю нвемэ нярпни; х б яюлнл деке, вхякн ндхмнйху 
(б нркхвхе нр вхякю янярнъыху б апюйе) б 1880~ц. б рюакхжюу нрясрярбсер, унръ
\picture{Пхя. 94. Рюаскърнп Унккепхрю. (Тнрнцпютхъ кчаегмн опеднярюбкемю 
юпухбнл IBM.)
}
бяъ менаундхлюъ, хмтнплюжхъ ашкю янапюмю. Цеплюм Унккепхр, дбюджюрхкермхи 
яксфюыхи Ачпн оепеохях, хгнапек нярпнслмши щкейрпхвеяйхи рюаскърнп, 
нрбевючыхи мсфдюл яанпю ярюрхярхйх, х нйнкн 100 ецн люьхм сяоеьмн 
хяонкэгнбюкхяэ опх напюанрйе яохяйнб оепеохях 1890~ц.

Мю пхя.~94 хгнапюфем оепбши юооюпюр Унккепхрю, опхбндхлши б деиярбхе нр 
юййслскърнпмшу аюрюпеи. Дкъ мюя нямнбмни хмрепея опедярюбкъер 
"янпрхпнбюкэмши ъыхй" яопюбю, йнрнпши нрйпшр я  жекэч онйюгюрэ онкнбхмс хг 
26 бмсрпеммху нрдекемхи. Ноепюрнп бярюбкъер оептнйюпрс пюглепю 
$6{5\over8}\times3{1\over4}$~дчилнб б "опеяя" х носяйюер псйнърйс; щрн 
опхбндхр й рнлс, врн гюйпеокеммше мю опсфхмюу ьршпх мю бепумеи оюмекх б реу
%%457
\bye