\input style
%% 140
ˆ’Œ€ ᝒ—…€ ‡€‚…˜€…’‘Ÿ; ’Ž’ €‹ƒŽˆ’Œ ŒŽ†Ž ›‹Ž › €‡‚€’œ 
‘Ž’ˆŽ‚ŠŽ‰ Ž‘…„‘’‚ŽŒ ……ƒˆŽ‚!

\MIX-Žƒ€ŒŒ€ „‹Ÿ €‹ƒŽˆ’Œ€ μ ˆ‚…„…€ ‚ “.~12. κ ‘Ž†€‹…ˆž, 
ŠŽ‹ˆ—…‘’‚Ž ‚‘ŽŒŽƒ€’…‹œ›• Ž…€–ˆ‰, …Ž•Ž„ˆŒ›• „‹Ÿ “€‚‹…ˆŸ 
Ž‘‹…„Ž‚€’…‹œŽ‘’œž ‘€‚…ˆ‰, ‚…‘œŒ€ ‚…‹ˆŠŽ, ’€Š —’Ž Žƒ€ŒŒ€ Œ……… 
””…Š’ˆ‚€, —…Œ „“ƒˆ… Œ…’Ž„›, ŠŽ’Ž›… Œ› €‡ˆ€‹ˆ. €ŠŽ €‹ƒŽˆ’Œ 
Ž‹€„€…’ Ž„ˆŒ ‚€†›Œ ŠŽŒ…‘ˆ“ž™ˆŒ Š€—…‘’‚ŽŒ: ‚‘… ‘€‚…ˆŸ/ŽŒ…›, 
Ž…„…‹Ÿ…Œ›… „€Ž‰ ˆ’…€–ˆ…‰ ˜€ƒ€ μη, ŒŽ†Ž ‚›Ž‹Ÿ’œ \emph{Ž„Ž‚…Œ…Ž} 
€ ύβμ ˆ‹ˆ ‹Žƒˆ—…‘Šˆ• ‘•…Œ€•, ŠŽ’Ž›… „Ž“‘Š€ž’ €€‹‹…‹œ›…
\picture{πˆ‘. 18.  γ…ŽŒ…’ˆ—…‘Š€Ÿ ˆ’……’€–ˆŸ Œ…’Ž„€ ᝒ—…€,  $N= 16$.}
‚›—ˆ‘‹…ˆŸ. ρ ’€ŠˆŒˆ €€‹‹…‹œ›Œˆ Ž…€–ˆŸŒˆ ‘Ž’ˆŽ‚Š€ ‚›Ž‹Ÿ…’‘Ÿ ‡€  
${1\over 2}\lceil \log_2  N \rceil (\lceil log_2 N \rceil + 1)$ ˜€ƒŽ‚, ˆ 
’Ž Ž„ˆ
ˆ‡ ‘€Œ›• ›‘’›• ˆ‡‚…‘’›• Ž™ˆ• Œ…’Ž„Ž‚. 퀏ˆŒ…, \emph{1024 ‹…Œ…’€ 
ŒŽ†Ž Ž’‘Ž’ˆŽ‚€’œ Œ…’Ž„ŽŒ ᝒ—…€ ‚‘…ƒŽ ‡€ 55 €€‹‹…‹œ›• ˜€ƒŽ‚}. εƒŽ 
‹ˆ†€‰˜ˆŒ ‘Ž…ˆŠŽŒ Ÿ‚‹Ÿ…’‘Ÿ Œ…’Ž„ ’’€ (‘Œ. “. 5.2.1--30), ŠŽ’Ž›‰ 
‡€’€—ˆ‚€…’ 40 ˆ‹ˆ 73 ˜€ƒ€ ‚ ‡€‚ˆ‘ˆŒŽ‘’ˆ Ž’ ’ŽƒŽ, Š€Š ‘—ˆ’€’œ: …‘‹ˆ Œ› 
ƒŽ’Ž‚› „Ž“‘’ˆ’œ ……Š›’ˆ… ‘€‚…ˆ‰ „Ž ’…• Ž, ŽŠ€ … Ž’…“…’‘Ÿ 
‚›Ž‹Ÿ’œ ……Š›‚€ž™ˆ…‘Ÿ ŽŒ…›, ’Ž „‹Ÿ ‘Ž’ˆŽ‚Šˆ 1024 ‹…Œ…’Ž‚ 
Œ…’Ž„ŽŒ ’’€ ’…“…’‘Ÿ ‚‘…ƒŽ 40 –ˆŠ‹Ž‚ ‘€‚…ˆŸ/ŽŒ…€. 䀋œ…‰˜ˆ… 
ŽŸ‘…ˆŸ ‘Œ. ‚ .~5.3.4.

\section "α›‘’€Ÿ ‘Ž’ˆŽ‚Š€". ⠌…’Ž„… ᝒ—…€ 
Ž‘‹…„Ž‚€’…‹œŽ‘’œ ‘€‚…ˆ‰ …„Ž…„…‹…€: Š€†„›‰ €‡ ‘€‚ˆ‚€ž’‘Ÿ Ž„ˆ 
ˆ ’… †… €› Š‹ž—…‰ …‡€‚ˆ‘ˆŒŽ Ž’ ’ŽƒŽ, —’Ž Œ› ŒŽƒ‹ˆ “‡€’œ Ž ”€‰‹… ˆ‡ 
…„›„“™ˆ• ‘€‚…ˆ‰. ύ’Ž “’‚…†„…ˆ… ‚ Ž‹œ˜Ž‰ Œ…… ‘€‚…„‹ˆ‚Ž ˆ 
ˆŒ…ˆ’…‹œŽ Š Œ…’Ž„“ “‡›œŠ€, •Ž’Ÿ €‹ƒŽˆ’Œ ⠈ ˆ‘Ž‹œ‡“…’ ‚ 
Žƒ€ˆ—…Ž‰ ‘’……ˆ Ž‹“—…›… ‘‚…„…ˆŸ, ‘ ’…Œ —’Ž› ‘ŽŠ€’ˆ’œ ŠŽ‹ˆ—…‘’‚Ž 
€Ž’› ‚ €‚ŽŒ ŠŽ–… ”€‰‹€. €’ˆŒ‘Ÿ ’……œ Š ‘Ž‚‘…Œ ˆŽ‰ ‘’€’…ƒˆˆ, 
ˆ ŠŽ’ŽŽ‰ ˆ‘Ž‹œ‡“…’‘Ÿ …‡“‹œ’€’ Š€†„ŽƒŽ ‘€‚…ˆŸ, —’Ž› Ž…„…‹ˆ’œ, 
Š€Šˆ… Š‹ž—ˆ ‘€‚ˆ‚€’œ ‘‹…„“ž™ˆŒˆ. ς€Š€Ÿ ‘’€’…ƒˆŸ … ƒŽ„ˆ’‘Ÿ „‹Ÿ 
€€‹‹…‹œ›• ‚›—ˆ‘‹…ˆ‰, Ž Ž€ ŒŽ†…’ ŽŠ€‡€’œ‘Ÿ ‹Ž„Ž’‚ŽŽ‰ „‹Ÿ 
‚›—ˆ‘‹ˆ’…‹œ›• Œ€˜ˆ, €Ž’€ž™ˆ• Ž‘‹…„Ž‚€’…‹œŽ.

%%141

θ’€Š, €‘‘ŒŽ’ˆŒ. ‘‹…„“ž™“ž ‘•…Œ“ ‘€‚…ˆ‰/ŽŒ…Ž‚. θŒ…ž’‘Ÿ „‚€ “Š€‡€’…‹Ÿ 
$i$ ˆ $j$, ˆ—…Œ ‚€—€‹… $i=l$, a $j=N$. ρ€‚ˆŒ $K_i:K_j$, ˆ …‘‹ˆ ŽŒ… 
… ’…“…’‘Ÿ, ’Ž “Œ…œ˜ˆŒ $j$ € …„ˆˆ–“ ˆ Ž‚’ŽˆŒ ’Ž’ Ž–…‘‘. οŽ‘‹… 
…‚ŽƒŽ ŽŒ…€ “‚…‹ˆ—ˆŒ $i$ € …„ˆˆ–“ ˆ “„…Œ Ž„Ž‹†€’œ ‘€‚…ˆŸ, 
“‚…‹ˆ—ˆ‚€Ÿ $i$, ŽŠ€ … Žˆ‡Ž‰„…’ …™… Ž„ˆ ŽŒ…. ςŽƒ„€ ŽŸ’œ “Œ…œ˜ˆŒ 
$j$ ˆ ’. „.; “„…Œ "‘†ˆƒ€’œ ‘‚…—Š“ ‘ ŽŽˆ• ŠŽ–Ž‚", ŽŠ€ … ‘’€…’ $i=j$. 
οŽ‘ŒŽ’ˆŒ, €ˆŒ…, —’Ž Žˆ‡Ž‰„…’ ‘ €˜ˆŒ ”€‰‹ŽŒ ˆ‡ ˜…‘’€„–€’ˆ —ˆ‘…‹:
{\catcode`\!=\active\def!#1 {\bf#1}
\def\inci{\noalign{\rightline{“‚…‹ˆ—ˆ’œ $i$}}}
\def\decj{\noalign{\rightline{“Œ…œ˜ˆ’œ $j$}}}
\ctable{#&&\bskip\hfill$#$\hfill\bskip\cr
䀍Ž:     &!503 & 087 & 512 & 061 & 908 & 170 & 897 & 275 & 653 & 426 & 154 & 509 & 612 & 677 & 765 &!703\cr
\decj
1-‰ ŽŒ… &!154 & 087 & 512 & 061 & 908 & 170 & 897 & 275 & 653 & 426 &!503 & 509 & 612 & 677 & 765 & 703\cr
\inci
2-‰ ŽŒ… & 154 & 087 &!503 & 061 & 908 & 170 & 897 & 275 & 653 & 426 &!512 & 509 & 612 & 677 & 765 & 703\cr
\decj
3-‰ ŽŒ… & 154 & 087 &!426 & 061 & 908 & 170 & 897 & 275 & 653 &!503 & 512 & 509 & 612 & 677 & 765 & 703\cr
\inci
4-‰ ŽŒ… & 154 & 087 & 426 & 061 &!503 & 170 & 897 & 275 & 653 &!908 & 512 & 509 & 612 & 677 & 765 & 703\cr
\decj
5-‰ ŽŒ… & 154 & 087 & 426 & 061 &!275 & 170 & 897 &!503 & 653 & 908 & 512 & 509 & 612 & 677 & 765 & 703\cr
\inci
6-‰ ŽŒ… & 154 & 087 & 426 & 061 & 275 & 170 &!503 &!897 & 653 & 808 & 512 & 509 & 612 & 677 & 765 & 703\cr
\decj
}
}
(χ’Ž› ‚›Ÿ‚ˆ’œ ‘Ž‘’ŽŸˆ… $i$ ˆ $j$, Š‹ž—ˆ $K_i$ ˆ $K_j$ €…—€’€› †ˆ›Œ 
˜ˆ”’ŽŒ.) η€Œ…’ˆŒ, —’Ž ‚ Š€†„ŽŒ ‘€‚…ˆˆ ’ŽƒŽ ˆŒ…€ “—€‘’‚“…’ Š‹ž— 
503; ‚ŽŽ™… ‚ Š€†„ŽŒ ‘€‚…ˆˆ “„…’ “—€‘’‚Ž‚€’œ ˆ‘•Ž„›‰ Š‹ž— $K_1$, 
Ž’ŽŒ“ —’Ž Ž “„…’ Ž„Ž‹†€’œ ŽŒ…ˆ‚€’œ‘Ÿ Œ…‘’€Œˆ ‘ „“ƒˆŒˆ Š‹ž—€Œˆ 
Š€†„›‰ €‡, ŠŽƒ„€ Œ› ……Š‹ž—€…Œ €€‚‹…ˆ…. κ ŒŽŒ…’“, ŠŽƒ„€ $i=j$, 
ˆ‘•Ž„€Ÿ ‡€ˆ‘œ $R_1$ ‡€‰Œ…’ ‘‚Žž ŽŠŽ—€’…‹œ“ž Ž‡ˆ–ˆž, Ž’ŽŒ“ —’Ž, Š€Š 
…’“„Ž ‚ˆ„…’œ, ‘‹…‚€  Ž’ …… … “„…’ Ž‹œ˜ˆ• Š‹ž—…‰, € ‘€‚€---Œ…œ˜ˆ•. 
θ‘•Ž„›‰ ”€‰‹ ŽŠ€†…’‘Ÿ €‡„…‹… ’€ŠˆŒ Ž€‡ŽŒ, —’Ž …‚Ž€—€‹œ€Ÿ ‡€„€—€ 
‘‚…„…’‘Ÿ Š „‚“Œ Ž‹…… Ž‘’›Œ: ‘Ž’ˆŽ‚Š… ”€‰‹€ $R_1$ \dots\ $R_{i-1}$ ˆ 
(…‡€‚ˆ‘ˆŒŽ) ‘Ž’ˆŽ‚Š… ”€‰‹€ $R_{i+1}$ \dots\ $R_N$. κ Š€†„ŽŒ“ ˆ‡ ’ˆ• 
Ž„”€‰‹Ž‚ ŒŽ†Ž ˆŒ…ˆ’œ ’Ž’ †… ‘€Œ›‰ Œ…’Ž„.

β ’€‹.~2 ŽŠ€‡€Ž, Š€Š ‚›€›‰ €Œˆ „‹Ÿ ˆŒ…Ž‚ ”€‰‹ Ž‹Ž‘’œž 
‘Ž’ˆ“…’‘Ÿ ˆ ŽŒŽ™ˆ ’ŽƒŽ Œ…’Ž„€ ‡€ 11 ‘’€„ˆ‰. β ‘ŠŽŠˆ ‡€Š‹ž—…› 
Ž„”€‰‹›, ŠŽ’Ž›… …™… …„‘’Žˆ’ Ž’‘Ž’ˆŽ‚€’œ; ‚ Œ€˜ˆ… ’ˆ Ž„”€‰‹› 
ŒŽ†Ž …„‘’€‚‹Ÿ’œ „‚“ŒŸ ……Œ…›Œˆ $l$ ˆ~$r$ (ƒ€ˆ–› €‘‘Œ€’ˆ‚€…ŒŽƒŽ ‚ 
„€›‰ ŒŽŒ…’ ”€‰‹€) ˆ ‘’…ŠŽŒ „ŽŽ‹ˆ’…‹œ›• € $(l_k, r_k)$. ꀆ„›‰ €‡, 
ŠŽƒ„€ ”€‰‹ Ž„€‡„…‹Ÿ…’‘Ÿ, Œ› ŽŒ…™€…Œ ‚ ‘’…Š \emph{Ž‹œ˜ˆ‰} ˆ‡ 
Ž„”€‰‹Ž‚ ˆ €—ˆ€…Œ Ž€€’›‚€’œ Ž‘’€‚˜ˆ‰‘Ÿ, ˆ ’€Š „Ž ’…• Ž, ŽŠ€ 
… ˆ„…Œ Š ’ˆ‚ˆ€‹œŽ ŠŽŽ’ŠˆŒ ”€‰‹€Œ; Š€Š ŽŠ€‡€Ž ‚ “.~20, ’€Š€Ÿ 
Ž–…„“€ ƒ€€’ˆ“…’, —’Ž ‚ ‘’…Š… ˆŠŽƒ„€ … “„…’ €•Ž„ˆ’œ‘Ÿ Ž‹……, —…Œ 
ˆŒ…Ž $\log_2 N$ ‹…Œ…’Ž‚.
%% 142
\bye