Beberapa Tipe Problem Pada Desain Analisis Algoritma

Sorting(Pengurutan)

Sorting merupakan proses pengurutan data yang sebelumnya disusun secara acak sehingga menjadi tersusun secara teratur menurut suatu aturan tertentu. Ada 2 jenis sorting yaitu ascending (naik) & descending (turun).

Macam-macam pengurutan :

• Exchange Sort

Melakukan pembandingan antar data, dan melakukan pertukaran apabila urutan yang didapat belum sesuai.

• Selection Sort

Mencari elemen yang tepat untuk diletakkan di posisi yang telah diketahui,dan meletakkannya di posisi tersebut setelah data tersebut ditemukan.

• Insertion Sort

Melakukan penyisipan(insertion) data di tempat yang tepat di dalam kumpulan data yang telah terurut.

• Merge Sort

Data dibagi menjadi subkumpulan-subkumpulan yang kemudian subkumpulan tersebut diurutkan secara terpisah, dan kemudian digabungkan kembali.

Contoh Kasus :

Mengurutkan beberapa nilai dari nilai yang paling tinggi ke nilai yang paling kecil.

Solusi :

Program di atas melakukan pengurutan dengan cara membandingkan array pertama dan kedua dahulu. Jika array kedua lebih besar dari array pertama maka data kedua array tersebut akan ditukar. Hal tersebut akan terus berulang hingga semua data telah terurutkan.

Searching(Pencarian)

Pencarian adalah menemukan nilai dari sekumpulan nilai yang ada. Algoritma pencarian (searching algorithm) adalah algoritma yang menerima sebuah argumen kunci dan dengan  langkah-langkah tertentu akan mencari rekaman dengan kunci tersebut.  Setelah proses pencarian dilaksanakan, akan diperoleh salah satu dari dua kemungkinan, yaitu data yang dicari ditemukan (successful) atau tidak ditemukan (unsuccessful).

Macam-macam pencarian :

• Pencarian sekuensial (Sequential searching)

Proses membandingkan setiap elemen larik satu per satu secara beruntun, mulai dari elemen pertama sampai elemen yang dicari ditemukan atau seluruh elemen sudah diperiksa.

• Pencarian Biner (binary search)

Sebuah teknik untuk menemukan nilai tertentu dengan menghilangkan setengah data pada setiap langkah,. Pencarian biner mencari nilai tengah (median), melakukan sebuah pembandingan untuk menentukan apakah nilai yang dicari ada sebelum atau sesudahnya, kemudian mencari setengah sisanya dengan cara yang sama.

Contoh Kasus :

Mencari data nis pada sekumpulan data nis.

Solusi :

Program di atas melakukan proses pencarian dengan cara membandingkan variable cari dengan semua data dari array nis. Apabila telah menemukan array yang cocok dengan variable cari maka program tersebut akan keluar dari proses looping dan mencetak hasil dari pencarian tersebut.

String Processing(Pemrosesan String)

String processing adalah metode operasi string yang umumnya berupa penggabungan (concatenation), pemenggalan (substring), pencarian posisi, penghitungan panjang string (length),  hingga pada word processing (pemrosesan kata) dan sebagainya.

Contoh Kasus :

Menggabungkan nama depan dan nama belakang dari dua variabel.

Solusi :

Program di atas memproses penggabungan dua string dengan cara menambahkan string pertama(depan) dan string kedua(belakang) ke dalam string ketiga(nama).

Permasalahan Graph

Graf adalah kumpulan noktah(simpul) di dalam bidang dua dimensi yang dihubungkan dengan sekumpulan garis(sisi). Graph dapat digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari graph adalah dengan menyatakan objek sebagai noktah, bulatan atau titik(vertex), sedangkan hubungan antara objek dinyatakan dengan garis(edge).

Contoh Kasus :

Menentukan TSP(Traveling Salesman Problem) Dengan 4 Kota.

Solusi :

I1 = (a, b, c, d, a) atau (a, d, c, b, a)  ==> panjang = 12 + 8 + 15 + 10 = 45

I2 = (a, c, d, b, a) atau (a, b, d, c, a)  ==> panjang = 5 + 15 + 9 + 12 = 41

I3 = (a, c, b, d, a) atau (a, d, b, c, a)  ==> panjang  = 5 + 8 + 9 + 10 = 32

Jadi, sirkuit Hamilton terpendek adalah I3 = (a, c, b, d, a) atau (a, d, b, c, a) dengan panjang sirkuit = 10 + 5 + 9 + 8 = 32.

Combinatorial Problem

Combinatorial problem adalah suatu masalah dalam menemukan suatu objek kombinatorik seperti permutasi, kombinasi atau subset(himpunan bagian) yang memenuhi batasan tertentu dan memiliki properti yang diinginkan.

Contoh Kasus :

Mencari banyaknya susunan ketua, bendahara dan sekretaris yang mungkin dari 8 calon.

Solusi :

n = 8

k = 3 (ketua, bendahara, sekretaris)

8P3 = 8! / (8 - 3)! = 8 x 7 x 6 x 5! / 5! = 8 x 7 x 6 = 336

Geometric Problem

Geometric problem merupakan masalah yang berkaitan dengan objek geometrik seperti titik, garis dan poligon. Misalnya  segitiga, lingkaran dan lain-lain atau dalam masa kini berupa aplikasi computer grafik dan robot.

Contoh Kasus :

Menentukan pasangan terdekat koordinat dari masing-masing titik adalah A(2,2), B(4,4), C(6,9), D(7,5), dan E(8,4).

Solusi : 

Program di atas mencoba merepresentasikan suatu himpunan titik melalui dua buah array yaitu array titikX sebagai kumpulan koordinat X dan array titikY yang merupakan data-data sumbu Y. dua buah array ini akan diproses dalam method cPoint untuk dicari nilai jaraknya menggunakan persamaan jarak dua titik.

Dalam method cPanel pertama kali dilakukan inisialisasi nilai variable dMin yang didapat dengan cara memeasukkan nilai koordinat titik pertama dan kedua dalam persamaan jarak dua titik. Kemudian melalui mekanisme perulangan dicari nilai jarak yang lain, jika nilai jarak lebih kecil daripada nilai dMin maka nilai dMin akan diganti dengan nilai jarak tersebut. Proses ini akan terus berulang hingga semua kemungkinan sudah dicoba.

Numeric Problem

Numeric problem merupakan masalah yang berkaitan dengan objek matematis yang memiliki sifat kontinyu dan mayoritas dapat diselesaikan secara aproksimasi saja misalnya memecahkan persamaan dan sistem persamaan, penghitungan integral dan lain-lain.

Contoh Kasus :

Menghitung integral dari

Solusi :

Sumber

http://web.if.unila.ac.id/nazrahefrilia/2015/11/17/tipe-tipe-sorting-2/

http://imeldapasaribu.blogspot.co.id/2014/06/pencarian-searching-dalam-algoritma.html