} I.Pendahuluan
Algoritma & struktur Data
Algoritma & struktur Data
} IF-2031
} Hamonangan situmorang
} Roadmap Belajar Pemrograman(1)
} Diambil dari referensi [1]
} Roadmap Belajar Pemrograman(2)
} Elemen Program [Prosedural]
} Program = Struktur Data + Algoritma (instruksi)
} Struktur data : dasar (int, real, boolean), bentukan (record, array, set)
} Instruksi : assignment, read/write, if/case, loop (for, while, repeat)
} Pengelompokan instruksi menjadi fungsi/prosedur
} Operasi file eksternal.
} Definisi Dasar
} Struktur data: cara merepresentasikan data agar efisien dalam penyimpanan dan pengolahannya. [2]
} Struktur data seharusnya diterapkan pada algoritma yang didisain secara efisien
} Jadi mata kuliah Algoritma & Struktur Data adalah suatu disiplin ilmu yang mempelajari bagaimana merepresentasikan data secara efisien dan disain pengolahannya secara efisien
} Latar Belakang mata kuliah Algoritma & Struktur Data (1)
} Data semakin kompleks
◦ Bayangkan: indeks dari 8 milyar halaman ! (Google)
} Implementasi dan perawatan software sangat sulit.
} Kerangka konsep yang jernih memungkinkan pembuatan koding yang lebih efisien dan benar.
} Requirements (persyaratan) untuksofware yang baik adalah :
◦ Clean Design
◦ Easy maintenance
◦ Reliable (no core dumps)
} Latar Belakang mata kuliah Algoritma & Struktur Data (2)
◦ Easy to use
◦ Fast algorithms
Diambil dari referensi [2]
®Struktur data yang efisien
®Algoritma yang efisien
} Latar Belakang mata kuliah Algoritma & Struktur Data (3)
} Contoh kasus sederhana :
◦ Dimisalkan ada 3.000 file teks dengan rata-rata 20 baris tiap file teks-nya. Dimana tiap baris mengandung 10 kata. Jadi akan ada 600.000 kata.
◦ Tentukan jumlah kata “bandung”
◦ Jika dimisalkan dibutuhkan waktu 1 detik untuk mencek sebuah kata sama dengan “bandung”.
} Solusi 1: menggunakan sequential matching, membutuhkan waktu 1 detik x 600.000 kata = 166 jam
} Latar Belakang mata kuliah Algoritma & Struktur Data (4)
} Solusi 2 : Binary searching :
◦ Urutkan kata
◦ Cari di setengah kumpulan data setiap waktunya
Contoh : Cari 25 pada kumpulan data berikut
5 8 12 15 15 17 23 25 27
25 ? 15 15 17 23 25 27
25 ? 23 23 25 27
25 ? 25
Berapa langkah?
log 2 600000 = 19 detik vs 166 jam!
} Problem Solving : langkah
• Problem definition
• Algorithm design / Algorithm specification
• Algorithm analysis
• Implementation
• Testing
• Maintenance
} 1. Problem Definition
} Apa tugas-tugas yang harus dilaksanakan?, misalnya :
◦ Hitung nilai rata-rata mahasiswa yang ditentukan.
◦ Terjemahkan naskah pidato dari bahasa inggris menjadi bahasa indonesia
} Apa persyaratan performansinya (ketepatan waktu/ruang/ kecepatan ) ?
} 2. Algorithm Design / Specifications (1)
} Algoritma: Sekumpulan instruksi terbatas yang jika dijalankan akan melaksanakan tugas tertentu.[3]
} Deskripsi (cara penulisan):
◦ natural language
◦ pseudo-code
◦ diagram (seperti flowchart)
} Kriteria algoritma:
◦ Input: nol atau lebih
◦ Output: satu atau lebih
◦ Definisi/terjemahan/interprestasi: jelas, tepat untuk tiap instruksi
◦ Batasan: sebuah algoritma harus berhenti setelah sejumlah langkah, walaupun jumlah langkah boleh banyak tapi harus terbatas
} 2. Algorithm Design / Specifications (2)
} Efektifitas: tiap instruksi harus berupa perintah dasar bukan merupakan bentukan dari beberapa perintah
} 2. Algoritma : Deskripsi menggunakan Pseudo-Code (1)
} Pseudo-Code = deskripsi algoritma dengan cara
◦ Lebih terstruktur dibanding menggunakan natural language tetapi tapi tidak
◦ Seformal menggunakan programming language
} Contoh: Algoritma untuk menentukan nilai maksimum array ditulis dalam pseudocode
Algorithm arrayMax(A, n):
Input: An array A storing n integers.
Output: The maximum element in A.
currentMax ¬ A[0]
for i¬ 1 to n -1 do
if currentMax < A[i] then currentMax¬ A[i]
return currentMax
} 2. Algoritma : Deskripsi menggunakan Pseudo-Code (2)
} Ekspresi: gunakan simbol matematika
◦ gunakan ¬ untuk assignment ( pemberian nilai)
◦ gunakan = untuk kesamaan (pengujian nilai)
} Deklarasi metode:
◦ -Algorithm name(param1, param2)
} Konstruksi pemrograman (flow control dan indeksing array):
◦ decision structures: if ... then ... [else ..]
◦ while-loops : while ... do
◦ repeat-loops: repeat ... until ...
◦ for-loop: for ... do
◦ array indexing: A[i]
} Metode
◦ calls: object method(args)
◦ returns: return value
} Gunakanlah comments
} Instruksi harus se-dasar mungkin dan mungkin diselesaikan
} 3. Algorithm Analysis
} Space complexity
◦ Berapa banyak space yang dibutuhkan
} Time complexity
◦ Berapa lawa waktu running algoritma
} Terkadang kita harus menggunakan estimasi
} Space Complexity(1)
} Space complexity = jumlah memory yang dibutuhkan oleh sebuah algoritma untuk berjalan sampai selesai.
◦ Core dumps (“memory leaks”) terjadi karena jumlah memory yang dibutuhkan lebih besar daripada yang disediakan oleh sistem.
} Beberapa algoritma terkadang lebih efisien jika keseluruhan datanya dimuatkan pada memory.
◦ Hal ini harus memperhatikan batasan sistem, misalnya 2GB teks dalam berbaga kategori (mis: politik, travel, olahraga, bencna alam, dll) – apakah mungkin data sebanyak ini dimuatkan ke memory?
} Space Complexity(2)
• Fixed part: ukuran yang dibutuhkan untuk menyimpan data/variabel, yang independen dari ukuran problem, seperti:
- Nama kumpulan data : ukurannya sama saja untuk teks berkuran 2GB ataupun 1MB
• Variable part: ukuran yang dibutuhkan ole variabel yang bergantung pada problem, seperti:
- actual text : load 2GB text VS. load 1MB text
} Space Complexity(3)
} S(P) = c + S(instance characteristics)
◦ c = constant
} Contoh:
void float sum (float* a, int n)
{
float s = 0;
for(int i = 0; i<n; i++) {
s+ = a[i];
}
return s;
}
Space? one word for n, one for a [passed by reference!], one for i à constant space!
} Time Complexity(1)
} Umumnya lebih penting dari space complexity
◦ Ketersediaan memory untuk program komputer saat ini cederung semakin besar
◦ Waktu masih menjadi masalah besar sampai saat ini
} Prosesor 3-4GHz di pasaran
◦ Apakah masih…
◦ Peniliti memperkirakan untuk komputasi variasi transformasi 1 rantai DNA tunggal untuk 1 protein pada komputer 1 TerraHZ membtuhkan waktu 1 tahun agar selesai.
} Waktu running algoritma menjadi isu penting
} Time Complexity(2)
} Time Complexity(3)
} Pengukuran running time :
◦ Pendekatan eksperimen
◦ Pendekatan teoritis
} Pendekatan eksperimen :
◦ Tuliskan program yang mengimplementasikan algoritma.
◦ Jalankan program dengan sekumpulan data yang bervariasi.
◦ Tentukan actual running time menggunakan fungsi system untuk mengukur waktu (contoh: system (date) );
◦ Apa problemnya?
} Time Complexity(4)
} Pendekatan teoritis [3] :
◦ Based on primitive operations (low-level computations independent from the programming language)
◦ E.g.:
– Make an addition = 1 operation
– Calling a method or returning from a method = 1 operation
– Index in an array = 1 operation
– Comparison = 1 operation etc.
◦ Method: Inspect the pseudo-code and count the number of primitive operations executed by the algorithm
◦ Berapa operasi-kah algoritma mencari nilai maksimum array yang ada pada halaman 14 slide presentasi ini?
} 4,5,6: Implementation, Testing, Maintainance
} Implementation
◦ Pemutusan bahasa pemrograman yang akan digunakan
– C, C++, Lisp, Java, Perl, Prolog, assembly, dll.
◦ Penulisan koding harus terdokumentasi dengan baik dan jelas.
} Test, test, test
} Mengintegrasikan feedback dari user, perbaiki bug, penjaminan kompatibelitas pada berbagai platform à Maintenance
} Referensi
} [1] Inggriani Liem, “Roadmap Belajar Pemrograman dari Kabupaten ke Nasional,” dalam presentasi TOKI Biro ITB, 2004.
} [2] Rada Mihalcea, “Data Structures and Algorithm Analysis,” CSCE3110 lecture notes chap.1, 2006.
} [2] Rada Mihalcea, “Data Structures and Algorithm Analysis,” CSCE3110 lecture notes chap.2, 2006.
0 komentar:
Posting Komentar