Struktur Data & Algoritme (Data Structures & Algorithms)

Struktur Data & Algoritme (Data Structures & Algorithms ) Pengantar

Denny [email protected] Fakultas Ilmu Komputer Universitas Indonesia Semester Genap - 2000/2001

Version 1.0 - Internal Use Only

Tujuan Mata Kuliah n

Dalam kuliah ini anda akan mempelajari dasar-dasar ilmu komputer agar dapat n melakukan perancangan dan pemilihan struktur data yang sesuai, n implementasi, dan n melakukan analisis secara umum pada algoritma yang dibuat.

n

Tentunya juga anda akan melatih diri dalam ‘programming’

SDA/INTRO/DN/V1. 0/2

Fundamental Data Types: String, Math, Casting

1

Arti kata (Webster) n

da•ta n n.pl. • [now usually with sing. v.] facts or figures to be processed; evidence, records, statistics, etc. from which conclusions can be inferred; information

n

struc•ture n n. • 1

manner of building, constructing, or organizing

• 2

something built or constructed, as a building or dam

• 3 the arrangement or interrelation of all the parts of a whole; manner of organization or construction [the structure of the atom, the structure of society] • 4 something composed of interrelated parts forming an organism or an organization SDA/INTRO/DN/V1. 0/3

Struktur Data n

Mengapa data itu disimpan? n Supaya bisa diakses/diproses di kemudian waktu

n

Mengapa dalam penyimpanan data diperlukan sebuah struktur? n Supaya lebih mudah/efisien dalam pengaksesan/pemrosesan



2

Mengapa kuliah ini penting? n

Apakah KP1 saja tidak cukup? n Perhatikan program berikut ini: if (k == 1) c001++; if (k == 2) c002++; ... if (k == 500) c500++; n

n

n

Program di atas (+- 500 baris) digunakan untuk menghitung jumlah kemunculan angka 1 sampai 500 dalam sebuah file. Progam di atas benar, tetapi sangat besar (butuh waktu pengembangan yang lebih lama) dan sulit dipelihara. Solusi: gunakanlah array dari integer yang terdiri dari 500 elemen SDA/INTRO/DN/V1. 0/5

Mengapa kuliah ini penting? (2) n

n

Moral story: n Pemilihan struktur data yang tepat, membuat program lebih terstruktur dan efesien Aplikasi: n Sistem basis data (Oracle, SQL Server, dll) n Menghitung ekspresi: (5 + 2) * 7 n Mencari jarak terpendek antara dua kota



3

Mengapa perlu belajar membuatnya, khan sudah ada di Java API n

Supaya kita dapat mengetahui struktur data yang tepat, tentunya kita harus mengetahui kelebihan dan kekurangan dari masing-masing struktur data.

n

Cara yang terbaik untuk benar-benar dapat memahami masing-masing struktur data adalah membuatnya. Dalam real world, bahasa yang digunakan tidaklah selalu Java. Mungkin saja di bahasa tersebut tidak terdapat library untuk struktur data.

n


Topik-Topik yang Dibahas n

Pengantar analisa algoritme

n

Tipe Data Abstrak (Abstract Data Type - ADT)

n

Model data linear: Array, Linked List

n

Stack, Queue

n

Model data hirarkis: Tree

n n

Graph Hashing

n

Pelacakan (searching)

n

Pengurutan (sorting)



4

Jadual Perkuliahan n

Masa perkuliahan: 29 Jan – 25 Mei 2001

n

Mid Test: n 27 Maret 2001 (pada jam kuliah)

n

Batas akhir pembatalan MK (drop): 16 Apr 2001

n

Minggu Tenang: 28 Mei – 01 Jun 2001

n

Final Test: n 5 - 15 Juni 2001 (sesuai dengan jadual sekretariat)

n

Total kuliah: 32 x


Administrasi Kelas B n

Dosen: Denny - [email protected]

n n

Asisten Dosen: akan diumumkan kemudian Newsgroup: news.cs.ui.ac.id - forum.iki.struktur

n

Homepage & resources: http://pala.acad.cs.ui.ac.id/academic/sda/

n

Buku Acuan: n Mark Allen Weiss. Data Structures & Problem Solving Using Java. Addison Wesley, 1998. (call code: 005.133 Wei d).



5

Penilaian n

n

Komponen penilaian: n Tugas Pemrograman n Quiz/Tugas Mandiri n Mid Test n Final Test n Presensi

30% 5% 25% 40% bonus

Grading (subject to change) n A: 85 ke atas n B: 70 sampai dengan 84.9 n C: 55 sampai dengan 69.9 n D: 35 sampai dengan 54.9 n E: di bawah 35 SDA/INTRO/DN/V1. 0/11

Peraturan Kuliah n

Presensi n minimum 70% kehadiran dari kehadiran dosen supaya dapat mengikuti ujian akhir. n bonus 5 point, proporsi dari presensi diatas 90% • contoh: • presensi 92% mendapat bonus 1 point • presensi 100% mendapat bonus 5 point • berguna bagi anda yang berada di perbatasan nilai untuk naik ke grade yang lebih tinggi.



6

Kejujuran Akademis n

Kecurangan n Setiap bentuk kecurangan akan mendapatkan sanksi dengan tegas sesuai dengan peraturan universitas • Kecurangan saat ujian (menyontek jawaban teman atau bekerjasama) • Kecurangan dalam tugas (menyalin & memodifikasi hasil pekerjaan yang lain) • Kecurangan dalam pencatatan kehadiran (titip tanda tangan) n

Sanksi akan dikenakan baik pada si pelaku maupun yang memberi kesempatan.


Asistensi/Responsi n

Peserta akan dibagi ke dalam 3 kelompok asistensi yang masing-masing akan di asuh oleh seorang asisten (asisten akan diumumkan kemudian).

n

Pembagian kelompok akan diumumkan pada forum.iki.struktur

n

Anggota kelompok beserta asistennya masingmasing dapat menentukan jadwal asistensi / responsi / pemeriksaan tugas.



7

Problem Solving n

Apa itu problem/masalah? n Apakah mencari pasangan hidup adalah problem?

n

Apakah semua problem bisa diselesaikan dengan menggunakan komputer?

n

Secara umum, ada 2 jenis problem: n problem to find n problem to prove


Problem Solving (2) Problem to find

Problem to decide

Input

Input

Condition

Condition

Output

n

n

True

False

Termasuk problem yang manakah? n Apakah ‘stop’ dan ‘pots’ adalah palindrome? n Cetak semua kelompok kata palindrom dari sebuah file. Prinsip terpenting dalam memecahkan masalah: pahamilah masalahmu! SDA/INTRO/DN/V1. 0/16


8

Polya’s Principle What are the inputs? What is the desired output? Find connection between input & output Can you derive anything of use from the inputs? Perhaps introduce an auxilary problem. Can you see an analogy? Make a good guess.

Understand the problem

Devise a plan

yes

Implement the plan

Draw a figure! Introduce suitable notation Have you seen it before? Do you know related problem? Look at the unknown (the output) Restate the problem Perhaps first consider a related but simpler problem

Is this a computer problem?

no

Outline your plan Check each step Is each step correct?

Test your implementation! Could you derive a better plan?

Look back

Carry out the plan

Can you check the results? SDA/INTRO/DN/V1. 0/17

Algorithms n

A clearly specified set of instructions the computer will follow to solve a problem

n

Contoh: n Problem: mencari sebuah integer dalam sebuah array terurut n Algoritme: binary search



9

Tugas Mandiri & Latihan n

Cari dan pelajari struktur data yang telah tersedia di Java API

n

Kerjakan latihan: 1.20 dalam buku acuan. n Buat sebuah method yang menerima sebuah integer dan mencetak angka romawi. Jika parameter adalah 1998, outputnya MCMLXLVIII.


Summary n

struktur data + algoritme = program

n

Langkah-langkah dalam memecahkan masalah: pahami masalah, buat sebuah rencana/solusi, implementasi/jalankan solusi, kemudian dikaji kembali solusi tersebut.



10

Further Reading n

http://pala.acad.cs.ui.ac.id/academic/sda/ 1998/handout/handout07.html

n

http://pala.acad.cs.ui.ac.id/javaresources /jdk1.2.2/docs/api/java/util/packagesummary.html


What’s Next n

Review konsep-konsep penting dalam Java (Chapter 1 - 4)



11

Struktur Data & Algoritme (Data Structures & Algorithms)

Recommend Documents