Algoritma Greedy

Hallo !!! kembali lagi dengan kami pada postingan sebelumnya kita telah mengetahui bagaimana menganalisis matematis algoritma rekursif. Pada kesempatan kali ini kita akan membahas salah satu algoritma greedy . Jika belum belum tahu apa itu algoritma greedy . Anda sangat beruntung sekali masuk ke blog kami dan akan membahas detail satu persatu sehingga kalian bisa dengan mudah memahami Algoritma Greedy ini .

1. Definisi Algoritma Greedy

          Algoritma Greedy merupakan jenis algoritma yang menggunakan pendekatan penyelesaian masalah dengan mencari nilai maksimum (local maximum) sementara pada setiap langkahnya . Algoritma nini merupakan metode yang paling populer untuk memecahkan suatu persoalan optimasi .  

Sebagai contoh masalah sehari – hari yang menggunakan prinsip algoritma greedy salah satunya adalah mencari jalu tercepat/tersingkat dari UNIKOM menuju Trans Studio Mall . 

Algoritma greedy disini membuat solusi langkah per langkah , banyak sekali pilihan yang perlu di eksplorasi pada setiap langkahnya . Oleh karena itu , setiap langkah harus dibuat keputusan yang tepat untuk menentukan pilihannya . Suatu keputusan yang sudah diambil tidak boleh diubah lagi pada langkah selanjutnya .

Perhatikan gambar dibawah ini :

Misalnya kita ingin bergerak dari UNIKOM menuju ke Trans Studio Bandung dan kita telah menemukan beberapa jalur dari peta . Suatu sistem peta (Google Maps) pada gambar secara otomatis mencari jalur tercepat menuju lokasi degan waktu kira-kira 37 menit perjalanan tanpa macet . Pada gambar diatas pada dasarnya menunjukan titik – titik yang saling berhubungan , dengan jarak tertentu dan waktu tertentu pada masing-masing titik tersebut . Misalkan peta diatas kita dipresentasikan dengan titik-titik penghubung seperti berikut :

Dari gambar di atas, kita dapat melihat bagaimana sebuah jalur perjalanan dapat dipresentasikan dengan menggunakan graph misal A = UNIIKOM dan B = TSM (Trans Studio Mall). Maka dari itu, untuk menyelesaikan suatu masalah jarak terpendek kita menggunakan struktur data graph untuk merepresentasikan peta. Berikut graph yang digunakan :

k   Untuk mencari jarak terpendek dari B ke A, langkah – langkah algoritma greedy adalah sebagai berikut:

1. Kunjungi satu titik pada graph , dan ambil seluruh titik yang dapat dikunjungi dari titik sekarang
      2.Cari local maximum ke titik selanjutnya.
      3. Tandai graph sekarang sebagai graph yang telah dikunjungi, dan pindah ke local maximum yang telah ditentukan .
      4. Kembali ke langkah 1 sampai titik tujuan didapatkan.

Jika pada graph B ke A kita akan mendapatkan pergerakan seperti berikut :
- Mulai dari titik awal (B). Ambil seluruh titik yang dapat dikunjungi.

- Local Maximum adalah C, karena jarak ke C adalah yang paling dekat .
- Tandai A sebagai titik yang telah dikunjungi, dan pindah ke C
- Ambil seluruh titik yang dapat dikunjungi dari C

- Local Maximum adalah ke G, karena yang paling dekat.
- Tandai C sebagai titik yang telah dikunjungi , dan pindah ke G
- Ambil seluruh titik yang dapat dikunjungi dari G

- Local Maximum adalah ke I, karena yang paling dekat.
- Tandai G sebagai titik yang telah dikunjungi , dan pindah ke I
- Ambil seluruh titik yang dapat dikunjungi dari I

- Local Maximum adalah ke A, karena yang paling dekat.
- Tandai I sebagai titik yang telah dikunjungi , dan pindah ke A
- Tandai semua titik yang sudah dikunjungi

Dengan menggunakan algoritma greedy pada graph diatas , maka hasil akhir yang kita dapat sebagai jarak terpendek adalah B-C-G-I-A. Hasil jarak terpendek yang didapatkan ini tidak tepat dengan jarak terpendek yang sebenarnya (B-C-F-A). Algoritma greedy memang tidak selamanya memberikan solusi yang optimal dan akurat , dikarenakan pencarian local maximum pada setiap langkahnya tidak memperhatikan solusi secara keseluruhan .

Contoh kasus dari algoritma greedy :

1. Penukaran Koin

Diberikan uang senilai A. Tukar A = 73 dengan koin-koin yang ada. Berapa jumlah minimum koin yang diperlukan untuk penukaran tersebut.

Tersedia koin 1, 5, 10, 25. Uang A = 73 akan ditukarkan. Berapa koin yang ditukarkan?

Cara 1 : 73 = 1 + 1 + 1 + .... + 1 (73 koin)

Cara 2 : 73 = 5 + 5 + 5 + .... + 1 + 1 + 1 (17 koin)

Cara 3 : 73 = 10 + 10 + 10 + .... + 1 + 1 + 1 (10 koin)

dst...

Cara n : 73 = 25 + 25 + 10 + 10 + 1 + 1 + 1 (7 koin) = solusi optimal

2. Minimasi waktu di dalam sistem penjadwalan

Sebuah server mempunyai n pelanggan yang harus dilayani. Waktu pelayanan untuk setiap pelanggan i adalah ti. Minimumkan total waktu di dalam sistem.

Tiga Pelanggan dengan t1 = 5, t2 = 8, t3 = 2

Enam urutan pelayanan yang mungkin :

-----------------------------------------------------------------

Urutan                                   T

-----------------------------------------------------------------

1, 2, 3:            5 + (5 + 8) + (5 + 8 + 2) = 33

1, 3, 2:            5 + (5 + 2) + (5 + 2 + 8) = 27

2, 1, 3:            8 + (8 + 5) + (8 + 5 + 2) = 36

2, 3, 1:            8 + (8 + 2) + (8 + 2 + 5) = 33

3, 1, 2:            2 + (2 + 5) + (2 + 5 + 8) = 24 (optimal)

3, 2, 1:            2 + (2 + 8) + (2 + 8 + 5) = 27

-----------------------------------------------------------------

Kesimpulan

Algoritma greedy merupakan algoritma yang besifat heuristik, mencari nilai maksimal sementara dengan harapan akan mendapatkan solusi yang cukup baik. Meskipun tidak selalu mendapatkan solusi terbaik (optimum), algoritma greedy umumnya memiliki kompleksitas waktu yang cukup baik, sehingga algoritma ini sering digunakan untuk kasus yang memerlukan solusi cepat meskipun tidak optimal

Analisa Matematis : Algoritma Rekursif

1. Algoritma Rekursif Balik_Angka

Operasi dasar dalam algortima diatas
1. <    = 1
2. div atau / (pembagian) = 1

maka nilai T(n) , cari operasi yang paling banyak atau alogritma yang paling dalam atau operasi yang paling dasar yang terbesar .

Karena yang paling besar adalah div (pembagian)
maka nilai T(n) :

T(n) = n

Untuk menganalisa matematis dalam algoritma Rekursif sebagai berikut :
Operasi Dasar Utama : Pembagian

P (n) = P ( n / 10)    ; untuk n > 10    //{ P = Balik_Angka }

M (n) = M( n / 10) + 10
         = [ M(n / 11) + 10] + 1 = M(n / 11) +11
         = [ M(n / 12) + 10] + 2 = M(n / 12) + 12

subtitusi
M( n / 10) = M(n / 11) + 10
M(n / 11) + 10 = M(n / 12) + 10

jadi ,
M(n) = M(n/ 10) +10 = .... = M(n / i) + i = .... = M( n - n ) + n = n

2.Algoritma Pangkat Rekursif

Karena jumlah eksekusi nya bervariasi maka kita harus mencari best,worst dan average case nya.

Best-Case : 1
Worst-Case : n
Avg-Case : 1/n

Rekurens
....

Kompleksitas Algoritma : Nilai Asimtotik

Halo, kembali lagi dengan kami setelah sebelumnya membahas Kompleksitas Algoritma : Percabangan dan untuk kali ini kita masih membahas kompleksitas algoritma, yaitu nilai asimtotik. Langsung saja disimak.

1. Nilai asimtotik dari algoritma S = 1 - 2/3 + 3/6 - 4/10 + .....

Dari algoritma yang sudah didapat di post sebelumnya. Kita cari nilai asimtotiknya dengan cara mencari O (big oh),  Ω (big omega), ϴ (big theta). T(n) dari algoritma S = 1 - 2/3 + 3/6 - 4/10 + .... adalah T(n) = (n - 2) + n + 3 + (n - 2) + 1 + n + n + 1 + 1.

O-notation

T(n) ϵ O(g(n))

       jika

T(n) ≤ c.g(n)

T(n) = (n - 2) + n + 3 + (n - 2) + 1 + n + n + 1 + 1 ≤ c.g(n)

Lakukan pengecekkan, jika n = 1 dan c = 7, maka

           (1 - 2) + 1 + 3 + (1 - 2) + 1 + 1 + 1 + 1 + 1 ≤ 7. 1

           7 ≤ 7

Kondisi pengecekkan benar, maka n = 1 dan c = 7

T(n) = (n - 2) + n + 3 + (n - 2) + 1 + n + n + 1 + 1 ≤ c.g(n^2)

Lakukan pengecekan, jika n = 10, maka

            (10 - 2) + 10 + 3 + (10 - 2) + 1 + 10 + 10 + 1 + 1 ≤ 1. 10^2

            52 ≤ 100

Lakukan pengecekan satu kali lagi dengan n = 100, maka

            (100 - 2) + 100 + 3 + (100 - 2) + 1 + 100 + 100 + 1 + 1 ≤  1. 100^2

            502 ≤  10000

Karena pengecekkan bernilai benar, untuk mengetahui nilai n dari n berapa ketika dilakukan pengecekkan sudah bernilai benar. Kita cari lagi n nya dengan n = 5.

           (5 - 2) + 5 + 3 + (5 - 2) + 1 + 5 + 5 + 1 + 1 ≤  1. 5^2

           24 ≤  25

Pengecekkan bernilai benar, maka c = 1; n = 5 dan T(n) = (n - 2) + n + 3 + (n - 2) + 1 + n + n + 1 + 1 ϵ O(g(n)). Karena T(n) = (n - 2) + n + 3 + (n - 2) + 1 + n + n + 1 + 1 ϵ O(g(n)) maka dapat diasumsikan bahwa T(n) = (n - 2) + n + 3 + (n - 2) + 1 + n + n + 1 + 1 ϵ O(g(n^2)), n^3 hingga n^n adalah anggota dari O.

Omega-notation

T(n) ϵ Ω(g(n))

       jika

T(n) ≥ c.g(n)

T(n) = (n - 2) + n + 3 + (n - 2) + 1 + n + n + 1 + 1 ≥ c.g(n)

Lakukan pengecekkan dengan n = 1 dan c = 1, maka

           (1 - 2) + 1 + 3 + (1 - 2) + 1 + 1 + 1 + 1 + 1 ≥ 1. 1

           7 ≥ 1

Kondisi pengecekkan benar, cek lagi dengan mengubah n nya menjadi n = 2, maka

           (2 - 2) + 2 + 3 + (2 - 2) + 1 + 2 + 2 + 1 + 1 ≥ 1. 2

           12 ≥ 2

Kondisi benar, maka kita lakukan pengecekkan lagi dengan mengecek apakah T(n) = (n - 2) + n + 3 + (n - 2) + 1 + n + n + 1 + 1 ϵ O(g(n^0))

T(n) = (n - 2) + n + 3 + (n - 2) + 1 + n + n + 1 + 1 ≥ c.g(n^0)

Lakukan pengecekkan dengan c = 1 dan n = 1, maka

            (1 - 2) + 1 + 3 + (1 - 2) + 1 + 1 + 1 + 1 + 1 ≥ 1. 1

            7 ≥ 1

Kondisi pengecekkan benar, maka dapat diasumsikan bahwa T(n) = (n - 2) + n + 3 + (n - 2) + 1 + n + n + 1 + 1 ϵ Ω(g(n^0)), n^-1, n^-n.

Theta-notation

T(n) ϵ ϴ(g(n))

       jika

c2.g(n) ≤  T(n) ≤ c1.g(n)

Untuk mencari apakah T(n) ϵ ϴ(g(n)), ada cara termudahnya yaitu dengan melihat apakah O-notation dan Omega-notation menjadi anggota yang sama dalam satu g(n)? Untuk kasus ini, kita memiliki g(n) yang sama antara O dan Ω yaitu g(n), maka T(n) ϵ ϴ(g(n)). Kenapa dapat disimpulkan seperti itu? Karena Big Theta hanya akan menjadi salah satu anggota n. Maka dari itu, dapat disimpulkan seperti itu. Jika tidak percaya kalian bisa membuktikannya sendiri.


       2. Dalam Algoritma sederhana sebelumnya Di No 2 di peroleh T(n) = 1 + 2 + … + n. , maka untuk menentukan notasi O, Omega , dan Theta nya sebagai berikut 

Jawab:

          1 + 2 + … + n = O(n²) karena

          1 + 2 + … + n <= n + n + … + n = n² untuk n >= 1.

          1 + 2 + … + n = Omega(n) karena

          1 + 2 + … + n <= 1 + 1 + … + 1 = n untuk n >= 1.

          1 + 2 + … + n >= [n/2] + … + (n – 1) + n

                                  >= [n/2] + … + [n/2] + [n/2]      

                                    = [(n + 1)/2] [n/2]

                                  >= (n/2)(n/2)

                                     = n²/4              

Kita menyimpulkan bahwa

          1 + 2 + … + n = Omega(n²)

Oleh karena itu,

          1 + 2 + … + n = Theta(n²)


 3.Nilai Asimtotik dari Algoritma Binary Search(No.3)
Bila Algoritma Binary Search mempunyai T(n) = 4 + n Maka, nilai asimtotiknya adalah sebagi berikut :

O-notation 

T(n) ϵ O(g(n))

       jika

T(n) ≤ c.g(n)

4 + n ≤ c.g(n)
Bila mana n=1 dan c=5
4 + n ≤ 5.1
5 ≤ 5  (terpenuhi)

4 + n ≤ c.g(n^2)
Bila mana n=1 dan c=5
4 + n ≤ 5.1
5 ≤ 5  (terpenuhi)
 2 kali terpenuhi sampai mana pun akan terpenuhi.

 Contoh kedua
4 + n ≤ c.g(n)
Bila mana n=10 dan c=5
4 + n ≤ 5.10
14 ≤ 50  (terpenuhi)

4 + n ≤ c.g(n^2)
Bila mana n=10 dan c=5
4 + n ≤ 5.10
14 ≤ 500  (terpenuhi)
Sekali lagi kondisinya terpenuhi yang mana 4 + n adalah anggota dari notasi Big Oh.

Omega-notation

T(n) ϵ Ω(g(n))

       jika

T(n) ≥ c.g(n)

4 + n ≥ c.g(n)
 Bila mana n=1 dan c=1
4 + n ≥ 1.1
5 ≥ 1  (terpenuhi)

4 + n ≥ c.g(n^0)
 Bila mana n=1 dan c=1
4 + n ≥ 1.1
5 ≥ 1  (terpenuhi)

Contoh kedua
4 + n ≥ c.g(n)
 Bila mana n=10 dan c=1
4 + n ≥ 1.10
14 ≥ 10  (terpenuhi)

4 + n ≥ c.g(n^0)
 Bila mana n=10 dan c=1
4 + n ≥ 1.1
14 ≥ 1  (terpenuhi)
 Sekali lagi kondisinya terpenuhi yang mana 4 + n adalah anggota dari notasi Big Omega.

Kompleksitas Algoritma : Percabangan

Halo, kembali lagi dalam materi pembahasan kompleksitas algoritma. Nah, sebelumnya kita sudah membahas tentang Kompleksitas Algoritma : Waktu. Untuk kali ini, kita akan membahas kompleksitas algoritma percabangan. Langsung saja disimak.

1. Menghitung S = 1 - 2/3 + 3/6 - 4/10 + ....

←
Tmin(n) = 6
Tmax(n) = n + 2
Tavg(n) = 6 + 7 + 8 + .... + n + 2

 2. mengurut tabel integer [1 .. N]dengan Bubble Sort dengan memanfaatkan boolean

Yang Paling Dalam adalah Perbandingan

Tmin(n) = 1
Tmax(n)= 2
T(n)=(N-1)+(N-2)+….+2+1
   n-1
= ∑ N-I = N(N-1)/2
I = 1


3.Mencari index dengan binary search

Tmin(n) =  5
Tmax(n) = N + 1
Tavg(n) = 1/2 N(N+1)/N
1/2.10(10+1)/10=5,5

4. Mencari Bilangan Prima

10115310 - Barrur Rhozi

Tmin(n)   = 2
Tmax(n)  = i
Tavg(n)   = (i+1) / 2



5. Mencari nilai terbesar pada array



Tmin(n) = 1
Tmax(n) = n
Tavg(n) = (n + 1) / 2

Kompleksitas Algoritma : Waktu

Hello, pada postingan ini kami akan membahas tentang Kompleksitas Waktu Algoritma, kita dapat mengukur waktu yang diperlukan oleh sebuah algoritma dengan menghitung banyaknya operasi/instruksi yang dieksekusi.
Jika kita mengetahui besaran waktu (dalam satuan detik) untuk melaksanakan sebuah operasi tertentu, maka kita dapat menghitung berapa waktu sesungguhnya untuk melaksanakan algoritma tersebut.


                        Dengan rumusan :

Berikut kami memberikan 5 contohnya :

1. Algoritma Jam pasir

       

Pada algoritma di atas terdapat :

• Input = (n + (n - 1) + (n - 1)) . a
• Output = n ^ 2 / n * n (output dari "$" dan (" ") jika disatukan) . b
• Jumlah operasi meliputi :
• <= (kurang dari sama dengan) :  n -1 . c
• >= (lebih besar sama dengan) : n -1 . d
• div : n - 1 . e
• + : n -1 . f
• - : n - 1 . g
• and : n . h
• or : n . i

T(n) = (n + (n - 1) + (n - 1) ) * a + (n * n) * b + (n - 1) * c + (n - 1) * d + (n - 1) * e + (n - 1) * f + (n - 1) * g + n * h + n * i

2.    Algoritma Belah Ketupat

Dari algoritma tersebut terdapat :

• Input = 5 + (5 - 1) + 5 + 4 + 4 + 4 . a
• Output = 5 + (5 - 1) + 5 + 4 + 4 + 4 . b
• - = 4 . c

T(n) = (5 + (5 - 1) + 5 + 4 + 4 + 4)*a + (5 + (5 - 1) + 5 + 4 + 4 + 4)*b + 4*c  

3. Algoritma Index Nilai

Pada algoritma di atas terdapat :

C(n)

• Output = 5  // misalkan a
• Input = 1   // misalkan b
• Jumlah Operasi

1.  ≥ = 4 // misalkan c
2. < = 4  //misalkan d
3.  and = 4 misalkan e

makan nilai T(n)
T(n) = 5a + b + 4c + 4d + 4e

4.Algoritma Pyramid

C(n)
    <- 209  a  (n*n+8n)
    <= 100  b (8n+1)
     +  82    c  (7n+5)
     -   18    d  (n+6)

   T(n) = 209a + 100b + 82c + 18d
   T(n) = (n*n+8n).a + (8n+1).b + (7n+5).c + (n+6).d


5. Menghitung rerata

procedure HitungRerata(input a₁, a₂, ..., a_n : integer, output r : real)

{ Menghitung nilai rata-rata dari sekumpulan elemen larik integer a₁, a₂, ..., a_n.

  Nilai rata-rata akan disimpan di dalam peubah r.

  Masukan: a₁, a₂, ..., a_n

  Keluaran: r (nilai rata-rata)

}

Deklarasi

   k : integer

   jumlah : real

Algoritma

   jumlah¬0

   k¬1

   while k £ n do 

     jumlah¬jumlah + a_k

     k¬k+1

   endwhile

   { k > n }

   r ¬ jumlah/n   { nilai rata-rata }

                  Operasi pengisian nilai (jumlah¬0,  k¬1, jumlah¬jumlah+ak, k¬k+1, dan r ¬ jumlah/n)

          

                  Jumlah seluruh operasi pengisian nilai adalah

                  t1 = 1 + 1 + n + n + 1 = 3 + 2n

                  Operasi penjumlahan (jumlah+ak, dan k+1)

                  Jumlah seluruh operasi penjumlahan adalah

                  t2 =  n + n = 2n 

                  Operasi pembagian (jumlah/n)

                  Jumlah seluruh operasi pembagian adalah

                  t3 = 1

     

                  Total kebutuhan waktu algoritma HitungRerata:

                  t = t1 + t2 + t3 = (3 + 2n)a + 2nb + c  detik

Model perhitungan kebutuhan waktu seperti di atas kurang dapat diterima:

1. Dalam praktek kita tidak mempunyai informasi berapa waktu sesungguhnya untuk melaksanakan suatu operasi tertentu

2. Komputer dengan arsitektur yang berbeda akan berbeda pula lama waktu untuk setiap jenis operasinya. Selain bergantung pada komputer, kebutuhan waktu sebuah program juga ditentukan oleh compiler bahasa yang digunakan.

Model abstrak pengukuran waktu/ruang harus independen dari pertimbangan mesin dan compiler apapun.

Besaran yang dipakai untuk menerangkan model abstrak pengukuran waktu/ruang ini adalah kompleksitas algoritma.
Ada dua macam kompleksitas algoritma, yaitu kompleksitas waktu dan kompleksitas ruang.

Kompleksitas waktu, T(n), diukur dari jumlah tahapan komputasi yang dibutuhkan untuk menjalankan algoritma sebagai fungsi dari ukuran masukan n.

Kompleksitas ruang, S(n), diukur dari memori yang digunakan oleh struktur data yang terdapat di dalam algoritma sebagai fungsi dari ukuran masukan n.

Dengan menggunakan besaran kompleksitas waktu/ruang algoritma, kita dapat menentukan laju peningkatan waktu (ruang) yang diperlukan algoritma dengan meningkatnya ukuran masukan n. 

Kompleksitas Waktu

Dalam praktek, kompleksitas waktu dihitung berdasarkan jumlah operasi abstrak yang mendasari suatu algoritma, dan memisahkan analisisnya dari implementasi.

Demikian Kumpilan Contoh  Kompleksitas Algoritma Waktu : T(n)
Terima Kasih ...

Sumber : Ebook , Book Note , Modul , Dll

DAFTAR ISI

Tugas 1

Numeric Problem
Combinatorial Problem
Geometry Problem
Graph Problem
String Matching

Sorting
Quick Sort
Bubble/Exchange Sort
Shell Sort
Heap Sort
Bucket Sort
Merge Sort
Insertion Sort
Selection Sort

Searching
Binary Search

Tugas 2
Kompleksitas Algoritma Waktu

Tugas 3
Kompleksitas Algoritma : Percabangan