LTM LOGIKA PERTEMUAN 13

Leny@Blogs

Welcome Guyz!!!!

Minggu, 2-Desember-2012

LTM LOGIKA ALGORITMA PERTEMUAN 13

  SOAL

1. Terdapat sebuah kapal dengan kapasitas 180 Ton, akan memuat  6buah 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,Beras 50 Ton dengan harga 150 Juta, Terigu 20 Ton dengan harga 40 Juta,Minyak Goreng 60 Ton dengan harga 200 Juta.

Dengan metode algoritma Greedy tentukan barang apa saja yang dimuat truk dengan harga yang paling mahal!

2. Apa yang menjadi persyaratan metode Traveling Salesman ,agar perjalanannya efektif dan efisien.

3. Jelaskan manfaat penggunaan Minimum Spanning Tree.

4. Jelaskan manfaat penggunaan Shortest Path Problem.

Jawabanya: ..

  1.      Diketahui M=180

                  N = 6 buah

      (Berat   Wi ) W1 W2 W3 W4  W5 W6    = 50, 60, 70,  50,  20,  60

     (Profit  Pi )  P1 P2 P3  P4  P5  P6         = 100, 80, 90, 150 , 40, 200

     Gula Pasir          => P1 /W1 => 100/50  = 2           = menjadi urutan 4

     Gula Merah        => P2 /W2 =>  80/60   = 1,3       = menjadi urutan 5

     Gula Batu            => P3 /W3 =>  90/70  = 1,28      = menjadi urutan 6

     Beras                   => P4 /W4 => 150/50 = 3           = menjadi urutan 2

     Terigu                  => P5 /W5 =>  40/20  = 2           = menjadi urutan 3

     Minyak goreng    => P6 /W6 => 200/60 = 3,3        = menjadi urutan 1

     Menjadi :

    (Berat   Wi ) W1 W2 W3 W4  W5 W6    = 60,50,20,50,60,70

    (Profit  Pi )  P1 P2 P3  P4  P5  P6           = 200,150,40,100,80,90

2.    Syarat utama yang menjadi persyaratan metode Traveling salesman adalah

Menentukan WAKTU perjalanan seorang salesman seminimal mungkin

3.    Manfaat penggunaan Minimum Spanning Tree adalah untuk memilih ruas suatu Graph dengan biaya seminimal mungkin. Kriterianya  :

-       Setiap ruas pada graph harus terhubung (conected)

-       Setiap ruas pada graph harus mempunyai nilai (label graph)

-       Setiap ruas pada graph tidak mempunyai arah (graph tidak berarah)

4.    Manfaat penggunaan Shortest Path Problem adalah untuk menghitung jalur Terpendek dari sebuah graph berarah

-       Kriterianya : - Setiap ruas pada graph harus mempunyai nilai (label graph)

                    - Setiap ruas pada graph tidak harus terhubung (unconected)

                    - Setiap ruas pada graph harus mempunyai arah (graph berarah)

LTM LOGIKA PERTEMUAN 12

1.       Jelaskan 5 manfaat penggunaan metode Greedy?

Jawaban:

1.       Mendapatkan solusi yang optimal dari permasalahan

2.       Optimal on tape storage problem

3.       Knapsack problem

4.       Minimum spanning tree problem

5.       Shortest path problem

2.       Terdapat  7 buah program (N=7) yang masing-masing mempunyai panjang program (L1=10, L2=3, L3=9, L4=12, L5=20, L6=7, L7=11), dengan metode Optimal  Storage Ontapes Problem. Tentukan order yang paling optimal?

Jawaban:

2314567 = 3 + (3+9) + (3+9+10) + (3+9+10+12) + (3+9+10+12+20) + (3+9+10+12+20+7) +

                     (3+9+10+12+20+7+11) = 258

3.       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:

Kapasitas ransel = 80 ton

Banyak barang =  3

Berat (W)

W_1, W_2, W₃  = 50, 60, 70

Profit (P)

P₁, P₂, P₃ = 100, 80, 90

Tentukan  barang apa saja yang dimuat ditruk dengan harga yang paling mahal!

Jawab :

P₁ = 100                (80-50)=30          X₁ = 1                     (50.1) + (60.0) + (70.30/70) =      

p₂ = 80                                   X₃ = 0                       50   +     0    +         30        =  80  P_i Maximal

P₃ = 90 (30/70)                   X₂ = 30/70

W₁ = 50 (80-50) =30         X₁ = 1                    

W₂ = 60 (30/60) = 1/2     X₂ = 1/2                W_i Minimum

W₃ = 70                                 X₃ = 0

100/50 = 2 (80-50)=30                     X₁ = 1

80/60 = 4/3 (30/60) = 1/2              X₂ = 1/2                               P_i . W_i

90/70 = 1,29                                        X₃ = 0

P_i.∑X_i

(100.1) + (80.0) + (90.30/70) = 100 + 0 + 38,5 = 138,5

(50.1) + (60.1/2) + (70.0) = 50 + 30 + 0 = 80

(100.1) + (80.1/2) + (90.0) = 100 + 40 + 0 = 140

4.      Dalam metode greedy jelaskan apa yang menjadi fungsi tujuan dan fungsi pembatas?

Jawaban:

          Fungsi tujuan       = fungsi yang menjadi penyelesaian permasalahan dengan mendapatkan solusi yang optimal.

                Fungsi pembatas = memberikan batas maksimal dari setiap obyek untuk dapat dimuat sehingga kapasitasnya tidak melebihi dari jumlah maksimal daya tampung.

LTM LOGIKA PERT 10

1.       Jelaskan pengertian Device and Conquer serta tujuannya?

Jawabannya:

Algoritma Divide and Conquer merupakan algoritma yang sangat popular di dunia Ilmu Komputer. Divide and Conquer merupakan algoritma yang berprinsip memecah-mecah permasalahan yang terlalu besar menjadi beberapa bagian kecil sehingga lebih mudah untuk diselesaikan.

Divide         :  membagi masalah menjadi beberapa masalah yang memiliki kemiripan dengan      

                    masalah semula namun berukuran lebih kecil (idealnya berukuran hampir sama),

Conquer    :  memecahkan (menyelesaikan) masing-masing masalah (secara  rekursif), dan

Combine    :  mengabungkan solusi masing-masing masalah sehingga membentuk solusi masalah   

                       semula. 

2.       Sebutkan algoritma metode sorting!

a.       Selection Sort

b.      Bubble Sort

c.       Merge Sort

d.      Quick Sort

e.      Insertion Sort

Jawabannya:

a.       #include<constrea.h>

#include<stdio.h>

void tampilkan_larik(int data[],int n)

{

int i;

for(i=0;i<n;i++)

cout<<data[i]<<" ";

cout<<endl<<endl;

}

void selection_sort(int data[],int n)

{

int posmin,posawal,j,tmp;

for(posawal=0;posawal<n-1;posawal++)

{

posmin=posawal;

for(j=posawal+1;j<n;j++)

if(data[posmin]>data[j])

posmin=j;

//tukarkan

tmp=data[posawal];

data[posawal]=data[posmin];

data [posmin]=tmp;

cout<<"\nHasil Ketika Posawal = "<<posawal<<":";

tampilkan_larik(data,n);

}

}

//global

int main()

{

int data[50],i,n;

cout<<"\n@Simulasi Selection Sort@\n\n\n";

cout<<"==================================\n";

cout<<"       Masukkan Banyak Data : ";cin>>n;

clrscr();

for(int a=0;a<n;a++)

{cout<<"\nMasukkan Data Ke "<<a<<":";cin>>data[a];}

selection_sort(data,n);

//hasil pengurutan

cout<<"\n\nHasil Pengurutan : \n\n";

cout<<" ";tampilkan_larik(data,n);

cout<<"\nSorting Selesai....";

getch();

}

b.      #include<constrea.h>

#include<stdio.h>

int data[10],data2[10];

int n;

void tukar(int a,int b)

{

int t;

t=data[b];

data[b]=data[a];

data[a]=t;

}

void bubble_sort()

{

for(int i=1;i<n;i++)

{

for(int j=n;j>=i;j--)

{

if(data[j]<data[j-i])tukar(j,j-i);

}

}

}

void main()

{

cout<<"===Program Bubble Sort==="<<endl;

//input data

cout<<"Masukkan Jumlah Data : ";cin>>n;

for(int i=1;i<n;i++)

{

cout<<"\nMasukkan Data Ke "<<i<<":";cin>>data[i];

data2[i]=data[i];

}

bubble_sort();

cout<<"\n\n";

//tampilkan data

cout<<"Data setelah di sort : ";

for(int i=1;i<=n;i++)

{

cout<<" "<<data[i];

}

cout<<"\nSorting Selesai....";

getch();

}

c.       #include<constrea.h>

//using namespace std

void merge(int low,int id,int up);

void mergeSort(int low,int up);

int a[50];

int main()

{

int jumlahBil,i;

cout<<"Masukkan Jumlah Elemen Array"<<endl;cin>>jumlahBil;

for(int i=0;i<jumlahBil;i++)

{

cout<<"Bilangan Ke - "<<i+1<<endl;cin>>a[i];

}

mergeSort(1,jumlahBil);

for(i=1;i<=jumlahBil;i++)

cout<<a[i]<<"   ";

cout<<endl;

getch();

}

void merge(int low,int mid,int up)

{

int h,i,j,k;

int b[50];

h=low;

i=low;

j=mid+1;

while((h<=mid)&&(j<=up))

{

if(a[h]<a[j])

{

b[i]=a[h];h++;

}

else

{

b[i]=a[j];

j++;

}

i++;

}

if(h>mid)

{

for(k=j;k<=up;k++)

{b[i]=a[k];i++;}

}

else

{for(k=h;k<=mid;k++)

{b[i]=a[k];i++;}

}

for(k=low;k<=up;k++)a[k]=b[k];

}

void mergeSort(int low,int up)

{

int mid;

if(low<up)

{

mid=(low+up)/2;

mergeSort(low,mid);

mergeSort(mid+1,up);

merge(low,mid,up);

}

}

d.      #include<constrea>

#define max 30

void quick_sort(int darr[max],int lb,int ub)

{

int a,up,down,temp;

if(lb>=ub)

return;

a=darr[lb];

up=ub;

down=lb;

while(down<up)

{

while(darr[down]<=a)

down++;

while(darr[up]>a)

up--;

if(down<up)

{

temp=darr[down];

darr[down]=darr[up];

darr[up]=temp;

}}

darr[lb]=darr[up];

darr[up]=a;

quick_sort(darr,lb,up-1);

quick_sort(darr,up+1,ub);

}

main()

{

int arr[max],i,n,lb,ub;

lb=0;

cout<<"masukkan banyak data yang ingin diurut = ";cin>>n;

ub=n;

cout<<"masukkan data-datanya :\n\n";

for(i=1;i<=n;i++)

{

cout<<"data ke-"<<i<<" : ";cin>>arr[i];

}

quick_sort(arr,lb,ub);

cout<<"\nhasil pengurutan data :";

for(i=1;i<=n;i++)

cout<<"  "<<arr[i];

getch();

}

e.      #include<constrea.h>

int data[10],data2[10];

int n;

void insertion_sort()

{

int temp,i,j;

for(i=1;i<n;i++)

{

temp=data[i];

j=i-1;

while(data[j]>temp&&j>=0)

{

data[j+1]=data[j];

j--;

}

data[j+1]=temp;

}

}

void main()

{

cout<<"===Program Insertion Sort==="<<endl;

//input data

cout<<"Masukkan jumlah data : ";cin>>n;

for(int i=1;i<n;i++)

{

cout<<"Masukkan data ke "<<i<<":";cin>>data[i];

data2[i]=data[i];

}

insertion_sort();

cout<<"\n\n";

//tampilkan data

cout<<"\nData setelah di sort : ";

{

for(int i=1;i<=n;i++)

cout<<" "<<data[i];

}

cout<<"\n\nsorting selesai";

getch();

}

3.       Terdapat deret angka : 99, 34, 11, 50, 23, 89, 65, 2, 6, 37, 74, 44.

Urutkan dengan seluruh teknik sorting yang ada!

Jawaban:

a.       Selection sort

b.      Bubble Sort

c. Merge Sort

a.  Quick Sort

b. Insertion sort

4.      Terdapat deret angka : 12, 45, 10, 55, 32, 81, 59, 21, 16, 71, 40, 90

Urutkan dengan seluruh teknik sorting yang ada!

Jawaban:

a.       Selection Sort

b.      Bubble Sort

c.       Merge Sort

d.      Quick Sort

e.      Insertion Sort