 |
| 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 :
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
5. While (i > 0 Λ A [i] > key )………………………. (true)Λ(true)
Sehingga
A[i+1] = 27
6. While (i > 0 Λ A [i] > key )………………………. (false)Λ(true)
Sehingga,
A[i+1] = 15
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
Tertanggal 13 September lalu, perfilman di dunia, khususnya Amerika
Serikat memang telah diramaikan dengan kehadiran sekuel film . Meski di
Cinema 21 masih menunggu tanggal perilisan, namun kabar menarik seputar
film horor satu ini sudah kembali menyeruak.
