Permasalahan Pada Algoritma

Nama : Dera Aprinaldi

NPM : 20312113

Kelas : IF 20 C

 

Apa Itu Algoritma

Algoritma adalah suatu urutan langkah logis yang digunakan untuk menyelesaikan suatu permasalahan, jadi dimana ada algoritma pasti ada permasalahan.

Berikut adalah jenis-jenis permasalahan dan penyelesaian menggunakan algoritma

Sorting (Pengurutan)

Dalam beberapa kasus, ada beberapa data yang harus diurutkan. Maka untuk menyelesaikan masalah Sorting bisa menggunakan beberapa algoritma, contoh nya algoritma "Bubble Sort".

Bubble Sort adalah salah satu algoritma yang dapat menyelesaikan permasalahan Sorting. Sederhananya Bubble Sort adalah algoritma pengurutan dengan cara menukarkan data dengan data yang berada disebelahnya secara terus menerus, sampai satu iterasi tidak dapat dilakukan perubahan.

Contoh Penyelesaian Menggunakan Algoritma Bubble Sort :

Urutkan bilangan dari yang terkecil sampai terbesar. [6 4 1 3 2]

iterasi ke-1 : [ 6 4 1 3 2] --> [4 1 3 2 6]

iterasi ke-2 : [4 1 3 2 6 ] --> [1 3 2 4 6]

iterasi ke-3 : [1 3 2 4 6 ] --> [1 2 3 4 6]

Jadi untuk mengurutkan (sorting) data [6 4 1 3 2] dari yang terkecil hingga terbesar, menggunakan Algoritma Bubble Sort  diperlukan iterasi sebanyak 3 iterasi.

Kelebihan dan Kekurangan Algoritma Bubble Sort 

Kelebihan

• Merupakan Metode Sorting (Pengurutan) termudah.
• Algortima Metode Bubble Sort paling mudah dipahami.
• Mudah ketika diubah menjadi kode program.
• Cocok untuk data yang kecil.

Kelemahan

• Metode paling tidak efisien.
• Jika data semakin besar, maka kinerja semakin memburuk.

Searching (Pencarian) 

Searching adalah merupakan suatu proses dalam pengolahan data, yang digunakan untuk menemukan nilai (data) tertentu didalam tumpukan tipe data yang sama.

Untuk menyelesaikan masalah searching bisa digunakan beberapa algoritma, contoh nya algoritma searching paling sederahana yaitu "Sequential Search" atau biasa disebut juga dengan "Linear Search". 

Sequential Search atau Linear Search ini melakukan pencarian dengan membandingkan setiap elemen  pada larik secara satu persatu secara berurut, mulai dari elemen awal sampai elemen akhir.

Contoh Penyelesaian Menggunakan Algoritma Sequential Search :

Carilah bilangan 3 pada data berikut [6  4 1 3 2], terletak pada indeks dan perlu berapa langkah untuk menemukannya.

step-1 : 3 = 6 (salah)

step-2 : 3 = 4 (salah)

step-3 : 3 = 1 (salah)

step-4 : 3 = 3 (benar)

Jadi bilangan 3 ditemukan pada indeks ke 4 dari data pada indeks ke-4, dengan memerlukan 4 langkah.

Kelebihan dan Kekurangan Algoritma Sequential Search

Kelebihan

• Proses pencarian dengan menggunakan algoritma sequential search lebih cepat pada jumlah data yang kecil dan tidak terlalu banyak.
• Algoritma sequential search merupakan algoritma yang sederhana dan tidak terlalu rumit.

Kelemahan

• Tidak efektif pada jumlah data yang berukuran besar.
• Beban pada komputasi lebih berat.

String Processing

Algoritma pencarian string, atau biasa disebut dengan algoritma pencocokan string, adalah algoritma yang digunakan untuk melakukan pencarian kemunculan dari string panjang dan string pendek. Pada string pendek disebut pattern dan pada string yang lebih panjang disebut teks.

 Untuk memecahkan masalah string processing ini, bisa menggunakan beberapa algoritma analsis, salah satunya yaitu algoritma analisis Straightforward Matching.

Algoritma straightforward matching adalah brute-force untuk menyelesaikan permasalahan pencarian pada string.

Contoh Penyelesaian Permasalahan Dengan Algoritma Straightforward Matching:

pertama kita membandingkan karakter pertama dari string dengan karakter pertama dari bagian text. Jika sama maka kita akan bergerak ke karakter selanjutnya, terus menerus sampai kita telah mencocokan keseluruhan string atau menemukan karakter yang tidak sama.

Jika saat melakukan pencocokan kita menemukan karakter yang tidak sama, maka kita akan bergerak satu langkah ke bagian selanjutnya, dan memulai kembali pencocokan string dari awal.

Kelebihan dan Kekurangan Algoritma Straightforward Matching

Kelebihan

• Algoritma ini sangat powerfull

Kekurangan

• Waktu yang akan digunakan akan sangat lama dan tidak efektif ketika harus mencari sebuah sring dalam text dengan ukuran yang sangat panjang

Graph Problem

Graph adalah kunpulan dari simpul-simpul (nodes/vertices) V, dan kumpulan sisi (edges) E yang menghubungkan sepasang simpul, atau bisa sebagai himpunan benda-benda yang disebut verteks (node) yang terhubung oleh sisi.

Biasanya Graf digambarkan dengan kumpulan titik, yang dihubungkan oleh garis-garis.

Untuk memecahkan masalah pada Graph Problem bisa diselesaikan dengan Algorima Greedy.

Algoritma greedy adalah metode yang biasa digunakan untuk mencari solusi yang paling optimum.

Solusi optimum adalah solusi yang dapat memnuhi semua kendala.

Contoh Penyelesaian Permasalah Dengan Algoritma Greedy:

Algoritma Greedy adalah algoritma yang menyelesaikan masalah secara langkah per langkah.

Misalkan ada sebauh koin :1,3,5.

uang senilai 8 dapat ditukar dengan cara :

• 1+1+1+1+1+1+1+1= 8 (8 koin)
• 1+1+1+5 = 8 (6 koin)
• 1+1+3+3 = 8 (4 koin)
• 3+5 = 8 (2 koin)                 Solusi Optimal

Jadi solusi optimalnya dari menukar uang senilai 8 hanya perlu 2 koin saja.

Kelebihan dan Kekurangan Algoritma Greedy

Kelebihan

• Fast response
• Efisien, tidak membutuhkan waktu banyak
• Mudah di implementasikan.

Kekurangan

• hasil akhir dari algoritma greedy kurang baik
• Tidak bisa memantau parameter
• Tidak ada pilihan lagi jika persoalan tidak dapat diselesaikan.

Combinatorial Problem

Combinatorial adalah salah satu cabang dari ilmu matematika diskrit yang memiliki tujuan untuk menghitung jumlah penyusanan objek-objek tanpa mengenumerasi kemungkinan dari susunannya.

Combinatorial Problem adalah permasalahan matematis untuk menyusun, mengelompokkan, mengurutkan, atau memilih beberapa objek diskrit.

Untuk menyelesaikan permasalahan ini dapat menggunakan Algoritma Nearest Neighbor.

Algoritma Nearest Neighbor adalah sebuah metode untuk klasifikasi terhadap suatu kumpulan data berdasarkan data yang sudah terklasifikasi sebelumnya.

Contoh Penyelesaian Permasalahan Dengan Algoritma Nearest Neighbor

salah satu permasalahannya adalah VRP atau Vehicle Routing problem, yaitu permasalahan optimasi untuk penentuan rute dengan keterbatasan kapasitas kendaraan.

Contohnya adalah ketika ada seorang tukang pos yang berangkat dari suatu kota untuk pergi ke beberapa kota yang lain, setiap kotanya hanya dikunjungi oleh satu tukang pos saja. Tujuan utama dari permasalahan ini adalah menimalkan total jarak atau total biaya perjalanan.

Dan berikut adalah langkah-langkah menggunakan Algoritma Nearest Neighbor

1. Titik mulai rute dimulai dari kantor pos.
2. Mencari lokasi penerima terdekat dari kantor pos yang belum dikunjungi.
3. Mencari lokasi terdekat lain dari lokasi terpilih sebelumnya. Ketika mencari lokasi lain terdapat beberapa hal yang harus di pertimbangkan yaitu:
   a. Total jumlah dari barang yang dibawa tidak melebihi kapasitas kendaraan yang digunakan.
   b. Jika terdapat lokasi terpilih selanjutnya dan masih terdapat sisa kapasitas kendaraan maka ulangi langkah 2.
4. Apabila kendaraan tidak memiliki sisa kapasitas, maka kembali ke langkah 1.
5. Algoritma akan berhenti jika semua penerima telah dikunjungi sebanyak 1 kali.

Kelebihan dan Kelemahan Algoritma Nearest Neighbor

Kelebihan

• Algoritma Nearest Neighbor sangat fleksibel
• Mudah dipahami dan diimplemantasikan\
• Efektif pada data yang besar
• Konsistensi yang kuat

Kelemahan

• Perlu menentukan parameter.
• Rentan pada perbedaan rentang variabel
• Nilai komputasi yang tinggi
• Tidak menangani nilai yang hilang secara implisit

Geometric Problem

Geometric Problem adalah suatu permasalahan dengan mempelajari algoritma yang berhubungan dengan ilmu geometri. Atau dari segi komputasi geometric problem adalah teknik-teknik  untuk mendesain dan menganalisis algoritma geometrik.

Geometric Problem membahas tentang bagaimana cara untuk membentuk poligon dari sekumpulan titik, pendeteksian suatu titik terhadap suatu poligon apakah titik terebut ada dalam poligon atau tidak, dll.

Untuk menyelesaikan Geometric Problem dapat menggunakan Algoritma Divide and Conquer.

Divide berarti membagi masalah menjadi 2 bagian yang lebih kecil.

Conquer berarti menyelesaikan masalah dengan sub permasalahan yang ada

Contoh Menyelesaikan Permasalahan dengan Algoritma Divine and Conquer 

Salah satu permasalahan nya adalah Problem Closest Pair berikut adalah gambarnya

Masalah ini bertujuan untuk menentukan pasangan titik terdekat.

Berikut adalah langkah-langkah penyelesaian dengan Algoritma Divide and Conquer

• Langkah 0 : Himpunan S sebagai input, yang terdiri dari n titik.
• Langkah 1 : Menentukan garis vertikal m sebagai nilai tengah, yang membagi himpunan S menjadi S1 dan S2 menurut sumbu X.
• Langkah 2 : Menentukan d1 dan closest pair of ponts dari d1 pada S1, dan menentukan d2 dan closest pair of points dari d2 pada S2, dengan cara rekursiv.
• Langkah 3 : d = min(d1,d2)
• Langkah 4 : Membuat jarak d ke arah kanan dan ke arah kiri dari garis m yaitu [m-d,m] sebagai P1 dan [m,m+d] sebagai p2.
• Langkah 5 : Titik pada P1 dan P2 diproyeksikan pada garis m untuk disortir terhadap sumbu Y, maka terbentuk P1* dan P2*
• Langkah 6 : Setiap titik pada P1* akan diperiksa oleh P2* secara rekursif pada daerah persegi dx 2d untuk mencari closest pair of points yyang disebut d3.
• Langkah 7 : ds = (d,d3)

Kelebihan dan Kelemahan Algoritma Divide and Conquer

Kelebihan

• Dapat memecahkan masalah yang sulit
• Memiliki efisiensi algoritma yang tinggi
• Dapat bekerja secara paralel
• Akses memori yang cukup kecil

Kelemahan

• Proses perulangan yang lambat
• Ketika menyelesaikan masalah yang sederhana terasa lebih rumit

Numerical Problem

Numerical Problem adalah suatu masalah yang berhubungan dengan objek yang bersifat matematis dan berkelanjutan. Metode numerik merupakan teknik yang digunakan untuk memformulasi kan masalah matematis sehingga dapat diselesaikan dengan menggunakan metode operasi perhitungan.

Numerical Problem bisa diselesaikan dengan Metode numerik.

Contoh Penyelesaian Permasalahan Dengan Metode Numerik

Permasalahan yang dapat diselesaikan diantara lain: Persamaan besar dan sistem persamaan, differensial, menghitung integral tak hingga, geometri yang rumit, memperkirakan cuaca, dll.

Berikut adalah tahap menyelesaikan masalah dengan metode numerik

1. Pemodelan
   Mengubah suatu permasalahan yang akan diselesaikan kedalam bentuk persamaan matematika.
2. Penyederhanaan model
   Menyederhanakan model matematika yang dihasilkan pada tahap sebelumnya dengan membuat pengandaian sehingga beberapa parameter dapat diabaikan.
3. Formulasi numerik
   Membuat hasil dari penyederhanaan model matematika secara numerik menjadi bentuk formula, dengan cara menentukan metode numerik apa yang digunakan dan membuat algoritmanya
4. Pemrograman
   Mengubah algoritma yang telah dibuat menjadi suatu program komputer.
5. Operasional
   Atau sering disebut tahap pengujian, menguji program komputer apakah layak digunakan dan disebar luaskan atau tidak.
6. Evaluasi
   Setelah program selesai di ujicoba, maka perlu dilakukan analisa untuk memperkirakan kualitas dari hasil solusi numerik tersebut.

Kelebihan dan Kelemahan Metode Numerik

Kelebihan

• Dapat menangani sistem persamaan besar, atau geometri yang rumit.
• Dapat menghitung dengan cepat dan mudah.
• Solusi yang dihasilkan selalu berupa angka.
• Semua masalah perhitungan dapat diselesaikan dengan metode numerik
• Tampilan hasil perhitungan dapat disimulasikan.

Kelemahan

• Hasil yang diperoleh hanya mendekati atau hampir.
• Tanpa bantuan komputer, proses perhitungan akan memakan waktu lama, dan berulang-ulang.