Pertanyaan tentang himpunan terbatas dan tak terbatas dan multiset, struktur dan konsep data terkait.
EDIT: Saya sekarang telah mengajukan pertanyaan serupa tentang perbedaan antara kategori dan set. Setiap kali saya membaca tentang teori jenis (yang memang agak informal), saya tidak dapat benar-benar memahami perbedaannya dari teori himpunan, secara konkret . Saya mengerti bahwa ada perbedaan...
Saya menerapkan serangkaian algoritma pencarian jalur seperti Dijkstra's, Depth First, dll. Awalnya saya menggunakan beberapa grafik yang dibuat sendiri, tapi sekarang saya ingin mengambil tantangan sedikit lebih jauh dan dengan demikian saya mencari grafik yang digunakan dalam tolok...
Ibu saya mengambil kursus online untuk menjadi semacam pustakawan, dalam kursus ini mereka mencakup pencarian boolean, sehingga mereka dapat mencari database secara efisien, namun, dia mendapat pertanyaan yang terdengar seperti ini: Pencarian "x ATAU" akan menghasilkan 105.000 klik, sedangkan...
Judul menyatakan pertanyaan. Kami memiliki sebagai input daftar elemen, yang dapat kami bandingkan (menentukan mana yang terbesar ). Tidak ada elemen yang bisa sama. Poin-poin penting: Perbandingannya bukan transitif (pikirkan gunting kertas batu): ini bisa benar: A> B, B> C, C> A...
Apakah ada struktur data yang memelihara kumpulan himpunan (himpunan terbatas hingga) yang mendukung operasi berikut? Setiap waktu menjalankan sublinear akan dihargai? Init set kosong. Tambahkan elemen ke set. Diberi dua set, laporkan apakah mereka
Saya tahu bahwa sejak ~ 2004, hukum Moore berhenti bekerja untuk kecepatan clock CPU. Saya mencari grafik yang menunjukkan ini, tetapi saya tidak dapat menemukannya: sebagian besar grafik di luar sana menunjukkan jumlah transistor atau kapasitas per tahun. Di mana saya dapat menemukan beberapa...
Wikipedia memiliki definisi berikut tentang lemma pemompaan untuk bahasa biasa ... Biarkan menjadi bahasa biasa. Kemudian ada bilangan bulat ≥ 1 hanya bergantung pada sehingga setiap string dalam panjang setidaknya ( disebut "panjang pemompaan") dapat ditulis sebagai = (yaitu, dapat dibagi...
Penyempurnaan partisi adalah teknik di mana Anda mulai dengan satu set terbatas objek dan semakin membelah set. Beberapa masalah, seperti minimisasi DFA, dapat diselesaikan dengan menggunakan penyempurnaan partisi dengan cukup efisien. Saya tidak tahu ada masalah lain yang biasanya diselesaikan...
Mengingat satu set set, saya ingin menemukan satu set M sehingga setiap set S di S mengandung setidaknya satu unsur M . Saya juga ingin M mengandung elemen sesedikit mungkin sambil tetap memenuhi kriteria ini, meskipun mungkin ada lebih dari satu M terkecil dengan properti ini (solusinya belum...
Aku punya dua set besar bilangan bulat dan . Setiap set memiliki sekitar satu juta entri, dan setiap entri adalah bilangan bulat positif dengan panjang maksimal 10 digit. AAABBB Apa algoritma terbaik untuk menghitung dan ? Dengan kata lain, bagaimana saya bisa secara efisien menghitung daftar...
Saya memiliki masalah algoritmik. Diberikan array (atau set) dari bilangan bulat tidak negatif. Temukan set maksimal dari sedemikian rupa sehingga untuk semua ,.TTTnnnSSSTTTa∈Sa∈Sa\in Sa⩾|S|a⩾|S|a\geqslant |S| Sebagai contoh: Jika TTT = [1, 3, 4, 1, 3, 6], maka SSS dapat menjadi [3, 3, 6] atau...
Ada struktur data yang efisien untuk mewakili sekumpulan partisi. Struktur data ini memiliki kompleksitas waktu yang baik untuk operasi seperti Union dan Find, tetapi mereka tidak terlalu efisien dalam ruang. Apa cara hemat-ruang untuk merepresentasikan partisi sekumpulan? Inilah satu titik awal...
Katakanlah kita memiliki 10 orang, masing-masing dengan daftar buku favorit. Untuk orang tertentu X, saya ingin menemukan subset khusus dari buku X yang hanya disukai oleh X, yaitu tidak ada orang lain yang menyukai semua buku dalam subset khusus X. Saya menganggap subset khusus ini sebagai "sidik...
Satu dapat memahami pertanyaan Anda dalam dua cara, sesuai dengan definisi "pelengkap CFL". kasus A: Komplemen CFL adalah kelas dari semua bahasa yang tidak ada dalam CFL. Secara formal, Dalam hal ini, jauh lebih besar dari , bahkan memiliki bahasa yang tidak ada dalam , dll. Tapi mungkin bukan...
Dalam pertanyaan ini, saya bertanya apa perbedaan antara set dan tipe . Jawaban ini benar-benar mengklarifikasi (misalnya @AndrejBauer), jadi dalam kehausan saya akan pengetahuan, saya tunduk pada godaan untuk menanyakan hal yang sama tentang kategori: Setiap kali saya membaca tentang teori...
Dari bacaan saya tampaknya sebagian besar tata bahasa berkaitan dengan menghasilkan string yang tak terbatas. Bagaimana jika Anda bekerja sebaliknya? Jika diberi n string dengan panjang m, harus dimungkinkan untuk membuat tata bahasa yang akan menghasilkan string itu, dan hanya string itu. Apakah...
Saya mencari implementasi tipe data yang ditetapkan. Kita harus melakukannya memelihara subset dinamis SSS (ukuran nnn ) dari alam semesta dari ukuran denganU={0,1,2,3,…,u–1}U={0,1,2,3,…,u–1}U = \{0, 1, 2, 3, \dots , u – 1\}uuu operasi insert(x)(tambahkan elemen xke ) dan (memeriksa apakah elemen...
Baru-baru ini saya berdiskusi dengan seorang teman tentang sebuah situs web yang mengusulkan tantangan regex, terutama mencocokkan sekelompok kata dengan properti khusus. Dia sedang mencari regex yang cocok dengan string seperti di ||||||||mana jumlah |prima. Saya segera mengatakan kepadanya bahwa...
Menurut Wikipedia, masalah Set Independen adalah kasus khusus dari masalah Set Packing . Tapi, menurut saya masalah ini setara. Masalah pencarian Set Independen adalah: diberi grafikG ( V, E)G(V,E)G(V,E) dan bilangan bulat nnn, Temukan nnn simpul tidak ada dua yang berdekatan. Masalah pencarian...