TREE

Pengertian dan Konsep Binary Tree

Pengertian Tree dalam Struktur Data

 Merupakan salah satu bentuk Struktur Data tidak linier Yang menggambarkan hubungan Yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree Bisa didefinisikan sebagai kumpulan Simpul / node dengan Satu elemen KHUSUS Yang disebut root Dan Node lainnya terbagi menjadi Himpunan-Himpunan Yang tak saling berhubungan Satu sama lainnya (disebut subtree). Untuk jelasnya, di Bawah Akan diuraikan istilah-istilah umum dalam tree

• Parent : predecssor satu level di atas suatu node.
• Child : successor satu level di bawah suatu node.
• Sibling : node-node yang memiliki parent yang sama dengan suatu node.
• Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
• Size : banyaknya node dalam suatu tree.
• Height : banyaknya tingkatan/level dalam suatu tree.
• Root : satu-satunya node khusus dalam tree yang tak punya predecssor.
• Leaf : node-node dalam tree yang tak memiliki seccessor.
• Degree : banyaknya child yang dimiliki suatu node. 

Pengertian Binaary Tree dalam Struktur Data

Pohon biner adalah pohon dengan syarat bahwa tiap node hanya memiliki boleh maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua anak/child.

Gambar Binary Tree

Node pada Binary Tree

                         Jumlah maksimum node pada setiap tingkat adalah 2ⁿ, Node pada binary tree maksimumnya berjumlah 2ⁿ-1.

SUMBER:

http://dinda-dinho.blogspot.com/2013/07/pengertian-dan-konsep-binary-tree.html

GRAF

Pengertian dan Konsep Graph dalam Struktur Data

Suatu graph didefinisikan oleh himpunan verteks dan himpunan sisi (edge). keterhubungan antara verteks. Biasanya untuk suatu graph G digunakan notasi matematis. Verteks menyatakan entitas-entitas data dan sisi menyatakan G = (V, E) Dimana :
G = Graph
V = Simpul atau Vertex, atau Node, atau Titik
E = Busur atau Edge, atau arc

V adalah himpunan verteks dan E himpunan sisi yang terdefinisi antara pasangan-pasangan verteks. Sebuah sisi antara verteks x dan y ditulis {x,y}. Suatu graph H = (V1, E1) disebut subgraph dari graph G jika V1 adalah himpunan bagian dari V dan E1 himpunan bagian dari E. Cara pendefinisian lain untuk graph adalah dengan menggunakan himpunan keterhubungan langsung Vx. Pada setiap verteks x terdefinisi Vx sebagai himpunan dari verteks-verteks yang adjacent dari x. Secara formal: Vx = {y | (x,y) -> E}


Dalam digraph didefinisikan juga terminologi-terminologi berikut ini.Predesesor dari suatu verteks x (ditulis Pred(x)) adalah himpunan semua vertex yang adjacent ke x. Suksesor dari verteks x (ditulis Succ(x)) adalah himpunan

Pokok bahasan sebelumnya menjelaskan bahwa graf menampilkan visualisasi data dan hubungannya. Sedangkan jika berbicara masalah implementasi struktur data graf itu sendiri, isu utama yang dihadapi adalah bagaimana informasi itu disimpan dan dapat diakses dengan baik, ini yang dapat disebut dengan representasi internal.

Secara umum terdapat dua macam representasi dari struktur data graf yang dapat diimplementasi. Pertama, disebut adjacency list, dan diimplementasi dengan menampilkan masing-masing simpul sebagai sebuah struktur data yang mengandung senarai dari semua simpul yang saling berhubungan. Yang kedua adalah representasi berupa adjacency matrix dimana baris dan kolom dari matriks (jika dalam konteks implementasi berupa senarai dua dimensi) tersebut merepresentasikan simpul awal dan simpul tujuan dan sebuah entri di dalam senarai yang menyatakan apakah terdapat sisi di antara kedua simpul tersebut.

Adjacency List
Dalam teori graf, adjacency list merupakan bentuk representasi dari seluruh sisi atau busur dalam suatu graf sebagai suatu senarai. Simpul-simpul yang dihubungkan sisi atau busur tersebut dinyatakan sebagai simpul yang saling terkait. Dalam implementasinya, hash table digunakan untuk menghubungkan sebuah simpul dengan senarai berisi simpul-simpul yang saling terkait tersebut.

Graf pada gambar diatas dapat dideskripsikan sebagai senarai {a,b},{a,c},{b,c}. Dan representasi adjacency list dapat digambarkan melalui tabel di bawah ini.

Tabel 1. Representasi Adjacency List

Vertex	Adjacency	Array of Adjacent
a	adjacent to	b,c
b	adjacent to	a,c
c	adjacent to	a,b

Salah satu kekurangan dari teknik representasi ini adalah tidak adanya tempat untuk menyimpan nilai yang melekat pada sisi. Contoh nilai ini antara lain berupa jarak simpul, atau beban simpul.

Adjacency Matrix
Adjacency Matrix merupakan representasi matriks nxn yang menyatakan hubungan antar simpul dalam suatu graf. Kolom dan baris dari matriks ini merepresentasikan simpul-simpul, dan nilai entri dalam matriks ini menyatakan hubungan antar simpul, apakah terdapat sisi yang menghubungkan kedua simpul tersebut. Pada sebuah matriks nxn, entri non-diagonal aij merepresentasikan sisi dari simpul i dan simpul j. Sedangkan entri diagonal aii menyatakan sisi kalang(loop) pada simpul i.

Gambar diatas merupakan adjacency matrix yang berkorelasi dengan graf tak berarah pada gambar 4. Kolom dan baris pada matriks merupakan simpul- simpul berlabel 1-6. Kelebihan dari adjacency matrix ini adalah elemen matriksnya dapat diakses langsung melalui indeks, dengan begitu hubungan ketetanggan antara kedua simpul dapat ditentukan dengan langsung. Sedangkan kekurangan pada representasi ini adalah bila graf memiliki jumlah sisi atau busur yang relative sedikit, karena matriksnya bersifat jarang yaitu hanya mengandung elemen bukan nol yang sedikit. Kasus seperti ini merugikan, karena kebutuhan ruang memori untuk matriks menjadi boros dan tidak efisien karena komputer menyimpan elemen 0 yang tidak perlu.

SUMBER:

http://dinda-dinho.blogspot.com/2013/11/pengertian-dan-konsep-graph-dalam.html

DISTRIBUSI BINOMIAL

DEFINISI

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,taitu sebasar ½..(Ronald E. Walpole)
CIRI – CIRI DISTRIBUSI BINOMIAL
Percobaan diulang sebanyak n kali.
Hasil setiap ulangan dapat dikategorikan ke dalam 2 kelas, misal :
“BERHASIL” atau “GAGAL”;
“YA” atau “TIDAK”;
“SUCCESS” or “FAILED”.
Peluang berhasil / sukses dinyatakan dengan p dan dalam setiap ulangan nilai p tetap. Peluang gagal dinyatakan dengan q, dimana q = 1-p.
Setiap ulangan bersifat bebas (independen) satu dengan lainnya.
Percobaannya terdiri atas n ulangan (Ronald.E Walpole)
Nilai n < 20 dan p > 0.05
RUMUS DISTRIBUSI BINOMIAL
b(x;n,p) = nCx px qn-x dimana x = 0,1,2,3,…,n
n : banyaknya ulangan
x : banyaknya keberhasilan dalam peubah acak x
p : peluang berhasil dalam setiap ulangan
q : peluang gagal, dimana q = 1-p dalam setiap ulangan
Catatan : Agar anda mudah dalam membedakan p dengan q, anda harus dapat menetapkan mana kejadian SUKSES dan mana kejadian GAGAL. Anda dapat menetapkan bahwa kejadian yang menjadi pertanyaan atau ditanyakan adalah = kejadian SUKSES.
Contoh Distribusi Binomial :

1.Berdasarkan data biro perjalanan PT Mandala Wisata air, yang khusus menangani perjalanan wisata turis manca negara, 20% dari turis menyatakan sangat puas berkunjung ke Indonesia, 40% menyatakan puas, 25% menyatakan biasa saja dan sisanya menyatakan kurang puas. Apabila kita bertemu dengan 5 orang dari peserta wisata turis manca negara yang pernah berkunjung ke Indonesia, berapakah probabilitas :
a.Paling banyak 2 di antaranya menyatakan sangat puas.
b.Paling sedikit 1 di antaranya menyatakan kurang puas
c.Tepat 2 diantaranya menyatakan biasa saja
d.Ada 2 sampai 4 yang menyatakan puas
Jawab :
a.X ≤ 2
Lihat tabel dan lakukan penjumlahan sebagai berikut :
b(x; n, p) = b(0; 5, 0.20) + b(1; 5, 0.20) + b(2; 5, 0.20) =
0.32768 + 0.40960 + 0.20480 = 0.94208 atau
b(x=0) = 5C0 (0.20)0 (0.80)5 = 0.32768
b(x=1) = 5C1 (0.20)0 (0.80)4 = 0.40960
b(x=2) = 5C2 (0.20)0 (0.80)3 = 0.20480
+
Maka hasil x ≤ 2 adalah = 0.94208
b.X ≥ 1
Lihat tabel dan lakukan penjumlahan sebagai berikut :
b(1; 5, 0.15) + b(2; 5, 0.15) + b(3; 5, 0.15) + b(4; 5, 0.15) + b(5; 5, 0.15) =
0.3915 + 0.1382 + 0.0244 + 0.002 + 0.0001 = 0.5562 atau
b(x ≥1; 5, 0.15) = 1 – b(x = 0)
1 – 5C0 (0.15)0 (0.85)5
1 – 0.4437 = 0.5563
c.X = 2
b(2; 5, 0.25) = 0.2637
d.X ≤ 2 X ≤ 4

Lihat tabel dan lakukan penjumlahan sebagai berikut :
b(2; 5, 0.40) + b(3; 5, 0.40) + b(4; 5, 0.40) = 0.3456 + 0.2304 + 0.0768 = 0.6528
Analisis masing – masing point :
a.Sebanyak paling banyak 2 dari 5 orang dengan jumlah 0.94208 atau 94,28% yang menyatakan sangat puas adalah sangat besar.
b.Paling sedikit 1 dari 5 orang (berarti semuanya) dengan jumlah 0,5563 atau 55,63% yang menyatakan kurang puas dapat dikatakan cukup besar (karena lebih dari 50%).
c.Tepat 2 dari 5 orang yang menyatakan biasa saja dengan jumlah 0,2637 atau 26,37% adalah kecil (karena dibawah 50%).
d.Ada 2 sampai 4 yang menyatakan puas dengan jumlah 0,6528% atau 65,28% dapat dikatakan cukup besar.
Analisis keseluruhan :
A. Persentase
Jika diambil persentase terbesar tanpa memperhatikan jumlah X, maka persentase terbesar ada di point pertama (a) yaitu 94,28% yang menyatakan sangat puas. Hal tersebut menandakan banyak turis manca negara yang sangat menyukai Indonesia.
B. Nilai X
Jika dilihat dari jumlah X, maka perlu diperhatikan point kedua (b). Jumlah X adalah paling sedikit 1 dari 5 orang (berarti X>=1) yaitu 55,63% yang menyatakan kurang puas . Hal tersebut berarti kelima (semua) turis manca negara kurang puas terhadap kunjungannya ke Indonesia.

2.Kepala bagian produksi PT SAMSUNG melaporkan bahwa rata - rata produksi televisi yang rusak setiap kali produksi adalah sebesar 15 %. Jika dari total produksi tersebut diambil secara acak sebanyak 4 buah televisi, berapakah perhitungan dengan nilai probabilitas 2 ?
Jawab : p ( rusak ) = 0,15, q ( baik ) = 0,85, x = 2, n = 4
Rumus : b ( x ; n ; p ) = nCx px q n-x
b (x = 2 ; 4 ; 0,12 ) = 4C2 (0,15)2 (0,85)(4 – 2)
= 0,0975
Analisis : Dengan jumlah 0,0975 atau 9,75% dari sampel acak sebanyak 4 buah televisi dan rata – rata produk rusak setiap kali produksi adalah sebesar 15%, dapat dikatakan kecil. Namun pada kenyataannya, meskipun dilihat secara persentase kecil (hanya 9,75%) yang namanya produk rusak harus tetap dikurangi atau bahkan dihilangkan untuk mengurangi kerugian.
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
Contoh Rata – rata dan Ragam Distribusi Binomial :
Untuk b (5; 5, 20) dimana x = 5, n = 5 dan p = 0.20
q = 1-p ; q = 1-0.20 = sehingga q = 0.80
maka : m = 5 x 0.20 = 1 s2 = 5 x 0.20 x 0.8 = 0.80 s = Ö 0.80 = 0.8944

SUMBER

http://cyber-learn.blogspot.com/2008/09/modul-distribusi-binomial.html

Permutasi dan Kombinasi

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 _nP_r atau ⁿP_r.
Rumusnya adalah

P(n,r) = nPr = nPr =	n!
	(n - r)!

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.

P(3,2) = 3P2 = 3P2 =	3!
	(3 - 2)!
=	3 × 2 × 1
	1!
=	6
	1
=	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, ⁵P₅ = ^5!/_(5-5)! = ^5!/_0! = ^{(5 × 4 × 3 × 2 × 1)}/₁ = 120.

Seperti terlihat dari contoh di atas, jika n = r, rumus untuk ⁿP_r = 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 _nC_r atau ⁿC_r.

Rumusnya adalah:

C(n,r) = nCr = nCr =	n!
	r! (n - r)!

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.

C(3,2) = 3C2 = 3C2 =	3!
	2! (3 - 2)!
=	3 × 2 × 1
	2 × 1 × 1!
=	6
	2
=	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, ⁵C₅ = ^4!/_3!(4-3)! = ^{(4 × 3 × 2 × 1)}/_{(3 × 2 × 1) 1!} = ²⁴/₆ = 4.

Untuk kombinasi, jika n = r, banyaknya kombinasi selalu 1.

SUMBER:

http://www.idomaths.com/id/permutasi_kombinasi.php