Penyelesaian Masalah Secara Algoritmik

Penyelesaian Masalah Secara Algoritmik dan Karakteristik Formal Algoritma

Materi ini mengeksplorasi metodologi analitis dalam mentransformasikan problem riil menjadi algoritma komputasi yang deterministik, andal, dan dapat diverifikasi kebenarannya.

1. Karakteristik Formal Algoritma (Kriteria Knuth)

Sebuah sekuens instruksi hanya dapat dikategorikan sebagai algoritma sah jika memenuhi 5 kriteria formal Donald Knuth:

• Finiteness (Keterbatasan): Algoritma wajib berhenti (terminate) setelah mengeksekusi sejumlah langkah berhingga. Algoritma tidak boleh terjebak dalam infinite loop tanpa kondisi terminasi yang dapat dicapai.
• Definiteness (Kepastian): Setiap langkah instruksi harus didefinisikan secara presisi, jelas, dan tanpa ambiguitas semantik.
• Input (Masukan): Memiliki nol atau lebih besaran masukan yang disuplai sebelum algoritma beroperasi.
• Output (Keluaran): Menghasilkan minimal satu luaran yang memiliki korelasi kausal langsung dengan masukan.
• Effectiveness (Efektivitas): Setiap instruksi harus cukup sederhana (primitive) sehingga secara prinsip dapat dikerjakan secara manual oleh manusia menggunakan pena dan kertas dalam waktu yang wajar.

2. Metodologi Pendekatan Masalah (*Problem-Solving Strategies*)

1. Top-Down Stepwise Refinement: Memulai dari gambaran abstrak tingkat tinggi, lalu menurunkan tiap komponen menjadi langkah-langkah implementatif yang semakin konkret.
2. Bottom-Up Synthesis: Mengembangkan komponen dasar yang sudah teruji kehandalannya, lalu merangkainya menjadi arsitektur sistem yang kompleks.
3. Analisis Kompleksitas Dasar: Memahami konsep ketergantungan sumber daya komputasi terhadap ukuran masukan $N$, membedakan pertumbuhan linier $\mathcal{O}(N)$ dengan pertumbuhan kuadratik $\mathcal{O}(N^2)$.