RESUME Mata Kuliah Algoritma Dan Struktur Data

Penulis Resume

Algoritma adalah prosedur atau alat bantu yang harus logis. Sifatnya step by step.

 ·         Pseudocode : Code untuk memudahkan pemahaman algoritma yang dapat di transformasikan kedalam berbagai bahasa pemrograman.

 ·         Kompleksitas algoritma : analisis kebutuhan dari algoritma khususnya waktu komputasi dan kapasitas memory

 ·         Strategi algoritma : perancangan kadang membutuhkan strategi.

*Dalam kuliah kedepannya akan di bahas tentang Greedy Algorithm, Devide-And-Conquer Dynamic Programing dan strategi-strategi algoritma metaheuristik untuk masalah optimis.

·         Struktur data : menyimpan dan mengorganisasi data untuk kepentingan akses dan modifikasi.

·         Masalah NP-Lengkap : tidak ada solusi efisien.

*) MASALAH PENCARIAN DATA

Input :  Barisan n bilangan Asli (a1,a2,…,an) dalam larik A dan sebuah bilangan key yang ingin di cari.

Output : lokasi key dalam A. Jika key tidak di temukan maka tambahkan key sebagai unsur terakhir.

            Contoh :

Input : Barisan bilangan A = {31,41,59,26,41,58} key =26

Output : indeks dari posisi key. Untuk kasus ini key=26

Algoritma pencarian mengembalikan nilai(unsur) dari indeks posisi key adalah 4

*) ALGORITMA LINEAR SEARCHING (NAÏVE)

a.      Telusuri seluruh indeks A untuk membandingkan apakah unsure dalam indeks yang di telusuri sama dengan key

b.      Jika key= unsur dalam indeks, algorima berhenti. Jika key tidak di temukan maka indeks terakhir dari A, tambahkan key sebagai unsure terkahir dari indeks terkahir

c.       Algoritma berhenti dan kembalikan nilai indeks dari A

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 [indeks] = key

6.                      Then ada=true;

7.                  Indeks ← indeks+1;

8.      If ada=False

9.         Then indeks ← length[A] + 1;

10.  Return indeks

*catatan : implementasi lain dari ide algoritma kedalam pseudo-code boleh jadi menghasilkan jumlah baris yang lebih sedikit, namun secara analisis, fungsi laju Runtimr algoritma terhadap jumlah data akan tetap sama.

*ada di atas menunjukkan pemberitahuan bahwasanya nilai key sudah ditemukan dalam A atau belum.

A.      LOOP INVARIANT AND CORRECTNESS

Masalah pencarian data

Input : Barisan n bilangan Asli (a1,a2,…,an)

Output : permutasi barisan bilangan sedemikian sehingga terurut kembali kedalam barisan bilangan (a1,a2,…,an)

B.      ALGORITMA INSENTION-SORT

Insention sort (A)

0.      Perulangan untuk patokan

1.      For J ← 2 to length [A]

2.        Key ← 2 [j]

3.           Sisipkan 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

*while di lakukan maksimal sebanyak j ( j=jumlah deret) untuk mengontrol perbandingannya masih ada atau tidak.

Contoh :

27

36

15

2

 Key = 36

Jawab :

1.      Untuk j = 2, key = A[2] = 36, i = j – 1 = 1

2.      While ( i > 0 Λ A [i] > key ) …………………… (true) Λ (false)

A[2] = 36

3.      Untuk j = 3, key = 15, i = 2

4.      While (i > 0 Λ A [i] > key )………………………. (true)Λ(true)

Sehingga, A[i+1] = 36

27

36

36

2

5.      While (i > 0 Λ A [i] > key )………………………. (true)Λ(true)

Sehingga A[i+1] = 27

27

27

36

2

6.      While (i > 0 Λ A [i] > key )………………………. (false)Λ(true)

Sehingga, A[i+1] = 15

15

27

36

2

Dst (sampai j = 4)

*) PERANCANGAN ALGORITMA DAN STRUKTUR DATA

Masalah pencarian data:

Input :  Barisan n bilangan Asli (a1,a2,…,an) dalam larik A dan sebuah bilangan key yang ingin di cari.

Output : lokasi key dalam A. Jika key tidak di temukan maka tambahkan key sebagai unsur terakhir.

Pencarian Linear

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

T(n) = 2n + 2  + (2s + 3)

Dimana :

ti = antara 0 – 1, nilainya 0 jikatidak tereksekusi

S = 0 dan 1, dimana jika ditemukan maka tidak di eksekusi sehingga s=0. Namun jika tidak di temukan maka lanjut di eksekusi sehingga s=1.

Contoh :

A = (31, 41, 59, 26, 41, 58), key = 26

*kasus terburuk

            Semua unsur dalam larik A sama dengan key. Dalam hal ini   = n dan S = 0

*kasus terbaik

            Tidak terdapat satupun unsur dalam larik A sama dengan key. Dalam hal ini  = 0 dan S = 1.

            T(n) = 2n + 2  + (2s + 3) = 2n + 5

*) IMPROVISASI ALGORITMA

1.      Ada ← false

2.      For i ← 1 to [length[A]/2]

3.         If A[i] = key then

4.             Posisi ← i

5.             Ada ← true

6.        If A[n – i + 1] = key then

7.            Posisi ← n – i + 1

8.            Ada ← true

9.      If not(ada) then

10.       Posisi ← length[A] + 1

11.       A[posisi] ← data

T(n) = 3/2n + 2  + 2  + (2s + 3)

Dimana : secara lebih singkat, di ambil dari ujung kiri dan ujung kanan untuk di bagi 2 sehingga nanti akan bertemu di tengah.

*kasus terburuk

            Semua unsure dalam larik A sama dengan key. Dalam hal ini  = n/2.

*kasus terbaik

            ???

Ide lain :

*ada aide lain yang membuat waktu komputasi pencarian data menjadi lebih cepat

*pengembangan alamiah : pencarian di pecah beberapa bagian.

1.      Struktur data : adalah prosedur penyimpanan data dalam bentuk tertentu sedemikian sehingga operasi dasar pada algoritma menjadi lebih efisien atau optimal.

2.      Binary Search Tree (BST) : struktur data yang memenuhi sifat berikut secara rekrusif :

Simpul.kiri < root < Simpul.kanan

key = 38, berapa banyak perbandingannya??

Jawab :

Melangkah awal dari 31 (karena 31 < 38, maka kita melangkah ke kanan)

Dari langkah pertama kita dapatkan 41 (karena 41 > 38, maka kita melangkah ke kiri untuk mendapatkan nilai yg lebih kecil lagi)

Sehigga di temukan key = 38, dengan banyak perbandingan yaitu 3x

          N = 2^k – 1

          2^k = N + 1

          k = log2 (N + 1)

Namun, data tidak mungkin di simpan di dalam computer dengan bentuk pohon seperti di atas. Maka di simpan dalam bentuk sebagai berikut :

A	1	2	3	4	5	6	7	8	9
Kiri	2	4	6
Kanan	3	5	7
Nilai data	31	26		41	17	28	38	59

Catatan :

Dari 31, data selanjutnya adalah 26 yang berada di sebelah kiri dari data 31, maka kolom kiri di isi dengan n (data ke- ) adalah 2 karena dalam urutan awal penulisan data, 26 berada pada A2.

Gambar Struktur Pohon Data

*catatan :
gambar di atas merupakan pelengkap dari postingan sebelumnya. 

Sumber : Dr. Armin Lawi, S.Si., M.Si. - Universitas Hasanuddin, Matematika 2012

Terima kasih juga saya sampaikan buat Dea Desy Syamsuddin yang bersedia mengizinkan saya reposting artikel ini.
Kunjungi juga Blog Dea Desy Syamsuddin