Algoritma dan Pemrograman

Definisi Algoritma

Pengertian Algoritma adalah "Aturan secara tepat menentukan seurutan operasi dalam menentukan langkah pembuatan suatu program"  yang mengikutkan semua program yang ada di komputer tersebut, termasuk program yang tidak melakukan perhitungan angka.  Suatu program hanya sebuah algoritma yang jika ia akan berhenti memproses kerjanya.
Algoritma dapat digambarkan dengan banyak notasi, termasuk pseudokode, bahasa alamiah, bagan drakon, diagram alur, bahasa pemrograman serta tabel kontrol.  Ekspresi bahasa alamiah terhadap algoritma biasanya lebih banyak dan tidak pasti, dan jarang digunakan untuk algoritma yang kompleks dan baik secara teknis. Pseudokode, diagram alur, bagan drakon, dan tabel kontrol adalah langkah yang terstruktur untuk penggambaran algoritma yang mencegah banyaknya ketidakpastian pada beberapa pernyataan bahasa alamiah. Bahasa pemrograman bertujuan untuk mengekspresikan algoritma dalam sebuah bentuk yang dapat diselesaikan oleh komputer, namun sering digunakan sebagai cara untuk menentukan atau mendokumentasikan suatu algoritma.

Algoritma dikelompokan menjadi tiga tingkatan berdasarkan deskripsi mesin Turing:
1. Deskripsi tingkat-tinggi
"... bertujuan untuk menjelaskan algoritma, tanpa melihat rincian implementasi. Pada tingkatan ini kita tidak perlu menuliskan bagaimana mesin mengatur perangkat pita atau kepala pita rekam."
2. Deskripsi implementasi
"... dipergunakan untuk menjelaskan cara mesin Turing menggunakan kepalanya dan proses penyimpanan data. Pada tingkatan ini kita tidak harus memberikan secara rinci kondisi ataupun fungsi transisi."
3. Deskripsi formal
Dilihat secara khusus dari "tingkatan terendah", menjelaskan "tabel kondisi" berdasarkan mesin Turing.

Kebanyakan algoritma bertujuan untuk diterapkan sebagai program komputer. Namun, algoritma juga dapat diterapkan untuk tujuan lain, seperti dalam jaringan saraf biologis (misalnya otak manusia yang menerapkan aritmatika atau pemburu yang melihat mangsa), dalam sirkuit elektris, ataupun didalam sebuah perangkat mekanis.

Contoh Algoritma
Salah satu dari algoritma sederhana adalah menentukan angka terbesar dalam sebuah deretan angka (tidak teratur). Solusinya membutuhkan pemeriksaan setiap angka dalam deret, tapi hanya sekali. Dari hal ini muncul beberapa algoritma sederhana, yang dapat dicantumkan dalam kalimat bahasa deskripsi tingkat tinggi, dapat dinyatakan seperti ini:

Deskripsi tingkat tinggi:
1. Jika angka dalam deret tidak ada maka tiada pula bilangan yang paling besar.
2. Input angka pertama dalam deret, maka ia menjadi yang paling besar.
3. Untuk  angka berikutnya dalam deret, apabila angka tersebut besar dari angka yang paling besar sekarang, anggap angka tersebut menjadi yang paling besar didalam deret.
4. Jika tak ada angka yang tersisa lagi pada suatu deret untuk diperiksa, anggap angka yang paling besar sekarang menjadi angka yang terbesar didalam deret tersebut.

Deskripsi (Quasi-)formal: Dituliskan dalam kalimat yang lebih dekat dengan bahasa tingkat-tinggi dari program komputer, dibawah  ini adalah kode formal dari algoritma dalam pseudokode :

Algoritma LargestNumber
  Input: Deret angka K.
  Output: Angka terbesar dalam daftar K.
  terbesar ← Knull
  untuk setiap item dalam K, lakukan
    jika item > terbesar, maka
      terbesar ← item
  kembalikan terbesar
• "←" merupakan singkatan untuk "diubah menjadi". Contohnya , "terbesar ← item" mempunyai arti yaitu nilai dari terbesar diubah menjadi nilai dari item.
• "kembalikan" pengakhiran algoritma dan mengeluarkan (Output)  nilai kembalian.

Algoritma Euclid

Algoritma Euclid muncul sebagai Proposisi II dalam Book VII ("Elementary Number Theory") dari Elements. Euclid mengajukan permasalahan: "Ambil dua angka yang bukan prima, untuk mencari bilangan pembagi paling besar". Ia menghasilkan "Sebuah angka [merupakan] besaran yang terdiri dari unit-unit": angka penghitung, integer positif kecuali 0. Dan "mengukur" adalah menempatkan ukuran panjang terkecil s dengan tepat (q kali) diantara ukuran terpanjang l sampai sisa r lebih kecil dari panjang terkecil s. Dalam dunia modern, sisa r = l - q*s, q sebagai hasil bagi, atau sisa r adalah "modulus", bagian sisa-integer yang tersisa setelah pembagian.

Agar metode Euclid berhasil, panjang awalnya harus memenuhi dua kebutuhan: (i) panjangnya tidak 0, DAN (ii) hasil pengurangan harus "lebih", sebuah pengujian harus menjamin bahwa bilangan terkecil dari dua angka adalah hasil pengurangan dari yang terbesar (cara lain, keduanya bisa sama sehingga pengurangan menghasilkan 0).

Pembuktian asli Euclid mengikutkan kebutuhan yang ketiga: kedua panjang bukanlah bilangan prima. Euclid menentukan hal ini agar dia bisa membentuk sebuah bukti reductio ad absurdum bahwa dua pembagi dua angka adalah yang terbesar. Walau algoritma Nicomachus sama dengan Euclid, bila keduanya itu bilangan prima maka menghasilkan angka "1" untuk bilangan pembagi paling besar. Jadi lebih jelasnya bahwa algoritma berikut adalah algoritma Nicomachus.

Pengujian Algoritma Euclid

Apakah algoritma berjalan seperti yang penulis inginkan? Beberapa kasus pengujian cukup menentukan fungsi inti. Sumber pertama menggunakan 3009 dan 884. Knuth memberi saran 40902, 24140. Pada Kasus menarik lainnya yaitu menggunakan dua angka relatif prima 14157 dan 5950.
Tapi kasus pengecualian harus teridentifikasi dan diuji. Apakah "inelegan" berjalan benar saat R > S, S > R, R = S? Sama juga dengan "Elegan": B > A, A > B, A = B? (Semua benar). Apakah yang terjadi bila salah satu bilangan 0, atau keduanya 0? ("Inelegan" terus berjalan pada kedua kasus; "elegan" terus berjalan saat A = 0.) Apakah yang terjadi bila angka negatif dimasukan kedalamnya? Angka desimal? Bila angka masukan, dimisalkan domain berdasarkan fungsi yang dihitung oleh algoritma atau program, dan hanya diikuti integer positif termasuk 0, maka kegagalan pada nol mengartikan bahwa algoritma (dan program instansiasinya) adalah sebuah fungsi parsial bukannya fungsi total. Kesalahan yang dikenal karena eksepsi adalah kegagalan roket Ariane V.

Bukti dari kebenaran program menggunakan induksi matematika: Knuth mendemonstrasikan penggunaan induksi matematika untuk versi "pengembangan" dari algoritma Euclid, dan dia mengusulkan "metode umum yang digunakan untuk membuktikan validitas dari tiap algoritma." Tausworthe mengusulkan tentang sebuah pengukuran dari kompleksitas dari sebuah program adalah panjang dari pembuktian kebenarannya.

Sumber: id.m.wikipedia.org/wiki/Algoritma

Created by: -RIDHO KARIMAN (D1041141020)

                     -HIDAYAT HABIBI (D1041141034)

                     -MUHAMMAD TOLIB (D1041141006)