Dasar – Dasar Algoritma

Diberikan pendekatan dengan model matematika yang merupakan bagian dari penyelesaian masalah. Penyelesaian yang sempurna adalah sebuah metode yang dibutuhkan untuk menyelesaikan permasalahan umum dengan menggunakan model. Idealnya, sebuah prosedur pada step – step barisan adalah peranan penting dari jawaban yang diinginkan.

Definisi 2.1

Sebuah Algoritma adalah prosedur terbatas untuk menyelesaikan sebuah permasalahan dengan langkah yang terbatas.

Istilah algoritma pertama kali ditulis oleh al-Khowarizmi matematikawan arab abad 19, dalam bukunya kitab al-jabr w’al muquabala.

Diberikan sebuah algoritma untuk mencari pembagi bersama terbesar yang dikenal sebagai algoritma Euclids sebagai berikut :

Algoritma Euclids : Diberikan 2 (dua) integer positif m dan n, untuk menemukan pembagi bersama terbesar yaitu integer positif terbesar yang dapat membagi m dengan n.

E1. [Temukan sisa]. Bagi m dan n dan berikan r sebagai sisa pembagian (dalam hal ini 0 < r < n).

E2. [ Apakah sisanya nol]. Jika r = 0, algoritma berakhir, n sebagai jawaban.

E3. [ Menukar tempat ]. M n, n r, dan kembali kelangkah E1.

Algoritma didefinisiakan sebagai prosedur terbatas untuk menyelesaikan sebuah permasalahan dengan langkah terbatas dalam waktu terbatas.

Ada beberapa sifat umum algoritma. Sifat-sifat tersebut digunakan ketika sebuah algoritma dideskripsikan. Sifat – sifat tersebut adalah :

1. Input. Suatu algoritma dapat mempunyai nol atau banyak input, yaitu suatu kuantitas dimana diberikan nilai awal sebelum algoritma dimulai. Input diperoleh dari himpuman objek yang telah ditetapkan. Dalam algoritma Euclids, terdapat 2 ( dua) nilai input yang diberi nama m dan n, dimana keduanya diambil dari himpunan integer positif.
2. Output. Dari setiap nilai input sebuah algoritma menghasilkan nilai output/keluaran dari himpunan yang dispesifikasikan. Nilai Output adalah penyelesaian dari permasalahan. Suatu algoritma dapat mempunyai satu atau banyak output. Algoritma Euclids mempunyai satu output, dinamakan n pada langkah E2, yang merupakan pembagi bersama terbesar dari dua input. Output merupakan informasi yang dihasilkan.
3. Definiteness. Langkah – langkah sebuah algoritma harus didefinisikan dengan tepat, tindakan penyelesaian harus ditetapkan dengan tepat dan jelas untuk setiap kasus. Dalam algoritma Euclids, pembacaan input diperjelas dan mudah dimengerti apa arti pembagian m dengan n dan apa sisanya. Kriteria definiteness harus yakin bahwa nilai m dan n selalu integer positif bilamana langkah E1 dieksekusi. Dengan hipotesa awal bernilai benar, dan setelah langkah E1, r adalah integer non negative dimana harus tidak nol jika didapat langkah E3, sehingga m dan n benar-benar integer positif yang dibutuhkan.
4. Finiteness. Sebuah algoritma seharusnya menghasilkan output yang diinginkan setelah akhir dari langkah untuk sebarang himpunan input. Algoritma Euclids menyakinkan kondisi ini, karena setelah langkah E1 nilai r lebih kecil dari pada n, sehingga jika r = 0, nilai n berkurang untuk waktu selanjutnya bahwa langkah E1 ditemukan.
5. Effectiveness. Algoritma harus memungkinkan untuk setiap langkahnya dilakukan pada sebuah algoritma yang sebenarnya dan mempunyai jumlahan waktu yang terbatas. Artinya semua operasi yang dilakukan dalam algoritma adalah operasi dasar. Algoritma euclids hanya digunakan operasi pembagian satu integer positif dengan yang lain, penguju if sebuah integer nol dan letak nilai pada satu variable sama dengan pada yang lain. Operasi ini adalah efektif, karena integer dapat menggambarkan dalam cara terbatas dan terdapat minimal satu metode untuk membagi satu dengan yang lain. Tetapi untuk operasi yang sama mungkin tidak efektif jika nilai yang digunakan berbelit – belit untuk sebarang bilangan real yang ditentukan dengan ekspansi decimal terbatas. Contoh langkah yang tidak efektif : “ jika 2 integer yang lebih benar dari n dimana ada sebuah solusi dengan persamaan sebagai xⁿ + yⁿ = zⁿ dalam integer positif x, y dan z, maka kembali kelangkah E4”. Sehingga sebuah statement akan menjadi operasi yang tidak efektif sementara seseorang berhasil menunjukkan bahwa ada sebuah algoritma untuk menentukan apakah 2 atau tidak ada integer yang lebih besar sebagaimana ditetapkan.