Breaking News

Advertising

Flickr

Latest Reviews

Facebook

Selasa, 30 Juni 2015

Pengantar Komputer 9-14

Pertemuan 9
MEMORI

I. Pengertian
Memori adalah bagian dari komputer tempat programprogram
dan data-data disimpan.
Memori utama (main memory) menyimpan data dan
program yang akan dijalankan oleh CPU.
Semakin cepat memori utama, semakin cepat permintaan
akses data yang akan diproses oleh CPU.

Parameter terpenting dalam sistem memori adalah:
1. Kapasitas (capacity): jumlah maksimum unit yang
dapat disimpannya.
2. Waktu pengaksesan (access time): waktu yang
diperlukan untuk mengakses data.
3. Kecepatan transfer (data transfer rate): jumlah bit
per detik data yang dapat dibaca.
4. Waktu siklus (cycle time): ukuran seberapa sering
memori dapat diakses.
5. Biaya (cost): biasa diekspresikan dalam bentuk rupiah
per bit.

II. Manajemen Memori Komputer
Terdapat 2 (dua) manajemen memori:
a. Manajeman memori statis
Dengan pemartisian statis, jumlah, lokasi dan ukuran
proses di memori tidak beragam sepanjang waktu
secara tetap.
b. Manajemen memori dinamis
Dengan pemartisian dinamis, jumlah, lokasi dan
ukuran proses di memori dapat beragam sepanjang
waktu secara dinamis.

II.1. Manajemen Memori Berdasarkan Alokasi
Memori
Terdapat dua cara menempatkan informasi ke dalam
memori, yaitu:
A. Alokasi Memori Berurutan (Contiguous Allocation)
Setiap proses menempati satu blok tunggal lokasi
memori yang berurutan.
Kelebihan: sederhana, tidak ada rongga memori
bersebaran, proses berurutan dapat dieksekusi
secara cepat.
Kekurangan: memori boros, tidak dapat disisip
apabila tidak ada satu blok memori yang mencukupi

B. Alokasi Memori Tak Berurutan (Non Contiguous
Allocation)
Setiap proses ditempatkan pada beberapa segmen
berserakan, tidak perlu saling berdekatan atau
berurutan.
Kelebihan: sistem dapat memanfaatkan memori
utama secara lebih efisien, dan dapat menyisip
proses bila jumlah lubang-lubang memori cukup
untuk memuat proses yang akan dieksekusi.
Kekurangan: memerlukan pengendalian yang lebih
rumit dan memori jadi banyak yang berserakan tidak
terpakai

II.2. Manajemen Memori Berdasarkan Keberadaan
A. Dengan Swapping
Tanpa pemindahan citra/gambaran proses antara
memori utama dan disk selama eksekusi
B. Tanpa Swapping
Dengan memindahan citra/gambaran proses antara
memori utama dan disk selama eksekusi.
Swapping adalah pemindahan proses dari memori utama
ke disk dan sebaliknya.

II.3. Manajemen Memori Tanpa Swapping
A.Monoprogramming
Sistem komputer hanya mengijinkan satu proses
berjalan pada satu waktu.
B.Multiprogramming
Sistem komputer mengijinkan banyak proses berjalan
pada satu waktu.
1. Dengan Swapping
2. Dengan pemartisian dinamis

II.4. Pencatatan Pemakaian Memori
A. Pencatatan memakai peta bit.
Masalah pada peta bit adalah penetapan mengenai
ukuran unit alokasi memori, yaitu:
Unit lokasi memori berukuran kecil berarti
membesarkan ukuran peta bit.
Unit lokasi memori berukuran besar berarti peta bit
kecil tapi memori banyak disiakan pada unit terakhir
jika ukuran proses bukan kelipatan unit lokasi
B. Pencatatan memakai penghubung berkait
Sistem Operasi mengelola penghubung berkait (linked
list) untuk segmen memori yang telah dialokasikan
dan bebas.
Penghubung segmen diurutkan sesuai alamat blok.

III. Karakteristik Sistem Memori
III.1. Berdasarkan Lokasi
A.Register
- Berada di dalam chip prosesor
- diakses langsung oleh prosesor
- digunakan sebagai memori sementara untuk
perhitungan maupun pengolahan data prosesor
B.Memori Internal
- Berada di luar chip prosesor
- diakses langsung oleh prosesor
- dibedakan menjadi memori utama dan cache memori
C.Memori Eksternal
- Berada di luar chip prosesor
- Diakses oleh prosesor via piranti I/O
- Dapat berupa disk atau pita magnetik

III.2. Berdasarkan Kapasitas
- dinyatakan dalam bentuk byte (1 byte = 8 bit) atau
word (1 word = 8 bit, 16 bit, 32 bit)
- kapasitas lebih besar daripada memori internal
III.3. Berdasarkan Satuan Transfer
- Word, ukuran word biasanya sama dengan jumlah bit
yang digunakan untuk representasi bilangan dan
panjang instruksi.
- Addressable units, pada sejumlah sistem, adressable
units adalah word. Namun terdapat sistem dengan
pengalamatan pada tingkatan byte.
- Unit of transfer, adalah jumlah bit yang dibaca atau
dituliskan ke dalam memori pada suatu saat. Pada
memori eksternal, transfer data biasa disebut block.

III.4. Berdasarkan Metode Akses
A.Sequential Access
- memori diorganisasi menjadi unit-unit data record
- akses harus dibuat dalam bentuk urutan linier (urut)
- Contoh: pita magnetik
B.Direct Access
- memori diorganisasi menjadi unit-unit data blok dan
record
- blok dan record memiliki alamat unik berdasarkan
lokasi fisiknya.
- akses dilakukan secara langsung pada alamat memori
- Contoh: magnetik disk

C.Random Access
- setiap lokasi memori dipilih secara random dan
diakses serta dialamati secara langsung
- Contoh: memori utama
D.Associative access
- data dicari berdasarkan isinya bukan alamatnya
dalam memori
- Contoh: cache memori

III.5. Berdasarkan Unjuk Kerja
- Access Time, adalah waktu yang dibutuhkan untuk
melakukan operasi baca atau tulis.
- Memory Cycle Time, konsep ini digunakan pada
random access memory dan terdiri dari access time
ditambah dengan waktu yang diperlukan transient agar
hilang pada saluran sinyal.
- Transfer rate, adalah kecepatan data transfer ke unit
memori atau dari unit memori.

III.6. Berdasarkan Tipe Fisik
- Memori Semikonduktor
Memori ini memakai teknologi LSI atau VLSI, banyak
digunakan untuk memorI internal misalnya RAM
- Memori Permukaan Magnetik
Banyak digunakan untuk memorI eksternal seperti disk
atau pita magnetik.

III.7. Berdasarkan Karakteristik Fisik
- Volatile, informasi akan hilang apabila daya listriknya
dimatikan
- NonVolatile, informasi tidak akan hilang apabila daya
listriknya dimatikan
- Erasable, isi memori dapat dihapus dan diganti
dengan informasi lain
- NonErasable, isi memori tidak dapat dihapus atau
diganti

III.8. Berdasarkan Organisasi
Organisasi adalah pengaturan bit dalam menyusun
word secara fisik.
Hirarki Memori :
Semakin kecil waktu akses, semakin besar harga
per bitnya.
Semakin besar kapasitas, semakin kecil harga per
bitnya.
Semakin besar kapasitas, semakin besar waktu
aksesnya.
Untuk kinerja yang optimal, diperlukan kombinasi
teknologi komponen memori

Semakin menurun hirarki,
maka akan terjadi:
Penurunan harga per bit
Peningkatan kapasitas
Peningkatan waktu akses
Penurunan frekuensi
akses memori oleh CPU.
Memori Semikonduktor

Pertemuan 10
MEMORI INTERNAL


I. Pengertian
Memori internal adalah memori yang dapat diakses
langsung oleh prosesor.
Fungsi dari memori utama adalah:
Menyimpan data yang berasal dari peranti masukan
sampai data dikirim ke ALU (Arithmetic and Logic Unit)
untuk diproses
Menyimpan data hasil pemrosesan ALU sebelum
dikirimkan ke peranti keluaran (dapat berupa data atau
program).
Menampung program/instruksi yang berasal dari
peranti masukan atau dari peranti pengingat sekunder.

II. Memori Semikonduktor
II.1. Random Access Memori (RAM)
data diakses secara langsung melalui alamat sehingga
dimungkinkannya pembacaan dan penulisan data ke
memori secara cepat dan mudah
bersifat volatile, sehingga RAM hanya menyimpan data
sementara
Operasi RAM: memori read/write dan memori read-only
Terdiri dari RAM dinamik dan RAM statik

Jenis-Jenis RAM
1. Dynamic RAM (DRAM)
DRAM adalah tipe RAM yang menyimpan setiap bit
data pada kapasitor yang terpisah dalam sebuah IC
Bit data disimpan sebagai tegangan (muatan listrik) di
dalam kapasitor, sehingga mampu menyimpan data
dengan kepadatan yang sangat tinggi
Termasuk jenis memori volatile, sehingga perlu
refrehing
Konstruksi lebih sederhana, lebih murah
Tempat yang dipakai per bitnya lebih kecil
Metode penyimpanan analog
Paling umum dipakai sebagai main memori

Jenis-Jenis RAM (lanjutan)
2. Static RAM (SRAM)
Digital (menggunakan rangkaian flip-flop)
Bit-bit disimpan sebagai switch on/off (secara logika)
Didesain menggunakan transistor tanpa kapasitor,
sehingga tidak ada daya yang dapat bocor
Tidak membutuhkan refreshing selama ada daya listrik
Tidak membutuhkan sirkuit untuk refresh
Lebih cepat
Konstruksi lebih rumit
Tempat yang dipakai menyimpan per bit lebih besar
Lebih mahal
Biasanya untuk cache

II.2. Read Only Memori (ROM)
Berisi pola data permanen yang tidak dapat diubah
Bersifat non-volatile
Diprogram secara microprogramming (pemrogram
mikroprosesor)
Digunakan untuk menyimpan:
Library subroutines untuk fungsi-fungsi sistem yang
sering dipanggil
System Programs (BIOS)
Tabel Set Instruksi

Jenis-Jenis ROM
1. Programmable ROM (PROM): ROM yang isinya dapat
diprogram, tetapi tidak bisa diulang. Jika informasi yang
disimpan akan diubah, harus dibuat piranti baru.
2. Erasable PROM (EPROM): ROM yang isinya dapat
dihapus dengan ultra violet, artinya ROM tersebut dapat
diprogram beberapa kali dengan cara dihapus
3. Electrically Erasable Programmable ROM
(EEPROM): ROM yang dapat dihapus secara elektrik
dengan field emission, dihapus per byte.
4. Flash memory: ROM yang dapat dihapus secara
elektrik dengan field emission, dihapus per byte atau
semua isi memori.

III. Cache Memori
Cache memori adalah memori berukuran kecil yang
sifatnya sementara (temporary) dan berkecepatan tinggi.
Fungsi cache memori:
‒ Mempercepat akses data pada komputer karena
cache menyimpan data/informasi yang telah diakses
oleh suatu buffer
‒ Meringankan kerja prosessor
‒ Menjembatani perbedaan kecepatan antara CPU dan
memori utama.
‒ Mempercepat kinerja memori.

Terdapat dua macam letak cache:
On chip cache atau cache internal.
Cache internal diletakkan dalam prosesor sehingga tidak
memerlukan bus eksternal, dikenal dengan nama first
level (L1), akibatnya waktu aksesnya akan cepat sekali
Off chip cache atau cache eksternal.
Cache eksternal berada di luar keping chip prosesor
yang diakses melalui bus eksternal, dikenal dengan
nama second level (L2).
Cache L2 sedikit lebih lambat daripada chache L1 tetapi
memiliki kapasitas yang jauh lebih besar, berkisar antara
64 KB sampai 16 MB.

Cache memori berguna untuk mempercepat waktu akses
data pada memori. Beberapa cara untuk mengurangi waktu
akses pada suatu referensi memori:
1. RAM kecil
Dengan mengimplementasikan cache sebagai RAM
kecil akan membuatnya lebih cepat daripada memori
utama. Dengan RAM, waktu akses merupakan fungsi
dari jumlah word di dalam memori.
2. Memori Asosiatif
Dengan memori asosiatif, waktu akses merupakan
fungsi dari panjang word di dalam memori. Panjang
word pada memori utama lebih kecil daripada jumlah
word pada memori. Sehingga memori asosiatif lebih
cepat dari memori utama yang berukuran sama.

3. Memori Semikonduktor
Dua jenis memori semikonduktor yang digunakan, yaitu
bipolar dan MOS (metal-oxide semiconductor). Memori
bipolar lebih cepat dan digunakan sebagai memori
cache kecil, sedangkan MOS digunakan dalam memori
utama.
4. Kombinasi.
Memori cache terbentuk dari suatu kombinasi memori
jenis lainnya.

Pertemuan 11
MEMORI EKSTERNAL

I. Pengertian
• Kebutuhan akan memori utama saja tidak mencukupi
maka diperlukan peralatan tambahan untuk menyimpan
data yang lebih besar dan dapat dibawa kemana-mana.
• Semakin besarnya peralatan penyimpanan maka dengan
sendirinya akan mempengaruhi waktu pemrosesan data.
• Memori eksternal adalah memori yang diakses prosesor
melalui piranti I/O
• Macam-macam memori eksternal adalah Magnetik Disk,
RAID, Optical Disk, Pita Magnetik.

II. Magnetik Disk
Disk adalah piringan bundar yang terbuat dari bahan
tertentu (logam atau plastik) dengan permukaan dilapisi
bahan yang dapat dimagnetisasi.
Mekanisme baca/tulis menggunakan kepala baca atau
tulis yang disebut head
Pada operasi penulisan, arus listrik pada head
memagnetisasi disk.
Pada operasi pembacaan, medan magnet pada disk
yang bergerak di bawah head menghasilkan arus listrik
pada head.
Selama operasi pembacaan dan penulisan, head
bersifat stasioner sedangkan piringan bergerak-gerak di
bawahnya

Disk diorganisasi dalam bentuk cincin-cincin konsentris
yang disebut track.
Tiap track dipisahkan oleh gap, yang berfungsi untuk
mencegah atau mengurangi kesalahan pembacaan
maupun penulisan yang disebabkan melesetnya head
atau karena interferensi medan magnet.
Semakin ke dalam disk maka kerapatan (density) disk
akan bertambah besar.
Data disimpan di memori dalam bentuk blok, umumnya
blok lebih kecil kapasitasnya daripada track.
Blok-blok data disimpan dalam disk yang berukuran
blok, yang disebut sector. Sehingga track biasanya terisi
beberapa sector, umumnya 10 hingga 100 sector tiap
tracknya.

II.1. Karakteristik Disk
A. Berdasarkan Gerakan Head
1. Head Tetap (Fixed Head)
setiap track memiliki kepala head sendiri
2. Head Bergerak (Movable Head)
satu kepala head digunakan untuk beberapa track
dalam satu muka disk

B. Berdasarkan Portabilitas
1. Non-Removable Disk
Disk yang tetap, secara permanen ada pada disk drive.
Media ini mempengaruhi kerja sistem secara langsung,
artinya media ini tidak dapat dipasang/dilepas secara
langsung pada saat komputer bekerja.
2 . Removable Disk
Disk yang dapat dipindah sehingga lebih fleksibel
Tidak terbatas dengan kapasitas disk
Media penyimpan yang tidak mempengaruhi kerja
sistem secara langsung, artinya media ini dapat
dipasang maupun dilepas secara langsung (plug and
play) saat komputer bekerja.

C. Berdasarkan Muka Sisinya (side)
1. Satu sisi disk (single side)
Hanya satu permukaan yang dimagnetisasi.
2 . Dua muka disk (double sides)
Kedua sisi permukaannya dimagnetisasi.

D. Berdasarkan Jumlah Piringannya (Platter)
1. Satu piringan (single platter)
Magnetic disk dengan satu piringan.
2 . Banyak piringan (multiple platters)
Magnetic disk dengan lebih dari satu piringan, yang
tertumpuk secara vertikal. Untuk membaca disk ini
diperlukan head dengan banyak lengan, tergantung
banyaknya piringan disk, sehingga setiap piringan
terdapat lengan head.

E. Berdasarkan Mekanisme Head
1. Head yang menyentuh disk (contact)
Terdapat kontak secara fisik antara head dengan medium
(disk) selama operasi baca/tulis.
2. Head yang mempunyai celah tetap
Ada jarak yang tetap antara head dengan disk.
3. Head yang mempunyai celah tidak tetap
Ada kertas timah pelindung yang aerodynamis antara
head dengan disk sehingga jarak antara head dan disk
dapat diperpendek.

II.2. Mekanisme baca tulis pada disk
Disk drive beroperasi dengan kecepatan konstan.
Untuk dapat membaca dan menulis, head harus berada
pada track yang diinginkan dan pada awal sectornya.
Seek time adalah Waktu untuk mencapai track yang
diinginkan.
Rotational latency adalah waktu yang diperlukan sampai
sektor yang bersangkutan berputar sesuai dengan
headnya.
Access time adalah waktu yang diperlukan disk untuk
berada pada posisi siap membaca atau menulis.
Jadi Access time = jumlah seek time + rotational latency

III. RAID (Redundancy Array of
Independent Disk)
RAID merupakan organisasi disk memori yang mampu
menangani beberapa disk dengan sistem akses paralel
dan redundansi, untuk meningkatkan reliabilitas.
Karakteristik umum disk RAID:
RAID adalah sekumpulan disk drive yang dianggap
sebagai sistem tunggal disk.
Data didistribusikan ke drive fisik array.
Kapasitas redundant disk digunakan untuk menyimpan
informasi paritas, yang menjamin recoveribility data
ketika terjadi masalah atau kegagalan disk.

Level pada RAID
1.RAID tingkat 0
Tidak menggunakan redundansi (penumpukan) dalam
meningkatkan kinerjanya
Data didistribusikan pada seluruh disk secara array
Sistem data dianggap tersimpan pada suatu disk logik
Mekanisme transfer data dalam satu sektor sekaligus
sehingga baik untuk menangani transfer data besar

2.RAID tingkat 1
Redundansi diperoleh dengan cara menduplikasi
seluruh data pada disk mirror-nya (penyalinan data
ke lebih dari satu buah hard disk).
Menggunakan teknologi stripping yaitu pemecahan
data ke beberapa hard disk
setiap strip logik dipetakan ke dua disk yang secara
logika terpisah sehingga setiap disk pada array akan
memiliki mirror disk yang berisi data sama.

RAID tingkat 1 (lanjutan)
Keuntungan RAID-1:
Permintaan pembacaan dapat dilayani oleh salah
satu disk karena terdapat dua disk berisi data sama
tergantung waktu akses yang tercepat.
Permintaan penyimpanan atau penulisan dilakukan
pada 2 disk secara paralel.
Terdapat back-up data, yaitu dalam disk mirror-nya.
Peningkatan kinerja dua kali lipat dibandingkan
RAID-0 pada operasi baca, namun untuk operasi
tulis tidak secara signifikan terjadi peningkatan.
Cocok digunakan untuk menangani data yang sering
mengalami kegagalan dalam proses pembacaan.

3.RAID tingkat 2
Menggunakan teknik akses paralel untuk semua disk.
Dalam proses operasinya, seluruh disk berpartisipasi
dan mengeksekusi setiap permintaan sehingga
terdapat mekanisme sinkronisasi perputaran disk dan
headnya.
Teknologi stripping yang digunakan berukuran kecil
(dalam ukuran word atau byte).
Koreksi kesalahan menggunakan sistem bit paritas
dengan kode Hamming.
Cocok digunakan untuk menangani sistem yang
sering mengalami kesalahan disk.

4.RAID tingkat 3
Membutuhkan disk redundan tunggal, tidak tergantung
jumlah array disknya.
Bit paritas dikomputasikan untuk setiap data word dan
ditulis pada disk paritas khusus.
Saat terjadi kegagalan drive, data disusun kembali dari
sisa data yang masih baik dan dari informasi
paritasnya.
Menggunakan akses paralel dengan data
didistribusikan dalam bentuk strip-strip kecil.
Kinerjanya menghasilkan transfer berkecepatan tinggi,
namun hanya dapat mengeksekusi sebuah permintaan
I/O saja sehingga kalau digunakan pada lingkungan
transaksi data tinggi terjadi penurunan kinerja.

5.RAID tingkat 4
Menggunakan teknik akses yang independen
sehingga permintaan baca/tulis dilayani secara
paralel.
Cocok untuk menangani sistem dengan kelajuan
tranfer data yang tinggi.
Tidak memerlukan sinkronisasi disk karena setiap
disknya beroperasi secara independen.
Stripping data dalam ukuran yang besar.
Saat operasi penulisan, array management software
tidak hanya meng-update data tetapi juga paritas
yang terkait.
Keuntungannya dengan disk paritas yang khusus
menjadikan keamanan data lebih terjamin, namun
dengan disk paritas yang terpisah akan
memperlambat kinerjanya.

6.RAID tingkat 5
Mempunyai kemiripan dengan RAID-4 dalam
organisasinya, perbedaannya adalah strip-strip
paritas didistribusikan pada seluruh disk.
Untuk keamanan, strip paritas suatu disk disimpan
pada disk lainnya.
Perbaikan dari RAID-4 dalam hal peningkatan
kinerjanya.
Biasanya digunakan dalam server jaringan.

7.RAID tingkat 6
Menggunakan metode penghitungan dua paritas
untuk alasan keakuratan dan antisipasi terhadap
koreksi kesalahan.
Memiliki kecepatan transfer yang tinggi.

Pertemuan 12
MEMORI EKSTERNAL
Lanjutan

IV. Optical Memory
• Optical memory identik dengan CD.
• CD (Compact Disk) dikembangkan pada tahun 1980
oleh Philips dan Sony.
• CD merupakan disk yang tidak dapat dihapus, mampu
menyimpan memori kurang lebih 60 menit informasi
audio pada salah satu sisinya.
• Secara komersial, CD mampu menyimpan data dalam
jumlah yang besar, menjadikannya media penyimpan
yang fleksibel digunakan di berbagai peralatan seperti
komputer, kamera video, MP3 player, dan lain-lain.

Macam-Macam Optical Disk
1.CD ROM (Compact Disk–Read Only Memory)
Dikenalkan pertama kali oleh Phillips dan Sony tahun
1984 yang dikenal dengan Yellow Book.
Digunakan untuk menyimpan data, dan dapat lebih dari
650 MB.
Penulisan data dengan cara membuat lubang mikroskopik
sebagai representasi data dengan laser berintensitas
tinggi.
Pembacaan data menggunakan laser berintensitas
rendah untuk menterjemahkan lubang mikroskopik ke
dalam bentuk data yang dapat dikenali komputer.
Data pada CD-ROM diorganisasikan sebagai urutan blok.

Keterangan urutan blok sebagai berikut
Dari gambar di atas urutan blok terdiri dari bidang-bidang:
Sync: Field sync mengidentifikasikan awal blok, yang terdiri dari byte 0,
byte 1, dan byte 0.
Header: berisi alamat blok dan mode byte.
Mode 0 untuk field data kosong
Mode 1 untuk penggunaan error-correcting code dan 2048 byte data
Mode 2 untuk 2336 byte data pengguna tanpa error-correcting code.
Data: untuk data pengguna.
Auxiliary: untuk data pengguna tambahan dalam mode 2

Keuntungan CD-ROM:
Kapasitas penyimpanan informasinya jauh lebih besar
dibandingkan dengan disk magnetik.
Dapat diperbanyak dengan harga murah
Dapat dipindah-pindah.
Kekurangan CD-ROM:
CD-ROM hanya dapat dibaca saja (read only) dan tidak
dapat di update.
CD-ROM memiliki waktu akses yang lebih lama
dibandingkan dengan waktu akses disk drive magnetik.

2.CD - R (Compact Disk Recordables)
Dikenalkan pertama kali oleh Kodak dan Fuji tahun 1989
yang dikenal dengan Orange Book.
Mirip dengan CD-ROM tetapi penulisan data hanya
sekali saja.
Penulisan CD-R secara inkremental sehingga
menambah fleksibilitas.
Untuk penggunaan khusus, biasanya digunakan untuk
master CD atau photo CD

3.CD - RW (Compact Disk Rewritables)
Jenis CD ini memungkinkan penulisan berulang kali
sehingga jenis ini memiliki nilai kompetitif dibandingkan
jenis lain.
CD-RW tidak menggunakan lapisan pewarna, namun
menggunakan logam paduan antara perak, indium,
antimon dan tellurium.
4.DVD (Digital Versatile Disk)
DVD adalah merupakan pengembangan dari CD dan
memiliki kapasitas yang lebih besar daripada jenis CD.
Transfer data pada DVD drive sekitar 1.4 MB/det,
sedangkan CD biasa hanya 150 KB/det.

5.DVD-R (DVD Recordable)
Dapat menulis ke disk hanya sekali dan hanya satu sisi
disk yang dapat digunakan.
6.DVD-RW (DVD Rewritable)
Dapat menghapus dan menulis ulang ke disk beberapa
kali. Hanya satu sisi disk yang dapat digunakan.

V. Magnetic Tape
Pita magnetik (Magnetic Tape) merupakan jenis memori
pembantu (Auxiliary memory) yang digunakan untuk tempat
penyimpanan offline yang besar.
Medium pita magnetik terbagi menjadi 9, 18, 36 track
Penyimpanan suatu karakter sekali simpan untuk setiap posisi
sepanjang pita, dan satu bit paritas pada track sisanya.
Kerapatan penyimpanan dinyatakan dengan byte per inch
Teknik pembacaan dan penulisan secara berurutan.
Dibaca dan ditulisi dalam bentuk blok-blok yang bersambungan
(kontinyu) yang disebut physical record.
Blok-blok tersebut dipisahkan oleh gap yang disebut interrecord
gap.
Kecepatan putaran pita magnetik adalah rendah sehingga
transfer data menjadi lambat.

Pertemuan 13
SISTEM BUS

I. Pengertian
Sistem bus adalah penghubung bagi keseluruhan
komponen komputer dalam menjalankan tugasnya.
1.Struktur Interkoneksi
• Komputer tersusun atas komponen-komponen atau
modul-modul (CPU, memori dan I/O) yang saling
berkomunikasi.
• Kumpulan lintasan atau saluran berbagai modul disebut
struktur interkoneksi.
• Rancangan struktur interkoneksi sangat bergantung
pada jenis dan karakteristik pertukaran datanya.

Modul-modul penyusun komputer berdasarkan pertukaran
datanya terdiri atas:
a. Memori
Memori terdiri atas N word memori dengan panjang
yang sama.
Setiap word diberi alamat numerik yang unik.
Word dapat dibaca/ditulis dengan kontrol read/write.
Lokasi bagi operasi dispesifikasikan oleh sebuah
alamat.
b. Modul I/O
Operasi modul I/O adalah pertukaran data dari dan ke
dalam komputer.
Modul I/O dapat mengontrol lebih dari sebuah
perangkat peripheral dan mengirimkan sinyal interupsi.

c. CPU
CPU berfungsi sebagai pusat pengolahan dan eksekusi
data berdasarkan routine program yang diberikan
padanya.
CPU mengendalikan seluruh sistem komputer sehingga
memiliki koneksi ke seluruh modul yang menjadi bagian
sistem komputer.

Struktur interkoneksi berdasarkan jenis pertukaran data yang
diperlukan modul-modul komputer, harus mendukung
perpindahan data berikut:
Memori ke CPU: CPU melakukan pembacaan data
maupun instruksi dari memori.
CPU ke Memori: CPU melakukan penyimpanan atau
penulisan data ke memori.
I/O ke CPU: CPU membaca data dari peripheral melalui
modul I/O.
CPU ke I/O: CPU mengirimkan data ke perangkat
peripheral melalui modul I/O.
I/O ke Memori atau dari Memori: digunakan pada sistem
DMA.

2. Interkoneksi Bus
• Bus merupakan lintasan komunikasi yang
menghubungkan dua atau lebih komponen komputer.
• Sifat penting dan merupakan syarat utama adalah bus
adalah media transmisi yang dapat digunakan bersama
oleh sejumlah perangkat yang terhubung padanya.
• Karena digunakan bersama, diperlukan aturan main
agar tidak terjadi tabrakan data atau kerusakan data
yang ditransmisikan.
• Walaupun digunakan bersama namun dalam satu waktu
hanya ada sebuah perangkat yang dapat menggunakan
bus.

II. Struktur Bus
Fungsi saluran bus dikategorikan dalam 3 bagian:
a. Bus data (data bus) adalah lintasan bagi perpindahan
data antar modul. Umumnya jumlah saluran terkait
dengan panjang word, misalnya 8, 16, 32 saluran
dengan tujuan agar mentransfer word dalam sekali
waktu. Jumlah saluran dalam bus data dikatakan lebar
bus, dengan satuan bit, misal lebar bus 16 bit.
b. Bus alamat (address bus) digunakan untuk
menspesifikasi sumber dan tujuan data pada bus data.
Saluran ini digunakan untuk mengirim alamat word pada
memori yang akan diakses CPU. Juga digunakan untuk
saluran alamat perangkat modul komputer saat CPU
mengakses suatu modul

c. Bus kontrol (control bus) digunakan untuk mengontrol
bus data, bus alamat dan seluruh modul yang ada.
Sinyal-sinyal kontrol terdiri atas sinyal pewaktuan dan
sinyal-sinyal perintah. Sinyal pewaktuan menandakan
validitas data dan alamat, sedangkan sinyal perintah
berfungsi membentuk suatu operasi.
Secara umum Bus kontrol meliputi:
Memory Write, memerintahkan data pada bus akan
dituliskan ke dalam lokasi alamat.
Momory Read memerintahkan data dari lokasi alamat
ditempatkan pada bus data.
I/O Write, memerintahkan data pada bus dikirim ke
lokasi port I/O.
I/O Read, memerintahkan data dari port I/O
ditempatkan pada bus data.

Secara umum Bus kontrol meliputi (lanjutan):
Transfer ACK, menunjukkan data telah diterima dari
bus atau data telah ditempatkan pada bus.
Bus Request, menunjukkan bahwa modul
memerlukan kontrol bus.
Bus Grant, menunjukkan modul yang melakukan
request telah diberi hak mengontrol bus.
Interrupt Request, menandakan adanya penangguhan
interupsi dari modul.
Interrupt ACK, menunjukkan penangguhan interupsi
telah diketahui CPU.
Clock, kontrol untuk sinkronisasi operasi antar modul.
Reset, digunakan untuk menginisialisasi seluruh
modul.

Prinsip operasi bus adalah sebagai berikut:
Operasi pengiriman data ke modul lainnya
a. Meminta penggunaan bus.
b. Apabila telah disetujui, modul akan memindahkan
data yang diinginkan ke modul yang dituju.
Operasi meminta data dari modul lainnya
a. Meminta penggunaan bus.
b. Mengirim request ke modul yang dituju melalui
saluran kontrol dan alamat yang sesuai.
c. Menunggu modul yang dituju mengirimkan data yang
diinginkan.

Bila terlalu banyak modul atau perangkat dihubungkan
pada bus maka akan terjadi penurunan kinerja, yang
disebabkan oleh:
Semakin besar delay propagasi untuk
mengkoordinasikan penggunaan bus.
Antrian penggunaan bus semakin panjang.
Dimungkinkan habisnya kapasitas transfer bus sehingga
memperlambat data.
Antisipasi dan solusi persoalan di atas adalah penggunaan
bus jamak yang hierarkis.
Modul-modul diklasifikasikan berdasarkan kebutuhan
terhadap lebar dan kecepatan bus.

Pada arsitektur berkinerja tinggi, modul-modul I/O
diklasifikasikan menjadi dua:
yang memerlukan transfer data berkecepatan tinggi
yang disambungkan dengan bus berkecepatan tinggi
pula, dan lebih terintegrasi dengan prosesor
yang memerlukan transfer data berkecepatan rendah
yang disambungkan pada bus ekspansi

III. Elemen Perancangan Bus
Tujuannya adalah bagaimana bus dapat cepat
menghantarkan data dan efisiensinya tinggi.
1.Jenis Bus
Dedicated bus adalah bus yang khusus menyalurkan
data tertentu, seperti paket data saja, atau alamat saja.
Multiplexed bus adalah bus yang menyalurkan informasi
yang berbeda baik data, alamat maupun sinyal kontrol.
Keuntungannya: hanya memerlukan saluran sedikit
sehingga dapat menghemat tempat
Kerugiannya: kecepatan transfer data menurun dan
diperlukan mekanisme yang komplek untuk mengurai
data yang telah dimulitipleks.

2.Metode Arbitras
Metode Tersentral, diperlukan pengontrol bus sentral
atau arbiter yang bertugas mengatur penggunaan bus
oleh modul.
Metode Terdistribusi, setiap modul memiliki logika
pengontrol akses (access control logic) yang berfungsi
mengatur pertukaran data melalui bus.

3.Timing
Metode pewaktuan sinkron terjadinya event pada bus
ditentukan oleh sebuah clock.
Semua perangkat modul pada bus dapat membaca
atau pengetahui siklus clock.
Biasanya satu siklus untuk satu event.
Model ini mudah diimplementasikan dan cepat namun
kurang fleksibel menangani peralatan yang beda
kecepatan operasinya.
Biasanya digunakan untuk modul-modul tertentu yang
sudah jelas karakteristiknya.

Timing (lanjutan)
Metode pewaktuan asinkron memungkinkan kerja modul
yang tidak serempak kecepatannya.
Dalam pewaktuan asinkron, event yang terjadi pada
bus tergantung event sebelumnya sehingga
diperlukan sinyal-sinyal validasi untuk
mengidentifikasi data yang ditransfer.
Sistem ini mampu menggabungkan kerja modulmodul
yang berbeda kecepatan maupun teknologinya,
asalkan aturan transfernya sama

4. Lebar Bus
Semakin lebar bus maka semakin besar data yang dapat
ditransfer sekali waktu.
Semakin besar bus alamat, akan semakin banyak range
lokasi yang dapat direfensikan.

5. Jenis Transfer Data
Dalam sistem komputer, operasi transfer data adalah
pertukaran data antar modul sebagai tindak lanjut atau
pendukung operasi yang sedang dilakukan.
Saat operasi baca, terjadi pengambilan data dari memori
ke CPU.
Saat operasi penulisan terjadi pengambilan data dari
CPU ke memori.
Bus harus mampu menyediakan layanan saluran bagi
semua operasi komputer.

Pertemuan 14
UNIT MASUKAN
DAN KELUARAN (I/O)

I. Pendahuluan
Piranti-piranti tidak langsung dihubungkan dengan bus
sistem komputer, dengan alasan:
1. Bervariasinya metode operasi piranti peripheral,
sehingga tidak praktis apabila sistem komputer harus
menangani berbagai macam sisem operasi piranti
peripheral tersebut.
2. Kecepatan transfer data piranti peripheral lebih lambat
dari pada laju transfer data pada CPU maupun memori.
3. Format data dan panjang data pada piranti peripheral
seringkali berbeda dengan CPU, sehingga perlu modul
untuk menselaraskannya.

II. Sistem I/O Komputer
Modul I/O merupakan peralatan antarmuka (interface) bagi
sistem bus atau switch sentral dan mengontrol satu atau
lebih perangkat peripheral.
Modul I/O juga sebuah piranti yang berisi logika dalam
melakukan fungsi komunikasi antara peripheral dan bus
komputer.
Fungsi utama modul I/O:
1. Sebagai piranti antarmuka ke CPU dan memori melalui
bus sistem.
2. Sebagai piranti antarmuka dengan peralatan peripheral
lainnya dengan menggunakan link data tertentu.

III. Fungsi Modul I/O
Modul I/O adalah suatu komponen dalam sistem
komputer yang bertanggung jawab atas pengontrolan
perangkat luar
Modul I/O juga bertanggung jawab dalam pertukaran data
antara perangkat luar tersebut dengan memori utama
ataupun dengan register-register CPU.
Fungsi dalam menjalankan tugas bagi modul I/O adalah:
a. Kontrol dan pewaktuan.
b. Komunikasi CPU.
c. Komunikasi perangkat eksternal.
d. Pem-buffer-an data (Buffering)
e. Deteksi kesalahan.

III.1. Kontrol dan Pewaktuan (control & timing)
• CPU berkomunikasi dengan satu atau lebih perangkat
dengan pola tidak menentu dan kecepatan transfer
komunikasi data yang beragam, dengan perangkat
internal seperti register-register, memori utama, memori
sekunder, perangkat peripheral.
• Proses tersebut bisa berjalan apabila ada fungsi kontrol
dan pewaktuan yang mengatur sistem secara
keseluruhan.
• Contoh kontrol pemindahan data dari peripheral ke CPU.

Langkah-langkah kontrol pemindahan data dari peripheral
ke CPU melalui sebuah modul I/O sebagai berikut:
1. Permintaan dan pemeriksaan status perangkat dari
CPU ke modul I/O.
2. Modul I/O memberi jawaban atas permintaan CPU.
3 . Jika perangkat eksternal telah siap untuk transfer data,
maka CPU akan mengirimkan perintah ke modul I/O.
4. Modul I/O akan menerima paket data dengan panjang
tertentu dari peripheral.
5. Modul I/O melakukan sinkronisasi panjang data dan
kecepatan transfer sehingga paket-paket data dapat
diterima CPU dengan baik.
6. Data dikirim ke CPU

III.2. Komunikasi CPU
Komunikasi CPU meliputi proses-proses berikut:
Command Decoding, yaitu modul I/O menerima
perintah dari CPU yang dikirimkan sebagai sinyal bagi
bus kontrol.
Misalnya, modul I/O untuk disk dapat menerima
perintah: Read sector, Scan record ID, Format disk.
Data, pertukaran data antara CPU dan modul I/O melalui
bus data.
Status Reporting, yaitu pelaporan kondisi status modul
I/O maupun perangkat peripheral, umumnya berupa
status kondisi Busy atau Ready dan error.
Address Recognition, agar komputer dapat dihubungi
atau dipanggil maka harus memiliki alamat yang unik.

III.2. Komunikasi CPU
Komunikasi CPU meliputi proses-proses berikut:
Command Decoding, yaitu modul I/O menerima
perintah dari CPU yang dikirimkan sebagai sinyal bagi
bus kontrol.
Misalnya, modul I/O untuk disk dapat menerima
perintah: Read sector, Scan record ID, Format disk.
Data, pertukaran data antara CPU dan modul I/O melalui
bus data.
Status Reporting, yaitu pelaporan kondisi status modul
I/O maupun perangkat peripheral, umumnya berupa
status kondisi Busy atau Ready dan error.
Address Recognition, agar komputer dapat dihubungi
atau dipanggil maka harus memiliki alamat yang unik.

III.5. Deteksi Kesalahan
• Apabila pada perangkat peripheral terdapat masalah
sehingga proses tidak dapat dijalankan, maka modul I/O
akan melaporkan kesalahan tersebut.
• Misal: kertas tergulung, pita/kertas habis.
• Teknik untuk deteksi kesalahan adalah penggunaan bit
paritas.

Fungsi antarmuka modul I/O:
Menginterpretasikan alamat dan isyarat memori I/O
Menentukan operasi I/O dan menerima keluaran data
dari bus
Memasukkan dan mengeluarkan data dari piranti I/O dan
mengubah format data paralel ke format yang diterima
Mengirim isyarat “ready” jika data diterima atau
diletakkan pada bus
Mengirim permintaan interupsi
Menerima isyarat reset dan melakukan inisialisasi ulang

V. Teknik I/O
V.1. I/O Terprogram
Pada I/O terprogram, data saling dipertukarkan antara
CPU dan modul I/O.
CPU mengeksekusi program yang memberikan operasi
I/O kepada CPU secara langsung, seperti pemindahan
data, pengiriman perintah baca/tulis, dan monitoring
perangkat.
Kelemahan teknik ini adalah CPU akan menunggu
sampai operasi I/O selesai dilakukan modul I/O sehingga
akan membuang waktu.
Dalam teknik ini, modul I/O tidak dapat melakukan
interupsi kepada CPU.
Seluruh proses merupakan tanggung jawab CPU sampai
operasi lengkap dilaksanakan.

Klasifikasi perintah I/O, yaitu:
1. Perintah control.
Perintah yang digunakan untuk mengaktivasi perangkat
peripheral dan memberitahukan tugas yang diperintahkan
padanya.
2. Perintah test.
Perintah yang digunakan CPU untuk menguji berbagai kondisi
status modul I/O dan peripheralnya.
3. Perintah read.
Perintah pada modul I/O untuk mengambil suatu paket data
kemudian menaruh dalam buffer internal untuk selanjutnya
paket data dikirim melalui bus data.
4. Perintah write.
Perintah pada modul I/O untuk mengambil data dari bus data
untuk diberikan pada perangkat peripheral tujuan data tsb.

V.2. Interupsi
Interupsi atau interrupt adalah suatu permintaan khusus
pada mikroprocessor untuk melakukan sesuatu, jika terjadi
interupsi maka komputer akan menghentikan dahulu apa
yang sedang dikerjakan dan melakukan apa yang diminta
oleh yang menginterupsi, setelah selesai maka aliran
program akan kembali ke pernyataan program sebelum
terjadinya interupsi.
Interupsi merupakan sub rutin yang sudah tersedia dalam
memori komputer.




































































Read more ...

Senin, 29 Juni 2015

Struktur Data 9-14

Pertemua 9

STRUKTUR POHON &
KUNJUNGAN POHON BINER

Pohon (Tree) termasuk struktur non linear yang
didefinisikan sebagai data yang terorganisir dari suatu
item informasi cabang yang saling terkait
Istilah – istilah Dalam Pohon
1. Predesesor
Node yang berada diatas node tertentu.
(contoh : B predesesor dari E dan F)
2. Succesor
Node yang berada dibawah node tertentu.
Istilah – istilah Dalam Pohon
(contoh : E dan F merupakan succesor dari B)
3. Ancestor
Seluruh node yang terletak sebelum node tertentu dan
terletak pada jalur yang sama.
(contoh : A dan B merupakan ancestor dari F)
4. Descendant
Seluruh node yang terletak sesudah node tertentu
dan terletak pada jalur yang sama.
(contoh : F dan B merupakan ancestor dari A)
5. Parent
Predesesor satu level diatas satu node
(contoh : B merupakan parent dari F)
6. Child
Succesor satu level dibawah satu node
(contoh : F merupakan child dari B)
7. Sibling
Node yang memiliki parent yang sama dengan satu
node (contoh : E dan F adalah sibling)
8. Subtree
Bagian dari tree yang berupa suatu node beserta
descendant-nya (contoh : Subtree B, E, F dan
Subtree D, G, H)
9. Size
Banyaknya node dalam suatu tree (contoh : gambar
tree diatas memiliki size = 8)
10. Height
Banyaknya tingkat/level dalam suatu tree (contoh :
gambar tree diatas memiliki height = 2) karena
program C++ diawali dari index ke-0
11. Root (Akar)
Node khusus dalam tree yang tidak memiliki
predesesor (Contoh : A)
12. Leaf (Daun)
Node-node dalam tree yang tidak memiliki daun
(contoh : Node E,F,C,G,H)
13. Degree (Derajat)
Banyaknya child yang dimiliki oleh suatu node
(contoh : Node A memiliki derajat 3, node B memiliki
derajat 2)
POHON BINAR (BINARY TREE)
Struktur ini biasanya digunakan untuk menyajikan data
yang mengandung hubungan hirarkial antara elemenelemennya.

Bentuk Pohon Berakar yang lebih mudah dikelola dalam
komputer adalah Pohon Biner (Binary Tree) yang lebih
dikenal sebagai Pohon Umum (General Tree) yang dapat
didefinisikan sebagai kumpulan simpul yang mungkin
kosong atau mempunyai akar dan dua Subpohon yang
saling terpisah yang disebut dengan Subpohon Kiri /
cabang kiri (Left Subtree) dan Subpohon Kanan / cabang
kanan (Right Subtree).
Karakteristik Pohon Binar (Binary Tree) :
1. Setiap Simpul paling banyak hanya memiliki dua buah
anak
2. Derajat Tertinggi dari setiap Simpul adalah dua.
3. Dibedakan antara Cabang Kiri dan Cabang Kanan.
4. Dimungkinkan tidak mempunyai Simpul
Berikut ini diberikan contoh gambar Pohon Binar (Binary
Tree) dengan Cabang Kiri dan Cabang Kanan.
ISTILAH PADA POHON BINER
• Pohon Biner Penuh
(Full Binary Tree)
Semua simpul (kecuali daun)
memiliki 2 anak dan tiap cabang
memiliki panjang ruas yang sama
• Pohon Biner Lengkap
(Complete Binary Tree)
Hampir sama dengan Pohon Biner
Penuh, semua simpul (kecuali
daun) memiliki 2 anak tetapi tiap
cabang memiliki panjang ruas
berbeda
• Pohon Biner Similer
Dua pohon yang memiliki struktur yang sama tetapi
informasinya berbeda
• Pohon Biner Ekivalent
Dua pohon yang memiliki struktur dan informasi yang
sama

• Pohon Biner Miring (Skewed Tree)
Dua pohon yang semua simpulnya mempunyai satu
anak / turunan kecuali daun

Penyajian Pohon Binar
(Binary Tree)

• Tree dapat dibuat dengan menggunakan linked list
secara rekursif.
• Linked list yang digunakan adalah double linked list non
circular
• Data yang pertama kali masuk akan menjadi node root.
• Data yang lebih kecil dari data node root akan masuk
dan menempati node kiri dari node root, sedangkan jika
lebih besar dari data node root, akan masuk dan
menempati node di sebelah kanan node root.

Bila diberikan untai HAKJCBL, maka proses untuk dapat
membentuk pohon biner dari untai diatas adalah :
1. Karakter pertama ‘H’ ditempatkan sebagai akar (root)
2. Karakter ‘A’,karena lebih kecil dari ‘H’, maka akan
menempati cabang kiri.
3. Karakter ‘K’, karena lebih besar dari ‘H’, maka akan
menempati cabang kanan.
4. Karakter ‘J’, lebih besar dari ‘H’ dan kecil dari ‘K’, maka
menempati cabang kiri ‘K’.

Pertemuan 10
KUNJUNGAN
PADA POHON BINER

1. Kunjungan Secara PreOrder (Dept First Order)
a. cetak isi simpul yang di kunjungi (Simpul Akar)
b. kunjungi cabang kiri
c. kunjungi cabang kanan
2. Kunjungan Secara Inorder (Symetric Order)
a. kunjungi cabang kiri
b. cetak isi simpul yang di kunjungi (Simpul Akar)
c.  kunjungi cabang kanan
3. Kunjungan Secara PostOrder
a. kunjungi cabang kiri
b.  kunjungi cabang kanan
c. cetak isi simpul yang di kunjungi (Simpul Akar)
Pada ketiga cara kunjungan diatas, kunjungan ke
Cabang Kiri dilakukan terlebih dahulu, baru kemudian
kunjungan ke Cabang Kanan. Dengan orientasi
semacam ini, Ketiga kunjungan diatas disebut dengan
Left To Right Oriented (LRO).
Jika kunjungan ke Cabang Kanan dilakukan lebih
dahulu baru kemudian kunjungan ke Cabang Kiri, maka
Orientasi semacam ini disebut Right To Left Oriented
(RLO).

Kunjungan LevelOrder
Selain kunjungan yang dijelaskan diatas, masih ada
satu macam kunjungan masih ada satu macam
kunjungan lagi yaitu kunjungan LevelOrder.
Kunjungan dimulai dari simpul yang ada pada tingkat
1 (Akar), diteruskan pada simpul di tingkat 2, tingkat 3
dan seterusnya.

Secara singkat kunjungan Level Order ini dapat dijelaskan
sebagai berikut.
1. Dimulai dengan memasukkan Akar kedalam antrean.
2. Kemudian mengeluarkan Akar tersebut keluar dari
antrean.
Pada saat Akar tersebut dikeluarkan dari antrean, cabang
kiri dan cabang kanan secara berturut-turut dimasukkan
dalam antrean.
Dengan kata lain jika suatu elemen dikeluarkan dari
antrean, maka cabang kiri dan kanan dari elemen yang
baru saja dikeluarkan dimasukkan kedalam antrean.

APLIKASI POHON BINER
NOTASI PREFIX, INFIX DAN POSTFIX
Pada bagian ini akan dibahas tentang bagaimana
menyusun sebuah Pohon Binar yang apabila dikunjungi
secara PreOrder akan menghasilkan Notasi Prefix,
kunjungan secara InOrder menghasilkan Notasi Infix, dan
kunjungan PostOrder menghasilkan Notasi Postfix.

Pertemuan 11
GRAPH dan
MATRIK PENYAJIAN GRAPH

Suatu Graph mengandung 2 himpunan, yaitu :
1. Himpunan V yang elemennya disebut simpul (Vertex
atau Point atau Node atau Titik)
2. Himpunan E yang merupakan pasangan tak urut dari
simpul. Anggotanya disebut Ruas (Edge atau rusuk
atau sisi)
Graph seperti dimaksud diatas, ditulis sebagai G(E,V).

Suatu Graph yang tidak mengandung ruas sejajar maupun
self-loop, sering disebut juga sebagai Graph sederhana
atau simple Graph.
Suatu Graph G’(E’,V’) disebut Sub Graph dari G(E,V), bila E’
himpunan bagian dari E dan V’ himpunan bagian dari V.
Jika E’ mengandung semua ruas dari E yang titik ujungnya
di V’, maka G’ disebut Subgraph yang direntang oleh V’
(Spanning Subgraph).
GRAPH BERLABEL

Graph G disebut berlabel jika ruas dan atau simpulnya
dikaitkan dengan suatu besaran tertentu. Khususnya jika
setiap Ruas e dari G dikaitkan dengan suatu bilangan
non negatif d(e), maka d(e) disebut bobot atau panjang
dari ruas e.

DERAJAT GRAPH
Derajat simpul V, ditulis d(v) adalah banyaknya ruas
yang menghubungi v. Karena setiap ruas dihitung dua
kali ketika menentukan derajat suatu Graph, maka :
Jumlah derajat semua simpul suatu Graph (derajat) =
dua kali banyaknya ruas Graph (Size) Atau dapat
dituliskan :
Derajat Graph = 2 x Size

Jika Derajat masing-masing simpul pada Graph berjumlah
Genap maka Graph tersebut disebut EULER Graph
KETERHUBUNGAN

Walk atau perjalanan dalam Graph G adalah barisan simpul
dan ruas berganti-ganti : V1,e1,V2,e2,......., e n-1, Vn
Disini ruas ei menghubungkan simpul Vi dan Vi+1.
Banyaknya ruas disebut Panjang Walk. Walk dapat ditulis
lebih singkat dengan hanya menulis deretan ruas :
e1,e2, ...., en-1 atau deretan simpul : V1, V2,....., Vn-1, Vn
dimana : V1 = simpul awal
Vn = simpul akhir.
Walk disebut tertutup bila V1 = Vn
1. Walk disebut tertutup, yang menghubungkan V1 dan
Vn yaitu setiap ruas menghubungkan simpul awal dan akhir
2. Trail adalah walk dengan semua ruas dalam barisan adalah berbeda
3. Path atau jalur adalah walk yang semua simpul dalam barisan adalah berbeda.

Graph merupakan Walk Terbuka, karena tidak ada ruas
yang menghubungkan Simpul U dan T.
Merupakan suatu Path atau Trail terbuka dengan
derajat setiap simpulnya = 2, kecuali simpul awal U dan
simpul akhir T berderajat = 1.

· Barisan ruas a,b,c,d,b,c,g,h adalah Walk bukan Trail
(karena ruas b dua kali muncul).
· Barisan simpul A, B, E, F bukan Walk (karena tdk
ada ruas yang menghubungkan simpul B ke F).
· Barisan simpul A, B, C, D, E, C, F adalah Trail
bukan Jalur/Path (karena c dua kali muncul)
· Barisan ruas a, d, g, k adalah Jalur/Path karena
menghubungkan A dengan F
· Ruas a, b, h, g, e, a, adalah Cycle.
Graph yang tidak mengandung Cycle disebut Acyclic.
Contoh dari Graph Acyclic adalah pohon atau Tree.

GRAPH TERARAH (DIRECTED GRAPH / DIGRAPH)
Graph terarah adalah Graph yang dapat menghubungkan
V1 ke V2 saja (1 arah).
Maksimum jumlah busur dari n simpul adalah : n ( n - 1)
Suatu Graph Berarah (Directed Graph) D terdiri atas 2
himpunan :
1) Himpunan V, anggotanya disebut simpul.
2) Himpunan A, merupakan himpunan pasangan terurut,
yang disebut ruas berarah atau arkus.

Bila arkus suatu Graph Berarah menyatakan suatu bobot,
maka Graph Berarah tersebut dinamakan jaringan /
Network. Biasanya digunakan untuk menggambarkan
situasi dinamis.
Bila V’ himpunan bagian dari V serta A’ himpunan bagian
dari A, dengan titik ujung anggota A’ terletak di dalam V’,
maka dikatakan bahwa D’(V’,A’) adalah Graph bagian
(Subgraph) dari D(V,A).
Bila A’ mengandung semua arkus anggota A yang titik
ujungnya anggota V’, maka dikatakan bahwa D’(V’,A’)
adalah Graph Bagian yang dibentuk atau direntang oleh V’.
MINIMUM SPANNING TREE

Merupakan Spanning Tree yang mempunyai Bobot dan
tidak mempunyai arah dengan hasil penjumlahan
bobotnya adalah minimum.

Langkah yang dilakukan untuk membentuk minimum
spanning tree adalah :
Bentuk kembali semua simpul tetapi tanpa ruas.
Gambar dan telusuri ruas dengan bobot paling kecil,
seterusnya (secara ascending) hingga semua simpul
terhubung

2. Breadth First Search (BFS).
Berbeda dengan cara BFS, dengan BFS penelusuran
akan diawasi dari Node-1, kemudian melebar pada
Adjacent Node dari Node-1 dan diteruskan pada
Node-2, Node- 3 dan seterusnya.


















Read more ...
Designed By