ALGORITMA Dijkstra

Algoritma Dijkstra, dinamai menurut penemunya, Edsger Dijkstra, adalah sebuah algoritma rakus (greedy algorithm) dalam memecahkan permasalahan jarak terpendek (shortest path problem) untuk sebuah graf berarah (directed graph) dengan bobot-bobot sisi (edge weights) yang bernilai tak-negatif.

Misalnya, bila vertices dari sebuah graf melambangkan kota-kota dan bobot sisi (edge weights) melambangkan jarak antara kota-kota tersebut, maka algoritma Dijkstra dapat digunakan untuk menemukan jarak terpendek antara dua kota.

Input algoritma ini adalah sebuah graf berarah yang berbobot (weighted directed graph) G dan sebuah sumber vertex s dalam G dan V adalah himpunan semua vertices dalam graph G.

Setiap sisi dari graf ini adalah pasangan vertices (u,v) yang melambangkan hubungan dari vertex u ke vertex v. Himpunan semua tepi disebut E.

Bobot (weights) dari semua sisi dihitung dengan fungsi

w: E → [0, ∞)

jadi w(u,v) adalah jarak tak-negatif dari vertex u ke vertex v.

Ongkos (cost) dari sebuah sisi dapat dianggap sebagai jarak antara dua vertex, yaitu jumlah jarak semua sisi dalam jalur tersebut. Untuk sepasang vertex s dan t dalam V, algoritma ini menghitung jarak terpendek dari s ke t.

//<![CDATA[
if (window.showTocToggle) { var tocShowText = "tampilkan"; var tocHideText = "sembunyikan"; showTocToggle(); }
//]]>

Pseudocode

 1  function Dijkstra(G, w, s)
 2     for each vertex v in V[G]                        // Initializations
 3           d[v] := infinity
 4           previous[v] := undefined
 5     d[s] := 0                                        // Distance from s to s
 6     S := empty set
 7     Q := V[G]                                        // Set of all vertices
 8     while Q is not an empty set                      // The algorithm itself
 9           u := Extract_Min(Q)
10           S := S union {u}
11           for each edge (u,v) outgoing from u
12                  if d[u] + w(u,v) < d[v]             // Relax (u,v)
13                        d[v] := d[u] + w(u,v) 
14                        previous[v] := u

ALGORITMA PRIM

Algoritma Prim adalah sebuah algoritma dalam graph theory untuk mencari pohon rentang minimum untuk sebuah graf terhubung berbobot, dengan kata lain sebuah himpunan bagian dari cabang-cabang yang membentuk suatu pohon yang terdiri dari semua node, di mana bobot keseluruhan semua cabang dalam pohon adalah paling kecil. Bila graf tersebut tidak terhubung, maka graf itu hanya memiliki satu pohon rentang minimum untuk satu dari komponen yang terhubung. Algoritma ini ditemukan pada 1930 oleh matematikawan Vojtěch Jarník dan kemudian secara terpisah oleh computer scientist Robert C. Prim pada 1957 dan ditemukan kembali oleh Dijkstra pada 1959. Karena itu algoritma ini sering dinamai algoritma DJP atau algoritma Jarnik.

Langkah-langkahnya adalah sebagai berikut:

• buat sebuah pohon yang terdiri dari satu node, dipilih secara acak dari graf
• buat sebuah himpunan yang berisi semua cabang di graf
• loop sampai semua cabang di dalam himpunan menghubungkan dua node di pohon
  • hapus dari himpunan satu cabang dengan bobot terkecil yang menghubungkan satu node di pohon dengan satu node di luar pohon
  • hubungkan cabang tersebut ke pohon

Dengan struktur data binary heap sederhana, algoritma Prim dapat ditunjukkan berjalan dalam waktu O(Elog V), di mana E adalah jumlah cabang dan V adalah jumlah node. Dengan Fibonacci heap, hal ini dapat ditekan menjadi O(E + Vlog V), yang jauh lebih cepat bila grafnya cukup padat sehingga E adalah Ω(Vlog V).

Contoh

	Ini adalah graf berbobot awal. Graf ini bukan pohon karena ada circuit. Nama yang lebih tepat untuk diagram ini adalah graf atau jaringan. Angka-angka dekat garis penghubung adalah bobotnya. Belum ada garis yang ditandai, dan node D dipilih secara sembarang sebagai titik awal.
	Node kedua yang dipilih adalah yang terdekat ke D: A jauhnya 5, B 9, E 15, dan F 6. Dari keempatnya, 5 adalah yang terkecil, jadi kita tandai node A dan cabang DA.
	Node berikutnya yang dipilih adalah yang terdekat dari D atau A. B jauhnya 9 dari D dan 7 dari A, E jauhnya 15, dan F 6. 6 adalah yang terkecil, jadi kita tandai node F dan cabang DF.
	Algoritma ini berlanjut seperti di atas. Node B, yang jauhnya 7 dari A, ditandai. Di sini, cabang DB ditandai merah, karena baik node B dan node D telah ditandai hijau, sehingga DB tidak dapat digunakan.
	Dalam hal ini, kita dapat memilih antara C, E, dan G. C jauhnya 8 dari B, E 7 dari B, dan G 11 dari F. E yang terdekat, jadi kita tandai node E dan cabang EB. Dua cabang lain ditandai merah, karena kedua node yang terhubung telah digunakan.
	Di sini, node yang tersedia adalah C dan G. C jauhnya 5 dari E, dan G 9 dari E. C dipilih, jadi ditandai bersama dengan cabang EC. Cabang BC juga ditandai merah.
	Node G adalah satu-satunya yang tersisa. Jauhnya 11 dari F, dan 9 dari E. E lebih dekat, jadi kita tandai cabang EG. Sekarang semua node telah terhubung, dan pohon rentang minimum ditunjukkan dengan warna hijau, bobotnya 39.

Bukti

Misalkan P adalah sebuah graf terhubung berbobot. Pada setiap iterasi algoritma Prim, suatu cabang harus ditemukan yang menghubungkan sebuah node di graf bagian ke sebuah node di luar graf bagian. Karena P terhubung, maka selalu ada jalur ke setiap node. Keluaran Y dari algoritma Prim adalah sebuah pohon, karena semua cabang dan node yang ditambahkan pada Y terhubung. Misalkan Y₁ adalah pohon rentang minimum dari P. Bila Y₁=Y maka Y adalah pohon rentang minimum. Kalau tidak, misalkan e cabang pertama yang ditambahkan dalam konstruksi Y yang tidak berada di Y₁, dan V himpunan semua node yang terhubung oleh cabang-cabang yang ditambahkan sebelum e. Maka salah satu ujung dari e ada di dalam V dan ujung yang lain tidak. Karena Y₁ adalah pohon rentang dari P, ada jalur dalam Y₁ yang menghubungkan kedua ujung itu. Bila jalur ini ditelusuri, kita akan menemukan sebuah cabang f yang menghubungkan sebuah node di V ke satu node yang tidak di V. Pada iterasi ketika e ditambahkan ke Y, f dapat juga ditambahkan dan akan ditambahkan alih-alih e bila bobotnya lebih kecil daripada e. Karena f tidak ditambahkan, maka kesimpulannya

w(f) ≥ w(e).

Misalkan Y₂ adalah graf yang diperoleh dengan menghapus f dan menambahkan e dari Y₁. Dapat ditunjukkan bahwa Y₂ terhubung, memiliki jumlah cabang yang sama dengan Y₁, dan bobotnya tidak lebih besar daripada Y₁, karena itu ia adalah pohon rentang minimum dari P dan ia mengandung e dan semua cabang-cabang yang ditambahkan sebelumnya selama konstruksi V. Ulangi langkah-langkah di atas dan kita akan mendapatkan sebuah pohon rentang minimum dari P yang identis dengan Y. Hal ini menunjukkan bahwa Y adalah pohon rentang minimum.

Algoritma-algoritma lain untuk masalah ini adalah Algoritma Kruskal dan Algoritma Borůvka.

TEORI GRAPH

Apa itu Graph? Nih Dia,

Di matematika dan ilmu komputer, teori graf adalah cabang ilmu yang mempelajari sifat-sifat graf. Secara informal, suatu graf adalah himpunan benda-benda yang disebut verteks (atau node) yang terhubung oleh edge-edge (atau arc). Biasanya graf digambarkan sebagai kumpulan titik-titik (melambangkan verteks) yang dihubungkan oleh garis-garis (melambangkan edge).

Banyak sekali struktur yang bisa direpresentasikan dengan graf, dan banyak masalah yang bisa diselesaikan dengan bantuan graf. Jaringan persahabatan pada Friendster bisa direpresentasikan dengan graf: verteks-verteksnya adalah para pemakai Friendster dan ada edge antara A dan B jika dan hanya jika A berteman dengan B. Perkembangan algoritma untuk menangani graf akan berdampak besar bagi ilmu komputer.

Sebuah struktur graf bisa dikembangkan dengan memberi bobot pada tiap edge. Graf berbobot dapat digunakan untuk melambangkan banyak konsep berbeda. Sebagai contoh jika suatu graf melambangkan jaringan jalan maka bobotnya bisa berarti panjang jalan maupun batas kecepatan tertinggi pada jalan tertentu. Ekstensi lain pada graf adalah dengan membuat edgenya berarah, yang secara teknis disebut graf berarah atau digraf (directed graph). Digraf dengan edge berbobot disebut jaringan.

Jaringan banyak digunakan pada cabang praktis teori graf yaitu analisis jaringan. Perlu dicatat bahwa pada analisis jaringan, definisi kata “jaringan” bisa berbeda, dan sering berarti graf sederhana (tanpa bobot dan arah).

Suatu graph G dapat dinyatakan sebagai G = < V,E > . Graph G terdiri atas himpunan V yang berisikan verteks/node pada graph tersebut dan himpunan dari E yang berisi edge pada graph tersebut. Himpunan E dinyatakan sebagai pasangan dari verteks yang ada dalam V. Sebagai contoh definisi dari graf pada gambar diatas adalah : V = {1,2,3,4,5,6} dan E = {(1,2),(1,5),(2,3),(3,4),(4,5),(5,2),(4,6)}

Gambar dengan node yang sama dengan yang diatas, tapi merupakan digraf.

Pada digraf maka pasangan-pasangan ini merupakan pasangan terurut. Untuk menyatakan digraf (gambar kedua yang menggunakan tanda panah) kita dapat menggunakan himpunan edge sebagai berikut :

E = { < 1,2 > , < 1,5 > , < 2,5 > , < 3,2 > , < 4,3 > , < 5,4 > , < 4,6 > }

Dalam himpunan edge untuk digraf, urutan pasangan verteks menentukan arah dari edge tersebut.

Dalam teori graf, formalisasi ini untuk memudahkan ketika nanti harus membahas terminologi selanjutnya yang berhubungan dengan graph. Beberapa terminologi berhubungan dengan teori graf :

• Degree atau derajat dari suatu node, jumlah edge yang dimulai atau berakhir pada node tersebut. Node 5 berderajat 3. Node 1 berderajat 2.
• Path suatu jalur yang ada pada graph, misalnya antara 1 dan 6 ada path
• Cycle siklus ? path yang kembali melalui titik asal 2 kembali ke 2.
• Tree merupakan salah satu jenis graf yang tidak mengandung cycle. Jika edge f dan a dalam digraf diatas dihilangkan, digraf tersebut menjadi sebuah tree. Jumlah edge dalam suatu tree adalah nV – 1. Dimana nV adalah jumlah vertex

REKURSI

Apa itu Rekursi?

Rekursi yaitu procedure atau function yang memanggil dirinya sendiri.  Gunanya untuk melakukan proses berulang yang sulit diketahui kapan akan berakhir. Banyak bahasa pemrograman modern mendukung proses rekursi, misalnya Turbo Pascal, Visual Basic, dll. Contoh paling terkenal dari rekursi adalah proses menghitung nilai faktorial dan mencari deret Fibonacci.

Contoh listing program:

function faktorial(n : integer):integer;
begin
if (n = 0) then faktorial := 1
else faktorial := n * faktorial(n – 1);
end;

Deret Fibonacci didefinisikan sebagai deret integer tak berhingga, di mana suatu bilangan adalah penjumlahan dari dua bilangan sebelumnya.
Contoh: 1, 1, 2, 3, 5,  8, 12, 13, 21, 34, 55, 89, 144, …
Dari data di atas dapat difahami bahwa angka 5 merupakan hasil penjumlahan dari 2 dan 3, sedangkan 12 merupakan 5 + 8.

function fibonacci(n : integer):integer;
begin
if (n = 1) or (n = 2) then fibonacci := 1
else fibonacci := fibonacci(n – 1) + fibonacci(n – 2);
end;

Sebagian mahasiswa sulit membedakan antara Rekursi dan Iterasi, karena keduanya melakukan perulangan yang jumlah perulangannya sulit ditentukan kapan berakhir. Padahal secara mudah didefinisikan: Rekursi yaitu prosedur atau fungsi yang memanggil dirinya sendiri, sedangkan Iterasi adalah proses perulangan dalam suatu prosedur atau fungsi.

Berikut ini adalah contoh yang paling mudah dipahami. Tujuannya mencetak tulisan “M” dari kiri ke kanan layar.

REKURSI

uses
crt;

procedure rekursi;
begin
if wherex < 80 then
begin
write(‘M’);
rekursi;
end;
end;

begin
clrscr;
rekursi;
end.

ITERASI

uses
crt;

procedure iterasi;
begin
while wherex < 80 do
begin
write(‘M’);
end;
end;

begin
clrscr;
iterasi;
end.

Dari dua program pendek di atas, anda tentu mendapatkan sebuah fakta baru, yaitu rekursi dapat melakukan perulangan tanpa bantuan FOR NEXT, WHILE DO, REPEAT UNTIL, dsb. Menakjubkan bukan?

Beberapa buku menyatakan iterasi lebih baik, lebih mudah dipahami, dan lebih terstruktur daripada rekursi, namun menurut saya, rekursi mempunyai keistimewaan tertentu yang sulit digantikan oleh iterasi.

OBJECT ORIENTED PROGRAMMING

Konsep dasar dari Pemrograman Berorientasi Objek
Pemrograman orientasi-objek menekankan konsep berikut:

* [[Kelas(Ilmu komputer)|kelas]] — kumpulan atas definisi data dan fungsi-fungsi dalam suatu unit untuk suatu tujuan tertentu. Sebagai contoh ‘class of dog’ adalah suatu unit yang terdiri atas definisi-definisi data dan fungsi-fungsi yang menunjuk pada berbagai macam perilaku/turunan dari anjing. Sebuah class adalah dasar dari modularitas dan struktur dalam pemrograman berorientasi object. ”Sebuah class secara tipikal sebaiknya dapat dikenali oleh seorang non-programmer sekalipun terkait dengan domain permasalahan yang ada,” dan kode yang terdapat dalam sebuah class sebaiknya (relatif) bersifat mandiri dan independen (sebagaimana kode tersebut digunakan jika tidak menggunakan OOP). Dengan modularitas, struktur dari sebuah program akan terkait dengan aspek-aspek dalam masalah yang akan diselesaikan melalui program tersebut. Cara seperti ini akan menyederhanakan pemetaan dari masalah ke sebuah program ataupun sebaliknya.

* [[Objek (ilmu komputer)|Objek]] – membungkus data dan fungsi bersama menjadi suatu unit dalam sebuah [[program komputer]]; [[objek (pemrograman berorientas objek)|objek]] merupakan dasar dari [[modularitas (pemrograman)|modularitas]] dan [[struktur]] dalam sebuah program komputer berorientasi objek.

* [[Abstraksi (ilmu komputer)|Abstraksi]] – Kemampuan sebuah program untuk melewati aspek informasi yang diproses olehnya, yaitu kemampuan untuk memfokus pada inti. Setiap objek dalam sistem melayani sebagai model dari “pelaku” abstrak yang dapat melakukan kerja, laporan dan perubahan keadaannya, dan berkomunikasi dengan objek lainnya dalam sistem, tanpa mengungkapkan bagaimana kelebihan ini diterapkan. Proses, fungsi atau metode dapat juga dibuat abstrak, dan beberapa teknik digunakan untuk mengembangkan sebuah pengabstrakan.

* [[Penyembunyian informasi|Enkapsulasi]] – Memastikan pengguna sebuah objek tidak dapat mengganti keadaan dalam dari sebuah objek dengan cara yang tidak layak; hanya metode dalam objek tersebut yang diberi ijin untuk mengakses keadaannya. Setiap objek mengakses [[interface (ilmu komputer)|interface]] yang menyebutkan bagaimana objek lainnya dapat berinteraksi dengannya. Objek lainnya tidak akan mengetahui dan tergantung kepada representasi dalam objek tersebut.

* [[Polimorfisme (ilmu komputer)|Polimorfisme]] melalui pengiriman pesan. Tidak bergantung kepada pemanggilan subrutin, bahasa orientasi objek dapat mengirim pesan; metode tertentu yang berhubungan dengan sebuah pengiriman pesan tergantung kepada objek tertentu di mana pesa tersebut dikirim. Contohnya, bila sebuah burung menerima pesan “gerak cepat”, dia akan menggerakan sayapnya dan terbang. Bila seekor singa menerima pesan yang sama, dia akan menggerakkan kakinya dan berlari. Keduanya menjawab sebuah pesan yang sama, namun yang sesuai dengan kemampuan hewan tersebut. Ini disebut polimorfisme karena sebuah variabel tungal dalam program dapat memegang berbagai jenis objek yang berbeda selagi program berjalan, dan teks program yang sama dapat memanggil beberapa metode yang berbeda di saat yang berbeda dalam pemanggilan yang sama. Hal ini berlawanan dengan [[bahasa fungsional]] yang mencapai polimorfisme melalui penggunaan fungsi kelas-pertama.

* [[Inheritas (ilmu komputer)|Inheritas]]- Mengatur polimorfisme dan enkapsulasi dengan mengijinkan objek didefinisikan dan diciptakan dengan jenis khusus dari objek yang sudah ada – objek-objek ini dapat membagi (dan memperluas) perilaku mereka tanpa haru mengimplementasi ulang perilaku tersebut ([[bahasa berbasis-objek]] tidak selalu memiliki inheritas.)

* Dengan menggunakan OOP maka dalam melakukan pemecahan suatu masalah kita tidak melihat bagaimana cara menyelesaikan suatu masalah tersebut (terstruktur) tetapi objek-objek apa yang dapat melakukan pemecahan masalah tersebut. Sebagai contoh anggap kita memiliki sebuah departemen yang memiliki manager, sekretaris, petugas administrasi data dan lainnya. Misal manager tersebut ingin memperoleh data dari bag administrasi maka manager tersebut tidak harus mengambilnya langsung tetapi dapat menyuruh petugas bag administrasi untuk mengambilnya. Pada kasus tersebut seorang manager tidak harus mengetahui bagaimana cara mengambil data tersebut tetapi manager bisa mendapatkan data tersebut melalui objek petugas adminiistrasi. Jadi untuk menyelesaikan suatu masalah dengan kolaborasi antar objek-objek yang ada karena setiap objek memiliki deskripsi tugasnya sendiri.

Bahasa pemrograman yang mendukung OOP antara lain:

1. Visual Foxpro
2. Java
3. C++
4. Pascal (bahasa pemrograman)
5. Visual Basic.NET
6. SIMULA
7. Smalltalk
8. Ruby
9. Python
10. PHP
11. C#
12. Delphi
13. Eiffel
14. Perl

AMDHAL’s LAW…WHAT ABOUT IT’s?

Hukum Amdahl

Telah dijelaskan bahwa dari <math> T_1 </math> (waktu yg dibutuhkan menjalankan pekerjaan dalam satu komputer) tadi, ada sebagian yg tidak bisa diparalelkan. Untuk menyatakan ini kita gunakan notasi <math> \alpha </math> dimana <math> 0 \le \alpha \le 1</math> menunjukkan berapa bagian dari <math> T_1 </math> yang ”’tidak bisa ”’ dijadikan paralel (atau bagian serial dari program ini).

Maka kita ketahui <math> \alpha * T_1 </math> adalah waktu yg tidak akan terpengaruh oleh bertambahnya komputer yg digunakan (a).

Sisanya <math> (1 – \alpha) * T_1 </math> adalah waktu yang akan berkurang menjadi <math> \frac {(1 – \alpha) * T_1} {N} </math> bila kita menggunakan
N komputer tambahan {b) .

Sehingga waktu total yang dibutuhkan untuk menjalankan pekerjaan dalam N komputer adalah (a) + (b) alias :
:<math> T_N = \alpha * T_1 + \frac {(1 – \alpha) * T_1} {N} </math>

[[Peningkatan kecepatan]] yang kita peroleh dari persamaan ini adalah :

:<math> S_N = \frac{T_1}{\alpha * T_1 + \frac {(1 – \alpha) * T_1}{N}} </math>

Mungkin anda akan mendapati persamaan speed up yang terlihat berbeda tapi pada dasarnya sama. Persamaan dibawah, bisa didapat dari persamaan diatas, dengan mengeliminasi komponen <math>T_1</math> (pada bagian atas dan bawah persamaan), lalu mengatur N dan <math> \alpha </math>

:<math> S_N = \frac{N}{1 +  \alpha(N-1)} </math>

Bila anda cermati persamaan di atas, bisa dilihat bahwa jika kita menggunakan komputer yang amat banyak (<math> N \rightarrow \infty </math>) komponen (b) akan dapat diabaikan, menyisakan persamaan :
:<math> S_N = \frac{1}{\alpha} </math>

Inilah batas maksimum [[peningkatan kecepatan]] yang bisa dicapai menurut [[hukum Amdahl]] yaitu perbandingan terbalik dari seberapa banyak bagian serial dari suatu pekerjaan.

Dalam [[sistem terdistribusi]] dimana anda berusaha menggunakan lebih banyak prosesor untuk menyelesaikan masalah, akan ada imbal balik. Menggunakan komputer tambahan dari lokasi yang berbeda memberikan anda sumber komputasi baru, tapi juga melibatkan biaya komunikasi tambahan, saat anda harus memberikan pekerjaan tersebut pada komputer yg terpisah.

Komputasi Paralel

Pemrograman paralel adalah teknik [[pemrograman komputer]] yang memungkinkan eksekusi perintah/operasi secara bersamaan ([[komputasi paralel]]), baik dalam komputer dengan satu (prosesor tunggal) ataupun banyak (prosesor ganda dengan [[mesin paralel]]) [[CPU]]. Bila komputer yang digunakan secara bersamaan tersebut dilakukan oleh komputer-komputer terpisah yang terhubung dalam suatu [[jaringan komputer]] lebih sering istilah yang digunakan adalah [[Komputasi Terdistribusi|sistem terdistribusi]] (”distributed computing”).
Tujuan utama dari pemrograman paralel adalah untuk meningkatkan performa [[komputasi]]. Semakin banyak hal yang bisa dilakukan secara bersamaan (dalam waktu yang sama), semakin banyak pekerjaan yang bisa diselesaikan. Analogi yang paling gampang adalah, bila anda dapat merebus air sambil memotong-motong bawang saat anda akan memasak, waktu yang anda butuhkan akan lebih sedikit dibandingkan bila anda mengerjakan hal tersebut secara berurutan (serial). Atau waktu yg anda butuhkan memotong bawang akan lebih sedikit jika anda kerjakan berdua.

Performa dalam pemrograman paralel diukur dari berapa banyak [[peningkatan kecepatan]] (”speed up”) yang diperoleh dalam menggunakan tehnik paralel. Secara informal, bila anda memotong bawang sendirian membutuhkan waktu 1 jam dan dengan bantuan teman, berdua anda bisa melakukannya dalam 1/2 jam maka anda memperoleh peningkatan kecepatan sebanyak 2 kali.

Peningkatan Kecepatan Komputasi Paralel

[[Peningkatan kecepatan]] dapat diformulasikan dalam persamaan berikut ini

<math> S = \frac{T_1}{T_j} </math>

Dimana <math> T_1 </math> adalah waktu yang dibutuhkan untuk menyelesaikan pekerjaan ([[program komputer]]) bila dijalankan dalam satu komputer. Dan <math> T_j </math> adalah waktu yang dibutuhkan jika pekerjaan dikerjakan bersamaan oleh beberapa komputer.

Ada limitasi dalam usaha membuat suatu [[program komputer]] berjalan lebih efisien melalui [[peningkatan kecepatan]], hukum yang menetapkan batasan ini dikenal sebagai [[Hukum Amdahl]]. Ide dari hukum amdahl ini adalah bahwa anda hanya akan bisa meningkatkan efisiensi [[program komputer]] anda, sebatas pada bagian tertentu dari program tersebut yang dapat di paralelkan. Sementara bagian yang memang harus dilaksanakan secara berurutan, akan menjadi penentu performa akhir.

Kembali ke analogi memasak tadi, bila anda harus menggunakan sarung tangan sebelum menyalakan kompor ataupun memotong bawang, maka waktu yang anda butuhkan untuk memakai sarung tangan ini adalah waktu serial, yang tidak dapat dihindari. Sementara waktu untuk memasak dan memotong bawang tadi adalah bagian yang bisa diparalelkan.

COA ADA DISINI, WHOSE FRIEND COA???

COA( COMPUTER ORGANIZATION AND ARCHITECTURE)

Arsitektur Komputer : mempelajari atribut-atribut sistem komputer yang terkait dengan eksekusi logis sebuah program.

Organisasi Komputer : mempelajari bagian yang terkait dengan unit-unit operasional komputer dan hubungan antara komponen-komponen sister komputer.

PENGERTIAN MEMORY

Memori merupakan media penyimpanan data pada komputer yang memiliki kapasitas yang berbeda-beda.

Banyaknya kapasitas memori biasanya dibulatkan dengan hitungan :

Jadi dapat disimpulkan bahwa besarnya kapasitas memori ini merupakan kelipatan dari 2. yaitu :

2,4,8,16,32,64,128,256,512,1024,2048,…..,dst.

Kita sering mengenal istilah kilobyte, megabyte, gigabyte dan lain sebagainya. Disini kita akan menjalaskan

istilah-istilah tersebut.

• Kilobyte merupakan nilai satuan yang didapat dari hasil pembagian perseribu (/1000) dari nilai perbyte atau nilai byte dibagi dengan 1000. lalu nilai hasilnya dibulatkan untuk supaya dengan mudah dapat diingat.

• Megabyte merupakan nilai satuan yang didapat dari hasil bagi 1.000.000 dari nilai satuan byte. Atau juga diperoleh hasil bagi 1000 dari nilai satuan kilobyte.

• Gigabyte merupakan nilai satuan yang didapat dari hasil bagi 1.000.000.000 dari nilai satuan byte.

Atau diperoleh hasil bagi 1000 dari nilai satuan Megabyte dan juga hasil bagi 1.000.000 dari nilai

satuan Kilobyte

Contoh pada kapasitas memori :

210 = 1024b = 1 Kb , dalam hitungan matematika ini harusnya bernilai 1,024Kb akan tetapi untuk

mempermudahnya kita bulatkan menjadi 1kb begitu juga untuk nilai yang lainnya,

220 = 1.048.576b = 1 Mb ,.

222 = 4.194.304b = 4 Mb ,.

223 = 8.388.608b = 8 Mb ,.

Kapasitas Memori = 2n x bit

230 = 1.073.741.824b = 1.000 Mb = 1Gb

232 = 4.294.967.296b = 4.000 Mb = 4Gb,…dst

B. Merangkai Memori Lebih Dari Satu Memori

Kita dapat menambahkan beberapa memori dengan menjumlahkan banyaknya memori yang saling

berhubingan. Untuk menghubungkan memori-memori tersebut kita membutuhkan sebuah decoder sebagai

kode pengalamatan. Contoh :

kita akan membuat memori dengan kapasitas 16b dari 8b,dan 2 buah 4b.

16 = 8+4+4

Kita ubah nilai diatas menjadi 2n, maka hasilnya 24 = 23 + 22 + 22 .

Nilai pangkat tersebut adalah cara untuk mengetahui banyaknya saluran data yang terdapat dalam

memori tersebut. Untuk mengetahui banyaknya jumlah saluran data (input) kita ambil nilai pangkat

yang paling besar, dari nili diatas nilai pangkat yang paling besar adalah 24. maka saluran data

inputannya adalah 4. Nilai 4 ini kita inisialisasikan dengan notasi I₀, I₁, I₂ dan I₃. dan 1 output.

Hubungan antara memori dengan prosessor keduanya saling berkaitan. Definisi fungsi secara umum

prosessor berfungsi untuk memproses seluruh bagian dan mengolah data dengan dilengkapi sistem kontrol sebagai pengatur data untuk diproses. Sementara memori adalah media untuk menampung beberapa data pada saat data diproses atau digunakan sebagai media menyimpanan data yang suatu saat akan diperlukan oleh prosessor.

Secara umum relasi antara memori dengan prosessor yang terdapat pada CPU dihubungkan dengan saluran data, saluran alamat dan saluran control. Jika memiliki beberapa memori sebagai kapasitas tambahan maka akan diperlukan pada prosessor sebuah decoder sebagai gerbang/kunci yang menentukan alamat data yang akan digunakan.

B. Rangkaian Memori

Disini akan dijelaskan mengenai rangkaian memori dengan kapasitas 1K x 8bit terhadap relasi ke prosessor.

Kita akan mengetahui banyaknya saluran data yang menghubungkan keduanya, banyaknya saluran alamat, kapasitas total memori, alamat awal dan alamat akhir memori.

• Saluran Data

Banyaknya saluran data ditentukan oleh banyaknya jumlah dalam perbyte. Contoh 32 K x 8 byte

maka jumlah saluran datanya ada 8. jika diketahui 125K x 16byte maka jumlah saluran datanya ada

16 saluran. Jadi untuk 1K x 8byte jumlah saluran datanya ada 8.

—saluran data = 8.

• Saluran Alamat

Banyaknya saluran alamat diperoleh dari total kapasitas yang di ubah menjadi bilangan 2n . n inilah

yang menentukan jumlah saluran alamat.

Berarti jika diketahui kapasitas memori 1K x 8byte maka 1K = 1024, kita masukan kedalam rumus

diatas, maka 1024 = 210. jumlah saluran alamat.

—saluran alamat = 10.

• Total Kapasitas Memori

Total kapasitas memori didapat dari jumlah total memori yang diketahui. Disini diketahui total

memori dari 1K x 8byte adalah 1K = 210

=1024

—total kapasitas memori = 1024.

• Alamat Awal

Untuk mengetahui alamat awal kita harus mengetahui kapasitas memori tersebut lalu diubah dalam

hitungan 2n , maka n inilah yang menentukan banyaknya alamat. Hal ini bertujuan untuk

mempermudah dalam menghitung banyaknya alamat.

Diketahui jumlah saluran = 10. kita tulis untuk alamat awal = 0 biner.

• Alamat Akhir

Alamat akhir diperoleh dari hasil nilai akhir yang terdapat pada jumlah alamat bilangan biner yaitu 1.

Gambar. Relasi antara Prosessor dengan Memori

Arsitektur Komputer

IQBAL ABDULLAH BASAR 077006070

Perintahnya diambil dari NPM yang akhirnya saja, yaitu 0. Maka Arsitektur Komputer AK x 8 bit dari 4 buah BK x 8 bit adalah :

0 => 2⁰ k x 8 bit = 1 k x 8 bit

Jadi tugasnya:

4k x 8 bit dari 4 buah 1k x 8 bit

1k = 1 x 2 ¹⁰ = 1024

Untuk yang 1k x 8 bit

Memiliki :

· Saluran Data : 8 dari D₇ – D₀

· Kapasitas Memory : 1 x 2 ¹⁰ = 1024

· Saluran Alamat : 1024 = 2¹⁰, hasilnya 10. Jadi Saluran Alamatnya dari A₉ – A₀

· Alamat Awal : karena Saluran Alamatnya bernilai 10, maka :

Alamat awalnya 00 0000 0000 _b = 000 _h

· Alamat Akhir : seperti Alamat Awal, cuman beda nilainya saja.

Alamat Akhir 11 1111 1111 _b = 3FF _h

Karena nilai 11 dari biner 0011 = 3 dan nilai 1111 = 15 = F

Untuk yang 4k x 8 bit

Memiliki :

· Saluran Data : 8 dari D₇ – D₀

· Kapasitas Memory : 4 x 1024 = 4096

· Saluran Alamat : 4k = 2² x 2¹⁰ = 2¹², hasilnya 12. Jadi Saluran Alamatnya dari A₁₁ – A₀

· Alamat Awal : karena Saluran Alamatnya bernilai 12, maka :

Alamat awalnya 0000 0000 0000 _b = 000 _h

· Alamat Akhir : seperti Alamat Awal, cuman beda nilainya saja.

Alamat Akhir 1111 1111 1111 _b = FFF _h

Karena nilai 1111 = 15 = F

gambar ecoder

gambar rangkaian memory
Tabel memory 1k x 8 bit

Tabel Memory 4 k x 8 bit

DO You Know About Binary System???? FiNd Here!

SISTEM BINER

Sistem bilangan biner merupakan sistem bilangan dengan basis 2. Sistem bilangan biner menggunakan dua buah simbol yaitu : 0 dan 1. Contoh bilangan biner adalah 1001 yang dapat diartikan dalam sistem bilangan desimal menjadi sebagai berikut :

Position value dalam sistem bilangan biner merupakan perpangkatan dari nilai 2.

Nilai desimal dari sistem bilangan biner juga dapat dicari menggunakan rumus dibawah ini.

Contoh :

Pertambahan Bilangan BINER

Pertambahan pada sistem bilangan biner dilakukan dengan cara yang sama dengan pertambahan pada sistem bilangan desimal. Dasar dari pertambahan sistem bilangan biner dapat dilihat pada gambar dibawah ini.

Contoh pertambahan bilangan BINER :

Pengurangan Bilangan BINER

Pengurangan pada sistem bilangan BINER dilakukan dengan cara yang sama dengan pengurangan sistem bilangan desimal. Dasar dari pengurangan sistem bilangan BINER dapat dilihat pada gambar dibawah ini.

Contoh pengurangan bilangan biner:
Pengurangan bilangan biner juga dapat dilakukan dengan menggunakan Komplemen. Terdapat dua macam komplemen pada sistem bilangan biner yaitu : Komplemen 1 (1s complement) dan Komplemen 2 (2s complement).
Contoh pengurangan bilangan biner menggunakan komplemen 1 :

Komplemen 1 pada sistem bilangan biner dilakukan dengan mengurangkan setiap bit dengan nilai 1, atau dengan cara mengubah setiap bit 0 menjadi 1 dan setiap bit 1 menjadi 0. Dengan komplemen 1, hasil digit paling kiri dipindahkan untuk ditambahkan pada bit paling kanan.
Contoh pengurangan bilangan biner menggunakan komplemen 2 :

Komplemen 2 adalah hasil dari komplemen 1 ditambah 1, misalnya komplemen 2 dari bilangan BINER 10110 adalah 01010 (dari komplemen 1 yaitu 01001 ditambah 1). Dengan menggunakan komplemen 2, hasil digit paling kanan dibuang, tidak digunakan.

Perkalian Bilangan BINER

Perkalian bilangan biner dilakukan dengan cara yang sama dengan perkalian pada sistem bilangan desimal. Dasar perkalian untuk masing-masing digit bilangan biner dapat dilihat pada gambar dibawah ini :

Contoh perkalian bilangan BINER :

Perhatikan, ada dua keadaan dalam perkalian bilangan biner, jika pengali adalah bilangan 1 maka cukup disalin saja, jika pengali adalah bilangan 0 maka hasilnya semuanya 0.

Pembagian Bilangan Biner

Pembagian bilangan biner juga dilakukan dengan cara yang sama dengan pembagian bilangan desimal. Pembagian dengan 0 tidak mempunyai arti, sehingga dasar untuk pembagian menjadi seperti dibawah ini.

Contoh pembagian pada bilangan biner

CLUSTER???? APA??? CHECK THIS OUT!!!

CLUSTER COMPUTER

Secara sederhana, komputer cluster didefenisikan sebagai kumpulan komputer pribadi (PC) yang dirangkai sedemikian rupa (menggunakan jaringan komputer) yang bekerja sama untuk menyelesaikan suatu pekerjaan sehingga pekerjaan tersebut dapat diselesaikan dengan lebih cepat.

Penggunaan cluster ini didasari pada kenyataan bahwa umumnya suatu penyelesaian permasalahan dapat dipecah-pecah dalam bagian-bagian kecil, sehingga penyelesaian per-bagian dapat dikerjakan secara terpisah.

Sebagai contoh, pada balapan F1, saat mobil masuk stop pit maka ada yang khusus mengganti ban kanan/kiri, mengisi bahan bakar, dll. Apabila hanya satu orang yang melakukan semua itu, maka pekerjaan itu akan membutuhkan waktu yang lama.

Cluster dibutuhkan jika kita membutuhkan sumber daya besar untuk menyelesaikan suatu masalah, misalnya pencocokan Gen. Apabila kita mencari satu persatu data gen dari database yang ada, maka mungkin akan butuh 6 bulan dengan satu komputer, namun dengan cluster bisa cuman 6 hari bahkan 6 jam atau bahkan 6 menit tergantung kemampuan cluster tersebut.

Tidak harus cluster memang. Di dunia ini ada juga yang namanya Super Komputer yaitu satu komputer yang mempunyai kemampuan ribuan kali dari komputer pribadi. Namun tentu saja harganya akan sangat mahal dan kalau ada kerusakan maka perlu biaya perbaikan yang besar pula.

Beda dengan cluster. Node cluster terdiri dari PC biasa, jadi kalo rusak maka perbaikan sama dengan memperbaiki PC anda dirumah.

Kelemahan cluster tentunya adalah karena node-node cluster tersebut terpisah maka akan ada delay waktu untuk transfer data diantara node. Dan membuat program di cluster tentu beda dengan membuat program pada satu komputer. Anda harus bisa memecah pekerjaan supaya terdistribusi secara baik diantara node, dll.

Kelebihan cluster dibandingkan dengan super komputer tentunya lebih murah, lebih fleksibel (dapat upgrade sesuai dengan kemampuan), dll.