1

DESAIN & ANALISISALGORITMA

PERTEMUAN 23/9/2010

ALGORITMA2

Algoritma bukan merupakanjawaban dari masalah.

Algoritma dapat dianggap

3/9/2010

Algoritma dapat dianggapsebagai serangkaian instruksiuntuk memecahkan masalah.

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)

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.

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.

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

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

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.

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

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.

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)

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

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

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.

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.

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

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

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

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.

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

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

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

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

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

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