Sejarah, Definisi dan Cara Kerja Algoritma Divide and Conquer

Algoritma Divide and Conquer

Sejarah divide and conquer Divide and Conquer dulunya adalah strategi militer yang dikenal dengan nama divide ut imperes. Sekarang strategi tersebut menjadi strategi fundamental di dalam ilmu komputer dengan nama Divide and Conquer. pengertian

• Divide: membagi masalah menjadi beberapa upa-masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil (idealnya berukuran hampir sama),

• Conquer: memecahkan (menyelesaikan) masing-masing upa-masalah (secara rekursif), dan

• Combine: mengabungkan solusi masing-masing upa-masalah sehingga membentuk solusi masalah semula.

Obyek permasalahan yang dibagi : masukan (input) atau instances yang berukuran n seperti: - tabel (larik), - matriks, - eksponen, - dll, 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. Perkembangan Algoritma Divide and Conquer Algoritma divide and conquer sudah lama diperkenalkan sebagai sumber dari pengendalian proses paralel, karena masalah-masalah yang terjadi dapat diatasi secara independen. Banyak arsitektur dan bahasa pemrograman paralel mendesain implementasinya (aplikasi) dengan struktur dasar dari algoritma divide and conquer. Untuk menyelesaikan masalah-masalah yang besar, dan dibagi (dipecah) menjadi bagian yang lebih kecil dan menggunakan sebuah solusi untuk menyelesaikan problem awal adalah prinsip dasar dari pemrograman/strategi divide and conquer.

Divide and conquer adalah varian dari beberapa strategi pemrograman topdown, tetapi keistimewaannya adalah membuat sub-sub problem dari problem yang besar, oleh karena itu strategi ini ditunjukkan secara berulang-ulang (recursively), didalam menerapkan algoritma yang sama dalam sub-sub problem seperti yangditerapkan pada masalah aslinya (original problem). Sebagaimana prinsip dasar algoritma perulangan dibutuhkan sebuah kondisi untuk mengakhiri perulangan tersebut. Biasanya untuk mengecek apakah problem sudah cukup kecil untuk diselesaikan dengan metode secara langsung. Mungkin dari segi ilustrasi kita, bahwa proses-proses pada komputer paralel tentunya memiliki proses/problem/job yang cukup kompleks sehingga harus dipecah-pecah menjadi sub-sub problem. Selain dibutuhkan sebuah “kondisi”, juga diperlukan “fase divide” untuk membagi/memecah problem menjadi sub-sub problem yang lebih kecil, dan “fase combine“ untuk menggabungkan kembali solusi dari sub-sub problem kedalam solusi dari problem awalnya.

Berikut pseudocode dari strategi divide and conquer

Pseudocode diatas adalah sebagai acuan dari strategi divide and conquer, tetapi dalam implementasinya ada beberapa diferensiasi dari bentuk diatas yang akan digunakan. Sebelum masuk ke pokok pemrograman dengan “Divide and Conquer strategy/algorithm”, ada 4 hal penting yang harus dipahami dalam strategi ini yaitu branching factor, balance, data dependence of divide function dan sequentiality.

Branching Factor

Branching factor dalam algoritma divide and conquer adalah jumlah dari subproblem yang akan dibagi dari sebuah problem awal. Ini adalah langkah nyata dari algoritma divide and conquer, didalam proses pembagian yang sebenarnya, jumlah dari branching factor harus 2 atau lebih, karena jika tidak problem tidak bisa dibagi. Banyak jenis algoritma ini termasuk pula algoritma komputasi geometric yang memiliki branching factor berjumlah 2.

Balance

Sebuah algoritma divide and conquer dikatakan balance jika problem awal dibagi menjadi sub-sub problem dengan ukuran yang sama. Yang artinya jumlah dari keseluruhan ukuran subproblem sama dengan ukuran problem awal (initial problem). Algoritma Mergesort dan binary tree, dan sama halnya dengan algoritma reduksi & prefix sum adalah beberapa contoh algoritma divide and conquer yang seimbang (balance).

Data Dependence of Divide Function

Algoritma divide and conquer memiliki sebuah fungsi pembagian terhadap data yang memiliki ketergantungan, artinya jika ukuran relatif dari sebuahsubproblem tergantung pada proses input datanya. Ini adalah salah satu ciri dari algoritma yang tidak seimbang, salah satu contohnya adalah algoritma quicksort yang akan membagi subproblem dengan fungsi data-dependent divide.

Control Parallelism or Sequentiality

Algoritma divide and conquer dikatakan berurutan (sequential) jika subproblem dieksekusi sesuai dengan perintah program. Paralelisasi dari algoritma divide and conquer yang terurut pertama kali didefinisikan oleh Mou’s Divacon[Mou90], yang terjadi ketika hasil dari salah satu sub-eksekusi diperlukan oleh subeksekusi yang lain. Dalam kasus ini hasil dari subtree pertama diberikan (passing) kepada proses komputasi subtree kedua, supaya hasil akhir tersebut bisa digunakan sebagai nilai awalnya, tetapi sekarang ini contoh diatas tidak dapat dijadikan ilustrasi lagi karena teknologi komputer paralel yang semakin canggih dan kompleks.

Klasifikasi dari Algoritma/Strategi Divide and Conquer

Berikut klasifikasi algoritma divide and conquer, kita bisa melihat daftar dan karakteristik dari beberapa algoritma yang ditunjukkan dalam tabel :

Tabel karakteristik dari Algoritma divide and conquer. Catatan bahwa quicksort

dan quickhull bisa dikonversi kedalam algoritma yang balance dengan cara

menemukan median (titik tengah) yang tepat.

Penerapan Data-Parallel Divide and Conquer Algorithms

Sorting

Quick Sort, Binary Sort

Computational Geometry

Closest Pairs, Convex Hull, Delaunay Triangulation

Graph Theory

Travelling Salesman Problem (TSP), Graph Separators

Numerical

Matrix Multiplication, FFT

Not Data Parallel

Naïve Merge Sort

Rekursi Divide and Conquer

Machiavelli menggunakan sintaks : Split (result1 = func (arg1), result2 = func (arg2) [, resultn = func (argn)]) Untuk membentuk fungsi call dalam algoritma divide and conquer. varn adalah hasil akhir yang kembali ke fungsi func dalam argument argn. Machiavelli membuat versi fungsi yang salah satunya mengaplikasikan reduksi menjadi sebuah “pengulangan sederhana” . Script berikut adalah contoh pemakaian fungsi fetch :

Penerapan fetch untuk integer

Script diatas dapat digunakan untuk meng-compile algoritma parallel dari versi serial. Script berikut menunjukkan contoh lain dimana lebih efisien dalam penerapannya yaitu Quicksort :

Contoh Penerapan Pada Binary Search

Temukan sebuah elemen atau bilangan pada array yang telah tersortir :

1. Divide : cek elemen tengah

2. Conquer : secara rekursif, cari disebuah subarray

3. Combine : trivial

Kasus :

Temukan bilangan 9 pada deret 3, 5, 7, 8, 9, 12, 15

Contoh Penerapan Bucket Sort Secara Paralel

Asumsikan sebuah p processor menangani setiap bucket (p bucket)

Penjelasan

Bagilah secara sekuen kedalam m bagian, bagian-bagian yang terbentuk akan ditangani oleh p processor, Masing-masing processor akan menangani p bucket dan memisahkan bilangan bilangan pada array ke dalam masing-masing bucket. Bucket-bucket akan dikosongkan kedalam p bucket akhir dari pengurutan yang membutuhkan masing-masing processor untuk mengirim sebuah bucket untuk setiap processor lainnya (bucket i to processor i )

Contoh Lain Penerapan Bucket Sort Secara Paralel

Pada contoh ini dikenalkan sebuah operasi message-passing yang baru all-to-all broadcast.

Penjelasan

Bagilah secara sekuen kedalam m bagian, bagian-bagian yang terbentuk akan ditangani oleh p processor, Masing-masing processor akan menangani p small bucket dan memisahkan bilangan-bilangan pada array ke dalam masing-masing small bucket. Masing-masing small bucket dari masing-masing processor akan dikosongkan, kemudian hasil perhitungan di small bucket akan ditampung ke masing-masing large buket. Di large bucket data diolah kembali untuk kemudian dihasilkan array yang telah tersortir dari masing-masing large bucket.

“all-to-all” broadcast routine

Mengkomunikasikan data dari masing-masing proses ke proses lainnya

all-to-all” routine pada dasarnya mentransfer baris-baris dari sebuah array ke kolomkolom yang dinamakan Transpose Matrix.

Kesimpulan :

Algoritma divide and conquer sudah lama diperkenalkan sebagai sumber dari pengendalian proses parallel, karena masalah-masalah yang terjadi dapat diatasi secara independent. Banyak arsitektur dan bahasa pemrograman parallel mendesain implementasinya (aplikasi) dengan struktur dasar dari algoritma divide and conquer.

Divide and Conquer secara umum terbagi dalam tiga fase, divide yakni membagi masalah kedalam sub-sub masalah yang lebih kecil, conquer yakni menyelesaikan sub-sub masalah secara rekursif, dan combine menggabungkan hasil dari penyelesian sub-sub masalah menjadi penyelesaian yang dikehendaki Terdapat empat hal pada strategi “divide and conquer” : branching factor, balance, data dependence of divide function dan sequentiality.

Implementasi Algoritma Divide and Conquer pada Sorting dan Searching

 Algoritma merupakan kumpulan perintah yang memiliki daya guna yang sangat besar bagi masyarakat. Algoritma biasanya digunakan sebagai kumpulan perintah untuk menyelesaikan suatu masalah. Algoritma ini memiliki aplikasi yang bermacam-macam dalam setiap masalah yang ada. Contohnya saja adalah algoritma cara menyelesaikan suatu aritmatika yang rumit, algoritma untuk menghitung luas penampang dari suatu kabel, atau bahkan untuk menghitung bayaran parkir di setiap mal. Salah satu aplikasi bentuk pemrograman ini adalah dalam bahasa permrograman yang disebut bahasa C. Dimana bahasa C ini memiliki suatu aturan-aturan tertentu yang sangat penting sehingga dalam penggunaanya kita harus memperhatikan cara menggunakan aturan tersebut. Salah satu cara penggunaannya adalah dengan array. Dimana array ini merupakan suatu data struktur yang berkoneksi satu sama lain dengan tipe yang sama. Aplikasi array ini banyak sekali, contohnya saja adalah menghitung golongan dari umur yang berjumlah 25 tahun hingga 55 tahun. Array ini juga bisa digunakan untuk mencari suatu elemen nilai dalam suatu struktur data, selain itu array ini juga bisa digunakan untuk mengurutkan data-data yang tidak berurutan. Hal –hal yang telah disebutkan disebut sebagai searching array dan sorting array.

    Sorting array merupakan salah satu aplikasi yang paling penting dalam suatu sistem aplikasi perhitungan data. Biasanya suatu bank memiliki komputasi sorting array yang sudah biasa digunakan dalam aplikasinya sehari-hari. Bahkan telephone juga mengurutkan suatu list yang terdiri dari nama akhir , nama awal agar bisa memudahkan dalam perhitungan dalam mencari nomor telephone.

    Searching array juga memiliki tak kalah pentingnya dibandingkan dengan sorting array. Pada searcing array kita biasa menggunakannya pada data yang sangat banyak. Sehingga sangat sulit bila kita ingin mencari suatu data atau suatu angka didalamnya satu per satu. Aplikasi searching array memudahkan kita dalam mencari suatu data atau angka yang kita inginkan dengan hanya memasukkan nilai input pada suatu data yang disikan.

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. 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

Proses rekursi berhenti jika mencapai elemen dasar. Hal ini terjadi bilamana bagian yang akan diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah terurut sesuai rangkaian.

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);

}

                                         Gambar3.1. Diagram Merge Sort

4. 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);

}

                    Gambar 3.2. Diagram Quick Sort

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

                                                        Gambar 3.3 Diagram Counting Sort

6. 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.

Algoritmanya :

source

List of bytes
source_n

number of bytes to sort
dest[256]

256 lists of bytes. each list should have enough space to hold source_n elements.
//——————-saving element in memory——————–

int distribution[256]
// fill the list with zeros.
for i=0 to source_n do
for i=0 to 255 do
distribution[i]=0;

// build a distribution history:


distribution] = distribution] +1;
for i=0 to 255 do
endfor

// Now we build a index-list for each possible element:

int index[256];

index [0]=0;


for i = 0 to source_n do
index[i]=index[i-1]+distribution[i-1];

endfor
//sorting
dest: array of bytes with space for source_n bytes.
 
endfor
  dest[index]]=source[i];
  index] = index] +1;

7. Searching

7.1 Linear Searching

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;

7.2 Binary Searching

Algoritma pencairan secara linear melakukan pengulangan sebanyak 1 kali untuk kasus terbaik (value sama dengan elemen pertama dalam tabel) dan Nmax kali untuk kasus terburuk. Sehingga algoritma ini mempunyai kompleksitas algoritma O(n).

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 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.

Berbagai Masalah Yang Dapat Diselesaikan Menggunakan Algoritma

 PENGERTIAN ALGORITMA

Algoritma adalah penyelesaian masalah yang logis. Logis maksudnya berdasarkan pada perhitungan pasti dan langkah yang tidak akan gagal. Menurut KBBI (Kamus Besar Bahasa Indonesia) Algoritma adalah prosedur sistematis untuk memecahkan masalah matematis dalam langkah-langkah terbatas dan urutan logis pengambilan keputusan untuk pemecahan masalah. Algoritma tidak hanya bisa diterapkan pada ilmu matematika. Algoritma juga berguna di segala macam bidang dan dalam kehidupan sehari-hari. Saat ini, algoritma adalah bagian terpenting dalam proses pemrogaman, Terutama untuk memecahkan suatu masalah dan langkah yang tepat untuk mencapainya. Manusia saat ini tidak lagi menulis program untuk pemrograman. Melainkan menyelesaikan masalah yang akan diprogram dengan desain sebagai pemecahannya. Desain algoritma yang nantinya akan menjalankan pemrograman sebagai solusi. Desain pemrograman dengan algoritma yang berisi cara berpikir dan urutan langkah yang harus dilakukan agar bisa mencapainya.

  Bisa pula dikatakan algoritma adalah sebuah langkah perhitungan, penalaran otomatis, dan pemrosesan data sebelum menyelesaikan suatu masalah. Algoritma akan memaparkan kondisi awal, eksekusi yang harus dilakukan, dan hasil. Algoritma bias juga  dipelajari melalui teks. Teks inilah yang akan membuat sebuah program bisa menyelesaikan masalah yang sedang dihadapi. Akan ada sebuah deskripsi dalam notasi untuk dimengerti dan dipahami. Notasi ini berupa notasi algoritmik dan notasi bahasa pemrograman.

  Algoritma secara bahasa diartikan sebagai proses perhitungan dalam bahasa Arab, namun saat ini ilmu algoritma berkembang sebagai ilmu dalam sistem komputasi. Mengutip dari laman stebisigm.ac.id (diakses pada 9/11/21), algoritma didefinisikan sebagai deretan langkah-langkah komputasi computer yang mentransformasikan data masukan menjadi keluaran. Berdasarkan pengertian ilmu algoritma dalam sistem komputasi tadi, maka algoritma secara umum dimanfaatkan sebagai sistem yang dapat memudahkan penyelesaian masalah dalam komputasi pemrograman.

ALGORITMA MENURUT PARA AHLI

 Algoritma adalah suatu daftar langkah demi langkah yang terhingga dari instruksi-instruksi yang terdefinisikan dengan jelas yang dipakai untuk permasalahan tertentu. (Seymour Lipschutz, Ph.D dan Marc Lipson, Ph.D.)

 Algoritma adalah hal umum untuk dipahami sebagai suatu keputusan yang tepat untuk mendefinisikan proses komputasi yang mengarahkan dari data awal hingga hasil yang diinginkan. ( Andrey Andreyvich Markov)

 Algoritma adalah suatu seperangkat aturan yang tepat mendefinisikan urutan operasi hingga sedemikian rupa sehingga setiap aturan yang efektif, jelas hingga sedemikian rupa sehingga urutan berakhir dalam waktu yang terbatas. (Stone dan Knuth)

 Definisi algoritma adalah suatu metode khusus untuk menyelesaikan suatu persoalan.(Abu Ja’far Muhammad Ibnu Musa Al Khawarizmi)

 Algoritma adalah urutan terbatas dari operasi-operasi terdefinisi dengan baik, yang masing-masing membutuhkan memori dan waktu yang terbatas untuk menyelesaikan suatu masalah.( Goodman Hedet Niemi )

 Algoritma adalah sekumpulan aturan-aturan berhingga yang memberikan sederetan operasi-operasi untuk menyelesaikan suatu jenis masalah yang khusus.( Donald E. Knuth )

BERBAGAI PERMASALAHAN YANG DAPAT DISELESAIKAN DENGAN ALGORITMA

1.      ALGORITMA DALAM KEHIDUPAN SEHARI-HARI

Algoritma sering digunakan oleh sebagian orang dalam kehidupan sehari-hari. Sebagian besar waktu, ini merupakan upaya untuk memecahkan beberapa masalah melalui urutan langkah-langkah yang sistematis.

a. Algoritma untuk membuat kopi

Contoh pertama dari algoritma dalam kehidupan sehari-hari  terkait dengan persiapan kopi. Ini termasuk instruksi untuk membuka bungkus kopi, menyeduh air, mencampur gula, dan mencampur dengan air panas. Kemudian megaduknya menggunaka sendok,Setelah semuanya tercampur rata, kopi siap disajikan.

b. Algoritma pembuatan mie goreng

Saat membuat mie goreng, buka bungkus mie dan biarkan sebentar sambil menunggu air yang dimasak panas lalu direbus dengan air panas tersebut. Langkah selanjutnya adalah mengeringkan air lalu mencampurkan bumbu dengan mie goreng. Setelah diaduk rata menggunakan sendok, bisa disantap hangat atau dingin.  

c. Algoritma memasak nasi

Sebelum menanak nasi, mohon cuci beras dan siapkan rice cooker. Setelah mendapatkan air yang cukup, letakkan di atas lalu tutup.colokkan kabel listrik rice cooker ke steker, Jangan lupa tekan tombol cooking dan biarkan nasi matang sampai muncul tombol warming.

 

2.      ALGORITMA PEMROGRAMAN

Dalam bidang komputer,Fungsi algoritma sangat diperlukan untuk menyelesaikan berbagai masalah pemrograman, terutama dalam komputasi numerik. Tanpa algoritma yang dirancang dengan baik, proses pemrograman akan menjadi salah, rusak, lambat dan tidak efisien. Pelaksana langkah-langkah di dalam algoritma adalah sistem komputer. Agar manusia dan komputer dapat berkomunikasi, manusia memberikan perintah-perintah kepada komputer berupa kumpulan instruksi yang dikumpulkan di dalam program. Dalam menyelesaikan persoalan, komputer perlu merumuskan beberapa langkah penyelesaian persoalan dalam sekumpulan instruksi. Kumpulan instruksi yang dimengerti oleh komputer inilah yang disebut dengan program.

a.      Algoritma Narasi

Contoh: Algoritma Kelulusan_mhs

Persoalan: Diberikan data berupa nama dan nilai mahasiswa. Jika nilai mahasiswa lebih besar atau sama dengan 60 maka mahasiswa tersebut dinyatakan lulus. Sedangkan jika nilainya lebih kecil dari 60, maka mahasiswa tersebut dinyatakan tidak lulus.

Algoritmanya akan seperti berikut:
baca nama dan nilai mahasiswa.
jika nilai >= 60 maka
keterangan = lulus
tetapi jika
keterangan = tidak lulus.
tulis nama dan keterangan

 

b.      Algoritma Pseudo Code

 

Contoh; Algoritma Kelulusan_mhs

Persoalan: Diberikan data berupa nama dan nilai mahasiswa. Jika nilai mahasiswa lebih besar atau sama dengan 60 maka mahasiswa tersebut dinyatakan lulus. Sedangkan jika nilainya lebih kecil dari 60, maka mahasiswa tersebut dinyatakan tidak lulus.

Deklarasi dari tipe datanya akan seperti berikut:
Nama = string
Nilai = integer
Keterangan = string

Algoritmanya akan seperti berikut:
read (nama, nilai)
if nilai >= 60 then
keterangan = ‘lulus’
else
keterangan = ‘tidak lulus’
write(nama, keterangan)

 

c.       Algoritma Flowchart

 

§  Flowchart menghitung luas lingkaran

Algoritma flowchart di bawah ini adalah contoh flowchart untuk menghitung luas lingkaran dengan rumus L = πr2:

Algoritma:

§  Program dimulai

§  Tentukan nilai phi dan r

§  Hitung L = phi x r2

§  Cetak Hasil L

§  Program Selesai

Flowchart:

Proses Design dan Life Cycle Basis Data

 RELATIONAL DATABASE

Relational Database adalah suatu model database yang disajikan dalam bentuk tabel. Model ini pertama kali diperkenalkan oleh E.F.Codd pada bulan juni 1970 dalam sebuah paper berjudul "A Relational Model of Data for Large Shared Data Banks"

Tujuan Relational Database :

• Untuk menekankan kemandirian data
• Menghilangkan inkonsitensi dan redudansi data menggunakan konsep normalisasi
• Meningkatkan kemampuan akses data

Karakteristik Relational Database :

• Struktur Tabular
• Satu bahasa digunakan untuk semua pemakai
• Data dihubungkan melalui nilai data

Model Data Relasional mengandung 3 komponen inti :

•  Struktur data (data diorganisasi dalam bentuk tabel)
• Manipulasi data (menggunakan SQL)
• Integritas data (Menjamin konsistensi data)

Integritas data adalah menjamin konsistensi data terhadap semua konstrain yang diberlakukan terhadap data tersebut, sehingga memberikan jaminan keabsahan data itu sendiri.

Struktur Data

Struktur berbentuk tabel data dua dimensi

Contoh :

Struktur yang baik adalah relasi yang mengandung redundansi minimal dan mengijinkan pengguna untuk menyisipkan, memodifikasi serta menghapus baris-baris tanpa menimbulkan kesalahan.

Manipulasi Data

• Data Definition Language (DDL)

- Create

- Drop

- Alter

• Data Manipulation Language (DML)

- Insert

- Delete

- Update

- Select

Batasan Integritas Data

Domain Atribut

• Setiap nilai yang disimpan dalam kolom sebuah relasi harus memiliki jangkauan nilai yang sama

Aturan Integritas

• Aturan yang menjamin setiap atribut primary key bernilai valid (unik dan bukan null)

Referensial Integrity

• Garis yang menghubungkan antara satu tabel dengan tabel lain

Proses Design Database

Basis data biasanya merupakan salah satu bagian dari suatu sistem informasi yang besar yang antara lain terdiri dari:

- Data

- Perangkat Lunak DBMS

- Perangkat Keras Komputer

- Perangkat Lunak dan Sistem Informasi Komputer

- Program-Program Aplikasi

- Pemrograman

Proses Design Basis Data yaitu:

Pengumpulan dan Analisa requirement

Pengidentifikasian group pemakai dan area aplikasi

Penelitian kembali dokumen-dokumen yang sudah ada yang berhubungan dengan aplikasi form, report, manual, organization chart, dsb

Analisa lingkungan operasi dan kebutuhan dari pemrosesan, seperti tipe transaksi, input/output, frekuensi suatu transaksi, dsb

Transfer informasi informal ke dalam bentuk terstruktur menggunakan salah satu bentuk formal dari requirement specification (bentuk diagram) seperti Flow Chart, DFD, UML Diagram, dll. Hal ini dilakukan untuk mempermudah pemeriksaan kekonsistenan, ketepatan, dan kelengkapan dari spesifikasi

Design basis data conceptual

- High level data model, bukan implementation-level data model

- Memberikan gambaran yang lengkap dari struktur basis data yaitu arti, hubungan, dan batasan-batasan.

- Conceptual schema bersifat tetap

- Alat komunikasi antar pemakai basis data, designer, dan analis

- Harus Bersifat Conceptual data model harus DBMS independent.

Pemilihan DBMS

Faktor teknis: storage, akses path, user interface, programmer, bahasa query, data models

Faktor ekonomi: software, hardware, maintenance, training, operasi, konversi, teknisi,

Faktor organisasi: kompleksitas, data, sharing antar aplikasi, perkembangan data, pengontrolan data

Mapping dari conceptual ke logical

Memetakan conceptual model ke dalam DBMS

Menyesuaikan schema dengan DBMS pilihan

Hasil pemetaan biasanya berupa DDL

Physical design

Struktur storage, akses path untuk mendapatkan performance yang baik

Kriteria baik dapat dilihat dari:

response time

pemakaian storage

throughput (jumlah transaksi per unit waktu)

Perlu tuning untuk memperbaiki performance berdasarkan statistik pemakaian

Implementasi

DDL dan SDL dari DBMS dikompilasi membentuk schema basis data dan basis data yang masih kosong

Basis data dapat dimuati (di-load) dari sistem yang lama

Transaksi dapat diimplementasikan oleh program aplikasi dan dikompilasi

Siap dioperasikan

Keenam fase dalam proses design tidak perlu dilaksanakan secara mutlak, mungkin ada umpan antar fase dan masing-masing fase.

Proses Design terdiri dari dua proses paralel yaitu:

Proses design dari data dan struktur dari basis data (data driven).

Proses design dari program aplikasi dan pemrosesan basis data (process driven)

Mengapa harus paralel???? Karena kedua proses tersebut saling bergantungan. Contoh :

Menentukan data item yang akan disimpan dalam basis data bergantung dari aplikasi basis data tersebut, juga dalam menentukan struktur dan akses path.

Design dari program aplikasi tergantung dari struktur basis datanya.

Biasanya condong ke salah satu.

Life Cycle Database

Daur hidup (Life Cycle) yang umum dari Aplikasi Basis Data yaitu :

Definisi Sistem

Ruang Lingkup basis data

Pemakai

Aplikasi

Design

logical design

physical design untuk suatu DBMS

Implementasi

membuat basis data

membuat program aplikasi

Loading/konversi data

memasukan data ke dalam basis data

mengkonversi file yang sudah ada ke dalam format basis data dan kemudian memasukannya dalam basis data

Konversi Aplikasi

Semua aplikasi dari sistem sebelumnya dikonversikan ke dalam sistem basis data

Testing dan Validasi

Sistem yang baru ditest dan divalidasi (diperiksa keabsahannya)

 Operasi

Pengoperasian basis data dan aplikasinya

Monitoring dan Maintenance

Selama operasi, sistem dimonitor dan dipelihara. Baik data maupun program aplikasi masih dapat terus tumbuh dan berkembang.