kelompok 1 in space

8/3/2019 Kelompok 1 in Space

1/14

MAKALAH

PERANCANGAN ANALISIS &

ALGORITMA

Disusun Oleh :

Bayu Tri Dewanto (54409214)

Citra Paramitha (50409577)

Madya Prayogie (54409372)

UNIVERSITAS GUNADARMA

2011

KATA PENGANTAR


2/14

Puji syukur Alhamdulillah penulis panjatkan kepada Allah SWT dan

Rasulnya, Nabi Muhammad SAW karena atas rahmat dan karunia-Nya penulis

dapat menyelesaikan program dan penulisan ini. Adapun penulisan ini diajukan

sebagai syarat kelulusan praktikum Pengantar Kecerdasan Buatan.

Dengan segala kerendahan hati, penulis menyadari bahwa dalam makalah

ini masih jauh dari sempurna baik dalam penulisan maupun pembuatan program,

karena keterbatasan kemampuan penulis. Namun demikian diharapkan agar

makalah ini dapat memenuhi syarat yang diperlukan.

Dalam kesempatan ini perkenankanlah penulis menyampaikan ucapan

terima kasih atas dorongan dan bantuan yang diterima oleh penulis, sehingga

dapat menyelesaikan makalah ini. Dan perkenankanlah penulis mengucapkan

rasa terima kasih kepada :

1. Ely Agustina, selaku dosen Perancangan Analisis Algoritma

2. Kedua Orang tua yang telah banyak memberikan bantuan baik secara

moril maupun materil serta dorongan semangat yang tak ternilai. Dan

berkat doa serta restu mereka jugalah terlaksananya penulisan ini.

Oleh karena itu penulis sangat menghargai kritik maupun saran yang

berguna bagi kesempurnaan penyusunan makalah ini. Akhir kata penulis berharap

semoga penulisan ini dapat bermanfaat bagi para pembaca.

1 Jakarta, November 2011

Penulis

SOURCE CODE


3/14


4/14


5/14


6/14

FLOWCHART

Start

Tampil

Komponen

Aksi

Reaksi

Klik Mulai

MyThread!

=null

T

r

y

int x=(int)

(Math.random()*350);

Waktu =

0?

Apakah

ingin

bermain

lagi?

End

try

Cat

ch

Print (ex)

End


7/14

TampilKomponen

Setting layout komponen

Tambah background

Tambah panel skor, nilai,

waktu, nama

Tambah panel Level,Start,

Waktu

Aksi

Reaksi

Lvl =mudah

Tdr = 1000

Mulai = enabled

Tdr = 750

Mulai = enabled

Tdr = 500

Mulai = enabled

Mulai = disabled

End

Lvl =

sedang

Lvl =

sulit

End


8/14

PSEUDO CODE

Pada permainan

Langkah 1 : Input Nama

Langkah 2 : Pilih Tingkat

Langkah 3 : IF tingkat Mudah THEN timer 1000.

IF tingkat Sedang THEN timer 750.

IF tingkat Sulit THEN timer 500.

Langkah 4 : Main tembak ufo.

Langkah 5 : IF waktu 0 THEN PRINT Selamat (nama) Nilai Anda (nilai).

Apakah Ingin Bermain Lagi?

Langkah 6 : IF Yes THEN START

IF NO THEN END

Pada program

Langkah 1 : Menentukan komponen tampilan awal.

Langkah 2 : Membuat tampilan input nama..

Langkah 3 : Membuat method aksi reaksi berdasarkan pilihan tingkat atau level

yang digunakan.

Langkah 4 : Penempatan posisi objek yang akan ditembak.

DIM INT X = RANDOM * 350.

DIM INT Y = RANDOM * 300.

Langkah 6 : Waktu habis

IF waktu 0 THEN END

Langkah 7 : Mengulang permainan

IF YES THEN START

Langkah 8 : Mengakhiri permainan

IF NO THEN END

ALGORITMA PROGRAM

10 CLS.

20 INPUT NAMA : , NAMA.

30 WRITE LEVEL MUDAH, SEDANG, SULIT.


9/14

40 IF LEVEL MUDAH THEN TIMER 1000.

50 IF LEVEL SEDANG THEN TIMER 750.

60 IF LEVEL SULIT THEN TIMER 500.

70 START

70 IF WAKTU = 0 THEN PRINT Selamat (nama) Nilai Anda (nilai).

Apakah Ingin Bermain Lagi?

80 IF YES THEN

90 GO TO 70

100 IF NO THEN

110 END

Algoritma Random (Acak)

Algoritma random adalah suatu algoritma yang mempekerjakan tingkat

keacakan sebagai bagian dari logika. Algoritma ini biasanya menggunakan

seragam acak bit sebagai input tambahan untuk memandu perilaku, dengan

harapan mencapai kinerja yang baik dalam "kasus rata-rata" atas semua pilihan

yang mungkin dari bit acak. Secara formal, kinerja algoritma akan menjadi

variabel acakditentukan oleh bit acak, dengan demikian baik waktu berjalan, atau

output (atau keduanya) adalah variabel acak.

Kita harus membedakan antara algoritma yang menggunakan masukan

acak untuk mengurangi waktu berjalan diharapkan atau penggunaan memori,

tetapi selalu mengakhiri dengan hasil yang benar dalam jumlah dibatasi waktu,

dan algoritma probabilistik, yang, tergantung pada masukan acak, memiliki

kesempatan menghasilkan hasil yang salah ( algoritma Monte Carlo ) atau gagal

untuk menghasilkan hasil ( Las Vegas algoritma ) baik oleh sinyal kegagalan atau

gagal untuk mengakhiri.

Dalam kasus kedua, kinerja dan output acak acak, "algoritma" istilah

untuk prosedur ini agak dipertanyakan. Dalam kasus output acak, tidak lagi secara

resmi efektif. Namun, dalam beberapa kasus, algoritma probabilistik adalah satu-

satunya cara praktis pemecahan masalah.
http://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Algorithm&usg=ALkJrhh4qj5fCP1MCIGt0jFEMXfeK9mYFwhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Randomness&usg=ALkJrhh5THKpk97nT1oGsNC836hb49QH1Qhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Uniform_distribution_(discrete)&usg=ALkJrhgV_9HHbxKoaUBQDWwLXL0V-gnnxwhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Random_variable&usg=ALkJrhj4WOTJBb5dzOhb9mDItP-e8oHRHghttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Monte_Carlo_algorithm&usg=ALkJrhhFMcpyNriqToXpNjrFDvR6SKN-mQhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Las_Vegas_algorithm&usg=ALkJrhirvhD0G3T4FgeGFuEMinFs8vVS5Ahttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Effective_method&usg=ALkJrhh4uiF1jhJk7ESlK8a50ajhzdNJdAhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Algorithm&usg=ALkJrhh4qj5fCP1MCIGt0jFEMXfeK9mYFwhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Randomness&usg=ALkJrhh5THKpk97nT1oGsNC836hb49QH1Qhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Uniform_distribution_(discrete)&usg=ALkJrhgV_9HHbxKoaUBQDWwLXL0V-gnnxwhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Random_variable&usg=ALkJrhj4WOTJBb5dzOhb9mDItP-e8oHRHghttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Monte_Carlo_algorithm&usg=ALkJrhhFMcpyNriqToXpNjrFDvR6SKN-mQhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Las_Vegas_algorithm&usg=ALkJrhirvhD0G3T4FgeGFuEMinFs8vVS5Ahttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Effective_method&usg=ALkJrhh4uiF1jhJk7ESlK8a50ajhzdNJdA


10/14

Dalam praktek yang umum, algoritma acak didekati menggunakan

generator yang pseudorandom sejumlah di tempat sumber sejati bit acak; seperti

sebuah implementasi bisa menyimpang dari perilaku teoritis diharapkan.

Sejarah

Secara historis, algoritma acak pertama adalah metode yang

dikembangkan oleh Michael O. Rabin untuk masalah pasangan terdekat dalam

geometri komputasi . Studi tentang algoritma acak didorong oleh penemuan 1977

dari tes primality acak(yaitu, menentukan primality dari angka) oleh Robert M.

Solovay dan Volker Strassen . Segera setelah itu Michael O. Rabin tahun 1976

menunjukkan bahwa tes primality Millerdapat berubah menjadi algoritma acak.

Pada saat itu, tidak praktis algoritma deterministikuntuk primality dikenal.

Tes Miller-Rabin primality bergantung pada hubungan biner antara dua

bilangan bulat positif k dan n yang dapat dinyatakan dengan mengatakan bahwa k

"adalah saksi ke compositeness dari" n. Hal ini dapat ditunjukkan bahwa

Jika ada saksi compositeness n, maka n adalah komposit (yaitu, n tidak

prima ),

Jika n adalah komposit maka setidaknya tiga perempat dari alam nomor

kurang dari n adalah saksi compositeness, dan

Ada algoritma yang cepat, mengingat k dan n, ascertains apakah k adalah

saksi compositeness n.

Amati bahwa ini menyiratkan bahwa masalah primality dalam Co- RP.

Jika salah satu secara acak memilih 100 nomor kurang dari jumlah

komposit n, maka kemungkinan gagal untuk menemukan seperti "saksi" adalah (1

/ 4) 100 sehingga untuk sebagian besar tujuan praktis, ini adalah tes primality baik.

Jika n adalah besar, mungkin tidak ada tes lain yang praktis. Probabilitas

kesalahan dapat dikurangi ke tingkat sewenang-wenang dengan melakukan tes

independen cukup.

Oleh karena itu, dalam prakteknya, tidak ada hukuman yang terkait dengan

probabilitas kecil menerima kesalahan, karena dengan sedikit perawatan
http://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Pseudorandom_number_generator&usg=ALkJrhjc8QLCaSqaTCazMhi6jXyGqQxM-whttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Michael_O._Rabin&usg=ALkJrhj7Ee6b1I_Gqch7nkVi17EEe8tH-whttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Closest_pair_of_points_problem&usg=ALkJrhiqCkAvYzmVIMJzxaSN1S9r-B4w9ghttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Computational_geometry&usg=ALkJrhhSGTJ5VFNov0K8SoKAFJLUG_SEeAhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Solovay-Strassen_primality_test&usg=ALkJrhinC9gDuKmaD-33h57OiTeqkvdBmghttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Primality_test&usg=ALkJrhjuMxSArZy6mcH67hHyDK47BOjFgQhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Primality_test&usg=ALkJrhjuMxSArZy6mcH67hHyDK47BOjFgQhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Robert_M._Solovay&usg=ALkJrhiMCWP7MWOqmhiPwB65QY83qS9U4Ahttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Robert_M._Solovay&usg=ALkJrhiMCWP7MWOqmhiPwB65QY83qS9U4Ahttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Robert_M._Solovay&usg=ALkJrhiMCWP7MWOqmhiPwB65QY83qS9U4Ahttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Volker_Strassen&usg=ALkJrhgooIbOazz3kZFRRCiS6GfmxSnZewhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Miller-Rabin_primality_test&usg=ALkJrhiaUmMEC5as3TxJsqRm96HLsWVe3Ahttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Miller-Rabin_primality_test&usg=ALkJrhiaUmMEC5as3TxJsqRm96HLsWVe3Ahttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Deterministic_algorithm&usg=ALkJrhgs6MvAA_Lwn6HLPSQPZ8mh5JERzAhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Prime_number&usg=ALkJrhhSkU3GneqE6fc9m4hC8HzCsZyZNQhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/RP_(complexity)&usg=ALkJrhi-hhWLn9nHcjBnV_WXHPJRCCDCKghttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Random&usg=ALkJrhg_OL4J8mx1jg39uQ0krEUiYCm3zQhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Pseudorandom_number_generator&usg=ALkJrhjc8QLCaSqaTCazMhi6jXyGqQxM-whttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Michael_O._Rabin&usg=ALkJrhj7Ee6b1I_Gqch7nkVi17EEe8tH-whttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Closest_pair_of_points_problem&usg=ALkJrhiqCkAvYzmVIMJzxaSN1S9r-B4w9ghttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Computational_geometry&usg=ALkJrhhSGTJ5VFNov0K8SoKAFJLUG_SEeAhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Solovay-Strassen_primality_test&usg=ALkJrhinC9gDuKmaD-33h57OiTeqkvdBmghttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Primality_test&usg=ALkJrhjuMxSArZy6mcH67hHyDK47BOjFgQhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Robert_M._Solovay&usg=ALkJrhiMCWP7MWOqmhiPwB65QY83qS9U4Ahttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Robert_M._Solovay&usg=ALkJrhiMCWP7MWOqmhiPwB65QY83qS9U4Ahttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Volker_Strassen&usg=ALkJrhgooIbOazz3kZFRRCiS6GfmxSnZewhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Miller-Rabin_primality_test&usg=ALkJrhiaUmMEC5as3TxJsqRm96HLsWVe3Ahttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Deterministic_algorithm&usg=ALkJrhgs6MvAA_Lwn6HLPSQPZ8mh5JERzAhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Prime_number&usg=ALkJrhhSkU3GneqE6fc9m4hC8HzCsZyZNQhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/RP_(complexity)&usg=ALkJrhi-hhWLn9nHcjBnV_WXHPJRCCDCKghttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Random&usg=ALkJrhg_OL4J8mx1jg39uQ0krEUiYCm3zQ


11/14

probabilitas kesalahan dapat dibuat astronomis kecil. Memang, meskipun tes

polinomial-waktu primality deterministik sejak itu telah ditemukan (lihattes AKS

primality ), belum diganti tes probabilistik tua dalam kriptografiperangkat lunak

juga tidak diharapkan untuk melakukannya di masa mendatang.

Motivasi

Sebagai contoh memotivasi, mempertimbangkan masalah dalam

menemukan 'a'dalam sebuah array yang dari n elemen.

Input: Sebuah array n elemen, di mana separuhnya 'a' dan setengah

lainnya adalah 'b's.

Output: Cari 'a'pada array.

Ada dua versi algoritma, satu Las Vegas algoritma dan satu Monte Carlo

algoritma .

Las Vegas algoritma:

Algoritma ini berhasil dengan probabilitas 1. Waktu berjalan

adalah acak (dan sewenang-wenang besar), tetapi harapan adalah atas

dibatasi oleh O

Monte Carlo algoritma:

Jika 'a'ditemukan, algoritma berhasil, algoritma yang lain gagal.

Setelah eksekusi kali k, probabilitas untuk menemukan sebuah 'a'adalah:

P r [f i n d_'a'] = 1 - (1 / 2) k

Algoritma ini tidak menjamin kesuksesan, tapi waktu berjalan

adalah tetap. Pemilihan dieksekusi persis kkali, sehingga runtime adalah

O (k).
http://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/AKS_primality_test&usg=ALkJrhhKNxvY-FS293efYC024xRWpmXYZAhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/AKS_primality_test&usg=ALkJrhhKNxvY-FS293efYC024xRWpmXYZAhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/AKS_primality_test&usg=ALkJrhhKNxvY-FS293efYC024xRWpmXYZAhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Cryptography&usg=ALkJrhhcXqihj8JQEZk5zBO4Jlq6abezowhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Computer_software&usg=ALkJrhhOCqoouKBwCaNF2VCnBLfSr6J4nAhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Array_data_structure&usg=ALkJrhjHL0ArtKtzhGQxLuBcQgtZTK39rAhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Las_Vegas_algorithm&usg=ALkJrhirvhD0G3T4FgeGFuEMinFs8vVS5Ahttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Monte_Carlo_algorithm&usg=ALkJrhhFMcpyNriqToXpNjrFDvR6SKN-mQhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Monte_Carlo_algorithm&usg=ALkJrhhFMcpyNriqToXpNjrFDvR6SKN-mQhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/AKS_primality_test&usg=ALkJrhhKNxvY-FS293efYC024xRWpmXYZAhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/AKS_primality_test&usg=ALkJrhhKNxvY-FS293efYC024xRWpmXYZAhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Cryptography&usg=ALkJrhhcXqihj8JQEZk5zBO4Jlq6abezowhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Computer_software&usg=ALkJrhhOCqoouKBwCaNF2VCnBLfSr6J4nAhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Array_data_structure&usg=ALkJrhjHL0ArtKtzhGQxLuBcQgtZTK39rAhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Las_Vegas_algorithm&usg=ALkJrhirvhD0G3T4FgeGFuEMinFs8vVS5Ahttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Monte_Carlo_algorithm&usg=ALkJrhhFMcpyNriqToXpNjrFDvR6SKN-mQhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Monte_Carlo_algorithm&usg=ALkJrhhFMcpyNriqToXpNjrFDvR6SKN-mQ


12/14

Algoritma acak sangat berguna ketika berhadapan dengan "musuh"

berbahaya ataupenyerang yang sengaja mencoba untuk memberi makan

input buruk untuk algoritma (lihat terburuk kompleksitas dan analisis

kompetitif (algoritma online) ) seperti dalam dilema Tahanan . Ini adalah

alasan inilah keacakan mana-mana dalam kriptografi. Dalam aplikasi

kriptografi, pseudo-acak nomor tidak dapat digunakan, karena musuh

dapat memprediksi mereka, membuat algoritma deterministik efektif.

Oleh karena itu baik sumber nomor benar-benar acak atau Generator

pseudo-random nomor kriptografis mengamankan diperlukan. Daerah

lain di mana keacakan melekat adalah komputasi kuantum.

Dalam contoh di atas, algoritma Las Vegas selalu output jawaban

yang benar, tetapi waktu yang berjalan adalah variabel acak. Algoritma

Monte Carlo (terkait dengan metode Monte Carlo untuk simulasi)

melengkapi dalam jumlah yang tetap waktu (sebagai fungsi dari ukuran

masukan), namun memungkinkan probabilitas kecil kesalahan. Amati

bahwa setiap Las Vegas algoritma dapat diubah menjadi algoritma Monte

Carlo (melalui kesenjangan Markov itu ), oleh karena itu keluaran

jawaban, sewenang-wenang mungkin tidak benar jika gagal untuk

menyelesaikan dalam waktu tertentu. Sebaliknya, jika prosedur verifikasi

yang efisien ada untuk memeriksa apakah jawaban benar, maka algoritma

Monte Carlo dapat diubah menjadi algoritma Las Vegas dengan

menjalankan algoritma Monte Carlo berulang-ulang sampai jawaban yang

benar diperoleh.

Kompleksitas Komputasi

Teori kompleksitas komputasi algoritma acak sebagai model

probabilistikmesin Turing . Kedua Las Vegas dan Monte Carlo algoritma

dianggap, dan beberapa kelas kompleksitas dipelajari. Kelas kompleksitas

paling dasar acak adalah RP , yang merupakan kelas masalah keputusan

yang ada efisien (waktu polinomial) algoritma acak (atau probabilistik

Turing mesin) yang mengakui NO-kasus dengan kepastian yang mutlak
http://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Attacker&usg=ALkJrhgbqS_OiRx_oOuzn9zyrZy69cP5owhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Worst-case_complexity&usg=ALkJrhjSdsyTazh3VDIJmHQzbIUTqT6QRghttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Competitive_analysis_(online_algorithm)&usg=ALkJrhhGff4V2-D2_Ccb_yfmbe08zpwmpAhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Competitive_analysis_(online_algorithm)&usg=ALkJrhhGff4V2-D2_Ccb_yfmbe08zpwmpAhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Prisoner%27s_dilemma&usg=ALkJrhgpoAldO5cTUSBUA7q8rEkVlDt50whttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Randomness&usg=ALkJrhh5THKpk97nT1oGsNC836hb49QH1Qhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Cryptography&usg=ALkJrhhcXqihj8JQEZk5zBO4Jlq6abezowhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Cryptographically_secure_pseudo-random_number_generator&usg=ALkJrhhULrrruRf0lTqguMLL6JGKnBHgOghttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Cryptographically_secure_pseudo-random_number_generator&usg=ALkJrhhULrrruRf0lTqguMLL6JGKnBHgOghttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Quantum_computer&usg=ALkJrhhSNsC3Mrwd8duy59NLOs4mdPsG8ghttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Monte_Carlo_method&usg=ALkJrhiBUN08I4sLLkOmRtJzBdbqrIbzLAhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Markov%27s_inequality&usg=ALkJrhj0a0BcxrKtKgUWWzTFx85fcN33yghttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Computational_complexity_theory&usg=ALkJrhjdJDUDlG6EouKTCDwqrbDYDuInaghttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Probabilistic_Turing_machine&usg=ALkJrhhUecNSI_fKGL0imvBmwnCSyYBkIQhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Turing_machine&usg=ALkJrhiGHWYOITgBqnZiOFsu7ptkrjpdGAhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Las_Vegas_algorithm&usg=ALkJrhirvhD0G3T4FgeGFuEMinFs8vVS5Ahttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Monte_Carlo_algorithm&usg=ALkJrhhFMcpyNriqToXpNjrFDvR6SKN-mQhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Complexity_class&usg=ALkJrhj_JMJ6ckWE2iHypwznErCjg6QQpghttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/RP_(complexity)&usg=ALkJrhi-hhWLn9nHcjBnV_WXHPJRCCDCKghttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Decision_problem&usg=ALkJrhi8ZxZS8vk4wq31JL3P2ErDcpSfVwhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Attacker&usg=ALkJrhgbqS_OiRx_oOuzn9zyrZy69cP5owhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Worst-case_complexity&usg=ALkJrhjSdsyTazh3VDIJmHQzbIUTqT6QRghttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Competitive_analysis_(online_algorithm)&usg=ALkJrhhGff4V2-D2_Ccb_yfmbe08zpwmpAhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Competitive_analysis_(online_algorithm)&usg=ALkJrhhGff4V2-D2_Ccb_yfmbe08zpwmpAhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Prisoner%27s_dilemma&usg=ALkJrhgpoAldO5cTUSBUA7q8rEkVlDt50whttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Randomness&usg=ALkJrhh5THKpk97nT1oGsNC836hb49QH1Qhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Cryptography&usg=ALkJrhhcXqihj8JQEZk5zBO4Jlq6abezowhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Cryptographically_secure_pseudo-random_number_generator&usg=ALkJrhhULrrruRf0lTqguMLL6JGKnBHgOghttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Cryptographically_secure_pseudo-random_number_generator&usg=ALkJrhhULrrruRf0lTqguMLL6JGKnBHgOghttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Quantum_computer&usg=ALkJrhhSNsC3Mrwd8duy59NLOs4mdPsG8ghttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Monte_Carlo_method&usg=ALkJrhiBUN08I4sLLkOmRtJzBdbqrIbzLAhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Markov%27s_inequality&usg=ALkJrhj0a0BcxrKtKgUWWzTFx85fcN33yghttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Computational_complexity_theory&usg=ALkJrhjdJDUDlG6EouKTCDwqrbDYDuInaghttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Probabilistic_Turing_machine&usg=ALkJrhhUecNSI_fKGL0imvBmwnCSyYBkIQhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Turing_machine&usg=ALkJrhiGHWYOITgBqnZiOFsu7ptkrjpdGAhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Las_Vegas_algorithm&usg=ALkJrhirvhD0G3T4FgeGFuEMinFs8vVS5Ahttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Monte_Carlo_algorithm&usg=ALkJrhhFMcpyNriqToXpNjrFDvR6SKN-mQhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Complexity_class&usg=ALkJrhj_JMJ6ckWE2iHypwznErCjg6QQpghttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/RP_(complexity)&usg=ALkJrhi-hhWLn9nHcjBnV_WXHPJRCCDCKghttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Decision_problem&usg=ALkJrhi8ZxZS8vk4wq31JL3P2ErDcpSfVw


13/14

dan mengakui YA-kasus dengan probabilitas minimal 1 / 2. Kelas

melengkapi untuk RP adalah co-RP. Masalah kelas memiliki (mungkin

nonterminating) algoritma dengan waktu polinomial kasus rata-rata waktu

berjalan yang outputnya selalu benar dikatakan dalam ZPP.

Kelas masalah yang baik YA dan TIDAK-contoh yang diizinkan

untuk diidentifikasi dengan beberapa error yang disebut BPP. Kelas ini

bertindak sebagai setara secara acak dari P , yaitu BPP merupakan kelas

dari algoritma acak efisien.

Aplikasi Algoritma Random

Quicksort

Quicksort adalah algoritma, akrab sering digunakan di mana

keacakan dapat berguna. Versi deterministik algoritma ini membutuhkan

O (n 2) waktu untuk menyortir nomor n untuk beberapa kelas yang

didefinisikan dengan baik merosot input (seperti sebuah array yang sudah

diurutkan), dengan kelas khusus input yang menghasilkan perilaku yang

didefinisikan oleh protokol untuk poros seleksi. Namun, jika algoritma

memilih elemen-elemen poros seragam secara acak, ia memiliki

probabilitas tinggi provably menyelesaikan dalam O (n log n) waktu

terlepas dari karakteristik input.

Konstruksi tambahan Acak dalam geometri

Dalam komputasi geometri , teknik standar untuk membangun

struktur seperti convex hull atau Triangulasi Delaunay adalah untuk

menukar urutan acak titik-titik input dan kemudian memasukkan mereka

satu per satu ke dalam struktur yang ada. Pengacakan memastikan bahwa

jumlah yang diharapkan dari perubahan struktur yang disebabkan oleh

penyisipan adalah kecil, sehingga waktu berjalan diharapkan dari

algoritma dapat dibatasi atas. Teknik ini dikenal sebagai konstruksi

tambahan secara acak.
http://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Quicksort&usg=ALkJrhiBD3N0LFAcQFbcZsPBeck0YTWgwghttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Big_O_notation&usg=ALkJrhjFN8pTXhAwXdP5maRUD5Dgopk6pAhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Computational_geometry&usg=ALkJrhhSGTJ5VFNov0K8SoKAFJLUG_SEeAhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Computational_geometry&usg=ALkJrhhSGTJ5VFNov0K8SoKAFJLUG_SEeAhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Convex_hull&usg=ALkJrhjsEpddpDTFWYd5e4Z_d_v1vSCVkQhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Convex_hull&usg=ALkJrhjsEpddpDTFWYd5e4Z_d_v1vSCVkQhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Delaunay_Triangulation&usg=ALkJrhi_-AemGOmLB-SaT0n3z9mm9A3OVwhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/w/index.php%3Ftitle%3DRandomized_incremental_construction%26action%3Dedit%26redlink%3D1&usg=ALkJrhh7jRJer8QlaoAQScqJQy1d7og_zQhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/w/index.php%3Ftitle%3DRandomized_incremental_construction%26action%3Dedit%26redlink%3D1&usg=ALkJrhh7jRJer8QlaoAQScqJQy1d7og_zQhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Quicksort&usg=ALkJrhiBD3N0LFAcQFbcZsPBeck0YTWgwghttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Big_O_notation&usg=ALkJrhjFN8pTXhAwXdP5maRUD5Dgopk6pAhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Computational_geometry&usg=ALkJrhhSGTJ5VFNov0K8SoKAFJLUG_SEeAhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Convex_hull&usg=ALkJrhjsEpddpDTFWYd5e4Z_d_v1vSCVkQhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/wiki/Delaunay_Triangulation&usg=ALkJrhi_-AemGOmLB-SaT0n3z9mm9A3OVwhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/w/index.php%3Ftitle%3DRandomized_incremental_construction%26action%3Dedit%26redlink%3D1&usg=ALkJrhh7jRJer8QlaoAQScqJQy1d7og_zQhttp://translate.googleusercontent.com/translate_c?hl=id&prev=/search%3Fq%3Dalgoritma%2Brandom%26start%3D10%26hl%3Did%26sa%3DN%26biw%3D1280%26bih%3D676%26prmd%3Dimvns&rurl=translate.google.co.id&sl=en&u=http://en.wikipedia.org/w/index.php%3Ftitle%3DRandomized_incremental_construction%26action%3Dedit%26redlink%3D1&usg=ALkJrhh7jRJer8QlaoAQScqJQy1d7og_zQ


14/14

Perkalian matriks memverifikasi

Input:SebuahR Matrix m p,BRp n, dan CRm n.

Output: Benar jika C=A B; false jika CA B

Contoh algoritma Monte Carlo untuk memecahkan masalah.

ANALISA GAME

Langkah pertama pada game kali ini kita diharuskan terlebih dahulu

memasukan nama, memilih level permainan, lalu start. Dalam Game UFO ini,

UFO yang ada akan dimusnahkan dengan menggunakan pointer dengan gambar

Nampak seperti pistol. Memusnahkannya dengan cara menembakkan pistol ke

arah UFO dengan menembak sebanyak-banyaknya untuk mendapatkan score

lebih besar. Jika waktu habis akan menampilkan score dari permainan tersebut.

Tujuan permainan ini adalah untuk mengarahkan target atau sasaran dengan tepat

dan cepat. Jika waktunya habis, terdapat pilihan apakah permainan akan

dilanjutkan atau tidak, jika ingin dilanjutkan pilih ya, jika tidak maka permainan

berakhir.

OUTPUT PROGRAM

kelompok 1 in space

Documents