Algoritma dan Struktur Data
Apa Itu Algoritma Pemrograman?
Algoritma pemrograman merupakan sebuah struktur yang berguna untuk memecahkan masalah secara sistematis.
Artinya algoritma sama dengan flowchart?
Perhatikan contoh studi kasus dibawah ini
Algoritma
● Baca nama dan nilai siswa
● Jika nilai >= 80 maka
● Keterangan lulus
● Tetapi jika
● Keterangan tidak lulus
● Tulis nama dan keterangan
Flowchart
Apa Saja Struktur Data?
Array termasuk dalam struktur data linier karena, elemen datanya disusun dalam satu dimensi.
Jika kita ingin mengakses elemen dalam array kia cukup menghitung posisi pada setiap elemen
Sedikit berbeda dengan array karena, elemen linked list tidak ditempatkan dalam alamat memori yang berdekatan, tetapi ditautkan dengan pointer
● Single Linked List, yaitu hanya melewati satu arah
● Doubly, Linked List, yaitu melewati dua arah
● Circular Linked List, yaitu sama seperti single namun circular memiliki head dan tail
● Circular Doubly Linked List, yaitu gabungan dari circular dan doubly
Prinsip kerja stack adalah Last In First Out (LIFO), sehingga elemen terakhir yang disisipkan akan keluar lebih dulu.
Dari ilustrasi tumpukan piring tsb dapat kita lihat, jika tumpukan terakhir akan diambil lebih dulu.
Berdasarkan memorinya stack ada 2:
● Register stack, hanya menampung data dengan jumlah kecil
● Memory stack, lebih fleksibel dan mampu menampung jumlah yang lebih besar
Sedangkan queue kebalikan dari stack dengan prinsip First In First Out (FIFO)
Ada 4 jenis queue:
● Simple Queue, yaitu menyisipkan item di belakang atau tail
● Circular Queue, yaitu menghubungkan item pertama dan terakhir
● Priority Queue, yaitu menentukan prioritas pada simpul dimana prioritas terbesar akan pertama kali dihapus
● Double-Ended Queue (Dequeue), operasi penyisipan dan penghapusan dapat terjadi di ujung depan dan belakang dari queue.
Tree termasuk dalam struktur data non-linier karena tidak disimpan secara berurutan
Macam-macam tree:
● General Tree, ia tidak memiliki batasan jumlah node pada hirarki tree
● Binary Tree, binary memiliki aturan jika simpul hanya boleh memiliki 2 anak
● Balanced Tree, disebut balance apabila subtree kanan dan kiri sama, jika ada selisih maksimal 1
● Binary Search Tree, cocok digunakan untuk berbagai algoritma pencarian dan pengurutan. Contohnya seperti AVL tree dan Red-black tree
Keterangan: Ada 4 buah verteks (simpul pada graph) dan 4 pasang sisi yang menghubungkan verteks (edge)
● Verteks (0, 1, 2, 3)
● Edge [(0,1) (0,2) (0,3) (1,2)]
● Graph (V, E)
Macam-macam graph:
a. Undirected Graph, simpulnya akan terhubung dengan edge yang sifatnya 2 arah
Contoh: jika simpul 1 dan 2 terhubung makan kita bisa berjelajah dari simpul 1 ke 2 dan sebaliknya.
b. Directed Graph, merupakan kebalikan dari Undirected
c. Weighted Graph, dimana setiap cabangnya memiliki bobot berupa numerik
d. Unweighted Graph, tidak memiliki bobot/kebalikan dari weighted
Fungsi utama data adalah untuk mempercepat akses data, terutama dengan adanya peningkatan jumlah data yang diproses oleh jaringan data global dan lokal. Hash table merupakan solusi yang efektif untuk mempercepat proses akses data dan menjaga keamanan dalam pertukaran data.
Hash table digunakan secara luas dalam berbagai bidang karena efisiensi waktu operasinya, termasuk dalam pengarsipan dan pencarian data. Sebagai contoh, dalam bidang jaringan komputer, hybrid open hash table dikembangkan dan digunakan untuk memproses jaringan komputer.
Bagaimana cara membuat hash table?
Untuk membuat hash table, langkah awalnya adalah memblok sepotong memori, yang dilakukan dengan cara yang sama seperti saat membuat array. Kemudian, untuk membuat indeks yang sesuai dengan potongan memori, perlu dibuat indeks yang didasarkan pada kunci dengan menggunakan fungsi hash.
Saat menempatkan data baru pada hash table, ada dua pemeriksaan yang perlu dilakukan: nilai hash dari kunci dan bagaimana nilai tersebut dibandingkan dengan objek lain. Dalam implementasinya dengan Python, pemeriksaan ini diperlukan karena kunci akan di-hash dan di-mask saat data dimasukkan, sehingga dapat diubah menjadi larik atau indeks yang efisien.
Apa saja teknik dari hash table?
a. Hashing
Hashing adalah proses mengubah sebuah kunci atau string karakter menjadi nilai lain. Salah satu penggunaan paling umum dari hashing adalah pada hash table. Hash table menyimpan pasangan kunci dan nilai dalam daftar yang dapat diakses melalui indeksnya. Karena pasangan kunci dan nilai dapat sangat banyak, fungsi hash akan memetakan kunci ke ukuran tabel dan mengubah nilainya menjadi indeks untuk elemen tertentu.
b. Linear Probing
Linear probing adalah sebuah skema dalam pemrograman komputer yang digunakan untuk menangani collision pada hash table. Dalam skema ini, setiap sel dari hash table hanya dapat menyimpan satu pasangan kunci-nilai. Jika fungsi hash memetakan kunci baru ke sel hash table yang sudah ditempati oleh kunci lain, maka linear probing akan mencari lokasi bebas terdekat pada tabel dan menyisipkan kunci baru tersebut.
Pencarian kunci dilakukan dengan cara yang sama, yaitu dengan mencari tabel secara berurutan, mulai dari posisi yang dihasilkan oleh fungsi hash, hingga menemukan sel dengan kunci yang cocok atau sel kosong. Hash table merupakan struktur data yang umum digunakan dan non-trivial. Meskipun linear probing dapat memberikan kinerja yang baik karena lokasi referensi yang baik, namun skema ini lebih sensitif terhadap kualitas fungsi hash daripada beberapa skema resolusi collision lainnya.
Merupakan struktur data dengan bentuk complete binary tree yang memenuhi heap property
Sedangkan complete binary, yaitu ketika seluruh level terisi penuh kecuali yang terakhir.
Contohnya:
Kemudian heap properti, memiliki 2 jenis heap sebagai berikut:
a. Max Heap, dimana kunci atau nilai yang ada di simpul mana pun harus lebih besar dari kunci/nilai yang ada di kedua simpul anaknya. Kunci terbesar ada di simpul akar (root node).
b. Min Heap, dimana kunci yang ada di simpul mana pun harus lebih kecil dari kunci yang ada di kedua anaknya. Kunci terkecil ada di simpul akar.
Tugas
Buatlah algoritma dan flowchart dari studi kasus berupa penyewaan motor
Referensi