pertemuan · ada cara yang lebih cerdik? contoh: mencari nilai maksimum dalam array strategi...

ANALISIS ALGORITMAJIMMY TIRTAWANGSA<[email protected]>

PROGRAM PASCA SARJANA INFORMATIKAUNIVERSITAS TELKOMSemester II 2018-2019

Jadwal

● Awal: 28 Januari 2019● PR 1: 7 Maret 2019● TUGAS 1: 21 Maret 2019● UTS: 18 Maret 2019● PR 2: 9 Mei 2019● TUGAS 2: hari ke-(UAS+3)● UAS: TBD (13/20 Mei 2019)

Pertemuan:

Tiap Senin pagi 9:00 - 11:30

Tugas, Nilai, dan Indeks

Sumber Penilaian:

● UAS 40%● UTS 25%● TUGAS 20%● Kuis & PR 15%

Batas Minimum Indeks:

A. > 70B. -C. -D. < 50E. -

Tugas dan Homework:● Tugaspemrograman di spoj.com

○ signup○ pilih problem yang diumumkan○ tugas submit disini

● submit PR ke email [email protected]

● perhatikan tanggal batas akhir submisi

Rujukan dan Sumber Informasi

Harus:● Cormen, Leserson, Rivest, and Sten:

Introduction to Algorithms 3rd ed.● Kleinberg and Tardos: Algorithm Design● Levitin: Design & Analysis of Algorithms● Gunakan Internet

○ Berbagai materi sejenis di tempat lain○ Google: lecture notes○ Youtube : coursewares○ eBooks

● Diskusi● Banyak latihan sendiri● Hadiri dan ikuti diskusi kelas

Jangan:● Gunakan Internet

○ Untuk Copy solusi (Baca boleh, tapi bukan untuk disalin mentah2)

○ Melakukan tindak plagiat, baik tulisan maupun program○ Saat hadir di kelas (otak anda yang sedang dilatih, situs

Google tidak perlu dilatih lagi)

● Bekerja sama, nyontek, dll○ (Boleh diskusi untuk persiapan PR, tugas dan sebelum

ujian)○ (Tapi pada saat pembuatannya harus bekerja sendiri

dengan kata2 sendiri)

● Terlambat submisi● Membuat alasan untuk tidak ikut ujian

● https://jimmytirtawangsa.staff.telkomuniversity.ac.id/

Apakah Algoritma?Mengapa perlu dianalisis?Apa yang perlu dianalisis?

Algoritma

● Urutan/komposisi instruksi komputasi untuk menyelesaikan suatu masalah● Eksekusinya selesai dalam waktu/jumlah langkah terbatas● Diberikan kondisi awal yang jelas, komputasi akan memberikan jawaban yang

jelas pula saat terminasi

● Berbasis model Random Access Machine (RAM):○ Simplifikasi cara kerja komputer modern○ Operasi primitif: aritmatika, logika, dan lainnya○ Instruksi Input-Output○ Instruksi Assigment instructions (perpindahan data dalam memori)○ Struktur kontrol: percabangan (if-else) dan pengulangan (while-loop)

Contoh: Mencari Nilai Maksimum dalam Array

Diberikan sebanyak n data dalam arrayCari nilai terbesar/terkecil (ekstrim) dalam array tersebut

● Caranya?

Operasi primitif yang tersedia adalah membandingkan sepasang data

● Ada cara yang lebih cerdik?


Strategi Brute-force (Hajar-bleh)● Nyata sejak awal bahwa seluruh data harus diperiksa● Jika tidak maka data yang terlewat diperiksa mungkin adalah yang terbesar● Jika urutan data diketahui dimana nilainya dapat diduga dari posisinya● Misalnya terurut membesar, maka data terakhir pastilah yang terbesar.

Dengan operasi primitif membandingkan 2 data● Bandingkan satu persatu dan● Simpan/catat data yang sejauh ini diketahui sebagai yang terbesar


func FindMax( A[1..n] ) : indeximax := 1i := 2while i < n do

if A[i] > A[imax] thenimax := i

endifi := i + 1

endwhilereturn imax

● Proses harus dilakukan secara sekuensial● Dengan membandingkan 2 data

○ Yang satu diketahui saat ini yang terbesar○ Yang lain data baru yang harus diuji

Analisis Algoritma: Kebenaran Algoritma

● INDUKSI○ Loop invarian: Kondisi yang selalu dipenuhi oleh loop utama algoritma○ Basis: Tunjukan bahwa kondisi tersebut berlaku sejak awal, saat memasuki loop pertama kali○ Induksi: Tunjukan jika sampai iterasi sebelumnya kondisi tersebut benar, maka kondisi

tersebut tetap benar pada akhir iterasi ini○ Terminasi: Tunjukan saat keluar dari loop, kombinasi kondisi terminasi dan loop invarian

menghasilkan bukti kebenaran algoritma

● KONTRADIKSI○ Mulai dengan klaim bahwa negasi dari kondisi adalah yang benar○ Buktikan bahwa pernyataan tersebut mengakibatkan konsekuensi yang konflik○ Sehingga kesimpulan yang dapat ditarik adalah kondisi semula-lah yang benar

● Pilih strategi yang paling sedikit yang harus dibuktikan● Bukti DENGAN CONTOH

○ ONLY to SHOW that the Algorithm is INCORRECT


func FindMax( A[1..n] ) : indeximax := 1i := 2{ L.I.: A[imax] > A[1..i-1] }while i < n do


endifi := i + 1

endwhile{ TERM.: i > n }return imax

Loop Invarian (L.I.):

● Kondisi yang relevan dengan obyektif algoritma tersebut● Situasi incremental menuju hasil akhir algoritma tsb.

● Bukan kondisi iterasi● Karena kondisi tersebut tidak berlaku setelah terminasi!




endifi := i + 1


● Basis: i==2, A[imax==1]>A[1..i-2=1] atau A[1] > A[1] berarti kondisi tersebut berlaku diawal eksekusi.

● Asumsi A[imax] > A[1..t-1] betul untuk semua 1 < t < n ○ (t berlaku dari nilai awal s.d. sebelum terminasi)

● Induksi terhadap proses dalam loop:○ Ketika i = t → L.I benar untuk i○ Jika A[i] < A[imax] maka imax tidak diubah, dan berlaku

kondisi A[imax] > A[1..i]○ Jika A[i] > A[imax] maka imax diubah ke-i dan berlaku

A[imax==i] > A[1..i]○ Pada baris terakhir dalam loop, nilai i bertambah, atau

berlaku i == t+1, dan kita peroleh kembali kondisi LI semula A[imax] > A[1..i-1] untuk nilai i yang baru

● Terminasi:○ i > n (karena incremental, i==n+1)○ dan A[imax] > A[i..i-1], sehingga A[imax] > A[1..n]○ Kesimpulannya A[imax] nilai terbesar dalam array tsb




endifi := i + 1


● Ambil A[imax], untuk imax=1..n, bukan nilai yang terbesar dalam array atau A[imax] ≱ A[1..n]

● Maka tentunya ada ix=1..n dimana A[ix] > A[imax]● Tetapi dalam loop yang diberikan, seluruh data dalam

array pasti diuji paling sedikit satu kali, termasuk A[ix]● Artinya pada saat iterasi i=ix A[imax] saat itu akan diuji

terhadap A[ix]● Karena pengujian (instruksi if) tidak mungkin salah,

tentunya indeks imax akan diisi nilai indeks ix● Dan iterasi lanjutan setelah i=ix s.d. n dengan alasan

yang sama (instruksi if) tentunya juga tidak akan mengubah nilai imax lagi.

● Sehingga diperoleh A[ix] == A[imax]● Terjadi kontradiksi dan hanya bisa disimpulkan bahwa

A[imax] > A[1..n] atau A[imax] nilai terbesar dalam array




endifi := i + 1

endwhilereturn imax

● Contoh: n=5 dengan A[1..n] = {3, 2, 13, 7, 17}● dst . . .

Analisis Algoritma

1. Kebenaran Fungsia. Pembuktian BENAR dengan INDUKSI atau KONTRAKDIKSIb. Pembuktian SALAH dengan CONTOH

2. Karakteristik Non-Fungsia. Sumber daya: WAKTU, MEMORI, BANDWIDTH, ...b. Skalabilitas, Bounded, Real-time, c. Stabilitas

3. Analisis Teori vs. Evaluasi Eksperimen?a. Algoritma vs. Program (Bukti vs. Afirmasi)b. Besar obyek masalah yang dihadapi (Lingkung lab vs. Data riil)

Analisis Non-Fungsional Algoritma: Kecepatan

● Bergantung pada:○ Platform hardware yang digunakan○ Situasi eksternal eksekusi (temperatur, tegangan listrik, …)○ Interaksi dengan proses lain (persaingan sumber daya, sinkronisasi I/O, …)○ Bahasa pemrograman dan perkakas yang digunakan (interpreted/translated)○ Style pemrograman / pemrogram○ Algoritma yang diterapkan

● Dari algoritma diprediksi/interpolasi karakteristik operasional tersebut○ Evaluasi setiap detil instruksi yang digunakan, atau○ Identifikasi instruksi yang esensial yang menjadi parameter penting (independen),○ Dan kalkulasi pengaruhnya dalam eksekusi algoritma




endifi := i + 1

endwhilereturn imax

● Operasi perbandingan diduga paling dominan karena yang akan paling sering dikerjakan dalam algoritma ini

● Instruksi assignment imax := i belum tentu sesering operasi perbandingan

● Iterasi terjadi untuk variabel i dari 2 s.d. n, atau (n-1) kali● Sehingga jumlah perbandingan adalah (n-1) kali● Diperkirakan waktu eksekusi akan berbanding lurus

dengan jumlah perbandingan.○ Jika waktu eksekusi untuk n=n0 diketahui t=t0 ○ Maka diprediksi untuk n=n1 waktu eksekusinya adalah

t1=(t0/n0)*n1

● Misalkan untuk n0=1K data, eksekusi adalah t0=1 detik, berapa waktu eksekusi jika n=1M data? Juga berapa data yang dapat diolah jika waktu yang tersedia adalah t=1jam?

Contoh: Mencari Suatu Nilai dalam Array

Diberikan suatu nilai yang ingin dicari, dan sejumlah data/nilai dalam arrayCari nilai tersebut dalam array dan berikan posisi/indeks nilai tersebut dalam array (jika ada)

● Saat mencari nilai ekstrim, nilai yang dicari belum tahu tapi pasti ada dalam array

● Saat mencari suatu nilai, nilai yang dicari diketahui, tetapi keberadaan dalam array tidak bisa dipastikan sebelumnya

Tidak perlu menguji semua data, dapat berhenti apabila data yang dicari sudah ditemukan.


● Menggunakan strategi Brute-force○ Nyata sejak awal bahwa mungkin seluruh data harus diperiksa○ Jika tidak maka data yang terlewat diperiksa mungkin adalah yang dicari○ Kecuali urutan data tertentu sehingga nilainya dapat diduga dari posisinya○ Misalnya terurut membesar, maka strategi lain lebih cerdik dapat dilakukan

● Dengan membandingkan v terhadap setiap elemen array A


func Search( A[1..n], v ) : indexi := n{ L.I.: . . . }while i > 1 and A[i] <> v do

i := i - 1endwhile{ TERM: . . . }return i

● Proses harus dilakukan secara sekuensial● Dengan membandingkan v terhadap

setiap elemen array A● Jika data v tidak ada dalam array, maka

fungsi mengembalikan nilai 0


func Search( A[1..n], v ) : indexi := n{ L.I.: A[i+1..n] <> v }while i > 1 and A[i] <> v do

i := i - 1endwhilereturn i{ TERM.: i < 1 or A[i] == v }

● Basis: i==n, A[n+1..n] berada diluar area array, jadi tidak mungkin v ada disana atau dpl. L.I. benar

● Asumsi L.I. berlaku saat memasuki loop● Induksi terhadap proses dalam loop:

○ Saat masuk loop L.I. berlaku A[i+1..n] <> v○ Kalau masuk loop maka otomatis A[i] <> v○ Sehingga menjadi berlaku A[i..n] <> v○ Setelah eksekusi satu2nya instruksi dalam loop,

kembali kita peroleh kondisi L.I. A[i+1..n] <> v

● Terminasi:○ i < 1 (karena decremental maka i==0), dengan kondisi

A[i+1..n] <> v, maka berlaku A[1..n] <> v yang artinya TIDAK ADA v dalam array A

○ ATAU A[i]==v dengan A[i+1..n] <> v○ Disimpulkan bahwa v ditemukan pada posisi ke-i jika

i > 0 atau tidak ada v dalam array A jika i == 0


func Search( A[1..n], v ) : indexi := nwhile i > 1 and A[i] <> v do

i := i - 1endwhilereturn i

● Badan loop praktis kosong● Sehingga operasi yang dominan adalah

perbandingan elemen array terhadap v● Bagian dominan masih loop tersebut,

dengan iterasi untuk i dari n s.d. 1, atau maksimum sebanyak n kali

● Jika nilai v tidak ditemukan, iterasi adalah sebanyak n kali● Jika nilai v ditemukan sebagai elemen pertama, iterasi sebanyak n-1 kali● Jika nilai v ditemukan sebagai elemen terakhir, iterasi tidak ada, 0 kali● Rerata jumlah iterasi saat mencari nilai v baik ditemukan maupun tidak adalah

T=(0+1+...+n-1+n)/(n+1) = ((n+0)n/2)/(n+1) = n2/(2n+2) ≃ ½n iterasi

Latihan: Binary Search

● Apa syarat pencarian biner?● Bagaimana ide pencarian biner?● Buat algoritma pencarian biner● Tentukan loop invariannya dan buktikan kebenarannya!● Prediksi waktu eksekusinya● Jika untuk data n0=1K waktu eksekusi adalah t0=1ms, berapa prediksi waktu

yang diperlukan jika jumlah data adalah n=1M? Jika alokasi waktu adalah t=2ms, kira-kira berapa besar maksimum array?

PENGURUTAN/PERMUTASI DATA

Pengurutan Data

● Diberikan n data dalam array A[1..n]● Proses agar isi array A[1..n] terurut membesar/mengecil (sesuai indeks)

○ i.e. posisi data dalam array sesuai dengan relatif nilai data terhadap tetangga kiri/kanannya.

Keterurutan data memudahkan banyak proses lain:● Mencari nilai ekstrim (terbesar, terkecil)● Mencari suatu nilai● Mencari nilai tengah (median) atau nilai ke-k

Aplikasi:● Sorting nama folder (PC, smartphone), contact (HP, smartphone) , dll● Evaluasi/visualisasi data statistik, eksperimen, ...

Pengurutan Data

● Salah satu problem komputasi yang telah (dan masih!) banyak dipelajari○ Untuk domain tantangan yang lebih luas○ Terdistribusi? Big data?○ Tipe data baru: Image? Sound?

● Mempunyai banyak solusi dan variasi karakteristik solusi○ Simpel vs. Efisien; mudah bagi progamer vs. bagi komputer○ Stabil; posisi relatif data tidak berubah untuk (kunci) nilai yang sama○ Prediktabilitas; variasi eksekusi vs. data

● Menjadi standar acuan pembelajaran algoritma○ Proses pembuktian○ Perhitungan efisiensi dan optimalitas○ Strategi2 komputasi untuk problem2 praktikal

Selection SortMetoda pengurutan data sederhana

Contoh: Selection SortDiperkenalkan: oleh E. Friend (1956) dan D. Bell (1958)

Idenya sederhana:

● Array yang terurut mempunyai data terbesar pada indeks terbesar,

● Indeks ke-2 terbesar berisi data ke-2 terbesar, dst.

● Jadi, cari data terbesar dan tempatkan ditempat seharusnya

● Lakukan iterasi untuk terbesar berikutnya

Proses dengan mencari yang terkecil lebih dulu Proses dengan mencari yang TERBESAR lebih dulu

Selection Sort

proc SelectionSort( A[1..n] )i := nwhile i > 1 do

j := FindMax(A[1..i])t := A[j]A[j] := A[i]A[i] : = ti := i - 1

endwhile

Idenya sederhana:

● Array yang terurut mempunyai data terbesar pada indeks terbesar,

● Indeks ke-2 terbesar berisi data ke-2 terbesar, dst.

● Jadi, cari data terbesar dan tempatkan ditempat seharusnya

● Lakukan iterasi untuk terbesar berikutnya

Contoh: Selection Sort

proc SelectionSort( A[1..n] )i := n{L.I.: . . . }while i > 1 do


endwhile{Term: . . . }

● Kondisi terminasi○ . . .

● Loop Invarian○ Refleksi dari perjalanan proses yang sedang berlangsung

● Setelah selesai iterasi sebelumnya○ Semua data A[1..i] lebih kecil dari A[i+1]○ Semua data A[i+1.. n] sudah terurut

Contoh: Selection Sort

proc SelectionSort( A[1..n] )i := n{L.I.: A[1..i]<A[i+1]< .. <A[n] }while i > 1 do


endwhile{Term: i < 1 }

● Loop Invarian○ Semua data A[1..i] lebih kecil dari A[i+1]○ Semua data A[i+1.. n] sudah terurut

● Basis: i==n saat pertama kali memasuki loop○ Sehingga A[n+1 .. n] berada diluar rentang array○ (Ingat: op implikasi logis p ⇒ q pada tabel kebenaran)

● Hipotesis: Kondisi LI diatas berlaku untuk 1 < i < n● Induksi:

○ Saat j memperoleh maks., kondisi tidak berubah■ A[1..i] < A[j] < A[i+1] < .. < A[n], dimana 1 < j < i

○ 3 instruksi berikutnya terjadi pertukaran data, sehingga:■ A[1..i-1] < A[i] < A[i+1] < .. < A[n]

○ Kondisi L.I. kembali diperoleh setelah i := i - 1■ A[1..i] < A[i+1] < .. < A[n]

● Terminasi:○ i < 1 (karena dekremental, i==1)○ A[1..i] < A[i+1] < .. < A[n]○ Sehingga A[1] < A[2] < .. < A[n] atau terurut !

● Karakteristik eksekusi?● Perkiraan untuk jumlah data

yang lebih besar?● Pengaruh dari platform yang

digunakan?

Karakteristik Eksekusi Selection Sort

● Apa yang terjadi untuk data lebih banyak?

● Apakah dapat diprediksi secara matematis?

● Apakah yang memprediksi paling baik? (Apa parameter independen yang cocok?)

● Apa yang terjadi jika komputer lebih cepat?

● Ap ayang terjadi jika bahasa pemrograman diganti?

● Alat prediksi yang paling cocok?

● Apa yang diprediksi: kondisi terburuk, rerata, terbaik?

Memprediksi Karakteristik Selection Sort

● Beberapa operasi utama sebagai representatif algoritma keseluruhan

● Operasi yang sering diperhatikan adalah:○ Perpindahan/pertukaran data○ Pembandingan data

● Kasus terburuk:○ Batas atas, kebutuhan maksimum

sumber daya○ Batas bawah, kebutuhan minimum

sumber daya● Kasus rerata:

○ Yang diharapkan dalam kondisi normal● Kasus terbaik:

○ Ada manfaatnykah?

Kompleksitas Asimptotik Selection Sort

Hasil eksperimen:

● Waktu eksekusi T(k)=c.k dengan konstanta c dan jumlah komparasi k

● Batas atas waktu terdekat dicapai pada catas.k dimana catas=1/1,400,000

● Batas bawah waktu terdekat dicapai pada cbawah.k, dimana cbawah=1/1,570,000

● Dimana catas dan cbawah adalah konstanta hasil pengamatan

● Konstanta bergantung pada bahasa dan komputer yang digunakan

● Cari fungsi dengan prediktor sebagai parameter independen, setelah dikali kostanta, selalu diatas (dibawah) waktu setelah jumlah data tertentu.

Utak Atik Hitungan FindMax

function FindMax( A[1..n] ) : indeximax := 1i := 2while i < n do


endifi := i + 1

endwhilereturn imax

● Komparasi terjadi pada instruksi “if”● Terjadi untuk i=2..n● Sehingga jumlah komparasi untuk n data,

TFINDMAX(n)=n-1

Utak Atik Hitungan Selection Sort

proc SelectionSort( A[1..n] )i := nwhile i > 1 do


endwhile

● Komparasi terjadi dalam fungsi FindMax● Sehingga jumlah komparasi,

TSSORT(n)=Σi=2..nTFINDMAX(i) =Σi=2..n(i-1) =Σi=1..n-1(i) =½(n-1+1)(n-1) =½(n)(n-1) =½n2 - ½n

Asimptotik adalah

[Merriam Webster] A straight line associated with curve such that as a point moves along an infinite branch of the curve, the distance from the point to the line approaches zero and the slope of the curve at the point approaches the slope of the line.

[Britannica] In mathematics, a line or curve that acts as the limit of another line or curve. For example, a descending curve that approaches but does not reach the horizontal axis is said to be asymptotic to that axis, which is the asymptote of the curve.

[Mathworld Wolfram] An asymptote is a line or curve that approaches a given curve arbitrarily closely.

Asimptotik Batas Atas

𝚶(f(n)) adalah fungsi f(n) setelah dikali suatu konstanta positif c akan selalu berada diatas data pengamatan g(n) setelah sejumlah n0 data.

g(n) ≤ c.f(n) saat n ≥ n0

Kita mencari kurva fungsi f(n) yang dapat memprediksi seakurat mungkin kinerja (g(n)) algoritma tersebut dengan berbagai variasi data masukan, untuk jumlah data yang relatif besar.

Kompleksitas algoritma umumnya diperoleh dalam bentuk big-Oh ini. Contohnya selection sort 𝚶(n2).

Asimptotik Batas Bawah

𝛀(f(n)) adalah fungsi f(n) setelah dikali suatu konstanta positif c akan selalu berada dibawah data pengamatan setelah minimum n0 data.

g(n) ≥ c.f(n) saat n ≥ n0

Kita mencari kurva fungsi f(n) yang dapat memprediksi kebutuhan mininum (g(n)) algoritma/problem tersebut dengan berbagai variasi data masukan, untuk jumlah data yang relatif besar.

Bagi selection sort 𝛀(n2) juga ternyata merupakan batas bawah, lihat kembali ilustrasi data.

Asimptotik Batas Optimal

𝚯(f(n)) adalah fungsi f(n)

setelah dikali suatu konstanta positif c1 akan selalu berada diatas data pengamatan (g(n)) setelah minimum n0 data

dan

setelah dikali suatu konstanta positif c2 akan selalu berada dibawah data pengamatan (g(n)) setelah minimum n0 data

Asymptotic Optimal Bound

𝚯(f(n)) adalah fungsi f(n)

d.f(n) ≤ g(n) ≤ c.f(n) saat n ≥ n0

● Jika batas atas dan batas bawah kompleksitas algoritma sama. Contoh: Selection sort pada 𝚯(n2)

● Jika batas atas kompleksitas algoritma sama dengan kebutuhan minimum komputasi problem tersebut, maka disebut problem tersebut disebut sudah mempunyai solusi yang optimal

Algoritma Pengurutan yang lain?

Contoh: Insertion Sort

Diperkenalkan oleh John Mauchly(1946), Knuth(1973)

Idenya:

● Seperti bermain kartu● Kartu baru disisipkan pada posisi yang sesuai,● Sehingga kartu ditangan akan selalu terurut,● Tidak bergantung pada nilai kartu di meja

Selection sort vs. Insertion sort

Karakteristik Insertion Sort

proc InsertionSort( A[1..n] )i := 2while i < n do

t := A[i]j := i-1while j > 1 and A[j] > t do

A[j+1] := A[j]j := j - 1

endwhileA[j+1] := ti := i + 1

endwhile

● Seperti bermain kartu● Kartu baru disisipkan pada posisi yang sesuai,● Sehingga kartu ditangan akan selalu terurut,● Tidak bergantung pada nilai kartu di meja

Pembuktian Insertion Sort

proc InsertionSort( A[1..n] )i := 2{ L.I.#1: . . . }while i < n do

t := A[i]j := i - 1{ L.I.#2: . . . }while j > 1 and A[j] > t do

A[j+1] := A[j]j := j - 1

endwhile{ Term#2: . . . }A[j+1] := ti := i + 1

endwhile{ Term#1: . . . }

● Buktikan mulai dari loop yang lebih dalam baru kemudian loop luar

● Tentukan loop invarian dan kondisi terminasi yang tepat untuk masing-masing loop

● Buktikan dengan cara induksi○ Basis○ Induksi○ Terminasi

Karakteristik Insertion Sort



A[j+1] := A[j]j := j - 1


endwhile

Asymptotic Complexity for Insertion Sort

Hasil eksperimen:

● Komparasi dan pemindahan data mempunyai kurva yang mirip dengan waktu eksekusi, karena …

● Disparitas batas bawah dan batas atas yang besar, karena …

● Konstanta pengali jumlah komparasi dan pemindahan data bergantung pada bahasa dan hardware yang digunakan

● Cari fungsi dengan prediktor sebagai parameter independen, setelah dikali kostanta, selalu diatas (dibawah) waktu setelah jumlah data tertentu.

Utak Atik Hitungan Insertion Sort



A[j+1] := A[j]j := j - 1


endwhile

● Jumlah operasi terdalam (A[j+1] := A[j]) berada dalam 2 nested loops:○ loop luar: i:=2 … n, atau n-1 iterasi○ loop dalam j:=i-1 … 1 atau s.d. A[j] < t < A[j+2]

● Worst case, loop dalam berhenti saat j == 0○ loop dalam i-1 iterasi, sehingga TISORT(n)=Σi=2..n(i-1) =

Σi=1..n-1(i)=½(n-1+1)(n-1)=½(n)(n-1) = ½n2-½n

● “Best” case, tidak masuk loop karena A[j==i-1] > t○ hanya loop luar, sehingga TISORT(n)=n-1

● Average case adalah rata2 dari semua kemungkinan loop-dalam berhenti.○ Asumsi probabilitas terjadinya loop-dalam antara 0 kali s.d.

i-1 kali adalah sama○ Sehingga rerata jumlah iterasi dalam adalah Tj(i) =

(Σj=0..i-1(j))/i = (Σj=1..i(j))/i - 1 = ½(i+1)-1 = ½i -½○ TISORT(n)=Σi=2..n(½i -½) = ½Σi=2..n(i-1) = ½(½n2-½n) = ¼n2-¼n

Kualitas Lain dari Insertion Sort

● Stabilitas● Proses incremental● Cepat untuk data “hampir terurut”

Randomized Insertion Sort


r := random(i, n)t := A[r]A[r] := A[i]j := i-1while j > 1 and A[j] > t do

A[j+1] := A[j]j := j - 1


endwhile

● Mengurangi disparitas waktu karena ketergantungan data masukan

Cerita Algoritma Sorting yang lain?

Untuk para guru/dosen

Beberapa algoritma tidak layak untuk bahan ajar

● Tidak mengarahkan pada berpikir secara komputasi (walau algoritma sederhana)

● Tidak efisien (algoritma pertama akan selalu diingat dan yang pertama diterapkan)

Karakteristik Bubble Sort

proc BubbleSort( A[1..n] )i := 1while i < n do

j := nwhile j > i do

if A[j] < A[j-1] thent := A[j]A[j] := A[j-1]A[j-1] := t

endifj := j - 1

endwhilei := i + 1

endwhile

Penamaan oleh Iverson(1962)

Idenya telah lama dikenal:● Make many iterations● Each time check whether two neighboring

data are in correct sequence● If not, do an exchange





endifj := j - 1

endwhilei := i + 1

endwhile



A[j+1] := A[j]j := j - 1


endwhile





endifj := j - 1

endwhilei := i + 1

endwhile

Memang BEGITU Lambat?

Penyempurnaan Algoritma

Karakteristik lain

● Cepat/memori kecil dll. bukan satu2nya properti yang diperhitungkan dalam pengembangan algoritma

● Cepat tapi salah, tidak berguna● Stabilitas data, tidak mengubah data/posisi yang tidak perlu diubah● Konsistensi waktu, pada situasi realtime● Untuk jumlah data besar, lokasi dan variasi tipe● Solusi eksak atau cukup aproksimasi (approx. sorting)● Kompatibilitas (variasi format, dll.)

Penyempurnaan Efisiensi

● Cari cara agar komputasi yang tidak perlu tidak akan dilakukan● Hindari komputasi yang sama dengan parameter yang sama, karena akan

memberikan hasil yang sama● Metoda algoritma mengarah pada penyempurnaan efisiensi diatas

○ Divide and conquer, Pruning○ Dynamic programming○ Greedy approach○ Branch and bound

● Analisis mendalam atas karakteristik dari problem tersebut dan/atau informasi tambahan tentang problem tersebut

Pangkas komputasi yang tidak perlu

● Proses pencarian (searching) harus satu per satu (brute force) jika tidak ada informasi tambahan

● Proses binary search dapat dilakukan jika diketahui data dalam keadaan terurut○ Setiap satu pengujian, bukan hanya satu data yang disingkirkan○ Ada sebagian data yang otomatis diketahui tidak akan mempengaruhi proses pencarian○ Dan dapat dipangkas/diabaikan pada iterasi berikutnya

Komputasi berulang

● Pada algoritma selection sort, misalkan dengan data contoh○ 2 3 5 7 11 13

● Pada iterasi 1, komparasi yang dilakukan (mencari Max):○ 2↔3, 3↔5, 5↔7, 7↔11, 11↔13

● Pada iterasi 2 sebagian besar komparasi yang akan diulang:○ 2↔3, 3↔5, 5↔7, 7↔11

● Dst nya sampai iterasi terakhir, pada dasarnya komparasi yang sudah dilakukan sebelumnya akan diulang

● Ide baru perlu dicari agar redundansi ini dapat dihilangkan/dikurangi

Divide and Conquer, Pemangkasan

● Divide and conquer, komputasi dikurangi dengan tidak melakukan untuk seluruh data yang ada pada setiap iterasi○ Quicksort○ Mergesort

● Pruning, komputasi dikurangi dengan memastikan sebagian data tidak perlu diproses lagi pada iterasi berikutnya○ Pencarian median dalam waktu linear

Dynamic Programming

● Jika komputasi utama terdiri dari sejumlah komputasi kecil serupa (terdifinisi rekursif)

● Komputasi kecil tersebut mungkin sama dan digunakan beberapa kali● Pengulangan dapat dihindari dengan menyimpan hasil komputasi kecil

tersebut untuk kemudian dipakai lagi tanpa harus diproses ulang● Komputasi utama cukup dengan mencari hasil komputasi kecil dari tabel

○ Menghitung nilai pada deret fibonacci

Pendekatan Greedy

● Dengan memilih alternatif terbaik dari yang terlihat sejauh horison komputasi yang dilakukan

● Untuk banyak problem, semua alternatif solusi terlihat dengan jelas, sehingga pilihan selalu yang terbaik○ Selection sort : pada setiap iterasi cari nilai terbesar berikutnya?

● Untuk banyak problem lain, tidak semua alternatif solusi terlihat dalam batas horison komputasi, sehingga pilihan terbaik saat itu belum tentu pada akhirnya yang terbaik○ TSP : pada setiap iterasi cari jarak dua kota terdekat berikutnya?

Branch and bound, Brute force

● Brute force, semua alternatif solusi harus diuji untuk menentukan mana yang terbaik.○ Mencari nilai maksimum dari sejumlah data tidak terurut

● Branch and bound, jika dalam proses diatas, separuh jalan suatu alternatif sudah diduga tidak mungkin ada solusi, maka alternatif tersebut ditinggal (bound), dan dilanjutkan dengan menguji alternatif lain (branch)○ Mencari jalur dari a ke b dengan total biaya tidak lebih dari c

HeapSortPenyempurnaan Selection sort

Heap prioritas

● FindMax sangat efisien untuk satu kali operasi○ (karena semua data -kan harus diperiksa)

● Tetapi jika dilakukan berulang-kali, pengulangan proses mungkin terjadi○ Perlu metoda lain untuk menghindari hal tersebut

● Heap adalah pohon biner dengan properti berikut:○ Nilai tersimpan setiap node tidak lebih kecil dari nilai kedua anak-nya○ Dapat disimpulkan, root pastilah mempunyai nilai terbesar○ Semua daun, yaitu node tanpa anak, otomatis memenuhi syarat tersebut○ Perhatikan tidak ada syarat bahwa anak kiri harus lebih kecil/besar dari anak yang kanan

Struktur Heap dapat disimpan dalam Array

Satu Node Salah Posisi ⇓

● Keseluruhan heap hampir benar, kecuali satu node● Nilai node tersebut (mungkin) lebih kecil dari salah satu atau kedua anaknya

● Lakukan operasi swap dengan anak-nya● Tapi mungkin perlu propagasi, jika setelah swap, nilainya juga masih lebih

kecil dari nilai cucu-nya


Perbaiki Heap ⇓

{ p pointer/indeks ke satu2nya node yang melanggar properti heap nilai pada arr[p] lebih kecil dari nilai (salah satu) anaknya}proc FixHeap( arr[1..n], p )

bigger := pmore2fix := truewhile more2fix do

more2fix := falsekr := p*2kn := kr + 1if kr < n and arr[kr] > arr[bigger] then bigger := krif kn < n and arr[kn] > arr[bigger] then bigger := knif p <> bigger then

arr[p] ⇄ arr[bigger]p := biggermore2fix := true

endifendwhile

endproc


● Hanya node arr[p] yang mungkin melanggar properti heap● arr[1..p-1] dan arr[p+1]..n], 1 < p < n, memenuhi properti heap

● Setelah satu iterasi:○ Properti node p diperbaiki○ Mungkin node 2p atau 2p+1 melanggar properti○ Invarian tetap berlaku (tidak lebih dari satu node yang melanggar properti)

● Saat terminasi:○ Properti node p tidak melanggar, atau○ p adalah leaf (2p dan 2p+1 lebih besar dari n)○ Maka heap kembali benar untuk semua node

● Bagaimana jika ada lebih dari satu node yang melanggar properti heap?


● Kompleksitas bergantung pada jumlah iterasi (s.d. more2fix menjadi false)● Setiap iterasi nilai p berubah menjadi 2p atau 2p+1,

○ sampai dengan p adalah leaf, atau○ arr[p] bukan node yang salah lagi

● Jumlah iterasi adalah jarak dari p awal s.d. leaf dalam pohon heap○ yaitu sebanyak . . .

Pohon Biner, Leaf, Tinggi(h), Kedalaman(d)1=root

n nodes →⌈½n⌉ leaves

p hTREE

hp

ooo

Pohon Biner, Leaf, Tinggi(h), Kedalaman(d)

● Pohon biner lengkap (CBT) merupakan pohon biner yang hampir sempurna○ semua tingkatan berisi node○ pada tingkat paling bawah, node mengisi sayap kiri lebih dulu (lihat gambar sebelumnya)

● Jika CBT mempunyai n node maka○ ⌈½n⌉ adalah leaf (Buktikan dengan menggunakan induksi)○ Tinggi pohon adalah jarak/jumlah edge dari root ke leaf terbawah, yaitu h = ⌊lg(n)⌋○ Kedalaman suatu node p adalah jarak/jumlah edge dari root ke p, yaitu d(p) = ⌊lg(p)⌋○ Maka tinggi node p adalah tinggi pohon dikurang kedalaman p, atau h(p) = h - d(p) ○ Jumlah node pada level i ada sebanyak ni, dimana i=0..h, kecuali pada level terbawah




● Maksimum jumlah iterasi adalah jarak dari p awal s.d. leaf dalam pohon heap

○ yaitu sebanyak tinggi p, atau T(n,p) = h - d(p) = ⌊lg(n)⌋ - ⌊lg(p)⌋○ Kasus terburuk terjadi jika node salah posisi adalah root, sehingga T(n,p)=T(n,1)=⌊lg(n)⌋○ Kasus terbaik terjadi ketika node salah posisi adalah parent dari leaf, atau ¼n < p < ½n,

sehingga T(n,p) = ⌊lg(n)⌋ - ⌊lg(¼n)⌋ .. ⌊lg(n)⌋ - ⌊lg(½n)⌋ = c, dimana c=1..2○ Kasus rerata . . .




● Maksimum jumlah iterasi adalah jarak dari p awal s.d. leaf dalam pohon heap

○ yaitu sebanyak tinggi p, atau T(n,p) = h - d(p) = ⌊lg(n)⌋ - ⌊lg(p)⌋○ Kasus terburuk terjadi jika node salah posisi adalah root, sehingga T(n,p)=T(n,1)=⌊lg(n)⌋○ Kasus terbaik terjadi ketika node salah posisi adalah parent dari leaf, atau ¼n < p < ½n,

sehingga T(n,p) = ⌊lg(n)⌋ - ⌊lg(¼n)⌋ .. ⌊lg(n)⌋ - ⌊lg(½n)⌋ = c, dimana c=1..2○ Kasus rerata dengan asumsi node p mungkin node mana saja diluar leaf adalah

T(n,p) = (∑i=0..h-12i )/(½n) = (1+2..+2h-1)/(½n) = (2h)/(½n) = (n)/(½n) = 2

Satu Node Salah Posisi ⇑

Perbaiki Heap ⇑

{ p pointer/indeks ke satu2nya node yang melanggar properti heap nilai pada arr[p] lebih besar dari nilai parent-nya }proc UpFixHeap( arr[1..n], p )

{ silakan dibuat algoritmanya }

endproc

● Buat algoritma versi upfix● Buktikan kebenaran algoritma ini● Hitung kompleksitasnya

Bangun Heap

● Diberikan sejumlah data dalam array (dan belum membentuk heap)● Susun data dalam array tersebut agar memenuhi properti heap!

● Perbaiki heap hanya berlaku jika yang tidak memenuhi properti heap hanya 1 node saja.

Bangun Heap

● Diberikan sejumlah data dalam array (dan belum membentuk heap)● Susun data dalam array tersebut agar memenuhi properti heap!

● Keadaan awal:○ Semua leaf memenuhi properti heap○ Ada sebanyak ⌈½n⌉ leaf dalam pohon biner dengan n node

● Selanjutnya, tambahkan satu persatu node tersisa menggunakan algoritma perbaiki heap

Bangun Heap

Bangun Heap

proc ConstructHeap( arr[1..n] )i := ⌊½n⌋while i > 1 do

FixHeap(arr[1..n], i)i := i - 1

endwhileendproc

Bangun Heap

proc ConstructHeap( arr[1..n] )i := ⌊½n⌋while i > 1 do

FixHeap(arr[1..n], i)i := i - 1

endwhileendproc

● Bukti kebenaran?○ Gunakan metoda induksi

● Perhitungan kompleksitas?○ TCONSTRUCTHEAP(n)=O(n)○ Bdk perhitungan rerata perbaikan heap

Heap Sort, Modifikasi Selection Sort

● FindMax diganti dengan struktur heap● Nilai maksimum adalah root dari heap● Perlu proses perbaikan heap setiap kali nilai maksimum diambil dari heap● Perlu proses awal untuk membangun heap

Heap Sort

proc HeapSort( arr[1..n] )ConstrutHeap(arr[1..n])i := nwhile i > 1 do

arr[i] ⇄ arr[1]FixHeap(arr[1..i], 1)i := i - 1

endwhile

Diciptakan oleh:

● R.W. Floyd (1964) Treesort● J.W.J WiIliams(1964) Heapsort

Heap Sort

proc HeapSort( arr[1..n] )ConstructHeap(arr[1..n])i := nwhile i > 1 do


endwhile

Heap Sort vs. Selection Sort

proc HeapSort( arr[1..n] )ConstructHeap(arr[1..n])i := nwhile i > 1 do


endwhileendproc

proc SelectionSort( arr[1..n] )

i := nwhile i > 1 do

imax := FindMax(arr[1..i])arr[i] ⇄ arr[imax]i := i - 1

endwhileendproc

Kompleksitas HeapSort

THeapSort(n) = TConstructHeap(n) + ∑i=2..nTFixHeap(i,1)

= O(n) + ∑i=2..nO(lg(i)-lg(1))

= O(n) + ∑i=2..nO(lg(i)) = O(n+½nlg(n)) = O(nlg(n))

Metoda Pengurutan Cepat Lainnya

Berbagai Algoritma Sorting

● https://en.wikipedia.org/wiki/Sorting_algorithm

Garis Besar Algoritma QuickSort

proc QuickSort( A[left..right] )if left < right then

p := Pivot(A[left..right])pv := A[p]A[left] ⇔ A[p]k := QuickSplit(A[left+1..right],A[left])A[left] ⇔ A[k]Quicksort(A[left..k-1])Quicksort(A[k+1..right])

endif

● Pilih suatu data acuan (pivot)● Bagi data dalam 2 kelompok

○ Data kelompok kiri tidak lebih besar dari p○ Kelompok kanan lebih besar dari p○ Data di kelompok kiri bernilai lebih kecil dari data di

kelompok kanan● Ulangi proses yang sama terhadap masing2 kelompok● Gabungan kedua kelompok membentuk data terurut

Pemilihan Pivot QuickSort

● Idealnya adalah nilai median, tetapi median mudah dicari jika sudah terurut○ Mungkinkah mencari median tanpa mengurutkan data lebih dulu?

● Jika diketahui data terdistribusi uniform, semua data mempunyai kesempatan yang sama sebagai median○ Ambil saja nilai tengah dari kumpulan data tersebut○ Ambil saja secara acak salah satu nilai dari kumpulan data tersebut?

● Kalau begitu, bisa saja ambil data yang pertama (atau terakhir) dari list○ Sederhana kan? Adakah kekurangan/kelemahan pilihan ini yang perlu diperhatikan?

Membagi dua data dalam QuickSort

func QuickSplit( A[left..right], pv )i := leftk := rightwhile i < k do

while i < k and A[i] < pv doi := i + 1

endwhilewhile i < k and A[k] > pv do

k := k - 1endwhileif i < k then

A[i] ⇔ A[k]endif

endwhilereturn k

QuickSortproc QuickSort( A[left..right] )

if left < right thenp := Pivot(A[left..right])pv := A[p]A[left] ⇔ A[p]i := left + 1k := rightwhile i < k do

while i < k and A[i] < pv doi := i + 1

while i < k and A[k] > pv dok := k - 1

if i < k thenA[i] ⇔ A[k]

endwhileA[left] ⇔ A[k]Quicksort(A[left..k-1])Quicksort(A[k+1..right])

endif

● Pembuktian dengan induksi● Loop invariant

○ Rekursif : … ○ Loop luar: … ○ Loop dalam: …

QuickSort

● Rekursif (if left < right then … )○ L.I.: Data terbagi dalam 3 group dengan relasi: A[..left-1] < A[left..right] < A[right+1..]○ Basis, hipotesis, induksi: …

● Loop luar (while i < k do … )○ L.I.: A[left..i-1] < A[k+1..right]

● Loop dalam (while i < k and A[i] < pv do … )○ L.I.: A[left..i-1] < pv

● Loop dalam (while i < k and A[k] > pv do … )○ L.I.: A[k+1..right] > pv

C.A.R Hoare menciptakan Quicksort (1959)

Analisis Waktu QuickSort

proc QuickSort( A[left..right] )if left < right then

p := Pivot(A[left..right])pv := A[p]A[left] ⇔ A[p]k := QuickSplit(A[left+1..right], pv)A[left] ⇔ A[k]Quicksort(A[left..k-1])Quicksort(A[k+1..right])

endif

● Misalkan A[1..n]c1 ; left > right

● TQSORT(n) = TQSORT(k-left)+TQSORT(right-k) + c2n ; left < right

● Nilai k mempengaruhi TQSORT(n)

Analisis Waktu QuickSort

● Jika k-left atau right-k ≈ konstan c3, maka● TQSORT(n) = T(c3) + T(n-c3) + c2n ≈ (c2n/c3) = 𝚶(n)

● Jika k-left dan right-k ≈ ½n, maka● TQsort(n) = 2T(½n) + c2n ≈ c2n lg n = 𝚶(n lg n)

● Jika k-left dan right-k ≈ c4n, maka● TQsort(n) = T(c4n) + T((1-c4)n) + c2n

≈ (c2n/lg c4) lg n ≈ c5n lg n = 𝚶(n lg n)

Randomization QuickSort

func Pivot( A[left..right] )return := (left + right) / 2

func Pivot( A[left..right] )return := left

func Pivot( A[left..right] )return := Random(left, right)

Algoritma Median

● Algoritma cepat pencarian median untuk pivot, 𝚶(n)● Modifikasi algoritma quicksort untuk mencari median atau data posisi ke-i

Analisis Batas Bawah Problem Komputasi

Pohon Keputusan Proses Sorting

● Visualisasi trace proses (pembandingan dalam sorting)● Percabangan pada node merupakan hasil apakah x<y, atau sebaliknya● Membentuk pohon biner● Leaf merupakan semua permutasi dari data asal

○ jika tidak semua, maka . . .

● Jalur dari root ke leaf merupakan rangkaian operasi yang digunakan untuk mencapai satu permutasi tersebut.

● Maka tinggi pohon menjadi representasi kompleksitas sorting tersebut

Pohon Keputusan Selection Sort 3 Data

● Ada beberapa operasi yang duplikasi

Pohon Keputusan Optimal Analisis Batas Bawah

● Berapa banyak kebutuhan minimum operasi komparasi?● Kedalaman dari pohon keputusan dapat menunjukan jumlah operasi

komparasi minimum yang diperlukan suatu proses (sorting)● Jumlah permutasi untuk n data adalah p(n) = . . .

○ misal 3 data: (a,b,c) (a,c,b) (b,a,c) (b,c,a) (c,a,b) (c,b,a) ⇒ ada sebanyak . . .

● Tinggi pohon biner dengan p(n) leaf adalah h(p(n)) = . . .

Analisis Batas Bawah

● Berapa banyak kebutuhan minimum operasi komparasi?● Kedalaman dari pohon keputusan dapat menunjukan jumlah operasi

komparasi minimum yang diperlukan suatu proses (sorting)● Jumlah permutasi untuk n data adalah p(n) = n!

○ misal 3 data: (a,b,c) (a,c,b) (b,a,c) (b,c,a) (c,a,b) (c,b,a) ⇒ ada sebanyak 3!=3.2=6

● Tinggi pohon biner dengan p(n) leaf adalah h(p(n)) = lg(n!) = . . . ?○ Ingat n! < nn = n.n. . . n○ Sehingga lg(n!) < lg(nn) = n.lg(n)○ Tapi ini berarti TSORT(n) = h(p(n)) = 𝚶(n.lg(n))○ Sedangkan yang dicari adalah TSORT(n) = 𝛀(n.lg(n))

Batas Bawah KompleksitasProblem Sorting

TSORT = 𝝮(lg(n!))

½nn/2 < n! < nn

TSORT > c.lg(½nn/2) ; c positif = ½cn.(lg(n)-lg(2)) = ½cn.lg(n) - ½cn = ¼cn.lg(n) + (¼cn.lg(n)-½cn) > ¼cn.lg(n) ; n > 4

TSORT = 𝝮(n.lg(n)) ; untuk n > 4

(¼cn.lg(n)-½cn) > 0¼cn.lg(n) > ½cnn.lg(n) > 2nlg(n) > 2

atau n > 4

Konsekuensi

● Dengan komparasi tidak ada metoda sorting lebih baik dari 𝝮(n.lg(n)) ● Sorting dapat lebih cepat bila tidak menggunakan operasi komparasi

○ Ada batasan kemampuan/kasus○ Perlu tahu karakteristik domain data Pengurutan dengan waktu Linear

Counting Sort

Diciptakan oleh H.H. Seward (1954)

1. Hitung/Akumulasi kemunculan setiap elemen data○ Data boleh duplikat

2. Buat informasi kumulatif dari hasil akumulasi○ yaitu kum(j) = ∑i=terkecil..jacc(i); j = terkecil+1 .. terbesar

3. Elemen data v berada pada posisi terurut di kum(v)○ Mulai dari elemen data paling akhir, agar hasil pengurutan stabil○ Setelah penempatan decrement kum(v), untuk posisi elemen sebelumnya

Counting Sort

Counting Sort

prosedur CountingSort( arr[1..n] )acc[terkecil..terbesar] = 0for i = 1 to n do

acc[arr[i]]++end-forfor j = terkecil+1 to terbesar do

acc[j] += acc[j-1]end-forfor i = n downto 1 do

dest[acc[arr[i]]] = arr[i]acc[arr[i]]--

end-forarr = dest

end-prosedur

Kompleksitas Counting Sort

● Untuk rentang data k=terbesar-terkecil+1,○ Inisialisasi akumulator acc[] perlu O(k)

● Dengan data sebanyak n○ Pencacahan isi arr[] adalah O(n)

● Akumulasi hasil pencacahan di acc[] adalah O(k)● Distribusi data dari arr[] melalui acc[] ke dest[] adalah O(n)● Total waktu adalah O(k+n)● Jika k = O(n) maka Countingsort adalah O(n)

Observasi Counting Sort

● Kinerja Counting sort bergantung rentang data yang akan diurutkan● Counting sort bersifat stabil

Metoda Sorting Waktu Linear Lain

● Radix sort○ Urut berdasarkan (kelompok) digit, dimulai digit kecil○ Perkelompok digunakan sorting stabil, misalnya counting sort○ Digunakan untuk mengurutkan kartu (mekanik)

● Bucket sort○ Bagi data dalam beberapa kelompok○ Ekspektasi jumlah data dalam satu kelompok/bucket adalah kecil (konstan)○ Gunakan sorting biasa untuk setiap bucket, misalnya insertion sort

Radixsort

pertemuan · ada cara yang lebih cerdik? contoh: mencari nilai maksimum dalam array strategi...

Documents