Algoritma Definisi Algoritma




старонка1/3
Дата канвертавання30.04.2016
Памер121.27 Kb.
  1   2   3



BAB 2

LANDASAN TEORI


  1. Algoritma

  1. Definisi Algoritma

Algoritma berasal dari kata Algoris dan Ritmis, kata-kata tersebut berasal dari seorang ahli matematika, Mohammed Ibn-Musa Al-Khawarizmi, yang merupakan bagian dari royal court, Baghdad. Algoritma adalah sebuah prosedur yang terstruktur dan dituliskan secara sistematis untuk menyelesaikan sebuah tugas, dimana memberikan initial state (keadaan awal), dan akan terminate di akhir (end state) dengan bantuan komputer.

Menurut Microsoft Press Computer and Internet Dictionary 1997,1998, definisi algoritma adalah Urutan langkah logis tertentu untuk memecahkan suatu masalah. Sedangkan dari Algoritma dan Struktur Data dengan C, C++, dan Java oleh Moh. Sjukani, algoritma adalah Alur pemikiran dalam menyelesaikan suatu pekerjaan yang dituangkan secara tertulis. Dari dua definisi diatas dapat disimpulkan bahwa algoritma harus mengikuti suatu urutan aturan tertentu dan tidak boleh melompat-lompat, dan algoritma seseorang dengan yang lain dapat berbeda-beda karena mempunyai alur pikir yang berbeda-beda pula, serta Algoritma dapat berupa kalimat, gambar atau tabel tertentu.

Dalam matematika dan komputasialgoritma atau algoritme,  merupakan kumpulan perintah untuk menyelesaikan suatu masalah. Perintah-perintah ini dapat diterjemahkan secara bertahap dari awal hingga akhir. Masalah tersebut dapat berupa apa saja, dengan catatan untuk setiap masalah, ada kriteria kondisi awal yang harus dipenuhi sebelum menjalankan algoritma. Algoritma akan dapat selalu berakhir untuk semua kondisi awal yang memenuhi kriteria, dalam hal ini berbeda dengan heuristik. Algoritma sering mempunyai langkah pengulangan (iterasi) atau memerlukan keputusan (logika Boolean dan perbandingan) sampai tugasnya selesai.


  1. Jenis-Jenis Algoritma

Beberapa paradigma yang digunakan dalam menyusun suatu algoritma akan dipaparkan dibagian ini. Masing-masing paradigma dapat digunakan dalam banyak algoritma yang berbeda, yaitu :

  • Divide and Conquer, paradigma untuk membagi suatu permasalahan besar menjadi permasalahan-permasalahan yang lebih kecil. Pembagian masalah ini dilakukan terus menerus sampai ditemukan bagian masalah kecil yang mudah untuk dipecahkan.

  • Dynamic programming, paradigma pemrograman dinamik akan sesuai jika digunakan pada suatu masalah yang mengandung sub-struktur yang optimal, dan mengandung beberapa bagian permasalahan yang tumpang tindih. Paradigma ini sekilas terlihat mirip dengan paradigma Divide and Conquer, sama-sama mencoba untuk membagi permasalahan menjadi sub permasalahan yang lebih kecil, tapi secara intrinsik ada perbedaan dari karakter permasalahan yang dihadapi.

  • Metode serakah, sebuah algoritma serakah mirip dengan sebuah pemrograman dinamik, bedanya jawaban dari submasalah tidak perlu diketahui dalam setiap tahap dan menggunakan pilihan "serakah" apa yang dilihat terbaik pada saat itu.

  1. Kompleksitas Algoritma, Waktu, Dan Masalah

Kompleksitas dari suatu algoritma merupakan ukuran seberapa banyak komputasi yang dibutuhkan algoritma tersebut untuk mendapatkan hasil yang diinginkan. Algoritma yang dapat memperoleh hasil yang diinginkan dalam waktu yang singkat memiliki kompleksitas yang rendah, sementara algoritma yang membutuhkan waktu yang lama untuk memperoleh hasil tersebut mempunyai kompleksitas yang tinggi.

Biasanya kompleksitas algoritma dinyatakan secara asimptotik dengan notasi big-O. Jika kompleksitas waktu untuk menjalankan suatu algoritma dinyatakan dengan T(n), dan memenuhi T(n) ≤ C(f(n)) untuk n ≥ n0, maka kompleksitas dapat dinyatakan dengan T(n) = O(f(n)).

Salah satu ukuran biaya dalam pengeksekusian sebuah algoritma adalah lamanya waktu yang diperlukan. Pengukuran waktu yang diperlukan dalam mengeksekusi suatu algoritma dinamakan kompleksitas waktu algoritma tersebut (Liu, C.L, 1995, p272).

Dua buah algoritma yang berbeda dapat digunakan memecahkan masalah yang sama dan mungkin saja, mempunyai kompleksitas waktu yang sangat berbeda (Liu, C.L, 1995, p274). Kompleksitas waktu algoritma terbaik untuk memecahkan masalah tersebut dinamakan sebagai kompleksitas waktu suatu masalah (Liu, C.L, 1995, p277).

Ada dua buah klasifikasi permasalahan (Leahy, Billy., 2000, p21-24), yaitu sebagai berikut :


  1. Permasalahan yang dapat dipecahkan (decidable / solvable problem)

permasalahan yang termasuk klasifikasi ini adalah semua jenis permasalahan yang mempunyai algoritma solusi, walaupun kadang kala tidak praktis. Dari segi komputasi, permasalahan dalam klasifikasi ini dapat dibedakan menjadi tiga kategori, yaitu :

  1. Permasalahan Tractable (mudah dari segi komputasi)

Suatu masalah dikatakan tractable, jika masalah tersebut dapat dipecahkan oleh suatu algoritma yang efisien. Contohnya, masalah penentuan bilangan terbesar di antara n bilangan, penentuan lintasan terpendek antara dua buah vertex di dalam sebuah graph, dan lain sebagainya.

  1. Permasalahan Intractable (sukar dari segi komputasi)

Suatu masalah dikatakan intractable, jika tidak ada algoritma yang efisien untuk memecahkan masalah tersebut.

  1. Permasalahan NP-Complete (NP singkatan dari Non-Deterministik Polinomial)

Suatu masalah dikatakan NP-Complete apabila masalah itu telah berhasil dibuktikan termasuk dalam masalah intractable. Contohnya, permasalahan pewarnaan graph.

  1. Permasalahan yang tidak dapat dipecahkan (undecidable / unsolvable problem)

permasalahan yang termasuk dalam klasifikasi ini adalah semua permasalahan yang tidak mempunyai aloritma solusi, maksudnya adalah tidak dapat dilakukan perhitungan, atau tidak dapat diperoleh jawaban dalam waktu terbatas. Contohnya, permasalahan unbounded tiling.


  1. Definisi Optimasi

Optimasi secara umum adalah untuk memaksimalkan atau mengoptimalkan sesuatu hal yang bertujuan untuk mengelola sesuatu yang dikerjakan, sehingga optimasi bisa dikatakan kata benda yang berasal dari kata kerja, dan optimasi bisa dianggap baik sebagai ilmu pengetahuan dan seni menurut tujuan yang ingin dimaksimalkan. (Dunia optimasi, optimasi, 2011)

Optimasi (Wikipedia, optimasi, 2012) adalah suatu proses untuk mencapai hasil yang ideal atau optimal (nilai efektif yang dapat dicapai). Dalam disiplin matematika, optimasi merujuk pada studi permasalahan yang mencoba untuk mencari nilai minimum dan maksimum dari suatu fungsi nyata. Untuk mencapai nilai minimum dan maksimum tersebut, secara sistematis dilakukan pemilihan integer atau bilangan nyata yang akan memberikan solusi yang optimal.

Sedangkan menurut Kamus Besar Bahasa Indonesia, optimasi adalah prosedur yang digunakan untuk membuat sistem atau desain yang fungsional atau seefektif mungkin dengan menggunakan teknik aplikasi matematika.

Dalam matematika dan ilmu komputer, sebuah masalah optimasi adalah masalah untuk menemukan solusi terbaik dari semua solusi. Masalah optimasi dapat dibagi menjadi dua kategori tergantung pada apakah variabel yang kontinyu atau diskrit. Masalah optimasi dengan variabel diskrit dikenal sebagai masalah optimasi kombinatorial . Dalam masalah optimasi kombinatorial, kami sedang mencari sebuah benda seperti grafik integer, permutasi atau dari himpunan berhingga (atau mungkin dihitung tak terbatas).




  1. Gambaran Umum tentang Label Kertas Atau Plastik

  1. Definisi Label

Dalam membuka sebuah usaha, adanya label pada produk yang dihasilkan sangatlah penting. Pada produk pakaian, makanan, minuman, elektronik, dan sebagainya, peran label sangat membantu produsen mengenalkan produk yang dihasilkan kepada para konsumen. Sehingga para konsumen dapat mengetahui produk yang ingin digunakannya.

Menurut Wikipedia, label adalah sepotong kertas, polymer, kain, logam, atau bahan lain yang ditempelkan pada wadah atau benda yang dicetak sebagai informasi produk, alamat, dan lain-lain. Label juga dapat langsung dicetak pada wadah atau benda. Sedangkan, pelabelan adalah setiap komunikasi tertulis, elektronik, atau gambar pada kemasan atau terpisah dari label terkait.

Dalam sistem online komputer, label (tag) adalah kata kunci non hierarki atau tidak bertingkat yang tugasnya adalah menunjukkan potongan-potongan informasi (seperti petunjuk internet, gambar digital, atau file komputer). Label merupakan jenis metadata yang membantu untuk menjelaskan suatu hal dan memungkinkan hal tersebut ditemukan ketika melakukan pencarian (browsing).

Gambar 2.1 Macam-macam label kertas



Tujuan utama dari label sebagai daya tarik calon pelanggan untuk mengetahui sebuah produk dan membuat produk terkesan unik. Label sebuah produk juga sebagai pencitraan dari sebuah perusahaan yang menghasilkan produk tersebut, menyampaikan pesan perusahaan kepada konsumen, serta membedakan produknya dengan produk dari perusahaan lainnya. Fungsi dari label adalah menyajikan identitas perusahaan dan identitas produk.


  1. Aturan Pembuatan Label Kemasan

Merancang atau mendesain label kemasan sangatlah tergantung pada kreativitas para desainernya, baik ukuran, bentuk, maupun corak warnanya. Namun demikian ada hal-hal yang harus diperhatikan dalam membuat label kemasan yaitu :

  1. Label tidak boleh menyesatkan, apa saja yang tercantum dalam sebuah label baik berupa kata-kata, kalimat, nama, lambang, logo, gambar dan lain sebagainya harus sesuai dengan produk yang ada di dalamnya.

  2. Memuat informasi yang diperlukan label sebaiknya cukup besar (relatif terhadap kemasannya), sehingga dapat memuat informasi atau keterangan tentang produknya.

  3. Hal-hal yang seharusnya ada atau tercantum dalam label produk makanan adalah sebagai berikut :

          1. Nama produk

Nama Produk adalah nama dari makanan atau produk pangan yang terdapat di dalam kemasan misalnya dodol nanas, keripik pisang, keripik singkong dan lain sebagainya.

          1. Cap / Trade mark bila ada

Suatu usaha sebaiknya memiliki cap atau trade mark atau merek dagang. Cap berbeda dengan nama produk dan bisa tidak berhubungan dengan produk yang ada di dalamnya misalnya dodol nanas cap “Panda”, Kecap Ikan cap “Wallet”, dsb.

          1. Komposisi / daftar bahan yang digunakan

Komposisi atau daftar bahan merupakan keterangan yang menggambarkan tentang semua bahan yang digunakan dalam pembuatan produk makanan tersebut. Cara penulisan komposisi bahan penyusun dimulai dari bahan mayor atau bahan utama atau bahan yang paling banyak digunakan sampai yang terkecil.

          1. Netto atau volume bersih

Netto atau berat bersih dan volume bersih menggambarkan bobot atau volume produk yang sesungguhnya. Apabila bobot produk berarti bobot produk yang sesungguhnya tanpa bobot bahan pengemas.

          1. Nama pihak produksi

Nama pihak produksi adalah nama perusahaan yang membuat atau mengolah produk makanan tersebut.

          1. Distributor atau pihak yang mengedarkan bila ada

Dalam kemasan juga harus mencantumkan pihak-pihak tertentu seperti pengepak atau importir bila ada.

          1. Nomor Registrasi Dinas Kesehatan

Nomor registrasi ini sebagai bukti bahwa produk tersebut telah teruji dan dinyatakan aman untuk dikonsumsi.

          1. Kode Produksi

Kode produksi adalah kode yang menyatakan tentang batch produksi dari produk pada saat pembuatan yang isinya tanggal produksi dan angka atau hurup lainnya yang mencirikan dengan jelas produk tersebut.

          1. Keterangan kadaluarsa

Keterangan kadaluarsa adalah keterangan yang menyatakan umur produk yang masih layak untuk dikonsumsi. Menurut Julianti dan Nurminah (2006), keterangan kadaluarsa dapat ditulis :

  • Best before date : produk masih dalam kondisi baik dan masih dapat dikonsumsi beberapa saat setelah tanggal yang tercantum terlewati.

  • Use by date : produk tidak dapat dikonsumsi, karena berbahaya bagi kesehatan manusia (produk yang sangat mudah rusak oleh mikroba) setelah tanggal yang tercantum terlewati.

          1. Logo halal

Untuk produk-produk yang telah mendapatkan sertifikasi “halal” dari MUI harus mencantumkan logo halal yang standard disertai dengan nomor sertifikasinya.

          1. Keterangan Lainnya

Selain yang telah diuraikan di atas masih ada lagi keterangan-ketrangan lain yang perlu dicantumkan dalam label kemasan makanan yang bermaksud memberi petunjuk, saran, atau yang lainnya demi keamanan konsumen.

  1. Tulisan atau keterangan yang ada

Tulisan atau keterangan yang ada pada label harus jelas dan mudah di baca, tidak dikaburkan oleh warna latar belakang atau gambar lainnya.

  1. Jumlah warna yang digunakan

Banyaknya warna yang digunakan dalam label akan berpengaruh terhadap biaya cetak, semakin banyak banyak warna yang digunakan, tentunya akan semakin besar biaya yang harus dikeluarkan.

  1. Jenis cetakan yang dikehendaki

Desain yang kita buat akan dicetak pada media apa? Plastik, kertas, aluminium foil, atau lainnya. Apakah akan dicetak dengan sablon atau menggunakan mesin modern.


  1. Macam – Macam Label

Terdapat 3 (tiga) macam label menurut Stanton (1994), yaitu:

  1. Brand Label

Label ini memuat merk, gambar, atau produsen dari produk yang dicantumkan dalam kemasan produk. Informasi tersebut penting bagi konsumen sehingga mereka dapat membedakan suatu produk dengan produk lainnya.

  1. Descriptive Label

Label ini memberikan informasi mengenai bahan baku, persentase kandungan, nilai kalori/gizi, cara penggunaan/konsumsi, tanggal pembuatn, tanggal kedaluarsa dll.



  1. Grade Label

Label ini menginformasikan kepada konsumen tentang penilaian kualitas produk.


  1. Pencarian

Pencarian (Munir, 2009) merupakan kegiatan mendefinisikan ruang masalah untuk masalah yang dihadapi. Ruang masalah ini dapat digambarkan sebagai himpunan keadaan (state) atau bisa juga sebagai himpunan rute dari keadaan awal (initial state) menuju keadaan tujuan (goal state).

Ada dua metode pencarian (searching), yaitu :



              1. Blind atau un-informed search (pencarian buta atau tidak berbekal informasi)

              2. Heuristic atau informed search (pencarian dengan berbekal informasi)




  1. Gambaran Umum Peletakan Posisi Label

Peletakan posisi label menggunakan metode A* heuristic dengan cara matematis menempatkan label dengan berbagai macam pola dua dimensi pada sebuah bin atau alas dasar, dalam kasus ini seperti kertas atau plastik. Tujuan dari program peletakan posisi label ini adalah meminimalkan penggunaan kertas atau plastik untuk menampung sejumlah pola label yang dibutuhkan.

Nilai dari sebuah pola adalah pasti, tidak nol, dan memiliki nilai yang positif akan mempermudah cara dan melakukan perhitungan untuk menempatkannya dalam bin atau pada kasus ini sebuah alas kertas atau plastik. Bin adalah ukuran yang pasti dari kertas atau plastik sebagai alas dasar untuk penempatan sejumlah pola label.

Terdapat banyak variasi dalam masalah optimasi peletakkan posisi label ini, seperti linear packing, packing by weight, packing by cost, dan lain sebagainya. Karena masalah ini termasuk ke dalam NP-Hard, maka algoritma yang diketahui efisien adalah heuristic. Penggunaan heuristic bertujuan untuk mendapatkan hasil yang baik dalam kebanyakan kasus, tetapi mungkin saja buka sebagai optimasi yang paling optimal. Heurisitic adalah sebuah algoritma yang mungkin saja menemukan solusi yang baik, tetapi tidak ada bukti bahwa solusinya tidak bisa menjadi buruk secara tidak masuk akal dan tidak ada argumen tentang hal ini bahwa hal seperti ini mungkin saja terjadi.


  1. NP-Hard

Menurut Wikipedia (2013), dalam teori “computational complexity”, NP (Non-deterministic Polynomial time) adalah sekumpulan permasalahan yang dapat dipecahkan menggunakan polynomial time – non-deterministic turing machine. Turing machines merupakan symbol abstrak dasar yang memanipulasi alat dimana dapat disesuaikan untuk mensimulasi logika dari komputer yang secara mungkin dapat dikonstruksi.

Hal ini dikemukakan pada tahun 1936 oleh Alan Turing, polynomial time adalah permasalahan waktu komputasi (ukuran berapa banyak langkah yang digunakan perangkat keras atau sistem perangkat lunak dalam pengkomputasi-pemrosesan informasi). Polynomial adalah sebuah pernyataan yang terbentuk dari satu atau lebih variable dan konstanta, dan hanya menggunakan penjumlahan, pengurangan, serta perkalian.

Sebuah kelas yang kompleks dari decision problems di mana pada dasarnya lebih sulit dari pada masalah yang biasa diselesaikan dengan non-deterministic turing machine dalam polynomial time. Terdapat tiga kelas permasalahan(problem), yaitu :


  • P adalah kumpulan “yes/no” problem yang bisa dipecahkan dalam waktu polynomial. Jadi bisa dikatakan bahwa P adalah kumpulan permasalahan yang bisa dipecahkan secara cepat.

  • NP adalah sekumpulan “yes/no” problem diikuti dengan property : jika “yes” maka ada pembuktian dari fakta itu yang bisa dicek dalam waktu polynomial. Jadi bisa dikatakan bahwa NP adalah sekumpulan permasalahan di mana bisa dikatakan “yes”, jika terdapat solusinya.

  • C
    o-NP adalah kebalikan dari NP, jika jawaban dari permasalahan co-NP adalah “no” maka ada pembuktian dari fakta itu yang bisa dicek dalam waktu polynomial.

Gambar 2.2 Hubungan antara P, NP, dan co-NP


  1. Metode Pencarian Heuristic

Menurut Munir (2009), heuristic berasal dari sebuah kata kerja Yunani, heuriskein yang berarti mencari atau menemukan. Dalam dunia pemrograman, sebagian orang menggunakan kata heuristic sebagai lawan kata dari algoritmik, dimana kata heuristic ini diartikan sebagai proses yang mungkin dapat menyelesaikan suatu masalah tetapi tidak ada jaminan bahwa solusi yang dicari selalu dapat ditemukan.

Heuristic memperbaiki proses pencarian solusi walaupun tidak harus sampai mengatasi kasus terburuk (worst case scenario). Heuristic ini mengembangkan efisiensi dalam proses pencarian, namun dengan kemungkinan mengorbankan kelengkapan (completeness). Algoritma ini biasanya mencari solusi yang dekat dengan solusi yang terbaik dan proses pencariannya cepat dan mudah. Fungsi heuristic h(n) adalah perkiraan biaya termurah dari node n ke node tujuan. Fungsi heuristic melambangkan cost yang akan dikeluarkan agent, jika memilih node tertentu.

Heuristic adalah sebuah algoritma yang mungkin saja menemukan solusi yang baik tetapi tidak ada bukti bahwa solusinya tidak bisa menjadi buruk secara tidak masuk akal, dan tidak ada argument tentang ini bahwa hal ini mungkin saja bisa terjadi.

Fungsi heuristic yang sempurna akan membuat algoritma A* langsung menuju final node tanpa harus mencari ke arah lain. Sehingga jika fungsi heuristic-nya terlalu underestimate akan menyebabkan algoritma ini beranggapan bahwa ada rute yang lebih baik dari rute yang ada. Untuk fungsi heuristic yang underestimate, bila nilainya terlalu rendah akan menyebabkan algoritma ini seperti algoritma Dijkstra yang mencari kesegala arah yang mungkin. Hal ini dikarenakan tidak cukupnya informasi mengenai masalah yang dihadapi, sehingga menyebabkan algoritma A* melakukan pencarian lebih banyak dan lebih lama.




  1. Best First Search

  1. Pengertian Best First Search

Best First Search merupakan sebuah metode yang membangkitkan simpul dari simpul sebelumnya. Best first search memilih simpul baru yang memiliki biaya terkecil diantara  semua leaf nodes (simpul-simpul pada level terdalam) yang pernah dibangkitkan. Penentuan simpul terbaik dilakukan dengan menggunakan sebuah fungsi yang disebut fungsi evaluasi f(n). fungsi evaluasi best first search dapat berupa biaya perkiraan dari suatu simpul menuju ke goal atau gabungan antara biaya sebenarnya dan biaya perkiraan tersebut.

Pada setiap langkah proses pencarian terbaik pertama, kita memilih node-node dengan menerapkan fungsi heuristik yang memadai pada setiap node yang kita pilih dengan menggunakan aturan-aturan tertentu untuk menghasilkan penggantinya. Fungsi heuristic merupakan suatu strategi untuk melakukan proses pencarian ruang keadaan suatu problema secara selektif, yang memandu proses pencarian yang kita lakukan sepanjang jalur yang memiliki kemungkinan sukses paling besar.

Ada beberapa istilah yang sering digunakan pada metode best first search, yaitu:


  1. Start node adalah sebuah terminology untuk posisi awal sebuah pencarian.

  2. Curret node adalah simpul yang sedang dijalankan dalam algoritma pencarian jalan terpendek.

  3. Suksesor adalah simpul-simpul yang yang akan diperiksa setelah current node.

  4. Simpul (node) merupakan representasi dari area pencarian.

  5. Open list adalah tempat menyimpan data simpul yang mungkin diakses dari starting node maupun simpul yang sedang dijalankan.

  6. Closed list adalah tempat menyimpan data simpul yang juga merupakan bagian dari jalur terpendek yang telah berhasil didapatkan.

  7. Goal node yaitu simpul tujuan.

  8. Parent adalah curret node dari suksesor.



  1   2   3


База данных защищена авторским правом ©shkola.of.by 2016
звярнуцца да адміністрацыі

    Галоўная старонка