Pertanyaan dalam Teori Informasi
Secara informal, kompleksitas Kolmogorov dari string adalah panjang dari program terpendek yang menghasilkan x . Kita dapat mendefinisikan gagasan 'string acak' yang menggunakannya ( x adalah acak jika K ( x ) ≥ 0,99 | x | ) Mudah untuk melihat bahwa sebagian besar string adalah acak (tidak ada...
Pertanyaan ini diajukan kepada Jeannette Wing setelah presentasi PCAST tentang ilmu komputer. "Dari perspektif fisika, apakah ada volume maksimum informasi yang dapat kita miliki?" (Pertanyaan tantangan yang bagus untuk komunitas ilmu komputer teoretis karena saya pikir itu menimbulkan...
Kompleksitas awalan Kolmogorov (yaitu adalah ukuran program pembatasan-diri minimal yang menghasilkan x ) memiliki beberapa fitur bagus:K(x)K(x)K(x)xxx Ini sesuai dengan intuisi memberikan string dengan patters atau struktur kompleksitas yang lebih rendah daripada string tanpa. Hal ini...
Saya mencari kode koreksi kesalahan dari jenis berikut: kode biner dengan laju konstan, didekodekan dari beberapa fraksi konstan kesalahan, oleh decoder diimplementasikan sebagai sirkuit Boolean ukuran , di mana N adalah panjang pengkodean.O(N)O(N)O(N)NNN Beberapa latar belakang: Spielman,...
Kode Huffman untuk distribusi probabilitas adalah kode awalan dengan panjang codeword rata-rata tertimbang minimum , di mana adalah panjang dari kata sandi ke- . Ini adalah teorema yang terkenal bahwa panjang rata-rata per simbol kode Huffman adalah antara dan , di mana adalah entropi Shannon dari...
Dalam teori informasi kuantum, jarak antara dua saluran kuantum sering diukur menggunakan norma intan. Ada juga sejumlah cara untuk mengukur jarak antara dua keadaan kuantum, seperti jarak jejak, kesetiaan, dll. Isomorfisma Jamiołkowski memberikan dualitas antara saluran kuantum dan keadaan...
Kompleksitas informasi telah menjadi alat yang sangat berguna dalam kompleksitas komunikasi, terutama digunakan untuk membatasi kompleksitas komunikasi dari masalah yang didistribusikan. Adakah analog kompleksitas informasi untuk kompleksitas kueri? Ada banyak persamaan antara kompleksitas kueri...
Dalam menerapkan filter Bloom, pendekatan tradisional membutuhkan beberapa fungsi hash independen. Kirsch dan Mitzenmacher menunjukkan bahwa Anda sebenarnya hanya membutuhkan dua, dan dapat menghasilkan sisanya sebagai kombinasi liniernya. Pertanyaan saya adalah: apa, sungguh, perbedaan antara dua...
Akhir-akhir ini saya telah berurusan dengan algoritma yang berhubungan dengan kompresi, dan saya bertanya-tanya mana yang merupakan rasio kompresi terbaik yang dapat dicapai dengan kompresi data lossless. Sejauh ini, satu-satunya sumber yang dapat saya temukan tentang topik ini adalah...
Lemma: Dengan asumsi kesetaraan eta kita memilikinya (\x -> ⊥) = ⊥ :: A -> B. Bukti: ⊥ = (\x -> ⊥ x)dengan kesetaraan eta, dan (\x -> ⊥ x) = (\x -> ⊥)dengan pengurangan di bawah lambda. Laporan Haskell 2010, bagian 6.2 menentukan seqfungsi dengan dua persamaan: seq :: a -> b...
Sebagian besar dari kita akrab dengan - atau setidaknya pernah mendengar tentang - entropi Shannon dari variabel acak, H(X)=−E[logp(X)]H(X)=−E[logp(X)]H(X) = -\mathbb{E} \bigl[ \log p(X)\bigr] , dan semua informasi terkait - ukuran teoretis seperti entropi relatif, informasi timbal balik, dan...
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...
Saya mencari terikat pada entropi dari jumlah dari dua variabel acak diskrit independen X dan Y . Tentu, H ( X + Y ) ≤ H ( X ) + H ( Y ) ( * ) Namun, diterapkan dengan jumlah dari n independen Bernoulli variabel acak Z 1 , ... , Z n , ini memberikan H ( Z 1 +H( X+ Y)H(X+Y)H(X+Y)XXXYYYH( X+ Y) ≤...
Katakanlah kita memiliki fungsi , sedemikian sehingga β x ∈ Z n 2 f ( x ) 2 = 1 (sehingga kita dapat menganggap { f ( x ) 2 } x ∈ Z n 2 sebagai distribusi) . Itu wajar untuk mendefinisikan entropi dari suatu fungsi seperti berikut: H ( f ) = - Σ x ∈ Z n 2 f ( xf: Zn2→ Rf:Z2n→Rf:\mathbb{Z}_2^n \to...
Biasanya entropi Shannon digunakan untuk membuktikan hasil pengkodean saluran. Bahkan untuk hasil pemisahan sumber-saluran digunakan shannon entropy. Mengingat kesetaraan antara pengertian Shannon (global) vs Kolmogorov (lokal) tentang informasi, apakah telah ada penelitian untuk memanfaatkan...
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...
Saya bekerja di laboratorium ilmu saraf komputasi yang menghitung informasi timbal balik antara pasangan atau kelompok neuron. Baru-baru ini, bosnya menggeser fokusnya untuk mengukur "kompleksitas dinamika saraf". Dalam mengejar garis penelitian itu, beberapa orang dalam kelompok saya tampaknya...
Diberikan status kuantum dipilih secara acak dari sekumpulan negara campuran , berapakah probabilitas rata-rata maksimum untuk mengidentifikasi dengan benar ? N ρ 1 . . . ρ N AρSEBUAHρA\rho_ANNNρ1. . . ρNρ1...ρN\rho_1 ... \rho_NSEBUAHAA Masalah ini dapat diubah menjadi dua masalah pembedaan status...
Mari kita perbaiki 0<E<10<E<10 E \}{i | ci≤E}{i | ci≤E}\{ i ~|~ c_i \leq E \} Jadi, Buktikan atau temukan bug! berharap itu bisa menjadi permainan lucu untuk Anda! Motivasi dari pertanyaan : Misalkan Anda memiliki variabel acak , ukuran khas "berapa banyak keacakan" yang ada di...
Saat ini saya sedang mencari subjek untuk tesis dan menemukan bidang teori informasi algoritmik. Lapangan itu tampaknya sangat menarik bagi saya, tetapi tampaknya semuanya adalah lapangan yang telah dilakukan sebelum bertahun-tahun. Jadi pertanyaan saya adalah: Apakah bidang itu "hidup" atau cukup...