Analisis & Algoritma


copas tulisan orang🙂

Pengenalan Desain dan Analisis Algoritma

Sebagai salah satu dasar dari ilmu komputer, algoritma merupakan hal yang sangat penting untuk dikuasai oleh orang-orang yang berkecimpung di dunia ilmu komputer, dari peneliti sampai ke praktisi. Tentunya penguasaan akan algoritma tidak cukup hanya sampai pada tahap mengetahui dan menggunakan algoritma yang tepat untuk menyelesaikan masalah. Seorang yang mengerti ilmu komputer harus juga mampu merancang dan mengembangkan sebuah algoritma berdasarkan masalah-masalah yang ditemui. Tulisan ini bertujuan untuk memberikan pengertian mendasar mengenai perancangan (desain) dan pengembangan algoritma, agar pembaca dapat tidak hanya menggunakan algoritma yang sudah ada, tetapi juga merancang dan mengembangkan algoritma sesuai dengan masalah yang akan diselesaikan.

Selain memberikan dasar perancangan, tulisan ini juga membahas jenis-jenis algoritma yang ada, untuk kemudian melakukan analisa terhadap beberapa algoritma untuk setiap jenisnya. Analisis algoritma dilakukan dengan tujuan utama agar pembaca dapat mengambil keputusan yang tepat dalam memilih algoritma untuk solusi.

Apa itu Algoritma?

Sebelum membahas mengenai perancangan ataupun analisis algoritma, tentunya kita terlebih dahulu harus mendefinisikan arti dari “Algoritma”. Apa itu algoritma?

Algoritma merupakan langkah-langkah (prosedur) yang harus dilakukan untuk menyelesaikan sebuah masalah.

Program komputer umumnya dibangun dengan menggunakan beberapa algoritma untuk menyelesaikan sebuah permasalahan. Misalnya sebuah program pencarian teks seperti grep akan memerlukan algoritma khusus untuk membaca dan menelusuri file, algoritma lain untuk mencari teks yang tepat di dalam file, dan satu algoritma lagi untuk menampilkan hasil pencarian ke pengguna.

Dalam mendefinisikan algoritma, kita harus dapat mendefinisikan tiga hal utama dengan jelas, yaitu:

  1. Masalah, yaitu sebuah persoalan yang ingin diselesaikan oleh sebuah algoritma.
  2. Masukan, yaitu contoh data atau keadaan yang menjadi permasalahan.
  3. Keluaran, yaitu bentuk akhir dari data atau keadaan setelah algoritma diimplementasikan ke masukan. Keluaran merupakan hasil ideal yang diinginkan dan dianggap telah menyelesaikan masalah.

Contoh (dan Solusi) Algoritma

Contoh dari sebuah definisi algoritma yang benar adalah sebagai berikut:

Masalah
Pengurutan sekumpulan nilai yang bernilai acak.
Masukan
Serangkaian data berukuran $n$.
Keluaran
Serangkaian data berukuran $n$, dengan urutan a1a2a3...an1an, di mana ax adalah data pada posisi x dalam rangkaian.

Data masukan yang diinginkan merupakan rangkaian data, tanpa memperdulikan jenis data (angka, huruf, teks, dan lainnya). Contoh dari nilai masukan adalah [2, 5, 1, 3, 4] ataupun ["Doni", "Andi", "Budi", "Clara"]. Data keluaran yang diinginkan, tentunya adalah data masukan yang telah terurut: [1, 2, 3, 4, 5] dan["Andi", "Budi", "Clara", "Doni"].

Untuk menyelesaikan masalah yang diberikan di atas, kita dapat menggunakan algoritma insertion sort. Kode di bawah menunjukkan implementasi insertion sort pada bahasa pemrograman python:

def insertion_sort(data):
    for i in range(0, len(data)):
        insert_val = data[i]
        hole_pos = i

        while hole_pos > 0 and insert_val < data[hole_pos - 1]:
            data[hole_pos] = data[hole_pos - 1]
            hole_pos = hole_pos - 1

        data[hole_pos] = insert_val

Implementasi insertion sort yang diberikan di atas menunjukkan bahwa pada dasarnya sebuah prosedur yang harus dijalankan untuk mengubah data masukan menjadi data keluaran, sehingga masalah dapat terselesaikan.

Algoritma yang Baik

Kita telah mengetahui dengan jelas makna dari algoritma, sehingga pertanyaan selanjutnya adalah algoritma seperti apa yang dapat dikatakan sebagai algoritma yang baik? Pada umumnya kita tidak ingin menggunakan algoritma yang salah untuk menyelesaikan masalah karena hal ini dapat menyebabkan masalah tidak diselesaikan dengan optimal, atau lebih buruknya, tidak diselesaikan sama sekali.

Sebuah algoritma yang baik memiliki sifat-sifat berikut:

  1. Benar, di mana algoritma menyelesaikan masalah dengan tepat, sesuai dengan definisi masukan / keluaran algoritma yang diberikan.
  2. Efisien, berarti algoritma menyelesaikan masalah tanpa memberatkan bagian lain dari apliikasi. Sebuah algoritma yang tidak efisien akan menggunakan sumber daya (memori, CPU) yang besar dan memberatkan aplikasi yang mengimplementasikan algoritma tersebut.
  3. Mudah diimplementasikan, artinya sebuah algoritma yang baik harus dapat dimengerti dengan mudah sehingga implementasi algoritma dapat dilakukan siapapun dengan pendidikan yang tepat, dalam waktu yang masuk akal.

Pada prakteknya, tentunya ketiga hal tersebut tidak dapat selalu tercapai. Kebenaran dari sebuah algoritma umumnya selalu dapat dicapai, setidaknya untuk nilai-nilai masukan umum, tetapi efisiensi dan kemudahan implementasi tidak selalu didapatkan. Begitupun, tentunya kita harus tetap berusaha mencapai ketiga hal tersebut dalam merancang sebuah algoritma.

Pembuktian Kebenaran Algoritma

Kita telah mengetahui bahwa sebuah algoritma yang baik adalah algoritma yang benar, efisien, dan mudah diimplementasikan. Pertanyaan berikutnya tentunya adalah, bagaimana kita mengetahui bahwa sebuah algoritma telah benar? Algoritma yang efisien itu seperti apa? Bagaimana kita mengukur kemudahan implementasi sebuah algoritma?

Bagian ini akan membahas mengenai pertanyaan pertama, yaitu bagaimana kita dapat mengetahui kebenaran sebuah algoritma. Tentunya efisiensi dan kemudahan implementasi sebuah algoritma menjadi tidak penting jika algoritma tersebut tidak dapat memberikan hasil yang benar.

Definisi dari kebenaran algoritma yang digunakan pada tulisan ini adalah sebagai berikut:

Sebuah algoritma dikatakan telah benar jika algoritma tersebut dapat memberikan keluaran yang benar jika menerima masukan sesuai dengan definisi algoritma tersebut, dan algoritma tersebut terbukti akan selalu dapat diterminasi (berakhir).

Pembuktian kebenaran sebuah algoritma sendiri dapat dilakukan dengan beberapa cara, misalnya:

  1. Induksi Matematika,
  2. Pembuktian kontradiktif,
  3. Pembuktian kontrapositif, dan
  4. Metode Formal.

Masing-masing alat pembuktian yang disebutkan memiliki kelebihan dan kekurangan masing-masing, serta kasus pengunaan yang berbeda-beda. Perlu diingat juga bahwa masih terdapat sangat banyak alat-alat pembuktikan lainnya yang dapat digunakan, tetapi kita hanya membahas satu cara pembuktian (induksi matematika) saja sebagai pengenalan cara membuktikan algoritma. Jika dibutuhkan, metode dan alat pembuktian lain akan dijelaskan lagi pada bagian yang relevan.

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

%d bloggers like this: