Archive for the Category »LOGIKA DAN ALGORITMA «

Pseudocode adalah cara untuk menuliskan sebuah algoritma secara high-level (level tingkat tinggi).

Biasanya Pseudocode dituliskan dengan kombinasi Bahasa Inggris dan notasi matematika. Biasanya sebuah Pseudocode tidak terlalu detail dibandingkan dengan program. Isu-isu detail dalam program yang sifatnya teknis tidak dibahas di dalam Pseudocode.

Komponen-komponen Pseudocode, antara lain :

  1. Variabel.
      Merupakan tempat penyimpanan sebuah nilai.
  2. Perulangan (Loop).
      Teknik for-do
      Teknik repeat-until
      Teknik while-do
  3. Percabangan (branch).
      Teknik if-then
      Teknik select-case
  4. Modul.
      Procedure/Sub
      Function.
      Teknik Rekursif

Contoh Pseudocode, sederhana :

1. Phi ← 3,14

2. Input (r)

3. Luas ← Phi x r x r

4. Output (Luas)

Ket :

* Rumus Luas Lingkaran = Phi x r x r

* r = jari-jari

Untuk menggambarkan sebuah algoritma yang terstruktur dan mudah dipahami oleh orang lain (khususnya programmer yang bertugas mengimplementasikan program), maka dibutuhkan alat bantu yang berbentuk Diagram Alir (Flowchart). Diagram alir ini akan menunjukkan alur di dalam program secara logika. Diagram alir ini selain dibutuhkan sebagai alat komunikasi, juga diperlukan sebagai dokumentasi. Dan sebelum lebih jauh memahami komponen-komponen diagram alir, maka perlu kiranya disampaikan aturan-aturan dalam perancangan diagram alir tersebut, yaitu :

  1. Diagram alir digambarkan dengan orientasi dari atas ke bawah dan dari kiri ke kanan;
  2. Setiap kegiatan/proses dalam diagram alir harus dinyatakan secara eksplisit;
  3. Setiap diagram alir harus dimulai dari satu Start State dan berakhir pada satu atau lebih Terminal Akhir/Terminator/Halt State;
  4. Gunakan Connector dan Off-Page Connector state dengan label yang sama untuk menunjukkan keterhubungan antar path algoritma yang terputus/terpotong, misalnya sebagai akibat pindah/ganti halaman.

Selain dengan Flowchart, untuk menuliskan sebuah algoritma dapat pula digunakan Pseudo-Code, yaitu suatu teknik penulisan algoritma dengan menggunakan sebanyak mungkin komponen-komponen dari salah satu bahasa tingkat tinggi (suatu bahasa pemrograman yang masih memerlukan unit kompilator untuk mengeksekusi program agar dapat berjalan). Dalam arti penulisan algoritma dengan Pseudo-Code ini hampir menyerupai sebuah program, tetapi tanpa menyertakan atribut-atribut program (seperti tipe data, dll), hanya menuliskan proses intinya saja.

Berikut ini adalah simbol-simbol state yang digunakan untuk menggambarkan algoritma dalam bentuk diagram alir. Sedangkan keterangan yang terdapat di bawah masing-masing simbol adalah kegunaan dari simbol-simbol yang bersangkutan.

Contoh-contoh flowchart :

Berikut ini adalah contoh-contoh pembuatan flowchart untuk menyelesaikan suatu masalah :

  1. Menghitung Luas Lingkaran

  • Prinsip dasar dari metoda ini adalah membagi n input menjadi k subset input yang berbeda (1<k≤n). Dari k subset input yang bebeda akan terdapat k subproblem . Setiap subproblem mempunyai solusi masing-masing, sehingga akan diperoleh solusi yang optimal.
  • Metoda DandC menggunakan teknik rekursif.
  • DandC digunakan untuk menyelesaikan persoalan searching dan sorting.

Algoritma DandC secara umum :

procedure DandC(p,q)

global n, A(1:N); integer m,p,q

if SMALL(p,q) then G(p,q)

else

m←DIVIDE (p,q)

COMBINE(DandC(p,m), DandC(m+1,q))

endif

end DandC

Keterangan :

  • Small(p,q) adalah fungsi bernilai boole yang menentukan apakah input q-p+1 berukuran cukup kecil sedemikian sehingga solusinya dapat dihitung tanpa pemecahan. Jika demikian halnya maka fungsi G(p,q) yang akan diproses atau dieksekusi. Pada keadaan lain, fungsi divide (p,q) yang diproses.
  • Fungsi divide(p,q) menghasilkan bilangan bulat yang menguraikan input menjadi dua bagian. Misal m= divide(p,q) maka input dipecah menjadi A(p:m) dan A(m+1:q).
  • Fungsi combine merupakan fungsi yang menentukan solusi umum atau solusi yang diharapkan dari persoalan semula A(p:q)

SEARCHING

  • Ø Menentukan bilangan maksimum dan minimum dengan menggunakan teknik iteratif.

Algoritma :

procedure straitmaxmin(A,n,max,min)

integer i,n

max←min←A(1)

for i←2 to n do

if A(i) > max

then max←A(i)

else

if A(i)<min

then min←A(i)

endif

repeat

endstaritmaxmin

  1. Keadaan Terbaik (Best Case)

Keadaan ini akan tercapai jika elemen-elemen pada array disusun secara menaik (increasing).

Contoh: array A berisi 4 bilangan yang disusun secara menaik

2 4 5 10

A =

Jika dijalankan dengan algortima straitmaxmin maka akan diperoleh:

max←min←A(1)=2

i=2

A(2) > max  ?

4 > 2  ? ya → max = 4 ……………1 operasi perbandingan

i=3

A(3) > max  ?

5 > 4  ? ya → max = 5 ……………1 operasi perbandingan

i=4

A(4) > max  ?

10 > 5  ? ya → max = 10 ……….1 operasi perbandingan

Sehingga akan diperoleh min=2, max=10

Penyelesaian tersebut diperoleh dengan membutuhkan 3 operasi perbandingan atau secara umum (n-1)satuan opersai, n banyaknya elemen dalam array.

  1. Keadaan Terburuk (Worst Case)

Keadaan ini akan tercapai jika elemen-elemen pada array disusun secara menurun (decreasing).

80 21 6 -10

A =

Jika dijalankan dengan algortima straitmaxmin maka akan diperoleh:

max←min←A(1)=80

i=2

A(2) > max  ?

21 > 80  ? tidak

A(2) < max  ?

21 < 80  ? ya → min = 21 ……………2 operasi perbandingan

i=3

A(3) > max  ?

6 > 80  ? tidak

A(3) < max  ?

6 < 80  ? ya → min = 6 ……………2 operasi perbandingan

i=4

A(4) > max  ?

-10 > 80  ? tidak

A(4) < max  ?

21-10 < 80 ? ya → min = -10  …………2 operasi perbandingan

Sehingga akan diperoleh min = -10, max = 80

Penyelesaian tersebut diperoleh dengan membutuhkan 6 operasi perbandingan atau secara umum 2(n-1)satuan opersai, n banyaknya elemen dalam array.

  1. Keadaan Rata-rata (Average Case)

Keadaan ini akan tercapai jika elemen-elemen pada array disusun secara acak. Akan diperoleh waktu sebesar (3n/2-1) satuan operasi.

  • Ø Menentukan bilangan maksimum dan minimum dengan menggunakakan metoda DandC (teknik rekursif)

Algortima :

procedure maxmin(I,j,fmax,fmin)

integer i,j

global n,A(1:n)

case

: i=j     ;   fmax←fmin←A(i)

: i=j-1 ;   if A(i) < A(j) then fmax←A(j); fmin←A(i)

else fmax←A(i); fmin←A(j)

endif

: else       mid←½(i+j)/2½

call maxmin(i,mid,gmax,gmin)

call maxmin(mid+1,j,hmax,hmin)

fmax←max(gmax,hmax)

fmin←min(gmin,hmin)

endcase

endmaxmin

Contoh : dalam suatu array terdapat 9 bilangan yaitu

22 13 -5 -8 15 60 17 31 47

A =

Penyelesaian disimulasikan dalam bentuk pohon (tree).

Nilai i=1, j=n=9

6, 9
1, 5
-5, -5
3, 3
22, 13
1, 2

Bilangan maksimum = 60

Bilangan minimum = -8

Analisis algoritma :

T(½n/2½) + T(T(½n/2½) + 2 ; untuk n>2

T(n) =      1                                                ; untuk  n= 2

0                                                 ; untuk n =1

Definisi Logika :

Logika berasal dari kata Yunani kuno λόγος (logos) yang berarti hasil pertimbangan akal pikiran yang diutarakan lewat kata dan dinyatakan dalam bahasa. Logika adalah salah satu cabang filsafat.

Sebagai ilmu, logika disebut dengan logike episteme (Latin: logica scientia) atau ilmu logika (ilmu pengetahuan) yang mempelajari kecakapan untuk berpikir secara lurus, tepat, dan teratur[1].

Ilmu disini mengacu pada kemampuan rasional untuk mengetahui dan kecakapan mengacu pada kesanggupan akal budi untuk mewujudkan pengetahuan ke dalam tindakan. Kata logis yang dipergunakan tersebut bisa juga diartikan dengan masuk akal. ( sumber : http://id.wikipedia.org/wiki/Logika)

Definisi Algoritma :

Ahli sejarah matematika menemukan kata algoritma berasal dari nama penulis buku Arab terkenal, yaitu Abu Abdullah Muhammad Ibnu Musa Al-Khuwarizmiseorang ahli matematika, astrologi, astronomi dan geografi.

Algoritma adalah sekumpulan langkah (tahapan) logis untuk menyelesaikan suatu pekerjaan (permasalahan).

Merupakan kumpulan perintah untuk menyelesaikan suatu masalah.

Perintah-perintah ini dapat diterjemahkan secara bertahap dari awal hingga akhir. Masalah tersebut dapat berupa apa saja, dengan catatan untuk setiap masalah, ada kriteria kondisi awal yang harus dipenuhi sebelum menjalankan algoritma. Algoritma akan dapat selalu berakhir untuk semua kondisi awal yang memenuhi kriteria, dalam hal ini berbeda dengan heuristik. Algoritma sering mempunyai langkah pengulangan (iterasi) atau memerlukan keputusan (logika Boolean dan perbandingan) sampai tugasnya selesai.

Desain dan analisis algoritma adalah suatu cabang khusus dalam ilmu komputer yang mempelajari karakteristik dan performa dari suatu algoritma dalam menyelesaikan masalah, terlepas dari implementasi algoritma tersebut. Dalam cabang disiplin ini algoritma dipelajari secara abstrak, terlepas dari sistem komputer atau bahasa pemrograman yang digunakan. Algoritma yang berbeda dapat diterapkan pada suatu masalah dengan kriteria yang sama

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.

Alat Bantu untuk menuliskan Logika dan Algoritma, salah satunya adalah FLOWCHART.

Pengertian FLOWCHART:

gambaran dalam bentuk diagram alir dari algoritma dalam suatu program atau prosedur sistem secara logika, yang menyatakan arah alur program dalam menyelesaikan suatu masalah.

SIMBOL Flowchart

Pedoman-pedoman dalam Membuat Flowchart:

  1. Bagan alir sebaiknya digambar dari atas ke bawah dan mulai dari bagian kiri dari suatu halaman.
  2. Kegiatan di dalam bagan alir harus ditunjukkan dengan jelas.
  3. Harus ditunjukkan dari mana kegiatan akan dimulai dan dimana akan berakhirnya (diawali dari satu titik START dan diakhiri dengan END).
  4. Masing-masing kegiatan di dalam bagan alir sebaiknya digunakan suatu kata yang mewakili suatu pekerjaan, misalnya:

-          “Persiapkan” dokumen

-          “Hitung” gaji

  1. Masing-masing kegiatan di dalam bagan alir harus di dalam urutan yang semestinya.
  2. Kegiatan yang terpotong dan akan disambung di tempat lain harus ditunjukkan dengan jelas menggunakan simbol penghubung.
  3. Gunakanlah simbol-simbol bagan alir yang standar.

Secara garis besar, Ada 3 bagian utama dalam flowchart :

Contoh:

Buat algoritma dan Flowchart untuk Menghitung Luas Persegi Panjang:

Pekerjaan:

Rumus:

LuasPersegiPanjang = Panjang x Lebar

Algoritma:

  1. Tentukan nama variabel yang akan menampung data Panjang, lebar dan luas persegi panjang.
  2. Masukkan (inputkan) data Panjang dan Lebar pada variabel yang sudah ditentukan.
  3. Hitung Luas persegi panjang.
  4. Tampilkan (outputkan) Luas persegi panjang.

Flowchart:

Latihan:

Buat algoritma dan Flowchart untuk Menghitung:

  1. Luas Segitiga
  2. Luas Lingkaran

IMPLEMENTASI DALAM PROGRAM

(Sebagai contoh: Bahasa Pemrograman Pascal)

Pengertian PROGRAM:

Kumpulan instruksi (statements) yang disusun secara logis untuk memecahkan suatu masalah. Instruksi-instruksi yang digunakan disesuaikan dengan jenis bahasa pemrograman yang digunakan (reserved word yang disediakan).

Stuktur Penulisan Pascal:

Program Nama_Program;

uses

. . .  {Unit-unit yang dipakai} ;

label

. . .  {label-label yang dipakai } ;

const

. . .  {pengumuman tetapan-tetapan} ;

type

. . .  { pengumuman tipe-tipe data };

var

. . .  { pengumuman peubah-peubah };

procedure Nama_Prosedur;

begin

. . .

end;

Function Nama_Fungsi;

begin

. . .

end;

{  Program utama   }

begin

. . .

end.

Perintah Input :

Perintah Pascal yang digunakan untuk memasukkan/menginputkan data.

Bentuk perintah:

Read dan Readln

Struktur penulisan:

Read(nama variabel);

Readln(nama Variabel)

Perintah Output:

Perintah Pascal yang digunakan untuk menampilkan/mengoutputkan data.

Bentuk perintah:

Write : setelah menampilkan data atau teks, kursor berada tepat disamping kanan data yang ditampilkan.

Write : setelah menampilkan data atau teks, kursor berada pada baris berikutnya.

Struktur penulisan:

write(nama variabel);

write(‘teks’);

writeln(nama Variabel);

writeln(‘teks’);

Contoh:

Buat program sederhana untuk Menghitung Luas Persegi Panjang:

Program LuasPersegiPanjang;

Var

Luas, Panjang, Lebar : integer;

Begin

Readln(panjang);

Readln(Lebar);Luas:= Panjang*Lebar;

Writeln(‘Luas Persegi  Panjang adalah:’,Luas);

Readln;

End.

Tampilan pada lembar kerja Pascal:

Menjalankan program dengan perintah:

Ctrl+F9(tekan tombol Ctrl dan F9 bersama-sama).

Apabila Panjang diisi 7 dan lebar diisi 8 maka hasil perintah diatas tampil sbb:

Latihan:

Buat program sederhana untuk Menghitung:

  1. Luas Segitiga
  2. Luas Lingkaran

STRUKTUR KENDALI  “IF’

Struktur kendali aliran adalah suatu bentuk/struktur yang memiliki peranan khusus  untuk mengatur aliran urutan pengerjaan operasi atau beberapa operasi tertentu.

Salah satu contoh pernyataan kendali yaitu pernyataan if .

Pernyataan if (if statement) akan memeriksa suatu persyaratan dan menentukan  apakah syarat tersebut benar atau salah, kemudian melakukan pekerjaan sesuai dengan nilai pernyataan tersebut.

Struktur Penulisan:

Berikut adalah bentuk-bentuk dari pernyataan if yang sering digunakan :

  1. If dengan satu pernyataan (statement)

If (kondisi) then pernyataan ;

  1. If dengan dua atau lebih pernyataan (statement)

If (kondisi) then

begin

pernyataan1 ;

pernyataan2 ;

…..

end;

  1. If dan else

If (kondisi) then

begin

pernyataan1 ;

pernyataan2 ;

…..

end

else

begin

pernyataan1 ;

pernyataan2 ;

…..

end;

Dari bentuk bentuk pernyataan if di atas yang harus diperhatikan adalah untuk pernyataan if dan else, pernyataan-pernyataan setelah then tanpa menggunakan “;”. Dengan kata lain jika pernyataan setelah then hanya terdiri dari satu pernyataan saja makan pernyataan tersebut tanpa menggunakan “;”, namun jika pernyataan setelah then terdiri dari lebih dari satu pernyataan makan setelah end tanpa menggunakan “;”.

Latihan:

Buat flowchart dan program sederhana untuk menampilkan bilangan terbesar.

TEKNIK BACKTRACKING

  • Pertama kali diperkenalkan oleh DH Lehmer (1950), dirumuskan dalam suatu algortima oleh RJ Walker (1960), aplikasinya dikembangkan oleh Golomb dan Baumert.
  • Dasar dari teknik Backtracking adalah searching.
  • Backtracking merupakan salah satu algotritma yang didasarkan pada pencarian ruang solusi.
  • Pencarian ruang solusi dalam algoritma backtracking menggunakan  teknik pencarian Depth First Search (DFS).
  • Masalah-masalah yang dapat diselesaikan dengan menggunakan algoritma Backtracking adalah :
    • Ø The 8-Queen Problem
    • Ø The 4-Queen Problem
    • Ø Sum of Subsets
    • Ø Graph Coloring
    • Ø Hamilton Cycles
    • Ø Knapsack Problem
    • Ø The Travelling Salesman Problem

Penyelesaian Sum of Subsets dengan Menggunakan Algoritma Backtracking

Masalah utama dari SUM of SUBSETS adalah jika terdapat n bilangan real dan ingin dihitung semua kombinasi yang mungkin dari himpunan bilangan tersebut. Kombinasi yang didinginkan adalahkombinasi yang jumlah seluruh elemen-elemennya sama dengan M (tertentu).

Algoritma Sum of Subset

procedure sumofsub(s,k,r)

global integer M,n

global real w(1:n)

real r,s

integer k,j

x(k) = 1

if s + w(k) = M then

print(x(j),j ß 1 to k)

else

if s + w(k) + w(k+1) ≤ M then

call sumofsub(s+w(k), k+1, r-w(k))

endif

endif

if s + r-w(k) ≥ M and s + w(k+1) ≤ M then

x(k) ß 0

call sumofsub(s, k+1, r-w(k))

endif

end sumofsub

Permasalahan :

Suatu himpunan terdiri dari 6 bilangan yaitu {5, 10, 12, 13, 15, 18} yang disusun secara tidak turun. Akan ditentukan himpunan-himpunan bagiannya yang jumlah seluruh elemennya adalah 30

Penyelesaian :

n=6

W(1:6) = {5,10,12,13,15,18}

M = 30

Diasumsikan bahwa w(1) ≤ M dan ∑ w(i) ≥ M

Dalam hal ini w(1)= 5 ≤ 30 dan ∑ w(i) = 73 ≥ 30,

k-1
j=1

dan nilai s diperoleh dari    ∑  w(j)x(j)

n
j=k

nilai r diperoleh dari ∑w(j)