Permasalahan
Sorting
1. Pengertian
Sorting
Ø Pengurutan data dalam struktur data sangat penting
untuk data yang bertipe data numerik ataupun karakter.
Ø Pengurutan dapat dilakukan secara ascending (urut
naik) dan descending (urut turun)
Ø Pengurutan (Sorting) adalah proses menyusun kembali
data yang sebelumnya telah disusun dengan suatu pola tertentu, sehingga dapat
tersusun secara teratur menurut aturan tertentu.
Contoh :
Ø Data Acak :
10 3 8 7 12 18 1 6
Ø Ascending :
1 3 6 7 8 10 12 18
Ø Descending : 18 12 10 8
7 6 3 1
2. Metode
Pengurutan Data Berdasarkan Perbandingan (Bubble Sort)
Metode Bubble Sort mengurutkan data dengan cara membandingkan
elemen sekarang dengan elemen berikutnya.
Bubble Sort merupakan cara pengurutan yang sederhana. Cara
kerjanya adalah dengan berulang-ulang melakukan traversal (proses looping)
terhadap elemen-elemen struktur data yang belum diurutkan. Di dalam traversal
tersebut nilai dari dua elemen struktur data dibandingkan. Jika ternyata
urutannya tidak sesuai dengan “pesanan”, maka dilakukan pertukaran (swap).
Algoritma sorting ini disebut juga dengan comparison sort dikarenakan hanya
mengandalkan perbandingan nilai elemen untuk mengoperasikan elemennya.
Contoh
:
Ø Pengurutan Ascending : Jika elemen sekarang lebih besar dari elemen
berikutnya maka kedua elemen tersebut ditukar.
Ø Pengurutan Descending : Jika elemen sekarang lebih kecil dari elemen
berikutnya, maka kedua elemen tersebut ditukar.
Ø Algoritma ini seolah-olah menggeser satu per satu
elemen dari kanan ke kiri atau kiri ke kanan, tergantung jenis pengurutannya.
Ø Ketika suatu proses telah selesai, maka bubble sort
akan mengulangi proses, demikian seterusnya dari 0 sampai dengan iterasi
sebanyak n-1.
Ø Kapan berhentinya? Bubble sort berhenti jika seluruh
array telah diperiksa dan tidak ada pertukaran lagi yang bias dilakukan, serta
tercapai perurutan yang telah diinginkan.
3. Kelebihan
dan Kekurangan Bubble Sort
I. Kelebihan
dari algoritma Bubble Sort adalah sebagai berikut :
· Algoritma yang
simpel.
· Mudah untuk diubah
menjadi kode.
· Definisi terurut
terdapat dengan jelas dalam algoritma.
· Cocok untuk
pengurutan data dengan elemen kecil telah terurut.
II. Kekurangan
dari algoritma Bubble Sort adalah sebagai berikut :
· Tidak efektif
dalam pengurutan data berskala besar.
· Langkah
pengurutan yang terlalu panjang.
· Kompleksitas
algoritma yang terlalu besar, baik dalam average case maupun worst case, yaitu
O(n2), sehingga seringkali disebut sebagai algoritma primitif, brute-force,
maupun algoritma naif
SEARCHING
1. PENGERTIAN SEARCHING
Searching juga bisa diartikan adalah
proses pencarian data dari sekumpulan data yang sudah ada. Pencarian data
sering juga disebut dengan table look-up atau store and retrieval information.
Hasil dari suatu pencarian dapat bernilai salah (tidak ketemu atau tidak
sukses) atau benar (ketemu atau sukses). Untuk data yang tidak ketemu biasanya
ada prosedur tersendiri untuk menambah atau menyisipkan data yang belum ada
tersebut.
2.
PERMASALAHAN
ada variable array yang berisi 1 2 3 4 5 6 misalkan ingin
mencari nilai 5 didalam array tersebut maka harus ?
3.
SOLUSI
maka harus memberikian
petunjuk atau nilai yang sama agar di bandingkan dengan nilai yang berisi di
dalam array. pada metode searching ada 2 teknik yang digunakan yaitu :
pencarian sekuensial (sequential search) dan pencarian biner (binary search).
1.
Pencarian sekuensial
(sequential search)
pencarian skuensial (squential search) atau sering disebut pencarian linier
menggunaka prinsip sebagai berikut :
data yang di bandingkan satu persatu secara berurutan dengan yang dicari. pada
dasarnya, pencarian ini hanya melakukan pengulangn dari 1 sampai jumlah data.
jika nilai yang di cari dan salah satu nilai yang berada di dalam sekumpulan
data sama maka di temukan. sebaliknya apabila perulangan sampai pada akhir maka
berarti tidak di temukan.
2.
Pencarian
biner (binary search)
salah satu syarat binary search dapat dilakukan adalah data sudah dalam keadaan
terurut. dengan kata lain, apabila data belum terurut, pencarian biner tidak
dapat dilakukan.
mula-mula
diambil dari posisi awal=1 dan posisi akhir =n.kemudian kita cari posisi data
tengah dengan rumus posisi tengah = posisi awal+posisi akhir) div 2, kemudian
data yang di cari dibandingkan dengan data tengah. jika sama, data ditemukan,
proses selesai. jika lebih kecil, proses dilakukan kembali tetapi posisi awal
dianggap sama dengan posisi tengah -1. jika lebih besar, proses dilakukan
kembali tetapi posisi awal dianggap sama dengan posisi tengah +1.
3. KELEBIHAN
DAN KEKURANGAN
Keunggulan
dari Pencarian berurutan :
1.
Relatif lebih cepat dan efisien untuk data yang jumlahnya terbatas.
2.
Algoritma programnya lebih sederhana.
Kelemahan
dari pencarian sekuensial :
1. Kurang cepat untuk mengerjakan data
dalam jumlah besar.
Kelebihan Pencarian Biner :
1. Untuk datang jumlah besar cenderung
lebih cepat karena data sudah terurut.
Kekurangan
Pencarian Biner :
1. Data harus sudah di sorting terlebih
dahulu agar proses pencarian lebih mudah.
2. Algoritma pemrogramannya lebih rumit
dari pencarian sekuensial, tidak baik untuk berangkai data.
STRING PROCESS
Algoritma pencarian string atau sering disebut juga pencarian
string adalah algoritma untuk melakukan semua kemunculan string pendek pattern
[0..n-1] yang disebut pattern di string yang lebih panjang teks [0...m-1] yang
disebut teks
Pemrosesan string dapat digunakan dalam Algoritma brute force
dalam pencarian string
Algoritma brute force merupakan algoritme pencarian string yang
ditulis tanpa peningkatan performa. Algoritma ini sangat jarang digunakan dalam
praktik, namun berguna dalam studi pembanding dan studi-studi lainnya.
2. PERMASALAHAN
DAN SOLUSI SERTA KELEBIHAN DAN KEKURANGAN
Pseudocode
Pseudocode algoritma brute force ini:
procedure BruteForceSearch(
input m, n :
integer,
input P :
array[0..n-1] of char,
input T :
array[0..m-1] of char,
output ketemu :
array[0..m-1] of boolean
)
Deklarasi:
i, j: integer
Algoritma:
for (i:=0 to m-n) do
j:=0
while (j <
n and T[i+j] = P[j]) do
j:=j+1
endwhile
if(j >= n)
then
ketemu[i]:=true;
endif
endfor
Graph problems
graph problems
dapat di gunakan dalam algoritma greedy. Pengertian dari Algoritma Greedy
merupakan metode yang paling populer untuk memecahkan persoalan optimasi.
Persoalan optimasi (optimization problems): persoalan yang
menuntut pencarian solusi optimum.
Persoalan
optimasi hanya ada dua macam:
1 . Maksimasi
(maximization)
2. Minimasi
(minimization)
Solusi optimum
(terbaik) adalah solusi yang bernilai minimum atau maksimum dari sekumpulan
alternatif solusi yang mungkin.
Solusi yang memenuhi semua kendala disebut solusi layak (feasible
solution). Solusi layak yang mengoptimumkan fungsi optimasi disebut solusi
optimum.
Algoritma Greedy adalah algoritma yang memecahkan masalah langkah
per langkah;
pada setiap langkah:
1. mengambil pilihan yang
terbaik yang dapat diperoleh pada saat itu tanpa memperhatikan konsekuensi ke
depan (prinsip “take what you can get
now!”)
2. berharap bahwa dengan
memilih optimum lokal pada setiap langkah akan berakhir dengan optimum global
Contoh kasus algoritma greedy :
Misalkan tersedia koin : 1, 3, 5.
Uang senilai X=8 dapat di tukar dengan cara :
1+1+1+1+1+1+1+1 = 8 (8 koin)
1+1+1+1+1+3=8 (6 koin)
1+1+1+5=8 (4 koin)
1+1+3+3=8 (4 koin)
3+5=8 (2 koin) solusi optimal.
Maka solusi optimal dari kasus penukaran koin di atas adalah 2
koin.
Algoritma yang termasuk ke dalam tipe algoritma greedy antara lain
:
·
Kode
Huffman
·
Algoritma
dijkstra
·
Algoritma
prim
·
Algoritma
kruskal
Yang ketiganya
digunakan dalam menyelesaikan permasalahan optimasi pada graf .
Algoritma greedy dalam menyelesaikan masalah dengan langkah per
langkah “ secara bertahap “ .
Dengan definisi , pada setiap langkah algoritma greedy :
1. Mengambil pilihan
yang terbaik
Yaitu dapat diperoleh pada
saat itu tanpa memperhatikan
konsekuensi kedepan ( prinsip “ take what you can get now )
2. Berharap bahwa
dengan memilih optimum
Local pada setiap langkah akan berakhir dengan optimum global .
Algoritma kruskal
Algoritma Kruskal adalah algoritma untuk mencari pohon merentang
minimum secara langsung didasarkan pada algoritma kruskal sisi-sisi di dalam
graf diurut terlebih dahulu berdasarkan bobotnya dari kecil ke besar. Sisi yang
dimasukkan ke dalam himpunan T adalah sisi graf G sedemikian sehingga T adalah
pohon. Pada keadaan awal, sisi-sisi sudah diurut berdasarkan bobot membentuk
hutan (forest). Hutan tersebut dinamakan hutan merentang (spanning forest).
Sisi dari graf G ditambahkan ke T jika tidak membentuk sirkuit di T.
Perbedaan prinsip antara algoritma Prim dan Kruskal adalah jika
pada algoritma Prim sisi yang dimasukkan ke dalam T harus bersisian dengan
sebuah simpul di T, maka pada algoritma Kruskal sisi yang dipilih tidak perlu
bersisian dengan simpul di T asalkan penambahan sisi tersebut tidak membentuk
sirkuit.
Langkah-langkah dalam algoritma Kruskal adalah sebagai berikut:
1. Lakukan pengurutan
terhadap setiap sisi di graf mulai dari sisi dengan bobot terkecil sampai
terbesar.
2. Pilih sisi yang
mempunyai bobot minimum yang tidak membentuk sirkuit di pohon. Tambahkan sisi
tersebut ke dalam pohon.
3. Ulangi langkah 2 sampai
pohon merentang minimum terbentuk, yaitu ketika sisi di dalam pohon merentang
minimum berjumlah n-1 (n adalah jumlah simpul di graf).
Untuk lebih memahami perbedaan algoritma Prim dan algoritma
Kruskal yang keduanya merupakan algoritma untuk pohon merentang minimum.
GRAFH PROBLEM
1. PENGERTIAN
Graph Problem
Graph adalah sekelompok simpul-simpul
(nodes/vertices) V, dan sekelompok sisi (edges) E yang menghubungkan sepasang
simpul, atau bias juga sebagai himpunan benda-benda yang disebut verteks (node)
yang terhubung oleh sisi (atau edge atau arc). biasanya graf digambarkan
sebagai kumpulan titik-titik (melambangkan verteks) yang dihubungkan oleh
garis-garis (melambangkan sisi).
ISTILAH
Ada beberapa istilah yang biasa digunakan pada suatu graph :
1.
Vertex (simpul / node)
Sebuah graph dibentuk dari kumpulan titik yang dihubungkan
dengan garis – garis. Titik titik tersebut disebut vertex.
2.
Edge (busur)
Merupakan garis penghubung antara dua vertex.
3.
Adjacent (bertetangga)
Pada graph tak berarah (indirected graph) dua buah vertex /
vertex disebut adjacent jika ada edge yang menghubungkan dua buah vertex.
Sedangkan pada graph berarah (directed graph) sebuah vertex a disebut adjacent
dengan vertex b jika ada vertex dari b ke a.
4.
Weight
Apabila setiap edge mempunyai sebuah nilai (dapat berupa jarak,
waktu atau biaya) yang menyatakan hubungan antara kedua buah vertex maka edge
tersebut dikatakan memiliki bobot. Graph yang memiliki bobot dapat disebut
sebagai graph berbobot atau weighted graph.
5.
Path (lintasan)
Path adalah serangkaian vertex yang berbeda yang adjacent secara
berturut turut dari vertex satu ke vertex berikutnya.
6.
Direct (arah)
Merupakan arah suatu graph. Pada graph berarah (directed graph
atau digraph) urutan vertex memiliki arti.
2. PERMASALAHAN DAN
SOLUSI SERTA KELEBIHAN DAN KEKURANGAN
1.
Graf tak berarah (undirected graph)
Graf yang sisinya tidak mempunyai orientasi arah disebut graf
tak berarah. Pada graf
tak-berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak
diperhatikan. salah satu contoh graf
tak berarah dimana sisi-sisi yang menghubungkan antar simpul dalam graf
tersebut tidak memiliki orientasi arah.
2.
Graf Berarah (directed graph)
Graf yang setiap sisinya memiliki orientasi arah disebut sebagai
graf berarah. Sisi berarah dalam graf ini dapat dinamakan sebagai busur (arc).
Lain halnya dengan graf tak-berarah, urutan pasangan simpul disini sangat
diperhatikan karena dapat menyatakan hal yang berbeda. contoh dari graf berarah yang
memiliki sisi-sisi dengan orientasi arah (busur).
Digraph & Undigraph
Graph Berarah (directed graph atau digraph): jika sisi-sisi pada
graph, misalnya {x, y} hanya berlaku pada arah-arah tertentu
saja, yaitu dari x ke y tapi tidak dari y ke x;
verteks x disebut origin dan vertex y disebut
terminus dari sisi tersebut. Secara grafis maka penggambaran arah sisi-sisi
digraph dinyatakan dengan anak panah yang mengarah ke verteks terminus, secara
notasional sisi graph berarah ditulis sebagai vektor dengan (x, y).
Graph Tak Berarah (undirected graph atau undigraph): setiap sisi
{x, y} berlaku pada kedua arah: baik x ke y maupun y ke x.
Secara grafis sisi pada undigraph tidak memiliki mata panah dan secara
notasional menggunakan kurung kurawal.
Dalam masalah-masalah graph undigraph bisa dipandang sebagai
suatu digraph dengan mengganti setiap sisi tak berarahnya dengan dua sisi untuk
masing-masing arah yang berlawanan.
Selain itu, berdasarkan definisi ini maka struktur data linear
maupun hirarkis adalah juga graph. Node-node pada struktur linear atupun
hirarkis adalah verteks-verteks dalam pengertian graph dengan sisi-sisinya
menyusun node-node tersebut secara linear atau hirarkis. Sementara kita telah
ketahui bahwa struktur data linear adalah juga tree dengan pencabangan pada
setiap node hanya satu atau tidak ada. Linear 1-way linked list adalah digraph,
linear 2-way linked list bisa disebut undigraph.
Aspek Algoritmis
Walau secara konseptual struktur linear adalah subset dari tree
dan demikian pula tree adalah subset dari graph, dalam aplikasinya perlu
dibedakan cara penanganan struktur-struktur tersebut untuk mencapai efisiensi
algoritmis. Algoritma-algoritma untuk graph secara umum terlalu mahal apabila
digunakan pada struktur hirarkis (tree), apalagi pada struktur linear. Jadi
apabila masalah yang dihadapi pada dasarnya hanya merupakan masalah dengan
struktur data hirarkis saja maka cukup lah kita menggunakan representasi dan
algoritma-algoritma tree.
Konektivitas pada Undigraph
·
Adjacency: Dua
verteks x dan y yang berlainan disebut
berhubungan langsung (adjacent) jika terdapat sisi {x, y}
dalam E.
·
Path: Sederetan
verteks yang mana setiap verteks adjacent dengan verteks yang tepat berada
disebelahnya.
·
Panjang dari path:
jumlah sisi yang dilalui path.
·
Siklus: suatu path dengan
panjang lebih dari satu yang dimulai dan berakhir pada suatu verteks yang sama.
·
Siklus sederhana:
dalan undigraph, siklus yang terbentuk pada tiga atau lebih verteks-verteks
yang berlainan yang mana tidak ada verteks yang dikunjungi lebih dari satu kali
kecuali verteks awal/akhir.
·
Dua verteks x dan y yang
berbeda dalam suatu undigraph disebut berkoneksi (connected) apabila jika
terdapat path yang menghubungkannya.
·
Himpunan bagian
verteks S disebut terkoneksi (connected) apabila dari setiap verteks x dalam
S terdapat path ke setiap verteks y (y bukan x)
dalam S.
·
Suatu komponen
terkoneksi (connected components) adalah subgraph (bagian dari graph) yang
berisikan satu himpunan bagian verteks yang berkoneksi.
·
Suatu undigraph dapat
terbagi atas beberapa komponen yang terkoneksi; jika terdapat lebih dari satu
komponen terkoneksi maka tidak terdapat path dari suatu verteks dalam satu
komponen verteks di komponen lainnya.
·
Pohon bebas (free
tree): suatu undigraph yang hanya terdapat satu komponen terkoneksi serta tidak
memiliki siklus sederhana.
Konektivitas pada Digraph
Terminologi di atas berlaku juga pada Digraph kecuali dalam
digraph harus dikaitkan dengan arah tertentu karena pada arah yang sebaliknya
belum tentu terdefinisi.
·
Adjacency ke / dari:
Jika terdapat sisi (x,y) maka dalam digraph dikatakan bahwa x “adjacent
ke” y atau y “adjacent dari” x.
Demikian pula jika terdapat path dari x ke y maka
belum tentu ada path dari y ke x Jadi dalam
digraph keterkoneksian didefinisikan lebih lanjut lagi sebagai berikut.
·
Terkoneksi dengan
kuat: Himpunan bagian verteks S dikatakan terkoneksi dengan kuat (strongly
connected) bila setiap pasangan verteks berbeda x dan y dalam
S, x berkoneksi dengan y dan y berkoneksi
dengan x (dpl., ada path dari x ke y dan
sebaliknya dari y ke x).
·
Terkoneksi dengan
Lemah: Himpunan bagian verteks S dikatakan terkoneksi dengan lemah (weakly
connected) bila setiap pasangan verteks berbeda x dan y dalam
S, salah satu: x berkoneksi dengan y (atau y berkoneksi
dengan x) dan tidak kebalikan arahnya (dpl., hanya terdefinisi satu
path: dari x ke y atau sebaliknya dari y ke x).
Himpunan Keterhubungan Langsung
Cara pendefinisian lain untuk graph adalah dengan menggunakan
himpunan keterhubungan langsung Vx. Pada setiap verteks x terdefinisi Vx sebagai
himpunan dari verteks-verteks yang adjacent dari x. Secara formal:
Vx = {y |
(x,y) Î E}
Dalam digraph didefinisikan juga terminologi-terminologi berikut
ini. Predesesor dari suatu verteks x (ditulis Pred(x)) adalah
himpunan semua verteks yang adjacent ke x. Suksesor dari
verteks x (ditulis Succ(x)) adalah himpunan semua verteks yang
adjacent dari x; yaitu adjacency set di atas.
Degree
·
Degree dari suatu
verteks x dalam undigraph adalah jumlah sisi di mana di salah
satu ujungnya terdapat x.
·
Indegree dari suatu
verteks x dalam digraph adalah jumlah dari predesesor x.
·
Outdegree dari suatu
verteks x dalam digraph adalah jumlah dari suksesor x.
Graph berbobot (weighted graph)
Apabila sisi-sisi pada graph disertai juga dengan suatu (atau beberapa)
harga yang menyatakan secara unik kondisi keterhubungan tersebut maka graph
tersebut disebut graph berbobot. Biasanya dalam masalah-masalah graph bobot
tersebut merupakan “biaya” dari keterhubungan ybs. Pengertian “biaya” ini
menggeneralisasikan banyak aspek: biaya ekonomis dari proses/aktifitas, jarak
geografis/tempuh, waktu tempuh, tingkat kesulitan, dan lain sebagainya. Dalam
beberapa masalah lain bisa juga bobot tersebut memiliki pengertian “laba” yang
berarti kebalikan dari “biaya” di atas. Dalam pembahasan algoritma-algoritma
graph nanti pengertian bobot akan menggunakan pengertian biaya sehingga apabila
diaplikasikan pada masalah yang berpengertian laba maka kuantitas-kuantitas
terkait adalah kebalikannnya. Misalnya mencari jarak tempuh minimum digantikan
dengan mencari laba maksimum.
COMBINATIORAL PROBLEM
1. PENGERTIAN
Combinatorial adalah salah satu cabang dari matematika dalam
bidang ilmu matetmatika diskrit yang bertujuan untuk menghitung jumlah
penyusunan objek-objek tanpa mengenumerasi kemungkinan susunannya.
jadi dapat disimpulkan, Combinatorial problem merupakan suatu
permasalahan matematis untuk menyusun, mengelompokkan, mengurutkan, atau
memilih sejumlah objek diskrit tertentu. Dan sampai saat ini,
combinatorial problem masih menjadi salah satu masalah yang paling sulit dalam
komputasi baik itu dari teori maupun prakteknya. Maka dari itu Combinatorial
menjadi salah satu bidang yang sering diteliti karena dengan semakin berkembangnya
ilmu pengetahuan diharapkan akan ditemukan metode-metode maupun
pendekatan-pendekatan baru yang bisa menjadi sebuah cara penyelesaian terbaik
untuk permasalahan ini.
Kesulitan dari combinatorial problem antara lain :
1.
Sejumlah objek
combinatoric tertentu berkembang seiring dengan meningkatnya ukuran masalah.
2.
Tidak diketahui
algoritma pasti yang dapat digunakan untuk menyelesaikan permasalahan
combinatorial problem
2. PERMASALAHAN DAN SOLUSI SERTA KELEBIHAN DAN KEKURANGAN
Masalah
: Menemukan suatu objek combinatoric seperti permutasi, kombinasi atau
subset yang memenuhi batasan tertentu dan memiliki properti yang diinginkan.
Problem
yang sulit :
·
Sejumlah objek
combinatorikctertentu tumbuh dengan cepat seiring peningkatan ukuran
masalah.
·
Tidak diketahui
algoritma eksak untuk menyelesaikan masalah tersebut.
beberapa permasalahan combinatorial problem dapat diselesaikan
menggunakan algoritma yang efisien, akan tetapi tetap harus mengikuti
aturan-aturannya. Berikut ini adalah beberapa contoh kasus dari combinatorial
problem :
1.
Vehicle Routing
Problem (VRP), merupakan sebuah cakupan masalah yang didalamnya terdapat sebuah
problem dimana ada sejumlah rute untuk sejumlah kendaraan yang berada pada satu
blok atau lebih yang harus ditentukan jumlahnya supaya tersebar secara
geografis sehingga dapat melayani konsumen-konsumen yang tersebar. VRP memiliki
tujuan yaitu mengantarkan barang pada konsumen dengan biaya minimum melalui
rute-rute kendaraan yang keluar-masuk blok. VRP merupakan sebuah pemrograman
integer yang termasuk dalam kategori NP-hard problem, yang berarti usaha
komputasi yang digunakan akan semakin sulit seiring meningkatnya ruang
lingkup masalah. Untuk Masalah-masalah seperti ini, biasanya dicari adalah
aproksimasi solusi masalah yang terdekat, karena solusi tersebut dapat dicari
dengan cepat dan akurat. Biasanya masalah seperti ini dapat terselesaikan
dengan melakukan pengamatan pada ruang lingkup masalah.
2.
Travelling Salesman
Problem (TSP), Merupakan masalah kombinasi optimasi dalam menemukan tour yang
terpendek. TSP adalah problem untuk menentukan urutan kota yang harus dilalui
salesman, setiap kota hanya boleh dilalui satu kali dalam setiap perjalanannya,
dimana jarak antara kota satu dengan kota yang lainnya sudah diketahui.
Salesman tersebut harus meminimalisir biaya dan dan jarak yang harus di tempuh
dalam perjalanan tersebut.
GEOMETRIC PROBLEM
1. PENGERTIAN
Geometric Problem itu
adalah algoritma yang menyelesaikan permasalahan algoritma tentang geometri.
Berhubungan dengan titik, garis, poligon, dan lainnya.
2. PERMASALAHAN DAN SOLUSI SERTA KELEBIHAN DAN
KEKURANGAN
Masalah
klasik dalam Geometric Problem :
1. Problem Closest Pair:
diberikan titik pada sebuah bidang dan menemukan pasangan terdekatnya.
2. Convex Hull: menemukan
poligon cembung terkecil yang melibatkan semua titik yang telah ditentukan.
Problem Closest Pair adalah suatu algoritma yang memecahkan
persoalan untuk mencari jarak terdekat antara kumpulan titik dalam suatu bidang
dua dimensi. Cara yang paling sederhana untuk menyelesaikan masalah ini dengan
cara membandingkan semua kemungkinan titik-titiknya untuk dicari jarak nya.
Algoritma akan mencoba semua kemungkinan titik titiknya hingga mendapatkan
nilai akhir yang paling kecil.
Convex Hull adalah sebuah permasalahan yang digambarkan secara sederhana
dalam ruang dua dimensi sebagai mencari subset dari himpunan sebuah titk-titik
pada bidang dua dimensi tersebut sehingga jika titik-titik tersebut dijadikan
poligon maka akan membentuk sebuah poligon konveks. Atau dapat diartikan dengan
poligon yang disusun dari subset titik, sehingga tidak ada titik dari himpunan
awal yang berada di luar poligon tersebut.
Untuk
menyelesaikan persoalan ini adalah persamaan garis pada sebuah
bidang. Persamaan garis pada bidang memisahkan bidang menjadi dua bagian. Yang
pertama area di sebelah kanan bidang (relatif terhadap orientasi
garis). Contohnya adalah garis yang berorientasi yaitu sumbu
koordinat. Misalnya garis yang dibentuk oleh titik-titik poligon jika memiliki
orientasi yang sama, maka setiap titik akan berada di sebelah kanan seluruh
garis tersebut.
Definisi
di atas dapat diartikan untuk menentukan aksi awal, yaitu memilih
titik yang berada paling luar pertama. Mencari titik yang memiliki nilai
komponen koordinat (horizontal atau vertikal) yang ekstrim (minimum atau
maksimum). Titik-titik convex hull lainnya ditentukan berdasarkan titik pertama
tadi.
Numerical Problems
1. PENGERTIAN
Numerical Problems adalah teknik pengoperasian masalah
matematika yang beragam, kemudian dapat terpecahkan dengan menggunakan operasi
hitung(arithmetic). metode numeric ialah sebuah teknik yang dapat menyelesaikan
rumus masalah matematika seperti operasi tambah, kurang, kali dan bagi. terbagi
banyak jenis metode numeric, namun ada perbedaan dari masing-masing metode yang
memiliki karakteristik beragam, dengan kemampuan untuk mengoperasikan hitung
matematika hingga terpecahkan dengan metode hitung arithmetic(tambah, kurang,
kali dan bagi).
2. PERMASALAHAN
NUMERICAL PROBLEMS :
Pada umumnya masalah dalam sains dan teknologi memiliki gambaran
dalam persamaan matematika. Persamaan ini sulit dipecahkan dengan bentuk
analitik hingga memerlukan penyelesaian pendekatan numeric. kemudian dengan
metode numeric, dapat memungkinkan kita terbebas dari perhitungan manual yang
memusingkan. sehingga kita bisa lebih focus pada penekanan formulasi problem
dan tidak terjebak dalam rutinitas hitung menghitung. para pengguna metode numeric
ini diharapkan bisa mengatasi berbagai kelemahan-kelemahan dari metode yang ada
sebelumnya.
Metode numeric digunakan untuk memecahkan persoalan pada saat
perhitungan secara analitik tidak dapat digunakan. metode numeric juga dibentuk
menggunakan algoritma-algoritma yang dapat dihitung secara cepat dan mudah.
3. SOLUSI NUMERIC
PROBLEMS :
Solusi Persamaan Non-Linier.
Solusi Persamaan Linier Simultan.
Interpolasi.
Integrasi Numerik.
4. KELEBIHAN NUMERIC
PROBLEMS :
Metode numeric merupakan sebuah teknik yang dapat memecahkan
masalah matematika yang efektif dan efisien. dengan bantuan komputer dapat
menangani masalah yang rumit dan melibatkan perhitungan yang luas.
Apabila masalah yang dihadapi sulit dipecahkan dengan bantuan
program paket komputer, maka pemecah masalah dapat menggunakan program
komputer(misalnya basic, pascal, atau program komputer lainnya).
saat ini terdapat berbagai paket program komputer(misalnya exel,
maple, matlab, atau program paket lainya) yang tersedia atau diperdagangkan
sehingga mudah didapat dalam pengoperasian yang mencakup metode numeric.
metode numeric juga merupakan sarana yang efisien untuk mengenal
karakteristik komputer.
5. KEKURANGAN NUMERIC
PROBLEMS :
Metode Analitik, solusi ini sangat berguna namun terbatas pada
masalah sederhana. sedangkan masalah real yang komplek dan non linier tidak
dapat diselesaikan.
Metode grafik, metode ini digunakan sebagai pendekatan
penuyelesaian yang kompleks. kendalanya bahwa metode ini tidak akurat, sangat
lama, dan banyak membutuhkan waktu.
Kalkulator dan slide rules, penyelesaian numeric secara manual.
cara ini cukup lama dan mungkin bisa terjadi kesalahan pemasukan data.
Sumber :
https://catatananalgo.wordpress.com/2016/10/03/algoritma-combinatorial-problem/
https://catatananalgo.wordpress.com/2016/10/03/algoritma-graph-problem/
http://analgo11.blogspot.com/2016/10/pengertian-string-processing-grap.html
http://squadronfreak.blogspot.com/2016/10/searching.html
https://sitianisa9911.blogspot.com/2021/10/permasalahan-dalam-algoritma.html
https://geymavancha.blogspot.com/2021/10/belajar-dan-mempelajari-permasalahan.html
https://novaistiqomahh.blogspot.com/2021/10/geometric-problems.html
Comme