Algoritma Pemrograman [BS204]

Algoritma Pemrograman [BS204] [1.1] Basic Programming Model

Robert Sedgewick, Kevin Wayne, Algorithms 4th Ed., Chapter 1, Addison-Wesley Professional, 2011

1

Tujuan Pertemuan Why Java Programming Language for Algorithms?  Mengerti Struktur Dasar Bahasa Pemrograman Java  Re-view Basic Programming Model 

http://algs4.cs.princeton.edu/code/ http://introcs.cs.princeton.edu/java/stdlib/ 2

Why Java Programming Language? Algoritma harus di implementasikan sebagai program yang ditulis dalam bahasa pemrograman.  Alasan algoritma harus di implementasi : 

◦ Program itu harus concise(deskripsinya ringkas), elegant(elegan), complete description of algoritms(algoritmanya harus lengkap); ◦ Menjalankan program untuk mempelajari sifat(properties) dari algoritma; ◦ Menempatkan algoritma sesegera mungkin(immediately) untuk digunakan dengan baik pada aplikasi. 

Keuntungan belajar algoritma dengan Java : ◦ Mudah untuk mendeskripsikan algoritma dalam bahasa Inggris karena Java base on english language. ◦ Java berbasis OOP yang dimana saat ini OOP itu harus!!! ◦ Kontruksi pemrograman Java yang baik banyak ditemukan dalam banyak bahasa modern dan diperlukan untuk menggambarkan algoritma yang memadai.

3

Anatomi Bahasa Pemrograman Java

4

Basic structure of a Java program 

Java (class) : library of static methods dan a data type definition.



7 komponen untuk membuat library of static methods dan a data type definition : ◦ tipe data primitif : makna istilah dan kombinasi dengan expression matematika.

◦ Statements : assign nilai ke variabel dan mengontrol execution flow. (declarations, assignments, conditionals, loops, calls, and returns) ◦ Arrays : bekerja dengan beberapa nilai(value/data) dari jenis yang sama. ◦ Static methods : encapsulate dan reuse kode serta modul independen. ◦ String : sequence of characters. ◦ Input / Output : set up komunikasi antara program dan dunia luar. ◦ Data abstraction (ADT-Abstract Data Type) : extends encapsulation dan reuse yang memungkinkan untuk mendefinisikan tipe data non-primitif, sehingga mendukung pemrograman berorientasi obyek.

5

Primitive data types and expressions Tipe data : seperangkat nilai dan operasi pada nilai.  Kategori tipe data primitif pada Java: 

◦ Integer : operasi aritmatika --> byte, short, int, long ◦ bilangan real : operasi aritmatika --> float, double ◦ Boolean : operasi logika --> boolean [true|false] ◦ Character : karakter alfanumerik & karakter legal --> char 

Ekspresi : untuk menentukan salah satu nilai dari tipe data. ◦ Ekspresi Arithmatika : *, /, %, +, ◦ Ekspresi Comparisons(Relasi/Logika) : ==, !=, >, >=, <, <= ◦ Ekspresi Assignment : = ◦ Ekspresi Fungsi : sum(), max(), min() ◦ Ekspresi Kondisional : if-else

6

Basic Building Blocks for Java Programs

7

Example Primitive Data Types in Java

8

Expressions 



Ekspresi khas adalah infiks(cara baca ekspresi oleh manusia): literal (atau ekspresi), diikuti oleh operator, diikuti oleh literal. Precedence conventions : compiler mengevaluasi operator.

9

Type conversion 

Widening Conversion : (Automatic Conversion) int contohData = 555; double contohConversion = contohData; //  555.0

byte 



short 

int 

long 

float 

double

Casting (Konversi Paksa) : kemungkinan ada data yang hilang double contohData = 555.55; int contohCasting = (int) contohData; //  555

10

Comparisons 

Operator ini akan membandingkan dua nilai dari jenis yang sama dan menghasilkan nilai boolean : ◦ Sama (==), ◦ Tidak sama (!=), ◦ Kurang dari (<), ◦ Kurang dari atau sama (<=),

◦ Lebih besar dari (>), ◦ Lebih besar dari atau sama (>=). 



Operator ini dikenal sebagai mixed-type operators karena nilainya boolean, bukan tipe dari nilai-nilai yang dibandingkan. Sebuah ekspresi dengan nilai boolean disebut boolean expression. Boolean expression : komponen penting dalam conditional dan loop statements. 11

Statements 

Menentukan perhitungan dengan menciptakan dan memanipulasi variabel, menetapkan nilai tipe data, dan mengendalikan flow pelaksanaan operasi-operasi yang dijalankan.



Statements sering diselenggarakan dalam block, urutan statement berada didalam kurung kurawal.



Suatu program merupakan urutan statement, dengan declarations, assignments, conditionals, loops, calls, dan returns. ◦ Declarations : membuat variabel dengan tipe data tertentu dan nama variabel(identifier).

◦ Assignments : mengasosiasikan nilai tipe data (didefinisikan oleh ekspresi) dengan variabel. ◦ Conditionals : memberikan perubahan sederhana dalam aliran execution—execute statement di salah satu dari dua blok atau tergantung pada kondisi tertentu. ◦ Loops : memberikan perubahan yang lebih besar dalam aliran execution—execute statement dalam blok selama kondisi tertentu adalah benar. ◦ Calls and returns : berhubungan dengan static methods, yang menyediakan cara lain untuk mengubah aliran pelaksanaan dan untuk mengatur kode.



Program dapat memiliki nested structure (block bersarang) : statement between statement dalam blok dengan conditional atau loop mungkin blok tersebut menjadi conditional atau loop. 12

Declarations Declaration statement : mengaitkan nama variabel dengan tipe data pada waktu kompilasi.  Java == typed language, karena compiler mengecek Java untuk konsistensi. 

Sintaks : ;  Contoh : 

◦ int minAge; ◦ int myAge, youAge; ◦ double yourPayment;

13

Assigments Memberikan atau mengubah nilai(value) dari sebuah variabel.  Nilai(value) dapat ditentukan saat program dibuat atau didapat dari input user atau dari perhitungan ekspresi matematika. 



Sintaks : =



Contoh : ◦ i = 0; ◦ myAge = (now() - myBirthDate) / 365;

◦ yourPayment = calculatePayment();

14

Conditionals – Struktur Kontrol Keputusan 

Java Construction for Conditionals : ◦ If statement : menentukan sebuah statement(atau blok kode) yang akan dieksekusi jika dan hanya jika ekspresi boolean(conditional expression) bernilai true. if () { // Statement sequence } ◦ If-else statement : digunakan apabila kita ingin mengeksekusi sebuah statement dengan kondisi true dan statement yang lain dengan kondisi false. if () { // Statement sequence }else { // Statement sequence } ◦ Nested-if statement (if bersarang). ◦ Switch-case statement. 15

Loops – Struktur Kontrol Pengulangan Statement dari Java dimana dapat mengeksekusi blok code berulang-ulang dalam kurun nilai tertentu.  3 jenis loops : ◦ for / Traversal 

◦ while-do

◦ do-while / Repeat Until

16

Break and Continue  

Beberapa situasi ekspresi aliran kontrol mungkin rumit/kompleks. Java mendukung 2 statement : ◦ Break : agar keluar dari loops. ◦ Continue : melakukan iterasi berikutnya dari loop.



Warning!!! Sebaiknya jangan menggunakan Break dan Continue dalam aliran kontrol!!! ◦ Caranya menghindarinya : sederhanakan aliran kontrol yang telah dibuat agar lebih elegan.

17

Shortcut notations 



Ada beberapa cara untuk menuliskan code perhitungan dan seharusnya mencari kode yang jelas, elegan, dan efisien. Cara penulisan code dengan cara pintas (ditemukan juga pada bahasa pemrograman lain) : ◦ Initializing declarations : gabungan declaration dan assigment  int i = 0; ◦ Implicit assignments : memodifikasi variabel nilai relatif terhadap nilai saat ini.  Increment/decrement operations  ++i; --i; i++; i--;  Other compound operations  i += 2; i -= 2; i *= 2; i /= 2; I %= 2; ◦ Single-statement blocks  for(int i = 0; i < 10; i++) i++; 18

Java Statement

19

Arrays 

Kemampuan dapat menggunakan satu variable untuk menyimpan kumpulan data dan melakukan manipulasi lebih effisien dengan tipe data yang sama.



Creating and initializing an array : 1. Array Declaration / deklarasi : tipe data + kurung siku [] + nama variable  char abjad []; char [] days; 2. Array Instantiation / instansiasi : menciptakan array + panjang dari array dengan contructor  abjad = new char [26]; days = new char [7]; 3. Array Accessing / beri dan ambil element array  Memberi element pada array index pertama  days[0] = monday;  Ambil element pada array index pertama  abjad[0]; 20

Long form, Short form, Initializing declaration Arrays

21

Using an array    

Setelah membuat sebuah array, ukurannya adalah tetap. Return panjang dari arrays : X.length Index terakhir dari array yang selalu [X.length-1]. Java tidak otomatis memeriksa batas dari arrays, jika telah membuat array berukuran N dan menggunakan indeks yang nilainya kurang dari 0 atau lebih besar dari N-1, program akan berakhir dengan runtime exception : ArrayOutOfBoundsException. [BUGS]

22

Arrays Aliasings vs Arrays Copy 

Arrays Aliasings ◦ Nama array mengacu pada seluruh array.

◦ Salah satu contoh variabel references.

int[] a = new int[N]; ... a[i] = 1234; ... int[] b = a; ... b[i] = 5678; // a[i] is now 5678 

Arrays Copy ◦ Jika saya ingin mengubah ukuran array dari 3 menjadi 7 tanpa menghapus isi dari array awal. Bagaimana caranya?

System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

    

src - the source array srcPos - starting position in the source array dest - the destination array destPos - starting position in the destination length - the number of array elements to be copied 23

Two[multi]-dimensional arrays 

Array multi-dimensi diimplementasikan sebagai array didalam array. Array multi-dimensi dideklarasikan dengan menambahkan jumlah tanda kurung setelah nama array. Contoh :

24

Typical Arrays-Processing Code

25

Static methods     

Disebut juga dengan function(fungsi) pada beberapa bahasa pemrograman. Data-type definition or library of static methods. Suatu kumpulan baris program yang sengaja dipisahkan dari main class untuk mengerjakan tugas tertentu. Urutan pernyataan yang dieksekusi, satu demi satu, ketika metode statis dipanggil Defining a static method : function_type static return_type function_name([parameters]) { //statement(s) }



Invoking a static method : class_name.function_name([parameters]); 26

Static methods

27

Typical Implementations of Static Methods

28

Properties of methods 

Yang perlu diperhatikan tentang properties(sifat) dari methods : ◦ Arguments are passed by value : Input nilai pada methods didapat dari variabel argument. (variabel argument vs variabel global) ◦ Method names can be overloaded : Nama methods dapat sama dalam 1 class asalkan memiliki parameter yang berbeda. (Methods overloading) ◦ A method has a single return value but may have multiple return statements : Methods hanya dapat mengembalikan single value, tetapi methods dapat memiliki banyak return statements. ◦ A method can have side effects (procedure) : methods yang tidak me-return value. Return type berupa "void". Produce side effects-memberikan efek samping (consume input, produce output, change entries in an array, or otherwise change the state of the system). 29

Recursion Sebuah methods yang dapat memanggil dirinya sendiri.  Tiga aturan dalam rekursif : 

◦ The recursion has a base case : menyertakan conditional statement sebagai statement pertama dalam program. ◦ Pemanggilan rekursif harus mengatasi subproblems yang kecil dalam arti tertentu, sehingga pemanggilan rekursif digunakan untuk kasus dasar. ◦ Pemanggilan rekursif tidak harus membahas subproblems yang overlap. 

Melanggar salah pedoman ini kemungkinan akan menyebabkan hasil yang salah atau program spektakuler tidak efisien. Mengikuti pedoman cenderung mengarah pada program yang clear dan correct dengan kinerja yang mudah dimengerti. 30

Recursion Example public class Faktorial { //fungsi rekursif public int factorR(int n) { int hasil; if (n == 1) return 1; hasil = factorR(n - 1) * n; return hasil; } //fungsi non-rekursif (loop) public int factorL(int n) { int hasil, c; hasil = 1; for (c = 1; c <= n; c++) hasil = hasil * c; return hasil; } }

31



Basic programming model Model dasar untuk pemrograman Java digunakan untuk mengembangkan sebuah program yang mengerjakan tugas komputasi tertentu dengan menciptakan static-methods library, salah satunya bernama main() method.



Modular programming ◦ Dengan static-methods library memungkinkan programming yang modular yang membangun modul(static-methods library) dan staticmethod dalam sebuah library dapat memanggil static-method yang didefinisikan di library lain. ◦ Static-method memungkin kita untuk :  Bekerja dengan modul yang ukurannya wajar, bahkan yang melibatkan kode yang banyak(kompleks).  Saling berbagi(sharing method) method dan reuse-code tanpa re-implementasi objek.  Mudah mengganti(subtitute) improvement implementation.  Develop abstract models yang sesuai untuk mengatasi masalah pemrograman.  Localize debugging



Unit testing ◦ Setiap modul harus dipastikan jalan dan sesuai tujuan/deskripsinya. ◦ Cara mudah : cek setiap class dengan membuat main() method dan testing setiap methods yang ada.

◦ Yang lebih elegant menggunakan JUnit.

32

External libraries 

Java sudah menyediakan sangat banyak standard library. (Bisa dipelajari lewat Java Documentation) ◦ Contoh : java.util.*; java.lang.*; etc…

External libraries : library yang dibuat dalam bahasa pemrograman Java untuk kepentingan suatu kelompok atau open source.  Pada buku Algorithms fouth edition, beberapa contoh menggunakan external library yang diberi nama StdLib. 

33

APIs - Application Programming Interfaces Sebuah komponen penting dari pemrograman modular adalah dokumentasi yang menjelaskan pengoperasian methods yang dimaksudkan untuk digunakan oleh orang lain.  Di Java dinamana Java libraries.  Example : 

34

Our standard libraries 

Class-Class yang terdapat di StdLib yang dapat diterapkan untuk aplikasi ilmiah, pengembangan, penelitian, dan penerapan algoritma.

35

Strings



Rangkaian karakter(char values). Tipe data String adalah tipe data Java tetapi bukan tipe primitif. (String adalah sebuah Class di Java) Java tidak dapat hidup tanpa class String. Automatic conversion to String. Concatenation :



Conversion :

   

36

Input dan output Tujuan utama input, output, dan drawing adalah mendukung model sederhana program Java untuk berinteraksi dengan dunia luar.  Standard input stream : mengambil nilai inputan dari command-line arguments atau dari aliran abstrak dari karakter.  Standard output stream : menulis ke aliran abstrak dari karakter lainnya. 

37

Commands and arguments

38

Standard output – StdOut library

39

Formatted output-printf

40

Standard input-StdIn library

41

Redirection and piping

42

Input and output from a file

43

Standard drawing (basic methods)

44

Standard drawing (control methods)

45

Standard drawing (control methods) Example

46

Binary search Pencarian suatu nilai dalam array.  Proses : 

◦ Menerima suatu nilai yang dicari ◦ Jika nilai ditemukan, menampilkan data ybs ◦ Jika nilai tidak ditemukan, menampilkan pesan

47

Binary search – Example (1)

48

Binary search – Example (2)

49

Binary search – Example (3)

50

Binary Search Code

51

52