1-intro strategi algoritmik

1

INTRODUKSI STRATEGI

ALGORITMIKS1 Teknik Informatika

Universitas Kristen Maranatha

2

STRATEGI ALGORITMIK kumpulan metode atau teknik untuk

memecahkan masalah guna mencapai tujuan yang ditentukan

deskripsi metode atau teknik tsb dinyatakan dalam suatu urutan langkah-langkah penyelesaian (ALGORITMA) [1]

3

INTRODUCTION Strategi pemecahan masalah

Tujuan : mendapatkan algoritma yang efisien dalam memecahkan suatu masalah

Notasi Big OAlat untuk membandingkan beberapa

algoritma Efisiensi berdasarkan waktu proses

4

STRATEGI PEMECAHAN MASALAH Strategi solusi langsung (direct solution strategies)

Algoritma Brute force Algoritma Greedy

5

STRATEGI PEMECAHAN MASALAH Strategi solusi langsung

Algoritma Brute force Exhaustive search/ generate and test Enumerasi semua kemungkinan solusi Combinatorial explosion

Contoh : mencari bilangan prima antara 1 s.d N Mis. N adalah 20, maka bil. prima : 2, 3, 5, 7, 11, 13, 17, 19

6

CONTOH BRUTE FORCE: CARI BILANGAN PRIMA (1/2)

[2]

7

CONTOH BRUTE FORCE: CARI BILANGAN PRIMA (2/2)

Komputer: AMD Turion 64 1.9 GHz dengan 2 GB RAM, 160 GB HDD dan Windows Vista.

8

STRATEGI PEMECAHAN MASALAH Strategi solusi langsung

Algoritma Greedy Pencarian solusi yang optimum

Contoh : Mencari jalur tersingkat dari kota A ke B Menghitung koin/lembaran uang kembalian/

gajian pegawai Mis. 3600 : 3 lembar ribuan, 1 koin 500, 1 koin

100

9

STRATEGI PEMECAHAN MASALAH Strategi berbasis pencarian pada

ruang status (state-space base strategies)Algoritma Backtracking Algoritma Branch and Bound

10

STRATEGI PEMECAHAN MASALAH Strategi berbasis pencarian pada

ruang statusAlgoritma Backtracking

Enumerasi set of partial candidates Dalam bentuk search tree Memakai Depth First Search Lebih cepat dari Brute Force

Contoh : perwarnaan peta (map coloring)

11

STRATEGI PEMECAHAN MASALAH Strategi berbasis pencarian pada

ruang status Algoritma Branch and Bound

Menemukan solusi optimal Memakai strategi Best First Search

Contoh : Traveling Salesman Problem

12

STRATEGI PEMECAHAN MASALAH Strategi solusi atas-bawah (top-down solution strategies)

Algoritma Divide and Conquer

Strategi solusi bawah-atas (bottom-up solution strategies)

Dynamic Programming

13

STRATEGI PEMECAHAN MASALAH Strategi solusi atas-bawah (top-down solution strategies)

Algoritma Divide and Conquer Dekomposisi masalah Pemecahan sub masalah Penggabungan solusi

Contoh : Quick sort Merge sort

14

STRATEGI PEMECAHAN MASALAH Strategi solusi bawah-atas (bottom-up solution strategies)

Dynamic Programming pemecahan masalah dengan cara menguraikan

solusi menjadi sekumpulan langkah (step) /tahapan (stage)

solusi dari persoalan dapat dipandang dari serangkaian keputusan yang saling berkaitan

Contoh : Knapsack 0/1 problem

15

LANGKAH DASAR ALGORITMA Sederhanakan masalah Membangun rencana penyelesaian

secara matematis Merancang algoritma Menguji kebenaran algoritma Implementasi dengan suatu bahasa

pemrograman yang dimengerti Dokumentasi Analisis kompleksitas algoritma

16

WAKTU PROSES ALGORITMA (1/2) Waktu proses algoritma

lamanya waktu yang diperlukan komputer untuk menjalankan sebuah algoritma.

Karena kecepatan komputer yang biasa kita gunakan sangat tinggi, maka biasanya waktu proses itu tidak terlalu kita perhatikan.

Tidak semua algoritma dapat selesai diproses dalam waktu kurang dari satu detik.

17

WAKTU PROSES ALGORITMA (2/2) Algoritma yang kompleks dapat

memerlukan waktu beberapa menit hingga berhari-hari untuk menyelesaikan prosesnya.

Hal ini berlaku bahkan di komputer paling canggih sekalipun.

Sejumlah algoritma dengan kompleksitas sangat tinggi bahkan ada yang memakan waktu lebih dari satu tahun untuk mengeluarkan hasil.

Dalam hal merancang algoritma yang cukup kompleks, sangat penting bagi kita untuk menghitung waktu proses algoritma.

18

VARIASI WAKTU PROSES (1/2) Algoritma bekerja berdasarkan input

yang dimasukkan user.

Setiap input memiliki ukuran. Misalnya kita hendak mengurutkan sejumlah bilangan, banyaknya bilangan yang perlu diurutkan merupakan ukuran besarnya input

Makin besar ukuran input yang dimasukkan, pada umumnya waktu proses akan semakin lama.

19

VARIASI WAKTU PROSES (2/2) Tergantung pada isi input, waktu proses

dapat bervariasi :Keadaan terbaik (best case)

Dilambangkan dengan notasi (...) dibaca Theta

Keadaan rata-rata (average case) Dilambangkan dengan notasi (...)

dibaca OmegaKeadaan terburuk (worst case)

Dilambangkan dengan notasi O(...) dibaca Big-O

Kinerja sebuah algoritma biasanya diukur dengan menggunakan patokan keadaan terburuk (worst case) yang dinyatakan dengan Big-O

20

NOTASI BIG O Big-Oh

Deskripsi umum dari algoritmaCompare algorithms in the limit

Mis. 20N hours vs N2 microseconds which is better?

21

CONTOHy = 3x

y = 6x-2

y = 15x + 44

Family O(n)

Kurva garis lurus Double input → double

time

y = x2

y = x2-6x+9

y = 3x2+4x

Family O(n2)

Kurva parabolaDouble input → quadruple time

22

DEFINISI FORMAL O-notation is an upper-bound, this

means that N is O(N), but it is also O(N2); we try to provide tight bounds. Formally:A function g(N) is O(f(N)) if there exist

constants c and n such that g(N) < cf(N) for all N > n cf(N)

g(N)

x = n

23

BIG-OH CALCULATIONS FROM CODE Search for element in array:

What is complexity (using O-notation)? A adalah array yang memiliki indeks 0, ..., n-1

Algoritma mencari posisi x di dalam array A return posisi x (idx) indeks 0 while (indeks < n) and (Aindeks x) do

indeks indeks + 1 endwhile

{ indeks < n } if indeks < n then { x ditemukan } idx indeks else idx -1 { x tidak ditemukan } endif

Best case? Average case? Worst case?

24

MEASURES OF COMPLEXITY

Worst caseGood upper-bound on behaviorNever get worse than this

Average caseWhat does average mean? Averaged over all inputs? Assuming uniformly

distributed random data?

25

MEMBACA BIG-OH O(1) artinya algoritma konstan O(log n) contohnya pada full balanced

Binary Search Tree O(n) artinya algoritma linear O(n log n) contohnya algoritma merge sort O(n2) artinya algoritma quadratic O(n3) artinya algoritma qubic O(nm) artinya algoritma eksponensial Notasi Big-O bisa berisi kombinasi dari

contoh di atas

26

ALGORITMA ITU PENTING (1/2) Komputer A yang cepat (109 instruksi

per detik) melakukan insertion sort melawan komputer B yang lebih lambat (107 instruksi per detik) melakukan merge sort. Manakah yang lebih cepat? [3]

Masing2 komputer hendak mengurutkan 1.000.000 bilangan.

Insertion sort 2n2 instruksi untuk mengurutkan n bilangan.

27

ALGORITMA ITU PENTING (2/2) Merge sort 50n log n instruksi untuk

mengurutkan 1.000.000 bilangan.

Untuk mengurutkan 1.000.000 bilangan, komputer A membutuhkan

Komputer B membutuhkan

28

106 INSTRUCTIONS/SEC, RUNTIMES

N O(log N)

O(N) O(N log N)

O(N2)

10 0.000003 0.00001 0.000033 0.0001

100 0.000007 0.00010 0.000664 0.1000

1,000 0.000010 0.00100 0.010000 1.0

10,000 0.000013 0.01000 0.132900 1.7 min

100,000 0.000017 0.10000 1.661000 2.78 hr

1,000,000 0.000020 1.0 19.9 11.6 day

1,000,000,000

0.000030 16.7 min 18.3 hr 318 centuries

29

LATIHAN Buatlah algoritma untuk mencari suatu

nilai dalam suatu matriks A berukuran n x n.

Bagaimana kompleksitas algoritma tersebut jika dituliskan dengan notasi big O ?

Best case ? Average case ? Worst case ?

30

BUAT RANGKUMAN Buat rangkuman untuk membantu

pemahaman saudara:Bab 2.1 dan Tabel di halaman 59 dari bukuIntroduction to The Design and Analysis of Algorithms 2nd edition oleh Anany Levitin.

Buat rangkuman dengan tulisan tangan. Dikumpulkan besok (8 Januari 2013)

sebelum perkuliahan dimulai.

31

REFERENSI[1] Materi kuliah IF 2251 Strategi Algoritmik :

http://kur2003.if.itb.ac.id/ Mata kuliah IF 2251 Strategi Algoritmik (sem.4)

[2] Efficient Prime Number Generating Algorithmshttps://en.wikibooks.org/wiki/Efficient_Prime_Number_Generating_Algorithms

[3] Cormen, T.H., Leiserson, C. E., Rivest, R.L., dan Stein, C. (2007) Introduction to Algorithms 2nd edition. The MIT Press.