Function knapsack greedy di DEVV C++

#include <cstdlib>
#include <iostream>

using namespace std;
void knapsack(int n, float weight[], float profit[], float capacity)
{
 float x[20], tp= 0;
 int i, j;
 float u=capacity;

 for (i=0;i<n;i++)
     x[i]=0.0;

 for (i=0;i<n;i++)
 {
 if(weight[i]>u)
      break;
 else
     {
     x[i]=1.0;
     tp= tp+profit[i];
     u=u-weight[i];
     }
 }

 if(i<n)
       x[i]=u/weight[i];

 tp= tp + (x[i]*profit[i]);

 printf("\n The result vector is:- ");
 for(i=0;i<n;i++)
        printf("%f\t",x[i]);

 printf("\m Maximum profit is:- %f", tp);

}

int main()
{
 float weight[20], profit[20], capacity;
 int n, i ,j;
 float ratio[20], temp;


 printf ("\n Enter the no. of objects:- ");
 scanf ("%d", &n);

 printf ("\n Enter the wts and profits of each object:- ");
 for (i=0; i<n; i++)
 {
 scanf("%f %f", &weight[i], &profit[i]);
 }

 printf ("\n enter the capacityacity of knapsack:- ");
 scanf ("%f", &capacity);

 for (i=0; i<n; i++)
 {
 ratio[i]=profit[i]/weight[i];
 }

 for(i=0; i<n; i++)
 {
    for(j=i+1;j< n; j++)
    {
      if(ratio[i]<ratio[j])
      {
      temp= ratio[j];
      ratio[j]= ratio[i];
      ratio[i]= temp;

     temp= weight[j];
     weight[j]= weight[i];
     weight[i]= temp;

     temp= profit[j];
     profit[j]= profit[i];
     profit[i]= temp;
     }
   }
 }

 knapsack(n, weight, profit, capacity);


    system("PAUSE");
    return EXIT_SUCCESS;
}

Read More

PROGRAM LAGORITMA DIJKSTRA

#include <cstdlib>
#include <iostream>
#define max 20
#define infinity 9999

using namespace std;
class dijkstra{
      private:
              int n,graph[max][max],colour[max],start,distance[max],predecessor[max];
              enum {green,yellow,red};
      public:
             void read_graph();
             void initialize();
             int select_min_distance_lable();
             void update(int);
             void output();
             void function();

      };
void dijkstra::read_graph(){
     cout<<"masukkan jumlah node = ";
     cin>>n;
     cout<<"masukkan nilai matrik untuk graf ::\n";
     int i,j;
     for(i=1;i<=n;i++){
                       for(j=1;j<=n;j++){
                                         cout<<"["<<i<<"],["<<j<<"]=";
                                         cin>>graph[i][j];}}
     for(i=1;i<=n;i++){
                       colour[i]=green;}
     cout<<"masukkan vertex mulai :: ";
     cin>>start;
     }
void dijkstra::initialize(){
     for(int i=1;i<=n;i++){
             if(i==start){
                          distance[i]=0;}
             else{distance[i]=infinity;}
     }
     for(int j=1;j<=n;j++){
             if(graph[start][j]!=0){
                                    predecessor[j]=start;}
             else{predecessor[j]=0;}
     }
}
int dijkstra::select_min_distance_lable(){
    int min=infinity;
    int p=0;
    for(int i=1;i<=n;i++){
            if(colour[i]==green){
                                 if(min>=distance[i]){
                                                   min=distance[i];
                                                   p=i;
                                                   }
                                 }
            }
    return p;
    }
void dijkstra::update(int p){
     cout<<"\nupdate jarak = \n";
     for(int i=1;i<=n;i++){
             if(colour[i]==green){
                                  if(graph[p][i]!=0){
                                                     if(distance[i]>graph[p][i]+distance[p]){
                                                                                             distance[i]=graph[p][i]+distance[p];
                                                                                             predecessor[i]=p;
                                                                                             }
                                                     }
                                  }
             cout<<distance[i]<<'\t';
             }
     }
void dijkstra::output()
{
 cout<<"****** Jalur akhir dan distacnes adalah ******\n\n";

 for(int i=1;i<=n;i++)
 {
  if(predecessor[i]==0 && i!=start)
  {
   cout<<"jalan tidak ada antara "<<i<<" dan awal titik "
    <<start<<endl;
   exit(1);
  }
  cout<<"jalan untuk node "<<i<<" is ::\n";
  int j=i;
  int array[max];
  int l=0;
  while(predecessor[j]!=0)
  {
   array[++l]=predecessor[j];
   j=predecessor[j];
  }
  for(int k=l;k>=1;k--)
   cout<<array[k]<<"->";

  cout<<i<<endl;
  cout<<"jarak adalah "<<distance[i]<<endl<<endl<<endl;
 }
}

void dijkstra::function()
{
 cout<<"\n**********************************************************************\n";
 cout<<"*Program ini adalah untuk menerapkan algoritma dijkstra dengan menggunakan kode warna* \n";
 cout<<"**********************************************************************\n\n";
 read_graph();
 initialize();  //repeate until all nodes become red
 int flag=0;
 int i;

 cout<<"\n\n******** Kerja dari algoritma ini adalah **********\n\n";

 for(i=1;i<=n;i++)
  if(colour[i]!=red)
   flag=1;

 cout<<"Jarak awal adalah ::\n";
 for(i=1;i<=n;i++)
  cout<<distance[i]<<'\t';
 cout<<endl;

 while(flag)
 {
  int p=select_min_distance_lable();
  cout<<"\nJarak min label yang berwarna kuning adalah "<<p;
  colour[p]=yellow;

  update(p);
  cout<<"\nnode ="<<p<<" berwarna merah "<<endl;
  colour[p]=red;

  flag=0;
  for(i=1;i<=n;i++)
   if(colour[i]!=red)
    flag=1;

  cout<<endl<<endl<<endl;
 }
 output();
}

int main(int argc, char *argv[])
{
    dijkstra d;
 d.function();
    system("PAUSE");
    return EXIT_SUCCESS;
    }

Read More

GARFIKA PRAKTIKUM 6

#include <windows.h> 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h>
#include <stdarg.h> 
#include <glut.h>
#include <glu.h>
#include <iostream>

float _angle = 45.0f;

//Draws the 3D scene
void mydisplay() 
{ 
    glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
    glMatrixMode(GL_MODELVIEW);//Switch to setting
    glLoadIdentity();//Reset the camera
    //glTranslatef(0.0f, 0.6f, 0.0f);
    //glScalef(0.7f, 0.7f, 0.7f);
    //glRotatef(_angle, 0.0f, 0.0f, 1.0f);
    glPushMatrix();//Save the transformations
    glBegin(GL_POLYGON); 
    glVertex3f(-0.1f, -0.1f,0.0f); 
    glVertex3f(-0.1f, 0.1f,0.0f); 
    glVertex3f(0.1f, 0.1f,0.0f); 
    glVertex3f(0.1f, -0.1f,0.0f); 
    glEnd();

    glPopMatrix();//Undo the move to the center of
    glutSwapBuffers();//Send the 3D scene to the
    glFlush(); 
}

void update(int value) {
    _angle += 9.0f;
    if (_angle > 360) {
        _angle -= 360;
    }
   
    glutPostRedisplay();
    glutTimerFunc(25, update, 0);
}
    
int main(int argc, char** argv) 
{ 
glutInitWindowSize(400, 400);
printf("Contoh Sederhana Kotak "); 
glutCreateWindow("Praktikum06");
glutDisplayFunc(mydisplay);
glutTimerFunc(25, update, 0);
glutMainLoop(); 
return 0;
}

Read More

pseudo-code Algoritma Kruskal

int kruskal(int n, int m, set_of_edges E,

set_of_edges& F)

{

set_pointer p, q;

edge e;

sort the m edges in E by weight;

initial(n);

while (# of edges in F < n1)

{

e = next lowest weight edge;

i,j = e.indices();

p = find(i);

q = find(j);

if (! equal(p,q)) {

merge(p,q);

add e to F;

}

}

}

Read More

Program Prims Baru

#include<iostream.h>
#include<conio.h>
class prims
{
private:
int n; //no of nodes
int graph_edge[250][4]; //edges in the graph
int g; //no of edges in the graph
int tree_edge[250][4]; //edges in the tree
int t; //no of edges in the tree
int s; //source node
//Partition the graph in to two sets
int T1[50],t1; // Set 1
int T2[50],t2; // Set 2
public:
void input();
int findset(int);
void algorithm();
void output();
};
void prims::input()
{
cout<<"*************************************************\n"
<<"This program implements the prims algorithm\n"
<<"*************************************************\n";
cout<<"Enter the no. of nodes in the undirected weighted graph ::";
cin>>n;
g=0;
cout<<"Enter the weights for the following edges ::\n";
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
cout<<" < "<<i<<" , "<<j<<" > ::";
int w;
cin>>w;
if(w!=0)
{
g++;
graph_edge[g][1]=i;
graph_edge[g][2]=j;
graph_edge[g][3]=w;
}
}
}
// print the graph edges
cout<<"\n\nThe edges in the given graph are::\n";
for(int i=1;i<=g;i++)
cout<<" < "<<graph_edge[i][1]
<<" , "<<graph_edge[i][2]
<<" > ::"<<graph_edge[i][3]<<endl;
}
int prims::findset(int x)
{
for(int i=1;i<=t1;i++)
if(x==T1[i])
return 1;
for(int i=1;i<=t2;i++)
if(x==T2[i])
return 2;
return -1;
}
void prims::algorithm()
{
t=0;
t1=1;
T1[1]=1; //The source node
t2=n-1;
int i;
for(i=1;i<=n-1;i++)
T2[i]=i+1; //The reamining nodes
cout<<"\n*****The algorithm starts*****\n\n";
while(g!=0 && t!=n-1)
{
// Find the least cost edge
int min=9999;
int p;
int u,v,w;
for(i=1;i<=g;i++)
{
bool flag1=false,flag2=false;
//if u and v are in different sets
if(findset(graph_edge[i][1])!=findset(graph_edge[i][2]))
{
if(min>graph_edge[i][3])
{
min=graph_edge[i][3];
u=graph_edge[i][1];
v=graph_edge[i][2];
w=graph_edge[i][3];
p=i;
}
}
}
//break if there is no such edge
cout<<"The edge included in the tree is ::";
cout<<" < "<<u<<" , "<<v<<" > "<<endl;
//delete the edge from graph edges
for(int l=p;l<g;l++)
{
graph_edge[l][1]=graph_edge[l+1][1];
graph_edge[l][2]=graph_edge[l+1][2];
graph_edge[l][3]=graph_edge[l+1][3];
}
g--;
//add the edge to the tree
t++;
tree_edge[t][1]=u;
tree_edge[t][2]=v;
tree_edge[t][3]=w;
//Alter the set partitions
t1++;
int m;
if(findset(v)==2)
{
T1[t1]=v;
m=v;
}
else if(findset(u)==2)
{
T1[t1]=u;
m=u;
}
int x;
for(x=1;T2[x]!=m;x++);
for(;x<t2;x++)
T2[x]=T2[x+1];
t2--;
// Print the sets
int k;
cout<<"NOW\nT1 :: ";
for(k=1;k<=t1;k++)
cout<<T1[k]<<' ';
cout<<endl;
cout<<"T2 :: ";
for(k=1;k<=t2;k++)
cout<<T2[k]<<' ';
cout<<endl;
cout<<"The graph edges are ::\n";
for(i=1;i<=g;i++)
cout<<" < "<<graph_edge[i][1]
<<" , "<<graph_edge[i][2]
<<" > ::"<<graph_edge[i][3]<<endl;
cout<<endl<<endl;
}
}
void prims::output()
{
cout<<"\nThe selected edges are ::\n";
for(int i=1;i<=t;i++)
cout<<" < "<<tree_edge[i][1]
<<" , "<<tree_edge[i][2]
<<" > ::"<<tree_edge[i][3]<<endl;
}
int main()
{
prims obj;
obj.input();
obj.algorithm();
obj.output();
getch();
return 0;
}

• HASIL RUNNING PROGRAM :

Read More

PROGRAM KRUSKAL

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define edge pair< int, int >
#define MAX 1000

vector< pair< int, edge > > GRAPH, MST;
int verteks, edg, parent[MAX], total ;

int findset(int , int );
void cetak();
void kruskal();
void reset();

int main()
{
    int i, u, v, w;
    printf("Masukkan jumlah verteks : ");
    scanf("%d", &verteks);
    printf("Masukkan jumlah edge : ");
    scanf("%d", &edg);
    reset();
    printf("Masukkan verteks awal, verteks akhir, dan panjang edge-nya : \n");
    for(i=0; i<edg; i++)
    {
        scanf("%d %d %d", &u, &v, &w);
        GRAPH.push_back(pair< int, edge >(w, edge(u, v)));
    }
    kruskal();
    cetak();
system ("PAUSE");
    return 0;
}

int findset(int x, int *parent)
{
    if(x != parent[x])
        parent[x] = findset(parent[x], parent);
    return parent[x];
}

void kruskal()
{
    int i, pu, pv;
    sort(GRAPH.begin(), GRAPH.end()); //fungsi untuk mengurutkan dari kecil ke besar.
    for(i=total=0; i<edg; i++)
    {
        pu = findset(GRAPH[i].second.first, parent);
        pv = findset(GRAPH[i].second.second, parent);
        if(pu != pv)
        {
            MST.push_back(GRAPH[i]);
            total += GRAPH[i].first;
            parent[pu] = parent[pv];
        }
    }
}

void reset()
{
    for(int i=1; i<=verteks; i++) parent[i] = i;
}

void cetak()
{
    int i, ukuran;
    ukuran = MST.size();
    for(i=0; i<ukuran; i++)
    {
        printf("( %d", MST[i].second.first);
        printf(", %d )", MST[i].second.second);
        printf(": %d\n", MST[i].first);
    }
    printf("Minimum cost: %d\n", total);
}

HASIL RUNNING :

Read More

Kapan Terjadinya Konkurensi

1.     .  Jelaskan kapan terjadi Konkurensi?

Jawab  :

Konkurensi adalah proses-proses (lebih dari satu proses) yang terjadi pada saat bersamaan. Konkurensi merupakan landasan umum perancangan sistem operasi. Proses-proses disebut konkuren jika proses-proses berada pada saat yang sama.

Konkurensi dapat terjadi pada, antara lain:

a)     Banyak aplikasi (multiple application).

Multiprogramming memungkinkan banyak proses sekaligus dijalankan. Proses-proses dapat berasal dari aplikasi-aplikasi berbeda. Pada sistem multiprogramming bisa terdapat banyak aplikasi sekaligus yang dijalankan di sistem komputer.

b)    Aplikasi terstruktur.

Perluasan prinsip perancangan modular dan pemrograman terstruktur adalah suatu aplikasi dapat secara efektif diimplementasikan sebagai sekumpulan proses. Dengan sekumpulan proses, maka tiap proses menyediakan satu layanan spesifik tertentu.

c)     Struktur sistem operasi.

Keunggulan strukturisasi dapat juga diterapkan ke pemrograman sistem. Beberapa sistem operasi aktual yang dipasarkan dan yang sedang dalam riset telah diimplementasikan sebagai sekumpulan proses. Sistem operasi bermodelkan client/server menggunakan pendekatan ini.

d)    Untuk Strukturisasi Satu Proses.

Saat ini untuk peningkatan kinerja maka satu proses dapat memiliki banyak thread yang independen. Thread-thread tersebut harus dapat bekerjasama untuk mencapai tujuan proses.

2.     Jelaskan beserta contoh, masalah- masalah yang terjadi ketika terjadi konkurensi?

Jawab :

Ø  Mutual Exclusion

Adalah jaminan hanya satu proses yang mengakses sumber daya pada suatu interval waktu tertentu. Proses-proses yang lain dilarang mengerjakan hal yang sama. Bagian program yang sedang mengakses memori atau sumber daya yang dipakai bersama disebut Critical Section/Region. Mutual Exclusion merupakan jaminan untuk mengatasi kondisi pacu agar tidak boleh 2 proses atau lebih memasuki Critical Section secara bersamaan. Kesuksesan proses- proses kongkuren memerlukan pendefinisian Critical Section dan memaksakan Mutual Exclusion di antara proses-proses kongkuren yang sedang berjalan. Pemaksaan Mutual Exclusion merupakan landasan pemrosesan kongkuren.

Contoh Mutual Exclusion :

Apabila kita sedang duduk di sebuah kursi orang lain tidak bisa menduduki kursi tersebut hingga kita pergi dari kursi itu.

Ø  Deadlock.

 adalah suatu kondisi dimana dua proses atau lebih saling menunggu proses yang lain untuk melepaskan resource yang sedang dipakai. Karena beberapa proses itu saling menunggu, maka tidak terjadi kemajuan dalam kerja proses-proses tersebut. Deadlock adalah masalah yang biasa terjadi ketika banyak proses yang membagi sebuah resource yang hanya boleh dirubah oleh satu proses saja dalam satu waktu. Di kehidupan nyata, deadlock dapat digambarkan dalam gambar berikut.Pada gambar diatas, deadlock dianalogikan sebagai dua antrian mobil yang akan menyeberangi jembatan. Dalam kasus diatas, antrian di sebelah kiri menunggu antrian kanan untuk mengosongkan jembatan (resource), begitu juga dengan antrian kanan. Akhirnya tidak terjadi kemajuan dalam kerja dua antrian tersebut. Misal ada proses A mempunyai resource X, proses B mempunyai resource Y. Kemudian kedua proses ini dijalankan bersama, proses A memerlukan resource Y dan proses B memerlukan resource X, tetapi kedua proses tidak akan memberikan resource yang dimiliki sebelum proses dirinya sendiri selesai dilakukan. Sehingga akan terjadi tunggu-menunggu.

·     

   Contoh Deadlock :

“Dalam persimpangan jalan” Dalam kasus ini setiap mobil bergerak sesuai dengan nomor yang ditentukan, tetapi tanpa pengaturan yang benar, maka setiap mobil akan bertemu pada satu titik yang permanen atau dapat dikatakan bahwa setiap mobil tidak dapat melanjutkan perjalanan lagi atau dapat disebut juga terjadi deadlock.

Ø  Starvation.

adalah kondisi yang biasanya terjadi setelah deadlock. Proses yang kekurangan resource (karena tidak deadlock) tidak akan pernah mendapat resource yang dibutuhkan sehingga mengalami starvation (kelaparan). Namun, starvation juga bisa terjadi tanpa deadlock. Hal ini ketika terdapat kesalahan dalam sistem sehingga terjadi ketimpangan dalam pembagian resouce. Satu proses selalu mendapat resource, sedangkan proses yang lain tidak pernah mendapatkannya. Ilustrasi starvation tanpa deadlock di dunia nyata dapat dilihat di bawah ini.Pada gambar diatas, pada antrian kanan terjadi starvationkarena resource(jembatan) selalu dipakai oleh antrian kiri, dan antrian kanan tidak mendapatkan giliran.

·         Contoh Starvation :

Sambil menunggu selesainya layanan (misalnya transferdata oleh modem) pemakai dapat berinteraksi denganaplikasi lain seperti aplikasi permainan game ataumengetikkan perintah pada text editorProses tersebut harus berjalan konkuren dan tidakterjadi deadlock (hang)

Ø  Sinkronisasi.

Adalah proses pengaturan jalannya beberapa proses pada saat yang bersamaan. Tujuan utama sinkronisasi adalah menghindari terjadinya inkonsistensi data karena pengaksesan oleh beberapa proses yang berbeda (mutual exclusion) serta untuk mengatur urutan jalannya proses-proses sehingga dapat berjalan dengan lancar dan terhindar dari deadlock atau starvation.

·         Contoh Sinkronisasi :

 masalah Bounded Buffer di atas sebenarnya sudah menggambarkan terjadinya Race Condition. P1 dan P2 saling berlomba meng-update nilai counter sehingga pada suatu waktu, nilai counter-nya bisa salah.

Read More