Эффективные алгоритмы, осень 2007: Приближённые алгоритмы

  • Published on
    14-Apr-2017

  • View
    89

  • Download
    3

Embed Size (px)

Transcript

<ul><li><p>/ 4: </p><p>. </p><p>Computer Science http://logic.pdmi.ras.ru/infclub/</p><p>. (CS ) 4. 1 / 25</p><p>http://logic.pdmi.ras.ru/~infclub/</p></li><li><p>1 </p><p>2 </p><p>. (CS ) 4. 2 / 25</p></li><li><p>1 </p><p>2 </p><p>. (CS ) 4. 2 / 25</p></li><li><p>1 </p><p>2 </p><p>. (CS ) 4. 3 / 25</p></li><li><p> (vertex cover problem) , .</p><p> 2- . 2- ., 2-, , .</p><p>. (CS ) 4. 4 / 25</p></li><li><p> (vertex cover problem) , .</p><p> 2- . 2- ., 2-, , .</p><p>. (CS ) 4. 4 / 25</p></li><li><p> (vertex cover problem) , .</p><p> 2- .</p><p> 2- ., 2-, , .</p><p>. (CS ) 4. 4 / 25</p></li><li><p> (vertex cover problem) , .</p><p> 2- . 2- .</p><p>, 2-, , .</p><p>. (CS ) 4. 4 / 25</p></li><li><p> (vertex cover problem) , .</p><p> 2- . 2- ., 2-, , .</p><p>. (CS ) 4. 4 / 25</p></li><li><p>Rand-Approx-Vertex-Cover(G )</p><p>C = , C C</p><p> Rand-Approx-Vertex-Cover 2-.</p><p>. (CS ) 4. 5 / 25</p></li><li><p>Rand-Approx-Vertex-Cover(G )</p><p>C = </p><p> , C C</p><p> Rand-Approx-Vertex-Cover 2-.</p><p>. (CS ) 4. 5 / 25</p></li><li><p>Rand-Approx-Vertex-Cover(G )</p><p>C = , C</p><p> C</p><p> Rand-Approx-Vertex-Cover 2-.</p><p>. (CS ) 4. 5 / 25</p></li><li><p>Rand-Approx-Vertex-Cover(G )</p><p>C = , C C</p><p> Rand-Approx-Vertex-Cover 2-.</p><p>. (CS ) 4. 5 / 25</p></li><li><p>Rand-Approx-Vertex-Cover(G )</p><p>C = , C C</p><p> Rand-Approx-Vertex-Cover 2-.</p><p>. (CS ) 4. 5 / 25</p></li><li><p> Copt . , , Copt., C Copt 1/2. ., |Copt| ., . ( |C |) 2|Copt|.</p><p>. (CS ) 4. 6 / 25</p></li><li><p> Copt .</p><p> , , Copt., C Copt 1/2. ., |Copt| ., . ( |C |) 2|Copt|.</p><p>. (CS ) 4. 6 / 25</p></li><li><p> Copt . , , Copt.</p><p>, C Copt 1/2. ., |Copt| ., . ( |C |) 2|Copt|.</p><p>. (CS ) 4. 6 / 25</p></li><li><p> Copt . , , Copt., C Copt 1/2.</p><p> ., |Copt| ., . ( |C |) 2|Copt|.</p><p>. (CS ) 4. 6 / 25</p></li><li><p> Copt . , , Copt., C Copt 1/2. .</p><p>, |Copt| ., . ( |C |) 2|Copt|.</p><p>. (CS ) 4. 6 / 25</p></li><li><p> Copt . , , Copt., C Copt 1/2. ., |Copt| .</p><p>, . ( |C |) 2|Copt|.</p><p>. (CS ) 4. 6 / 25</p></li><li><p> Copt . , , Copt., C Copt 1/2. ., |Copt| ., . ( |C |) 2|Copt|.</p><p>. (CS ) 4. 6 / 25</p></li><li><p> G = (V ,E ), v w(v). .</p><p> 2- , : (u, v) ,</p><p> 1w(u)(</p><p>1w(u) +</p><p>1w(v)</p><p>)1 </p><p> u, 1w(v)(</p><p>1w(u) +</p><p>1w(v)</p><p>)1 v .</p><p>. (CS ) 4. 7 / 25</p></li><li><p> G = (V ,E ), v w(v).</p><p> .</p><p> 2- , : (u, v) ,</p><p> 1w(u)(</p><p>1w(u) +</p><p>1w(v)</p><p>)1 </p><p> u, 1w(v)(</p><p>1w(u) +</p><p>1w(v)</p><p>)1 v .</p><p>. (CS ) 4. 7 / 25</p></li><li><p> G = (V ,E ), v w(v). .</p><p> 2- , : (u, v) ,</p><p> 1w(u)(</p><p>1w(u) +</p><p>1w(v)</p><p>)1 </p><p> u, 1w(v)(</p><p>1w(u) +</p><p>1w(v)</p><p>)1 v .</p><p>. (CS ) 4. 7 / 25</p></li><li><p> G = (V ,E ), v w(v). .</p><p> 2- , : (u, v) ,</p><p> 1w(u)(</p><p>1w(u) +</p><p>1w(v)</p><p>)1 </p><p> u, 1w(v)(</p><p>1w(u) +</p><p>1w(v)</p><p>)1 v .</p><p>. (CS ) 4. 7 / 25</p></li><li><p> G = (V ,E ), v w(v). .</p><p> 2- , : (u, v) ,</p><p> 1w(u)(</p><p>1w(u) +</p><p>1w(v)</p><p>)1 </p><p> u, 1w(v)(</p><p>1w(u) +</p><p>1w(v)</p><p>)1 v .</p><p>. (CS ) 4. 7 / 25</p></li><li><p>minvV</p><p>w(v)x(v)</p><p>x(v1) + x(v2) 1, (v1, v2) E</p><p>x(v) {0, 1}, v V</p><p>. (CS ) 4. 8 / 25</p></li><li><p> x(v) {0, 1} x(v) 0 . {x(v)}vV . :</p><p>x(v) =</p><p>{1, x(v) 1/20, </p><p> C = {v V |x(v) = 1}. ( ), (u, v) x(u) + x(v) 1, , x(u) 1/2 x(v) 1/2.w(C ) =</p><p>vV w(v)x(v) 2</p><p>vV w(v)x(v) 2w(Copt).</p><p>. (CS ) 4. 9 / 25</p></li><li><p> x(v) {0, 1} x(v) 0 .</p><p> {x(v)}vV . :</p><p>x(v) =</p><p>{1, x(v) 1/20, </p><p> C = {v V |x(v) = 1}. ( ), (u, v) x(u) + x(v) 1, , x(u) 1/2 x(v) 1/2.w(C ) =</p><p>vV w(v)x(v) 2</p><p>vV w(v)x(v) 2w(Copt).</p><p>. (CS ) 4. 9 / 25</p></li><li><p> x(v) {0, 1} x(v) 0 . {x(v)}vV .</p><p> :</p><p>x(v) =</p><p>{1, x(v) 1/20, </p><p> C = {v V |x(v) = 1}. ( ), (u, v) x(u) + x(v) 1, , x(u) 1/2 x(v) 1/2.w(C ) =</p><p>vV w(v)x(v) 2</p><p>vV w(v)x(v) 2w(Copt).</p><p>. (CS ) 4. 9 / 25</p></li><li><p> x(v) {0, 1} x(v) 0 . {x(v)}vV . :</p><p>x(v) =</p><p>{1, x(v) 1/20, </p><p> C = {v V |x(v) = 1}. ( ), (u, v) x(u) + x(v) 1, , x(u) 1/2 x(v) 1/2.w(C ) =</p><p>vV w(v)x(v) 2</p><p>vV w(v)x(v) 2w(Copt).</p><p>. (CS ) 4. 9 / 25</p></li><li><p> x(v) {0, 1} x(v) 0 . {x(v)}vV . :</p><p>x(v) =</p><p>{1, x(v) 1/20, </p><p> C = {v V |x(v) = 1}.</p><p> ( ), (u, v) x(u) + x(v) 1, , x(u) 1/2 x(v) 1/2.w(C ) =</p><p>vV w(v)x(v) 2</p><p>vV w(v)x(v) 2w(Copt).</p><p>. (CS ) 4. 9 / 25</p></li><li><p> x(v) {0, 1} x(v) 0 . {x(v)}vV . :</p><p>x(v) =</p><p>{1, x(v) 1/20, </p><p> C = {v V |x(v) = 1}. ( ), (u, v) x(u) + x(v) 1, , x(u) 1/2 x(v) 1/2.</p><p>w(C ) =</p><p>vV w(v)x(v) 2</p><p>vV w(v)x(v) 2w(Copt).</p><p>. (CS ) 4. 9 / 25</p></li><li><p> x(v) {0, 1} x(v) 0 . {x(v)}vV . :</p><p>x(v) =</p><p>{1, x(v) 1/20, </p><p> C = {v V |x(v) = 1}. ( ), (u, v) x(u) + x(v) 1, , x(u) 1/2 x(v) 1/2.w(C ) =</p><p>vV w(v)x(v) 2</p><p>vV w(v)x(v) 2w(Copt).</p><p>. (CS ) 4. 9 / 25</p></li><li><p>Weighted-Vertex-Cover-1(G , w)</p><p>C = (v1, v2), w(v1) &gt; 0 w(v2) &gt; 0, :</p><p>I = min{w(v1),w(v2)}I w(v1) = w(v1) I w(v2) = w(v2) </p><p> 0</p><p>. (CS ) 4. 10 / 25</p></li><li><p>Weighted-Vertex-Cover-1(G , w)</p><p>C = </p><p> (v1, v2), w(v1) &gt; 0 w(v2) &gt; 0, :</p><p>I = min{w(v1),w(v2)}I w(v1) = w(v1) I w(v2) = w(v2) </p><p> 0</p><p>. (CS ) 4. 10 / 25</p></li><li><p>Weighted-Vertex-Cover-1(G , w)</p><p>C = (v1, v2), w(v1) &gt; 0 w(v2) &gt; 0, :</p><p>I = min{w(v1),w(v2)}I w(v1) = w(v1) I w(v2) = w(v2) </p><p> 0</p><p>. (CS ) 4. 10 / 25</p></li><li><p>Weighted-Vertex-Cover-1(G , w)</p><p>C = (v1, v2), w(v1) &gt; 0 w(v2) &gt; 0, :</p><p>I = min{w(v1),w(v2)}</p><p>I w(v1) = w(v1) I w(v2) = w(v2) </p><p> 0</p><p>. (CS ) 4. 10 / 25</p></li><li><p>Weighted-Vertex-Cover-1(G , w)</p><p>C = (v1, v2), w(v1) &gt; 0 w(v2) &gt; 0, :</p><p>I = min{w(v1),w(v2)}I w(v1) = w(v1) </p><p>I w(v2) = w(v2) 0</p><p>. (CS ) 4. 10 / 25</p></li><li><p>Weighted-Vertex-Cover-1(G , w)</p><p>C = (v1, v2), w(v1) &gt; 0 w(v2) &gt; 0, :</p><p>I = min{w(v1),w(v2)}I w(v1) = w(v1) I w(v2) = w(v2) </p><p> 0</p><p>. (CS ) 4. 10 / 25</p></li><li><p>Weighted-Vertex-Cover-1(G , w)</p><p>C = (v1, v2), w(v1) &gt; 0 w(v2) &gt; 0, :</p><p>I = min{w(v1),w(v2)}I w(v1) = w(v1) I w(v2) = w(v2) </p><p> 0</p><p>. (CS ) 4. 10 / 25</p></li><li><p>Weighted-Vertex-Cover-2(G , w)</p><p> (v1, v2) E w(v1) = 0, w(v2) = 0, 0 , w(v1) &gt; 0 w(v2) &gt; 0 :</p><p>(v) =</p><p>{min{w(v1),w(v2)}, v {v1, v2}0, </p><p> Weighted-Vertex-Cover-2(G , w )</p><p>. (CS ) 4. 11 / 25</p></li><li><p>Weighted-Vertex-Cover-2(G , w)</p><p> (v1, v2) E w(v1) = 0, w(v2) = 0, 0</p><p> , w(v1) &gt; 0 w(v2) &gt; 0 :</p><p>(v) =</p><p>{min{w(v1),w(v2)}, v {v1, v2}0, </p><p> Weighted-Vertex-Cover-2(G , w )</p><p>. (CS ) 4. 11 / 25</p></li><li><p>Weighted-Vertex-Cover-2(G , w)</p><p> (v1, v2) E w(v1) = 0, w(v2) = 0, 0 , w(v1) &gt; 0 w(v2) &gt; 0</p><p> :</p><p>(v) =</p><p>{min{w(v1),w(v2)}, v {v1, v2}0, </p><p> Weighted-Vertex-Cover-2(G , w )</p><p>. (CS ) 4. 11 / 25</p></li><li><p>Weighted-Vertex-Cover-2(G , w)</p><p> (v1, v2) E w(v1) = 0, w(v2) = 0, 0 , w(v1) &gt; 0 w(v2) &gt; 0 :</p><p>(v) =</p><p>{min{w(v1),w(v2)}, v {v1, v2}0, </p><p> Weighted-Vertex-Cover-2(G , w )</p><p>. (CS ) 4. 11 / 25</p></li><li><p>Weighted-Vertex-Cover-2(G , w)</p><p> (v1, v2) E w(v1) = 0, w(v2) = 0, 0 , w(v1) &gt; 0 w(v2) &gt; 0 :</p><p>(v) =</p><p>{min{w(v1),w(v2)}, v {v1, v2}0, </p><p> Weighted-Vertex-Cover-2(G , w )</p><p>. (CS ) 4. 11 / 25</p></li><li><p> Weighted-Vertex-Cover-2 2-.</p><p> OPT(w), OPT(w ), OPT() w , w , , , Copt, Cwopt , C opt .</p><p>w(Copt) = (w )(Copt) + (Copt) (w )(Cwoptw) + (Copt)</p><p>OPT(w) OPT(w ) + OPT() </p><p>vV w(v).</p><p> 0, .</p><p>. (CS ) 4. 12 / 25</p></li><li><p> Weighted-Vertex-Cover-2 2-.</p><p> OPT(w), OPT(w ), OPT() w , w , , , Copt, Cwopt , C opt .</p><p>w(Copt) = (w )(Copt) + (Copt) (w )(Cwoptw) + (Copt)</p><p>OPT(w) OPT(w ) + OPT() </p><p>vV w(v).</p><p> 0, .</p><p>. (CS ) 4. 12 / 25</p></li><li><p> Weighted-Vertex-Cover-2 2-.</p><p> OPT(w), OPT(w ), OPT() w , w , , , Copt, Cwopt , C opt .</p><p>w(Copt) = (w )(Copt) + (Copt) (w )(Cwoptw) + (Copt)</p><p>OPT(w) OPT(w ) + OPT() </p><p>vV w(v).</p><p> 0, .</p><p>. (CS ) 4. 12 / 25</p></li><li><p> Weighted-Vertex-Cover-2 2-.</p><p> OPT(w), OPT(w ), OPT() w , w , , , Copt, Cwopt , C opt .</p><p>w(Copt) = (w )(Copt) + (Copt) (w )(Cwoptw) + (Copt)</p><p>OPT(w) OPT(w ) + OPT() </p><p>vV w(v).</p><p> 0, .</p><p>. (CS ) 4. 12 / 25</p></li><li><p> Weighted-Vertex-Cover-2 2-.</p><p> OPT(w), OPT(w ), OPT() w , w , , , Copt, Cwopt , C opt .</p><p>w(Copt) = (w )(Copt) + (Copt) (w )(Cwoptw) + (Copt)</p><p>OPT(w) OPT(w ) + OPT()</p><p>vV w(v). 0, .</p><p>. (CS ) 4. 12 / 25</p></li><li><p> Weighted-Vertex-Cover-2 2-.</p><p> OPT(w), OPT(w ), OPT() w , w , , , Copt, Cwopt , C opt .</p><p>w(Copt) = (w )(Copt) + (Copt) (w )(Cwoptw) + (Copt)</p><p>OPT(w) OPT(w ) + OPT() </p><p>vV w(v).</p><p> 0, .</p><p>. (CS ) 4. 12 / 25</p></li><li><p> Weighted-Vertex-Cover-2 2-.</p><p> OPT(w), OPT(w ), OPT() w , w , , , Copt, Cwopt , C opt .</p><p>w(Copt) = (w )(Copt) + (Copt) (w )(Cwoptw) + (Copt)</p><p>OPT(w) OPT(w ) + OPT() </p><p>vV w(v).</p><p> 0, .</p><p>. (CS ) 4. 12 / 25</p></li><li><p> ()</p><p> w . , (w )(C ) 2OPT(w ). (C ) 2min{w(v1),w(v2)} 2OPT(). , w(C ) 2(OPT(w ) + OPT()) 2OPT (w).</p><p>. (CS ) 4. 13 / 25</p></li><li><p> ()</p><p> w .</p><p> , (w )(C ) 2OPT(w ). (C ) 2min{w(v1),w(v2)} 2OPT(). , w(C ) 2(OPT(w ) + OPT()) 2OPT (w).</p><p>. (CS ) 4. 13 / 25</p></li><li><p> ()</p><p> w . , (w )(C ) 2OPT(w ).</p><p> (C ) 2min{w(v1),w(v2)} 2OPT(). , w(C ) 2(OPT(w ) + OPT()) 2OPT (w).</p><p>. (CS ) 4. 13 / 25</p></li><li><p> ()</p><p> w . , (w )(C ) 2OPT(w ). (C ) 2min{w(v1),w(v2)} 2OPT().</p><p> , w(C ) 2(OPT(w ) + OPT()) 2OPT (w).</p><p>. (CS ) 4. 13 / 25</p></li><li><p> ()</p><p> w . , (w )(C ) 2OPT(w ). (C ) 2min{w(v1),w(v2)} 2OPT(). , w(C ) 2(OPT(w ) + OPT()) 2OPT (w).</p><p>. (CS ) 4. 13 / 25</p></li><li><p>minvV</p><p>w(v)x(v)</p><p>x(v1) + x(v2) 1, (v1, v2) E</p><p>x(v) 0, v V</p><p>maxeE</p><p>y(e)</p><p>e:ve</p><p>y(e) w(v), v V</p><p>y(e) 0, e E</p><p> , w(Copt) </p><p>eE y(e), y .</p><p>. (CS ) 4. 14 / 25</p></li><li><p> y(e) = 0 e E e = (v1, v2), y(e) , y(e), (</p><p>e:ve w(v)) C , , </p><p>, w(C ) =</p><p>vC w(v) =</p><p>vC</p><p>e:ve y(e) 2</p><p>eE y(e) </p><p>2w(Copt)</p><p>. (CS ) 4. 15 / 25</p></li><li><p> y(e) = 0 e E</p><p> e = (v1, v2), y(e) , y(e), (</p><p>e:ve w(v)) C , , </p><p>, w(C ) =</p><p>vC w(v) =</p><p>vC</p><p>e:ve y(e) 2</p><p>eE y(e) </p><p>2w(Copt)</p><p>. (CS ) 4. 15 / 25</p></li><li><p> y(e) = 0 e E e = (v1, v2), y(e) , y(e), (</p><p>e:ve w(v)) </p><p> C , , </p><p>, w(C ) =</p><p>vC w(v) =</p><p>vC</p><p>e:ve y(e) 2</p><p>eE y(e) </p><p>2w(Copt)</p><p>. (CS ) 4. 15 / 25</p></li><li><p> y(e) = 0 e E e = (v1, v2), y(e) , y(e), (</p><p>e:ve w(v)) C , , </p><p>, w(C ) =</p><p>vC w(v) =</p><p>vC</p><p>e:ve y(e) 2</p><p>eE y(e) </p><p>2w(Copt)</p><p>. (CS ) 4. 15 / 25</p></li><li><p> y(e) = 0 e E e = (v1, v2), y(e) , y(e), (</p><p>e:ve w(v)) C , , </p><p>, </p><p>w(C ) =</p><p>vC w(v) =</p><p>vC</p><p>e:ve y(e) 2</p><p>eE y(e) 2w(Copt)</p><p>. (CS ) 4. 15 / 25</p></li><li><p> y(e) = 0 e E e = (v1, v2), y(e) , y(e), (</p><p>e:ve w(v)) C , , </p><p>, w(C ) =</p><p>vC w(v) =</p><p>vC</p><p>e:ve y(e) 2</p><p>eE y(e) </p><p>2w(Copt)</p><p>. (CS ) 4. 15 / 25</p></li><li><p>1 </p><p>2 </p><p>. (CS ) 4. 16 / 25</p></li><li><p> (hitting set problem) X = {x1, . . . , xm} S1, . . . , Sn X C X , C Si = i .</p><p>NP-NP- .</p><p>. (CS ) 4. 17 / 25</p></li><li><p> (hitting set problem) X = {x1, . . . , xm} S1, . . . , Sn X C X , C Si = i .</p><p>NP-NP- .</p><p>. (CS ) 4. 17 / 25</p></li><li><p> (set cover problem) U = {u1, . . . , un} S1, . . . , Sm, U, , U .</p><p>. (CS ) 4. 18 / 25</p></li><li><p> :</p><p>I x1, . . . , xm, S1, . . . ,Sn;I xi Sj , xi Sj .</p><p> , . ( , ).</p><p>. (CS ) 4. 19 / 25</p></li><li><p> :</p><p>I x1, . . . , xm, S1, . . . ,Sn;I xi Sj , xi Sj .</p><p> , . ( , ).</p><p>. (CS ) 4. 19 / 25</p></li><li><p> :</p><p>I x1, . . . , xm, S1, . . . ,Sn;</p><p>I xi Sj , xi Sj . , . ( , ).</p><p>. (CS ) 4. 19 / 25</p></li><li><p> :</p><p>I x1, . . . , xm, S1, . . . ,Sn;I xi Sj , xi Sj .</p><p> , . ( , ).</p><p>. (CS ) 4. 19 / 25</p></li><li><p> :</p><p>I x1, . . . , xm, S1, . . . ,Sn;I xi Sj , xi Sj .</p><p> , .</p><p> ( , ).</p><p>. (CS ) 4. 19 / 25</p></li><li><p> :</p><p>I x1, . . . , xm, S1, . . . ,Sn;I xi Sj , xi Sj .</p><p> , . ( , ).</p><p>. (CS ) 4. 19 / 25</p></li><li><p> . xi = 1, xi C , xi = 0 . :</p><p>minmi=1</p><p>xi</p><p>iSj</p><p>xi 1, 1 j n</p><p>xi {0, 1}, 1 i m</p><p>. (CS ) 4. 20 / 25</p></li><li><p> .</p><p> xi = 1, xi C , xi = 0 . :</p><p>minmi=1</p><p>xi</p><p>iSj</p><p>xi 1, 1 j n</p><p>xi {0, 1}, 1 i m</p><p>. (CS ) 4. 20 / 25</p></li><li><p> . xi = 1, xi C , xi = 0 .</p><p> :</p><p>minmi=1</p><p>xi</p><p>iSj</p><p>xi 1, 1 j n</p><p>xi {0, 1}, 1 i m</p><p>. (CS ) 4. 20 / 25</p></li><li><p> . xi = 1, xi C , xi = 0 . :</p><p>minmi=1</p><p>xi</p><p>iSj</p><p>xi 1, 1 j n</p><p>xi {0, 1}, 1 i m</p><p>. (CS ) 4. 20 / 25</p></li><li><p>, x1, . . . , xn , C = {i |xi = 1} . xi {0, 1} 0 xi 1 . x1, . . . , xm ., </p><p>mi=1 xi </p><p> Copt. : xi 1 xi . C = {i |xi = 1}.</p><p>. (CS ) 4. 21 / 25</p></li><li><p>, x1, . . . , xn , C = {i |xi = 1} .</p><p> xi {0, 1} 0 xi 1 . x1, . . . , xm ., </p><p>mi=1 xi </p><p> Copt. : xi 1 xi . C = {i |xi = 1}.</p><p>. (CS ) 4. 21 / 25</p></li><li><p>, x1, . . . , xn , C = {i |xi = 1} . xi {0, 1} 0 xi 1 .</p><p> x1, . . . , xm ., </p><p>mi=1 xi </p><p> Copt. : xi 1 xi . C = {i |xi = 1}.</p><p>. (CS ) 4. 21 / 25</p></li><li><p>, x1, . . . , xn , C = {i |xi = 1} . xi {0, 1} 0 xi 1 . x1, . . . , xm .</p><p>, m</p><p>i=1 xi Copt. : xi 1 xi . C = {i |xi = 1}.</p><p>. (CS ) 4. 21 / 25</p></li><li><p>, x1, . . . , xn , C = {i |xi = 1} . xi {0, 1} 0 xi 1 . x1, . . . , xm ., </p><p>mi=1 xi </p><p> Copt.</p><p> : xi 1 xi . C = {i |xi = 1}.</p><p>. (CS ) 4. 21 / 25</p></li><li><p>, x1, . . . , xn , C = {i |xi = 1} . xi {0, 1} 0 xi 1 . x1, . . . , xm ., </p><p>mi=1 xi </p><p> Copt. : xi 1 xi .</p><p> C = {i |xi = 1}.</p><p>. (CS ) 4. 21 / 25</p></li><li><p>, x1, . . . , xn , C = {i |xi = 1} . xi {0, 1} 0 xi 1 . x1, . . . , xm ., </p><p>mi=1 xi </p><p> Copt. : xi 1 xi . C = {i |xi = 1}.</p><p>. (CS ) 4. 21 / 25</p></li><li><p>, C ( - Sj). , C Sj = . |Sj | = k . , </p><p>iSj xi 1.</p><p>Pr(CSj = ) =iSj</p><p>(1xi ) </p><p>(iSj (1 xi )</p><p>k</p><p>)k (11/k)k &lt; e1</p><p>. (CS ) 4. 22 / 25</p></li><li><p> , C ( - Sj).</p><p> , C Sj = . |Sj | = k . , </p><p>iSj xi 1.</p><p>Pr(CSj = ) =iSj</p><p>(1xi ) </p><p>(iSj (1 xi )</p><p>k</p><p>)k (11/k)k &lt; e1</p><p>. (CS ) 4. 22 / 25</p></li><li><p> , C ( - Sj). , C Sj = .</p><p> |Sj | = k . , </p><p>iSj xi 1.</p><p>Pr(CSj = ) =iSj</p><p>(1xi ) </p><p>(iSj (1 xi )</p><p>k</p><p>)k (11/k)k &lt; e1</p><p>. (CS ) 4. 22 / 25</p></li><li><p> , C ( - Sj). , C Sj = . |Sj | = k .</p><p> , </p><p>iSj xi 1.</p><p>Pr(CSj = ) =iSj</p><p>(1xi ) </p><p>(iSj (1 xi )</p><p>k</p><p>)k (11/k)k &lt; e1</p><p>. (CS ) 4. 22 / 25</p></li><li><p> , C ( - Sj). , C Sj = . |Sj | = k . , </p><p>iSj xi 1.</p><p>Pr(CSj = ) =iSj</p><p>(1xi ) </p><p>(iSj (1 xi )</p><p>k</p><p>)k (11/k)k &lt; e1</p><p>. (CS ) 4. 22 / 25</p></li><li><p> , C ( - Sj). , C Sj = . |Sj | = k . , </p><p>iSj xi 1.</p><p>Pr(CSj = ) =iSj</p><p>(1xi ) </p><p>(iSj (1 xi )</p><p>k</p><p>)k (11/k)k &lt; e1</p><p>. (CS ) 4. 22 / 25</p></li><li><p> t = log(2n) C , , C Sj , (e1)log(2n) = 1/2n., 1/2 . t = log(2n) C xi 1 1 (1 xi )t .. C </p><p>mi=1 xi Copt.</p><p> , . log n .</p><p>. (CS ) 4. 23 / 25</p></li><li><p> t = log(2n) C , , C Sj , (e1)log(2n) = 1/2n.</p><p>, 1/2 . t = log(2n) C xi 1 1 (1 xi )t .. C </p><p>mi=1 xi Copt.</p><p> , . log n .</p><p>. (CS ) 4. 23 / 25</p></li><li><p> t = log(2n) C , , C Sj , (e1)log(2n) = 1/2n., 1/2 .</p><p> t = log(2n) C xi 1 1 (1 xi )t .. C </p><p>mi=1 xi Copt.</p><p> , . log n .</p><p>. (CS ) 4. 23 / 25</p></li><li><p> t = log(2n) C , , C Sj , (e1)log(2n) = 1/2n., 1/2 . t = log(2n) C xi 1 1 (1 xi )t .</p><p>. C m</p><p>i=1 xi Copt. , . log n .</p><p>. (CS ) 4. 23 / 25</p></li><li><p> t = log(2n) C , , C Sj , (e1)log(2n) = 1/2...</p></li></ul>

Recommended

View more >