Kuliah Desain dan Analisis Algoritma: Algorithm Correctness

Pengantar

• Definisi: Algorithm correctness (kebenaran algoritma) adalah bagaimana cara kita tahu suatu algoritma itu benar.
• Menggunakan sedot (pseudo-code) untuk menjelaskan algoritma, mirip dengan bahasa pemrograman seperti C atau Java.
  • Contoh: Menukar dua variabel x dan y cukup dengan deskripsi sederhana "tukar".

Insertion Sort

Definisi

• Insertion Sort adalah algoritma yang digunakan untuk mengurutkan data dalam array.
• Karakteristik:
  • In-place: Data terurut di dalam array yang sama tanpa memerlukan array tambahan yang besar.
  • Stable: Urutan relatif data duplikat tidak berubah.

Implementasi Insertion Sort

1. Nama Algoritma: Insertion Sort
2. Input: Sebuah array A.
3. Proses:
   • Gunakan for-loop untuk iterasi elemen di array.
   • Key: Ambil elemen yang akan disisipkan.
   • Geser elemen yang lebih besar ke kanan hingga menemukan tempat yang tepat untuk key.
   • Sisipkan key pada posisi yang tepat.

Contoh Eksekusi

• Array awal: [5, 2, 4, 6, 1, 3]
• Proses:
  • Iterasi 1: [2, 5, 4, 6, 1, 3]
  • Iterasi 2: [1, 2, 4, 5, 6, 3]
  • Iterasi 3: [1, 2, 3, 4, 5, 6]

Loop Invariant

Definisi

• Loop invariant adalah pernyataan yang benar sebelum dan setelah setiap iterasi loop.

Tiga Hal yang Perlu Dibuktikan

1. Initialization: Benar sebelum loop dimulai.
2. Maintenance: Jika benar sebelum iterasi, tetap benar setelah iterasi.
3. Termination: Saat loop berakhir, invariant memberikan informasi tentang kebenaran algoritma.

Teknik Pembuktian Kebenaran Algoritma

Postcondition

• Postcondition adalah kondisi yang harus dipenuhi setelah eksekusi algoritma.
• Contoh postcondition untuk Insertion Sort: array harus terurut setelah eksekusi.

Penggunaan Loop Invariant

• Menggunakan loop invariant untuk memastikan bahwa algoritma memberikan hasil yang diharapkan.

Rasio Multiplikasi

Deskripsi Algoritma

• Menghitung hasil kali dua bilangan asli A dan B.
• Memvisualisasikan dengan dua kolom: satu untuk A yang dibagi dua, satu untuk B yang dikali dua.
• Menjumlahkan baris yang memiliki nilai genap pada kolom A.

Implementasi Algoritma

1. Inisialisasi total = 0.
2. Lakukan loop hingga x = 0.
3. Jika x ganjil, tambahkan y ke total.
4. Pembagian x dengan 2 dan kalikan y dengan 2.
5. Return total sebagai hasil.

Rancangan Algoritma

Menggunakan Loop Invariant

• Untuk menghitung jumlah elemen dalam array:
  1. Inisialisasi total = 0.
  2. Gunakan loop dengan kondisi j tidak sama dengan n.
  3. Tambahkan elemen array ke total saat iterasi.

Kesimpulan

• Kebenaran algoritma dapat dibuktikan menggunakan loop invariant.
• Penting untuk memastikan bahwa setiap bagian dari algoritma berfungsi dengan benar dan memberikan hasil yang diharapkan.