Tujuan dari dokumen ini adalah untuk menguraikan
persyaratan perangkat lunak untuk sistem penerimaan siswa baru. Sistem ini
bertujuan untuk merampingkan proses penerimaan siswa baru ke lembaga
pendidikan, menyediakan platform yang efisien dan ramah pengguna untuk pelamar
dan administrator.
1.2 Scope
Sistem penerimaan siswa baru akan menangani seluruh
proses penerimaan, mulai dari pengajuan aplikasi hingga seleksi akhir dan
pendaftaran siswa. Ini juga akan menyediakan fungsionalitas yang diperlukan
untuk melacak dan mengelola informasi pelamar, memfasilitasi komunikasi antara
pelamar dan administrator, dan menghasilkan laporan untuk analisis.
2. Functional Requirements
2.1 User Registration
Sistem akan memungkinkan pelamar untuk membuat
akun pengguna dengan memberikan informasi pribadi mereka.
Sistem akan memvalidasi dan memverifikasi alamat
email pengguna untuk aktivasi akun.
2.2 Application Submission
Sistem harus menyediakan formulir aplikasi online
bagi pelamar untuk diisi dan diserahkan.
Formulir aplikasi harus mencakup bidang untuk
informasi pribadi, latar belakang pendidikan, dan dokumen tambahan yang
diperlukan.
Sistem akan memungkinkan pelamar untuk menyimpan
kemajuan mereka dan menyelesaikan aplikasi nanti jika diinginkan.
Sistem harus memvalidasi permohonan yang diajukan
untuk kelengkapan dan kebenarannya.
2.3 Application Processing
Sistem akan memungkinkan administrator untuk meninjau
dan memproses aplikasi yang diajukan.
Administrator harus memiliki kemampuan untuk
melihat dan memperbarui informasi pemohon.
Sistem harus menyediakan fungsionalitas untuk
melacak status setiap aplikasi (misalnya, diterima, ditinjau, diterima, ditolak).
Administrator harus memiliki kemampuan untuk
berkomunikasi dengan pelamar melalui sistem (misalnya, mengirim
pemberitahuan, meminta dokumen tambahan).
2.4 Selection and Admission
Sistem harus memfasilitasi proses seleksi dengan
memungkinkan administrator untuk mengevaluasi dan membandingkan aplikasi
berdasarkan kriteria yang telah ditentukan.
Sistem harus menyediakan fungsionalitas untuk
menghasilkan penawaran penerimaan bagi pelamar terpilih.
Administrator harus memiliki kemampuan untuk
mengirim penawaran penerimaan dan melacak tanggapan pelamar (misalnya,
penerimaan, penolakan).
2.5 Enrollment
Sistem harus menyediakan fungsionalitas bagi
pelamar yang diterima untuk mengkonfirmasi pendaftaran mereka dan
memberikan rincian pendaftaran yang diperlukan (misalnya, pemilihan
kursus, informasi pembayaran).
Administrator harus memiliki kemampuan untuk
melacak dan mengelola status pendaftaran setiap pemohon yang diterima.
3. Non-Functional Requirements
3.1 Usability
Sistem harus memiliki antarmuka yang ramah
pengguna, memastikan kemudahan penggunaan bagi pelamar dan administrator.
Sistem harus memberikan instruksi dan panduan yang
jelas selama proses aplikasi.
Sistem harus dapat diakses di beberapa perangkat
(misalnya, desktop, tablet, ponsel) dan mendukung berbagai browser web.
3.2 Security
Sistem harus menerapkan langkah-langkah keamanan
yang tepat untuk melindungi data pemohon dan mencegah akses yang tidak
sah.
Mekanisme otentikasi dan otorisasi pengguna harus
diterapkan untuk memastikan hanya individu yang berwenang yang dapat
mengakses dan mengubah data.
3.3 Performance
Sistem harus mampu menangani volume besar pengguna
bersamaan selama periode penerimaan puncak.
Waktu respons untuk operasi sistem (misalnya,
pengajuan aplikasi, pengambilan data) harus dalam batas yang dapat
diterima.
3.4 Reliability
Sistem harus dapat diandalkan dan tersedia untuk
digunakan selama proses penerimaan.
Mekanisme pencadangan dan pemulihan bencana yang
memadai harus tersedia untuk mencegah kehilangan data jika terjadi
kegagalan sistem.
4. Constraints
4.1 Technology Constraints
Sistem harus dikembangkan menggunakan bahasa
pemrograman XYZ dan kerangka ABC.
Sistem harus berjalan pada sistem operasi tertentu
atau kompatibel dengan beberapa sistem operasi.
4.2 Regulatory Constraints
Sistem harus mematuhi peraturan perlindungan data
dan privasi yang relevan (misalnya, GDPR, HIPAA).
5. Assumptions and Dependencies
5.1 Assumptions
Pelamar memiliki akses ke internet dan perangkat
yang sesuai untuk melengkapi aplikasi online.
Administrator memiliki infrastruktur perangkat
keras dan perangkat lunak yang diperlukan untuk mendukung sistem.
5.2 Dependencies
Sistem tergantung pada konektivitas internet yang
andal untuk operasinya.
Sistem dapat berintegrasi dengan layanan eksternal
untuk verifikasi email, pemrosesan pembayaran, dll.
Dokumen Spesifikasi Persyaratan Perangkat Lunak ini
memberikan gambaran umum tentang persyaratan utama untuk sistem penerimaan
siswa baru. Ini berfungsi sebagai dasar untuk pengembangan dan implementasi
perangkat lunak, memastikan bahwa semua fungsi penting disertakan.
Metode Branch and Bound adalah sebuah teknik algoritma yang secara khusus mempelajari bagaimana caranya memperkecil Search Tree menjadi sekecil mungkin.
Sesuai dengan namanya, metode ini terdiri dari 2 langkah yaitu :
Branch yang artinya membangun semua cabang tree yang mungkin menuju solusi.
Bound yang artinya menghitung node mana yang merupakan active node (E-node) dan node mana yang merupakan dead node (D-node) dengan menggunakan syarat batas constraint (kendala).
Teknik Branch and Bound
Ada beberapa teknik dalam Branch and Bound yaitu:
FIFO Branch and Bound Adalah teknik Branch and Bound yang menggunakan bantuan queue untuk perhitungan Branch and Bound secara First In First Out.
LIFO Branch and Bound Adalah teknik Branch and Bound yang menggunakan bantuan stack untuk perhitungan Branch and Bound secara Last In First Out.
Least Cost Branch and Bound Teknik ini akan menghitung cost setiap node. Node yang memiliki cost paling kecil dikatakan memiliki kemungkinan paling besar menuju solusi.
Masalah yang dapat dipecahkan with Branch and Bound
Branch and Bound dapat digunakan untuk memecahkan berbagai masalah yang menggunakan Search Tree : –Traveling Salesman Problem –N-Queen Problem –15 Puzzle Problem –0/1 Knapsack Problem –Shortest Path
Knapsack Problem
Knapsack problem adalah suatu masalah bagaimana cara menentukan pemilihan barang dari sekumpulan barang dimana setiap barang tersebut mempunyai berat dan profit masing masing, sehingga dari pemilihan barang tersebut didapatkan profit yang maksimum. Penyelesaian masalah dengan menggunakan algoritma exhaustive search adalah mengenumerasikan semua kemungkinan barang-barang yang layak atau memenuhi syarat yaitu tidak melebihi batas daya angkut gerobak untuk dijual setiap harinya , kemudian menghitung tiap-tiap keuntungan yang diperoleh dan memilih solusi yang menghasilkan keuntungan terbesar.
Berbeda dengan algoritma exhaustive search yang cukup memakan waktu dan dapat menghasilkan solusi yang optimum, penyelesaian masalah dengan menggunakan algoritma greedy dilakukan dengan memasukan objek satu persatu kedalam gerobak dan tiap kali objek tersebut telah dimasukan kedalam gerobak maka objek tersebut tidak dapat lagi dikeluarkan dari gerobak. Pencarian solusi akan dilakukan dengan memilih salah satu jenis greedy (greedy by weight, greedy by profiit or greedy by density) yang diperkirakan dapat menghasilkan solusi yang optimum. Algoritma Branch and Bound juga merupakan salah satu strategi yang dapat digunakan dalam pencarian solusi optimum dari permasalahan knapsack ini.
Algoritma Branch and Bound
Sebagaimana pada algortima runut-balik, algoritma Branch & Bound juga merupakan metode pencarian di dalam ruang solusi secara sistematis. Ruang Solusi diorganisasikan ke dalam pohon ruang status. Pembentukan pohon ruang status. Pembentukan pohon ruang status pada algoritma B&B berbeda dengan pembentukan pohon pada algoritma runutbalik. Bila pada algoritma runut-balik ruang solusi dibangun secara Depth-First Search(DFS), maka pada algoritma B&B ruang solusi dibangun dengan skema Breadth-First Search (BFS).
Pada algoritma B&B, pencarian ke simpul solusi dapat dipercepat dengan memilih simpul hidup berdasarkan nilai ongkos (cost). Setiap simpul hidup diasosiasikan dengan sebuah ongkos yang menyatakan nilai batas (bound). Pada prakteknya, nilai batas untuk setiap simpul umumnya berupa taksiran atau perkiraan. Fungsi heuristik untuk menghitung taksiran nilai tersebut dinyatakan secara umum sebagai :
(i) = (i) + (i)
yang dalam hal ini,
(i) = ongkos untuk simpul i (i) = ongkos mencapai simpul i dari akar (i) = ongkos mencapai simpul tujuan dari simpul akar i (perkiraan)
Nilai digunakan untuk mengurutkan pencarian. Simpul berikutnya yang dipilih untuk diekspansi adalah simpul yang memiliki minimum (Simpul-E). Strategi memilih simpul-E seperti ini dinamakan strategi pencarian berdasarkan biaya terkecil (least cost search).
Prinsip dari algoritma branch and bound ini adalah :
1. Masukkan simpul akar ke dalam antrian Q. Jika simpul akar adalah simpul solusi (goal node), maka solusi telah ditemukan. Stop.
2. Jika Q kosong, tidak ada solusi . Stop.
3. Jika Q tidak kosong, pilih dari antrian Q simpul i yang mempunyai (i) paling kecil. Jika terdapatbeberapa simpul i yang memenuhi, pilih satusecara sembarang.
4. Jika simpul i adalah simpul solusi, berarti solusi sudah ditemukan, stop. Jika simpul i bukan simpul solusi, maka bangkitkan semua anak-anaknya. Jika i tidak mempunyai anak, kembali ke langkah 2.
5. Untuk setiap anak j dari simpul i, hitung (j), dan masukkan semua anak-anak tersebut ke dalam antrian Q.
6. Kembali ke langkah 2.
Knapsack Problem Solve
Untuk lebih memahami tahap-tahap penyelesaian permasalahan knapsack ini, kita ambil contoh persoalan seperti yang dituliskan pada bagian Abstrak yaitu dimana seorang pedagang keperluan rumah tangga keliling harus memilih barang-barang yang akan dijual setiap harinya dengan batas daya angkut gerobak yang dimilikinya. Untuk mempermudah, kita misalkan pedagang keliling tersebut hanya memiliki 4 jenis barang untuk dijual dengan berat dan keuntungan penjualan yang berbeda-beda untuk tiap jenisnya.
Gerobak yang akan dipakai untuk mengangkut barang-barang tersebut hanya mampu menampuk beban seberat 16 kg. Berikut merupakan tebel penggambaran beratdan keeuntungan yang akan diperoleh untuk tiap penjualan barang tersebut.
dari tiap tiap simpul anak untuk dapat menentukan simpul mana yang kelak akan dibangkitkan yaitu simpul dengan cost tertinggi dalam penelusuran pohon unutk mencapai solusi dari permasalahan ini. Dalam permasalahan ini, kita akan mencari simpul-simpul yang akan membawa kita pada keuntungan terbesar oleh karena itu urutan pembangkitan simpul akan ditentukan oleh simpul mana yang memiliki cost tertinggi. Cost dari tiap simpul akan ditentukan dengan:
(i) = (i) + (i)
yang dalam hal ini,
(i) = cost untuk simpul i (i) = cost untuk sampai ke simpul I, dalam hal ini merupakan keuntungan dari simpul akar ke simpul i (i) = cost dari simpul i untuk sampai ke simpul tujuan, dalam hal ini dapat diperoleh dengan menggunakan rumus : (P/W)max * daya angkut yang tersisa
pada tahap awal kita akan melakukan perhitungan dengan menggunakan rumus diatas untuk memperoleh batas awal atau akar dari pohon yang juga merupakan simpul pertama. Pada keadaan ini, batas dihitung dengan pemikiran bahwa belum ada satupun barang yang dimasukan kedalam alat pengangkut maka kita dapat memilih 6 sebagai (P/W) terbesar karena belum ada satu barangpun yang dimasukan kedalam alat pengangkut dan kapasitas daya angkutpun masih utuh yaitu seberat 16 kg.
(i) = (i) + (i)
(1) = keuntungan yang diperoleh sampai disimpul
awal + (P/W)max * daya angkut yang tersisa
= 0 + 6 *
= 96
Maka kita memperoleh 96 batas awal atau cost dari simpul awal.
Bangkitkan simpul-simpul anak dari akar pohon yaitu dengan membangkitkan simpul 1, simpul 2, simpul 3 dan simpul 4 sebagai gambaran dari 4 pilihan barang yang akan dimasukan pertama kali pada alat pengangkut dengan x1 merupakan keuntungan yang akan diperoleh pada penjualan tiap barang tersebut. Kemudian kita akan menghitung cost dari tiap simpul anak yang hidup dan juga kelayakannya untuk tetap hidup atau harus dibunuh. Dalam hal ini, simpul yang jumlah dari lintasannya tidak bisa lagi dibangkitkan (jika ditambah barang lagi kedalam alat pengangkut maka beratnya akan melebihi daya angkut) akan dibunuh.
(2) = 12 + 5*(16-2) = 82
(3) = 15 + 6*(16-5) = 81
(3) = 50 + 6*(16-10)=86
(4) = 10 + 6*(16-5)=76
Dari simpul-simpul yang telah dibangkitkan dan dihitung cost nya, maka diperoleh bahwa simpul 4 lah yang memiliki cost tertinggi oleh karena itu maka simpul 4 akan di perluas lagi. Simpul 6 ,7,8 akan dibangkitkan sebagai perluasan dari simpul 4 dengan barang yang mungkin dimasukan kedalam alat pengangkut adalah barang ke 1,2 dan 4. kemudian kita akan mengkitung cost dari simpul 6,7dan 8.
Algoritma merupakan kumpulan perintah yang memiliki daya guna yang sangat besar bagi masyarakat. Algoritma biasanya digunakan sebagai kumpulan perintah untuk menyelesaikan suatu masalah. Algoritma ini memiliki aplikasi yang bermacam-macam dalam setiap masalah yang ada. Contohnya saja adalah algoritma cara menyelesaikan suatu aritmatika yang rumit, algoritma untuk menghitung luas penampang dari suatu kabel, atau bahkan untuk menghitung bayaran parkir di setiap mal. Salah satu aplikasi bentuk pemrograman ini adalah dalam bahasa permrograman yang disebut bahasa C. Dimana bahasa C ini memiliki suatu aturan-aturan tertentu yang sangat penting sehingga dalam penggunaanya kita harus memperhatikan cara menggunakan aturan tersebut. Salah satu cara penggunaannya adalah dengan array. Dimana array ini merupakan suatu data struktur yang berkoneksi satu sama lain dengan tipe yang sama. Aplikasi array ini banyak sekali, contohnya saja adalah menghitung golongan dari umur yang berjumlah 25 tahun hingga 55 tahun. Array ini juga bisa digunakan untuk mencari suatu elemen nilai dalam suatu struktur data, selain itu array ini juga bisa digunakan untuk mengurutkan data-data yang tidak berurutan. Hal –hal yang telah disebutkan disebut sebagai searching array dan sorting array.
Sorting array merupakan salah satu aplikasi yang paling penting dalam suatu sistem aplikasi perhitungan data. Biasanya suatu bank memiliki komputasi sorting array yang sudah biasa digunakan dalam aplikasinya sehari-hari. Bahkan telephone juga mengurutkan suatu list yang terdiri dari nama akhir , nama awal agar bisa memudahkan dalam perhitungan dalam mencari nomor telephone.
Searching array juga memiliki tak kalah pentingnya dibandingkan dengan sorting array. Pada searcing array kita biasa menggunakannya pada data yang sangat banyak. Sehingga sangat sulit bila kita ingin mencari suatu data atau suatu angka didalamnya satu per satu. Aplikasi searching array memudahkan kita dalam mencari suatu data atau angka yang kita inginkan dengan hanya memasukkan nilai input pada suatu data yang disikan.
1. Insertion sort
Salah satu algoritma sorting yang paling sederhana adalah insertion sort. Ide dari algoritma ini dapat dianalogikan seperti mengurutkan kartu. Penjelasan berikut ini menerangkan bagaimana algoritma insertion sort bekerja dalam pengurutan kartu. Anggaplah anda ingin mengurutkan satu set kartu dari kartu yang bernilai paling kecil hingga yang paling besar. Seluruh kartu diletakkan pada meja, sebutlah meja ini sebagai meja pertama, disusun dari kiri ke kanan dan atas ke bawah. Kemudian kita mempunyai meja yang lain, meja kedua, dimana kartu yang diurutkan akan diletakkan. Ambil kartu pertama yang terletak pada pojok kiri atas meja pertama dan letakkan pada meja kedua. Ambil kartu kedua dari meja pertama, bandingkan dengan kartu yang berada pada meja kedua, kemudian letakkan pada urutan yang sesuai setelah perbandingan. Proses tersebut akan berlangsung hingga seluruh kartu pada meja pertama telah diletakkan berurutan pada meja kedua. Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan (meja pertama) dan yang sudah diurutkan (meja kedua). Elemen pertama diambil dari bagian array yang belum diurutkan dan kemudian diletakkan sesuai posisinya pada bagian lain dari array yang telah diurutkan. Langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian array yang belum diurutkan.
Algoritmanya :
void insertionSort(Object array[], int startIdx, int endIdx)
{
for (int i = startIdx; i < endIdx; i++) {
int k = i;
for (int j = i + 1; j < endIdx; j++) {
k = j;
}
}
swap(array[i],array[k]);
}
}
2. Selection sort
Jika anda diminta untuk membuat algoritma sorting tersendiri, anda mungkin akan menemukan sebuah algoritma yang mirip dengan selection sort. Layaknya insertion
sort, algoritma ini sangat rapat dan mudah untuk diimplementasikan. Mari kita kembali menelusuri bagaimana algoritma ini berfungsi terhadap satu paket kartu. Asumsikan bahwa kartu tersebut akan diurutkan secara ascending. Pada awalnya, kartu tersebut akan disusun secara linier pada sebuah meja dari kiri ke kanan, dan dari atas ke bawah. Pilih nilai kartu yang paling rendah, kemudian tukarkan posisi kartu ini dengan kartu yang terletak pada pojok kiri atas meja. Lalu cari kartu dengan nilai paling rendah diantara sisa kartu yang tersedia. Tukarkan kartu yang baru saja terpilih dengan kartu pada posisi kedua. Ulangi langkah – langkah tersebut hingga posisi kedua sebelum posisi terakhir dibandingkan dan dapat digeser dengan kartu yang bernilai lebih rendah.
Ide utama dari algoritma selection sort adalah memilih elemen dengan nilai paling rendah dan menukar elemen yang terpilih dengan elemen ke-i. Nilai dari i dimulai dari 1 ke n, dimana n adalah jumlah total elemen dikurangi 1.
Algoritmanya :
void selectionSort(Object array[], int startIdx, int endIdx)
{
int min;
for (int i = startIdx; i < endIdx; i++) {
if (((Comparable)array[min]).compareTo(array[j])>0) {
min = i;
for (int j = i + 1; j < endIdx; j++) {
min = j;
}
}
}
swap(array[min], array[i]);
}
3. Merge sort
Beberapa algoritma mengimplementasikan konsep rekursi untuk menyelesaikan permasalahan. Permasalahan utama kemudian dipecah menjadi sub-masalah, kemudian solusi dari sub-masalah akan membimbing menuju solusi permasalahan utama.
Pada setiap tingkatan rekursi, pola tersebut terdiri atas 3 langkah.
1. Divide
Memilah masalah menjadi sub masalah
2. Conquer
Selesaikan sub masalah tersebut secara rekursif. Jika sub-masalah tersebut cukup ringkas dan sederhana, pendekatan penyelesaian secara langsung akan lebih efektif
3. Kombinasi
Mengkombinasikan solusi dari sub-masalah, yang akan membimbing menuju penyelesaian atas permasalahan utama
Seperti yang telah dijelaskan sebelumnya, Merge sort menggunakan pola divide and conquer. Dengan hal ini deskripsi dari algoritma dirumuskan dalam 3 langkahberpola 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 berurutan
Proses 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.
Algoritmanya :
void mergeSort(Object array[], int startIdx, int endIdx)
Quicksort ditemukan oleh C.A.R Hoare. Seperti pada merge sort, algoritma ini juga berdasar pada pola divide-and-conquer. Berbeda dengan merge sort, algoritma ini hanya mengikuti langkah – langkah sebagai berikut :
1. Divide
Memilah rangkaian data menjadi dua sub-rangkaian A[p…q-1] dan A[q+1…r] dimana setiap elemen A[p…q-1] adalah kurang dari atau sama dengan A[q] dan setiap elemen pada A[q+1…r] adalah lebih besar atau sama dengan elemen pada A[q]. A[q] disebut sebagai elemen pivot. Perhitungan pada elemen q merupakan salah satu bagian dari prosedur pemisahan.
2. Conquer
Mengurutkan elemen pada sub-rangkaian secara rekursif
Pada algoritma quicksort, langkah “kombinasi” tidak di lakukan karena telah terjadi pengurutan elemen – elemen pada sub-array
Algoritmanya :
void quickSort(Object array[], int leftIdx, int rightIdx) {
int pivotIdx;
/* Kondisi Terminasi */
pivotIdx = partition(array, leftIdx, rightIdx);
if (rightIdx > leftIdx) {
quickSort(array, leftIdx, pivotIdx-1);
}
quickSort(array, pivotIdx+1, rightIdx);
}
Gambar 3.2. Diagram Quick Sort
5. Counting sort
Adalah sebuah algoritma sorting linear yang digunakan untuk mengurutkan ‘item’ ketika urutannya telah ditentukan dan memiliki panjang yang terbatas. Bilangan interval yang telah tetap, katakana k1 ke k2 adalah contoh dari ‘item’ tersebut. Counting sort sebenarnya merupakan metode pengurutan yang memanfaatkan index variabel array. Hanya effektif pada data yang nilainya kecil.
Algoritma ini diproses dengan mendefinisikan sebuah hubungan urutan antara ‘item’ yang akan disorting. Katakana ‘item’ yang akan disorting adalah variable A. Maka, terdapat sebuah array tambahan dengan ukuran yang serupa dengan array A. katakana array tersebut adalah array B. untuk setiap element di A, sebut e, algoritma ini menyimpan jumlah ‘item’ di A lebih kecil dari atau sama dengan e di B(e). jika hasil sorting yang terakhir disimpan di array C, maka untuk masing-masing e di A, dibuat dalam arah yang sebaliknya, yaitu C[B(e)]=e. setelah step di atas, niali dari B(e) berkurang dengan 1.
Algoritma ini membuat 2 passover A dan passover B. Jika ukuran dari range k lebih kecil dari ukuran input n, maka time complexity = O(n). perhatikan juga bahwa algoritma ini stabil yang berarti bahwa sambungan diselesaikan dengan langsung mengabarkan element-element yang muncul pertama kali.
Adapun syarat algoritma ini berjalan dengan baik ialah:
Data harus bilangan bulat yang bernilai lebih besar atau sama dengan nol
Range data diketahui
Ada 3 macam array yang terlibat:
Array untuk mengisi bilangan yang belum diurutkan.
Array untuk mengisi frekuensi bilangan itu, sekaligus sebagai penghitung kejadian.
Array untuk mengisi bilangan yang sudah diurutkan.
Algoritmanya :
countingsort(A[], B[], min, max, n)
for i = min to max do
C[i] = 0
C[A[j]] = C[A[j]] + 1
for j = 1 to n do
for i = min + 1 to max do
B[C[A[j]]] = A[j]
C[i] = C[i] + C[i-1]
for j = n downto 1 do
C[A[j]] = C[A[j]] – 1
Gambar 3.3 Diagram Counting Sort
6. Radix Sort
Radix sorting bisa digunakan ketika masing-masing universal element bisa dilihat sebagai sebuah urutan digit (atau huruf atau symbol lainnya). Sebagai contoh, kita bisa membuat masing-masing bilangan bulat antar 0 sampai 99 sebagai sebuah urutan dengan dua digit (seperti “05”). Untuk menyorting sebuah array dari angka 2-digit, algoritma ini membuat dua ‘passing’ sorting melalui array tersebut. Pada ‘passing’ pertama, element array disorting pada least significant decimal digit. Kunci utama dari radix sort adalah pada passing yang kedua. Hasilnya, setelah kedua passing melewati array tersebut, data yang terisi telah disorting.
Algoritmanya :
source
List of bytes
source_n
number of bytes to sort
dest[256]
256 lists of bytes. each list should have enough space to hold source_n elements.
//——————-saving element in memory——————–
int distribution[256]
// fill the list with zeros.
for i=0 to source_n do
for i=0 to 255 do
distribution[i]=0;
// build a distribution history:
distribution] = distribution] +1;
for i=0 to 255 do
endfor
// Now we build a index-list for each possible element:
int index[256];
index [0]=0;
for i = 0 to source_n do
index[i]=index[i-1]+distribution[i-1];
endfor
//sorting
dest: array of bytes with space for source_n bytes.
endfor
dest[index]]=source[i];
index] = index] +1;
7. Searching
7.1 Linear Searching
Algoritma pencarian secara linear adalah algoritma untuk mencari sebuah nilai pada table sambarang dengan cara melakukan pass atau transversal. Transversal dari awal sampai akhir table. Ada dua macam cara pencarian pada table. Algoritma mempunyai dua jenis metode yaitu dengan Boolean dan tanpa Boolean.
Algoritmanya :
void SeqSearch1 (int T[], int Nmax,
int value, int *idx)
{
/*Algoritma*/
/*kamus lokal*/
int i;
i = 1;
i = i + 1;
while ((i<Nmax) && (T[i] !=
value))
{
}
if (T[i]==value)
}
{
*idx = i;
}
else
{
*idx = 0;
}
Algoritma di atas melakukan pengulangan sampai i sama dengan Nmax (ukuran tabel) atau harga value dalam tabel sudah ditemukan. Kemudian harga i di-assign ke dalam variable idx. Elemen terakhir diperiksa secara khusus.
void SeqSearch2 (int T[],int Nmax,
int value, int *idx)
{
int i;
i = 1;
boolean found;
/*algoritma*/
found = false;
if (T[i] == value)
while ((i<=Nmax) && (!found))
{
{
found = true;
}
else
{
i = i + 1;
}
}
}
if (found)
{
*idx = i;
}
else
{
*idx = 0;
7.2 Binary Searching
Algoritma pencairan secara linear melakukan pengulangan sebanyak 1 kali untuk kasus terbaik (value sama dengan elemen pertama dalam tabel) dan Nmax kali untuk kasus terburuk. Sehingga algoritma ini mempunyai kompleksitas algoritma O(n).
Implementasi algoritma pencarian biner dalam bahasa C adalah sebagai berikut.
void BinSearch (int T[],int Nmax, int
value, int* idx)
int i,j,mid;
found = false;
boolean found;$
/*algoritma*/
i = 1;
mid = (i+j) div 2;
j = Nmax;
while ((!found) && (i<=j))
{
if (T[mid] == value)
{
found = true;
}
else
{
if (T[mid]<value)
{
i = mid + 1;
}
else
{
j = mid – 1;
}
}
}
}
if (found)
{
*idx = mid;
}
else
{
*idx = 0;
}
Algoritma pencarian biner adalah algoritma untuk mencari sebuah nilai pada tabel teurut dengan cara menghilangkan setengah data pada setiap langkah. Algoritma ini mencari nilai yang dicari dengan tiga langkah yaitu :
• Mencari nilai tengah dari tabel (median).
• Melakukan perbandingan nilai tengah dengan nilai yang dicari untuk menentukan apakah nilai yang dicari ada pada sebelum atau setelah nilai tengah.
Awal dari algoritma ini utamanya adalah pengurangan dan penaklukan - masalah asli secara berturut-turut dipecah menjadi sub-masalah tunggal, dan memang dapat diselesaikan secara berulang.
Pencarian biner, algoritma penurunan-dan-taklukkan di mana sub-masalah berukuran kira-kira setengah dari ukuran aslinya, memiliki sejarah yang panjang. Sementara deskripsi yang jelas tentang algoritma pada komputer muncul pada tahun 1946 dalam sebuah artikel oleh John Mauchly, gagasan untuk menggunakan daftar item yang diurutkan untuk memfasilitasi pencarian tanggal kembali setidaknya sejauh Babylonia pada 200 SM. Algoritma penurunan-dan-taklukkan kuno lainnya adalah algoritma Euclidean untuk menghitung pembagi persekutuan terbesar dari dua bilangan dengan mengurangi bilangan tersebut menjadi subproblem ekuivalen yang lebih kecil dan lebih kecil, yang berasal dari beberapa abad SM.
Contoh awal dari algoritma bagi-dan-taklukkan dengan beberapa subproblem adalah deskripsi Gauss tahun 1805 tentang apa yang sekarang disebut algoritma Cooley – Tukey fast Fourier transform (FFT), meskipun dia tidak menganalisis jumlah operasinya secara kuantitatif, dan FFT tidak tersebar luas sampai mereka ditemukan kembali lebih dari satu abad kemudian.
Algoritma D&C dua sub problem awal yang secara khusus dikembangkan untuk komputer dan dianalisis dengan benar adalah algoritma pengurutan gabungan, yang ditemukan oleh John von Neumann pada tahun 1945.
Sebagai contoh lain dari algoritma bagi-dan-taklukkan yang awalnya tidak melibatkan komputer, Donald Knuth memberikan metode yang biasanya digunakan kantor pos untuk merutekan surat: surat diurutkan ke dalam kantong terpisah untuk wilayah geografis yang berbeda, masing-masing kantong ini diurutkan sendiri ke dalam batch untuk sub-wilayah yang lebih kecil, dan seterusnya sampai dikirimkan. Ini terkait dengan jenis radix, yang dijelaskan untuk mesin sortir kartu berlubang sejak tahun 1929.
Definisi Algoritma Devide dan Conquer
Dalam ilmu komputer, Algoritma divide and conquer adalah paradigma desain algoritma yang didasarkan pada rekursi multi-cabang. Algoritme bagi-dan-taklukkan bekerja dengan memecah masalah secara rekursif menjadi dua atau lebih sub-masalah dari jenis yang sama atau terkait, hingga masalah ini menjadi cukup sederhana untuk diselesaikan secara langsung.
Cara Kerja Algoritma Devide dan Conquer
Contoh sederhana : Misalkan, untuk menghitung total jumlah dari bilangan-bilangan yang ada di dalam sebuah list, kita dapat menggunakan perulangan sederhana
nums = [1, 2, 3, 5, 6, 7, 19, 28, 58, 18, 28, 67, 13]
total = 0
for i in range(0, len(nums)):
total = total + nums[i]
print(total) # 255
Algoritma perulangan yang digunakan pada kode di atas memang sederhana dan memberikan hasil yang benar, tetapi terdapat beberapa masalah pada kode tersebut, yaitu perhitungan dilakukan secara linear, yang menghasilkan kompleksitas O(n). Hal ini tentunya cukup ideal untuk ukuran list kecil, tetapi jika ukuran list menjadi besar (beberapa Milyar elemen) maka perhitungan akan menjadi sangat lambat. Kenapa perhitungannya menjadi lambat? Karena nilai dari total tergantung kepada kalkulasi nilai total sebelumnya. Kita tidak dapat melakukan perhitungan total dari depan dan belakang list sekaligus, sehingga kita dapat mempercepat perhitungan dua kali lipat. Dengan kode di atas, kita tidak dapat membagi-bagikan pekerjaan ke banyak pekerja / CPU!
Lalu apa yang dapat kita lakukan? Langkah pertama yang dapat kita lakukan adalah menerapkan teknik rekursif untuk membagi-bagikan masalah menjadi masalah yang lebih kecil. Jika awalnya kita harus menghitung total keseluruhan list satu per satu, sekarang kita dapat melakukan perhitungan dengan memecah-mecah list terlebih dahulu:
def sums(lst):
if len(lst) >= 1:
return lst[0]
mid = len(lst) // 2
left = sums(lst[:mid])
right = sums(lst[mid:])
return left + right
print(sums(nums)) # 255
Apa yang kita lakukan pada kode di atas?
Baris if len(lst) >= 1 memberikan syarat pemberhentian fungsi rekursif, yang akan mengembalikan isi dari list ketika list berukuran 1 (hanya memiliki satu elemen).
Baris mid = len(lst) // 2 mengambil median dari list, sebagai referensi ketika kita membagi list menjadi dua bagian.
Baris left = sum(lst[:mid]) dan selanjutnya membagikan list menjadi dua bagian, dengan nilai mid sebagai tengah dari list.
Singkatnya, setelah membagikan list menjadi dua bagian terus menerus sampai bagian terkecilnya, kita menjumlahkan kedua nilai list tersebut, seperti pada gambar berikut:
Apa kelebihan pendekatan dengan membagi-bagikan masalah ini?
Dengan menggunakan bahasa dan library yang tepat, kita dapat membagi-bagikan setiap bagian rekursif (left = ... dan right = ...) ke satu unit kerja baru, yang dikenal dengan nama thread. Mekanisme pada sistem operasi atau compiler kemudian akan membagi-bagikan tugas pembagian dan perhitungan lanjutan agar dapat dijalankan secara paralel, misalnya dengan membagikan tugas ke dalam beberapa core prosesor, atau bahkan ke dalam mesin lain (jika terdapat sistem dengan banyak mesin).
Dengan membagi-bagikan pekerjaan ke dalam banyak unit, tentunya pekerjaan akan lebih cepat selesai! Teknik memecah-mecah pekerjaan untuk kemudian dibagikan kepada banyak pekerja ini dikenal dengan nama divide and conquer.
Algoritma sering dipakai sejumlah orang dalam kehidupan sehari-hari. Karena biasanya hal ini berfungsi sebagai salah satu upaya untuk memecahkan sejumlah permasalahan dengan menggunakan runtut langkah yang sistematis. Maka tidak mengherankan jika banyak yang bertanya apa saja contoh algoritma dalam kehidupan sehari hari.
Pengertian Algoritma
Bila didefinisikan algoritma merupakan suatu upaya pemecahan masalah dengan menggunakan langkah yang sistematis atau terurut. Selain itu juga menggunakan alur pemikiran yang terprogram, misalnya saja pada perhitungan untuk menghitung bagaimana pengamanan data. Untuk mencapai hasil dari upaya pemecahan masalah maka semua proses tersebut akan dijadikan poin-poin penting
Peranan Algoritma
Penerapan contoh algoritma dalam kehidupan sehari-hari juga sangat banyak untuk ditemukan. Membiasakan diri menggunakan pola pikir algoritma dapat membuat seseorang terlatih agar bisa berpikir secara kritis dan sistematis. Terlebih juga dapat meningkatkan analisis demi menghindari diri dari melakukan suatu kesalahan.
Menulis Algoritma
Sebenarnya banyak contoh algoritma dalam kehidupan sehari-hari mungkin tidak diketahui banyak pihak. Untuk menerapkan prinsip ini dalam kehidupan sebenarnya terdapat 3 cara yang bisa dilakukan. Misalnya saja menulis kalimat deskriptif kemudian diiringi dengan pembuatan grafis yang sistematis. Terakhir memulai bentuk penulisan algoritma yang hampir sama seperti bahasa pemrograman.
Perlunya Algoritma Dalam Kehidupan
Secara umum bisa dikatakan jika algoritma punya fungsi sangat besar dalam kehidupan. Selain untuk memecahkan masalah algoritma juga bisa digunakan sebagai panduan atau langkah cara dalam beraktivitas. Juga bisa diartikan dalam pembuatan sebuah program atau langkah-langkah mengenai hal-hal penting yang akan dilakukan.
Contoh Algoritma Dalam Kehidupan Sehari Hari
1. Algoritma Membuat kopi
Contoh algoritma dalam kehidupan sehari-hari pertama adalah terkait dengan cara membuat kopi. Yaitu berisi panduan mulai dari membuka kemasan kopi, menyeduh air, mencampurkan gula hingga mencampurkannya dengan air panas. Setelah semua tercampur rata, kopi siap dihidangkan, sebelum disantap harus diaduk terlebih dahulu.
2. Algoritma Membuat mie goreng
Saat membuat mie goreng buka kemasan mie sebelum kemudian diseduh dengan air panas dan diamkan selama beberapa saat. Langkah selanjutnya keringkan air kemudian campurkan bumbu ke dalam mie goreng. Setelah diaduk dengan merata kemudian siap untuk disantap dalam keadaan hangat maupun dingin.
3. Algoritma Memasak Nasi
Sebelum mulai memasak nasi, cuci beras dan siapkan penanak nasinya. Setelah diberikan air yang cukup lalu letakkan pada magicom dan tutup lalu pilih atau memasak. Jangan lupa tekan tombol cook, biarkan nasi masak dengan sendirinya sampai muncul tombol warm.
4. Algoritma Memakai Pakaian
Terakhir adalah algoritma memakai pakaian yang dipakai dalam lemari. Apabila memiliki resleting silakan buka terlebih dahulu kemudian pasangkan pada badan. Langkah terakhir tutup kembali resleting yang sebelumnya dibuka dan merapikan pakaian hingga terlihat lebih bagus dipandang.
5. Algoritma Mengecas Ponsel
Apabila ponsel telah menandakan kekurangan daya segera ambil charger. Selanjutnya pasang cas ponsel ini pada stop kontak atau colokan, pastikan pasang dengan benar. Bila telah menunjukkan penambahan daya silahkan tunggu hingga penuh dengan menjalankan aktivitas lain
Relational Database adalah suatu model database yang disajikan dalam bentuk tabel.
Model ini pertama kali diperkenalkan oleh E.F.Codd pada bulan Juni 1970 dalam sebuah paper berjudul : "A Relational Model of Data for Large Shared Data Banks"
Tujuan Relational Database :
Untuk menekankan kemandirian data
Menghilangkan inkonsistensi dan redudansi data menggunakan konsep normalisasi
Meningkatkan kemampuan akses data
Characteristic Relational Database :
Stuktur Tabular
Satu bahasa digunakan untuk semua pemakai
Data dihubungkan melalui nilai data
Model Data Relasional mengandung 3 komponen inti :
Struktur data (data diorganisasi dalam bentuk tabel)
Manipulasi data (menggunakan SQL)
Integritas data (Menjamin konsistensi data
Struktur Data
Struktur berbentuk tabel data dua dimensi
Contoh :
Struktur yang baik adalah relasi yang mengandung redundansi minimal dan mengijinkan pengguna untuk menyisipkan, memodifikasi serta menghapus baris-baris tanpa menimbulkan kesalahan.
Manipulasi Data
Data Definition Language (DDL)
Create
Drop
Alter
Data Manipulation Language (DML)
Insert
Delete
Update
Batasan Integritas Data
Domain Atribut
Setiap nilai yang disimpan dalam kolom sebuah relasi harus memiliki jangkauan nilai yang sama
Aturan Integritas
Aturan yang menjamin setiap atribut primary key bernilai valid (unik dan bukan null)
Referensial Integrity
Garis yang menghubungkan antara satu tabel dengan tabel lain
Database atau basis data adalah kumpulan informasi yang disimpan di dalam komputer secara sistematik sehingga dapat diperiksa menggunakan suatu program komputer untuk memperoleh informasi dari basis data tersebut. Kegunaan utama sistem basis data adalah agar pemakai mampu menyusun suatu pandangan (view) abstraksi data.
Database-System Applications
- Enterprise Information : Sales, accounting, human resources, manufacturing
- Banking and Finance : Banking, credit, finance
Database System vs File Processing System
- Data redudancy & inconsistency
- Difficulty in accessing data
- Data isolation
- Integrity problems
- Atomicity problems
- Concurrent-access anomalies
- Security problems
Data Abstraction
- Physical Level
- Logical Level
- View Level
Relational Database
- Uses a collection of tables to represent both data and the relationships among those data
- Each table has multiple columns, and each column has a unique name
- Tables are also known as relations
- Record-based models are so named because the database is structured in
fixed-format records of several types
- Each table contains records of a particular type. Each record type defines a fixed number
of fields, or attributes
- The columns of the table correspond to the attributes of the record type
- The relational data model is the most widely used data model, and a vast majority of
current database systems are based on the relational model
Order of the Tuples
- The order is irrelevant
- Because a relation is a set of tuples
- And also could be sorted by query and index
Attribute Types
- The set of allowed values for each attribute is called the domain of the attribute
- Attribute values are (normally) required to be atomic; that is, indivisible
- The special value null is a member of every domain
- The null value causes complications in the definition of many operations
Database Schema
- Database schema : logical design of the database
- Database instance : snapshot of the data in the database at a given instant time
Keys
- Must have a way to specify how tuples within a given relation are distinguished
- Expressed in terms of their attributes
- The values of the attribute values of a tuple must be such that they can uniquely identify the tuple
- No two tuples in a relation are allowed to have exactly the same value for all attributes
