ANALISIS ALGORITMA

-       Algoritma adalah urutan langkah yang tepat dan pasti dalam memecahkan suatu masalah secara logis.

-       Beberapa masalah dapat diselesaikan dengan algoritma yang bermacam macam asal hasilnya sama.

-       Setiap bahasa pemrograman memiliki kelebihan dan kekurangan dalam mengimplementasikan algoritma dan setiap pemrogram dapat mengimplementasikan suatu algoritma dengan cara yang berbeda-beda pula.

-       Namun algoritma dapat dianalisis efisiensi dan kompleksitasnya.

-       Penilaian algoritma didasarkan pada:

·         Waktu eksekusi (paling utama)

·         Penggunaan memori/sumber daya

·         Kesederhanaan dan kejelasan algoritma

-       Analisis algoritma tidak mudah dilakukan secara pasti, maka hanya diambil:

·         Kondisi rata-rata (average case)

·         Kondisi terburuk (worst case)

-       Waktu eksekusi dipengaruhi oleh:

·         Jenis data input

·         Jumlah data input

·         Pemilihan instruksi bahasa pemrograman

-       Faktor-faktor yang menyulitkan analisis disebabkan oleh:

·         Implementasi instruksi oleh bahasa pemrograman yang berbeda

·         Ketergantungan algoritma terhadap jenis data

·         Ketidakjelasan algoritma yang diimplementasikan

-       Langkah-langkah analisis algoritma

·         Menentukan jenis/sifat data input.

·         Mengidentifikasi abstract operation dari data input.

·         Menganalisis secara matematis untuk menentukan average case atau worst case nya.

NOTASI Big-Oh

adalah fungsi yang lebih berkaitan dengan kelajuan proses daripada kelajuan pertambahan data.

T(n) = O(f(n))

jika ada konstan c dan no sedemikian rupa sehingga

T(n) ≤ c.f(n) untuk n ≥ no

Secara sederhana dikatakan bahwa O(f(n)) dpt dianggap sebagai nilai maksimum dari c.f(n).

Contoh:

Jika f(n) = 2n2 maka T(n) = O(n2)

Jika f(n) = 4n2 + 7n + 3 maka T(n) = O(n2)

Contoh program:

Penghitungan eksekusi:

˚       sum = 0                      dieksekusi 1 kali

˚       i = 0                             dieksekusi 1 kali

˚       i < n                            diekseklusi n kali

˚       i++                               dieksekusi n kali

˚       sum = sum + a[i]       dieksekusi n kali

----------------------

2 + 3n kali

Jadi T(n) = O(n)

Contoh program:

Penghitungan eksekusi:

-       sum = 0                            dieksekusi 1 kali

-       i = 0                                   dieksekusi 1 kali

-       i < n                                  dieksekusi 1 kali

-       i++                                     dieksekusi n kali

-       j = o                                   dieksekusi n kali

-       j < n                                   dieksekusi n × n kali

-       j++                                     dieksekusi n × n kali

-       sum = sum + a[ j ]           dieksekusi n × n kali

---------------------------

3 + 2n + 3n2 kali

• Jika sebagian besar instruksi pada program hanya dieksekusi constant kali.
• Bersifat konstan, tidak bergantung pada parameter atau banyak data yang diolah
• Merupakan algoritma paling ideal

Contoh:

• Waktu eksekusinya sebanding/sama dengan jumlah data.
• Setiap data input hanya diolah secara sederhana. Misal hanya di tambah,

• dikurangi, dikalikan, dan dibagi.
• Inilah kondisi optimal yang dicari dalam membuat algoritma.

Contoh :

• Waktu eksekusi berbading dengan kwadrat jumlah data. Misal:

·         Jika n=10 waktu eksekusinya 100

·         Jika n=20 waktu eksekusinya 400

• Biasanya timbul karena setiap data dieksekusi 2 kali, misal dlm nested loop.

• Contoh : Algoritma Bublesort

Contoh:

• Waktu eksekusi sebanding dengan logaritma dari jumlah data.
• Misal jumlah data menjadi 2 kali semula berarti waktu proses bertama 1 unit, jika 1000 kali bertambah 10 unit, jika sejuta berarti 20 satuan.
• Biasanya untuk algoritma yang memecah masalah besar kedalam sub masalah yang lebih kecil.
• Contoh : Algoritma binary search dan algoritma fungsi rekursif

• Bersifat linieritmis (linier dan logaritmis)
• Untuk algoritma yang memecah masalah besar menjadi sub-masalah yang lebih kecil dan diselesaikan secara terpisah, kemudian hasilnya digabungkan.
• Contoh : Quicksort

Untuk algoritma yang mengolah setiap data input 3 kali. Biasanya berupa 3 buah nested loop.

• Algoritma semacam ini sebisa mungkin dihindari.

Contoh:

• Pada implementasinya, algoritma kadang-kadang memiliki Big-Oh yang merupakan kombinasi dari klasifikasi dasar tersebut.
• Perancangan algoritma yang memiliki Big-Oh baik tetapi rumit tidak selalu menguntungkan apabila jumlah data inputnya hanya sedikit.
• Nilai Big-Oh adalah nilai worst case, sehingga dalam implementasinya biasanya tidak mencapai nilai setinggi itu.

CONTOH DAN ATURAN

1.    For loop (perulangan)

Waktu eksekusi pada for loop, maksimum sebanyak waktu eksekusi statement-statement yang ada di dalam loop dikalikan banyaknya iterasi.

Contoh:

Waktu eksekusi = 2 x n kali

Jadi T(n) = O(n)

2.    Nested for loop (perulangan bersarang)

·         Dianalisis dari loop terdalam kemudian keluar.

·         Waktu eksekusi total sebuah statement adalah waktu eksekusi statement tsb dikalikan hasil kali dari banyaknya iterasi semua loop yang ada diluarnya.

Contoh:

a[i,j] akan dieksekusi sebanyak (m x n) kali.

Jadi T(n) = O(n2)

3.   Consecutive Statement (statement yang berurutan)

·         Untuk statement yang berurutan, waktu eksekusinya adalah jml dari masing-masing statement.

·         Berdasarkan pengertian Big-OH, hal tsb akan diambil nilai yang terbesar.

Contoh:

 Jadi T(n) = T1(n) + T2(n) = O(n2)

4.   if else

Total waktu eksekusi adalah waktu test ditambah waktu yang terbesar dari eksekusi Statemen1 atau Statemen2

Contoh:

Jadi total waktu eksekusi adalah 1 + 10 = 11

Jadi T(n) = O(n)

Read More

Congestion Control

1. Congestion  (kemacetan)

      Congestion bisa diartikan macet atau perlambatan. Maksudnya, congestion merupakan perlambatan yang terjadi pada jalu paket-paket data. Kondisi ini di akibatkan ketika sebuah network yang besar mempunyai beban yang banyak dan mengakibatkan performansi menurun/lambat dengan kata lain jumlah pengiriman data melebihi kapasitas router yang ada. Hal ini dapat di analogikan seperti berikut , ketika kecepatan data dari suatu pengirim lebih tinggi dari pada yang lain maka pengirim yang mempunyai kecepatan lebih rendah mengalami kongesti.

Congestion  pada lalulintas jaringan disebabkan oleh :

1. Terlalu banyak host dalam sebuah broadcast domain. 

Host artinya alat yang terhubung ke jaringan yang bisa menerima dan mengirimkan informasi dari dan ke alat lainnya dalam jaringan tersebut. Broadcast domain adalah kumpulan dari alat-alat di sebuah segmen jaringan yang ( harus ) menerima paket broadcast yang dikirim oleh alat-alat yang lain dalam segmen jaringan tersebut.

2. Broadcast Storm

Terjadi karena semua alat mengirimkan paket broadcast ke seluruh alat-alat yang lain melalui jaringan. Semakin banyak host maka semakin besar broadcat storm.

3. Multicasting

Jika dalam satu jaringan terdapat banyak komputer di mana setiap komputer  mengakses beberapa halaman web bervolume tinggi dalam satu waktu yang sama maka besar kemungkinan akan terjadi Congestion Bandwith yang kecil. Jalur yang kecil akan membuat lalu lintas jaringan akan mudah padat jika di lewati oleh banyak data dalam satu periode.

4. Data Collision

 yaitu tabrakan data. Collision Domain, yaitu suatu kondisi network dimana sebuah alat mengirimkan paket data ke sebuah segmen network, yang kemudian memaksa semua alat lain yang ada di segmen jaringan tersebut untuk memperhatikan paketnya. Pada saat yang bersamaan alat yang berbeda mencoba untuk mengirimkan paket yang lain, yang mengakibatkan tabrakan (collision), paket yang dikirim menjadi rusak akibatnya semua alat harus melakukan pengiriman ulang paket. Sebuah kondisi yang tidak efisien.

5. Bandwith yang kecil

Media jaringan yang mempunya bandwith kecil sehingga tidak seimbang dengan banyaknya lalulintas data yang terjadi sehingga mengakibatkan overload.

Efek  Congestion

1.      Paket data yang tiba langsung disimpan pada buffer  masukan.

2.      Terbentuk routing

3.      Mampu membuang paket

4.      Paket bergerak ke buffer keluaran

5.      paket paket antri untuk dipancarkan keluar.

6.      Mampu menyebarkan congestion melalui jaringan

7.      Paket-paket data tersebut mengkondisikan seperti antrian yang siap untuk menjadi output.

2.  Jaringan   Data

         Jaringan data merupakan sekumpulan jalur  telekomunikasi dan peralatan switching   / pertukaran yang dapat memungkinkan berlangsungnya pengiriman data secara fisik. Tugas dari jaringan data yang terpenting adalah melakukan pertukaran dengan cepat dan benar diantara terminal-terminal dan sistem komputer.

Komponen jaringan data

Host atau node, yaitu sistem komputer yang berfungsi sebagai sumber atau penerima dari data yang dikirimkan. Node ini dapat berupa:

Server : komputer tempat penyimpanan data dan program-program aplikasi yang digunakan dalam                   jaringan,

Client : komputer yang dapat mengakses sumber daya (berupa data dan program aplikasi) yang ada                 pada server,

Shared pheriperal : peralatan-peralatan yang terhubung dan digunakan dalam jaringan (misalnya,                                        printer, scanner, harddisk, modem, dan lain-lain).

Link, adalah media komunikasi yang menghubungkan antara node yang satu dengan node lainnya.                         Media ini dapat berupa saluran transmisi kabel dan tanpa kabel,

Software (Perangkat Lunak), yaitu program yang mengatur dan mengelola jaringan secara keseluruhan. Termasuk di dalamnya sistem operasi jaringan yang berfungsi sebagai pengatur komunikasi data dan periferal dalam jaringan.

3.  Pengendali Kemacetan  / Conggestion Control

Congestion control digunakan untuk menangani terjadinya kemacetan. Terjadinya kemacetan bisa diterangkan lewat uraian berikut. Pada dasarnya, sebuah jaringan packet-switched adalah jaringan antrian. Pada masing-masing node, terdapat sebuah antrian paket yang akan dikirimkan ke kanal tertentu. Apabila kecepatan datangnya suatu paket dalam sebuah antrian lebih besar dibandingkan kecepatan pentransferan paket,maka akan muncul efek bottleneck. Apabila antrian makin panjang dan jumlah node yang menggunakan kanal juga bertambah, maka kemungkinan terjadi kemacetan sangat besar. Permasalahan yang serius yang diakibatkan efek congestion adalah deadlock , yaitu suatu kondisi di mana sekelompok node tidak bisa meneruskan pengiriman paket karena tidak ada buffer yang tersedia.

4.  Cara mengatasi congestion / kemacetan

Salah satu yang menyebabkan congestion adalah kelebihan beban dalam jaringan, dan cara mengatasinya dapat dilakukan dengan dua kemungkinan yaitu :

1. Melakukan segmentasi jaringan.

Karena kita tidak mungkin mengurangi komputer yang harus terkoneksi ke jaringan jadi langkah rasional yang bisa dilakukan adalah membagi beberapa host-host ke dalam beberapa segmen jaringan tersendiri.

2.Menyesuaikan dengan situasi jaringan.

3. Router disisipkan diantara segmen–segmen network

   Router digunakan untuk menghubungkan dua atau lebih network dan bertugas sebagai perantara dalam menyampaikan data antar network. Kita bisa menggunakan jenis router yang dedicated seperti router buatan perusahaan Cisco atau router jenis nondedicated seperti Pc Router (jenis komputer lama yang difungsikan sebagai router dengan menambah interface padanya menjadi dua interface).

Cara lainnya yaitu:

Beberapa teknik berikut dapat digunakan untuk mengatasi Congestion: 

  -   End-system flow control 

Ini bukan skema kontrol kongesti tetapi cara untuk menjaga agar sender tidak mengirimkan paket berlebih kepada receiver.

  -   Network congestion control 

Mekanisme ini hampir sama dengan end-to-end flowcontrol tetapi difokuskanuntuk mengurangi kongesti pada jaringan, bukan pada receiver.

   -   Network-based congestion avoidance

Pada skema ini, router mendeteksi kemungkinan terjadinya kongesti sehingga router  memperkecil paket yang dikirim sebelum antrian menjadi penuh.

Source: http://nurlinaamik.blogspot.com/2014/06/congestion-pada-jaringan-data.html

Read More