Algoritma dan Pemograman Pendekatan pemograman Modular

KATA PENGANTAR

Dengan memanjatkan do'a dan puji syukur kehadirat Allah SWT serta sholawat serta salam tercurahkan ke junjungan kita Nabi Muhammad SAW, sehingga penulis dapat menyelesaikan makalah dengan judul Algoritma dan Pemograman Pendekatan pemograman Modular .Adapun penulisan makalah ini dapat terselesaikan berkat bantuan dari segala pihak yang menyelesaikan makalah ini.

Teknologi Informasi adalah salah satu jurusan di Fakultas Ilmu Pendidikan Universitas Almuslim yang lulusannya diharapkan menjadi pendidik yang profesional dibidangnya.. Teknologi Informasi dan Komunikasi adalah mata kuliah yang sangat perlu dikembangkan mengingat begitu besar peranannya dalam pendidikan, khususnya pada pembelajaran disekolah dengan menggunakan media.

Penulis menyadari akan kekurangan dalam penysunan makalah ini. Karena itu kami sangat mengharapkan kritik dan saran yang bersifat membangun dari semua pihak demi kesempurnaan makalah ini.

Matang, 1 Januari 2011

Penyusun

DAFTAR ISI

Kata Pengantar ................................................................................................... i

Daftar Isi ............................................................................................................ ii

Bab I Pendahuluan ............................................................................................. 1

1.1.Latar Belakang ..................................................................................... 1

1.2.Tehnik pemograman ............................................................................. 1

1.3.Bentuk sub modul ................................................................................ 2

Bab II Pembahasa ............................................................................................... 3

2.1.Model Top-Down ................................................................................ 3

2.2 Pendekatan Pemograman Modular .................................................... 4

2.3 Algoritma Welsh & Powell ................................................................ 9

2.4 Algoritma Prim .................................................................................... 11

Bab III Penutup .................................................................................................. 13

........ 3.1. Kesimpulan ......................................................................................... 13

3.2. Saran ................................................................................................... 13

Daftar Pustaka

BAB I

PENDAHULUAN

1.1. Latar Belakang

Pengertian LOGIKA:

Logika berasal dari bahasa Yunani yaitu LOGOS yang berarti ilmu. Logika pada dasarnya filsafat berpikir. Berpikir berarti melakukan suatu tindakan yang memiliki suatu tujuan. Jadi pengertian Logika adalah ilmu berpikir / cara berpikir dengan berbagai tindakan yang memiliki tujuan tertentu.

Pengertian ALGORITMA:

Pada Merriam-Webster’s Collegiate Dictionary, istilah algoritma diartikan sebagai prosedur langkah demi langkah untuk memecahkan masalah atau menyelesaikan suatu tugas. Kamus Besar Bahasa Indonesia (KBBI) mendefinisikan algoritma sebagai urutan logis pengambilan keputusan untuk pemecahan masalah.

Algoritma & Modular Programming Merupakan paradigma pemrograman yang pertama kali diperkenalkan oleh Information Ciri:

1. ada keyword return

2. ada tipe data yang mengawali fungsi

3 Pemrograman Modular:

Program dipecah-pecah kedalam modul-modul, dimana setiap modul Ciri-ciri pemrograman terstruktur. Mengandung teknik pemecahan masalah yang tepat Algoritma Pemrograman Yang Baik. Ciri-ciri algoritma pemrograman yang baik adalah : dapat membantu memecahkan masalah antara lain teknik Top Down dan teknik Modular. Mengenal Pemrograman Berbasis Obyek (OOP) pada C++ yang akan kita buat menjadi lebih modular Ciri -ciri dasar OOP.

B.Teknik Pemrograman

Penekanan pada pemrograman terstruktur

 Struktur dasar

Menggunakan flow chart dan pseudocode

Menggunakan sistem modular.

 Program dibuat dalam bentuk modul-modul untuk fungsi tertentu maupun

subroutine tertentu.

 Modul-modul dikendalikan oleh modul utama (program utama

 Modul bersifat independen (tidak ada modul yang dapat akses langsung

ke modul lain, kecuali modul pemanggil dan submodulnya sendiri)

 Modul dapat diubah secara radikal tanpa mempengaruhi modul lain sejauh fungsi modul tidak berubah

Implementasi pemrograman modul menggunakan subroutine-subroutine digambarkan

sebagai berikut;

1.3. Bentuk sub module

 Internal subroutine; berupa bagian dari program yang

menggunakannya

 External subroutine;

 bukan bagian dari program yang menggunakan modul itu.

 Modul tersimpan dalam library dalam bentuk ”object module” yang siap

digunakan oleh modul-modul yang akan menggunakan.

 Modul dapat digunakan untuk tugas lebih dari satu program

 Dalam menggunakan, pemrograman perlu mengetahui di mana

diperoleh, namanya, bagaimana mengirim data padanya, dan

jabawan baliknya.

BAB II

PEMBAHASAN

2.1 MODEL TOP-DOWN

 modul utama tunggal

 sub modul dari suatu modul minimum dua. Bila hanya satu ditijau kembali seperti

contoh berikut ;

Teori Graf

Siklus Hamilton (Hamiltonian cycle) adalah siklus dalam graf G yang

mengandung setiap verteks di G tepat satu kali.

Contoh 10.1 :

Untuk graf G = (V,E) dalam Gambar 10.1, carilah sebuah siklus

Hamilton.

Penyelesaian :

Sebuah siklus Hamilton untuk graf G adalah siklus (a, b, c, d, e, f, g, a).

Masalah Perjalanan Wiraniaga

 Soal perjalanan wiraniaga berkaitan dengan masalah pencarian siklus

Hamilton dengan panjang minimum dalam sebuah graf berbobot G.

Jika kita menganggap verteks-verteks dalam graf berbobot sebagai kota

dan bobot rusuk sebagai jarak, masalah perjalanan wiraniaga adalah

mencari sebuah rute terpendek sehingga wiraniaga tersebut dapat

mengunjungi setiap kota satu kali, berawal dan berakhir pada kota

yang sama.

 Contoh 10.2 :

Selesaikanlah masalah perjalanan wiraniaga untuk graf berikut.

Kita lihat bahwa siklus

Hamilton (a, b, c, d, a) dan

(a, d, c, b, a) merupakan

siklus Hamilton dengan

panjang minimum untuk G.

Penyelesaian :

Siklus Hamilton	Panjang
(a, b, c, d, a) (a, b, d, c, a) (a, c, b, d, a) (a, c, d, b, a) (a, d, b, c, a) (a, d, c, b, a)	2+3+3+2 = 10 2+11+3+11 = 27 11+3+11+2 = 27 11+3+11+2 = 27 2+11+3+11 = 27 2+3+3+2 = 10

2.2 PENDEKATAN PEMROGRAMAN MODULAR

GRAPH

Graph terdiri dari simpul-simpul dan lintasan-lintasan.

 Simpul

VERTEX : dapat mewakili peristiwa kata, sasaran, dan sebagainya.

 Lintasan

 Lintasan i j : menghubungkan simpul i dan j

 Lintasan bearah ij : menunjujkkan lintasan yang dilewati 9ditunjukan dengan

anak panah) dari simpul i menuju j

 Lintasan langsung i j: lintasan dari i ke j tanpabmelewati simpul yang lain.

 Lintasan tak langsung ij : lintasan dari I ke j dengan melewati simpul lain.

GRAPH

3. Derajat simpul (vertex) :

 k : menunujukkan cacah lintasan yang terhubung dengan simpul yang

bersangkutan.

 Derajat simpul masuk k1 : menunjukkan cacah lintasan yang masuk menuju simpul

 Derajat simpul keluar k2 : cacah lintasan yang keluar

Graph dapat mewakili :

 jaringan transportasi

 jaringan kegiatan suatu proyek dan lain-lain

Lintasan dapat mewakili : biaya operasi, jarak antara simpul

(kota), profit, dan sebagainya. Besaran dalam dimensinya

masing-masing

Graph dapat direpresentasikan dalam bentuk matrik lintasan

1 = ada lintasan

0 = tidak ada

simpul y Graph dapat

direpresentasikan dalam bentuk matrik

lintasan ang bersangkutan

→ 1 = TRUE

0 = FALSE

Graph dengan lintasan berarah = directed graph = diagraph

Graph dengan lintasan tak berarah = undirect graph = undiagraph

Disini hanya muncul ada atau tidak hubungan antara dua vertex ( dalam undirect graph

(undiagraph) lintasan tak berarah, matriks lintasannya simetris

Matrik lintasan tak berarah

1 = ada hubungan

0 = tidak ada hubungan

atau vertex itu sendir

bobot lintasan menunjukkan harga besaran yang diwakilinya. Dalam banyak kasus nilai

dalam lintasan menunjukkan harga besaran yang diwakilikinya.

Misalnya untuk masalah transportasi ada unsur-unsur matriks lintasan menunjukkan

biaya ( dalam satuan mata uang). Untuk vertex i ke j bila tidak ada lintasannya, biaya

= ∞ dan bila i biaya = 0

Nilai 0 dan ~

Tak ditulis

Dalam lintasan berarah, bobot lintasan yang dicantumkan dalam matrik lintasan hanya

bila ada lintasan ( matrik lintasan mungkin tidak simetris).

→ matrik lintasan mungkin tidak simetris

Contoh kasus :

 mencari lintasan terpendek atau biaya termurah dari suatu perjalanan

 perjalanan diawali dari salah satu vertex, menuju kepada semua vertex lain

Algoritma untuk menemukan lintasan terpendek dikenalkan oleh

E.Dijkstra

3. Awali pada lintasan (i) pada simpul (vo),

lintasan terpendek dari vo-v1. lingkup S→Vo.

5. Pilih vertex (v-s) sedemikian sehingga lintasan (v) minimu dari

semua lintasan dalam (v-s)

6. Untuk setiap u dalam 1-s, diperbarui lintasan (u) = min,

lintasan u, lintasan w, lintasan (v,w)

7. Ulangi langkah 2

Representasi dalam linklist

· Graph coloring adalah problem klasik algoritma tentang bagaimana caranya mewarnai graph dengan warna berbeda untuk setiap node yang ”berdekatan”

o Berdekatan berarti ada edge yang menghubungkan kedua node tersebut

o Nilai adjacency-nya lebih besar dari 0

· Tantangan dari problem ini adalah bagaimana caranya mengusahakan agar jumlah warna yang diperlukan seminimal mungkin.

· Edge coloring

o Bukan node yang diwarnai melainkan edge-nya. Sejumlah edge yang bertemu di node tertentu tidak boleh diberi warna yang sama.

· Region coloring

o Mewarnai sebidang wilayah yang terbagi atas sub-wilayah kecil.Setiap sub-wilayah yang memiliki perbatasan tidak boleh diberiwarna yang sama. Problem ini lebih terkenal dengan sebutan map coloring.

o Map coloring dapat diselesaikan dengan mengubahnya menjadi graph, mewarnai graph, kemudian dipetakan kembali.

CHROMATIC NUMBER

 Diperlukan 3 warna untuk mewarnai graph di atas

 Jumlah warna minimal yang harus dipakai untuk mewarnai sebuah

graph disebut chromatic number.

MAP COLORING

KONVERSI MAP KE GRAPH

2.3 ALGORITMA WELSH & POWELL

1. Urutkan node dalam sebuah graph berdasarkan jumlah edge yang terhubung padanya, secara descending (dari besar ke kecil)

2. Berdasarkan urutan di atas, warnai semua node dalam graph dengan warna 1

3. jika sebuah node tidak berbatasan dengan node yang sudah berwarna 1

4. Ulangi proses ini untuk warna 2, warna 3, dst hingga semua node telah diberi

5. Warna

 Merupakan salah satu contoh algoritma Metode Greedy

 Hasilnya belum tentu optimal

 Penyelesaian secara optimal adalah NP-Complete problem

 Baca bab 6.6 di buku untuk penjelasan detil langkah per langkah jalannya

algoritma Welsh & Powell

HASIL GRAPH COLORING

MAP COLORING

2.4 Algoritma Prim

Sebuah algoritma dalam teori graf untuk mencari pohon rentang minimum untuk sebuah graf berbobot yang saling terhubung. Ini berarti bahwa sebuah himpunan bagian dari edge yang membentuk suatu pohon yang mengandung node, di mana bobot keseluruhan dari semua edge dalam pohon diminimalisasikan. 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 V.Jarnik 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.

Algoritma Prim

Untuk menentukan minimum spanning tree

Algoritmanya:

 Inisialisasi tree T

 T diperbaharui bila lintasan adalah minimum yang

menghubungkan vertex, dan vertex tak di T, maka T←T+e

 Bila E(T) = p – 1 (p= cacah vertex maka output adalah E(T)).

Bila tidak, ke langkah 2.

Algoritma Prim.

Contoh :

Algoritma Bouruvka

Untuk menentukan minimum spanning tree

Algoritmanya:

4. Inisialisasi spanning Forest . F→Fp

5. Forest F diperbaharui. Untuk tiap komponen F’ dari hubungan

vertex F’ ke vertex lain dari F dengan lintasan minimum.

Set lintasan adalah S, sehingga F → F+ S

7. Lintasan |E(F)|=p-1 [ p cacah vertex maka output E(F),

sebaliknya ke langkah 2.

Algoritma Bouruvka

Contoh

BAB III

PENUTUP

3.1. Kesimpulan

Logika berasal dari bahasa Yunani yaitu LOGOS yang berarti ilmu. Logika pada dasarnya filsafat berpikir. Berpikir berarti melakukan suatu tindakan yang memiliki suatu tujuan. Jadi pengertian Logika adalah ilmu berpikir / cara berpikir dengan berbagai tindakan yang memiliki tujuan tertentu.

istilah algoritma diartikan sebagai prosedur langkah demi langkah untuk memecahkan masalah atau menyelesaikan suatu tugas

Algoritma & Modular Programming Merupakan paradigma pemrograman yang pertama kali diperkenalkan oleh Information

3.2. S a r a n

Penyusunan makalah ini dapat dianggap cukup,namun masih diperlukan tambahan perbaikan – perbaikan untuk menghasilkan makalah yang lebih baik lagi dan lengkap.

Adapun saran dari penyusun adalah perlu adanya perbaikan – perbaikan tambahan dari pembaca untuk kesempurnaan dalam pembuatan makalah ini

DAFTAR PUSTAKA

Oky Dwi Nurhayati, ST, MT (email: okydn@undip.ac.id)