ALGORITMA DAN STRUKTUR DATA

ALGORITMA DAN STRUKTUR DATA

Apa itu Algoritma ?

• Prosedur komputasional yang terdefinisi dengan baik yang membutuhkan nilai (atau himpunan nilai) sebagai input dan menghasilkan nilai (atau himpunan nilai) sebagai output
• Alat bantu (tools) menyelesaikan masalah komputasional yang terdefinisi dengan baik (well-defined computational problem)
• Metode penyelesaian yang logis dan ‘wajib’ benar (correctness) sesuai keinginan masalah (desired solution)

Desain dan Analisis Algoritma

• Pseudocode: Kode untuk memudahkan pemahaman algoritma yang dapat ditransformasi kedalam berbagai Bahasa Pemrograman.
• Kompleksitas algoritma: Analisis kebutuhan dari algoritma, khususnya waktu komputasi dan kapasitas memory.
• Strategi algoritma: Perancangan kadang membutuhkan strategi perancangan algoritma tertentu.
  Dalam kuliah ini: Greedy algorithm, divide-and-conquer, dynamic programming dan strategi-strategi algoritma meta-heuristik untuk masalah optimisasi.
• Struktur data: Menyimpan dan mengorganisasi data untuk kepentingan akses dan modifikasi.
  (Tidak dibahas lengkap karena diluar topik MK ini)

Contoh Masalah Komputasional

• Masalah NP-lengkap: Tidak ada solusi efisien.
• Masalah Pencarian Data (Searching Problem)

Input:  Barisan n bilangan asli  <a1, a2, …, an> dalam larik A dan sebuah bilangan key yang ingin dicari.

Output: Lokasi key dalam A. Jika key tidak ditemukan dalam A, tambahkan key sebagai unsur terakhir.

Pseudo-code Algoritma

• Linear-Search(A, key)
• indeks ← 1;
• ada ← False;
• while  indeks ≤ length[A]  and ada = False
•     if  A[indeks] = key  then
•         ada = True;
•     indeks ← indeks + 1;
•          indeks ← indeks - 1;
• if  ada = False  then
•     indeks ← length[A] + 1;
•          A[indeks] ← key;
• return  indeks

Contoh Masalah Lain

• Masalah Pengurutan Data (Sorting Problem)

Input:  Barisan n bilangan dalam array A = <a1, a2, …, an>

Output:  Permutasi barisan bilangan sedemikian sehingga terurut kembali kedalam barisan bilangan  A = <a1’, a2’, …, an’>, dimana a1’ ≤ a2’ ≤ … ≤ an’

Input: Barisan bilangan  A= <31, 41, 59, 26, 41, 58>

Output: Barisan bilangan terurut A = <26, 31, 41, 41, 58, 59>

Algoritma pengurutan (sorting algorithm) mengembalikan permutasi barisan bilangan yang terurut kembali.

Contoh :

 A = 26    10 35   5

Simulasi :

1. (for j = 2) 

1. Key = A[j] =10  , i = j – 1 = 1
2. While (i > 0 ^ A[i] > key) 

b.1.  A(i+1) = A[i] = 26 A [26][26][35][5]

b.2.  i = i – 1 = 0

3. While ( i >0 ^ A[i] > key)
4. A[i+1] = key = 10 A [10][26][35][5]

2. (for j = 3)

1. Key = A[j] = 35
2. While (i > 0 ^ A[i] > key)
3. A[i+1] = key = 35 A [10][26][35][5]

3. (for j = 4)

1. Key = A[j] = 5  ,i=j-1=3
2. While (i > 0 ^ A[i] > key)

b.1. A(i+1) = A[i] = 35 A [10][26][35][35]

b.2. i = i – 1 = 2

3. While ( i >0 ^ A[i] > key)

c.1. A(i+1) = A[i] = 26 A [10][26][26][35]

c.2. i = i – 1 = 1

4. While (i > 0 ^ A[i] > key)

d.1. A(i+1) = A[i] = 10 A [10][10][26][35]

d.2. i = i – 1 = 0

5. While (i > 0 ^ A[i] > key)
6. A[i+1] = key = 5 A [5][10][26][35]

4. (for j = 5)