Definisi Algoritme

Algoritme adalah prosedur sistematis untuk memecahkan masalah matematis dalam langkah-langkah terbatas.

Dalam ilmu matematika dan ilmu komputer, algoritme adalah prosedur langkah-demi-langkah untuk penghitungan. Algoritme digunakan untuk penghitungan, pemrosesan data dan penalaran otomatis.

Algoritme adalah metode efektif diekspresikan sebagai rangkaian terbatas dari instruksi-instruksi yang telah didefinisikan dengan baik untuk menghitung sebuah fungsi.

Dimulai dari sebuah kondisi awal dan input awal (mungkin kosong), instruksi-instruksi tersebut menjelaskan sebuah komputasi yang, bila dieksekusi, diproses lewat sejumlah urutan kondisi terbatas yang terdefinisi dengan baik, yang pada akhirnya menghasilkan “keluaran” dan berhenti di kondisi akhir. Transisi dari satu kondisi ke kondisi selanjutnya tidak harus deterministik; beberapa algoritme, dikenal dengan algoritme pengacakan, menggunakan masukan acak.

Algoritme adalah jantung dari ilmu komputer atau informatika, tetapi tidak identik dengan komputer saja karena algoritme selalu dipakai dalam sehari-hari. Contohnya adalah dalam resep memasak dengan langkah-langkahnya yang sistematis. Dan masih banyak lagi kegiatan sehari-hari yang merupakan algoritme. Bedanya adalah dalam dunia TI algoritma dipakai dalam bahasa pemrograman, karena komputer hanyalah salah satu pemroses. Agar dapat dilaksanakan oleh komputer, algoritme harus dituliskan dalam bahasa pemrograman. Bahasa pemrograman ada banyak, antara lain Pascal, C, C++, Basic, Fortran, Labview, Java, dll.

Perkalian Algoritme

Algoritme Perkalian Booth adalah algoritma perkalian yang mengalikan dua signed binary number dalam notasi two’s complement. Algoritma ini ditemukan oleh Andrew Donald Booth pada tahun 1951 ketika melakukan penelitian dalam kristalografi di Birbeck College di Bloombury, London. Algoritma Booth banyak digunakan dalam dunia computer.

Prosedur

Algoritma Booth bekerja dengan berulang kali menambahkan satu dari dua nilai ditentukan A dan S untuk produk P, kemudian melakukan shift kanan aritmatik pada P. Misalnya m dan r menjadi multiplicand dan multiplier, dan x dan ymerupakan jumlah bit di m dan r.

1. Tentukan nilai A dan S, dan nilai awal P. Semua angka-angka harus memiliki panjang sama dengan (x + y + 1).

A : Isi yang paling signifikan (paling kiri) bit dengan nilai m. Isi sisa (y + 1) bit dengan nol.
S : Isi bit yang paling signifikan dengan nilai (-m) di notasi two’s complement. Isi sisa (y + 1) bit dengan nol.
P : Isi bit paling signifikan x dengan nol. Di sebelah kanan ini, tambahkan nilai r. Isi bit paling signifikan (paling kanan) dengan nol.

2. Tentukan dua paling signifikan (paling kanan) bit dari P.

Jika mereka adalah 01, tentukanlah nilai dari P + A. Abaikan overflow apapun.
Jika mereka adalah 10, tentukanlah nilai dari P + S. Abaikan overflow apapun.
Jika mereka 00, tidak perlu melakukan apa-apa. Gunakan P langsung pada langkah berikutnya.
Jika mereka 11, tidak perlu melakukan apa-apa. Gunakan P langsung pada langkah berikutnya.

3. Lakukan sekali shift kanan aritmatik terhadap nilai yang diperoleh dari langkah 2.

4. Ulangi langkah 2 dan 3 sebanyak y kali.

5. Buang LSB dari nilai P (bit paling kanan). Nilai yang diperoleh adalah hasil perkalian m dan r.

Contoh

Tentukan nilai dari -5 x 7, dengan m = -5 dan r = 7, dimana x = 4 dan y = 4

A = 1011 0000 0
S = 0101 0000 0
P = 0000 0111 0

Kita akan melakukan 4 kali looping:

1. P = 0000 0111 0. Dua bit terakhir adalah 10.

→ P = 0101 0111 0. P = P + S.

→ P = 0010 1011 1. Shift kanan aritmatik.

2. P = 0010 1011 1. Dua bit terakhir adalah 11.

→ P = 0001 0101 1. Shift kanan aritmatik.

3. P = 0001 0101 1. Dua bit terakhir adalah 11.

→ P = 0000 1010 1. Shift kanan aritmatik

4. P = 0000 1010 1. Dua bit terakhir adalah 01

→ P = 1011 1010 1. P = P + A.

→ P = 1101 1101 0. Shift kanan aritmatik

Hasil perkalian adalah 1101 1101 = -35

Algoritme Strassen

Algoritme Strassen dalam matematika, khususnya aljabar linear adalah sebuah algoritme yang dinamakan oleh Volker Strassen yang merupakan sebuah algoritme yang digunakan untuk perkalian matriks yang secara asimtot lebih cepat daripada algoritme perkalian matriks standar dan sangat berguna dalam penggunaanya untuk matriks yang berukuran besar.

Sejarah

Volker Strassen mempublikasikan algoritme Strassen tahun 1969. Meskipun algoritme ini hanya sedikit lebih cepat daripada algoritme standar untuk perkalian matriks, dialah yang pertama menjelaskan bahwa eliminasi Gauss adalah tidak optimal. Dalam tulisannya, dia memulai penelitian untuk melengkapi algoritme-algoritme yang lebih cepat seperti algoritme Winograd dari Shmuel Winograd pada 1980, dan yang lebih kompleks algoritme Coppersmith-Winograd dipublikasikan pada 1987.

Algoritme Strassen

Misalkan A, B dua matriks persegi pada ring R. Kita ingin menghitung produk matriks C sebagai

\mathbf {C} =\mathbf {A} \mathbf {B} \qquad \mathbf {A} ,\mathbf {B} ,\mathbf {C} \in R^{2^{n}\times 2^{n}}

Jika matriks A, B bukan bertipe 2ⁿ x 2ⁿ kita isi baris-baris dan kolom-kolom yang kosong dengan nol.

Kita partisi A, B dan C kedalam matriks blok yang berukuran sama.

\mathbf {A} ={\begin{bmatrix}\mathbf {A} _{1,1}&\mathbf {A} _{1,2}\\\mathbf {A} _{2,1}&\mathbf {A} _{2,2}\end{bmatrix}}{\mbox{ , }}\mathbf {B} ={\begin{bmatrix}\mathbf {B} _{1,1}&\mathbf {B} _{1,2}\\\mathbf {B} _{2,1}&\mathbf {B} _{2,2}\end{bmatrix}}{\mbox{ , }}\mathbf {C} ={\begin{bmatrix}\mathbf {C} _{1,1}&\mathbf {C} _{1,2}\\\mathbf {C} _{2,1}&\mathbf {C} _{2,2}\end{bmatrix}}

dengan

\mathbf {A} _{i,j},\mathbf {B} _{i,j},\mathbf {C} _{i,j}\in R^{2^{n-1}\times 2^{n-1}}

lalu

\mathbf {C} _{1,1}=\mathbf {A} _{1,1}\mathbf {B} _{1,1}+\mathbf {A} _{1,2}\mathbf {B} _{2,1}

\mathbf {C} _{1,2}=\mathbf {A} _{1,1}\mathbf {B} _{1,2}+\mathbf {A} _{1,2}\mathbf {B} _{2,2}

\mathbf {C} _{2,1}=\mathbf {A} _{2,1}\mathbf {B} _{1,1}+\mathbf {A} _{2,2}\mathbf {B} _{2,1}

\mathbf {C} _{2,2}=\mathbf {A} _{2,1}\mathbf {B} _{1,2}+\mathbf {A} _{2,2}\mathbf {B} _{2,2}

Dengan konstruksi ini kita tidak mengurangi jumlah dari perkalian-perkalian. Kita masih memerlukan 8 perkalian-perkalian untuk menghitung matriks-matriks C_i,j , dengan jumlah perkalian yang sama kita perlukan ketika menggunakan matriks perkalian standar.

Sekarang sampai pada bagian terpenting. Kita tetapkan matriks baru

\mathbf {M} _{1}:=(\mathbf {A} _{1,1}+\mathbf {A} _{2,2})(\mathbf {B} _{1,1}+\mathbf {B} _{2,2})

\mathbf {M} _{2}:=(\mathbf {A} _{2,1}+\mathbf {A} _{2,2})\mathbf {B} _{1,1}

\mathbf {M} _{3}:=\mathbf {A} _{1,1}(\mathbf {B} _{1,2}-\mathbf {B} _{2,2})

\mathbf {M} _{4}:=\mathbf {A} _{2,2}(\mathbf {B} _{2,1}-\mathbf {B} _{1,1})

\mathbf {M} _{5}:=(\mathbf {A} _{1,1}+\mathbf {A} _{1,2})\mathbf {B} _{2,2}

\mathbf {M} _{6}:=(\mathbf {A} _{2,1}-\mathbf {A} _{1,1})(\mathbf {B} _{1,1}+\mathbf {B} _{1,2})

\mathbf {M} _{7}:=(\mathbf {A} _{1,2}-\mathbf {A} _{2,2})(\mathbf {B} _{2,1}+\mathbf {B} _{2,2})

Yang kemudian digunakan untuk mengekspresikan C_i,j dalam bentuk M_k. Karena kita telah mendefenisikan M_k kita bisa mengeliminasi satu perkalian matriks dan mengurangi jumlah perkalian-perkalian menjadi 7 (satu perkalian matriks untuk tiap M_k) dan ekspresi C_i,j sebagai

\mathbf {C} _{1,1}=\mathbf {M} _{1}+\mathbf {M} _{4}-\mathbf {M} _{5}+\mathbf {M} _{7}

\mathbf {C} _{1,2}=\mathbf {M} _{3}+\mathbf {M} _{5}

\mathbf {C} _{2,1}=\mathbf {M} _{2}+\mathbf {M} _{4}

\mathbf {C} _{2,2}=\mathbf {M} _{1}-\mathbf {M} _{2}+\mathbf {M} _{3}+\mathbf {M} _{6}

Kita iterasikan bagian diatas ke-n kali proses sampai submatriks-submatriks menjadi angka-angka.

Algoritme Strassen pada penerapannya mengubah metode standar dari perkalian matriks agar submatriks-submatriks yang cukup kecil menjadi lebih efisien. Fakta-fakta agar algoritme Strassen lebih efisien bergantung pada implementasi khusus dan hardware.

Analisi Numerik

Perkalian matriks standar melakukan

n^{3}=n^{\log _{2}8}

perkalian-perkalian dari elemen-elemen dalam ring R. Kita anggap penjumlahan-penjumlahan diperlukan karena bergantung pada R, yang bisa jauh lebih cepat daripada perkalian-perkalian dalam implementasi pada komputer terutama jika ukuran dari entri matriks melebihi ukuran kata dari mesin.

Dengan algoritme Strassen kita bisa mengurangi jumlah perkalian-perkalian

n^{\log _{2}7}\approx n^{2.807}

Pengurangan dalam jumlah perkalian bagaimanapun akan sampai saat pilihan dari sedikit pengurangan kestabilan numerik.

Contoh program sederhana pada Matlab

function c = strass(a,b)
nmin = 2;
%misalkan matriks a dan b berukuran 2 x 2
[n,n] = size(a);
if n <= nmin;
   c = a*b;
else
   %entri matriks a dan b berukuran n x n; n=2^k; k=2,3,...
   %misalkan entri matriks a dan b berukuran n=2^2 atau 4 x 4
   a11=a(1:2,1:2); a12=a(1:2,3:4); a21=a(3:4,1:2); a22=a(3:4,3:4);
   b11=b(1:2,1:2); b12=b(1:2,3:4); b21=b(3:4,1:2); b22=b(3:4,3:4);
   p1 = (a11+a22)*(b11+b22);
   p2 = (a21+a22)*b11;
   p3 = a11*(b12-b22);
   p4 = a22*(b21-b11);
   p5 = (a11+a12)*b22;
   p6 = (a21-a11)*(b11+b12);
   p7 = (a12-a22)*(b21+b22);
   c = [p1+p4-p5+p7 p3+p5; p2+p4 p1-p2+p3+p6];
end

Catatan: program diatas hanya untuk matriks berukuran 1×1, 2×2, 4×4. Untuk matriks yang berukuran lebih besar, masih diperlukan penyempurnaan. Agar programnya bisa berjalan.

Barisan polinomial

Rangkaian bilangan di atas dapat dinyatakan dalam bentuk barisan: 0, 1, 3, 6, … . Tentu akan menyulitkan kita jika ingin melihat jumlah jabatan tangan pada kelompok yang anggotanya 201 orang. Untuk itu seringkali kita berusaha mencari bentuk umum dari barisan tersebut, dan benar bahwa pada barisan tersebut apabila jumlah n orang dalam kelompok secara umum terdapat ${\frac {n^{2}-n}{2}}$ atau $U_{n}={\frac {1}{2}}n^{2}-{\frac {1}{2}}n$ jabatan tangan yang menunjukkan barisan tersebut berupa barisan polinom.

Proses pencarian kemungkinan bentuk umum peristiwa di atas sering dipakai konsep kombinasi, tetapi ternyata prinsip-prinsip keistimewaan barisan polinom dengan menggunakan operasi aritmetika sederhana dari operasi pengurangan, penjumlahan, perkalian dan pembagian, juga dapat dimanfaatkan.

Membuat Barisan Polinom

Jika f sebuah fungsi polinom variabel tunggal maka barisan polinom yang dibangun dari fungsi f tersebut dapat dinyatakan dalam bentuk,

f(1) , f(2) , f(3) , …. , f(n) , ….mempunyai arti:

suku ke 1 = U₁ = f(1)suku ke 2 = U₂ = f(2) suku ke 3 = U₃ = f(3) ………………….. suku ke n = U_n = f(n)	Barisan bilangan 0, 1, 3, 6, … dapat diartikan, U₁ = 0 , U₂ = 1, U₃ = 3, U₄ = 6, …. , $U_{n}={\frac {1}{2}}n^{2}-{\frac {1}{2}}n$ atau barisan tersebut dibangkitkan oleh fungsi polinom $f(n)={\frac {1}{2}}n^{2}-{\frac {1}{2}}n$ berupa fungsi berderajat 2Derajat polinom adalah pangkat tertinggi dari variabel fungsi polinom. Untuk i, a_i berupa bilangan cacah, $f(n)=a_{i}n^{i}+a_{i-1}n^{i-1}+\cdots +a_{2}n^{2}+a_{1}n+a_{0}=\sum \limits _{k=0}^{i}a_{k}n^{k}.$ maka fungsi f(n) mempunyai derajat i pada suku polinom a_inⁱ

suku ke 1 = U₁ = f(1)suku ke 2 = U₂ = f(2)

suku ke 3 = U₃ = f(3)

…………………..

suku ke n = U_n = f(n)

Barisan bilangan 0, 1, 3, 6, … dapat diartikan, U₁ = 0 , U₂ = 1, U₃ = 3, U₄ = 6, …. ,

U_{n}={\frac {1}{2}}n^{2}-{\frac {1}{2}}n

atau barisan tersebut dibangkitkan oleh fungsi polinom

f(n)={\frac {1}{2}}n^{2}-{\frac {1}{2}}n

berupa fungsi berderajat 2Derajat polinom adalah pangkat tertinggi dari variabel fungsi polinom.

Untuk i, a_i berupa bilangan cacah,

f(n)=a_{i}n^{i}+a_{i-1}n^{i-1}+\cdots +a_{2}n^{2}+a_{1}n+a_{0}=\sum \limits _{k=0}^{i}a_{k}n^{k}.

maka fungsi f(n) mempunyai derajat i pada suku polinom a_inⁱ

Menggali Keistimewaan Barisan Polinom

Dalam menggali keistimewaan barisan polinom kita mencoba membentuk beberapa pengertian sebagai jembatan untuk memperoleh beberapa keistimewaan tersebut.

Keistimewaan Barisan Polinom

Pada akhir penggalian keistimewaan barisan polinom dapat dengan mudah kita simpulkan adanya beberapa peculiar barisan polinom^[1] tersebut yaitu:

Barisan selisih suku ke derajad polinom yang dibentuk akan berupa barisan C.
Besar konstanta adalah ai!,bow down beaches

risan yang diketahui beberapa suku pertamanya. Langkah-langkah untuk mencari kemungkinan bentuk umum barisan tersebut salah satunya adalah:

Jika barisan tersebut (anggap barisan utama) adalah barisan konstanta atau dapat dianggap konstanta maka lanjutkan ke langkah terakhir.
Buat barisan selisih suku terus menerus sampai menghasilkan barisan konstanta atau dapat dianggap konstanta.
Hitung jumlah barisan selisih suku (misal ada q barisan), dan salah satu suku konstanta yang dihasilkan adalah p, maka dimungkinkan barisan utama tersebut mengandung komponen polinom : ${\frac {p}{q!}}n^{q}$ .
Hapus komponen polinom yang diperoleh dari langkah ke 3 dari barisan utama dengan mengurangi masing-masing suku barisan utama dengan nilai masing-masing suku komponen polinom yang diperoleh di langkah 3. Kemudian ulangi dari langkah 1 dengan barisan utama yang baru (setelah dihilangkan komponen polinom yang diperoleh dari langkah 3).
Kemungkinan rumus umum barisan yang kita cari adalah jumlah semua komponen yang diperoleh di langkah ke 3 ditambah salah satu suku barisan konstanta paling akhir (barisan utama baru terakhir).

Contoh Penggunaan Algoritme

Misalkan kita mencoba mencari salah satu kemungkinan rumus umum dari barisan bilangan 0, 0, 0, 6, …

0, 0, 0, 6, …. bukan barisan konstanta maka,

0-0,0-0,6-0, … atau 0, 0, 6, …. barisan selisih suku ke 1

0-0,6-0, … atau 0, 6, … barisan selisih ke 2

6-0, … atau 6 … barisan selisih ke 3 kita anggap barisan konstanta

ada 3 barisan selisih suku maka barisan utama mengandung komponen ${\frac {6}{3!}}n^{3}=n^{3}$ .
Barisan n³ adalah 1, 8, 27, 64, … kita hilangkan dari 0, 0, 0, 6, … akan menghasilkan barisan 0-1,0-8,0-27,6-64,… atau -1, -8, -27, -58, …
-1, -8, -27, -58, … bukan barisan konstanta maka,

-8+1,-27+8,-58+27, … atau -7, -19, -31, …. barisan selisih suku ke 1

-19+7,-31+19, … atau -12, -12, … barisan selisih ke 2 berupa barisan konstanta

ada 2 barisan selisih suku maka barisan utama mengandung komponen ${\frac {-12}{2!}}n^{2}=-6n^{2}$ .
Barisan -6n² adalah -6, -24, -54, -96, … hilangkan dari -1, -8, -27, -58, … hasilnya -1+6,-8+24,-27+54,-58+96,… atau 5, 16, 27, 38, …
5, 16, 27, 38, …. bukan barisan konstanta maka,

16-5,27-16,38-27, … atau 11, 11, 11, …. barisan selisih suku ke 1 berupa barisan konstanta

ada 1 barisan selisih suku maka barisan utama mengandung komponen ${\frac {11}{1!}}n=11n$ .
Barisan 11n adalah 11, 22, 33, 44, … hilangkan dari 5, 16, 27, 38, … hasilnya barisan 5-11,16-22,27-33,38-44,… atau -6, -6, -6, -6, …
-6, -6, -6, -6, …. adalah barisan konstanta.

Kemungkinan rumus umum barisan 0, 0, 0, 6, … adalah U_n = n³ – 6n² + 11n – 6

Manfaat Algoritme

Dalam kehidupan seringkali kita berusaha melihat keteraturan menjadi jelas dan dapat diprediksi. Data keteraturan yang dapat dinyatakan dengan bilangan dalam interval yang sama dengan kurun waktu tertentu akan membentuk sebuah barisan.

Barisan tersebut selalu mempunyai multi penafsiran untuk data-data yang belum terlampaui. Untuk menentukan kemungkinan pola keteraturan data tersebut sebagai alternatif prediksi dapat digunakan algoritme di atas.

Melalui algoritme ini dapat dengan banyak cara untuk mencari kemungkinan aturan suku suatu barisan, diantaranya

Menambah pada beberapa suku berikutnya

Misalnya ada barisan bilangan 2, 4, 6, …. maka kita dapat menentukan kemungkinan rumus umum barisan dengan tiga suku tersebut menggunakan algoritme.

Untuk mendapatkan kemungkinan yang lain kita dapat menambahkan beberapa suku berikutnya menggunakan bilangan yang kita kehendaki, misalnya untuk barisan tersebut dapat kita jadikan 2, 4, 6, 10, …. atau 2, 4, 6, 4, 2, …. dan masih banyak lagi.

Menyisipkan bentuk rumus umum yang diharapkan

Metode ini memungkinkan kita menyisipkan sembarang suku yang kita kehendaki.

Misal pada barisan bilangan 2, 4, 6, …, jika kita menghendaki pada rumus umumnya terdapat suku n.sin(90n⁰) mak kita dapat mengambil bagian tersebut dari barisan 2, 4, 6, …, sehingga muncul barisan 2-1.sin(90⁰), 4-2.sin(180⁰), 6-3.sin(270⁰), …. atau barisan bilangan 1, 4, 3, …..

Barisan 1, 4, 3, … kita cari kemungkinannya menggunakan algoritme dan hasilnya dijumlahkan dengan n.sin(90n⁰).

Memecah masing-masing suku dengan aturan yang dikehendaki

Metode ini memecah masing masing suku dengan aturan yang sama, kemudian masing-masing pecahan suku kita buat barisan yang hasilnya kita gabung sesuai aturan pemecahan yang telah kita gunakan.

Misal 2, 4, 6, …. dapat kita pecah menjadi 1×2, 2×2, 2×3, … sehingga muncul dua barisan yaitu 1, 2, 2, … dan 2, 2, 3, …. Jika barisan pertama mempunyai rumus U_n1 dan barisan kedua memunyai rumus U_n2 maka rumus barisan 2, 4, 6, … kemungkinan adalah U_n = U_n1.U_n2

Mengembangkan Algoritme

Keistimewaan yang telah ditunjukkan barisan polinom yang selalu memberikan barisan selisih suku ke derajatnya berupa barisan konstanta maka barisan selisih suku berikutnya adalah barisan 0 (nol).

Mengacu pada pengertian tersebut maka dengan meneliti perilaku barisan selisih suku disaat tanpa barisan polinom, kemungkinan akan mendapatkan keteraturan, sehingga memungkinkan membentukan algoritmeberlandaskan keteraturan tersebut.

Dalam makalah seminar Menentukan Rumus Umum Barisan Polinom terdapat contoh algoritme untuk menyertakan sebuah suku eksponen dalam barisan polinom sebagai berikut:

Jika barisan tersebut (anggap barisan utama) adalah barisan konstanta atau dapat dianggap konstanta maka lanjutkan ke langkah terakhir.
Buat barisan selisih suku terus menerus sampai menghasilkan barisan dengan rasio sukunya sama atau rasio sukunya dapat dianggap sama.
Hitung jumlah barisan selisih suku (misal ada q barisan), dan nilai suku awal barisan selisih paling akhir adalah p, maka dimungkinkan barisan utama tersebut mengandung komponen suku eksponen : ${\frac {p}{{(r-1)}^{q}}}r^{n-1}$
Hapus komponen eksponen yang diperoleh dari langkah ke 3 dari barisan utama dengan mengurangi masing-masing suku barisan utama dengan nilai masing-masing suku komponen polinom yang diperoleh di langkah 3.
Jika barisan tersebut (anggap barisan utama) adalah barisan konstanta atau dapat dianggap konstanta maka lanjutkan ke langkah terakhir.
Buat barisan selisih suku terus menerus sampai menghasilkan barisan konstanta atau dapat dianggap konstanta.
Hitung jumlah barisan selisih suku (misal ada q barisan), dan salah satu suku konstanta yang dihasilkan adalah p, maka dimungkinkan barisan utama tersebut mengandung komponen polinom : ${\frac {p}{q!}}n^{q}$ .
Hapus komponen polinom yang diperoleh dari langkah ke 7 dari barisan utama dengan mengurangi masing-masing suku barisan utama dengan nilai masing-masing suku komponen polinom yang diperoleh di langkah 7. Kemudian ulangi dari langkah 5 dengan barisan utama yang baru (setelah dihilangkan komponen polinom yang diperoleh dari langkah 7).
Kemungkinan rumus umum barisan yang kita cari adalah jumlah semua komponen yang diperoleh di langkah ke 3 , dan 7, serta ditambah salah satu suku barisan konstanta paling akhir (barisan utama baru terakhir).

Misalnya kita mencari kemungkinan rumus umum barisan 2, 7, 24, 77, 238, …

2, 7, 24, 77, 238, …. bukan barisan konstanta maka,

7-2,24-7,77-24,238-77, … atau 5, 17, 53, 161, …. barisan selisih suku ke 1

17-5,53-17,161-53, … atau 12, 36, 108, … barisan selisih ke 2 kita anggap barisan mempunyai : $r={\frac {36}{12}}={\frac {108}{36}}=3$

ada 2 barisan selisih suku dengan rasio 3 maka kemungkinan mengandung komponen ${\frac {12}{{(3-1)}^{2}}}3^{n-1}=3^{n}$ .
Barisan 3ⁿ adalah 3, 9, 27, 81, 243, … kita hilangkan dari 2, 7, 24, 77, 238 … akan menghasilkan barisan 2-3,7-9,24-27,238-234,… atau -1, -2, -3, -4, …
-1, -2, -3, -4, …. bukan barisan konstanta maka,

-2+1,-3+2,-4+3, … atau -1, -1, -1, …. barisan selisih suku ke 1 berupa barisan konstanta

ada 1 barisan selisih suku maka barisan utama mengandung komponen ${\frac {-1}{1!}}n=-n$ .
Barisan -n adalah -1, -2, -3, -4, … hilangkan dari -1, -2, -3, -4, … hasilnya barisan -1+1,-2+2-3+3,-4+4,… atau 0, 0, 0, 0, …
0, 0, 0, 0, …. adalah barisan konstanta.

Kemungkinan rumus umum barisan 2, 7, 24, 77, 238, …adalah $U_{n}={\frac {12}{{(3-1)}^{2}}}3^{n-1}=3^{n}-n$ .

Melihat contoh di atas maka persoalan Deret aritmetika dan Deret ukur atau Deret Geometri memungkinkan juga dapat diselesikan menggunakan algoritme terakhir.

Contoh Soal dan Jawaban Algoritme

1) Contoh dari sebuah definisi algoritma yang benar adalah sebagai berikut:

Masalah: Pengurutan sekumpulan nilai yang bernilai acak.
Masukan: Serangkaian data berukuran $n$.
Keluaran: Serangkaian data berukuran $n$, dengan urutan $a_{1} \leq a_{2} \leq a_{3} \leq . . . \leq a_{n - 1} \leq a_{n}$ , di mana $a_{x}$ adalah data pada posisi $x$ dalam rangkaian.

Data masukan yang diinginkan merupakan rangkaian data, tanpa memperdulikan jenis data (angka, huruf, teks, dan lainnya). Contoh dari nilai masukan adalah [2, 5, 1, 3, 4] ataupun ["Doni", "Andi", "Budi", "Clara"]. Data keluaran yang diinginkan, tentunya adalah data masukan yang telah terurut: [1, 2, 3, 4, 5] dan ["Andi", "Budi", "Clara", "Doni"].

Untuk menyelesaikan masalah yang diberikan di atas, kita dapat menggunakan algoritme insertion sort. Kode di bawah menunjukkan implementasi insertion sort pada bahasa pemrograman python:

def insertion_sort(data):
    for i in range(0, len(data)):
        insert_val = data[i]
        hole_pos = i

        while hole_pos > 0 and insert_val < data[hole_pos - 1]:
            data[hole_pos] = data[hole_pos - 1]
            hole_pos = hole_pos - 1

        data[hole_pos] = insert_val

Implementasi insertion sort yang diberikan di atas menunjukkan bahwa pada dasarnya sebuah prosedur yang harus dijalankan untuk mengubah data masukan menjadi data keluaran, sehingga masalah dapat terselesaikan.

2) Algoritma mendapatkan minyak dengan volume 4 liter.

Jawaban:

1. Isi penuh ember 3 liter dengan minyak. {ember 3 liter berisi minyak 3 liter}

1. Tuangkan minyak dari ember 3 liter ke dalam ember 5 liter. {ember 5 liter berisi minyak 3 liter}.

1. Isi penuh ember 3 liter dengan minyak. {ember 3 liter berisi minyak 3 liter}

1. Tuang minyak dari ember 3 liter ke ember 5 liter hingga ember 5 liter penuh. {di dalam ember 3 liter sekarang berisi minyak sebanyak 1 liter}

1. Kembalikan minyak dari ember 5 liter ke dalam drumnya. {ember 5 liter kosong}

1. Tuangkan minyak dari ember 3 liter ke ember 5 liter. {ember 3 liter kosong, ember 5 liter berisi minyak 1 liter}

Isi penuh ember 3 liter dengan minyak, lalu tuang ke dalam ember 5 liter. Maka akan diperoleh minyak sebanyak 4 liter {1 + 3 = 4 liter minyak }.

3) Tuliskan algoritme untuk mencetak banyak HALO sebanyak 10 kali.

Algoritme cetak_banyak_halo
Deklarasi
K : integer {pencacah pengulangan}
Deskripsi
K ← 1 {inisialisasi}
While k ≤ 10 do
Write (‘HALO’)
K ←K+1
Endwhile
{kondisi berhenti : k > 10}.

4) Untuk mencari nilai terbesar dari 3 buah bilangan, dalam C++, kode yang dapat digunakan adalah

#include <iostream>

using namespace std;

void main() {

int a, b, c, d;

cout << “nilai 1: “;

cin >> a;

cout << “nilai 2: “;

cin >> b;

cout << “nilai 3: “;

cin >> d;

c = (a > b ? a : b);

cout << “nilai terbesar adalah : ” << (c > d ? c : d) << “\n”;

}

Logika:

Bandingkan nilai pertama dengan nilai kedua. Kemudian yang lebih besar di antara nilai tersebut di bandingkan dengan nilai berikutnya (nilai ke tiga), sehingga di dapat nilai terbesar di antara ketiga variabel tersebut.

Penjelasan kode:

Seperti yang kita lihat di atas, pertama – tama, kita membuat tiga variabel yaitu, variabel a, b, c, dan d. Kemudian, kita meminta user untuk memasukkan nilai untuk variabel a, b, dan d. Setelah itu, kita membandingkan nilai masing – masing variabel. Disini digunakan variabel c sebagai “alat bantu”. Variabel c sendiri menyimpan nilai terbesar antara variabel adan b. Kemudian ditampilkan nilai yang terbesar yang didapat setelah membandingkan variabel c dan d.

5) Salah satu dari algoritme sederhana adalah menemukan bilangan terbesar dalam sebuah deretan angka (tak berurut). Solusinya membutuhkan pemeriksaan setiap angka dalam deret, tetapi hanya sekali. Dari hal ini munculah algoritme sederhana, yang bisa dinyatakan dalam kalimat bahasa deskripsi tingkat-tinggi, sebagai:

Deskripsi tingkat-tinggi:

Jika tidak ada angka dalam deret makan tidak ada bilangan terbesar.
Asumsikan item pertama dalam deret adalah yang terbesar.
Untuk setiap sisa angka dalam deret, jika angka tersebut besar dari angka terbesar sekarang, anggap angka tersebut menjadi yang terbesar dalam deret.
Bila tidak ada lagi angka yang tersisa pada deret untuk diperiksa, anggap angka terbesar sekarang menjadi angka yang terbesar dalam deret.

Deskripsi (Quasi-)formal: Ditulis dalam kalimat yang lebih dekat dengan bahasa tingkat-tinggi dari program komputer, berikut ini adalah kode formal dari algoritme dalam pseudokode atau kode pijin:

Algoritma LargestNumber
  Masukan: Deret angka L.
  Keluaran: Angka terbesar dalam daftar L.

terbesar ← L_nulluntuk setiapitemdalamL, lakukanjikaitem > terbesar, makaterbesar ← itemkembalikanterbesar

“←” adalah singkatan untuk “diubah menjadi”. Misalnya, “terbesar ← item” artinya nilai dari terbesar diubah menjadi nilai dari item.
“kembalikan” mengakhiri algoritma dan mengeluarkan nilai kembalian.

5) Pseudocode dari luas Persegi adalah…

read(panjang, lebar)

Luas = panjang * lebar

write(Luas)

end

6) Nilai P=0, Q=5, R=10 jika diketahui nilai PQR adalah seperti yang tersebut dan algoritmanya adalah nilai P=Q, Q=R maka nilai PQR adalah…

Jawaban:

P=5; Q=10; R=10

7) Urutan algoritma yang benar adalah
(1)Mulai
(2)Menulis Surat
(3)Surat dimasukkan amplop
(4)Menutup amplop
(5)Menempel perangko di amplop
(6)Mengantar ke kantor pos
(7)Selesai

Jawaban:

1-2-3-4-5-6-7

8) Dibaca waktu tempuh seorang pelari marathon dalam jam-menit-detik (hh:mm:ss). Diminta mengkonversi waktu tempuh tersebut ke dalam detik. Tuliskan algoritmanya.

Ingatlah
1 menit = 60 detik
1 jam = 3600 detik
Misalnya waktu tempuh seorang pelari marathon adalah 1 jam, 5 menit, 40 detik. Dalam detik, waktu tempuh seluruhnya adalah ( 1 x 3600 ) + ( 5 x 60 ) + 40 = 3940 detik.

Penyelesaian :
Algoritma KONVERSI_JAM_KE_DETIK
{ dibaca jam-menit-detik (hh:mm:ss). Nilai jam-menit-detik dikonversi ke dalam detik, lalu ditampilkan ke piranti keluaran }

DEKLARASI
Type jam : record <hh : integer    {0..23},    {jam}
mm : integer    {0..59},    {menit}
ss : integer    {0..59},    {detik}
>
J : jam
TotalDetik : integer

DESKRIPSI
read(J.hh,J.mm,J.ss))
TotalDetik ← (J.hh*3600) + (J.mm*60) + J.ss
write(TotalDetik)

Jika anda mentranslasikan algoritma KONVERSI_JAM_KE_DETIK ke dalam bahasa pascal, anda harus memperhatikan tipe bilangan bulat yang digunakan. Karena ranah nilai tipe integer terbatas, maka ada kemungkinan hasil pengubahan jam-menit-detik ke total detik bernilai negatif, sebab nilai (J.hh*3600) + (J.mm*60) + J.ss berada di luar rentang tipe integer. Tipe longint yang mempunyai ranah yang lebih besar dapat dipakai untuk masalah ini.
Jadi, program KONVERSI_JAM_KE_DETIK dalam bahasa pascal adalah sebagai berikut :
program KONVERSI_JAM_KE_DETIK;
{ dibaca jam-menit-detik (hh:mm:ss). Nilai jam-menit-detik dikonversi ke dalam detik, lalu ditampilkan ke piranti keluaran.}

uses wincrt;

(* DEKLARASI *)
type Jam = record
hh : longint;        {jam}
mm : longint;        {menit}
ss : longint;        {detik}
end;

var
J : Jam;
TotalDetik : longint;

(* deskripsi *)
begin
write(‘Jam :’); readln(J.hh);
write(‘Menit:’); readln(J.mm);
write(‘Detik:’); readln(J.ss);
TotalDetik:= (J.hh*3600) + (J.mm*60) + J.ss;
writeln(‘Total detik = ‘, TotalDetik);
end.

9) Nilai P=0, Q=5, R=10 jika diketahui nilai PQR adalah seperti yang tersebut dan algoritmanya adalah nilai P=Q, Q=R maka nilai P+Q+R adalah…

Jawaban:

Nilai P=0, Q=5, R=10 algoritmanya adalah nilai P=Q, Q=R maka nilai P+Q+R adalah …
Nilai P=0 Algoritmanya P=Q Maka nilai P sama dengan nilai Q yaitu 5, P=5
Nilai Q=5 Algoritmanya Q=R Maka nilai Q sama dengan nilai R yaitu 5, Q=10
Nilai R tetap karena nilai R tidak dialgoritmakan, R =10
Maka P+Q+R=5+10+10=25

10) Berikut adalah contoh aplikasi algoritma genetika yang digunakan untuk menyelesaikan masalah kombinasi. Misalkan ada persamaan a+2b+3c+4d = 30, kita mencari nilai a, b, c, dan d yang memenuhi persamaan diatas. Kita mencoba menggunakan algoritma genetika untuk menyelesaikan permasalahan tersebut.

Penjelasan mengenai langkah-langkah penyelesaian permasalahan diatas menggunakan algoritma genetika adalah sebagai berikut:

1. Pembentukan chromosome

Karena yang dicari adalah nilai a, b, c, d maka variabel a, b, c, d dijadikan sebagai gen-gen pembentuk chromosome. Batasan nilai variabel a adalah bilangan integer 0 sampai 30. Sedangkan batasan nilai variabel b, c, dan d adalah bilangan integer 0 sampai 10.

2. Inisialisasi

Proses inisialisasi dilakukan dengan cara memberikan nilai awal gen-gen dengan nilai acak sesuai batasan yang telah ditentukan.
Misalkan kita tentukan jumlah populasi adalah 6, maka:
Chromosome[1] = [a;b;c;d] = [12;05;03;08] Chromosome[2] = [a;b;c;d] = [02;01;08;03] Chromosome[3] = [a;b;c;d] = [10;04;03;04] Chromosome[4] = [a;b;c;d] = [20;01;10;06] Chromosome[5] = [a;b;c;d] = [01;04;03;09] Chromosome[6] = [a;b;c;d] = [20;05;07;01]

3. Evaluasi Chromosome

Permasalahan yang ingin diselesaikan adalah nilai variabel a, b, c, dan d yang memenuhi persamaan a+2b+3c+4d = 30, maka fungsi_objektif yang dapat digunakan untuk mendapatkan solusi adalah fungsi_objektif(chromosome) = | (a+2b+3c+4d) – 30 |
Kita hitung fungsi_objektif dari chromosome yang telah dibangkitkan:
fungsi_objektif(chromosome[1]) = Abs(( 12 + 2*5 + 3*3 + 4*8 ) – 30)
= Abs((12 + 10 + 9 + 32 ) – 30)
= Abs(63 – 30)
= 33
fungsi_objektif(chromosome[2]) = Abs(( 2 + 2*1 + 3*8 + 4*3 ) – 30)
= Abs(( 2 + 2 + 24 + 12 ) – 30)
= Abs(40 – 30)
= 10
fungsi_objektif(chromosome[3]) = Abs(( 10 + 2*4 + 3*3 + 4*4 ) – 30)
= Abs(( 10 + 8 + 9 + 16 ) – 30)
= Abs(43 – 30)
= 13
fungsi_objektif(chromosome[4]) = Abs(( 20 + 2*1 + 3*10 + 4*6 ) – 30)
= Abs(( 20 + 2 + 30 + 24 ) – 30)
= Abs(76 – 30)
= 46
fungsi_objektif(chromosome[5]) = Abs(( 1 + 2*4 + 3*3 + 4*9 ) – 30)
= Abs(( 1 + 8 + 9 + 36 ) – 30)
= Abs(54 – 30)
= 24
fungsi_objektif(chromosome[6]) = Abs(( 20 + 2*5 + 3*7 + 4*1 ) – 30)
= Abs(( 20 + 10 + 21 + 4) – 30)
= Abs(55 – 30)
= 25
Rata-rata dari fungsi objektif adalah:
rata-rata = (33+10+13+46+24+25)/6
= 151 / 6
= 25.167

4. Seleksi Chromosome

Proses seleksi dilakukan dengan cara membuat chromosome yang mempunyai fungsi_objektif kecil mempunyai kemungkinan terpilih yang besar atau mempunyai nilai probabilitas yang tinggi. Untuk itu dapat digunakan fungsi fitness = (1/(1+fungsi_objektif)), fungsi_objektif perlu ditambah 1 untuk menghindari kesalahan program yang diakibatkan pembagian oleh 0.

fitness[1]    = 1 / (fungsi_objektif[1]+1)
= 1 / 34
= 0.0294
fitness[2]    = 1 / (fungsi_objektif[2]+1)
= 1 / 11
= 0.0909
fitness[3]   = 1 / (fungsi_objektif[3]+1)
= 1 / 14
= 0.0714
fitness[4]   = 1 / (fungsi_objektif[4]+1)
= 1 / 47
= 0.0212
fitness[5]   = 1 / (fungsi_objektif[5]+1)
= 1 / 25
= 0.0400
fitness[6]   = 1 / (fungsi_objektif[6]+1)
= 1 / 26
= 0.0385
total_fitness    = 0.0294 + 0.0909 + 0.0714 + 0.0212 + 0.04 + 0.0385
= 0.2914

Rumus untuk mencari probabilitas: P[i] = fitness[i] / total_fitness

P[1]    = 0.0294 / 0.2914
= 0.1009
P[2]    = 0. 0909 / 0.2914
= 0.3119
P[3]    = 0. 0714 / 0.2914
= 0.2450
P[4]    = 0. 0212 / 0.2914
= 0.0728
P[5]    = 0.04 / 0.2914
= 0.1373
P[6]    = 0.0385 / 0.2914
= 0.1321

Dari probabilitas diatas dapat kita lihat kalau chromosome ke 2 yang mempunyai fitness paling besar maka chromosome tersebut mempunyai probabilitas untuk terpilih pada generasi selanjutnya lebih besar dari chromosome lainnya. Untuk proses seleksi kita gunakan roulete wheel, untuk itu kita harus mencari dahulu nilai kumulatif probabilitasnya:
C[1]    = 0.1009
C[2]   = 0.1009+ 0.3119
= 0.4128
C[3]    = 0.1009+ 0.3119 + 0.2450
= 0.6578
C[4]    = 0.1009+ 0.3119 + 0.2450 + 0.0728
= 0.7306
C[5]    = 0.1009+ 0.3119 + 0.2450 + 0.0728 + 0.1373
= 0.8679
C[6]    = 0.1009+ 0.3119 + 0.2450 + 0.0728 + 0.1373 + 0.1321
= 1
Setelah dihitung cumulative probabilitasnya maka proses seleksi menggunakan roulete-wheel dapat dilakukan. Prosesnya adalah dengan membangkitkan bilangan acak R dalam range 0-1.
Jika R[k] < C[1] maka pilih chromosome 1 sebagai induk, selain itu pilih chromosome ke-k sebagai induk dengan syarat C[k-1] < R < C[k]. Kita putar roulete wheel sebanyak jumlah populasi yaitu 6 kali (bangkitkan bilangan acak R) dan pada tiap putaran, kita pilih satu chromosome untuk populasi baru. Misal:
R[1] = 0.201
R[2] = 0.284
R[3] = 0.009
R[4] = 0.822
R[5] = 0.398
R[6] = 0.501
Angka acak pertama R[1] adalah lebih besar dari C[1] dan lebih kecil daripada C[2] maka pilih chromosome[2] sebagai chromosome pada populasi baru, dari bilangan acak yang telah dibangkitkan diatas maka populasi chromosome baru hasil proses seleksi adalah:
chromosome[1] = chromosome[2] chromosome[2] = chromosome[2] chromosome[3] = chromosome[1] chromosome[4] = chromosome[5] chromosome[5] = chromosome[2] chromosome[6] = chromosome[3]

Chromosome baru hasil proses seleksi:
chromosome[1] = [02;01;08;03] chromosome[2] = [02;01;08;03] chromosome[3] = [12;05;03;08] chromosome[4] = [01;04;03;09] chromosome[5] = [02;01;08;03] chromosome[6] = [10;04;03;04]

5. Crossover

Setelah proses seleksi maka proses selanjutnya adalah proses crossover. Metode yang digunakan salah satunya adalah one-cut point, yaitu memilih secara acak satu posisi dalam chromosome induk kemudian saling menukar gen. Chromosome yang dijadikan induk dipilih secara acak dan jumlah chromosome yang mengalami crossover dipengaruhi oleh parameter crossover_rate ( ρc ).
Pseudo-code untuk proses crossover adalah sebagai berikut:
begin
k← 0;
while(k<populasi) do
R[k] ← random(0-1);
if (R[k] < ρc ) then
select Chromosome[k] as parent;
end;
k = k + 1;
end;
end;

Misal kita tentukan crossover probability adalah sebesar 25%, maka diharapkan dalam satu generasi ada 50% Chromosome (3 chromosome) dari satu generasi mengalami proses crossover. Prosesnya adalah sebagai berikut:
Pertama kita bangkitkan bilangan acak R sebanyak jumlah populasi
R[1] = 0.191
R[2] = 0.259
R[3] = 0.760
R[4] = 0.006
R[5] = 0.159
R[6] = 0.340

Maka Chromosome ke k akan dipilih sebagai induk jika R[k] < ρc, dari bilangan acak R diatas maka yang dijadikan induk adalah chromosome[1], chromosome[4] dan chromosome[5].

Setelah melakukan pemilihan induk proses selanjutnya adalah menentukan posisi crossover. Ini dilakukan dengan cara membangkitkan bilangan acak dengan batasan 1 sampai (panjang chromosome-1), dalam kasus ini bilangan acak yang dibangkitkan adalah 1 – 3. Misalkan didapatkan posisi crossover adalah 1 maka chromosome induk akan dipotong mulai gen ke 1 kemudian potongan gen tersebut saling ditukarkan antar induk.
chromosome[1] >< chromosome[4] chromosome[4] >< chromosome[5] chromosome[5] >< chromosome[1]

Posisi cut-point crossover dipilih menggunakan bilangan acak 1-3 sebanyak jumlah crossover yang terjadi, misal
C[1] = 1
C[2] = 1
C[3] = 2

offspring[1] = chromosome[1] >< chromosome[4] = [02;01;08;03] >< [01;04;03;09] = [02;04;03;09] offspring[4] = Chromosome[4] >< Chromosome[5] = [01;04;03;09] >< [02;01;08;03] = [01;01;08;03] offspring[5] = Chromosome[5] >< Chromosome[1] = [02;01;08;03] >< [02;01;08;03] = [02;01;08;03] Dengan demikian populasi Chromosome setelah mengalami proses crossover menjadi:
chromosome[1] = [02;04;03;09] chromosome[2] = [02;01;08;03] chromosome[3] = [12;05;03;08] chromosome[4] = [01;01;08;03] chromosome[5] = [02;01;08;03] chromosome[6] = [10;04;03;04]

6. Mutasi

Jumlah chromosome yang mengalami mutasi dalam satu populasi ditentukan oleh parameter mutation_rate. Proses mutasi dilakukan dengan cara mengganti satu gen yang terpilih secara acak dengan suatu nilai baru yang didapat secara acak. Prosesnya adalah sebagai berikut. Pertama kita hitung dahulu panjang total gen yang ada dalam satu populasi. Dalam kasus ini panjang total gen adalah total_gen = (jumlah gen dalam chromosome) * jumlah populasi
= 4 * 6
= 24
Untuk memilih posisi gen yang mengalami mutasi dilakukan dengan cara membangkitkan bilangan integer acak antara 1 sampai total_gen, yaitu 1 sampai 24. Jika bilangan acak yang kita bangkitkan lebih kecil daripada variabel mutation_rate (ρm) maka pilih posisi tersebut sebagai sub-chromosome yang mengalami mutasi. Misal ρm kita tentukan 10% maka diharapkan ada 10% dari total_gen yang mengalami populasi:
jumlah mutasi = 0.1 * 24
= 2.4
= 2
Misalkan setelah kita bangkitkan bilangan acak terpilih posisi gen 12 dan 18 yang mengalami mutasi. Dengan demikian yang akan mengalami mutasi adalah chromosome ke-3 gen nomor 4 dan Chromosome ke-5 gen nomor 2. Maka nilai gen pada posisi tersebut kita ganti dengan bilangan acak 0-30.

Misalkan bilangan acak yang terbangkitkan adalah 2 dan 5. Maka populasi chromosome setelah mengalami proses mutasi adalah:
chromosome[1] = [02;04;03;09] chromosome[2] = [02;01;08;03] chromosome[3] = [12;05;03;02] chromosome[4] = [01;01;08;03] chromosome[5] = [02;05;08;03] chromosome[6] = [10;04;03;04]

Setelah proses mutasi maka kita telah menyelesaikan satu iterasi dalam algoritma genetika atau disebut dengan satu generasi. Maka fungsi_objective setelah satu generasi adalah:

chromosome[1] = [02;04;03;09] fungsi_objektif[1] = Abs(( 2 + 2*4 + 3*3 + 4*9 ) – 30)
= Abs(( 2 + 8 + 9 + 36 ) – 30)
= Abs( 55 – 30)
= 25

chromosome[2] = [02;01;08;03] fungsi_objektif[2] = Abs(( 2 + 2*1 + 3*8 + 4*3 ) – 30)
= Abs(( 2 + 2 + 24 + 12 ) – 30)
= Abs(40 – 30)
= 10

chromosome[3] = [12;05;03;02] fungsi_objektif[3] = Abs(( 12 + 2*5 + 3*3 + 4*2 ) – 30)
= Abs(( 12 + 10 + 9 + 8 ) – 30)
= Abs(39 – 30)
= 9

chromosome[4] = [01;01;08;03] fungsi_objektif[4] = Abs(( 1 + 2*1 + 3*8 + 4*3 ) – 30)
= Abs(( 1 + 2 + 24 + 12 ) – 30)
= Abs(39 – 30)
= 9

chromosome[5] = [02;05;08;03] fungsi_objektif[5] = Abs(( 2 + 2*5 + 3*8 + 4*3 ) – 30)
= Abs(( 2 + 10 + 24 + 12 ) – 30)
= Abs(48 – 30)
= 18

chromosome[6] = [10;04;03;04] fungsi_objektif[6] = Abs(( 10 + 2*4 + 3*3 + 4*4 ) – 30)
= Abs(( 10 + 8 + 9 + 16 ) – 30)
= Abs(43 – 30)
= 13

Rata-rata fungsi objektif setelah satu generasi adalah:
rata-rata = ( 25 + 10 + 9 + 9 + 18 + 13) / 6
= 84 / 6
= 14.0

Dapat dilihat dari hasil perhitungan fungsi objektif diatas bahwa setelah satu generasi, nilai hasil rata-rata fungsi_objektif lebih menurun dibandingkan hasil fungsi_objektif pada saat sebelum mengalami seleksi, crossover dan mutasi. Hal ini menunjukkan bahwa chromosome atau solusi yang dihasilkan setelah satu generasi lebih baik dibandingkan generasi sebelumnya. Maka pada generasi selanjutnya chromosome-chromosome yang baru adalah:

chromosome[1] = [02;04;03;09] chromosome[2] = [02;01;08;03] chromosome[3] = [12;05;03;02] chromosome[4] = [01;01;08;03] chromosome[5] = [02;05;08;03] chromosome[6] = [10;04;03;04]

Chromosome-chromosome ini akan mengalami proses yang sama seperti generasi sebelumnya yaitu proses evaluasi, seleksi, crossover dan mutasi yang kemudian akan menghasilkan chromosome-chromosome baru untuk generasi yang selanjutnya. Proses ini akan berulang sampai sejumlah generasi yang telah ditetapkan sebelumnya.

Setelah 50 generasi didapatkan chromosome yang terbaik adalah:
Chromosome = [07;05;03;01] Jika didekode maka:
a=7 ; b=5 ; c=3 ; d=1
Jika dihitung terhadap persamaan f = a+2b+3c+4d:
7 + (2*5) + (3*3) + (4*1) = 30

11) Perkalian dan Pembagian Algoritma Booth

40112862, diambil 2 digit terbelakang yaitu 6 dan 2.

Perkalian menggunakan Algoritma Booth

6 x (-2) = ?

Q = 6 = 0110 M = 0010 . . . .+2

= 1101 . . . .1’ komplemen

= 1110 . . . .2’ komplemen

Jadi, M = -2 = 1110

A Q Q₁

A₃ A₂ A₁ A₀ Q₃ Q₂ Q₁ Q₀Proses

0 0 0 0 0 1 1 0 0 Inisialisasi

0 0 0 0 0 0 1 1 0 . . . . Shift right Siklus 1

1 1 1 0 0 0 1 1 0 A = A + M

1 1 1 1 0 0 0 1 1 . . . . Shift right Siklus 2

1 1 1 1 1 0 0 0 1 . . . . Shift right Siklus 3

0 0 0 1 1 0 0 0 1 A = A – M

0 0 0 0 1 1 0 0 0 . . . . Shift right Siklus 4

Hasil diatas adalah 12, sedangkan untuk perkalian 6 x (-2) = -12

Maka dari itu kita lakukan pengubahan

12 = 0000 1100

1111 0011 . . . . 1’ Komplemen

1111 0100 . . . . 2’ Komplemen

Jadi, -12 = 1111 0100

dikarenakan -128 + 64 + 32 + 16 + 4 = -12

Pembagian menggunakan Algoritma Booth

6 : 2 = ?

Q = 6 = 0110 M = 2 = 0010 atau 1110

A Q

A₃ A₂ A₁ A₀Q₃ Q₂ Q₁ Q₀Proses

0 0 0 0 0 1 1 0 Inisialisasi

0 0 0 0 1 1 0 0 Shift left

1 1 1 0 A = A – M

0 0 0 0 1 1 0 0 A = A + M dan Q₀ = 0 . . . . Siklus 1

0 0 0 1 1 0 0 0 Shift left

1 1 1 1 A = A – M

0 0 0 1 1 0 0 0 A = A + M dan Q₀ = 0 . . . . Siklus 2

0 0 1 1 0 0 0 0 Shift left

0 0 0 1 A = A – M

0 0 0 1 0 0 0 1 Q₀= 1 . . . . Siklus 3

0 0 1 0 0 0 1 0 Shift left

0 0 0 0 A = A – M

0 0 0 0 0 0 1 1 Q₀= 1 . . . . Siklus 4

Hasil pembagian dari 6 : 2 = 3

0000 (sisa bagi) = 0 0011 (hasil bagi) = 3

Bacaan Lainnya Yang Dapat Membuat Anda lebih Pintar

Unduh / Download Aplikasi HP Pinter Pandai

Respons “Ohh begitu ya…” akan sering terdengar jika Anda memasang applikasi kita!

Siapa bilang mau pintar harus bayar? Aplikasi Ilmu pengetahuan dan informasi yang membuat Anda menjadi lebih smart!

Sumber bacaan: Math is Fun

Algoritme Beserta Contoh Soal dan Jawaban

Definisi Algoritme

Perkalian Algoritme

Algoritme Strassen

Sejarah

Algoritme Strassen

Analisi Numerik

Contoh program sederhana pada Matlab

Barisan polinomial

Membuat Barisan Polinom

Menggali Keistimewaan Barisan Polinom

Keistimewaan Barisan Polinom

Contoh Penggunaan Algoritme

Manfaat Algoritme

Menambah pada beberapa suku berikutnya

Menyisipkan bentuk rumus umum yang diharapkan

Memecah masing-masing suku dengan aturan yang dikehendaki

Mengembangkan Algoritme

Misalnya kita mencari kemungkinan rumus umum barisan 2, 7, 24, 77, 238, …

Contoh Soal dan Jawaban Algoritme

1) Contoh dari sebuah definisi algoritma yang benar adalah sebagai berikut:

Masalah

Pengurutan sekumpulan nilai yang bernilai acak.

Masukan

Serangkaian data berukuran $n$.

Keluaran

Serangkaian data berukuran $n$, dengan urutan a1≤a2≤a3≤...≤an−1≤ana1≤a2≤a3≤…≤an−1≤an, di mana axax adalah data pada posisi xx dalam rangkaian.

2) Algoritma mendapatkan minyak dengan volume 4 liter.

3) Tuliskan algoritme untuk mencetak banyak HALO sebanyak 10 kali.

4) Untuk mencari nilai terbesar dari 3 buah bilangan, dalam C++, kode yang dapat digunakan adalah

5) Pseudocode dari luas Persegi adalah… read(panjang, lebar)

6) Nilai P=0, Q=5, R=10 jika diketahui nilai PQR adalah seperti yang tersebut dan algoritmanya adalah nilai P=Q, Q=R maka nilai PQR adalah…

7) Urutan algoritma yang benar adalah (1)Mulai (2)Menulis Surat (3)Surat dimasukkan amplop (4)Menutup amplop (5)Menempel perangko di amplop (6)Mengantar ke kantor pos (7)Selesai

8) Dibaca waktu tempuh seorang pelari marathon dalam jam-menit-detik (hh:mm:ss). Diminta mengkonversi waktu tempuh tersebut ke dalam detik. Tuliskan algoritmanya.

9) Nilai P=0, Q=5, R=10 jika diketahui nilai PQR adalah seperti yang tersebut dan algoritmanya adalah nilai P=Q, Q=R maka nilai P+Q+R adalah…

1. Pembentukan chromosome

2. Inisialisasi

3. Evaluasi Chromosome

4. Seleksi Chromosome

5. Crossover

6. Mutasi

11) Perkalian dan Pembagian Algoritma Booth

Bacaan Lainnya Yang Dapat Membuat Anda lebih Pintar

Unduh / Download Aplikasi HP Pinter Pandai

Rumus Matematika dan Contoh untuk Penggunaan Sehari-hari

Heuristik Matematika adalah metode komputasi yang cepat memberikan solusi

Panjang keliling Bumi | Berapa Panjanganya? Siapa Yang Menghitung…

Tinggalkan Balasan Batalkan balasan

Serangkaian data berukuran $n$, dengan urutan $a_{1} \leq a_{2} \leq a_{3} \leq . . . \leq a_{n - 1} \leq a_{n}$ , di mana $a_{x}$ adalah data pada posisi $x$ dalam rangkaian.

5) Pseudocode dari luas Persegi adalah…

read(panjang, lebar)

7) Urutan algoritma yang benar adalah
(1)Mulai
(2)Menulis Surat
(3)Surat dimasukkan amplop
(4)Menutup amplop
(5)Menempel perangko di amplop
(6)Mengantar ke kantor pos
(7)Selesai