Tugas 4 Algoritma

ALGORITMA DFS (Depth-First Search)

Pengertian Algoritma DFS

Bayangkan Anda adalah seorang manajer proyek yang memiliki 5 pekerjaan (A, B, C, D, dan E) yang harus diselesaikan oleh satu mesin. Anda tahu setiap pekerjaan memiliki durasi dan tingkat kepentingan (bobot) yang berbeda. Tugas Anda adalah menemukan satu urutan kerja yang paling efisien, yaitu yang menghasilkan "total biaya" paling minimum.

Masalahnya, ada sangat banyak kemungkinan urutan (permutasi). Bagaimana Anda bisa yakin menemukan yang terbaik? Di sinilah Algoritma DFS (Depth-First Search) berperan sebagai strategi Anda.

Alih-alih bingung memikirkan semua kemungkinan sekaligus, Anda memutuskan untuk mencoba satu urutan penuh dari awal sampai akhir. Misalnya, Anda mencoba urutan A → B → C → D → E. Anda selesaikan simulasi untuk urutan ini sampai tuntas dan menghitung total biayanya. Inilah yang disebut pendekatan "Depth-First" atau "mendahulukan kedalaman"; Anda menjelajahi satu cabang kemungkinan secara mendalam hingga ke ujungnya.

Setelah mendapatkan biaya untuk urutan pertama, Anda tidak berhenti. Anda mundur satu langkah (backtracking) ke pekerjaan terakhir (E), lalu menukarnya dengan pilihan lain yang mungkin, misalnya A → B → C → E → D. Anda hitung lagi biayanya dan membandingkannya dengan biaya terbaik yang sudah Anda catat.

Proses ini terus berlanjut. Anda secara sistematis akan "mundur" dan mencoba cabang-cabang baru dari titik persimpangan terakhir, lalu menelusurinya lagi sampai ke dalam. Seperti yang dilakukan oleh fungsi cariUrutan dalam kode, algoritma ini secara rekursif akan mencoba setiap kemungkinan jalur sampai semua kombinasi urutan telah dieksplorasi.

Pada akhirnya, setelah semua cabang "pohon kemungkinan" telah dijelajahi, Anda akan memiliki satu urutan yang tercatat sebagai urutanTerbaik dengan biayaMinimum. Dengan cara ini, DFS menjamin bahwa Anda telah memeriksa setiap skenario dan menemukan solusi yang paling optimal.

Karakteristik Algoritma DFS

• Memprioritaskan Kedalaman

  Karakteristik paling mendasar. DFS akan selalu mencoba menjelajahi sejauh dan sedalam mungkin ke satu arah sebelum akhirnya mundur untuk mencoba arah lain.

• Menggunakan Struktur Data Stack (Tumpukan)

  Secara implementasi, DFS menggunakan mekanisme LIFO (Last-In, First-Out) yang mirip dengan tumpukan, baik secara eksplisit maupun melalui rekursi.

• Membutuhkan Memori yang Lebih Sedikit

  Dibandingkan dengan BFS, DFS umumnya lebih hemat memori karena hanya perlu menyimpan satu jalur dari titik awal hingga titik saat ini.

• Bisa Menemukan Solusi yang Sangat Jauh dengan Cepat

  Jika solusi berada di ujung sebuah cabang yang dalam, DFS bisa menemukannya dengan sangat cepat karena sifatnya yang langsung menelusuri ke dalam.

• Tidak Menjamin Menemukan Jalur Terpendek

  Ini adalah kelemahan utamanya. Karena DFS menjelajah secara "mendalam buta", jalur pertama yang ditemukannya belum tentu merupakan jalur terpendek.

Contoh Kasus: Penjadwalan Pekerjaan

Deskripsi Masalah

Cerita: Ada 5 pekerjaan yang harus dikerjakan 1 mesin secara berurutan. Setiap pekerjaan punya waktu pengerjaan dan bobot. Kita ingin mengatur urutan kerja agar "total waktu selesai × bobot" sekecil mungkin.

Data Pekerjaan (Durasi, Bobot):

• A: (3 jam, bobot 4)
• B: (2 jam, bobot 2)
• C: (5 jam, bobot 10)
• D: (1 jam, bobot 1)
• E: (4 jam, bobot 3)

Tujuan: Cari urutan pekerjaan supaya total "waktu selesai × bobot" minimum.

Pseudocode

1. Mulai
2. Cari semua kemungkinan urutan pekerjaan.
3. Untuk setiap urutan, hitung total biayanya.
4. Bandingkan semua total biaya dan temukan yang paling kecil.
5. Tampilkan urutan dengan biaya terkecil.
6. Selesai

Implementasi Kode Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class JadwalKerjaOOP {
    Map<String, int[]> jobs = new HashMap<>();
    long biayaMinimum = Long.MAX_VALUE;
    List<String> urutanTerbaik = new ArrayList<>();

    public JadwalKerjaOOP() {
        jobs.put("A", new int[]{3, 4});
        jobs.put("B", new int[]{2, 2});
        jobs.put("C", new int[]{5, 10});
        jobs.put("D", new int[]{1, 1});
        jobs.put("E", new int[]{4, 3});
    }

    void cariUrutan(List<String> urutanSekarang, List<String> sisaPekerjaan) {
        if (sisaPekerjaan.isEmpty()) {
            long biayaSekarang = hitungBiaya(urutanSekarang);
            if (biayaSekarang < this.biayaMinimum) {
                this.biayaMinimum = biayaSekarang;
                this.urutanTerbaik = new ArrayList<>(urutanSekarang);
            }
            return;
        }
        for (String pekerjaan : new ArrayList<>(sisaPekerjaan)) {
            urutanSekarang.add(pekerjaan);
            sisaPekerjaan.remove(pekerjaan);
            
            cariUrutan(urutanSekarang, sisaPekerjaan);

            sisaPekerjaan.add(pekerjaan);
            urutanSekarang.remove(urutanSekarang.size() - 1);
        }
    }

    long hitungBiaya(List<String> urutan) {
        long totalBiaya = 0;
        long waktuSelesai = 0;
        for (String namaPekerjaan : urutan) {
            int durasi = this.jobs.get(namaPekerjaan)[0];
            int bobot = this.jobs.get(namaPekerjaan)[1];
            waktuSelesai += durasi;
            totalBiaya += waktuSelesai * bobot;
        }
        return totalBiaya;
    }

    public static void main(String[] args) {
        JadwalKerjaOOP program = new JadwalKerjaOOP();
        List<String> namaPekerjaan = new ArrayList<>(program.jobs.keySet());

        System.out.println("--- Mencari Jadwal Kerja Terbaik (Versi OOP) ---");
        program.cariUrutan(new ArrayList<>(), namaPekerjaan);

        System.out.println("\n--- Hasil Akhir ---");
        System.out.println("Urutan terbaik: " + program.urutanTerbaik);
        System.out.println("Biaya minimum: " + program.biayaMinimum);
    }
}

Kesimpulan

Kode tersebut menggunakan algoritma DFS untuk menyelesaikan masalah penjadwalan kerja. Algoritma ini bekerja dengan cara mencoba setiap kemungkinan urutan pekerjaan satu per satu secara mendalam. Untuk setiap urutan yang lengkap, kode akan menghitung total biayanya, lalu membandingkannya dengan biaya terbaik yang pernah ditemukan. Proses ini menjamin penemuan urutan kerja yang paling optimal dengan total biaya minimum setelah semua kemungkinan dieksplorasi.

Tugas 3 ALgoritma

ALGORITMA GREEDY

Pengertian Algoritma Greedy

Algoritma Greedy adalah metode pemecahan masalah yang membuat pilihan terbaik (paling optimal) yang tersedia pada setiap langkahnya dengan harapan akan menemukan solusi terbaik secara keseluruhan (optimal global). Dengan kata lain, algoritma ini "rakus" atau "serakah" karena tidak pernah mempertimbangkan konsekuensi jangka panjang dari pilihan yang dibuatnya. Setelah sebuah pilihan diambil, pilihan itu tidak akan pernah diubah lagi.

Karakteristik Utama

• Selalu Lokal Optimal: Hanya fokus pada pilihan terbaik saat ini.
• Tidak Pernah Mundur: Keputusan yang sudah diambil bersifat final dan tidak pernah ditinjau ulang (tidak ada backtracking).
• Cepat dan Sederhana: Biasanya lebih mudah diimplementasikan dan lebih cepat dieksekusi daripada algoritma lain seperti Dynamic Programming.

---

Contoh Kasus: Penjadwalan Pekerjaan

4) Kasus: Menyusun jadwal kerja (Scheduling)

Cerita: Ada 5 pekerjaan yang harus dikerjakan 1 mesin secara berurutan (tidak bisa paralel). Setiap pekerjaan punya waktu pengerjaan dan bobot penting. Kita ingin mengatur urutan kerja agar “total waktu selesai × bobot” sekecil mungkin.

Data pekerjaan (durasi, bobot):

• A: (3 jam, bobot 4)
• B: (2 jam, bobot 2)
• C: (5 jam, bobot 10)
• D: (1 jam, bobot 1)
• E: (4 jam, bobot 3)

Tujuan: Cari urutan pekerjaan supaya total “waktu selesai × bobot” minimum.

Pseudocode

1. Siapkan data pekerjaan (nama, durasi, bobot).
2. Hitung rasio (durasi / bobot) untuk setiap pekerjaan.
3. Urutkan semua pekerjaan berdasarkan rasio terkecil.
4. Hitung total biaya dengan menjumlahkan biaya setiap pekerjaan sesuai urutan.
5. Tampilkan urutan pekerjaan dan total biaya minimum.

Implementasi Kode Java

public class Soal4 {
    public static void main(String[] args) {
        // Siapkan data dan hitung rasionya
        String[] nama = {"A", "B", "C", "D", "E"};
        int[] durasi = {3, 2, 5, 1, 4};
        int[] bobot = {4, 2, 10, 1, 3};
        double[] rasio = new double[5];

        for (int i = 0; i < 5; i++) {
            rasio[i] = (double) durasi[i] / bobot[i];
        }

        // Urutkan semua data berdasarkan rasio terkecil (Bubble Sort)
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4 - i; j++) {
                if (rasio[j] > rasio[j + 1]) {
                    // Tukar rasio
                    double tempRasio = rasio[j];
                    rasio[j] = rasio[j + 1];
                    rasio[j + 1] = tempRasio;

                    // Tukar nama
                    String tempNama = nama[j];
                    nama[j] = nama[j + 1];
                    nama[j + 1] = tempNama;

                    // Tukar durasi
                    int tempDurasi = durasi[j];
                    durasi[j] = durasi[j + 1];
                    durasi[j + 1] = tempDurasi;

                    // Tukar bobot
                    int tempBobot = bobot[j];
                    bobot[j] = bobot[j + 1];
                    bobot[j + 1] = tempBobot;
                }
            }
        }

        // Hitung total biaya dan tampilkan hasilnya
        long totalBiaya = 0;
        long waktuSelesai = 0;

        System.out.print("Urutan pekerjaan terbaik: ");
        for (int i = 0; i < 5; i++) {
            waktuSelesai += durasi[i];
            totalBiaya += waktuSelesai * bobot[i];
            System.out.print(nama[i] + (i == 4 ? "" : ", "));
        }

        System.out.println("\nTotal Biaya Minimum: " + totalBiaya);
    }
}

OUTPUTNYA

Urutan pekerjaan terbaik: C, A, B, D, E 
Total Biaya Minimum: 158

---

Kesimpulan Cara Kerja Algoritma

Dari kode di atas, dapat disimpulkan bahwa cara kerja algoritma Greedy untuk masalah penjadwalan ini adalah sebagai berikut:

1. Hitung Prioritas Setiap Pekerjaan
   Langkah pertama adalah menghitung "tingkat efisiensi" atau rasio dari setiap pekerjaan dengan rumus `durasi / bobot`.
   Pekerjaan A: 3 / 4 = 0.75
   Pekerjaan B: 2 / 2 = 1.0
   Pekerjaan C: 5 / 10 = 0.5
   Pekerjaan D: 1 / 1 = 1.0
   Pekerjaan E: 4 / 3 = 1.33
2. Pilih Pekerjaan Paling Efisien (Rasio Terkecil)
   Greedy akan memilih pekerjaan dengan rasio terkecil sebagai yang pertama dikerjakan, yaitu **Pekerjaan C (rasio 0.5)**.
3. Pilih Pekerjaan Berikutnya dari yang Tersisa
   Dari sisa pekerjaan, Greedy kembali memilih yang rasionya terkecil, yaitu **Pekerjaan A (rasio 0.75)**.
4. Ulangi Hingga Semua Pekerjaan Terjadwal
   Proses ini diulangi terus. Jika ada rasio yang sama (seperti B dan D), urutannya tidak terlalu berpengaruh pada hasil akhir. Pilihan berikutnya adalah B, lalu D, dan terakhir E.
5. Susun Urutan Final
   Setelah semua pilihan dibuat, didapatkan urutan pekerjaan yang optimal: Urutan Final: C → A → B → D → E
6. Hitung Total Biaya Minimum
   Dengan urutan tersebut, program menghitung total biaya penalti, yang merupakan solusi paling minimum yang bisa didapatkan.

Tugas 2 IMK

Analisis dan Iterasi Desain Kalkulator

Desain Awal Kalkulator

Prototipe awal dikembangkan dengan fungsionalitas dasar untuk memenuhi kebutuhan kalkulasi standar. Desainnya dibuat minimalis dan fungsional.

CODE HTML

<div class="calculator">
    <div class="input" id="input"></div>
    <div class="buttons">
        <div class="operators">
            <div>+</div>
            <div>-</div>
            <div>×</div>
            <div>÷</div>
        </div>
        <div class="leftPanel">
            <div class="numbers">
                <div>7</div>
                <div>8</div>
                <div>9</div>
            </div>
            <div class="numbers">
                <div>4</div>
                <div>5</div>
                <div>6</div>
            </div>
            <div class="numbers">
                <div>1</div>
                <div>2</div>
                <div>3</div>
            </div>
            <div class="numbers">
                <div>0</div>
                <div>.</div>
                <div id="clear">C</div>
            </div>
        </div>
        <div class="equal" id="result">=</div>
    </div>
</div>

CODE CSS

body {
    width: 500px;
    margin: 4% auto;
    font-family: 'Source Sans Pro', sans-serif;
    letter-spacing: 5px;
    font-size: 1.8rem;
    -moz-user-select: none;
    -webkit-user-select: none;
    -ms-user-select: none;
}

.calculator {
    padding: 20px;
    -webkit-box-shadow: 0px 1px 4px 0px rgba(0, 0, 0, 0.2);
    box-shadow: 0px 1px 4px 0px rgba(0, 0, 0, 0.2);
    border-radius: 1px;
}

/* ... dan seterusnya ... */

CODE JS

"use strict";

var input = document.getElementById('input'), // input/output button
    number = document.querySelectorAll('.numbers div'), // number buttons
    operator = document.querySelectorAll('.operators div'), // operator buttons
    result = document.getElementById('result'), // equal button
    clear = document.getElementById('clear'), // clear button
    resultDisplayed = false; // flag to keep an eye on what output is displayed

// adding click handlers to number buttons
for (var i = 0; i < number.length; i++) {
    number[i].addEventListener("click", function(e) {
        // ... dan seterusnya ...
    });
}

---

Analisis Usability

Kelebihan

1. Mudah Dipelajari: Tata letaknya sama persis seperti kalkulator pada umumnya, jadi siapa saja bisa langsung memakainya tanpa perlu belajar lagi.
2. Konsisten: Tombol angka 0-9 dan operatornya (+, -, ×, ÷) punya desain dan ukuran yang seragam, mirip seperti yang ada di kalkulator fisik.
3. Umpan Balik: Cukup jelas. Setiap tombol yang ditekan akan langsung muncul angkanya di layar, jadi kita tahu apa yang sedang diketik.
4. Estetika: Desainnya bersih dan minimalis. Tidak banyak hiasan yang mengganggu, sehingga nyaman dilihat dan fokus pada fungsi.

Kekurangan dari Kalkulator Ini

1. Tidak ada tombol backspace untuk memperbaiki kesalahan ketik.
2. Fungsi sangat terbatas (hanya tambah, kurang, kali, bagi).
3. Pesan kesalahan tidak jelas (misalnya saat dibagi dengan nol).
4. Tidak ada riwayat untuk melihat perhitungan sebelumnya.

---

Iterasi Desain

Setelah menganalisis permasalahan yang ada, maka saya membuat desain baru ini agar permasalahan di atas dapat diatasi. Perbaikan mencakup penambahan tombol backspace, fungsi akar (√) dan plus-minus (±), serta peningkatan estetika secara keseluruhan.

CODE HTML

<div class="calculator">
    <div class="input" id="input"></div>
    <div class="buttons">
        <div class="row">
            <div class="button function" id="clear">C</div>
            <div class="button function" id="plus-minus">±</div>
            <div class="button function" id="sqrt">√</div>
            <div class="button operator" id="backspace">⌫</div>
        </div>
        <div class="row">
            <div class="button number">7</div>
            <div class="button number">8</div>
            <div class="button number">9</div>
            <div class="button operator">÷</div>
        </div>
        <!-- ... dan seterusnya ... -->
    </div>
</div>

CODE CSS

@import url('https://fonts.googleapis.com/css2?family=Roboto:wght@300&display=swap');

body {
    display: flex;
    justify-content: center;
    align-items: center;
    height: 100vh;
    margin: 0;
    font-family: 'Roboto', sans-serif;
    background: linear-gradient(to bottom right, #fdfbfb, #ebedee);
}

.calculator {
    width: 320px;
    padding: 20px;
    border-radius: 20px;
    /* ... dan seterusnya ... */
}

CODE JS

"use strict";

const input = document.getElementById('input');
const numberButtons = document.querySelectorAll('.number');
const operatorButtons = document.querySelectorAll('.operator');
const resultButton = document.getElementById('result');
// ... dan seterusnya ...

numberButtons.forEach(button => {
    button.addEventListener("click", (e) => {
        // ... dan seterusnya ...
    });
});

---

Hasil Akhir (Kalkulator Interaktif)

Setiap proyek pengembangan sering kali dimulai dari sebuah prototipe dasar. Dalam kasus ini, titik awalnya adalah kalkulator digital sederhana. Langkah terpenting selanjutnya bukanlah menganggapnya selesai, melainkan melakukan analisis dan iterasi. Proses ini melibatkan pengujian untuk menemukan kelemahan pada versi pertama. Berdasarkan temuan tersebut, kami melakukan siklus perbaikan (iterasi) yang melahirkan versi kedua yang jauh lebih matang. Hasilnya adalah sebuah kalkulator yang tidak hanya tampil dengan desain modern, tetapi juga dilengkapi fitur esensial dan logika cerdas yang mampu memberikan pesan error spesifik. Transformasi ini adalah contoh nyata bagaimana analisis kritis terhadap versi awal menjadi fondasi untuk menciptakan produk akhir yang lebih baik.

C

±

√

⌫

7

8

9

÷

4

5

6

×

1

2

3

-

0

.

+

=

Tugas 2 Algoritma

Apa itu Algoritma Brute Force?

Algoritma brute force adalah cara penyelesaian masalah dengan mencoba semua kemungkinan solusi yang ada, kemudian memilih yang terbaik. Sederhananya, brute force itu seperti “cek satu per satu” tanpa trik khusus.

Kelebihan: Hasilnya pasti optimal karena semua kemungkinan dihitung.
Kekurangan: Sangat lambat jika jumlah data besar, karena banyaknya kombinasi akan meledak sangat cepat.

Penjelasan Soal: Penjadwalan Kerja

Dalam soal ini kita punya lima pekerjaan, masing-masing dengan durasi pengerjaan dan bobot kepentingan. Semua pekerjaan dikerjakan secara berurutan pada satu mesin, jadi tidak bisa paralel. Tujuannya adalah mencari urutan pekerjaan supaya jumlah total (waktu selesai × bobot) menjadi sekecil mungkin.

Berikut adalah data pekerjaannya:

• Pekerjaan A: Durasi 3, Bobot 4
• Pekerjaan B: Durasi 2, Bobot 2
• Pekerjaan C: Durasi 5, Bobot 10
• Pekerjaan D: Durasi 1, Bobot 1
• Pekerjaan E: Durasi 4, Bobot 3

Pseudocode Algoritma

MULAI
  // 1. Siapkan data
  data nama = {"A", "B", "C", "D", "E"}
  data durasi = {3, 2, 5, 1, 4}
  data bobot = {4, 2, 10, 1, 3}

  // 2. Siapkan variabel untuk menyimpan hasil terbaik
  biayaTerbaik = Tak Terhingga
  urutanTerbaik = ""

  // 3. Coba semua 120 kemungkinan urutan dengan 5 loop
  UNTUK setiap pekerjaan p1 DARI 0 SAMPAI 4:
    UNTUK setiap pekerjaan p2 DARI 0 SAMPAI 4:
      ... (lanjutkan untuk p3, p4, p5)
      
      // Pastikan tidak ada pekerjaan yang sama dalam satu urutan
      JIKA ada pekerjaan duplikat, LANJUT

      // Jika urutan valid, hitung biayanya
      biayaSekarang = hitung_total_biaya(urutan_p1_p2_p3_p4_p5)

      // Bandingkan dengan juara bertahan
      JIKA biayaSekarang < biayaTerbaik:
        biayaTerbaik = biayaSekarang
        urutanTerbaik = urutan_nama_p1_p2_p3_p4_p5
      AKHIR JIKA
    ...
  AKHIR UNTUK

  // 4. Tampilkan hasilnya
  CETAK urutanTerbaik, biayaTerbaik
SELESAI

Implementasi Kode Program (Java)

public class SchedulingBruteForceLoop {
    public static void main(String[] args) {
        String[] nama = {"A", "B", "C", "D", "E"};
        int[] durasi = {3, 2, 5, 1, 4};
        int[] bobot  = {4, 2, 10, 1, 3};

        int bestCost = Integer.MAX_VALUE;
        String bestOrder = "";

        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                if (j == i) continue;
                for (int k = 0; k < 5; k++) {
                    if (k == i || k == j) continue;
                    for (int l = 0; l < 5; l++) {
                        if (l == i || l == j || l == k) continue;
                        for (int m = 0; m < 5; m++) {
                            if (m == i || m == j || m == k || m == l) continue;

                            int[] urut = {i, j, k, l, m};

                            // hitung total cost
                            int waktu = 0, total = 0;
                            for (int idx : urut) {
                                waktu += durasi[idx];
                                total += waktu * bobot[idx];
                            }

                            if (total < bestCost) {
                                bestCost = total;
                                bestOrder = nama[i] + " " + nama[j] + " " + nama[k] + " " + nama[l] + " " + nama[m];
                            }
                        }
                    }
                }
            }
        }
        System.out.println("Urutan terbaik: " + bestOrder);
        System.out.println("Total (waktu × bobot) = " + bestCost);
    }
}

Solusi Akhir

Pada algoritma brute force, kita perlu mencoba semua kemungkinan urutan pekerjaan (total 5! = 120 urutan). Untuk tiap urutan, kita menghitung waktu selesai kumulatif lalu mengalikan dengan bobot, dan hasilnya dijumlahkan. Dari semua hasil itu kita pilih yang paling kecil.

Karena jumlah pekerjaan hanya lima, brute force masih memungkinkan. Jika kode program di atas dijalankan, hasil optimal yang didapatkan adalah:

• Urutan Terbaik: C → A → B → D → E
• Total Biaya Minimum: 158