IMPLEMENTASI ALGORITMA ALGORITMA BRANCH AND BOUND

 

IMPLEMENTASI ALGORITMA ALGORITMA BRANCH AND BOUND

 Analisis dan Strategi Algoritma

Nama : Ahmad Januar A
NPM : 19312162
Kelas :IF 21 Dx

FTIK TEKNOKRAT

UNIVERSITAS TEKNOKRAT INDONESIA

Metode Branch and Bound

    Metode Branch and Bound adalah sebuah teknik algoritma yang secara khusus mempelajari bagaimana caranya memperkecil Search Tree menjadi sekecil mungkin. 

Sesuai dengan namanya, metode ini terdiri dari 2 langkah yaitu :

• Branch yang artinya membangun semua cabang tree yang mungkin menuju solusi. 
• Bound yang artinya menghitung node mana yang merupakan active node (E-node) dan node mana yang merupakan dead node (D-node) dengan menggunakan syarat batas constraint (kendala).
• Teknik Branch and Bound

Ada beberapa teknik dalam Branch and Bound yaitu: 

• FIFO Branch and Bound Adalah teknik Branch and Bound yang menggunakan bantuan queue untuk perhitungan Branch  and Bound secara First In First Out.
• LIFO Branch and Bound Adalah teknik Branch and Bound yang menggunakan bantuan stack untuk perhitungan Branch and Bound secara Last In First Out.

Least Cost Branch and Bound

    Teknik ini akan menghitung cost setiap node. Node yang memiliki cost paling kecil dikatakan memiliki kemungkinan paling besar menuju solusi. 

    Masalah yang dapat dipecahkan with Branch and Bound Branch and Bound dapat digunakan untuk memecahkan berbagai masalah yang menggunakan Search Tree :

• Traveling Salesman Problem
• N-Queen Problem
• 15 Puzzle Problem
• 0/1 Knapsack Problem
• Shortest Path

Knapsack Problem

    Knapsack problem adalah suatu masalah bagaimana cara menentukan pemilihan barang dari sekumpulan barang dimana setiap barang tersebut mempunyai berat dan profit masing masing, sehingga dari pemilihan barang tersebut didapatkan profit yang maksimum. 

    Penyelesaian masalah dengan menggunakan algoritma exhaustive search adalah mengenumerasikan semua kemungkinan barang-barang yang layak atau memenuhi syarat yaitu tidak melebihi batas daya angkut gerobak untuk dijual setiap harinya , kemudian menghitung tiap-tiap keuntungan yang diperoleh dan memilih solusi yang menghasilkan keuntungan terbesar. 

    Berbeda dengan algoritma exhaustive search yang cukup memakan waktu dan dapat menghasilkan solusi yang optimum, penyelesaian masalah dengan menggunakan algoritma greedy dilakukan dengan memasukan objek satu persatu kedalam gerobak dan tiap kali objek tersebut telah dimasukan kedalam gerobak maka objek tersebut tidak dapat lagi dikeluarkan dari gerobak.

    Pencarian solusi akan dilakukan dengan memilih salah satu jenis greedy (greedy by weight, greedy by profiit or greedy by density) yang diperkirakan dapat menghasilkan solusi yang optimum. Algoritma Branch and Bound juga merupakan salah satu strategi yang dapat digunakan dalam pencarian solusi optimum dari permasalahan knapsack ini.

Algoritma Branch and Bound

    Sebagaimana pada algortima runut-balik, algoritma Branch & Bound juga merupakan metode pencarian di dalam ruang solusi secara sistematis. Ruang Solusi diorganisasikan ke dalam pohon ruang status. Pembentukan pohon ruang status. Pembentukan pohon ruang status pada algoritma B&B berbeda dengan pembentukan pohon pada algoritma runutbalik. 

    Bila pada algoritma runut-balik ruang solusi dibangun secara Depth-First Search(DFS), maka pada algoritma B&B ruang solusi dibangun dengan skema Breadth-First Search (BFS).

    Pada algoritma B&B, pencarian ke simpul solusi dapat dipercepat dengan memilih simpul hidup berdasarkan nilai ongkos (cost). Setiap simpul hidup diasosiasikan dengan sebuah ongkos yang menyatakan nilai batas (bound). 

    Pada prakteknya, nilai batas untuk setiap simpul umumnya berupa taksiran atau perkiraan. Fungsi heuristik untuk menghitung taksiran nilai tersebut dinyatakan secara umum sebagai :

(i) = (i) + (i)

yang dalam hal ini,

(i) = ongkos untuk simpul i

(i) = ongkos mencapai simpul i dari akar

(i) = ongkos mencapai simpul tujuan dari simpul akar i (perkiraan)

    Nilai digunakan untuk mengurutkan pencarian. Simpul berikutnya yang dipilih untuk diekspansi adalah simpul yang memiliki  minimum (Simpul-E). Strategi memilih simpul-E seperti ini dinamakan strategi pencarian berdasarkan biaya terkecil (least cost search).

Prinsip dari algoritma branch and bound ini adalah :

1. Masukkan simpul akar ke dalam antrian Q. Jika simpul akar adalah simpul solusi (goal node), maka solusi telah ditemukan. Stop.
2. Jika Q kosong, tidak ada solusi . Stop.
3. Jika Q tidak kosong, pilih dari antrian Q simpul i yang mempunyai (i) paling kecil. Jika terdapatbeberapa simpul i yang memenuhi, pilih satusecara sembarang.
4. Jika simpul i adalah simpul solusi, berarti solusi sudah ditemukan, stop. Jika simpul i bukan simpul solusi, maka bangkitkan semua anak-anaknya. Jika i tidak mempunyai anak, kembali ke langkah 2.
5. Untuk setiap anak j dari simpul i, hitung  (j), dan masukkan semua anak-anak tersebut ke dalam antrian Q.
6. Kembali ke langkah 2.

Knapsack Problem Solve

    Untuk lebih memahami tahap-tahap penyelesaian permasalahan knapsack ini, kita ambil contoh persoalan seperti yang dituliskan pada bagian Abstrak yaitu dimana seorang pedagang keperluan rumah tangga keliling harus memilih barang-barang yang akan dijual setiap harinya dengan batas daya angkut gerobak yang dimilikinya. 

    Untuk mempermudah, kita misalkan pedagang keliling tersebut hanya memiliki 4 jenis barang untuk dijual dengan berat dan keuntungan penjualan yang berbeda-beda untuk tiap jenisnya. 

    Gerobak yang akan dipakai untuk mengangkut barang-barang tersebut hanya mampu menampuk beban seberat 16 kg. Berikut merupakan tebel penggambaran beratdan keeuntungan yang akan diperoleh untuk tiap penjualan barang tersebut.

    Dari tiap tiap simpul anak untuk dapat menentukan simpul mana yang kelak akan dibangkitkan yaitu simpul dengan cost tertinggi dalam penelusuran pohon unutk mencapai solusi dari permasalahan ini.

    Dalam permasalahan ini, kita akan mencari simpul-simpul yang akan membawa kita pada keuntungan terbesar oleh karena itu urutan pembangkitan simpul akan ditentukan oleh simpul mana yang memiliki cost tertinggi. Cost dari tiap simpul akan ditentukan dengan:

(i) = (i) + (i)

yang dalam hal ini,

(i) = cost untuk simpul i

(i) = cost untuk sampai ke simpul I, dalam hal ini merupakan keuntungan dari simpul akar ke simpul i

(i) = cost dari simpul i untuk sampai ke simpul tujuan, dalam hal ini dapat diperoleh dengan menggunakan rumus : (P/W)max * daya angkut yang tersisa

    pada tahap awal kita akan melakukan perhitungan dengan menggunakan rumus diatas untuk memperoleh batas awal atau akar dari pohon yang juga merupakan simpul pertama.

    Pada keadaan ini, batas dihitung dengan pemikiran bahwa belum ada satupun barang yang dimasukan kedalam alat pengangkut maka kita dapat memilih 6 sebagai (P/W) terbesar karena belum ada satu barangpun yang dimasukan kedalam alat pengangkut dan kapasitas daya angkutpun masih utuh yaitu seberat 16 kg.

(i) = (i) + (i)

(1) = keuntungan yang diperoleh sampai disimpul

awal + (P/W)max * daya angkut yang tersisa

= 0 + 6 *

= 96

Maka kita memperoleh 96 batas awal atau cost dari simpul awal.

    Bangkitkan simpul-simpul anak dari akar pohon yaitu dengan membangkitkan simpul 1, simpul 2, simpul 3 dan simpul 4 sebagai gambaran dari 4 pilihan barang yang akan dimasukan pertama kali pada alat pengangkut dengan x1 merupakan keuntungan yang akan diperoleh pada penjualan tiap barang tersebut.

    Kemudian kita akan menghitung cost dari tiap simpul anak yang hidup dan juga kelayakannya untuk tetap hidup atau harus dibunuh. Dalam hal ini, simpul yang jumlah dari lintasannya tidak bisa lagi dibangkitkan (jika ditambah barang lagi kedalam alat pengangkut maka beratnya akan melebihi daya angkut) akan dibunuh.

(1) = 12 + 5*(16-2) = 82

(2) = 15 + 6*(16-5) = 81

(3) = 50 + 6*(16-10)=86

(4) = 10 + 6*(16-5)=76

    Dari simpul-simpul yang telah dibangkitkan dan dihitung cost nya, maka diperoleh bahwa simpul 4 lah yang memiliki cost tertinggi oleh karena itu maka simpul 4 akan di perluas lagi. Simpul 6 ,7,8 akan dibangkitkan sebagai perluasan dari simpul 4 dengan barang yang mungkin dimasukan kedalam alat pengangkut adalah barang ke 1,2 dan 4. kemudian kita akan mengkitung cost dari simpul 6,7dan 8.

(5) = (50+12) + 3*(16-10-2) = 74

(6) = (50+15) + 6*(16-10-5) = 71

(7) = (50+10) + 6*(16-10-5) = 66

Read More

  

Implementasi Algoritma Divide and Conquer pada Sorting dan Searching

Nama : Ahmad Januar A

Npm : 19312162

Mata Kuliah   : Analisis dan Strategi Algoritma

Alamat Web Universitas    : https://teknokrat.ac.id/

Alamat Web Fakultas        : http://ftik.teknokrat.ac.id/

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.

Read More

PENGERTIAN MULTIMEDIA

 

Pengertian Multimedia

Secara bahasa, multimedia terdiri dari dua kata, yaitu multi dan media. Multi banyak, sedangkan media artinya adalah sesuatu yang digunakan untuk menyampaikan pesan (perantara). jadi Pengertian multimedia adalah perantara pesan yang terdiri lebih dari 1 elemen atau banyak.

Dalam definisi lain, Multimedia adalah sarana komunikasi yang mengintegrasikan teks, grafik, gambar diam dan bergerak, animasi audio, dan media lain. Kombinasi elemen tersebut dapat ditampilkan, disimpan, dikirim, dan diproses dengan sebuah perangkat tertentu. 

Pengertian Multimedia Menurut Para Ahli

• Menurut McCormick (1996), Multimedia adalah kombinasi tiga elemen, suara, gambar, dan
• Menurut Rosch (1996), Multimedia sebagai kombinasi dari komputer dan video.
• Menurut Gumelar (2014), Multimedia adalah penggunaan komputer untuk menyajikan dan menggabungkan teks, animasi, suara, gambar dan video dengan tools (alat bantu) dan link sehingga pengguna dapat melakukan navigasi, interaksi, berkarya dan berkomunikas

Sesuai dengan namanya, suatu media dapat dikatakan multimedia jika terdiri dari 2 atau lebih elemen. Sebagai contoh, sebuah brosur dapat dikatakan multimedia karena ia terdiri dari elemen teks dan gambar.

Sebuah video klip dapat dikatakan media karena terdapat unsur suara, gambar atau juga teks. Ini berbeda dengan misalnya rekaman suara kaset. Ia tidak bisa dikatakan multimedia karena hanya mengandung 1 elemen, yakni suara.

Fungsi Multimedia

Sebuah riset dari CTR (Computer Technology Research) memberikan gambaran baru tentang ingatan manusia yang berhubungan dengan komunikasi. Orang lebih mudah mengingat informasi berupa audio yang didengarkan, daripada citra visual yang dilihatnya.

Orang hanya mampu mengingat sekitar 20% informasi yang pernah dilihatnya. Di sisi lain, jika informasi tersebut diperoleh melalui pendengaran, kemampuan memori manusia untuk mengingatnya bisa mencapai 30%.

Ini berarti manusia akan lebih mudah mengingat informasi yang disampaikan dalam bentuk kombinasi antara audio dan visual. Hasil riset CTR juga menyimpulkan bahwa orang cenderung bisa mengingat sebanyak 50% informasi yang diperolehnya dari mendengar sekaligus melihat.

Hasil riset tersebut mengungkapkan bahwa multimedia berfungsi utama sebagai sarana menyampaikan informasi. Multimedia  menjadikan komunikasi berjalan lebih efektif daripada metode-metode klasik yang selama ini dipakai, terutama dalam hal komunikasi massal.

Manfaat Multimedia

Multimedia kini telah merambah ke segala aspek kehidupan. Perkembangan teknologi digital turut mendukungnya. Kemajuan ini memberikan manfaat luar biasa. Multimedia dimanfaatkan di segala bidang untuk berbagai keperluan, di antaranya..

1. Sarana Informasi Umum

Instansi pelayanan publik lebih mudah menyebarkan informasi dengan multimedia. Hanya memerlukan infrastruktur perangkat yang memadai untuk dipasang di lokasi strategis. Di mana publik bisa langsung mengakses dan memperoleh informasi dengan mudah.

Multimedia mulai banyak ditemukan di berbagai tempat, seperti hotel, stasiun, bandara, pusat perbelanjaan, dan objek wisata tertentu. Tersedia perangkat multimedia yang menyebarkan informasi umum, tanpa pengunjung harus mendatangi saluran khusus.Penerapan ini dapat memangkas waktu dan mengurangi pengeluaran untuk personel bagian informasi. Meski masih akan diperlukan tenaga khusus untuk menyampaikan informasi yang lebih mendetail.

2. Media Pembelajaran

Di sekolah, multimedia akan menjadi media pembelajaran yang efektif. Selama ini metode pengajaran dianggap monoton dan membosankan. Dengan sarana multimedia, ilmu dapat disampaikan secara lebih menarik sehingga anak didik mudah mengingatnya.

Salah satu contoh penggunaan multimedia adalah pada tugas presentasi. Di mana peserta didik juga menggunakan media interaktif untuk mempresentasikan hasil belajar menggunakan laptop dan proyektor.

Di sisi lain, multimedia pun menjadi sarana yang tepat untuk mengetahui minat peserta didik. Peserta didik memiliki kebebasan dalam memilih bidang kegemarannya, belajar sesuai kehendaknya, sehingga lebih aktif mendapatkan pendidikan.Meskipun begitu, multimedia tak lantas menghilangkan peranan para pendidik. Peserta didik yang aktif masih membutuhkan bimbingan dan arahan dari guru dan orang tua, agar mereka memperoleh pembelajaran yang positif.

3. Memajukan Ilmu Kesehatan

Beberapa tahun yang lalu, seorang ibu hamil baru bisa mengetahui secara pasti jenis kelamin jabang bayinya setelah lahir. Namun dengan perkembangan multimedia di bidang kesehatan, fenomena tersebut kini malah menjadi hal yang langka.

Penemuan peranti pemindai, USG, membuat dokter dapat mengetahui kondisi janin dalam kandungan. Salah satunya dapat digunakan untuk mengetahui jenis kelamin bayi. Inilah salah satu contoh pemanfaatan multimedia di ranah medis dan kesehatan.

Peranti USG bukan satu-satunya perangkat multimedia yang dimanfaatkan dalam kedokteran. Pemindai X-ray adalah yang lainnya, di mana menjadi sarana penting bagi dokter untuk mendiagnosis gangguan kesehatan pada pasiennya.

Berbagai penemuan penting berbasis multimedia di bidang kedokteran memudahkan tenaga medis dalam pemeriksaan kesehatan. Sehingga kemudian tenaga medis bisa menentukan penanganan paling tepat untuk para pasien. 

Komponen Multimedia

Multimedia menggabungkan berbagai jenis komponen di dalamnya. Komponen tersebut dibagi menjadi dua jenis berdasarkan prosesnya, yaitu komponen penyusun dan komponen pengoperasian. Berikut uraian singkat tentang komponen-komponen tersebut.

1. Komponen Penyusun

Komponen penyusun meliputi elemen-elemen yang biasa digunakan dalam pembuatan sajian multimedia. Di antaranya teks, grafik, suara, foto, gambar diam dan gambar bergerak, serta animasi.

2. Komponen Pengoperasian

Komponen pengoperasian merupakan perangkat yang dipakai dalam membuat, mengontrol, memutar, dan menampilkan karya multimedia. Di antaranya komputer, software, layar multimedia, speaker, jaringan internet, cakram CD, DVD, dan sebagainya.

Jenis Jenis Multimedia

Ada banyak klasifikasi pada multimedia, sehingga jenisnya pun menjadi bermacam-macam. Berdasarkan aksesnya, multimedia dibagi menjadi dua jenis, yaitu multimedia online dan offline. Perbedaannya hanya terletak pada penggunannya yang membutuhkan jaringan internet.

Jika dilihat dari metode penyajiannya, multimedia dibedakan menjadi lima jenis. Di antaranya multimedia berbasis kertas (buku dan majalah), cahaya (slideshow dan transparansi), suara (radio dan tape), gambar bergerak (televisi), dan digital (komputer dan ponsel pintar).

Pengelompokkan multimedia menggunakan variabel yang cukup bervariasi. Berdasarkan sifat penggunaannya, komunikasi multimedia dikelompokkan dalam tiga tipe, yaitu multimedia interaktif, hiperaktif, dan linier. Berikut penjelasan masing-masing jenis tersebut.

• Multimedia interaktif. Adalah jenis multimedia yang memungkinkan pengguna dapat mengontrol komponen-komponen di dalamnya. Tipe ini lebih mengutamakan personalisasi pemakain multimedia sesuai keinginan penggunanya.
• Multimedia hiperaktif. Merupakan jenis komunikasi multimedia yang memanfaatkan hubungan antara setiap komponen multimedia. Sifatnya juga interaktif, sehingga pengguna dapat memilih asupan informasi sesuai selera melalui tautan yang tersedia.
• Multimedia linier. Adalah jenis multimedia yang bersifat tidak interaktif. Artinya pengguna hanya bisa menikmati sajian informasi secara linier, tanpa memiliki kesempatan untuk mengontrolnya sendiri.

Sejarah Multimedia

Sebenarnya, istilah multimedia berasal dari dunia teater. Sebuah teater disebut multimedia jika menampilkan beberapa jenis media. Di antaranya seni drama yang diperankan manusia, serta lukisan, instalasi, dan musik yang berperan sebagai latar cerita.

Multimedia tidak bisa lepas dari berbagai penemuan perangkat komunikasi. Seperti Gutenberg and Caxton yang pertama kali memperkenalkan media cetak pada abad ke-15. Kemudian dilanjutkan pada abad ke-19, yaitu masa terpenting bagi perkembangan dunia komunikasi.

Matthew Brady mengejutkan publik dengan pameran fotografinya sekitar 1862. Lalu ditandai dengan penemuan telegraf oleh Samuel Morse, telepon oleh Alexander Graham Bell, radio oleh Gugliemo Marconi, serta ide awal televisi oleh John Logie Baird dan Lumiere bersaudara.

Revolusi televisi sekitar tahun 1940-an membawa multimedia ke arah lebih serius. Apalagi, ketika era komputer dan internet mulai berlangsung sejak tahun 1960-an.

Teknologi ini memungkinkan manusia untuk menggabungkan berbagai macam media dengan satu perangkat.

Internet telah menjadi raksasa media komunikasi saat ini. Multimedia akhirnya memperoleh cakupan wilayah penggunaan tak terbatas. Dan hingga kini masih belum ada tanda-tanda munculnya teknologi pengganti yang lebih mutakhir.

Read More

  

Pengertian Monitor | Sejarah, Fungsi, dan Jenisnya

Nama  : Ahmad Januar A

Npm    : 19312162

Kelas   : IF 21 B

Universitas Teknokrat Indonesia

FTIK Teknokrat – Kampusnya Sang Juara

Perangkat monitor menjadi kebutuhan utama manusia dalam berinteraksi dengan komputer. Bahkan semua data yang Anda input ke dalam komputer akan terbaca karena adanya monitor. Selain itu, saat mendokumentasikan foto, merekam video, pasti akan membutuhkan media untuk menampilkan gambar maupun video tersebut. Monitor akan menghasilkan output tampilan berupa sajian grafis dan sejenisnya dari data yang telah di input.

Secara umum monitor sudah berevolusi dari tahun ke tahun dalam segi kualitas gambar, perkembangan bentuk, dan jenisnya. Jenis monitor juga dibuat sedemikian rupa mengikuti perkembangan teknologi untuk menyesuaikan kebutuhan pengguna komputer. Bagaimana, apakah Anda sudah dapat membayangkan jenis dan pentingnya monitor? Untuk mengulas lebih jauh, silakan simak penjelasannya berikut ini!

Apa itu Monitor?

Sumber Gambar : Unsplash.com

Monitor adalah perangkat display yang bekerja untuk menginterpretasikan dan menampilkan sinyal output grafis dari kartu grafis (VGA Card) ke layar komputer. Perangkat display ini memungkinkan Anda untuk melihat antarmuka tampilan dan berinteraksi dengan komputer dengan bantuan periferal seperti mouse maupun keyboard.

Pada umumnya monitor tampak seperti televisi, namun kedua perangkat ini berbeda. Layar televisi bekerja dengan menampilkan data dari sinyal siar, sedangkan monitor akan menampilkan data dari sinyal siar sekaligus data digital yang diterima melalui kartu grafis (VGA Card). Sebenarnya Anda dapat menggunakan layar TV sebagai monitor, tetapi hasil dan kualitas yang ditampilkan tidak sebaik monitor asli. Hal ini karena TV tidak dapat mereproduksi warna yang optimal dan cukup melelahkan mata ketika bekerja dengan TV.

Monitor dirancang secara khusus dengan antarmuka visual yang optimal untuk komputer. Perangkat display atau monitor terdiri dari tampilan visual, sirkuit, casing, dan Power Supply. Tampilan monitor modern yang banyak digunakan di antaranya, LCD dan LED, sebelumnya monitor menggunakan tabung sinar katoda (CRT). Output warna yang ditampilkan monitor juga sangat baik, Anda dapat menghubungkan monitor ke komputer melalui konektor melalui VGA, DVI, HDMI, DisplayPort, USB-C, LVDS, dan konektor lainnya. Sehingga pengguna komputer dapat memperoleh visual yang berkualitas tajam dan realistis.

Sejarah Perkembangan Monitor

Tahun	Riwayat
1964	Munculnya teknologi pendahulu layaknya layar bawaan monitor CRT, yaitu Mesin Uniscope 300.
1965	E. A. Johnson berhasil menciptakan teknologi touch screen (layar sentuh) pada tahun 1965.
1973	Pada tanggal 1 Maret 1973, perusahaan komputer Xerox Alto merilis monitor komputer pertama kali. Monitor ini menggunakan teknologi CRT dengan tampilan monokrom
1975	George Samuel Hurst mengembangkan monitor layar sentuh resistif ‘resistive touch screen’ yang pertama pada 1975. Namun tidak diproduksi dan digunakan lagi hingga tahun 1982.
1976	Munculnya Komputer Apple I dan Sol-20 sebagai komputer pertama dengan port audio bawaannya.
1977	James P. Mitchell mengembangkan teknologi monitor LED, namun monitor jenis ini belum bisa di perjual belikan sekitar 30 tahun-an.
1977	Apple II, dirilis pada Juni 1977, dengan tampilan warna pada monitor CRT.
1987	Muncul monitor VGA pertama yaitu IBM 8513, yang dirilis oleh IBM.
1989	Standar SVGA secara resmi di gunakan untuk tampilan komputer oleh VESA pada tahun 1989.
1980-an	Monitor CRT warna diizinkan menampilkan layar dengan resolusi 1024 x 768 pada akhir 1980-an.
1990-an	Pada pertengahan 1990-an, Eizo Nanao Technologies memproduksi dan merilis monitor LCD pertama sebagai komputer desktop yaitu Eizo L66.
1997	Perusahaan teknologi, Apple, IBM, dan Viewsonic mulai mengembangkan monitor LCD warna dengan resolusi dan kualitas yang memadai, melebihi monitor CRT.
1998	Pada tahun 1998, Apple memproduksi Apple Studio Display menjadi salah satu monitor LCD warna pertama dan terjangkau untuk komputer desktop.
2003	Monitor LCD terjual lebih banyak (outsold) dari monitor CRT untuk pertama kalinya pada tahun 2003. Pada tahun 2007, monitor LCD secara konsisten mengungguli monitor CRT, dan menjadi jenis monitor komputer yang paling populer.
2006	Pada tahun 2006, Jeff Han memperkenalkan monitor komputer interface-free berbasis sentuhan, pertama kali di TED.
2009	Perusahaan NEC memproduksi pertama kali monitor LED untuk komputer desktop. Mereka merilis monitor ini sebagai MultiSync EA222WMe, yang rilis pada akhir 2009.
2010	AMD dan Intel, bersama beberapa produsen monitor komputer mengumumkan untuk mengurangi dukungan untuk VGA mulai dari Desember 2010.
2017	Monitor LCD ‘Touch screen’ mengalami penurunan harga, dan dibuat terjangkau untuk konsumen rata-rata pada tahun 2017. Monitor layar sentuh ukuran 20 hingga 22 inci turun seharga di bawah $ 500.

Fungsi dan Manfaat Monitor

Sumber Gambar : Unsplash.com

• Sebagai media output tampilan yang berupa teks, gambar, video, dan informasi lainnya.
• Sebagai media pengguna dalam memilih opsi fungsi atau fitur dari sistem dan aplikasi pada komputer.
• Untuk menunjukkan tampilan pekerjaan apapun yang sedang dilakukan pengguna di komputer melalui perangkat input apapun.
• Bekerja sama dengan kartu video atau kartu grafis komputer. Ketika kartu grafis mengubah informasi biner dari 1s dan 0s menjadi sebuah gambar, maka monitor akan terhubung secara langsung untuk menampilkan gambar-gambar tersebut.

Jenis – Jenis Monitor

Sumber Gambar : Unsplash.com

Beberapa jenis monitor yang dapat di ketahui saat ini adalah sebagai berikut:

1. Monitor CRT

Monitor CRT (Cathode Ray Tube) adalah salah satu monitor komputer tertua dan tradisional. Monitor ini disebut tabung sinar kathoda yang digunakan sejak tahun 1950-an, dan masih ada yang menggunakannya saat ini. Monitor CRT menggunakan balok elektron untuk menerangi area layar yang berbeda, balok tersebut bergerak bolak-balik secara cepat untuk memperbarui gambar layar berkali-kali dalam tiap detik.

Jenis monitor ini diperjual belikan dengan harga relatif murah dan terjangkau. Segi desain dan bentuk dibilang cukup rumit dan berat, karena itu saat ini sudah mulai tergantikan dengan kebutuhan monitor berbentuk tipis dan nyaman seperti halnya monitor LCD.

Kelebihan

• Merupakan monitor dengan teknologi usang, sehingga dapat menemukan dan membeli dengan harga yang mudah atau gratis.
• Tidak memungkinkan monitor CRT untuk ‘dead pixel’.
• Sudut pandang tampilan luas, sehingga dapat melihat gambar dengan jelas hampir dari semua sudutnya.

Kelemahan

• Berbentuk tabung besar, berat, dan menempati banyak ruang.
• Boros listrik atau daya dan menghasilkan banyak radiasi.
• Tampilan monitor dapat berkedip beberapa saat karena laju penyegaran, yang memungkinkan mengganggu mata.

2. Monitor LCD

Monitor LCD (Liquid Crystal Display) atau dikenal dengan monitor panel datar merupakan monitor yang menggunakan lapisan piksel untuk menghasilkan gambar. Selain itu layar LCD menggunakan elektroda transparan untuk mengontrol array piksel serta memperbarui gambar. Desain dan bentuk monitor ini jauh lebih tipis daripada CRT. Ada dua jenis teknologi LCD meliputi, Active matrix technology dikenal dengan teknologi TFT (Thin Film Transistor) dan Passive matrix technology.

Kelebihan

• Ringkas, ringan, tipis, dan hemat ruang, sesuai kebutuhan modern untuk desktop.
• Membutuhkan sedikit daya daripada monitor CRT tradisional.
• Layar matte pada jenis layar LCD tidak silau seperti yang terdapat pada monitor CRT.
• Kedipan layar cukup minimal.
• Tidak terjadi masalah dengan pembakaran gambar.

Kelemahan

• Harga jual relatif mahal daripada monitor CRT.
• Ketika melihat tampilan dari sudut gambar pada monitor akan terlihat samar.
• Piksel mati atau ‘dead pixel’ kemungkinan dapat terjadi karena buruknya produksi kristal cair.
• Karena menggunakan filter polarisasi, arah cahaya cukup terbatas dan mengganggu masalah sudut pandang pengguna.

3. Monitor LED

Monitor LED (Light Emitting Diode) merupakan salah satu monitor terbaru. Pada dasarnya monitor LED tampak seperti LCD, namun LED tidak menggunakan lampu latar neon, tetapi lampu LED atau dioda pemancar cahaya. Monitor LED adalah monitor yang menggunakan dioda pemancar cahaya, yang memberikan cahaya neon terang dan konsumsi daya minimal.

Kelebihan

• Menggunakan daya yang cukup sedikit daripada monitor LCD. Sangat ideal untuk perangkat yang sensitif energi seperti laptop dan tablet.
• Kualitas gambar yang dihasilkan lebih baik, bahkan ketajaman dan warna lebih unggul daripada monitor LCD.

Kelemahan

• Harga yang cukup mahal, karena biaya manufaktur yang tinggi.

4. Monitor OLED

Monitor OLED (Organic Light Emitting Diode) merupakan salah satu monitor yang terbuat dari karbon dan hidrogen. Monitor OLED dapat memancarkan cahaya hasil ciptaan sendiri dengan tidak memerlukan sumber cahaya lain atau backlight.

Kelebihan

• Lebih hemat daya karena tidak membutuhkan backlight seperti LED.
• Terbuat dari bahan organik yang sangat ramah lingkungan.
• Tampilan baru dan menarik, layar didesain dari warna dan kaca yang transparan yang cukup tipis sehingga ringan dan fleksibel.
• Jangkauan warna yang terang dan memiliki tampilan sudut pandang yang luas. Monitor OLED dapat memancarkan cahaya secara langsung.

Kelemahan

• Harga cukup mahal.
• Masa bertahan bahan organik relatif pendek yaitu sekitar 14.000 jam dibandingkan dengan monitor datar lainnya. Namun, sejak 2007 lalu ada perkembangan masa bertahan OLED hingga 198.000 jam, dari sebelumnya.
• Kandungan bahan organik OLED dapat rusak jika terlalu lama di tempat lembab atau bahkan terkena air.

5. Monitor PDP (Panel Display Plasma)

Monitor plasma di kenal mirip dengan monitor LCD. Monitor jenis plasma ini menggunakan sel-sel kecil gas yang bermuatan untuk membuat gambar. Sel-sel ini mirip seperti bola lampu neon yang setiap selnya dapat menciptakan iluminasi sendiri dan mampu memberikan kontras yang kuat. Tipe monitor plasma menggabungkan konsep LCD dan CRT untuk kualitas gambar yang baik dengan sudut pandang yang luas.

6. Monitor QLED

Monitor QLED (Quantum Light Emitting Diode) merupakan monitor pengembangan dari Samsung yang mengedepani TV LED / LCD. Untuk menjunjung kualitas HDR Samsung merilis monitor QLED. QLED menjadi teknologi pada TV QLED yang dapat memberikan warna dinamis dan berkualitas tinggi. Dengan teknologi Quantum dot tersebut TV QLED mampu mencapai kecerahan dan warna tertinggi sekitar 1.500 hingga 2.000 nit.

Kesimpulan,

Setelah mempelajari apa itu monitor dapat disimpulkan bahwa perangkat monitor digunakan untuk melihat antarmuka sistem operasi dan mengoperasikannya dengan perangkat tambahan lainnya. Komputer dapat bekerja sesuai sistem komputasi tanpa adanya monitor, namun sebagai pengguna komputer Anda tidak dapat melihat apa yang dilakukan komputer dengan program yang dijalankan. Monitor juga menampilkan antarmuka saat membuka program dan memungkinkan Anda untuk berinteraksi dengan komputer menggunakan periferal tambahan seperti keyboard dan mouse.

Apa itu monitor?

Monitor adalah perangkat display sebagai media output yang menampilkan sajian grafis atau gambar dari pengolahan data kartu grafis. Sederhananya, monitor merupakan perangkat yang digunakan untuk menampilkan data pada komputer.

Kapan pertama kali monitor komputer ditemukan?

Monitor komputer pertama di temukan pada sebuah sistem komputer Xerox Alto sejak 1 Maret 1973.

Apakah komputer dapat bekerja tanpa monitor?

Untuk dapat bekerja, komputer tidak memerlukan monitor. Namun, tanpa adanya monitor pengguna akan kesulitan berinteraksi dengan antarmuka komputer. Dengan perangkat output atau monitor ini pengguna juga dapat mengoperasikan sistem operasi dan menentukan metode yang dilakukan komputer.

Itulah ulasan lengkap mengenai pengertian monitor, sejarah, fungsi, dan jenis-jenisnya. Bagikan artikel ini ke sosial media Anda supaya lebih berguna dan bermanfaat. Jika ada yang belum di mengerti, silakan bertanya melalui kolom komentar di bawah ini Terima Kasih!

Read More