Analisis dan Strategi Algoritma
1
K01-
Agenda • • • •
Apa itu Algoritma Sekilas Materi Kuliah Contoh Penerapan Algoritma Tanya Jawab
2
K01-
TigaAn • 3 Ciri Algoritma –
Terencana, Dapat dilakukan, Selesai
• 3 state Algoritma –
Pre, while, Post
• 3 AlgoritmaSeminal • 3 kondisi Analysis –
Al-K, Recipe, DNA
• 3 dalam Paradigma –
Input, Proses, Output
–
Best, Worst, Average
• 3 macam Solusi –
Satu, banyak, tanpa
• 3 jurus dasar: –
Search, Sort, Merge
3
K01-
Apakah Strategi, Algoritma dan Analisis Algoritma Itu? •
Strategi adalah rencana yang cermat mengenai kegiatan untuk mencapai sasaran khusus
•
Algoritma :
•
Urutan langkah-langkah untuk memecahkan suatu masalah Terencana, dapat dilakukan, selesai
Analisis algoritma : penentuan kelas algoritma
4
K01-
Referensi Kuliah • Text
– Introduction to Algorithms, 2nd edition T. H. Cormen, C. E. Leiserson, R. L. Rivest, and Clifford Stein Published by: MIT Press or McGraw-Hill – Introduction to the design and analysis of algorithm Anany Levitin Published by: Addison Wesley
• Reference:
– Diktat Strategi Algoritmik IF2251, Ir. Rinaldi Munir, M.T, Departemen Teknik Informatika, Institut Teknologi Bandung
5
K01-
• Strategi algoritmik adalah • kumpulan metode/teknik untuk memecahkan masalah guna mencapai tujuan yang ditentukan, • yang dalam hal ini deskripsi metode atau teknik tersebut dinyatakan dalam suatu urutan langkah-langkah penyelesaian. 6
K01-
Standar Kompetensi Setelah mengikuti matakuliah ini diharapkan mahasiswa mampu menganalisis kebenaran suatu algoritma terhadap kasus-kasus tertentu 7
K01-
Pokok Bahasan •
Basic algorithmic analysis
– – –
– – –
Asymptotic analysis of upper and average complexity bounds Identifying differences among best, average, and worst case behaviors Big "O," little "o," omega, and theta notation Standard complexity classes Time and space tradeoffs in algorithms Using recurrence relations, characteristic equation, and master theorem to analyze recursive algorithms
•
Algorithmic strategies
–
Fundamental computing
1. 2. 3. 4. 5. 6. 7.
Brute-force algorithms Greedy algorithms Divide-and-conquer Backtracking Branch-and-bound Heuristics Pattern matching and string/text algorithms 8. Numerical approximation algorithms 9. Dynamic Programming
algorithms 8
K01-
3 Algoritma Seminal • I: pen and paper – Angka Arab, Al-Khawarizmi, Yang mana?
• II: Resep Masakan – China, Cap Cay
• III: DNA – Kompleks dalam kesederhanaan
9
K01-
I: Pen and Paper • Bagaimana kita melakukan perkalian bilangan? – Hafalan – Dengan Bantuan • Tangan • Kertas • Kalkulator
• Manakah yang merupakan Algoritma? 10
K01-
Mengalikan menggunakan Kertas • Menggunakan Angka Arab
2345 678 x 18760 16415 14070 + 1589910
• Angka Romawi
MMCCCVL DLXXVIII x
?
11
K01-
Pencil and Paper • • • • • •
Penjumlahan Pengurangan Perkalian Pembagian Akar Bilangan Pangkat Bilangan
12
K01-
3 Komponen Algoritma • Paradigma IPO Setiap Algoritma dapat disebutkan: • Input : masukan • Proses : me-‘*^%$’-kan I O • Output : keluaran
13
K01-
Latihan
I: Pen and Paper
• Pada Algoritma perkalian menggunakan kertas, sebutkan IPOnya. • Input : Dua buah bilangan • Proses : <pre-memory> • Output : Bilangan hasil perkalian
14
K01-
II: Resep Masakan Resep membuat Cap Cay • Input : Bahan Masakan, dan Cara Memrosesnya • Proses :
• Output : Cap Cay untuk 6 orang
15
K01-
Algorithm in Action Contoh Kasus
16
K01-
Why we study Theory? Demo
17
K01-
Card Trick • A volunteer, please.
18
K01-
Binary Search like example Contoh penerapan Loop Invariant
19
K01-
Pick a Card
Done 20
K01-
Loop Invariant: The selected card is one of these.
21
K01-
Which column?
left 22
K01-
Loop Invariant: The selected card is one of these.
23
K01-
Selected column is placed in the middle
24
K01-
I will rearrange the cards
25
K01-
Relax Loop Invariant: I will remember the same about each column.
26
K01-
Which column?
right 27
K01-
Loop Invariant: The selected card is one of these.
28
K01-
Selected column is placed in the middle
29
K01-
I will rearrange the cards
30
K01-
Which column?
left 31
K01-
Loop Invariant: The selected card is one of these.
32
K01-
Selected column is placed in the middle
33
K01-
Here is your card.
Wow! 34
K01-
Loop Invariants Suatu cara yang baik untuk menyusun program: – Simpan semua yang anda tahu pada basisdata. – Pada loop utama, update basisdata ini pada saat program dijalankan.
35
K01-
Introduction •So you want to be a computer scientist? •Grade School Revisited: How To Multiply Two Numbers Jeff Edmonds York University
Lecture 1
36
K01-
COSC 3101
So you want to be a computer scientist?
37
K01-
Is your goal to be a mundane programmer?
38
K01-
Or a great leader and thinker?
39
K01-
Original Thinking
40
K01-
Boss assigns task: – Given today’s prices of sausage, grain, sawdust, … – Given constraints on what constitutes a hotdog. – Make the cheapest hotdog.
41 Everyday industry asks these questions. K01-
Your answer: • Um? Tell me what to code.
With more suffocated software engineering systems, the demand for mundane programmers will diminish. 42
K01-
Your answer: • I learned this great algorithm that will work.
Soon all known algorithms will be available in libraries.
43
K01-
Your answer: • I can develop a new algorithm for you. Great thinkers will always be needed.
44
K01-
The future belongs to the computer scientist who has – Content: An up to date grasp of fundamental problems and solutions – Method: Principles and techniques to solve the vast array of unfamiliar problems that arise in a rapidly changing field
45
K01-
Rudich www.discretemath.com
I like understanding things using a story. I will now tell one.
46
K01-
The Getting to School Problem
47
K01-
Problem Specification • Pre condition: location of home and school • Post condition: Traveled from home to school
48
K01-
Algorithm • What is an Algorithm?
49
K01-
Algorithm • The algorithm defines the computation route.
50
K01-
Algorithm • Is this reasonable?
51
K01-
Complexity • There are an infinite number of input instances •Algorithm must work for each.
52
K01-
Complexity • Difficult to predict where computation might be in the middle of the computation.
53
K01-
Location of Computation • The current “State” of computation is determined by values of all variables.
54
K01-
Location of Computation • Suppose the computation ends up here?
55
K01-
Don’t Panic • Where ever the computation might be, take best step towards school.
56
K01-
General Principle • Do not worry about the entire computation. • Take one step at a time!
57
K01-
Defining Algorithm • Wherever the computation might be, take best step towards school.
58
K01-
Take a step • What is required of this step?
59
K01-
A Measure of Progress
75 km to school 79 km to school 60
K01-
Defining Algorithm • Is this sufficient to define a working algorithm?
79 km
75 km
61
K01-
Working Algorithm •Computation steadily approaches goal
79 km
75 km
to school
to school
62
K01-
Defining Algorithm • Extra requirements
79 km
km
75 km
79 km 0 km 78.999 km 63
K01-
Define a Step • Wherever the computation might be, take best step towards school.
64
K01-
Computation Stuck • Location too confusing for algorithm • Algorithm too lazy to define step for every location.
65
K01-
Safe Locations • Algorithm specifies from which locations it knows how to step.
66
K01-
Loop Invariant • “The computation is presently in a safe location.” • Maybe true and maybe not.
67
K01-
Defining Algorithm • From every safe location, define one step towards school.
68
K01-
Take a step • What is required of this step?
69
K01-
Maintain Loop Invariant • If the computation is in a safe location, it does not step into an unsafe one.
70
K01-
Maintain Loop Invariant • If the computation is in a safe location, it does not step into an unsafe one.
• Can we be assured that the computation will always be in a safe location?
71
K01-
Maintain Loop Invariant • If the computation is in a safe location, it does not step into an unsafe one.
• Can we be assured that the computation will always be in a safe location?
No. What if it is not initially true? 72
K01-
Establishing Loop Invariant From the Pre-Conditions on the input instance we must establish the loop invariant.
73
K01-
Maintain Loop Invariant
• Can we be assured that the computation will always be in a safe location? • By what principle?
74
K01-
Maintain Loop Invariant • By Induction the computation will always be in a safe location.
S ( 0)
iS ( i ) iS ( i ) S ( i 1) 75
K01-
Ending The Algorithm
Define Exit Condition
Termination: With sufficient progress, the exit condition will be met.
Exit
0 km
Exit
When we exit, we know – exit condition is true Exit – loop invariant is true
from these we must establish the post conditions.
Exit
76
K01-
Let’s Recap
77
K01-
Is this sufficient?
Designing an Algorithm Define Problem
Define Loop Invariants
Define Measure of Progress 79 km to school
Define Step
Define Exit Condition
Maintain Loop Inv Exit
Exit Make Progress
Initial Conditions
Ending
Exit 79 km
75 km
km
0 km
Exit
Exit 78
K01-
Consider an Algorithm Exit
Exit 79 km 75 km
km
0 km
Exit
Exit
79
K01-
Loop Invariant Maintained
Exit
80
K01-
Computation can always proceed
81
K01-
Computation always makes progress
79 km
75 km
Exit 79 km
75 km
82
K01-
Computation Terminates
km
0 km Exit
0 km 79 km 75 km
0 km
Exit
83
K01-
Computation Terminates
Exit
Exit 84
K01-
Consider an Algorithm Exit
Exit 79 km 75 km
km
0 km
Exit
Exit
This is sufficient!
85
K01-
