1 overview
TRANSCRIPT
![Page 1: 1 Overview](https://reader035.vdokumen.com/reader035/viewer/2022080223/55cf98c5550346d0339993c3/html5/thumbnails/1.jpg)
Analisis dan Strategi AlgoritmaAnalisisAnalisis dan Strategi Algoritmadan Strategi Algoritma
![Page 2: 1 Overview](https://reader035.vdokumen.com/reader035/viewer/2022080223/55cf98c5550346d0339993c3/html5/thumbnails/2.jpg)
28/02/2011 2
Deskripsi Mata Kuliah• Konsep dasar analisis algoritma
• Beberapa jenis algoritma
![Page 3: 1 Overview](https://reader035.vdokumen.com/reader035/viewer/2022080223/55cf98c5550346d0339993c3/html5/thumbnails/3.jpg)
28/02/2011 3
Standar Kompetensi• Mahasiswa mampu membandingkan
beberapa algoritma dan menentukan algoritma yang terbaik untuk memecahkan kasus-kasus tertentu
![Page 4: 1 Overview](https://reader035.vdokumen.com/reader035/viewer/2022080223/55cf98c5550346d0339993c3/html5/thumbnails/4.jpg)
28/02/2011 4
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
![Page 5: 1 Overview](https://reader035.vdokumen.com/reader035/viewer/2022080223/55cf98c5550346d0339993c3/html5/thumbnails/5.jpg)
28/02/2011 5
Penilaian Komponen:
Nilai UTS, UAS, dan Tugas Kuliah
Penilaian: Tugas Mandiri = 30 %
Hasil UTS = 35 %
Hasil UAS = 35 %
![Page 6: 1 Overview](https://reader035.vdokumen.com/reader035/viewer/2022080223/55cf98c5550346d0339993c3/html5/thumbnails/6.jpg)
28/02/2011 6
Masalah• Pertanyaan atau tugas yang harus
dicari jawaban atau penyelesaiannya Solusi
• Contoh: mengurutkan bilangan, mencari suatu bilangan, menggabungkan string kalimat, dll
![Page 7: 1 Overview](https://reader035.vdokumen.com/reader035/viewer/2022080223/55cf98c5550346d0339993c3/html5/thumbnails/7.jpg)
28/02/2011 7
• 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]
![Page 8: 1 Overview](https://reader035.vdokumen.com/reader035/viewer/2022080223/55cf98c5550346d0339993c3/html5/thumbnails/8.jpg)
28/02/2011 8
Algoritma• Untuk masalah yang besar, solusinya
menjadi lebih sulit.• Perlu sebuah prosedur umum yang
berisi langkah-langkah penyelesaianmasalah algoritma
• Algoritma: urutan langkah-langkahuntuk memecahkan suatu masalah
![Page 9: 1 Overview](https://reader035.vdokumen.com/reader035/viewer/2022080223/55cf98c5550346d0339993c3/html5/thumbnails/9.jpg)
28/02/2011 9
• 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 suatumasukan dalam jumlah waktu yang terbatas [LEV03].
– Prosedur komputasi yang terdefinisi dengan baik yang menggunakan beberapa nilai sebagai masukan danmenghasilkan beberapa nilai yang disebut keluaran. Jadi, algoritma adalah deretan langkah komputasi yang mentransformasikan masukan menjadi keluran [COR89].
![Page 10: 1 Overview](https://reader035.vdokumen.com/reader035/viewer/2022080223/55cf98c5550346d0339993c3/html5/thumbnails/10.jpg)
28/02/2011 10
• Notasi apapun dapat digunakan untukmenuliskan algoritma asalkan mudah dibacadan dipahami.
• Misalnya:– Bagan alir (flow chart)
– Kalimat-kalimat deskriptif
– Pseudo-code (gabungan antara bahasa alamidengan bahasa pemrograman
![Page 11: 1 Overview](https://reader035.vdokumen.com/reader035/viewer/2022080223/55cf98c5550346d0339993c3/html5/thumbnails/11.jpg)
28/02/2011 11
3 Komponen Algoritma• Paradigma IPO:
– Input : masukan
– Proses : me-‘*^%$’-kan I O
– Output : keluaran
![Page 12: 1 Overview](https://reader035.vdokumen.com/reader035/viewer/2022080223/55cf98c5550346d0339993c3/html5/thumbnails/12.jpg)
28/02/2011 12
Analisis Algoritma• Sebuah algoritma tidak hanya harus benar,
tetapi juga harus mangkus (efficient)
• Ukuran kemangkusan algoritma: waktu danruang memori (space).
• Algoritma yang mangkus: algoritma yang meminimumkan kebutuhan waktu dan ruang
![Page 13: 1 Overview](https://reader035.vdokumen.com/reader035/viewer/2022080223/55cf98c5550346d0339993c3/html5/thumbnails/13.jpg)
28/02/2011 13
• 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
![Page 14: 1 Overview](https://reader035.vdokumen.com/reader035/viewer/2022080223/55cf98c5550346d0339993c3/html5/thumbnails/14.jpg)
28/02/2011 14
• Operasi yang dihitung hanyalah operasidasar (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
![Page 15: 1 Overview](https://reader035.vdokumen.com/reader035/viewer/2022080223/55cf98c5550346d0339993c3/html5/thumbnails/15.jpg)
28/02/2011 15
Analisis dan Strategi Algoritma
• Nama mata kuliah di prodi ini
• Strategi algoritma adalah pendekatan umum untuk memecahkan masalahguna mencapai tujuan yang ditentukan
• Analisis algoritma adalah penentuan kelas algoritma
![Page 16: 1 Overview](https://reader035.vdokumen.com/reader035/viewer/2022080223/55cf98c5550346d0339993c3/html5/thumbnails/16.jpg)
28/02/2011 16
• Analisis dan Strategi Algoritmabertujuan mencari algoritma yang mangkus untuk memecahkan masalah
• Ukuran kemangkusan algoritmadinyatakan dengan notasi Ο,Ω, atauΘ.
![Page 17: 1 Overview](https://reader035.vdokumen.com/reader035/viewer/2022080223/55cf98c5550346d0339993c3/html5/thumbnails/17.jpg)
28/02/2011 17
Mengapa ASA?• Memberikan panduan untuk
merancang algoritma bagi masalahbaru.
• Mengklasifikasikan algoritmaberdasarkan gagasan perancanganyang mendasarinya.
![Page 18: 1 Overview](https://reader035.vdokumen.com/reader035/viewer/2022080223/55cf98c5550346d0339993c3/html5/thumbnails/18.jpg)
28/02/2011 18
Klasifikasi ASA1. Strategi solusi langsung (direct solution
strategies)– Algoritma Brute Force
– Algoritma Greedy
2. Strategi berbasis pencarian pada ruangstatus (state-space base strategies)– Algoritma Backtracking
– Algoritma Branch and Bound
![Page 19: 1 Overview](https://reader035.vdokumen.com/reader035/viewer/2022080223/55cf98c5550346d0339993c3/html5/thumbnails/19.jpg)
28/02/2011 19
3. Strategi solusi atas-bawah (top-down solution strategies)
– Algoritma Divide and Conquer.
4. Strategi solusi bawah-atas (bottom-up solution strategies)
– Dynamic Programming.
![Page 20: 1 Overview](https://reader035.vdokumen.com/reader035/viewer/2022080223/55cf98c5550346d0339993c3/html5/thumbnails/20.jpg)
28/02/2011 20
Masalah: Keluar dari Labirin