ALGORITMA

ALGORITMA

Algoritma : urutan langkah-langkah untuk memecahkan suatu masalah Algoritma adalah prosedur komputasi yang terdefinisi dengan baik yang menggunakan beberapa nilai sebagai masukan dan menghasilkan beberapa nilai yang disebut keluaran. Jadi, algoritma adalah deretan langkah komputasi yang mentransformasikan masukan menjadi keluran.

Algoritmik: Studi mengenai algoritma.
• Notasi apapun dapat digunakan untuk menuliskan algoritma asalkan mudah dibaca dan dipahami.
Algoritma dapat ditulis dengan notasi:
1. Bagan alir (flow chart)
2. Kalimat-kalimat deskriptif
3. Pseudo-code (gabungan antara bahasa alami
dengan bahasa pemrograman)
Alat ukur kemangkusan algoritma:
1. Kompleksitas waktu, T(n)
2. Kompleksitas ruang, S(n)
• n = ukuran masukan yang diproses oleh algoritma
• T(n) : jumlah operasi yang dilakukan untuk menjalankan sebuah algoritma sebagai fungsi dari ukuran masukan n.
• S(n): ruang memori yang dibutuhkan algoritma sebagai fungsi dari ukuran masukan n.

Kompleksitas waktu asimptotik:
- perkiraan kasar kebutuhan waktu algoritma dengan meningkatnya nilai n
- menyatakan laju pertumbuhan waktu, bukan menyatakan jumlah operasi dasar
Sesungguhnya.
Strategi algoritmik : pendekatan umum untuk memecahkan masalah secara algoritmis yang dapat diterapkan pada beraneka ragam masalah guna mencapai tujuan
Klasifikasi Strategi Algoritmik:
1. Strategi solusi langsung (direct solution strategies)
- Algoritma Brute Force
- Algoritma Greedy
2. Strategi berbasis pencarian pada ruang status (state-space base strategies)
- Algoritma Backtracking
- Algoritma Branch and Bound
3. Strategi solusi atas-bawah (top-down solution strategies)
- Algoritma Divide and Conquer.
4. Strategi solusi bawah-atas (bottom-up solution strategies)
- Dynamic Programming.

Definisi Brute Force
• Brute force : pendekatan yang lempang (straightforward) untuk memecahkan suatu masalah
• Biasanya didasarkan pada:
– pernyataan masalah (problem statement)
– definisi konsep yang dilibatkan.
• Algoritma brute force memecahkan masalah dengan
– sangat sederhana,
– langsung,
– jelas (obvious way).

Karakteristik Algoritma Brute Force
1. Algoritma brute force umumnya tidak “cerdas” dan tidak mangkus, karena ia membutuhkan jumlah langkah yang besar dalam penyelesaiannya. Kata “force” mengindikasikan “tenaga” ketimbang “otak” Kadang-kadang algoritma brute force disebut juga algoritma naif (naïve algorithm).
Algoritma brute force lebih cocok untuk masalah yang berukuran kecil.
Pertimbangannya:
- sederhana,
- implementasinya mudah
Algoritma brute force sering digunakan sebagai basis pembanding dengan algoritma yang lebih mangkus. Meskipun bukan metode yang mangkus, hampir semua masalah dapat diselesaikan dengan algoritma brute force. Sukar menunjukkan masalah yang tidak dapat
diselesaikan dengan metode brute force. Bahkan, ada masalah yang hanya dapat diselesaikan dengan metode brute force. Contoh: mencari elemen terbesar di dalam senarai.

Kekuatan:
1. Metode brute force dapat digunakan untuk memecahkan hampir sebagian
besar masalah (wide applicability).
2. Metode brute force sederhana dan mudah dimengerti.
3. Metode brute force menghasilkan algoritma yang layak untuk beberapa
masalah penting seperti pencarian, pengurutan, pencocokan string,
perkalian matriks.
4. Metode brute force menghasilkan algoritma baku (standard) untuk tugas –
tugas komputasi seperti penjumlahan/perkalian n buah bilangan,
menentukan elemen minimum atau maksimum di dalam tabel (list).

Kelemahan:
1. Metode brute force jarang menghasilkan algoritma yang mangkus.
2. Beberapa algoritma brute force lambat sehingga tidak dapat diterima.
3. Tidak sekontruktif/sekreatif teknik pemecahan masalah lainnya.
• Ken Thompson (salah seorang penemu Unix) mengatakan: “When in doubt, use brute force”, faktanya kernel Unix yang asli lebih menyukai algoritma yang sederhana dan kuat (robust) daripada algoritma yang cerdas tapi rapuh.

Algoritma greedy merupakan metode yang paling populer untuk memecahkan persoalan optimasi.
• Persoalan optimasi (optimization problems):
è persoalan mencari solusi optimum.
• Hanya ada dua macam persoalan optimasi:
1. Maksimasi (maximization)
2. Minimasi (minimization)
Greedy = rakus, tamak, loba, …
• Prinsip greedy: “take what you can get now!”.
• Algoritma greedy membentuk solusi langkah per langkah (step by step).
• Pada setiap langkah, terdapat banyak pilihan yang perlu dieksplorasi.
• Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik
dalam menentukan pilihan. Pada setiap langkah, kita membuat pilihan optimum lokal (local optimum), dengan harapan bahwa langkah sisanya mengarah ke solusi optimum global (global optimm).
Algoritma greedy adalah algoritma yang memecahkan masalah langkah per langkah; pada setiap langkah:
1. mengambil pilihan yang terbaik yang dapat diperoleh pada saat itu tanpa
memperhatikan konsekuensi ke depan (prinsip “take what you can get now!”)
2. berharap bahwa dengan memilih optimum lokal pada setiap langkah akan berakhir dengan optimum global. Warning: Optimum global belum tentu merupakan solusi optimum (terbaik), tetapi sub-optimum atau pseudooptimum.

Alasan:
1. Algoritma greedy tidak beroperasi secara menyeluruh terhadap semua
alternatif solusi yang ada (sebagaimana pada metode exhaustive search).
2. Terdapat beberapa fungsi SELEKSI yang berbeda, sehingga kita harus memilih fungsi yang tepat jika kita ingin algoritma menghasilkan solusi optiamal.
Jadi, pada sebagian masalah algoritma greedy tidak selalu berhasil memberikan solusi yang optimal.