BREAKING NEWS

Informatika

Sabtu, 18 Desember 2021

Implementasi algoritma divide and conquer pada sorting dan searching

Nama    : Armelia Luvita Sari

Npm   : 20312057

Kelas   : IF20B


Implementasi Algoritma Divide And Conquer Pada Sorting dan Searching


Komputer pada awalnya diciptakan sebagai perangkat untuk melakukan kalkulasi secara otomatis dan akurat. Meskipun awalnya hanya berfokus pada kalkukasi numerik, komputer modern yang dijumpai sekarang telah melakukan kalkulasi pada banyak hal, seperti teks ataupun gambar. Berbagai kalkulasi dan analisa yang dilakukan komputer biasanya diimplementasikan melalui perangkat lunak. Dengan semakin besarnya ruang lingkup hal-hal yang dilakukan oleh komputer, perangkat lunak yang dikembangkan juga menjadi semakin kompleks. Algoritma, sebagai bagian dari perangkat lunak yang melakukan pemrosesan, juga memerlukan berbagai teknik baru. Misalkan, untuk menghitung total jumlah dari bilangan-bilangan yang ada di dalam sebuah list, kita dapat menggunakan perulangan sederhana.

Selanjutnya kita akan membahas mengenai Algoritma Divide and Conquer, Algoritma Divide and Conquer adalah metode pemecahan masalah yang bekerja dengan membagi masalah menjadi beberapa upa-masalah yang lebih kecil, kemudian menyelesaikan masing-masing upa-masalah tersebut secara independent, dan akhirnya menggabungkan solusi masing-masing upa-masalah sehingga menjadi solusi dari masalah semula.

Sebuah algoritma divide and conquer (selanjutnya disebut dengan D&C) memiliki tiga langkah, yaitu:

  • Divide (Memecah) pada langkah ini kita memecahkan masalah atau data ke dalam bentuk yang sama, tetapi dalam ukuran yang lebih kecil. Pemecahan langkah biasanya dilakukan dengan menggunakan algoritma rekursif, sampai ukuran data menjadi sangat kecil dan dapat diselesaikan dengan algoritma sederhana.
  • Conquer (Menaklukkan) dalam langkah ini kita mencoba menyelesaikan masalah atau data yang telah dipecahkan pada langkah pertama, dengan menggunakan algoritma sederhana.
  • Combine (Menggabungkan) setelah menjalankan langkah conquer, tentunya kita harus menggabungkan kembali hasil dari masing-masing pecahan yang ada, untuk mendapatkan hasil akhir kalkulasi. Langkah combine mencoba mencapai hal tersebut.

1.      Algoritma Divide And Conquer Pada Merge Sort

        Merge sort, seperti namanya, merupakan algoritma yang dirancang untuk melakukan pengurutan terhadap sekumpulan bilangan. Ide utama dari merge sort sama dengan algoritma perhitungan total, yaitu membagi-bagikan keseluruhan list menjadi komponen kecil, dan kemudian mengurutkan komponen tersebut dan menggabungkannya kembali menjadi sebuah list besar.

2.      Algoritma Divide And Conquer Pada Binary Search

    Algoritma pencarian Binary search adalah algoritma untuk mencari sebuah nilai pada tabel teurut dengan cara menghilangkan setengah data pada setiap langkah. Algoritma ini mencari nilai yang dicari dengan tiga langkah yaitu:

  1. Mencari nilai tengah dari tabel (median).
  2. Melakukan perbandingan nilai tengah dengan nilai yang dicari untuk menentukan apakah nilai yang dicari ada pada sebelum atau setelah nilai tengah.
  3. Mencari setengah sisanya dengan cara yang sama.

3.      Algoritma Divide And Conquer Pada Insertion sort

        Salah satu algoritma sorting yang paling sederhana adalah insertion sort. Ide dari algoritma ini dapat dianalogikan seperti mengurutkan kartu. Penjelasan berikut ini menerangkan bagaimana algoritma insertion sort bekerja dalam pengurutan kartu. Anggaplah anda ingin mengurutkan satu set kartu dari kartu yang bernilai paling kecil hingga yang paling besar. Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan (meja pertama) dan yang sudah diurutkan (meja kedua). Elemen pertama diambil dari bagian array yang belum diurutkan dan kemudian diletakkan sesuai posisinya pada bagian lain dari array yang telah diurutkan. Langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian array yang belum diurutkan.

4.      Algoritma Divide And Conquer Pada Selection sort

        Algoritma ini sangat rapat dan mudah untuk diimplementasikan. Ide utama dari algoritma selection sort adalah memilih elemen dengan nilai paling rendah dan menukar elemen yang terpilih dengan elemen ke-i. Nilai dari i dimulai dari 1 ke n, dimana n adalah jumlah total elemen dikurangi 1.

5.      Algoritma Divide And Conquer Pada Quick sort

     Quicksort ditemukan oleh C.A.R Hoare. Seperti pada merge sort, algoritma ini juga berdasar pada pola divide-and-conquer. Berbeda dengan merge sort, algoritma ini hanya mengikuti langkah – langkah sebagai berikut

1.  Divide

Memilah rangkaian data menjadi dua sub-rangkaian A[p…q-1] dan A[q+1…r] dimana setiap elemen A[p…q-1] adalah kurang dari atau sama dengan A[q] dan setiap elemen pada A[q+1…r] adalah lebih besar atau sama dengan elemen pada A[q]. A[q] disebut sebagai elemen pivot. Perhitungan pada elemen q merupakan salah satu bagian dari prosedur pemisahan.

2.   Conquer

Mengurutkan elemen pada sub-rangkaian secara rekursif. Pada algoritma quicksort, langkah “kombinasi” tidak di lakukan karena telah terjadi pengurutan elemen – elemen pada sub-array.

6.      Algoritma Divide And Conquer Pada Counting sort

        Adalah sebuah algoritma sorting linear yang digunakan untuk mengurutkan ‘item’ ketika urutannya telah ditentukan dan memiliki panjang yang terbatas. Bilangan interval yang telah tetap, katakana k1 ke k2 adalah contoh dari ‘item’ tersebut. Counting sort sebenarnya merupakan metode pengurutan yang memanfaatkan index variabel array. Hanya effektif pada data yang nilainya kecil.

        Algoritma ini membuat 2 passover A dan passover B. Jika ukuran dari range k lebih kecil dari ukuran input n, maka time complexity = O(n). perhatikan juga bahwa algoritma ini stabil yang berarti bahwa sambungan diselesaikan dengan langsung mengabarkan element-element yang muncul pertama kali.

7.    Algoritma Divide And Conquer Pada Linear Searching

    Algoritma pencarian secara linear adalah algoritma untuk mencari sebuah nilai pada table sambarang dengan cara melakukan pass atau transversal. Transversal dari awal sampai akhir table. Ada dua macam cara pencarian pada table. Algoritma mempunyai dua jenis metode yaitu dengan Boolean dan tanpa Boolean.

8.      Algoritma Divide And Conquer Pada Radix Sort

        Radix sorting bisa digunakan ketika masing-masing universal element bisa dilihat sebagai sebuah urutan digit (atau huruf atau symbol lainnya). Sebagai contoh, kita bisa membuat masing-masing bilangan bulat antar 0 sampai 99 sebagai sebuah urutan dengan dua digit (seperti “05”). Untuk menyorting sebuah array dari angka 2-digit, algoritma ini membuat dua ‘passing’ sorting melalui array tersebut. Pada ‘passing’ pertama, element array disorting pada least significant decimal digit. Kunci utama dari radix sort adalah pada passing yang kedua. Hasilnya, setelah kedua passing melewati array tersebut, data yang terisi telah disorting.


Selasa, 14 Desember 2021

Sejarah, Definisi dan Cara Kerja Algoritma Divide and Conquer

Nama   : Armelia Luvita Sari
Npm     : 20312057
Kelas     : IF20B

Sejarah Algoritma Devide dan Conquer


Pencarian biner, algoritma penurunan-dan-taklukkan di mana sub-masalah berukuran kira-kira setengah dari ukuran aslinya, memiliki sejarah yang panjang. Sementara deskripsi yang jelas tentang algoritma pada komputer muncul pada tahun 1946 dalam sebuah artikel oleh John Mauchly, gagasan untuk menggunakan daftar item yang diurutkan untuk memfasilitasi pencarian tanggal kembali setidaknya sejauh Babylonia pada 200 SM.

Algoritma penurunan-dan-taklukkan kuno lainnya adalah algoritma Euclidean untuk menghitung pembagi persekutuan terbesar dari dua bilangan dengan mengurangi bilangan tersebut menjadi subproblem ekuivalen yang lebih kecil dan lebih kecil, yang berasal dari beberapa abad SM.

Awal dari algoritma ini utamanya adalah pengurangan dan penaklukan - masalah asli secara berturut-turut dipecah menjadi sub-masalah tunggal, dan memang dapat diselesaikan secara berulang.

Contoh awal dari algoritma bagi-dan-taklukkan dengan beberapa subproblem adalah deskripsi Gauss tahun 1805 tentang apa yang sekarang disebut algoritma Cooley – Tukey fast Fourier transform (FFT), meskipun dia tidak menganalisis jumlah operasinya secara kuantitatif, dan FFT tidak tersebar luas sampai mereka ditemukan kembali lebih dari satu abad kemudian.

Algoritma D&C dua sub problem awal yang secara khusus dikembangkan untuk komputer dan dianalisis dengan benar adalah algoritma pengurutan gabungan, yang ditemukan oleh John von Neumann pada tahun 1945.

 1.  Pengertian

Algoritma Divide and Conquer merupakan algoritma yang sangat populer di dunia Ilmu Komputer. Divide and Conquer merupakan algoritma yang berprinsip memecah-mecah permasalahan yang terlalu besar menjadi beberapa bagian kecil sehingga lebih mudah untuk diselesaikan. Langkah-langkah umum algoritma Divide and Conquer :

  1. Divide : Membagi masalah menjadi beberapa upa-masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil ( idealnya berukuran hampir sama ).
  2. Conquer : Memecahkan ( menyelesaikan ) masing-masing upa-masalah ( secara rekursif ).
  3. Combine : Menggabungkan solusi masing-masing upa-masalah sehingga  membentuk solusi masalah semula.

Objek masalah yang di bagi adalah masukan (input) atau instances yang berukuran n: tabel (larik), matriks, dan sebagainya, bergantung pada masalahnya. Tiap-tiap upa-masalah mempunyai karakteristik yang sama (the same type) dengan karakteristik masalah asal, sehingga metode Divide and Conquer lebih natural diungkapkan dalam skema rekursif. Sesuai dengan karakteristik pembagian dan pemecahan masalah tersebut, maka algoritma ini dapat berjalan baik pada persoalan yang bertipe rekursif (perulangan dengan memanggil dirinya sendiri). 

Dengan demikian, algoritma ini dapat diimplementasikan dengan cara iteratif ( perulangan biasa ), karena pada prinsipnya iteratif hampir sama dengan rekursif. Salah satu penggunaan algoritma ini yang paling populer adalah dalam hal pengolahan data yang bertipe array ( elemen larik ). Mengapa ? Karena pengolahan array pada umumnya selalu menggunakan prinsip rekursif atau iteratif. Penggunaan secara spesifik adalah untuk mencari nilai minimal dan maksimal serta untuk mengurutkan elemen array. Dalam hal pengurutan ini ada empat macam algoritma pengurutan yang berdasar pada algoritma Divide and Conquer, yaitu merge sort, insert sort, quick sort, dan selection sort. Merge sort dan Quick sort mempunyai kompleksitas algoritma O(n ²log n). Hal ini lebih baik jika dibandingkan dengan pengurutan biasa dengan menggunakan algoritma brute force.

2. Penerapan Algoritma

2.1. Pemecahan Masalah Convex Hull dengan Algoritma Divide and Conquer

Pada penyelasaian masalah pencarian Convex Hull dengan menggunakan algoritma Divide and Conquer, hal ini dapat dipandang

sebagai generalisasi dari algoritma pengurutan merge sort. Berikut ini merupakan garis besar gambaran dari algoritmanya:

Pertama-tama lakukan pengurutan terhadap titik-titik dari himpunan S yang diberika berdasarkan koordinat absis-X, dengan kompleksitas waktu O(n log n).

Jika |S| ≤ 3, maka lakukan pencarian convex hull secara brute-force dengan kompleksitas waktu O(1). (Basis).

Jika tidak, partisi himpunan titik-titik pada S menjadi 2 buah himpunan A dan B, dimana A terdiri dari setengah jumlah dari |S| dan titik dengan koordinat absix-X yang terendah dan B terdiri dari setengah dari jumlah |S| dan titik dengan koordinat absis-X terbesar.

Secara rekursif lakukan penghitungan terhadap HA = conv(A) dan HB = conv(B).

Lakukan penggabungan (merge) terhadap kedua hull tersebut menjadi convex hull, H, dengan menghitung da mencari upper dan lower tangents untuk HA dan HB dengan mengabaikan semua titik yang berada diantara dua buah tangen ini.

Permasalahan convex hull adalah sebuah permasalahan yang memiliki aplikasi terapan yang cukup banyak, seperti pada permasalahan grafika komputer, otomasi desain, pengenalan pola (pattern recognition), dan penelitian operasi. Divide and Conquer adalah metode pemecahan masalah yang bekerja dengan membagi masalah menjadi beberapa upa-masalah yang lebih kecil, kemudian menyelesaikan masing-masing upa-masalah tersebut secara independent, dan akhirnya menggabungkan solusi masing-masing upa-masalah sehingga menjadi solusi dari masalah semula.

Algoritma Divide and Conquer merupakan salah satu solusi dalam penyelesaian masalah convex hull. Algoritma ini ternyata memiliki kompleksitas waktu yang cukup kecil dan efektif dalam menyelesaikan permasalahan ini (jika dibandingkan algoritma lain). Selain itu juga, algoritma ini dapat digeneralisasi untuk permasalahan convex hull yang berdimensi lebih dari 3.

2.2. Persoalan Minimum dan Maksimum (MinMaks)

Persoalan : Misalnya diketahui table A yang berukuran n eleman sudah berisi nilai integer. Kita ingin menentukan nilai minimum dan nilai maksimum sekaligus di dalam table tersebut. Ukuran table hasil pembagian dapat dibuat cukup kecil sehingga mencari minimum dan maksimum dapat diselesaikan (SOLVE) secara lebih mudah. Dalam hal ini, ukuran kecil yang dipilih adalah 1 elemen atau 2 elemen.

Algoritma MinMaks :

1. Untuk kasus n = 1 atau n = 2,

SOLVE : Jika n = 1, maka min = maks = An. Jika n = 2, maka bandingkan kedua elemen untuk menentukan min dan maks.

2. Untuk kasus n > 2,

DIVIDE : Bagi dua table A secSkema procedur utama Konversi dengan optimasi

Skema procedur rekursif dengan menerapkan Algoritma Divide and Conquer


Kompleksitas waktu algoritma :

T(n) = O(n/3)

dengan n menyatakan eksponen terkecil dari 2 yang mempunyai nilai 2n lebuh besar dari angka decimal

Algoritma konversi system bilangan dengan menggunakan algoritma dengan optimasi yang menerapkan algoritma Divide and Conquer lebih mangkus daripada algoritma konversi dengan metode pembagian sisa biasa jika dilihat dari segi kompleksitas waktunya. Hanya saja optimasi ini diimbangi dengan kenaikan pada kompleksitas ruangnya, meskipun pengaruhnya tidak sebesar optimasi yang kita lakukan.

2.4. Mencari Pasangan Titik yang Jaraknya Terdekat ( Closest Pair )

Persoalan : Diberikan himpunan titik, P, yang terdiri dari n buah titik, (xi,yi), pada bilangan 2-D. Tentukan jarak terdekat antara dua buah titik di dalam himpunan P. Jarak dua buah titik p1 = (x1, y1) dan p2 = (x2, y2) :

Penyelesaian dengan Algoritma Divide and Conquer :

a. Asumsi : n = 2k dan titik-titik diurut berdasarkan absis (x).

b. Algoritma Closest Pair :

  1. SOLVE : jika n = 2, maka jarak kedua titik dihitung langsung dengan rumus Euclidean.
  2. DIVIDE : Bagi titik-titik itu ke dalam dua bagian, PLeft dan PRight, setiap bagian mempunyai jumlah titik yang sama
  3. CONQUER :Secara rekursif, terapkan algoritma D-and-C pada masingmasing bagian.

Pasangan titik yang jaraknya terdekat ada tiga kemungkinan letaknya :

  • Pasangan titik terdekat terdapat di bagian PLeft.
  • Pasangan titik terdekat terdapat di bagian PRight.
  • Pasangan titik terdekat dipisahkan oleh garis batas L, yaitu satu titik di PLeft dan satu titik di PRight.

Jika kasusnya adalah (c), maka lakukan tahap COMBINE untuk mendapatkan jarak dua titik terdekat sebagai solusi persoalan semula.ara rekursif menjadi dua bagian yang berukuran sama, yaitu bagian kiri dan bagian kanan.

  • CONQUER : Terapkan algoritma Divide and Conquer untuk masing-masing bagian, dalam hal ini min dan maks dari table bagian kiri dinyatakan dalam peubah min1 dan maks1, dan min dan maks dari table bagian kanan dinyatakan dalam peubah min2 dan maks2.
  • COMBINE : Bandingkan min1 dan min2 untuk menentukan min table A, serta bandingkan maks1 dan maks2 untuk menentukan maks table A.

2.3. Optimasi Konversi Bilangan Desimal Ke Biner

Salah satu cara optimasi yang bias kita lakukan adalah membagi bilangan decimal yang hendak diubah dengan angka 8 ( bukan 2 ). Di sinilah prinsip algoritma Divide and Conquer kita gunakan untuk melakukan optimasi. Kita pecah-pecah angka decimal yang akan kita gunakan dengan cara membaginya dengan angka 8 secara berulang. Angka-angka sisa pembagian yang kita peroleh kemudian kita ubah ke dalam bilangan biner sebelum kita gabungkan menjadi hasil jawaban.

Karena angka pembagi yang kita pakai adalah 8 (23), maka kita dapat mengurangijumlah pembagian yang kita lakukan menjadi ± 1/3 dari jumlah semula. Hal ini tentu saja akan sangat berpengaruh pada kinerja dan waktu yang diperlukan oleh computer mengingat proses pembagian merupakan salah satu proses yang cukup rumit.


Selasa, 05 Oktober 2021

Permasalahan dalam Sorting

Nama  : Armelia Luvita Sari

Npm    : 20312057

Kelas   : IF20B


Pengertian Sorting

Pengurutan data dalam struktur data sangat penting untuk data yang bertipe data numerik ataupun karakter.

Pengurutan dapat dilakukan secara ascending (urut naik) dan descending (urut turun)

Pengurutan (Sorting) adalah proses menyusun kembali data yang sebelumnya telah disusun dengan suatu pola tertentu, sehingga dapat tersusun secara teratur menurut aturan tertentu.

Contoh :

Data Acak       : 10 3 8 7 12 18 1 

Ascending       : 1 3 6 7 8 10 12 18

Descending     : 18 12 10 8 7 6 3 1


2. Metode Pengurutan Data Berdasarkan Perbandingan (Bubble Sort)

Metode Bubble Sort mengurutkan data dengan cara membandingkan elemen sekarang dengan elemen berikutnya.

Bubble Sort merupakan cara pengurutan yang sederhana. Cara kerjanya adalah dengan berulang-ulang melakukan traversal (proses looping) terhadap elemen-elemen struktur data yang belum diurutkan. Di dalam traversal tersebut nilai dari dua elemen struktur data dibandingkan. Jika ternyata urutannya tidak sesuai dengan “pesanan”, maka dilakukan pertukaran (swap). Algoritma sorting ini disebut juga dengan comparison sort dikarenakan hanya mengandalkan perbandingan nilai elemen untuk mengoperasikan elemennya.

 Contoh :

1. Pengurutan Ascending : Jika elemen sekarang lebih besar dari elemen berikutnya maka kedua elemen tersebut ditukar.

2.  Pengurutan Descending : Jika elemen sekarang lebih kecil dari elemen berikutnya, maka kedua elemen tersebut ditukar.

3.  Algoritma ini seolah-olah menggeser satu per satu elemen dari kanan ke kiri atau kiri ke kanan, tergantung jenis pengurutannya.

4.  Ketika suatu proses telah selesai, maka bubble sort akan mengulangi proses, demikian seterusnya dari 0 sampai dengan iterasi sebanyak n-1.


3. Kelebihan dan Kekurangan Bubble Sort

  a.  Kelebihan dari algoritma Bubble Sort adalah sebagai berikut :

·      Algoritma yang simpel.

·     Mudah untuk diubah menjadi kode.

·    Definisi terurut terdapat dengan jelas dalam algoritma.

·   Cocok untuk pengurutan data dengan elemen kecil telah terurut.


 Kekurangan dari algoritma Bubble Sort adalah sebagai berikut :

·    Tidak efektif dalam pengurutan data berskala besar.

·  Langkah pengurutan yang terlalu panjang.

·     Kompleksitas algoritma yang terlalu besar, baik dalam average case maupun worst case, yaitu O(n2), sehingga seringkali disebut sebagai algoritma primitif, brute-force, maupun algoritma naif

Kamis, 05 Agustus 2021

Geometric Distribution & Poisson Distribution - PART 18

Geometric Distribution

Geometric Distribution merupakan suatu discrete probability distribution yang memenuhi kriteria berikut:

  • Percobaan (trial) akan dilakukan berulang kali sampai mendapatkan outcome success.

  • Setiap percobaan (trial) adalah independent terhadap trials lainnya.

  • Memiliki nilai probability success (p) yang sama untuk tiap trial.

  • Random variable x merepresentasikan banyaknya trials yang dilakukan sampai mendapati kondisi success.

Geometric Distribution Formula


P(x) = p \times q^{x-1}q = 1-p


Geometric Distribution contoh


Diketahui seorang pemain basket sejauh ini mencatat keberhasilan 75% dalam melakukan free throws. Berapa probability pemain tersebut mendapatkan point free throw pertamanya pada pelemparan ketiga atau keempat?

p=0.75\\ q=0.25\begin{equation} \begin{split} P(3) &= 0.75 \times 0.25^{3-1}\\ &\approx 0.046875\\ \\ P(4) &= 0.75 \times 0.25^{4-1}\\ &\approx 0.011719 \end{split} \end{equation}\begin{equation} \begin{split} P(3\ or\ 4) &= P(3) + P(4)\\ &\approx 0.059 \end{split} \end{equation}

Poisson Distribution


Poisson Distribution merupakan suatu discrete probability distribution yang memenuhi kriteria berikut:

  • Random variable x merepresentasikan banyaknya kemunculan suatu event dalam interval waktu tertentu.

  • Nilai probability untuk kemunculan event adalah sama untuk setiap interval.

  • Jumlah kemunculan event pada suatu interval adalah independent terhadap jumlah kemunculan event pada interval lainnya.

Poisson Distribution Formula

P(x) = \frac{\mu^{x}\times e^{- \mu}}{x!}


Poisson Distribution contoh


Diketahui rata-rata jumlah kasus kecelakaan lalu lintas per bulan yang terjadi di suatu ruas jalan toll adalah  3 kasus. Berapa nilai probability untuk mendapatkan 4 kasus kecelakaan dalam satu bulan tertentu pada ruas jalan toll tersebut?


x = 4\\ \mu = 3P(4) = \frac{3^{4}\times e^{- 3}}{4!} \approx 0.168

Geometric Distribution & Poisson Distribution - PART 17

Geometric Distribution

Geometric Distribution merupakan suatu discrete probability distribution yang memenuhi kriteria berikut:

  • Percobaan (trial) akan dilakukan berulang kali sampai mendapatkan outcome success.

  • Setiap percobaan (trial) adalah independent terhadap trials lainnya.

  • Memiliki nilai probability success (p) yang sama untuk tiap trial.

  • Random variable x merepresentasikan banyaknya trials yang dilakukan sampai mendapati kondisi success.

Geometric Distribution Formula

P(x) = p \times q^{x-1}q = 1-p


Poisson Distribution


Poisson Distribution merupakan suatu discrete probability distribution yang memenuhi kriteria berikut:

  • Random variable x merepresentasikan banyaknya kemunculan suatu event dalam interval waktu tertentu.

  • Nilai probability untuk kemunculan event adalah sama untuk setiap interval.

  • Jumlah kemunculan event pada suatu interval adalah independent terhadap jumlah kemunculan event pada interval lainnya.

Poisson Distribution Formula

P(x) = \frac{\mu^{x}\times e^{- \mu}}{x!}



contoh :


Diketahui rata-rata jumlah kasus kecelakaan lalu lintas per bulan yang terjadi di suatu ruas jalan toll adalah  3 kasus.Berapa nilai probability untuk mendapatkan 4 kasus kecelakaan dalam satu bulan tertentu pada ruas jalan toll tersebut?

x = 4\\ \mu = 3P(4) = \frac{3^{4}\times e^{- 3}}{4!} \approx 0.168

Distribusi Binomial Binomial Distribution - PART 16

Binomial Experiments

Binomial experiment merupakan suatu probability experiment yang memenuhi kriteria berikut:

  • Memiliki jumlah percobaan (trials) yang tetap dan setiap trial independent terhadap trials lainnya.
  • Setiap trial hanya memiliki dua kemungkinan outcomes; biasa dikategorikan sebagai success (S) atau failure (F).
  • Memiliki nilai probability success yang sama untuk tiap trial.
  • Random variabel x merepresentasikan jumlah kemunculan success dalam suatu experiment.
Contoh :

Suatu teknik pembibitan ikan lele memiliki tingkat keberhasilan 85%. Teknik ini lalu diterapkan pada 8 kolam ikan (empang). Nilai random variable merepresentasikan banyaknya empang yang berhasil melakukan pembibitan. Apakah experiment ini bisa dikategorikan sebagai binomial experiment?

n=8\\ p=0.85\\ q=1-0.85=0.15\\ x=0,1,2,3,4,5,6,7,8

Binomial Probability Formula


Terdapat beberapa cara untuk menghitung probability dari x success dari sejumlah n trials pada suatu binominal experiment: Tree Diagram, Multiplication Rule

Binomial Probability Formula.

\begin{equation} \begin{split} P(x) & =\ _{n}C_x \times p^{x} \times q^{n-x}\\ & = \frac{n!}{(n-x)!\times x!} \times p^{x} \times q^{n-x} \end{split} \end{equation}

Binomial Probability contoh Tree Diagram


Diketahui peluang keberhasilan untuk suatu operasi otot tendon adalah 90%. Bila dilakukan operasi terhadap 3 orang pasien; berapa probability untuk mendapatkan keberhasilkan tepat pada 2 orang pasien?

\begin{equation} \begin{split} P(2) &= 3 \times \frac{81}{1000}\\ &= 0.243 \end{split} \end{equation}


Binomial Probability contoh Formula


Diketahui peluang keberhasilan untuk suatu operasi otot tendon adalah 90%. Bila dilakukan operasi terhadap 3 orang pasien; berapa probability untuk mendapatkan keberhasilkan tepat pada 2 orang pasien?

\begin{equation} \begin{split} n &= 3\\ p &= \frac{9}{10}\\ q &= \frac{1}{10}\\ x &= 2 \end{split} \end{equation}\begin{equation} \begin{split} P(x) &= \frac{n!}{(n-x)! \times x!} \times p^{x} \times q^{n-x}\\ &= \frac{3!}{(3-2)! \times 2!} \times \left (\frac{9}{10} \right )^{2} \times \left (\frac{1}{10} \right )^{3-2} \\ &= 0.243 \end{split} \end{equation}


Binomial Probability: Mean, Variance & Standard Deviation


Mean

\mu = n \times p


Variance

\sigma^2 = n \times p \times q

Standard Deviation
\sigma = \sqrt{\sigma^2} = \sqrt {n \times p \times q}


Example Mean, Variance & Standard Deviation


n=30;\ \ p=0.56;\ \ q=0.44


Dari hasil pendataan, diperoleh bahwa 56% cuaca harian di Kota Malang dalam satu tahun adalah berawan.

Carilah mean dan standard deviation yang merepresentasikan jumlah hari di Kota Malang dengan cuaca harian berawan pada Bulan Juni!


\begin{equation} \begin{split} \mu &= n \times p\\ &= 30 \times 0.56\\ &= 16.8 \end{split} \end{equation}


\begin{equation} \begin{split} \sigma^2 &= n \times p \times q\\ &= 30 \times 0.56 \times 0.44\\ &\approx 7.4 \end{split} \end{equation}\begin{equation} \begin{split} \sigma &= \sqrt{\sigma^2} \\ &= \sqrt{n \times p \times q}\\ &= \sqrt{30 \times 0.56 \times 0.44}\\ &\approx 2.7 \end{split} \end{equation}

Distribusi Probabilitas Probability Distribution - PART 15

Random Variables

Random variable x merepresentasikan suatu nilai numerik yang berasosiasi dengan setiap outcome dari suatu probability experiment.

Kata “Random” mengindikasikan bahwa nilai x ditentukan secara kebetulan (by chance).

  • Discrete: Semua kemungkinan outcomes dapat dihitung (countable) atau memiliki batasan (finite)

  • Continuous: Semua kemungkinan outcomes tidak dapat dihitung (uncountable), umumnya direpresentasikan dengan nilai interval.

contoh:


Discrete

Random variable x merepresentasikan jumlah wisudawan dari Fakultas Teknologi Informasi di tahun ini.


Continuous

Random variable x merepresentasikan volume minyak goreng yang ditampung dalam sebuah tangki berkapasitas 150 Liter.


Discrete Probability Distribution

Suatu Discrete Probability Distribution mendata setiap kemungkinan nilai random variable beserta probabilitasnya.

Setiap Discrete Probability Distribution harus memenuhi kedua kondisi berikut:

0 \le P(x) \le 1 \sum P(x) = 1


Membangun Discrete Probability Distributions

  1. Bangun frequency distribution untuk seluruh outcome

  2. Hitung total jumlah kemunculan (sum of the frequencies)

  3. Hitung probability untuk setiap outcome

  4. Pastikan kedua syarat untuk suatu frequency distribution terpenuhi

Discrete Probability Distributions contoh 1:

Dilakukan pendataan tingkat kepuasan pelanggan untuk suatu mini market menggunakan likert scale dengan rentang mulai dari 1 (sangat tidak puas) sampai dengan 5 (sangat puas). Dari frequency distribution yang terbentuk, buatlah discrete probability distribution-nya!

\

Mean untuk Discrete Random Variable


Nilai mean untuk suatu discrete random variable dapat diformulasikan sebagai berikut:

\mu = \sum x P(x)

Contoh :
Berdasarkan discrete probability distribution dari pendataan tingkat kepuasan pelanggan untuk suatu mini market menggunakan likert scale dengan rentang mulai dari 1 (sangat tidak puas) sampai dengan 5 (sangat puas); hitunglah nilai mean untuk score-nya!


Standard Deviation untuk Discrete Random Variable


Nilai variance dan standard deviation untuk suatu discrete random variable dapat diformulasikan sebagai berikut:

\sigma^{2} = \sum (x-\mu)^2 P(x)\sigma = \sqrt{\sigma^{2}} = \sqrt{\sum (x-\mu)^2 P(x)}


contoh :


Berdasarkan discrete probability distribution dari pendataan tingkat kepuasan pelanggan untuk suatu mini market menggunakan likert scale dengan rentang mulai dari 1 (sangat tidak puas) sampai dengan 5 (sangat puas); hitunglah nilai standard deviation-nya!

\sigma = \sqrt{\sigma^{2}} = \sqrt{1.6164} = 1.3



Expected Value


Nilai mean dari suatu random variable merepresentasikan apa yang bisa kita harapkan untuk diperoleh dari ribuan kali percobaan (trials). Ini juga dikenal dengan istilah expected value.

E(x) = \mu = \sum x P(x)


  • Nilai probability tidak mungkin negatif, tetapi nilai expected value memungkinkan untuk negatif

  • Di banyak kasus, nilai expected value 0 dapat memiliki makna tersendiri;

    • Untuk kasus permainan: fair game

    • Untuk kasus loss & profit analysis: break-even point 


contoh :


Dalam suatu undian berhadiah, terjual sebanyak 1500 tickets. Harga untuk tiap ticket $2 dan tersedia empat hadiah untuk undian ticket: $498, $248, $148, dan $73. Kalau kita membeli satu buah ticket; berapa expected value untuk memenangkan undian (gain)?


\begin{equation} \begin{split} E(x) &= \sum x P(x)\\ &= 498 \times \frac{1}{1500} + 248 \times \frac{1}{1500} + 148 \times \frac{1}{1500} + 73 \times \frac{1}{1500} + (-2) \times \frac{1496}{1500} \\ &= -1.35 \end{split} \end{equation}



Langganan: Postingan ( Atom )
 
Copyright © 2014 Armelia Luvita. Designed by OddThemes