TUGAS UNTUK PRAKTIKUM
PERANCANGAN ALGORITMA DAN ANALISIS PROGRAM
MOH.ACENG HASIRI
54410460
3IA02
LABORATORIUM TEKNIK INFORMATIKA
UNIVERSITAS GUNADARMA
2012/2013
DAFTAR ISI
A.
ALGORITMA GREEDY
A.1 Definisi
Algoritma Greedy
A.2 Contoh
Program C++ Menggunakan Algoritma Greedy
B.
ALGORITMA BRUTE FORCE
B.1
Defisi Algoritma Brute Force
B.2
Contoh Program C++ menggunakan Algoritma Brute
Force
C.
ALGORITMA DYNAMIC PROGRAMING
C.1
Defini Algoritma Dynamic Programing
C.2
Contoh Program C++ Menggunakan Algoritma Dynamic
Programing
D.
ALGORITMA KRUSKAL
D.1 Definisi
Algoritma Kruskal
D.2 Contoh
Program C++ Menggunakan Algoritma Kruskal
E.
ALGORITMA DJIKSTRA
E.1
Definisi Algoritma Djikstra
E.2
Contoh Program C++ Menggunakan Algoritma
Djikstra
A.
ALGORITMA GREEDY
A.1 Definisi Algoritma Greedy
Algoritma greedy adalah algoritma yang memecahkan masalah
langkah demi langkah dengan memakai kemungkinan yang ada. Algoritma Greedy membentuk solusi langkah per
langkah, terdapat banyak pilihan yang perlu di eksplorasi pada setiap langkah
solusi, karenanya pada setiap langkah harus dibuat keputusan yang terbaik dalam
menentukan pilihan. keputusan yang telah di ambil pada suatu langkah tidak
dapat diubah lagi pada langkah selanjutnya.dan merupakan salah satu metode
dalam optimasi.
Pendekatan
yang digunakan di dalam algoritma greedy adalah membuat
pilihan yang “tampaknya” memberikan perolehan terbaik, yaitu dengan membuat
pilihan optimum lokal (local optimum) pada setiap
langkah dengan harapan bahwa sisanya mengarah ke solusi optimum
global (global optimum).
Algoritma greedy adalah
algoritma yang memecahkan masalah langkah per langkah, pada setiap langkah:
1. mengambil pilihan yang terbaik yang
dapat diperoleh pada saat itu tanpa memperhatikan konsekuensi ke depan (prinsip
“take what you can get now!”)
2. berharap bahwa dengan memilih
optimum lokal pada setiap langkah akan berakhir dengan optimum global.
A.2 Contoh Program C++ Menggunakan Algoritma Greedy
Program Penukaran Koin
#include
#include
#define size 99
void sort(int[],
int);
main(){
clrscr ();
int
x[size],i,n,uang,hasil[size];
printf("Banyak
Koin : ");
scanf("%d",
&n);
printf("\nMasukkan
Jenis Koin : ");
printf("\n");
for(i=1;i<=n;i++){
scanf("%d",
&x[i]);
}
sort(x,n);
printf("\nKoin
yang tersedia :");
printf("\n");
for(i=1;i<=n;i++){
printf("%d",x[i]);
printf("\n");
}
printf("\n");
printf("\nMasukkan
nilai yang dipecah :");
scanf("%d",
&uang);
printf("\n");
for(i=1;i<=n;i++){
hasil[i]=uang/x[i];
uang=uang%x[i];
}
for(i=1;i<=n;i++){
printf("keping
%d",x[i]);
printf("-an
sebanyak : %d",hasil[i]);
printf("\n
\n");
}
getch();
return 0;
}
void sort (int
a[],int siz){
int pass, hold, j;
for (pass=1; pass
hold=a[j+1];
a[j+1]=a[j+2];
a[j+2]=hold;}}}
B.
ALGORITMA
BRUTE FORCE
B.1 Definisi Algoritma Brute Force
Algoritma Brute Force
adalah sebuah pendekatan yang lempang (straightforward) untuk memecahkan suatu
masalah, biasanya didasarkan pada pernyataan masalah (problem statement) dan
definisi konsep yang dilibatkan.
Cara kerja algoritma
Brute Force
1.
Enumerasi
(list) setiap solusi yang mungkin dengan cara yang sistematis.
2.
Evaluasi
setiap kemungkinan solusi “satu per satu” dan simpan solusi terbaik yang
ditemukan sampai sejauh ini.
3.
Bila
pencarian solusi berakhir, umumkan solusi terbaik
Karakteristik Algoritma Brute Force
1. Algoritma brute force
sebenarnya bukanlah algoritma yang “cerdas” dan mangkus(efisien), karena ia
membutuhkan jumlah langkah yang besar/banyak dalam penyelesaiannya dan tentu
saja membutuhkan waktu yang berbanding lurus dengan jumlah langkah
penyelesaiannya. Kadang-kadang algoritma brute force disebut juga
algoritma naif (naïve algorithm).
2. Algoritma brute force
seringkali merupakan pilihan yang kurang disukai karena ketidakmangkusannya
itu, tapi kalau mencari pola2 dasar, keteraturan, atau trik-trik khusus,
biasanya dapat membantu membantu untuk menemukan algoritma yang lebih cerdas
dan lebih mangkus lagi.
3. Untuk persoalan2 yang kecil,
kesederhanaan brute force lebih diperhitungkan daripada ketidakmangkusannya.
Algoritma brute force sering digunakan sebagai basis bila membandingkan
beberapa alternatif algoritma yang mangkus.
4.
Meskipun brute force bukan merupakan teknik
pemecahan masalah yang mangkus, namun teknik brute force dapat
diterapkan pada sebagian besar persoalan. Bayangkan..,sangat sulit menemukan
masalah yang tidak dapat dipecahkan dengan teknik brute force, tapi ada
masalah yang hanya dapat dipecahkan secara brute force
B.2 Contoh Program C++ Menggunakan
Algoritma Brute Force
Program mencari
Bilangan Prima, Sorting Bilangan, dan Perkalian Matriks
#include
#include
#include
void prima (),bsort(),kalimatriks();
main()
{
start :
int x;
clrscr();
printf ("\n \t Algoritma Brute Force \n");
printf ("\n ==========================================");
printf ("\n \t 1. Pencarian Bilangan Prima");
printf ("\n \t 2. Sorting Bilangan");
printf ("\n \t 3. Perkalian Matriks");
printf ("\n \t 4. Exit ");
printf ("\n ========================================= \n");
printf ("\n Masukkan Pilihan (1-4) : ");
scanf ("%d",&x);
switch(x)
{
case 1 : prima ();
goto start;
case 2 : bsort();
goto start;
case 3 : kalimatriks();
goto start;
case 4 : return 0;
default : clrscr();
printf("\n \n \n \n \n \n \t \t \t Anda Salah memasukkan Input");
printf("\n \t \t Program Akan Direstart Setelah Anda Menekan Tombol Enter");
getch();
goto start;
}
}
void prima ()
{
int bil,j;
clrscr();
printf ("\t \t \t Pencarian Bilangan Prima \n \n \n");
printf ("Masukkan Data Yang Ingin Diinput: ");
scanf("%d",&bil);
for(j=2;j<=bil;j++)
{
if ((j%2>0)&&(j%3>0)&&(j%5>0)&&(j%7>0) || (j==2)||(j==3)||(j==5)||(j==7))
printf ("%i ",j);
}
getch();
}
void bsort()
{
int i,j,temp,n,bil[100];
clrscr();
printf ("\t \t \t Sorting Bilangan \n \n \n" );
printf ("Masukkan jumlah bilangan: " );
scanf ("%d",&n);
for(i=0;i
{
printf ("Bilangan ke-%d \t: ",i+1);
scanf ("%d",&bil[i]);
}
printf ("\n");
for(i=0;i
{
for(j=n-1;j>i;j--)
{
if (bil[i] > bil[j])
{
temp = bil[i];
bil[i] = bil[j];
bil[j] = temp;
}
}
}
printf ("Sorting:");
for(i=0;i
{
printf ("%d",bil[i]);
if (i!= n-1)
{
printf (",");
}
}
getch();
}
void kalimatriks()
{
int i,j,k,temp,ordo,ma[10][10],mb[10][10],mc[10][10];
clrscr();
printf ("\t \t \t Perkalian Matriks \n \n \n");
printf ("Masukkan Ordo Matriks: ");
scanf ("%d", &ordo);
printf ("Matriks A: ");
for(i=0;i
{
for(j=0;j
{
gotoxy((j+1)*5,i+6);
scanf ("%d", &ma[i][j]);
}
}
printf ("\n");
printf ("Matriks B: ");
for(i=0;i
{
for(j=0;j
{
gotoxy((j+1)*5,i+8+ordo);
scanf ("%d", &mb[i][j]);
}
}
for(i=0;i
{
for(j=0;j
{
temp = 0;
for(k=0;k
{
temp += ma[i][k] * mb[k][j];
}
mc[i][j] = temp;
}
}
printf ("\n \n");
printf ("Hasil Matriks A * Matriks B: ");
for(i=0;i
{
for(j=0;j
{
gotoxy((j+1)*5,i+11+ordo*2);
printf ("%d",mc[i][j]);
}
}
getch();
}
#include
#include
void prima (),bsort(),kalimatriks();
main()
{
start :
int x;
clrscr();
printf ("\n \t Algoritma Brute Force \n");
printf ("\n ==========================================");
printf ("\n \t 1. Pencarian Bilangan Prima");
printf ("\n \t 2. Sorting Bilangan");
printf ("\n \t 3. Perkalian Matriks");
printf ("\n \t 4. Exit ");
printf ("\n ========================================= \n");
printf ("\n Masukkan Pilihan (1-4) : ");
scanf ("%d",&x);
switch(x)
{
case 1 : prima ();
goto start;
case 2 : bsort();
goto start;
case 3 : kalimatriks();
goto start;
case 4 : return 0;
default : clrscr();
printf("\n \n \n \n \n \n \t \t \t Anda Salah memasukkan Input");
printf("\n \t \t Program Akan Direstart Setelah Anda Menekan Tombol Enter");
getch();
goto start;
}
}
void prima ()
{
int bil,j;
clrscr();
printf ("\t \t \t Pencarian Bilangan Prima \n \n \n");
printf ("Masukkan Data Yang Ingin Diinput: ");
scanf("%d",&bil);
for(j=2;j<=bil;j++)
{
if ((j%2>0)&&(j%3>0)&&(j%5>0)&&(j%7>0) || (j==2)||(j==3)||(j==5)||(j==7))
printf ("%i ",j);
}
getch();
}
void bsort()
{
int i,j,temp,n,bil[100];
clrscr();
printf ("\t \t \t Sorting Bilangan \n \n \n" );
printf ("Masukkan jumlah bilangan: " );
scanf ("%d",&n);
for(i=0;i
{
printf ("Bilangan ke-%d \t: ",i+1);
scanf ("%d",&bil[i]);
}
printf ("\n");
for(i=0;i
{
for(j=n-1;j>i;j--)
{
if (bil[i] > bil[j])
{
temp = bil[i];
bil[i] = bil[j];
bil[j] = temp;
}
}
}
printf ("Sorting:");
for(i=0;i
{
printf ("%d",bil[i]);
if (i!= n-1)
{
printf (",");
}
}
getch();
}
void kalimatriks()
{
int i,j,k,temp,ordo,ma[10][10],mb[10][10],mc[10][10];
clrscr();
printf ("\t \t \t Perkalian Matriks \n \n \n");
printf ("Masukkan Ordo Matriks: ");
scanf ("%d", &ordo);
printf ("Matriks A: ");
for(i=0;i
{
for(j=0;j
{
gotoxy((j+1)*5,i+6);
scanf ("%d", &ma[i][j]);
}
}
printf ("\n");
printf ("Matriks B: ");
for(i=0;i
{
for(j=0;j
{
gotoxy((j+1)*5,i+8+ordo);
scanf ("%d", &mb[i][j]);
}
}
for(i=0;i
{
for(j=0;j
{
temp = 0;
for(k=0;k
{
temp += ma[i][k] * mb[k][j];
}
mc[i][j] = temp;
}
}
printf ("\n \n");
printf ("Hasil Matriks A * Matriks B: ");
for(i=0;i
{
for(j=0;j
{
gotoxy((j+1)*5,i+11+ordo*2);
printf ("%d",mc[i][j]);
}
}
getch();
}
C.
ALGORITMA DYNAMIC
PROGRAMING
C.1 Definisi Algoritma Dynamic
Programing
Program dinamis
(Dynamic programing) merupakan metode pemecahan maslah dengan cara menguraikan
solusi menjadi sekumpulan langkah (step) atau tahapan (stage) sedemikian hingga
solusi dari persoalan dapat dipandang dari serangkaian keputusan yang saling
berkaitan.
Algoritma pemrograman
dinamik dapat dibagi kedalam 4 langkah:
1.
Menentukan
struktur dari suatu penyelesaian optimal.
2.
Mendefinisikan
secara rekursif nilai dari penyelesaian optimal.
3.
Menghitung
nilai dari penyelesaian optimal dengan cara bottom-up. Langkah1-3 ini merupakan
basis dari penyelesaian pemrograman dinamik. Langkah 4 dapat diabaikan apabila
hanya diperlukan sebuah solusi optimal.
4.
Membentuk
suatu penyelesaian optimal dari informasi yang didapat.
C.2 Contoh Program C++ Menggunakan Algoritma Dynamic programing
Program mencari jalan
terpendek pada Graph
#include
#include
using namespace std;
int min(int a,int b);
int cost[10][10],a[10][10],i,j,k,c;
main()
{
int n,m;
cout
<<"enter no of vertices";
cin >>
n;
cout
<<"enter no od edges";
cin >>
m;
cout<<"enter the\nEDGE Cost\n";
for(k=1;k<=m;k++)
{
cin>>i>>j>>c;
a[i][j]=cost[i][j]=c;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(a[i][j]== 0 && i !=j)
a[i][j]=31999;
}
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
cout <<"Resultant adj matrix\n";
for(i=1;i<=n;i++)
{
for( j=1;j<=n;j++)
{
if(a[i][j]
!=31999)
cout <<
a[i][j] <<" ";
}
cout <<"\n";
}
getch();
}
int min(int a,int b)
{
if(a
return a;
else
return b;
}
D.
ALGORITMA KRUSKAL
D.1 Definisi Algoritma Kruskal
Algoritma Kruskal
adalah algoritma untuk mencari pohon merentang minimum secara langsung
didasarkan pada algoritma MST (Minimum Spanning Tree) umum. Pada
algoritma Kruskal sisi-sisi di dalam graf diurut terlebih dahulu berdasarkan
bobotnya dari kecil ke besar. Sisi yang dimasukkan ke dalam himpunan T adalah
sisi graf G sedemikian sehingga T adalah pohon. Pada keadaan awal, sisi-sisi
sudah diurut berdasarkan bobot membentuk hutan (forest). Hutan tersebut
dinamakan hutan merentang (spanning forest). Sisi dari graf G
ditambahkan ke T jika tidak membentuk sirkuit di T.
D.2 Contoh Program C++ Menggunakan Algoritma Kruskal
Mencari minimal
spaning tree
#include
#include
#include
using
namespace std;
class
kruskal
{
private:
int n; //no of nodes
int noe; //no edges in the graph
int graph_edge[100][4];
int tree[10][10];
int sets[100][10];
int top[100];
public:
int read_graph();
void initialize_span_t();
void sort_edges();
void algorithm();
int find_node(int );
void print_min_span_t();
};
int
kruskal::read_graph()
{
//cout<<"Program
ini Mengimplementasikan Algoritma Kruskal\n";
cout<<"Banyak
titik graph : ";
cin>>n;
noe=0;
cout<<"\nJarak
antar tiap titik:\n";
for(int
i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
cout<<"("<
int w;
cin>>w;
if(w!=0)
{
noe++;
graph_edge[noe][1]=i;
graph_edge[noe][2]=j;
graph_edge[noe][3]=w;
}
}
}
}
void
kruskal::sort_edges()
{
/**** Sort
the edges using bubble sort in increasing order**************/
for(int
i=1;i<=noe-1;i++)
{
for(int j=1;j<=noe-i;j++)
{
if(graph_edge[j][3]>graph_edge[j+1][3])
{
int t=graph_edge[j][1];
graph_edge[j][1]=graph_edge[j+1][1];
graph_edge[j+1][1]=t;
t=graph_edge[j][2];
graph_edge[j][2]=graph_edge[j+1][2];
graph_edge[j+1][2]=t;
t=graph_edge[j][3];
graph_edge[j][3]=graph_edge[j+1][3];
graph_edge[j+1][3]=t;
}
}
}
cout<<"\n\nSetelah
Jarak diurutkan adalah ::\n";
for(int
i=1;i<=noe;i++)
cout<<"("<<
graph_edge[i][1]
<<"
, "<
<<"
) = "<
}
void
kruskal::algorithm()
{
for(int i=1;i<=n;i++)
{
sets[i][1]=i;
top[i]=1;
}
cout<<"\nRentang
Yang di Pakai\n\n";
for(int i=1;i<=noe;i++)
{
int p1=find_node(graph_edge[i][1]);
int p2=find_node(graph_edge[i][2]);
if(p1!=p2)
{
cout<<"Rentang yg masuk ke pohon
::"
<<" <
"<
<
"<
tree[graph_edge[i][1]][graph_edge[i][2]]=graph_edge[i][3];
tree[graph_edge[i][2]][graph_edge[i][1]]=graph_edge[i][3];
// Mix the two sets
for(int j=1;j<=top[p2];j++)
{
top[p1]++;
sets[p1][top[p1]]=sets[p2][j];
}
top[p2]=0;
}
else
{
cout<<"Jika "
<<" < "<
<
"<<"di masukkan, maka terbentuk siklus. jadi di
hapus\n\n";
}
}
}
int
kruskal::find_node(int n)
{
for(int i=1;i<=noe;i++)
{
for(int j=1;j<=top[i];j++)
{
if(n==sets[i][j])
return i;
}
}
return -1;
}
int main(int
argc, char *argv[])
{
kruskal obj;
obj.read_graph();
obj.sort_edges();
obj.algorithm();
system("PAUSE");
return EXIT_SUCCESS;
}
E.
ALGORITMA
DJIKSTRA
E.1 Definisi Algoritma Djikstra
Bobot pada sisi bisa berarti jarak.waktu ataupun bobot lainnya. Jalur terpendek dalam graph adalah jumlah total minimum bobot dari sisi-sisi yang menghubungkan simpul sumber dengan simpul tujuan. Misalnya, bila vertices dari sebuah graf melambangkan kota-kota dan bobot sisi melambangkan jarak antara kota-kota tersebut, maka algoritma Dijkstra dapat digunakan untuk menemukan jarak terpendek antara dua kota.
Input algoritma ini adalah sebuah graf berarah yang berbobot G dan sebuah sumber vertex s dalam G dan V adalah himpunan semua vertices dalam graph G.
Setiap sisi dari graf ini adalah pasangan vertices (u,v) yang melambangkan hubungan dari vertex u ke vertex v. Himpunan semua tepi disebut E.
Bobot dari semua sisi dihitung dengan fungsi
w: E → [0, ∞)
jadi w(u,v) adalah jarak tak-negatif dari vertex u ke vertex v.
Ongkos dari sebuah sisi dapat dianggap sebagai jarak antara dua vertex, yaitu jumlah jarak semua sisi dalam jalur tersebut. Untuk sepasang vertex s dan t dalam V, algoritma ini menghitung jarak terpendek dari s ke t.
E.2 Contoh Program C++ Menggunakan Algoritma Djikstra
Program mencari biaya
perjalanan pada graph
#include
#include
#define MAXNODES 50
#define MAX1 150
#define INFINITY 5000
using namespace std;
int weight[MAXNODES][MAXNODES],i,j,distance[MAXNODES],visit[MAXNODES];
int precede[MAXNODES],final=0;
int path[MAX1];
int smalldist,newdist,k,s,d,current,n,distcurr;
void Display_Result()
{
i=d;
path[final]=d;
final++;
while(precede[i]!=s)
{
j=precede[i];
i=j;
path[final]=i;
final++;
}
path[final]=s;
printf("\nThe shortest path followed is :\n\n");
for(i=final;i>0;i--)
printf("\t\t(%d -> %d) with cost = %d\n\n",path[i],path[i-1],weight[path[i]][path[i-1]]);
printf("\nFor total cost = %d",distance[d]);
}
main()
{
printf("\nEnter the number of nodes(Less than 50)in the matrix : ");
scanf("%d",&n);
printf("\nEnter the cost matrix :\n\n");
for(i=0;i
for(j=0;j
scanf("%d",&weight[i][j]);
printf("\nEnter the source node (0 to %d) : ",n-1);
scanf("%d",&s);
printf("\nEnter the destination node (0 to %d) : ",n-1);
scanf("%d",&d);
for(i=0;i
{
distance[i]=INFINITY;
precede[i]=INFINITY;
}
distance[s]=0;
current=s;
visit[current]=1;
while(current!=d)
{
distcurr=distance[current];
smalldist=INFINITY;
for(i=0;i
if(visit[i]==0)
{
newdist=distcurr+weight[current][i];
if(newdist
{
distance[i]=newdist;
precede[i]=current;
}
if(distance[i]
{
smalldist=distance[i];
k=i;
}
}
current=k;
visit[current]=1;
}
Display_Result();
getch();
}
#include
#define MAXNODES 50
#define MAX1 150
#define INFINITY 5000
using namespace std;
int weight[MAXNODES][MAXNODES],i,j,distance[MAXNODES],visit[MAXNODES];
int precede[MAXNODES],final=0;
int path[MAX1];
int smalldist,newdist,k,s,d,current,n,distcurr;
void Display_Result()
{
i=d;
path[final]=d;
final++;
while(precede[i]!=s)
{
j=precede[i];
i=j;
path[final]=i;
final++;
}
path[final]=s;
printf("\nThe shortest path followed is :\n\n");
for(i=final;i>0;i--)
printf("\t\t(%d -> %d) with cost = %d\n\n",path[i],path[i-1],weight[path[i]][path[i-1]]);
printf("\nFor total cost = %d",distance[d]);
}
main()
{
printf("\nEnter the number of nodes(Less than 50)in the matrix : ");
scanf("%d",&n);
printf("\nEnter the cost matrix :\n\n");
for(i=0;i
printf("\nEnter the source node (0 to %d) : ",n-1);
scanf("%d",&s);
printf("\nEnter the destination node (0 to %d) : ",n-1);
scanf("%d",&d);
for(i=0;i
distance[i]=INFINITY;
precede[i]=INFINITY;
}
distance[s]=0;
current=s;
visit[current]=1;
while(current!=d)
{
distcurr=distance[current];
smalldist=INFINITY;
for(i=0;i
{
newdist=distcurr+weight[current][i];
if(newdist
distance[i]=newdist;
precede[i]=current;
}
if(distance[i]
smalldist=distance[i];
k=i;
}
}
current=k;
visit[current]=1;
}
Display_Result();
getch();
}
DAFTAR PUSTAKA
1.
A
Hypercube Algorithm for the 0/1
KnapsackProblem.
http://www.cise.ufl.edu/~sahni/paper
s/knap.pdf.
2.
Dynamic
Programming Examples:
Integer
Knapsack.
http://cgm.cs.mcgill.ca/~msuder/courses/
360/lectures/integer-knapsack.html.
4.
http://
repository.upnyk.ac.id
