НИЖНЯЯ И ВЕРХНЯЯ ОЦЕНКИ ПОРЯДКА АФФИННОСТИ ПРЕОБРАЗОВАНИЙ ПРОСТРАНСТВ БУЛЕВЫХ ВЕКТОРОВ

  • Published on
    05-Apr-2017

  • View
    214

  • Download
    2

Embed Size (px)

Transcript

<ul><li><p>2013</p><p> 2(20)</p><p> 510.52 </p><p>.. , . . </p><p> , , . , , . , </p><p>E-mail: spg54@bk.ru</p><p> - n- . .</p><p> : , , .</p><p> :N ;Vn n- , n N;n Vn Vn;0n = (0, . . . , 0 </p><p>n</p><p>)T ;</p><p>bcc c, g(n), h(n) n N</p><p> n0 N, n &gt; n0 g(n) &lt; h(n), </p><p>g(n)</p></li><li><p> 15</p><p> {f1, . . . , fn} F . (1) - </p><p>F (x) = , (2)</p><p> x = (x1, . . . , xn), =</p><p>1. . .n</p><p>. A1, . . . , AardF , F . (1)</p><p>( (2)) -:</p><p>Ai(x) = , i = 1, . . . , ardF,</p><p> (2). , ardF .</p><p> .</p><p>ardn = maxFn</p><p>ardF.</p><p> ardn n. ardn (2).</p><p> 1. n &gt; 2 </p><p>ardn &gt;2n</p><p>n2.</p><p>. , Vn Vn 2n(n+1). </p><p>A1, . . . , A2n(n+1) (3)</p><p> n. u ardn. F n Vn M1, . . . ,Mk,k 6 u, Ai1 , . . . , Aik , , Aij F Mj,j {1, . . . , k}. , Ml , , Ai1 , . . . , Aik u .</p><p> h n, - u :</p><p>h 6</p><p>(2n(n+1)</p><p>u</p><p>) u2n . (4)</p><p> (4) , Ai1 , . . . , Aiu (3). Ai1 , . . . , Aiu , u2n F n, F (), Vn, u .</p><p> , h &lt; 2un(n+1) u2n . (5)</p><p> (5) 2, </p><p>log2 h &lt; un(n+ 1) + 2n log2 u. (6)</p></li><li><p>16 .. , . . </p><p>, </p><p>ardn 62n</p><p>n2.</p><p> (6) , </p><p>log2 h &lt; 2n</p><p>(n+</p><p>n(n+ 1)</p><p>n2 2 log2 n</p><p>). (7)</p><p> n &gt; 2 (7) </p><p>log2 h &lt; n 2n. (8)</p><p> u n, h = |n| = 2n2n ,</p><p>log2 h = n 2n. (9)</p><p> (8) (9) , ardn &gt;2n</p><p>n2.</p><p> ardn. - .</p><p> , . 1. {((1), (1)), . . . , ((m), (m))} Vn, </p><p>m 6 n, {(1), . . . , (m)} . - L n, , </p><p>L((i)) = (i), i = 1, . . . ,m.</p><p> 2. M Vn, |M | &gt; 2k, k {0, . . . , n 1}, M. M k + 1 .</p><p>. , (, ) t &lt; k+ 1 . (1), . . . , (t). M - (1), . . . , (t), M = M \ {0n}. , M M , |M | &gt; 2k. , |M | = 2t1 6 2k1 &lt; 2k. .</p><p> 2. n &gt; 2 :</p><p>ardn 62n</p><p>n</p><p>n1i=1</p><p>2i nn i</p><p>.</p><p>. F , n. F : Vn ( r). ( {(1)1 , . . . , </p><p>(1)n }) F </p><p> , F (0n). 1, </p><p>L n, L((1)i ) = F ((1)i ) F (0n), i = 1, . . . , n. </p></li><li><p> 17</p><p>L(x) F (0n) F {(1)1 , . . . , </p><p>(1)n , 0n}. </p><p>r1 , 1, F - . , ardn 6 r.</p><p> r. Vn \{0n}, n &gt; 1, </p><p>Vn \ {0n} = 2n 1 &gt; 2n1. 2, Vn \ {0n} n (1)1 , . . . , </p><p>(1)n . </p><p> M = Vn \ {(1)1 , . . . , (1)n , 0n} |M | &gt; 2n1, </p><p> n (2)1 , . . . , (2)n , , </p><p> M = Vn \ ({(1)1 , . . . , (1)n , 0n} {</p><p>(2)1 , . . . , </p><p>(2)n } . . . {(rn1)1 , . . . , </p><p>(rn1)n })</p><p> |M | &lt; 2n1. rn1 n , rn1 , </p><p>rn1 =2n 1 (2n1 qn1)</p><p>n=</p><p>2n1 1 + qn1n</p><p>,</p><p> qn1 = n, (2n1 1)/n; qn1 {1, . . . , n 1} , (2n1 1 ++qn1)/n , (2n1 1)/n.</p><p> n 1 . </p><p>rn2 =2n1 qn1 (2n2 qn2)</p><p>n 1=</p><p>2n2 qn1 + qn2n 1</p><p>,</p><p> qn2 {1, . . . , n 1}, . , </p><p>ri =2i+1 qi+1 (2i qi)</p><p>i+ 1=</p><p>2i qi+1 + qii+ 1</p><p> i+ 1 , qi {1, . . . , i+ 1}, i 0, . . . , n 2. </p><p>r = rn1 + rn2 + . . .+ r0 =2n1 1 + qn1</p><p>n+</p><p>2n2 qn1 + qn2n 1</p><p>+ rn3 + . . .+ r0 =</p><p>=1</p><p>n 1</p><p>(n 1n</p><p>(2n1 1 + qn1) + 2n2 qn1 + qn2)</p><p>+ rn3 + . . .+ r0 =</p><p>=1</p><p>n 1</p><p>(2n1 2</p><p>n1</p><p>n+ 2n2 + qn2 </p><p>(qn1n</p><p>+n 1n</p><p>))+ rn3 + . . .+ r0 6</p><p>62n1</p><p>n 1+</p><p>2n2 1 + qn2n 1</p><p>+ rn3 + rn4 + . . .+ r0 =</p><p>=2n1</p><p>n 1+</p><p>(2n2 1 + qn2</p><p>n 1+</p><p>2n3 qn2 + qn3n 2</p><p>)+ rn4 + . . .+ r0 6</p><p>62n1</p><p>n 1+</p><p>2n2</p><p>n 2+</p><p>(2n3 1 + qn3</p><p>n 2+</p><p>2n4 qn3 + qn4n 3</p><p>)+ rn5 + . . .+ r0 6</p><p>62n1</p><p>n 1+</p><p>2n2</p><p>n 2+ . . .+</p><p>22</p><p>2+</p><p>(21 1 + q1</p><p>2+</p><p>20 q1 + q01</p><p>)=</p><p>=2n1</p><p>n 1+</p><p>2n2</p><p>n 2+ . . .+</p><p>22</p><p>2+</p><p>21</p><p>1=</p><p>2n</p><p>n</p><p>(21</p><p>n</p><p>n 1+ 22</p><p>n</p><p>n 2+ . . .+ 2(n1)</p><p>n</p><p>1</p><p>).</p><p> .</p></li><li><p>18 .. , . . </p><p> 3. </p><p>limn</p><p>n1i=1</p><p>2in</p><p>n i= 1.</p><p>. :</p><p>n1i=1</p><p>2in</p><p>n i=b3 log2 nci=1</p><p>2in</p><p>n i+</p><p>n1i=b3 log2 nc+1</p><p>2in</p><p>n i. (10)</p><p> (10) S1, S2. , </p><p>b3 log2 nci=1</p><p>2i &lt; S1</p></li></ul>

Recommended

View more >