Resume Algoritma & Struktur Data

PENGANTAR ALGORITMA

A. PENGERTIAN ALGORITMA Algoritma adalah cara kerja komputasi yang baik, dimana memiliki nilai

input dan output. Algoritma digunakan untuk menyelesaikan masalah

komputasional yang mana hasil penyelesainnya ini dimengerti dan

sesuai dengan masalah yang disediakan. Gambaran algoritma dapat

dilihat dari ilustrasi dibawah ini :

B. Desain dan Analisis Algoritma

- Pseucodocode Kode yang digunakan dalam menerapkan suatu algoritma yang bisa

dijalankan oleh berbagai bahasa pemograman.

- Kompleksitas algoritma

Untuk mengetahui hal-hal yang dibutuhkan suatu algoritma, seperti

waktu komputasi dan kapasitas memory.

- Strategi algoritma

- Struktur data

Menyimpan data dan mengatur data untuk dimodifikasi.

- Masalah NP-lenkap

Hal ini akan muncul jika masalah yang ada tidak memiliki solusi

yang efisien

input output

masalah

Algoritma

C. Contoh Masalah Komputasional

Masalah pencarian data (searching problem) Kita akan menginput barisan n yang bilangan asli di dalam larik A,

dan sebuah bilangan yang dicari (key). Dan hasilnya key berada

dalam larik A, tetapi jika key tidak ditemukan dalam larik A makan

akan ditambahkan pada barisan terakhir sebagai unsur terakhir.

Algoritmanya :

1. Mengecek satu persatu dari setiap unsur yang terdapat dalam

larik A, apakah ada yang mirip dengan key.

2. Jika terdapat unsur yang mirip dengan key, maka pencarian

berhenti. Tetapi jika tidak ditemukan, maka key ditambahkan

sebagai unsur terakhir dalam larik A.

3. Algoritma berhenti dan kembalikan nilai indeksnya.

Pada algoritma ini, dibutuhkan perulangan (looping) dan

penyeleksian kondisi (selection condition).

Pseudocode algoritma

Linear-Search (A, key)

1. indeks 1 ;

2. ada False;

3. Mengecek key dalam A[1..length[A]]

4. While indeks length [A] and ada = False

5. If A[indeks] = key;

6. Then ada = True;

7. Indeks indeks + 1;

8. If ada = False

9. Then indeks length[A]+1;

10. Return indeks

Contohnya :

27 36 15 2 31

Key = 7

Solusinya :

1. Indeks = 1;

2. Ada False;

3. Mengecek key dalam A[1..length[A]]

4. While indeks length [5] and ada = false

5. If A [1] = 7

27 = 7

Indeks+1 = 1+1=2

If A [2] = 7

36 = 7

Indeks+1 = 2+1=3

If A [3] = 7

15 = 7

Indeks+1 = 3+1=4

If A [4] = 7

2 = 7

Indeks+1 = 4+1=5

If A [5] = 7

31 = 7

Then indeks length[[5]+1]

If A [6] = 7

7= 7

Return indeks

Proses diatas akan mengeluarkan output seperti ini :

27 36 15 2 31 7

Jika key yang ditentukan sama dengan salah satu unsur dalam larik A, maka proses hanya akan sampai pada langkah 5 dan kembali padproses awal.

A =

Salah, maka akan

dilanjutkan ke langkah berikutnya

Masih salah, lanjut!




Karena unsur yang disediakan sudah

habis sedangkan key belelum

ditemukan makan length (kotaknya)

ditambahkan. Seperti langkah 9. Key dijadikan unsur

terakhir..

Masalah Pengurutan Data (Sorting Problem)

Kita akan menginput barisan n bilangan (a1, a2,..,an), dan outputnya

adalah barisan bilangan yang sudah diurutkan (a1, a2,..,an), dimana

a1a2.an.

Algoritmanya:

1. Menscanning semua kartu.

2. Memilih satu kartu sebagai patokan untuk dijadikan perbandingan

dengan kartu lain.

3. Menukar kartu yang ter-scanning jika ternyata lebih kecil daripada

kartu yang dijadikan patokan tadi.

Pseudo codenya:

Insertion-Sort(A)

0 perulangan untuk patokan

1 for j 2 to length[A]

2 key A[j]

3 Sisip A[j] kedalam barisan terurut A[1.. j 1]

4 i j 1

5 while (i > 0 A[i] > key)

6 A[i + 1] A[i]

7 i i 1

8 A[i + 1] key

Contohnya : Urutkan data tersebut dari terkecil ke terbesar:

27 36 15 2

Solusinya : o For j = 2 , key = A[2] = 36 , i = j-1 = 1

While (1 > 0 27 > 36 ) Karena, salah satu persyaratan salah maka lanjut j = 3. Urutan sekarang : (masih seperti awal)

27 36 15 2

I > 0 , berfungsi untuk menghetikan

proses jika unsur telah habis

diseleksi.

A[i] > key, berfungsi untuk

membandingkan key dengan angka

sebelumnya.

(i > 0 A[i] > key) T F

o For j = 3, key = A[3] = 15 , i = j-1 = 2

While (1 > 0 36 > 15 ) A [i+1] = 36 urutan sekarang :

27 36 36 2

i = i-1= 2-1 = 1

While (1 > 0 27 > 15) A [i+1] = 27 urutan sekarang :

27 27 36 2

i = i-1= 1-1 = 0

While (0 > 0 . > 15) A[i] = key = 15 Karena, salah satu persyaratan salah maka lanjut j = 4. Urutan sekarang : (masih seperti awal)

15 27 36 2

o For j = 4, key = A[4] = 2 , i = 4-1 = 3

While (3 > 0 36 > 2 ) A [i+1] = 36 urutan sekarang :

15 27 36 36

i = i-1= 3-1 = 2

While (2 > 0 27 > 2) A [i+1] = 27

T

(i > 0 A[i] > key) T

36 bertukar posisi 15 pada A[3]

T T


15 sebetulnya sudah berada

A[2], tapi nilainya < 36.



F

T

(i > 0 A[i] > key) T


T T




n

j jt

2

urutan sekarang :

15 27 27 36

i = i-1= 2-1 = 1

While (1 > 0 15 > 2) A [i+1] = 15 urutan sekarang :

15 15 27 36

i = i-1= 1-1 = 0

While (0 > 0 . > 2) A[i] = key = 2 Urutan akhir : ( karena j hanya sampai 5)

2 15 27 36

Analisis Algorima : Insertion-Sort(A)

1 for j 2 to length[A]

2 key A[j]

3 Sisip A[j] kedalam barisan terurut A[1.. j 1]

4 i j 1

5 while (i > 0 A[i] > key)

6 A[i + 1] A[i]

7 i i 1

8 A[i + 1] key

Total waktu dari algoritma ini (running time) :



F

T T




cost times

c1 n

c2 n 1

0 n 1 c

4 n 1

c5

c

6

c

7

c

8 n 1

n

j jt

2)1(

n

j jt

2)1(

Urutan data yang diinput juga mempengaruhi waktu komputasi. Pada urutan yang diinpu terdapat dua kasus yaitu :

- Kasus terbaik (best case) yakni dimana data yang diiput sudah berurut, tj=1. Laju komputasi dalam fungsi linear.

- Kasus terburuk (worst case) akni dimana data yang diiput terurut terbalik, tj=j. laju komputasi dalam fungsi kuadratik.

)1()1()1()1()1()( 82

7

2

6

2

5421

nctctctcncncncnTn

j

j

n

j

j

n

j

j

)()(1)( 1321322

1 kknkkknkknTn

j

)()(2

)( 13212121

32

2

1 kknkknk

knkjknTn

j

PERANCANGAN ALGORITMA DAN STRUKTUR DATA

Masalah pencarian data (searching problem)

Kita menginput barisan n bilangan asli (a1, a2,..,an) dalam larik A dan akan terdapat sebuah key yang akan dicari. Maka outputnya adalah lokasi key dalam larik A atau jika tidak ditemukan maka akan ditambahkan sebagai unsur terakhir dalam larik A.

Pencarian Linier Linear-Search(A, key)

1 ada False

2 for i 1 to length[A]

3 if A[i] = key then

4 posisi i

5 ada True

6 if not(ada) then

7 posisi length[A] + 1

8 A[posisi] data

Jika unsur dalam larik A semuanya sama dengan key, maka hal ini akan menjadi kasus terburuknya.

Times

1

n + 1

n

1

s

s

n

i it

1

n

i it

1

)32(22)(1

stnnTn

i

i

34)32(22)(1

nstnnTn

i

i

Sebaliknya, akan terjadi kasus terbaik jika tidak ada sama seklai unsur dalam larik A sama dengan key.

Pencarian Biseksi Pencarian ini merupakan ide ilmiah dalam menyelesaikan masalah ini,

yaitu dengan cara membagi dua data. Sehingga pencarian dua kali lebih cepat. Kasus terburuk dan kasus terbaik dari cara ini akan mengalami pengurangan n, sehinggan waktu komputasionalis kasus terburuknya akan menjadi 7/2n+3 dan waktu komputasionalis kasus terbaiknya menjadi 3/2n+5.

Binary Search Tree (BST) Sebuah pohon yang digunakan dalam prosedur penyimpana dalam

berbagai bentuk sehingga operasi algoritma menjadi lebih optimal. Susunan data dalam BST itu adalah bagian kiri pohon lebih kecil daripada rootnya sedangkan bagian kanan pohon lebih besar dari rootnya.

simpul kiri < root < simpul kanan

Contohnya:

52)32(22)(1

nstnnTn

i

i

N = jumlah data , k = jumlah langkah

N = 2k-1 = 24-1 = 16-1 = 15

k = log2 (N+1) = 0,3(15+1) = 0,3(16) = 4

Bentuk penyimpanannya :

31

26 41

11 28 36

50

52

49

48

34

32

27

13

5

1 data

3 data

7 data

15 data

1 langkah

2 langkah

3 langkah

4 langkah

1

2 3

4 5 6

7

15

14

13

12

11

10

9

8

Merge Sort Merge sort adalah metode mengurutkan data dengan menggunkan

divide and conquer, yaitu dengan cara memecahkan masalah kemudian

menyelesaikannya dan menggabungkannya kembali.

Divide and conquer memiliki tiga langkah yaitu :

- Divide

Membagi-bagi data menjadi beberapa bagian.

- Conquer

Menyelesaikan masalah data yang telah dibagi-bagi.

- Combine

Menggabungkan kembali data yag telah diselesaikan.

Contoh :

Urutkan data tersebut dari terkecil ke terbesar

21 5 10 8 25 16

Solusi :

Data ke-

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Data kiri

2 4 6 8 10 12 14 Tidak memiliki data kiri (data paling bawah)

Data kanan

3 5 7 9 11 13 15 Tidak memiliki data kanan (data paling bawah)

Nilai 31 26 41 11 28 36 50 5 13 27 32 34 48 29 50

Kotak dan panah warna kuning menunjukkan terjadinya prose divide,

sedangkan kotak dan panah warna biru menunjukka terjadinya proses

conquer dan combine.

21 5 10

8 25 16

5 10

25 16

21 8 5 10 16

6

25

21 5 10

16 25

8

5 10 21

8 16 25

21 5 10 8 25 16

5 8 10 16 21 25

KOMPLEKSITAS ALGORITMA Kompleksitas algoritma adalah perubahan data yang diiput terhadap hasilnya(output) yakni menghitung waktu/ruang yang dibutuhkan suatu

algoritma dalam menyelesaikan satu masalah (running time). Kompleksitas

algoritma bisa dipengaruhi oleh kondisi data yang diinput, seperti urutan data

yang tidak terurut atau terurut terbalik.

Batas Atas (Upper Bound)

O(g(n)) = {f(n) : terdapat konstanta c dan n0

sedemikian sehingga 0 f(n) cg(n), n n0}

O(g(n)) (dibaca : big oh g(n)) menyatakan batas atas kompleksitas algoritma.

Cocok digunakan untuk kondisi terburuk.

Batas Bawah (Lower Bound)

n0

f(n) = O(g(n))

cg(n)

n0

f(n) = (g(n))

cg(n)

n

(g(n)) = {f(n) : terdapat konstanta c dan n0

sedemikian sehingga 0 cg(n) f(n), n n0}

(g(n)) (dibaca : big omega g(n)) menyatakan batas bawah kompleksitas

suatu algoritma. Cocok digunakan untuk kondisi terbaik.

Batas Ketat (Tight Bound)

(g(n)) = {f(n) : terdapat konstanta c1, c2, dan n0 sedemikian sehingga 0

c1g(n) f(n) c2g(n) , n n0}

(g(n)) (dibaca : big theta g(n)) menyatakan batas ketat suatu kompleksitas

algoritma. Cocok digunakan untuk kasus rata-rata.

Diantara ketiga batas diatas, yang paling efisien digunakan adalah batas atas

(upper bound), karena dengan menentukan batas atas suatu algoritma maka kita

tidak perlu khawatir akan adanya suatu kemungkinan terjadi kebutuhan

ruang/waktu yang besar.

n0

f(n) = (g(n))

c1g(n)

n

c2g(n)

Resume Algoritma & Struktur Data

Documents