Link youtube tugas metode sorting

metode sorting selection sort

https;//youtu.be/ljfkReo_9Ds

SOAL METODE GREEDY & KUNCI JAWABAN

LATIHAN SOAL

1.Terdapat 4 buah program (N=4) yang masing-masing mempunyai panjang program (L1=10, L2=3, L3=9, L4=12), Dengan metode optimal storage ontapes problem, tentukan order yang paling optimal!

JAWABAN :

N=4 (L1=10, L2=3, L3=9, L4=12)

ORDERING           D( I )

1,2,3,4                10+(10+3)+(10+3+9)+(10+3+9+12)=79

1,3,2,4                10+(10+9)+(10+9+3)+(10+9+3+12)=85

1,4,3,2                10+(10+12)+(10+12+9)+(10+12+9+3)=88

2,3,4,1                3+(3+9)+(3+9+12)+(3+9+12+10)=73

2,1,4,3                3+(3+10)+(3+10+12)+(3+10+12+9)=84

2,4,3,1                3+(3+12)+(3+12+9)+(3+12+9+10)=76

3,4,2,1                9+(9+12)+(9+12+3)+(9+12+3+10)=88

3,2,1,4                9+(9+3)+(9+3+10)+(9+3+10+12)=77

4,3,2,1                12+(12+9)+(12+9+3)+(12+9+3+10)=91

4,1,3,2                12+(12+10)+(12+10+9)+(12+10+9+3)=99

Dari tabel tersebut, didapat susunan/ order yang optimal, sbb :

- susunan pertama untuk program ke tiga

- susunan ketiga untuk program kesatu

- susunan keempat untuk program kedua

2.-Terdapat sebuah truk dengan kapasitas 80 ton, akan memuat 3 buah barang masing-masing adalah : gula pasir 50 ton dengan harga 100 juta, gula merah 60 ton dengan harga 80 juta dan gula batu 70 ton dengan harga 90 juta.

- Dengan metode Greedy . Tentukan barang apa saja yang dimuat truk dengan harga yang paling mahal.

JAWABAN:

W1, W2, W3 = 50 ton, 60 ton, 70 ton

P1, P2, P3 = 100 jt, 80 jt, 90 jt.

M = 80 ton

N = 3

Profit maksimal

P1= 100 jt = X1 = 1

P2= 80 jt = X2=0

P3=90 jt = X3 = 3/70

Berat minimal:

W1= 50 ton = X1 = 1

W2= 60 ton = X2 = 2/3

W3= 70 ton = X3 = 0

Pilih barang dengan menghitung perbandingan dari profit dibagi berat (Pi/Wi) yang diurut secara tidak naik, yaitu :

P1/W1 = 100/50 = 2 = karna terbesar X1=1

P2/W2 = 80/60 = 1,3 = pembatas X2 = 1/3

P3/W3 = 90/70 = 1,2 = karna terkecil X3 = 0

Dibuatkan tabel berdasarkan elemen dari ke-3 kriteria metode Greedy

Profit Max        W Min                  P/W Max

P1 = 1               W1 = 1                 P1/W1 = 1

P2 = 0               W2 = 2/3              P2/W2 = 1/3

P3 = 3/70          W3 = 0                 P3/W3 = 0

Penjelasan :

Profit Max =  M = 80 ton

                      P1 = 100 jt

                     P3 = 3/70 x 90 = 3,85 / jumlah 100 jt + 3,85 =103.85 profit  

                     W1 = 50 ton                                

                            =P3 = 1/3 x 90 = 30 ton / total berat 50 + 30 = 80 ton

W min =  M = 80 ton 

                P1 = 100 jt

               profit =  2/3 x 60 = 40 / total 100 jt + 40 = 140 profit

               W1 = 50 ton                           

               W2 = 1/2 x 60 = 30 ton / total berat 50 + 30= 80 ton

 P/W max = M = 80 ton

                    P1/W1 = 100/50

                   P1 = 100 

                   P2/W2 = 1/3 x 80 = 26,6 / total 100 + 20 = 126,6 profit

                   W1= 50 ton

                   P2/W2 = 1/3 x 60 = 30 / total berat 50 + 30 = 80 ton

 harga yang paling mahal atau nilai profit maksimal adalah 140  dengan komposisi yang sama

METODE GREEDY

METODE  GREEDY

   A.    Pengertian Metode Greddy

Metode  greedy adalah salah satu jenis algoritma, Metode  greedy menggunakan pendekatan penyelesaian masalah dengan mencari nilai maksimum sementara dalam setiap langkah atau local maxium.

Metode ini banyak digunakan dalan berbagai penyelesaian masalah

 antara lain adalah :                              

      1.      Optimal Storage On Tape problem

·         Bagaimana mengoptimalkan penyimpanan, agar data yang disimpan dapat termuat dengan optimal.

·         Bagaimana susunan yang harus dibentuk.

     2.      Knapsack problem

Knapsack problem adalah suatu masalah bagaimana cara menentukan pemilihan barang dari sekumpulan barang di mana setiap barang tersebut mempunyai berat dan profit masing-masing, sehingga dari pemilihan barang tersebut didapatkan profit yang maksimum.

     3.      Minimum Spanning Tree Problem

Permasalahan umum dari minimum spanning tree adalah mencari minimum biaya (cost) spanning tree dari setiap ruas (edge) suatu graph yang mebentuk pohon (tree).

Untuk masalah minimum spanning tree, syarat graph dapat dicari minimum spanning treenya adalah :

·         Graph harus terhubung

·         Ruasnya punya bobot / nilai

·         Graphnya tidak berarah

Algoritma yang dapat dipakai untuk menentukan minimum spanning tree adalah :

·         Algoritma Solin

·         Algoritma Kruskal

·         Algoritma Prim’s

Skema Umum Algoritma Greedy algoritma greedy disusun oleh elemen-elemen berikut :

1.      Himpunan Kandidat

Berisi elemen-elemen pembentuk solusi.

2.      Himpunan solusi berisi kandidat-kandidat yang terpilih sebagai solusi persoalan.

3.      Fungsi seleksi (selection function).

4.      Fungsi kelayakan (feasible)

5.      Fungsi objektif yaitu fungsi yang memaksimumkan atau meminimumkan nilai solusi (misalnya panjang lintasan, keuntungan, dan lain-lain).

Soal Teknik Searching dan Kunci jawabannya

Silahkan jawab pertanyaan berikut !!

1. Usaha untuk mengurutkan kumpulan –kumpulan data dalam suatu array disebut :

a. Searcing                        c. Sorting 
b. Divide                           d. Concuer
2. Teknik pengurutan dengan cara pemilihan elemen data terkecil untuk kemudian dibandingkan & ditukarkan dengan elemen pada awal data. Adalah teknik pengurutan dengan metode…
a. insertion                    c.buble sort
b. merge sort                d. selection sort 
3. Teknik sort yang bekerja dengan prinsip gelembung yang bergerak naik keatas secara satu persatu. Adalah teknik sort dengan metode..
a. insertion                   c.buble sort 
b. merge sort               d. selection sort
4. Jika terdapat data 14 11 8 5 10 maka langkah kedua pengurutan dengan metode selection adalah …
a. 5 11 8 14 10                c. 5 11 8 10 14
b. 5 8 11 14 10             d. 11 14 8 5 10
5. Berikut ini adalah metode yang digunakan pada teknik sorting, kecuali :
a. Bubble                          c. Heap
b. Fibonacci                    d. Insertion
6. Tehnik dalam memilih dan menyeleksi sebuah elemen dari beberapa elemen yang ada disebut :
a. Searching                      b. Sorting
c. Divide                             d. Conquer
7. Algoritma pencarian elemen Maximal dan Minimal dengan Linier/Sequential Search disebut :
a. StraitMaxMin                      c. Binary Search
b. D AND C                               d. Knapsack
8. Pencarian data dengan meneliti data satu persatu dari posisi awal dikenal dengan istilah :
a. Binary Searching                        c. Random Searchingb.
b. Sequential Searching               d. Binary Searching
9. Bila terdapat deret data atau angka sebanyak 950 buah dan kita akan melakukan pencarian data pada deret tersebut dengan teknik linier search, maka akan membutuhkan waktu maksimal :
a. 400 kali                  c. 95 kali
b. 470 kali                  d. 950 kali 
10. Teknik Pencarian MAXMIN bertujuan untuk..
a. mencari nilai MAX                                  c. Mencari Nilai MIN
b. mencari nilai MAX dan MIN               d. Mengurutkan nilai
11. Teknik yang digunakan untuk mencari suatu data pada himpunan data yang tersusun secara urut dengan cara membagi urutan himpunan menjadi 2 bagian adalah :
a. Sequential Serch                  c. Fibonacci Search
b. Binary Search                    d. D and C Search
12. Metode Greedy dapat digunakan untuk menyelesaikan masalah dibawah ini, kecuali :
a. Knapsack Problem                           c. Faktorial 
b. Shortest Path Problem                     d. Minimum Spanning tree
13. Permasalahan bagaimana mengoptimalisasi storage / memory dalam computer agar data yang disimpan dapat termuat dengan optimal , merupakan bentuk permasalahan dari :
a. Knapsack problem
b. Shortest Path Problem
c. Minimum Spanning Tree
d. Optimal On Tape Storage Problem 
14. Misal terdapat 3 buah program ( n= 5 ) yang masing masing mempunyai panjang program (I1, I2, I3, I4, I5)=(15, 8, 10, 22, 9) Tentukan Urutan penyimpanannya :
a. I4, I1, I3, I5, I2                     c. . I2, I4, I3,I1, I5
b. I2, I5, I3,I1, I4                    d. I4, I1, I2, I5, I1
15. Penyelesaian knapsack dengan Kriteria Greedy adalah dengan konsep dibawah ini , kecuali:
a. Pilih obyek dengan nilai Pi maximal
b. Pilih obyek dengan berat Wi minimal
c. Pilih obyek dengan Pi/Wi maximal
d. Pilih obyek dengan berat Wi maximal
16. Dalam kasus menentukan obyek yang akan dimuat dalam suatu kantong , masing-masing Obyek dari n obyek tersebut harus mempunyai :
a. Berat dan Profil                      c. Profit dan Panjang
b. Berat dan Panjang                    d. Panjang dan Lebar
17. untuk menyelesaikan masalah dengan metode greedy, terdapat dua kriteria yaitu :
a. tujuan utama                      c. nilai pembatas/ constrain
b. a dan c benar                     d. a dan c salah
18. Solusi yang memenuhi semua kendala disebut
a. solusi layak                 c. fungsi tujuan
b. Solusi optimal            d. fungsi pembatas
19. Menghitung jarak satu persatu sesuai dengan arah dari graph yang ditunjuk oleh tiap-tiap ruas/edge dan dilakukan terhadap ruas dari graph yang memiliki jalur awal dan jalur akhir adalah proses untuk mendapatkan solusi optimal dari permasalahan :
a. Knapsack                                        c. Knapsack Problem
b. Shortest Path Problem                d. Minimum Spanning Tree

20. Short Path Problem digunakan untuk mencari jalur ..
a. Terlama                  c. terpanjang
b. Terpendek            d. Terdepan

Soal dan jawaban metode divide dan conquer

Silahkan jawab pertanyaan dibawah ini !!

1.Algoritma yang berprinsip memecahkan permasalahan yang terlalu besar menjadi beberapa bagian kecil sehingga lebih mudah untuk diselesaikan disebut:

      a. Sorting                                                         d. Logika

      b. Divide and Conquer                                 e. Algoritma

      c. Partition exchange sort

2. Tehknik pengurutan dgn cara pemilihan elemen atau proses kerja  dgn memilih elemen data terkecil yang kemudian dibandingkan & ditukarkan dgn elemen pd data awal, dst s/d seluruh elemen shg akan menghasilkan pola data yg telah disort disebut:

      a. Buble Sort                           d. Insertion

      b. Merge Sort                          e. Selection Sort

      c. Quick Sort

3. Tehnik Sort yg bekerja dgn menggunakan prinsip gelembung (bubble) udara yg akan bergerak naik ke atas secara satuper satu di sebut:

      a. Buble Sort                          d. Insertion

      b. Merge Sort                          e. Selection Sort

      c. Quick Sort

4.  Metode QuickSort sering disebut metode partition exchange sort, Diperkenalkan oleh:

      a. Ibnu Nafis                           d. Aristoteles  

      b. C.A.R. Hoare                                e. James Watt

      c. Alexander Graham Bell

     5. 1. Kelompokan deret bilangan kedalam 2 bagian, 4 bagian, 8 bagian, ......dst   à (2ⁿ)

         2. Urutkan secara langsung bilangan dalam kelompok    tsb.

         3. Lakukan langkah diatas untuk kondisi bilangan yg lain sampai didapatkan urutan yg    optimal .

      Perinsip kerja di atas dalam sorting data adalah untuk teknik:

      a. Buble Sort                           d. Insertion

      b. Merge Sort                         e. Selection Sort

      c. Quick Sort

6.  Dalam tehnik Searching yang termasuk tehnik pencarian tunggal adalah:

        a.Tehnik Sequential Search / Linier Search dan Tehnik Binary Search

        b. Tehnik StraitMAXMIN dan Tehnik D and C

 c .Tehnik Best Case

 d. Tehnik Worst Case

 e .Tehnik Average Case

7. Proses yg dilaksanakan pertama kali pd bgn tengah dr elemen himpunan, jk data yg dicari ternyata < elemen bagian atasnya, maka pencarian dilakukan dr bagian tengah ke bawah. Merupakan dalam tehnik:

         a.Tehnik Sequential Search / Linier Search

         b. Tehnik Binary Search **

         c. Tehnik StraitMAXMIN

        d. Tehnik D and C

        e. Tehnik Best Case

8. Rumus untuk menentukan Nilai Tengah (mid) adalah:

       a. ( Low + High ) Div 2

       b. ( Low + High ) - 2

       c. Mid –1

       d. Mid +1

       e. Mid *1

9. Terjadi jika elemen dalam himpunan disusun secara decreasing (menurun), Dengan Oprasi perbandingan sebanyak 2(n-1) kali satuan operasi di sebut:

       a. Worst Case

       b. Best Case

       c. Average Case

       d. StraitMAXMIN

       e. Binary Search

10. Pencarian yg dimulai dari record-1 diteruskan kerecord selanjutnya yaitu record-2, ke-3,..., sampai diperoleh isi record sama dengan informasi yg dicari di sebut:

        a. StraitMAXMIN

        b. Linear/Sequential Search

       c. StraitMAXMIN

       d. Average Case

       e. Best Case

11. Solusi optimal dari permasalahan yg mempunyai dua kriteria yaitu Fungsi Tujuan/Utama & nilai pembatas (constrain) disebut:

       a. Metode D dan C

       b. Metode Greedy

        c. Metode Buble Sort

        d. Metode Quick Sort

       e. Metode Searching

12. Manakah dibawah ini masalah yang bisa diselesaikan dengan Metode GREEDY adalah:

       a. Optimal On Tape Storage Problem

        b. Searching data

        c. Devide dan Conquer

        d. Sorting Data

       e. StartMaxMin

13. Misal terdapat 3 buah program ( n= 4 ) yang masing-masing mempunyai panjang program ( p1,p2,p3,p4)=(5,10, 2,1) Tentukan Urutan penyimpanannya :

       a. p2, p3, p1, p4                                 d. P4, p3, p1, p2          

       b. P3, p2, p1, p4                                 e. p1, p2, p3, p4

       c. p4, p2, p3, p1

14. Penyelesaian knapsack dengan Kriteria Greedy adalah dengan konsep dibawah ini , kecuali :
a. Pilih obyek dengan nilai Pi maximal
b. Pilih obyek dengan berat Wi minimal
c. Pilih obyek dengan Pi/Wi maximal
d. Pilih obyek dengan berat Wi maximal

       e. Pilih obyek dengan berat Pi x Xi

15.  Diketahui bahwa kapasitas M=40 Kg,dengan jumlah barang n=5. Berat Wi barang=(W1,W2,W3,W4,W5)=(14, 10, 20, 12, 16). Nilai Pi barang=(P1,P2,P3,P4,P5) = (28, 40, 70, 36, 24).Profit nilai yang didapat adalah:

          a.140                           d.124
   b.150                          e. 104
   c.160
 16.Diketahui bahwa kapasitas M=40 Kg, dengan jumlah barang n=5. Berat Wi barang = (W1,W2,W3,W4,W5) = (14, 10, 20, 12, 16) Nilai Pi barang = (P1,P2,P3,P4,P5) = (28, 40, 70, 36, 24).  Pola urutan data yang baru untuk Wi adalah:
a.10, 12, 14, 16, 20                  d. 14, 10, 12, 16, 20
b.12, 14, 10, 20, 16                 e. 10, 16, 12, 20, 14

       c. 10, 20, 12, 14, 16

17. Menggunakan soal No.21

         Pola urutan data yang baru untuk Pi adalah:
 a. 28, 70, 36, 40, 24                d. 40, 70, 36, 28, 24    
 b.40, 70, 28, 36, 24                 e. 40, 70, 24, 28, 36

        c. 24, 28, 36, 40, 70

18.  Menghitung jarak satu persatu sesuai dengan arah dari graph yang ditunjuk oleh tiap-tiap ruas/edge dan dilakukan terhadap ruas dari graph yang memiliki jalur awal dan jalur akhir adalah proses untuk mendapatkan solusi optimal dari permasalahan :
a. Knapsack                               d. Minimum Spanning Tree
b. Shortest Path Problem        e. Searching
c. Knapsack Problem

19. Pada gambar diatas. Berapa waktu minimal yang dibutuhkan untuk mencapai ke 5 simpul?

      a. 45                            c. 52                e. 25

      b. 54                            d. 50

20 Dibawah ini yang termasuk kriteria2 dari spanning tree adalah, kecuali :

      a. Setiap ruas pada graph harus terhubung (conected)

      b. Setiap ruas pd graph hrs mpy nilai (label graph)

      c. Setiap ruas pd graph tdk mpy arah (graph tdk berarah)

      d. Setiap ruas pd graph tsb hrs mpy arah (graph berarah)

      e. Salah semua