Beberapa algoritma pembelajaran mesin yang populer seperti Regresi Logistik atau Neural networks memerlukan inputnya untuk numerik. Yang saya tertarik adalah bagaimana Anda membuat algoritma ini bekerja pada input non-numerik (seperti string pendek). Sebagai contoh, katakanlah kita sedang...
Bayangkan saya memiliki pemesanan pada banyak elemen seperti: Di mana panahX←YX←YX \leftarrow Y berarti . Ini juga transitif: .X<YX<YX < Y(X<Y)∧(Y<Z)⟹(X<Z)(X<Y)∧(Y<Z)⟹(X<Z)\left(X < Y\right) \wedge \left(Y < Z\right) \implies \left(X < Z\right) Agar dapat menjawab...
Membiarkan x=(x1,…,xn)x=(x1,…,xn)x=(x_1,\dots,x_n) dan y=(y1,…,yn)y=(y1,…,yn)y=(y_1,\dots,y_n) menjadi nnn-vektor variabel boolean. Saya memiliki predikat booleanQ(x,y)Q(x,y)Q(x,y) di x,yx,yx,y. Saya memberi teman saya PriscillaQ(x,y)Q(x,y)Q(x,y). Sebagai tanggapan, dia memberi sayaP(x)P(x)P(x),...
Bagi saya yang mengambil seluruh grafik, norma dari vektor kesalahan harus menurun secara monoton, jika tidak kita tidak dapat menjamin bahwa PageRank akan pernah bertemu. Namun, apakah hal yang sama berlaku pada basis per-simpul? Yaitu, dari iterasi t ke iterasi t + 1, apakah kesalahan kuadrat...
Saya punya grafik GkGkG_k dan HkHkH_k dengan | V(Gk) | = | V(Hk)|2 k=n2 k|V(Gk)|=|V(Hk)|2k=n2k|\mathcal{V}(G_k)|=|\mathcal{V}(H_k)|^{2k}=n^{2k} dengan k∈Nk∈Nk\in\Bbb Nyang lulus pemeriksaan kewarasan seperti lemma tanpa homomorfisme. Apakah ada alat gratis dan mudah digunakan untuk menguji...
Saya mengalami kesulitan memahami mengapa mudah mendeteksi siklus bobot negatif (Bellman Ford) tetapi sulit menemukan siklus bobot maksimum dalam grafik yang tidak diarahkan. Jika kita meniadakan bobot masing-masing sisi, kita dapat dengan mudah menemukan apakah ada siklus dengan berat total>...
Saya seorang sarjana ilmu komputer yang masih muda, dan saya diminta untuk menulis makalah yang melibatkan faktorisasi bilangan bulat. Akibatnya, saya harus melihat algoritma Shor pada komputer kuantum. Untuk algoritma lain, saya dapat menemukan persamaan khusus untuk menghitung jumlah instruksi...
Saya telah mencoba cukup lama untuk menemukan konstruksi sehingga saya dapat secara resmi menunjukkan bahwa PDA deterministik ditutup dengan komplementasi. Namun, kebetulan setiap ide yang saya dapatkan memiliki sesuatu yang pada akhirnya tidak cocok. Bisakah Anda membantu saya? Masalah utama...
Baru-baru ini, saya membaca makalah tentang dikotomi . Saya tidak mengerti kondisi apa yang bisa disebut dikotomi ? Apa arti dari "sebuah pertanyaan baik di P atau di NP - lengkap "? (asumsikan P NP )≠≠\neq Sebagai contoh, saya sudah tahu teorema dikotomi Schaefer, di mana dikotomi tentang...
Saya belajar tentang analisis asimptotik, dan telah melihat beberapa kerumitan yang terlihat eksotis yang hidup di antara yang umum lainnya. Misalnya "log log n" adalah antara 1 dan log n. Itu membuat saya bertanya-tanya apakah seseorang dapat selalu menemukan kompleksitas di antara dua...
Karena ada kalkulus lambda yang tidak diketik, dan kalkulus lambda yang diketik sederhana (seperti yang dijelaskan, misalnya, dalam buku Jenis dan Bahasa Pemrograman Benjamin Pierce), apakah ada logika kombinatorik yang diketik secara sederhana? Sebagai contoh, akan terlihat bahwa tipe alami untuk...
Inilah pertanyaan yang mungkin naif yang telah menggelitik saya: Apakah ada Ω (n--√3)Ω(n3)\Omega(\sqrt[3]{n})batas bawah asimptotik untuk menangani memori besar sewenang-wenang secara acak? Penyebab kepercayaan saya adalah bahwa jalur terpendek ke memori yang disimpan secara fisik harus melalui...
Kita tahu bahwa P = NP menyiratkan NP = coNP. Apakah implikasi sebaliknya berlaku? Apakah NP sama dengan BNP menyiratkan bahwa P sama dengan NP? Jika tidak, mengapa tidak? Saya mencari di Google tetapi tidak menemukan
Seperti yang telah saya pelajari, memutuskan keteraturan bahasa bebas konteks tidak dapat diputuskan. Namun, kita dapat menguji keteraturan menggunakan teorema Myhill – Nerode yang menyediakan kondisi yang diperlukan dan memadai. Jadi masalahnya harus diperhitungkan. Di mana kesalahan...
Misalkan saya ingin mengoptimalkan fungsi unimodal yang didefinisikan pada beberapa interval nyata. Saya dapat menggunakan algoritma terkenal seperti yang dijelaskan dalam Wikipedia dengan nama pencarian ternary . Dalam kasus algoritma yang berulang kali membagi dua interval, adalah umum untuk...
Baru-baru ini saya telah berurusan dengan masalah yang mengarahkan saya ke pertanyaan-pertanyaan berikut: Apakah ada algoritma yang baik untuk menghitung semua pencocokan maksimum / sempurna dalam grafik umum? Apakah ada algoritma yang baik untuk menemukan semua pencocokan maksimum / sempurna...
Biarkan , di mana dan untuk semua .L={an∣n≥0}L={an∣n≥0}L = \{a^n \mid n \ge 0\}a0=ϵa0=ϵa^0 = \epsilonan=an−1aan=an−1aa^n = a^{n-1}an≥1n≥1n \ge 1 Jadi terdiri dari urutan dari semua panjang, termasuk urutan panjang . Mari menjadi subset tak terbatas . Saya perlu menunjukkan selalu ada DFA untuk...
Biarkan menjadi DAG. Kita tahu bahwa beberapa node dalam adalah "buruk", sementara yang lain "baik"; keturunan dari simpul buruk adalah buruk sedangkan nenek moyang dari simpul baik adalah baik. Kita juga tahu bahwa node buruk memiliki elemen minimal unik di yang ingin kami tanyakan sesedikit...
Secara berkala saya menemukan kalimat seperti "Varian Winograd [20] dari algoritma ini, yang kompleksitas asimptotiknya juga dianggap" (dari https://www.cise.ufl.edu/~sahni/papers/strassen.pdf )O(n2.81)O(n2.81)O(n^{2.81}) Saya memahami secara intuitif bagaimana kita berakhir dengan kompleksitas...
Saya membaca teorema empat warna dan bertanya-tanya apakah ada aplikasi praktisnya. (Saya rasa memisahkan peta menjadi empat warna berbeda dapat dianggap sebagai aplikasi.) Saya mencoba Googling untuk aplikasi tetapi tidak dapat