Algoritma dan Struktur Data

PEMROGRAMAN

ALGORITMA & STRUKTUR DATA
PENDAHULUAN

APA ITU ALGORITMA ?
Algoritma : Sekumpulan instruksi terbatas yang jika dijalankan akan melaksanakan tugas tertentu
Deskripsi (Cara Penulisan) :
Natural Language
Pseudo-code
Diagram (Seperti Flowchart)

Kriteria Algiritma :
Input : nol atau lebih
Output : satu atau lebih
Definisi/terjemahan/interprestasi: jelas, tepat untuk tiap instruksi
Batasan : sebuah algoritma harus berhenti setelah sejumlah langah, walaupun jumlah langkah boleh
banyak tapi harus terbatas

APA ITU STRUKTUR DATA ?
Struktur Data : cara merepresentasikan data agar efisien dalam penyimpanan dan pengelolaan.
Struktur data seharusnya diterapkan pada algoritma yang didesain secara efisien
Jadi mata kuliah algoritma & Struktur Data adalah ilmu yang mempelajari bagaimana merepresentasikan data secara efisie dan desain pengolahannya secara efisien.

 ELEMEN PROGRAM
Program = Algoritma (instruksi) + Struktur Data
Struktur Data : Dasar (int, real, boolean), bentuk (record, array, set)
Instruksi : assigment, read/write, if/case, loop (for, while, repeat)
Pengelompokan instruksi menjadi fungsi/prosedur

LATAR BELAKANG KULIAH
ALGORITMA & STRUKTUR DATA

Data semakin kompleks
Bayangkan: indeks dari 8 milyar halaman (Google)
Implementasi dan perawatan software sangat sulit.
Kerangka konsep yang jernih memungkinkan pembuatan koding lebih efisien dan benar.
Requirments (persyaratan) untuk Software yang lebih baik adalah :
Clean Design
Easy maintenance
Reliable (no core dumps)
Easy to use
Fast algorithms

PROBELM SOLVING : LANGKAH

1. Probelm definition
2. Algorithm design / Algorithm Specification
3. Algorithm analysis
4. Implementation
5. Testing
6. Maintenance

1. PROBELM 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 / SPECIFICATION

Efektifitas : Tiap instruksi harus berupa perintah dasar bukan merukakan bentuk dari beberapa perintah

Pseudo-Code : Deskripsi algoritma dengan cara

- Lebih terstruktur dibanding menggunakan natural language tetapi 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

ALGORTIMA : DESKRIPSI MENGGUNAKAN PSEUDO-CODE

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 araay):

-decision structures:   if ... then ... [else ..]

-while-loops:                    while ... do

-repeat-loops:                  repeat ... until ...

-for-loops:                       for ... do

-array indexing:          A[i]

Metode

-Calls:              object method(args)

-returns:           return value

Gunakanlah comments

Instruksi harus se-dasar mungkin dan mungkin diselesaikan

ALGORITHM ALAYSIS

Space complexity

-Berapa banyak space yang dibutuhkan

Time complexity

-Berapa lama waktu running algoritma

Terkadang kita harus menggunakan estimasi

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 2 GB teks dalam berbagai kategori (mis:politik, travel, olahraga, bencana alam, dll) - apakah mungkin data sebanyak ini dimuatkan oleh memory?

SPACE COMPLEXITY

1. Fixed part: ukuran yang dibutuhkan untuk menyimpan data/variabel, yang independen dari ukuran problem, seperti:

- Nama kumpulan data : ukurannya sama saja untuk teks berukuran 2GB ataupun 1MB

2. Variable part: ukuran yang dibutuhkan oleh variabel yang bergantung pada problem, seperti :

- actual text : load 2GB text VS. load 1MB text

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

Umumnya lebih penting dari space complexity

- Ketersediaan memory untuk program komputer saat ini cenderung semakin besar

- Waktu masih menjadi masalah besar sampai saat ini

Prosesor 3-4GHz di pasaran

- Apakah masih...

- Peneliti memperkirakan untuk komputasi variasi transformasi 1 rantai DNA tunggal untuk 1 protein pada komputer 1 TerraHZ membutuhkan waktu 1 tahun agar selesai.

Waktu running algoritma menjadi isu penting

Jika program mengandung if-then statement yang dapat dieksekusi atau tidak > variable running time umumnya running time algoritma diukur dari worst case

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?

Pendekatan teoritis :

- 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?

IMPLEMENTASI, TESTING, MAINTENANCE

Implementation

- Pemutusan bahasa pemrograman yang akan digunakan

  -> C, C++, Lisp, Java, Perl, Prolog, assembly, dll.

- Penulis koding harus terdokumentasi dengan baik dan jelas

Test, test, test

Mengintegrasikan feedback dari user, perbaiki bug, penjamin kompatibelitas pada berbagai platform > Maintenance