CPU (Central Processing Unit)

CPU (Central Processing Unit) yaitu sebuah unit pengolahan pusat yang merujuk kepada perangkat keras komputer yang memahami dan melaksanakan perintah dan data dari perangkat lunak.

A. Komponen CPU
* Unit kontrol
mampu mengatur jalannya program. Komponen ini sudah pasti terdapat dalam semua CPU.CPU bertugas mengontrol komputer sehingga terjadi sinkronisasi kerja antar komponen dalam menjalankan fungsi-fungsi operasinya. termasuk dalam tanggung jawab unit kontrol adalah mengambil intruksi-intruksi dari memori utama dan menentukan jenis instruksi tersebut. Bila ada instruksi untuk perhitungan aritmatika atau perbandingan logika, maka unit kendali akan mengirim instruksi tersebut ke ALU. Hasil dari pengolahan data dibawa oleh unit kendali ke memori utama lagi untuk disimpan, dan pada saatnya akan disajikan ke alat output. Dengan demikian tugas dari unit kendali ini adalah:
o Mengatur dan mengendalikan alat-alat input dan output.
o Mengambil instruksi-instruksi dari memori utama.
o Mengambil data dari memori utama (jika diperlukan) untuk diproses.
o Mengirim instruksi ke ALU bila ada perhitungan aritmatika atau
Perbandingan logika serta mengawasi kerja dari ALU.
o Menyimpan hasil proses ke memori utama.


* Register
merupakan alat penyimpanan kecil yang mempunyai kecepatan akses cukup tinggi, yang digunakan untuk menyimpan data dan/atau instruksi yang sedang diproses. Memori ini bersifat sementara, biasanya di gunakan untuk menyimpan data saat di olah ataupun data untuk pengolahan selanjutnya. Secara analogi, register ini dapat diibaratkan sebagai ingatan di otak bila kita melakukan pengolahan data secara manual, sehingga otak dapat diibaratkan sebagai CPU, yang berisi ingatan-ingatan, satuan kendali yang mengatur seluruh kegiatan tubuh dan mempunyai tempat untuk melakukan perhitungan dan perbandingan logika.

* ALU
unit yang bertugas untuk melakukan operasi aritmetika dan operasi logika berdasar instruksi yang ditentukan. ALU sering di sebut mesin bahasa karena bagian ini ALU terdiri dari dua bagian, yaitu unit arithmetika dan unit logika boolean yang masing-masing memiliki spesifikasi tugas tersendiri. Tugas utama dari ALU adalah melakukan semua perhitungan aritmatika (matematika) yang terjadi sesuai dengan instruksi program. ALU melakukan semua operasi aritmatika dengan dasar penjumlahan sehingga sirkuit elektronik yang digunakan disebut adder.

Tugas lain dari ALU adalah melakukan keputusan dari suatu operasi logika sesuai dengan instruksi program. Operasi logika meliputi perbandingan dua operand dengan menggunakan operator logika tertentu, yaitu sama dengan (=), tidak sama dengan (¹ ), kurang dari (<), kurang atau sama dengan (£ ), lebih besar dari (>), dan lebih besar atau sama dengan (³ ).

* CPU Interconnections
Adalah sistem koneksi dan bus yang menghubungkan komponen internal CPU, yaitu ALU, unit kontrol dan register-register dan juga dengan bus-bus eksternal CPU yang menghubungkan dengan sistem lainnya, seperti memori utama, piranti masukan /keluaran.

B. Diagram Blok CPU





C. CARA KERJA CPU

Saat data dan/atau instruksi dimasukkan ke processing-devices, pertama sekali diletakkan di RAM (melalui Input-storage); apabila berbentuk instruksi ditampung oleh Control Unit di Program-storage, namun apabila berbentuk data ditampung di Working-storage). Jika register siap untuk menerima pengerjaan eksekusi, maka Control Unit akan mengambil instruksi dari Program-storage untuk ditampungkan ke Instruction Register, sedangkan alamat memori yang berisikan instruksi tersebut ditampung di Program Counter. Sedangkan data diambil oleh Control Unit dari Working-storage untuk ditampung di General-purpose register (dalam hal ini di Operand-register). Jika berdasar instruksi pengerjaan yang dilakukan adalah arithmatika dan logika, maka ALU akan mengambil alih operasi untuk mengerjakan berdasar instruksi yang ditetapkan. Hasilnya ditampung di Accumulator. Apabila hasil pengolahan telah selesai, maka Control Unit akan mengambil hasil pengolahan di Accumulator untuk ditampung kembali ke Working-storage. Jika pengerjaan keseluruhan telah selesai, maka Control Unit akan menjemput hasil pengolahan dari Working-storage untuk ditampung ke Output-storage. Lalu selanjutnya dari Output-storage, hasil pengolahan akan ditampilkan ke output-devices.
[sunting] Fungsi CPU

CPU berfungsi seperti kalkulator, hanya saja CPU jauh lebih kuat daya pemrosesannya. Fungsi utama dari CPU adalah melakukan operasi aritmatika dan logika terhadap data yang diambil dari memori atau dari informasi yang dimasukkan melalui beberapa perangkat keras, seperti papan ketik, pemindai, tuas kontrol, maupun tetikus. CPU dikontrol menggunakan sekumpulan instruksi perangkat lunak komputer. Perangkat lunak tersebut dapat dijalankan oleh CPU dengan membacanya dari media penyimpan, seperti cakram keras, disket, cakram padat, maupun pita perekam. Instruksi-instruksi tersebut kemudian disimpan terlebih dahulu pada memori fisik (RAM), yang mana setiap instruksi akan diberi alamat unik yang disebut alamat memori. Selanjutnya, CPU dapat mengakses data-data pada RAM dengan menentukan alamat data yang dikehendaki.

Saat sebuah program dieksekusi, data mengalir dari RAM ke sebuah unit yang disebut dengan bus, yang menghubungkan antara CPU dengan RAM. Data kemudian didekode dengan menggunakan unit proses yang disebut sebagai pendekoder instruksi yang sanggup menerjemahkan instruksi. Data kemudian berjalan ke unit aritmatika dan logika (ALU) yang melakukan kalkulasi dan perbandingan. Data bisa jadi disimpan sementara oleh ALU dalam sebuah lokasi memori yang disebut dengan register supaya dapat diambil kembali dengan cepat untuk diolah. ALU dapat melakukan operasi-operasi tertentu, meliputi penjumlahan, perkalian, pengurangan, pengujian kondisi terhadap data dalam register, hingga mengirimkan hasil pemrosesannya kembali ke memori fisik, media penyimpan, atau register apabila akan mengolah hasil pemrosesan lagi. Selama proses ini terjadi, sebuah unit dalam CPU yang disebut dengan penghitung program akan memantau instruksi yang sukses dijalankan supaya instruksi tersebut dapat dieksekusi dengan urutan yang benar dan sesuai.
[sunting] Percabangan instruksi

Pemrosesan instruksi dalam CPU dibagi atas dua tahap, Tahap-I disebut Instruction Fetch, sedangkan Tahap-II disebut Instruction Execute. Tahap-I berisikan pemrosesan CPU dimana Control Unit mengambil data dan/atau instruksi dari main-memory ke register, sedangkan Tahap-II berisikan pemrosesan CPU dimana Control Unit menghantarkan data dan/atau instruksi dari register ke main-memory untuk ditampung di RAM, setelah Instruction Fetch dilakukan. Waktu pada tahap-I ditambah dengan waktu pada tahap-II disebut waktu siklus mesin (machine cycles time).

Penghitung program dalam CPU umumnya bergerak secara berurutan. Walaupun demikian, beberapa instruksi dalam CPU, yang disebut dengan instruksi lompatan, mengizinkan CPU mengakses instruksi yang terletak bukan pada urutannya. Hal ini disebut juga percabangan instruksi (branching instruction). Cabang-cabang instruksi tersebut dapat berupa cabang yang bersifat kondisional (memiliki syarat tertentu) atau non-kondisional. Sebuah cabang yang bersifat non-kondisional selalu berpindah ke sebuah instruksi baru yang berada di luar aliran instruksi, sementara sebuah cabang yang bersifat kondisional akan menguji terlebih dahulu hasil dari operasi sebelumnya untuk melihat apakah cabang instruksi tersebut akan dieksekusi atau tidak. Data yang diuji untuk percabangan instruksi disimpan pada lokasi yang disebut dengan flag.


Bilangan yang dapat ditangani

Kebanyakan CPU dapat menangani dua jenis bilangan, yaitu fixed-point dan floating-point. Bilangan fixed-point memiliki nilai digit spesifik pada salah satu titik desimalnya. Hal ini memang membatasi jangkauan nilai yang mungkin untuk angka-angka tersebut, tetapi hal ini justru dapat dihitung oleh CPU secara lebih cepat. Sementara itu, bilangan floating-point merupakan bilangan yang diekspresikan dalam notasi ilmiah, di mana sebuah angka direpresentasikan sebagai angka desimal yang dikalikan dengan pangkat 10 (seperti 3,14 x 1057). Notasi ilmiah seperti ini merupakan cara yang singkat untuk mengekspresikan bilangan yang sangat besar atau bilangan yang sangat kecil, dan juga mengizinkan jangkauan nilai yang sangat jauh sebelum dan sesudah titik desimalnya. Bilangan ini umumnya digunakan dalam merepresentasikan grafik dan kerja ilmiah, tetapi proses aritmatika terhadap bilangan floating-point jauh lebhttp://www.blogger.com/post-create.g?blogID=8787501002580000730ih rumit dan dapat diselesaikan dalam waktu yang lebih lama oleh CPU karena mungkin dapat menggunakan beberapa siklus detak CPU. Beberapa komputer menggunakan sebuah prosesor sendiri untuk menghitung bilangan floating-point yang disebut dengan FPU (disebut juga math co-processor) yang dapat bekerja secara paralel dengan CPU untuk mempercepat penghitungan bilangan floating-point. FPU saat ini menjadi standar dalam banyak komputer karena kebanyakan aplikasi saat ini banyak beroperasi menggunakan bilangan floating-point.


Sumber : http://id.wikipedia.org/wiki/Unit_Pengolah_Pusat

SISTEM I/O

Unit Input/Output (I/O) adalah bagian dari mikroprosesor yang digunakan oleh mikroprosesor itu untuk berhubungan dengan dunia luar. Unit input adalah unit luar yang digunakan untuk memasukan data dari luar kedalam mikroprosesor ini, contohnya data yang berasal dari keyboard dan mouse. sedangkan unit output biasanya untuk menampilkan data contohnya monitor, printer, dll.

Sistem I/O terdiri dari:
a. Perangkat Keras I/O
b. Aplikasi Antarmuka I/O
c. Kernel I/O
d. Mengubah I/O Request menjadi operasi perangkat keras
e. Streams
f. Performance

a. Perangkat Keras I/O
Konsep Umum :
> Port
> Bus (Daisy chain atau shared direct access)
> Controller (host adapter)
Perangkat kontrol instruksi I/O
Perangkat-perangkat tersebut memiliki alamat, digunakan untuk:
> Instruksi I/O langsung
> Memory-mapped I/O

Jenis Perangkat Keras
> Perangkat penyimpan data
> Perangkat penghubung
> Perangkat antarmuka dengan user

Suatu perangkat berhubungan dengan sistem komputer dengan cara mengirim sinyal melalui suatu kabel atau bahkan melalui udara Perangkat tersebut berkomunikasi dengan mesin melalui port, Struktur komputer yang umum dipakai adalah Daisy Chain.

DIAGRAM BLOK ARSITEKTUR KOMPUTER



POLLING
> Host terus membaca busy-bit secara berulang-ulang sampai bit tersebut clear
> Host set write-bit di command-register dan menulis satu byte di data-out register
> Host set bit command-ready
> Ketika controller mengetahui kalau bit command-ready di-set, dia men-set busy bit
> Controller membaca command-register dan melihat perintah tulis. Dia membaca
data-out register untuk mendapatkan bytenya, dan melakukan operasi I/O
> Controller menghapus bit command-ready, membersihkan bit error di status register
yang menandakan operasi I/O berhasil,dan menghapus busy-bit yang menandakan kalau
operasi sudah selesai.

Interrupt
> Jalur interrupt dihasilkan oleh perangkat I/O
> Interrupt Handler menerima interrupt tersebut
> Mekanisme interrupt juga digunakan untuk penanganan exception

Interrupt-Driven I/O Cycle



Direct Memory Access (DMA)
> Generasi komputer yang sangat tua
@ Controller membaca dari perangkat
@ Sistem Operasi meminta controller membaca data
> Generasi komputer yang tua
@ Controller membaca dari perangkat
@ Controller meng-interrupt OS
@ Sistem Operasi menyalin data ke memori
> Generasi DMA
@ Controller membaca dari perangkat
@ Controller menyalin data ke memori
@ Controller meng-interrupt OS

DMA Transfer



Aplikasi Antar-Muka I/O
> Sifat-sifat perangkat komputer diabstraksi oleh I/O system call berbentuk
kelas-kelas umum.
> Lapisan driver perangkat menyembunyikan perbedaanperbedaan I/O controller dari
kernel.
> Ragam device dari beberapa sisi:
> Character-stream atau block
> Sequential atau random-access
> Synchronous atau asynchronous
> Sharable atau dedicated
> Speed atau operation
> Read-write, read only, write only

Perangkat Block dan Character
> Perangkat block:
Ø Meliputi berbagai disk drive
Ø Perintah baca, tulis, pencarian data
Ø Dimungkinkan untuk mengakses berkas secara memorymapped
> Perangkat character:
Ø Contoh: keyboard, mouse
Ø Perintah menulis, mengambil
Ø Dapat dibuat library pengakses data per-baris

Perangkat Jaringan
> Interface berbeda dari baca, tulis disk, disebut interface socket.
> Socket: penghubung komputer dengan jaringan.
> Local socket dihubungkan dengan remote socket.
> Komunikasi antar komputer dilakukan melalui socket.

Clock dan Timer
> Fungsi clock dan timer pada hardware:
Ø Waktu saat ini
Ø Lama sebuah proses
ØTrigger proses pada suatu waktu
> Programmable interval timer : hardware pengukur waktu dan trigger.
> Sistem operasi mampu menangani time request lebih banyak dari jumlah hardware timer

Blocking dan Non-blocking I/O
> Blocking : proses dihentikan sementara
Ø Lebih mudah dimengerti
Ø Tidak cukup untuk beberapa hal
> Non-blocking : diimplementasikan lewat multi-threading
> Asynchronous : proses berjalan selama I/O dieksekusi

Kernel I/O Subsystem
> Scheduling :
* Permohonan I/O dilakukan berdasarkan antrian perangkat
* Beberapa sistem operasi berusaha untuk seadil mungkin
> Buffering : menyimpan data di memori selama proses transfer antar perangkat
* Solusi perbedaan kecepatan dari perangkat yang ada
* Solusi perbedaan ukuran transfer perangkat

Struktur Data Kernel
> Kernel menyimpan informasi penggunaan komponen I/O, termasuk tabel open-file
koneksi networking, informasi karakter device.
> Struktur data yang rumit dapat digunakan untuk memeriksa buffer, alokasi memori,
dan menentukan batasan sektor/blok.
> Beberapa sistem operasi menggunakan tehnik object oriented untuk mengkapsulasikan
perbedaan-perbedaan semantik yang ada.

Transformasi I/O Menjadi Operasi H/W
Proses:
> Blocking read system call diberikan pada pendeskripsi data dari data yang sudah
terbuka sebelumnya.
> Kode di kernel memeriksa parameter. Dalam proses input, jika data sudah ada di
buffer, data dikembalikan ke proses dan permintaan I/O selesai.

Contoh: membaca data dari disk untuk di proses.
> Menentukan device yang mengandung data,
> Menerjemahkan nama ke perwakilan device
> Secara fisik memindahkan data dari disk ke buffer
> Mempersiapkan data untuk proses permintaan I/O
> Mengembalikan kontrol ke proses

I/O Stream
> I/O stream adalah suatu mekanisme pengiriman data secara bertahap dan terus
menerus melalui suatu aliran data (dua arah)
> Biasa digunakan dalam network protocol
> Asynchronous
> Menggunakan message passing dalam men-transfer data
> Untuk memasukkan ke dalam stream digunakan ioctl system call
> Untuk menuliskan data ke device digunakan write / putmsg system call
> Untuk membaca data dari device digunakan read / getmsg system call
> User process: berhubungan langsung dengan stream head
> Ada beberapa modul dengan write dan read queue
> Device berhubungan langsung dengan driver

Kinerja I/O
> Pembuat CPU melaksanakan kode device-driver
> Memberitahukan ke-tidak efisien-an pada mekanisme penanganan interrupt dalam kernel
> Me-load memory bus sewaktu menyalin data yang dilakukan di controller dan physical
memory

Meningkatkan Kinerja I/O
> Memperkecil jumlah context switch
> Memperkecil jumlah penyalinan data yang dilakukan sewaktu pengoperan data antara
device dan aplikasi
> Memperkecil jumlah interrupt dengan menggunakan transfer secara besar-besaran,
smart controllers dan polling (jika busywaiting bisa diminimalisir)
> Menambah konkurensi dengan menggunakan DMA controllers atau channels yang telah
diketahui untuk meng-offload pennyalin sederhana dari CPU
> Memindahkan proses-proses primitif ke perangkat keras, untuk membuat operasinya
dalam device controllers konkuren dengan CPU dan operasi Bus
> Menyeimbangkan CPU, memory subsystem, bus, dan I/O performance, karena kelebihan
di salah satu area akan membuat keterlambatan pada yang lain.

Multiflexer dan Demultiflexer

A. Pengertian Multiplexer dan Demultiplexer
> Multiplexer adalah rangkaian logika yang menerima beberapa input data digital dan menyeleksi salah satu dari input tersebut pada saat tertentu untuk dikeluarkan pada sisi output.
> Demultiplexer adalah rangkain logika yang menerima satu input data digital dan mendistribusikan input tersebut ke beberapa output.



MULTIPLEXER : > Perangkat pemilih beberapa jalur data kedalam satu jalur data untuk dikirim ketitik lain.
> Mempunyai dua atau lebih signal digit sebagai input dan control sebagai pemilih (selector).
> Merupakan data selector (pemilih data)



Diagram Logika untuk 4 jalur multiplexer



IC 74151 Multiplexer 8 Jalur Input








DEMULTIPLEXER : > Kebalikan dari multiplexer.
> Mempunyai satu input data dan beberapa output data.
> Merupakan data distributor (distribusi data)





IC 74139 Demultiplexer 2-4 Jalur ( 2 Selector dan 4 jalur Output )



Diagram Logika IC 74139 Demultiplexer 2-4 jalur






Referensi : 1. http://www.scribd.com/doc/19169115/Multiplexer
2. http://id.wikipedia.org/wiki/Multiplekser

Arsitektur Komputer

Arsitektur Komputer

Secara umum komputer dapat diartikan sebagai alat elektronika yang bekerja secara koordinasi dan integrasi berdasarkan program, dapat menerima masukan berupa data yang diproses didalam suatu sistem dan dikeluarkan dalam bentuk informasi.

Adapaun Arsitektur komputer tersebut adalah sebagai berikut :


1. Input Device (Alat Masukan)

Adalah perangkat keras komputer yang berfungsi sebagai alat untuk memasukan data atau perintah ke dalam komputer.

2. Output Device (Alat Keluaran)

Adalah perangkat keras komputer yang berfungsi untuk menampilkan keluaran sebagai hasil pengolahan data. Keluaran dapat berupa hard-copy (ke kertas), soft-copy (ke monitor), ataupun berupa suara.

3. I/O Ports

Bagian ini digunakan untuk menerima ataupun mengirim data ke luar sistem. Peralatan input dan output di atas terhubung melalui port ini.

4. CPU (Central Processing Unit)

CPU merupakan otak sistem komputer, dan memiliki dua bagian fungsi operasional, yaitu: ALU (Arithmetical Logical Unit) sebagai pusat pengolah data, dan CU (Control Unit) sebagai pengontrol kerja komputer.

5. Memori

Memori terbagi menjadi dua bagian yaitu memori internal dan memori eksternal. Memori internal berupa RAM (Random Access Memory) yang berfungsi untuk menyimpan program yang kita olah untuk sementara waktu, dan ROM (Read Only Memory) yaitu memori yang haya bisa dibaca dan berguna sebagai penyedia informasi pada saat komputer pertama kali dinyalakan.

6. Data Bus

Adalah jalur-jalur perpindahan data antar modul dalam sistem komputer. Karena pada suatu saat tertentu masing-masing saluran hanya dapat membawa 1 bit data, maka jumlah saluran menentukan jumlah bit yang dapat ditransfer pada suatu saat. Lebar data bus ini menentukan kinerja sistem secara keseluruhan. Sifatnya bidirectional, artinya CPU dapat membaca dan menirma data melalui data bus ini. Data bus biasanya terdiri atas 8, 16, 32, atau 64 jalur paralel.

7. Address Bus

Digunakan untuk menandakan lokasi sumber ataupun tujuan pada proses transfer data. Pada jalur ini, CPU akan mengirimkan alamat memori yang akan ditulis atau dibaca. Address bus biasanya terdiri atas 16, 20, 24, atau 32 jalur paralel.

8. Control Bus

Control Bus digunakan untuk mengontrol penggunaan serta akses ke Data Bus dan Address Bus. Terdiriatas 4 samapai 10 jalur paralel.

Referensi : http://www.scribd.com/doc/10916989/Organisasi-Dan-Arsitektur-Komputer

Algoritma Binary Search

A. Pengertian
Binary Search adalah algoritma pencarian yang lebih efisien daripada algorima Sequential Search. Hal ini dikarenakan algoritma ini tidak perlu menjelajahi setiap elemen dari tabel. Kerugiannya adalah algoritma ini hanya bisa digunakan pada tabel yang elemennya sudah terurut baik menaik maupun menurun.
Pada intinya, algoritma ini menggunakan prinsip divide and conquer, dimana sebuah masalah atau tujuan diselesaikan dengan cara mempartisi masalah menjadi bagian yang lebih kecil. Algoritma ini membagi sebuah tabel menjadi dua dan memproses satu bagian dari tabel itu saja.
Algoritma ini bekerja dengan cara memilih record dengan indeks tengah dari tabel dan membandingkannya dengan record yang hendak dicari. Jika record tersebut lebih rendah atau lebih tinggi, maka tabel tersebut dibagi dua dan bagian tabel yang bersesuaian akan diproses kembali secara rekursif.

B. Keunggulan
Keunggulan utama dari algoritma binary search adalah kompleksitas algoritmanya yang lebih kecil daripada kompleksitas algoritma sequential search. Hal ini menyebabkan waktu yang dibutuhkan algoritma binary search dalam mencari sebuah record dalam sebuah tabel lebih kecil daripada waktu yang dibutuhkan algoritma sequential search.

C. Fungsi
Pencarian Biner (Binary Search) dilakukan untuk :
1. 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.

2. 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).

3. Syarat utama untuk pencarian biner adalah data di dalam tabel harus sudah terurut, misalkan terurut menaik.


ALGORITMA

Kamus
Const N : integer = 8 { misalkan jumlah elemen array maksimum = 8 }
Type A = array [ 1 ..... N ] of integer
Cari, BatasAtas, BatasBawah, Tengah : Integer
Ketemu : boolean
ALGORITMA
Input (cari) { meminta nilai data yang akan dicari}
BatasAtas  1 { indeks array dimulai dari 1 }
BatasBawah  N
Ketemu  False
While (BatasAtas < BatasBawah) and (not ketemu) do
Tengah  (BatasAtas + BatasBawah) div 2
If A [Tengah] = cari then
Ketemu  true
Else
If ( A [Tengah] < cari ) then { cari di bagian kanan }
BatasAtas  Tengah + 1
Else
BatasBawah  Tengah – 1 { cari di bagian kiri }
Endif
Endif
EndWhile
If (ketemu) then
Output ( ‘Data berada di index nomor’, Tengah )
Else Output ( ‘Data tidak ditemukan’ )
Endif


CONTOH

Contoh Nilai-Nilai data yang sudah terurut :

A 2 5 8 12 15 25 37 57
1 2 3 3 5 6 7 8

Kasus 1 : cari = 12
Loop pertama : Tengah = (BatasAtas + BatasBawah) div 2 = (1 + 8) div 2 = 4
A [Tengah] = A [4] = 12, berarti loop pertama data langsung ditemukan

Kasus 2 : cari = 15
Loop pertama : Tengah = (BatasAtas + BatasBawah) div 2 = (1 + 8) div 2 = 4
A [Tengah] = A [4] = 12 < cari = 15, berarti BatasAtas = Tengah + 1 = 4 + 1 = 5
Loop kedua : Tengah = (BatasAtas + BatasBawah) div 2 = (5 + 8) div 2 = 6
A [Tengah] = A [6] = 25 > cari = 15, berarti BatasBawah = Tengah - 1 = 6 - 1 = 5
Loop ketiga : Tengah = (BatasAtas + BatasBawah) div 2 = (5 + 5) div 2 = 5
A [Tengah] = A [5] = 15, berarti setelah loop ketiga, data ditemukan

Kasus 3 : cari = 10
Loop pertama : Tengah = (BatasAtas + BatasBawah) div 2 = (1 + 8) div 2 = 4
A [Tengah] = A [4] = 12 > cari = 10, berarti BatasBawah = Tengah - 1 = 4 - 1 = 3
Loop kedua : Tengah = (BatasAtas + BatasBawah) div 2 = (1 + 3) div 2 = 2
A [Tengah] = A [2] = 5 < cari = 10, berarti BatasAtas = Tengah + 1 = 2 + 1 = 3
Loop ketiga : Tengah = (BatasAtas + BatasBawah) div 2 = (3 + 3) div 2 = 3
A [Tengah] = A [3] = 8, berarti setelah loop ketiga, data tidak ditemukan

Untuk jumlah data sebanyak n, maka proses pembandingan maksimal sebanyak ( log n ) kali. Untuk contoh di atas, jumlah data 8, maka proses pembandingan maksimal sebanyak 3 kali.

Algoritma Divide dan Conquer

Divide and Conquer adalah metode pemecahan

masalah yang bekerja dengan membagi masalah menjadi

beberapa upa-masalah yang lebih kecil, kemudian

menyelesaikan masing-masing upa-masalah tersebut

secara independen, dan akhirnya menggabungkan solusi

masing-masing upamasalah sehingga menjadi solusi dari

masalah semula.

Pada algortima Divide and Conquer ini meiliki tiga proses

utama yaitu:

- Divide: membagi masalah menjadi beberapa upamasalah

yang memiliki kemiripan dengan masalah semula namun

berukuran lebih kecil (idealnya berukuran hampir sama),

- Conquer: memecahkan (menyelesaikan) masingmasing

upa-masalah (secara rekursif), dan

- Combine: mengabungkan solusi masing-masing upamasalah

sehingga membentuk solusi masalah semula.

Pada algoritma ini, tiap-tiap upa-masalah mempunyai

karakteristik yang sama (the same type) dengan

karakteristik masalah asal, sehingga metode Divide and

Conquer lebih natural diungkapkan dalam skema rekursif.

Secara umum, algoritma Divide and Conquer memiliki

sekema sbb:

procedure DIVIDE_and_CONQUER(input n :

integer)

{ Menyelesaikan masalah dengan

algoritma Dand-

C.

Masukan: masukan yang berukuran n

Keluaran: solusi dari masalah semula

}

Deklarasi

r, k : integer

Algoritma

if n ≤ n0 then {ukuran masalah sudah

cukup

kecil }

SOLVE upa-masalah yang berukuran n ini

else

Dalam Algoritma divide dan conquer Pemrogram bertanggung jawab atas implementasi solusi. Pembuatan program akan menjadi lebih sederhana jika masalah dapat dipecah menjadi sub masalah - sub masalah yang dapat dikelola.

Penyelesaian masalah dengan komputer berhadapan dengan 4 hal, yaitu :

1. Pemahaman keterhubungan elemen-elemen data yang relevan terhadap solusi secara menyeluruh.

2. Pengambilan keputusan mengenai operasi-operasi yang dilakukan terhadap elemen-elemen data.

3. Perancangan representasi elemen-elemen data di memori sehingga memenuhi kriteria berikut:

a. Memenuhi keterhubungan logik antara elemen-elemen data.

b. Operasi-operasi terhadap elemen-elemen data dapat dilakukan secara mudah dan efisien.

4. Pengambilan keputusan mengenai mengenai bahasa pemrograman terbaik untuk menerjemahkan solusi persoalan menjadi program.

STRATEGI DIVIDE DAN CONQUER

Metode

Strategi Divide dan Conquer memecah masalah menjadi submasalah-submasalah independen yang lebih kecil sehingga solusi submasalah-submasalah dapat diperoleh secara mudah, solusi submasalah-submasalah digabung menjadi solusi seluruh masalah.

Skema umum algoritma divide dan conquer

Procedure DNC ( i,j : integer )

Var K : integer ;

If SMALL (i,j) then SOLVE (i,j)

Else begin

K : = DIVIDE (i,j)

COMBINE (DNC(i,k),DNC(k+1,j))

End if

Keterangan :

1. SMALL adalah fungsi yang mengirim BOOLEAN, menentukan apakah ukuran telah cukup kecil sehingga solusi dapat diperoleh. Ukuran dinyatakan sebagai telah berukuran kecil bergantung masalah.

2. DIVIDE adalah fungsi membagi menjadi 2 bagian pada posisi K. Biasanya bagian berukuran sama.

3. COMBINE adalah fungsi menggabungkan solusi X dan Y submasalah. Solusi diperoleh dengan memanggil prosedur rekursif DNC.

Jika ukuran kedua submasalah sama, waktu komputasi DNC dideskripsikan hubungan rekuren berikut :

T(n) = g (n), n kecil

2 T (n/2) + f (n), selainnya

dimana :

· T(n) adalah waktu untuk DNC dengan n masukan,

· g(n) adalah waktu komputasi jawaban secara langsung untuk masukan kecil dan

· f(n) adalah waktu COMBINE.

Untuk algoritma divide dan conquer yang menghasilkan submasalah-submasalah dengan tipe masalah yang sama dengan masalah awal, sangat alami untuk mendeskripsikan algoritma secara rekursi. Kemudian untuk meningkatkan efisiensi dilakukan penerjemahan menjadi bentuk iterasi.

Pemakaian teknik Divide dan Conquer banyak digunakan dalam menyelesaikan berbagai macam persoalan, antara lain :

1. Searching

2. Sorting

Sumber : http://pdflost.com/download/5991507/

Algoritma Kruskall

Contoh : Pandang sebuah graph sebagai berikut;

Algoritma Kruskall

Dasar pembentukan algoritma Kruskal berasal dari analogi growing forest. Growing forest maksudnya adalah untuk membentuk pohon merentang minimum T dari grafG adalah dengan cara mengambil satu per satu sisi dari graf G dan memasukkannya ke dalam pohon yang telah terbentuk sebelumnya. Seiring dengan berjalannya iterasi untuk setiap sisi, maka forest akan memiliki pohon yang semakin sedikit. Oleh sebab itu, maka analogi ini disebut dengan growing forest. Algoritma Kruskal akan terus menambahkan sisi – sisi ke dalam hutan yang sesuai hingga akhirnya tidak akan ada lagi forest dengan, melainkan hanyala

h sebuah pohon yang merentang minimum.Soal diatas dapat dijawab dengan menggunakan Algoritma Kruskall seperti ditunjukkan dibawah ini :.

-------Edge----- Cost

1. ( 1,2 )----- 10
   
2. ( 3,6 )----- 15
   
3. ( 4,6 )----- 20
   
4. ( 2,6 )----- 25
   
5. ( 1,4 )----- 30
6. ( 3,5 )----- 35

Maka Spanning Tree- nya adalah

Sehingga total costnya ialah 105

Tugas: (minimum spanning tree dan total cost nya)