Permasalahan sorting
Urutkan [ 5 4 3 2 ] dari terkecil ke terbesar
Solusi:
Pengurutan menggunakan metode Bubble Sort
1. Membandingkan data
ke-i dengan data ke-(i+1) (tepat bersebelahan). Jika tidak sesuai maka tukar
(data ke-i = data ke-(i+1) dan data ke-(i+1) = data ke-i). Apa maksudnya tidak
sesuai? Jika kita menginginkan algoritme menghasilkan data dengan urutan ascending
(A-Z) kondisi tidak sesuai adalah data ke-i > data ke-i+1, dan sebaliknya
untuk urutan descending (A-Z).
2. Membandingkan data
ke-(i+1) dengan data ke-(i+2). Kita melakukan pembandingan ini sampai data
terakhir. Contoh: 1 dgn 2; 2 dgn 3; 3 dgn 4; 4 dgn 5 … ; n-1 dgn n.
3. Selesai satu iterasi,
adalah jika kita sudah selesai membandingkan antara (n-1) dgn n. Setelah
selesai satu iterasi kita lanjutkan lagi iterasi berikutnya sesuai dengan
aturan ke-1. mulai dari data ke-1 dgn data ke-2, dst.
4. Proses akan berhenti jika tidak ada pertukaran dalam satu iterasi.
Iterasi ke-1: 5, 4, 3, 2 :: 4, 3, 5, 2 :: 4, 3, 2, 5 (ada 3 pertukaran)
Iterasi ke-2: 3, 4, 2, 5 :: 3, 2, 4, 5 :: 3, 2, 4, 5 (ada 2 pertukaran)
Iterasi ke-3: 2, 3, 4, 5 :: 2, 3, 4, 5 :: 2, 3, 4, 5 (ada 1 pertukaran)
Iterasi ke-4: 2, 3, 4, 5 :: 2, 3, 4, 5 :: 2, 3, 4, 5 (ada 0 pertukaran) -> proses selesai
Kelebihan dan Kekurangan metode:
Kelebihan :
- Metode Buble Sort merupakan metode yang paling simpel
- Metode Buble Sort mudah dipahami algoritmanya
Kelemahan:
- Meskipun simpel metode Bubble sort merupakan metode pengurutan yang paling tidak efisien.
- Pada saat mengurutkan data yang sangat besar akan mengalami kelambatan luar biasa.
Permasalahan Searching
Cari 2 dari [ 3 4 2 5 1 ]
Solusi:
Pencarian menggunakan sequential search
data yang ingin ditemukan ialah 2, maka proses yang dilakukan iyalah, mengecek data satu persatu secara berurutan, sehingga menemukan nilai yang dicari. Hasil yang didapatkan iyalah, nilai 2 terdapat pada baris ke 3.
Kelebihan dan Kekurangan metode:
Kelebihan :
- Algoritma ini sangat efektif digunakan pada pencarian data
yang memiliki jumlah nilai yang sedikit.
- Bila nilai yang dicari terdapat pada awal kumpulan data, maka algoritma ini akan cepat menyelesaikan prosesnya.
Kekurangan :
- Algoritma ini tidak efektif digunakan pada data yang
banyak, dikarenakan algoritma ini menggunakan proses dengan cara mengecek satu
persatu data yang ada hingga menemukan data yang dicari.
Permasalahan String processing
Cari GULA dari teks
Solusi:
Brute Force
Pattern : GULA
Teks : GILAGULU GULAKU GALIGALIGU
Dengan pendekatan brute force, dilakukan pengecekan untuk setiap indeks teks, apakah indeks tersebut merupakan awal dari pattern yang akan di-match.
Kelebihan dan Kekurangan metode:Kelebihan
1. Algoritma Brute Force dapat digunakan untuk memecahkan
hampir sebagian besar masalah
2. Algoritma Brute Force sederhana dan mudah dimengerti
3. Algoritma Brute Force menghasilkan algoritma yang layak untuk beberapa masalah penting seperti pencarian, pengurutan, pencocokkan string , atau perkalian matriks
Kekurangan
1. Algoritma Brute Force jarang menghasilkan algoritma yang
manjur
2. Beberapa algoritma Brute Force lambat, sehingga tidak
dapat diterima
Graph problems
Solusi:
Greedy
- Langkah 1
: New York menuju Chicago (Jarak = 809)
- Langkah 2
: Chicago menuju Dallas (Jarak = 809 + 921 = 1730)
- Langkah 3
: Dallas menuju Miami (Jarak = 809 + 921 + 1343 = 3073.
- Langkah 4
: Miami menuju New York (Jarak = 809 + 921 + 1343 + 1334 = 4407)
Kelebihan dan Kekurangan metode:
Kelebihan
dari algoritam greedy adalah cepat dalam bertindak alias fast response. Apabila
anda membutuhkan penyelesaian masalah secara instant dan juga cepat, algoritma
greedy adalah salah satu metode yang tepat. Algoritma greedy tidak membutuhkan
waktu lama untuk memikirkan opsi – opsi lain yang bisa dilakukan, serta tidak
perlu mempertimbangkan baik buruk serta konsekuensi dari apa yang diputuskan.
Kelemahan
dari algoritma greedy memiliki berupa hasil akhirnyayang tidak sebaik algoritma
brute force. Hal ini tentu saja disebabkan karena pemilihan opsi yang
ditiadakan, sehhingga dapat negative ataupun konsekuensi dari pemilihan
keputusan tersebut tidak dapat dipertanggungjawabkan secara penuh.
Combinatorial problems
Travelling
Salesman Problem atau yg disingkat dengan TSP adalah sebuah masalah kombinasi
optimasi dalam operasi penelitian dan teori ilmu komputer. Dengan daftar
sejumlah kota yang akan dikunjungi, cara ini sangat bagus untuk menemukan
dengan cepat kota yang akan dikunjungi. TSP adalah sebuah masalah untuk
menentukan urutan dari sejumlah kota yang harus dilalui oleh salesman, setiap
kota hanya boleh dilalui satu kali dalam perjalanannya, dan perjalanan tersebut
harus berakhir pada kota keberangkatannya dimana salesman tersebut memulai
perjalananya, dengan jarak antara setiap kota satu dengan kota lainnya sudah
diketahui. Salesman tersebut harus meminimalkan pengeluaran biaya, dan jarak
yang harus ditempuh untuk perjalanannya tersebut.
Solusi:
Algoritma
exhaustive, yaitu dengan mencari semua kombinasi yang mungkin terjadi, kemudian
memilih kombinasi perjalanan dengan jarak terdekat, algoritma ini mempunyai
kompleksitas n!/2n.
Permasalahan
:
• Diberikan n buah kota serta diketahui
jarak antara setiap kota satu dengan kota yang lain.
Temukan perjalanan (tour) terpendek
yang melalui setiap kota lainnya dengan hanya sekali
melewati kota-kota tersebut dan kembali
lagi ke kota asal keberangkatan.
• Permasalahan TSP ini dimodelkan sebagai
graf lengkap dengan n buah simpul. Bobot pada
setiap setiap sisi menyatakan jarak
antara dua buah kota yang bertetangga.
• Permasalahan TSP tidak lain adalah menemukan
sirkuit Hamilton dengan bobot paling
minimum.
Algoritma
exhaustive search untuk persoalan TSP :
A. Enumerasikan (list) semua sirkuit Hamilton
dari graf lengkap dengan n buah simpul.
B. Hitung (evaluasi) bobot setiap sirkuit
Hamilton yang ditemukan pada langkah 1.
C. Pilih sirkuit Hamilton yang mempunyai
bobot paling terkecil.
Algoritma tersebut sangat efisien karena simpul simpul mati tidak akan dilanjutkan lagi, sehingga dapat mengurangi jumlah operasi. Namun kelemahan dari algoritma ini adalah bahwa solusi pertama yang dihasilkan adalah solusi yang pertama kali ditemukan sehingga belum tentu solusi terbaik.
Geometric problems
Solusi:
Dengan menggunakan metode algoritma Graham's Scan, kita dapat menemukan convex
hull pada O(nLogn). Berikut ini adalah algoritma Graham's Scan :
Misalkan titik (0..n-1) adalah input dari sebuah array.
1. Cari titik paling bawah dengan membandingkan koordinat y dari semua titik. Jika ada dua titik dengan nilai y yang sama, maka titik dengan nilai koordinat x terkecil adalah yang dapat dihitung. Biarkan titik paling bawah tersebut sebagai P0. Masukkan P0 tersebut pada posisi pertama output hull.
2. Hitung sisa titik n-1 yang tersisa, dan urutkan titik-titik tersebut dengan sudut polar yang berlainan arah jarum jam di sekitar titik [0]. Jika sudut polar dari sebuah titik sama, maka simpanlah titik yang terdekat.
3. Setelah diurutkan, cek apabila dua atau lebih titik mempunyai sudut yang sama. Apabila dua atau lebih titik mempunyai sudut yang sama, maka hapus semua titik yang mempunyai sudut yang sama kecuali titik yang terjauh dari P0. Anggaplah ukuran baru dari array sebagai m.
4. Jika m kurang dari 3, return alias convex hull tidak memungkinkan.
5. Buatlah stack kosong 'S' dan masukkan titik [0], titik [1] dan titik [2] ke stack tersebut.
6. Selesaikan titik m-3 yang tersisa tadi satu
persatu. Lakukan hal di bawah ini untuk semua titik[i]
Hapus titik
dari stack selagi orientasi dari 3 titik tidak berlawanan arah jarum jam (Atau
tidak berbelok ke arah kiri)
Pindahkan
next ke tumpukkan paling atas.
Pindah ke
tumpukkan paling atas
Masukkan
nilai titik[i] ke S
7. Tampilkan isi dari S.
Kelebihan dan Kekurangan metode:
Berdasarkan analisis program dari segi kompleksitas waktu maka didapatkan kompleksitas waktu untuk algoritma Graham adalah O(n2 ) karena terdapat proses sorting sedangkan kompleksitas waktu untuk algoritma Melkman adalah O(n).
Numerical problems
Consider the problem of solving
3x3 + 4 = 28
for the unknown quantity x.
Solusi:
|
Direct method |
|
|
3x3 + 4 = 28. |
|
|
Subtract 4 |
3x3 = 24. |
|
Divide by 3 |
x3 = 8. |
|
Take cube roots |
x = 2. |
For the iterative method, apply
the bisection method to f(x)
= 3x3 − 24. The initial values are a = 0, b =
3, f(a) = −24, f(b) = 57.
|
Iterative method |
|||
|
a |
b |
mid |
f(mid) |
|
0 |
3 |
1.5 |
−13.875 |
|
1.5 |
3 |
2.25 |
10.17... |
|
1.5 |
2.25 |
1.875 |
−4.22... |
|
1.875 |
2.25 |
2.0625 |
2.32... |
From this table it can be concluded that the solution is between 1.875 and 2.0625. The algorithm might return any number in that range with an error less than 0.2.
Kelebihan dan Kekurangan metode:
Kelebihan:
·
Setiap
siklus adalah operasi O(N2) untuk mode penyimpanan penuh.
·
Kesalahan
pembulatan hanya terjadi selama operasi O(N2) yang terjadi pada O(N3) dalam
metode langsung.
Kekurangan:
·
O(n3
) kompleksitas waktu terlalu mahal (bahkan O(n1.4) terlalu banyak untuk matriks
yang jarang kasus)
·
Kompleksitas
ruang juga dapat menjadi masalah (pengisian berlebihan)
·
Kesalahan
tumbuh secara linier dengan ukuran masalah
·
Beberapa
matriks besar mungkin secara inheren padat
0 Comments