Global

Global

Senin, 04 April 2011

Sequential search dan Binary search

1.SEARCHING IN COLLECTIONS
Artikel berikut ini akan membahas penerapan algoritma pencarian yang berbeda di Jawa untuk menemukan elemen dalam koleksi.

Pencarian dalam koleksi ini dilakukan untuk menjawab pertanyaan:

     *Apakah unsur yang ada dalam koleksi
     * Dapatkan elemen dari koleksi
     *Menghapus elemen dari koleksi

Koleksi dalam artikel ini digunakan dalam arti luas dan bukan dalam arti Jawa ketat. Untuk pengumpulan contoh kita melihat array saya akan atau daftar.
2. SEQUENTIAL SEARCH
2.1 Overvieew
Sequential search adalah pendekatan sederhana. Mengingat koleksi Anda mencoba setiap elemen dalam koleksi sampai Anda telah menemukan elemen atau sampai Anda mencapai akhir koleksi.
2.2 Implementation
Sequential Search adalah sangat mudah untuk diimplementasikan.

Buat proyek Java "de.vogella.algorithms.search.sequential" dan sebuah paket dengan nama yang sama.

Buat program berikut.
package de.vogella.algorithms.search.sequential;

public class SequentialSearch {
 public static boolean contains(int[] a, int b){
  for (int i : a) {
   if (i==b){
    return true;
   }
  }
  return false; 
 }
}

2.3 Test
Anda dapat menggunakan uji JUnit berikut untuk memvalidasi metode semacam Anda. Untuk 
mempelajari tentang JUnit silakan lihat Tutorial JUnit.
package de.vogella.algorithms.search.sequential;

import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;

import org.junit.Test;

public class SequentialSearchTest {

 @Test
 public void testContains() {
  int[]a = {1, 2, 3, 4, 5, 19, 17, 7};
  assertTrue(SequentialSearch.contains(a, 17));
  assertTrue(SequentialSearch.contains(a, 1));
  assertTrue(SequentialSearch.contains(a, 2));
  assertTrue(SequentialSearch.contains(a, 3));
  assertTrue(SequentialSearch.contains(a, 4));
  assertFalse(SequentialSearch.contains(a, 10));
 }

}
 3. BINARY SEARCH
3.1 Overview 
Pencarian biner mensyaratkan bahwa koleksi sudah disortir.Misalnya dengan Quicksort atau mergesort. 
Pencarian biner cek elemen di tengah koleksi.  Jika elemen pencarian yang lebih kecil atau lebih
besar maka elemen ditemukan maka sub-array didefinisikan yang kemudian mencari lagi. 
Jika mencari elemen lebih kecil maka elemen ditemukan maka sub-array dari awal array sampai 
elemen ditemukan.Jika mencari elemen lebih besar maka elemen ditemukan maka sub-array dari elemen  
yang ditemukan sampai akhir array.Setelah dicari elemen ditemukan atau koleksi kosong maka pencarian selesai
3.2 Implementation
Buat proyek Java "de.vogella.algorithms.search.binary" dan sebuah paket dengan nama yang sama.

 Buat program berikut.
package de.vogella.algorithms.search.binary;

public class BinarySearch {
 public static boolean contains(int[] a, int b) {
  if (a.length == 0) {
   return false;
  }
  int low = 0;
  int high = a.length-1;

  while(low <= high ) {
   int middle = (low+high) /2; 
   if (b> a[middle] ){
    low = middle +1;
   } else if (b< a[middle]){
    high = middle -1;
   } else { // The element has been found
    return true; 
   }
  }
  return false;
 }
}
3.3 Test
 Anda dapat menggunakan uji JUnit berikut untuk memvalidasi metode semacam Anda. Untuk 
mempelajari tentang JUnit silakan lihat Tutorial JUnit.package de.vogella.algorithms.search.sequential;
package de.vogella.algorithms.search.binary;


import org.junit.Test;

import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;

public class BinarySearchTest {

 @Test
 public void testContains() {
  int[]a = {1, 2, 3, 4, 5, 7, 17,  19 };
//  assertTrue(BinarySearch.contains(a, 17));
  assertTrue(BinarySearch.contains(a, 1));
  assertTrue(BinarySearch.contains(a, 2));
  assertTrue(BinarySearch.contains(a, 3));
  assertTrue(BinarySearch.contains(a, 4));
  assertFalse(BinarySearch.contains(a, 10));
 }

}


Jumat, 01 April 2011

Pengertian Link List



Linked list tidak lain adalah suatu struktur data yg merupakan suatu rangkaian atau daftar record berjenis sama. Kemudian dihubungkan melalui bantuan pointer. Pengalokasian daftar dapat dilakukan secara dinamis sehingga isi dari daftar dapat dimanipulasi. Untuk memahami

linked list, terlebih dahulu anda harus tahu konsep pointer dan pengalokasian memori

Coba anda bayangkan apabila anda mendeklarasikan array dari record(array of record) sebanyak 10 elemen. Setiap kali program dijalankan, maka akan memesan memory sebesar 10x ukuran record. Itu merupakan suatu pemborosan walaupun kita hanya menggunakan 5 elemen record.

Maka dari itu, biasanya para programer lebih memilih menggunakan linked list dalam pemrograman. Linked list dibedakan atas 2 jenis yaitu singly linked list dan doubly linked list.


Linked List : Definisi Node, Linked List, Single Linked List, Double Linked List, & Circular Linked List

21012010
2. Jelaskan definisi NodeLinked List, Single Linked List, Double Linked List, dan Circular Linked List!
(sertai gambar permodelannya)
a. Nodes
Self-referential objects (object yang mereferensikan dirinya sendiri) yang disebutnodes, yang dihubungkan dengan links, membentuk kata “linked” list.
b. Linked List ( LL )
Adalah koleksi data item yang tersusun dalam sebuah barisan  secara linear, dengan penyisipan dan pemindahan dapat dilakukan dalam semua tempat di LL tersebut.
c. Single Linked List
Adalah sebuah LL yang menggunakan sebuah variabel pointer saja untuk menyimpan banyak data dengan metode LL, suatu daftar isi yang saling berhubungan.
Ilustrasi single LL:
Pada gambar di atas, data terletak pada sebuah lokasi dalam sebuah memory, tempat yang disediakan memory untuk menyimpan data disebut node ? simpul, setiap node memiliki pointer ( penunjuk ) yang menunjuk ke node berikutnya sehingga terbentuk suatu untaian yang disebut single LL.
Bila dalam single LL pointer hanya dapat bergerak ke satu arah saja, maju / mundur, kanan / kiri, sehingga pencarian datanya juga hanya satu arah saja.
d. Double Linked List
Dalam double LL ( Linked List berpointer ganda ) dapat mengatasi kelemahan-kelemahan single LL tersebut.
Ilustrasi double LL:
e. Circular Linked List
Adalah double / single LL yang simpul terakhirnya menunjuk ke simpul awal, dan simpul awalnya menunjuk ke simpul akhir, atau dapat disebut LL yang dibuat seakan-akan merupakan sebuah lingkaran dengan titik awal dan titik akhir saling bersebelahan jika LL tersebut masih kosong, ilustrasi Circular LL :
Dalam ilmu komputer , daftar link (atau lebih jelas, "-linked list tunggal") adalah sebuah struktur data yang terdiri dari urutan node yang masing-masing berisi referensi (yaitu, link) ke node berikutnya dalam urutan tersebut.
Tunggal-terkait-list.svg 
Sebuah node linked list yang berisi dua bidang: nilai integer dan link ke node berikutnya
Linked list adalah salah satu struktur data sederhana dan paling umum. Mereka dapat digunakan untuk melaksanakan beberapa umum lainnya struktur data abstrak , termasuk tumpukan , antrian , array asosiatif , dan ekspresi simbolik , meskipun tidak jarang untuk menerapkan struktur data lainnya secara langsung tanpa menggunakan daftar sebagai dasar pelaksanaan.
Manfaat utama dari sebuah linked list melalui konvensional array adalah bahwa daftar elemen dengan mudah dapat ditambahkan atau dihapus tanpa realokasi atau reorganisasi dari struktur keseluruhan karena item data tidak perlu disimpan contiguously dalam memori atau pada disk. daftar Linked memungkinkan penyisipan dan penghapusan node pada setiap titik dalam daftar, dan dapat melakukannya dengan sejumlah konstan operasi jika link sebelumnya untuk link yang ditambahkan atau dihapus dipertahankan selama pencarian daftar.
Di sisi lain, linked list sederhana dengan sendirinya tidak memungkinkan akses acak ke data lain dari node pertama data, atau segala bentuk pengindeksan yang efisien. Dengan demikian, banyak dasar operasi - seperti mendapatkan node terakhir dari daftar (dengan asumsi bahwa node terakhir tidak dipertahankan sebagai referensi node terpisah dalam struktur daftar), atau menemukan sebuah node yang berisi acuan tertentu, atau menemukan tempat dimana node baru harus dimasukkan - mungkin memerlukan pemindaian sebagian besar atau semua elemen daftar.

Sejarah

daftar Linked dikembangkan di 1955-56 oleh Allen Newell , Cliff Shaw dan Herbert Simon di RAND Corporation sebagai struktur data utama untuk mereka Informasi Pengolahan Bahasa . IPL digunakan oleh para penulis untuk mengembangkan beberapa awal kecerdasan buatanprogram-program, termasuk Logika Teori Mesin, yang Umum Problem Solver , dan program catur komputer. Laporan pekerjaan mereka muncul dalam Transaksi IRE Teori Informasi pada tahun 1956, dan beberapa prosiding konferensi 1957-1959, termasuk Proceedings of the Western Conference Komputer Bersama pada tahun 1957 dan 1958, dan Informasi Pengolahan (Prosiding pertama UNESCO Konferensi Internasional Pengolahan Informasi ) pada tahun 1959. Diagram sekarang-klasik yang terdiri dari blok merupakan daftar node dengan panah yang menunjuk ke daftar node berturut-turut muncul dalam "Programming Logic Machine Theory" oleh Newell dan Shaw di Proc. WJCC, Februari 1957. Newell dan Simon diakui dengan ACM Turing Award pada tahun 1975 karena "kontribusi dasar dibuat untuk kecerdasan buatan, psikologi kognisi manusia, dan pengolahan daftar". Masalah mesin terjemahan untuk bahasa alami pengolahan dipimpin Victor Yngve di Massachusetts Institute of Technology (MIT) untuk menggunakan linked list sebagai struktur data dalam COMITprogramming bahasa nya untuk penelitian komputer di bidang linguistik . Sebuah laporan mengenai bahasa ini berjudul "Sebuah bahasa pemrograman untuk terjemahan mekanik" muncul dalam penerjemahan Teknik pada tahun 1958.
LISP , berdiri untuk prosesor daftar, diciptakan oleh John McCarthy pada tahun 1958 ketika ia berada di MIT dan pada tahun 1960 ia menerbitkan desain dalam makalah di Komunikasi ACM , berjudul "Fungsi Rekursif dan Komputasi Simbolik Ekspresi mereka oleh Mesin, Bagian Aku ". Salah satu struktur utama LISP's data adalah linked list. Pada awal 1960-an, kegunaan kedua daftar terkait dan bahasa yang menggunakan struktur ini sebagai representasi data primer mereka mapan. Bert Green dari Laboratorium MIT Lincoln menerbitkan sebuah artikel berjudul "Komputer bahasa untuk manipulasi simbol" dalam Transaksi IRE pada Faktor Manusia dalam Elektronika Maret 1961 yang meringkas keuntungan dari pendekatan linked list. Sebuah artikel review kemudian, "Sebuah Perbandingan bahasa komputer daftar-pengolahan" oleh Bobrow dan Raphael, muncul di Komunikasi dari ACM pada bulan April 1964.
Beberapa sistem operasi yang dikembangkan oleh Systems Teknis Konsultan (awalnya dari West Lafayette Indiana, dan kemudian Chapel Hill, North Carolina) digunakan secara terpisah terkait daftar sebagai struktur file. Sebuah entri direktori menunjuk ke sektor pertama dari sebuah file, dan bagian berhasil file itu berada dengan melintasi pointer. Sistem menggunakan teknik ini termasuk Flex (untuk Motorola 6800CPU), mini-Flex (CPU yang sama), dan Flex9 (untuk CPU 6809 Motorola). Sebuah varian yang dikembangkan oleh TSC untuk dan dipasarkan oleh Smoke Sinyal Penyiaran di California, digunakan penggandaan daftar dengan cara yang sama.
TSS/360 sistem operasi, yang dikembangkan oleh IBM untuk mesin 360/370 Sistem, menggunakan linked list ganda untuk sistem mereka katalog file. Struktur direktori yang sama dengan Unix, dimana direktori bisa berisi file dan / atau direktori lain dan mencakup setiap kedalaman. Sebuah kutu utilitas diciptakan untuk memperbaiki masalah file sistem setelah crash, karena bagian modifikasi dari file katalog kadang-kadang dalam memori ketika kecelakaan terjadi. Masalah yang terdeteksi dengan membandingkan link ke depan dan ke belakang untuk konsistensi. Jika link forward adalah korup, maka jika mundur link ke node terinfeksi ditemukan, link forward ditetapkan untuk simpul dengan link mundur. Sebuah komentar lucu dalam kode sumber tempat utilitas ini dipanggil menyatakan "Semua orang tahu kerah kutu menghilangkan bug pada kucing".