Pertimbangkan masalah berikut - Mengingat maksimal planar grafik dan G 2 , menemukan graf G dengan jumlah maksimum tepi sehingga ada subgraph (tidak harus diinduksi) di kedua G 1 dan G 2 yang isomorfik ke G .G1G1G_1G2G2G_2GGGG1G1G_1G2G2G_2GGG Bisakah ini dilakukan dalam waktu polinomial? Jika ya,...
Dalam " Saran untuk Mahasiswa Pascasarjana " Manuel Blum : LEONID LEVIN percaya ketika saya melakukan itu, apa pun jawaban untuk P = NP? masalah, itu tidak akan seperti apa pun yang Anda pikir seharusnya. Dan dia telah memberikan beberapa contoh yang indah. Untuk satu, ia telah memberikan...
Pertanyaan ini adalah tentang masalah pemrograman kuadratik dengan kendala kotak (kotak-QP), yaitu masalah optimasi formulir meminimalkan f(x)=xTAx+cTxf(x)=xTAx+cTxf(\mathbf{x}) = \mathbf{x}^T A \mathbf{x} + \mathbf{c}^T \mathbf{x} tunduk pada x ∈[0,1]nx∈[0,1]n\mathbf{x} \in [0,1]^n . Jika...
Saya ingin tahu tentang sejarah dua istilah ini: " efisien ", " layak ". Siapa yang menggunakannya tentang perhitungan / algoritma pertama kali? (dalam pengertian modern istilah ini, yaitu abad ke-20). Bagaimana mereka menjadi arus utama? Bagaimana kedua istilah ini mulai digunakan sebagai...
Saya mencari implementasi algoritma untuk menghitung jalur lebar grafik. Telah diketahui bahwa menghitung lebar jalur setara dengan menghitung angka pencarian simpul, angka pemisahan titik, atau ketebalan interval grafik. Algoritma tidak harus sangat cepat; Saya ingin menjalankannya pada grafik...
Algoritma DEFLATE populer menggunakan Huffman coding di atas Lempel-Ziv. Secara umum, jika kita memiliki sumber data acak (= 1 bit entropi / bit), tidak ada pengkodean, termasuk Huffman, yang cenderung memampatkannya secara rata-rata. Jika Lempel-Ziv "sempurna" (yang mendekati untuk sebagian besar...
Kita diberi grafik asiklik terarah dengan angka yang terkait dengan setiap simpul ( g : V → N ), dan nomor target TG=(V,E)G=(V,E)G=(V,E)g:V→Ng:V→Ng:V\to \mathbb{N} .T∈NT∈NT\in \mathbb{N} The DAG bagian sum masalah (mungkin ada dengan nama yang berbeda, referensi akan menjadi besar) menanyakan...
Branch and bound adalah heuristik yang efektif untuk masalah pencarian, dan Wikipedia mencantumkan sejumlah masalah sulit di mana branch-and-bound telah digunakan. Namun, saya belum dapat menemukan referensi untuk menyarankan bahwa itu lebih dari sekedar "satu metode" untuk menyelesaikan masalah...
Bab 1 buku Metode Probabilistik, oleh Alon dan Spencer menyebutkan masalah berikut: Diberikan grafik , putuskan apakah konektivitas tepinya setidaknya n / 2 atau tidak.GGGn/2n/2n/2 Penulis menyebutkan adanya sebuah algoritma oleh Matula dan meningkatkan ke O ( n 8 / 3 log n )
O ( log n )HAI(catatann)O({\log}n)O ( m + n )HAI(m+n)O(m+n) Apa algoritma paralel yang paling dikenal untuk st-konektivitas dalam grafik planar terarah? Silakan sebutkan waktu berjalan, algoritma deterministik / acak dan model PRAM yang digunakan (dengan asumsi jumlah prosesor adalah...
Dalam makalah oleh Kempe-Kleinberg-Tardos, Penulis mengusulkan algoritma rakus berdasarkan fungsi submodular untuk menentukan paling berpengaruh node dalam grafik, dengan aplikasi untuk jaringan sosial.kkk Pada dasarnya algoritma berjalan sebagai berikut: S= e m p t y s e t S=emhalty setS = {\rm...
Saya menemukan masalah ini di bidang fisika yang cukup jauh dari ilmu komputer, tetapi sepertinya jenis pertanyaan yang telah dipelajari di CS, jadi saya pikir saya akan mencoba peruntungan saya menanyakannya di sini. Bayangkan Anda diberi satu set titik dan daftar beberapa jarak antara titik d i...
Saya membaca kertas "Fast Paxos" oleh Leslie Lamport dan terjebak dengan bukti kebenaran dari Paxos klasik dan Fast Paxos. Untuk konsistensi, nilai vvv dipilih oleh koordinator dalam fase 2a2a2a di babak iii harus memuaskan CP(v,i):CP(v,i):CP(v,i): Untuk setiap rondej<ij<ij < i , tidak...
Fungsi-set adalah submodular monoton jika untuk semua , A , B f ( A ) + f ( B ) ≥ f ( A ∪ B ) + f ( A ∩ B ) .fffA , BSEBUAH,BA,Bf( A ) + f( B ) ≥ f( A ∪ B ) + f( A ∩ B ) .f(SEBUAH)+f(B)≥f(SEBUAH∪B)+f(SEBUAH∩B). f(A) + f(B) \geq f(A \cup B) + f(A \cap B). Properti yang lebih kuat adalah f( A ) +...
Salah satu teman saya bertanya kepada saya masalah penjadwalan berikut di pohon. Saya menemukan ini sangat bersih dan menarik. Apakah ada referensi untuk itu? Masalah: Ada pohon , setiap sisi memiliki biaya perjalanan simetris 1 . Untuk setiap simpul v i , ada tugas yang harus dilakukan sebelum...
Pada tahun 1973 Weiner memberikan pembangunan pohon akhiran linear pertama kali. Algoritma disederhanakan pada tahun 1976 oleh McCreight, dan pada tahun 1995 oleh Ukkonen. Namun demikian, saya menemukan algoritma Ukkonen relatif terlibat secara konseptual. Apakah ada penyederhanaan pada algoritma...
Saya memiliki masalah aljabar yang berhubungan dengan vektor di bidang GF (2). Misalkan menjadi (0,1) -vektor dimensi n , dan m = n O ( 1 ) . Cari algoritma waktu polinomial yang menemukan (0,1) -vector u dari dimensi yang sama seperti yang u bukanlah jumlah dari setiap ( log n ) O ( 1 ) vektor...
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...
Dalam pekerjaan saya masalah berikut muncul: Apakah ada algoritma yang diketahui, yang mendekati jumlah kromatik grafik tanpa urutan 65 yang independen? (Jadi alpha (G) <= 64 diketahui dan | V | / 64 adalah lebih rendah sepele, | V | batas atas sepele. Tetapi apakah ada perkiraan yang lebih...
Pertimbangkan masalah tes keanggotaan abelian-subkelompok berikut ini . Input: Sebuah kelompok abelian berhingga dengan sewenang-wenang-besar .G=Zd1×Zd1…×ZdmG=Zd1×Zd1…×ZdmG=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m}didid_i Sebuah pembangkit-set dari subkelompok...