ALGORITMA DAN KOMPLEKSITAS (Branch and Bound)

Algoritma Branch and Bound (B&B)

 Algoritma Branch and Bound (B&B) juga merupakan metode pencarian di dalam ruang solusi secara sistematis.
 Algoritma runut-balik skema DFS  Algoritma B&B skema BFS
 Untuk mempercepat pencarian ke simpul solusi, maka setiap simpul diberi sebuah nilai ongkos (cost).
 Simpul berikutnya yang akan diekspansi tidak lagi berdasarkan urutan pembangkitannya (sebagaimana pada BFS murni), tetapi simpul yang memiliki ongkos yang paling kecil (least cost search) –pada kasus minimasi.
 Nilai ongkos pada setiap simpul i menyatakan taksiran ongkos termurah lintasan dari simpul i ke simpul solusi (goal node): 
)( ˆ i c = nilai taksiran lintasan termurah dari  simpul status i ke status tujuan 
 Dengan kata lain, ) (ˆ ic
 menyatakan batas bawah (lower bound) dari ongkos pencarian solusi dari status i. 

KASUS BFS DISELESAIKAN DENGAN SKEMA MURNI

 Solusi pertama dicapai pada simpul 30, yaitu X= (2, 4, 1, 3). Dengan skema BFS murni / FIFO, kita harus memperluas dulu simpul 12, simpul 15, dan simpul 16 sebelum memperluas simpul 22 yang melahirkan simpul solusi, yaitu simpul 30.
 Pada algoritma B&B, pencarian ke simpul solusi dapat dipercepat dengan memilih simpul hidup berdasarkan nilai ongkos (cost).
 Setiap simpul hidup diasosiasikan dengan sebuah ongkos yang menyatakan nilai batas (bound).
 Simpul hidup yang menjadi simpul-E ialah simpul yang mempunyai nilai batas terkecil (strategi  pencarian berdasarkan biaya terkecil(least cost search)).
 Untuk setiap simpul X, nilai batas ini dapat berupa : 1. jumlah simpul dalam subpohon X yang perlu  dibangkitkan sebelum simpul solusi ditemukan, atau 2. panjang lintasan dari simpulX ke simpul solusi terdekat (dalam subpohon X ybs)
 Misal digunakan ukuran (b):

 Pemberian nilai batas seperti pada persoalan N-Ratu di atas adalah nilai batas yang ideal, karena letak simpul solusi diketahui.
 Pada umumnya, untuk kebanyakan persoalan, letak simpul solusi tidak diketahui, karena itu, dalam prakteknya, nilai batas untuk setiap simpul umumnya berupa taksiran atau perkiraan.
 Fungsi heuristik untuk menghitung taksiran cost: 

 Simpul berikutnya yang dipilih untuk diekspansi adalah simpul yang memiliki c ˆ minimum

ALGORITMA BRANCH AND BOUND
1. Masukkan simpul akar ke dalam antrian Q. Jika simpul akar adalah simpul solusi (goal node),  maka solusi telah ditemukan.  Stop.
2. Jika Q kosong, tidak ada solusi. Stop.
3. Jika Q tidak kosong, pilih dari antrian Q simpul i yang mempunyai ) (ˆ ic paling kecil. Jika terdapat beberapa simpul i  yang memenuhi, pilih satu secara sembarang.
4. Jika simpul i adalah simpul solusi, berarti solusi sudah ditemukan, stop. Jika simpul i bukan simpul solusi, maka bangkitkan semua  anak-anaknya.  Jika i tidak mempunyai anak, kembali ke langkah 2. 5. Untuk setiap anak j dari simpul i, hitung ) (ˆ jc , dan masukkan semua anak-anak tersebut ke dalam Q.
6. Kembali ke langkah 2.

PERSOALAN PERDAGANGAN KELILING (TRAVELLING SALESPERSON PROBLEM - TSP)
Misalkan 
(i) G=(V,E) adalah graf lengkap TSP
(ii) V=n = jumlah simpul dalam graf G.     
 Simpul- simpul diberi nomor 1, 2, …, n.
(iii) cij = bobot sisi (i, j) (iv) perjalanan (tur) berawal dan berakhir di simpul 1.   (v) S adalah ruang solusi, yang dalam hal ini 
S = { (1,  , 1)   adalah permutasi (2, 3, ..., n) } 

Solusi TSP dinyatakan sebagai  X = (1, x1, x2, ..., xn – 1, 1) yang dalam hal ini         
 xo= xn = 1 (simpul asal = simpul akhir= 1).

Contoh instansiasi persoalan TSP:

 Ongkos atau nilai batas untuk setiap simpul dihitung dengan menggunakan matriks ongkos-tereduksi (reduced cost matrix) dari graf G.
 Sebuah matriks dikatakan tereduksi jika setiap kolom dan barisnya mengandung paling sedikit satu buah nol dan semua elemenlainnyanon-negatif.

Contoh :
Tinjau graf lengkap berarah TSP dengan n = 5

Lakukan reduksi baris:

Kemudian, lakukan reduksi kolom (dari hasil reduksi baris di atas):

Total jumlah semua pengurang = (10 + 2 + 2 + 3 + 4) + (1 + 3) = 25.

Nilai 25 ini adalah nilai batas untuk simpul akar, 

Selanjutnya, misalkan A adalah matriks tereduksi untuk simpul R. 
Misalkan S adalah anak dari simpul R sedemikian sehingga sisi (R, S) pada pohon ruang status berkoresponden dengan sisi (i, j) pada perjalanan. 
Jika S bukan simpul daun, maka matriks bobot tereduksi untuk simpul S dapat dihitung sebagai berikut:

(a) ubah semua nilai pada baris i dan kolom j menjadi . Ini untuk mencegah agar tidak ada lintasan yang keluar dari simpul i atau masuk pada simpul j; 
(b) ubah A(j, 1) menjadi . Ini untuk mencegah penggunaan sisi (j, 1); 
(c) reduksi kembali semua baris dan kolom pada matriks A kecuali untuk elemen . 
Jika r adalah total semua pengurang, maka nilai batas untuk simpul S adalah:   

Hasil reduksi ini menghasilkan matriks B.

Perhitungan selanjutnya:

Pohon ruang status yang terbentuk sampai saat ini adalah:

Pohon ruang status yang terbentuk sampai saat ini adalah:

Pohon ruang status yang terbentuk sampai saat ini adalah:

Pohon ruang status yang terbentuk sampai saat ini adalah:

Karena tidak ada lagi simpul hidup di dalam pohon ruang status, maka X = (1, 4, 2, 5, 3, 1) menjadi solusi persoalan TSP di atas dengan bobot 28.







Terima Kasih telah membacanya semoga bermanfaat

SISTEM INFORMASI MANAJEMEN( Lanjutan materi sebelumnya)

JARINGAN KOMPUTER

 Komunikasi secara langsung (point to point) seringkali tidak praktis

  -  Jarak antar peralatan terlalu jauh

  -  Sejumlah peralatan akan memerlukan jumlah koneksi yang besar

 Solusi yang nyata adalah : Jaringan Komunikasi (Jaringan Komputer)

DIFINISI

 Jaringan Komputer

Sekelompok komputer yang saling dihubungkan dengan menggunakan suatu protokol komunikasi sehingga antara satu komputer dengan komputeryang lain dapat berbagi data atau berbagi sumber daya (sharing resources).

TIPE JARINGAN

 Jarak Geografis

   - Local Area Networks (LAN)

   - Metropolitan Area Networks (MAN)

   - Wide Area Networks (WAN)

 Tipe Informasi

  - Jaringan data vs. jaringan telekomunikasi

 Tipe Aplikasi

  - Jaringan yang digunakan secara khusus: reservasi pesawat

terbang, jaringan perbankan, aplikasi SIGO dan SIMAS

  - Jaringan yang digunakan secara umum : Internet

Komunikasi Data Nirkabel

Topologi Jaringan

Wide Area Networks

 Area yang dilingkupi luas

 Menggunakan saluran komunikasi publik

 Kecepatan transfer datanya relatif rendah

 Beberapa teknologi alternatif

   - Circuit switching

   - Packet switching

   - Frame relay

   - Asynchronous Transfer Mode (ATM)

Circuit Switching adalah Jenis Koneksi temporer yang dibentuk antara dua titik(two points). Ketika proses berlangsung, jalur temporer tadi akan tetap dipertahankan hingga koneksi selesai. Data dipecah-pecah menjadi paket-paket kecil dan kemudian dikirim melalui jalur tetap

Packet switching adalah metode komunikasi jaringan digital yang ditransmisikan kelompok semua data – terlepas dari konten, tipe struktur, atau – menjadi blok-blok berukuran yang sesuai, yang disebut paket . Fitur- fitur switching paketpengiriman variabel-bit-rate data stream (urutanpaket) melalui jaringan bersama.

Frame Relay adalah konsep di mana informasi akan dikirim menggunakan data frame dalam format digital. penggunaan layanan relay ini data dapat dikirim dengan cara yang cepat dan efisien melalui internet. ... Frame-relay juga umum digunakan dalam jaringan komputer LAN dan WAN.

Asynchronous Transfer Mode (ATM) adalah teknologi switching dan multiplexing, dimaksudkan untuk memindahkan berbagai jenis trafik (data, suara, video, audio) dengan cepat dan efisien. Circuit switching umumnya mensyaratkan bahwa paket di set ke posisi dalam frame berulang, misalnya sinkron dalam waktu, langkah, sesuai dengan aplikasi dan atau jam jaringan. Transmisi Asynchronous memungkinkan sel-sel yang akan diposisikan di

mana saja dalam data stream.

ATM saat ini memiliki kecepatan 155Mbps (OC- 3port), 622Mbps (OC-12 port), 1,2 Gbps dan 2,5

Gbps. Asynchronous Transfer Mode (ATM) merupakan protokol jaringan yang berbasis sel, yaitu paket-paket kecil yang berukuran tetap (48 byte data + 5 byte header) pada sirkuit virtual. Protokol lain yang berbasis paket, seperti IP dan Ethernet, menggunakan satuan data paket yang berukuran

Local Area Networks

 Area yang dilingkupi terbatas

   - Dalam gedung atau kampus kecil

 Dimiliki oleh sebuah organisasi

 Kecepatan transfer datanya besar (>= 10 MBps)

 Biasanya menggunakan sistem broadcast

 Beberapa teknologi alternatip :

   -  switched systems dan ATM

   - Wifi

Arsitektur Komunikasi Komputer

 Keterhubungan antar elemen-elemen yang dibutuhkan untuk

dapat melakukan komunikasi data dalam sistem komputer

Contohnya :

 Komunikasi antara software aplikasi, komputer, kabel.

 arsitektur sistem komputer yang berasas vendor (produsen)

adalah

      SNA (System Network Architecture) oleh IBM

      DNA (Dec NetworkvArchitecture) oleh DEC.

 arsitektur yang tidak berdasarkan vendor seperti

      OSI (Open System Architecture)

      TCP/IP (Transport Communication Protocol / Internet Protocol).

Arsitektur Jaringan Komputer

 Jaringan hybrid

 Jaringan peer to peer

 Jaringan clien - server

Protocol

 Aturan / standar yang mengatur dan mengijinkan terjadinya komunikasi danantara 2 atau lebih komputer. perpindahan data

 Dengan adanya protocol, komputer-komputer anggota jaringan dan komputer berbeda platform dapat saling berkomunikasi

Elemen Kunci Protocol

 Sintak, meliputi segala sesuatu yang berkaitan dengan format data dan level – level sinyal

Contoh : sebuah protokol sederhana akan memiliki urutan pada delapan bit pertama adalah alamat pengirim, delapan bit kedua adalah alamat penerima informasinya sendiri dan bit stream sisanya merupakan

 Semantics, meliputi informasi kontrol untuk koordinasi dan pengendalian kesalahan. mengacu pada maksud setiap section bit. Dengan kata lain adalah bagaimana bit-bit tersebut terpola untuk dapat diterjemahkan.

 Timing, meliputi kesesuaian urutan dan kecepatan, mengacu pada 2 karakteristik yakni kapan data harus dikirim dan seberapa cepat data tersebut dikirim.

PERANCANGAN BASIS DATA

MANIPULASI DATA

DASAR TEORI 

    DML (Data Manipulation Language) adalah bahasa yang memungkinkan pengguna mengakses atau memanipulasi data seperti yang diatur oleh model data, manipulasi data adalah (Octaviani, 2010): 

1. Pengambilan informasi yang disimpan dalam basis data. 

2. Penempatan informasi baru dalam basis data.  

3. Penghapusan informasi dari basis data.  

4. Modifikasi informasi yang disimpan dalam basis data.  

      DML (Data Manipulation Language) merupakan bahasa yang bertujuan memudahkan pemakai untuk mengakses data sebagaimana direpresentasikan oleh model data, ada 2 jenis DML, yaitu (Octaviani, 2010): 

1. Prosedural, yang mensyaratkan agar pemakai menentukan data apa yang ditentukan serta bagaimana cara mendapatkannya. 

2. Nonprosedural, yang membuat pemakai dapat menentukan data apa yang diinginkan tanpa menyebutkan bagaimana cara mendapatkannya. 

     Yang termasuk dalam perintah-perintah dalam DML (Data Manipulation Language) adalah sebagai berikut: 

1. INSERT, menyisipkan atau menambahakan data baru ke dalam tabel. 

2. SELECT, mengambil atau menampilkan data dari tabel, statement ini adalah statement dasar yang digunakan untuk mengambil informasi dari database. Dengan statement ini user dimungkinkan untuk mengambil data dari satu tabel atau lebih bahkan dari database lainnya, hasil dari statement ini dikenal sebagai result set yang berbentuk tabel juga. 

3. UPDATE, memperbaharui data yang lama ke dalam data yang baru. 

4. DELETE, menghapus data dalam tabel. Untuk lebih memahami perintah-perintah DML (Data Manipulation Language). Berikut ini adalah penjelasan dalam praktikum untuk masing-masing dari pritah-perintah di atas.  

KEGIATAN PRAKTIKUM 

Pernyataan INSERT  

      Setelah tabel dibuat beserta constraint-constraintnya bila ada, maka tabel siap digunakan untuk menampung data. Perintah wajib pada T-SQL untuk memasukkan data ke dalam tabel adalah perintah INSERT. Kita akan memasukkan data pada tabel Barang dan tabel Pembelian. Bentuk perintah INSERT adalah sebagai berikut : 

INSERT INTO table_name 

(column1,column2,column3,...) 

VALUES (value1,value2,value3,...); 

Memasukkan data pada tabel Barang 

INSERT INTO Barang 

(ID_Barang,Nama_Barang,Tanggal_Terima)  

VALUES ('BRG01','Sony Ericsson','2011-04-03');

Dan data seterusnya silahkan masukkan sendiri dengan petunjuk queri diatas berdasarkan data pada gambar dibawah ini, lihatlah hasilnya dibawah ini!   

      Kolom yang tidak disebutkan pada pernyataan INSERT secara otomatis akan diisi dengan NULL. Pada Stok_Barang nilainya akan terisi 0 karena pada saat kita membuat tabel Barang kita memberikan nilai Stok_Barang itu default, sehingga pada saat memasukkan data kita tidak memberikan nilai pada Stok_Barang tersebut.   

Memasukkan data pada tabel Pembelian.   

INSERT INTO Pembelian 

(ID_Pembeli,ID_Barang,Tanggal_Beli,Nama_Pembeli, Jumlah_Pembelian) 

VALUES ('P01','BRG03','2011-04-07','Jaka Widana',2);

Dan data seterusnya silahkan masukkan sendiri dengan petunjuk queri diatas berdasarkan data pada gambar dibawah ini, lihatlah hasilnya dibawah ini!

       Seperti telah dijelaskan bahwa perintah INSERT selain dapat menambahkan satu buah record, juga bisa langsung menambahkan beberapa record sekaligus dalam tabel, untuk mempraktekkannya buatlah satu tabel lagi pada database “Toko” dengan nama tabel “Pelanggan” yang memiliki field ID_Pelanggan dan Nama_Pelanggan. Untuk membuat tabel Pelanggan gunakan queri dibawah ini:   

CREATE TABLE Pelanggan (ID_Pelanggan varchar (10), Nama_Pelanggan varchar(80))

     Setelah tabel Pelanggan dibuat, kemudian ketikkan queri dibawah ini untuk mengisi tabel “Pelanggan” dengan jumlah pembelian=1. 

INSERT INTO Pelanggan(ID_Pelanggan, Nama_Pelanggan) 

SELECT ID_Pembeli,Nama_Pembeli FROM Pembelian WHERE Jumlah_Pembelian='1’ 

Untuk memeriksa kebenarannya, gunakan queri dibawah ini dan lihat hasilnya ! 

SELECT * FROM Pelanggan

Pernyataan UPDATE 

Pernyataan UPDATE digunakan untuk memodifikasi data dalam tabel database. 

UPDATE namatabel  

SET namakolom=nilai_baru  

WHERE namakolom= nilai 

Pada queri diatas : 

SET        : Untuk menentukan kolom yang akan diubah dan nilai penggantinya. 

WHERE  : Menentukan kondisi dari baris-baris yang akan diganti. Berikut ini queri untuk mengupdate field nama barang pada tabel Barang dengan nama 

“SONY” yang awalnya bernama “Sony ericsson”. 

UPDATE Barang 

SET Nama_Barang='SONY' 

WHERE ID_Barang='BRG01'

Pernyataan DELETE 

      Pernyataan DELETE digunakan untuk menghapus baris pada tabel, bentuk querinya sebgai berikut.

DELETE FROM namatabel  

WHERE namakolom= values 

    Pada contoh ini kita akan menghapus field dengan ID_Barang=’BRG01’ pada tabel Pembelian. Untuk mempraktekkannya tulislah queri dibawah ini!   

DELETE FROM Pembelian 

WHERE ID_Barang='BRG03' 

  

   Dalam perintah DELETE jika kita ingin menghapus semua data pada tabel tanpa menghapus tabel, maka klausa WHERE tidak perlu disebutkan, berikut querinya.   

DELETE FROM namatabel  

atau 

DELETE * FROM namatabel 

PEMOGRAMAN 1

ARRAY

      Array   adalah  sekumpulan  variabel  yang  memiliki  tipe  data  yang  sama  dan

dinyatakan dengan nama  yang  sama. Array merupakan  konsep  yang  penting  dalam

pemrograman, karena array memungkinkan untuk menyimpan data maupun referensi

objek dalam jumlah banyak dan terindeks. Array menggunakan indeks integer untuk

menentukan  urutan  elemen-elemennya, dimana elemen pertamanya  dimulai  dari indeks

0, elemen kedua memiliki indeks 1, danseterusnya.

      Setelah pendeklarasian, kita harus membuat array dan menentukan berapa panjangnya

dengan sebuah  konstruktor. Proses ini di Java disebut sebagai  instantiation ( Kata dalam

Java yang berarti membuat ).

Deklarasi Array

int[ ] bilangan; atau

int bilangan[ ];

//deklarasi

int ages[];  

 

Gambar 2: Inisialisasi Arrays

//instantiate obyek

ages = new int[100];

String[] nama = new String[5];

Memasukan data ke Array

Mengambil data dari Array

Array Multi Dimensi

      Pada  Java  juga  menyediakan  fasilitas  untuk  membuat  array  dua dimensi  yang  dapat 

membantu  dalam  pemrograman  apabila  arrray  satu dimensi  tidak  mencukupi  dalam 

menghasilkan  suatu  solusi.  Array  dua dimensi sebenarnya adalah array yang berisi array.

Contoh 1 :

public class SingleArray {

    public static void main(String[] args) {

    int [] x;                  // Cara 1

    x = new int[3];

    x[0] = 20 ;

    x[1] = 10 ;

    x[2] = 30;

    System.out.println("Nilai x[0] : " + x[0]); 

    System.out.println("Nilai x[1] : " + x[1]);

    System.out.println("Nilai x[2] : " + x[2]);

    int [] y = new int[3];      // Cara 2  

    y[0] = 20 ; 

   y[1] = 10 ;

    y[2] = 30;

    System.out.println("Nilai y[0] : " + y[0]);

    System.out.println("Nilai y[1] : " + y[1]);

    System.out.println("Nilai y[2] : " + y[2]);

    int[] z = {20,10,30};           // Cara 3 tdk menggunakan new

    System.out.println("Nilai z[0] : " + z[0]);

    System.out.println("Nilai z[1] : " + z[1]);

    System.out.println("Nilai z[2] : " + z[2]);

    }

}

Contoh 2:

import java.util.*;

public class arr3 {

    public static void main (String[] args) {

      int i,j;

      Scanner input = new Scanner(System.in);

      System.out.print ("Banyak Array : ");

      int x=input.nextInt();

      int nilai[]=new int[x]; 

      System.out.println ("-------------------------------");

      for(i=0;i<nilai.length;i++){

      System.out.print ("Nilai Ke : "+(i+1)+" = ");

      nilai[i]=input.nextInt();

      }

      System.out.println ("--------------------------------");

      System.out.println ("Data yang diinput : ");

      System.out.println ("--------------------------------");

      for(i=0;i<nilai.length;i++){

      System.out.print ("["+nilai[i]+"] ");

    }   

  }

}

Array List

Array list merupakan sebuah class yang memungkinkan kita membuat sebuah objek untuk menampung apapun.

import java.util.ArrayList;

ArrayList al = new ArrayList();

Metode Array List

Karena array list merupakan sebuah objek yang terbuat dari class Array List, maka dia punya method (fungsi) untuk melakukan sesuatu.

•Fungsi add() untuk menambahkan sesuatu ke dalam Array List;

•Fungsi remove() untuk menghapus sesuatu ke dalam Array List;

•Fungsi size() untuk mengambil ukuran Array List;

•Fungsi get(id) untuk mengambil item dalam Array List berdasarkan id atau indeks tertentu.

Contoh :

import java.util.ArrayList;

public class Doraemon {

    public static void main(String[] args) {

        // membuat objek array list

        ArrayList kantongAjaib = new ArrayList();

        // Mengisi kantong ajaib dengan 5 benda

        kantongAjaib.add("Senter Pembesar");

        kantongAjaib.add(532);

        kantongAjaib.add("tikus");

        kantongAjaib.add(1231234.132);

        kantongAjaib.add(true);

        // menghapus tikus dari kantong ajaib

        kantongAjaib.remove("tikus");

        // Menampilkan isi kantong ajaib

        System.out.println(kantongAjaib);

        // menampilkan banyak isi kantong ajaib

        System.out.println("Kantong ajaib berisi "+ kantongAjaib.size() +" item");

    }

}