Dengan asumsi P NP, masalah NP-complete adalah "sulit untuk dipecahkan, tetapi memiliki jawaban yang mudah untuk diperiksa." Apakah masuk akal untuk mempertimbangkan yang sebaliknya, yaitu, masalah yang mudah untuk menghitung jawaban yang benar, tetapi sulit untuk memverifikasi solusi yang diakui...
Saya tertarik pada pertanyaan tentang cara terbaik untuk mengajarkan kelengkapan NP ke jurusan ilmu komputer. Secara khusus, haruskah kita mengajarkannya menggunakan pengurangan Karp atau menggunakan pengurangan Turing? Saya merasa bahwa konsep pelengkapan dan pengurangan NP adalah sesuatu yang...
Saya mencari struktur data yang mendukung pencarian kunci yang efisien (misalnya, jarak Levenshtein untuk string), mengembalikan kecocokan terdekat yang mungkin untuk kunci input. Struktur data yang paling cocok yang saya temukan sejauh ini adalah pohon Burkhard-Keller , tapi saya bertanya-tanya...
Anda punya satu koin. Anda dapat membaliknya sebanyak yang Anda inginkan. Anda ingin menghasilkan bilangan acak rrr sehingga a≤r<ba≤r<ba \leq r < b mana .r,a,b∈Z+r,a,b∈Z+r,a,b\in \mathbb{Z}^+ Distribusi angka harus seragam. Mudah jika :b−a=2nb−a=2nb -a = 2^n r = a + binary2dec(flip n...
Beberapa orang berkata sebagai berikut: Siapa pun yang berusaha menghasilkan angka acak dengan cara deterministik, tentu saja, hidup dalam keadaan berdosa. Itu selalu berarti bahwa Anda tidak dapat menghasilkan angka acak benar hanya dengan komputer. Dan dia mengatakan bahwa ketika komputer...
Jika masalah kedua jenderal itu tidak terpecahkan, bagaimana mungkin kita manusia sepakat tentang berbagai hal? Maksud saya, kita berkomunikasi setiap hari dan memiliki keterbatasan yang sama dengan masalah komunikasi yang ditangani oleh ilmu komputer. Mengapa itu tidak memengaruhi...
Ini pertanyaan dari ujian sebelumnya yang saya coba selesaikan: Untuk grafik tidak terarah dengan bobot positif w ( e ) ≥ 0 , saya mencoba mencari potongan minimum. Saya tidak tahu cara lain untuk melakukan itu selain menggunakan teorema min-cut max-flow. Tetapi grafik tidak diarahkan, jadi...
Apakah ada struktur data untuk mempertahankan daftar yang diurutkan yang mendukung operasi berikut dalam waktu diamortisasi?O(1)O(1)O(1) GetElement (k) : Mengembalikan elemen ke- dari daftar.kkk InsertAfter (x, y) : Masukkan elemen baru y ke dalam daftar segera setelah x. Hapus (x) : Hapus x...
WP memiliki diskusi yang memadai tentang paging , yang saya pikir saya mengerti .. Namun saya bingung dengan artikel yang berulang kali menggunakan istilah Page Frame . Saya pikir bingkai dan halaman adalah hal yang berbeda. Bisakah seseorang tolong menjelaskan
Jika seseorang membangun komputer kuantum universal, akankah hal itu berimplikasi pada masalah P vs
Saya bertanya-tanya apakah ada percobaan yang menunjukkan ada atau tidak adanya korelasi antara penggunaan bahasa dinamis (seperti Python, Ruby, atau bahkan bahasa yang berjalan pada platform Java seperti Groovy, Clojure) melalui bahasa statis (seperti C / C ++), dan perbedaan
Saya telah menemukan beberapa alat pemrograman visual open source seperti Blockly dan teman-teman, dan proyek lain yang dihosting di Github, tetapi tidak dapat menemukan yang bekerja langsung dengan pohon sintaksis abstrak. Mengapa demikian? Saya bertanya karena begitu saya menemukan bahwa setiap...
Cukup sederhana untuk memahami mengapa masalah penghentian tidak dapat diputuskan untuk program tidak murni (yaitu, yang memiliki I / O dan / atau negara bagian bergantung pada negara mesin-global); tetapi secara intuitif, tampaknya program murni berhenti pada komputer yang ideal akan dapat...
Saya membaca buku "Singularitas sudah dekat" yang ditulis oleh Kurzweil dan dia menyebutkan gerbang yang dapat dibalik seperti misalnya gerbang Fredkin . Keuntungan menggunakan gerbang seperti itu adalah kita bisa membuang limbah termal yang terkait dengan perhitungan di mana bit hilang menjadi...
Saya tidak begitu mengerti mengapa rotasi dalam struktur data splay tree memperhitungkan tidak hanya induk dari simpul penilaian, tetapi juga kakek-nenek (operasi zig-zag dan zig-zig). Mengapa yang berikut ini tidak berfungsi: Ketika kita memasukkan, misalnya, simpul baru ke pohon, kami memeriksa...
Apakah ada referensi yang jelas, dengan pseudo-code, tentang bagaimana cara mengimplementasikan juru bahasa Prolog dalam bahasa yang murni fungsional? Apa yang saya temukan sejauh ini tampaknya hanya berurusan dengan bahasa imperatif, hanyalah sebuah demonstrasi dari Prolog yang dilaksanakan dengan...
Salah satu hyperparameter untuk jaringan LSTM adalah suhu. Apa
Sebuah Bloom Filter memungkinkan untuk efisien melacak apakah berbagai nilai telah ditemui selama pengolahan. Ketika ada banyak item data maka filter Bloom dapat menghasilkan penghematan memori yang signifikan di atas tabel hash. Fitur utama dari filter Bloom, yang dibagikan dengan tabel hash,...
Berikut dugaan untuk ekspresi reguler: Untuk ekspresi reguler , biarkan panjang | R | menjadi jumlah simbol di dalamnya, mengabaikan tanda kurung dan operator. Misalnya | 0 ∪ 1 | = | ( 0 ∪ 1 ) ∗ | = 2RRR|R||R||R||0∪1|=|(0∪1)∗|=2|0∪1|=|(0∪1)∗|=2|0 \cup 1| = |(0 \cup 1)^*| = 2 Dugaan: Jika dan...
Jelas tidak ada masalah yang tidak dapat dipastikan dalam NP. Namun, menurut Wikipedia : NP adalah himpunan semua masalah keputusan yang contohnya adalah "ya" memiliki [.. bukti yang] dapat diverifikasi dalam waktu polinomial oleh mesin Turing deterministik. [...] Suatu masalah dikatakan...