PERMUTASI
Permutasi adalah pengaturan elemen-elemen dari sebuah himpunan dimana urutan dari elemen elemen tersebut diperhatikan.
Secara matematik, dari sebuah himpunan yang mempunyai elemen sebanyak
n, banyaknya permutasi dengan ukuran (permutasi dengan jumlah elemen)
r ditulis sebagai
P(n,r) atau nPr atau nPr.
Rumusnya adalah
dimana
n! (n faktorial) = n × (n-1) × (n-2) × ... × 1 dan 0! = 1.
Contoh, dari himpunan huruf-huruf {a,b,c}, permutasi-permutasi dengan
ukuran 2 (ambil 2 elemen dari himpunan tersebut) adalah {a,b}, {b,a},
{a,c}, {c,a}, {b,c}, dan {c,b}. Perhatikan bahwa
urutan dari elemen-elemen itu adalah penting, dengan kata lain {a,b} adalah berbeda dengan {b,a}.
Banyaknya permutasi adalah 6.
Contoh lainnya: Berapa banyaknya cara untuk mengatur 5 buku yang berbeda di atas rak buku?
Jawaban: Di sini,
n = 5 dan r = 5.
Jadi,
5P5 = 5!/(5-5)! = 5!/0! = (5 × 4 × 3 × 2 × 1)/1 = 120.
Seperti terlihat dari contoh di atas, jika
n = r, rumus untuk
nPr = n!.
KOMBINASI
Kombinasi adalah pengaturan elemen-elemen dari sebuah himpunan dimana urutan dari elemen elemen tersebut tidak diperhatikan.
Dari sebuah himpunan yang memiliki
n elemen, banyaknya kombinasi yang berukuran (kombinasi dengan jumlah elemen)
r ditulis sebagai
C(n,r) atau nCr atau nCr.
Rumusnya adalah
dimana
n! (n faktorial) = n × (n-1) × (n-2) × ... × 1 dan 0! = 1.
Contoh, dari himpunan huruf-huruf {a,b,c} kombinasi-kombinasi yang
berukuran 2 (ambil 2 elemen dari himpunan tersebut) adalah {a,b}, {a,c},
and {b,c}. Perhatikan bahwa
urutan dari elemen-elemen itu tidak penting, dengan kata lain {b,a} adalah dianggap sama dengan {a,b}.
Banyaknya kombinasi adalah 3.
Contoh lainnya: Sebuah keranjang berisi sebuah apel, sebuah jeruk,
sebuah jambu, dan sebuah pisang. Berapa banyaknya kombinasi yang terdiri
dari 3 macam buah?
Jawaban: Di sini,
n = 4 dan r = 3.
Jadi,
5C5 = 4!/3!(4-3)! = (4 × 3 × 2 × 1)/(3 × 2 × 1) 1! = 24/6 = 4.
Untuk kombinasi, jika
n = r, banyaknya kombinasi selalu 1.
Distribusi Binomial
Distribusi Probabilitas
Kunci aplikasi probabilitas dalam statistik adalah
memperkirakan terjadinya peluang/probabilitas yang dihubungkan dengan
terjadinya peristiwa tersebut dalam beberapa keadaan.
Jika kita mengetahui keseluruhan probabilitas dari kemungkinan
outcome yang terjadi, seluruh probabilitas kejadian tersebut akan membentuk
suatu distribusi probabilitas.
Distribusi
binomial adalah salah
satu distribusi probbabilitas diskrit yang paling sering digunakan dalam
analisis statistic modern. Di bidang teknik, distribusi ini erat kaitannya
dengan pengendalian kualitas (quality control).
Dalam teori probabilitas
dan statistika, distribusi binomial adalah distribusi probabilitas diskret jumlah
keberhasilan dalam n percobaan
ya/tidak (berhasil/gagal) yang saling bebas, dimana setiap hasil percobaan
memiliki probabilitas p.
Eksperimen berhasil/gagal juga disebut percobaan bernoulli. Ketika n = 1, distribusi
binomial adalah distribusi bernoulli. Distribusi binomial merupakan dasar
dari uji binomial
dalam uji signifikansi statistik.
Distribusi ini seringkali
digunakan untuk memodelkan jumlah keberhasilan pada jumlah sampel n dari jumlah populasi N. Apabila sampel tidak saling bebas
(yakni pengambilan sampel tanpa pengembalian), distribusi yang dihasilkan
adalah distribusi
hipergeometrik, bukan
binomial. Semakin besar N
daripada n, distribusi binomial
merupakan pendekatan yang baik dan banyak digunakan.
Distribusi Binomial
adalah suatu distribusi probabilitas yang dapat digunakan bilamana suatu proses
sampling dapat diasumsikan sesuai dengan proses Bernoulli. Misalnya, dalam
perlemparan sekeping uang logam sebanyak 5 kali, hasil setiap ulangan mungkin
muncul sisi gambar atau sisi angka. Begitu pula, bila kartu diambil
berturut-turut, kita dapat memberi label "berhasil" bila kartu yang
terambil adalah kartu merah atau ”gagal” bila yang terambil adalah kartu hitam.
Ulangan-ulangan tersebut bersifat bebas dan peluang keberhasilan setiap ulangan
tetap sama, yaitu sebesar 0,5. (Ronald E. Walpole)
Distribusi Binomial biasa dirumuskan seperti :
B
(x;n,p) = ncxpxqn-x
Dimana :
x = 0,1,2,3,.....,n
n = banyaknya ulangan
x = banyaknya kerberhasilan dalam peubah acak x
p = Peluang berhasil dalam setiap ulangan
q = Peluang gagal, dimana q = 1 - p
dalam setiap ulangan
Contoh :
Dadu dilemparkan 5 kali, diharapkan keluar mata 6 dua kali,
maka kejadian ini dapat ditulis b(2,5,1/6)
x=2, n=5, p=1/6
Eksperimen Binomial
Satu atau serangkaian eksperimen dinamakan eskperimen
binomial bila dan hanya bila eksperimen yang bersangkutan terdiri dari
percobaan-percobaan Bernoulli atau percobaan-percobaan binomial.
Jika hanya berminta untuk mengetahui apakah hasil suatu
percobaan disebut gagal atau sukses, maka ruang sampel yang merumuskan
percobaan diatas harus memuat 2 unsur saja yaitu, unsur B bagi sukses dan unsur
G bagi gagal. Singkatnya, probabilita kedua unsur diatas dapat dinyatakan
sebagai,
p ({B})
= p, p ({G}) = 1 - p = q
Dimana : p + q = 1 dan 0 < p <1
Eksperimen ini merupakan n kali percobaan Bernoulli, sehingga
harus memenuhi kondisi-kondisi berikut:
1. Jumlah
percobaan n adalah konstanta yang telah ditentukan sebelumnya (dinyatakan
sebelum eksperimen dimulai).
2. Setiap
pengulangan eksperimen, biasa disebut percobaan (trial), hanya dapat
menghasilkan satu dari dua keluaran yang mungkin sukses ataupun gagal.
3. Probabilitas
sukses p, dan demikian juga probabilitas gagal q = 1 – p selalu konstan dalam
setiap percobaan.
4. Setiap
percobaan saling bebas secara statistic, yang berarti keluaran suatu percobaan
tidak berpengaruh pada keluaran percobaan lainnya.
Syarat Distribusi Binomial
1.
Jumlah trial
merupakan bilangan bulat Contoh melambungkan coin 2 kali, tidak mungkin2
½ kali.
2.
Setiap
eksperiman mempunya idua outcome (hasil). Contoh:sukses/gagal,laki/perempuan,
sehat/sakit,setuju/tidaksetuju.
3.
Peluang
sukses sama setiap eksperimen.
Contoh:
Jika pada lambungan pertama peluang keluar mata H/sukses adalah ½, pada
lambungan seterusnya juga ½. Jika sebuah dadu, yang diharapkan adalah keluar
mata lima, maka dikatakan peluang sukses adalah 1/6, sedangkan peluang gagal
adalah 5/6.Untuk itu peluang sukses dilambangkan p, sedangkan peluang gagal
adalah (1-p) atau biasa juga dilambangkan q, di mana q = 1-p.
Ciri-ciri Distribusi Binomial
Distribusi
Binomial dapat diterapkan pada peristiwa yang memiliki ciri-ciri percobaan
Binomial atau Bernoulli trial sebagai berikut :
1.
Setiap
percobaan hanya mempunyai 2 kemungkinan hasil : sukses(hasil yang dikehendakai,
dan gagal(hasil yang tidak dikehendaki)
2.
Setiap
percobaan bersifat independen atau dengan pengembalian.
3.
Probabilita
sukses setiap percobaan harus sama, dinyatakan dengan p. Sedangkan probabilita
gagal dinyatakan dengan q, dan jumlah p dan q harus sama dengan satu.4.
Jumlah
percobaan, dinyatakan dengan n, harus tertentu jumlahnya.
Penerapan Distribusi Binomial
Beberapa
kasus dimana distribusi normal dapat diterapkan yaitu :
1.
Jumlah
pertanyaan dimana anda dapat mengharapkan bahwa terkaan anda benar dalam ujian
pilihan ganda.
2.
Jumlah
asuransi kecelakaan yang harus dibayar oleh perusahaan asuransi.
3.
Jumlah
lemparan bebas yang dilakukan oleh pemain basket selama satu musim.
Rata-rata
dan Ragam Distribusi Binomial
Rata – rata μ = n . p
Ragam σ2 = n . p . q
n : ukuran populasi
p : peluang berhasil dalam setiap ulangan
q : peluang gagal, dimana q = 1-p dalam setiap ulangan
GRAF
Seperti yang sudah
dipelajari pada mata kuliah Struktur Diskrit, graf dapat digunakan untuk
merepresentasikan berbagai hal. Graf terbagi menjadi beberapa bagian yaitu graf
berarah dan tak berarah. Dalam bahasan kali ini yang akan digunakan untuk
merepresentasikan jalan dan tempat-tempat acuannya adalah graf berarah.
Graf Berarah
Sebuah graf
terarah atau digraf G terdiri dari suatu himpunan V dari verteks-verteks (atau
simpul-simpul) dan suatu himpunan E dari rusuk-rusuk (atau busur-busur)
sedemikian rupa sehingga setiap rusuk e ∈
E menghubungkan pasangan verteks terurut.
Gambar 2 :
Contoh graf berarah
Graf berarah dianggap yang
paling tepat untuk merepresentasikan masalah ini karena jalan-jalan di bumi
memiliki arah dan tidak semua jalan “dua arah” ada juga jalan “satu arah”. Oleh
karena itu dengan graf berarah masalah tersebut dapat terselesaikan. Sehingga
jalan tercepat menuju ke tempat tujuan dapat ditemukan tanpa perlu khawatir
akan jalan “satu arah”.
Tetapi masih ada masalah
selanjutnya yaitu kepadatan jalan-jalan di perkotaan yang sering menimbulkan
kemacetan terutama di saat liburan seperti libur Natal dan tahun baru 2008 di
Kota Bandung sangat padat akan kendaraan dari luar kota dan juga dari dalam
kota. Selain itu banyaknya jalan-jalan yang rusak akibat cuaca yang tidak
menentu sehingga banyak perbaikan jalan yang menyebabkan jalan ditutup atau
macet total. Sebagai contoh adalah jalan yang hancur akibat ledakan pipa PDAM
di Jalan L.L.R.E. Martadinata, Bandung menyebabkan jalan tidak bias dilalui
kendaraan sehingga menimbulakan kemacetan dan perlu dicari jalan alternatif.
Masalah ini dapat diselesaikan dengan merepresentasikan gambar jalan yang
diterima oleh perangkat navigasi GPS dari satelit dengan graf berbobot.
Graf
Berbobot
Sebuah graf dengan bilangan-bilangan
pada rusuk-rusuknya disebut graf berbobot (weighted graph). Dalam sebuah graf
berbobot, panjang lintasan adalah jumlah bobot rusuk-rusuk dalam lintasan.
Dalam bahasan ini bobot setiap lintasan tidak hanya merepresentasikan panjang
lintasan saja, tetapi juga merepresentasikan tingkat kepadatan/ kemacetan
jalan/lintasan. Jadi akumulasi dari panjang jalan dari suatu titik/tempat acuan
di jalan yang nyata ke titik berikutnya dan tingkat kepadatan pada jalan
tersebut merupakan bobot untuk setiap lintasan.
Gambar 3 :
Contoh graf berbobot tak berarah.
Semakin besar bobot suatu
lintasan maka akan menghabiskan waktu yang semakin lama untuk melalui lintasan
itu. Jadi bobot pada graf berbanding lurus dengan waktu tempuh dan efektifitas
jalan untuk dilalui.
Untuk merepresentasikan
gambar jalan yang diterima dari satelit pada perangkat navigasi GPS maka kedua
bentuk graf yang sudah dibahas di atas perlu digabung sehingga membentuk graf
berbobot dan berarah. Dengan graf berbobot dan berarah maka kedua masalah utama
untuk merepresentasikan lintasan atau jalan dapat diatasi, yaitu masalah
jarak/panjang lintasan dan tingkat kepadatan jalan. Sekarang masih ada satu
masalah yang sangat penting untuk dicari solusinya yaitu mengambil keputusan
jalan mana yang akan dipilih. Hal tersebut akan dilakukan pendekatan dengan
menggunakan pohon keputusan.
POHON
KEPUTUSAN /TREE
Secara umum pohon keputusan
digunakan untuk memodelkan persoalan yang terdiri dari serangkaian keputusan yang
mengarah ke solusi. Tiap simpul pada pohon keputusan menyatakan keputusan,
setiap daun menyatakan solusi dan seitap cabang menyatakan keputusan yang
diambil. Pohon keputusan adalah salah satu metode klasifikasi yang paling
populer karena mudah untuk diinterpretasi oleh manusia. Pohon keputusan adalah
model prediksi menggunakan struktur pohon atau struktur berhirarki. Konsep dari
pohon keputusan adalah mengubah data menjadi pohon keputusan dan aturan-aturan
keputusan. Manfaat utama dari penggunaan pohon keputusan adalah kemampuannya
untuk mem-break down proses pengambilan keputusan yang kompleks menjadi lebih
simpel sehingga pengambil keputusan akan lebih menginterpretasikan solusi dari
permasalahan.
Kelebihan dari metode pohon
keputusan adalah:
v Daerah pengambilan keputusan
yang sebelumnya kompleks dan sangat global, dapat diubah menjadi lebih simpel
dan spesifik.
v
Eliminasi perhitungan-perhitungan yang tidak diperlukan,
karena ketika menggunakan metode pohon keputusan maka sample diuji hanya
berdasarkan kriteria atau kelas tertentu.
v
Fleksibel untuk memilih fitur dari internal node yang
berbeda, fitur yang terpilih akan membedakan suatu kriteria dibandingkan
kriteria yang lain dalam node yang sama. Kefleksibelan metode pohon keputusan
ini meningkatkan kualitas keputusan yang dihasilkan jika dibandingkan ketika
menggunakan metode penghitungan satu tahap yang lebih konvensional.
v Dalam analisis multivariat,
dengan kriteria dan kelas yang jumlahnya sangat banyak, seorang penguji
biasanya perlu untuk mengestimasikan baik itu distribusi dimensi tinggi ataupun
parameter tertentu dari distribusi kelas tersebut. Metode pohon keputusan dapat
menghindari munculnya permasalahan ini dengan menggunakan criteria yang
jumlahnya lebih sedikit pada setiap node internal tanpa banyak mengurangi
kualitas keputusan yang dihasilkan.
Kekurangan metode pohon
keputusan, yaitu:
Ø Terjadi overlap terutama
ketika kelas-kelas dan criteria yang digunakan jumlahnya sangat banyak. Hal
tersebut juga dapat menyebabkan meningkatnya waktu pengambilan keputusan dan
jumlah memori yang diperlukan.
Ø
Pengakumulasian jumlah eror dari setiap tingkat dalam sebuah
pohon keputusan yang besar.
Ø Kesulitan dalam mendesain
pohon keputusan yang optimal. Hasil kualitas keputusan yang didapatkan dari
metode pohon keputusan sangat tergantung pada bagaimana pohon tersebut
didesain.
Gambar 4 : Contoh pohon keputusan
Gambar di atas adalah contoh
pohon keputusan apakah akan pergi bermain atau tidak dengan cuaca sebagai
faktor penentu. Contoh pohon keputusan di atas sangat sesuai untuk menantukan
jalan yang akan dipilih dengan panjang lintasan dan tingkat kepadatan jalan
(bobot lintasan) sebagai faktor penentu. Contoh di atas juga menggambarkan tata
cara yang serupa dalam pengambilan keputusan jalan mana / solusi mana yang terbaik dan akan
diinformasikan pada pengguna sistem navigasi GPS.
Meskipun memiliki beberapa
kekurangan, tetapi metode pengambilan keputusan dengan pohon keputusan ini
merupakan pendekatan yang paling simpel, sederhana dan sesuai untuk menentukan jalan
mana yang paling cepat, dekat dan efektif yang akan dipilih pada sistem
navigasi GPS. Metode pohon keputusan ini melengkapi data yang telah diubah
menjadi bentuk graf berarah dan berbobot lalu akan memberikan solusi jalan/
lintasan terbaik pada sistem navigasi GPS.
Ketika menemui cabang jalan
atau simpul pada graf berarah dan berbobot yang telah dibentuk, kita tidak
dapat langsung memilih jalan / lintasan dengan bobot terkecil begitu saja
karena jalan/lintasan dari suatu titik asal ke titik tempat tujuan belum tentu
hanya terdiri dari sebuah lintasan saja, sehingga lintasan tercepat dan
terefektif tidak dapat ditentukan jika hanya memilih jalan dengan bobot
terkecil setiap kali menemui cabang jalan atau simpul pada graf yang telah
terbentuk dari data yang diterima dari satelit pada sistem navigasi GPS. Dengan
meenggunakan pohon keputusan maka kita dapat menentukan jalan mana yang
terbaik, lintasan yang pada awalnya memiliki bobot yang tinggi mungkin saja
pada pilihan jalan / cabang berikutanya adapat menghantarkan kita pada tujuan
dengan lebih cepat karena jalan selanjutnya memiliki bobot yang kecil.
Sedangkan jalan / lintasan yang bobot awalnya kecil mungkin saja
lintasan-lintasan berikutnya berbobot besar dan akan semakin menghambat jalan
ke titik tujuan. Untuk itu diperlukan pohon keputusan dan algoritma pohon
secara rekusif untuk setiap cabang pohon agar dapat memperoleh solusi terbaik
dengan cara yang efisien. Setiap cabang jalan pada graf atau pada kehidupan
nyata merupakan simpul atau node pada keputusan dimana pada pohon akan
dilakukan perbandingan bobot pada masing-masing cabang jalan / lintasan dan
begitselanjutanya untuk setiap cabang jalan yang ditemui, kita akan dihadapkan
pada pilihan yang harus diambil pada pohon keputusan sampai diperoleh jalan
yang terbaiak lalu diinformasikan pada pengguna sistem navigasi GPS cabang
jalan mana atau arah mana yang harus dipilih.
sumber
http://suebzains.blogspot.com/2012/05/matematika-diskrit.html
sumber
http://syfajaar.blogspot.com/2013/11/distribusi-binomial.html
sumber
http://www.idomaths.com/id/permutasi_kombinasi.php
Tampilan berisi
ucapan selamat datang dan pilihan untuk mendaftar atau langsung masuk dalam
aplikasi web ini.
