Perbedaan dan hubungan antara algoritma acak dan tidak deterministik?

Apa perbedaan dan hubungan antara algoritma acak dan algoritma nondeterministic?

Dari Wikipedia

Sebuah algoritma acak merupakan algoritma yang mempekerjakan tingkat keacakan sebagai bagian dari logika. Algoritme biasanya menggunakan bit acak seragam sebagai input bantu untuk memandu perilakunya, dengan harapan mencapai kinerja yang baik dalam "kasus rata-rata" di atas semua pilihan bit acak yang mungkin. Secara formal, kinerja algoritma akan menjadi variabel acak yang ditentukan oleh bit acak; dengan demikian waktu yang berjalan, atau output (atau keduanya) adalah variabel acak.

Sebuah algoritma non-deterministik adalah suatu algoritma yang dapat menunjukkan perilaku yang berbeda pada berjalan yang berbeda, sebagai lawan dari algoritma deterministik. Ada beberapa cara suatu algoritma dapat berperilaku berbeda dari menjalankan ke menjalankan. Sebuah algoritma bersamaan dapat melakukan berbeda pada berjalan berbeda karena kondisi lomba. Sebuah algoritma probabilistik 's perilaku tergantung pada nomor acak generator. Algoritma yang memecahkan masalah dalam waktu polinomial nondeterministik dapat berjalan dalam waktu polinomial atau waktu eksponensial tergantung pada pilihan yang dibuat selama eksekusi.

Apakah algoritma acak dan algoritma probabilitas adalah konsep yang sama?

Jika ya, apakah algoritma acak hanyalah semacam algoritma nondeterministik?

Algoritma non-deterministik sangat berbeda dari algoritma probabilistik.

Algoritma probabilitas adalah yang menggunakan pelemparan koin, dan bekerja "sebagian besar waktu". Sebagai contoh, varian acak dari quicksort bekerja dalam waktu dengan harapan (dan dengan probabilitas tinggi), tetapi jika Anda kurang beruntung, dapat mengambil sebanyak . Algoritma probabilistik praktis, dan digunakan misalnya oleh komputer Anda saat membuat kunci RSA (untuk menguji bahwa dua faktor kunci rahasia Anda prima). Algoritma probabilistik yang tidak menggunakan lemparan koin kadang-kadang disebut "deterministik".Θ ( n 2$\Theta(n\log n)$$\Theta(n^2)$

Algoritma non-deterministik adalah yang "membutuhkan petunjuk" tetapi selalu benar: mereka tidak dapat dibodohi dengan diberi petunjuk yang salah. Sebagai contoh, di sini adalah algoritma non-deterministik bahwa faktor-faktor integer : menebak faktorisasi , dan memverifikasi bahwa semua faktor yang utama (ada "cepat-in-teori" algoritma deterministik untuk melakukan itu). Algoritma ini sangat cepat, dan menolak petunjuk yang salah. Kebanyakan orang berpikir bahwa algoritma acak tidak dapat memperhitungkan faktor integer dengan cepat. Jelas model komputasi ini tidak realistis.$n$$n$

Mengapa kita peduli dengan algoritma non-deterministik? Ada kelas masalah, yang dikenal sebagai NP, yang terdiri dari masalah keputusan yang memiliki algoritma non-deterministik yang efisien. Kebanyakan orang berpikir bahwa masalah yang paling sulit di kelas itu, yang disebut masalah NP-complete, tidak memiliki algoritma deterministik yang efisien (atau bahkan acak); ini dikenal sebagai pertanyaan P vs NP. Karena banyak masalah alam adalah NP-lengkap, menarik untuk mengetahui apakah sebenarnya mereka tidak dapat dipecahkan secara efisien, dalam kasus terburuk (dalam prakteknya, seringkali contoh yang muncul dalam praktek sebenarnya dipecahkan dalam waktu yang wajar).

Algoritma menentukan metode untuk mendapatkan dari input yang diberikan ke output yang diinginkan yang memiliki hubungan tertentu dengan input. Kami mengatakan bahwa algoritme ini bersifat deterministik jika pada titik mana pun, ditentukan secara pasti dan tidak ambigu apa langkah selanjutnya dalam algoritme yang harus dilakukan sebagai bagian dari metode itu, yang berpotensi bergantung pada input atau sebagian data yang dihitung sejauh ini, tetapi selalu diidentifikasi secara unik.

Nondeterminisme berarti bahwa beberapa bagian dari algoritma dibiarkan atau bahkan tidak ditentukan. Misalnya, "int i = angka genap antara 0 dan n" tidak ditentukan. Ini berarti tidak ada perilaku unik yang ditentukan pada saat ini.

Agar pembedaan ini bermanfaat, Anda memerlukan konsep 'benar' untuk algoritma (deterministik) (yang biasanya), yang secara informal adalah bahwa "algoritme selalu menghitung apa yang ingin saya hitung". Maka menjadi menarik untuk berpikir tentang apa arti kebenaran untuk algoritma nondeterministic, yang harus memperhitungkan pilihan yang mungkin dalam instruksi yang tidak ditentukan.

Ada dua cara mendefinisikan kebenaran untuk nondeterminisme. Yang pertama agak sederhana dan kurang menarik, yang kebenarannya berarti "algoritma selalu menghitung apa yang saya ingin hitung, untuk semua urutan pilihan yang saya boleh buat". Ini kadang-kadang terjadi jika seorang penulis pseudocode sedikit terlalu malas untuk memilih nomor dan mengatakan "pilih angka genap antara 0 dan n", ketika "pilih 0" akan membuat algoritma deterministik. Pada dasarnya, dengan mengganti semua nondeterminisme dengan hasil dari beberapa pilihan, Anda dapat membuat algoritma menjadi deterministik.

Ini juga merupakan 'nondeterminisme' yang disebutkan dalam paragraf kedua Anda. Ini juga merupakan nondeterminisme dalam algoritma paralel: dalam algoritme ini Anda tidak begitu yakin seperti apa eksekusi itu, tetapi Anda tahu bahwa itu akan selalu berhasil, tidak peduli apa yang terjadi secara tepat (jika tidak, algoritma paralel Anda akan salah).

Definisi yang menarik tentang kebenaran untuk algoritma nondeterministic adalah "algoritma selalu menghitung apa yang saya inginkan, untuk beberapa urutan pilihan yang saya boleh buat". Ini berarti bahwa mungkin ada pilihan yang salah, dalam arti bahwa mereka membuat algoritma menghasilkan jawaban yang salah atau bahkan masuk dalam loop yang tak terbatas. Dalam contoh "pilih angka genap antara 0 dan n", mungkin 4 dan 16 adalah pilihan yang benar, tetapi semua angka lainnya salah, dan angka-angka ini dapat bervariasi tergantung pada input, hasil sebagian dan pilihan yang dibuat sejauh ini.

Ketika digunakan dalam ilmu komputer, nondeterminisme biasanya terbatas pada nondeterministik memilih salah satu 0 atau 1. Namun, jika Anda memilih banyak bit seperti nondeterministik, Anda dapat menghasilkan angka nondeterministik panjang atau objek lain, serta membuat pilihan nondeterministik, jadi ini hampir tidak (jika pernah) membatasi penerapannya - jika penerapannya terbatas, nondeterminisme terlalu kuat sejak awal.

Nondeterminism adalah alat yang persis sama kuatnya dengan algoritma deterministik berbasis sertifikat, yaitu, algoritma yang memeriksa properti yang diberikan instance dan sertifikat untuk properti itu. Anda cukup dapat menebak sertifikat untuk satu arah, dan Anda dapat memberikan sertifikat yang berisi semua jawaban 'benar' untuk tebakan nondeterministik 0 dan 1 program Anda untuk arah lain.

Jika kita membuang waktu berlari ke dalam campuran, maka segalanya menjadi lebih menarik. Waktu berjalan dari algoritma nondeterministic biasanya dianggap sebagai minimum dari semua pilihan (kanan). Namun, pilihan lain dapat menyebabkan waktu berjalan yang secara dramatis lebih buruk (yang dapat secara asimptot lebih buruk atau bahkan lebih buruk daripada yang minimum), atau bahkan loop tanpa batas. Inilah mengapa kami mengambil yang minimum: kami tidak peduli dengan kasus-kasus aneh ini.

Sekarang kita sampai pada algoritma acak. Algoritma acak seperti algoritma nondeterministic, tetapi alih-alih 'memperbolehkan' pilihan antara 0 dan 1 pada titik-titik tertentu, pilihan ini ditentukan oleh lemparan koin acak pada saat pilihan harus dibuat (yang mungkin berbeda dari jalankan untuk menjalankan , atau ketika pilihan yang sama harus dibuat lagi nanti selama eksekusi algoritma). Ini berarti bahwa hasilnya adalah 0 atau 1 dengan probabilitas yang sama. Kebenaran sekarang menjadi "algoritma hampir selalu menghitung apa yang saya ingin hitung" atau "algoritma selalu menghitung apa yang saya ingin hitung" (hanya versi deterministik). Dalam kasus kedua, waktu yang dibutuhkan algoritma untuk menghitung jawabannya biasanya 'hampir selalu cepat', berbeda dengan deterministik 'selalu cepat'.

Membandingkan ketiganya: algoritme deterministik secara spesifik menentukan jawaban untuk pilihan itu, nondeterminisme membiarkannya benar-benar terbuka, tetapi memberi tahu Anda jawaban 'benar' ada, dan pengacakan membuat jawaban itu kebetulan. Perhatikan bahwa Anda dapat menebak lemparan koin yang tepat, yang menimbulkan hierarki di antara ketiganya: nondeterminisme sama kuatnya dengan pengacakan, yang pada gilirannya sama kuatnya dengan determinisme, atau, sehubungan dengan waktu polinomial, . Dalam pengaturan ini, tidak ada bukti yang diketahui apakah ada yang benar-benar lebih kuat dari yang lain.$P \subseteq ZPP \subseteq NP$

Singkatnya: non-determinisme berarti memiliki banyak pilihan yang sama validnya tentang bagaimana melanjutkan perhitungan. Pengacakan berarti menggunakan sumber eksternal (acak) bit untuk memandu perhitungan.

Untuk memahami nondeterminisme, saya sarankan Anda melihat finite automata (FA). Untuk FA deterministik (DFA), fungsi transisi adalah, yah, fungsi. Dengan status saat ini dan simbol input berikutnya, status selanjutnya didefinisikan secara unik.

Otomat non-deterministik (NFA), di sisi lain, memiliki hubungan transisi : mengingat kondisi saat ini dan simbol input berikutnya, ada beberapa kemungkinan status berikutnya! Sebagai contoh, pertimbangkan otomat ini untuk bahasa :$(ab)^*(ac)^*$

^{[ sumber ]}

Otomat tebakan yang tanda perbatasan antara dan ; robot deterministik harus menunda keputusannya sampai setelah membaca simbol setelah masing masing .( a b ) ∗ ( a c ) ∗$a$$(ab)^*$$(ac)^*$$a$

Poin kunci di sini adalah bahwa penerimaan didefinisikan sebagai "menerima jika ada proses penerimaan" untuk NFA. Kriteria keberadaan ini dapat diartikan sebagai "selalu menebak dengan benar", meskipun tidak ada dugaan yang sebenarnya.

Perhatikan bahwa tidak ada probabilitas di sini, di mana pun. Jika Anda menerjemahkan nondeterminisme ke dalam bahasa pemrograman, Anda akan memiliki pernyataan yang dapat menyebabkan lompatan ke pernyataan lain yang berbeda dengan status yang sama . Hal semacam itu tidak ada, kecuali mungkin dalam bahasa pemrograman esoteris yang dirancang untuk mengubah pikiran Anda.

Pengacakan sangat berbeda. Jika kami memecahnya, otomat / program tidak memiliki banyak pilihan untuk melanjutkan eksekusi. Setelah bit acak diambil, pernyataan selanjutnya didefinisikan secara unik:

if ( rand() > 5 )
  do_stuff();
else
  do_other_stuff();

Dalam hal automata terbatas, pertimbangkan ini:

^{[ sumber ]}

Sekarang setiap kata memiliki probabilitas, dan automaton mendefinisikan distribusi probabilitas lebih dari (perbedaan antara dan jumlah tepi keluar adalah probabilitas mengakhiri; kata-kata yang tidak dapat diterima memiliki probabilitas ). 1 $\{a,b,c\}^*$$1$$0$

Kita dapat melihat ini sebagai otomat deterministik, mengingat urutan keputusan acak (yang modelnya berlatih dengan sangat baik, karena kita biasanya tidak menggunakan sumber acak nyata); ini dapat dimodelkan sebagai DFA lebih dari mana adalah alfabet yang cukup besar yang digunakan oleh sumber acak.$\Sigma \times \Pi$$\Pi$

Satu catatan terakhir: kita dapat melihat bahwa nondeterminisme adalah konsep yang murni teoretis, tidak dapat diterapkan! Jadi mengapa kita menggunakannya?

1. Ini sering memungkinkan untuk representasi yang lebih kecil. Anda mungkin tahu bahwa ada NFA yang DFA terkecil secara eksponensial sama besar¹. Menggunakan yang lebih kecil hanya masalah penyederhanaan desain robot dan bukti teknis.

2. Terjemahan antar model seringkali lebih mudah jika nondeterminisme diperbolehkan dalam model target. Pertimbangkan, misalnya, mengubah ekspresi reguler menjadi DFA: cara yang biasa (dan sederhana) adalah menerjemahkannya ke NFA dan menentukan yang ini. Saya tidak mengetahui adanya konstruksi langsung.

3. Ini mungkin menjadi perhatian akademis, tetapi menarik bahwa nondeterminisme dapat meningkatkan kekuatan perangkat. Ini tidak berlaku untuk automata terbatas dan mesin Turing, yang dapat diperdebatkan sebagai perangkat model mesin yang paling populer, tetapi misalnya deterministic pushdown-automata, Büchi automata dan top-down tree automata dapat menerima bahasa yang lebih sedikit daripada saudara kandungnya yang non-deterministik².

1. Lihat pertanyaan ini di cstheory.SE untuk contoh.
2. Lihat di sini , di sini dan di sini (Proposisi 1.6.2) , masing-masing.

Anda harus sadar bahwa ada dua definisi berbeda tentang nondeterminisme yang dilemparkan ke sini.

1. Seperti yang didefinisikan oleh wikipedia, cukup banyak "bukan determinisme", yaitu, algoritma apa pun yang tidak selalu memiliki perilaku yang sama pada input yang sama. Algoritma acak adalah kasus khusus dari algoritma "tidak deterministik", karena mereka sesuai dengan definisi yang baru saja saya berikan.

2. Model komputasi nondeterministik (seperti mesin turing nondeterministic) adalah model teoritis komputasi. Mereka mungkin memiliki banyak jalur eksekusi yang mungkin dan mereka "menerima" jika salah satu dari jalur itu menerima. Anda harus perhatikan bahwa itu tidak nyata. Tidak ada cara untuk secara fisik menjalankan algoritma yang tidak deterministik dalam pengertian ini, walaupun Anda dapat mensimulasikannya dengan yang acak atau deterministik.

Dalam CS, nondeterminisme biasanya berarti (2), jadi definisi Wikipedia yang Anda berikan (yaitu (1)) menyesatkan. Sebagian besar jawaban yang diberikan sejauh ini menjelaskan (2), bukan (1).

Meninjau kembali ini karena beberapa penelitian terkait yang saya lakukan, ketidaksepakatan antara saya dan beberapa orang lain yang menjawab, dapat diasimilasi ke dalam pemahaman holistik di mana kita semua benar. Tapi IMO terminologi ilmu komputer yang diadopsi "nondeterminism terikat" adalah oxymoron yang salah (yang saya maksud sebelumnya).

Poin utama mereka adalah untuk membedakan antara nondeterminisme yang terikat dan tidak terikat. [1]

Turing mesin nondeterministic (alias “NTMs”) memiliki bounded nondeterminism di setiap transisi negara memiliki bounded sejumlah kemungkinan, yaitu jumlah program (alias “konfigurasi”) adalah terbatas. Rekaman itu tetap tidak terikat, sehingga bukti pemutusan tetap tidak dapat diputuskan. Tetapi untuk setiap input yang diberikan terhenti, outputnya deterministik dan dibatasi waktu in yaitu untuk input apa pun hasilnya deterministik atau tidak berakhir. Juga NTM mengeksekusi semua konfigurasi yang mungkin secara paralel, sehingga mereka mengeksekusi secara eksponensial lebih cepat daripada emulasi NTM pada mesin Turing deterministik (alias "DTM"). [2]

Benar-benar tidak ada hubungan nondeterministik antara input dan hasil dalam NTM karena hasilnya selalu sama untuk setiap input atau keadaan awal, yang jelas karena mereka dapat ditiru oleh DTMs tanpa tambahan keacakan. [2] Tidak dapat diputuskan bukanlah kebalikan dari deterministik, karena tidak berhenti juga merupakan hasil deterministik. Mesin deterministik selalu memiliki hasil yang sama untuk input yang diberikan, bahkan ketika hasil itu tidak berhenti. Nondeterminisme lokal dari NTM adalah dalam setiap transisi keadaan dari algoritma pelaksana. Tidak dapat ditentukan apriori mana jalur pohon mungkin berakhir memberikan keadaan output. Tetapi ketidakpastian bukanlah bukan determinisme. Dengan demikian istilah "nondeterminisme terbatas" dimaksudkan untuk menggambarkan ketidakpastian penentuan dalam mesin negara tetapi tidak hubungan input dengan hasil, maka konsep "terikat". Saya masih berpikir istilah "nondeterminisme terbatas" adalah sebuah oxymoron dan bisa lebih akurat digambarkan sebagai "transisi keadaan paralel" mesin Turing.

Sedangkan, untuk setiap input atau keadaan awal yang diberikan, nondeterminisme yang tidak terikat (alias "indeterminisme") memiliki sejumlah keadaan yang tidak terbatas. Nondeterminisme tanpa batas melibatkan tidak hanya jumlah kemungkinan konfigurasi program, tetapi juga beberapa kondisi eksternal tidak terikat yang bukan bagian dari input atau keadaan awal, seperti penundaan tanpa batas. Dan dengan demikian hasil dapat bervariasi pada eksekusi berulang untuk input atau kondisi awal yang sama; dengan demikian bukan hubungan deterministik antara input dan hasil. [3]

Algoritma acak dan probabilistik menggunakan beberapa nondeterminisme, yaitu pemilihan acak dari kemungkinan konfigurasi yang mungkin dibatasi oleh sejumlah konfigurasi, tetapi mereka tidak menjalankan semua konfigurasi yang mungkin seperti yang dilakukan oleh NTM. Dengan demikian mereka tidak deterministik kecuali keacakannya deterministik (misalnya PRNG) dan keadaan awal entropi untuk keacakan tersebut dianggap sebagai bagian dari input.

[1] https://en.wikipedia.org/w/index.php?title=Unbounded_nondeterminism&oldid=710628370#Nondeterministic_automata

[2] https://en.wikipedia.org/w/index.php?title=Non-deterministic_Turing_machine&oldid=754212081#Equivalence_with_DTMs

[3] Hewitt, Meijer dan Szyperski: The Actor Model (semua yang Anda ingin tahu ...) . Lompat ke tanda 17:44 menit.

Terlepas dari semua jawaban yang menjelaskan perbedaannya, saya memiliki contoh yang dapat membantu Anda mendapatkan hal yang ingin mereka katakan.
Pertimbangkan koin melemparkan, Anda baik mendapatkan H atau T . Jika lempar koin acak, sangat mungkin bahwa dari 1000 lemparan koin, 500 akan H dan cukup mungkin bahwa 999 dari mereka akan H . Tetapi jika lemparan koin adalah non-deterministik, kita tidak bisa mengatakan bahwa mendapatkan 999 H akan sangat tidak mungkin.

Algoritma acak (waktu polinomial, hasil boolean) berada dalam kelas kompleksitas komputasi RP, yang merupakan subset NP di mana algoritma non-deterministik (waktu polinom, hasil boolean) berada dan superset P di mana deterministik (waktu polinomial, hasil boolean) algoritma berada.

Mengompleks kompleksitas adalah tentang mengurangi masalah dalam satu set ke set lainnya. Jadi RP ⊆ NP tidak mengecualikan kemungkinan algoritma acak yang juga non-deterministik karena secara definitif superset berisi subset. Subset berarti setiap algoritma RP (atau algoritma RP-complete) dapat direduksi menjadi beberapa algoritma NP (atau algoritma NP-complete). P adalah subset dari RP karena setiap masalah dalam P dapat direduksi menjadi masalah dalam RP di mana jumlah entropi yang tidak terkontrol adalah 0.

_{Secara garis besar, ini analog dengan bagaimana setiap masalah dalam NC (komputasi paralel) dapat direduksi menjadi masalah dalam P dengan mensimulasikan komputasi paralel dalam pengurangan ke masalah seri dalam P tetapi belum terbukti bahwa kebalikannya benar, yaitu bahwa setiap masalah dalam P dapat direduksi menjadi masalah di NC, atau terbukti tidak benar, yaitu bukti tidak masuk akal bahwa masalah P-complete tidak dapat direduksi menjadi masalah di NC. Mungkin saja ada masalah yang inheren serial dan tidak dapat dihitung secara paralel, tetapi untuk membuktikan bahwa membuktikan P ≠ NC tampaknya tidak masuk akal (karena alasan yang terlalu tangensial untuk dibahas dalam jawaban ini).}

Lebih umum (yaitu tidak terbatas pada tipe hasil boolean), algoritma acak dibedakan dari algoritma deterministik di mana beberapa entropi bersumber eksternal . Algoritma acak dibedakan dari algoritma non-deterministik karena entropi dibatasi , dan dengan demikian algoritma acak (dan bukan non-deterministik) dapat dibuktikan selalu berakhir.

Ketidakpastian algoritma nondeterministic disebabkan oleh ketidakmampuan untuk menghitung semua kemungkinan permutasi dari input entropi (yang menghasilkan ketidakpastian pemutusan). Ketidakpastian algoritma acak disebabkan oleh ketidakmampuan untuk mengontrolsemua entropi input (yang menghasilkan ketidakpastian hasil yang tak tentu, meskipun tingkat ketidakpastian dapat diprediksi). Tak satu pun dari ini adalah pernyataan tentang ketidakpastian jawaban yang benar untuk masalah tersebut, tetapi ketidakstabilan bermanifestasi masing-masing dalam saluran sampingan pemutusan hubungan kerja dan hasil tak tentu. Tampaknya banyak pembaca menggabungkan ketidakpastian dalam satu area dengan ketidakpastian hasil yang benar, yang merupakan perpaduan yang tidak pernah saya tulis (tinjau riwayat sunting).

Adalah kunci untuk memahami bahwa non-determinisme selalu (dalam ilmu apa pun atau penggunaan istilah) ketidakmampuan untuk menyebutkan entropi universal (yaitu tidak terikat). Sedangkan, pengacakan mengacu pada mengakses sumber entropi lain (dalam program entropi selain dan karenanya tidak di bawah kendali variabel input) yang mungkin atau mungkin tidak terikat.

Saya menambahkan komentar berikut di bawah ini jawaban paling populer saat ini untuk utas lainnya yang menanyakan pertanyaan serupa.

Semua ilmu menggunakan definisi nondeterminisme yang sama yang disatukan pada konsep entropi tanpa batas. Hasil yang tidak dapat diprediksi dalam semua ilmu pengetahuan disebabkan oleh ketidakmampuan untuk menghitung secara apriori semua kemungkinan keluaran dari suatu algoritma (atau sistem) karena ia menerima keadaan yang tidak terikat, yaitu kelas kompleksitas NP. Menentukan input tertentu untuk mengamati apakah itu berhenti dan mencatat bahwa hasilnya idempoten setara dalam ilmu lain untuk menahan sisa entropi konstanta alam semesta sambil mengulangi perubahan keadaan yang sama. Komputasi memungkinkan isolasi entropi ini, sementara ilmu alam tidak.

Menambahkan beberapa komentar terbaik untuk menambahkan klarifikasi poin saya tentang satu-satunya perbedaan yang menonjol antara acak dan tidak deterministik.

Ini benar-benar sangat elegan dan mudah untuk melihat perbedaannya, setelah Anda semua berhenti mengacaukannya dengan mencoba menggambarkannya dari sudut pandang operasional alih-alih dari sudut pandang entropi yang menonjol.

@reinierpost semua orang menggabungkan perbedaan antara acak dan tidak deterministik. Ini menyebabkan komentar Anda kacau. Algoritme merespons interaksi entropi input (variabel) dan kode sumbernya (invarian) entropi internal. Nondeterminisme adalah entropi tanpa batas. Entropi invarian bahkan dapat dibatasi secara internal seperti memperluas digit π . Acak adalah beberapa entropi tidak digabungkan ke input sebagaimana didefinisikan (yaitu mungkin berasal dari panggilan sistem ke /dev/random, atau simulasi keacakan misalnya NFA atau PRNG).

.

@Raphael definisi formal non-deterministic finite automa (NFA) adalah entropi input terbatas (data: 5-tuple). Dengan demikian setiap NFA dapat berjalan pada mesin Turing deterministik, yaitu tidak memerlukan mesin Turing-lengkap nondeterministic. Dengan demikian NFA tidak berada dalam kelas masalah nondeterministik. Gagasan "nondeterminisme" dalam NFA adalah bahwa determinismenya (walaupun jelas ada karena setiap NFA dapat dikonversi menjadi DFA) tidak diperluas secara eksplisit - tidak sama dengan nondeterminisme perhitungan

.

@ Raphael yang diklaim "non-determinisme" dalam NFA adalah benar-benar keacakan adalah pengertian definisi saya tentang perbedaan antara keacakan & nondeterminisme. Definisi saya adalah bahwa keacakan adalah ketika beberapa entropi yang tidak berada di bawah kendali, pengetahuan (, atau ekspansi non-eksplisit yang diinginkan dalam kasus NFA) dari input ke program atau fungsi. Padahal, nondeterminisme sejati adalah ketidakmampuan untuk mengetahui entropi dalam kasus apa pun, karena tidak terikat. Inilah yang dibedakan secara acak dari nondeterminisme. Jadi NFA harus menjadi contoh dari yang pertama, bukan yang terakhir seperti yang Anda klaim.

.

@ Raphael seperti yang sudah saya jelaskan, gagasan non-determinisme dalam NFA berpasangan dengan non-deterministik dengan entropi terbatas. Jadi non-determinisme adalah konsep lokal untuk tidak memperluas determinisme sebagai bentuk kompresi atau kenyamanan, jadi kami tidak mengatakan NFA bersifat non-deterministik, melainkan memiliki tampilan acak ke oracle yang tidak mau menghitung ekspansi deterministik. Tapi itu semua adalah fatamorgana karena disebut diperluas secara deterministik karena entropi tidak terikat, yaitu terbatas.

Kamus adalah alat. Belajarlah menggunakannya.

kata sifat acak

Statistik. atau mengkarakterisasi proses seleksi di mana setiap item dari set memiliki probabilitas yang sama untuk dipilih.

menjadi atau berkaitan dengan suatu himpunan atau elemen himpunan masing-masing yang unsur-unsurnya memiliki probabilitas kejadian yang sama

Jadi pengacakan hanya mensyaratkan bahwa beberapa entropi input harus dapat disetel, yang dengan demikian sesuai dengan definisi saya bahwa beberapa entropi input tidak dikontrol oleh penelepon fungsi. Perhatikan bahwa pengacakan tidak mengharuskan entropi input tidak dapat ditentukan untuk diakhiri.

Dalam ilmu komputer, algoritma deterministik adalah algoritma yang, diberi input tertentu, akan selalu menghasilkan output yang sama, dengan mesin yang mendasarinya selalu melewati urutan negara yang sama.

Secara formal, algoritma deterministik menghitung fungsi matematika; suatu fungsi memiliki nilai unik untuk setiap input dalam domainnya, dan algoritma adalah proses yang menghasilkan nilai khusus ini sebagai output.

Algoritme deterministik dapat didefinisikan dalam istilah mesin negara: keadaan menjelaskan apa yang dilakukan mesin pada saat tertentu dalam waktu tertentu. Mesin negara lolos secara terpisah dari satu kondisi ke kondisi lainnya. Tepat setelah kita memasukkan input, mesin berada dalam keadaan awal atau keadaan mulai. Jika mesin bersifat deterministik, ini berarti bahwa dari titik ini dan seterusnya, kondisi saat ini menentukan apa yang akan terjadi selanjutnya; jalurnya melalui serangkaian negara telah ditentukan sebelumnya. Perhatikan bahwa mesin dapat bersifat deterministik dan masih tidak pernah berhenti atau selesai, dan karena itu gagal memberikan hasil.

Jadi ini memberitahu kita bahwa algoritma deterministik harus sepenuhnya ditentukan oleh keadaan input dari fungsi, yaitu kita harus dapat membuktikan bahwa fungsi tersebut akan berakhir (atau tidak berakhir) dan itu tidak dapat diputuskan. Terlepas dari upaya Wikipedia yang membingungkan untuk menggambarkan nondeterministik, satu-satunya antitesis untuk deterministik seperti yang didefinisikan di atas oleh Wikipedia, adalah algoritma yang kondisi masukan (entropi) tidak jelas. Dan satu-satunya cara negara input dapat didefinisikan dengan tidak jelas adalah ketika tidak terikat (sehingga tidak dapat ditentukan secara deterministik). Inilah yang membedakan mesin Turing nondeterministik (dan banyak program dunia nyata yang ditulis dalam bahasa lengkap Turing umum seperti C, Java, Javascript, ML, dll.) Dari TM deterministik dan bahasa pemrograman seperti HTML, rumus spreadsheet, Coq, Epigram,

Dalam teori kompleksitas komputasi, algoritma nondeterministic adalah algoritma yang, pada setiap langkah yang memungkinkan, dapat memungkinkan untuk beberapa kelanjutan (bayangkan seorang pria berjalan menyusuri jalan di hutan dan, setiap kali ia melangkah lebih jauh, ia harus memilih garpu mana di jalan yang diinginkannya. untuk mengambil). Algoritma ini tidak sampai pada solusi untuk setiap jalur komputasi yang mungkin; namun, mereka dijamin akan tiba pada solusi yang tepat untuk beberapa jalur (yaitu, pria yang berjalan melalui hutan hanya dapat menemukan kabinnya jika dia mengambil beberapa kombinasi jalur yang "benar"). Pilihan dapat diartikan sebagai tebakan dalam proses pencarian.

Wikipedia dan yang lain mencoba untuk mengacaukan pengacakan dengan nondeterminisme, tetapi apa gunanya memiliki dua konsep jika Anda tidak akan membedakannya dengan fasih?

Jelas determinisme adalah tentang kemampuan untuk menentukan. Jelas pengacakan adalah tentang membuat beberapa peralatan entropi.

Termasuk entropi acak dalam keadaan algoritma tidak perlu membuatnya tidak dapat ditentukan. Sebagai contoh, PRNG dapat memiliki distribusi statistik yang dapat dipersyaratkan yang lengkap, namun juga sepenuhnya deterministik.

Konsep ortogonal yang berkembang adalah apa yang orang IQ rendah. Saya berharap lebih baik dari itu dari komunitas ini!