Buatlah contoh bagan pertandingan sepakbola dengan sistem gugur yang diikuti oleh 10 klub dimana pada akhir turnament tersisa 1 peserta sebagai juara ! , dan tentukan jumlah pertandingan yang terjadi !
Solusi :
Bagan pertandingan sistem gugur adalah contoh pohon biner teratur, sehingga kita dapat membuat contoh bagannya sebagai berikut :
Dalam pohon biner berlaku i = t – 1 , dimana i menyatakan banyak simpul cabang dan t menyatakan banyaknya daun. Dengan rumus di atas maka dapat diketahui banyaknya pertandingan = 8 – 1 = 7 pertandingan.
Aplikasi Konigsberg Bridge Problem (Teka-Teki Jembatan Konigsberg) yang berawal muncul dari penduduk sebuah kota bernama yang dahulu bernama Konigsberg di Jerman. Dalam sejarahnya, seorang matematikawan Swiss yang bernama Leonhard Euler menulis jurnal pada tahun 1736 mengenai teori Graf dengan judul “Seven Bridge of Konigsberg”. Analisis Euler tersebut membahas ada atau tidak adanya struktur yang menghubungkan daratan kota Konigsberg atau Kaliningrad, Rusia dan sebuah pulau kecil yang dihubungkan oleh tujuh buah jembatan. Graf yang memiliki komponen dasar berupa simpul dan sisi, yang kemudian dapat membentuk graf terbuka dan graf
tertutup dengan sejumlah lintasan dan sirkuit, telah mengahpus tanda tanya besar dalam penyelesaian Teka-Teki
Jembatan Konigsberg dan berbagai masalah yang serupa dengannya. “Dalam era digital, teori Graf bermanfaat untuk menciptakan link yang ada di internet, algoritme, transportasi, kecerdasan buatan, dan GPS.
Dalam pembuatan website seperti toko online, CRUD (Create, Read, Update dan Delete) merupakan dasar dalam membuat website dinamis. Dimana pengguna ataupun admin dapat menambah, menampilkan, mengubah dan menghapus data yang ada di dalam website tersebut.
Hashing merupakan teknik yang digunakan untuk menyusun dan mengakses elemen data dalam List dengan waktu yang relatif konstan melalui manipulasi key untuk mengidentifikasi lokasi dalam List.
Hash function merupakan fungsi yang digunakan untuk memanipulasi key dari elemen data dalam List untuk mengidentifikasi lokasi aslinya di list. Fungsi ini akan memetakan list data yang ukurannya berubah-ubah ke ukuran tetap. Nilai kembalian dari fungsi hash disebut dengan Hash Values.
Hash table adalah sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.
Keunggulan dari struktur hash table ini adalah waktu aksesnya yang cukup cepat, jika record yang dicari langsung berada pada angka hash lokasi penyimpanannya. Akan tetapi pada kenyataannya sering sekali ditemukan hash table yang recordrecordnya mempunyai angka hash yang sama (bertabrakan).
Karena pemetaan hash function yang digunakan bukanlah pemetaan satu-satu, (antara dua record yang tidak sama dapat dibangkitkan angka hash yang sama) maka dapat terjadi bentrokan (collision) dalam penempatan suatu data record. Untuk mengatasi hal ini, maka perlu diterapkan kebijakan resolusi bentrokan (collision resolution policy) untuk menentukan lokasi record dalam tabel. Umumnya kebijakan resolusi bentrokan adalah dengan mencari lokasi tabel yang masih kosong pada lokasi setelah lokasi yang berbentrokan.
Hash table menggunakan memori penyimpanan utama berbentuk array dengan tambahan algoritma untuk mempercepat pemrosesan data. Pada intinya hash table merupakan penyimpanan data menggunakan key value yang didapat dari nilai data itu sendiri. Dengan key value tersebut didapat hash value. Jadi hash function merupakan suatu fungsi sederhana untuk mendapatkan hash value dari key value suatu data. Yang perlu diperhatikan untuk membuat hash function adalah:
– ukuran array/table size(m),
– key value/nilai yang didapat dari data(k),
– hash value/hash index/indeks yang dituju(h).
Berikut contoh penggunaan hash table dengan hash function sederhana yaitu memodulus key value dengan ukuran array : h = k (mod m)
Misal kita memiliki array dengan ukuran 13, maka hash function : h = k (mod 13).
Dengan hash function tersebut didapat :
Perhatikan range dari h untuk sembarang nilai k.
Maka data 7 akan disimpan pada index 7, data 13 akan disimpan pada index 0, dst..
Untuk mencari kembali suatu data, maka kita hanya perlu menggunakan hash function yang sama sehingga mendapatkan hash index yang sama pula.
Misal : mencari data 25 → h = 25 (mod 13) = 12
Namun pada penerapannya, seperti contoh di atas terdapat tabrakan (collision) pada k = 13 dan k = 39. Collision berarti ada lebih dari satu data yang memiliki hash index yang sama, padahal seperti yang kita ketahui, satu alamat / satu index array hanya dapat menyimpan satu data saja.
Untuk meminimalkan collision gunakan hash function yang dapat mencapai seluruh indeks/alamat. Dalam contoh di atas gunakan m untuk me-modulo k. Perhatikan bila kita menggunakan angka m untuk me-modulo k maka pada indeks yang lebih besar dari dan sama dengan m di hash table tidak akan pernah terisi (memori yang terpakai semakin kecil), kemungkinan terjadi collision juga semakin besar.
Karena memori yang terbatas dan untuk masukan data yang belum diketahui tentu collision tidak dapat dihindari.
Graph merupakan representasi data yang tidak kontigu/ non linear, dengan adanya penanda keterkaitan/hubungan antara dua data. Sebuah data dilambangkan/disebut sebagai sebuah node atau vertex, dan keterkaitan antar data disebut sebagai edge.
Pada gambar di atas vertices V = {0,1,2,3,4} dan satu set edges E = {01, 12, 23, 34, 04, 14, 13}.
Graphs digunakan untuk menggambarkan dan memecahkan problem pada dunia nyata. Sebagai contoh Graphs graph digunakan untuk menggambarkan jaringan/ networks. Bentuk jaringan antara lain rute antar kota, jaringan telepon dalam suatu daerah, jaringan listrik, jaringan komputer. Graphs juga digunakan untuk memodelkan hubungan data dalam social networks seperti linkedIn, Facebook. Sebagai contoh di Facebook, setiap orang menggambarkan vertex/ node. Setiap node memuat informasi mengenai person id, name, gender, locale etc.
Binary tree adalah struktur data non linier bentuk khusus dari pohon umum (general tree) yang diilhami dari pohon yang kita lihat sehari-hari. Namun, karena ini merupakan pohon imajiner maka bentuknya bisa dibolak-balik sesuai yang kita inginkan.
Pohon umum di gambar 1 memiliki 7 simpul (7 nodes), yaitu A, B, C, D, E, F, dan G. Setiap simpul bisa memiliki hubungan dengan 0, 1, 2, 3, atau berapapun simpul lain. Yang dikatakan hubungan adalah garis yang menghubungkan simpul tersebut dengan simpul-simpul di bawahnya. Karena ketidakpastian banyaknya simpul yang dapat berhubungan dengan simpul lain, maka akan menimbulkan kesulitan jika akan dilakukan komputerisasinya. Kalau masing-masing dipatok (default) dengan penyediaan sebanyak 5 hubungan dari masing-masing simpul, maka, jika akhirnya hanya digunakan 1 sampai 3 saja, berakibat terjadinya pemborosan penggunaan memori. Sebaliknya, jika hanya disediakan 3 hubungan dari setiap simpul tetapi pada akhirnya banyak yang memiliki hubungan dengan lebih dari 3 simpul lain, maka akan terjadi loosing data.
