Apakah ada survei (dari makalah, bab buku, tutorial, tautan, ...) tentang semantik dari berbagai fitur bahasa pemrograman? Saya awalnya kewalahan oleh fitur-fitur D di sini http://www.digitalmars.com/d/2.0/comparison.html Saya ingin melihat apa yang mungkin saya dapat dari sini, walaupun saya...
Saya seorang jurusan matematika yang tertarik pada TCS. Saya ingin mempelajari sendiri algoritme, dan kompleksitasnya untuk menyelesaikan masalah teoretis kelompok seperti urutan elemen, penghitungan coset, menemukan generator, menguji apakah subset yang diberikan menghasilkan grup. Buku apa...
Kita dapat menganggap kompleksitas Kolmogorov dari sebuah string sebagai panjang dari program terpendek P dan input y sedemikian rupa sehingga x = P ( y ) . Biasanya program-program ini diambil dari beberapa set Turing-complete (seperti P mungkin merupakan deskripsi mesin Turing, atau bisa juga...
Jika adalah grafik dengan derajat 3 maksimum dan merupakan minor , maka adalah minor topologiH G HGGGHHHGGGHHH . Wikipedia mengutip hasil ini dari "Grafik Theory" Diestel. Itu terdaftar sebagai Prop 1.7.4 di versi terbaru buku. Buku ini tidak memiliki bukti atau kutipan. Apakah keberadaannya...
Saya mencari referensi (bukan bukti, yang bisa saya lakukan) untuk perpanjangan Chernoff berikut. Misalkan menjadi variabel acak Boolean, tidak harus independen . Sebagai gantinya, dijamin bahwa untuk setiap dan setiap peristiwa yang hanya bergantung pada
Katakanlah grafik memiliki properti M jika simpulnya dapat dipesan v 1 , v 2 , ... v n sedemikian rupa sehingga grafik H i diinduksi oleh simpul { v 1 , ... , v i } memiliki d i s t H i ( v j , v k ) = d i s t G ( v j , vGGGMMMv1,v2,…vnv1,v2,…vnv_1, v_2, \ldots v_nHiHiH_i{v1,…,vi}{v1,…,vi}\{v_1,...
SAT unik adalah masalah yang terkenal: diberi rumus CNF , apakah benar F memiliki satu model?FFFFFF Saya tertarik pada masalah «Persis -SAT»: diberikan rumus CNF F dan integer m > 1 , apakah benar F memiliki model m persis ?mmmFFFm > 1m>1m>1FFFmmm Kedua masalah terlihat serupa. Jadi...
Berapakah lebar pohon minimum dari suatu sirkuit di atas {∧,∨,¬}{∧,∨,¬}\{\wedge,\vee,\neg\} untuk menghitung MAJ? Di sini MAJ :{0,1}n→{0,1}:{0,1}n→{0,1}:\{0,1\}^n \rightarrow \{0,1\} menghasilkan 1 jika setidaknya setengah dari inputnya adalah 111 . Saya hanya peduli tentang ukuran sirkuit...
Jadi kita semua tahu perbandingan-pohon batas bawah pada jumlah perbandingan terburuk yang dibuat oleh algoritma sortir perbandingan (deterministik). Itu tidak berlaku untuk penyortiran perbandingan acak (jika kita mengukur perbandingan yang diharapkan untuk input kasus terburuk). Misalnya, untuk n...
Saya cukup yakin bahwa saya bukan yang pertama untuk menghibur gagasan bahwa saya akan hadir. Namun, akan sangat membantu jika saya dapat menemukan literatur yang terkait dengan ide tersebut. Idenya adalah untuk membangun Mesin Turing M dengan properti bahwa jika P = NP maka M akan menyelesaikan...
Asumsikan seseorang memiliki algoritma acak (BPP) AAA menggunakan rrr bit keacakan. Cara alami untuk memperbesar probabilitas keberhasilannya menjadi 1−δ1−δ1-\delta , untuk setiap δ>0δ>0\delta>0 , adalah Berjalan independen + suara terbanyak: jalankan AAA secara independen...
Ada peneliti yang menunjukkan bahwa menghapus bit harus mengkonsumsi energi, sekarang adakah penelitian yang dilakukan terhadap konsumsi rata-rata algoritma dengan kompleksitas komputasi ? Saya kira, kompleksitas komputasi F ( n ) berkorelasi dengan konsumsi energi rata-rata, harap saya bisa...
Saat ini saya sedang melakukan penelitian Bahasa Formal yang melibatkan kelas-kelas bahasa di atas Reguler tetapi di bawah Konteks Gratis. Saya melihat hal-hal seperti Mesin Multicounter Berbalik-Pembalikan, mesin penghitung tumpukan tunggal, CFL deterministik, dll. Saya ingin tahu apakah ada yang...
Saya harap seseorang tahu referensi untuk ini, jadi saya tidak perlu membaca literatur ... Pertimbangkan urutan angka . Pikirkan urutan sebagai interval . Jelas, urutan asli adalah bitonic jika ada titik pada garis nyata menusuk paling banyak 2 interval. Kita akan merujuk pada urutan di mana titik...
Saya mencari referensi bibliografi untuk algoritme / masalah berikut: Saya menamakannya "BiSelect" atau "t-ary Select" atau "Select in Union of Sorted Arays", tapi saya kira itu diperkenalkan sebelum dengan nama lain? Masalah Pertimbangkan masalah berikut: Mengingat kkk disjoint array yang...
MPA (multipebble automaton) adalah 2DFA (otomat hingga hingga deterministik dua arah) yang dapat menggunakan jumlah kerikil yang sewenang-wenang (sebenarnya paling banyak kerikil pada input yang diberikan - input ditulis pada kaset di antara dua ujung -Penanda sebagai ). Selama perhitungan, MPA...
Jadi, pencarian cepat di web membuat saya percaya bahwa "APXHardness menyiratkan bahwa tidak ada QPTAS untuk suatu masalah kecuali [beberapa kelas kompleksitas] termasuk dalam beberapa [kelas kompleksitas lain]" dan ini juga dikenal! Sepertinya semua orang tahu ini kecuali aku. Sayangnya, tidak ada...
Jika Anda diberi koleksi pesanan parsial, jenis topologi akan memberi tahu Anda jika ada perpanjangan koleksi ke pesanan total (ekstensi dalam hal ini adalah pesanan total yang konsisten dengan masing-masing pesanan parsial). Saya menemukan variasi: Perbaiki satu set . Anda diberikan urutan...
Mengingat komposit jumlah jenderal lapangan saringan terkenal algoritma faktorisasi untuk integer faktorisasi . Ini adalah algoritma acak dan kami mendapatkan kompleksitas yang diharapkan dari faktor . N O ( e √N∈NN∈NN\in\Bbb
Algoritma simpleks sering diperlakukan baik dalam aritmatika nyata, atau dalam dunia diskrit dengan perhitungan yang tepat. Namun, tampaknya paling sering diterapkan dengan aritmatika floating-point. Ini mengarah pada pertanyaan apakah algoritma simpleks harus dianggap sebagai algoritma numerik,...