ALGORITMA

(sumber: https://course-net.com/blog/algoritma-adalah/)

KASUS PENJADWALAN KULIAH DI UNSULBAR

bagian akademik UNSULBAR harus menyusun jadwal perkuliahan. Ada banyak mata kuliah, dosen, dan kelas, tapi ruang kuliah terbatas. Kalau jadwal dibuat sembarangan, bisa jadi dua mata kuliah bertabrakan di jam dan ruangan yang sama.

INPUT

1. Daftar mata kuliah yang akan di ajarkan

2. Nama dosen nya

3. Jam berapa kuliah nya berlangsung

4. Daftar ruang kuliah

PROSES

1. Cek semua mata kuliah dan jam kuliah nya

jika ada 2 matkul di jam yang sama kita tidak boleh kasih di ruangan yang sama

2. Bagi mata kuliah ke ruang kuliah yang berbeda

misal nya:

a. Algoritma (senin 07:30-09:10) ke utbk 2

b. PBO (senin 07:30-09:10) ke hp 5

c. Basis data (senin 07:30-09:10) ke hp 6

3. Kalau jamnya berbeda, kita bisa memakai ruangan yang sama

misal:

a. Statistika (Senin 09:30-11:10) boleh di ruangan hp 5

OUTPUT

Hasil akhirnya berupa jadwal kuliah yang rapi dan jelas tidak bertabrakan

2. A. Alasan algoritma saya efektif

efektif karena dia langsung mencegah bentrok sejak awal. Jadi, setiap kali ada mata kuliah baru, sistem langsung cek dulu: Apakah mata kuliah baru ini bertabrakan atau tidak Kalau tabrakan, otomatis dipindahkan ke ruang lain yang kosong. Kalau tidak, bisa ditempatkan di ruang yang sama tapi di jam berbeda.

Dengan cara ini semua ruangan bisa di pakai secara bergantian dan tidak ada ruangan yang kosong dalam waktu yang terlalu lama, jadi singkat nya Algoritma ini efektif karena bisa mencegah bentrok, memaksimalkan ruangan dan serta meminimalisir ruangan yang bertabrakan.

B. Terjadi kebutuhan untu mengubah algoritma secara keseluruhan atau tidak?

Tidak akan mengubah algoritma secara keseluruhan tetapi menyesuaikan nya

INPUT

1. Daftar mata kuliah yang akan di ajarkan

2. Nama dosen nya

3. Jam berapa kuliah nya berlangsung

4. Daftar ruang kuliah

5. Tiba-tiba ada kegiatan memakai ruangan UTBK 2 pada hari senin(ruangan tidak tersedia hari senin(perubahan input)

PROSES SETELAH ADA INPUTAN BARU

1. Maka semua mata kuliah yang ada di UTBK 2 akan di pindahkan hari serta menyesuaikan pada jadwal di hari penggantinya misal nya:

matkul Algoritma yang awal nya UTBK 2 hari senin jam 07:30-09:10 akan pindah ke hari selasa dan mengisi ruangan serta jam yang kosong

OUTPUT

Hasil akhirnya berupa jadwal kuliah yang rapi dan jelas tidak bertabrakan

3. BAGAIMANA ANDA MEMASTIKAN BAHWA ALGORITMA ANDA TIDAK HANYA EFISIEN DAN EFEKTIF TETAPI JUGA ADIL DAN TRANSPARAN

Algoritma penjadwalan ini bisa dibilang adil karena semu mata kuliah diperlakukan sama. Tidak ada yang di utama hanya karena dosennya atau kelas nya di anggap lebih penting. Aturannya satu: kalau ada kuliah di jam yang sama merreka tidak boleh masuk ke ruangan yang sama. Jadi siapa pun dapat kesempatan yang sama untuk mendapatkan ruangan.

Selain itu, algoritma ini juga transparan karena cara kerjanya bisa dilihat dan dipahami. Misalnya, data awal yang dipakai jelas: daftar mata kuliah, dosen, jam, dan jumlah ruang. Dari situ prosesnya bisa ditelusuri, sampai keluar jadwal akhir yang bisa dicek bersama. Kalau ada bentrok, semua orang bisa tahu kenapa itu terjadi dan bagaimana cara menyelesaikannya.

==========================================================================

TUGAS 2

public class BruteForce {
            static int[][] graph = {
                    {0,1,1,0,0,0,0,1},
                    {1,0,1,0,0,1,0,0},
                    {1,1,0,1,1,0,0,0},
                    {0,0,1,0,1,0,0,1},
                    {0,0,1,1,0,0,1,0},
                    {0,1,0,0,0,0,0,0},
                    {0,0,0,0,1,0,0,0},
                    {1,0,0,1,0,0,0,0}
            };

            static int n = 8;
            static int minColors = Integer.MAX_VALUE;
            static int[] bestSolution;
            static String[] colorNames = {
                    "", "Merah", "Hijau", "Biru", "Kuning", "Ungu", "Oranye", "Coklat", "Abu-abu"
            };
            public static void main(String[] args) {
                int[] colors = new int[n];
                bruteForce(colors, 0, 1);
                System.out.println("Jumlah warna minimum: " + minColors);
                System.out.print("Pewarnaan terbaik: ");
                for (int i = 0; i < n; i++) {
                    System.out.print("Node " + (i+1) + " -> " + colorNames[bestSolution[i]] + " | ");
                }
            }
            static void bruteForce(int[] colors, int idx, int maxColorUsed) {
                if (idx == n) {
                    if (isValid(colors)) {
                        if (maxColorUsed < minColors) {
                            minColors = maxColorUsed;
                            bestSolution = colors.clone();
                        }
                    }
                    return;
                }
                for (int color = 1; color <= maxColorUsed + 1; color++) {
                    colors[idx] = color;
                    bruteForce(colors, idx + 1, Math.max(maxColorUsed, color));
                }
            }
            static boolean isValid(int[] colors) {
                for (int i = 0; i < n; i++) {
                    for (int j = i + 1; j < n; j++) {
                        if (graph[i][j] == 1 && colors[i] == colors[j]) return false;
                    }
                }
                return true;
            }
        }

public class BruteForce {

static int[][] graph = {

{0,1,1,0,0,0,0,1},

{1,0,1,0,0,1,0,0},

{1,1,0,1,1,0,0,0},

{0,0,1,0,1,0,0,1},

{0,0,1,1,0,0,1,0},

{0,1,0,0,0,0,0,0},

{0,0,0,0,1,0,0,0},

{1,0,0,1,0,0,0,0}

};

static int n = 8;

static int minColors = Integer.MAX_VALUE;

static int[] bestSolution;

static String[] colorNames = {

"", "Merah", "Hijau", "Biru", "Kuning", "Ungu", "Oranye", "Coklat", "Abu-abu"

};

public static void main(String[] args) {

int[] colors = new int[n];

bruteForce(colors, 0, 1);

System.out.println("Jumlah warna minimum: " + minColors);

System.out.print("Pewarnaan terbaik: ");

for (int i = 0; i < n; i++) {

System.out.print("Node " + (i+1) + " -> " + colorNames[bestSolution[i]] + " | ");

}

static void bruteForce(int[] colors, int idx, int maxColorUsed) {

if (idx == n) {

if (isValid(colors)) {

if (maxColorUsed < minColors) {

minColors = maxColorUsed;

bestSolution = colors.clone();

}

return;

}

for (int color = 1; color <= maxColorUsed + 1; color++) {

colors[idx] = color;

bruteForce(colors, idx + 1, Math.max(maxColorUsed, color));

}

static boolean isValid(int[] colors) {

for (int i = 0; i < n; i++) {

for (int j = i + 1; j < n; j++) {

if (graph[i][j] == 1 && colors[i] == colors[j]) return false;

}

return true;

}

ini adalah output nya

C:\Users\LENOVO\OneDrive\Dokumen\IntelijeaProject\Algoritma\out\production\Algoritma BruteForce

Jumlah warna minimum: 3

==========================================================================TUGAS 3

🌈 Cerita: Negeri Simpul dan Cat Ajaib

Di sebuah negeri ajaib bernama Graphlandia, ada 8 kerajaan (node/simpul).
Setiap kerajaan punya jalan yang menghubungkan mereka dengan kerajaan lain (edge/tetangga).

Tapi ada satu masalah besar:

Kalau dua kerajaan bertetangga pakai warna bendera yang sama, maka akan terjadi kekacauan diplomatik. 😱

Untuk menghindari perang, Dewan Graphlandia memutuskan memakai cat ajaib yang terdiri dari 5 warna:
👉 Merah, Hijau, Biru, Kuning, Ungu.

Mereka harus mewarnai semua kerajaan dengan aturan:

a.Dua kerajaan bertetangga tidak boleh punya warna yang sama.

b.Pewarnaan dilakukan cepat dengan cara serakah (greedy): setiap kerajaan ambil warna pertama yang masih bebas dari tetangganya

⚙️ Prosesnya (Algoritma Greedy dalam cerita)

Kerajaan 1 melihat tetangganya (2,3,8) belum ada yang punya warna → dia ambil warna Merah.
Kerajaan 2 cek tetangganya (1,3,6). Karena 1 sudah pakai Merah → dia ambil Hijau.
Kerajaan 3 tetangganya (1,2,4,5). Sudah ada Merah (1) dan Hijau (2) → dia ambil Biru.
Kerajaan 4 tetangganya (3,5,8). Karena 3 pakai Biru, sisanya belum → dia bebas ambil Merah.
Kerajaan 5 tetangganya (3,4,7). Ada Biru (3) dan Merah (4) → dia ambil Hijau.
Kerajaan 6 hanya bertetangga dengan 2 (Hijau) → dia ambil Merah.
Kerajaan 7 bertetangga dengan 5 (Hijau) → dia ambil Merah.
Kerajaan 8 bertetangga dengan 1 (Merah) dan 4 (Merah) → dia nggak boleh pakai Merah, jadi ambil Hijau.

==========================================================================

TUGAS 4

Tujuan utama DFS adalah untuk mengunjungi setiap simpul (node) dalam graf tepat satu kali. Ide dasarnya adalah "masuk lebih dalam terlebih dahulu". Algoritma ini akan terus menelusuri satu cabang sampai ke ujung, baru kemudian kembali (backtrack) untuk menelusuri cabang lain yang belum dikunjungi.

Untuk melacak simpul mana yang harus dikunjungi selanjutnya dan untuk menghindari siklus tak terbatas (infinite loops), DFS menggunakan:

Mekanisme LIFO (Last-In, First-Out): Ini diimplementasikan baik secara implisit melalui rekursi (menggunakan call stack) atau secara eksplisit menggunakan struktur data Stack.

Penanda "Visited": Sebuah array atau set untuk mencatat simpul-simpul yang sudah pernah dikunjungi agar tidak dikunjungi lagi.

Cara Kerja Algoritma

Berikut adalah langkah-langkah umum dari algoritma DFS secara rekursif, yang merupakan implementasi paling umum:

Pilih Titik Awal: Mulai dari sebuah simpul awal (misalnya, A).

Tandai dan Proses: Tandai simpul A sebagai "sudah dikunjungi" (visited). Lakukan operasi yang diinginkan pada simpul ini (misalnya, mencetaknya).

Kunjungi Tetangga: Lihat semua tetangga dari simpul A (misalnya, B, C).

Masuk Lebih Dalam (Rekursi): Untuk setiap tetangga yang belum pernah dikunjungi, panggil kembali fungsi DFS untuk tetangga tersebut. Misalnya, jika tetangga pertama adalah B, maka algoritma akan langsung pindah ke B dan mengulangi proses dari langkah 2 untuk B dan tetangganya, sebelum kembali untuk memeriksa tetangga lain dari A (yaitu C).

Backtrack: Jika sebuah simpul sudah tidak memiliki tetangga yang belum dikunjungi, eksekusi fungsi akan selesai. Ini secara otomatis akan "kembali" ke pemanggilan fungsi sebelumnya (misalnya, dari B kembali ke A) untuk melanjutkan penelusuran pada tetangga lain yang belum dijelajahi.

Selesai: Algoritma berhenti ketika semua simpul yang terjangkau dari titik awal telah dikunjungi.

Contoh Sederhana

Mari kita terapkan DFS pada graf sederhana di bawah ini, dimulai dari simpul A.

Urutan Penelusuran:

Mulai dari A. Tandai A sebagai visited.

Path: A

Lihat tetangga A: B dan D. Pilih satu untuk dijelajahi, misalnya B.

Pindah ke B. Tandai B sebagai visited.

Path: A -> B

Lihat tetangga B: C. C belum dikunjungi.

Pindah ke C. Tandai C sebagai visited.

Path: A -> B -> C

Lihat tetangga C: D. D belum dikunjungi.

Pindah ke D. Tandai D sebagai visited.

Path: A -> B -> C -> D

Lihat tetangga D: A dan E. A sudah visited. Pilih E.

Pindah ke E. Tandai E sebagai visited.

Path: A -> B -> C -> D -> E

Simpul E tidak punya tetangga yang belum dikunjungi. Backtrack ke D.

Simpul D tidak punya tetangga lain yang belum dikunjungi. Backtrack ke C.

Simpul C tidak punya tetangga lain yang belum dikunjungi. Backtrack ke B.

Simpul B tidak punya tetangga lain yang belum dikunjungi. Backtrack ke A.

Di A, tetangga D sudah dikunjungi. Semua cabang dari A sudah dijelajahi.

Proses selesai. Urutan simpul yang dikunjungi adalah: A, B, C, D, E.

Aplikasi dan Kegunaan

DFS sangat berguna untuk berbagai masalah dalam teori graf, di antaranya:

Menemukan Jalur (Pathfinding): Mencari tahu apakah ada jalur antara dua simpul dalam graf.

Mendeteksi Siklus (Cycle Detection): Menemukan adanya siklus dalam sebuah graf.

Topological Sorting: Mengurutkan simpul dalam graf berarah (DAG) secara linear.

Menemukan Komponen Terhubung (Connected Components): Mengelompokkan simpul-simpul yang saling terhubung dalam sebuah graf.

Penyelesaian Maze dan Puzzle: Seperti pada contoh labirin, DFS dapat digunakan untuk menemukan jalan keluar.

Kompleksitas

Kompleksitas Waktu: O(V+E), di mana V adalah jumlah simpul (vertices) dan E adalah jumlah sisi (edges), karena setiap simpul dan sisi akan dikunjungi tepat satu kali.

Kompleksitas Ruang: O(V), karena dalam kasus terburuk, kedalaman rekursi atau ukuran stack bisa mencapai jumlah seluruh simpul.

Tentu, ini adalah contoh kode Java untuk implementasi algoritma Depth-First Search (DFS) pada sebuah graf.

Kode ini menggunakan rekursi untuk menelusuri graf secara mendalam.

Cerita: Proyek Pengecatan Kompleks "Grafika Indah" 🏘️

Alkisah, di sebuah kota digital, berdirilah sebuah kompleks perumahan baru yang unik bernama "Grafika Indah". Kompleks ini memiliki 8 rumah yang letaknya saling terhubung oleh jalan setapak.

Pak Budi, sang ketua RT yang baru terpilih, mendapat tugas pertama: mengecat semua 8 rumah tersebut. Pengembang perumahan memberikan satu aturan ketat: "Dua rumah yang terhubung langsung oleh jalan setapak tidak boleh memiliki warna cat yang sama."

Tentu saja, Pak Budi ingin menyelesaikan tugas ini dengan seefisien mungkin, yaitu menggunakan jenis warna cat sesedikit mungkin agar hemat biaya.

Dengan membawa denah kompleks dan daftar cat, Pak Budi pun memulai pekerjaannya.

Proses Pengecatan Langkah demi Langkah 🎨

Pak Budi memutuskan untuk mengecat rumah secara berurutan dari nomor 1 hingga 8. Palet cat yang ia siapkan adalah Merah, Biru, dan Hijau.

Rumah 1: Rumah ini adalah yang pertama. Belum ada rumah lain yang dicat, jadi Pak Budi bebas memilih. Untuk memulai, ia memilih warna pertama dari daftarnya.

Rumah 1 dicat dengan warna Merah.

Rumah 2: Pak Budi pindah ke Rumah 2. Ia melihat denahnya, Rumah 2 terhubung dengan Rumah 1. Karena Rumah 1 sudah Merah, ia tidak boleh memakai warna Merah. Ia pun mengambil warna berikutnya.

Rumah 2 dicat dengan warna Biru.

Rumah 3: Ini adalah rumah yang sibuk, terhubung dengan Rumah 1 (Merah) dan Rumah 2 (Biru). Pak Budi berpikir, "Saya tidak bisa pakai Merah, tidak bisa pakai Biru." Ia terpaksa membuka kaleng cat baru.

Rumah 3 dicat dengan warna Hijau.

Rumah 4: Pak Budi memeriksa tetangga Rumah 4 yang sudah dicat, yaitu Rumah 3 (Hijau) dan Rumah 5 (belum dicat) serta Rumah 8 (belum dicat). Karena hanya warna Hijau yang dilarang, ia bisa kembali menggunakan warna pertama yang tersedia untuk berhemat.

Rumah 4 dicat dengan warna Merah.

Rumah 5: Tetangganya adalah Rumah 3 (Hijau) dan Rumah 4 (Merah). Warna Merah dan Hijau dilarang. Warna pertama yang bisa ia gunakan adalah Biru.

Rumah 5 dicat dengan warna Biru.

Rumah 6: Tetangga satu-satunya adalah Rumah 2 (Biru). Jadi, ia bebas memakai warna lain. Untuk hemat, ia kembali ke warna pertama.

Rumah 6 dicat dengan warna Merah.

Rumah 7: Tetangga satu-satunya adalah Rumah 5 (Biru). Sama seperti sebelumnya, ia bisa memakai warna Merah.

Rumah 7 dicat dengan warna Merah.

Rumah 8: Rumah terakhir. Pak Budi melihat tetangganya adalah Rumah 1 (Merah) dan Rumah 4 (juga Merah). Satu-satunya warna yang dilarang adalah Merah. Warna berikutnya yang tersedia adalah Biru.

Rumah 8 dicat dengan warna Biru.

Hasil Akhir Proyek ✅

Pak Budi menatap hasil kerjanya dengan puas. Semua 8 rumah kini berwarna cerah, dan ia berhasil mematuhi aturan pengembang. Ia lalu membuat laporan akhir:

Cat Merah digunakan untuk Rumah: 1, 4, 6, 7

Cat Biru digunakan untuk Rumah: 2, 5, 8

Cat Hijau digunakan untuk Rumah: 3

Ia tersenyum. Dengan perencanaan yang cermat, ia berhasil menyelesaikan proyek besar ini hanya dengan 3 jenis warna cat. Misi efisiensi pun berhasil!

==========================================================================

TUGAS 4

Petualangan Algoritma BFS: Misi Pewarnaan Graf 🎨

Ini adalah cerita tentang program Java kita yang mendapat tugas untuk mewarnai sebuah peta digital yang terdiri dari 8 titik (node). Aturannya ketat: tidak boleh ada dua titik bertetangga yang warnanya sama. Misi utamanya adalah menyelesaikan tugas ini dengan palet warna sesedikit mungkin.

Babak 1: Persiapan di `main` Method

Semuanya dimulai di main method. Di sinilah kita mempersiapkan segalanya.

Membangun Peta (Adjacency List) 🗺️ Pertama, kita harus paham petanya. Kita tidak melihatnya sebagai gambar, melainkan sebagai data. Kita gunakan struktur data Adjacency List (di Java, ini seperti Map<Integer, List<Integer>>) untuk mencatat siapa bertetangga dengan siapa.
Java
// Representasi peta dalam pikiran program 1: [2, 3, 8] 2: [1, 3, 6] 3: [1, 2, 4, 5] 4: [3, 5, 8] 5: [3, 4, 7] 6: [2] 7: [5] 8: [1, 4]
Menyiapkan Kanvas dan Palet (Data Structures) ⚙️ Kita butuh "kanvas" untuk menyimpan warna setiap titik. Sebuah array integer bernama colors berukuran 9 (kita abaikan indeks 0 agar lebih mudah) sudah cukup. Awalnya, semua isinya 0, menandakan "belum diwarnai".
int[] colors = new int[9]; // Awalnya {0, 0, 0, 0, 0, 0, 0, 0, 0}
Untuk traversal BFS, kita butuh sebuah "antrean tugas" (a Queue). Di Java, kita pakai LinkedList. Ini akan menentukan urutan titik mana yang akan kita kunjungi dan warnai.
Queue<Integer> queue = new LinkedList<>();

Babak 2: Ekspedisi Pewarnaan Dimulai

Ekspedisi kita mulai dari titik pertama yang belum diwarnai. Kita pilih Node 1.

Langkah Awal: Kita tambahkan Node 1 ke dalam antrean. queue.add(1);
Memulai Perulangan (The while loop): Selama antrean tugas tidak kosong, petualangan berlanjut!
- Giliran Node 1:
  - Kita keluarkan Node 1 dari antrean.
  - Tugas Pewarnaan: Node 1 belum punya tetangga yang diwarnai. Jadi, kita bebas memberinya warna pertama dari palet kita.
  - colors[1] = 1; // Kita sebut saja Warna 1 adalah Merah.
  - Menyebar Misi: Kita lihat tetangga Node 1: 2, 3, dan 8. Karena mereka belum pernah masuk antrean, kita masukkan mereka semua.
  - Status Antrean: [2, 3, 8]
- Giliran Node 2:
  - Kita keluarkan Node 2.
  - Tugas Pewarnaan: Siapa tetangga Node 2 yang sudah berwarna? Hanya Node 1 (Merah). Jadi, Node 2 tidak boleh Merah. Kita berikan warna palet berikutnya yang tersedia.
  - colors[2] = 2; // Warna 2 adalah Hijau.
  - Menyebar Misi: Kita lihat tetangga Node 2: 1, 3, 6. Node 1 sudah diproses, Node 3 sudah di antrean. Hanya Node 6 yang baru. Kita masukkan Node 6.
  - Status Antrean: [3, 8, 6]
- Giliran Node 3:
  - Kita keluarkan Node 3.
  - Tugas Pewarnaan: Tetangga Node 3 yang sudah berwarna adalah Node 1 (Merah) dan Node 2 (Hijau). Warna Merah dan Hijau terlarang. Kita butuh warna baru.
  - colors[3] = 3; // Warna 3 adalah Biru.
  - Menyebar Misi: Kita lihat tetangga Node 3: 1, 2, 4, 5. Node 1 & 2 sudah beres. Node 4 & 5 baru. Kita masukkan keduanya ke antrean.
  - Status Antrean: [8, 6, 4, 5]
- Giliran Node 8:
  - Kita keluarkan Node 8.
  - Tugas Pewarnaan: Tetangganya yang sudah berwarna adalah Node 1 (Merah). Node 4 masih di antrean. Jadi, Node 8 tidak boleh Merah. Warna Hijau (2) tersedia.
  - colors[8] = 2; // Node 8 diberi warna Hijau.
  - Status Antrean: [6, 4, 5]
- ... dan seterusnya. Proses ini berlanjut hingga antrean kosong. Algoritma akan secara cerdas memilih warna pertama yang valid untuk setiap node yang dikunjungi.

Babak 3: Laporan Hasil Akhir

Setelah antrean kosong, seluruh peta sudah terwarnai. Array colors kita sekarang berisi laporan lengkapnya.

Node	Tetangga Berwarna Sebelumnya	Pilihan Warna	Hasil Akhir
1	(Tidak ada)	Warna 1	🔴 Merah
2	1 (Merah)	Warna 2	🟢 Hijau
3	1 (Merah), 2 (Hijau)	Warna 3	🔵 Biru
8	1 (Merah)	Warna 2	🟢 Hijau
6	2 (Hijau)	Warna 1	🔴 Merah
4	3 (Biru), 8 (Hijau)	Warna 1	🔴 Merah
5	3 (Biru), 4 (Merah)	Warna 2	🟢 Hijau
7	5 (Hijau)	Warna 1	🔴 Merah

Epilog: Kesimpulan Misi

Program Java kita berhasil menyelesaikan misinya. Dengan mengikuti alur BFS dan menerapkan strategi pewarnaan "pilih warna valid terkecil", kita berhasil mewarnai seluruh graf.

Total warna yang kita keluarkan dari palet adalah 3. Karena kita tahu di dalam peta terdapat segitiga (seperti 1-2-3) yang sudah pasti butuh 3 warna, maka 3 adalah jumlah warna minimum yang mungkin. Misi selesai dengan efisien!

Cari Blog Ini

BLOGKU

ALGORITMA

🌈 Cerita: Negeri Simpul dan Cat Ajaib

⚙️ Prosesnya (Algoritma Greedy dalam cerita)