Selasa, 14 April 2009

PENGERTIAN DASAR

LOGIKA DAN ALGORITMA

Diperkenalkan Oleh Ahli atematika : Abu Ja’far Muhammad Ibnu Musa Al Khawarizmi

DEFINISI ALGORITMA

1. Langkah-langkah yang dilakukan agar solusi masalah dapat diperoleh
2. Suatu prosedur yang merupakan urutan langkah-langkah yang terintegrasi
3. Suatu metode khusus yang digunakan untuk menyelesaikan suatu masalah yang nyata

Kriteria pemilihan Algoritma
1. Ada output
2. Efektifitas dan Efesiensi
3. Jumlah langkahnya berhingga
4. Berakhir
5. Terstruktur

“Suatu Algoritma yang terbaik yaitu Algoritma yang menghasilkan output yang tepat guna (efektif) dalam waktu yang relatif singkat dan penggunaan memori yang relatif sedikit (efisien) dengan langkah yang berhingga dan prosedurnya berakhir baik dalam keadaan diperoleh suatu solusi ataupun tidak adanya solusi “

Tahapan Analisa Algoritma

1. Merencanakan Algoritma

2. Menyatakan Algoritma

a. Bahasa semu/ sehari-hari (pseucode)
b. Diagram Alur / Flowchart
c. Statement/ penggalan program

3. Validitas Algoritma

4. Menganalisa Algoritma

a. Waktu Tempuh/ Running Time

i. Banyaknya langkah
ii. Bear dab jenis input data
iii. Jenis operasi
iv. Komputer dan kompilator

b. Jumlah memori yang digunakan

5. Menguji Algoritma

a. Fase Debugging
b. Fase Profillig

Sifat-sifat Algoritma

1. Banyaknya langkah intruksi harus berhingga
2. Langkah atau intruksi harus jelas
3. Proses harus jelas dan mempunyai batasan
4. Input dan Output harus mempunyai batasan
5. Efektifitas
6. Adanya bataan ruang lingkup.


Pada algoritma klasik, diterapkan teknik enkripsi konvensional (simetris). Algoritma ini merupakan algoritma kriptografi yang biasa digunakan orang sejak berabad-abad yang lalu. Dua teknik dasar yang biasa digunakan, yaitu : [KUR04]
1. Teknik Subsitusi
2. Teknik Transposisi

1. Teknik Subsitusi
Subsitusi adalah penggantian setiap karakter plaintext dengan karakter lain. Beberapa istilah yang mungkin perlu diingat adalah : [KUR04]
a. Monoalfabet : Setiap karakter ciphertext mengganti satu macam karakter plaintext tertentu.
b. Polyalfabet : Setiap karakter ciphertext dapat mengganti lebih dari satu karakter plaintext.
c. Monograf / unilateral : Satu enkripsi dilakukan terhadap satu karakter plaintext.
d. Polygraf / multilateral : Satu enkripsi dilakukan terhadap lebih dari satu karakter plaintext sekaligus.
Cipher subsitusi paling tua yang dikenal adalah subsitusi yang dilakukan Julius Caesar. Beberapa teknik subsitusi yang pernah dilakukan, antara lain : [KUR04]
a. Subsitusi deret campuran kata kunci yaitu subsitusi yang kata kuncinya didapat dari mengumpulkan karakter yang sama dari sebuah plaintext dan pada ciphertextnya ditambahkan semua sisa karakter dalam abjad.
b.bSubsitusi monomer-dinome-trinome. Monome berarti setiap satu karakter plaintext akan disubsitusi oleh satu karakter ciphertext, dinome disubsitusi dua karakter ciphertext, tridome disubsitusi tiga karakter ciphertext. Jadi sistem ini adalah campuran dari ketiga sistem dasar.
c. Subsitusi multilateral variant. Subsitusi ini masih termasuk jenis monoalfabet yang dalam mensubsitusi memanfaatkan huruf abjad a,b,c,…,z yang disusun dalam matrik 5 X 5.
d. Subsitusi digrafik. Pada sistem ini, setiap huruf plaintext akan disubsitusi oleh dua huruf ciphertext. Pola huruf cipher text diambil dari sebuah matrik 26 X 26 yang berasal dari 26 abjad yang memiliki pola khusus.
e. Subsitusi persegi panjang. Sistem digrafik terlalu memerlukan matrik yang besar. Untuk memperkecil matrik dengan keamanan yang setara dapat digunakan sistem empat persegi.
f. Subsitusi kode playfair. Kode rahasia multi huruf yang paling terkenal adalah playfair. Playfair menggunakan 676 digraf. Selama waktu yang lama, kode ini dianggap tak dapat dipecahkan. Playfair dijadikan sistem standar oleh tentara Inggris dalam PD I dan masih digunakan secara luas oleh tentara Amerika dan sekutu selama PD II. Sistem ini menggunakan matrik 5 X 5.
g. Subsitusi Polialfabet periodik. Dalam sistem polialfabet, setiap ciphertext dapat memiliki banyak kemungkinan plaintext. Dan sistem periodik itu sendiri dikarenakan adanya kunci yang berulang. Jenis polialfabet klasik yang terkenal adalah Vigenere.
h. Enigma. Merupakan mesin kriptografi yang digunakan oleh tentara NAZI Hitler pada masa PD II. Mesin ini menggunakan rotor. Enigma menggunakan tiga rotor untuk melakukan subsitusi. Tiga rotor berarti tiga kali subsitusi.

2. Teknik Transposisi ( Permutasi )
Beberapa model kriptografi yang menggunakan teknik transposisi, antara lain : [KUR04]
1. Algoritma transposisi kolom dengan kunci numerik. Teknik ini menggunakan permutasi karakter. Kunci dapat diperoleh dari kata yang mudah dibaca dan kemudian dikodekan menjadi bilangan.
2. Masukan plaintext pola zig-zag, keluaran ciphertext berupa baris.
3. Masukan pola segitiga, keluaran berupa kolom, dibaca dari atas kebawah.
4. Masukan berpola spiral, dari luar kedalam, keluaran berupa kolom dibaca dari atas ke bawah.
5. Dimasukan secara diagonal dari kiri bawah ke kanan atas, keluaran baris.
6. Masukan spiral dari dalam ke luar, keluaran diagonal bergantian.
Kombinasi subsitusi dan transposisi yang komplek menjadi dasar pembentukan algoritma-algoritma kriptografi modern. Salah satu algoritma klasik yang menggunakan kedua teknik ini adalah VIC yang tidak memerlukan komputer dalam penggunaannya.

Diagram Alur sering digunakan untuk menggambarkan sebuah algoritma.

Dalam matematika dan komputasi, algoritma merupakan kumpulan perintah untuk menyelesaikan suatu masalah. Perintah-perintah ini dapat diterjemahkan secara bertahap dari awal hingga akhir. Masalah tersebut dapat berupa apa saja, dengan catatan untuk setiap masalah, ada kriteria kondisi awal yang harus dipenuhi sebelum menjalankan algoritma. Algoritma akan dapat selalu berakhir untuk semua kondisi awal yang memenuhi kriteria, dalam hal ini berbeda dengan heuristik. Algoritma sering mempunyai langkah pengulangan (iterasi) atau memerlukan keputusan (logika Boolean dan perbandingan) sampai tugasnya selesai.

Desain dan analisis algoritma adalah suatu cabang khusus dalam ilmu komputer yang mempelajari karakteristik dan performa dari suatu algoritma dalam menyelesaikan masalah, terlepas dari implementasi algoritma tersebut. Dalam cabang disiplin ini algoritma dipelajari secara abstrak, terlepas dari sistem komputer atau bahasa pemrograman yang digunakan. Algoritma yang berbeda dapat diterapkan pada suatu masalah dengan kriteria yang sama.

Kompleksitas dari suatu algoritma merupakan ukuran seberapa banyak komputasi yang dibutuhkan algoritma tersebut untuk menyelesaikan masalah. Secara informal, algoritma yang dapat menyelesaikan suatu permasalahan dalam waktu yang singkat memiliki kompleksitas yang rendah, sementara algoritma yang membutuhkan waktu lama untuk menyelesaikan masalahnya mempunyai kompleksitas yang tinggi.

Sejarah istilah “algoritma”

Kata algoritma berasal dari latinisasi nama seorang ahli matematika dari Uzbekistan Al Khawārizmi (hidup sekitar abad ke-9), sebagaimana tercantum pada terjemahan karyanya dalam bahasa latin dari abad ke-12 “Algorithmi de numero Indorum”. Pada awalnya kata algorisma adalah istilah yang merujuk kepada aturan-aturan aritmetis untuk menyelesaikan persoalan dengan menggunakan bilangan numerik arab (sebenarnya dari India, seperti tertulis pada judul di atas). Pada abad ke-18, istilah ini berkembang menjadi algoritma, yang mencakup semua prosedur atau urutan langkah yang jelas dan diperlukan untuk menyelesaikan suatu permasalahan.

Jenis-jenis Algoritma

Terdapat beragam klasifikasi algoritma dan setiap klasifikasi mempunyai alasan tersendiri. Salah satu cara untuk melakukan klasifikasi jenis-jenis algoritma adalah dengan memperhatikan paradigma dan metode yang digunakan untuk mendesain algoritma tersebut. Beberapa paradigma yang digunakan dalam menyusun suatu algoritma akan dipaparkan dibagian ini. Masing-masing paradigma dapat digunakan dalam banyak algoritma yang berbeda.

  • Divide and Conquer, paradigma untuk membagi suatu permasalahan besar menjadi permasalahan-permasalahan yang lebih kecil. Pembagian masalah ini dilakukan terus menerus sampai ditemukan bagian masalah kecil yang mudah untuk dipecahkan. Singkatnya menyelesaikan keseluruhan masalah dengan membagi masalah besar dan kemudian memecahkan permasalahan-permasalahan kecil yang terbentuk.
  • Metode serakah. Sebuah algoritma serakah mirip dengan sebuah Pemrograman dinamik, bedanya jawaban dari submasalah tidak perlu diketahui dalam setiap tahap; dan menggunakan pilihan “serakah” apa yang dilihat terbaik pada saat itu.

Tidak ada komentar:

Posting Komentar