LATIHAN SOAL PERTEMUAN 14 ( COLORING )

Nama kelompok :

#Tiar Prasetiyo ( 17190782 )

#Rivaldi Nazar Yuniar ( 17190659 )
#Eko Mardiyanto ( 17190801 )
#Rian Ferdian Maulana ( 17190684 )

UNIVERSITAS BINA SARANA INFORMATIKA
Kelas ( 17.1E.07 )

LATIHAN SOAL PERTEMUAN 14 
LOGIKA DAN ALGORITMA

LATIHAN SOAL PERTEMUAN 13 ( METODE TRAVELLING SALESMAN & MINIMUM SPANNING TREE )

Nama kelompok :

#Tiar Prasetiyo ( 17190782 )

#Rivaldi Nazar Yuniar ( 17190659 )
#Eko Mardiyanto ( 17190801 )
#Rian Ferdian Maulana ( 17190684 )

UNIVERSITAS BINA SARANA INFORMATIKA
Kelas ( 17.1E.07 )

LATIHAN SOAL PERTEMUAN 13 
LOGIKA DAN ALGORITMA

1. Gunakan metode travelling salesman

Terapat 4 kota yaitu ABCD.

Jarak antar kota A, B, C, dan D sebagai berikut :

Jarak A ke B = 7, A ke C = 5, A ke D = 3, B ke C = 6, B ke D = 6, Dan C ke D = 2.

Graf dapat dilihat dibawah ini

Kota pusat : A

Buat lasolusi untuk jalur terpendeknya

Problem diatas menghasilkan waktu minimalnya adalah 18 diperoleh perjalanan sebagai berikut :

2. Buat lah minimum spanning tree (MST) dan nilai bobotnya dari graf berikut ini dengan menggunakan algoritma solin dan kruskal.

graf G :

Penyelesaian Algoritma Solin

1. Urutkan Ruas Graf (G) menurut bobotnya dari bobot terbesar sampai bobot terkecil.

BOBOT	RUAS
10	E,F	E,G
9	B,E	E,I
8	D,E	E,H
7	C,F	G,J	I,J
6	D,F	G,H	H,J
5	A,B	A,C
4	C,D	B,D	H,I
3	F,G

2. Lakukan penghapusan masing masing ruas yang tidak menyebabkan graf menjadi tidak terhubung atau membentuk sirkuit, kita mulai melakukan tahapan penghapusan dengan ruas dengan nilai terbesar sampai nilai terkecil.

1. Bobot : 10 EF, EG

Ruas EF, EG Tidak Dihapus karena ruas tersebut menyebabkan graf terhubung

2. Bobot : 9 BE, EI

BE, EI Tidak dihapus karena dua ruas tersebut menghubungkan graf

3. bobot : 8 DE, EH

Ruas DE, EH TIdak dihapus karena dua ruas tersebut menghubungkan graf

4. Bobot 7 : CF, GJ, IJ

Ruas CF GJ dihapus Sedangkan IJ dihapus Karena membentuk sirkuit

5. Bobot 6 : DF, GH, HJ

Ruas DF, GH, HJ dihapus karena membentuk sirkuit

6. Bobot 5 : AB, AC

Ruar AB tidak dihapus sedangkan AC dihapus karena membentuk sirkuit

7. Bobot 4 : BD, CD, HI

Ruas BD, CD, HI dihapus karena membentuk sirkuit

8. Bobot 3 : FG

Ruas FG dihapus karena membentuk sirkuit

Tahap penghapusan selesai, bobot 4 adalah minimum Spanning Tree dari graf G dengan nilai : 73

Penyelesaian Algoritma Kruskal

1. Mula mula kita buat graf G hanya terdiri dari simpul saja

2. Urutkan ruas dari bobot terkecil ke bobot terbesar (FG,CD,BD,HI,AB,AC,DF,GH,HJ,CF,GJ,IJ,DE,EH,BE,EI,EF,EG), Kemudian berdasarkan urutan tersebut, kita menambahkan ruas dengan mencegah terbentuknya sirkuit.

Gambar 1 : Penambahan Ruas FG

Gambar 2 : Penambahan Ruas BD, CD, HI

Gambar 3 : Penambahan Ruas AB, Ruas AC tidak dilakukan

Gambar 4 : Penambahan ruas DF, GH, HJ

Gambar 5 : Penambahan CF, GJ, IJ Tidak dilakukan karena membentuk sirkuit

Gambar 6 : Penambahan ruas DE dilakukan, sedangkan ruas EH tidak dilakukan karena membentuk sirkuit

Gambar 7 : Penambahan Ruas BE, EI tidak dilakukan karena membentuk sirkuit

Gambar 8 : Penambahan Ruas EF, EG tidak dilakukan karena membentuk sirkuit

Gambar 9 : SELESAI

MST Graf G Nilainya 46 

3. gunakan dijstra algoritma untuk mencari rute terpendek antara node 1 dan setiap node lainnya dalam jaringan berikut :

Titik Pengunjung	1	2	3	4	5	6	7	8
#	#	#	#	#	#	#	#	#
1	0	1	2	#	#	#	#	#
1,2	#	1	2	#	#	#	#	#
1,2,3	#	#	2	4	3	6	#	#
1,2,3,5	#	#	#	#	3	6	10	#
1,2,3,5,6	#	#	#	#	#	6	9	8
1,2,3,5,6,8	#	#	#	#	#	#	#	8

Titik Pengunjung	1	2	3	4	5	6	7
#	#	#	#	#	#	#	#
1	0	5	1	#	#	#	#
1,3	#	3	1	7	#	#	#
1,3,2	#	3	#	10	3	6	#
1,3,2,5	#	#	#	7	3	9	10
1,3,2,5,4	#	#	14	7	#	8	13
1,3,2,5,4,6	#	15	#	#	#	8	10
1,3,2,5,4,6,7	#	#	#	#	#	#	10

LATIHAN SOAL PERTEMUAN 12 ( METODE GREEDY )

Nama kelompok :

#Tiar Prasetiyo ( 17190782 )

#Rivaldi Nazar Yuniar ( 17190659 )
#Eko Mardiyanto ( 17190801 )
#Rian Ferdian Maulana ( 17190684 )

UNIVERSITAS BINA SARANA INFORMATIKA
Kelas ( 17.1E.07 )

LATIHAN SOAL PERTEMUAN 12 
LOGIKA DAN ALGORITMA

PERTEMUAN 12 (METODE GREEDY)

1. Diketahui 4 program yang akan disimpan dalam media penyimpanan dengan panjang masing masing 6,8,4,2. Bagaimana proses penyimpanan yang optimal dengan metode greedy?
Jawab : 

N = 4 jadi 4 = 4 x 3 x 2 x 1 = 24

Jadi dibutuhkan 24 langkah dalam penyusunannya

L1=6

L2=8

L3=4

L4=2

No	Order	D(L)	Total
1	1,2,3,4	6+(6+8)+(6+8+4)+(6+8+4+2)	58
2	1,2,4,3	6+(6+8)+(6+8+2)+(6+8+2+4)	56
3	1,3,2,4	6+(6+4)+(6+4+8)+(6+4+8+2)	54
4	1,3,4,2	6+(6+4)+(6+4+2)+(6+4+2+8)	50
5	1,4,2,3	6+(6+2)+(6+2+8)+(6+2+8+4)	46
6	1,4,3,2	6+(6+2)+(6+2+4)+(6+2+4+8)	40
7	2,1,4,3	8+(8+6)+(8+6+2)+(8+6+2+4)	64
8	2,1,3,4	8+(8+6)+(8+6+4)+(8+6+4+2)	60
9	2,3,1,4	8+(8+4)+(8+4+6)+(8+4+2+6)	58
10	2,3,4,1	8+(8+4)+(8+4+2)+(8+6+6+2)	54
11	2,4,3,1	8+(8+2)+(8+2+4)+(8+2+6+4)	52
12	2,4,1,3	8+(8+2)+(8+2+6)+(8+2+4+6)	58
13	3,4,2,1	4+(4+2)+(4+2+8)+(4+2+8+6)	44
14	3,4,1,2	4+(4+2)+(4+2+6)+(4+2+6+8)	42
15	3,2,1,4	4+(4+8)+(4+8+6)+(8+4+6+2)	54
16	3,2,4,1	4+(4+8)+(4+8+2)+(8+4+2+6)	50
17	3,1,2,4	4+(4+6)+(4+6+8)+(4+6+8+2)	40
18	3,1,4,2	4+(4+6)+(4+6+2)+(4+6+2+8)	46
19	4,3,2,1	2+(2+4)+(2+4+8)+(2+4+8+6)	42
20	4,3,1,2	2+(2+4)+(2+4+6)+(2+4+6+8)	40
21	4,2,1,3	2+(2+8)+(2+8+6)+(2+8+6+4)	48
22	4,2,3,1	2+(2+8)+(2+8+4)+(2+8+4+6)	46
23	4,1,2,3	2+(2+6)+(2+6+8)+(2+6+8+4)	46
24	4,1,3,2	2+(2+6)+(2+6+4)+(2+6+4+8)	42

4 Dari nilai diatas didapat nilai minimal adalah

a. Nilai terkecil pertama adalah 40, yaitu untuk posisi penyimpanan urutan ke-1 pada posisi            ke-6
b    b. Nilai terkecil pertama adalah 42, yaitu untuk posisi penyimpanan urutan ke-3 pada posisi            ke-2
      c. Nilai terkecil pertama adalah 46, yaitu untuk posisi penyimpanan urutan ke-4 pada posisi            ke-4
      d. Nilai terkecil pertama adalah 52, yaitu untuk posisi penyimpanan urutan ke-2 pada posisi            ke-5

2. Diketahui 4 barang yang akan disimpan pada suatu tempat yang memiliki kapasitas maksimal sebesar 30kg. Berat masing masing adalah 15kg, 10kg, 18kg, dan 20kg dimana setiap barang memiliki profit sebesar masing masing 20, 25, 9 dan 15. Tentukan barang mana saja yang dapat disimpan dalam tempat penyimpanan sehingga diperoleh nilai profit yang maksimal! (Cari dengan kriteria greedy dan algoritma greedy).

1. Diketahui

N = 4

M = 30 Kg

W1 = 15 | P1 = 20

W2 = 10 | P2 = 25

W3 = 18 | P3 = 9

W4 = 20 | P4 = 15

2. Mengurutkan Berdasarkan Profit Terbesar (Pi)

P2 = 25 | W2 = 10

P1 = 20 | W1 = 15

P4 = 15 | W4 = 20
   
P3 = 9 | W3 = 18

3. Mengurutkan Bersadarkan Berat Tekecil (Wi)

    · P2 = 25 | W2 = 10

    · P1 = 20 | W1 = 15

    · P3 = 9 | W3 = 18

    · P4 = 15 | W4 = 20

4. Perbandingan Profit dengan Bobot

    · P1 = 20 | W1 = 15

    · P2 = 25 | W2 = 10

    · P3 = 9 | W3 = 18

    · P4 = 15 | W4 = 20

Perbandingan Proft dengan Bobot

· P1/W1 = 20/15 = 1.3 <<< Urutan Kedua >>>

· P2/W2 = 25/10 = 2.5 <<< Urutan Pertama >>>

· P3/W3 = 9/18 = 0.5 <<< Urutan Ke Empat >>>

· P4/W4 = 15/20 = 0.75 <<< Urutan Ketiga >>>