Pengertian, Contoh Skripsi Algoritma dan Pemrograman

BAB 2 LANDASAN TEORI
2.1. Algoritma dan Pemrograman
Dalam matematika dan komputasi, algoritma merupakan kumpulan perintah untuk menyelesaikan suatu masalah8). Kumpulan perintah ini biasanya diterjemahkan oleh komputer secara bertahap dari yang pertama sampai yang terakhir secara sekuensial. Masalah yang terkait disini dapat berupa berbagai macam masalah asalkan masalah tersebut memiliki kriteria kondisi awal yang harus dipenuhi sebelum menjalankan algoritma.

Kata algoritma berasal dari latinisasi nama seorang ahli matematika dari Usbekistan Al Khawārizmi (hidup sekitar abad ke-9), sebagaimana tercantum pada terjemahan karyanya dalam bahasa latin dari abad ke-12 "Algorithmi de numero Indorum". Pada awalnya kata algoritma adalah istilah yang merujuk kepada aturan-aturan aritmatik untuk menyelesaikan persoalan dengan menggunakan bilangan numerik arab (sebenarnya dari India, seperti tertulis pada judul di atas). Pada abad ke-18, istilah ini berkembang menjadi algoritma, yang mencakup semua prosedur atau urutan langkah yang jelas dan diperlukan untuk menyelesaikan suatu permasalahan.
Jenis-jenis algoritma dapat diklasifikasikan berdasarkan metode yang digunakan untuk mendesain algoritma tersebut. Menurut Cormen dan Leiserson, disamping metoda sekuensial (Sequential Programming), terdapat empat metode umum yang digunakan dalam mendesain algoritma yaitu Divide and Conquer, Dynamic Programming, Greedy Algorithms, dan Amortized Analysis. Penjelasan dari masing masing metoda diberikan pada sub bab berikut.

2.1.1.   Divide and Conquer
Divide and Conquer merupakan pendekatan algoritma yang membagi-bagi permasalahan ke dalam bentuk yang lebih kecil, sehingga dapat dipecahkan secara terpisah9). Pendekatan ini memecahkan masalah ke dalam sub-masalah yang mirip namun dengan ukuran yang lebih kecil, untuk kemudian dapat dipecahkan secara rekursif (perulangan). Hasil pemecahan tiap-tiap sub-masalah kemudian digabungkan kembali untuk mendapatkan solusi masalah secara keseluruhan.
Pendekatan Divide  and  Conquer  memiliki tiga langkah umum pada setiap tingkat perulangan, yaitu Divide, Conquer, dan Combine. Contoh umum dari penggunaan pendekatan ini dalah dalam algoritma Merge  Sort.  Pada  algoritma Merge  Sort,  banyaknya angka  yang  ada dibagi dengan pembagi dua (Langkah Divide). Kemudian urutkan angka- angka tersebut pada tiap sub-masalahnya (Langkah Conquer). Setelah angka-angka tersebut  terurut,  gabungkan dengan  sub-masalah  lainnya agar membentuk solusi umum (Langkah Combine).
Menggunakan pendekatan Divide and Conquer memiliki keuntungan sebagai berikut :
-Dapat memecahkan masalah yang sulit.

Divide and Conquer merupakan cara yang sangat efektif untuk menyelesaikan masalah yang rumit. Contoh lain yang memerlukan pendekatan ini adalah penyelesaian Tower of Hanoi. Pada Tower of Hanoi, akan lebih efektif untuk memecahkan masalah adalah dengan, menyelesaikan masalah dan kemudian menggabungkannya, daripada menyelesaikan secara sekuensial tanpa memecahkan ke dalam sub- masalah terlebih dahulu.
-Memiliki efisiensi algoritma yang tinggi.

Pendekatan Divide and Conquer juga memiliki efisiensi algoritma yang cukup tinggi. Contohnya, jika ukuran masalah n memiliki sub- masalah p dengan ukuran n/p pada tiap perulangannya, maka kompleksitas algoritma untuk ukuran waktu konstan O akan menjadi
O(n log n).  Cara  ini  lebih  efisien  dalam  menyelesaikan  algoritma sorting yang memiliki kompleksitas algoritma O(n 2 ) jika dijalankan dengan algoritma sekuensial.

-Dapat bekerja secara paralel.
Divide and Conquer telah didisain untuk dapat bekerja dalam mesin- mesin   yang   memiliki   banyak   prosesor.   Terutama  mesin   yang memiliki sistem pembagian memori, dimana komunikasi data antar prosesor tidak perlu direncanakan terlebih dahulu, hal ini karena pemecahan sub-rutin dapat dilakukan di prosesor lainnya.

-Akses memori yang cukup kecil.
Untuk akses memori, Divide and Conquer dapat meningkatkan efisiensi memori yang ada cukup baik. Hal ini karena, sub-rutin memerlukan memori lebih kecil daripada masalah utamanya. Disamping itu, Divide and Conquer hanya memerlukan satu bagian memori untuk menyelesaikan sub-rutin sub-rutin tersebut (karena berupa perulangan dan sudah memiliki pesanan memori untuk variabel-variabelnya).
Kerugian  –   kerugian  menggunakan  pendekatan  Divide   and Conquer  adalah:

-Lambatnya proses perulangan
Proses  pemanggilan  sub-rutin  yang  berlebih,  sehingga  call  stack penuh dari beberapa sub-rutin tersebut. Hal ini dapat menjadikan beban yang cukup signifikan pada prosesor. Misalnya pengulangan yang  terus  menerus  pada  sub-rutin yang  cukup  banyak,  sehingga dapat memperlambat proses pengulangan.
-Lebih rumit untuk masalah yang sederhana
Untuk pemecahan masalah yang relatif sederhana, algoritma sekuensial terbukti lebih mudah dibuat daripada algoritma divide and conquer. Hal ini disebabkan karena algoritma sekuensial tidak perlu melalui  ketiga  langkah  yang  dilakukan  oleh  divide  and  conquer. Salah satu contohnya ialah, untuk menambah n-banyak bilangan, perulangan sederhana akan lebih mudah dibuat daripada harus memecah n-bilangan tersebut, menambahkannya satu sub-rutin demi satu sub-rutin, kemudan menjumlahkan hasil dari sub-rutin tersebut.

2.1.2.   Dynamic Programming
Seperti metoda Divide and Conquer, Dynamic Programming juga menyelesaikan masalah dengan cara menggabungkan solusi-solusi dari penyelesaian subrutin-subrutinnya1). Perbedaan pokok Dynamic Programming dapat digunakan saat subrutin-subrutinnya tidak independen,  yaitu,  saat   subrutinnya  membagi  sub-subrutin.   Dalam konteks ini, Divide and Conquer memerlukan langkah yang lebih banyak daripada Dynamic Programming, karena harus mengerjakan subsubrutin yang mirip berkali-kali. Pada Dynamic Programming, setiap subsubrutin hanya dijalankan sekali untuk kemudian disimpan nilainya didalam tabel, sehingga dapat mempersingkat waktu kerja.
Dynamic Programming biasanya diaplikasikan pada masalah optimisasi.  Masalah  seperti  ini  dapat  memiliki  banyak  solusi.  Setiap solusi memiliki nilai-nilai yang berbeda. Disinilah tugas Dynamic Programming untuk mencari solusi yang paling optimal. Pengembangan Dynamic Programming dapat dipecah menjadi empat langkah utama, yaitu:
1.   Menyusun struktur solusi optimal.
2.   Secara rekursif tentukan nilai dari solusi optimal tersebut.
3.   Hitung nilai solusi optimal dengan cara bottom-up.
4.   Buat solusi optimal dari informasi-informasi tersebut.

Keuntungan Dynamic Programming adalah bahwa metode ini dapat mempersingkat waktu yang sangat signifikan bagi masalah yang memiliki lebih dari satu solusi, karena dapat menemukan solusi yang optimal. Sedangkan kerugiannya adalah bahwa Dynamic Programming juga  memerlukan  waktu  yang  relatif  lebih  lama  saat  memecahkan masalah dengan subrutin yang relatif sedikit.
Salah satu contoh permasalahan yang memerlukan solusi optimal adalah pencarian angka ke-n dari deret Fibonacci, yang beradasarkan pada definisi matematis:
Jika pada rumus diatas dipanggil fib(5), akan ada banyak fungsi yang sama yang dipanggil berkali-kali:
1. fib(5)
2. fib(4) + fib(3)
3. (fib(3) + fib(2)) + (fib(2) + fib(1))
4.   ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
5.   (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
Pada umumnya, fib(2) dihitung dua kali (pada no. 3). Pada contoh yang lebih besar, banyak fungsi fib(n), atau subrutin, yang dikomputasi ulang, sehingga memerlukan waktu yang cukup besar. Jika menggunakan Dynamic Programming, maka nilai fib(2) hanya perlu dilakukan sekali dimana nilai tersebut kemudian akan ditampung di satu tabel yang akan dipanggil kembali jika menemukan kasus serupa. Fungsi hasilnya hanya memerlukan kompleksitas O(n) daripada menggunakan sekuensial, maupun Divide and Conquer.

2.1.3.   Greedy Algorithms
Algoritma yang digunakan untuk optimalisasi solusi biasanya melewati beberapa langkah, dengan pilihan-pilihan di setiap langkahnya. Untuk banyak masalah yang memerlukan optimalisasi solusi, menggunakan Dynamic Programming akan membuang banyak sumber daya (memori dan waktu). Greedy Algorithm merupakan metode yang akan selalu memilih pilihan yang terbaik di setiap langkahnya. Greedy Algorithm selalu memilih pilihan optimal pada setiap langkahnya yang berpeluang tinggi untuk menjadi pilihan terbaik seterusnya. Contoh masalah yang dapat diselesaikan dengan Greedy Algorithm adalah Minimum Spanning Tree, Dijkstra’s Algorithm untuk jalan terpendek dari satu sumber, dan Chvatal Greedy Set-Covering Heuristic.

2.1.4.   Amortized Analysis
Dalam Amortized Analysis, waktu yang diperlukan untuk memproses struktur-data terurut dirata-ratakan dari semua operasi. Amortized Analysis dapat digunakan untuk menunjukkan bahwa nilai operasi rata-rata cukup kecil,   walaupun ada beberapa operasi yang memiliki nilai besar. Metoda ini cukup berguna untuk menghitung nilai sumber daya yang terbuang secara keseluruhan.

2.2. Kecerdasan Buatan (Artificial Intelligence)
Kecerdasan buatan atau Artificial Intelligence (AI) adalah salah satu cabang ilmu komputer yang berhubungan dengan tingkah laku yang pintar, belajar   dan   dapat   beradaptasi   pada   mesin2) Penelitian   pada   Artificial Intelligence  dipusatkan  pada  penghasilan  mesin  yang  mengotomatisasikan tugas-tugas yang memerlukan tingkah laku yang pintar. Contohnya kontrol, perencanaan dan penjadwalan, kemampuan menjawab diagnostik dan pertanyaan-pertanyaan pelanggan, handwriting, suara dan pengenalan wajah. Untuk itu, Artificial Intelligence telah menjadi disiplin ilmu, difokuskan pada penyediaan solusi masalah-masalah kehidupan nyata, aplikasi software, game strategi seperti catur komputer dan video game lainnya.

2.2.1.   Klasifikasi Ilmu Artificial Intelligence
Artificial Intelligence dibagi dalam dua bidang studi yaitu: Artificial Intelligence Konvensional dan Computational Intelligence (CI). Artificial Intelligence Konvensional terutama meliputi metode yang diklasifikasikan sebagai mesin yang belajar (machine learning), dicirikan dengan analisis statistika. Ini juga dikenal sebagai simbolik Artificial Intelligence, logikal Artificial Intelligence, neat Artificial Intelligence (menyatakan  solusi  harus  luwes,  jelas  dan  benar)  dan  Good  Old Fashioned Artificial Intelligence (GOFAI). Metodenya meliputi :
-Sistem  Pakar  (Expert  System):  menerapkan  kemampuan  menalar untuk mencapai kesimpulan. Sebuah sistem pakar dapat memproses sejumlah besar informasi yang diketahui dan menyediakan kesimpulan berdasarkan informasi tersebut.
-Case based reasoning : merupakan proses penyelesaian masalah baru berdasarkan  pada  solusi  dari  masalah  lampau  yang  serupa.  Case based reasoning dapat disebut juga menganalogikan masalah yang mirip dengan masalah lampau.
-Bayesian  networks  merupakan grafik asiklik tertuju dimana tiap node-nya mewakilkan satu variabel, dan garis penghubung tiap node disebut hubungan ketergantungan statistik diantara variabel tersebut dan nilai distribusi probabilitas lokal untuk tiap variabel yang diberikan dari node sebelumnya.
-Behavior based Artificial Intelligence : merupakan kecerdasan buatan dimana kecerdasannya dibuat dari banyak elemen modul yang relatif sederhana dalam membuatnya. Setiap elemen berfungsi hanya pada konteks khusus, yang hanya dikenali oleh modul tersebut.
Computation Intelligence meliputi pengembangan iterative atau belajar. Pembelajaran didasarkan pada kumpulan data-data empiris yang dihubungkan dengan kecerdasan buatan non-simbolik. Beberapa metode pembelajaran tersebut adalah sebagai berikut:
-Neural Network: sistem dengan kemampuan pengenalan pola.
-Fuzzy System: teknik untuk menalar dibawah ketidakpastian, secara luas digunakan pada industri modern dan sistem kontrol produk konsumen.
-Evolutionary computation: menerapkan konsep yang terinspirasi dari permasalahan biologi seperti populasi, mutasi dan survival  of  the fittest untuk menghasilkan solusi yang lebih baik. Metode ini dapat dibagi lagi   menjadi   evolutionary   algorithm   (contoh   genetic algorithm) dan swarm intelligence (contoh ant algorithm).
Dengan hybrid intelligent system berusaha untuk membuat kombinasi dari dua group ini. Aturan kesimpulan pakar dapat dihasilkan melalui neural network atau aturan produksi dari pembelajaran statistika seperti ACT-R. Otak manusia menggunakan multiple teknik untuk bersama-sama memformulasikan dan menghasilkan cross-check. Jadi, integrasi terlihat menjanjikan dan mungkin perlu dalam artificial intelligence yang sebenarnya.
Satu metode baru yang menjanjikan disebut intelligence amplification, dimana mencoba mencapai tingkat artificial intelligence dalam proses pengembangan yang evolusioner sebagai   penjelasan kecerdasan manusia melalui teknologi.

2.2.2.   Pengunaan artificial intelligence pada Bisnis
Bank menggunakan sistem kecerdasan buatan untuk mengorganisasikan operasi, penanaman saham dan mengatur properti. Pada agustus 2001, robot melebihi manusia dalam simulasi kompetisi pertukaran keuangan (BBC news, 2001). Klinik medikal dapat menggunakan sistem kecerdasan buatan untuk mengatur dan menjadwalkan, membuat rotasi pegawai dan menyediakan informasi secara periodik. Banyak juga aplikasi tergantung pada jaringan syaraf tiruan (ANN   artificial  neural  network),  yaitu  jaringan yang mempolakan organisasi dalam cara meniru otak manusia. Aplikasi ini mempunyai banyak kebaikan dalam hal pengenalan pola. Institusi keuangan telah lama menggunakan sistem seperti ini untuk mendeteksi klaim di luar kewajaran. ANN juga digunakan secara luas pada homeland security, suara dan pengenalan teks, diagnosis medical, data mining dan e-mail spam filtering. Homeland security mempunyai fungsi untuk mencegah, mendeteksi, menanggapi dan memperbaiki suatu tingkah laku kegiatan seperti teroris dan juga bencana alam.

Robot juga telah umum digunakan di banyak industri. Mereka sering   diberikan   pekerjaan   yang   dipertimbangkan   berbahaya   bagi manusia.  Robot  juga  terbukti  efektif  pada  pekerjaan  yang  sangat repetitive yang mungkin menyebabkan kesalahan atau kecelakaan tugas karena kehilangan konsentrasi, jika dikerjakan oleh manusia. Contohnya General Motor (GM) menggunakan 16.000 robot untuk tugas painting, welding dan assembly. Jepang merupakan negara pemimpin dalam penggunaan robot, dari data yang didapat pada 1995, 700.000 robot digunakan secara luas diseluruh dunia dan lebih dari 500.000 berasal dari Jepang (Encarta, 2006). Lihat Sambungan 2.3