Penjadwalan Ujian pada metode greedy


Penjadwalan Ujian

Kali ini kita akan mencoba memecahkan masalah penjadwalan dengan cara melakukan pewarnaan pada sebuah graf.Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek. Representasi visual dari graf adalah dengan menyatakan objek dengan simpul, noktah, bulatan, titik, atau vertex, sedangkan hubungan antara objek dinyatakan dengan garis , edge atau ruas.

Pewarnaan graf adalah proses pelabelan setiap simpul dalam graf dengan label tertentu (warna) sehingga tidak ada dua simpul bertetangga yang memiliki warna sama. Warna yang kita gunakan untuk mewarnai objek diusahakan seminimal mungkin. Jumlah warna minimum yang dapat digunakan untuk mewarnai simpul disebut bilangan kromatik

Tabel berikut adalah contoh penjadwalan kuliah dalam graf:

Tabel 1 Contoh tabel penjadwalan kuliah 
 
Gambar 1
Advertisements

shortest path problem


TRAVELLING SALESMAN
Untuk menentukan waktu perjalanan seorang salesman seminimal mungkin.
Permasalahan:
Setiap minggu sekali, seorang petugas kantor telepon berkeliling untuk mengumpulkan coin-coin pada telepon umum yang dipasang diberbagai tempat. Berangkat dari kantornya, ia mendatangi satu demi satu telepon umum tersebut dan akhirnya kembali ke kantor lagi. Masalahnya ia menginginkan suatu rute perjalanan dengan waktu minimal.

modelgraf

Matrix



NOTASI MATRIKS
Bentuk umum matriks: Matriks adalah susunan segi empat siku-siku dari bilangan yang diatur berdasarkan baris dan kolom/lajur. Bilangan-bilangan dalam susunan tersebut dinamakan entri dalam matriks atau disebut juga elemen atau unsur.

Suatu matriks dinyatakan dengan huruf kapital  A , B , C ,. . . dan seterusnya, sedangkan unsur matriks dinyatakan dengan huruf kecil a, b , c , . . ., dan seterusnya.

contoh :

Matriks A mempunyai dua baris dan dua kolom. Oleh karena itu kita katakan bahwa matriks A berordo 2 X 2 ditulis A2x2  atau (a22).

JENIS-JENIS MATRIKS
Matriks dibedakan berdasarkan berbagai susunan entri dan bilangan pada entrinya. Sehingga matriks dibedakan sebagai berikut:
1. Matriks nol
Matriks nol didefinisikan sebagai matriks yang setiap entri atau elemennya adalah bilangan nol.

Continue reading

Iterasi dan rekursif


Iterasi

pada iterasi kita menggunakan perulangan untuk mencari hasilnya. perhatikan coding berikut.

#include <stdio.h>
#include <conio.h>
#include <iostream>
using namespace std;

int main () {
printf(“Program Iterasi Perpangkatan \n\n”);
int x,a,hasil;

printf (“masukkan nilai x = “); scanf(“%d”,&x);
printf(“masukkan nilai a = “); scanf(“%d”, &a);

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

if(i==0){

hasil= x*x;
}else{

hasil=hasil * x;

}

cout<<“hasil pemangkatan “<<x <<“^” <<a <<” = ” <<hasil;

getch( );

pada coding yang di beri warna merah merupakan iterasi/perulangan yang beefungsi untuk mencari nailai pemangkatan. dimana x merupakan nilai variabel dan a merupakan pangkatnya. Xa

nah kemudian diatas dapat kita lihat untuk menampilkan text menggunakan printf dan meminta input dengan perintah scanf. yang mana anda juga bisa menggunakan fungsi cout<< dan cin>>. pada printf dan scanf (agak ribet) mesti mengunakan code seperti %d setiap ada variabel yang ingin digunakan contoh scanf(“%d”,&x);

flowchart perpangkatan

Rekursif

pada rekursif kita menggunakan fungsi yang memanggil dirinya sendiri untuk mencari hasilnya sampai memenuhi kondisi. perhatikan coding berikut.

#include <stdio.h>
#include <conio.h>
#include <iostream>
using namespace std;

int pangkat (int j, int k) { //membuat function/fungsi pangkat
int hasil;
if (k==0) { hasil=1; }
else {
hasil =j*pangkat(j,k-1);
}
return(hasil);
}

int main(){ //program utama
printf(“Program Iterasi Perpangkatan \n\n”);
int x,a,hasil;

printf (“masukkan nilai x = “); scanf(“%d”,&x);
printf(“masukkan nilai a = “); scanf(“%d”, &a);

cout<<“hasil pemangkatan “<<x <<“^” <<a <<” = ” <<pangkat(x,a);
}

Yang paling penting adalah fungsi pangkat yang diwarnai merah
Fungsi ini digunakan mencari hasil pemangkatan,
penjelasan coding

int hasil; (digunakan untuk menampung hasil dari pemangkatan)

if (k==0) { hasil=1; } jika k =0 maka hasilnya pemangkatannya 1, j0 =1

else {
hasil =j*pangkat(j,k-1); }
jika k =bukan 0 misalnya 3 (33) maka hasilnya 3*pangkat(3,2) nah nilai k nya masih 2 (belum 0) maka akan di lakukan pemanggilan fungsi pangkat sampai nilai k nya 0
jadi nanti bentuk proses pencariannya begini

pangkat(3,3) = 3*pangkat(3,2)= 3*3*pangkat(3,1)= 3*3*3 pangkat(3,0)= 3*3*3*1

Dan terakhir
return(hasil); untuh menampilkan hasil dari pemangkatan yang di letakkan pada variabel hasil.

Kekurangan perulangan rekursif :

  • Tidak bisa melakukan nested loop atau looping bersarang.
  • Biasanya membuat fungsi sulit untuk dipahami, hanya cocok untuk persoalan tertentu saja
  • Memerlukan stack yang lebih besar, sebab setiap kali fungsi dipanggil, variabel lokal dan parameter formal akan ditempatkan ke stack dan ada kalanya akan menyebabkan stack tak cukup lagi (Stack Overum).
  • Proses agak berbelit-belit karena terdapat pemangilan fungsi yang berulang-ulang dan pemanggilan data yang ditumpuk.

contoh soal :

Mr.X membuat 2 macam boneka A dan B. Boneka A memerlukan bahan 10 blok B1 dan 2 blok B2, sedangkan boneka B memerlukan bahan 5 blok B1 dan 6 blok B2. Berapa jumlah boneka yang dapat dihasilkan bila tersedia 80 blok bahan B1 dan 36 blok bahan B2. (dimana iterasinya)
Variabel yang dicari adalah jumlah boneka, anggap:
x1 adalah jumlah boneka A
x2 adalah jumlahboneka B