1.2.5 Kelebihan dan Kekurangan Menggunanakan
Jaringan WLAN
1.2.6 Standar
1.3 Model Referensi TCP/IP
1.4 User Daragram Protocol (UDP)
1.5 Keamanan Jaringan
1.6 Jenis Serangan
BAB I
LANDASAN TEORI
Pengertian Implementasi
Implementasi adalah langkah yang vital dalam pengembangan
teknologi informasi untuk mendukung karyawan, pelanggan, dan pihakpihak yang bekepentingan lainnya. (O'Brien, 2005:529).
Jaringan Wireless
Definisi dan Kons ep Jaringan Wireless
Wireless (jaringan Nirkabel) merupakan satu jaringan komunikas
antar komputer dengan menggunakan frekuensi radio. Kad g disebut juga
jaringan Wifi atau WLAN (Sopandi,2008:113).
LAN disini dapat didefinisikan sebagai sebuah sistem
komunikasi data fleksibel yang dapat digunakan untuk m nggantikan atau
menambah jaringan LAN yang sudah ada untuk memberikan mbahan
fungsi dalam konsep jaringan komputer pada umumnya. Fungsi yang
ditawarkan disini dapat berupa konektivitas yang andal sehubung dengan
mobilitas (Hantoro, 2009: 2).
Menurut Hantoro (2009:2) prinsip awal komunikasi data
menggunakan jaringan radio bermula sejak perang dunia I oleh tentara
Amerika. Merekan mengembangkan teknologi transmisi data dengan
medium radio, dimana data disini telah terenkripsi den sangat baik. Hal
inilah mendorong para peneliti dari Universitas Hawai ntuk
mengembangkan hal yang sama dimana mereka menciptakan atu jaringan
pertama yang menggunakan teknologi komunikasi radio yang mana juga
menjadi cikal bakal dari WLAN yaitu ALOHNET pada tahun 1971. WLAN
pertama ini terdiri dari 7 komputer yang saling berkom ikasi di dalam
topologi jaringan secara .
Tidak lama setelah itu, IBM melakukan percobaan yang d lakukan
pada akhir 1970 dalam rangka merancang WLAN dengan tek ologi IR (Sinar
Infra Merah) dengan tujuan mencari alternatif penggunaan IEEE
802. kegiatan mencari solusi seperti ini diikuti oleh erusahaan lain seperti
Hewlett-Packard (HP) menguji WLAN dengan RF (Frekuensi Radio).
Intrusion Detection System
Menurut Ariyus (2007:27)Intrusion Detection System dapat
didefinisikan sebagai tool, metode, sumber daya yang m berikan bantuan
untuk melakukan identifikasi, memberikan laporan terhadap aktivitas
jaringan komputer. (IDS) sebenarnya tidak
cocok diberi pengertian tersebut karena IDS tidak mend ksi penyusupan
tetapi hanya mendeteksi aktivitas pada lalu lintas jaringan yang tidak layak
terjadi.
secara keseluruhan dari sistem yang telah diinstal IDS IDS tidak berdiri
sendiri dalam melindungi suatu sistem.
IDS juga memiliki peran penting untuk
mendapatkan arsitektur (pertahanan yang mendalam)
dengan melindungi akses jaringan internal, sebagai tam ahan dari parameter
Hal-hal yang dilakukan IDS ( ) pada
jaringan internal adalah sebagai berikut: (Ariyus, 2007:34).
1. Memonitor akses database : ketika mempetimbangkan pemi ihan
kandidat untuk penyimpanan data, suatu perusahaan akan memilih
database sebagai solusi untuk menyimpan data-data yang berharga.
2. Melindungi e-mail server : IDS ( ) juga
berfungsi untuk mendeteksi virus seperti QAZ, ,
2.9.4. Peran IDS (Intrusion Detection System)
intrusion detection system
defence-in-depth
defence. intrusion detection system
intrusion detection system
e-mail Worm.
Algoritma Branch and Bound digunakan untuk memecahkan masalah pencarian rute terpendek.
Algoritma ini memiliki 2 prinsip, yaitu:
- Algoritma ini akan melakukan perhitungan secara rekursif, akan memecah masalah kedalam masalah-masalah kecil, sambil tetap menghitung nilai terendah / terbaik. Proses ini dinamakan branching.
- Jika branching diterapkan secara sendirian, maka hasilnya akan tetap mencari setiap kemungkinan yang ada. Untuk meningkatkan performa, algoritma ini akan melakukan pencatatan biaya minimum sebagai bound dalam setiap perhitungan, sehingga untuk calon hasil jawaban yang diperkirakan akan melebihi bound akan dibuang karena tidak mungkin akan mencapai nilai terbaik.
Implementasi Algoritma Branch & Bound Pada Masalah Knapsack
Metode Branch and Bound
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.
(6) = (50+12) + 3*(16-10-2) = 74
(7) = (50+15) + 6*(16-10-5) = 71
(8) = (50+10) + 6*(16-10-5) = 66
Demikian artikel tentang Implementasi Algoritma Branch and Bound, semoga bermanfaat😉
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.
Contoh penting lainnya adalah algoritma yang ditemukan oleh Anatolii A. Karatsuba pada tahun 1960 [8] yang dapat mengalikan dua angka n-digit di O (n log 2 3) {\ displaystyle O (n ^ {\ log _ {2} 3} )} O (n ^ {\ log _ {2} 3}) operasi (dalam notasi Big O). algoritma ini menyangkal dugaan Andrey Kolmogorov tahun 1956 bahwa operasi Ω (n 2) {\ displaystyle \ Omega (n ^ {2})} \ Omega (n ^ {2}) diperlukan untuk tugas tersebut.
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
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:
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.
Demiikian artikel tentang Sejarah, Definisi dan Cara Kerja Algoritma Divide and Conquer. Semoga bermanfaat😊
SWITCH CASE adalah percabangan kode program dimana kita membandingkan isi sebuah variabel dengan beberapa nilai. Jika proses perbandingan tersebut menghasilkan nilai true, maka block kode program akan dijalankan atay bisa dikatakan juga, Switch Case merupakan pernyataan yang digunakan untuk menjalankan salah satu pernyataan dari beberapa kemungkinan pernyataan.
Contoh Program Switch Case
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Tugas_Praktikum
{
class Program
{
static void Main(string[] args)
{
int Masukan;
Console.WriteLine("Pilihan Program : ");
Console.WriteLine("1. Program Karyawan");
Console.WriteLine("2. Program Jumlah Bilangan");
Console.Write("Masukan Pilihan Anda : ");
Masukan = int.Parse(Console.ReadLine());
switch (Masukan)
{
case 1:
int lembur, data, tot_gaji, bonus, x;
string nama;
Console.Write("Masukan Jumlah Karyawan : ");
data = int.Parse(Console.ReadLine());
x = 1;
while (x <= data)
{
Console.Write("\nData Karyawan Ke-{0} : ",x);
Console.Write("\nNama : ");
nama = Console.ReadLine();
Console.Write("Lembur : ");
lembur = int.Parse(Console.ReadLine());
bonus = 50000 * lembur;
tot_gaji = 2000000 + bonus;
Console.WriteLine("\nTotal Gaji : " + tot_gaji);
x++;
}
break;
case 2:
int ulang, jumlah, nilai;
Console.Write("\nJumlah Data : ");
data = int.Parse(Console.ReadLine());
ulang = 1;
jumlah = 0;
while (ulang <= data)
{
Console.Write("Data Ke-{0} : ", ulang);
nilai = int.Parse(Console.ReadLine());
jumlah = jumlah + nilai;
ulang++;
}
Console.Write("Jumlah data yang diinput :" + jumlah);
break;
}
Console.ReadKey();
}
}
}
Dari program di atas, maka akan menampilkan seperti gambar di bawah ini :
Statement
IF digunakan untuk mengeksekusi beberapa kode program apabila mempunyai
kondisi True atau False.
Rumus
Pernyataan If, yaitu :
if (condition) {
//statements
Statement IF menentukan kondisi ekspresi yang akan ditentukan.
Apabila kondisi benar, pernyataan dalam kurung kurawal “{}” akan dijalankan.Apabila kondisi salah, maka akan diabaikan atau tidak ada hasil yang ditampilkan.
Contoh
Penggunaan Statement If
Output yang
akan dihasilkan adalah :
Jika nilai A diganti menjadi lebih kecil dari nilai B, maka tidak ada
hasil yang akan ditampilkan.
II. Statement
Else C#
Statement Else adalah
pengikut dari Statement IF,
apabila Statement IF adalah
statement utama, maka Statement Else adalah
statement kedua (Statement Opsional). Statement Else akan di eksekusi apabila Statement IF tidak mendapatkan
hasil atau mempunyai hasil salah.
Rumus
Pernyataan Else, yaitu :
if (condition) {
//statements
}
else
{
//statements
}
Contoh
Penggunaan Statement Else
Pada
program di atas, output yang akan dihasilkan mempunyai 2 pilihan, yaitu “True”
dan “False”, dapat dilihat pada gambar di bawah ini :
