would like to thank you, for taking time to visit my blog

Minggu, 03 April 2011

SPANNING TREE


SPANNING TREE

Dalam matematika bidang teori graph , sebuah pohon rentang T dari tersambung , graf tak berarah G adalah sebuah pohon yang terdiri dari semua simpul dan beberapa (atau mungkin semua) dari tepi G . Informal, pohon rentang dari G adalah pilihan tepi G yang membentuk pohon merentang setiap simpul.Artinya, setiap vertex terletak di pohon, tetapi tidak ada siklus (atau loop) terbentuk. Di sisi lain, setiap jembatan dari G harus milik T .
Sebuah pohon rentang dari graf terhubung G juga dapat didefinisikan sebagai satu set maksimal tepi G yang berisi siklus tidak ada, atau sebagai seperangkat minimal tepi yang menghubungkan semua titik.
Dalam bidang-bidang tertentu teori grafik sering berguna untuk mencari pohon rentang minimum dari sebuah graf berbobot . masalah optimasi lain di pohon mencakup juga telah dipelajari, termasuk mencakup pohon maksimum, pohon minimum yang mencakup setidaknya simpul k, pohon rentang minimum dengan di tepi k paling per titik (Gelar-Dibatasi Spanning Tree) , pohon merentang dengan jumlah daun terbesar (erat kaitannya dengan terkecil terhubung mendominasi set ), pohon merentang dengan daun paling sedikit (berkaitan erat dengan masalah jalan Hamilton ), dengan rentang diameter pohon minimal, dan dilatasi minimum spanning tree.
Sebuah hutan yang mencakup adalah jenis subgraf yang generalises konsep pohon rentang. Namun, ada dua definisi umum digunakan. Salah satunya adalah bahwa hutan membentang adalah subgraf yang terdiri dari pohon rentang pada setiap komponen terhubung dari graf. (Dengan kata lain, itu adalah siklus subgraf bebas maksimal.) Definisi ini adalah umum di ilmu komputer dan optimasi. Itu juga merupakan definisi yang digunakan ketika mendiskusikan hutan rentang minimum, generalisasi untuk grafik terputus pohon rentang minimum. Definisi lain, umum dalam teori graph , adalah bahwa hutan membentang adalah setiap subgraf yang baik hutan (tidak mengandung siklus) dan mencakup (termasuk setiap vertex).
Menghitung pohon rentang
Jumlah t (G) dari pohon rentang dari graf terhubung adalah penting invarian . Dalam beberapa kasus, mudah untuk menghitung t (G) secara langsung. Hal ini juga banyak digunakan dalam struktur data di bahasa komputer yang berbeda. [ rujukan? ] Sebagai contoh, jika G itu sendiri pohon, maka t (G) = 1 , sedangkan jika G adalah graph siklus C n dengan n simpul, maka t (G) = n . Untuk setiap graf G, nomor t (G) dapat dihitung dengan menggunakan pohon teorema's matriks-Kirchhoff (ikuti link untuk contoh eksplisit menggunakan teorema itu).
Cayley's formula ini adalah formula untuk jumlah mencakup pohon di graf lengkap K n dengan n simpul. Menyatakan formula yang t ( K n ) = n n - 2 . Cara lain untuk menyatakan's formula Cayley adalah bahwa ada persis n n - 2 pohon berlabel dengan n simpul. Cayley's formula dapat dibuktikan dengan menggunakan teorema's matriks pohon-Kirchhoff atau melalui kode Prüfer .
Jika G adalah graf bipartit lengkap K p , q , maka t ( G ) = p q - 1 q p - 1 , sedangkan jika G adalah n -dimensi hypercube grafik Q n , maka . rumus Ini juga konsekuensi dari teorema matriks-pohon.
Jika G adalah multigraph dan e adalah tepi G , maka jumlah t (G) dari pohon rentang G memenuhi penghapusan-kontraksi kambuh t (G) = t (Ge) + t (G / e) , dimana Ge adalah multigraph diperoleh dengan menghapus e dan G / e merupakan kontraksi dari G oleh e , di mana beberapa tepi yang timbul dari kontraksi ini tidak dihapus.


KELEBIHAN SPANNING TREE.
Dapat menyediakan system jalur backup & juga mencegah loop yang tidak diinginkan pada jaringan yang memiliki beberapa jalur menuju ke satu tujuan dari satu host.
Loop terjadi bila ada route/jalur alternative di antara host-host. Untuk menyiapkan jalur back up, Spanning tree membuat status jalur back up menjadi stand by atau diblock. Spanning tree hanya membolehkan satu jalur yang active (fungsi pencegahan loop) di antara dua host namun menyiapkan jalur back up bila jalur utama terputus.
Bila "cost" spanning tree berubah atau ada jalur yang terputus, algoritma spanning tree mengubah topology spanning tree dan mengaktifkan jalur yang sebelumnya stand by.
Tanpa spanning tree pun sebenarnya memungkinkan koneksi antara dua host melewati beberapa jalur sekaligus namun dapat juga membuat looping yang tidak pernah akan selesai di dalam jaringan anda. Yang pasti akan menghabiskan kapasitas jalur yang ada hanya untuk melewatkan packet data yang sama secara berulang dan berlipat ganda.

linked list


Linked List
Linked List adalah salah satu bentuk struktur data, berisi kumpulan data (node) yang tersusun secara sekuensial, saling sambung-menyambung, dinamis dan terbatas.
• Linked List sering disebut juga Senarai Berantai
• Linked List saling terhubung dengan bantuan variabel pointer
• Masing-masing data dalam Linked List disebut dengan node (simpul) yang menempati alokasi memori secara dinamis dan biasanya berupa struct yang terdiri dari beberapa field.
Jenis – Jenis Linked List Ada Beberapa Macam S

Alah Satu nya:


DOUBLE LINKED LIST
• Pada dasarnya, penggunaan Double Linked List hampir sama dengan penggunaan Single Linked List yang telah kita pelajari pada materi sebelumnya. Hanya saja Double Linked List menerapkan sebuah pointer baru, yaitu prev, yang digunakan untuk menggeser mundur selain tetap mempertahankan pointer next.
• Keberadaan 2 pointer penunjuk (next dan prev) menjadikan Double Linked List menjadi lebih fleksibel dibandingkan Single Linked List, namun dengan mengorbankan adanya memori tambahan dengan adanya pointer tambahan tersebut.
• Ada 2 jenis Double Linked List, yaitu: Double Linked List Non Circular dan Double Linked List Circular.

I. DOUBLE LINKED LIST NON CIRCULAR (DLLNC)
a. DLLNC
• DLLNC adalah sebuah Linked List yang terdiri dari dua arah pointer, dengan node yang saling terhubung, namun kedua pointernya menunjuk ke NULL.
• Setiap node pada linked list mempunyai field yang berisi data dan pointer yang saling berhubungan dengan node yang lainnya.

b. GAMBARAN NODE DLLNC



c. PEMBUATAN DLLNC
• Deklarasi Node
typedef struct TNode
{
int data;
TNode *next;
TNode *prev;
}

• Pembuatan DLLNC dengan Head
o Ilustrasi :

o Fungsi-fungsi yang biasa digunakan :
 Fungsi untuk inisialisasi awal
void init() // inisialisasi awal
{
TNode *head;
head = NULL;
}
 Perlu diperhatikan :
 Fungsi ini harus ada, untuk memunculkan node awal.
 Setelah memahami penggunaan fungsi ini, bukalah Turbo C++ Anda, dan copy-kan fungsi ini. Jangan lupa untuk mendeklarasikan node-nya terlebih dahulu.

 Fungsi untuk mengecek kosong tidaknya Linked List
int isEmpty() // mengecek kosong tidaknya Linked List
{
if(head == NULL)
return 1;
else
return 0;
}
 Perlu diperhatikan :
 Setelah memahami penggunaan fungsi ini, bukalah Turbo C++ Anda, dan copy-kan fungsi ini.

 Fungsi untuk menambahkan data di depan
void insertDepan(int value) // penambahan data di depan
{
TNode *baru;
baru = new TNode; // pembentukan node baru

baru->data = value; // pemberian nilai terhadap data baru
baru->next = NULL; // data pertama harus menunjuk ke NULL
baru->prev = NULL; // data pertama harus menunjuk ke NULL

if(isEmpty() == 1) // jika Linked List kosong
{
head = baru; // head harus selalu berada di depan
head->next = NULL;
head->prev = NULL;
}
else // jika Linked List sudah ada datanya
{
baru->next = head; // node baru dihubungkan ke head
head->prev = baru; // node head dihubungkan ke node baru
head = baru; // head harus selalu berada di depan
}

printf(“data masuk\n”);
}
 Perlu diperhatikan :
 Baca code beserta panduan proses yang terjadi, pahami, lalu gambarkan ilustrasi proses terjadinya penambahan di depan. Misalkan saja data pada Linked List ada 4.
 Setelah memahami penggunaan fungsi ini, bukalah Turbo C++ Anda, dan copy-kan fungsi ini.

 Fungsi untuk menambahkan data di belakang
void insertBelakang(int value) // penambahan data di belakang
{
TNode *baru, *bantu;
baru = new TNode; // pembentukan node baru

baru->data = value; // pemberian nilai terhadap data baru
baru->next = NULL; // data pertama harus menunjuk ke NULL
baru->prev = NULL; // data pertama harus menunjuk ke NULL

if(isEmpty() == 1) // jika Linked List kosong
{
head = baru; //head harus selalu berada di depan
head->next = NULL;
head->prev = NULL;
}
else
{
bantu = head; // bantu diletakan di head dulu
while(bantu->next != NULL)
{
bantu = bantu->next // menggeser hingga node terakhir
}

baru->next = baru; // node baru dihubungkan ke head
head->prev = bantu; // node head dihubungkan ke node baru
}
printf(“data masuk\n”);
}
 Perlu diperhatikan :
 Jika Linked List hanya menggunakan head, maka dibutuhkan satu pointer untuk membantu mengetahui node terakhir dari Linked List. Dalam code di atas digunakan pointer bantu.
 Baca code beserta panduan proses yang terjadi, pahami, lalu gambarkan ilustrasi proses terjadinya penambahan di belakang. Misalkan saja data pada Linked List ada 4.
 Setelah memahami penggunaan fungsi ini, bukalah Turbo C++ Anda, dan copy-kan fungsi ini.

 Fungsi untuk menambahkan data di tengah (menyisipkan data)
void insertTengah(int value, int cari) //penambahan data di tengah
{
TNode *baru, *bantu, *bantu2;
baru = new TNode; // pembentukan node baru

baru->data = value; // pemberian nilai terhadap data baru
baru->next = NULL; // data pertama harus menunjuk ke NULL
baru->prev = NULL; // data pertama harus menunjuk ke NULL
bantu = head; // bantu diletakan di head dulu

while(bantu->data != cari)
{
bantu = bantu->next; //menggeser hingga didapat data cari
}

bantu2 = bantu->next; // menghubungkan ke node setelah yang dicari
baru->next = bantu2; // menghubungkan node baru
bantu2->prev = baru;
bantu->next = baru; // menghubungkan ke node sebelum yang dicari
baru->prev = bantu;
}
 Perlu diperhatikan :
 Dibutuhkan satu pointer untuk membantu mencari node di mana data yang ingin disisipkan ditempatkan. Dalam code di atas digunakan pointer bantu.
 Penggunaan pointer bantu2 pada code di atas sebenarnya bisa digantikan dengan pemanfaatan pointer bantu. Bagaimana caranya?
 Baca code beserta panduan proses yang terjadi, pahami, lalu gambarkan ilustrasi proses terjadinya penambahan di tengah. Misalkan saja data pada Linked List ada 4, lalu sisipkan data baru setelah node kedua.
 Setelah memahami penggunaan fungsi ini, bukalah Turbo C++ Anda, dan copy-kan fungsi ini.

 Fungsi untuk menghapus data di depan
void deleteDepan() // penghapusan data di depan
{
TNode *hapus;

if(isEmpty() == 0) // jika data belum kosong
{
if(head->next != NULL) // jika data masih lebih dari 1
{
hapus = head; // letakan hapus pada head
head = head->next; // menggeser head (karena head harus ada)
head->prev = NULL; // head harus menuju ke NULL
delete hapus; //proses delete tidak boleh dilakukan jika node masih ditunjuk oleh pointer
}
else // jika data tinggal head
{
head = NULL; // langsung diberi nilai NULL saja
}
printf(“data terhapus\n”);
}
else // jika data sudah kosong
printf(“data kosong\n”);
}
 Perlu diperhatikan :
 Dibutuhkan satu pointer untuk membantu memindahkan head ke node berikutnya. Dalam code di atas digunakan pointer hapus. Mengapa head harus dipindahkan?
 Baca code beserta panduan proses yang terjadi, pahami, lalu gambarkan ilustrasi proses terjadinya penghapusan di depan. Misalkan saja data pada Linked List ada 4.
 Setelah memahami penggunaan fungsi ini, bukalah Turbo C++ Anda, dan copy-kan fungsi ini.

 Fungsi untuk menghapus data di belakang
void deleteBelakang() // penghapusan data di belakang
{
TNode *hapus;

if(isEmpty() == 0) // jika data belum kosong
{
if(head->next != NULL) // jika data masih lebih dari 1
{
hapus = head; // letakan hapus pada head
while(hapus->next != NULL)
{
hapus = hapus->next; // menggeser hingga node akhir
}

hapus->prev->next = NULL; // menghubungkan node sebelumnya dengan NULL
delete hapus; //proses delete tidak boleh dilakukan jika node sedang ditunjuk oleh pointer
}
else // jika data tinggal head
{
head = NULL; // langsung diberi nilai NULL saja
}
printf(“data terhapus\n”);
}
else // jika data sudah kosong
printf(“data kosong\n”);

}
 Perlu diperhatikan :
 Jika Linked List hanya menggunakan head, maka dibutuhkan satu pointer untuk membantu mengetahui node terakhir dari Linked List. Dalam code di atas digunakan pointer hapus.
 Jangan lupa untuk tetap mengaitkan node terakhir ke NULL.
 Baca code beserta panduan proses yang terjadi, pahami, lalu gambarkan ilustrasi proses terjadinya penghapusan di belakang. Misalkan saja data pada Linked List ada 4.
 Setelah memahami penggunaan fungsi ini, bukalah Turbo C++ Anda, dan copy-kan fungsi ini.

 Fungsi untuk menghapus data di tengah
void deleteTengah(int cari) // penghapusan data di tengah
{
TNode *hapus, *bantu, *bantu2;

hapus = head; // letakan hapus pada head
while(hapus->data != cari)
{
hapus = hapus->next; // menggeser hingga data cari
}
bantu2 = hapus->next; // mengkaitkan node sebelum dan sesudahnya
bantu = hapus->prev;
bantu->next = bantu2;
bantu2->prev = bantu;
printf("data terhapus\n");
delete hapus; //proses delete tidak boleh dilakukan jika node sedang ditunjuk oleh pointer
}
 Perlu diperhatikan :
 Dibutuhkan satu pointer untuk membantu mencari node di mana data yang ingin dihapus ditempatkan. Dalam code di atas digunakan pointer hapus.
 Penggunaan pointer bantu dan bantu2 pada code di atas sebenarnya bisa digantikan dengan pemanfaatan pointer hapus. Bagaimana caranya?
 Baca code beserta panduan proses yang terjadi, pahami, lalu gambarkan ilustrasi proses terjadinya penghapusan di tengah. Misalkan saja data pada Linked List ada 4, lalu hapus data pada node ketiga.
 Setelah memahami penggunaan fungsi ini, bukalah Turbo C++ Anda, dan copy-kan fungsi ini.

 Fungsi untuk menghapus semua data
void clear() // penghapusan semua data
{
TNode *bantu, *hapus;
bantu = head; // letakan bantu pada head
while (bantu != NULL) // geser bantu hingga akhir
{
hapus = bantu;
bantu = bantu->next;
delete hapus; // delete satu persatu node
}

head = NULL; // jika sudah habis berikan nilai NULL pada head
}
 Perlu diperhatikan :
 Dibutuhkan dua pointer untuk membantu menggeser dan menghapus, di mana dalam code di atas digunakan pointer bantu dan hapus.
 Setelah memahami penggunaan fungsi ini, bukalah Turbo C++ Anda, dan copy-kan fungsi ini.

 Fungsi untuk menampilkan semua data
void cetak() // menampilkan semua data
{
TNode *bantu;
bantu = head; // letakan bantu pada head

if(isEmpty() == 0)
{
while (bantu != NULL)
{
printf(“%d ”, bantu->data); // cetak data pada setiap node
bantu = bantu->next; // geser bantu hingga akhir
}
printf(“\n”);
}
else // jika data sudah kosong
printf(“data kosong”);
}
 Perlu diperhatikan :
 Dibutuhkan satu pointer untuk membantu menggeser, di mana dalam code di atas digunakan pointer bantu.
 Setelah memahami penggunaan fungsi ini, bukalah Turbo C++ Anda, dan copy-kan fungsi ini.

• Latihan 1 :
1. Setelah deklarasi node dilakukan, dan semua fungsi sudah tersedia. Sekarang gabungkan setiap fungsi yang ada pada sebuah program penuh dengan spesifikasi :
 Pada program utama (main) berisi sebuah menu yang berisi fitur-fitur yang terdapat dari setiap fungsi yang sudah ada ada sebelumnya, yaitu : tambah data, hapus data, cek data kosong, dan cetak semua data.
 Pada struct hanya terdapat 1 tipe data saja yaitu integer.
 Sesuaikan fungsi-fungsi yang ada dengan program yang Anda buat (jangan langsung copy-paste dan digunakan).
2. Buat program untuk enkripsi dan dekripsi password yang memanfaatkan Linked List, dengan spesifikasi :
 Panjang password minimal 6 digit.
 Isi password terserah dari user dan password diinputkan terlebih dahulu sebelumnya (penambahan data di belakang).
 Enkripsi dilakukan dengan memindahkan 3 node terakhir, menjadi node terdepan. Kemudian sisipkan 1 karakter baru (kunci) setelah node ketiga dari yang dipindahkan tersebut.
 Ilustrasi :



 Lakukan juga proses dekripsi-nya.
 Berikan juga fitur untuk menampilkan password.

• Pembuatan DLLNC dengan Head dan Tail
o Ilustrasi :

o Sebenarnya sama saja dengan DLLNC dengan menggunakan head saja, hanya saja perbedaannya terletak pada kemudahan pengaksesan di bagian data terakhirnya saja (tail).
o Fungsi-fungsi yang biasa digunakan :
 Fungsi untuk inisialisasi awal
void init() //inisialisasi awal
{
TNode *head, *tail;
head = NULL;
tail = NULL;
}

 Fungsi untuk mengecek kosong tidaknya Linked List
int isEmpty() //mengecek kosong tidaknya Linked List
{
if(tail == NULL)
return 1;
else
return 0;
}

 Fungsi untuk menambahkan data di depan
void insertDepan(int value) //penambahan data di depan
{
TNode *baru;
baru = new TNode; // pembentukan node baru

baru->data = value; // pemberian nilai terhadap data baru
baru->next = NULL; // data pertama harus menunjuk ke NULL
baru->prev = NULL; // data pertama harus menunjuk ke NULL

if(isEmpty() == 1) // jika Linked List kosong
{
head = baru; // letakan baru pada head
tail = head; // head = tail
head->next = NULL;
head->prev = NULL;
tail->next = NULL;
tail->prev = NULL;
}
else // jika Linked List sudah ada datanya
{
baru->next = head; // menyambungkan data baru dengan head lama
head->prev = baru;
head = baru; //head harus selalu berada di depan
}
printf(“data masuk\n”);
}
 Perlu diperhatikan :
 Baca code beserta panduan proses yang terjadi, pahami, lalu gambarkan ilustrasi proses terjadinya penambahan di depan.

 Fungsi untuk menambahkan data di belakang
void insertBelakang(int value) //penambahan data di belakang
{
TNode *baru;
baru = new TNode; // pembentukan node baru

baru->data = value; // pemberian nilai terhadap data baru
baru->next = NULL; // data pertama harus menunjuk ke NULL
baru->prev = NULL; // data pertama harus menunjuk ke NULL

if(isEmpty() == 1) // jika Linked List kosong
{
head = baru; // letakan baru pada head
tail = head; // head = tail
head->next = NULL;
head->prev = NULL;
tail->next = NULL;
tail->prev = NULL;
}
else // jika Linked List sudah ada datanya
{
tail->next = baru; // menghubungkan data baru dengan tail lama
baru->prev = tail;
tail = baru; // tail harus selalu berada di belakang
tail->next = NULL;
}
printf(“data masuk\n”);
}
 Perlu diperhatikan :
 Baca code beserta panduan proses yang terjadi, pahami, lalu gambarkan ilustrasi proses terjadinya penambahan di belakang.
 Perhatikan kemudahan pengaksesan node terakhirnya.

 Fungsi untuk menambahkan data di tengah (menyisipkan data)
void insertTengah(int value, int cari) //penambahan data di tengah
{
TNode *baru, *bantu, *bantu2;
baru = new TNode; // pembentukan node baru
baru->data = value; // pemberian nilai terhadap data baru
baru->next = NULL; // data pertama harus menunjuk ke NULL
baru->prev = NULL; // data pertama harus menunjuk ke NULL

bantu = head; // letakan bantu di awal
while(bantu->data != cari)
{
bantu = bantu->next; // geser bantu sampai data cari
}

bantu2 = bantu->next; // menghubungkan ke node setelah yang dicari
baru->next = bantu2; // menghubungkan node baru
bantu2->prev = baru;
bantu->next = baru; // menghubungkan ke node sebelum yang dicari
baru->prev = bantu;
}
 Perlu diperhatikan :
 Baca code beserta panduan proses yang terjadi, pahami, lalu gambarkan ilustrasi proses terjadinya penambahan di tengah. Misalkan saja data pada Linked List ada 4, lalu sisipkan data sebelum node ketiga.

 Fungsi untuk menghapus data di depan
void deleteDepan() // penghapusan data di depan
{
TNode *hapus;

if(isEmpty() == 0) // jika data belum kosong
{
if(head->next != NULL) // jika data tidak tinggal 1
{
hapus = head; // letakan hapus pada head
head = head->next; // menggeser head (karena head harus ada)
head->prev = NULL; // head harus menuju ke NULL
delete hapus; //proses delete tidak boleh dilakukan jika node sedang ditunjuk oleh pointer
}
else // jika data tinggal head
{
head = NULL; // langsung diberi NULL saja
tail = NULL;
}
printf(“data terhapus\n”);
}
else // jika data kosong
printf(“data kosong\n”);
}
 Perlu diperhatikan :
 Baca code beserta panduan proses yang terjadi, pahami, lalu gambarkan ilustrasi proses terjadinya penghapusan di depan.

 Fungsi untuk menghapus data di belakang
void deleteBelakang() // penghapusan data di belakang
{
TNode *hapus;

if(isEmpty() == 0) // jika data belum kosong
{
if(head ->next != NULL) // jika data tidak tinggal 1
{
hapus = tail; // letakan hapus pada tail
tail = tail->prev; // menggeser tail
tail->next = NULL; // tail harus menuju ke NULL
delete hapus; //proses delete tidak boleh dilakukan jika node sedang ditunjuk oleh pointer
}
else // jika data tinggal head
{
head = NULL; // langsung diberi NULL saja
tail = NULL;
}
printf(“data terhapus\n”);
}
else // jika data kosong
printf(“data kosong\n”);
}
 Perlu diperhatikan :
 Baca code beserta panduan proses yang terjadi, pahami, lalu gambarkan ilustrasi proses terjadinya penghapusan di belakang.
 Perhatikan kemudahan pengaksesan node terakhirnya.

 Fungsi untuk menghapus data di tengah
void deleteTengah(int cari) // penghapusan data di tengah
{
TNode *hapus, *bantu, *bantu2;

hapus = head; // letakan hapus pada head
while(hapus->data != cari)
{
hapus = hapus->next; // menggeser hingga data cari
}
bantu2 = hapus->next; // mengkaitkan node sebelum dan sesudahnya
bantu = hapus->prev;
bantu->next = bantu2;
bantu2->prev = bantu;
printf("data terhapus\n");
delete hapus; //proses delete tidak boleh dilakukan jika node sedang ditunjuk oleh pointer
}
 Perlu diperhatikan :
 Baca code beserta panduan proses yang terjadi, pahami, lalu gambarkan ilustrasi proses terjadinya penghapusan di tengah. Misalkan saja data pada Linked List ada 4, lalu hapus data pada node ketiga.

 Fungsi untuk menghapus semua data
void clear() // penghapusan semua data
{
TNode *bantu, *hapus;
bantu = head; // letakan bantu pada head
while (bantu != NULL) // geser bantu hingga akhir
{
hapus = bantu;
bantu = bantu->next;
delete hapus; // delete satu persatu node
}

head = NULL; // jika sudah habis berikan nilai NULL pada head
tail = NULL; // jika sudah habis berikan nilai NULL pada tail
}

 Fungsi untuk menampilkan semua data
void cetak() // menampilkan semua data
{
TNode *bantu;
bantu = head; // letakan bantu pada head

if(isEmpty() == 0)
{
while (bantu != tail->next)
{
printf(“%d ”, bantu->data); // cetak data pada setiap node
bantu = bantu->next; // geser bantu hingga akhir
}
printf(“\n”);
}
else // jika data sudah kosong
printf(“data kosong”);
}

• Latihan 2 :
1. Lakukan latihan 1 no 1 dengan DLLNC dengan head dan tail, bandingkan kemudahan penggunaannya.
2. Lakukan latihan 1 no 2 dengan DLLNC dengan head dan tail, lalu berikan spesifikasi tambahan :
 Tambahkan 2 macam user : anonymous dan admin.
 Pada bagian fitur menampilkan password, jika admin user yang ingin melihat password tampilkan password secara benar (dari depan ke belakang), namun jika anonymous user yang ingin melihat password tampilkan password secara terbalik (dari belakang ke depan – manfaatkan tail dalam pengaksesan semacam ini).

d. TUGAS (DLLNC)
1. Dari latihan 2 no 1 yang sudah Anda buat, buat juga fitur tambahan untuk melakukan sorting (ascending dan descending).
2. Dengan memanfaatkan semua fitu yang sudah ada sebelumnya. Buat sebuah aplikasi SIMULASI FRAGMENTASI HARDDISK. Dengan spesifikasi sebagai berikut :
 Setiap node dilambangkan sebagai 1 fragmen harddisk dalam komputer Anda.
 Dalam setiap fragmen berisi :
• Nama data (unik).
• Jenis data (aplikasi, OS, dokumen)
• Ukuran data.
 Terdapat menu untuk melakukan :
• Penambahan fragmen / penambahan data.
• Penghapusan fragmen / penghapusan data.
• Pencarian fragmen (bisa ditambahkan fitur untuk mencari ukuran terbesar/terkecil, pencarian berdasarkan nama ataupun jenis data).
• Edit isi fragmen.
• Menampilkan isi fragmen (bisa dikombinasikan dengan fitur pencarian).
• Melakukan defragmentasi (sorting), di mana bisa dilakukan terhadap : jenis data dan ukuran data.

II. Double Linked List Cicular
1. Dengan Head
- Menggunakan 1 pointer head
- Head selalu menunjuk node pertama

Sebelumnya kita harus mendeklarasikan dulu pointer head :
TNode *head;
Setelah kita mendeklarasikan pointer head, kita belum bisa secara langsung mendeklarasikan node yang dituju. Sehingga pointer head harus dibuat bernilai null terlebih dahulu :
head = NULL;
untuk mengetahui apakah suatu Linked List kosong atau tidak, kita dapat mengetahuinya dengan mengecek nilai dari pointer Head-nya.

int isEmpty() {
if(head==NULL) return 1;
else return 0;
}
Contoh program :
• Penambahan di depan

void tambahdata (int databaru){
TNode *baru,*bantu;
//pointer bantu digunakan untuk menunjuk node terakhir (head->prev)
baru = new TNode;
baru -> data = databaru;
baru -> next = baru;
baru -> prev = baru;

if (isEmpty()==1) {
head=baru;
head->next=head;
head->prev=head;
}
else {
bantu=head->prev;
baru->next=head;
head->prev=baru;
head=baru;
head->prev=bantu;
bantu->next=head;
}
printf(”data masuk”);
}


Penggambaran :
head



Setelah dibuat node baru dan jika diketahui head==NULL :
head baru

Bila kita membuat node baru lagi maka :
baru head bantu

baru head bantu

baru head bantu

head bantu



head bantu

• Penambahan di belakang

void insertBelakang (int databaru){
TNode *baru,*bantu;
baru = new TNode;
baru->data = databaru;
baru->next = baru;
baru->prev = baru;
if(isEmpty()==1){
head=baru;
head->next = head;
head->prev = head;
}
else {
bantu=head->prev;
bantu->next = baru;
baru->prev = bantu;
baru->next = head;
head->prev = baru;
}
printf(”data masuk”);
}




• Tampil

void tampil(){
TNode *bantu;
bantu = head;
if(isEmpty()==0){
do{
printf(“%i ”,Bantu->data);
bantu=bantu->next;
}while(bantu!=head);
printf(“\n”);
} else printf(“masih Kosong”);cout<<"Masih kosong\n";
}

• Hapus di depan

void hapusDepan (){
TNode *hapus,*bantu;
int d;
if (isEmpty()==0){
if(head->next != head){
hapus = head;
d = hapus->data;
bantu = head->prev;
head = head->next;
bantu->next = head;
head->prev = bantu;
delete hapus;
} else {
d = head->data;
head = NULL;
}
printf(“%i terhapus”,d);
} else printf(“Masih kosong\n”);
}

• Hapus di belakang

void hapusBelakang(){
TNode *hapus,*bantu;
int d;
if (isEmpty()==0){
if(head->next != head){
bantu = head;
while(bantu->next->next != head){
bantu = bantu->next;
}
hapus = bantu->next;
d = hapus->data;
bantu->next = head;
delete hapus;
} else {
d = head->data;
head = NULL;
}
printf(“%i terhapus\n”,d);
} else printf(“Masih Kosong”);
}

latihan :
• Buatlah ilustrasi dari masing-masing potongan program.
• Buat program lengkap dari potongan-potongan program yang ada diatas! Buat agar menjadi seperti menu.
• Buat program untuk memasukkan node baru tetapi diantara node yang sudah ada. Tentukan node yang baru akan berada pada antrian keberapa.

2. Dengan Head dan tail
- Menggunakan 2 pointer, head dan tail.
- Head selalu menunjuk node pertama dan tail selalu menunjuk node terakhir
Sebelumnya kita harus mendeklarasikan dulu pointer head :
TNode *head, *tail;
Setelah kita mendeklarasikan pointer head, kita belum bisa secara langsung mendeklarasikan node yang dituju. Sehingga pointer head harus dibuat bernilai null terlebih dahulu :
head = NULL;
tail = NULL;
untuk mengetahui apakah suatu Linked List kosong atau tidak, kita dapat mengetahuinya dengan mengecek nilai dari pointer Tail-nya.
int isEmpty() {
if(tail==NULL) return 1;
else return 0;
}
Contoh program :
• Penambahan di depan

void tambahdata (int databaru){
TNode *baru;
baru = new TNode;
baru -> data = databaru;
baru -> next = NULL;
baru -> prev = NULL;

if (isEmpty()==1) {
head=baru;
tail=head;
head->next=head;
head->prev=head;
tail->next=tail;
tail->prev=tail;
}
else {
baru->next=head;
head->prev=baru;
head=baru;
head->prev=tail;
tail->next=head;
}
printf(”data masuk”);
}

Penggambaran :
head tail



Setelah dibuat node baru dan jika diketahui tail==NULL :
head baru tail

Bila kita membuat node baru lagi maka :

baru head bantu

baru head tail

baru head tail

head bantu

head bantu

• Penambahan di belakang

void insertBelakang(int databaru){
TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = baru;
baru->prev = baru;
if(isEmpty()==1){
head=baru;
tail=baru;
head->next = head;
head->prev = head;
tail->next = tail;
tail->prev = tail;
}
else {
tail->next = baru;
baru->prev = tail;
tail = baru;
tail->next = head;
head->prev = tail;
}
printf(“Data masuk\n”);
}

• Tampil

void tampil(){
TNode *bantu;
bantu = head;
if(isEmpty()==0){
do{
cout<data<<" ";
bantu=bantu->next;
}while(bantu!=tail->next);
printf(“\n”);
} else printf(“masih kosong\n”);
}

• Hapus di depan

void hapusDepan(){
TNode *hapus;
int d;
if (isEmpty()==0){
if(head != tail){
hapus = head;
d = hapus->data;
head = head->next;
tail->next = head;
head->prev = tail;
delete hapus;
} else {
d = head->data;
head = NULL;
tail = NULL;
}
printf(“%i terhapus\n”,d);
} else printf(“Masih Kosong”);
}

• Hapus di belakang

void hapusBelakang(){
TNode *hapus;
int d;
if (isEmpty()==0){
if(head != tail){
hapus = tail;
d = hapus->data;
tail = tail->prev;
tail->next = head;
head->prev = tail;
delete hapus;
} else {
d = head->data;
head = NULL;
tail = NULL;
}
cout<} else cout<<"Masih kosong\n";
}

latihan :
• Buatlah ilustrasi dari masing-masing potongan program.
• Buat program lengkap dari potongan-potongan program yang ada diatas! Buat agar menjadi seperti menu.
• Buat program untuk memasukkan node baru tetapi diantara node yang sudah ada. Tentukan node yang baru akan berada pada antrian keberapa.


Soal Double Linked List Circular
Soal Guided
1. Marilah kita buat sebuah Double Linked List Circular(DLLC) sederhana…
Buatlah sebuah program dengan menggunakan DLLC yang dapat menerima inputan dari belakang maupun dari depan.
#include "stdio.h"
typedef struct Tnode
{
int value;
Tnode *next;
Tnode *back;
};

Tnode *baru, *bantu,*head,*tail;

void tambah(int value)
{
baru = new Tnode;
baru->next = baru;
baru->back = baru;
baru->value = value;
}
void tambahbelakang(int value){
tambah(value);
if(head == NULL)
head = tail = baru;
else{
tail->next = baru;
baru->back = tail;
tail = baru;
}
tail->next = head;
head->back = tail;
}
void tambahdepan(int value){
tambah(value);
if(head == NULL)
head = tail = baru;
else {
baru->next = head;
head->back = baru;
head = baru;
}
tail->next = head;
head->back = tail;
}

void cetak(){
bantu = head;
do
{
printf("%d",bantu->value);
bantu = bantu->next;
}while(bantu!=head);
}
void menu(){
int pil;
int isi;
do {
printf("Menu :\n1.Masuk dari depan\n2.Masuk dari belakang\n3.Cetak\n4.Exit\nMasukkan pilihan anda");
scanf("%d",&pil);
switch(pil){
case 1 :
printf("Masukkan nilai : "); scanf("%d",&isi);
tambahdepan(isi);
break;
case 2 :
printf("Masukkan nilai : "); scanf("%d",&isi);
tambahbelakang(isi);
break;
case 3 : cetak();
break;
case 4 : printf("Terima kasih");
break;

default:
printf("Tidak ada pilihan tersebut, masukkan angka dari 1 sampai 3");
}
}while(pil!=4);
}

int main(){
menu();
return 0;
}

2. Setelah dapat menambahkan dari depan dan belakang, mari kita berlatih untuk dapat menghapus data yang telah di masukkan. Berikut ini adalah contoh program untuk mendelete data dari belakang.

#include "stdio.h"
typedef struct Tnode
{
int value;
Tnode *next;
Tnode *back;
};

Tnode *baru, *bantu,*head,*tail, *bantudelete;

void tambah(int value)
{
baru = new Tnode;
baru->next = baru;
baru->back = baru;
baru->value = value;
}
void tambahbelakang(int value)
{
tambah(value);
if(head == NULL)
head = tail = baru;
else
{
tail->next = baru;
baru->back = tail;
tail = baru;
}
tail->next = head;
head->back = tail;
}
void deletebelakang()
{
if(head == NULL)
head = tail = NULL;
else
{
bantudelete = tail;
tail = tail->back;
tail->next = head;
head->back = tail;
delete bantudelete;
}
}

void cetak()
{
if(head != NULL)
{bantu = head;
do
{
printf("%d",bantu->value);
bantu = bantu->next;
}while(bantu!=head);
}else
printf("tidak ada data");
}
void menu()
{
int pil;
int isi;
do
{
printf("Menu :\n1.Masuk dari belakang\n2.Delete dari belakang\n3.Cetak\n4.Exit\nMasukkan pilihan anda");
scanf("%d",&pil);
switch(pil)
{
case 1 :
printf("Masukkan nilai : "); scanf("%d",&isi);
tambahbelakang(isi);
break;
case 2 :
deletebelakang();
break;
case 3 : cetak();
break;
case 4 : printf("Terima kasih");
break;

default:
printf("Tidak ada pilihan tersebut, masukkan angka dari 1 sampai 3");
}
}while(pil!=4);
}

int main(){
menu();
return 0;
}
Soal Unguided
1. Setelah tadi diberi contoh mengenai tambah depan dan belakang, coba sekarang buatlah yang menambah data nya dari tengah. Penambahan dilakukan setelah data ke n(inputan user)
2. Setelah dapat menambahkan data setelah data ke n, bagaimana dengan menghapus data ke n? silahkan dicoba dikerjakan…

Soal Take Home
1. Marilah kita membuat sebuah game
Sebuah mesin roulette memiliki 16 point yang masing-masing memiliki warna dan sebuah nilai angka. Nilai angka yang ada di point-point yang ada adalah angka 1 sampai 16 yang peletakannya secara urut dan warna untuk setiap point berbeda-beda dengan urutan warna merah, putih, dan hitam.
Tentukan sebuah bola (sebuah pointer random) yang menunjuk ke mesin roulette tersebut dengan perhitungan random tentu saja…
User bisa memilih akan melempar bola tersebut ke arah kanan atau kearah kiri tergantung pilihan user
Sebelum memulai user dapat menentukan pilihan dengan cara memilih antara angka 1 – 16 atau warna antara putih, hitam, dan merah. Kemudian memasukkan banyaknya bet(banyaknya point yang ditaruhkan)(pada awal user diberi 1000point)
Jika tebakan benar maka point user bertambah yaitu 2 kali bet. Jika salah maka point user berkurang sebanyak bet yang dimasukkan
2. Sebuah bank di Indonesia ingin membuat sebuah program dengan menggunakan urutan prioritas. Tujuan program ini adalah untuk memberikan no urut kepada para nasabahnya. No urut yang diberikan kemudian akan dipanggil oleh program sehingga nasabah yang memiliki no tersebut dapat menuju ke teller yang telah ditunjuk.
Permasalahannya di bank tersebut terdapat sebuah sistem prioritas yang mendahulukan orang2 yang memiliki prioritas, sehingga ketika nasabah yang memiliki prioritas bisa dipanggil terlebih dahulu dari pada nasabah yang tidak memiliki prioritas. Buatlah program menggunakan DLLC untuk mengatasi hal ini…

Jumat, 25 Maret 2011

TEKNIK SORTING DAN SEARCHING

SORTING

Dalam penyelesaian suatu masalah pasti terdapat banyak cara atau solusi-solusi yang dapat dilakukan, seperti halnya pembuatan program memiliki banyak tehnik atau algoritma yang dapat di gunakan salah satunya untuk kebutuhan SORTING atau PENGURUTAN kumpulan data-data. terdapat 4 algoritma atau tehnik dalam melakukan sorting.
• Straight Selection Sort. teknik sorting ini dibuat dengan cara melakukan pengecek'an 1 persatu, bila kita akan mengurutkan secara ascending maka kita lakukan pengecek'an nilai tempat yang pertama (index pertama pada array) bila lebih kecil daripada index berikutnya (index 1 dengan index 2, index 1 dengan index 3, ..... index 1 dengan index terakhi) maka kita lakukan pertukaran nilai pada array index tersebut. proses ini dilakukan terus menerus sampai pada pengecekan index terakhir - 1 dengan nidex terakhir. listing program (open in Inrternet eplorer only)
• Selection Sort.Teknik sorting ini dibuat dengan cara melakukan pengecek'an 1 persatu, bila kita akan mengurutkan secara ascending maka kita lakukan pengecek'an nilai tempat yang pertama (index pertama pada array)kita bandingkan dengan semua nilai yang ada kita cari nilai minimalnya. lalu simpan index/ letak nilai minimum itu di temukan, setelah pengecekan selesai tukar index awal pengecekan dengan nilai minimum yang telah di simpan tadi. Proses ini dilakukan terus menerus sampai pada pengecekan index terakhir min 1 dengan index terakhir. beda dengan streith selection sort adalah dengan teknik ini melakukan pertukaran nilai lebih sedikit, hanya jumlah data - 1 pertukaran. jadi waktu untuk melakukan proses sorting lebih cepat.listing program (open in Inrternet eplorer only)
• Bubble Sort. Teknik ini dilakukan degan pola membawa nilai terbesar menjadi nilai index terakhir array. jadi sistem ini melakukan pengecekan nilai 1 dengan 2, lalu 2 dengan 3 samapai dengan data terakhir, bila nilai index yang lebih kecil lebih besar maka akan dilakukan pertukaran. proses ini dilakuan hingga jumlah data - 1. listing program (open in Inrternet eplorer only)
• Modified Bubble Sort. Teknik ini dilakukan degan pola membawa nilai terbesar menjadi nilai index terakhir array. Jadi sistem ini melakukan pengecekan nilai 1 dengan 2, lalu 2 dengan 3 samapai dengan data terakhir, bila nilai index yang lebih kecil lebih besar maka akan dilakukan pertukaran. proses ini dilakuan hingga jumlah data dikurangi 1 atau sampai program tidak melakukan pertukaran. jadi waktu untuk melakukan proses sorting lebih cepat.listing program (open in Inrternet eplorer only)
Algoritma sorting ada yang tidak terdapat di web ini, untuk lebih jelasnya silahkan klik di sini.

SEARCHING

Dalam pencarian data juga terdapat beberapa jenis algoritma, tujuan dari adanya banyak algoritma yang di temukan adalah karena memiliki keuntungan-keuntungan tersendiri, seperti lebih cepatnya bila mengolah data yang jumlahnya lebih dari juta data, ada yang lebih efisien dengan jumlah kurang dari jutaan. serta ada pula yang tidak perlu untuk mengurutkan data terlebih dahulu, tetapi memakan waktu lebih lama.
• Line Search. teknik searching ini dibuat dengan cara melakukan pengecek'an 1 persatu, yaitu antara data yang di cari dengan kumpulan data yang di miliki, Keuntungan metode ini adalah kita tidak perlu mengurutkan data yang ada, bila mencari data pada kumpulan data yang tidak urut hanya terdapat metode ini yang dapat di lakukan. listing program (open in Inrternet eplorer only)
• Binnary Search. teknik ini hanya dapat digunakan hanya pada kumpulan data yang sudah di urutkan, karena teknik ini melakukan pencarian dengan mencari data pada index yang tengah, apakah lebih besar/lebih kecil/sama dengan. bila hasil sama dengan maka nilai yang di cari telah di temukan. bila lebih kecil/lebih besar maka akan di buang setengah data dari yang salah, dan mencari dari indeks yang tengah dari sisanya. demikian samapi data ditemukan atau tidak di temukan. listing program (open in Inrternet eplorer only)
• Fibonachi Search. Teknik ini hanya dapat digunakan hanya pada kumpulan data yang sudah di urutkan, karena teknik ini melakukan pencarian dengan mencari data melalui pola bilangan fibonachi. Bila pada binnary search pembandingnya adalah nilai pada index tengahnya jumlah data, pada fibonachi search berbeda yaitu: bilangan fibonachi, yang bilangan fibonachinya terdekat dengan jumlah data tetapi tidak lebih besar dari jumlah data yang akan di proses. Bilangan fibonachi itu di jumlahkan dengan batas paling awal data dikurangi 1. Contohnya: jumlah data yang akan di cari adalah 15, maka batas paling bawah adalah 1 dan batas paling akhir=15 dan index pembandingnya= 13(nilai awal + dijumlahkan Bilangan fibonachi - 1) karena bilangan fibonachi terdekat dengan 15 (data ke 1- data ke 15) adalah 13 (1,2,3,5,8,13,21,34.....), bila data yang di cari lebih besar dari bilangan indeks ke tengahnya maka. batas paling bawah= tetap, batas akhir nilai tengah-1, bila data yang dicari lebih kecil maka batas bawah = nilai tengah +1 dan batas akhir tetap, sedangkan nilai tengahnya memakai fungsi tadi. listing program (open in Inrternet eplorer only)

tentang perkembangan komputer dan penerapan di bidang elektronik


Komputer adalah alat yang dipakai untuk mengolah data menurut prosedur yang telah dirumuskan. Kata computer semula dipergunakan untuk menggambarkan orang yang perkerjaannya melakukan perhitungan aritmatika, dengan atau tanpa alat bantu, tetapi arti kata ini kemudian dipindahkan kepada mesin itu sendiri. Asal mulanya, pengolahan informasi hampir eksklusif berhubungan dengan masalah aritmatika, tetapi komputer modern dipakai untuk banyak tugas yang tidak berhubungan dengan matematika.

Dalam arti seperti itu terdapat alat seperti slide rule, jenis kalkulator mekanik mulai dari abakus dan seterusnya, sampai semua komputer elektronik yang kontemporer. Istilah lebih baik yang cocok untuk arti luas seperti "komputer" adalah "yang mengolah informasi" atau "sistem pengolah informasi." Selama bertahun-tahun sudah ada beberapa arti yang berbeda dalam kata "komputer", dan beberapa kata yang berbeda tersebut sekarang disebut disebut sebagai komputer.

Kata computer secara umum pernah dipergunakan untuk mendefiniskan orang yang melakukan perhitungan aritmatika, dengan atau tanpa mesin pembantu. Menurut Barnhart Concise Dictionary of Etymology, kata tersebut digunakan dalam bahasa Inggris pada tahun 1646 sebagai kata untuk "orang yang menghitung" kemudian menjelang 1897 juga digunakan sebagai "alat hitung mekanis". Selama Perang Dunia II kata tersebut menunjuk kepada para pekerja wanita Amerika Serikat dan Inggris yang pekerjaannya menghitung jalan artileri perang dengan mesin hitung.

Jenis-jenis computer

1. PC atau Personal Computer
Sesuai dengan namanya personal komputer,maka PC adalah komputer yang ditujukan untuk pemakaian satu orang atau dimiliki secara pribadi. Sebelum PC ini muncul, komputer dahulunya berwujud sangat besar, sehingga hanya dimiliki oleh perusahaan tertentu saja. PC pertama bernama Altair yang diproduki oleh MITS pada tahun 1975.

2. Komputer Desktop

Yaitu komputer yang dirancang untuk tidak dapat dipindahkan-pindahkan, atau khusus dirancang untuk diletakkan disuatu tempat seperti diatas meja kerja. Komputer jenis ini sangat banyak beredar dipasaran, terutama dikalangan perguruan tinggi, kantor dan perusahaan.

3. Laptop

Dahulu istilah laptop berbeda dengan Notebook ditinjau dari segi ukuran, namun sekarang laptop atau notebook mengacu ke maksud yang sama, yaitu komputer portable (mudah dibawa-bawa) yang terintegrasi langsung dengan monitor, keyboard, mouse pad/trackbal, processor, harrdisk, memory dan peripheral lainnya dengan ukuran yang kecil dan ringan. Kemampunya bahkan melebihi komputer dekstop maupun PC..

4. PDA, Personal Digital Assistants
PDA adalah komputer canggih yang menggunakan flash memory sebagai pengganti media penyimpanan. PDA tidak memiliki keyboard, namun menggunakan teknologi layar sentuh (touchscreen) sebagai media input. PDA mempunyai ukuran yang sangat kecil, sedikit diatas ukuran handphone dan dapat dengan mudah dibawa kemana-mana.

5. Komputer Workstation
Workstation sebenarnya adalah komputer desktop yang memiliki kelebihan utama dalam hal kemampuan prosesor, memory yang besar, dan kemampuannya dalam menjalankan aplikasi-aplikasi yang membutuhkan performa tinggi, seperti aplikasi 3 dimensi, grafik, multimedia dan lain sebagainya.

6. Komputer Server
Server adalah komputer diperuntukan untuk menyediakan layanan terhadap komputer lainnya (client) dalam sebuah jaringan. Komputer server memiliki prosesor yang powerfull, memory yang besar dan kapasitas harddisk yang lebih besar.

7. Komputer Mainframe
Adalah komputer dengan ukuran besar yang mampu melayani ratusan program aplikasi secara bersamaan, mendukung puluhan bahasa pemrograman yang berbeda, mampu menyimpan dan mengakses library rutin dengan kapasitas yang besar, mampu melayani ratusan transaksi secara bersamaan, bahkan lebih dan kelebihan lainnya. Komputer ini biasanya berfungsi sebagai pusat data pada perusahaan besar. Namun dengan perkembangan zaman, komputer-komputer terbaru saat ini secara bertahap akan mampu menyaingi kelebihan dari komputer mainframe ini. Untuk ukuran yang sedang disebut dengan mini komputer dan ukuran lebih kecil disebut dengan mikro komputer.

8. Wearable Computer
Wearable Computer adalah perkembangan terbaru dalam bidang komputer, yaitu perangkat komputer menyatu seperti layaknya pakaian saja. Aplikasi-aplikasi yang biasa digunakan seperti email, database, multimedia, kalender terintegrasi langsung dengan jam tangan, handphone atau dalam bentuk lainnya. Sehingga perangkat komputer sudah menyatu dalam kehidupan kita sehari-hari.

Komputer telah merambah ke berbagai sektor dalam kehidupan kita, tidak saja digunakan oleh orang kantoran, akademisi, mahasiswa, anak-anakpun sudah terbiasa dengan komputer ini. Secara sederhana, komputer dapat kita definisikan sebagai perangkat elektronik yang menerima input (dapat berupa input dari keyboard, mouse, sidik jari, retina mata, dan lain-lain) kemudian di proses oleh prosesornya dan ditampilkan melalui monitor atau dalam bentuk hardcopy (printer). komputer akan terus berkembang sesuai dengan kebutuhan manusia yang lebih mobile dan lebih simple .

Rabu, 23 Februari 2011

Alogaritma Biner

Alogaritma Biner

Algoritma menempatkan posisi dari item dalam diurutkan array.Karya pencarian biner dengan membandingkan nilai input ke elemen array tengah. Perbandingan menentukan apakah elemen sama dengan input, kurang dari masukan atau lebih. Ketika elemen yang dibandingkan dengan input sama berhenti pencarian dan biasanya mengembalikan posisi elemen. Jika elemen tidak sama dengan masukan kemudian perbandingan dibuat untuk menentukan apakah input kurang dari atau lebih besar dari elemen.Tergantung pada yang adalah algoritma kemudian mulai berakhir, tapi hanya mencari bagian atas atau bawah subset dari array yang elemen-elemen tersebut. Algoritma pencarian biner biasanya membagi dua jumlah item untuk mengecek dengan masing-masing iterasi berturut-turut, sehingga menempatkan benda yang diberikan (atau menentukan ketiadaan) dalam waktu logaritmik . Sebuah pencarian biner adalah dikotomis membagi dan menaklukkan algoritma pencarian .

Contoh dari alogaritma biner:

     23 
     48
    ___ +
 
Kita mulai dengan menambahkan 3 +8 = 11. Satu dimasukkan ke dalam kolom 10's (dilakukan), dan 1 dicatat dalam kolom seseorang dari Uang Selanjutnya, tambahkan {(2 +4) +1} (salah satu dari membawa) = 7, yang dimasukkan dalam kolom 1 yang sama, tetapi angka berbeda. Begin with one-bit binary addition: Mulailah dengan 0 tentang jumlah tersebut. Jadi, jawabannya adalah 71. 

Biner Selain bekerja pada prinsip penambahan biner satu-bit:

    0
    0
  ___ +
    0 1 

1 +1 membawa kita ke dalam kolom berikutnya. Dalam bentuk desimal, 1 +1 = 2. Dalam biner, setiap digit lebih tinggi dari 1 menempatkan kita kolom sebelah kiri (seperti yang akan 10 dalam notasi decimal). Angka desimal "2" ditulis dalam notasi biner sebagai "10" (1 * 2 ^ 1) + (0 * 2 ^ 0). Catat 0 di kolom yang, dan membawa 1 ke kolom kelompok dua-dua untuk mendapatkan jawaban dari "10. Dalam notasi vertikal kami,

    1 
  +1 
  ___ 
   10 

Proses ini sama untuk bilangan biner beberapa-bit:

         1010
        +1111
       ______ 
  • angkah satu:
    Kolom 2 ^ 0: 0 +1 = 1.
    Catatan 1.
    Hasil Sementara: 1; Carry: 0
  • Langkah dua:
    Kolom 2 ^ 1: 1 +1 = 10.
    Catat 0, membawa 1.
    Hasil Sementara: 01; Carry: 1
  • Langkah ketiga:
    Kolom 2 ^ 2: 1 +0 = 1 Tambahkan 1 dari melakukan: 1 +1 = 10.
    Catat 0, membawa 1.
    Hasil sementara: 001; Carry: 1
  • Langkah empat:
    Tambahkan 1 dari melakukan: 10 +1 = 11.
    Catat 11.
    Hasil Akhir: 11001

Bergantian:

    11 (membawa)
    1010
    1111
  ______  +
11001 

Selalu ingat

  • 0+0=0
  • 1+0=1
  • 1+1=10

Perkalian Biner

Multiplikasi dalam sistem biner bekerja dengan cara yang sama seperti dalam sistem desimal:

  • 1*1=1
  • 1*0=0
  • 0*1=0
   101                  
     11   
  ____ *
   101 
  1010  
  1111 

Perhatikan bahwa mengalikan oleh dua sangat mudah. Untuk kalikan dengan dua, cukup tambahkan 0 di ujungnya.