Pytania o teorię informacji, entropię i zawartość informacji z różnych źródeł
Czy wszystkie ciągi kodu Morse'a są jednoznacznie rozszyfrowalne? Bez spacji ......-...-..---.-----.-..-..-.. może być, Hello Worldale być może pierwsza litera jest 5- w rzeczywistości wydaje się bardzo mało prawdopodobne, aby dowolna sekwencja kropek i myślników miała unikalne...
Pomysł ten przyszedł mi do głowy jako dziecko uczące się programowania i przy pierwszym spotkaniu z PRNG. Nadal nie wiem, jak realistyczne jest, ale teraz jest wymiana stosów. Oto 14-letni schemat niesamowitego algorytmu kompresji: Weź PRNG i zaszczep go ziarnem, saby uzyskać długą sekwencję...
Według Wikipedii : Entropia Shannona mierzy informacje zawarte w wiadomości, a nie część wiadomości, która jest określona (lub przewidywalna). Przykłady tych ostatnich obejmują nadmiarowość w strukturze języka lub właściwości statystyczne związane z częstotliwościami występowania par liter lub...
Powiedz, że muszę zasymulować następujący rozkład dyskretny: P(X=k)={12N,1−12N,if k=1if k=0P(X=k)={12N,if k=11−12N,if k=0 P(X = k) = \begin{cases} \frac{1}{2^N}, & \text{if $k = 1$} \\ 1 - \frac{1}{2^N}, & \text{if $k = 0$} \end{cases} Najbardziej oczywistym sposobem jest narysowanie losowych...
Mam plik zawierający uporządkowane liczby binarne od do 2 n - 1 :0002)n- 12n−12^n - 1 0000000000 0000000001 0000000010 0000000011 0000000100 ... 1111111111 7z nie skompresował tego pliku bardzo wydajnie (dla n = 20 22 MB zostało skompresowanych do 300 kB). Czy istnieją algorytmy, które potrafią...
Czytam książkę: „ Kod: ukryty język sprzętu i oprogramowania komputerowego ”, aw rozdziale 2 autor mówi: Mówi się, że kod Morse'a jest kodem binarnym (dosłownie dwa na dwa), ponieważ składniki kodu składają się tylko z dwóch rzeczy - kropki i myślnika. Z drugiej strony Wikipedia mówi:...
Niedawno natknąłem się na następujący interesujący artykuł, który twierdzi, że skutecznie kompresuje losowe zestawy danych o zawsze ponad 50%, niezależnie od rodzaju i formatu danych. Zasadniczo używa liczb pierwszych do unikalnego skonstruowania reprezentacji 4-bajtowych fragmentów danych, które...
Porównując parę uporządkowaną (x, y) z parą nieuporządkowaną {x, y} (zestaw), a następnie teoretycznie, różnica wynosi tylko jeden bit, ponieważ to, czy x jest pierwsze, czy y wymaga dokładnie jednego bitu do przedstawienia. Więc jeśli otrzymamy zestaw {x, y}, gdzie x, y to dwie różne 32-bitowe...
Aby zaszyfrować wiadomość za pomocą klawisza jednorazowego k wykonaj E n c ( m 1 , k ) = m 1 ⊕ k .m1m1m_1kkkmin c ( m1, k ) = m1⊕kEnc(m1,k)=m1⊕kEnc(m_1,k) = m_1 \oplus k Jeśli użyjesz tego samego do zaszyfrowania innej wiadomości m 2 , otrzymasz E n c ( m 2 , k ) = m 2 ⊕ k , a jeśli wykonasz Xor...
Masz tablicę różnych elementów. Masz dostęp do komparatora (funkcja czarnej skrzynki, która bierze dwa elementy a i b i zwraca prawdziwy iff a < b ) oraz naprawdę losowe źródło bitów (funkcja czarnej skrzynki nie przyjmuje argumentów i zwraca niezależnie jednakowo losowy bit). Rozważ następujące...
Czytałem o algorytmach kompresji danych i teoretycznym limicie kompresji danych. Ostatnio spotkałem metodę kompresji zwaną „kombinatorycznym kodowaniem entropii”, główną ideą tej metody jest kodowanie pliku jako znaków przedstawionych w pliku, ich częstotliwości i indeksu permutacji tych znaków...
Określenie dowolnej dowolnej siatki 9x9 wymaga podania pozycji i wartości każdego kwadratu. Naiwne kodowanie tego może dać 81 (x, y, wartość) trypletów, wymagając 4 bitów dla każdego x, y i wartości (1-9 = 9 wartości = 4 bity) w sumie 81x4x3 = 972 bitów. Numerując każdy kwadrat, można zmniejszyć...
Według Wikipedii : Nieformalnie, z punktu widzenia algorytmicznej teorii informacji, zawartość informacyjna ciągu jest równoważna długości możliwie najkrótszej możliwej niezależnej reprezentacji tego ciągu. Jaka jest analogiczna nieformalna rygorystyczna definicja „użytecznych informacji”?...
Biorąc pod uwagę ciąg wartości , Shannon Entropy w bazie log wynosi . Z tego, co rozumiem, w bazie Entropia Shannona zaokrąglona w górę to minimalna liczba bitów w systemie binarnym, która reprezentuje jedną z wartości.AAAAAAAABCAAAAAAAABCAAAAAAAABC2220.9220.9220.922222 Zaczerpnięte ze wstępu na...
Obecnie piszę kod do generowania danych binarnych. W szczególności muszę wygenerować liczby 64-bitowe przy określonej liczbie ustawionych bitów; dokładniej, procedura powinna zająć około i zwrócić pseudolosową 64-bitową liczbę z dokładnie bitami ustawionymi na , a resztą ustawioną na 0.0 < n...
W pracy miałem za zadanie wnioskować o pewnych typach informacji o dynamicznym języku. Przepisuję sekwencje instrukcji na letwyrażenia zagnieżdżone , tak jak poniżej: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then { T;...
Próbując zrozumieć związki między kodowaniem Huffmana, kodowaniem arytmetycznym i kodowaniem zakresu, zacząłem myśleć o niedociągnięciach kodowania Huffmana związanych z problemem częściowego upakowania bitów . To znaczy, załóżmy, że masz 240 możliwych wartości dla symbolu i potrzebujesz zakodować...
W teorii kodowania „jak dobry jest kod” oznacza liczbę błędów kanału, które można poprawić lub, mówiąc lepiej, maksymalny poziom szumu, z którym kod może sobie poradzić. Aby uzyskać lepsze kody, kody są zaprojektowane przy użyciu dużego alfabetu (zamiast binarnego). A potem kod jest dobry, jeśli...
Wymóg, aby kodowanie było wolne od prefiksów, skutkuje dużymi drzewami, ponieważ drzewo musi być kompletne. Czy istnieje próg, w którym niekodowane przechowywanie danych o stałej długości byłoby bardziej wydajne niż kodowanie
Problem polega na udowodnieniu lub obaleniu istnienia , st, ; ; . ( oznacza odległość uderzenia)doCC| c | =6,∀c∈C|c|=6,∀c∈C|c| = 6,\forall c\in C| do| =32|C|=32|C| = 32re(doja,dojot) ≥ 2 , 1 ≤ i < j ≤ 32d(ci,cj)≥2,1≤i<j≤32d(c_i,c_j)\geq2,1\leq