Download - DAA-PERTEMUAN_2
![Page 1: DAA-PERTEMUAN_2](https://reader037.vdokumen.com/reader037/viewer/2022100304/5571fb474979599169946d20/html5/thumbnails/1.jpg)
1
DESAIN & ANALISISALGORITMA
PERTEMUAN 23/9/2010
![Page 2: DAA-PERTEMUAN_2](https://reader037.vdokumen.com/reader037/viewer/2022100304/5571fb474979599169946d20/html5/thumbnails/2.jpg)
ALGORITMA2
Algoritma bukan merupakanjawaban dari masalah.
Algoritma dapat dianggap
3/9/2010
Algoritma dapat dianggapsebagai serangkaian instruksiuntuk memecahkan masalah.
![Page 3: DAA-PERTEMUAN_2](https://reader037.vdokumen.com/reader037/viewer/2022100304/5571fb474979599169946d20/html5/thumbnails/3.jpg)
Langkah-langkah PembuatanAlgoritma
Pemahaman Permasalahan
Memutuskan:sarana komputasi,
pencarian solusi tepat atau approksimasi,struktur data,
teknik desain algoritma
Desain algoritma
Pembuktian kebenaranalgoritma
Analisis algoritma
Penulisan kode (source code)
![Page 4: DAA-PERTEMUAN_2](https://reader037.vdokumen.com/reader037/viewer/2022100304/5571fb474979599169946d20/html5/thumbnails/4.jpg)
1. Pemahaman Masalah
Sebelum memulai merancang algoritma,permasalahan harus benar-benar dipahami terlebihdahulu.
Ada beberapa kategori permasalahan yang sering Ada beberapa kategori permasalahan yang seringmuncul di dunia komputing dan telah memilikialgoritma penyelesaiannya. Jika permasalahanyang akan diselesaikan termasuk dalam kategoritersebut, kita dapat mengacu kepada algoritmapenyelesaiannya.
![Page 5: DAA-PERTEMUAN_2](https://reader037.vdokumen.com/reader037/viewer/2022100304/5571fb474979599169946d20/html5/thumbnails/5.jpg)
2.1. Penentuan Kemampuan AlatKomputasi
Algoritma yg digunakan sekarang ini masih mengacu kemodel komputer John von Neumann (1903-1957), yaituarsitektur Random Access Memory (RAM).
Arsitektur RAM mengasumsikan bahwa instruksi2 komputerdieksekusi satu per satu, baris per baris instruksi. Algoritmadieksekusi satu per satu, baris per baris instruksi. Algoritmayang didesain untuk dieksekusi pada jenis mesin tersebutdisebut sequential algorithm.
Generasi terbaru komputer saat ini memungkinkan proseseksekusi secara paralel (parallel computing). Algoritmanyadisebut parallel algorithm.
![Page 6: DAA-PERTEMUAN_2](https://reader037.vdokumen.com/reader037/viewer/2022100304/5571fb474979599169946d20/html5/thumbnails/6.jpg)
2.2. Exact vs Approximate Solution
Exact solution: solusi tepat untuk pemecahan masalah
Approximate solution: solusi yang paling mendekati solusipemecahan masalah
Beberapa permasalahan yang menggunakan approximatesolution:solution:
Pencarian akar kuadrat
Persamaan non-linier
Permasalahan2 yg exact solution nya membutuhkan waktu yangsangat lama karena tingkat kompleksitasnya tinggi
![Page 7: DAA-PERTEMUAN_2](https://reader037.vdokumen.com/reader037/viewer/2022100304/5571fb474979599169946d20/html5/thumbnails/7.jpg)
2.3. Penentuan Struktur Data
Pemilihan struktur data yang paling tepatsangat menentukan performa dari algoritmayang akan didesain.
Algorithms + Data Structures = Programs Algorithms + Data Structures = Programs(Wirth1976)
Macam2 struktur data: array, linked list,stack, queue, hash table
![Page 8: DAA-PERTEMUAN_2](https://reader037.vdokumen.com/reader037/viewer/2022100304/5571fb474979599169946d20/html5/thumbnails/8.jpg)
2.4. Teknik Desain Algoritma
Teknik Desain Algoritma merupakan pendekatan umumuntuk memecahkan masalah dengan algoritma yang dapatditerapkan ke berbagai permasalahan pada area yangberbeda di dunia komputing. (LEV2007)
Mempelajari berbagai macam teknik desain algoritma Mempelajari berbagai macam teknik desain algoritmadapat membantu kita dalam mendesain algoritma untukpermasalahan baru.
Teknik desain algoritma mengelompokkan algoritma sesuaiide dasarnya, sehingga dapat mempermudahpengkategorian dan pembelajarannya.
![Page 9: DAA-PERTEMUAN_2](https://reader037.vdokumen.com/reader037/viewer/2022100304/5571fb474979599169946d20/html5/thumbnails/9.jpg)
3. Metode untuk MenspesifikasikanAlgoritma
Beberapa metode yang dapat digunakan untuk menggambarkanalgoritma adalah: Pseudocode
Gabungan antara bahasa natural dan bentuk bahasa pemrograman.Contoh:
ALGORITHM Euclid(m,n)
//Menghitung FPB(m,n)//Menghitung FPB(m,n)
while n≠0 do
r m mod n
m n
n r
return m
Flowchart
Menggunakan bentuk geometri yang mendeskripsikan langkah-langkahalgoritma
![Page 10: DAA-PERTEMUAN_2](https://reader037.vdokumen.com/reader037/viewer/2022100304/5571fb474979599169946d20/html5/thumbnails/10.jpg)
4. Pembuktian Kebenaran Algoritma
Merupakan langkah untuk membuktikan apakah algoritmamenghasilkan hasil yang diinginkan untuk sembarang inputyang sah dalam waktu yang finite.
Contoh: Pada Algoritma Euclid, FPB(m,n), nilainya akansemakin kecil pada setiap iterasi dan algoritma berhentiketika angka kedua bernilai 0.ketika angka kedua bernilai 0.
Teknik yang umumnya digunakan untuk pembuktianalgoritma adalah dengan induksi matematika.
Catatan: Tracing tidak menjamin kebenaran suatualgoritma.
Jika algoritma terbukti tidak benar, maka dilakukanredesign atau pertimbangkan untuk mengubah struktur datayang digunakan.
![Page 11: DAA-PERTEMUAN_2](https://reader037.vdokumen.com/reader037/viewer/2022100304/5571fb474979599169946d20/html5/thumbnails/11.jpg)
5. Analisis Algoritma
Kita ingin agar algoritma kita berkualitas.Beberapa faktor yang dipertimbangkan:
Efficiency
Time efficiency (seberapa cepat algoritma)
Space efficiency (berapa memori yang dibutuhkan)
Simplicity (berkaitan dengan keindahan dankesederhanaan)
Generality (berkaitan dengan ruang lingkuppermasalahan yang diselesaikan dan range input yangdapat diterima oleh algoritma)
![Page 12: DAA-PERTEMUAN_2](https://reader037.vdokumen.com/reader037/viewer/2022100304/5571fb474979599169946d20/html5/thumbnails/12.jpg)
6. Penulisan Kode
Transisi dari algoritma ke sourcecode merupakan hal yangberesiko, karena berpotensimenghasilkan program yangsalah atau sangat tidak efisien.
Validitas program perlu dicek Validitas program perlu dicekdengan melakukan testing dandebugging.
RULE: A good algorithmis a result of repeatedeffort and rework
![Page 13: DAA-PERTEMUAN_2](https://reader037.vdokumen.com/reader037/viewer/2022100304/5571fb474979599169946d20/html5/thumbnails/13.jpg)
Tipe Permasalahan Penting
Sorting (Pengurutan) Mengurutkan sejumlah item secara
menaik atau menurun, berdasarkan
key (kunci).
Sorting memudahkan pencarian sebuah item (Contoh: kamus, buku Sorting memudahkan pencarian sebuah item (Contoh: kamus, bukutelepon, daftar absensi, dll).
Ada banyak algoritma sorting, beberapa algoritma lebih ungguldari yang lain, tetapi tidak ada algoritma terbaik yang dapatmenyelesaikan semua permasalahan.
Dua sifat yang perlu diperhatikan:
Stabil : Menjaga urutan 2 item dengan nilai yang sama
In place : Tidak membutuhkan memori tambahan
![Page 14: DAA-PERTEMUAN_2](https://reader037.vdokumen.com/reader037/viewer/2022100304/5571fb474979599169946d20/html5/thumbnails/14.jpg)
Searching (Pencarian)
Mencari sebuah item tertentu dalam sebuah himpunan,berdasarkan key.
Ada banyak algoritma pencarian, mulai dari yangsederhana hingga yang kompleks.
Tidak ada algoritma yang paling sesuai untuk semua Tidak ada algoritma yang paling sesuai untuk semuakondisi. Beberapa algoritma bekerja lebih cepat tetapimembutuhkan memori tambahan; algoritma lainnya, cepattetapi hanya dapat bekerja pada array yang sudahterurut, dst.
Umumnya searching digunakan bersamaan dengan prosespenambahan (add), pengubahan (update), danpenghapusan (delete) item.
![Page 15: DAA-PERTEMUAN_2](https://reader037.vdokumen.com/reader037/viewer/2022100304/5571fb474979599169946d20/html5/thumbnails/15.jpg)
String Processing (Pemrosesan String)
String: Kumpulan karakter dari alfabet.
Macam-macam string:
Text string: terdiri dari abjad (A-Z), angka (0-9), karakter spesial (!, #)
Bit string: terdiri dari nilai 0 dan 1
Gene sequence: dimodelkan dengan string karakter terdiri dari huruf A(Adenine), C (Cytosine),(Adenine), C (Cytosine),
G (Guanine), T (Thymine)
Algoritma pemrosesan string sudah digunakan sejak komputerdiciptakan (untuk pemrosesan bahasa komputer dan kompilasi)
String matching (Pencocokan string): pencarian sebuah kata dalamsebuah teks.
![Page 16: DAA-PERTEMUAN_2](https://reader037.vdokumen.com/reader037/viewer/2022100304/5571fb474979599169946d20/html5/thumbnails/16.jpg)
Permasalahan Graph
Graph: Sekumpulan vertex yang dihubungkan oleh garis
yang disebut edge
Graph dapat digunakan untuk memodelkan
permasalahan, di antaranya jaringan transportasi &
telekomunikasi, penjadwalan proyek, dan game.telekomunikasi, penjadwalan proyek, dan game.
Beberapa algoritma Graph:
Penelusuran graph (graph traversal)
Pencarian path terpendek (shortest-path)
Pengurutan graph secara topologis
Beberapa permasalahan graph:
Traveling Salesman Problem (TSP)
Graph-coloring Problem
![Page 17: DAA-PERTEMUAN_2](https://reader037.vdokumen.com/reader037/viewer/2022100304/5571fb474979599169946d20/html5/thumbnails/17.jpg)
Combinatorial Problem
Permasalahan Kombinatorik:permasalahan yang mencari objekkombinatorik (misal: permutasi,kombinasi, atau himpunan bagian)yang memenuhi batasan tertentudan sifat yang diinginkan (misal:memaksimalkan nilai ataumeminimalkan biaya)meminimalkan biaya)
Contoh: Traveling Salesman Problem
Secara umum, merupakanpermasalahan tersulit di duniakomputing untuk 2 alasan: Jumlah objek kombinatorik “tumbuh”
sangat cepat jika ukuranpermasalahan semakin besar
Tidak ada algoritma yang dapatdengan tepat menyelesaikanpermasalahan ini dalam waktu yangreasonable
![Page 18: DAA-PERTEMUAN_2](https://reader037.vdokumen.com/reader037/viewer/2022100304/5571fb474979599169946d20/html5/thumbnails/18.jpg)
Permasalahan Geometrik
Algoritma Geometrik berhubungan dengan objek geometrikseperti titik, garis, dan poligon.
Algoritma geometrik dapat diaplikasikan pada aplikasiseperti computer graphic, robotika, dan tomografi(pengambilan gambar dengan metode section contoh:(pengambilan gambar dengan metode section contoh:alat CT-Scan).
Contoh algoritma geometrik:
Closest-pair problem: Mencari jarak terdekat antara dua titikpada sebuah bidang
Convex-hull problem: Mencari poligon konveks
terkecil yang mencakup semua titik yang ada
pada sebuah bidang
![Page 19: DAA-PERTEMUAN_2](https://reader037.vdokumen.com/reader037/viewer/2022100304/5571fb474979599169946d20/html5/thumbnails/19.jpg)
Permasalahan Numerik
Merupakan permasalahan yangmelibatkan penggunaan objekmatematika yang kontinyu:penyelesaikan persamaan,penghitungan integral, evaluasi fungsi,dsb.
Mayoritas dapat diselesaikan secaraaproksimasi saja.aproksimasi saja.
Sempat menjadi primadona bagiilmuwan untuk menyelesaikanpermasalahan sains dan engineering.
Sejak 25 tahun lalu, dunia komputingbergeser ke arah bisnis, sehinggaalgoritma yang dibutuhkan adalahalgoritma untuk penyimpananinformasi, temu kembali (retrieval),transportasi melalui jaringan, danpresentasi kepada pengguna.
![Page 20: DAA-PERTEMUAN_2](https://reader037.vdokumen.com/reader037/viewer/2022100304/5571fb474979599169946d20/html5/thumbnails/20.jpg)
Small Quiz
1. Jelaskan langkah2 pembuatan algoritma!
2. Jelaskan perbedaan antara exact solution danapproximation solution!
3. Apa yang dimaksud dengan permasalahan
20
3. Apa yang dimaksud dengan permasalahankombinatorik? Jelaskan dan berikan contohnya!
3/9/2010
![Page 21: DAA-PERTEMUAN_2](https://reader037.vdokumen.com/reader037/viewer/2022100304/5571fb474979599169946d20/html5/thumbnails/21.jpg)
Fundamental Data Structures
Linear Data Structures
Array
Menyimpan data yang memiliki tipe yang sama
21
Item[0] Item[1] Item[2] ….. Item[n-1]
Menyimpan data yang memiliki tipe yang sama
Data diakses dengan menspesifikasikan index dari array
3/9/2010
![Page 22: DAA-PERTEMUAN_2](https://reader037.vdokumen.com/reader037/viewer/2022100304/5571fb474979599169946d20/html5/thumbnails/22.jpg)
Fundamental Data Structures(cont’d)
Linked List
Tiap elemen disebut sebagai node yang menyimpan 2 info: sebuahdata dan pointer ke node lain dalam list
Jika pointer dari sebuah node bernilai null, maka node tersebut tidak
22
Jika pointer dari sebuah node bernilai null, maka node tersebut tidakmemiliki node lanjutan (successor)
Node diakses dengan menunjuk pada node pertama dan menelusuripointer sampai ditemukan node yang dicari
Array dan Linked List digunakan untukmerepresentasikan abstract data type (tipe dataabstrak) LIST
3/9/2010
![Page 23: DAA-PERTEMUAN_2](https://reader037.vdokumen.com/reader037/viewer/2022100304/5571fb474979599169946d20/html5/thumbnails/23.jpg)
Fundamental Data Structures(cont’d)
Stacks : Proses insert dan delete hanya dapatdilakukan dari 1 ujung saja (top)
Queue: Proses delete dilakukan dari front(dequeue) dan proses insert dilakukan dari rear
23
(dequeue) dan proses insert dilakukan dari rear(enqueue)
Priority queue: queue yang sudah terurut
Heap: Pengembangan dari priority queue (minimumheap dan maximum heap)
3/9/2010
![Page 24: DAA-PERTEMUAN_2](https://reader037.vdokumen.com/reader037/viewer/2022100304/5571fb474979599169946d20/html5/thumbnails/24.jpg)
Fundamental Data Structures(cont’d)
Graphs
Terdiri dari sekumpulan vertex yang saling terhubungoleh edge
Direpresentasikan dengan adjacency matrix
24
Weighted graph: Graph yang edge-nya memiliki bobot
3/9/2010
a bc
de
8
4
4
9
62
1253
![Page 25: DAA-PERTEMUAN_2](https://reader037.vdokumen.com/reader037/viewer/2022100304/5571fb474979599169946d20/html5/thumbnails/25.jpg)
Trees
Graph yang tidak memiliki cycle (acyclic)
Sets and Dictionaries
25
Sets and Dictionaries
Set: Himpunan elemen tidak terurut yang berbeda satu sama lain
Multiset: Himpunan elemen tidak terurut yang tidak harus berbeda satusama lain
Dictionary: Struktur data yang mengimplementasikan pencarian,penambahan, penghapusan item di dalam set/multiset
3/9/2010