Diberikan satu set n pekerjaan dengan [waktu mulai, waktu selesai, biaya] menemukan subset sehingga tidak ada 2 pekerjaan yang tumpang tindih dan biaya maksimum. Sekarang saya tidak yakin apakah algoritma serakah akan melakukan trik. Yaitu, urutkan berdasarkan biaya dan selalu mengambil...
Saya punya sedikit masalah untuk memahami bukti Teorema Time Hierarchy (Hennie and Stearns, 1966) yang memastikan keberadaan bahasa yang dapat diterima dalam tetapi tidak dapat diterima dalam untuk fungsi apa pun , sehingga dapat dikonstruksi waktu
Jika Anda memiliki bahasa L, tanpa melakukan bukti apa pun, adakah cara untuk mengetahui apakah itu dapat dikenali atau dikenali bersama atau dapat dipilih? Pada dasarnya ada petunjuk atau trik yang bisa digunakan untuk menceritakannya. Atau mungkin pola umum untuk mencari tahu jenis apa...
Apakah PC kami berfungsi sebagai Mesin Turing? Model Mesin Turing terdiri dari pita memori tak terbatas, yang berarti status tak terbatas. Tapi anggaplah jika PC kita memiliki 128 MB memori dan 30GB disk itu akan memiliki 256 ^ 30128000000 negara dan dengan demikian, ia memiliki status yang...
Pertimbangkan masalah ini: Diberikan grafik tidak terarah G=(V,E)G=(V,E)G = (V, E), Temukan G′=(V′,E′)G′=(V′,E′)G' = (V', E') seperti yang: G′G′G' adalah subgraph yang diinduksi dari GGG G′G′G' tidak memiliki 3-klik |V′||V′||V'| maksimal Jadi jumlah simpul paling sedikit harus...
Dari grafik isomorfisme, kita tahu bahwa dua grafik A dan B adalah isomorfik jika ada matriks permutasi P sehingga A = P× B ×P- 1SEBUAH=P×B×P-1A = P \times B \times P^{-1} Jadi, untuk menyelesaikan masalah, jika dua grafik isomorfis, kita perlu menemukan matriks permutasi P. Masalahnya diyakini...
Membiarkan LLLmenjadi bahasa biasa. Buktikan bahwa: L+−−={w:∃u|u|=2|w|∧wu∈L}L+−−={w:∃u|u|=2|w|∧wu∈L}L_{+--}=\left\{w: \exists_u |u|=2|w| \wedge wu\in L\right\} L++−={w:∃u2|u|=|w|∧wu∈L}L++−={w:∃u2|u|=|w|∧wu∈L}L_{++-}=\left\{w: \exists_u 2|u|=|w| \wedge wu\in L \right\}...
Model paralel teoretis mana yang paling dekat dengan model pemrograman CUDA / OpenCL? Misalnya, ini cocok pada tingkat tertentu dengan model Mesin Akses Acak Paralel (PRAM) generik. Namun, itu terlalu umum, karena membuat abstraksi dari berbagai latensi akses memori dan masalah
Saya mencoba (secara intuitif) memahami dua istilah "decidability" dan "verifiability". Saya telah melakukan banyak pencarian dan pencarian berbagai teks yang dapat saya lakukan. Namun, pemahaman intuitif mereka nampaknya lepas dari saya, khususnya untuk yang kedua. Dari banyak definisi yang...
Pertimbangkan masalah alam semesta berikut ini . Masalah alam semesta. Diberikan himpunan terbatas untuk kelas bahasa, dan otomat yang menerima bahasa , putuskan apakah .ΣΣ\SigmaLLLL=Σ∗L=Σ∗L=\Sigma^* Dalam [1], dinyatakan dan dibuktikan bahwa masalah alam semesta tidak dapat diputuskan untuk...
Slide kuliah ini membuat sketsa bukti ituL={anbn∣n≥0}∪{anb2n∣n≥0}L={anbn∣n≥0}∪{anb2n∣n≥0}L=\{ a^n b^n \mid n \geq 0 \} \cup \{ a^n b^{2n} \mid n \geq 0 \} tidak dapat diterima oleh Deterministic Pushdown Automaton. Sayangnya, slide tidak memberikan referensi ke mana bukti itu berasal. Saya...
Tentukan kesetaraan Nerode di atas bahasa sebagai iff untuk setiap .L⊆Σ∗L.⊆Σ∗L \subseteq \Sigma^{*}u∼Lvkamu∼L.vu \sim_L vuw∈L⇔vw∈Lkamuw∈L.⇔vw∈L.uw \in L \Leftrightarrow vw \in Lw∈Σ∗w∈Σ∗w \in \Sigma^{*} Nerode ekivalen memiliki banyak kelas ekivalensi tepat ketika dapat dikenali oleh otomat...
Diberikan grafik , cari simpul , yang penghapusan akan menghasilkan grafik dengan komponen terkecil terkecil. G=(V,E)G=(V,E)G = (V, E)kkk{v∗1,…,v∗k}{v1∗,…,vk∗}\{v^*_1,\dots,v^*_k\} Saya berasumsi untuk besardan besar masalahnya sulit (NP-keras), tapi saya tertarik pada nilai kecil ( ).n=|V|n=|V|n...
Ini agak terkait dengan pertanyaan lain yang saya ajukan , tetapi saya merasa itu cukup berbeda untuk menjamin pertanyaannya sendiri. Saya sedang melakukan penelitian di mana saya mencoba untuk menemukan struktur pelengkap kelas tertentu dari bahasa yang terbatas. Sangat mudah bagi saya untuk...
Saat menghitung ketergantungan runtime pada input, perhitungan apa yang dipertimbangkan? Sebagai contoh, saya pikir saya belajar bahwa pengindeksan array serta pernyataan tugas tidak dihitung, mengapa
Saat ini saya sedang mengerjakan tesis master saya, dan ini tentang pengelompokan pada grafik. Saya bekerja dengan ide menggunakan semut untuk menyelesaikan masalah. Saat ini saya sedang mengerjakan implementasinya dan saya bertanya-tanya seberapa baik merepresentasikan tepi grafik. Setiap sisi...
Diberikan array bilangan bulat yang diurutkan, saya ingin menemukan jumlah pasangan yang berjumlah . Misalnya, mengingat , jumlah pasangan yang dijumlahkan menjadi nol adalah .000{ - 3 , - 2 , 0 , 2 , 3 , 4 }{−3,−2,0,2,3,4}\{-3,-2,0,2,3,4\}222 Misalkan adalah jumlah elemen dalam array input. Jika...
Menurut CLRS, algoritma Prim diimplementasikan seperti di bawah ini - MST-PRIM (G,w,r)MST-PRIM(G,w,r)\mathtt{\text{MST-PRIM}}(G,w,r) untuk setiap lakukanu ∈ V[ G ]u∈V[G]u \in V[G] kunci [u]←∞key[u]←∞\mathtt{\text{key}}[u] \leftarrow \infty π[ u ] ← NILπ[u]←NIL\pi[u] \leftarrow...
Saya seorang Ph.D. mahasiswa dalam ilmu komputer, dan saya mencoba untuk memahami beberapa makalah teori permainan klasik, seperti yang oleh Nash, Kalai dan Smorodinsky. Tetapi saya merasa sulit untuk memahami bagian matematika. Tampaknya makalah ini ditulis oleh ahli matematika, untuk ahli...
Saya mencari algoritme yang menyediakan string kanonik untuk grafik berwarna yang diberikan. Yaitu. sebuah algoritma yang mengembalikan string untuk grafik, sehingga dua grafik mendapatkan string yang sama jika dan hanya jika mereka isomorfik. Secara khusus, saya mencari algoritma sederhana yang...