Algoritma

algoritma adalah rangkaian terbatas dari instruksi-instruksi yang rumit, yang biasanya digunakan untuk menyelesaikan atau menjalankan suatu kelompok masalah komputasi tertentu. Algoritma digunakan sebagai spesifikasi untuk melakukan perhitungan dan pemrosesan data. Algoritma yang lebih mutakhir dapat melakukan deduksi otomatis (disebut sebagai penalaran otomatis) dan menggunakan tes matematis dan logis untuk mengarahkan eksekusi kode melalui berbagai rute (disebut sebagai pengambilan keputusan otomatis). Penggunaan karakteristik manusia sebagai deskriptor mesin secara metaforis telah dipraktekkan oleh Alan Turing dengan terminologi seperti "memory", "search" dan "stimulus".

Diagram alur dari sebuah (Algoritme Euclid) untuk menghitung faktor persekutuan terbesar (f.p.b.) dari dua angka a dan b dalam lokasi bernama A dan B. Algoritme dijalankan dengan pengurangan berturut-turut dalam dua pengulangan: JIKA pengujian B >= A menghasilkan "ya" (atau benar) (lebih akuratnya angka b dalam lokasi B lebih besar atau sama dengan angka a dalam lokasi A) MAKA, algoritme menentukan B ← B - A (artinya angka b - a menggantikan b sebelumnya). Hal yang sama, JIKA A > B, MAKA A ← A - B. Proses tersebut berhenti saat (isi dari) B adalah 0, menghasilkan f.p.k. dalam A. (Algoritme tersebut diambil dari Scott 2009:13; simbol dan gaya penggambaran dari Tausworthe 1977).

Sebaliknya, heuristika adalah pendekatan untuk pemecahan masalah komputasi yang mungkin tidak sepenuhnya terspesifikasi atau tidak menjamin hasil yang benar atau optimal, terutama dalam ranah masalah komputasi yang mana tidak ada hasil yang benar atau optimal yang terdefinisi dengan baik.[2]

Sebagai metode yang efektif, algoritma dapat diekspresikan dalam jumlah ruang dan waktu yang terbatas,[3] dan dalam bahasa formal yang terdefinisi dengan baik[4] untuk menghitung suatu fungsi.[5] Dimulai dari tataran awal dan input awal (bisa jadi kosong),[6] instruksi-instruksi yang ada menggambarkan sebuah komputasi yang, ketika dieksekusi, berjalan melalui sejumlah tataran dengan jumlah terhingga yang terdefinisi dengan baik,[7] yang pada akhirnya menghasilkan "output"[8] dan berakhir pada tataran final akhir. Transisi dari satu tataran ke tataran berikutnya tidak selalu bersifat menentukan; beberapa algoritme, yang dikenal sebagai algoritme acak, menggabungkan input acak.

Contoh Algoritma 

1. algoritma euclid 

Algoritme Euclid muncul sebagai Proposisi II dalam Book VII ("Elementary Number Theory") dari Elements. [56] Euclid mengajukan permasalahan: "Ambil dua angka bukan prima, untuk mencari bilangan pembagi terbesar". Dia menentukan "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) di antara ukuran terpanjang l sampai sisa r lebih kecil dari panjang terkecil s. [57] Dalam dunia modern, sisa r = l - q*s, q sebagai hasil bagi, atau sisa r adalah "modulus", bagian sisa-integer yang tersisa setelah pembagian.

Supaya 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 supaya dia bisa membentuk sebuah bukti reductio ad absurdum bahwa dua pembagi dua angka adalah yang terbesar. [59] Walau algoritme Nicomachus sama dengan Euclid, bila kedua bilangan prima maka menghasilkan angka "1" untuk bilangan pembagi terbesar. Jadi untuk lebih jelasnya algoritme berikut adalah algoritme Nicomachus.

Algoritme berikut disebut sebagai versi Euclid dan Nichomachus 4-langkah-nya Knuth, tetapi bukannya menggunakan pembagi untuk menentukan sisa ia menggunakan pengurangan berturut-turut dari panjang terkecil s dari sisa panjang r sampai r kurang dari s. Deskripsi tingkat-tinggi, diperlihatkan dengan tulisan tebal, diadaptasi dari Knuth 1973:2-4:

INPUT:

1 [Kedalam dua lokasi L dan S taruh angka l dan s yang merepresentasikan kedua panjang]:
 INPUT L, S
2 [Inisialisasi R: buat supaya sisa panjang r sama dengan panjang awal l]
 R ← L

E0: [Pastikan r ≥ s.]

3 [Pastikan angka terkecil dari kedua angka ada dalam S dan yang terbesar di R]:
  IF R > S THEN
    isi dari L adalah angka terbesar jadi lewati langkah 4, 5 dan 6:
    GOTO step 6
  ELSE
    tukar isi R dan S.
4 L ← R (langkah pertama ini berlebih, tetapi berguna untuk diskusi nanti).
5 R ← S
6 S ← L

E1: [Cari sisa]: Sampai sisa panjang r di R kurang dari panjang terkecil s pada S, kurangi angka s dalam S berulang kali dari sisa panjang r dalam R.

7 IF S > R THEN
   selesai mengukur jadi
   GOTO 10
 ELSE
   ukur lagi,
8 R ← R - S
9 [Pengulangan-sisa]:
   GOTO 7.

E2: [Apakah sisa 0?]: APAKAH (i) pengukuran terakhir adalah sama dan sisa di R adalah 0 program dapat berhenti, ATAU (ii) algoritme harus terus jalan: hasil pengukuran meninggalkan sisa di R kurang dari angka pengukuran dalam S.

10 IF R = 0 THEN
   selesai jadi
   GOTO langkah 15
 ELSE
   lanjut ke langkah 11,

E3: [Interchange s dan r]: Sulitnya algoritme Euclid. Menggunakan sisa r untuk mengukur angka terkecil sebelumnya s:; L sebagai lokasi sementara.
11 L ← S
12 R ← S
13 S ← L
14 [Ulang proses pengukuran]:
   GOTO 7
OUTPUT:
15 [Selesai. S berisi faktor persekutuan terbesar]:
   PRINT S
DONE:
16 HALT, END, STOP.