OVERVIEW ANALISA ALGORITMA wijanarto
Outline • PENDAHULUAN • PROBLEM DAN SOLUSI • FRAMEWORK ANALISA ALGORITMA
– PEMODELAN SUATU KOMPUTER. – DEFINISI FORMAL DAN INFORMAL TERMINOLOGI DASAR – MODEL MATEMATIKA PADA KOMPUTER – PERBANDINGAN RAM DENGAN KOMPUTER ATAU KOMPILER NYATA
• STRATEGI UMUM ANALISA ALGORITMA • CONTOH PROBLEM
Pendahuluan • • • •
Tujuan mendisain agoritma yang “cepat” Perlu planning disain algoritma Teknik well define Lakukan dengan Scientifically – Pendekatan Analitis – Developing Mathematical Model – Mempelajari Property Algoritma
Problem Dan Solusi • Studi algoritma, sebenarnya di hadapkan pada munculnya suatu masalah, yang akan di selesaikan secara komputasional dengan caracara tertentu • Perlu standar dalam disain
Problem Dan Solusi • Standar untuk Problem dan Solusi
Problem Dan Solusi • Contoh : faktorisasi suatu bilangan
• Notasi Agoritmik
Problem Dan Solusi • Contoh : GCD
FRAMEWORK ANALISA ALGORITMA • Framework di pakai untuk – Perbandingan Waktu Tempuh – Efisiensi Memori
• Dilakukan dengan – Memodelkan secara matematika (fungsi) – Pengukuran order fungsi
PEMODELAN SUATU KOMPUTER • Algoritma di ukur tidak dengan komputer nyata • Perlu model matematika komputer :
– Berapa waktu tempuh yang di perlukan pada model tersebut untuk setiap operasi algoritma yang di jalankan. – Berapakah data yang seharusnya di inputkan pada algoritma tersebut. – Bagaimanakah model yang kita bangun tersebut berhubungan dengan komputersesungguhnya. Jika model yang kita bangun sangat berbeda, maka konklusi dari model tersebut mungkin tidak berguna untuk komputer sesungguhnya.
DEFINISI FORMAL DAN INFORMAL TERMINOLOGI DASAR • Problem adalah spesifikasi dari suatu nilai valid input dan apakah terdapat valid output yang dapat di terima oleh setiap valid input tersebut. • Instance input : suatu nilai x adalah input instance untuk problem P, jika x adalah input valid sesuai dengan spesifikasi. • Ukuran Input Instance ( size of an input instance ) secara formal dikatakan sebagai, sejumlah sedikit yang di perlukan untuk merepresentasikan suatu input instance. Sedangkan secara informal ( lebih berguna ) , dikatakan sebagai tiap parameter yang tumbuh secara cepat dengan ukuran formalnya.
DEFINISI FORMAL DAN INFORMAL TERMINOLOGI DASAR • Algoritma adalah suatu abstraksi prosedur komputer yang memerlukan beberapa atau banyak nilai input dan menghasilkan beberapa atau banyak nilai sebagai output. • Abstrak, karena algoritma dapat di ekspresikan dengan berbagai cara, misal gambar, psuedo code, rumus matematika, program, dan sebagainya. • Program yaitu merupakan ekspresi dari suatu algoritma dengan menggunakan suatu bahasa yang di mengerti komputer.
DEFINISI FORMAL DAN INFORMAL TERMINOLOGI DASAR • Contoh : gcd 2 bilangan input : 36,48 output : 12 • Dari contoh di atas maka bilangan 36,48 dan 12 merupakan input dan output instance dari problem gcd.
MODEL MATEMATIKA PADA KOMPUTER • RAM : Random Access Machine • Penyederhanaan dari model komputer yang terdiri dari 2 bagian utama : – Processor – Memory
0
– ISP (Instruction Set f Processor)
• Instruksi akan di kerjakan satu langkah
M-1
ISP • Operasi Aritmatika dan Logika – A=B+C – X=Y-Z – Semua operator aritmatika, logika, relasi dsb
• Jump dan Conditional Jump – goto dan if(kondisi) then goto
• Instruction Pointer dan Array – B=*C , *C = B, A[i] = B, B = X[i].
ISP • Contoh Instruction Pointer dan Array – A=B+C*D-F
• Berapa instruksi yang di jalankan prosesor ?, kita akan pecah ekspresi tersebut yang di dasarkan atas banyak operasi ( +,* dan - ) , jadi pada instruksi di atas terdapat 3 langkah yang akan di kerjakan oleh prosesor.
ISP (cont.) • A[i] =B[i]+C[i], maka fetch prosesor adalah – X =B[i], direct access ke memori 1 langkah – Y =C[i], direct access ke memori 1 langkah – Z =x+y, direct access ke memori 1 langkah – A[i] =Z, direct access ke memori 1 langkah
• Jadi terdapat 4 langkah yang di lakukan oleh processor
ISP (cont.) • Contoh lain for i=1 to n do C[i]=A[i]+B[i] • Ekuivalen dengan 1. i=1 2. if i>n then goto 9 3. X=A[i] 4. Y=B[i] 5. Z=X+Y 6. C[i]=Z 7. i=i+1 8. Goto 2 9. end
ISP (cont.) • Analisis pada RAM
ISP (cont.) • Total waktu tempuh untuk fragmen di atas adalah b*n+2n+ ( n+1) +1, b adalah body of loop dalam iterasi sebanyak n, sehingga menjadi 2+n( b+3) , dimana b terdiri dari 4 langkah, maka akan di dapatkan 2+7n atau 7n+2. • Dalam hal pemanggilan fungsi, untuk menghitung langkah pada pemanggilan fungsi dalam algoritma adalah Waktu = Jumlah Argumen Fungsi. • Dalam hal ini kita akan mengacu pada sintak gaya bahasa c, artinya tipa data array dan structure di katagorikan dalam pass by references dan variable primitive sebagai pass by value.
PERBANDINGAN RAM DENGAN KOMPUTER ATAU KOMPILER NYATA
STRATEGI UMUM ANALISA ALGORITMA • Model matematika yang paling sederhana yang dapat kita pakai sebagai model untuk menerapkan strategi analisa algoritma adalah dengan memakai suatu fungsi T (n) • Fungsi T(n) adalah waktu tempuh maximum algoritma, misal A, yang di jalankan untuk menyelesaikan masalah dalam RAM untuk setiap input instance berukuran n.
Contoh • Pembahasan contoh dalam diktat dengan media whiteboard
