Jasa Urus Dokumen Expatriat

ALGORITMA
1.1. Pendahuluan
Algoritma memegang peranan penting dalam bidang pemrograman. Sebegitu
pentingnya suatu algoritma, sehingga perlu dipahami konsep dasar algoritma. Apalagi
untuk seorang programer, tentu diperlukan suatu algoritma sehingga dapat membuat
program yang lebih efektif dan efisien. Bagi kebanyakan orang, algoritma sangat
membantu dalam memahami konsep logika pemrograman.
Algoritma adalah kumpulan instruksi yang dibuat secara jelas untuk menunjukan
langkah-langkah penyelesaian suatu masalah. Pada umumnya algoritma kurang lebih sama
dengan suatu prosedur yang sering dilakukan setiap hari, misalnya prosedur untuk
mengganti ban bocor/pecah, prosedur pemakaian telepon umum, prosedur membuat kue
dan lain-lain.


Dalam bidang komputer, misalnya EDP (Elektronik Data Processing) atau MIS
(Management Information System), algoritma sering dimanfaatkan untuk menyelesaikan
suatu masalah atau untuk proses pengambilan keputusan. Seorang sistem analisis (analisist
system) tentunya menggunakan algoritma untuk merancang suatu sistem. Bagi seorang
programer, algoritma digunakan untuk membuat modul-modul program.
Guna memahami suatu algoritma, harus dimiliki pengetahuan dasar matematika
karena pada dasarnya algoritma lahir dari konsep logika matematika. Disini yang perlu
dilatih adalah kemampuan logikanya agar benar-benar bisa menyusun langkah-langkah
penyelesaian masalah dengan baik.
Dalam buku ajar ini, disajikan konsep dasar dan analisis algoritma. Pada bagian
konsep dasar dibahas komponen utama, desain, dan contoh pembuatan. Selanjutnya, untuk
mendapatkan algoritma yang efisien serta mendapatkan rumusan matematika sebagai
ukuran kerumitan (kompleksitas) maka dibahas analisis algoritma dengan menggunakan
notasi O (big O).
Buku Ajar Metode Numerik, didanai oleh Proyek HEDS tahun 2002 2
1.2. Konsep Dasar Algoritma
Algoritma adalah kumpulan instruksi/perintah yang dibuat secara jelas dan
sistematis berdasarkan urutan yang logis (logika) untuk penyelesaian suatu masalah.
French,C.S. (1984) menyatakan sejumlah konsep yang mempunyai relevansi
dengan masalah rancangan program yaitu kemampuan komputer, kesulitan dan ketepatan.
Penerapan dari konsep tersebut biasanya digunakan dalam rancangan algoritma. Dalam
merancang sebuah algoritma, Fletcher (1991) memberikan beberapa cara atau metode yaitu
kumpulan perintah, ekspresi, tabel instruksi, program komputer, kode semu dan flow chart,
sedangkan Knuth (1973) menyarankan algoritma fundamental. Untuk keperluan
matematika dan program komputer metode yang sering digunakan yaitu :
1. Diagram Alir (Flow Chart)
2. Kode Semu (Pseudo Code)
3. Algoritma Fundamental
Knuth (1973) menyatakan 5 komponen utama dalam algoritma yaitu finiteness,
definiteness, input, output dan effectiveness. Sehingga dalam merancang sebuah algoritma
ada 3 (tiga) komponen yang harus ada yaitu:
1. Komponen masukan (input)
Komponen ini biasanya terdiri dari pemilihan variable, jenis variable, tipe variable,
konstanta dan parameter (dalam fungsi).
2. Komponen keluaran (output)
Komponen ini merupakan tujuan dari perancangan algoritma dan program.
Permasalahan yang diselesaikan dalam algoritma dan program harus ditampilkan dalam
komponen keluaran. Karakteristik keluaran yang baik adalah benar (menjawab)
permasalahan dan tampilan yang ramah (Frendly).
3. Komponen proses (processing)
Komponen ini merupakan bagian utama dan terpenting dalam merancang sebuah
algoritma. Dalam bagian ini terdapat logika masalah, logika algoritma (sintaksis dan
semantik), rumusan, metode (rekursi, perbandingan, penggabungan, pengurangan dan
lain-lain).
Buku Ajar Metode Numerik, didanai oleh Proyek HEDS tahun 2002 3
Konsep Logika
Matematika Format Algoritma
FlowChart
Algoritma
Fundamental
Knuth, 1973
Pseudo Code
Gambar 1.1. Struktur Hubungan dan Jenis Algoritma
1.3. Diagram Alir
Algoritma ini menggunakan sejumlah simbol untuk menyatakan kegiatan-kegiatan
secara keseluruhan. Simbol dan artinya dalam diagram alir sebagai berikut:
Proses Input dan
output
Prosedur/
Sub routin Fungsi
Keputusan
Terminal
(start dan end
Looping
Buku Ajar Metode Numerik, didanai oleh Proyek HEDS tahun 2002 4
Hubungan Paralel
Ya Tidak
Garis alir
Gambar 1.2. Simbol dan arti Diagram Alir
1.4. Kode Semu
Dalam merancang sebuah algoritma menggunakan kode semu, komponenkomponen
input, output dan proses harus terdefinisi secara jelas. Disamping itu beberapa
ketentuan dan aturan pendefinisian memang secara baku tidak ditemukan dalam beberapa
buku literatur, namun aturan-aturan yang di ajukan dibawah ini akan membantu
mempermudah perancangan algoritma dan evaluasi serta analisis algoritma.
Aturan-aturan tersebut :
1. Kode semu harus dimulai dengan judul. Aturan ini secara mudah dapat dimengerti
fungsi dan manfaatnya. Judul harus dapat menjelaskan spesifikasi masalah yang
dirancang algoritmanya. Penulisannya dapat dengan huruf kapital semuanya atau tidak.
2. Kode semu harus ditulis dengan nomor yang menunjukkan urutan-urutan langkahlangkah
dalam algoritma.
3. Pendeklarasian variabel, konstanta, parameter, rumus dan pernyataan harus sederhana
Dokumen
Hubungan
Pusat data
Input Manual
Operasi
Manual
Buku Ajar Metode Numerik, didanai oleh Proyek HEDS tahun 2002 5
Contoh. 1.1
Bandingkan kedua algoritma ini. Masalah : Mencari akar-akar persamaan non linear dengan
metode bagi dua.
A. Kode semu yang dirancang tidak menggunakan aturan.
Penyelesaian:
1. Formulasikan sebuah persaman non linier
2. Cari nilai bawah xb yang menyebabkan nilai fungsif(xb) positif atau negatif,
kemudian cari nilai atas xa yang menyebabkan nilai fungsi f(xa) berlawanan (positif
negatif) dengan nilai bawah.
3. Bandingkan nilai f(xb) dengan f(xa)
4. Jika f(xb).f(xa) > 0 maka ulangi langkah 2
5. Jika f(xb).f(xa) < 0 maka bagi dua interval xb dengan xa. Ulangi langkah 3
6. Jika f(xb).f(xa) = 0 maka iterasi berhenti, akar-akar persamaan x diperoleh
B. Kode semu yang dirancang menggunakan aturan
Penyelesaian:
Algoritma Bagi Dua
1. Formulasikan masalah f(x)
2. Cari taksiran bawah (xb) dan taksiran atas (xa)
3. Bandingkan dan evaluasi, jika f(xb).f(xa) > 0 maka ulangi langkah 2
4. Jika f(xb).f(xa) < 0 maka bagi dua interval dengan (xb+xa) / 2, kembali bandingkan
dan evaluasi.
5. Jika f(xb).f(xa) = 0 maka iterasi berhenti, akar-akar persamaan x diperoleh
Buku Ajar Metode Numerik, didanai oleh Proyek HEDS tahun 2002 6
1.5. Algoritma Fundamental
Knuth (1973)menyajikan format algoritma yang dapat digunakan secara bebas
untuk berbagai bahasa pemrograman, artinya dapat dengan mudah diimplementasikan
menggunakan Pascal, C, Fortran, PL atau BASIC. Secara umum notasi dan aturan yang
digunakan sebagai berikut :
1. Nama/judul algoritma harus ditulis dengan huruf kapital
Contoh : Algoritma BAGI DUA
2. Berikan komentar dan penjelasan pendahuluan. Penjelasan secara singkat tentang
algoritma.
Contoh : Algoritma BAGI DUA
Mencari akar persamaan dengan taksiran pertama xb dan xa
3. Langkah-langkah. Algoritma tersusun menurut nomor langkah-langkah diawali dengan
‘[......]’ untuk memberikan keterangan tentang langkah tersebut.
Contoh : 1. [formulasikan f(x)]
4. Komentar (comments). Komentar untuk penjelasan bagi pembaca ditulis dengan tanda
(......)
5. Pernyataan dan struktur Kontrol
Pernyataan adalah perintah yang terdapat didalam algoritm, sedangkan struktur kontrol
untuk mengendalikan pernyataan yang digunakan. Pernyataan dan struktur kontrol
terdiri dari :
a. Perintah pemberian nilai menggunakan ↔, ←
Contoh : A ← B (artinya A = B)
X ← 0 (artinya x bernilai 0)
X↔Y (artinya x dan y saling tukar)
b. Pernyataan IF
Perintah yang digunakan:
• IF kondisi
Then.....
• IF kondisi
Then.....
.......
Buku Ajar Metode Numerik, didanai oleh Proyek HEDS tahun 2002 7
else.....
c. Pernyataan Case
Perintah ini untuk menyeleksi pilihan tertentu. Bentuknya :
Select Case (ekspresi)
Case nilai 1 :
Case nilai 2 :
.
.
.
Case nilai n :
Default :
d. Pernyataan Repeat
Perintah pengulangan digunakan dengan bentuk :
• Repeat for indeks = barisan nilai
• Repeat while ekspresi logika
• Repeat for indeks = barisan nilai while ekspresi logika
e. Pernyataan Goto dan Exitloop
Perintah untuk melompat ke langkah yang telah ditentukan dan keluar dari
pengulangan.
Bentuknya :
Goto step.....
Exitloop
f. Pernyataan Exit
Perintah untuk menghentikan algoritma.
6. Nama-nama variabel harus ditulis dengan huruf besar
7. Input dan output
Data dapat dimasukkan melalui variabel dengan pernyataan READ dengan bentuk :
Read : NAMA VARIABEL
Untuk mencetak pesan-pesan/tulisan (diapit dengan tanda kutip) dan juga variabel
digunakan pernyataan :
Write : tulisan dan atau nama variabel
Buku Ajar Metode Numerik, didanai oleh Proyek HEDS tahun 2002 8
8. Prosedur
Bentuk prosedur digunakan untuk modul algoritma yang berdiri sendiri untuk
menyelesaikan masalah tertentu. Pemakaian prosedur untuk masalah sederhana,
sedangkan algoritma untuk masalah umum. Bentuk yang digunakan :
Procedure nama prosedur
9. Fungsi
Sama dengan prosedur menggunakan bentuk :
Function nama fungsi
Contoh 1.2.
Masalah : Mencari elemen terbesar dari data dengan n bilangan.
Buatlah algoritma dari masalah ini menggunakan
a. Kode Semu
b. Diagram Alir
c. Algoritma Fundamental
Penyelesaian :
a. Kode semu (Pseudo Code)
Algoritma Maksimum
1. Mula-mula masukkan bilangan dalam register xi ke dalam register yang
dinamakan maks.
2. Untuk i = 2,3,....,n, lakukan : Bandingkan bilangan dalam register xi dengan
bilangan dalam register maks. Jika bilangan dalam register xi lebih besar
daripada bilangan dalam register maks, pindahkan bilangan dalam register xi ke
register maks; jika tidak jangan lakukan apa-apa.
3. Terakhir, bilangan dalam register maks adalah elemen terbesar di antara n
bilangan.
Buku Ajar Metode Numerik, didanai oleh Proyek HEDS tahun 2002 9
b. FlowChart (Diagram Alir)
Mulai
x1 = Maks
FOR i = 2 TO n
IF xi > Maks
Maks = xi
NEXT i
Maks
End
tidak
ya
c. Algoritma Fundamental
Algoritma MAKSIMUM
Mencari elemen terbesar di dalam data dengan n bilangan.
1. [Inisialisasi]
Maks x1
2. [Mulai Loop]
I 2
3. [Naikkan Pencacah]
I I + 1
4. [Bandingkan]
IF Maks < xi
THEN Maks xi ELSE GOTO 3
5. [Ulangi Loop]
GOTO 3
6. [Selesai]
Exit
Buku Ajar Metode Numerik, didanai oleh Proyek HEDS tahun 2002 10
1.6. Analisis Algoritma dan Kompleksitas Algoritma
Seorang programer atau sistem analisis paling tidak harus memiliki dasar untuk
menganalisis algoritma. Analisis algoritma sangat membantu di dalam meningkatkan
efisiensi program. Kecanggihan suatu program bukan dilihat dari tampilan program, tetapi
berdasarkan efisiensi algoritma yang terdapat didalam program tersebut.
Pembuatan program komputer tidak terlepas dari algoritma, apalagi program yang
dibuat sangat kompleks. Program dapat dibuat dengan mengabaikan algoritma, tetapi
jangan heran bila seandainya ada orang lain yang membuat program seperti program anda
tersebut memiliki akses yang lebih cepat dan memakai memori yang sangat sedikit.
Analisis algoritma adalah bahasan utama dalam ilmu komputer. Dalam menguji
suatu algoritma, dibutuhkan beberapa kriteria untuk mengukur efisiensi algoritma.
Terdapat dua tipe analisis algoritma, yaitu :
1. Memeriksa kebenaran algoritma
Dapat dilakukan dengan cara perurutan, memeriksa bentuk logika, implementasi
algoritma, pengujian dengan data dan menggunakan cara matematika untuk
membuktikan kebenaran.
2. Penyederhanaan Algoritma
Membagi algoritma menjadi bentuk yang sederhana.
1.7. Notasi O (Big O)
Misalkan 4 program yang mensorting n bilangan dengan fungsi yang menyatakan
sejumlah langkah yang dijumlahkan masing-masing program untuk sorting n bilangan :
f1(n) = n, f2(n) = n2, f3 (n) = 2n, f4(n) = n!
Bila n = 4 maka f1 (n) = 4, f2 (n) = f3 (n) = 16 dan f4 (n) = 24 sedangkan untuk n = 100,
program ketiga akan memerlukan 21000 langkah.
Dalam analisis sebuah algoritma biasanya yang dijadikan ukuran adalah operasi
aljabar seperti penjumlahan, pengurangan, perkalian dan pembagian, proses pengulangan
(looping/Iterasi), proses pengurutan (sorting) dan proses pencarian (searching).
Buku Ajar Metode Numerik, didanai oleh Proyek HEDS tahun 2002 11
Definisi 1.1
Misalkan S sebuah himpunan fungsi riil untuk setiap domain D, dengan D = N, Z atau R.
Misalkan f,g ∈S. Dikatakan f = O(g) jika ada bilangan positif c dan k sehingga
f (x) ≤ c g(x) untuk semua x∈D yang x > k
Dalam analisis algoritma ada 3 bagian yang dapat dianalisis yaitu kecepatan waktu,
kapasitas biaya dan kapasitas ruang. Ketiganya menggunakan notasi O.
Teorema 1.1
Misalkan f(x) = anxn + an-1xn-1 + ........ + a1x + a0 adalah fungsi polinom dan misalkan g(x) =
xn maka f= O(g).
Bukti :
Misalkan 1 1 0 c a a ... a a n n = + + + + − . Misalkan x sebuah bilangan riil yang lebih dari 1,
maka
( )
...
...
...
( ) ...
1 1 0
1 1 0
1 0
1
1
1 0
cx c g x
a a a a x
a x a x a x a x
a x a x a x a
F x a x a x a
n
n
n n
n n n
n
n
n
n
n
n
n
n
n
= =
= + + + +
≤ + + + +
≤ + + + +
= + + +
−
−
−
−
Sehingga f = O(g)
Teorema 1.2.
Misalkan S sebuah himpunan fungsi dengan dominan D yang sama dengan D = n, Z atau R
dan kodomain (0,~). Misalkan f1, f2, g1, g2 ∈ S sehingga f1 = O(g1) dan f2 = O(g2), maka
dengan hubungan O diperoleh :
a). f1 + f2 = O(maks{g1,g2}) dan
b). f1 . f2 = O(g1,g2)
Buku Ajar Metode Numerik, didanai oleh Proyek HEDS tahun 2002 12
Bukti:
a) Karena f1=O(g1) dan f2=O(g2), ada bilangan positif c1, k1, c2, dan k2
sedemikian sehingga jika x ∈ D dan x > k1 maka |f1(x)| < c1 |g1(x)| dan
jika x > k2 maka |f2(x)| < c2|g2(x)|. Misalkan k=maks{k1, k2} dan c = c1
+ c2, maka
|(f1 + f2)(x)| = (f1+f2)(x)
= f1(x) + f2(x)

= c1g1(x) + c2g2(x)
≤ c1 max {g1(x), g2(x)}+c2 max{g1(x),g2(x)}
= (c1+c2) max {g1(x),g2(x)}
= c max{g1(x),g2(x)}
= c |(max{g1,g2})(x)|
maka f1 + f2 = O(max{g1,g2}(x))
b) |(f1f2)(x)| = |f1(x)| |f2(x)|
≤ c1 |g1(x)| c2|g2(x)|
= c1 c2 |g1(x)g2(x)|
= c1 c2 |(g1g2)(x)|
= c |(g1g2)(x)|
sehingga f1f2 = O(g1g2)