Các mô hình mạng 1

Chia sẻ: Thi Sms | Ngày: | Loại File: PDF | Số trang:11

Thêm vào BST

Báo xấu

64
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tham khảo tài liệu 'các mô hình mạng 1', công nghệ thông tin, quản trị mạng phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Các mô hình mạng 1

3 ∑p C n chú ý r ng: = 0,3 + 0,4 +0,3 = 1. i i =1 M t s phân ph i xác su t thư ng dùng c a bi n ng u nhiên liên t c và r i r c ñư c li t kê dư i ñây. Phân ph i ñ u trong [0,1): X nh n các giá tr thu c n a kho ng [0,1) v i kh năng “như nhau”. Hàm m t ñ xác su t f(x) c a nó ñư c bi n di n trên hình IV.1. f(x) 1 Hình IV.1. ð th hàm m t ñ phân ph i ñ u Phân ph i Poát−xông: V i m t h th ng hàng ch m t kênh (xem m c 3), s lư ng X tín hi u ñ n trong m t kho ng th i gian là m t bi n ng u nhiên, X có th nh n các giá tr nguyên không âm 0, 1,..., k,... Gi s s tín hi u ñ n trung bình trong m t kho ng th i gian ñã bi t ñư c (kí hi u s ñó là λ) thì v i m t s ñi u ki n nh t ñ nh có th coi X tuân theo lu t phân ph i xác su t Poát−xông (Poisson) như sau: Các giá tr c a X: xi ... +∞ 0 1 ... k Xác su t pi P(X = 0) P(X = 0) ... ... λ k e−λ P(X = k) = tương ng k!  λ 0 λ1 λ 2 λk +∞  ∑p = e −λ  + + + ...  = e −λ × eλ = 1 . + ... + D th y: i  0! 1! 2! k!  i =0 Chú ý r ng s ñ c trưng cho giá tr trung bình c a bi n ng u nhiên X ñư c g i là kì v ng. Trong phân ph i Poát−xông, kì v ng c a X là λ. S ñ c trưng cho ñ phân tán các giá tr c a X xung quanh giá tr kì v ng c a nó ñư c g i là ñ l ch chu n σ. V i phân ph i Poát−xông thì σ2 = λ. Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........100
Phân ph i mũ: Trên ñây ta ñã xét phân ph i Poát−xông c a s các tín hi u ñ n trong m t ñơn v th i gian. M t ki u bi n ng u nhiên thư ng xét là kho ng th i gian gi a hai tín hi u liên ti p s tuân theo phân ph i mũ. ðây là bi n ng u nhiên liên t c ch nh n các giá tr không âm v i hàm m t ñ xác su t là f (τ) = λe −λτ . Kí hi u bi n ng u t τ thì xác su t P(τ ≤ t) = −λτ ∫ λe dτ có th hi u là xác su t c ng d n nhiên ñang xét là 0 t t cho t i t. Do ñó hàm phân ph i xác su t c a τ là: F(t) = ∫ f (τ)dτ = ∫ λe −λτ dτ = −e −λτ = t 0 0 0 1 − e−λt. Phân ph i chu n t c N(0, 1): Gi s X là bi n ng u nhiên có phân ph i chu n t c N(0,1). Lúc ñó nó có kì v ng m = 0 và ñ l ch chu n σ = 1. Hàm phân ph i xác su t c a X có d ng: x x ∫ f (x)dx ∫ (1/ F(x) = P (X≤ x) = 2π ) exp(− x 2 / 2)dx . = −∞ −∞ Cho X là bi n ng u nhiên tuân theo lu t phân ph i chu n N(m, σ2) có kì v ng m, ñ X−m l ch chu n σ. Lúc ñó, th c hi n phép ñ i bi n Z = thì Z là m t bi n ng u nhiên σ tuân theo lu t phân ph i chu n t c N(0,1). Mô ph ng các phân ph i xác su t Ví d 1: Mô ph ng phân ph i ñ u trên [0, 1) Cách 1: Dùng b ng s ng u nhiên (xem ph l c 2A và 2B). ðây là các b ng s ghi l i các s (gi ) ng u nhiên ñư c phát sinh nh các hàm sinh s ng u nhiên trong máy tính. Ch ng h n, s d ng ph l c 2B chúng ta nh n ñư c m t dãy s ng u nhiên: 0,10; 0,09; 0,73; 0,25... Cách 2: S d ng các hàm sinh s ng u nhiên (Random number generator) ñã ñư c cài ñ t trên máy tính. Dù dùng b ng s ng u nhiên hay s d ng các hàm sinh s ng u nhiên trong máy tính, ta cũng l y ra ho c tính ñư c liên ti p các s ng u nhiên xi trong [0, 1) v i i = 1, 2,..., n. T n s các giá tr này rơi vào k kho ng nh v i ñ dài b ng nhau 1/k ñư c chia ra t [0, 1) là g n như nhau (≈ n/k). V i n l n thì các t n s ñó càng sát g n n/k. Vì v y ta coi các giá tr phát sinh ñư c là các th hi n c a bi n ng u nhiên X tuân theo phân ph i ñ u trên [0, 1). Trong trư ng h p c n mô ph ng bi n Y phân ph i ñ u trên [a, b), ta ch vi c tính yi = a + (b − a)xi. Chú ý r ng ñ phát sinh các s ng u nhiên nh n giá tr nguyên 0, 1, 2,..., N, ch c n áp d ng công th c yi = [(N + 1)xi], trong ñó v ph i là ph n nguyên c a (N + 1)xi. M t s b ng s ng u nhiên nguyên hay hàm sinh s ng u nhiên nguyên cài ñ t s n trong các h máy tính cũng giúp gi i quy t v n ñ này.
Ví d 2: Mô ph ng phân ph i r i r c v i lu t phân ph i xác su t sau Các giá tr c a X: xi 6 9 12 Xác su t pi 0,3 0,4 0,3 Mu n mô ph ng phân ph i trên, trư c h t c n t o ra m t dãy các ch s ng u nhiên b ng cách tra b ng s ng u nhiên hay dùng hàm sinh s ng u nhiên ñã ñư c cài ñ t trong máy tính. Ch ng h n ta có th ch n dãy sau 1009732533 7652013586 3467354876... l y t hàng ñ u b ng s ng u nhiên trong ph l c 2B. Ta quy ñ nh n u các ch s 0, 1, 2 xu t hi n thì coi X = 6, n u 3, 4, 5, 6 xu t hi n thì coi X = 9, còn n u có 7, 8, 9 xu t hi n thì coi X = 12. Lúc ñó ng v i 10 ch s ñ u tiên c a dãy trên a1a2...a10 = 1009732533 ta có b ng sau ñây cho bi t các giá tr c a X có th l y: ai 1 0 0 9 7 3 2 5 3 3 Các giá tr c a X: xi 6 6 6 12 12 9 6 9 9 9 Như v y, ñã có 10 giá tr (th hi n) c a X ñư c t o ra. Tương t , có th t o ra các th hi n khác c a X. Do t n su t (hay xác su t th c nghi m) c a m i ch s ng u nhiên t 0 t i 9 trong b ng s ng u nhiên là kho ng 10% nên t n su t (xác su t th c nghi m) X nh n giá tr 6, 9 và 12 theo th t là 30%, 40% và 30%. Do ñó có th coi P(X = 6) = 30%, P(X = 9) = 40%, P(X = 12) = 30%. V y mu n mô ph ng phân ph i c a X ph i phát sinh ra m t lo t các giá tr (các th hi n) xi c a bi n ng u nhiên X tuân theo quy lu t phân ph i ñã cho. Ví d 3: Mô ph ng phân ph i mũ. Gi s bi n ng u nhiên τ tuân theo phân ph i mũ v i hàm phân ph i xác su t là F(t) = P(τ ≤ t) = 1 − e −λt , v i λ là tham s ñã cho c a phân ph i mũ. F(t) chính là xác su t ñ τ nh n giá tr không l n hơn m t s t cho trư c. r là bin ng u nhiên có phân ph i ñ u trên [0, 1) thì P(r ≥ e−λt ) = 1 − e−λt = Nu 1 P(τ ≤ t) (xem hình III.1). Do ñó, P(lnr ≥ − λt) = P(− lnr ≤ t) = P(τ ≤ t). V y ñ phát λ sinh ra giá tr ng u nhiên τ c a τ thì trư c h t c n phát sinh ra giá tr ng u nhiên r c a r 1 và tính τ = − lnr. Ch ng h n, t b ng s ng u nhiên (ph l c 2B), n u l y λ r = 0,10 và λ = 5 thì τ = −0,2×lnr = −0,2×ln0,1 = 0,46. Ti p theo, n u l y r = 0,09 thì τ = − 0,2×ln 0,09 = 0,482. C như v y ta thu ñư c m t dãy các th hi n c a τ. 2. ÁP D NG MÔ PH NG NG U NHIÊN Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........102
2.1. Vai trò c a phương pháp mô ph ng Nhi u bài toán th c t ch a các y u t ng u nhiên, b t n ñ nh không gi i ñư c b ng các phương pháp gi i tích. N u chúng ta áp d ng các phương pháp gi i tích thì trong nhi u trư ng h p bu c ph i công nh n nh ng gi thi t ch t ch không ñư c tho mãn trên th c t và do ñó l i gi i tìm ñư c cũng ít có giá tr th c ti n. Phương pháp mô ph ng ñư c dùng r ng rãi ñ gi i các bài toán lo i ñó, nh t là nh ng bài toán liên quan ñ n h th ng l n, b t n ñ nh, hàm ch a nhi u y u t ng u nhiên. Chúng ta c n áp d ng phương pháp mô ph ng trong các tình hu ng sau ñây: − Khi không tìm ñư c mô hình gi i tích nào thích h p. − Các ho t ñ ng c a h th ng thư ng b ng t quãng, ñ t ño n không theo quy lu t nào c . − Mô ph ng là phương pháp duy nh t cho chi phí ti t ki m và t n ít th i gian. Tuy nhiên phương pháp mô ph ng có m t s ñi m h n ch sau: − Không ñưa ra ñư c l i gi i chính xác. − Khó xác ñ nh ñư c sai s . − Mô ph ng ch s d ng khi môi trư ng có tính b t n ñ nh. − Mô ph ng ch t o ra các phương án ñánh giá ch không ñưa ra ñư c kĩ thu t tìm l i gi i t i ưu. − Mô ph ng ñôi khi r t ñ t ti n. 2.2. Các bư c c n ti n hành khi áp d ng mô ph ng − Xác ñ nh v n ñ hay h th ng c n mô ph ng. − Xác ñ nh mô hình mô ph ng. − ðo và thu th p s li u c n thi t cho mô hình. − Ch y mô ph ng. − Phân tích k t qu mô ph ng, n u c n thì ph i s a l i phương án ñã ñư c ñánh giá qua ch y mô ph ng. − Ch y mô ph ng ñ ki m ch ng phương án m i. − Ki m tra tính ñúng ñ n c a m i k t lu n v h th ng th c t ñư c rút ra sau khi ch y mô ph ng. Trên ñây là các bư c c n làm khi áp d ng mô ph ng ng u nhiên ñ tìm ra các phương án h p lí cho các bài toán th c t . Ngoài ra, mô ph ng còn ñư c áp d ng ñ gi i quy t nhi u v n ñ khác. 2.3. M t s ví d v áp d ng phương pháp mô ph ng
Ví d 1: C n l a ch n m t trong hai chi n lư c ñ phát tri n s n ph m, v i các s li u thu th p ñư c cho trong ba b ng IV.1, IV.2 và IV.3. B ng IV.1. Xác su t th i gian phát tri n s n ph m Xác su t Th i gian phát tri n s n ph m Chi n lư c I Chi n lư c II 6 0,2 0,4 9 0,3 0,4 12 0,5 0,2 B ng IV.2. Chi phí l i nhu n Chi phí/giá bán Chi n lư c I Chi n lư c II Chi phí c ñ nh 600.000 1.500.000 Chi phí bi n thiên/ñơn v 7,5 6,75 Giá bán/ñơn v s n ph m 10 10 B ng IV.3. Doanh s ph thu c th i gian phát tri n s n ph m Xác su t Doanh s 6 tháng 9 tháng 12 tháng 1.000.000 0,2 0,4 0,5 1.500.000 0,8 0,6 0,5 V n ñ ñ t ra là áp d ng phương pháp mô ph ng ñ tính l i nhu n trung bình c a t ng chi n lư c, sau ñó ki m tra k t qu (so sánh v i k t qu lí thuy t). Như v y có năm phân ph i xác su t c n mô ph ng ng v i năm bi n ng u nhiên: X1 − th i gian phát tri n s n ph m (theo chi n lư c) I, X2 − th i gian phát tri n s n ph m II, X3 − doanh s cho th i gian 6 tháng, X4 − doanh s cho th i gian 9 tháng và X5 − doanh s cho th i gian 12 tháng. Trong ví d này, ñ trình bày ñơn gi n v v n ñ mô ph ng các phân ph i xác su t c a các bi n trên, ta dùng mư i s ng u nhiên, m i s g m mư i ch s ng u nhiên rút ra t b ng s ng u nhiên − ph l c 2A (vì v y các ch s 0, 1, 2,..., 9 m i s chi m kho ng 10%). a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 1 5 8 1 9 2 2 3 9 6 2 0 6 8 5 7 7 9 8 4 8 2 6 2 1 3 0 8 9 2 8 3 7 4 8 3 6 0 4 9 4 6 3 7 5 6 7 4 8 8 Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........104
0 9 2 8 1 0 5 5 8 2 7 2 9 5 0 8 8 5 7 9 9 5 8 6 1 1 1 6 3 2 7 0 5 5 5 0 8 7 6 7 6 4 7 2 3 8 2 9 3 4 Ta quy ñ nh a1 ng v i X1, a2 ng v i X2, a6 ng v i X3, a8 ng v i X4 và a10 ng v i X5. Ngoài ra cũng quy ñ nh: thì X1 = 6 tháng (th i gian phát tri n s n ph m I) 0,1  thì X1 = 9 tháng a1 = 2 ,3,4 thì X1 = 12 tháng 5,6,7 ,8,9  0,1,2,3 thì X2 = 6 tháng (th i gian phát tri n s n ph m II)  a2 = 4,5,6,7 thì X2 = 9 tháng 8,9 thì X2 = 12 tháng  thì X3 = 106 (doanh s 6 tháng phát tri n s n ph m)  0 ,1 a6 =  6  2 , 3 ,..., 9 thì X3 = 1,5.10 6  0 ,1, 2 , 3 thì X4 = 10 (doanh s 9 tháng phát tri n s n ph m) a8 =  6  4 , 5 ,..., 9 thì X4 = 1,5.10 6  0 ,1, 2 , 3 , 4 thì X5 = 10 (doanh s 12 tháng phát tri n s n ph m) a10 =  6  5 , 6 ,..., 9 thì X5 = 1,5.10 C n nh c l i m t s công th c trong lĩnh v c qu n tr kinh doanh như sau: + L i nhu n = (Doanh s − ði m hoà v n) × (L i nhu n/ñơn v s n ph m) + ði m hoà v n = (Chi phí c ñ nh)/(L i nhu n/ñơn v s n ph m) + L i nhu n/ñơn v s n ph m = (Giá bán/ñơn v s n ph m) - (chi phí/ñơn v s n ph m) Các tính toán mô ph ng ñư c t ng h p trong b ng IV4. B ng IV.4. K t qu tính toán mô ph ng S ng u nhiên Th i gian Doanh s L i nhu n a1 a2 a6 a8 a10 I II I II I II 1,5.106 106 3,15.106 1,75.106 1 5 8 1 9 2 2 3 9 6 6 9 1,5.106 1,5.106 3,15.106 3,38.106 2 0 6 8 5 7 7 9 8 4 9 6 6 6 6 6 8 2 6 2 1 3 0 8 9 2 12 6 10 1,5.10 1,9.10 3,38.10 6 6 6 6 8 3 7 4 8 3 6 0 4 9 12 6 1,5.10 1,5.10 3,15.10 3,38.10 6 6 6 6 4 6 3 7 5 6 7 4 8 8 9 9 1,5.10 1,5.10 3,15.10 3,38.10
6 6 6 6 0 9 2 8 1 0 5 5 8 2 6 12 10 10 1,9.10 1,75.10 6 6 6 6 7 2 9 5 0 8 8 5 7 9 12 6 1,5.10 1,5.10 3,15.10 3,38.10 6 6 6 6 9 5 8 6 1 1 1 6 3 2 12 9 10 1,5.10 1,9.10 3,38.10 6 6 6 6 7 0 5 5 5 0 8 7 6 7 12 6 1,5.10 10 3,15.10 1,75.10 6 6 6 6 6 4 7 2 3 8 2 9 3 4 12 9 10 1,5.10 1,9.10 3,38.10 600.000 = 240.000 ði m hoà v n c a chi n lư c I = 10 − 7 ,5 1.500.000 = 461.538 ði m hoà v n c a chi n lư c II = 10 − 6, 75 B ng IV.5. So sánh l i nhu n gi a chi n lư c I và II Chi n lư c I Chi n lư c II T ng l i nhu n 26,5 × 10 28,91×10 6 6 L i nhu n trung bình 2,65 × 10 2,891×10 6 6 (Σ l i nhu n/10) C n chú ý r ng trong b ng IV.5 là k t qu tính toán khi ch y mô ph ng 10 lư t ng v i 10 s ñã ch n ra. N u ta l y càng nhi u s ng u nhiên thì ñ chính xác ñ t ñư c càng cao. Vì v y, n u vi c tính toán trên ñây ñư c l p trình và ch y trên máy tính v i hàng trăm, hàng ngàn lư t thì ñ chính xác s r t cao. Qua các phân tích trên ta th y, ñ ti n hành mô ph ng c n ph i có: − Cơ s d li u (DataBase) − Cơ s tri th c (KnowledgeBase) Ki m tra k t qu mô ph ng trên b ng cách so sánh v i k t qu lí thuy t ñư c th c hi n như sau: Doanh s chi n lư c I = 0,2×(0,2×106 + 0,8×1,5×106) + 0,3×(0,4×106 + 0,6×1,5×106) + 0,5×(0,5×106 + 0,5×1,5×106) = 1,295×106. L i nhu n trung bình chi n lư c I = (1,295 - 0,24)×2,5×106 = 2,637×106. K t qu tính toán mô ph ng là 2,65×106 r t sát v i k t qu này. Tương t ta tính ñư c doanh s và l i nhu n trung bình cho chi n lư c II (2,84×106) và rút ra ñư c k t lu n v ñ chính xác c a tính toán mô ph ng. Ví d 2: Tìm xác su t p ñ bao l i c a 4 ñi m l y b t kì trong vòng tròn ñơn v là m t hình tam giác (bài toán Sylvester). Có l cách ñơn gi n nh t ñ gi i bài toán này là áp d ng mô ph ng ng u nhiên theo các bư c sau ñây: Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........106
i) Gán cho bi n ñ m Counter giá tr ban ñ u b ng 0. ii) Ti n hành m t ñ t gieo ng u nhiên tám s th c 0 ≤ ri ≤ 1 và 0 ≤ ϕi ≤ 2π (ñ gieo ϕi ta l y s ng u nhiên thu c [0, 1) gieo ñư c nhân thêm v i 2π), i = 1, 2, 3, 4. ð t xi = risinϕi, yi = ricosϕ i, ta có 4 ñi m n m trong hình tròn ñơn v . ð t A = (x1, y1), B = (x2, y2), C = (x3, y3), D = (x4, y4). iii) Ta tính di n tích 4 tam giác ABC, ABD, ACD và BCD. N u ta có di n tích c a m t tam giác b ng t ng di n tích ba tam giác còn l i thì ta ñư c bao l i c a b n ñi m A, B, C và D là m t tam giác. Ta tăng giá tr c a bi n ñ m Counter lên thêm 1, n u trái l i bi n ñ m gi nguyên giá tr cũ và quay v bư c ii). Quá trình c th ti p di n cho t i khi s ñ t gieo ñ t t i m t giá tr khá l n ñư c ch n t trư c (ch ng h n 10.000 ñ t ho c 20.000 ñ t, ho c 100.000 ñ t). M i l n bi n ñ m Counter s có giá tr k t thúc khác nhau. L y t s c a s ñó và s ñ t, ta có t n su t xu t hi n c a s ki n "bao l i c a 4 ñi m là tam giác". S t n su t này theo lu t s l n là giá tr g n ñúng c a xác su t c n tính. Theo các tài li u chuyên kh o, l i gi i ñúng c a bài toán là: p = 35/(12π2) ≈ 0,29552. Rõ ràng, trong trư ng h p này, ta nên áp d ng mô ph ng ng u nhiên ñ tính ra t n su t (vi c d th c hi n), thay th cho vi c tính xác su t theo lí thuy t (vi c khó th c hi n). Sau ñây là văn b n chương trình máy tính v i ngôn ng l p trình C gi i bài toán Sylvester. #include #include #include #include #define PI 3.14159265358979 const double esp =4.5e−12; struct diem {double x,y;}; /* Tao bo so ngau nhien bang cach tron − shuffling */ int rd(){return rand()%10;} double radm() {return rand()%100+0.1*rd()+0.001*rd()+0.0001*rd();} /* Chuong trinh chinh */ void main()
{ clrscr(); long int count = 0, reps; diem d[4]; double r, goc; printf("\n Provide number of repetitions:"); scanf("%ld",&reps); printf("\n reps= %ld",reps); srand(19587); /* Gieo ngau nhien 4 diem va tinh dien tich bon tam giac */ for(long int i=0;i0&&s134>0&&s234>0) { s123=sqrt(s123);s124=sqrt(s124); s134=sqrt(s134);s234=sqrt(s234); if(fabs(s123−(s124+s134+s234))
count++; else if(fabs(s134−(s123+s124+s234))
th ch ng minh ñư c quá trình SA s h i t theo xác su t v l i gi i t i ưu toàn c c) như sau: Bư c kh i t o Ta xu t phát t m t phương án X b t kì ban ñ u tho ñi u ki n ràng bu c. L y nhi t ñ T = Tban ñ u khá cao (Tban ñ u =10000, ch ng h n). Các bư c l p T i m i m c nhi t ñ T th c hi n các bư c sau: i) Ch n X’ ∈ D và thu c m t lân c n ñ nh c a X. ii) Xét ∆f = f(X’) - f(X). N u ∆f < 0 thì ñ t X:= X’. N u trái l i khi ∆f > 0 thì ch p nh n X:= X’ v i xác su t p = exp(−∆f /(K b × T)) , trong ñó Kb là h ng s Boltzmann (Kb = 1,38.1023), T là nhi t ñ hi n th i trong quá trình ngu i. Quy trình i) và ii) l p l i m t s l n L ñ l n (ch ng h n L = 200, 300,...). Sau ñó tính m c nhi t ñ m i theo công th c T: = αT (α ≈ 1, ch ng h n như α = 0,95 hay 0,99…). Thu t toán d ng khi T ≤ Tcu i (Tcu i là giá tr ñã ch n trư c ≈ 0). Sau ñây là văn b n chương trình annealing.cpp: /* Su dung ky thuat simulated annealing − mo phong toi luyen giai bai toan toi uu toan cuc co rang buoc */ #include #include #include #include /* Tinh gia tri ham so can cuc tieu hoa */ float f(float x,float y) { float fg = 4*pow(x,2)−2.1*pow(x,4)+pow(x,6)/3; fg = fg +x*y −4*pow(y,2)+4*pow(y,4); return fg; } /* Kiem tra cac dieu kien rang buoc */ int constraint(float x,float y) Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........110