Logika Algoritma

Pewarnaan (Coloring) – Penjadwalan Ujian

Posted on Updated on

Sumber: http://bloglogika.blogspot.com/2011/01/penjadwalan-ujian.html

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


Pada tabel diatas 6 kolom yang dilambangkan dengan huruf menunjukan nama mata kuliah, sedangkan 8 baris yang ditunjukan dengan angka menunjukan mahasiswa, sedangkan angka 1 menandakan mata kuliah yang diambil, 0 berarti mata kuliah yg tdk diambil. 

Pada tabel diatas menunjukan adanya mahasiswa yang mengambil 2 mata kuliah sekaligus.
Maka berdasarkan tabel diatas, tim pembuat jadwal harus membuat jadwal, dimana siswa harus dapat mengikuti semua ujian dari mata kuliah yang diambil, berarti mata kuliah yang diambil bersamaan oleh seorang mahasiswa tidak boleh dijadwalkan pada waktu yang sama.
Maka untuk menyelesaikan permasalahan tersebut, hal yang dilakukan adalah
  1. Menggambarkan Simpul yang menunjukan mata kuliah
  2. Membuat ruas atau garis penghubung menyatakan ada mahasiswa yang memilih kedua mata kuliah itu.
  3. Memilih simpul yang berwarna sama, simpul yang berwarna sama menunjukan tidak ada mahasiswa yang mengambil mata kuliah tersebut secara bersamaan, berarti boleh dijadwalkan pada waktu yang sama
untuk lebih jelasnya lihat gambar berikut

Gambar 2
Berdasarkan graf tersebut kita menyimpulkan, bahwa apabila terdapat dua buah simpul dihubungkan oleh sisi atau ruas, maka ujian kedua mata kuliah itu tidak dapat dibuat pada waktu yang sama. Maka untuk mempermudah kita bisa memberi warna pada masing-masing simpul, dimana warna yang berbeda dapat diberikan pada simpul graf yang menunjukkan bahwa waktu ujiannya berbeda, warna yang digunakan harus seminimal mungkin dengan ketentuan simpul yang berdampingan atau bertetangga tidak boleh berwarna sama, berikut cara pemberian warnanya.
Gambar 3
M = Merah
P = Putih
H = Hijau
Dari gambar diatas kita memulai memberikan pewarnaan pada simpul F dengan warna merah, kemudian kita memberi warna pada simpul A dengan warna putih, selanjutnya kita memberi warna simpul E dengan warna merah, dilanjutkan ke simpul B kita beri warna Putih, kemudian kita lanjutkan ke simpul D, kembali kita beri warna Merah, terakhir kita mewarnai simpul C dengan warna hijau, mengapa simpul C berwarna hijau, ini dikarenakan ketentuan yang telah kita bahas diatas, bahwa setiap simpul yang bertetangga tidak boleh berwarna sama, kita lihat simpul C bertetangga dengan simpul B yang berwarna putih, dan simpul D yang berwarna merah, maka simpul C harus diberi warna selain warna Merah dan Putih.
Kemudian kita kelompokan simpul yang mempunyai warna sama, simpul dengan warna sama berarti bisa dijadwalkan dalam waktu yang bersamaan karena tidak ada mahasiswa yang mengambil mata kuliah tersebut secara bersamaan, dari gambar 3 diperoleh hasil:
  1. Simpul merah = F, E, D
  2. Simpul Putih = A, B
  3. Simpul hijau = C
Catatan:
Untuk posisi peletakan Simpul Bisa Bebas
Awal pemberian warna boleh bebas
Warna yang digunakan Bebas
Awal pemberian warna mempengaruhi susunan Jadwal

Pewarnaan (Coloring) – Pengaturan Warna Pada Lampu Lalu Lintas

Posted on Updated on

Sumber: http://bloglogika.blogspot.com/2011/02/pengaturan-warna-pada-lampu-lalu-lintas.html

Pewarnaan (Coloring)

Pewarnaan yang kita bahas kali ini adalah sebuah cara yang digunakan untuk menyelesaiakan proses panjadwalan. Dimana dalam pewarnaan ini akan digambarkan dengan graph yang terdiri atas simpul, dan ruas

Dalam kehidupan sehari-hari sering kali kita dipusingkan oleh rumitnya penjadwalan, misalnya jika kita harus membuat jadwal ujian dimana ada beberapa mahasiswa yang mengikuti beberapa mata kuliah, tentunya agar mahasiswa tersebut dapat mengikuti  semua ujian, maka mata kuliah yang diambil secara bersamaan oleh satu siswa tersebut tidak boleh dijadwalkan pada hari dan jam yang sama. Atau misalnya kita mendapatkan proyek untuk membuat  lampu lalulintas di sebuah perlimaan, maka kita harus mengatur nyala lampu merah dan hijau agar tidak terjadi tabrakan. Saat ini kita akan belajar bersama salah satu metode untuk mengatasi permasalahan tersebut dengan metode pewarnaan (Coloring).

 

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

.
beberapa contoh permasalahan yang bisa diselesaikan dengan pewarnaan adalah

Pengaturan Warna Pada Lampu Lalu Lintas

Pada tulisan kali ini, kita akan mencoba menyelesaikan permasalahan pada pembuatan lampu lalu lintas pada sebuah jalan simpang 5, kita akan mencoba menentukan jalur mana yg bisa berjalan dengan memberi lampu hijau, dan memberi lampu merah agar kendaraan pada lintasan yg lain berhenti, tujuannya adalah agar tidak terjadi tabrakan
mari kita lihat contoh gambarberikut

Gambar 1

Dari gambar diatas dapat kita peroleh informasi, bahwa jalur yang boleh melintas adalah dari A ke B, A ke C, A ke D, B ke C, B ke D, E ke B, E ke C, dan E ke D.

Setelah kita tahu jalur yang boleh dilewati kita akan menempuh langkah sebagai berikut

1. Membuat simpul sebagai simbol dari semua jalur yag diperboleh. letak masing-masing simpul bebas. lihat gambar berikut:

Gambar 2


2. Menentukan ruas untuk menghubungkan 2 simpul yang saling melintas atau bersebrangan, pada gambar 1 diatas terlihat bahwa jalur AB, dan  BD, saling berseberangan, maka kita hubungkan simpul AB dam BD dengan garis yang disebut ruas, dan kita akan memberikan ruas pada semua jalur yang bersebrangan, mari kita lihat gambar 3 berikut

Gambar 3

3. pada gambar 3 kita telah menghubungkan semua jalur yang saling melintas, langkah berikutnya adalah memberikan warna pada masing-masing simpul yang terhubung dengan ruas atau garis, ketentuan pemberian warnanya adalah

  • Gunakan Warna seminimal mungkin
  • Simpul yang berdampingan atau /Terhubung langsung dengan ruas, tidak boleh berwarna sama
  • Berikan warna yang sama pada simpul yang tidak terhubung secara langsung
  • Simpul yang tidak terhubung dengan ruas atau simpul bebas, berarti lintasan tersebut boleh berlaku lampu hijau terus.
  • Awal pewarnaan Bebas
Gambar 4

Dari Gambar 4 diatas, semua simpul telah diwarnai, dari gambar ersebut simpul EC berwarna kuning sendiri, hal ini dikarenakan simpul EC terhubung secara langsung dengan simpul AD yang berwarna merah, dan terhubung dengan simpul BD yang berwarna coklat, jadi kita harus memberi warna selain coklat dan merah, dalam hal ini kita pilih warna kuning,  sementara simpul ED, AB, BC , jadi ke 3 simpul tersebut kita beri warna yang sama, selain merah, coklat dan kuning tentunya, pada contoh diatas kita beri warna hijau. Simpul ED, AB, BC adalah simpul bebas (simpul yang tidak terhubung dengan simpul lain) yang berarti jalur tersebut tidak ada jalur yang saling melintas artinya ketiga ruas bebas itu bisa berlaku lampu hijau terus.

4. langkah berikutnya adalah mengelompokan simpul berdasarkan warna
Merah => AC, AD
Coklat => BD, EB
Kuning => EC
Hijau    => ED, AB, BC

Dari langkah-langkah diatas kita bisa mendapatkan 3 fase pola lampu lalu lintas sebagai berikut

Hijau AC, AD, ED, AB, BC
Merah BD, EB, EC
Hijau BD, EB, ED, AB, BC
Merah AC,AD, EC
Hijau EC, ED, AB, BC
Merah AC,AD, BD, EB

Latihan Soal Metode Greedy

Posted on Updated on

Untuk Mahasiswa kelas 12.1E.04 Tolong kerjakan soal-soal berikut ini kemudian jawabannya di upload di website kelompok. Untuk mengerjakan soalnya perhatikan jika NIM nya.

greedy1 greedy2 greedy3 greedy4 greedy5 greedy6

 

 

Contoh Program C++ Searching

Posted on

Sumber:

http://sokhi95.blogspot.com/2013/05/contoh-program-c-searching.html

Program : C++
Specific  : Searching

========================================

#include <stdio.h>
#include <iostream.h>
#include <iomanip.h>
#include <conio.h>
main()
{
char npm[500][10];
char nm[500][20];
char kls[500][3];
char npm_cari [10];
int ketemu=0, i=0, jd=0, no=0;
char adm=’Y’;

while (adm==’Y’)
{
clrscr();
jd++;
gotoxy (10,5) ; cout <<“Input Data Mahasiswa”;
gotoxy (10,7) ; cout <<“Data Mahasiswa ke-” << (i+1);
gotoxy (10,8) ; cout <<“NPM   = “;
gotoxy (10,9) ; cout <<“Nama  = “;
gotoxy (10,10); cout <<“Kelas = “;
gotoxy (10,12); cout <<“Ada Data Mahasiswa Lainnya [Y/T] = “;
gotoxy (18,8); gets (npm[i]);
gotoxy (18,9); gets (nm[i]);
gotoxy (18,10); gets (kls[i]);
i++;
gotoxy (45,12); cin >> adm;
}
// Menampilkan seluruh data yg diinputkan
clrscr();
gotoxy (10,2); cout << “Daftar Mahasiswa TI Angkatan 2012”;
gotoxy (2,4); cout << “————————————————“;
gotoxy (2,5); cout << “| No. |   NPM    |       Nama          | Kelas |”;
gotoxy (2,6); cout << “————————————————“;
//                    234567890123456789012345678901234567890123456789
//                            1         2         3         4
for (i=0; i<jd; i++)
{
no=no+1;
gotoxy (2,6+no); cout << “|     |          |                     |       |”;
gotoxy (5,6+no); cout << no << “.”;
gotoxy (10,6+no); cout << npm[i];
gotoxy (21,6+no); cout << nm[i];
gotoxy (45,6+no); cout << kls[i];

}
gotoxy (2,7+no); cout << “————————————————“;
getch();

// Proses Searching

i=0;
clrscr();
gotoxy (20,10); cout << “Mencari Data Mahasiswa”;
gotoxy (20,12); cout << “Inputkan NPM = “; cin >> npm_cari;
while (i<jd && ketemu==0)
{
if(strcmp(npm[i],npm_cari)==0)
ketemu=1;
else
i++;
}

if (ketemu)
{
gotoxy(20,14); cout << “Data Mahasiswa tsb berada pada indeks ke-” << i;
gotoxy(20,16); cout << “Nama  = ” << nm[i];
gotoxy(20,17); cout << “Kelas = ” << kls[i];
}
else
{    gotoxy(20,14); cout << “Data Mahasiswa tsb tidak ditemukan”; }
getch();
}

Contoh Program C++ Searching Mencari Angka

Posted on

Sumber:

http://pemrogramanamikomsi.blogspot.com/2013/11/contoh-program-c-serching-mencari-angka.html

Contoh program c++ Sequential Search mencari posisi / letak angka.

searching . . . .mencari angka data ditemukan

#include <conio.h>
#include <iostream.h>
main(){
int c,i,posisi;
int A[20]={3,2,4,10,20,1,5,8,7,9,6,5,11,12,14,13,16,15,17,19};

cout<<“Data : “;
for(i=0;i<20;i++){
cout<<A[i]<<” “;
}

cout<<“\nData yang ingin dicari : “;
cin>>c;
i=0;
posisi=0;
while(i<19 && A[i]!=c){
i++;
}
if (A[i]!=c){
cout<<“Maaf data yang dicari tidak ada”;
}else if(posisi=i+1)
cout<<“ditemukan pada posisi ke “<<posisi;
getch();
}

Sorting dengan Metode Insertion dan Merge Sort

Posted on

Sumber:

http://dinda-dinho.blogspot.com/2013/02/sorting-dengan-metode-insertion-dan.html

 

Insertion Sort
Posting sebelumnya dibahas tentang Bubble Sort  dan Selection Sort, kali ini akan membahas Insertion Sort. Mirip dengan cara orang mengurutkan kartu, selembar demi selembar kartu diambil
dan disisipkan (insert) ke tempat yang seharusnya.  Pengurutan dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil , maka akan ditempatkan ( diinsert ) diposisi yang seharusnya. Pada penyisipan elemen, maka elemen-elemen lain akan bergeser ke belakang.

Contoh dari Insertion Sort
Insertion-sort-example-300px

 

Merge Sort
Algoritma dirumuskan dalam 3 langkah berpola divide-and-conquer. Berikut menjelaskan langkah kerja dari Merge sort. 

  1. Divide  : Memilah elemen – elemen dari rangkaian data menjadi dua bagian.
  2. Conquer : Conquer setiap bagian dengan memanggil prosedur merge sort secara rekursif
  3. Kombinasi : Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutanProses rekursi berhenti jika mencapai elemen dasar. Hal ini terjadi bilamana bagian yang akan diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah terurut sesuai rangkaian.

Contoh dari Merge Sort

Merge-sort-example-300px

 

 

Sorting dengan Metode Quick Sort

Posted on

Sumber:

http://dinda-dinho.blogspot.com/2013/07/sorting-dengan-metode-quick-sort.html

Sorting dengan Metode Quick Sort

Quicksort-example

Quick Sort sebenarnya sama seperti Merge sort yaitu menggunakan metode Divide & Conquer. Prinsip dalam algoritma quicksort sebagai berikut:

  1. Bila elemen dalam array kurang dari jumlah tertentu (biasanya 2), proses selesai.
  • Ambil sebuah elemen yang berfungsi sebagai poros.
  • Pisahkan array dalam 2 bagian, sebelah kiri lebih kecil dari poros, sebelah kanan lebih besar dari poros.
  • Ulangi proses secara rekursif pada tiap-tiap bagian.

 

Hal penting dari hal algoritma ini adalah: bagaimana memilih poros dengan tepat dan secara efisien mengatur tiap-tiap elemen sehingga didapat elemen kecil > poros > elemen besar dalam kondisi (mendekati) seimbang.
Contoh Quick sort dalam gambar

quick-sort