Jumat, 31 Desember 2010

PENCARIAN dalam Algoritma Pemograman

PENCARIAN 
Pencarian merupakan sebuah algoritma dasar yang sering diperlukan dalam pembuatan program .
Algoritm Pencarian adalah Algoritma yang mengambil input berupa persoalan dan mengembalikan penyelesaian (nilai yang ditemukan) atau nilai yang dicari dalam inputan .

PENCARIAN SEKUENSIAL  
Pencarian Sekuensial adalah proses membandingkan setiap elemen larik (array) satu persatu dengan nilai yang dicari secara beruntun , mulai dari elemen pertama sampai elemen yang dicari sudah ditemukan atau sampai seluruh elemen sudah diperiksa .

Pada dasarnya, pencarian ini hanya melakukan pengulangan dari 1 sampai
dengan jumlah data.  Pada setiap pengulangan, dibandingkan data ke-i dengan yang
dicari.  Apabila sama, berarti data telah ditemukan.   Sebaliknya apabila sampai akhir
pengulangan tidak ada data yang sama, berarti data tidak ada.  Pada kasus yang paling
buruk, untuk N elemen data harus dilakukan pencarian sebanyak N kali pula.




Di bawah ini merupakan fungsi untuk mencari data menggunakan pencarian
sekuensial.


int SequentialSearch(int x) 
 }
 int i = 0; 
 bool ketemu = false; 
 while ((!ketemu) && (i < Max)){ 81
  if(Data[i] == x) 
   ketemu = true; 
  else 
   i++; 
 { 
 if(ketemu) 
  return i; 
 else 
  return -1; 
  {


PENCARIAN GROVER



Pada persoalan pencarian dengan exhaustive search, diberikan suatu fungsi f(x),x=0,1...(N-1), dimana f(x) adalah fungsi yang akan selalu menghasilkan 0 untuk semua  x, kecuali satu nilai  x yang akan menghasilkan Tujuan dari persoalan ini  adalah mencari nilai x sehingga f(x) = 1.

Ide dasar dari algoritma pencarian kuantum (algoritma Grover) adalah misalkan ada  N buah status yang berkorespondensi dengan N item dalam suatu daftar tak terurut.  






Peluang untuk setiap status, bahwa status tersebut adalah yang dicari dalam daftar tersebut adalah 1/N. Dengan prinsip mekanika kuantum, dimungkinkan untuk meningkatkan nilai peluang status yang dicari karena pengaruh status yang lain (status yang bukan status yang dicari), sehingga pada akhirnya status yang dicari akan memiliki nilai peluang tertinggi. Prinsip mekanika kuantum juga memungkinkan untuk berada dalam 
lebih dari satu status, dan melakukan lebih dari satu komputasi dalam waktu yang bersamaan.  



Pada pencarian dengan probabilitas pada komputer klasik, peluang untuk status yang dicari akan meningkat sebesar 1/N setiap kali iterasi pada kalang for, sehingga dengan iterasi sebanyak N kali, akan ditemukan solusi dengan nilai peluang tertinggi. Kompleksitas algoritma ini adalah O(N).Berikut ini adalah pseudo code nya:



kamus
function random(input N : integer)→ integer   
{random(N) mengembalikan nilai acak antara 0 
sampai (N-1) } 


function f(input r:integer) → integer 
{f(r) adalah fungsi boolean yang 
mengembalikan 1 jika r adalah solusi yang 
dicari dan 0 jika bukan solusi} 


i,r,answer,N : integer 
        
algoritma
  
   input ← N 
   answer ← -1  
   r ← random(N)  
   for i = 0 to N do  
      if f(r) = 1 then
 answer = r  
      r ← random(N);  
      
   output ← answer 







PENCARIAN BINER . 
Sebuah algoritma pencarian biner (atau pemilahan biner) adalah sebuah teknik untuk menemukan nilai tertentu dalam sebuah larik (array) linear, dengan menghilangkan setengah data pada setiap langkah, dipakai secara luas tetapi tidak secara ekslusif dalam ilmu komputer. Sebuah pencarian biner mencari nilai tengah (median), melakukan sebuah pembandingan untuk menentukan apakah nilai yang dicari ada sebelum atau sesudahnya, kemudian mencari setengah sisanya dengan cara yang sama. 


Pencarian Biner (Binary Search) pada array yang sudah terurut


Pencarian Biner (Binary Search) dilakukan untuk :
   memperkecil jumlah operasi pembandingan yang harus dilakukan antara data yang dicari dengan data yang ada di dalam tabel, khususnya untuk jumlah data yang sangat besar ukurannya.
   Prinsip dasarnya adalah melakukan proses pembagian ruang pencarian secara berulang-ulang sampai data ditemukan atau sampai ruang pencarian tidak dapat dibagi lagi (berarti ada kemungkinan data tidak ditemukan).
   Syarat utama untuk pencarian biner adalah data di dalam tabel harus sudah terurut, misalkan terurut menaik.

Entri Populer