Download - SDA 01.Pengantar v2 DN
IKI10400 Struktur Data & Algoritma:IKI10400 Struktur Data & Algoritma:Pengantar
Fakultas Ilmu Komputer Universitas IndonesiaSlide acknowledgments:
Suryana Setiawan, Ade Azurat, Denny, Ruli Manurung, Tisha Melia
Fasilkom UI IKI10400 Struktur Data & Algoritma 2012/13 Genap Kuliah 1 1
Tujuan Mata Kuliah
• Mempelajari dasar‐dasar ilmu komputer agar dapat melakukan p– perancangan dan pemilihan struktur data yang sesuai,– implementasi, danimplementasi, dan – melakukan analisis secara umum pada algoritma yang dibuat.
• Meningkatkan ketrampilan pemrograman– Skala lebih besar lebih efisien dan elegan– Skala lebih besar, lebih efisien dan elegan.– “Programming to an interface”Prinsip prinsip dasar RPL: abstraksi modularitas dst
Fasilkom UI IKI10400 Struktur Data & Algoritma 2011/12 Ganjil Kuliah 1 2
– Prinsip‐prinsip dasar RPL: abstraksi, modularitas, dst.
Arti kata (Webster) • da•ta (n.pl.)
1. facts or figures to be processed; evidence, records, i i f hi h l i b i f dstatistics, etc. from which conclusions can be inferred;
information• struc•ture (n )struc•ture (n.)
1. manner of building, constructing, or organizing2. something built or constructed, as a building or dam2. something built or constructed, as a building or dam3. the arrangement or interrelation of all the parts of a
whole; manner of organization or construction [the t t f th t th t t f i t ]structure of the atom, the structure of society]
4. something composed of interrelated parts forming an organism or an organization
Fasilkom UI IKI10400 Struktur Data & Algoritma 2011/12 Ganjil Kuliah 1 3
organism or an organization
Arti kata (Webster) • al•go•rithm (n.)
1. Math. a) any systematic method of solving a certain kind of problem b) the repetitive calculations used in finding the greatest common divisor of two numbers (called in full Euclidean algorithm)(called in full Euclidean algorithm)
2. Comput. a predetermined set of instructions for solving a specific problem in a limited number of g p psteps
• Contoh:– Problem: mencari sebuah elemen dalam array
terurut
Fasilkom UI IKI10400 Struktur Data & Algoritma 2011/12 Ganjil Kuliah 1 4
– Algoritma: binary search
Struktur Data
• Semua program berurusan dengan data– Sistem informasi: informasi, laporan, user, …, p , ,– Game: posisi & status pemain, musuh, skor, …– Search engine: URL isi hyperlink bobotSearch engine: URL, isi, hyperlink, bobot, …
• Mengapa data itu disimpan?S pa a bisa diakses/diproses di kem dian akt– Supaya bisa diakses/diproses di kemudian waktu
• Mengapa dalam penyimpanan data diperlukan b h k ?sebuah struktur?
– Supaya lebih mudah/efisien dalam k / d b
Fasilkom UI IKI10400 Struktur Data & Algoritma 2011/12 Ganjil Kuliah 1 5
pengaksesan/pemrosesan data tersebut
Struktur Data
• Struktur data memudahkan kita untuk component reuse.p– Sekali kita implementasi, dapat digunakan berkali‐kali dalam aplikasi yang berbeda
Fasilkom UI IKI10400 Struktur Data & Algoritma 2011/12 Ganjil Kuliah 1 6
Mengapa kuliah ini penting?Apakah kuliah DDP saja tidak cukup?•Perhatikan program untuk menghitung jumlah kemunculan angka 1 sampai 500 dalam sebuah file:angka 1 sampai 500 dalam sebuah file:
if (k == 1) c001++;if (k == 2) c002++;
P di 500 b i
...if (k == 500) c500++;
•Program di atas >500 baris.•Progam di atas benar walaupun tidak efisien, sangat besar (500 lines of code), dan sulit dipelihara.( ), p•Solusi sederhana: gunakanlah array integer yang terdiri dari 500 elemen:
A k h k d b ?int c[500];
Fasilkom UI IKI10400 Struktur Data & Algoritma 2011/12 Ganjil Kuliah 1 7
Apakah program kedua benar?int c[500];c[k]++;
Mengapa kuliah ini penting? (2) • Moral of the story:
– Pemilihan struktur data maupun algoritma yang tepat dapat membuat program lebih: efisien, mudah, elegan
C t h A lik i• Contoh Aplikasi:– Mencari jarak terpendek antara dua kota
• menggunakan struktur data Graph• menggunakan struktur data Graph
Fasilkom UI IKI10400 Struktur Data & Algoritma 2011/12 Ganjil Kuliah 1 8
Mengapa kuliah ini penting? (3) • Contoh Aplikasi:
– Sistem basis data (Oracle, SQL Server, dll) • menggunakan struktur data BTree, Hashtable
– Menghitung ekspresi: (5 + 2) * 7/• menggunakan struktur data Stack/Tree
Fasilkom UI IKI10400 Struktur Data & Algoritma 2011/12 Ganjil Kuliah 1 9
Mengapa Belajar Implementasi Struktur Data?
• Mengetahui kelebihan dan kekurangan dari masing‐masing struktur data.
• Cara yang terbaik untuk benar‐benar dapat memahami masing‐masing struktur data adalah membuatnya.
• Menyesuaikan struktur data yang ada untuk problem baru (augmented data structure)
• Dalam industri, bahasa yang digunakan tidaklah selalu Java. Mungkin saja di bahasa tersebut tidak terdapat lib t k t kt d tlibrary untuk struktur data.
• Melatih berpikir tentang efisiensi
Fasilkom UI IKI10400 Struktur Data & Algoritma 2011/12 Ganjil Kuliah 1 10
Topik‐Topik yang Dibahas
• Analisis algoritma• Abstract Data Type + Java Collections API• Pemrograman secara rekursif• Pengurutan (sorting) • Implementasi struktur data linear: List, Stack, Queue
• Struktur data hirarkis: Tree• Binary Search Tree, AVL Tree, Btree, Binary Heap, Red Black Tree (video)
• Hashtable
Fasilkom UI IKI10400 Struktur Data & Algoritma 2011/12 Ganjil Kuliah 1 11
• Graph
Jadwal Perkuliahan• Masa perkuliahan (termasuk ujian):10 Februari – 14 Juni 2014
• Ujian:– UTS : 2 ‐ 12 April 2014UAS : 4 14 Juni 2014– UAS : 4 ‐ 14 Juni 2014
• Jadwal Kuliah– Selasa JumatSelasa, Jumat– 08‐00‐09.40, 10.00‐11.40
Fasilkom UI IKI10400 Struktur Data & Algoritma 2011/12 Ganjil Kuliah 1 12
Jadwal Perkuliahan• Tutorial Lab (Worksheet, Quiz, atau Persiapan Ujian)
– Setiap minggu, dua jam. (jadwal diatur oleh asisten)– Senin atau Jumat: 16.00‐18.00– 3‐4 asisten per kelas (sebisa mungkin)– Soal LAB diumumkan 4 hari sebelum lab submission dibatasi– Soal LAB diumumkan 4 hari sebelum lab, submission dibatasi jam 17.00 saat lab– Jumat: publish Senin jam 8.00 pagi– Sabtu: publish Senin jam 8.00 pagi– Senin: publish Rabu jam 8.00 pagiSoal Mini Kuis diumumkan tepat jam 16 00 (sebelum di lab)– Soal Mini Kuis diumumkan tepat jam 16.00 (sebelum di lab), submission jam 18.00
Fasilkom UI IKI10400 Struktur Data & Algoritma 2011/12 Ganjil Kuliah 1 13
Jadwal Perkuliahan• Asistensi Teori
– Senin atau Jumat: 16.00‐18.00 (tidak wajib bagi mahasiswa)– Cukup 2 asisten per kelas– Membahas solusi dari lab dan mini kuis
Fasilkom UI IKI10400 Struktur Data & Algoritma 2011/12 Ganjil Kuliah 1 14
Jadwal Perkuliahan• Quiz Teori Online
– Setiap minggu, masa pengerjaan satu minggu, boleh dilakukan berulang kali SCELEberulang kali, SCELE
– Mulai minggu ke‐2– Dibuka Senin jam 00.00 sampai Minggu jam 23.55j p gg j
• Quiz Programming– 3 soal kecil: 2 mudah (35% + 35%), 1 sedang (30%)
• Tugas– Demo tugas perjanjian dengan asisten– Klinik tugas: waktu lab
Fasilkom UI IKI10400 Struktur Data & Algoritma 2011/12 Ganjil Kuliah 1 15
Tim Pengajar
• Dosen: – Arief Ramadhan ‐ [email protected] @– Bayu Distiawan – [email protected] – Denny – denny@cs ui ac idDenny [email protected]– Gilang Kusuma – gilang @cs.ui.ac.id– Hadaiq Rolis ‐hadaiq@cs ui ac id– Hadaiq Rolis ‐[email protected]
• Asisten Dosen:K di R @ il– Koordinator: Remmy ‐ [email protected]
– Tim asdos (akan diumumkan kemudian)
Fasilkom UI IKI10400 Struktur Data & Algoritma 2011/12 Ganjil Kuliah 1 16
Materi Ajar
• Homepage & resources:– https://scele.cs.ui.ac.id
– slide semester lalu sudah tersedia online– revisi slide akan diupload setelah kuliah (jika ada)G l Wiki di h //j– Google, Wikipedia, http://java.sun.com
– Video rekaman: http://content.cs.ui.ac.id/sda Mahasiswa di encourage untuk menonton video kuliah– Mahasiswa di‐encourage untuk menonton video kuliah sebelum kuliah
• Buku Acuan:– Mark Allen WeissData Structures & Problem Solving Using Java (4rd Edition) Addi W l 2010
Fasilkom UI IKI10400 Struktur Data & Algoritma 2011/12 Ganjil Kuliah 1 17
Addison Wesley, 2010.
Skema Penilaian
– 25% ‐ UTS– 25% ‐ UAS– Rata‐rata UTS dan UAS harus >= 40 untuk lulus– 20% ‐ Tugas Programming (2 tugas)g g g ( g )– 12% ‐ Quiz Programming + Mini UTS (waktu tutorial lab, 3x) )
– 3% ‐ Quiz online (14x, per minggu, SCELE)– 15% ‐ Lab + Mini Quiz (7x)% Q ( )
• Masing‐masing latihan 2% + bonus 1% apabila lengkap.• Bobot: Lab (40%), Mini Quiz (60%)
Fasilkom UI IKI10400 Struktur Data & Algoritma 2011/12 Ganjil Kuliah 1 18
Peraturan• Peserta diwajibkan mengikuti kuliah dan tutorial (lab, quiz, persiapan ujian).S l j l b t ih• Selama pengerjaan lab, peserta masih diperkenankan untuk bertanya dan berdiskusi dengan asisten atau rekan kuliah. g
• Quiz, tugas dan ujian, harus dikerjakan sendiri.• Peserta dengan kehadiran kurang dari 75% tidak diperkenankan mengikuti ujian akhir.
• Asistensi teori diadakan setiap minggu dan tidak wajibwajib.
Fasilkom UI IKI10400 Struktur Data & Algoritma 2011/12 Ganjil Kuliah 1 19
Kejujuran Akademis• Setiap bentuk kecurangan akan mendapatkan sanksi dengan tegas sesuai dengan peraturan universitas. Contoh kecurangan:g– Kecurangan saat ujian: menyontek jawaban teman, bekerjasama, menginformasikan soal atau jawaban dengan pihak lain.p
– Kecurangan dalam makalah: menyalin (quote) dari makalah lain tanpa menginformasikan sumber‐nya
– Kecurangan dalam tugas: menyalin & memodifikasi hasil kerjaKecurangan dalam tugas: menyalin & memodifikasi hasil kerja orang lain
– Mahasiswa diperbolehkan berdiskusi satu dengan yang lain, namun tugas harus dikerjakan sendiri (tidak diperkenankan g j ( pmenuliskan kolaborator)
– Kecurangan dalam pencatatan kehadiran (titip tanda tangan) • Sanksi akan dikenakan baik kepada si pelaku maupun yang
Fasilkom UI IKI10400 Struktur Data & Algoritma 2011/12 Ganjil Kuliah 1 20
• Sanksi akan dikenakan baik kepada si pelaku maupun yang membantu kecurangan tersebut.
Kejujuran Akademis
• Tim pengajar berhak memberikan nilai nol atau nilai E apabila ditemukan tindak l i i h d b k l iplagiarism terhadap semua bentuk evaluasi
(latihan, kuis, tugas, maupun ujian).
Fasilkom UI IKI10400 Struktur Data & Algoritma 2011/12 Ganjil Kuliah 1 21
Summary
• Struktur data + Algoritma = Program• Pemilihan struktur data dan algoritma yang tepatPemilihan struktur data dan algoritma yang tepat dapat membuat program lebih efisien, mudah, dan elegandan elegan
Fasilkom UI IKI10400 Struktur Data & Algoritma 2011/12 Ganjil Kuliah 1 22