close

Вход

Забыли?

вход по аккаунту

?

отчет(17)

код для вставкиСкачать
???????????? ??????????? ? ????? ?????????? ?????????
??????????????? ??????????????? ??????????
??????? ????????????????? ???????????
"????????????? ??????????????? ??????????? ??. ?.?. ????????????"
????????? ?????????????? ?????????? ? ???????????
??????? ??????????????? ??????????? ???
?????????? ???????? ???????? n-????? ?? ?????????
(??????? 592)
????????: ??????? ?????? 8309
???????? ?. ?.
????????: ???????? ?.?.
?????? ????????
2012
??????????
1.???????? ??????????3
?????????? ??????3
???????? ?????????? ???????? ???????? ? ??????? ??????????3
???????? ?????????? ? ?????????????? d-???.4
????????? ???????? ???????????? ??? d-????? ? ????????? ?????? ?????????.4
???????? ?????????? k-????????.6
???????? ?????????? ?????????.7
2.??????????? ????????????? ?????? ????????? ????????? ??????????.7
????????? ?????????? ? ??????? d-???:8
????????? ?????????? ? ??????? ?????????? k-????????:10
3.??????????? ????????????.11
4.????????? ??????????14
5.??????15
???????? ??????????
?????????? ??????
??? ????? a1, ..., an, ??? n=1, ai=(ai,1, ai,2)?R2 ??? i=1, ..., n, ??????? ??????? b1, ..., bm ???????? ???????? Conv(a1, ..., an) ? ??????? ?? ??????? ??? ???????? ?? ?? ???????. ???????, ??? ? ????? ?????? Conv(a1, ..., an) ????? ???????????????, ? ? ??????????? ??????? ????? ?????????? ??????? ??? ?????. ? ?????? ??????? ??????? ????????? ???????????? ?????? ????????? ?????? ???? ??? ?????????? ??? ??????? ?????, ? ? ?????? ????? ? ???? ??? ?????. ?????????? ???????? ???????? ????????? ????????? ???????????? ?????????? ?????????? ?????????? ???????? ???????? n ????? ?? ????????? ? ?????????????? ????????????. ?????????:
????????, ???????????? ?????????? ? ??????? d-????, d=50
????????, ???????????? ?????????? (k-50)-????????, k=92
???????? ?????????? ???????? ???????? ? ??????? ?????????? ????? ??????????????????? ???????? c = lexmin(a1, ... ,an) ????? ????? ??????? ????? {a1, a2..., an}. ??? ????? ?????????? ???????????? ????? ? ??????????? ?????? ???????????, ? ????? ? ???? ???????????? ?????????? ????? ? ??????????? ?????? ???????????. ?????????? ????? c ????? ?????? ????????? ???????? ????????.
?????? ??????? ?????? ??????? ????????? ? ?????????? ????? {a1-c, a2-c..., an-c}.
?? ?????? a1, ..., an ???????????? ???????? ??????? ( = ), ??? ??? c1,c2 ?{a1-c, ... ,an-c} ????? ????? c1 = c2, ????
???? det(c1,c2)>0,
???? (det(c1,c2)=0)&( (c1,1)2+(c1,2)2) < (c2,1)2+(c2,2)2 ).
??????????? ?????????? ????? ?? ?????????? ????????? ???? ?? ??????(=). ???????????? ???????? ???????????????? ??????? ? ????? ????????? ???????? ????? b1, ..., bm ?????? ?? ???? ???????, ??? ????? bi+1 ????????????? ?????? ????? ?? ???????, ??????? ?? ????? bi-1 ? ????? bi, ??? ???????????? ?????????? ????, ????? det(bi-bi-1,bi+1-bi)>0.
????????? ???????? ???????????? ???????, ?????? m-????? ???????? ???????? ???????? ????????? ?????? ?????.
???????? ?????????? ? ?????????????? d-???.
?? ??????? ????? ??????????? ??????????? d-????? ??????(??????? ???? ?????? ????????????? ??????? ???????). ??? ???????????? d-?????? ?????? ???????????:
?????? ?? ???????? ????, ?????, ???? ?????, ??????, ?????? ????? ????? d ???????????????? ????????. (???? ?????????? ????? ????? ????? ????? ???????? ?? 0 ?? d)
???? h - ?????? ??????, ?? ??? ?i? {0,1,..n-1} i-?? ??????? ?????? ????? ????? di ?????, ? ?? ????????? ?????? ????? ???? ????? ????? ????? ?? 1 ?? dn.
??????????? ???????? ?????????? (?????????? ???????? diving(i) ?? ??????? ? ????? n-1,...0. ??? ??????? ???? ?? ??????????? ????? ?????????, ??????????? ? ??? ????????.
?????????? ? ????? ??????? Sort ???????, ?????????? ?????? ? d-????. ?? ????? ????? ?????? ??????? ? ???????????? ????????, ?????? ???? ????????? ?? 1 ? ???????????? ?????????? ????????? ???????? ????.
?????????? ????????? ???????? (? ?????? 2.) ?? ??? ???, ???? ?????? ???? ?? ????? ????? 1.
? ???? ????????? ??????? ? ???????????? ?????, ??? ?????????? ???????? ? ????? ??????? Sort. ????? ???????, ??????? ?????? Sort, ??????????????? ?? ?? ????????.
????????? ???????? ???????????? ??? d-????? ? ????????? ?????? ?????????.
Diving(i)
{
j1=i;
j2=MinChild(i);
while ( !IsLeaf(j1) && (Key[j2] <= Key[j1] ) )
{
Swap(j1,j2);
j1=j2;
j2=MinChild(j1);
}
}
MinChild(i){
L=LeftChild(i),R=RightChild(i); if (L == -1) return i; //???? ??? ????????
min_key=Key[L];
minchild=L;
for(j=L+1; j<R+1; j++)
if( Key[j] <= min_key) {
minchild=j;
min_key=Key[j]; }
return minchild;
}
IsLeaf(i){
if( i*D+1 >=N ) return true; ; // d-???? ? d=D ? ?????? ????????? =N return false;
}
LeftChild(i){
if (IsLeaf(i))
return -1;
return 1+(D*i);
}
RightChild(i){
if (IsLeaf(i))
return -1;
else if( i*D+D < count-1)
return i*D+D;
return count-1;
}
Swap(a,b){ Key[a] ?Key[b]; }
DeleteMin{ if (count==0) return Key[0]; // ???????????? ?????? ??? ??????????
Swap(0, (N-1) ); N--; Diving(0);
return Key[0];
}
MakeHeap(){
for(i=N-1;i=0;i--)
Diving(i);
}
SortHeap()
{
MakeHeap();
for(i=0;i=n-1;i++)
{
W=DeleteMin();
Sort[i]=w;
}
}
???????? ?????????? k-????????.
?? ??????????? ?????????? ??????? ? ????????? ??????? ?? k ?????????????? ?????????? ??????, ?? ??????????? ? ??????????? ???????????? ??????????????? ??????????. ??? ????? ???????????? ??? ?????????: SORT_MERGE(a,i,j,k) ? MERGE(a,i,m,j), ?????? ?? ??????? ????????? ?? ?????????? ??????? a[i...j] ????????? ??????? a[1...n], ?????? ??????? ??? ??????????????? ??????? a[i...m] ? a[m+1...j]. ????? ?????? ????????? ? ??????????? i=1 ? j=n ????????? ???? ?????? a.
procedure SORT_MERGE(var a;i,j,k);
begin
if (j-i+1) then ?????????? ??????? a[i..j] ?????-?????? ??????? ???????? (????????, ??????????? ???????????) else begin
step:=(j-i+1) div k; for numb:= 0 to k-1 do begin if (numb<k-1) then SORT_MERGE(a,i+step*numb,i+step*(numb+1)-1,k)
else SORT_MERGE(a,i+(k-1)*step,j,k);
end;
for numb:= 0 to k-2 do begin
if (numb<k-2) then MERGE(a,i,i+step*(numb+1)-1, i+step*(numb+2)-1)
else MERGE(a,i,i+(k-1)*step-1,j);
end;
end;
end;
procedure MERGE(var a;i,m,j);
begin
1. ???????? ??????? b ???????? j-i+1, ????????????? ?????????? i1:=i, i2:=m+1;
2. ? ?????, ???? i1+i2<j+m+2, ??????????? ????????? ????????: 2.1. ???? (i1m ? i2<j+1 ? a[i1]a[i2]) ??? (i2=j+1), ?? b[i1+i2-i-m]:=a[i1] ? i1:=i1+1;
2.2. ?? ???? ????????? ??????? b[i1+i2-i-m]:=a[i2] ? i2:=i2+1;
3. ??????????? ?????????? ??????? b ? ?????? a[i...j].
end;
???????? ?????????? ?????????.
? ?????????? k-???????? ?????? ?????????????? ?????-?????? ??????? ?????? ??????????. ? ???? ?????? ???????????? ???????? ?????????? ?????????.
? ?????? ????????? ?? ????????????? ?????? ?? i-?? ????. ?????? ? ????? ??????? ???????? ?? ??? ?????: ??????????????? ( ?? a[0] ?? a[i] ) ? ??????????????? ( ??????? ? a[i+1] ?? a[n] ).
?? ?????? ????????? (i+1)-?? ???? ????????? ????? a[i+1] ? ????????? ?? ?????? ????? ? ??????? ????? ???????.
????? ??????????? ????? ??? ?????????? ???????? (?.?. a[i+1] ) ?????????????? ????? ???????????????? ????????? ? ??????????, ???????? ????? ???. ? ??????????? ?? ?????????? ????????? ??????? ???? ???????? ?? ??????? ????? (??????? ?????????), ???? ??? ???????? ??????? ? ??????? ???????????.
??????????? ????????????? ?????? ????????? ????????? ??????????.
????????? ????????? ????????? ?????????? ???????? ???????? ???????????? ?? ?????????? ?????????? ??????? ???? ?????????. ????? ???????, ?????????? ??????? ????????? ????????? ??????:
????? ??????????????????? ???????? ?=lexmin{a1,...,an} ?????????????? ? 2 ?????. ?? 1 ????? ??????????? ?????????? ??????? ?????? ????? ? ??????????? ?????? ???????????. ????????? ????? ???????? ?????????? ?(n), ??? n - ????? ????????? ???????.
?? 2 ????? ????? ????? ? ??????????? ?????? ??????????? ????? ???????????? ????? ? ??????????? ?????? ??????????? ????? ??????????? ??????????? ???????????? ????????? ???????. ? ?????? ?????? ?????????? ????? ? ??????????? ?????? ??????????? ????????? ? ???????????? ????????? ??????? (??????, ????? ??? ????? ????? ?????????? ?????? ??????????). ??????? ????????? ????? ???????? ?????? ?? ????????? ?(n).
??????? ??????? ????????? ? ????? ?=lexmin{a1,...,an} ?????????????? ???????? ?? ????? ??????? ? ?????????? ??????????????? ??? ?????????. ????? ???????, ????????? ?????????? ??????? ????? ??????? ?(n).
?????????? ?????????????? ? ??????? 52-??? ? ??????????? ?????????? ?????????? 50-????????.
????????? ?????????? ? ??????? d-???:
?????????? ?????? ??? ?????????? ? ??????? d-???.
??? ????? ????? ??????? ????????? ????????? ??????:
??????????
? ????? ?? ?????????? ????????? ? ??????? ???????? ???????? ???????????? (DeleteMin) ?? d-????.
????????? ???????? ??????????:
???????.
?????????????? ????????? ???????? ?????????? ????? ?(n).
??????????????:
???????? ?????????? ??????????? ? ???????????????? ?????????? ?????????, ??????? ? ?????????? ???????? ??????.
????????? ?????????? ? ?????? i ?????????? O(d(h-i)). ????????? ???????? ?????????? (Diving) ?????? ? ?????????? ???????. ????????? ???? ???????? ????????????:
?????????? ???????? ?????? ??????? ? ??????????? ?????? (MinChild). ??? ??? ? ??????? ?? ????????? ????, ?? ??????????? ??????, ????? d ????????, ?? ????????? ???????? MinChild ??????? ?(d).
?????? ???????? ?????, ? ??????? ??? ???????? ???????????. ? ????? ?????? ??????, ????? ???????? ????? ????? h.
?????????????, ??? ???? ? ????????????? ?????? ?????? ?????????? ????? ????? O(dh), ? ??? ???? ? ?????? i - O(d(h-i)).
? ????? ??????????? d-????? ?????? ? n ?????? ? ??????? h ??????? ?? ????? ??? n/d^(h-1-i) .
?????????? ????????? ?????????? ?????? ?????? h:
????? h-i=j, ?? ???????:
?_(j=0)^h�j/d^j =?_(j=0)^8�?j*(1/d)^j= 1/d?*?_(j=1)^8�?j*(1/d)^(j-1) ?
??? ??? ??? 0<1/d<1 ??? ??? ???????? ??????????, ?? ???????:
1/d ?_(j=1)^8�?j*(1/d)^(j-1)=1/d (?_(j=1)^8�(1/d)^j )^'=? 1/d (1/(1-1/d))^2=d/(d-1)^2 ?.?.?.
????????? ???????? ???????? ???????????? (DeleteMin):
??????????, ?????? ???????? ???????? ? ???? 2 ????????:
swap
diving
???????? Swap ??????????? ?? ????? ?(1). ? ??? ???? ???????? ????, ???????? ?????????? (diving) ?????? ???????? ??????????? ?? ????? ?(dh). ?????? ?????? ??????.
???????.
?????? h ???????????? -?????? ?????? ????????????? ?????????? ??????????? .
??????????????:
??????????? ????? ????? ? ?????? ?????? ???????????? ????????? ????????????
, ?.?. ? ??????????? -????? ?????? ?????? ????, ?? ???????????, ???? ?????, ?????? ????, ???????? ????? -????????. ????? ??????????? ?????????? ????? ?????, ????? ???? ???? ???? ????? ?????? ???????.
???????????? ?????????? ????? ? ?????? ?????? ???????????? ????????? ???????????? . ????? ???????????? ?????????? ????? ?????, ????? ??? ???? ????? ????? -????????.
????? ???????, ????? ????? ? ?????? ?????? ????????????? ???????????:
. ????????????? ????? ? ?????? ????? ??????? ???????????:
?????? ????????, , ?.?.?.
????? ???????, ??????? ?????? ????????? ???????? ?????????? ???? n ????????? (???????????? ??????? ????? ??????????) ?????????? ????, ????????? ?????????? ? ??????? d-??? ????? =O(n*logn)
????????? ?????????? ? ??????? ?????????? k-????????:
????? ??????? ????? ?????? ????? ?????????, ?????? ????? ?????? ?????????? ????????.
??? ????? ???????? ???????????? ???????????. ?????? T(n) - ????? ?????????? ??????? ????? n, ????? ??? ?????????? ???????? ??????????? T(n)=2*T(n/2)+O(n) (O(n) - ??? ?????, ??????????? ?? ??, ????? ????? ??? ???????). ???????? ??? ???????????:
T(n)=2*T(n/2)+O(n)=4*T(n/4)+2*O(n)=...=2k *T(1)+k*O(n)
???????? ??????? k. ?? ?????, ??? 2k=n, ? ?????? k=log n.
????????? ?????? ??? T(n)=n*T(1)+log n *O(n). ??? ??? T(1)- ?????????, ??
T(n)=O(n)+log n *O(n)= O(n* log n) - ????, ??? ????????? ?????????? ????????.
??? ?????? ?????????? k-???????? ??????????? ?????? ????????? ????????? ?????????? ?????????. ??? ??? ? ???????? ?????? ????????? ????? ???????? ??????? ?????? ???????? ????????, ?????? ????? ????????? ????? ???????? ?? ???????. ??????????? ????????:
????? P=(p1,p2,...,pn) ???????? ????????????? ????? 1,2,...,n. ????????? ? ???????????? P ?????????? ?????? ???? ???????? i,j ?????, ??? 1= i<j=n ? P[i]>P[j] . ?????????????, ?????????? ??????? ????? ?????????? ???????? ? ???????? ??????? ??? ??????????? ?? ?????????? ??????????. ???????????? ?????????? ???????? ?????????? ? ???????, ???????? ???????? ????????????? ?? ?? ???????????. ????? ???????? ? ????? ??????? 1/2 *n(n-1). ???????? ?????? ?(n2).
?????? ?????? ????????? ????????? ?????????? k-????????. ???????, ??????
??? ????? ??? ?? ???????? ???????????? ???????????. ?????? T(n) - ????? ?????????? ??????? ????? n, ????? ??? ?????????? ???????? ??????????? T(n)=2*T(n/2)+O(n) (O(n) - ??? ?????, ??????????? ?? ??, ????? ????? ??? ???????). ???????? ??? ???????????:
T(n)=2*T(n/2)+O(n)=4*T(n/4)+2*O(n)=...=2l *T(w)+l*O(n)
??? w - ????? ?????????, ??????? ??????????? ?????????. ?????? ???????????: T(w)=O(w2) (???????? ? ?????????? ??????)
2l=n/w w- ? ??????????? ?? n ????? ?????????? ?? 1 ?? k-1 (?????????? k-????????).
????? ???????, l=logn/w =logn - logw. ?.?. w=const ??? ??????????? n, ?? O(l)=O(logn), ? ?????????? ??? O(2l)=O(n/w)=O(n).
????, T(n)= O(nw2)+log n *O(n)= O(n)+log n *O(n)= O(n* log n)
4.???????? ??????? ??? ????????? ????????? ????????? ????? ???????? ???????? ??????????? ?? ????? ?(n)
5.???????? ??????? ? ???????? ??????? ????????? ??????????? ?? ???? ?????? ?? ??????, ?.?. ?? ????? ?(n).
?? ??????????? ????????????? ???????, ??? ????????? ????????? ???????? ?????????? ???????? ???????? ????? O(n*logn)+ ?(n)= O(n*logn)
???????? ?????????.
? ?????? ???????????? ?????? ??????????? 3 ?????????. ?????? ????????? ????????????? ???????????? ?????? ?????????. ?????? ?????????? ????? ????????? ?? ????????? ??????. ????????? ??????? ?????????:
LAB_ADS.exe n q w mode
n- ?????????? ?????????
q,w- ????? ?????? ?????????????? (q x w)
mode- ?????? ????????? ?????? (?????? ??? ??? ??????????????)
????????? ?????????? ??????????????? ??????? ?????? ????????????? ?????, ? ????????? ???????? ?????? ???????? ????????, ????????? ?????????? ?????????? ?? ?????? d-???? ? ?????????? k-????????. ????? ?????????? ???????? ????????, ??????????? ???????? ?? ????? ??????? ?????, ????????????? ?? ?????????? ????? ???????? ???????? ?????????. ?? ????????? ?????? ?????????? ?? ????? ????? ???????? ????? ???????? ????????, ????????? ? ???, ?????? ?? ??? ???????? ??? ???, ????? ?????? ? ???????? ??????? ?????????(?? ?????? ??????????????? ??????????). ???? ?????????? ????? ????? ? ???????? ???????? (<1000 ??? <10000 ? ??????????? ?? ??????? ?????????), ?? ?? ?????? ???????? ??????????? ??????????? ????? ???????? ???????? ? ???? ????????? ?????.
?????? ? ?????? ????????? ?????????? ??? ?????????? ?????????????. ?????? ??? ?????????? ????????????? ??? ????????????? ? ???????????? ????????? , ?????? ??? ????? ????????????? ??? ????????????? ? ???????????? ?????????? .
????????? ?????? ?????? ????????? ?? ????????? ?????? ?????????:
// LAB_ADS.exe n n1 mode
//n- ????????? ?????????? ?????????
//n1- ???????? ?????????? ?????????
//mode- 1 ??? 2, ?????? ????????? ??????
//q=w=1000001
????????? ?????? ??????? ????????? ?? ????????? ?????? ?????????:
// LAB_ADS.exe qw qw1 mode
//n- ????? ????????? = 1000000
//qw- ????????? ??????? ????????(qw x qw)
//qw1- ???????? ??????? ????????
//mode- 1 ??? 2, ?????? ????????? ??????
?? ???? ?????? ????????? ?????????? ?? ????? ????? ????????? ????? ?????? ? ???????? ??????? ?????????(?? ?????? ??????????????? ??????????). ? ??? ?? ????? ?????? ????? ???????????? ? ???? ??? ?????????? ????????.
??????????? ????????????.
???????? ???????????? ?????? ???? ????????? 2 ?????? ?????????????:
????? ? ?????? ?????????????? ??? ????????? ????? ??????????? (106), ?????????? ?????????? ???????????? ????? ? ????? .
??????????? ?????????? ???????????? ????? (106), ?????????? ????? ? ?????? ?????????????? ??? ????????? ????????? ????? ? ????? ??? ??????? ?????? ?????????? ????????? ??????? ???????????? ????? ?????, ??????? ???????? ?? ???? ??????????? ??????????. ?????????????? ?????????? ????? ?????? (? ????????) ??????? ????????? ??? ????????? ?????????? ?????.
?????????? ?????? ?????? ????????????? ????????? ?????????????? ?? ???.1 ? ???2, ? ?????????? ?????? - ?? ???.3 ? ??? 4.
???.1. ????? ?????? ??????????? ?????????? ??? ????????????? ? ???????????? ????????? ; ?=K=10-6
???.2 ????? ?????? ??????????? ?????????? ??? ????????????? ? ???????????? ????????? ; ?=11*10-5; K=9*10-5
??c3. ????? ?????? ??????????? ?????????? ??? ????????????? ? ???????????? ?????????? ??c4. ????? ?????? ??????????? ?????????? ??? ????????????? ? ???????????? ?????????? ????????? ??????????
?? ??????????? ??????????? ????????????? ????? ????????? ????????????? ?????? ??????? ?? ??????????. ???????????? ??????????, ??? ???????? ?????????? ???????? ????????, ???????????? ????? ?????????? ? ??????? 50-????, ???????? ???????????, ??? ???????? ?????????? ???????? ????????, ???????????? ????? ?????????? 52-????????. ?????????? ????????, ???, ??????? ? ????????? ???????? ????? (??????) ?????????????? ????????????? ????? ??? ????????????? ?? ?????????? (??. ???.3,4), ????? ?????? ?????????? ??????????????? ? ??????????? ?????????? ????????. ?????? ???? ??????? ? ???, ??? ????? ?????? ????????? ?? ??????? ?? ???????? ?????????????? ?????????????. ??????
????????????? ?????? ????????? ????? ?????????? ??????????? ????????? ??????? (????????? ????? ??????? , ??? ?????????? ????????????? ????????? , ??? ??????? ). ??????? ????? ????????????? ??? ???????????? ???????? ????? ????? ??????? (??. ???.1) ?????? ? ???????? ??????? . ????? ???????, ?????????? ???????????? ????????????? ?? ???????????? ??????, ?.?. ?????? ??????? ???????? ? ????? ????????????? ??????.
Документ
Категория
Без категории
Просмотров
26
Размер файла
277 Кб
Теги
отчет
1/--страниц
Пожаловаться на содержимое документа