TUGAS METODE ALGORTIMA (SOFTSKILL)

PENG. TEKNOLOGI SISTEM CERDAS

DOSEN : JULIA FAJARYANTI, ST., MMSI.

Oleh :

Fatihah Mardhotillah                    14114041

Gusna Nilam Kharisma                 14114634

Ira Rochimah                                 1C114882

Nuri andini                                     18114217

Rahmania Juniharti                       18114792

FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI

SISTEM INFORMASI (3KA15)

UNIVERSITAS GUNADARMA

2017

 

METODE ALGORITMA DYNAMIC PROGRAMMING

1.      Pengertian Dynamic Programming

Dynamic Programming merupakan suatu teknik analisa kuantitatif untuk membuat tahapan keputusan yang saling berhubungan. Teknik ini menghasilkan prosedur yang sistematis untuk mencari keputusan dengan kombinasi yang optimal.

Program Dinamis (Dynamic Programming) adalah metode pemecahan masalah dengan cara menguraikan solusi menjadi sekumpulan (stage), sedemikian sehingga solusi dari persoalan dapat dipandang dari serangkaian keputusan yang saling berkaitan.

Dynamic Programming adalah prosedur matematis yang terutama dirancang untuk memperbaiki efisiensi perhitungan masalah pemrograman matematis tertentu dengan menguraikannya menjadi bagian masalah yang lebih kecil. Dynamic programming pada umumnya menjawab masalah dalam tahap-tahap dengan setiap tahap meliputi tepat satu variable optimasi.Perhitungan ditahap yang berbeda-beda dihubungkan melalui perhitungan rekursi dengan cara yang menghasilkan pemecahan optimal bagi seluruh masalah.

Istilah Program Dinamis muncul karena kecenderungan penggunaan metode ini dalam menganalisa dan mendokumentasikan hasil perhitungan pada setiap tahapnya melibatkan pengambilan keputusan yang berkaitan dengan waktu. Tetapi, situasi lain dimana waktu bukan merupakan factor juga dipecahakan oleh dynamic programming dimana prosedur itu pada umumnya menentukan pemecahan dalamtahap-tahap.

Teori utama dalam dynamic programming adalah prinsip optimalitas. Prinsip itu pada dasarnya menentukan bagaimana suatu masalah yang diuraikan dengan benar dapat dijawab dalam tahap-tahap.

Pemecahan masalah dengan menggunakan dynamic programming mempunyai empat tahapan, yaitu :

a. Memecah permasalahan asli menjadi bagian permasalahan yang juga disebut sebagai tahapan dengan aturan keputusan ditiap-tiap tahapan.

b.      Memecahkan tahapan terakhir dari permasalahan dengan semua kondisi dan keadaan yang memungkinkan.

c.       Bekerja mundur dari tahapan terakhir dan memecahkan tiap tahap. Hal ini dikerjakan dengan mencari keputusan optimal dari tahap tersebut sampai dengan tahapterakhir.

d.      Solusi optimal dari permasalahan didapatkan jika semua tahap sudah terpecahkan.

2.      Model Dynamic Programming

Dalam dynamic programming perhitungan dilakukan dalam tahap-tahap dengan memerincikan masalah menjadi beberapa bagian masalah. Setiap bagian masalah kemudian dipertimbangkan secara terpisah dengan tujuan untuk mengurangi jumlah dan kerumitan perhitungan. Tetapi karena semua maslah saling bergantung, harus dipikirkan sebuah prosedu runtuk menghubungkan perhitungan dengan cara yang menjamin bahwa pemecahan yang layak untuk tiap-tiap tahap juga layak untuk keseluruhan masalah.

           Sebuah tahap dalam dynamic programming didefinisikan sebagai bagian darimasalah yang memiliki beberapa alternative yang saling menggantikan yang dari nya alternatif terbaik akan dipilih. Gagasan dasar dynamic programming adalah secara praktis menghilangkan pengaruh saling ketergantungan antar tahap-tahap dengan menghubungkan definisi suatu keadaan dengan setiapt ahap. Suatu keadaan biasanya didefinisikan untuk menunjukkan suatu batasan yang mengikat semua tahap secara bersama-sama.

           Semua keputusan dimasa yang akan datang dipilih secara optimal tanpa melihat keputusan yang diambil sebelumnya. Sifat khusus ini merupakan prinsip optimalitas yang merupakan dasar bagi keabsahan perhitungan dynamic programming.

           Ada 2 (dua) Pendekatanpada Program dinamis, yaitu :

1.      Program DinamisMaju ( forward atau up-down)

2.      Program DinamisMundur (Bacwardatau button-up)

Misalkan x₁,x₂,…., x_nmenyaatakan peubah (variable) keputusan yang dibuat  masing-masing untuk tahap 1,2,…, n. Maka ,

1.      Program dinamis maju. Program dinamis bergerak mulai dari tahap 1, terus maju ketahap 2, 3, dan seterusnya sampai tahap n. runtunan peubah keputusan adalah x₁, x₂, ..,x_n.

2.      Program dinamis mundur. Program dinamis bergerak mulai dari tahap n_, terus mundur ketahap n-1, n-2, dan seterusnya sampai a tahap 1. Runtunan peubah keputusan adalah x_n, x_n-1, …, x_1.Dengan demikian, Prinsip optimalitas pada program dinamis maju adalah ongkos pada tahap  k +1 = (ongkos yang dihasilkan pada tahap k) + (ongkos dari tahap k ke tahap k + 1), k = 1, 2, …, n – 1Sedangkan prinsip optimalitas pada program dinamis mundur adalah ongkos pada tahap k = (ongkos yang dihasilkan pada tahap k + 1) + ( ongkos dari tahap k + 1 ke tahap k), k = n, n – 1,…, 1.

      Pada prinsipnya Program Dinamis berdasarkan pada Graf multitahap (multistage graph). Tiap simpul didalam garaf tersebut menyatakan status, sedanagkan V1,V2,… menyatakan tahap.

Gambar1 :Garph multi tahap

Pada Persoalan Graph Multitaphap dikaitkan dengan program dinamis, dikenal :

1.   Tahap (k) adalah proses memilih simpul tujuan berikutnya (Gambar 1, ada 5 tahap).

2.   Status (s) yang berhubungan dengan masing-masing tahap adalah simpul-simpul di dalam garaf.

Relasi rekurens berikut menyatakan lintasan terpendek dari status s ke x4 pada tahap k :

 

Tujuan Program Dinamis Maju mendapatkan   dengan cara mencari  terlebih dahulu.

3.   Karakteristik dan Konsep Dasar Dynamic Programming

Dynamic Programming memiliki beberapa karakteristik diantaranya :

•     Permasalahan dibagia menjadi stage, dengan keputusan diperlukan pada tiap stage.

•     Tiap stage punya nomor stage berhubungan dengan awal dari stage.

Hasil dari setiap stage penyelesaiannya ditransformasikan pada stage yang lainnya.

•     Prosedur dirancang untuk mendapatkan hasil yang optimal.

•     Hasil optimal dari suatu stage tidak berhubungan dengan stage sebelumnya.

•     Prosedur penyelesaiannya diawali dari stage terakhir.

Konsep dasar dalam dynamic programming yaitu :

•     Dekomposisi

Persoalan dynamic programming dapat dipecah-pecah menjadi subpersoalan atau tahapan ayang lebih kecil dan berurutan. Setiap tahap disebut juga sebagai titik keputusan. Setiap keputusan yang dibuat pada suatu tahap akan mempengaruhi keputusan-keputusan pada atahap berikutnya.

•     Status

Status adalah kondisi awal dan kondisi akhir pada setiap tahap, dimana pada atahap tersebut keputusan dibuat. Status akhir pada sebuah tahap tergantung keadaan status awal dan keputusan ayang dibuat pada tahap yang bersangkutan. Status akhir pada suatu tahap merupakan input bagi tahap berikutnya.

•     Variable Keputusan dan Hasil

Keputusan yang dibuat pada setiap atahap merupakan keputusan yang berorientasi kepada return yang diakibatkannya, tingkat maksimal atau minimal.

•     Fungsi Transisi

Fungsi transisi menjelaskan secara pasti bagaimana tahap-tahap saling berhubungan. Fungsi ini berbentuk fungsi hubungan antar status pada setiap tahap yang berurutan.

•     Optimasi Tahap

Optimasi tahap dalam dynamic programming adalah menentukan keputusan optimal pada setiap tahap dari bebagai kemungkinan nilai status inputnya.

•     Fungsi Rekursif

Fungsi rekursif  biasanya digunakan pada berbagai program computer, dimana nilai sebuah variable pada fungsi itu merupakan nilai kumulatif dari nilai variable tersebut pada tahap sebelumnya.

                  Dynamic Programming (DP) merupakan salah satu teknik perancangan algoritma yang dikembangkan untuk menyelesaikan permasalahan yang sangat kompleks dengan memecah permasalahan tersebut menjadi banyak sub-permasalahan. Perbedaan utama DP dengan Divide and Conquer (D&C) adalah pada DP kita menggunakan kembali Perbedaan utama dari DP dengan D&C adalah DP melakukan penyimpanan hasil penyelesaian sub-masalah sehingga kita tidak perlu menyelesaikan sub-masalah yang sama berulang kali.

Contoh :

Perbedaan Dynamic programming dan Divide and Conquer (D&C) dalam perhitungan bilangan fibonacci. Algoritma untuk menyelesaikan perhitungan fibonacci secara naif adalah seperti berikut:

  

Algoritma fibonacci sederhana seperti di atas dapat dikatakan sebagai algoritma D&C, karena kita membagikan perhitungan fibonacci ke dua fungsi fibonacci, sampai didapatkan nilai hasil terkecilnya. Pemanggilan fungsi fibonacci di atas dapat digambarkan seperti berikut:

PemanggilanFungsi Fibonacci

Perhatikan bagaimana f(n−2)danf(n−3) dikalkulasikan sebanyak dua kali, dan semakin kita masuk kedalam pohon pemanggilan, kita akan melihat semakin banyak fungsi-fungsi yang dipanggil berkali-kali. Pendekatan DP menghindari kalkulasi fungsi yang berulang kali seperti ini dengan melakukan memoization, yaitu menyimpan hasil kalkulasi fungsi tersebut dan menggunakan nilai yang disimpan ketika perhitungan yang sama dibutuhkan kembali. Dengan menyimpan hasil kalkulasi seperti ini, tentunya jumlah total langkah perhitungan yang harus dilakukan menjadi berkurang.

Misalnya, kita dapat menyimpan hasil kalkulasi dari fungsi fibonacci tersebut pada sebuah dictionary, seperti berikut:

Dengan menyimpan hasil kalkulasi dari fungsi yang telahada, maka proses pemanggilan fungsi akan menjadi seperti berikut:

PemanggilanFungsi Fibonacci Dynamic Programming

Seperti yang dapat dilihat, pohon pemanggilan fungsi terpotong setengahnya! Tentunya perhitungan fibonacci akan menjadi sangat efisien dengan menggunakan fungsi yang baru ini.

Pendekatan lain dalam menghitung fibonacci lagi, yang masih adalah DP, yaitu dengan menghitung nilai fibonacci dari bawah pohon (pada kode sebelumnya kita melakukan perhitungan dari atas pohon):

Untuk ketiga fungsi tersebut, ketika ketiga fungsi tersebut dijalankan untuk n yang sama, akan tampak perbedaan waktu eksekusinya.

https://www.academia.edu/14480072/Algoritma_Dynamic_Programming

METODE PENGUJIAN SISTEM CERDAS

Para ahli di bidang kecerdasan buatan / artificial intelligence (AI) akan berkumpul pada acara konvensi tahunan Association for the Advancement of Artificial Intelligence pada tanggal 25 Januari 2015, di Austin, Texas, Amerika Serikat. Mereka berkumpul untuk mengadakan sebuah workshop untuk membahas tes alternatif yang digunakan untuk menguji keberhasilkan tingkat kecerdasan sebuah AI untuk menggantikan Turing Test yang selama ini digunakan.

Turing Test yang dicetuskan oleh Alan Turing pada tahun 1950 bertujuan untuk menguji apakah sebuah program komputer itu cerdas. Tes tersebut dilakukan dengan membiarkan seorang penguji (C) melakukan sesi tanya-jawab (dengan text) dengan sebuah mesin (A) dan manusia (B), dan pada akhir sesi tersebut C diharuskan untuk menentukan diantara A dan B manakah yang sebuah mesin (program komputer). Jika C dapat membedakan dengan mudah maka AI tersebut tidak begitu “cerdas”, sedangkan jika C tidak dapat menentukan dengan benar yang mana yang mesin dan yang mana manusia maka dapat disimpulkan bahwa program komputer tersebut “cerdas” karena dapat meniru kemampuan manusia menjawab pertanyaan seperti layaknya manusia.

  

Turing Test, C mengajukan pertanyaan kepada A dan B dan akhirnya menentukan apakah A dan B adalah mesin atau manusia. – Wikipedia

Pada masa awal perkembangan penelitian AI, tingkat kesulitan tes tersebut (Turing Test) masih sangat jauh diatas kemampuan program komputer pada masa itu. Akan tetapi saat ini telah banyak bermunculan “chatbot” yang sangat sederhana menggunakan beberapa kata-kata kunci dan kalimat-kalimat yang dirangkai sangat bagus, telah dapat mengelabui, orang-orang yang tidak sadar, bahwa mereka sedang melakukan percakapan dengan manusia. Kasus terakhir adalah pada bulan Juni 2014, sebuah program komputer “menyamar” menjadi seorang anak Ukraina berusia 13 tahun bernama Egene Goostman telah berhasil “mengelabui” cukup banyak orang di Inggris bahwa ia adalah seorang manusia (meskipun diprogram tersebut dibantu oleh kondisi bahwa mereka percaya sedang berbicara dengan seorang anak remaja yang memiliki kemampuan bahasa Inggris terbatas).

Kemenangan Goostman tersebut kemudian disebarkan oleh media secara berlebihan hingga akhirnya Gary F. Marcus , seorang peneliti psikologi New York University, mengangkat isu tentang apakah Turing Test menjadi mudah untuk dipermainkan, dan mendesak komunitas AI untuk mencari penggantinya yang lebih baik. Dan tidak disangka-sangka para peneliti dari penjuru dunia bersedia untuk memberikan bantuan terkait hal tersebut. Dan sebagai tindak lanjutnya akan diadakan workshop untuk membahas hal tersebut.

Salah satu kritik terhadap Turing Test adalah tes tersebut terlalu menekankan pada  kemampuan berbahasa di atas kemampuan lainnya seperti vision atau movement. Marcus berharap dari workshop tersebut akan dihasilkan serangkaian tes yang dapat menguji berbagai area kecerdasan yang dideskripsikan olehnya sebagai “Turing triathlon”. Beberapa orang peneliti yang mengikuti workshop tersebut diantaranya Manuela Veloso dari Carniege-Mellon University yang menekankan tentang pentingnya sebuah komputer untuk dapat memahami dan berinteraksi dengan dunia nyata. Kemudian kan hadir pula Peter Clark dari Allen Institute for ArtificialIntelligence, akan mendeskripsikan hasil pekerjaan kelompok penelitiannya tentang memberi kemampuan membaca buku pengetahuan alam anak sekolah menengah kepada komputer untuk kemudian menjawab tes terstandarisasi mengenai materi tersebut. Pembicara lainnya adalah Patrick Henry Winston dari MIT, akan berbicara tentang penelitiannya terkait dengan memberi kemampuan komputer untuk memahami cerita.

Dari serangkaian tes yang akan dihasilkan dari workshop ini nantinya, pasti masih ada cara untuk “mempermainkan” tes tersebut seperti halnya yang dilakukan oleh “chatbot”, atau sepak bola robot di mana sebuah robot dengan sengaja menduduki bola sehingga pertandingan dapat berakhir seri. Bagi Marcus sendiri, semua itu sangatlah buruk. “Jika dalam 10 tahun komputer dapat melampaui semua tes dengan menggunakan cara curang dan jalan pintas, dan bukan dengan sesuatu yang menyerupai kecerdasan yang asli, kami tidak akan bahagia. Kami akan mengejar kecerdasan yang sebenarnya.”

Sumber: 

http://spectrum.ieee.org/robotics/artificial-intelligence/artificialintelligence-experts-to-explore-turing-test-triathlon