IMPLEMENTASI ALGORITMA BRANCH AND BOUND

 Algoritma B&B (Branch and Bound) adalah salah satu algoritma yang digunakan untuk pencarian jalur. Contoh yang dibahas kali ini adalah mengenai pencarian jalur yang melalui semua titik dengan biaya terendah.

Algoritma ini memiliki 2 prinsip, yaitu:

Algoritma ini akan melakukan perhitungan secara rekursif, akan memecah masalah kedalam masalah-masalah kecil, sambil tetap menghitung nilai terendah / terbaik. Proses ini dinamakan branching

Jika branching diterapkan secara sendirian, maka hasilnya akan tetap mencari setiap kemungkinan yang ada. Untuk meningkatkan performa, algoritma ini akan melakukan pencatatan biaya minimum sebagai bound dalam setiap perhitungan, sehingga untuk calon hasil jawaban yang diperkirakan akan melebihi bound akan dibuang karena tidak mungkin akan mencapai nilai terbaik

Diasumsikan ada 5 titik yang harus dilalui semuanya, yaitu A,B,C,D,E

semua titik tidak terhubung secara langsung dengan titik-titik lainnya, melainkan hanya melalui jalur tertentu saja

setiap jalur juga memiliki biaya sendiri-sendiri

maka tentukan jalur yang harus diambil untuk mengelilingi semua titik yang ada

Diasumsikan data jalur yang tersedia adalah sebagai berikut

Titik awal

Titik Tujuan

Biaya

Titik A

Titik B

10

Titik A

Titik E

11

Titik B

Titik A

12

Titik B

Titik C

20

Titik B

Titik D

6

Titik B

Titik E

9

Titik C

Titik B

15

Titik C

Titik D

14

Titik D

Titik B

7

Titik D

Titik C

5

Titik E

Titik C

8

Titik E

Titik D

13

Jika diilustrasikan dalam gambar, maka model data awal adalah sebagai berikut

Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:

* Tentukan jumlah titik yang harus dihubungkan

Diasumsikan dalam kasus ini, jumlah titik ada 5 buah

Const jumlahTitik As Integer = 5

Langkah-langkah penggunaan algoritma ini adalah

1. Lakukan inisialisasi daftar jalur sesuai dengan data yang tersedia

Terdapat matriks berukuran [jumlah titik x jumlah titik] untuk menyimpan jalur dari masing-masing titik

Jika tidak ada jalur diantara 2 titik, maka nilai jalurnya adalah 0

Dim daftarBiaya(,) As Double = New Double(jumlahTitik - 1, jumlahTitik - 1) { _

{0, 10, 0, 0, 11}, _

{12, 0, 20, 6, 9}, _

{0, 15, 0, 14, 0}, _

{0, 7, 5, 0, 0}, _

{0, 0, 8, 13, 0} _

}

2. Hitung rata-rata biaya pada semua data

Nilai ini nantinya akan digunakan untuk perkiraan nilai biaya apakah akan melebihi bound atau tidak

Dim rata2 As Integer = 0

Dim count As Integer = 0

For i As Integer = 0 To jumlahTitik - 1

For j As Integer = 0 To jumlahTitik - 1

If daftarBiaya(i, j) <> 0 Then

rata2 += daftarBiaya(i, j)

count += 1

End If

Next

Next

rata2 /= count

3. Lakukan perhitungan pencarian jalur melalui semua titik yang ada

Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 3a)

CariJalurTerbaik(jumlahTitik, rata2, daftarBiaya, jalurTerbaik, BiayaTerbaik)

Memasuki perhitungan pada fungsi CariJalurTerbaik

3a. Lakukan perhitungan pada masing-masing titik (poin 3a1 – 3a3)

For i As Integer = 0 To jumlahTitik - 1

. . .

3a1. Beri nilai awal calon jalur dengan nilai -1

For j As Integer = 0 To jumlahTitik - 1

calonJalur(j) = -1

Next

3a2. Lakukan perhitungan pada masing-masing titik selain titik awal (poin 3a2a – 3a2c)

For j As Integer = 0 To jumlahTitik - 1

If daftarBiaya(i, j) <> 0 Then

. . .

3a2a. Masukkan titik awal pada calon jalur yang sedang dihitung

calonJalur(0) = i

3a2b. Inisialisasi titik titik yang sudah dihitung dengan nilai false,

kemudian tandai titik awal dengan nilai True agar tidak dapat digunakan dalam perhitungan selanjutnya

Dim titikTerpilih(jumlahTitik - 1) As Boolean

titikTerpilih(i) = True

3a2c. Lakukan pencarian jalur dimulai dari titik awal yang terpilih

Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan dibawah ini

CariJalur(jumlahTitik, rata2, daftarBiaya, jalur, biaya, titikTerpilih, calonJalur, totalCalonJalur, 1)

Memasuki Perhitungan pada fungsi CariJalur

3a2c1. Jika semua titik sudah terpilih, maka bandingkan total biaya jalur ini dengan total biaya terbaik

Jika total biaya jalur ini kurang dari total biaya terbaik, maka ambil total jalur ini sebagai jalur terbaik

If jumlahTitikTerpilih >= jumlahTitik Then

If totalCalonJalur < biayaTerbaik Then

biayaTerbaik = totalCalonJalur

Array.Copy(calonJalur, jalurTerbaik, jumlahTitik)

End If

. . .

3a2c2. Lakukan perhitungan dibawah ini apabila kondisi diatas tidak terpenuhi (poin 3a2c2a – 3a2c2c)

Else

. . .

3a2c2a. Lakukan pengecekan terhadap sisa titik yang akan dihitung

Apabila perkiraan sisa titik akan melebihi bound biaya terbaik, maka hentikan perhitungan

Dim sisaTitik As Integer = jumlahTitik - jumlahTitikTerpilih

If totalCalonJalur + rata2 * sisaTitik >= biayaTerbaik Then

Return

End If

3a2c2b. Dapatkan indeks titik yang terakhir kali dihitung untuk digunakan sebagai titik awal pada perhitungan berikutnya

Dim idxTitikTerakhir As Integer = calonJalur(jumlahTitikTerpilih - 1)

3a2c2c. Lakukan perhitungan pada masing-masing titik untuk titik-titik yang belum terpilih dan memiliki jarak dengan titik terakhir (poin 3a2c2c1 – 3a2c2c3)

For i As Integer = 0 To jumlahTitik - 1

If titikTerpilih(i) = False AndAlso daftarBiaya(idxTitikTerakhir, i) <> 0 Then

. . .

3a2c2c1. Masukkan titik ini sebagai titik berikutnya pada calon jalur yang sedang dihitung

dan tandai titik ini sebagai titik yang sudah terpilih

calonJalur(jumlahTitikTerpilih) = i

titikTerpilih(i) = True

3a2c2c2. Lakukan proses percabangan / branch,

yaitu Ulangi fungsi ini menggunakan titik yang baru sebagai titik awal

CariJalur(jumlahTitik, rata2, daftarBiaya, jalurTerbaik, biayaTerbaik, titikTerpilih, _

  calonJalur, totalCalonJalur + daftarBiaya(idxTitikTerakhir, i), jumlahTitikTerpilih + 1)

3a2c2c3. Setelah semua kemungkinan cabang pada titik tersebut sudah dihitung,

maka keluarkan titik ini dari calon jalur yang sedang dihitung

dan tandai titik ini sebagai titik yang belum terpilih

calonJalur(jumlahTitikTerpilih) = -1

titikTerpilih(i) = False

3a3. Jika biaya jalur yang baru ditemukan lebih baik dari biaya jalur terbaik,

maka ambil jalur tersebut sebagai jalur terbaik

If biaya < biayaTerbaik Then

biayaTerbaik = biaya

Array.Copy(jalur, jalurTerbaik, jumlahTitik)

End If

Hasil akhir adalah: (klik untuk perbesar gambar)

Jika diilustrasikan dalam gambar, maka model hasil akhirnya adalah sebagai berikut

IMPLEMENTASI ALGORITMA DIVIDE and CONQUER PADA SORTING dan SEARCHING

Nama : Silvia Ranti

NPM ; 20312073

Kelas : IF 20B

Algoritma Divide and Conquer

    Divide and Conquer (D&C) adalah algoritma pemrograman yang melakukan pemecahan masalah menjadi dua sub-masalah secara rekursif sampai setiap sub-masalah cukup sedarhana untuk diselesaikan secara lansung. Tiap solusi dari masing-masing sub-masalah akan digabungkan untuk mendapatkan solusi dari masalah utama tersebut. Algoritma D&C menjadi basis dari algoritma-algoritma efisien untuk masalah-masalah seperti sorting dan searching. 
 
    Algoritma Divide and Conquer secara natural diimplementasikan secara rekursif sebagai pemanggilan prosedur dalam dirinya sendiri. Sub-masalah akan dikerjakan dalam procedur-call stack. Setiap Sub-masalah yang merupakan hasil pembagian dari masalah utama biasanya dibagi tanpa menimbulkan overlapping sehingga tidak ada pengerjaan redundan. Semuanya akan dimasukkan kedalam stack dan dikerjakan mulai dari sub-masalah terkecil.

 

Implementasi Algoritma Divide and Conquer pada Sorting dan Searching

A. Sorting 
1. Insertion Sort
  Salah satu algoritma sorting yang paling sederhana adalah insertion sort. Ide dari algoritma ini dapat dianalogikan seperti mengurutkan kartu. Penjelasan berikut ini menerangkan bagaimana algoritma insertion sort bekerja dalam pengurutan kartu. Anggaplah anda ingin mengurutkan satu set kartu dari kartu yang bernilai paling kecil hingga yang paling besar. Seluruh kartu diletakkan pada meja, sebutlah meja ini sebagai meja pertama, disusun dari kiri ke kanan dan atas ke bawah. Kemudian kita mempunyai meja yang lain, meja kedua, dimana kartu yang diurutkan akan diletakkan. Ambil kartu pertama yang terletak pada pojok kiri atas meja pertama dan letakkan pada meja kedua. Ambil kartu kedua dari meja pertama, bandingkan dengan kartu yang berada pada meja kedua, kemudian letakkan pada urutan yang sesuai setelah perbandingan. Proses tersebut akan berlangsung hingga seluruh kartu pada meja pertama telah diletakkan berurutan pada meja kedua. Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan (meja pertama) dan yang sudah diurutkan (meja kedua). Elemen pertama diambil dari bagian array yang belum diurutkan dan kemudian diletakkan sesuai posisinya pada bagian lain dari array yang telah diurutkan. Langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian array yang belum diurutkan.

Algoritmanya :

void insertionSort(Object array[], int startIdx, int endIdx) 
{
   for (int i = startIdx; i < endIdx; i++) {
   int k = i;
   if(((Comparable) array[k]).compareTo(array[j])>0) {
   for (int j = i + 1; j < endIdx; j++) {
   k = j;
   }
   }
   swap(array[i],array[k]);
   }
}

 2. Selection Sort 

 

    Jika anda diminta untuk membuat algoritma sorting tersendiri, anda mungkin akan menemukan sebuah algoritma yang mirip dengan selection sort. Layaknya insertion sort, algoritma ini sangat rapat dan mudah untuk diimplementasikan. Mari kita kembali menelusuri bagaimana algoritma ini berfungsi terhadap satu paket kartu. Asumsikan bahwa kartu tersebut akan diurutkan secara ascending. Pada awalnya, kartu tersebut akan disusun secara linier pada sebuah meja dari kiri ke kanan, dan dari atas ke bawah. Pilih nilai kartu yang paling rendah, kemudian tukarkan posisi kartu ini dengan kartu yang terletak pada pojok kiri atas meja. Lalu cari kartu dengan nilai paling rendah diantara sisa kartu yang tersedia. Tukarkan kartu yang baru saja terpilih dengan kartu pada posisi kedua. Ulangi langkah – langkah tersebut hingga posisi kedua sebelum posisi terakhir dibandingkan dan dapat digeser dengan kartu yang bernilai lebih rendah.

Ide utama dari algoritma selection sort adalah memilih elemen dengan nilai paling rendah dan menukar elemen yang terpilih dengan elemen ke-i. Nilai dari i dimulai dari 1 ke n, dimana n adalah jumlah total elemen dikurangi 1.

Algoritmanya :

void selectionSort(Object array[], int startIdx, int endIdx) 
{
    int min;
     for (int i = startIdx; i < endIdx; i++) {
     if (((Comparable)array[min]).compareTo(array[j])>0) {
     min = i;
     for (int j = i + 1; j < endIdx; j++) {
      min = j;
}
      }
      }
       swap(array[min], array[i]);
      }

 

3. Quick Sort

 

    Quicksort ditemukan oleh C.A.R Hoare. Seperti pada merge sort, algoritma ini juga berdasar pada pola divide-and-conquer. Berbeda dengan merge sort, algoritma ini hanya mengikuti langkah – langkah sebagai berikut :

1. Divide

Memilah rangkaian data menjadi dua sub-rangkaian A[p…q-1] dan A[q+1…r] dimana setiap elemen A[p…q-1] adalah kurang dari atau sama dengan A[q] dan setiap elemen pada A[q+1…r] adalah lebih besar atau sama dengan elemen pada A[q]. A[q] disebut sebagai elemen pivot. Perhitungan pada elemen q merupakan salah satu bagian dari prosedur pemisahan

2. Conquer

Mengurutkan elemen pada sub-rangkaian secara rekursif

Pada algoritma quicksort, langkah “kombinasi” tidak di lakukan karena telah terjadi pengurutan elemen – elemen pada sub-array

Algoritmanya :

void quickSort(Object array[], int leftIdx, int rightIdx) {

int pivotIdx;

/* Kondisi Terminasi */

pivotIdx = partition(array, leftIdx, rightIdx);
if (rightIdx > leftIdx) {


quickSort(array, leftIdx, pivotIdx-1);
}

quickSort(array, pivotIdx+1, rightIdx);

}

4. Merge Sort

    Beberapa algoritma mengimplementasikan konsep rekursi untuk menyelesaikan permasalahan. Permasalahan utama kemudian dipecah menjadi sub-masalah, kemudian solusi dari sub-masalah akan membimbing menuju solusi permasalahan utama.

Pada setiap tingkatan rekursi, pola tersebut terdiri atas 3 langkah.

1. Divide

    Memilah masalah menjadi sub masalah

2. Conquer

    Selesaikan sub masalah tersebut secara rekursif. Jika sub-masalah tersebut cukup ringkas dan sederhana, pendekatan penyelesaian secara langsung akan lebih efektif

3. Kombinasi

    Mengkombinasikan solusi dari sub-masalah, yang akan membimbing menuju penyelesaian atas permasalahan utama

Seperti yang telah dijelaskan sebelumnya, Merge sort menggunakan pola divide and conquer. Dengan hal ini deskripsi dari algoritma dirumuskan dalam 3 langkahberpola divide-and-conquer. Berikut menjelaskan langkah kerja dari Merge sort.

1. Divide

    Memilah elemen – elemen dari rangkaian data menjadi dua bagian.

2. Conquer

    Conquer setiap bagian dengan memanggil prosedur merge sort secara rekursif

3. Kombinasi

    Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutan

Algoritmanya:

void mergeSort(Object array[], int startIdx, int endIdx) 
{

if (array.length != 1) {

mergeSort(leftArr, startIdx, midIdx);
//Membagi rangkaian data, rightArr dan leftArr


}
mergeSort(rightArr, midIdx+1, endIdx);

combine(leftArr, rightArr);

}

5. Counting Sort

    Adalah sebuah algoritma sorting linear yang digunakan untuk mengurutkan ‘item’ ketika urutannya telah ditentukan dan memiliki panjang yang terbatas. Bilangan interval yang telah tetap, katakana k1 ke k2 adalah contoh dari ‘item’ tersebut. Counting sort sebenarnya merupakan metode pengurutan yang memanfaatkan index variabel array. Hanya effektif pada data yang nilainya kecil.

Algoritma ini diproses dengan mendefinisikan sebuah hubungan urutan antara ‘item’ yang akan disorting. Katakana ‘item’ yang akan disorting adalah variable A. Maka, terdapat sebuah array tambahan dengan ukuran yang serupa dengan array A. katakana array tersebut adalah array B. untuk setiap element di A, sebut e, algoritma ini menyimpan jumlah ‘item’ di A lebih kecil dari atau sama dengan e di B(e). jika hasil sorting yang terakhir disimpan di array C, maka untuk masing-masing e di A, dibuat dalam arah yang sebaliknya, yaitu C[B(e)]=e. setelah step di atas, niali dari B(e) berkurang dengan 1.

Algoritma ini membuat 2 passover A dan passover B. Jika ukuran dari range k lebih kecil dari ukuran input n, maka time complexity = O(n). perhatikan juga bahwa algoritma ini stabil yang berarti bahwa sambungan diselesaikan dengan langsung mengabarkan element-element yang muncul pertama kali.

Adapun syarat algoritma ini berjalan dengan baik ialah:

1.      Data harus bilangan bulat yang bernilai lebih besar atau sama dengan nol

2.      Range data diketahui

Ada 3 macam array yang terlibat:

1.      Array untuk mengisi bilangan yang belum diurutkan.

2.      Array untuk mengisi frekuensi bilangan itu, sekaligus sebagai penghitung kejadian.

3.      Array untuk mengisi bilangan yang sudah diurutkan.

Algoritmanya :

countingsort(A[], B[], min, max, n)
for i = min to max do
C[i] = 0

C[A[j]] = C[A[j]] + 1
for j = 1 to n do

for i = min + 1 to max do
B[C[A[j]]] = A[j]
C[i] = C[i] + C[i-1]

for j = n downto 1 do
C[A[j]] = C[A[j]] – 1

 Radix Sort

    Radix sorting bisa digunakan ketika masing-masing universal element bisa dilihat sebagai sebuah urutan digit (atau huruf atau symbol lainnya). Sebagai contoh, kita bisa membuat masing-masing bilangan bulat antar 0 sampai 99 sebagai sebuah urutan dengan dua digit (seperti “05”). Untuk menyorting sebuah array dari angka 2-digit, algoritma ini membuat dua ‘passing’ sorting melalui array tersebut. Pada ‘passing’ pertama, element array disorting pada least significant decimal digit. Kunci utama dari radix sort adalah pada passing yang kedua. Hasilnya, setelah kedua passing melewati array tersebut, data yang terisi telah disorting.

 

B. Searching

1. Linear Search

    Algoritma pencarian secara linear adalah algoritma untuk mencari sebuah nilai pada table sambarang dengan cara melakukan pass atau transversal. Transversal dari awal sampai akhir table. Ada dua macam cara pencarian pada table. Algoritma mempunyai dua jenis metode yaitu dengan Boolean dan tanpa Boolean.

Algoritmanya :

void SeqSearch1 (int T[], int Nmax,

int value, int *idx)
{
/*Algoritma*/
/*kamus lokal*/
int i;
i = 1;
i = i + 1;
while ((i<Nmax) && (T[i] !=
value))
{
}
if (T[i]==value)
}
{
*idx = i;
}
else
{
*idx = 0;
}

Algoritma di atas melakukan pengulangan sampai i sama dengan Nmax (ukuran tabel) atau harga value dalam tabel sudah ditemukan.    Kemudian harga i di-assign ke dalam variable idx. Elemen terakhir diperiksa secara khusus.

void SeqSearch2 (int T[],int Nmax,

int value, int *idx)

{

int i;

i = 1;
boolean found;

/*algoritma*/


found = false;

if (T[i] == value)
while ((i<=Nmax) && (!found))

{


{

found = true;

}

else

{

i = i + 1;

}
}

}

if (found)

{

*idx = i;

}

else

{
*idx = 0;

 

2. Binary Search 

    Algoritma pencarian biner adalah algoritma untuk mencari sebuah nilai pada tabel teurut dengan cara menghilangkan setengah data pada setiap langkah. Algoritma ini mencari nilai yang dicari dengan tiga langkah yaitu :

• Mencari nilai tengah dari tabel (median).

• Melakukan perbandingan nilai tengah dengan nilai yang dicari untuk menentukan apakah nilai yang dicari ada pada sebelum atau setelah nilai tengah.

• Mencari setengah sisanya dengan cara yang sama.

Implementasi algoritma pencarian biner dalam bahasa C adalah sebagai berikut.

void BinSearch (int T[],int Nmax, int

value, int* idx)

int i,j,mid;

found = false;
boolean found;$

/*algoritma*/


i = 1;

mid = (i+j) div 2;
j = Nmax;

while ((!found) && (i<=j))

{



if (T[mid] == value)

{

found = true;

}

else

{

if (T[mid]<value)

{

i = mid + 1;

}

else

{

j = mid – 1;

}
}

}
}
if (found)

{

*idx = mid;

}
else

{

*idx = 0;
}

Algoritma Divide and Conquer

Nama ; Silvia Ranti

NPM : 20312073

Kelas : IF 20B

 1.        Sejarah Algoritma Devide and Conquer

Awal dari algoritma ini utamanya adalah pengurangan dan penaklukan - masalah  asli secara berturut-turut dipecah menjadi sub-masalah tunggal, dan memang dapat diselesaikan secara berulang.

Pencarian biner, algoritma penurunan-dan-taklukkan di mana sub-masalah berukuran kira-kira setengah dari ukuran aslinya, memiliki sejarah yang panjang. Sementara deskripsi yang jelas tentang algoritma pada komputer muncul pada tahun 1946 dalam sebuah artikel oleh John Mauchly, gagasan untuk menggunakan daftar item yang diurutkan untuk memfasilitasi pencarian tanggal kembali setidaknya sejauh Babylonia pada 200 SM. 

Algoritma penurunan-dan-taklukkan kuno lainnya adalah algoritma Euclidean untuk menghitung pembagi persekutuan terbesar dari dua bilangan dengan mengurangi bilangan tersebut menjadi subproblem ekuivalen yang lebih kecil dan lebih kecil, yang berasal dari beberapa abad SM. 

Contoh awal dari algoritma bagi-dan-taklukkan dengan beberapa subproblem adalah deskripsi Gauss tahun 1805 tentang apa yang sekarang disebut algoritma Cooley – Tukey fast Fourier transform (FFT), meskipun dia tidak menganalisis jumlah operasinya secara kuantitatif, dan FFT tidak tersebar luas sampai mereka ditemukan kembali lebih dari satu abad kemudian. Algoritma D&C dua sub problem awal yang secara khusus dikembangkan untuk komputer dan dianalisis dengan benar adalah algoritma pengurutan gabungan, yang ditemukan oleh John von Neumann pada tahun 1945. 

Contoh penting lainnya adalah algoritma yang ditemukan oleh Anatolii A. Karatsuba pada tahun 1960 [8] yang dapat mengalikan dua angka n-digit di O (n log 2 ⁡ 3) {\ displaystyle O (n ^ {\ log _ {2} 3} )} O (n ^ {\ log _ {2} 3}) operasi (dalam notasi Big O). algoritma ini menyangkal dugaan Andrey Kolmogorov tahun 1956 bahwa operasi Ω (n 2) {\ displaystyle \ Omega (n ^ {2})} \ Omega (n ^ {2}) diperlukan untuk tugas tersebut. Sebagai contoh lain dari algoritma bagi-dan-taklukkan yang awalnya tidak melibatkan komputer, Donald Knuth memberikan metode yang biasanya digunakan kantor pos untuk merutekan surat: surat diurutkan ke dalam kantong terpisah untuk wilayah geografis yang berbeda, masing-masing kantong ini diurutkan sendiri ke dalam batch untuk sub-wilayah yang lebih kecil, dan seterusnya sampai dikirimkan. Ini terkait dengan jenis radix, yang dijelaskan untuk mesin sortir kartu berlubang sejak tahun 1929.

2.        Devinisi Algoritma Devide and Conquer 

Dalam ilmu komputer, Algoritma divide and conquer adalah paradigma desain algoritma yang didasarkan pada rekursi multi-cabang. Algoritme bagi-dan-taklukkan bekerja dengan memecah masalah secara rekursif menjadi dua atau lebih sub-masalah dari jenis yang sama atau terkait, hingga masalah ini menjadi cukup sederhana untuk diselesaikan secara langsung

3.        Cara Kerja Algoritma Devide and Conquer

1. Divide : Membagi masalah menjadi beberapa upa-masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil ( idealnya berukuran hampir sama ).
2. Conquer : Memecahkan ( menyelesaikan ) masing-masing upa-masalah ( secara rekursif ).
3. Combine : Menggabungkan solusi masing-masing upa-masalah sehingga  membentuk solusi masalah semula.

 

Objek masalah yang di bagi adalah masukan (input) atau instances yang berukuran n: tabel (larik), matriks, dan sebagainya, bergantung pada masalahnya. Tiap-tiap upa-masalah mempunyai karakteristik yang sama (the same type) dengan karakteristik masalah asal, sehingga metode Divide and Conquer lebih natural diungkapkan dalam skema rekursif. Algoritma ini dapat berjalan baik pada persoalan yang bertipe rekursif ( perulangan dengan memanggil dirinya sendiri ). Dengan demikian, algoritma ini dapat diimplementasikan dengan cara iteratif ( perulangan biasa ), karena pada prinsipnya iteratif hampir sama dengan rekursif. 

Salah satu penggunaan algoritma ini yang paling populer adalah dalam hal pengolahan data yang bertipe array ( elemen larik ). Mengapa ? Karena pengolahan array pada umumnya selalu menggunakan prinsip rekursif atau iteratif. Penggunaan secara spesifik adalah untuk mencari nilai minimal dan maksimal serta untuk mengurutkan elemen array. 

Dalam hal pengurutan ini ada empat macam algoritma pengurutan yang berdasar pada algoritma Divide and Conquer, yaitu :

 

1.     Merge sort

2.     Insert sort

3.     Quick sort

4.     Selection sort.

https://teknokrat.ac.id/

https://ftik.teknokrat.ac.id/

 

GEOMETRIC PROBLEM

Nama : Silvia Ranti

NPM : 20312073

Kelas : IF 20A

Mata Kuliah : Analisis Dan Strategi Algoritma

Geometric Problem itu adalah algoritma yang menyelesaikan permasalahan algoritma tentang geometri. Berhubungan dengan titik, garis, poligon, dan lainnya.

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.

Perbedaan Antara Threads dan Processes

 

Perbedaan Antara Threads dan Processes

PENGERTIAN PROSES DAN THREAD    

Proses  merupakan suatu upaya pemberian ajaran secara mendalam (tanpa kritik) atau penggemblengan mengenai suatu paham atau doktrin tertentu dng melihat suatu kebenaran dr arah tertentu saja :)

Thread adalah unit dasar dari penggunaan CPU, yang terdiri dari Thread ID, program counter, register set, dan stack. Sebuah thread berbagi code section, data section, dan sumber daya sistem operasi dengan Thread lain yang dimiliki oleh proses yang sama. Thread juga sering disebut lightweight process.

A. Perbedaan antara Proses dan Thread

Sebuah proses adalah sebuah peristiwa adanya sebuah program yang dapat dieksekusi. Sebagai sebuah eksekusi proses, maka hal tersebut membutuhkan perubahan keadaan. Keadaan dari sebuah proses dapat didefinisikan oleh aktivitas proses tersebut. Suatu proses adalah lebih dari kode program, dimana kadang kala dikenal sebagai bagian tulisan. Proses juga termasuk aktivitas yang sedang terjadi, sebagaimana digambarkan oleh nilai pada program counter dan isi dari daftar prosesor/ processor’s register. Suatu proses umumnya juga termasuk process stack, yang berisikan data temporer (seperti parameter metoda, address yang kembali, dan variabel lokal) dan sebuah data section, yang berisikan variabel global. Setiap proses mungkin menjadi satu dari beberapa state berikut, antara lain: new, ready, running, waiting, atau terminated. Setiap proses direpresentasikan ada sistem operasi berdasarkan proses-control-block (PCB)-nya.

Saya tekankan bahwa program itu sendiri bukanlah sebuah proses. Suatu program adalah satu entitas pasif, seperti isi dari sebuah berkas yang disimpan didalam disket, sebagaimana sebuah proses dalam suatu entitas aktif, dengan sebuah program counter yang mengkhususkan pada instruksi selanjutnya untuk dijalankan dan seperangkatsumber daya/resource yang berkenaan dengannya.

Proses memiliki dua karakteristik namun kedua karakteristik dilakukan secara independen oleh sistem operasi :

- Resource ownership (kepemilikan sumber daya)

Proses mempunyai ruang alamat virtual untuk menangani image proses yang didefinisikan dalam PCB.

- Scheduling-execution (penjadwalan-eksekusi)

Mengikuti suatu path eksekusi (trace), ada pergatian dari satu proses ke lainnya Unit dari kepemilikan sumber daya diacu sebagai proses atau taskuatu thread yang salah dapat menganggu thread yang lain didalam proses yang sama,karena thread berbagai pakai ruang memori virtual dan sumber daya lain yang sama.

Thread adalah unit dasar dari penggunaan CPU, thread mengandung Thread ID, program counter, register set, dan stack. Sebuah Thread berbagi code section, data section, dan sumber daya sistem operasi dengan Thread lain yang dimiliki oleh proses yang sama. Thread juga sering disebut lightweight process. Sebuah proses tradisional atau heavyweight process mempunyai thread tunggal yang berfungsi sebagai pengendali. Perbedaan antara proses dengan thread tunggal dengan proses dengan thread yang banyak adalah proses dengan thread yang banyak dapat mengerjakan lebih dari satu tugas pada satu satuan waktu.

B. Perbedaan antara Proses dan Thread

1. Proses sulit untuk membuat karena membutuhkan duplikasi proses induk dan alokasi memori sedangkan thread lebih mudah untuk membuat karena mereka tidak memerlukan ruang alamat yang terpisah.

2. Thread digunakan untuk tugas-tugas sederhana, sementara proses yang digunakan untuk tugas-tugas yang berat-berat seperti pelaksanaan aplikasi.

3. Proses tidak berbagi ruang alamat yang sama, namun thread dalam berbagi proses yang sama ruang alamat yang sama.

4. Proses yang independen satu sama lain, tetapi thread saling bergantung karena mereka berbagi ruang alamat yang sama.

6. Sebuah proses dapat terdiri dari beberapa thread.

7. Karena thread berbagi ruang alamat yang sama, virtual memori hanya terkait dengan proses tapi tidak dengan thread. Tapi prosesor virtual yang berbeda dikaitkan dengan setiap thread.

8. Setiap proses memiliki kode dan data sendiri sedangkan proses thread berbagi kode yang sama dan data.

9. Setiap proses dimulai dengan thread utama, tapi dapat membuat thread tambahan jika diperlukan.

10. Konteks beralih antara proses jauh lebih lambat dibandingkan konteks beralih antara thread dari proses yang sama.

11. Thread dapat memiliki akses langsung ke segmen data, tetapi proses memiliki salinan sendiri segmen data mereka.

12. roses memiliki overhead tapi tidak thread.

Ringkasan Proses vs Thread

Proses dan thread dua teknik yang digunakan oleh programmer untuk mengontrol prosesor dan pelaksanaan instruksi pada komputer dengan cara yang efisien dan efektif. Sebuah proses dapat berisi beberapa thread. Thread menyediakan cara yang efisien untuk berbagi memori meskipun beroperasi beberapa eksekusi dari proses. Oleh karena itu, thread merupakan alternatif untuk beberapa proses. Dengan tren yang berkembang menuju prosesor multi-core, thread akan menjadi alat yang paling penting dalam dunia programmer.

 

Single Instruction Stream Multiple Data Stream (SIMD) || Multi Processor Organitations

 

1. Pengertian Single Instruction Stream Multiple Data Stream (SIMD)

SIMD adalah satu unit kontrol yang mengeksekusi aliran tunggal instruksi, tetapi lebih dari satu elemen pemroses. Mesin SIMD secara umum mempunyai karakteristik sbb:

·                     Mendistribusi proses ke sejumlah besar hardware

·                     Beroperasi terhadap berbagai elemen data yang berbeda

·                     Melaksanakan komputasi yang sama terhadap semua elemen data

Peningkatan kecepatan pada SIMD proporsional dengan jumlah hardware (elemen pemroses) yang tersedia. SIMD bertugas untuk menyesuaikan kontras dalam citra digital atau menyesuaikan volume audio digital. Desain CPU modern termasuk instruksi SIMD dalam rangka meningkatkan kinerja multimedia yang digunakan.

2. Keuntungan SIMD

·                     Keuntungan SIMD antara lain sebuah aplikasi adalah salah satu dimana nilai yang sama sedang ditambahkan ke (atau dikurangkan dari) sejumlah besar titik data, operasi umum di banyak multimedia aplikasi. Salah satu contoh akan mengubah kecerahan gambar. Setiap pixel dari suatu gambar terdiri dari tiga nilai untuk kecerahan warna merah (R), hijau (G) dan biru (B) bagian warna. Untuk mengubah kecerahan, nilai-nilai R, G dan B yang dibaca dari memori, nilai yang ditambahkan dengan (atau dikurangi dari) mereka, dan nilai-nilai yang dihasilkan ditulis kembali ke memori.

·                     Dengan prosesor SIMD ada dua perbaikan proses ini. Untuk satu data dipahami dalam bentuk balok, dan sejumlah nilai-nilai dapat dimuat sekaligus. Alih-alih serangkaian instruksi mengatakan “mendapatkan pixel ini, sekarang mendapatkan pixel berikutnya”, prosesor SIMD akan memiliki instruksi tunggal yang efektif mengatakan “mendapatkan n piksel” (dimana n adalah angka yang bervariasi dari desain untuk desain). Untuk berbagai alasan, ini bisa memakan waktu lebih sedikit daripada “mendapatkan” setiap pixel secara individual, seperti desain CPU tradisional.

·                     Keuntungan lain adalah bahwa sistem SIMD biasanya hanya menyertakan instruksi yang dapat diterapkan pada semua data dalam satu operasi. Dengan kata lain, jika sistem SIMD bekerja dengan memuat delapan titik data sekaligus, add operasi yang diterapkan pada data akan terjadi pada semua delapan nilai pada waktu yang sama. Meskipun sama berlaku untuk setiap desain prosesor super-skalar, tingkat paralelisme dalam sistem SIMD biasanya jauh lebih tinggi.

3. Kekurangan SIMD

·                     Tidak semua algoritma dapat vectorized. Misalnya, tugas aliran-kontrol-berat seperti kode parsing tidak akan mendapat manfaat dari SIMD.

·                     Ia juga memiliki file-file register besar yang meningkatkan konsumsi daya dan area chip.

·                     Saat ini, menerapkan algoritma dengan instruksi SIMD biasanya membutuhkan tenaga manusia, sebagian besar kompiler tidak menghasilkan instruksi SIMD dari khas Program C, misalnya vektorisasi dalam kompiler merupakan daerah aktif penelitian ilmu komputer.

·                     Pemrograman dengan khusus SIMD set instruksi dapat melibatkan berbagai tantangan tingkat rendah.

·                     SSE (Streaming SIMD Ekstensi) memiliki pembatasan data alignment, programmer akrab dengan arsitektur x86 mungkin tidak mengharapkan ini.

·                     Mengumpulkan data ke dalam register SIMD dan hamburan itu ke lokasi tujuan yang benar adalah rumit dan dapat menjadi tidak efisien.

·                     Instruksi tertentu seperti rotasi atau penambahan tiga operan tidak tersedia dalam beberapa set instruksi SIMD.

·                     Set instruksi adalah arsitektur-spesifik: prosesor lama dan prosesor non-x86 kekurangan SSE seluruhnya, misalnya, jadi programmer harus menyediakan implementasi non-Vectorized (atau implementasi vectorized berbeda) untuk mereka.

·                     Awal MMX set instruksi berbagi register file dengan tumpukan floating-point, yang menyebabkan inefisiensi saat pencampuran kode floating-point dan MMX. Namun, SSE2 mengoreksi ini.

SIMD dibagi menjadi beberapa bentuk lagi yaitu :

1.             Exclusive-Read, Exclusive-Write (EREW) SM SIMD

2.             Concurent-Read, Exclusive-Write (CREW) SM SIMD

3.             Exclusive-Read, Concurrent-Write (ERCW) SM SIMD

4.             Concurrent-Read, Concurrent-Write (CRCW) SM SIMD