STRUKTUR DATA KULIAH KE : 3
ALGORITMA
Ciri-ciri algoritma 1. 2. 3. 4. 5.
Input Output Definite Efective Terminate
: masukan : keluaran : jelas : efektif : berakhir
1.
Input
2.
Output
terdapat nol masukan atau lebih yang diberikan secara eksternal
sedikitnya terdapat satu keluaran yang harus dikeluarkan
3.
Definite
: jelas
4.
Efective
: efektif
5.
Terminate : berakhir
harus secara sempurna menyatakan apa yang dilakukan. contoh (tidak direkomendasikan) : a. hitung 5/0 b. tambahkan 6 atau 7 ke x
setiap instruksi harus dapat dilakukan secara manual menggunakan pensil dan kertas dalam sejumlah waktu yang berhingga harus berhenti setelah sejumlah terbatas operasi
masalah disebut dapat diselesaikan secara algoritma jika dapat ditulis program komputer yang dapat menghasilkan jawaban benar untuk sembarang masukan (yang dispesifikasikan) dalam waktu yang berhingga dan menggunakan ruang memori yang tersedia.
Model formal studi algoritma
Computability theory Computability complexity
Computability theory adalah teori yang mendeskripsikan dan mencirikan masalah yang dapat diselesaikan dan tidak dapat diselesaikan secara algoritma. contoh : perfect chess playing
Computability complexity Ada 2 macam : 1. Kompleksitas dari fungsi komputasi (complexity of computability) 2. Kompleksitas untuk persoalan dan algoritma tertentu
Kegiatan-kegiatan yang terkait dengan algoritma : Perancangan algoritma Validasi algoritma Analisis algoritma Penulisan algoritma menjadi program Pengujian algoritma
Dalam perancangan struktur data diperlukan penguasaan : Kemampuan mengajukan bentuk-bentuk representasi data Kemampuan membuat analisis terhadap algoritma yang beroperasi pada struktur tsb.
1. Perancangan algoritma Æ Æ
Merupakan “art” Strategi : 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
Strategi greedy Strategi divide-and-conquer Strategi pemrograman dinamis Strategi backtracking Strategi branch-and-bound Strategi pencarian dan penelusuran (search and traversal) Strategi pemrograman linier Strategi pemrograman integer Strategi algoritma genetik Strategi neural network
2. Validasi algoritma •
Tujuan : –
•
Menjamin algoritma bekerja secara benar, tidak bergantung bahasa pemrograman
Cara pembuktian kebenaran algoritma : 1.
Spesifikasi dinyatakan dengan kalkulus predikat 2. Barisan assertion yang dinyatakan dengan kalkulus predikat
3. Analisis Algoritma • Kegunaan : – Sebagai kegiatan intelektual yang menyenangkan – Memprediksi kelakuan algoritma – Sebagai sarana untuk pemilihan algoritma yang efisien – Untuk memperbaiki kinerja algoritma
•
–
Tugas-tugas yang dilakukan :
Penentuan jumlah operasi dan ongkos relatifnya (analisis komputasi) Penentuan jumlah ruang data yang diperlukan algoritma
–
•
Tipe analisis algoritma :
1.
Analisis untuk memeriksa kebenaran algoritma 2. Analisis efisiensi algoritma (kompleksitas komputasi dan ruang) 3. Analisis optimalitas algoritma
1. Analisis Kebenaran Algoritma Yang dilakukan : 1. Penelusuran algoritma 2. Penelusuran logik (assertion) 3. Implementasi algoritma 4. Pengujian dengan data 5. Atau menggunakan teknik matematika untuk pembuktian kebenaran Æ Sering dimasukkan sebagai proses validasi algoritma
2. Analisis Efisiensi Algoritma
Terdapat 2 fase : 1. 2.
A priori analysis A posteriori testing
A priori analysis
Untuk menemukan fungsi (beserta parameter-parameter yang relevan) yang membatasi waktu komputasi algoritma
Notasi matematika yang digunakan untuk menunjukkan hasil : { { {
O-notation (Big-O) Ω-notation Θ-notation
A posteriori testing
Dikumpulkan statistik nyata konsumsi waktu dan ruang suatu algoritma pada mesin dan bahasa pemrograman tertentu. Tujuan : {
menentukan jumlah waktu dan ruang penyimpanan yang diperlukan program.
Kegunaan : {
Memvalidasi a priori analysis.
3. Analisis optimalitas algoritma
Algoritma disebut optimal jika tidak terdapat algoritma lain di kelas persoalan itu yang mempunyai jumlah operasi yang lebih sedikit dibanding algoritma itu.
Harus ditemukan lower bound jumlah operasi minimum yang perlu dilakukan untuk penyelesaian masalah. Jika algoritma menyelesaikan masalah dengan jumlah operasi yang sama dengan lower bound maka algoritma disebut optimal.
Pengukuran Kebaikan Algoritma z
Kebaikan algoritma ditentukan oleh : – –
Seberapa baik algoritma menyelesaikan masalah Seberapa efisien algoritma menyelesaikan masalah
penilaian terhadap algoritma melibatkan analisis algoritma sehingga terdapat 2 tipe analisis algoritma : 1.
aspek kualitatif Æ Analisis untuk memeriksa kebenaran algoritma
2.
Aspek kuantitatif Æ Analisis terhadap efisiensi algoritma
Analisis Kualitatif z
Dilakukan dengan penelusuran algoritma, dilakukan penelusuran logik menggunakan teknik matematika untuk membuktikan kebenaran atau implementasi algoritma Æ mengujinya dengan data.
z
Contoh : Æ Algoritma pengurutan data (sorting) tidak dapat disebut sebagai algoritma pengurutan jika algoritma tidak dapat mengurutkan sembarang masukan barisan data.
Analisis Kuantitatif z z
z
Dilakukan dengan melakukan perhitungan kompleksitas komputasi (waktu) dan ruang. Aspek kuantitatif mencoba mengukur seberapa besar sumber daya yang diperlukan suatu algoritma 2 sumber daya yang diukur : – –
Kecepatan bekerja algoritma Ruang yang diperlukan untuk bekerja
Kompleksitas Komputasi dan Ruang Notasi untuk menyatakan kinerja
Æ big-oh (O) yaitu waktu komputasi algoritma berbanding terhadap satu fungsi tertentu Big-O biasanya hanya dinyatakan dengan
suku yang paling berarti dan menghilangkan konstanta pengalinya. Jadi O((n2-n)/2) hanya dinyatakan dengan O(n2).
Tugas : 1. Cari algoritma untuk mengurutkan data
menggunakan metode bubblesort dan insertion sort . 2. Buat programnya.
