Kamis, 05 Juni 2014

Tree (Pohon Struktur Data)

Pohon (struktur data)


Dalam ilmu komputer, sebuah Pohon adalah suatu struktur data yang digunakan secara luas yang menyerupai struktur pohon dengan sejumlah simpul yang terhubung.

Sebuah contoh sederhana pohon tidak terurut.

                                                            

  Simpul (node)

Sebuah Simpul dapat mengandung sebuah nilai atau suatu kondisi atau menggambarkan sebuah struktur data terpisah atau sebuah bagian pohon itu sendiri. Setiap simpul dalam sebuah pohon memiliki nol atau lebih simpul anak (child nodes), yang berada dibawahnya dalam pohon (menurut perjanjian, pohon berkembang ke bawah, tidak seperti yang dilakukannya di alam). Sebuah simpul yang memiliki anak dinamakan simpul ayah (parent node) atau simpul leluhur (ancestor node) atau superior. Sebuah simpul paling banyak memiliki satu ayah. Tinggi dari pohon adalah panjang maksimal jalan ke sebuah daun dari simpul tersebut. Tinggi dari akar adalah tinggi dari pohon. Kedalaman dari sebuah simpul adalah panjang jalan ke akarnya dari simpul tersebut.


Daun (Leaf nodes)


9, 14, 19, 67 dan 76 adalah daun.
Semua simpul yang berada pada tingkat terendah dari pohon dinamakan daun (leaf node). Sejak mereka terletak pada tingkat paling bawah, mereka tidak memiliki anak satupun. Seringkali, daun merupakan simpul terjauh dari akar. Dalam teori grafik, sebuah daun adalah sebuah sudut dengan tingkat 1 selain akar (kecuali jika pohonnya hanya memiliki satu sudut; maka akarnya adalah daunnya juga). Setiap pohon memiliki setidaknya satu daun.

Dalam pohon berdasarkan genetic programming sebuah daun (juga dibilang terminal) adalah bagian terluar dari sebuah program pohon. Jika dibandingkan dengan fungsinya atau simpul dalam, daun tidak memiliki argumen. Di banyak kasus dalam daun-GP input ke programnya.

Simpul dalam (Internal nodes)

Sebuah simpul dalam adalah semua simpul dari pohon yang memiliki anak dan bukan merupakan daun. Beberapa pohon hanya menyimpan data di dalam simpul dalam, meskipun ini memengaruhi dinamika penyimpanan data dalam pohon. Sebegai contoh, dengan daun yang kosong, seseorang dapat menyimpan sebuah pohon kosong dengan satu daun.
Bagaimanapun juga dengan daun yang dapat menyimpan data, tidak dimungkinkan untuk menyimpan pohon kosong kecuali jika seseorang memberikan beberapa jenis penanda data di daun yang menandakan bahwa daun tersebut seharusnya kosong (dengan demikian pohon itu seharusnya kosong juga).

Sebaliknya, beberapa pohon hanya menyimpan data dalam daun, dan menggunakan simpul dalam untuk menampung metadata yang lain, seperti jarak nilai dalam sub pohon yang berakar pada simpul tersebut. Jenis pohon ini berguna untuk jarak yang meragukan.


Sub pohon (Subtrees)

Sebuah sub pohon adalah suatu bagian dari pohon struktur data yang dapat dilihat sebagai sebuah pohon lain yang berdiri sendiri. Simpul apapun dalam pohon P, bersama dengan seluruh simpul dibawahnya, membentuk sebuah sub pohon dari P. Sub pohon yang terhubung dengan akar merupakan keseluruhan pohon tersebut. Sub pohon yang terhubung dengan simpul lain manapun dinamakan sub pohon asli (proper subtree)

Penyusunan pohon

Terdapat dua jenis pohon. Sebuah pohon tidak terurut (unordered tree) adalah sebuah pohon dalam arti struktural semata-mata, yang dapat dikatakan memberikan sebuah simpul yang tidak memiliki susunan untuk anak dari simpul tersebut. Sebuah pohon dengan suatu susunan ditentukan, sebagai contoh dengan mengisi bilangan asli berbeda ke setiap anak dari simpul tersebut, dinamakan sebuah pohon terurut (ordered tree), dan struktur data yang dibangun di dalamnya dinamakan pohon terurut struktur data (ordered tree data structures). Sejauh ini pohon terurut merupakan bentuk umum dari pohon struktur data. Pohon biner terurut merupakan suatu jenis dari pohon terurut.


Hutan

Sebuah hutan adalah sebuah himpunan yang terdiri dari pohon terurut. Lintasan inorder, preorder, dan postorder didefinisikan secara rekursif untuk hutan.
  • inorder
  1. lewati inorder hutan yang dibentuk oleh sub pohon yang pertama dalam hutan, jika ada
  2. kunjungi akar dari pohon pertama.
  3. lewati inorder hutan yang dibentuk oleh sisa pohon dalam hutan, jika ada.
  • preorder
  1. kunjungi akar dari pohon pertama.
  2. lewati preorder hutan yang dibentuk oleh sub pohon yang pertama dalam hutan, jika ada
  3. lewati preorder hutan yang dibentuk oleh sisa pohon dalam hutan, jika ada.
  • postorder
  1. lewati postorder hutan yang dibentuk oleh sub pohon yang pertama dalam hutan, jika ada
  2. lewati postorder hutan yang dibentuk oleh sisa pohon dalam hutan, jika ada.
  3. kunjungi akar dari pohon pertama.

Penggambaran pohon

Ada banyak cara untuk menggambarkan pohon; pada umumnya penggambaran mewakili simpul sebagai rekor yang dialokasikan pada heap (bedakan dengan heap struktur data) yang mengacu pada anaknya, ayahnya, atau keduanya, atau seperti data materi dalam array, dengan hubungan diantaranya ditentukan oleh posisi mereka dalam array (contoh binary heap).


Pohon sebagai grafik

Dalam teori grafik, sebuah pohon adalah sebuah grafik asiklis yang terhubung. Pohon yang berakar merupakan sebuah grafik dengan sudut tunggal di luar sebagai akar. Dalam kasus ini, dua sudut apapun yang terhubung dengan sebuah sisi mewarisi hubungan orang tua dan anak. Sebuah grafik asiklis dengan bermacam-macam komponen yang terhubung atau himpunan dari pohon-pohon yang berakar kadang-kadang dipanggil hutan

Metode traversal

Melangkah melalui materi dari pohon, dengan arti dari hubungan antara orang tua dan anak, dinamakan menelusuri pohon, dan tindakannya adalah sebuah jalan dari pohon. Seringkali, sebuah operasi mungkin dapat dilakukan sebagai penunjuk ysng mengacu pada simpul khusus. Sebuah penelusuran dimana setiap simpul ayah dikunjungi sebelum anaknya dinamakan pre-order walk; sebuah penelusuran dimana anaknya dikunjungi sebelum ayahnya masing-masing dinamakan post-order walk.

Operasi umum

  • Menghitung seluruh materi (item)
  • Pencarian untuk sebuah materi
  • Menambahkan sebuah materi pada sebuah posisi tertentu dalam pohon
  • Menghapus sebuah materi
  • Mengeluarkan seluruh bagian dari sebuah pohon pruning
  • Menambahkan seluruh bagian ke sebuah pohon grafting
  • Menemukan akar untuk simpul apapun

Penggunaan umum

  • Memanipulasi data secara hierarki
  • Membuat informasi mudah untuk dicari
  • Memanipulasi data sorted lists




Diposting oleh di Tidak ada komentar:

Graf


Definisi

Teori graf memiliki definisi yang bervariasi. Di bawah ini merupakan definisi dasar graf dan strukturnya.

Graf

Sebuah graf atau graf tidak berarah G adalah sebuah pasangan G := (V, E) yang memenuhi kondisi:
  • V adalah sebuah himpunan, yang elemennya dinamakan sudut atau simpul
  • E adalah sebuah himpunan dari pasangan-pasangan sudut yang terpisah, yang dinamakan sisi atau garis.


Teori graf

Di matematika dan ilmu komputer, teori graf adalah cabang kajian yang mempelajari sifat-sifat graf.

Secara informal, suatu graf adalah himpunan benda-benda yang disebut simpul (vertex atau node) yang terhubung oleh sisi (edge) atau busur (arc). Biasanya graf digambarkan sebagai kumpulan titik-titik (melambangkan simpul) yang dihubungkan oleh garis-garis (melambangkan sisi) atau garis berpanah (melambangkan busur).Suatu sisi dapat menghubungkan suatu simpul dengan simpul yang sama. Sisi yang demikian dinamakan gelang (loop).

Banyak sekali struktur yang bisa direpresentasikan dengan graf, dan banyak masalah yang bisa diselesaikan dengan bantuan graf.
Jaringan persahabatan pada Facebook bisa direpresentasikan dengan graf, yakni simpul-simpulnya adalah para pengguna Facebook dan ada sisi antar pengguna jika dan hanya jika mereka berteman. Perkembangan algoritma untuk menangani graf akan berdampak besar bagi ilmu komputer.
Sebuah struktur graf bisa dikembangkan dengan memberi bobot pada tiap sisi. Graf berbobot dapat digunakan untuk melambangkan banyak konsep berbeda. Sebagai contoh jika suatu graf melambangkan jaringan jalan maka bobotnya bisa berarti panjang jalan maupun batas kecepatan tertinggi pada jalan tertentu. Ekstensi lain pada graf adalah dengan membuat sisinya berarah, yang secara teknis disebut graf berarah atau digraf (directed graph). Digraf dengan sisi berbobot disebut jaringan.
Jaringan banyak digunakan pada cabang praktis teori graf yaitu analisis jaringan. Perlu dicatat bahwa pada analisis jaringan, definisi kata "jaringan" bisa berbeda, dan sering berarti graf sederhana (tanpa bobot dan arah).

Penjelasan Lebih dalam


Suatu graph G dapat dinyatakan sebagai G=<V,E>. Graph G terdiri atas himpunan V yang berisikan simpul pada graf tersebut dan himpunan dari E yang berisi sisi pada graf tersebut. Himpunan E dinyatakan sebagai pasangan dari simpul yang ada dalam V. Sebagai contoh definisi dari graf pada gambar di atas adalah : V = \{{1,2,3,4,5,6}\} dan E=\{{(1,2),(1,5),(2,3),(3,4),(4,5),(5,2),(4,6)}\}




Gambar dengan node yang sama dengan yang di atas, tapi merupakan digraf.

Pada digraf maka pasangan-pasangan ini merupakan pasangan terurut. Untuk menyatakan digraf (gambar kedua yang menggunakan tanda panah) kita dapat menggunakan himpunan edge sebagai berikut :

E=\{{<1,2>,<1,5>,<2,5>,<3,2>,<4,3>,<5,4>,<4,6>}\}


Dalam himpunan edge untuk digraf, urutan pasangan verteks menentukan arah dari edge tersebut.
Dalam teori graf, formalisasi ini untuk memudahkan ketika nanti harus membahas terminologi selanjutnya yang berhubungan dengan graph. Beberapa terminologi berhubungan dengan teori graf :

  • Degree atau derajat dari suatu node, jumlah edge yang dimulai atau berakhir pada node tersebut. Node 5 berderajat 3. Node 1 berderajat 2.
  • Path suatu jalur yang ada pada graph, misalnya antara 1 dan 6 ada path b \rightarrow c \rightarrow g
  • Cycle siklus  path yang kembali melalui titik asal 2 f \rightarrow c \rightarrow d \rightarrow e kembali ke 2.
  • Tree merupakan salah satu jenis graf yang tidak mengandung cycle. Jika edge f dan a dalam digraf di atas dihilangkan, digraf tersebut menjadi sebuah tree. Jumlah edge dalam suatu tree adalah nV - 1. Dimana nV adalah jumlah vertex
  • Graf Tak Berarah (Undirected Graph) Graf G disebut graf tak berarah (undirected graph) jika setiap sisinya tidak berarah. Dengan kata lain (vi,vj)=(vj,vi)
  • Graf Berarah (Directed Graph) Graf G disebut graf berarah (directed graph) jika setiap sisinya berarah. Titik awal dari suatu sisi disebut verteks awal (initial vertex) sedangkan titik akhir dari suatu sisi disebut verteks akhir (terminal vertex). Loop pada graf adalah sisi yang verteks awal dan verteks akhirnya sama.



    Graf (matematika)




    Sebuah graf dengan 6 sudut dan 7 sisi.
    Dalam matematika, sebuah graf adalah objek dasar pelajaran dalam teori graf. Dalam bahasa sehari-hari, sebuah graf adalah himpunan dari objek-objek yang dinamakan titik, simpul, atau sudut dihubungkan oleh penghubung yang dinamakan garis atau sisi.

    Dalam graf yang memenuhi syarat, dimana biasanya tidak berarah, sebuah garis dari titik A ke titik B dianggap sama dengan garis dari titik B ke titik A. Dalam graf berarah, garis tersebut memiliki arah. Pada dasarnya, sebuah graf digambarkan dengan bentuk diagram sebagai himpunan dari titik-titik (sudut atau simpul) yang digabungkan dengan kurva (garis atau sisi).

Diposting oleh di 2 komentar:

Binomial

Teorema binomial

Dalam aljabar elementer, teorema binomial adalah teorema yang menjelaskan mengenai pengembangan eksponen dari penjumlahan antara dua variabel (binomial). Berdasarkan teorema ini, dimungkinkan untuk mengembangkan eksponen (x + y)n menjadi sebuah penjumlahan dari suku-suku dengan bentuk axbyc, dimana eksponen b dan c adalah bilangan bulat non negatif dengan b + c = n, dan koefisien a dari setiap suku adalah bilangan bulat positif tertentu tergantung pada n dan b. Ketika suatu eksponen adalah nol, faktor yang bereksponen nol tersebut biasanya dihilangkan dari sukunya. Contohnya,
(x+y)^4 \;=\; x^4 y^0 \,+\, 4 x^3y \,+\, 6 x^2 y^2 \,+\, 4 x y^3 \,+\, x^0y^4.


Koefisien a pada suku axbyc dikenal sebagai koefisien binomial atau (keduanya memiliki nilai yang sama). Koefisien untuk setiap variasi n dan b dapat disusun membentuk segitiga Pascal. Angka-angka ini juga muncul dalam kombinatorika, dimana menunjukkan banyaknya kombinasi yang berbeda dari unsur b yang dapat dipilih dari suatu himpunan dengan unsur sebanyak n.





Contoh

                        
                        Segitiga Pascal



Contoh paling dasar teorema binomial adalah rumus untuk x + y kuadrat
(x + y)^2 = x^2 + 2xy + y^2.\!
Koefisien binomial 1, 2, 1 muncul dalam pengembangan ini sesuai dengan baris ketiga dari segitiga Pascal. Koefisien tingkat yang lebih tinggi dari x + y sesuai dengan baris selanjutnya dari segitiga itu:
\begin{align} \\[8pt] (x+y)^3 & = x^3 + 3x^2y + 3xy^2 + y^3, \\[8pt] (x+y)^4 & = x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4, \\[8pt] (x+y)^5 & = x^5 + 5x^4y + 10x^3y^2 + 10x^2y^3 + 5xy^4 + y^5, \\[8pt] (x+y)^6 & = x^6 + 6x^5y + 15x^4y^2 + 20x^3y^3 + 15x^2y^4 + 6xy^5 + y^6, \\[8pt] (x+y)^7 & = x^7 + 7x^6y + 21x^5y^2 + 35x^4y^3 + 35x^3y^4 + 21x^2y^5 + 7xy^6 + y^7. \end{align}

Perhatikan bahwa:
  1. Eksponen dari x menurun hingga mencapai 0 (x^0=1) dengan nilai awal adalah n (n pada (x+y)^n).
  2. Eksponen dari y naik dari 0 (y^0=1) hingga mencapai n (juga n pada (x+y)^n).
  3. Baris ke-n pada segitiga Pascal akan menjadi koefisien binomial yang dikembangkan (perhatikan bahwa puncaknya adalah baris 0).
  4. Untuk setiap baris, jumlah semua unsur (yaitu jumlah dari koefisien) sama dengan 2^n.
  5. Untuk setiap baris, banyaknya unsur sama dengan n+1.
Teorema binomial dapat diterapkan ke eksponen dari binomial apapun. Contohnya,
\begin{align} (x+4)^3 &= x^3 + 3x^2(4) + 3x(4)^2 + 4^3 \\ &= x^3 + 12x^2 + 48x + 64.\end{align}
Untuk binomial dalam pengurangan, teorema binomial dapat diterapkan dengan menggunakan tanda yang berlawanan pada suku berikutnya:
(x-y)^3 = x^3 - 3x^2y + 3xy^2 - y^3.\!
Contoh lain yang berguna adalah pengembangan akar kuadrat berikut:
(1+x)^{0.5} = \textstyle 1 + \frac{1}{2}x - \frac{1}{8}x^2 + \frac{1}{16}x^3 - \frac{5}{128}x^4 + \frac{7}{256}x^5 - \cdots
(1+x)^{-0.5} = \textstyle 1 -\frac{1}{2}x + \frac{3}{8}x^2 - \frac{5}{16}x^3 + \frac{35}{128}x^4 - \frac{63}{256}x^5 + \cdots


Distribusi binomial

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,pabila 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.


Contoh:

Sebagai contoh,sebuah dadu dilempar sepuluh kali dan dihitung berapa jumlah muncul angka empat. Distribusi jumlah acak ini adalah distribusi binomial dengan n = 10 dan p = 1/6.

Contoh lain, sebuah uang logam dilambungkan tiga kali dan dihitung berapa jumlah muncul sisi depan. Distribusi jumlah acak ini merupakan distribusi binomial dengan n = 3 dan p = 1/2.




Diposting oleh di Tidak ada komentar:

Permutasi Dan Kombinasi

Permutasi


permutasi adalah menggabungkan beberapa objek dari suatu grup dengan memperhatikan urutan. Di dalam permutasi, urutan diperhatikan.
{1,2,3} tidak sama dengan {2,3,1} dan {3,1,2}
Contoh: Ada sebuah kotak berisi 3 bola masing-masing berwarna merah, hijau dan biru. Jika seorang anak ditugaskan untuk mengambil 2 bola secara acak dan urutan pengambilan diperhatikan, ada berapa permutasi yang terjadi?
Solusi: Ada 6 permutasi yaitu; M-H, M-B, H-M, H-B, B-M, B-H.
Salah satu aplikasi kombinasi dan permutasi adalah digunakan untuk mencari probabilitas suatu kejadian.


Rumus

Permutasi pengulangan

Jika urutan diperhatikan dan suatu objek dapat dipilih lebih dari sekali maka jumlah permutasinya adalah:
n^r \,
di mana n adalah banyaknya objek yang dapat dipilih dan r adalah jumlah yang harus dipilih.
Sebagai contoh, jika kamu memiliki huruf A, B, C, dan D dan kamu ingin mencari tahu ada berapa cara untuk menyusunnya dalam suatu grup yang berisi tiga angka maka kamu akan menemukan bahwa ada 43 atau 64 cara untuk menyusunnya. Beberapa cara untuk menyusunnya adalah: AAA, BBB, CCC, DDD, ABB, CBB, DBB, dst.


Permutasi tanpa pengulangan

Jika urutan diperhatikan dan setiap objek yang tersedia hanya bisa dipilih atau dipakai sekali maka jumlah permutasi yang ada adalah:
\frac{n!}{(n-r)!}
di mana n adalah jumlah objek yang dapat kamu pilih, r adalah jumlah yang harus dipilih dan ! adalah simbol faktorial.
Sebagai contoh, ada sebuah pemungutan suara dalam suatu organisasi. Kandidat yang bisa dipilih ada lima orang. Yang mendapat suara terbanyak akan diangkat menjadi ketua organisasi tersebut. Yang mendapat suara kedua terbanyak akan diangkat menjadi wakil ketua. Dan yang mendapat suara ketiga terbanyak akan menjadi sekretaris. Ada berapa banyak hasil pemungutan suara yang mungkin terjadi? Dengan menggunakan rumus di atas maka ada 5!/(5-3)! = 60 permutasi.

Umpamakan jika n = r (yang menandakan bahwa jumlah objek yang bisa dipilih sama dengan jumlah yang harus dipilih) maka rumusnya menjadi:
\frac{n!}{(n-n)!} = \frac{n!}{0!} = n! karena 0! = 1! = 1
Sebagai contoh, ada lima kotak kosong yang tersedia. Kelima kotak kosong itu harus diisi (tidak boleh ada yang kosong). Kelima kotak kosong itu hanya boleh diisi dengan angka 1,2,3,4,5. Ada berapa banyak cara untuk mengisi kotak kosong? Dengan menggunakan rumus n! maka ada 5! = 120 permutasi.

 

Kombinasi

Kombinasi adalah menggabungkan beberapa objek dari suatu grup tanpa memperhatikan urutan. Di dalam kombinasi, urutan tidak diperhatikan.
{1,2,3} adalah sama dengan {2,3,1} dan {3,1,2}.

Contoh:
Seorang anak hanya diperbolehkan mengambil dua buah amplop dari tiga buah amplop yang disediakan yaitu amplop A, amplop B dan amplop C.Tentukan ada berapa banyak kombinasi untuk mengambil dua buah amplop dari tiga buah amplop yang disediakan?

Solusi: Ada 3 kombinasi yaitu; A-B, A-C dan B-C.


Rumus

Kombinasi tanpa pengulangan

Ketika urutan tidak diperhatikan akan tetapi setiap objek yang ada hanya bisa dipilih sekali maka jumlah kombinasi yang ada adalah:
{{n!} \over {r!(n - r)!}} = {n \choose r}
Di mana n adalah jumlah objek yang bisa dipilih dan r adalah jumlah yang harus dipilih.
Sebagai contoh, kamu mempunyai 5 pensil warna dengan warna yang berbeda yaitu; merah, kuning, hijau, biru dan ungu. Kamu ingin membawanya ke sekolah. Tapi kamu hanya boleh membawa dua pensil warna. Ada berapa banyak cara untuk mengkombinasikan pensil warna yang ada? Dengan menggunakan rumus di atas maka ada 5!/(5-2)!(2)! = 10 kombinasi.


Kombinasi pengulangan

Jika urutan tidak diperhatikan dan objek bisa dipilih lebih dari sekali, maka jumlah kombinasi yang ada adalah:
{{(n + r - 1)!} \over {r!(n - 1)!}} = {{n + r - 1} \choose {r}} = {{n + r - 1} \choose {n - 1}}
Di mana n adalah jumlah objek yang bisa dipilih dan r adalah jumlah yang harus dipilih. Sebagai contoh jika kamu pergi ke sebuah toko donat. Toko donut itu menyediakan 10 jenis donat berbeda. Kamu ingin membeli tiga donat. Maka kombinasi yang dihasilkan adalah (10+3-1)!/3!(10-1)! = 220 kombinasi.



Diposting oleh di Tidak ada komentar:
Langganan: Postingan (Atom)