Quicksort

June 3, 2010

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 :

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.

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

ALGORITMA

void quickSort(Object array[], int leftIdx, int rightIdx) {

int pivotIdx;

/* Kondisi Terminasi */

if (rightIdx > leftIdx) {

pivotIdx = partition(array, leftIdx, rightIdx);

quickSort(array, leftIdx, pivotIdx-1);

quickSort(array, pivotIdx+1, rightIdx);

}

}

Contoh :

Rangkaian data:

Pilih sebuah elemen yang akan menjadi elemen pivot. Contoh pivot = 3

Inisialisasi elemen kiri sebagai elemen kedua dan elemen kanan sebagai elemen akhir.

Geser elemen kiri kearah kanan sampai ditemukan nilai yang lebih besar dari elemen pivot tersebut dan geser elemen kanan ke arah kiri sampai ditemukan nilai dari elemen yang tidak lebih besar dari elemen tersebut.

Tukarkan antara elemen kiri dan kanan

Geserkan lagi elemen kiri dan kanan.

Tukarkan antar elemen kembali.

Geserkan kembali elemen kiri dan kanan.

Terlihat bahwa titik kanan dan kiri telah digeser sehingga mendapatkan nilai elemenkanan < elemen kiri. Dalam hal ini tukarkan elemen pivot dengan elemen kanan.

Kemudian urutkan elemen sub-rangkaian pada setiap sisi dari elemen pivot.

Advertisements

QUICKSORT

May 31, 2010

Quicksort

Quicksort is a well-known sorting algorithm developed by C. A. R. Hoare that, on average, makes (nlogn) (big O notation) comparisons to sort n items. In the worst case, it makes (n2) comparisons, though if implemented correctly this behavior is rare. Typically, quicksort is significantly faster in practice than other (nlogn) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data, it is possible to make design choices which minimize the probability of requiring quadratic time. Additionally, quicksort tends to make excellent usage of the memory hierarchy, taking perfect advantage of virtual memory and available caches. Coupled with the fact that quicksort is an in-place sort and uses no temporary memory, it is very well suited to modern computer architectures. Quicksort (also known as “partition-exchange sort”) is a comparison sort and, in efficient implementations, is not a stable sort.

History

The quicksort algorithm was developed in 1960 by C. A. R. Hoare while in the Soviet Union, as a visiting student at Moscow State University. At that time, Hoare worked in a project on machine translation for the National Physical Laboratory. He developed the algorithm in order to sort the words to be translated, to make them more easily matched to an already-sorted Russian-to-English dictionary that was stored on magnetic tape.

Algorithm

Quicksort sorts by employing a divide and conquer strategy to divide a list into two sub-lists. Full example of quicksort on a random set of numbers. The boxed element is the pivot. It is always chosen as the last element of the partition.

The steps are:

  1. Pick an element, called a pivot, from the list.
  2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
  3. Recursively sort the sub-list of lesser elements and the sub-list of greater elements.

The base case of the recursion are lists of size zero or one, which are always sorted. The correctness of the partition algorithm is based on the following two arguments:

  • At each iteration, all the elements processed so far are in the desired position: before the pivot if less than or equal to the pivot’s value, after the pivot otherwise (loop invariant).
  • Each iteration leaves one fewer element to be processed (loop variant).

The correctness of the overall algorithm follows from inductive reasoning: for zero or one element, the algorithm leaves the data unchanged; for a larger data set it produces the concatenation of two parts, elements less than or equal to the pivot and elements greater than it, themselves sorted by the recursive hypothesis.

Parallelizations

Like merge sort, quicksort can also be easily parallelized due to its divide-and-conquer nature. Individual in-place partition operations are difficult to parallelize, but once divided, different sections of the list can be sorted in parallel. If we have p processors, we can divide a list of n elements into p sublists in (n) average time, then sort each. Ignoring the (n) preprocessing, this is linear speedup. Given n processors, only (n) time is required overall.

One advantage of parallel quicksort over other parallel sort algorithms is that no synchronization is required. A new thread is started as soon as a sublist is available for it to work on and it does not communicate with other threads. When all threads complete, the sort is done. Other more sophisticated parallel sorting algorithms can achieve even better time bounds. For example, in 1991 David Powers described a parallelized quicksort that can operate in O(logn) time given enough processors by performing partitioning implicitly.

Formal analysis

From the initial description it’s not obvious that quicksort takes (nlogn) time on average. It’s not hard to see that the partition operation, which simply loops over the elements of the array once, uses (n) time. In versions that perform concatenation, this operation is also (n). In the best case, each time we perform a partition we divide the list into two nearly equal pieces. This means each recursive call processes a list of half the size. Consequently, we can make only logn nested calls before we reach a list of size 1. This means that the depth of the call tree is (logn). But no two calls at the same level of the call tree process the same part of the original list; thus, each level of calls needs only (n) time all together (each call has some constant overhead, but since there are only (n) calls at each level, this is subsumed in the (n) factor). The result is that the algorithm uses only (nlogn) time. An alternate approach is to set up a recurrence relation for the T(n) factor, the time needed to sort a list of size n. Because a single quicksort call involves (n) factor work plus two recursive calls on lists of size n / 2 in the best case. The master theorem tells us that T(n) = (nlogn). In fact, it’s not necessary to divide the list this precisely; even if each pivot splits the elements with 99% on one side and 1% on the other (or any other fixed fraction), the call depth is still limited to 100logn, so the total running time is still (nlogn). In the worst case, however, the two sublists have size 1 and n − 1 (for example, if the array consists of the same element by value), and the call tree becomes a linear chain of n nested calls. This is the same relation as for insertion sort and selection sort, and it solves to T(n) = (n2). Given knowledge of which comparisons are performed by the sort, there are adaptive algorithms that are effective at generating worst-case input for quicksort on-the-fly, regardless of the pivot selection strategy.

Randomized quicksort expected complexity

Randomized quicksort has the desirable property that, for any input, it requires only (nlogn) expected time (averaged over all choices of pivots). But what makes random pivots a good choice?

Suppose we sort the list and then divide it into four parts. The two parts in the middle will contain the best pivots; each of them is larger than at least 25% of the elements and smaller than at least 25% of the elements. If we could consistently choose an element from these two middle parts, we would only have to split the list at most 2log2n times before reaching lists of size 1, yielding an (nlogn) algorithm. A random choice will only choose from these middle parts half the time. However, this is good enough. Imagine that you are flipping a coin over and over until you get k heads. Although this could take a long time, on average only 2k flips are required, and the chance that you won’t get k heads after 100k flips is highly improbable. By the same argument, quicksort’s recursion will terminate on average at a call depth of only 2(2log2n). But if its average call depth is (logn), and each level of the call tree processes at most n elements, the total amount of work done on average is the product, (nlogn). Note that the algorithm does not have to verify that the pivot is in the middle half – if we hit it any constant fraction of the times, that is enough for the desired complexity. The outline of a formal proof of the O(nlogn) expected time complexity follows. Assume that there are no duplicates as duplicates could be handled with linear time pre- and post-processing, or considered cases easier than the analyzed. Choosing a pivot, uniformly at random from 0 to n − 1, is then equivalent to choosing the size of one particular partition, uniformly at random from 0 to n − 1. With this observation, the continuation of the proof is analogous to the one given in the average complexity section.

Average complexity

Even if pivots aren’t chosen randomly, quicksort still requires only (nlogn) time over all possible permutations of its input. Because this average is simply the sum of the times over all permutations of the input divided by n factorial, it’s equivalent to choosing a random permutation of the input. When we do this, the pivot choices are essentially random, leading to an algorithm with the same running time as randomized quicksort.

Space complexity

The space used by quicksort depends on the version used.

Quicksort has a space complexity of (logn), even in the worst case, when it is carefully implemented such that

  • in-place partitioning is used. This requires (1).
  • After partitioning, the partition with the fewest elements is (recursively) sorted first, requiring at most (logn) space. Then the other partition is sorted using tail recursion or iteration. (This idea is commonly attributed to R.Sedgewick .

The version of quicksort with in-place partitioning uses only constant additional space before making any recursive call. However, if it has made (logn) nested recursive calls, it needs to store a constant amount of information from each of them. Since the best case makes at most (logn) nested recursive calls, it uses (logn) space. The worst case makes (n) nested recursive calls, and so needs (n) space; Sedgewick’s improved version using tail recursion requires (logn) space in the worst case. We are eliding a small detail here, however. If we consider sorting arbitrarily large lists, we have to keep in mind that our variables like left and right can no longer be considered to occupy constant space; it takes (logn) bits to index into a list of n items. Because we have variables like this in every stack frame, in reality quicksort requires ((logn)2) bits of space in the best and average case and (nlogn) space in the worst case. This isn’t too terrible, though, since if the list contains mostly distinct elements, the list itself will also occupy (nlogn) bits of space.

Selection-based pivoting

A selection algorithm chooses the kth smallest of a list of numbers; this is an easier problem in general than sorting. One simple but effective selection algorithm works nearly in the same manner as quicksort, except that instead of making recursive calls on both sublists, it only makes a single tail-recursive call on the sublist which contains the desired element. This small change lowers the average complexity to linear or (n) time, and makes it an in-place algorithm. A variation on this algorithm brings the worst-case time down to (n) (see selection algorithm for more information). Conversely, once we know a worst-case (n) selection algorithm is available, we can use it to find the ideal pivot (the median) at every step of quicksort, producing a variant with worst-case (nlogn) running time. In practical implementations, however, this variant is considerably slower on average. Another variant is to choose the Median of Medians as the pivot element instead of the median itself for partitioning the elements. While maintaining the asymptotically optimal run time complexity of (nlogn) (by preventing worst case partitions), it is also considerably faster than the variant that chooses the median as pivot.

Variants

There are three well known variants of quicksort:

  • Balanced quicksort: choose a pivot likely to represent the middle of the values to be sorted, and then follow the regular quicksort algorithm.
  • External quicksort: The same as regular quicksort except the pivot is replaced by a buffer. First, read the M/2 first and last elements into the buffer and sort them. Read the next element from the beginning or end to balance writing. If the next element is less than the least of the buffer, write it to available space at the beginning. If greater than the greatest, write it to the end. Otherwise write the greatest or least of the buffer, and put the next element in the buffer. Keep the maximum lower and minimum upper keys written to avoid resorting middle elements that are in order. When done, write the buffer. Recursively sort the smaller partition, and loop to sort the remaining partition.
  • Three-way radix quicksort (also called multikey quicksort): is a combination of radix sort and quicksort. Pick an element from the array (the pivot) and consider the first character (key) of the string (multikey). Partition the remaining elements into three sets: those whose corresponding character is less than, equal to, and greater than the pivot’s character. Recursively sort the “less than” and “greater than” partitions on the same character. Recursively sort the “equal to” partition by the next character (key).

Source : http://en.wikipedia.org/wiki/Quicksort

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

ALGORITMA

void quickSort(Object array[], int leftIdx, int rightIdx) {

int pivotIdx;

/* Kondisi Terminasi */

if (rightIdx > leftIdx) {

pivotIdx = partition(array, leftIdx, rightIdx);

quickSort(array, leftIdx, pivotIdx-1);

quickSort(array, pivotIdx+1, rightIdx);

}

}

Contoh :

Rangkaian data:

3          1          4          1          5          9          2          6          5          3          5          8

Pilih sebuah elemen yang akan menjadi elemen pivot.

Elemen pivot =3

3 1          4          1          5          9          2          6          5          3          5          8

Inisialisasi elemen kiri sebagai elemen kedua dan elemen kanan sebagai elemen akhir.

kiri kanan

3 1          4          1          5          9          2          6          5          3          5          8

Geser elemen kiri kearah kanan sampai ditemukan nilai yang lebih besar dari elemen pivot tersebut. Geser elemen kanan ke arah kiri sampai ditemukan nilai dari elemen yang tidak lebih besar dari elemen tersebut.

kiri kanan

3 1          4          1          5          9          2          6          5          3          5          8

Tukarkan antara elemen kiri dan kanan

kiri kanan

3 1          3          1          5          9          2          6          5          4          5          8

Geserkan lagi elemen kiri dan kanan.

kiri kanan

3 1          3          1          5          9          2          6          5          4          5          8

Tukarkan antar elemen kembali.

Kiri kanan

3 1          3          1          2          9          5          6          5          4          5          8

Geserkan kembali elemen kiri dan kanan.

Kanan kiri

3 1          3          1          2          9          5          6          5          4          5          8

Terlihat bahwa titik kanan dan kiri telah digeser sehingga mendapatkan nilai elemen

kanan < elemen kiri. Dalam hal ini tukarkan elemen pivot dengan elemen kanan.

pivot

2 1          3          1          3 9          5          6          5          4          5          8

Kemudian urutkan elemen sub-rangkaian pada setiap sisi dari elemen pivot.

KOMPUTASI PARALEL

May 25, 2010

Komputasi paralel merupakan salah satu teknik yang digunakan untuk melakukan komputasi secara bersamaan dengan memanfaatkan beberapa mesin komputer independen secara bersamaan. Teknik ini umumnya diperlukan pada saat kapasitas yang diperlukan sangat besar, baik karena harus mengolah data dalam jumlah besar ( dalam industri keuangan, bioinformatika, dll) ataupun karena tuntutan proses komputasi yang banyak. Kasus kedua umum ditemui di kalkulasi numerik untuk menyelesaikan persamaan matematis di bidang fisika (fisika komputasi), kimia (kimia komputasi) dll.

Untuk melakukan aneka jenis komputasi paralel ini diperlukan infrastruktur mesin paralel yang terdiri dari banyak komputer yang dihubungkan dengan jaringan dan mampu bekerja secara paralel untuk menyelesaikan satu masalah. Untuk itu diperlukan aneka perangkat lunak pendukung yang biasa disebut sebagai middleware yang berperan untuk mengatur distribusi pekerjaan antar node dalam satu mesin paralel contohnya adalah openPC. Selanjutnya pemakai harus membuat pemrograman paralel untuk merealisasikan komputasi. Tidak berarti dengan mesin paralel semua program yang dijalankan diatasnya otomatis akan diolah secara paralel.

Pemrograman Paralel

Pemrograman parallel merupakan teknik yang digunakan dalam pemrograman komputer yang memungkinkan eksekusi perintah/operasi dijalankan secara bersamaan (komputasi paralel), baik dalam komputer dengan satu prosesor (tunggal) ataupun banyak prosesor (ganda dengan mesin paralel) CPU.

· Bila komputer yang digunakan secara bersamaan tersebut dilakukan oleh komputer-komputer terpisah yang terhubung dalam suatu jaringan komputer lebih sering istilah yang digunakan adalah sistem terdistribusi (distributed computing).

Tujuan utama dari pemrograman paralel adalah untuk meningkatkan performa komputasi. Semakin banyak hal yang bisa dilakukan secara bersamaan (dalam waktu yang sama), semakin banyak pekerjaan yang bisa diselesaikan. Analogi yang paling gampang adalah, bila anda dapat memasak nasi sambil mencuci piring saat anda akan memasak, waktu yang anda butuhkan akan lebih sedikit dibandingkan bila anda mengerjakan hal tersebut secara berurutan (serial). Atau waktu yg anda butuhkan untuk mencuci piring akan lebih sedikit jika anda dibantu oleh teman anda (2 orang). Performa dalam pemrograman paralel diukur dari berapa banyak peningkatan kecepatan (speed up) yang diperoleh dalam menggunakan teknik paralel. Secara informal, bila anda mencuci piring sendirian membutuhkan waktu 1 jam dan dengan bantuan teman, berdua anda bisa melakukannya dalam 1/2 jam maka anda memperoleh peningkatan kecepatan sebanyak 2 kali.

· Peningkatan Kecepatan

dapat diformulasikan dalam persamaan berikut ini

Keterangan :

T1 adalah waktu yang dibutuhkan untuk menyelesaikan pekerjaan (program komputer) bila dijalankan dalam satu komputer.

Tj adalah waktu yang dibutuhkan jika pekerjaan dikerjakan bersamaan oleh beberapa komputer.

Ada limitasi dalam usaha membuat suatu program komputer berjalan lebih efisien melalui peningkatan kecepatan, hukum yang menetapkan batasan ini dikenal sebagai Hukum Amdahl. Ide dari hukum amdahl ini adalah bahwa anda hanya akan bisa meningkatkan efisiensi program komputer anda, sebatas pada bagian tertentu dari program tersebut yang dapat di paralelkan. Sementara bagian yang memang harus dilaksanakan secara berurutan, akan menjadi penentu performa akhir. Kembali ke analogi memasak tadi, bila anda harus menggunakan sarung tangan sebelum menyalakan kompor ataupun mencuci piring, maka waktu yang anda butuhkan untuk memakai sarung tangan ini adalah waktu serial, yang tidak dapat dihindari. Sementara waktu untuk memasak dan mencuci piring tadi adalah bagian yang bisa diparalelkan.

Hukum Amdahl

Telah dijelaskan bahwa dari T1 (waktu yg dibutuhkan menjalankan pekerjaan dalam satu komputer) tadi, ada sebagian yg tidak bisa diparalelkan. Untuk menyatakan ini kita gunakan notasi α dimana menunjukkan berapa bagian dari T1 yang tidak bisa dijadikan paralel (atau bagian serial dari program ini).

· Maka kita ketahui α * T1 adalah waktu yg tidak akan terpengaruh oleh bertambahnya komputer yg digunakan. α * T1 dilambangkan sebagai persamaan (a)

· Sisanya (1 − α) * T1 adalah waktu yang akan berkurang menjadi bila kita menggunakan N komputer tambahan (b) .

Sehingga waktu total yang dibutuhkan untuk menjalankan pekerjaan dalam N komputer adalah (a) + (b) alias :

Peningkatan kecepatan yang kita peroleh dari persamaan ini adalah :

Dari hasil diatas, didapat persamaan speed up yang terlihat berbeda tapi pada dasarnya sama. Persamaan dibawah, bisa didapat dari persamaan diatas, dengan mengeliminasi komponen T1 (pada bagian atas dan bawah persamaan), lalu mengatur N dan α


Dari persamaan di atas, bisa dilihat bahwa jika kita menggunakan komputer yang amat banyak () komponen (b) akan dapat diabaikan, menyisakan persamaan :

Inilah batas maksimum peningkatan kecepatan yang bisa dicapai menurut hukum Amdahl yaitu perbandingan terbalik dari seberapa banyak bagian serial dari suatu pekerjaan. Dalam sistem terdistribusi dimana anda berusaha menggunakan lebih banyak prosesor untuk menyelesaikan masalah, akan ada imbal balik. Menggunakan komputer tambahan dari lokasi yang berbeda memberikan anda sumber komputasi baru, tapi juga melibatkan biaya komunikasi tambahan, saat anda harus memberikan pekerjaan tersebut pada komputer yg terpisah.

Bahasa populer dalam Pemrograman Paralel

· MPI Message Passing Interface, bahasa pemrograman dengan basis pertukaran pesan.

· PVM Parallel Virtual machine.

Istilah-istilah dalam pemrograman paralel

1. Embarasingly Parallel adalah pemrograman paralel yang digunakan pada masalah-masalah yang bisa diparalelkan tanpa membutuhkan komunikasi satu sama lain. Sebenarnya pemrograman ini bisa dibilang sebagai pemrograman paralel yang ideal, karena tanpa biaya komunikasi, lebih banyak peningkatan kecepatan yang bisa dicapai.

2. Taksonomi dari model pemrosesan paralel dibuat berdasarkan alur instruksi dan alur data yang digunakan:

SISD (Single Instruction Single Datapath) merupakan prosesor tunggal, yang bukan paralel.

SIMD (Single Instruction Multiple Datapath) alur instruksi yang sama dijalankan terhadap banyak alur data yang berbeda. Alur instruksi di sini kalau tidak salah maksudnya ya program komputer itu. trus datapath itu paling ya inputnya, jadi inputnya lain-lain tapi program yang digunakan sama.

MIMD (Multiple Instruction Multiple Datapath) alur instruksinya banyak, alur datanya juga banyak, tapi masing-masing bisa berinteraksi.

MISD (Multiple Instruction Single Datapath) alur instruksinya banyak tapi beroperasi pada data yang sama.

Komputasi paralel merupakan salah satu teknik yang digunakan untuk melakukan komputasi secara bersamaan dengan memanfaatkan beberapa mesin komputer independen secara bersamaan. Teknik ini umumnya diperlukan pada saat kapasitas yang diperlukan sangat besar, baik karena harus mengolah data dalam jumlah besar ( dalam industri keuangan, bioinformatika, dll) ataupun karena tuntutan proses komputasi yang banyak. Kasus kedua umum ditemui di kalkulasi numerik untuk menyelesaikan persamaan matematis di bidang fisika (fisika komputasi), kimia (kimia komputasi) dll.

Untuk melakukan aneka jenis komputasi paralel ini diperlukan infrastruktur mesin paralel yang terdiri dari banyak komputer yang dihubungkan dengan jaringan dan mampu bekerja secara paralel untuk menyelesaikan satu masalah. Untuk itu diperlukan aneka perangkat lunak pendukung yang biasa disebut sebagai middleware yang berperan untuk mengatur distribusi pekerjaan antar node dalam satu mesin paralel contohnya adalah openPC. Selanjutnya pemakai harus membuat pemrograman paralel untuk merealisasikan komputasi. Tidak berarti dengan mesin paralel semua program yang dijalankan diatasnya otomatis akan diolah secara paralel.

Pemrograman Paralel

Pemrograman parallel merupakan teknik yang digunakan dalam pemrograman komputer yang memungkinkan eksekusi perintah/operasi dijalankan secara bersamaan (komputasi paralel), baik dalam komputer dengan satu prosesor (tunggal) ataupun banyak prosesor (ganda dengan mesin paralel) CPU.

· Bila komputer yang digunakan secara bersamaan tersebut dilakukan oleh komputer-komputer terpisah yang terhubung dalam suatu jaringan komputer lebih sering istilah yang digunakan adalah sistem terdistribusi (distributed computing).

Tujuan utama dari pemrograman paralel adalah untuk meningkatkan performa komputasi. Semakin banyak hal yang bisa dilakukan secara bersamaan (dalam waktu yang sama), semakin banyak pekerjaan yang bisa diselesaikan. Analogi yang paling gampang adalah, bila anda dapat memasak nasi sambil mencuci piring saat anda akan memasak, waktu yang anda butuhkan akan lebih sedikit dibandingkan bila anda mengerjakan hal tersebut secara berurutan (serial). Atau waktu yg anda butuhkan untuk mencuci piring akan lebih sedikit jika anda dibantu oleh teman anda (2 orang). Performa dalam pemrograman paralel diukur dari berapa banyak peningkatan kecepatan (speed up) yang diperoleh dalam menggunakan teknik paralel. Secara informal, bila anda mencuci piring sendirian membutuhkan waktu 1 jam dan dengan bantuan teman, berdua anda bisa melakukannya dalam 1/2 jam maka anda memperoleh peningkatan kecepatan sebanyak 2 kali.

· Peningkatan Kecepatan

dapat diformulasikan dalam persamaan berikut ini

 S = \frac{T_1}{T_j}

Keterangan :

T1 adalah waktu yang dibutuhkan untuk menyelesaikan pekerjaan (program komputer) bila dijalankan dalam satu komputer.

Tj adalah waktu yang dibutuhkan jika pekerjaan dikerjakan bersamaan oleh beberapa komputer.

Ada limitasi dalam usaha membuat suatu program komputer berjalan lebih efisien melalui peningkatan kecepatan, hukum yang menetapkan batasan ini dikenal sebagai Hukum Amdahl. Ide dari hukum amdahl ini adalah bahwa anda hanya akan bisa meningkatkan efisiensi program komputer anda, sebatas pada bagian tertentu dari program tersebut yang dapat di paralelkan. Sementara bagian yang memang harus dilaksanakan secara berurutan, akan menjadi penentu performa akhir. Kembali ke analogi memasak tadi, bila anda harus menggunakan sarung tangan sebelum menyalakan kompor ataupun mencuci piring, maka waktu yang anda butuhkan untuk memakai sarung tangan ini adalah waktu serial, yang tidak dapat dihindari. Sementara waktu untuk memasak dan mencuci piring tadi adalah bagian yang bisa diparalelkan.

Hukum Amdahl

Telah dijelaskan bahwa dari T1 (waktu yg dibutuhkan menjalankan pekerjaan dalam satu komputer) tadi, ada sebagian yg tidak bisa diparalelkan. Untuk menyatakan ini kita gunakan notasi α dimana   0 \le \alpha \le 1 menunjukkan berapa bagian dari T1 yang tidak bisa dijadikan paralel (atau bagian serial dari program ini).

· Maka kita ketahui α * T1 adalah waktu yg tidak akan terpengaruh oleh bertambahnya komputer yg digunakan. α * T1 dilambangkan sebagai persamaan (a)

· Sisanya (1 − α) * T1 adalah waktu yang akan berkurang menjadi  \frac  {(1 - \alpha) * T_1} {N} bila kita menggunakan N komputer tambahan (b) .

Sehingga waktu total yang dibutuhkan untuk menjalankan pekerjaan dalam N komputer adalah (a) + (b) alias :

 T_N = \alpha * T_1 + \frac {(1 - \alpha) *  T_1} {N}

Peningkatan kecepatan yang kita peroleh dari persamaan ini adalah :

 S_N = \frac{T_1}{\alpha * T_1 + \frac {(1 -  \alpha) * T_1}{N}}

Dari hasil diatas, didapat persamaan speed up yang terlihat berbeda tapi pada dasarnya sama. Persamaan dibawah, bisa didapat dari persamaan diatas, dengan mengeliminasi komponen T1 (pada bagian atas dan bawah persamaan), lalu mengatur N dan α

 S_N = \frac{N}{1 +  \alpha(N-1)}

Dari persamaan di atas, bisa dilihat bahwa jika kita menggunakan komputer yang amat banyak ( N  \rightarrow \infty ) komponen (b) akan dapat diabaikan, menyisakan persamaan :

 S_N = \frac{1}{\alpha}

Inilah batas maksimum peningkatan kecepatan yang bisa dicapai menurut hukum Amdahl yaitu perbandingan terbalik dari seberapa banyak bagian serial dari suatu pekerjaan. Dalam sistem terdistribusi dimana anda berusaha menggunakan lebih banyak prosesor untuk menyelesaikan masalah, akan ada imbal balik. Menggunakan komputer tambahan dari lokasi yang berbeda memberikan anda sumber komputasi baru, tapi juga melibatkan biaya komunikasi tambahan, saat anda harus memberikan pekerjaan tersebut pada komputer yg terpisah.

Bahasa populer dalam Pemrograman Paralel

· MPI Message Passing Interface, bahasa pemrograman dengan basis pertukaran pesan.

· PVM Parallel Virtual machine.

Istilah-istilah dalam pemrograman paralel

1. Embarasingly Parallel adalah pemrograman paralel yang digunakan pada masalah-masalah yang bisa diparalelkan tanpa membutuhkan komunikasi satu sama lain. Sebenarnya pemrograman ini bisa dibilang sebagai pemrograman paralel yang ideal, karena tanpa biaya komunikasi, lebih banyak peningkatan kecepatan yang bisa dicapai.

2. Taksonomi dari model pemrosesan paralel dibuat berdasarkan alur instruksi dan alur data yang digunakan:

SISD (Single Instruction Single Datapath) merupakan prosesor tunggal, yang bukan paralel.

SIMD (Single Instruction Multiple Datapath) alur instruksi yang sama dijalankan terhadap banyak alur data yang berbeda. Alur instruksi di sini kalau tidak salah maksudnya ya program komputer itu. trus datapath itu paling ya inputnya, jadi inputnya lain-lain tapi program yang digunakan sama.

MIMD (Multiple Instruction Multiple Datapath) alur instruksinya banyak, alur datanya juga banyak, tapi masing-masing bisa berinteraksi.

MISD (Multiple Instruction Single Datapath) alur instruksinya banyak tapi beroperasi pada data yang sama.

STRATEGI MERANCANG SECURITY JARINGAN

October 23, 2009

STRATEGI MERANCANG SECURITY JARINGAN

Dalam zaman yang modern ini dunia internet semakin berkembang mengikuti perkembangan zaman. Sejalan dengan perkembangan tersebut semakin meningkat juga jumlah para hacker, cracker dan semua orang yang melakukan perbuatan yang dianggap bisa merusak sistem jaringan kita. Untuk itu diperlukan strategi yang mampu melindungi semua system yang ada dari pengrusakan yang tidak diinginkan, sehingga user dapat merasakan kenyamanan dalam menjalankan setiap kegiatan didalam system jaringan.

Berikut ini saya hanya akan membahas 3 strategi dari berbagai macam strategi dasar yang ada dalam merancang security jaringan komputer. Strategi dasar ini bisa dijadikan basis untuk penerapan hingga pengembangan security system.

Strategi dasar tersebut adalah :

  1. Perlindungan terhadap Hak Akses

  2. Strategi “Satu jalur masuk”

  3. Stub Sub-Network

1.Perlindungan terhadap Hak Akses

Hak akses merupakan hak yang diberikan kepada user untuk mengakses seluruh kegiatan yang ada didalam sistem. Dalam strategi security ini, setiap objek dalam sistem (user, administrator, software, dan sistem itu sendiri) harus diberikan hak akses yang berguna untuk menunjang fungsi kerja dari objek tersebut. Dengan kata lain, objek hanya memperoleh hak akses minimum. Dengan demikian, aksi objek terhadap sistem dapat dibatasi sehingga objek tidak akan melakukan hal-hal yang membahayakan sekuriti jaringan komputer. Hak akses minimum akan membuat para penyusup dari sebuah jaringan tidak dapat berbuat banyak saat berhasil menembus sebuah user account pada sistem jaringan komputer. Selain itu, hak akses minimum juga mengurangi bahaya ”musuh dalam selimut” dalam arti salah satu orang yang mengendalikan sistem yang mengancam sistem dari dalam. Itulah beberapa keuntungan yang dapat diperoleh dari strategi ini.

Sedangkan kerugian dari penggunaan strategi hak akses ini adalah keterbatasan akses yang dimiliki setiap user sehingga dapat menimbulkan ketidaknyamanan menjalankan tugasnya sebagai sebagai seorang user. Penyelesaian masalah ini bergantung kepada dua hal yaitu segi perangkat dan segi administrator jaringan dan keduanya saling terikat. Seorang administrator jaringan harus pandai-pandai menyiasati rancangan hak akses yang akan diberikan kepada user agar kebutuhan user dapat terpenuhi tanpa harus mengorbankan tingkat sekuriti. Bila perangkat yang dijalankan memiliki keluwesan dalam hal setting, hal ini akan memudahkan tugas administrator. Bila tidak, administrator harus memutar otak untuk menyiasatinya. Bila usaha tersebut telah maksimal dan hasilnya tetap tidak seperti yang diharapkan, ada dua pilihan yang bisa dilakukan yaitu mengganti perangkat atau memberikan pengertian kepada user akan keterbatasan yang ada. Mengapa kebutuhan user menjadi begitu penting? Kebutuhan user yang tidak terpenuhi akan dapat menimbulkan efek-efek yang kadangkala sulit diprediksi. Ia mungkin dapat berubah dari user biasa menjadi “musuh dalam selimut”.

2. Satu Jalur Masuk

Strategi satu jalur masuk merupakan strategi yang menggunakan hanya satu jalan masuk menuju jaringan komputer yang kita miliki. Dengan demikian, hanya satu jalan yang perlu kita awasi dengan ketat. Strategi ini mirip dengan membuat benteng. Benteng yang dibangun biasanya hanya akan memiliki sebuah pintu masuk dimana ditempatkan pengawasan yang paling ketat. Inti dari strategi ini adalah pengawasan terpusat. Kita bisa mencurahkan sebagian besar daya pengawasan ke titik tersebut sehingga penyusup akan kesulitan menembus jalur tersebut. Tentunya strategi ini akan gagal apabila kita memiliki jalur masuk lain. Jika kita ingin menerapkan strategi ini sepenuhnya, usahakan tidak ada jalur masuk lain selain yang akan kita awasi ketat.

Kelemahan strategi ini adalah bila jalur masuk tersebut berhasil ditembus oleh para penyusup, ia akan langsung mengobrak-abrik jaringan komputer kita. Resiko ini dapat dikurangi dengan membuat pertahanan jalur menjadi berlapis-lapis sehingga memaksa para penyusup untuk menghentikan aksinya.

Stub Sub-Network

Stub sub-network adalah sub-jaringan komputer yang hanya memiliki satu jalur keluar masuk sub-jaringan tersebut. Strategi ini merupakan strategi yang mirip dengan strategi satu jalur masuk, hanya saja strategi ini menggunakan perangkat tambahan yaitu router yang menggunakan pengaturan keamanan jaringan. Strategi ini digunakan untuk mengisolasi sub-jaringan komputer yang benar-benar memerlukan perlindungan maksimal. Jalur keluar-masuk sub-jaringan tersebut diawasi dengan (bila perlu) lebih ketat daripada strategi satu jalur masuk. Contohnya, data-data rahasia perusahaan yang tersimpan dalam sebuah komputer perlu diakses secara langsung oleh beberapa bagian tertentu. Solusinya tentu saja jaringan komputer. Tetapi salah satu bagian tersebut memerlukan hubungan ke jaringan komputer perusahaan yang telah terhubung ke Internet tanpa harus pindah komputer. Nah, di sinilah strategi stub sub-network diperlukan. Jaringan pengakses data rahasia dirancang hanya memiliki satu jalur masuk melalui komputer yang memiliki akses Internet tersebut. Pengawasan lalu lintas data yang melalui komputer tersebut harus dipantau dengan baik dan dapat pula diberlakukan sistem packet filtering pada komputer tersebut.

Itulah beberapa strategi dasar yang dapat diterapkan dalam system jaringan yang kita gunakan. Apapun strategi security jaringan yang kita gunakan, tujuan utamanya adalah membuat para penyusup (hacker, cracker, phreaker, dlsb) “berpikir seribu kali” sebelum menjalankan aksi mereka terhadap sistem jaringan komputer kita. Apabila mereka tetap nekat mencoba, kita hadapkan mereka kepada rintangan dan hambatan yang memerlukan daya upaya yang sangat besar untuk menembus sistem kita sampai mereka menghentikan aksinya.

KOMPRESI AUDIO

October 23, 2009

KOMPRESI AUDIO

Kompresi audio adalah salah satu bentuk kompresi data yang bertujuan untuk mengecilkan ukuran file audio dengan metode :

Lossy : format : MP3;

Loseless : format : FLAC; pengguna : audio engineer, audiophiles

Kompresi dilakukan pada saat pembuatan file audio dan pada saat distribusi file audio tersebut!

Kendala kompresi audio:

• Perkembangan sound recording yang cepat dan beranekaragam

• Nilai dari audio sample berubah dengan cepat

Losless audio codec tidak mempunyai masalah dalam kualitas suara, penggunaannya dapat difokuskan pada:

• Kecepatan kompresi dan dekompresi

• Derajat kompresi

• Dukungan hardware dan software

Lossy audio codec penggunaannya difokuskan pada:

• Kualitas audio

• Faktor kompresi

• Kecepatan kompresi dan dekompresi

• Inherent latency of algorithm (penting bagi real-time streaming)

• Dukungan hardware dan software

Metode Kompresi Audio

  • Metode Transformasi

Menggunakan algoritma seperti MDCT (Modified Discreate Cosine Transform) untuk mengkonversikan gelombang bunyi ke dalam sinyal digital agar tetap dapat didengar oleh manusia (20 Hz s/d 20kHz) , yaitu menjadi frekuensi 2 s/d 4kHz dan 96 dB.

  • Metode Waktu

Menggunakan LPC (Linier Predictive Coding) yaitu digunakan untuk speech (pidato), dimana LPC akan menyesuaikan sinyal data pada suara manusia, kemudian mengirimkannya ke pendengar. Jadi seperti layaknya komputer yang berbicara dengan bahasa manusia dengan kecepatan 2,4 kbps

Kompresi Audio MP3

Asal-usul MP3 dimulai dari penelitian IIS-FHG (Institut Integriette Schaltungen-Fraunhofer Gesellschaft), sebuah lembaga penelitian terapan di Munich, Jerman dalam penelitian coding audio perceptual. – Penelitian tersebut menghasilkan suatu algoritma yang menjadi standard sebagai ISO-MPEG Audio Layer-3 (MP3)

Format Header MP3

File MP3 terdiri atas 2 bagian data:

  • Header : berfungsi sebagai tanda pengenal bagi file MP3 agar dapat dibaca oleh MP3 player yang berukuran 4 byte Beberapa karakteristik yang dibaca komputer adalah bit ID, bit layer, bit sampling frequency dan bit mode.

  • Data audio : berisi data file mp3.

Teknik kompresi MP3

Beberapa karakteristik dari MP3 memanfaatkan kelemahan pendengaran manusia.

1. Model psikoakustik

– Model psikoakustik adalah model yang menggambarkan karakteristik pendengaran manusia.

– Salah satu karakteristik pendengaran manusia adalah memiliki batas frekuensi 20 Hz s/d 20 kHz, dimana suara yang memiliki frekuensi yang berada di bawah ambang batas ini tidak dapat didengar oleh manusia, sehingga suara seperti itu tidak perlu dikodekan.

2. Auditory masking

Manusia tidak mampu mendengarkan suara pada frekuensi tertentu dengan amplitudo tertentu jika pada frekuensi di dekatnya terdapat suara dengan amplitudo yang jauh lebih tinggi.

3. Critical band

merupakan daerah frekuensi tertentu dimana pendengaran manusia lebih peka pada frekuensi-frekuensi rendah, sehingga alokasi bit dan alokasi sub-band pada filter critical band lebih banyak dibandingkan frekuensi lebih tinggi.

4. Join Stereo

Terkadang dual channel stereo mengirimkan informasi yang sama. Dengan menggunakan joint stereo, informasi yang sama ini cukup ditempatkan dalam salah satu channel saja dan ditambah dengan informasi tertentu. Dengan teknik ini bitrate dapat diperkecil.

Beberapa persyaratan dari suatu encoder/decoder MP3:

  • Ukuran file terkompresi harus sekecil mungkin

  • Kualitas suara file yang telah terkompresi haruslah sedekat mungkin dengan file asli yang belum dikompresi

  • Tingkat kesulitan rendah, sehingga dapat direalisasikan dengan aplikasi yang mudah dibuat dan perangkat keras yang ‘sederhana’ dengan konsumsi daya yang rendah

Filter Bank merupakan kumpulan filter yangberfungsi memfilter masukan pada frekuensi tertentu, sesuai dengan critical band yang telah didefinisikan. Filter yang dipakai adalah gabungan dari filter bank polyphase dan Modified Discrete Cosine Transform (MDCT)

Perceptual model, dapat menggunakan filter bank terpisah atau penggabungan antara perhitungan nilai energi dan filter bank utama. Keluaran model ini adalah nilai masking treshold. Apabila noise berada dibawah masking treshold, maka hasil kompresi tidak akan dapat dibedakan dari sinyal aslinya.

Quantization/Coding, merupakan proses kuantisasi setelah sinyal disampling. Proses ini dilakukan oleh power-law quantizer, yang memiliki sifat mengkodekan amplitudo besar dengan ketepatan rendah dan dimasukkannya proses noise shaping. Setelah itu nilai yang telah dikuantisasi dikodekan menggunakan Huffman Coding.

Encoding Bitstream, merupakan tahap terakhir dimana bit-bit hasil pengkodean sampling sinyal disusun menjadi sebuah bitstream.

TENSES

October 23, 2009

Simple Present Tense
kebiasaan setiap hari yang waktunya spesifik
Rumus
(he, she, it) + V1 + s/es………….(+)
(I, you, we, they) + V1………….(+)
do (1, you, we, they) + V1………(?)
Does (he, she, it) + V1………….(?)
(I, you, we, they) do not + V1….(-)
(he, she, it) does not + V1……..(-)

Present Progressive Tense
Kegiatan yang membutuhkan durasi waktu (saat ini)
Rumus :
I am + V-ing………………………(+)
(we, you, they) are + V-ing……..(+)
(He, she, it) is + V-ing…………..(+)
Am I + V-ing………………………(-)
Are (you, they, we) + V-ing……..(-)
Is (he, she, it) + V-ing……………(-)
I am not + V-ing …………………(-)
(we, they, you) are not + V-ing…(-)
(he, she, it) is not + V-ing………(-)

Example : Simple Present and Present Progressive
We …… (eat) dinner at seven o’clock tonight. Answer : (are eating)
They …… (drive) to school tomorrow. Answer : (are driving)
Maria …… (have) a cold. Answer : (has)
Jorge …… (swim) right now. Answer : (is swimming)
Jerry …… (mow) the lawn now. Answer : (is mowing)
Something …… (smell) Very good. Answer : (smells)
He …… (practice) the piano every day. Answer : (practices)
I …… (believe) you. Answer : (believe)
John …… (hate) smoke. Answer : (hates)
Jill always …… (get) up at 6:0 am. Answer : (gets)

Simple Past Tense
kegiatan yang terjadi pada masa lampau (waktunya spesifik)
Rumus :
Did (person) + V1………(?)
(person) did not + V1…..(-)

Past Progressive Tense
kegiatan yang sedang terjadi pada masa lampau tapi tiba – tiba diselingi dengan kejadian lagi (menggunakan When)
bila kegiatan tersebut terjadi secara bersamaan menggunaan kata penghubung while.
Rumus
(I, he, she, it) was + V-ing……(+)
(you, we, they) were + V-ing…(+)
was (I, he, she, it) + V-ing…….(?)
were (you, we, they) + V-ing….(?)
(I, he, she, it) was not + V-ing…(-)
(you, we, they) were not + V-ing..(-)

Example : Simple Past and Past Progressive
Gene ……(eat) dinner when his friend called. Answer : (was eating)
While Maria was cleaning the apartment, her husband ……(sleep). Answer : (was sleeping)
At three o’clock this morning, Elennor ……(study). Answer : (was studying)
When Mark arrived, the Johnsons …… (have) dinner, but they stopped in order to talk to him. Answer : (were having)
John …… (go) to France last year. Answer : (went)
When the teacher …… (enter) the room, the student were talking. Answer : (enter)
While Joan was writing the report, Henry …… (look) for more information. Answer : (was looking)
We …… (see) this movie last right. Answer : (saw)
At one time, Mr.Roberts …… (own) this building. Answer : (owned)
Jose …… (writer) a letter to his family where his pencil …… (broke). Answer : (broke)

Present Perfect Tense
Kejadian di masa lampau yang masih berlangsung hingga sekarang
Kejadian di masa lampau yang tidak jelas waktunya.
Kejadian di masa lampau yang terjadi lebih dari 1 (satu) kali.
Rumus :
(I, you, we, they) have + V3………(+)
(he, she, it) has + V3………………(+)
Have (I, you, we, they) + V3……..(?)
Has (he, she, it) + V3……………..(?)
(I, you, we, they) have not + V3…(-)
(he, she, it) has not + V3………….(-)

Example : Present Perfect and Past Tense
John …… (write) his report last night. Answer : (wrote)
Bob …… (see) this movie before. Answer : (has seen)
Jorge …… (read) the newspaper already. Answer : (has read)
Mr.Johnsons …… (work) in the same place for thirty – five years and he not planning to retire yet. Answer : (has work)
We …… (begin / negative) to study for the last yet. Answer : (aren’t begun)
George …… (go) to the store at ten o’clock this morning. Answer : (went)
Joan …… (travel) around the world. Answer : (has travel)
Betty …… (write) a letter last night. Answer : (wrote)
Guillermo …… (call) his employer yesterday. Answer : (called)
We …… (see/negative) this movie yet. Answer : (haven’t seen)

hello

October 20, 2009

Baru belajar bwt blog ney…,

Biar GO-BLOG …..,

hahaha…..,

Hello world!

October 16, 2009

Welcome to WordPress.com. This is your first post. Edit or delete it and start blogging!