Karena banyak variabel acak dalam aplikasi terbentuk di bawah pengaruh beberapa faktor acak yang bergantung lemah, distribusinya dianggap normal. Dalam hal ini harus diperhatikan kondisi bahwa tidak ada faktor yang dominan. Teorema limit pusat dalam kasus ini membenarkan penerapan distribusi normal.

YouTube ensiklopedis

• 1 / 5

  Biarkan ada urutan tak terbatas dari variabel acak independen yang didistribusikan secara identik dengan harapan dan varians matematis yang terbatas. Tunjukkan yang terakhir (\displaystyle \mu ) dan 2 (\displaystyle \sigma ^(2)), masing-masing. Biarkan juga

  . S n − n σ n → N (0 , 1) (\displaystyle (\frac (S_(n)-\mu n)(\sigma (\sqrt (n))))\to N(0,1) ) dengan distribusi di ,

  di mana N (0 , 1) (\displaystyle N(0,1))- distribusi normal dengan ekspektasi matematis nol dan simpangan baku sama dengan satu. Menunjukkan sampel rata-rata yang pertama n (\gaya tampilan n) besaran, yaitu X n = 1 n ∑ i = 1 n X i (\displaystyle (\bar (X))_(n)=(\frac (1)(n))\sum \limits _(i=1)^( n)X_(i)), kita dapat menulis ulang hasil teorema limit pusat dalam bentuk berikut:

  n X n → N (0 , 1) (\displaystyle (\sqrt (n))(\frac ((\bar (X))_(n)-\mu )(\sigma ))\to N(0,1)) dengan distribusi di n → (\displaystyle n\ke \infty ).

  Laju konvergensi dapat diperkirakan dengan menggunakan pertidaksamaan Berry- Esseen.

  Perkataan

  • Secara informal, teorema limit pusat klasik menyatakan bahwa jumlah n (\gaya tampilan n) variabel acak independen yang terdistribusi identik memiliki distribusi yang mendekati N (n μ , n 2) (\displaystyle N(n\mu ,n\sigma ^(2))). Setara, X¯n (\displaystyle (\bar(X))_(n)) memiliki distribusi yang mendekati N (μ , 2 / n) (\displaystyle N(\mu ,\sigma ^(2)/n)).
  • Karena fungsi distribusi dari distribusi normal standar kontinu, konvergensi pada distribusi ini setara dengan konvergensi pointwise dari fungsi distribusi ke fungsi distribusi dari distribusi normal standar. Menempatkan Z n = S n μ n n (\displaystyle Z_(n)=(\frac (S_(n)-\mu n)(\sigma (\sqrt (n))))), kita mendapatkan F Z n (x) → (x) , ∀ x R (\displaystyle F_(Z_(n))(x)\to \Phi (x),\;\forall x\in \mathbb (R) ), di mana (x) (\displaystyle \Phi (x)) adalah fungsi distribusi dari distribusi normal standar.
  • Rumusan klasik teorema limit pusat dibuktikan dengan metode fungsi karakteristik (Teorema kontinuitas Levy).
  • Secara umum, konvergensi densitas tidak mengikuti konvergensi fungsi distribusi. Namun demikian, dalam kasus klasik ini, inilah masalahnya.

  CPT lokal

  Di bawah asumsi perumusan klasik, anggaplah sebagai tambahan bahwa distribusi variabel acak ( X i ) i = 1 (\displaystyle \(X_(i)\)_(i=1)^(\infty )) benar-benar kontinu, yaitu memiliki kerapatan. Kemudian distribusinya juga benar-benar kontinu, dan terlebih lagi,

  f Z n (x) → 1 2 e x 2 2 (\displaystyle f_(Z_(n))(x)\to (\frac (1)(\sqrt (2\pi )))\,e^ (-(\frac (x^(2))(2)))) pada n → (\displaystyle n\ke \infty ),

  di mana f Z n (x) (\displaystyle f_(Z_(n))(x))- kepadatan variabel acak Z n (\gaya tampilan Z_(n)), dan di sisi kanan adalah densitas dari distribusi normal standar.

  Generalisasi

  Hasil teorema limit pusat klasik berlaku untuk situasi yang jauh lebih umum daripada independensi penuh dan distribusi yang sama.

  C.P.T. Lindeberg

  Biarkan variabel acak independen X 1 , … , X n , … (\displaystyle X_(1),\ldots ,X_(n),\ldots ) didefinisikan pada ruang probabilitas yang sama dan memiliki ekspektasi dan varians matematis yang terbatas: E [ X i ] = i , D [ X i ] = i 2 (\displaystyle \mathbb (E) =\mu _(i),\;\mathrm (D) =\sigma _(i)^( 2)).

  Biarlah S n = i = 1 n X i (\displaystyle S_(n)=\sum \limits _(i=1)^(n)X_(i)).

  Kemudian E [ S n ] = m n = i = 1 n i , D [ S n ] = s n 2 = i = 1 n i 2 (\displaystyle \mathbb (E) =m_(n)=\sum \ limit _(i=1)^(n)\mu _(i),\;\mathrm (D) =s_(n)^(2)=\sum \limits _(i=1)^(n)\ sigma _(i)^(2)).

  Dan biarkan berjalan Kondisi Lindeberg:

  > 0 , lim n → ∑ i = 1 n E [ (X i − μ i) 2 s n 2 1 ( | X i i | > s n ) ] = 0 , (\displaystyle \forall \varepsilon >0,\;\lim \limits _(n\to \infty )\sum \limits _(i=1)^(n)\mathbb (E) \left[(\frac ((X_(i)-\ mu _(i))^(2))(s_(n)^(2)))\,\mathbf (1) _(\(|X_(i)-\mu _(i)|>\varepsilon s_ (n)\))\kanan]=0,)

  di mana 1 ( | X i i | > s n ) (\displaystyle \mathbf (1) _(\(|X_(i)-\mu _(i)|>\varepsilon s_(n)\))) fungsi - indikator.

  dengan distribusi di n → (\displaystyle n\ke \infty ).

  Ts.P.T.Lyapunova

  Biarkan asumsi dasar Ts. P. T. Lindeberg terpenuhi. Biarkan variabel acak ( X i ) (\displaystyle \(X_(i)\)) memiliki momen ketiga yang terbatas. Kemudian urutannya

  r n 3 = i = 1 n E [ | X saya saya | 3 ] (\displaystyle r_(n)^(3)=\sum _(i=1)^(n)\mathbb (E) \left[|X_(i)-\mu _(i)|^(3 )\Baik]).

  Jika batas

  lim n → r n s n = 0 (\displaystyle \lim \limits _(n\ke \infty )(\frac (r_(n))(s_(n)))=0) (Kondisi Lyapunov), S n m n s n → N (0 , 1) (\displaystyle (\frac (S_(n)-m_(n))(s_(n)))\to N(0,1)) dengan distribusi di n → (\displaystyle n\ke \infty ).

  C.P.T. untuk martingales

  Biarkan proses (X n) n N (\displaystyle (X_(n))_(n\in \mathbb (N) )) adalah martingale dengan kenaikan terbatas. Secara khusus, mari kita asumsikan bahwa

  E [ X n + 1 X n X 1 , … , X n ] = 0 , n N , X 0 0 , (\displaystyle \mathbb (E) \left=0,\;n\in \mathbb (N) ,\;X_(0)\equiv 0,)

  dan kenaikannya berbatas seragam, yaitu

  C > 0 n N | X n + 1 X n | C (\displaystyle \exists C>0\,\forall n\in \mathbb (N) \;|X_(n+1)-X_(n)|\leq C) n = min ( k | i = 1 k i 2 n ) (\displaystyle \tau _(n)=\min \left\(k\left\vert \;\sum _(i=1)^ (k)\sigma _(i)^(2)\geq n\kanan.\kanan\)). X n n → N (0 , 1) (\displaystyle (\frac (X_(\tau _(n)))(\sqrt (n)))\ke N(0,1)) dengan distribusi di n → (\displaystyle n\ke \infty ).

  Python untuk mengajar ilmu komputer ilmiah: Pemodelan sistem antrian

  • Terjemahan
  • tutorial

  anotasi

  Dalam makalah ini, kami menyajikan metodologi untuk memulai informatika ilmiah berdasarkan pemodelan dalam pendidikan. Kami menawarkan sistem antrian multi-fase sebagai dasar untuk objek yang diteliti. Kami menggunakan Python dan komputasi paralel untuk mengimplementasikan model, menyediakan kode dan hasil simulasi stokastik.

  1. Pendahuluan dan latar belakang

  Dalam studi kami, kami memahami arti istilah "informatika ilmiah" sebagai penggunaan komputer untuk menganalisis dan memecahkan masalah ilmiah dan rekayasa. Kami membedakannya dari perhitungan numerik sederhana. Penggunaan informatika ilmiah dalam pengajaran selalu menjadi tantangan baik bagi siswa maupun guru. Proses pembelajaran seperti itu berkaitan dengan banyak masalah teknis dan interdisipliner, dan juga membutuhkan sinkronisasi pengetahuan matematika dengan ilmu komputer. Untuk mengatasi tantangan ini, kami mengusulkan seperangkat prinsip dan metodologi pengajaran yang dibangun di atas pendekatan konstruktivis untuk belajar dan memberikan dasar struktural yang sesuai untuk guru. Semua ini memungkinkan siswa untuk melakukan serangkaian eksperimen komputasi dengan model komputer. Pendekatan ini dikaitkan dengan pengetahuan matematika dan pemrograman, yang, pada gilirannya, diajarkan dalam kursus kurikulum utama dan terkait erat dengannya. Kami akan mempertimbangkan bagian statistik komputasi sebagai bagian pengantar ilmu komputer ilmiah dan sebagai kemungkinan bidang penerapan studi ini. Latar belakang metodologi ini disajikan di bawah ini.

  1.1. informatika ilmiah

  Carniadax dan Kirby II mendefinisikan "Informatika Komputer sebagai `jantung` penelitian simulasi." Penulis menawarkan “pendekatan holistik untuk algoritma numerik, metode pemrograman modern, dan komputasi paralel… Seringkali konsep dan alat serupa seperti itu dipelajari secara berkala di berbagai kursus dan buku teks terkait, dan hubungan di antara keduanya segera menjadi jelas. Kebutuhan untuk mengintegrasikan konsep dan alat biasanya menjadi jelas setelah menyelesaikan kursus, misalnya selama kerja pasca sarjana pertama atau ketika menulis tesis disertasi, sehingga memaksa siswa untuk mensintesis pemahaman tiga bidang independen menjadi satu, untuk memperoleh solusi yang dibutuhkan. Meskipun proses ini tidak diragukan lagi sangat berharga, ini memakan waktu dan, dalam banyak kasus, mungkin tidak menghasilkan kombinasi konsep dan alat yang efektif. Dari sudut pandang pedagogis, untuk meningkatkan pemahaman topik ilmu komputer ilmiah, pendekatan holistik dan terintegrasi dapat merangsang siswa ke beberapa disiplin ilmu sekaligus. Gambar 1 menyajikan definisi ilmu komputer ilmiah sebagai persimpangan matematika numerik, ilmu komputer dan pemodelan.
  

  

  
  Beras. satu. Informatika ilmiah.

  1.2. Konstruktivisme dalam pembelajaran

  Kane dan Kane, dalam penelitian fundamental mereka, mengajukan prinsip-prinsip dasar konstruktivisme dalam pembelajaran. Salah satu yang paling penting bagi kita adalah sebagai berikut: "Otak memproses bagian-bagian dan keseluruhan pada waktu yang sama."

  Dengan demikian, proses pembelajaran yang terorganisir dengan baik menunjukkan detail dan ide yang mendasarinya. Menggunakan pendekatan berbasis simulasi, setelah model simulasi dibuat, tujuan penelitian menjadi jelas. Hal ini memungkinkan kita untuk mengamati hasil dan menarik kesimpulan yang tepat.

  1.3. Pembelajaran Berbasis Simulasi: Mengapa Model?

  Gibbons memperkenalkan program pelatihan berbasis simulasi pada tahun 2001. Menyoroti prinsip-prinsip dasar berikut:
  • Pelajar memperoleh pengalaman dengan berinteraksi dengan model;
  • Siswa memecahkan masalah ilmiah dan rekayasa dengan bereksperimen dengan model;
  • Pertimbangan dan perumusan masalah;
  • Definisi tujuan pembelajaran tertentu;
  • Menyajikan semua informasi yang diperlukan dalam konteks keputusan.
  Millard dkk mengajukan model pembelajaran terfasilitasi dengan menggunakan “simulasi interaktif”. Para penulis menyajikan teknologi komputer modern berdasarkan "metodologi yang menjanjikan" berdasarkan "dinamika sistem". “Pengalaman praktis termasuk membangun model interaktif … dan menggunakannya untuk menguji hipotesis dan eksperimen.”

  Lehrer dan Schauble fokus pada eksperimen dengan representasi model yang berbeda: "Pembelajaran siswa ditingkatkan ketika siswa memiliki kesempatan untuk membuat dan merevisi beberapa versi model, dan kemudian membandingkan kecukupan deskripsi model yang berbeda ini."

  1.4. Informatika ilmiah di jantung pendidikan: eksperimen dengan model

  Xue mengusulkan "reformasi pengajaran dalam pembelajaran 'informatika ilmiah' melalui pemodelan dan simulasi." Dia menyarankan "... untuk menggunakan pemodelan dan simulasi untuk memecahkan masalah aktual pemrograman, pemodelan dan analisis data ...". Pembelajaran berbasis pemodelan digunakan dalam pendidikan matematika. Banyak model dibangun menggunakan perangkat lunak Geogebra. Model memainkan peran utama dalam Pendidikan Sains.

  1.5. Pemodelan stokastik sistem antrian

  Kami menyarankan penggunaan sistem antrian karena kesederhanaan definisi awal mereka dan karena kemungkinan pemodelan dan simulasi yang luas. Teori antrian sudah dikenal luas dan pemodelan sistem antrian (QS) banyak digunakan dalam ilmu pengetahuan dan pendidikan. Sistem antrian multi-fase adalah platform yang baik untuk eksperimen siswa, seperti halnya penggunaan komputasi paralel. Ada juga sejumlah hasil teoritis yang menarik untuk studi dan penelitian.

  1.6. Python dalam pendidikan berdasarkan ilmu komputer ilmiah

  Python adalah salah satu bahasa pemrograman paling populer bagi para ilmuwan dan pendidik. Python banyak digunakan dalam komputasi ilmiah industri. Langtangen melaporkan pengalaman jangka panjang menggunakan Python sebagai bahasa utama untuk mengajar Ilmu Komputer di Universitas Oslo. Python sedang dipromosikan sebagai bahasa pertama untuk belajar pemrograman, serta untuk studi lanjutan dari metode komputasi.

  2. Dasar-dasar

  Sebelum memulai pemodelan, mari kita tentukan pendekatan utama yang akan kita gunakan dalam proses. Dalam bab ini, kita akan menyentuh generasi bilangan acak dan distribusi probabilitas, pemodelan stokastik. Pertimbangkan teori probabilitas dasar. Tugas utama eksperimen ini adalah pembuktian eksperimen Teorema Limit Pusat. Model dan eksperimen dengan model ini memperjelas prinsip pembangkit bilangan pseudo-acak dan kuasi-acak, serta memahami distribusi eksponensial. Ini dapat memberikan dasar untuk eksperimen yang lebih rinci dengan model QS.

  2.1. Variabel acak dan distribusi

  Semua elemen teori probabilitas secara tradisional dianggap sulit untuk dipahami dan selalu menjadi perhatian lembaga pendidikan internasional. Pada saat yang sama, pertanyaan-pertanyaan ini memainkan peran penting dalam penelitian ilmiah. Pendekatan pemodelan membuat materi ini lebih mudah dipahami. Model yang akan kita lihat dalam artikel ini adalah model melempar satu dadu atau lebih, dimulai dengan satu dan diakhiri dengan beberapa.

  Tugas eksperimen pendahuluan ini agak rumit. Kami tidak hanya akan melihat distribusi probabilitas, tetapi juga menyentuh pemodelan dan komputasi paralel. Kami juga akan mengambil satu langkah maju dalam penelitian ilmiah: kami akan membuktikan secara eksperimental Teorema Batas Pusat.

  Kami akan mulai dengan menghasilkan angka acak (tanpa mempengaruhi distribusi). Kemudian kami menjelaskan variabel acak terdistribusi seragam. Diskusi tentang keacakan sejati dan keacakan semu disajikan oleh penulis. Untuk pelajar tingkat lanjut, serangkaian eksperimen dengan generator pseudo-acak Python akan disajikan. Pada tahap awal, untuk kejelasan studi, kami akan menambah jumlah tes dengan mengamati hasil simulasi. Pada langkah selanjutnya, kita akan beralih ke eksperimen yang lebih kompleks dan komputasi paralel. Kami akan menggunakan modul variabel acak Python untuk pemodelan, dan pustaka mpi4py untuk komputasi paralel. Modul Acak Python didasarkan pada generator nomor pseudo-acak untuk berbagai distribusi. Sebagai contoh: acak.randint(a,b) mengembalikan bilangan bulat acak N di mana a N b dan random.expovariate(lambd) mengembalikan variabel acak yang terdistribusi secara eksponensial dengan parameter 'lambd'. Lihat dokumentasi Python untuk lebih jelasnya. Pemrograman model lempar dadu ditunjukkan pada Gambar 2.

  Import pylab import random number_of_trials =100 ## Di sini kita mensimulasikan pelemparan berulang dari satu dadu enam sisi list_of_values ​​= untuk i dalam range(number_of_trials): list_of_values.append(random.randint(1,6)) print "Trials =" , jumlah_percobaan, "kali." print "Rata-rata =", pylab.mean(list_of_values) print "Standar deviasi =", pylab.std(list_of_values) pylab.hist(list_of_values, bins=) pylab.xlabel("Value") pylab.ylabel("Jumlah kali ") pylab.show()
  Beras. 2. Memprogram Model Gulungan Dadu Tunggal dengan Python

  Hasil simulasi pelemparan satu dadu ditunjukkan pada Gambar 3.

  

  
  Beras. 3. Hasil Simulasi Dadu Tunggal

  

  
  Beras. 4. Perbandingan fungsi kepadatan probabilitas

  Proses pembelajaran dilanjutkan dengan memodifikasi kode simulasi pelemparan dua dadu sedemikian rupa sehingga mulai mempertimbangkan kasus dengan dadu berganda. Kodenya mirip dengan kode die tunggal, kecuali dua baris kode di bawah ini:

  List_of_values.append(random.randint(1, 6) + random.randint(1, 6)) ... pylab.hist(list_of_values, pylab.arange(1.5, 13.5, 1.0)) ...
  Hasil perhitungan pada kasus dua kubus ditunjukkan pada Gambar 5.

  

  
  Beras. 5. Kasus dua kubus

  Sekarang kita dapat mempertimbangkan distribusi normal. Tugas pada tahap ini adalah menunjukkan bagaimana kasus sebelumnya dengan beberapa kubus berkorelasi dengan distribusi normal. Masalah berikutnya akan memperkenalkan kita pada mean dan standar deviasi. Kode tetap sama seperti dalam kasus satu dadu, kecuali untuk petunjuk di bawah ini:

  List_of_values.append(random.normalvariate(7, 2.4)) ...
  Hasil simulasi untuk distribusi normal ditunjukkan pada Gambar 6.

  

  
  Beras. 6. Hasil simulasi untuk distribusi normal

  Langkah terakhir adalah mendemonstrasikan distribusi eksponensial. Distribusi eksponensial digunakan untuk memodelkan distribusi (durasi) interval antara saat-saat kedatangan persyaratan dalam sistem dari berbagai jenis. Hasil pemodelan mereka disajikan pada Gambar 7 dan 8.

  Import pylab import random number_of_trials = 1000 number_of_customer_per_hour = 10 ## Di sini kami mensimulasikan waktu antar kedatangan pelanggan list_of_values ​​​​= untuk i dalam rentang(jumlah percobaan): list_of_values.append(random.expovariate(number_of_customer_per_hour)) mean=pylab. mean( list_of_values) std=pylab.std(list_of_values) print "Trials =", number_of_trials, "times" print "Mean =", mean print "Standar deviasi =", std pylab.hist(list_of_values,20) pylab.xlabel( "Nilai") pylab.ylabel("Jumlah waktu") pylab.show()
  Beras. 7. Model Python untuk Distribusi Eksponensial

  

  
  Beras. delapan. Hasil simulasi untuk distribusi eksponensial

  2.2. Simulasi stokastik

  Pemodelan stokastik adalah elemen penting dari informatika ilmiah. Kami akan fokus pada metode Monte Carlo. Setelah model dibangun, kita dapat menghasilkan variabel acak dan bereksperimen dengan berbagai parameter sistem. Dalam kerangka artikel ini, poin kunci dari eksperimen Monte Carlo adalah mengulang pengujian berkali-kali untuk mengumpulkan dan mengintegrasikan hasilnya. Aplikasi paling sederhana telah dijelaskan di bagian sebelumnya. Dengan meningkatkan jumlah tes, kami akan meningkatkan akurasi hasil simulasi.

  Di sini siswa harus melakukan sejumlah percobaan menggunakan model sederhana ini dengan meningkatkan jumlah percobaan. Dengan menambah jumlah kubus dan jumlah percobaan, siswa akan mengalami waktu komputasi yang relatif lama. Ini adalah alasan yang bagus untuk menggunakan komputasi paralel. Model Python untuk beberapa dadu ditunjukkan pada Gambar 9. Dan hasil simulasi ditunjukkan pada Gambar 10. Langkah selanjutnya adalah mempertimbangkan masalah yang lebih umum terkait dengan berbagai sistem antrian. Pengantar singkat tentang klasifikasi QS disajikan di bagian selanjutnya dari artikel ini. Mari kita mulai dengan sistem M/M/1 dan sistem antrian yang lebih kompleks. Konsep dasar proses stokastik akan dibahas secara rinci di bagian artikel ini. Sebagai contoh yang mungkin, kita dapat mengusulkan masalah mempelajari aliran keluaran. Mari kita buktikan bahwa keluaran M/M/1 dari sistem adalah aliran Poisson. Dengan demikian, data yang terkumpul akan disajikan dalam bentuk histogram empiris keluaran yang dibangun.

  Import pylab import random number_of_trials = 150000 number_of_dice = 200 ## Di sini kita mensimulasikan pelemparan berulang ## dari sejumlah dadu bersisi enam list_of_values ​​​​= untuk i dalam range(number_of_trials): sum=0 untuk j dalam range(number_of_dice ): sum+=random.randint(1,6) list_of_values.append(sum) mean=pylab.mean(list_of_values) std=pylab.std(list_of_values) print "Trials =", number_of_trials, "times" print "Mean =" , mean print "Standar deviasi =", std pylab.hist(list_of_values,20) pylab.xlabel("Value") pylab.ylabel("Number of times") pylab.show()
  Beras. sembilan. Model Simulasi Python untuk Distribusi Normal Tertambah

  

  
  Beras. sepuluh. Hasil simulasi untuk distribusi normal diperpanjang

  3. Sistem antrian multifase dan pemodelan stokastik

  Di bawah ini adalah deskripsi pengantar QS, dengan mempertimbangkan nuansa pemodelan dan stokastik.

  3.1. Sistem Antrian

  Sistem antrian sederhana terdiri dari satu server yang memproses permintaan yang masuk. Skema umum sistem antrian sederhana ditunjukkan pada Gambar 11. Secara umum, sebuah QS terdiri dari satu atau lebih server yang memproses permintaan masuk. Dimungkinkan juga untuk memiliki satu atau lebih langkah layanan dengan satu atau lebih perangkat layanan di setiap fase. Klien masuk yang mendapati semua server sibuk bergabung dengan satu atau lebih antrian di depan perangkat yang melayani. Ada banyak aplikasi yang dapat digunakan untuk memodelkan QS, seperti sistem produksi, sistem komunikasi, sistem pemeliharaan, dan lain-lain. QS umum dapat dicirikan oleh tiga komponen utama: aliran permintaan, proses layanan, dan metode antrian. Aplikasi dapat berasal dari beberapa sumber terbatas atau tidak terbatas.

  

  
  Beras. sebelas. CMO sederhana.

  Proses ticketing menjelaskan bagaimana tiket masuk ke dalam sistem. Mari kita definisikan
  sebagai interval waktu antara kedatangan klaim antara dan klaim ke-, waktu yang diharapkan (rata-rata) antara kedatangan klaim serta frekuensi penerimaan klaim sebagai

  Kami juga mendefinisikan sebagai jumlah perangkat layanan. Mekanisme layanan ditentukan oleh nomor ini. Setiap server memiliki antrian sendiri, serta distribusi probabilistik dari waktu layanan permintaan.

  Mari kita definisikan sebagai waktu layanan dari permintaan ke-, sebagai waktu rata-rata untuk melayani permintaan, dan sebagai kecepatan melayani permintaan.

  Aturan yang digunakan server untuk memilih permintaan berikutnya dari antrian disebut disiplin antrian QS. Disiplin antrian yang paling umum adalah: Prioritas - pelanggan dilayani dalam urutan kepentingan mereka. FIFO - pertama datang pertama dilayani; LIFO - tumpukan, terakhir datang pertama dilayani. Klasifikasi diperpanjang sistem menurut Kendall menggunakan 6 simbol: A/B/s/q/c/p, di mana A adalah distribusi interval antara permintaan yang masuk, B adalah distribusi interval layanan, s adalah jumlah server, q adalah disiplin layanan (dihilangkan untuk FIFO), c – kapasitas sistem (dihilangkan untuk antrian tak terbatas), p – jumlah permintaan yang mungkin (dihilangkan untuk sistem terbuka) . Misalnya, M/M/1 menjelaskan aliran input Poisson, satu server eksponensial, satu antrian FIFO tak terhingga, dan jumlah pelanggan tak terhingga.

  QS digunakan untuk memodelkan dan mempelajari berbagai bidang ilmu pengetahuan dan teknologi. Misalnya, kita dapat memodelkan dan mempelajari sistem produksi atau transportasi menggunakan teori antrian. Selain itu, permintaan layanan dianggap sebagai aplikasi, dan prosedur pemeliharaan sebagai mekanisme layanan. Contoh berikutnya adalah: komputer (permintaan terminal dan respons server, masing-masing), sistem memori multi-disk komputer (permintaan untuk menulis / membaca data, pengontrol disk umum), komunikasi radio berbatang (sinyal telepon, repeater), jaringan komputer (permintaan , saluran). Dalam biologi, teori antrian dapat digunakan untuk memodelkan sistem enzim (protein, enzim umum). Dalam biokimia, model jaringan antrian dapat digunakan untuk mempelajari rantai regulasi operon LAK.

  3.2. Mengapa multifase?

  Pertimbangkan QS multi-fase, yang terdiri dari beberapa server yang terhubung secara seri dan memiliki jumlah permintaan yang tidak terbatas. Waktu antara permintaan dan waktu pemrosesan adalah independen dan terdistribusi secara eksponensial. Antrian tidak terbatas dengan disiplin layanan FIFO. QS multifase secara alami mencerminkan topologi sistem komputer multicore. Seperti yang akan kita lihat nanti, setiap model dapat dengan mudah ditulis dalam bahasa pemrograman, dipelajari dan dimodifikasi. Model ini juga memungkinkan studi komparatif dari berbagai pendekatan untuk multiprocessing. Model QS multifase ditunjukkan pada Gambar 12.

  

  
  Beras. 12. Multifase QS.

  3.3. Landasan teori

  Dalam hal pemodelan statistik, kita selalu menghadapi masalah verifikasi kode komputer. Selalu ada pertanyaan terbuka tentang kesalahan dalam program atau algoritme kami. Modelnya tidak sepenuhnya analitis dan setiap kali kita menjalankan program, kita memiliki data input/output yang berbeda. Jadi, untuk memeriksa kebenaran kode atau algoritme, diperlukan pendekatan yang berbeda (dari yang kami gunakan dalam kasus data input yang sepenuhnya deterministik). Untuk mengatasi masalah ini, kita harus menerapkan hasil teoretis dari beberapa penelitian yang dapat ditemukan dalam literatur ilmiah. Hasil ini memberi kami dasar untuk memverifikasi dan menganalisis data keluaran, serta untuk memecahkan masalah kebenaran hasil simulasi.

  Kami akan menyelidiki waktu tinggal klaim dalam QS multifase. Dilambangkan sebagai waktu tinggal permintaan dalam sistem, sebagai waktu layanan n-aplikasi j fase -th. Pertimbangkan caranya k fase -th.

  Ada konstanta sedemikian sehingga

  Dalil. Jika kondisi (1) dan (2) terpenuhi, maka

  3.4. Pemodelan statistik

  Setelah model dibangun, kita bisa menjalankan serangkaian eksperimen dengan model ini. Ini akan memungkinkan Anda untuk mempelajari beberapa karakteristik sistem. Kita dapat memancarkan variabel acak dengan mean yang diharapkan dan menghitung (menggunakan persamaan rekursif di bawah) nilai yang diinginkan untuk dipelajari. Nilai-nilai ini juga akan acak (kami memiliki stokastik dari data input model kami - waktu acak antara kedatangan permintaan dan waktu layanan acak). Akibatnya, kita dapat menghitung beberapa parameter dari variabel acak (variabel): nilai rata-rata dan distribusi probabilitas. Kami menyebut metode ini pemodelan statistik karena keacakan yang ada dalam model. Jika diperlukan hasil yang lebih akurat, kita harus mengulangi percobaan dengan model kita dan kemudian mengintegrasikan hasilnya, kemudian menghitung karakteristik integral: nilai rata-rata atau simpangan baku. Ini disebut metode Monte Carlo dan dijelaskan dalam artikel sedikit lebih tinggi.

  3.5. persamaan berulang

  Untuk mengembangkan algoritma untuk pemodelan QS yang dijelaskan sebelumnya, perlu untuk menganalisis beberapa konstruksi matematis. Tugas utama mempelajari dan menghitung waktu tinggal permintaan dengan nomor n dalam QS multi fase yang terdiri dari fase. Kita dapat memberikan persamaan rekursif berikut , menunjukkan: - waktu kedatangan orde -th; sebagai waktu layanan klaim -th fase -th; . Persamaan rekursif berikut berlaku untuk waktu tunggu orde ke-th dari fase ke-th:
  

  Anggapan. Persamaan rekursif untuk menghitung waktu tinggal aplikasi dalam QS multifase.

  Bukti. Benar bahwa jika waktunya , maka waktu tunggu pada fase -th dari orde -th adalah 0. Dalam hal ini, , waktu tunggu pada fase -th dari order -th dan . Mempertimbangkan dua kasus di atas, kami akhirnya mendapatkan hasil yang diinginkan.

  Sekarang kita dapat mulai menerapkan algoritma yang diperlukan berdasarkan semua hasil teoretis yang diperoleh.

  4. Python untuk multiprosesor

  Python sebagai bahasa pemrograman sangat populer di kalangan ilmuwan dan pendidik dan bisa sangat menarik untuk memecahkan masalah yang berorientasi pada sains. Python menyediakan platform yang kuat untuk pemodelan dan simulasi, termasuk utilitas grafis, berbagai macam paket matematika, statistik, dan multiprosesor. Untuk mengurangi waktu eksekusi, perlu untuk menggabungkan kode Python dan C. Semua ini memberi kami platform pemodelan yang kuat untuk memperoleh data statistik dan hasil pemrosesan. Konsep kunci dalam Python yang juga penting dalam pemodelan adalah dekorator, coroutine, ekspresi hasil, multiprosesor, dan antrian. Poin-poin ini dipertimbangkan dengan sangat baik oleh Beasley dalam bukunya. Meskipun demikian, ada beberapa cara untuk mengatur komunikasi antar proses, dan kami akan mulai dengan penggunaan antrian, karena ini sangat wajar mengingat mempelajari QS.

  Di bawah ini adalah contoh sederhana dari manfaat menggunakan multiprocessing untuk meningkatkan efisiensi dan efektivitas kode. Siswa dapat meningkatkan hasil simulasi dengan menggunakan komputasi paralel pada superkomputer atau sistem cluster. Di satu sisi, multiprosesor akan memungkinkan kita untuk mencocokkan model multifase dengan sumber daya prosesor multi-inti, dan di sisi lain, kita dapat menggunakan multiproses untuk melakukan serangkaian tes Monte Carlo paralel. Kita akan melihat kedua pendekatan ini di bagian selanjutnya. Untuk pelajar yang termotivasi, berikut adalah pengantar singkat untuk multiprosesing dengan Python.

  Kita akan mulai dengan menggunakan modul mpi4py. Hal ini penting untuk mempresentasikan ide pokok cara kerja MPI. Ini hanya menyalin program yang disediakan ke salah satu inti prosesor yang ditentukan pengguna dan mengintegrasikan hasilnya setelah menggunakan metode kumpulkan (). Contoh kode Python (Gbr. 13) dan hasil simulasi (Gbr. 14) disajikan di bawah ini.

  #!/usr/bin/python import pylab import random import numpy as np from mpi4py import MPI dice=200 percobaan= 150000 rank = MPI.COMM_WORLD.Get_rank() size = MPI.COMM WORLD.Get_size() name = MPI.Get_processor_name () random.seed(rank) ## Setiap proses - satu kali pelemparan sejumlah dadu bersisi enam nilai= np.zeros(trials) untuk i dalam range(trials): sum=0 untuk j dalam range(dadu): jumlah+=random.randint(l,6) nilai[i]=jumlah data=np.array(MPI.COMM_WORLD.gather(nilai, root=0)) jika peringkat == 0: data=data.flatten() mean= pylab.mean(data) std=pylab.std(data) print "Jumlah percobaan =", ukuran* percobaan, "kali." print "Mean =", mean print "Standar deviasi =", std pylab.hist(data,20) pylab.xlabel("Value") pylab.ylabel("Number of times") pylab.savefig("multi_dice_mpi.png" )
  Beras. tigabelas. Model Python untuk distribusi normal diperpanjang menggunakan MPI.

  

  
  Beras. empat belas. Distribusi normal menggunakan MPI.

  5. Pendekatan pendidikan berbasis simulasi

  QS multifase memberi kami inti untuk mengembangkan pendekatan berbasis simulasi yang sesuai. Pendekatan ini mencakup konsep dasar yang dijelaskan pada bagian sebelumnya, serta hasil dan metode teoretis yang lebih kompleks. Ide-ide utamanya adalah stokastik di alam: variabel acak, distribusi numerik acak, generator nomor acak, Teorema Batas Tengah; Konstruksi pemrograman python:
  dekorator, coroutine, dan ekspresi hasil. Hasil yang lebih kompleks mencakup konsep teoretis berikut: waktu yang dihabiskan oleh klaim dalam sistem, persamaan rekursif untuk menghitung waktu yang dihabiskan oleh klaim dalam QS, metode pemodelan stokastik, dan teknologi multiprosesor. Gambar 15 menunjukkan diagram utama yang menggambarkan kerangka pendidikan.

  

  
  Beras. limabelas. Pendekatan Pendidikan Berbasis Simulasi

  Semua struktur teoritis dan program ini memungkinkan siswa untuk bereksperimen dengan berbagai model QS multi-fase. Tujuan dari eksperimen ini ada dua. Pertama, membuat siswa memahami urutan berikut, yang penting dalam setiap penelitian ilmiah: fakta teoritis yang diperlukan untuk belajar, model matematika, struktur program, model komputer, model stokastik dan pengamatan hasil simulasi. Ini akan memberi siswa gambaran lengkap tentang penelitian ilmiah umum (Gambar 16).

  

  
  Beras. enambelas. Area penelitian

  Pendekatan ini akan memungkinkan pemahaman yang lebih dalam tentang pemodelan stokastik dan konstruksi perangkat lunak dasar seperti multiprocessing dan pemrograman paralel. Ketentuan ini sangat penting dalam bidang komputasi ilmiah.

  5.1. Eksperimen Model

  Pada bagian ini, kami mempertimbangkan tiga model komputer QS multifase. Semua model ini berbeda dalam fitur filosofis dan kuncinya. Terlepas dari kenyataan bahwa tujuan percobaan adalah untuk membuat model statistik dan mempelajari parameter utama sistem multifase, ide konseptual dari model ini sama sekali berbeda. Membandingkan ide-ide dasar ini akan membantu siswa memahami konsep dasar yang mendasari komputasi paralel, pemodelan statistik dan simulasi multiprosesor.

  Model pertama yang kami hadirkan didasarkan pada perekaman real-time dan kami menyebutnya model simulasi. Ini menggunakan modul multiprosesor Python. Keakuratan model ini bergantung pada akurasi dan resolusi metode time(). Ini bisa sangat rendah dalam kasus berbagai sistem operasi tujuan umum, dan cukup tinggi dalam kasus sistem waktu nyata. Siswa dapat memodifikasi model ini menggunakan persamaan rekursif yang diusulkan sebelumnya (untuk menghitung waktu yang dihabiskan oleh entitas dalam sistem) dan membandingkan hasilnya dalam kedua kasus.

  Model berikut menghitung waktu tinggal pesanan dalam sistem dan didasarkan pada simulasi stokastik. Model tidak menggunakan multiprocessing secara langsung. Multiprocessing ditiru menggunakan hasil dalam ekspresi Python.

  Model terbaru disajikan di sini menggunakan modul mpi4py Python MPI. Di sini kami menggunakan pendekatan MPI (multiprosesor) nyata untuk pemodelan statistik dan, karena itu, dapat meningkatkan jumlah pengujian dalam metode Monte Carlo.

  Secara umum, tugas mahasiswa adalah membuat rangkaian percobaan dengan model yang disediakan dan memperoleh pembuktian percobaan hukum logaritma iterasi untuk waktu tinggal aplikasi pada multifase QS.

  5.2. Model simulasi menggunakan layanan multiprosesor

  Di bawah ini adalah model simulasi. Pertanyaan utama untuk dipelajari adalah perbedaan antara model simulasi dan model statistik. Isu penting lainnya adalah kebenaran dan akurasi model simulasi. Juga penting adalah pertanyaan tentang kebenaran dan keakuratan model yang disajikan. Siswa dapat memeriksa dan membandingkan hasil simulasi tergantung pada berbagai parameter seperti interval pemrosesan dan frekuensi, jumlah permintaan, dan jumlah node yang melayani. Skema umum model ditunjukkan pada Gambar 17.

  

  
  Beras. 17. model simulasi

  Kode Program Kode terdiri dari dua bagian utama. Yang pertama ditujukan langsung untuk perhitungan, dan yang berikutnya untuk memplot hasil. Modul kalkulasi berisi tiga fungsi utama: produser() - untuk menerima permintaan dan menempatkannya di tempat pertama; server() - untuk permintaan servis; konsumen() - untuk mendapatkan hasil. Model pemrograman ini didasarkan pada simulasi nyata dan tidak menggunakan ekspresi matematika untuk perhitungan. Keakuratannya tergantung pada keakuratan modul sementara Python dan umumnya bergantung pada sistem operasi. Perhitungan kerja perangkat layanan didistribusikan di antara berbagai proses dalam sistem multiprosesor. Kode komputer untuk implementasi model di atas ditunjukkan pada Gambar 18.

  Import multiprocessing import time import random import numpy as np def server(input_q,next_q,i): while True: item = input_q.get() if i==0:item.st=time.time() ## mulai merekam waktu ## (fase pertama) timc.sleep(random.expovariate(glambda|i])) ##stop waktu perekaman (fase terakhir) jika i==M-1:item.st=time.time()-item.st next_q.put(item) input_q.task_done() print("Server%d stop" % i) ##tidak akan pernah dicetak mengapa? def producer(sequence,output_q): untuk item dalam urutan: time.sleep(random.expovariate(glambda)) output_q.put(ilem) def consumer(input_q): "Prosedur penyelesaian" ## mulai merekam waktu pemrosesan ptime=waktu. time() in_seq= while True: item = input_q.get() in_scq+= input_q.task_done() if item.cid == N-1: break print_results(in_seq) print("END") print("Waktu pemrosesan detik. %d" %(time.time()-ptime)) ## berhenti merekam waktu pemrosesan printf("CPU digunakan %d" %(multiprocessing.cpu_count())) def print_resulls(in_seq): "Hasil keluaran" f=buka ("out.txt","w") f.write("%d\n" % N) untuk l dalam rentang(M): f.write("%d%s" % (glambda[t]," ,")) f.write("%d\n" % glambda[M]) untuk t dalam rentang(N-1): f.write("%f%s" % (in_seq[t].st," ,")) f.write("%f\n" % (in_seq.st)) f.close() class Klien(objek): "Klien kelas" def __init__(self,cid,st): self.cid= cid ## id pelanggan self.st=st ## waktu tinggal pelanggan ###GLOBALS N=100 ## jumlah total pelanggan yang tiba M=5 ## jumlah server ### glambda - kedatangan + frekuensi layanan ### = pelanggan/per unit waktu glambda=np.array(+) ###START if __name__ == "__main__": all_clients= q= for i in range(M): serv = multiprocessing.Process(target=server,args=(q[i],q,i)) serv.daemon=Benar serv.start() cons = multiprocessing.Process(target=consumer,args=(q[M] ,)) cons.start() ### mulai "memproduksi" pelanggan produser(all_clients,q) untuk i in q: i.join()
  Beras. delapan belas. Kode python untuk model simulasi menggunakan layanan multiprosesor.

  Pertanyaan untuk dipelajari:

  • Bagaimana variabel global disediakan dan dibagikan di antara proses?
  • Bagaimana cara menghentikan proses yang terkait dengan berbagai perangkat layanan?
  • Bagaimana arus informasi ditransmisikan antara proses yang berbeda?
  • Bagaimana dengan kebenaran model?
  • Bagaimana dengan efisiensi model. Berapa lama waktu yang dibutuhkan untuk berbagai proses untuk bertukar informasi?
  Kami sekarang dapat mencetak hasilnya menggunakan modul matplotlib dan dapat menganalisis hasilnya secara visual setelah memberikan grafik. Kita dapat melihat (Gambar 19) bahwa model tersebut perlu perbaikan lebih lanjut. Dengan demikian, kita dapat beralih ke model yang lebih kuat.

  

  
  Beras. sembilan belas. Hasil simulasi model simulasi layanan multiprosesor.

  5.3. Model statistik proses unit

  Fitur utama dari model statistik adalah sebagai berikut: sekarang kami menggunakan persamaan rekursif untuk secara akurat menghitung waktu yang dihabiskan oleh pesanan dalam sistem; kami memproses semua data dalam satu proses menggunakan fungsi coroutine Python tertentu; kami melakukan sejumlah simulasi Monte Carlo untuk keandalan perhitungan yang lebih baik. Model ini memberi kita perhitungan "tepat" dari waktu yang dihabiskan pesanan dalam sistem. Diagram utama model ditunjukkan pada Gambar 20. Siswa dapat mengeksplorasi perbedaan antara model simulasi dan model statistik.

  

  
  Beras. 20. Model statistik proses unit

  Kode program untuk implementasi model di atas ditunjukkan pada Gambar 21. Hasil simulasi ditunjukkan pada Gambar 22.

  #!/usr/bin/python import random import time import numpy as np from numpy import linspace def coroutine(func): del start(*args,**kwargs): g = func(*args,**kwargs) g. next() return g return start def print_header(): "Hasil keluaran - header" f=open("out.txt","w") f.write("%d\n" % N) ##jumlah poin dalam pencetakan template f.write("%d\n" % TMPN) untuk t dalam range(M): f.write("%d%s" % (glambda[t],",")) f.write( "%d\n" % glambda[M]) f.close() def print_results(in_seq): "Output rezults" f=open("out.txt","a") k=() for i in range( N-2): if in_seq[i].cid==template[k]: f.write("%f%s" % (in_seq[i].st,",")) k+=1 f.write( "%f\n" % (in_seq.st)) f.close() coroutine def server(i): ST=0 ##waktu tinggal untuk klien sebelumnya item=Tidak ada saat Benar: item = (item hasil) ## dapatkan item jika item == Tidak ada: ##new Monte Carlo iterasi ST=0 lanjutkan waiting_time=max(0.0,ST-item.st-item.tau) item.st+=random.expovariate(glambda)+waiting_time ST=item. st def produser(): hasil= i=0 sementara Benar : if i == N: break c=Client(i,0.,0.) if i!=0: c.tau=random.expovariate(glambda) i+= 1 for s in p: c=s.send( c) hasil+=[c] untuk s di p: c=s.send(None) ## sinyal akhir mengembalikan kelas hasil Klien(objek): def __init__(self,cid,st,tau): self.cid=cid self .st=st self.tau=tau def params(self): return (self.cid,self.st,self.tau) stt=time.time() N=1000000 ## Klien M=5 ## Server ## Frekuensi input/layanan glambda= + MKS=20 ## Hasil simulasi Monte Carlo ## Jumlah poin dalam template pencetakan TMPN=N/10000 ##templat pencetakan template= peta(int,linspace(0,N-1,TMPN) ) print_header() p= untuk i dalam jangkauan(M):p += untuk i dalam jangkauan! MKS): print_results(producer()) print("Langkah=%d" % i) sys.stdout.write("Waktu pemrosesan:%d\n" % int(time.time()-stt))
  Beras. 21. Kode python untuk model statistik proses unit

  

  
  Beras. 22. Hasil simulasi untuk proses unit model statistik

  5.4. Model statistik pada MPI

  Langkah selanjutnya dalam pengembangan model kami adalah penggunaan modul Python MPI - mpi4py. Ini memungkinkan kami untuk menjalankan lebih banyak simulasi Monte Carlo dan menggunakan cluster untuk menjalankan dan menguji model. Langkah selanjutnya adalah perbaikan lebih lanjut dari model yang didasarkan pada penggunaan bahasa pemrograman C, teknologi MPI atau SWIG (https://ru.wikipedia.org/wiki/SWIG) “asli” untuk Python. Model ini hampir identik dengan model sebelumnya, dengan satu-satunya perbedaan adalah bahwa mpi4py digunakan untuk multiprocessing dan integrasi hasil (Gambar 23).

  

  
  Beras. 23. Model statistik MPI

  Selain model sebelumnya, beberapa modul tambahan harus diimpor. Fungsi print_results() juga perlu ditulis ulang karena kami memiliki lebih banyak pengujian pada tahap ini. Kita juga harus menulis ulang bagian utama dari program. Pada Gambar 24, kami hanya menyediakan bagian kode yang berbeda dari kode model sebelumnya. Hasil simulasi ditunjukkan pada Gambar 25.

  Impor sistem dari mpi4py impor MPI .................... def print_results(in_seq): "Output rezults" f=open("out.txt","a") untuk m dalam rentang(int(ukuran)): untuk j dalam rentang(MKS): untuk i dalam rentang(TMPN-l): f.write("%f%s" % (in_seq[m].st,", ")) f.write("%f\n" % (in_seq[m][(TMPN-l)+j*TMPN].st)) f.close() ........... ......... stt=time.time() #waktu mulai untuk peringkat proses = MPI.COMM_WORLD.Get_rank() size = MPI.COMM_WORLD.Get_size() name = MPI.Get_processor_name() N= 10 **3 ## Klien M=5 ## Server ## Frekuensi input/layanan glambda=+ ## Jumlah simulasi Monte-Carlo untuk proses particuar ini MKS=20 TMPN=200 ## Jumlah poin dalam pencetakan template template= peta (int,linspace(0,N-1,TMPN)) ## poin untuk mencetak p= hasil= ## proses ini menghasilkan total_results= ## hasil keseluruhan untuk i dalam rentang(M):p += untuk i dalam rentang( MKS):results+=producer() total_results=MPI.COMM_WORLD.gather(results,0) random.seed(rank) jika rank == 0: print_header() print_results(total_results) sys.stdout.write("Proses ng waktu: %d\n" % int(time.time()-stt))
  Beras. 24. Kode python untuk model statistik berdasarkan MPI

  

  
  Beras. 25. Hasil simulasi model statistik MPI

  6. Kesimpulan

  Dalam artikel ini, beberapa model pembelajaran berbasis simulasi telah dipertimbangkan. Model-model ini memungkinkan siswa untuk melakukan serangkaian eksperimen dan meningkatkan pemahaman tentang disiplin Ilmu Komputer Ilmiah. Ada beberapa tingkat kompleksitas model yang disajikan dan eksperimen dengan model tersebut. Tingkat pertama adalah dasar. Ini membawa kita pada pemahaman tentang variabel acak, dan juga memberi kita pemahaman utama tentang bidang penelitian ilmiah. Tingkat selanjutnya lebih maju dan memberikan pemahaman yang lebih dalam tentang pemrograman paralel dan simulasi stokastik. Pengetahuan teoritis yang relevan disajikan, dan, jika perlu, dapat digunakan sebagai bahan tambahan. Semua ini menyediakan perangkat dasar untuk pengenalan Ilmu Komputer Ilmiah. Akhirnya, kami ingin membuat rekomendasi untuk studi lebih lanjut dan perbaikan model.

  6.1. Linearitas Model dan Parameter Statistik QS

  Model QS multifase yang disajikan dalam artikel ini tidak linier. Ini menjadi jelas dari persamaan rekursif, karena mengandung fungsi matematika non-linier maks. Jika kita ingin mendapatkan hasil simulasi yang benar, khususnya dalam hal penghitungan parameter statistik QS, kita harus menggunakan model linear parsial untuk perhitungannya. Ini sangat penting untuk sistem transportasi tanpa muatan, karena jika tidak, kita bisa mendapatkan perbedaan kesalahan yang agak besar dalam perhitungan.

  6.2. Ekstensi Modul Python dan Pemrograman C Paralel

  Untuk pelajar yang terampil, mungkin menarik untuk terus meningkatkan efisiensi kode. Ini dapat dilakukan dengan memperluas modul Python dengan fungsi C yang diimplementasikan menggunakan teknologi SWING. Hal ini dimungkinkan untuk meningkatkan perhitungan kode dan mempercepat perhitungan menggunakan Cython, bahasa pemrograman C, teknologi MPI "nyata" dan HTC (komputasi kinerja tinggi) dalam sistem cluster.

  6.3. Efisiensi solusi perangkat lunak dan pengembangan lebih lanjut

  Pada bagian ini, siswa dapat mengeksplorasi efektivitas berbagai solusi perangkat lunak. Topik ini penting untuk model pemrograman apa pun yang didasarkan pada komputasi paralel. Siswa dapat mempelajari efektivitas berbagai model pemrograman dan mencoba untuk meningkatkan algoritma langkah demi langkah. Poin kuncinya di sini adalah mempelajari rasio jumlah arus informasi dan perhitungan untuk berbagai proses perangkat lunak. Jadi rasio ini penting dalam membangun pengembangan program yang paling efisien dengan komputasi paralel. Topik menarik lainnya adalah studi tentang kemungkinan mengubah struktur algoritmik menjadi struktur HTC yang terkelompok.

  Sebagai tugas tambahan untuk penelitian, penulis mempertimbangkan pemodelan QS, yang harus dimodelkan dan dianalisis. Sifat QS yang relatif kompleks dan jenis aplikasi yang sesuai memerlukan penggunaan teknik pemrograman yang lebih ekstensif. Ini menyediakan platform dasar yang baik untuk mengimplementasikan konsep pemrograman umum seperti pewarisan, enkapsulasi, dan polimorfisme. Di sisi lain, konsep teoritis dasar ilmu komputer juga perlu dibahas. Di atas semua ini, pemodelan statistik dan simulasi QS membutuhkan pengetahuan teori probabilitas yang lebih maju, penggunaan lebih banyak sumber daya komputasi dan penyediaan lingkungan komputasi ilmiah yang nyata, serta motivasi yang baik untuk siswa tingkat lanjut.

  literatur

  Daftar referensi lengkap

  A. Arazi, E. Ben-Jacob dan U. Yechiali, Menjembatani jaringan genetik dan teori antrian, Physica A: Mekanika Statistik dan Aplikasinya 332 (2004), 585–616.
  D.M. Beazley, Referensi Esensial Python, Addison-Wesley Professional, 2009.
  J. Bernard, Gunakan Python untuk komputasi ilmiah, Linux Journal 175 (2008), 7.
  PBB Bhat, Pengantar Pemodelan dan Analisis Teori Antrian dalam Aplikasi, Birkhäuser, Boston, MA, 2008.
  KJ Bogacev, Dasar-dasar Pemrograman Paralel, Binom, Moskow, 2003.
  R.N. Caine dan G. Caine, Membuat Koneksi: Pengajaran dan Otak Manusia, Asosiasi Pengawasan dan Pengembangan Kurikulum, Alexandria, 1991.
  J. Clement dan M.A. Rea, Pembelajaran dan Pengajaran Berbasis Model dalam Sains, Springer, Belanda, 2008.
  N.A. Cookson, W.H. Mather, T. Danino, O. Mondragón- Palomino, R.J. Williams, L.S. Tsimring dan J. Hasty, Antrian untuk pemrosesan enzimatik: pensinyalan berkorelasi melalui degradasi berpasangan, Molecular Systems Biology 7 (2011), 1. A.S. Gibbons, Instruksi yang berpusat pada model, Jurnal Pembelajaran Struktural dan Sistem Cerdas 4 (2001), 511–540. M.T. Heath, Scientific Computing an Introductory Survey, McGraw-Hill, New York, 1997.
  A. Hellander, Simulasi Stochastic dan Metode Monte Carlo, 2009.
  G.I. Ivchenko, V.A. Kastanov dan I.N. Kovalenko, Teori Sistem Antrian, Visshaja Shkola, Moskow, 1982.
  ZL Joel, N.W. Wei, J.Louis dan T.S. Chuan, Diskrit-acara
  simulasi sistem antrian, dalam: Sixth Youth Science Conference, Singapore Ministry of Education, Singapore, 2000, hlm. 1-5.
  E. Jones, Pengantar komputasi ilmiah dengan Python, dalam: SciPy, California Institute of Technology, Pasadena, CA, 2007, p. 333.
  M. Joubert dan P. Andrews, Penelitian dan pengembangan dalam pendidikan probabilitas secara internasional, dalam: Kongres Inggris untuk Pendidikan Matematika, 2010, hal. 41.
  G.E. Karniadakis dan R.M. Kyrby, Komputasi Ilmiah Paralel dalam C++ dan MPI. Pendekatan Mulus untuk Algoritma Paralel dan Implementasinya, Cambridge Univ. pers, 2003.
  D.G. Kendall, proses Stochastic yang terjadi dalam teori antrian dan analisisnya dengan metode rantai Markov tertanam, The Annals of Mathematical Statistics 1 (1953), 338–354.
  NONA. Khine dan I.M. Saleh, Models and Modeling, Cognitive Tools for Scientific Enquiry, in: Models and Modeling in Science Education, Springer, 2011, p. 290.
  T. Kiesling dan T. Krieger, Simulasi sistem antrian paralel yang efisien, dalam: The 38th Conference on Winter Simulation, Winter Simulation Conference, 2006, hlm. 1020–1027.
  J. Kiusalaas, Metode Numerik dalam Rekayasa dengan Python, Cambridge Univ. Pers, 2010.
  A. Kumar, Python untuk Pendidikan. Belajar Matematika & Sains Menggunakan Python dan Menulisnya di LATEX, Inter University Accelerator Centre, New Delhi, 2010.
  HP Langtangen, Python Scripting untuk Ilmu Komputasi, Springer-Verlag, Berlin, 2009.
  HP Langtangen, A Primer tentang Pemrograman Ilmiah dengan Python, Springer-Verlag, Berlin, 2011.
  HP Langtangen, Pengalaman menggunakan Python sebagai bahasa utama untuk mengajar komputasi ilmiah di Universitas Oslo, Universitas Oslo, 2012.
  R. Lehrer dan L. Schauble, Menumbuhkan penalaran berbasis model dalam pendidikan sains, dalam: The Cambridge Handbook of the Learning Sciences, Cambridge Univ. Pers, 2005, hal. 371–388.
  G. Levy, Pengantar bilangan kuasi-acak, dalam: Numerical Algorithms, Group, 2012.
  J.S. Liu, Strategi Monte Carlo dalam Komputasi Ilmiah, Harvard Univ., 2001.
  VE. Malishkin dan V.D. Korneev, Pemrograman Paralel Multikomputer, Novosibirsk Technical Univ., Novosibirsk, 2006.
  N. Matloff, Pemrograman pada Mesin Paralel: GPU, Multi-core, Cluster, dan Lainnya, University of California, 2012.
  M.Milrad, J.M. Spector dan P.I. Davidsen, Model pembelajaran yang difasilitasi, dalam: Desain Instruksional, Pengembangan dan Evaluasi, Syracuse Univ. pers, 2003.
  S. Minkevicius, Tentang hukum logaritma berulang dalam sistem antrian multifase, Informatica II (1997), 367–376.
  S. Minkevicius dan V. Dolgopolovas, Analisis hukum logaritma iterasi untuk waktu idle pelanggan dalam antrian multifase, Int. J. Aplikasi Murni. Matematika. 66 (2011), 183–190.
  Model-Centered Learning, Pathways to matematika understanding using GeoGebra, in: Modeling and Simulations for Learning and Instruction, Sense Publishers, The Netherlands, 2011.
  C.R. Myers dan J.P. Sethna, Python untuk pendidikan: Metode komputasi untuk sistem nonlinier, Computing in Science & Engineering 9 (2007), 75–79.
  H. Niederreiter, Random Number Generation dan Metode Quasi-Monte Carlo, SIAM, 1992.
  F.B. Nilsen, Sistem antrian: Pemodelan, analisis dan simulasi, Departemen Informatika, Universitas Oslo, Oslo, 1998.
  R.P. Sen, Riset Operasi: Algoritma dan Aplikasi, Pembelajaran PHI, 2010. Tambahkan tag

  Rencana:

  1. Konsep teorema limit pusat (teorema Lyapunov)

  2. Hukum bilangan besar, probabilitas dan frekuensi (teorema Chebyshev dan Bernoulli)

  1. Konsep teorema limit pusat.

  Distribusi normal dari probabilitas sangat penting dalam teori probabilitas. Hukum normal mematuhi probabilitas ketika menembak target, dalam pengukuran, dll. Secara khusus, ternyata hukum distribusi untuk jumlah variabel acak independen yang cukup besar dengan hukum distribusi arbitrer mendekati distribusi normal. Fakta ini disebut teorema limit pusat atau teorema Lyapunov.

  Diketahui bahwa variabel acak terdistribusi normal banyak digunakan dalam praktik. Apa yang menjelaskan ini? Pertanyaan ini telah dijawab

  Teorema limit pusat. Jika variabel acak X adalah jumlah dari sejumlah besar variabel acak independen yang saling bebas, pengaruh masing-masing variabel tersebut terhadap jumlah keseluruhan dapat diabaikan, maka X memiliki distribusi yang mendekati distribusi normal.

  Contoh. Biarkan beberapa kuantitas fisik diukur. Setiap pengukuran hanya memberikan nilai perkiraan dari kuantitas yang diukur, karena banyak faktor acak independen (suhu, fluktuasi instrumen, kelembaban, dll.) mempengaruhi hasil pengukuran. Masing-masing faktor ini menghasilkan "kesalahan parsial" yang dapat diabaikan. Namun, karena jumlah faktor ini sangat besar, efek kumulatifnya menghasilkan "kesalahan total" yang sudah terlihat.

  Mengingat kesalahan total sebagai jumlah dari sejumlah besar kesalahan parsial yang saling independen, kita dapat menyimpulkan bahwa kesalahan total memiliki distribusi yang mendekati distribusi normal. Pengalaman menegaskan validitas kesimpulan ini.

  Pertimbangkan kondisi di mana "teorema limit pusat" terpenuhi

  x1,X2, ..., Xn adalah urutan variabel acak independen,

  M(X1),M(X2), ...,M(Xn) adalah harapan matematis akhir dari jumlah ini, masing-masing sama dengan M(Xk)= aku

  D (X1),D(X2), ...,D(Xn) - varians akhir mereka, masing-masing sama dengan D(X k)= bk2

  Kami memperkenalkan notasi: S= X1+X2 + ...+Xn;

  A k= X1+X2 + ...+Xn=; B2=D (X1)+D(X2)+ ...+D(Xn) =

  Kami menulis fungsi distribusi dari jumlah yang dinormalisasi:

  Mereka mengatakan ke urutan x1,X2, ..., Xn teorema limit pusat berlaku jika, untuk sembarang x fungsi distribusi jumlah ternormalisasi sebagai n ® cenderung ke fungsi distribusi normal:

  Kanan "style="border-collapse:collapse;border:none;margin-left:6.75pt;margin-right: 6.75pt">

  Pertimbangkan variabel acak diskrit X, diberikan oleh tabel distribusi:

  Mari kita tentukan sendiri tugas memperkirakan probabilitas bahwa penyimpangan variabel acak dari harapan matematisnya tidak melebihi nilai absolut angka positif ε

  Jika sebuah ε cukup kecil, dengan demikian kami akan memperkirakan probabilitas bahwa X akan mengambil nilai yang cukup dekat dengan ekspektasi matematisnya. membuktikan ketidaksetaraan yang memungkinkan kita untuk memberikan perkiraan yang menarik bagi kita.

  Lemma Chebyshev. Diberikan variabel acak X yang hanya mengambil nilai non-negatif dengan harapan M(X). Untuk sembarang bilangan >0, ekspresi terjadi:

  Pertidaksamaan Chebyshev. Probabilitas bahwa penyimpangan variabel acak X dari ekspektasi matematisnya dalam nilai absolut lebih kecil dari angka positif ε , tidak kurang dari 1 – D(X) / ε 2:

  P(|X-M(X)|< ε ) 1 - D (X) / ε 2.

  Komentar. Pertidaksamaan Chebyshev memiliki nilai praktis yang terbatas, karena sering kali memberikan perkiraan kasar dan terkadang sepele (tanpa minat).

  Signifikansi teoretis dari ketidaksetaraan Chebyshev sangat besar. Di bawah ini kita akan menggunakan pertidaksamaan ini untuk menurunkan teorema Chebyshev.

  2.2. Teorema Chebyshev

  Jika X1, X2, ..., Xn.. adalah peubah acak bebas berpasangan, dan variansnya terbatas seragam (tidak melebihi konstanta bilangan C), maka sekecil apapun bilangan positif ε , peluang pertidaksamaan

  (X1+X2 + ...+Xn) / n - (M(X1)+M(X2)+ ...+M(Xn))/n |< ε

  akan sewenang-wenang mendekati kesatuan jika jumlah variabel acak cukup besar.

  P (÷ (X1+X2 + ...+Xn) / n - (M(X1)+M(X2)+ ...+M(Xn))/n |< ε )=1.

  Teorema Chebyshev menyatakan:

  1. Kami mempertimbangkan sejumlah besar variabel acak independen dengan varians terbatas,

  Saat merumuskan teorema Chebyshev, kita mengasumsikan bahwa variabel acak memiliki ekspektasi matematis yang berbeda. Dalam praktiknya, sering terjadi bahwa variabel acak memiliki ekspektasi matematis yang sama. Jelas, jika kita kembali mengasumsikan bahwa dispersi jumlah ini terbatas, maka teorema Chebyshev akan berlaku untuk mereka.

  Mari kita nyatakan ekspektasi matematis dari masing-masing variabel acak melalui sebuah;

  Dalam kasus yang sedang dipertimbangkan, rata-rata aritmatika dari ekspektasi matematis, seperti yang mudah dilihat, juga sama dengan sebuah.

  Seseorang dapat merumuskan teorema Chebyshev untuk kasus tertentu yang sedang dipertimbangkan.

  Jika X1, X2, ..., Xn.. adalah peubah acak bebas berpasangan yang mempunyai ekspektasi matematis a yang sama, dan jika dispersi peubah-peubah tersebut terbatas beraturan, maka sekecil apapun bilangan ε > Oh, peluang pertidaksamaan

  (X1+X2 + ...+Xn) / n - sebuah | < ε

  akan sewenang-wenang mendekati kesatuan jika jumlah variabel acak cukup besar" .

  Dengan kata lain, di bawah kondisi teorema

  P (÷ (X1+X2 + ...+Xn) / n - a |< ε ) = 1.

  2.3. Inti dari teorema Chebyshev

  Meskipun variabel acak independen individu dapat mengambil nilai yang jauh dari harapan matematisnya, rata-rata aritmatika dari sejumlah variabel acak yang cukup besar dengan probabilitas tinggi mengambil nilai yang mendekati bilangan konstan tertentu, yaitu bilangan

  (M(Xj) + M (X2)+... + M (Xn))/n atau ke nomor dan masuk kasus tertentu.

  Dengan kata lain, variabel acak individu dapat memiliki penyebaran yang signifikan, dan rata-rata aritmatikanya tersebar kecil.

  Jadi, seseorang tidak dapat dengan yakin memprediksi nilai yang mungkin diambil oleh masing-masing variabel acak, tetapi seseorang dapat memprediksi berapa nilai rata-rata aritmatikanya.

  Jadi, rata-rata aritmatika dari sejumlah besar variabel acak independen (variansnya terbatas secara seragam) kehilangan karakter variabel acak.

  Hal ini dijelaskan oleh fakta bahwa penyimpangan dari masing-masing besaran dari ekspektasi matematisnya bisa positif dan negatif, dan dalam rata-rata aritmatika mereka saling meniadakan.

  Teorema Chebyshev berlaku tidak hanya untuk diskrit, tetapi juga untuk variabel acak kontinu; itu adalah contoh yang menegaskan validitas doktrin tentang hubungan antara kebetulan dan kebutuhan.

  2.4. Signifikansi teorema Chebyshev untuk praktek

  Mari kita berikan contoh penerapan teorema Chebyshev untuk solusi masalah praktis.

  Biasanya, untuk mengukur suatu besaran fisis tertentu, dilakukan beberapa kali pengukuran dan rata-rata aritmatikanya diambil sesuai dengan ukuran yang diinginkan. Dalam kondisi apa metode pengukuran ini dianggap benar? Jawaban atas pertanyaan ini diberikan oleh teorema Chebyshev (kasus khusus).

  Memang, pertimbangkan hasil setiap pengukuran sebagai variabel acak

  X1, X2, ..., Xn

  Untuk jumlah ini, teorema Chebyshev dapat diterapkan jika:

  1) Mereka berpasangan independen.

  2) memiliki ekspektasi matematis yang sama,

  3) dispersinya terbatas secara seragam.

  Persyaratan pertama terpenuhi jika hasil setiap pengukuran tidak bergantung pada hasil yang lain.

  Persyaratan kedua terpenuhi jika pengukuran dilakukan tanpa kesalahan sistematis (satu tanda). Dalam hal ini, ekspektasi matematis dari semua variabel acak adalah sama dan sama dengan ukuran sebenarnya sebuah.

  Persyaratan ketiga terpenuhi jika perangkat memberikan akurasi pengukuran tertentu. Meskipun hasil pengukuran individu berbeda, hamburannya terbatas.

  Jika semua persyaratan ini terpenuhi, kami berhak menerapkan teorema Chebyshev pada hasil pengukuran: untuk ukuran yang cukup besar P peluang ketidaksetaraan

  | (X1 + Xa+...+Xn)/n - a |< ε sewenang-wenang dekat dengan kesatuan.

  Dengan kata lain, dengan jumlah pengukuran yang cukup besar, hampir pasti bahwa rata-rata aritmatikanya sedikit berbeda dari nilai sebenarnya dari kuantitas yang diukur.

  Teorema Chebyshev menunjukkan kondisi di mana metode pengukuran yang dijelaskan dapat diterapkan. Namun, adalah keliru untuk berpikir bahwa dengan meningkatkan jumlah pengukuran, seseorang dapat mencapai akurasi tinggi yang sewenang-wenang. Faktanya adalah bahwa perangkat itu sendiri memberikan pembacaan hanya dengan akurasi ± , oleh karena itu, setiap hasil pengukuran, dan karenanya rata-rata aritmatikanya, akan diperoleh hanya dengan akurasi yang tidak melebihi akurasi perangkat.

  Metode pengambilan sampel yang banyak digunakan dalam statistik didasarkan pada teorema Chebyshev, yang intinya adalah sampel acak yang relatif kecil digunakan untuk menilai seluruh populasi (populasi umum) dari objek yang diteliti.

  Misalnya, kualitas bal kapas dinilai dari bundelan kecil yang terdiri dari serat yang dipilih secara acak dari berbagai bagian bal. Meskipun jumlah serat dalam satu bundel jauh lebih sedikit daripada dalam satu bale, bundel itu sendiri mengandung jumlah serat yang cukup besar, berjumlah ratusan.

  Sebagai contoh lain, seseorang dapat menunjukkan penentuan kualitas biji-bijian dari sampel kecil. Dan dalam hal ini, jumlah biji-bijian yang dipilih secara acak kecil dibandingkan dengan seluruh massa biji-bijian, tetapi itu sendiri cukup besar.

  Sudah dari contoh-contoh yang dikutip, orang dapat menyimpulkan bahwa untuk praktik teorema Chebyshev sangat penting.

  2.5. DalilBernoulli

  Diproduksi P tes independen (bukan peristiwa, tetapi tes). Di masing-masing dari mereka, probabilitas terjadinya suatu peristiwa A adalah sama dengan R.

  Timbul pertanyaan, berapakah frekuensi relatif terjadinya peristiwa tersebut? Pertanyaan ini dijawab oleh teorema yang dibuktikan oleh Bernoulli, yang disebut "hukum bilangan besar" dan meletakkan dasar bagi teori probabilitas sebagai ilmu.

  teorema Bernoulli. Jika di masing-masing P probabilitas tes independen R terjadinya suatu peristiwa TETAPI konstan, maka probabilitas penyimpangan frekuensi relatif dari probabilitas R akan sewenang-wenang kecil dalam nilai absolut jika jumlah percobaan cukup besar.

  Dengan kata lain, jika >0 adalah bilangan kecil sewenang-wenang, maka di bawah kondisi teorema kita memiliki persamaan

  P(|m / n - p|< ε)= 1

  Komentar. Adalah salah, berdasarkan teorema Bernoulli, untuk menyimpulkan bahwa dengan peningkatan jumlah percobaan, frekuensi relatif terus cenderung ke probabilitas R; dengan kata lain, teorema Bernoulli tidak menyiratkan kesetaraan (t/n) = p,

  PADA Teorema ini hanya berurusan dengan probabilitas bahwa, dengan jumlah percobaan yang cukup besar, frekuensi relatif akan berbeda sedikit dari probabilitas konstan terjadinya suatu peristiwa di setiap percobaan.

  Tugas 7-1.

  1. Perkirakan peluang bahwa setelah 3600 pelemparan dadu, jumlah kemunculan 6 akan menjadi sedikitnya 900.

  Keputusan. Misalkan x adalah jumlah kemunculan 6 poin dalam 3600 lemparan koin. Peluang terambilnya 6 angka dalam sekali lempar adalah p=1/6, maka M(x)=3600 1/6=600. Kami menggunakan pertidaksamaan Chebyshev (lemma) untuk = 900

  = P(x 900) £ 600 / 900 =2 / 3

  Menjawab 2 / 3.

  2. 1000 tes independen dilakukan, p=0,8. Tentukan peluang banyaknya kemunculan peristiwa A dalam pengujian ini menyimpang dari modulo ekspektasi matematisnya kurang dari 50.

  Keputusan. x adalah jumlah kemunculan kejadian A dalam n - 1000 percobaan.

  M (X) \u003d 1000 0,8 \u003d 800. D(x)=100 0,8 0,2=160

  Kami menggunakan pertidaksamaan Chebyshev untuk = 50 . yang diberikan

  P(|x-M(x)|< ε) 1 - D (x) / ε 2

  R(|x-800|< 50) ³ / 50 2 = 1-160 / 2500 = 0,936.

  Menjawab. 0,936

  3. Dengan menggunakan pertidaksamaan Chebyshev, perkirakan peluang bahwa |X - M(X)|< 0,1, если D (X) = 0,001. Ответ Р³0,9.

  4. Diketahui: P(|X- M(X)\< ) 0,9; D (X)= 0,004. Menggunakan pertidaksamaan Chebyshev, cari . Menjawab. 0,2.

  Kontrol pertanyaan dan tugas

  1. Tujuan dari teorema limit pusat

  2. Kondisi penerapan teorema Lyapunov.

  3. Perbedaan antara lemma dan teorema Chebyshev.

  4. Kondisi penerapan teorema Chebyshev.

  5. Syarat penerapan teorema Bernoulli (hukum bilangan besar)

  Persyaratan untuk pengetahuan dan keterampilan

  Siswa harus mengetahui rumusan semantik umum dari teorema limit pusat. Mampu merumuskan teorema parsial untuk variabel acak independen yang terdistribusi identik. Pahami pertidaksamaan Chebyshev dan hukum bilangan besar dalam bentuk Chebyshev. Memiliki gagasan tentang frekuensi suatu peristiwa, hubungan antara konsep "probabilitas" dan "frekuensi". Memiliki pemahaman tentang hukum bilangan besar dalam bentuk Bernoulli.

  (1857-1918), matematikawan Rusia yang luar biasa

  Batas teorema teori probabilitas

  Pertidaksamaan Chebyshev

  Mari kita pertimbangkan sejumlah pernyataan dan teorema dari sekelompok besar yang disebut teorema batas teori probabilitas, yang membangun hubungan antara karakteristik teoretis dan eksperimental dari variabel acak dengan sejumlah besar tes pada mereka. Mereka membentuk dasar statistik matematika. Teorema limit secara konvensional dibagi menjadi dua kelompok. Kelompok teorema pertama, disebut hukum bilangan besar, menetapkan stabilitas nilai rata-rata, yaitu dengan sejumlah besar percobaan, hasil rata-rata mereka tidak lagi acak dan dapat diprediksi dengan akurasi yang cukup. Kelompok teorema kedua, disebut batas tengah, menetapkan kondisi di mana hukum distribusi jumlah dari sejumlah besar variabel acak mendekati yang normal tanpa batas.

  Pertama, pertimbangkan pertidaksamaan Chebyshev, yang dapat digunakan untuk: a) memperkirakan secara kasar probabilitas kejadian yang terkait dengan variabel acak yang distribusinya tidak diketahui; b) pembuktian sejumlah teorema hukum bilangan besar.

  Teorema 7.1. Jika variabel acak X memiliki harapan dan varians matematis DX, maka pertidaksamaan Chebyshev

  .

  (7.1)

  Perhatikan bahwa pertidaksamaan Chebyshev dapat ditulis dalam bentuk lain:

  untuk frekuensi atau acara di n percobaan independen, di mana masing-masing dapat terjadi dengan probabilitas , yang variansnya , Pertidaksamaan Chebyshev memiliki bentuk

  Ketimpangan (7.5) dapat ditulis ulang sebagai

  .

  (7.6)

  Contoh 7.1. Dengan menggunakan pertidaksamaan Chebyshev, perkirakan peluang penyimpangan variabel acak X dari ekspektasi matematisnya akan kurang dari tiga standar deviasi, yaitu lebih kecil.

  Keputusan:

  Dengan asumsi dalam rumus (7.2), kita memperoleh

  Penilaian ini disebut aturan tiga sigma.

  teorema Chebyshev

  Pernyataan utama dari hukum bilangan besar terkandung dalam teorema Chebyshev. Di dalamnya dan teorema lain dari hukum bilangan besar, konsep "konvergensi variabel acak dalam probabilitas" digunakan.

  variabel acak konvergen dalam probabilitas dengan nilai A (acak atau non-acak), jika untuk sembarang peluang suatu kejadian di cenderung satu, yaitu

  

  (atau ). Konvergensi dalam probabilitas secara simbolis ditulis sebagai berikut:

  Perlu dicatat bahwa konvergensi dalam probabilitas mensyaratkan bahwa ketidaksetaraan berlaku untuk sebagian besar anggota urutan (dalam analisis matematis - untuk semua n > N, di mana N- angka tertentu), dan untuk hampir semua anggota barisan harus termasuk dalam ε- lingkungan TETAPI.

  Teorema 7.3 (Hukum bilangan besar dalam bentuk P.L. Chebyshev). Jika variabel acak independen dan ada nomor C> 0, yang , maka untuk sembarang

  ,

  (7.7)

  itu. rata-rata aritmatika dari variabel acak ini konvergen dalam probabilitas ke rata-rata aritmatika dari harapan matematis mereka:

  .

  Bukti. Dari dulu

  .

  Kemudian, dengan menerapkan pertidaksamaan Chebyshev (7.2) ke variabel acak, kita dapatkan

  itu. rata-rata aritmatika dari variabel acak konvergen dalam probabilitas dengan harapan matematis sebuah:

  

  Bukti. Sebagai

  dan varians variabel acak , yaitu terbatas, kemudian menerapkan teorema Chebyshev (7.7), kami memperoleh pernyataan (7.9).

  Akibat wajar dari teorema Chebyshev membenarkan prinsip "rata-rata aritmatika" dari variabel acak saya terus-menerus digunakan dalam praktik. Ya, biarkan itu dilakukan n pengukuran independen dari beberapa kuantitas, nilai sebenarnya yang sebuah(tidak diketahui). Hasil setiap pengukuran adalah variabel acak saya. Menurut akibat wajar, sebagai nilai perkiraan kuantitas sebuah Anda dapat mengambil rata-rata aritmatika dari hasil pengukuran:

  .

  Kesetaraan semakin akurat, semakin n.

  Teorema Chebyshev juga didasarkan pada banyak digunakan dalam statistik metode pengambilan sampel, yang intinya adalah bahwa kualitas sejumlah besar bahan homogen dapat dinilai dari sampelnya yang kecil.

  Teorema Chebyshev menegaskan hubungan antara keacakan dan kebutuhan: nilai rata-rata variabel acak praktis tidak berbeda dari variabel non-acak.

  teorema Bernoulli

  Teorema Bernoulli secara historis merupakan bentuk pertama dan paling sederhana dari hukum bilangan besar. Ini secara teoritis mendukung sifat stabilitas dari frekuensi relatif.

  Teorema 7.4 (Hukum bilangan besar dalam bentuk J. Bernoulli). Jika peluang suatu kejadian terjadi TETAPI dalam satu tes adalah R, banyaknya kejadian tersebut pada n percobaan independen sama dengan , maka untuk setiap nomor kami memiliki kesetaraan

  ,

  (7.10)

  yaitu frekuensi relatif dari peristiwa TETAPI konvergen dalam probabilitas ke probabilitas R acara TETAPI: .

  Bukti. Kami memperkenalkan variabel acak sebagai berikut: jika dalam saya-percobaan ke-th suatu peristiwa terjadi TETAPI, dan jika tidak muncul, maka . Kemudian nomor TETAPI(jumlah keberhasilan) dapat direpresentasikan sebagai

  Ekspektasi matematis dan varians variabel acak adalah: , . Hukum distribusi variabel acak X i memiliki bentuk

  saya
  R		R

  untuk apa saja saya. Jadi, variabel acak X saya independen, varians mereka terbatas pada jumlah yang sama , karena

  .

  Oleh karena itu, teorema Chebyshev dapat diterapkan pada variabel acak ini

  .

  ,

  Karena itu, .

  Teorema Bernoulli secara teoritis mendukung kemungkinan perhitungan perkiraan probabilitas suatu peristiwa menggunakan frekuensi relatifnya. Jadi, misalnya, frekuensi relatif dari peristiwa ini dapat diambil sebagai probabilitas memiliki anak perempuan, yang menurut data statistik kira-kira sama dengan 0,485.

  Pertidaksamaan Chebyshev (7.2) untuk variabel acak

  mengambil bentuk

  di mana pi- peluang kejadian TETAPI di saya- tes m.

  Contoh 7.2. Probabilitas kesalahan ketik pada satu halaman naskah adalah 0,2. Perkirakan probabilitas bahwa dalam sebuah manuskrip yang berisi 400 halaman, frekuensi terjadinya salah cetak berbeda dari modulo probabilitas yang sesuai kurang dari 0,05.

  Keputusan:

  Kami menggunakan rumus (7.11). Pada kasus ini , , , . Kami memiliki , yaitu .

  Teorema limit pusat

  Teorema limit pusat adalah kelompok kedua dari teorema limit yang membangun hubungan antara hukum distribusi jumlah variabel acak dan bentuk pembatasnya - hukum distribusi normal.

  Mari kita rumuskan teorema limit pusat untuk kasus ketika suku-suku jumlah memiliki distribusi yang sama. Teorema ini paling sering digunakan dalam praktik. Dalam statistik matematika, variabel acak sampel memiliki distribusi yang sama, karena diperoleh dari populasi umum yang sama.

  Teorema 7.5. Biarkan variabel acak menjadi independen, terdistribusi secara merata, memiliki harapan dan varians matematis yang terbatas , . Kemudian fungsi distribusi dari jumlah terpusat dan ternormalisasi dari variabel acak ini cenderung ke fungsi distribusi dari variabel acak normal standar.

  Versi paling sederhana dari Central Limit Theorem (CLT) dari teori probabilitas adalah sebagai berikut.

  (untuk istilah yang didistribusikan secara identik). Biarlah X 1 , X 2 ,…, X n, … adalah variabel acak independen yang terdistribusi identik dengan ekspektasi matematis M(X saya) = m dan dispersi D(X saya) = , saya= 1, 2,…, n,… Kemudian untuk sembarang bilangan real X ada batasnya

  

  di mana F(x) adalah fungsi distribusi normal standar.

  Teorema ini kadang-kadang disebut teorema Lindeberg-Levy.

  Dalam beberapa masalah yang diterapkan, kondisi distribusi identik tidak terpenuhi. Dalam kasus seperti itu, teorema limit pusat biasanya tetap valid, tetapi kondisi tertentu harus diterapkan pada urutan variabel acak. Inti dari kondisi ini adalah tidak ada suku yang dominan, kontribusi setiap suku terhadap rata-rata aritmatika harus dapat diabaikan dibandingkan dengan jumlah akhir. Teorema Lyapunov paling sering digunakan.

  Teorema limit pusat(untuk istilah yang didistribusikan secara berbeda) – teorema Lyapunov. Biarlah X 1 , X 2 ,…, X n, … adalah variabel acak independen dengan ekspektasi matematis M(X saya) = saya dan dispersi D(X saya) = , saya= 1, 2,…, n,… Misalkan, untuk beberapa >0, semua variabel acak yang dipertimbangkan memiliki momen pusat orde 2+δ dan “fraksi Lypunov” berkurang tanpa batas:

  

  

  Kemudian untuk sembarang bilangan real X ada batasnya

  di mana F(x) adalah fungsi distribusi normal standar.

  Dalam kasus suku acak terdistribusi identik

  dan teorema Lyapunov berubah menjadi teorema Lindeberg-Levy.

  Sejarah memperoleh teorema limit pusat untuk variabel acak membentang selama dua abad - dari karya pertama De Moivre di tahun 30-an abad ke-18 hingga kondisi perlu dan cukup yang diperoleh Lindeberg dan Feller di tahun 30-an abad ke-20.

  teorema Lindeberg-Feller. Biarlah X 1 , X 2 ,…, X n, …, adalah variabel acak independen dengan ekspektasi matematis M(X saya) = saya dan dispersi D(X saya) = , saya= 1, 2,…, n,… Relasi limit (1), yaitu teorema limit pusat, dipenuhi jika dan hanya jika untuk sembarang >0

  

  di mana Fk(x) menunjukkan fungsi distribusi dari variabel acak X k.

  Bukti varian yang terdaftar dari teorema limit pusat untuk variabel acak dapat ditemukan dalam kursus klasik tentang teori probabilitas.

  Untuk statistik terapan dan, khususnya, untuk statistik non-numerik, teorema limit pusat multivariat sangat penting. Ini bukan tentang jumlah variabel acak, tetapi tentang jumlah vektor acak.

  Kondisi perlu dan cukup untuk konvergensi multidimensi. Biarlah F n menunjukkan fungsi distribusi bersama k-dimensi vektor acak , n= 1,2,…, dan menyenangkan . Kondisi perlu dan cukup untuk konvergensi F n untuk sebagian k-fungsi distribusi dimensi F Apakah itu menyenangkan memiliki limit untuk sembarang vektor .

  Teorema di atas berharga karena konvergensi vektor direduksi menjadi konvergensi kombinasi linier koordinatnya, mis. ke konvergensi dari variabel acak yang biasa dipertimbangkan sebelumnya. Namun, tidak memungkinkan untuk menunjukkan distribusi batas secara langsung. Hal ini dapat dilakukan dengan menggunakan teorema berikut.

  Teorema konvergensi multidimensi. Biarlah F n dan menyenangkan sama dengan teorema sebelumnya. Biarlah F- fungsi distribusi bersama k-dimensi vektor acak. Jika fungsi distribusi menyenangkan konvergen dengan meningkatnya ukuran sampel ke fungsi distribusi F untuk sembarang vektor , dimana F adalah fungsi distribusi kombinasi linier , kemudian F n konvergen ke F.

  Di sini konvergensi F n ke F artinya untuk apa saja k vektor -dimensi sedemikian rupa sehingga fungsi distribusi F terus menerus dalam , urutan nomor F n menyatu dengan pertumbuhan n ke nomor F. Dengan kata lain, konvergensi fungsi distribusi dipahami dengan cara yang persis sama seperti dalam pembahasan teorema limit untuk variabel acak di atas. Mari kita sajikan analog multidimensi dari teorema ini.

  Teorema limit pusat multidimensi. Pertimbangkan independen terdistribusi identik k-dimensi vektor acak

  

  di mana prima menunjukkan operasi transposisi vektor. Mari kita asumsikan vektor acak kamu tidak memiliki momen orde pertama dan kedua, yaitu

  M(kamu tidak) = μ, D(kamu tidak) = Σ,

  di mana μ adalah vektor ekspektasi matematis dari koordinat vektor acak, adalah matriks kovariansnya. Kami memperkenalkan urutan vektor acak rata-rata aritmatika:

  Maka vektor acak memiliki asimtotik k-distribusi normal dimensi, yaitu itu didistribusikan secara asimtotik dengan cara yang sama seperti k-dimensi normal dengan rata-rata nol, kovarians , dan densitas

  Di sini |Σ| adalah determinan matriks . Dengan kata lain, distribusi vektor acak konvergen ke k-distribusi normal dimensi dengan rata-rata nol dan matriks kovarians .

  Ingat bahwa distribusi normal multivariat dengan harapan dan matriks kovarians adalah distribusi dengan kepadatan

  Teorema limit pusat multivariat menunjukkan bahwa distribusi jumlah vektor acak independen yang terdistribusi identik dengan banyak suku didekati dengan baik oleh distribusi normal yang memiliki dua momen pertama yang sama (vektor harapan dari koordinat vektor acak dan korelasinya matriks) sebagai vektor asli. Distribusi yang sama dapat ditinggalkan, tetapi ini akan memerlukan beberapa komplikasi simbolisme. Secara keseluruhan, dari teorema konvergensi multidimensi, kasus multidimensi tidak berbeda secara mendasar dari kasus satu dimensi.

  Contoh. Biarlah X 1 , … X n,… adalah variabel acak independen yang terdistribusi identik. Mempertimbangkan k-dimensi independen vektor acak terdistribusi identik

  Harapan matematis mereka adalah vektor momen awal teoretis, dan matriks kovarians terdiri dari momen pusat yang sesuai. Maka adalah vektor momen pusat sampel. Teorema limit pusat multivariat mengklaim memiliki distribusi normal asimtotik. Sebagai berikut dari teorema pewarisan konvergensi dan linearisasi (lihat di bawah), distribusi berbagai fungsi momen awal sampel dapat dideduksi dari distribusi tersebut. Dan karena momen-momen sentral dinyatakan dalam momen-momen awal, pernyataan serupa juga berlaku untuk mereka.

  Sebelumnya