Senin, 15 Desember 2014

Searching Pada Java, binary search dan sequential search

Sequential Search

Sequential Search adalah teknik pencarian data dimana data dicari secara urut dari depan ke belakang atau dari awal sampai akhir. berdasarkan key yang di cari.

Kelebihan dari proses pencarian secara sequential ini :
· jika data yang dicari terletak didepan, maka data akan ditemukan dengan cepat. 

Tetapi dibalik kelebihannya ini, teknik ini juga memiliki kekurangan :
· jika data yang dicari terletak dibelakang atau paling akhir, maka akan membutuhkan waktu yang lama   dalam proses pencariannya.
· beban komputer akan semakin bertambah jika jumlah data dalam array sangat banyak. 

Proses:
· Mulai dari awal(atau dari akhir) cek seluruh record dalam array atau list, baca satu persaru
· Temukan record sesuai dengan key yang dicari.
· Proses Searching berhenti karena salah satu alasan.
Ø Success – Found the target key
Ø End of List – No more records to compare 
Diaplikasikan pada Array (sorted &unsorted) atau Linked List.
Algoritma Sequential Search :
1. i ← 0
2. ketemu ←false
3. Selama (tidak ketemu) dan (i < N) kerjakan baris 4
4. Jika (Data[i] = key) maka
5. ketemu ←true
6. jika tidak
7. i ←i+1
8. Jika (ketemu) maka
9. i adalah indeks dari data yang dicari
10. jika tidak
11. data tidak ditemukan 

Binary Search

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. Sebuah pencarian biner adalah salah satu contoh dari algoritma divide and conquer (atau lebih khusus algoritma decrease and conquer) dan sebuah pencarian dikotomi (lebih rinci di Algoritma pencarian).

Algoritma
Penerapan terbanyak dari pencarian biner adalah untuk mencari sebuah nilai tertentu dalam sebuah list terurut. Jika dibayangkan, pencarian biner dapat dilihat sebagai sebuah permainan tebak-tebakan, kita menebak sebuah bilangan, atau nomor tempat, dari daftar (list) nilai.
Pencarian diawali dengan memeriksa nilai yang ada pada posisi tengah list; oleh karena nilai-nilainya terurut, kita mengetahui apakah nilai terletak sebelum atau sesudah nilai yang di tengah tersebut, dan pencarian selanjutnya dilakukan terhadap setengah bagian dengan cara yang sama. Berikut ini adalah pseudocode sederhana yang menentukan indeks (posisi) dari nilai yang diberikan dalam sebuah list berurut, a berada antara left dan right :

Karena pemanggilan fungsi di samping adalah rekursif ekor, fungsi tersebut dapat dituliskan sebagai sebuah pengulangan (loop), hasilnya adalah algoritma in-place:
Pada kedua kasus, algoritma akan berakhir karena paa setiap pemanggilan rekursif atau pengulangan, jangkauan indeks rightdikurang left akan selalu mengecil, dan akhirnya pasti akan menjadi negatif.
Pencarian biner adalah sebuah algoritma logaritmik dan bekerja dalam waktu O(log n). Secara khusus, 1 + log2N pengulangan yang diperlukan untuk menghasilkan jawaban. Hal ini dianggap lebih cepat dibandingkan sebuah pencarian linear. Pencarian biner dapat diimplementasikan dengan rekursi atau iterasi, seperti yang terlihat di atas, walaupun pada kebanyakan bahasa pemrograman akan lebih elegan bila dinyatakan secara rekursif.



Listing Program

import java.util.*;

public class umur2
{
    public static void main (String[]args)
    {
        Scanner input = new Scanner (System.in);
        int a;
        boolean data = false;
        String [] nama = {"Ani","Budi","Septi","Caca","Roka"};
        int [] umur = {7, 10, 8, 12, 5};
               
        System.out.println ("DATA NAMA DAN UMUR ANAK :\nNama\t\tUmur");
       
        for (int x = 0 ; x < umur.length ; x++)
        {
            System.out.println (nama[x]+"\t\t"+umur[x]);
        }
       
        System.out.print ("\nSOAL :\n1. Mencari usia anak yang berusia 8 tahun dari dalam data\n2. Menampilkan nama anak yang usianya lebih dari 10 tahun\n3. Menampilkan nama anak yang usianya kurang dari 10 tahun\n\nMasukkan nomor soal : ");
        int soal = input.nextInt();
       
        switch (soal)
        {
            case 1 :
                int angka = 8;
                System.out.print ("\nYang berusia "+angka+" tahun : ");
                for (a = 0 ; a < umur.length ; a++)
                {
                    if (umur[a] == angka)
                    {
                        data = true;
                        System.out.print (" "+nama[a]+", ");
                    }
                }
            break;
           
            case 2 :
                System.out.print ("\nYang berusia lebih dari 10 tahun : ");
                for (a = 0 ; a < umur.length ; a++)
                {
                    if (umur[a] > 10)
                    {
                        data = true;
                        System.out.print (""+nama[a]+" ");
                       
                    }
                }
       
            break;
           
            case 3 :
                System.out.print ("\nYang berusia kurang dari 10 tahun : ");
                for (a = 0 ; a < umur.length ; a++)
                {
                    if (umur[a] < 10)
                    {
                        data = true;
                        System.out.print (""+nama[a]+", ");
                    }
                }
       
            break;
           
            default :
                System.out.println ("Pilihan salah.");
        }
       
    }
}

Printscreen (Output)

 Mencari usia anak yang berumur 8 tahun
2.      Menampilkan nama anak yang berusia lebih dari 10 tahun


3.      Menampilkan nama-nama anak yang usianya kurang dari 10 tahun.

Pembahasan

Program ini adalah salah satu contoh dari Sequential Search dimana program ini akan mencari nama anak dengan kondisi umur yang telah ditentukan berdasarkan data yang telah disediakan. Algoritma program :
Ø  Inisialisasi variabel data yang memiliki nilai yang salah
Ø  Buat array bertipe string yang berisi nama anak
Ø  Buat array bertipe integer yang berisi umur anak
Ø  Tampilkan data kedua array tersebut sebagai soal untuk user
Ø  Gunakan switch case untuk memilih apa yang akan dilakukan program
Ø  Disetiap case, lakukan perulangan sehingga data yang ditemukan sesuai dengan yang diperintahkan.
Ø  Apabila data ditemukan rekam secara keseluruhan
Ø  Lalu tampilkan semua nama anak yang ditemukan
Flowchart




 Penjelasan : 

Pertama mendeklarasikan variabel array dengan nama “nama” bertipe data string. Lalu mendeklarasikan variabel array dengan nama “umur” bertipe data integer. Setelah itu melakukan perulangan for loop untuk menampilkan data kedua buah array agar tampil semua datanya.
Kita lalu menggunakan variabel soal sebagai switch untuk memilih case mana yang akan dijalankan pada program yang akan diinput oleh user.
Pada case 1, kita menggunakan perulangan for untuk mengecek nilai setiap indeks array umur untuk dibandingkan dengan umur yang ingin dicari user. Jika umur yang dicari user dapat ditemukan, maka program akan mencetak nama anak yang memiliki usia itu. Dan jika tidak bisa ditemukan, program akan memberitahu bahwa usia yang user cari tidak bisa ditemukan.

Pada case 2, kita menggunakan perulangan for untuk mengecek nilai setiap array umur apakah memenuhi syarat. Syarat dari case 2 adalah umur anak harus lebih dari 10. Meskipun program sudah menemukan satu anak yang umurnya memenuhi syarat, tetapi untuk case 2, program akan mengecek seluruh array tanpa terkecuali. Setiap hasil pengecekan sesuai dengan syarat, program akan mencetak nama anak yang memiiki usia tersebut. Setelah pengecekan selesai sampai data terakhir, barulah program tersebut berhenti.
Pada case 3, kita menggunakan perulangan for untuk melakukan pengecekan nilai-nilai array dalam variabel umur apakah memenuhi syarat atau tidak. Syarat untuk case 3 ini adalah nilai array umur harus lebih dari 10. Apabila ada array yang sudah memenuhi syarat tersebut, maka program tetap terus akan melakukan pengecekan terhadap seluruh nilai array umur. Setiap ada nilai yang memenuhi syarat, program akan mencetak nama anak yang usianya memenuhi syarat.

Default digunakan apabila user menginputkan pilihan selain case yang telah disediakan. Dalam program ini, yang dilakukan adalah mencetak pernyataan bahwa user menginputkan pilihan yang salah.

Definisi & Pengertian Parity Check

Definisi & Pengertian Parity Check - Apa itu Parity check? Bagaimana Cara kerja dari sistem parity check itu?


 Dasar Pemikiran Munculnya Parity Check

Ketika sebuah karakter atau data ditransmisikan dari terminal satu ke terminal yang lainnya ( kalo bingung apa itu terminal anggap aja komputer XD ) ,  rata rata data tersebut akan terkirim dengan suksesnya. Nah, yang jadi Pertanyaan bila terjadi sesuatu dengan data itu ditengah perjalanan, sehingga kode biner dari data tersebut berubah, bagaimanakah terminal tertuju tahu bahwa data tersebut tidak valid (Tidak sama dengan data yang sesungguhnya dikirm)?

Untuk menanggapi permasalahan yang seperti itu Dikenalkanlah Gambaran Umun yang Dinamakan Dengan " Metode Pendeteksian Error " atau yang kalau dibahasa inggriskan menjadi " Error Detection Methods ". Nah, Parity check sendiri adalah 1 dari demikian banyak metode pendeteksian error.


  Konsep Umum & Cara kerja Parity check

Konsep umum dari parity check adalah sebuah sistem yang membuat pihak terminal tertuju tahu bahwa data yang iya terima tersebut sama atau tidak dengan data yang dikirim oleh terminal pengirim.

Caranya?  Pertama tama pihak pengirim  akan menambahkan 1 bit tambahan ( Atau yang Lebih dikenal dengan nama Parity Bit ) pada data, untuk menggambarkan karakteristik dari data tersebut. Nilai dari bit parity ( 1 atau 0 ) tidak diperoleh secara sembarangan ( Proses penentuan nilai bit parity akan dibahas pada sub bab III ).

Lanjut, dalam proses pentransmisiannya data tadi dikirim bersamaan ( data kita dan parity bitnya ) dan kita anggap data dapat terkirim dengan suskses. Pada Terminal Penerima Data kita dibaca dan Di dekodisasi ( di definisi kan ulang ) dengan cara yang sama seperti saat kita menentuan nilai parity bit di sisi pengirim. Lalu Hasil dekodisasi tadi dibandingkan dengan parity bit yang tadi sengaja dibawakan oleh pengirim. Gampangannya apabila hasil pembacaan ( Dekodisasi ) data terkirim sama dengan Parity bitnya maka data tersebut Dapat dianggap benar. Dan apabila diperoleh perbedaan nilai antara hasil dekodisasi dengan parity bitnya maka data dapat di klasifikasikan sebagai data yeng error, Lebih lanjut terminal penerima akan mengirimkan request pada terminal pengirim untuk mengirimkan ulang data yang terbaca error tadi. Masih bingung?? Tenang, contoh kasus akan dibeberkan pada ahir bab konsep ini.


 Menentukan Nilai Parity Bit

Penentuan nilai parity bit ( apakah 1 atau 0 ) dilakukan dengan Meng-XOR kan semua bit yang ada pada data sepasang sepasang, hasil ahir dari Peng-XOR an seluruh bit ini lah yang dijadikan acuan untuk menentukan nilai dari parity bit yang akan ditambahkan ( jadi, belum tentu hasil peng-XOR an langsung dijadikan sebagai nilai dari parity bit ).

Masih ingat XOR ? Perhatikan tabel eksitasi / truth tabel berikut :


 ( Kiri = Tabel XOR ; Kanan = ilustrasi XOR Gate )

Seandainya saya mempunyai data yang berupa 1 karakter semisal huruf "M", yang menurut ASCII sama dengan 1011001, maka proses Peng-XOR annya = ((((((1 XOR 0) XOR 1) XOR 1) XOR 0) XOR 0) XOR 1) yang menghasilkan hasil ahir = 0. Bingung?? amati pencacahan dibawah ini:


1 XOR 0 = 1
1 XOR 1 = 0

0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 0 = 1
1 XOR 1 = 0



Jika sudah paham betul prosesnya cukup dihafalkan saja hasil ahirnya, jika bit 1 pada data berjumlah genab maka keluaran ahirnya pasti "0", jika ganjil maka "1"

Gambar Skema Peng-XOR an data 7 bit :



B0 adalah bit pertama B1 adalah bit kedua begitu seterusnya

OK, setelah kita tadi dapatkan nilai bit dari hasil dari hasil peng-XOR-an data, barulah kita akan menentukan nilai dari parity bit data kita. Ada 2 metode yang sering digunakan yaitu Even Parity Bit dan Odd Parity Bit. Dalam Event Parity Bit, nilai parity bit sama dengan hasil peng-XOR an. sedangkan dalam Odd Parity Bit, Nilai parity bit merupakan komplement( kebalikan ) dari hasil peng-XOR an data.


 Study Kasus Parity Check ( Contoh Kongkret )

Budi dan Anto sedang chatingan satu sama lain, jelas keduanya sedang bercakap cakap dengan metode berkirim teks. Diasumsikan Metode Pendeteksian Error = Parity Check & Terminalnya Character-Oriented Transmission ( G usah bingung, g Ngerti juga GPP ).

Budi Mengetik Kata : Aku
Dalam Kode ASCII Berarti
A =  1000001
k =  1101011
u =  1010111

Dalam terminal Pengirim, Kata "Aku" Dianalisa Perkarakter "A" lalu "k" lalu "u". Dari masing masing huruf itu Masing masing ditambahkan dengan parity bit nya ( Asumsikan kita menggunakan Even Parity Bit ) Maka Data Akan berubah menjadi:

(A = 1000001  Setelah Di XOR kan, Hasilnya "0"  Karena kita menggunakan metode Even Parity Bit maka Parity Bitnya Bernilai "0", maka Kode biner huruf "A" ditambah menjadi A = 10000010)

A = 10000010
k =  11010111
u =  10101111

Data lalu dikirim dengan format berikut:
10101111_11010111_10000010


Karena suatu hal entah itu attenuasi atau distorsi dan noise noise lainnya Bit Bit tadi ada yang berubah dalam perjalanannya menjadi:
10101111_11010111_11000010

Pada Sisi Penerima Data tersebut dibaca sebagai kata "Cku" bukan "Aku" ( Lihat Tabel ASCII ), bila tanpa Metode Pendeteksian Error maka data tersebut akan dianggap valid dan tentu saja Anto menjadi Kebingungan melihat Tulisan Budi tesebut.

Mekanisme Pembacaannya:
1. Deret bit 1100001 Di dekodisasi sehingga menghasilkan bit "1" ( Tanpa Melibatkan Parity Bit nya )
2. Penerima membandingkan Hasil dekodisasi tadi dengan Parity bitnya. "1" dan "0", Karena tidak sama Maka Karakter Terdeteksi Error
3. Penerima Meminta data dikirim ulang, berharap data tidak rusak lagi.
4. Proses Diulang sampai data dianggap benar
 
 http://www.sentra-edukasi.com/2009/10/definisi-pengertian-parity-check.html#.VI7bQskVQgA