Analisis dan Strategi Algoritma
Deskripsi Mata Kuliah • Konsep dasar analisis algoritma • Beberapa jenis algoritma
28/02/2011
2
Standar Kompetensi • Mahasiswa mampu membandingkan beberapa algoritma dan menentukan algoritma yang terbaik untuk memecahkan kasus-kasus tertentu
28/02/2011
3
Referensi • Introduction to Algorithms, 2nd edition , T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, MIT Press • Introduction to the design and analysis of algorithm, Anany Levitin, Addison Wesley • Diktat Strategi Algoritmik IF2251, Ir. Rinaldi Munir, M.T, Departemen Teknik Informatika, Institut Teknologi Bandung
28/02/2011
4
Penilaian Komponen: Nilai UTS, UAS, dan Tugas Kuliah Penilaian: Tugas Mandiri Hasil UTS Hasil UAS
28/02/2011
= 30 % = 35 % = 35 %
5
Masalah • Pertanyaan atau tugas yang harus dicari jawaban atau penyelesaiannya Solusi • Contoh: mengurutkan bilangan, mencari suatu bilangan, menggabungkan string kalimat, dll
28/02/2011
6
• Contoh: mengurutkan bilangan secara menaik (ascending) – diberikan input masalah: [20, 9, 14, 3, 7, 10, 16, 11], dengan n = 8 – solusi: [3, 7, 9, 10, 11, 14, 16, 20]
28/02/2011
7
Algoritma • Untuk masalah yang besar, solusinya menjadi lebih sulit. • Perlu sebuah prosedur umum yang berisi langkah-langkah penyelesaian masalah algoritma • Algoritma: urutan langkah-langkah untuk memecahkan suatu masalah
28/02/2011
8
• Definisi lain ALGORITMA: – Deretan langkah-langkah komputasi yang mentransformasikan data masukan menjadi keluaran [COR92]. – Deretan instruksi yang jelas untuk memecahkan masalah, yaitu untuk memperoleh keluaran yang diinginkan dari suatu masukan dalam jumlah waktu yang terbatas [LEV03]. – 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 [COR89].
28/02/2011
9
• Notasi apapun dapat digunakan untuk menuliskan algoritma asalkan mudah dibaca dan dipahami. • Misalnya: – Bagan alir (flow chart) – Kalimat-kalimat deskriptif – Pseudo-code (gabungan antara bahasa alami dengan bahasa pemrograman
28/02/2011
10
3 Komponen Algoritma • Paradigma IPO: – Input : masukan – Proses : me-‘*^%$’-kan I O – Output : keluaran
28/02/2011
11
Analisis Algoritma • Sebuah algoritma tidak hanya harus benar, tetapi juga harus mangkus (efficient) • Ukuran kemangkusan algoritma: waktu dan ruang memori (space). • Algoritma yang mangkus: algoritma yang meminimumkan kebutuhan waktu dan ruang
28/02/2011
12
• Alat ukur kemangkusan algoritma: – Kompleksitas waktu, T(n) – Kompleksitas ruang, S(n)
• n = ukuran masukan yang diproses oleh algoritma • T(n) : jumlah operasi yang dilakukan untuk • menjalankan sebuah algoritma sebagai fungsi dari n. • S(n): ruang memori yang dibutuhkan algoritma sebagai fungsi dari n
28/02/2011
13
• Operasi yang dihitung hanyalah operasi dasar (basic operation) saja • Operasi dasar: operasi khas yang mendasari suatu algoritma • Misalnya: – operasi perbandingan elemen pada algoritma pengurutan/pencarian – operasi penjumlahan dan perkalian pada algoritma perkalian matriks
28/02/2011
14
Analisis dan Strategi Algoritma • Nama mata kuliah di prodi ini • Strategi algoritma adalah pendekatan umum untuk memecahkan masalah guna mencapai tujuan yang ditentukan • Analisis algoritma adalah penentuan kelas algoritma
28/02/2011
15
• Analisis dan Strategi Algoritma bertujuan mencari algoritma yang mangkus untuk memecahkan masalah • Ukuran kemangkusan algoritma dinyatakan dengan notasi Ο,Ω, atau Θ.
28/02/2011
16
Mengapa ASA? • Memberikan panduan untuk merancang algoritma bagi masalah baru. • Mengklasifikasikan algoritma berdasarkan gagasan perancangan yang mendasarinya.
28/02/2011
17
Klasifikasi ASA 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
28/02/2011
18
3. Strategi solusi atas-bawah (topdown solution strategies) –
Algoritma Divide and Conquer.
4. Strategi solusi bawah-atas (bottomup solution strategies) –
Dynamic Programming.
28/02/2011
19
Masalah: Keluar dari Labirin
28/02/2011
20
