[Ringkasan Kuliah IF5152-Analisis Algoritma]: Pembuktian Kebenaran Algoritma, Live @ 7607


Postingan ini merupakan ringkasan kuliah yang diambil secara  ‘live’ di ruang kuliah 7607 Labtek V, Informatika ITB, oleh Pak Rila Mandala.  B-) Semoga bisa kyk gini lagi di kuliah2 berikutnya *itupun kalo dibolehin oleh dosennya* :p

Pembuktian Kebenaran Algoritma

Pembuktian kebenaran algoritma tidak dapat dilakukan secara eksperimental. Maksudnya adalah kita tidak dapat mengklaim bahwa algoritma tersebut benar (sesuai yg diinginkan) dengan cara mencoba sekian banyak data masukan. Karena algoritma dapat dianggap benar apabila berjalan dengan benar untuk semua masukan.

Adapun cara-cara pembuktian kebenaran alogritma yg pernah diusulkan :

  • Induksi Matematika
  • Computational Logic (Logika Propoposisi dan Logika Predikat Orde Pertama)

Salah satu cara teoritis untuk menjamin kebenaran suatu algoritma yaitu assertion (asersi)

Assertion

  • Pernyataan yang menyatakan state/kondisi dari tahap2 yang dilalui pada suatu algoritma
  • Asersi dapat berubah-ubah sesuai dengan perintah yang dijalankan
  • Asersi awal: kondisi awal sebelum menjalankan algoritma
  • Asersi akhir: tujuan dari algoritma tsb
  • Jika setelah perintah-perintah yang dijalankan dan hasil akhirnya tidak sesuai dengan asersi akhir (walaupun asersi awalnya benar) maka algoritma tersebut ‘salah’, or vice versa

Contoh Asersi

Asersi awal {P} : {bokek, penampilan pas-pasan}

Perintah S1 – Dipermak di salon

Asersi 1 {Q} : {bokek, ganteng}

………

Aserso Akhir {R} : {ganteng, kaya, ditaksir miss Universe}

*(doh) si bapak ngasih contoh kasus yang aneh2 aja. X|*

Aturan-Aturan Dasar Asersi

  1. ({P} s {Q} ,{P} => {R}) <=> {R} s {Q} (Ket: “Jika dari asersi {P} dikerjakan perintah s menjadi asersi {Q}, dan diberikan info bahwa jika {P} benar, maka {R} benar”, maka pernyataan tersebut ekivalen dengan  “dari asersi {R} dikerjakan perintah s akan menjadi asersi {Q}”)
  2. ({P} s {Q} , {Q} => {R}) <=> {P} s {R} (Ket: “Jika dari asersi {P} dikerjakan perintah s menjadi asersi {Q}, dan diberikan info bahwa jika {Q} benar, maka {R} benar”, maka pernyataan tersebut ekivalen dengan  “dari asersi {P} dikerjakan perintah s akan menjadi asersi {R}”)
  3. {P0} s1{P1}, {P1} s2 {P2} ,…, {Pn-1} sn {Pn} <=> {P0} si {Pn} (Ket: ‘keknya sama dengan fungsi dari asersi itu sendiri’)

Aturan Asersi untuk Perulangan

{P Λ B} s {P}, {P Λ ~B} => {B} ≡ {P} While B do S {Q}

(Ket: untuk membuktikan kebenaran potongan algortima perulangan, harus dibuktikan bahwa {P Λ B} s {P}, {P Λ ~B}

Aturan Asersi untuk If.. Else..

{P Λ B} s1 {Q}, {P Λ ~B} s2 {Q} ≡ {P} if B then s1 then s2 {Q}

(Ket: untuk membuktikan kebenaran potongan algortima if..else.. harus dibuktikan bahwa {P Λ B} s1 {Q}, {P Λ ~B} s2 {Q}

Sekian dulu.. cuma itu yang berhasil ku catat😛

2 thoughts on “[Ringkasan Kuliah IF5152-Analisis Algoritma]: Pembuktian Kebenaran Algoritma, Live @ 7607

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s