WorksheetsAlgoritma dan Pemrograman
Total questions: 14
Worksheet time: 7mins
Prinsip utama dari algoritma Greedy dalam pemecahan masalah adalah:
Menguji semua kemungkinan submasalah.
Membagi masalah menjadi submasalah yang tidak tumpang tindih.
Menggunakan memorisasi untuk menyimpan solusi submasalah.
Mencari solusi yang optimal secara keseluruhan dengan meninjau ke belakang.
Membuat pilihan optimal secara lokal pada setiap langkah dengan harapan mendapatkan solusi global yang optimal.
Apa yang WAJIB dimiliki oleh fungsi rekursif agar tidak terjadi infinite loop (pengulangan tak terbatas)?
Struktur data Stack.
Penggunaan variabel global.
Panggilan fungsi yang sama di badan fungsi.
Kondisi yang membuat waktu eksekusi menjadi O(n).
Kondisi basis (base case) yang menghentikan panggilan rekursif.
Algoritma Pemrograman Dinamis (Dynamic Programming) paling cocok digunakan untuk masalah yang menunjukkan dua properti utama, yaitu:
Kecepatan dan kemudahan implementasi.
Pilihan Greedy dan rekursi sederhana.
Masalah yang tidak memiliki struktur optimal.
Pemanfaatan Stack dan Queue.
Substruktur optimal dan submasalah tumpang tindih.
Kelemahan utama algoritma Greedy adalah:
Selalu membutuhkan waktu eksekusi yang lama (O(n^2)).
Tidak dapat diterapkan pada masalah optimasi.
Memerlukan memori yang sangat besar untuk memorisasi.
Sangat sulit diimplementasikan menggunakan bahasa pemrograman.
Tidak selalu menjamin solusi global yang optimal.
Teknik yang digunakan oleh Pemrograman Dinamis untuk menghindari perhitungan berulang dari submasalah yang sama adalah:
Divide and Conquer.
Backtracking.
Branch and Bound.
Pencarian Linear.
Memoization atau Tabulation.
Salah satu contoh masalah klasik yang secara alami dapat dipecahkan menggunakan rekursi adalah:
Travelling Salesman Problem.
Sorting (misalnya Bubble Sort).
Mencari elemen terkecil dalam Array.
Hashing.
Menghitung faktorial (n!) atau barisan Fibonacci.
Apa perbedaan mendasar antara algoritma Greedy dan Dynamic Programming dalam memecahkan masalah optimasi?
Greedy selalu lebih cepat daripada DP.
DP menggunakan rekursi, sedangkan Greedy tidak.
Greedy hanya berlaku untuk masalah sederhana.
DP selalu menghasilkan solusi yang tidak optimal.
Greedy membuat pilihan lokal tanpa melihat solusi submasalah sebelumnya, sementara DP menggabungkan solusi dari submasalah tumpang tindih.
Dalam struktur data, proses panggilan fungsi rekursif diimplementasikan dan dikelola menggunakan:
Queue (Antrian).
Heap.
Tree (Pohon).
Hash Table.
Stack (Tumpukan).
Masalah berikut ini yang merupakan contoh aplikasi umum dari Pemrograman Dinamis adalah:
Penemuan rute terpendek di graph tanpa bobot.
Selection Sort.
Depth-First Search (DFS).
Pencarian Biner.
The Knapsack Problem (0/1 Knapsack).
Algoritma Greedy seringkali melibatkan pengurutan data untuk:
Mempermudah perhitungan alokasi memori.
Mempercepat proses I/O.
Mengurangi jumlah panggilan rekursif.
Menghindari masalah overflow.
Memastikan pilihan optimal lokal dapat dibuat dengan cepat.
Anda memiliki daftar kegiatan dengan waktu mulai dan waktu selesai. Anda ingin memilih kegiatan sebanyak mungkin tanpa ada yang saling tumpang tindih. Misalnya, Aktivitas A (mulai jam 9, selesai jam 10) dan Aktivitas B (mulai jam 9:30, selesai jam 11) tumpang tindih. Strategi Greedy yang paling efektif untuk masalah pemilihan aktivitas (Activity Selection Problem) ini adalah:
Memilih aktivitas dengan waktu mulai paling awal.
Memilih aktivitas dengan durasi terpendek.
Memilih aktivitas dengan waktu selesai paling lambat.
Memilih aktivitas dengan waktu selesai paling awal terlebih dahulu.
Memilih aktivitas yang paling sering muncul.
Mengapa sebuah fungsi rekursif wajib memiliki Kondisi Basis (Base Case)?
Untuk menjamin penggunaan memori Heap yang efisien.
Untuk mempercepat waktu komputasi menjadi O(n).
Untuk memastikan fungsi melakukan panggilan dirinya sendiri.
Untuk mencegah Stack Overflow (pengulangan tak terbatas).
Agar dapat menggunakan teknik Memoization.
Dalam konteks keamanan komputer, Algoritma Brute Force umumnya merujuk pada teknik:
Memecahkan kata sandi dengan menebak setiap kemungkinan kombinasi karakter.
Mengenkripsi data dengan kunci acak.
Menggunakan sertifikat digital untuk otentikasi.
Melakukan Hashing untuk mempercepat pencarian data.
Membagi jaringan menjadi subnet yang lebih kecil.
Ketika seorang programmer menggunakan teknik Memoization dalam Pemrograman Dinamis (DP), data apa yang disimpan (dicatat) untuk menghindari perhitungan berulang?
Seluruh urutan pemanggilan fungsi rekursif (Call Stack).
Waktu eksekusi setiap submasalah.
Solusi dari submasalah yang telah diselesaikan.
Jumlah total langkah yang diambil.
Pilihan Greedy yang dibuat pada langkah sebelumnya.
