desain dan analisa algoritma
Post on 06-Dec-2014
251 Views
Preview:
DESCRIPTION
TRANSCRIPT
Desain dan Analisa Algoritma
PendahuluanPeraturan kuliahAturan penilaian.Silabus/materi
Peraturan Kuliah
Sesuai dengan peraturan yang ada
Penilaian Project: 35%
◦ Presentasi specifikasi: 10% (Minggu terakhir sbl UTS)
◦ Topik 25 %. Ujian tengah semester: 30% Ujian akhir semester: 35%
Project dilakukan per kelompok◦ Setiap kelompok: ??
Materi Algorithmics: Theory & Practices,
Brassard and Bratley, 1996. Fundamental of computer algorithms,
Horowitz and Sahni, 1978.
Pengertian desain, analisa, algoritma.
Dasar AlgoritmaKompleksitas AlgoritmaAlgoritma Brute Force
MateriAlgoritma Divide and Conquer
◦Searching (Binary search)◦Sorting
- Bubble sort- Selection sort- Insertion sort- Shell sort- Merge sort- Quick sort
MateriAlgoritma GreedyDynamic ProgrammingBranch and BoundBacktracking
AlgoritmaKata algoritma dari nama Abu
Ja’fat Mohammed Ibn Musa al-Khowarizmi
Seorang ilmuan Persia yang menulis buku berjudul Kitab al jabr w’al-muqabala (rules of restoration and reduction) sekitar tahun 825
Definisi AlgoritmaDictionary.com: An algorithm is a
step-by-step problem-solving procedure, especially an established, recursive computational procedure for solving a problem in a finite number of steps.
A better one: An algorithm is a sequence of unambiguous instructions for solving a well-specified computational problem in a finite number of steps.
Definisi AlgoritmaMerriam-Webster’s Collegiet Dictionary
istilah algorithm diartikan sebagai prosedur langkah demi langkah untuk memecahkan masalah atau Penyelesaian suatu tugas khususnya dengan menggunakan bantuan komputer.
Algoritma adalah logika, metode dan tahapan (urutan) sistematis yang digunakan untuk memecahkan suatu permasalahan.
Algoritma
Input
Proses
Output
Algoritma
Source
Code
Executable
Source
Contohsehari-hariProses Algoritma Langkah dalam
algoritma
Membuat kue bolu Kue Bolu Siapkan wadahMasukkan 2 butir telurKocok tekurMasukkan tepungAdukMasukkan cetakanMasukkan ke Oven
Syarat AlgoritmaMenurut Donald E Knuth
algoritma harus memenuhi persyaratan :FinitenessDefiniteness, Input, Output, Effectiveness,
KriteriaKriteria Algoritma yang baik:Tepat, benar, sederhana, standar dan
efektif.Logis, terstruktur dan sistematis.Semua operasi terdefinisi.Semua proses harus berakhir setelah
sejumlah langkah dilakukan.Ditulis dengan bahasa yang standar
dengan format pemrograman agar mudah untuk diimplementasikan dan tidak menimbulkan arti ganda.
Ciri ciriSelalu memiliki terminasi/langkah
akhirSetiap langkah dinyatakan secara
jelas dan tegasSetiap langkah sederhana, sehingga
kinerjanyaSehubungan dengan waktu yang
effisien/bisa diterima akalMemberikan hasil (output), mungkin
dengan satu atau lebih.
Hub SD dan AlgoritmaStruktur data
◦cara pengaturan data agar bisa disimpan memory komputer secara efisien
Program◦algoritma yang diimplementasikan dalam
bahasa pemrograman tertentu
Algoritma + SD = Program
Tahapan hingga pemrogaman
Proses pemecahan masalah dengan algoritma tertentu hingga menjadi program dapat dibagi dalam sembilan tahap:Mendefinisikan masalahMasalah yang ingin dipecahkan harus jelas
lingkupnya.Membuat model Yang dimaksud model ini adalah model
(bentuk) matematis yang dapat digunakan untuk memecahkan masalah, misalnya apakah harus dilakukan pengurutan terhadap data.
Tahapan hingga pemrogamanMerancang algoritma
(flowchart/pseudocode)◦Apa maksudnya, bagaimana rincian
prosesnya, apa keluarannya.Menulis program
◦Ubah algoritma menjadi program (source code) dalam bahasa pemrograman tertentu.
Mengubah source code menjadi executable code melalui proses compiling.
Memeriksa hasil compiling, jika salah maka kembali ke tahap empat.
PenyajianPseudocode
◦ Menggunakan bahasa sehari-hari, tetapi harus jelas dan struktur.
◦ Kode yang mirip dengan kode pemrogaman sebenarnya (Pascal atau C)
◦ Menggambarkan algoritma untuk dikomunikasikan dengan pemrogram
◦ Contoh:MulaiBaca Data1Tulis Data1If Data1 < 100 and Data1>9 then
Tulis bilangan puluhan
ElseTulis bukan bilangan puluhan
Selesai
PenyajianFlowchart
◦Gambar atau bagan yg memperlihatkan urutan dan hubungan antar proses beserta pernyataannya.
Latihan:Mengurutkan 2 bilanganJumlah bilangan faktorial
Input P,l
Start
L=1/2*p*l
Tampilkan L
End
Struktur DasarStruktur berurutan
◦Pernyataannya secara berurutanStruktur pilihanStruktur perulangan (Iteration)
Analisis AlgoritmaBeban komputasi/berhubungan dengan kecepatan eksekusi program◦Banyaknya operasi yang dilakukan
Efisiensi penggunaan memory.◦Struktur data dan variabelsvyang digunakan
Study of algorithmsHow to devise algorithms: algorithm
designHow to express algorithms:
structured programmingHow to validate algorithms:
algorithm validationHow to analyze algorithms:
algorithm analysisHow to test algorithms: algorithm
debugging and profiling
Analisis AlgoritmaMana yang lebih baik: menggunakan algoritma yang waktu eksekusinya cepat dengan komputer standard atau menggunakan algoritma yang waktunya tidak cepat tetapi dengan komputer yang cepat?
Efisiensi Algoritma
Pertimbangan memilih algoritma:KebenaranTepat guna (efektif)Sesuai dengan permasalahanKemudahan/ kesederhanaanUntuk dipahamiUntuk diprogram(prosescoding)
Efisiensi Algoritma
Kecepatan AlgoritmaBerkaitan dengan kecepatan
eksekusi programHemat BiayaMengacu pada kebutuhan
memory
top related