algoritma

Algoritma

Muḥammad bin Mūsā al-Khawārizmī ( 780 – 850 M )

Kata algoritma berasal dari latinisasial-Khawārizmī, Di dunia Barat, ia dikenal sebagai Al-Khawarizmi, Al-Cowarizmi, Al-Ahawizmi, Al-Karismi, Al-Goritmi, Al-Gorismi awalnya menjadi algorisma yang berarti:

"aturan-aturan aritmetis untuk menyelesaikan persoalan dengan menggunakan bilangan numerik"

Abad-18, istilah ini berkembang menjadi algoritma, yang berarti:

"prosedur atau urutan langkah yang jelas dan diperlukan untuk menyelesaikan suatu permasalahan"

PemecahanMASALAH

kumpulan perintah yang kebanyakan memiliki langkah

pengulangan (iterasi) atau memerlukan keputusan (logika

Boolean dan perbandingan), berupa

susunan elemen-elemen berdasarkan baris & kolom yang

membentuk satu kesatuan

Algoritma

KondisiAWAL

X2+10x=39

PemecahanMASALAH

Memiliki tipe data:Integer, double, real (floating point), string,

dll

Tiap tipe data memiliki• anggota dengan

nilai-nilai tertentu• operasi-operasi

yang dapat dilakukan pada tiap anggota tipe data

Algoritma

KondisiAWAL

Aspek penting

ALGORITMA

int a=6;main(){

while(a>5){

cout<<a;a++;

}}

Bagaimana akhir dari

algoritma ini?UNFINITE

Algoritma harus berhenti setelah melalui beberapa

tahapan (langkah)

Finiteness

How could we define the “MIRACLE”?

Setiap langkah harus didefinisikan secara tepat,

tidak boleh membingungkan (ambigu)

Definiteness

OUTPUTAlgoritmaINPUT

Sebuah algoritma memiliki nol atau

lebih input sebelum

dijalankan

Sebuah algoritma

memiliki satu atau lebih

output, yang biasanya

bergantung kepada input

Setiap algoritma harus

berdaya-guna(sangkil/ efektif)

Effectiveness

Case: Fake Coin Problem You have 9 gold coins. All 9 coins look exactly

the same but one coin is a fake and is either lighter or heavier than the other 8 coins.  You have a scale  - balance type with 2 trays- but can only load it twice. How do you find the fake gold coin?

Tugas

You have 12 identical-looking coins, one of which is counterfeit.  The counterfeit coin is either heavier or lighter than the rest.  The only scale you have to use is a simple balance.  Using the scale only three times (Note: not loading, but using for balancing), find the counterfeit coin.

Paradigma

Algoritma

SMALLERPROBLEMSOLVED

SMALLERPROBLEMSOLVED

SMALLERPROBLEMSOLVED

SMALLERPROBLEMSOLVED

SMALLERPROBLEMSOLVED

SMALLERPROBLEMSOLVED

SMALLERPROBLEMSOLVED

SMALLERPROBLEMSOLVED

SMALLERPROBLEMSOLVED

SMALLERPROBLEM

SMALLERPROBLEM

SMALLERPROBLEM

SMALLERPROBLEM

SMALLERPROBLEM

SMALLERPROBLEM

SMALLERPROBLEM

SMALLERPROBLEM

SMALLERPROBLEM

Permasalahan-permasalahan

kecil dipecahkan

secara parsial

Divide and Conquer

CONQUER

SMALLERPROBLEMSOLVED

SMALLERPROBLEMSOLVED

SMALLERPROBLEMSOLVED

SMALLERPROBLEMSOLVED

SMALLERPROBLEMSOLVED

SMALLERPROBLEMSOLVED

SMALLERPROBLEMSOLVED

SMALLERPROBLEMSOLVED

SMALLERPROBLEMSOLVED

Permasalahan terpecahkan

Divide and Conquer

BIGPROBLEM

SOLVED

COMBINE

Bilangan yang tidak memiliki pecahan

desimal BILANGAN BULAT

INTEGER

Integer Data Type

•SignedBertanda (+ / -)•Unsigned

Bulat positif

Pembagian integer

a | b jika b = ac; c Z; a 0

a habis membagi b (a divides b)Jika terdapat bilangan bulat c

a dan b adalah dua bil. bulatdengan syarat a tidak sama dgn. 0

Sedemikian hingga b = ac

Pembagian integer

Contoh:

4 | 12 ? Ya

5 | 17 ? Tidak

Teorema Euclidian

m = nq + rm dan n adalah bilangan bulatdengan n > 0, jika m (dividend)dibagi n (divisor) menghasilkanbilangan bulat q (quotient) danmenyisakan bilangan bulat r(remainder), untuk 0 r < n

Teorema Euclidian

m = nq + rq = m div nr = m mod n

Teorema Euclidian

Contoh:

34 = 5.6 + 46 = 34 div 54 = 34 mod 5

Tugas

Tunjukkan apakah 19 habis membagi

a.89b.773c.8721

Tugas

Carilah q dan r sehingga m = nq + r

a. m = 66, n = 11b. m = 221, n = 12c. m = 3, n = 7

Diffie Hellman Key Exchange