Pytania otagowane jako it.information-theory

Pytania w teorii informacji

13
Teoria informacji użyta do udowodnienia trafnych twierdzeń kombinatorycznych?
Jakie są twoje ulubione przykłady, w których teoria informacji jest wykorzystywana do udowodnienia zgrabnego kombinatorycznego stwierdzenia w prosty sposób? Niektóre przykłady, które mogę wymyślić, są związane z dolnymi granicami dla dekodowanych lokalnie kodów, np. W tym artykule: załóżmy, że dla wiązki ciągów binarnych długości ma to, że dla każdego , …
10
Zastosowania złożoności Kołmogorowa w złożoności obliczeniowej
Nieformalnie mówiąc, złożoność Kołmogorowa ciągu jest długością najkrótszego programu, który wypisuje . Możemy zdefiniować pojęcie „losowego ciągu” używając go ( jest losowy, jeśli ) Łatwo jest zauważyć, że większość ciągów jest losowa (nie ma tak wielu krótkich programów).x x K ( x ) ≥ 0,99 | x |xxxxxxxxxK.( x ) …
3
Jaka jest objętość informacji?
To pytanie zostało zadane Jeannette Wing po prezentacji PCAST na temat informatyki. „Czy z punktu widzenia fizyki istnieje maksymalna ilość informacji, którą możemy mieć?” (Fajne wyzwanie dla teoretycznej społeczności informatycznej, ponieważ myślę, że rodzi to pytanie „Czym jest informacja?”) Poza „Czym jest informacja?” należy również dowiedzieć się, co oznacza „objętość” …
1
Dobre kody dekodowalne przez obwody liniowe?
Szukam kodów korygujących błędy następującego typu: kody binarne o stałej szybkości, dekodowalny z pewnej stałej części błędów za pomocą dekodera możliwego do zaimplementowania jako logiczny obwód o rozmiarze , gdzie N jest długością kodowania.O ( N)O(N)O(N)N.NN Trochę tła: Spielman, w liniowych kodowalnych i dekodowalnych kodach korygujących błędy , dał kody …
2
Jak dobry jest kod Huffmana, gdy nie ma dużych liter prawdopodobieństwa?
Kod Huffmana dla rozkładu prawdopodobieństwa jest kodem prefiksu o minimalnej średniej ważonej długości słowa kodowego , gdzie jest długością tego słowa kluczowego. Jest dobrze znanym twierdzeniem, że średnia długość na symbol kodu Huffmana zawiera się między a , gdzie jest entropią Shannona rozkładu prawdopodobieństwa.ppp∑piℓi∑piℓi\sum p_i \ell_iℓiℓi\ell_iiiiH(p)H(p)H(p)H(p)+1H(p)+1H(p)+1H(p)=−∑ipilog2piH(p)=−∑ipilog2⁡piH(p) = -\sum_i \, p_i …
3
Czy istnieje związek między normą diamentową a odległością stanów powiązanych?
W teorii informacji kwantowej odległość między dwoma kanałami kwantowymi jest często mierzona za pomocą normy diamentowej. Istnieje również wiele sposobów pomiaru odległości między dwoma stanami kwantowymi, takich jak odległość śladu, wierność itp. Izomorfizm Jamiołkowskiego zapewnia dualność między kanałami kwantowymi a stanami kwantowymi. Jest to dla mnie interesujące, ponieważ norma diamentowa …
1
Złożoność informacji algorytmów zapytań?
Złożoność informacji jest bardzo przydatnym narzędziem w złożoności komunikacji, stosowanym głównie w celu ograniczenia złożoności komunikacyjnej rozproszonych problemów. Czy istnieje analogia złożoności informacji dla złożoności zapytań? Istnieje wiele podobieństw między złożonością zapytań a złożonością komunikacji; często (ale nie zawsze!) dolna granica w jednym modelu zostaje przetłumaczona na dolną granicę w …
1
Skróty filtra Bloom: więcej czy więcej?
Podczas wdrażania filtra Bloom tradycyjne podejście wymaga wielu niezależnych funkcji skrótu. Kirsch i Mitzenmacher pokazali, że tak naprawdę potrzebujesz tylko dwóch, a resztę możesz wygenerować jako kombinacje liniowe. Moje pytanie brzmi: jaka tak naprawdę jest różnica między dwiema funkcjami skrótu i ​​jedną z podwójną entropią? Wynika to z patrzenia na …
5
Przydatność entropii Renyi?
Większość z nas zna - lub przynajmniej słyszała - entropię Shannona zmiennej losowej, H(X)=−E[logp(X)]H(X)=−E[log⁡p(X)]H(X) = -\mathbb{E} \bigl[ \log p(X)\bigr] oraz wszystkie powiązane miary teoretyczne, takie jak entropia względna, wzajemna informacja i tak dalej. Istnieje kilka innych miar entropii, które są powszechnie stosowane w informatyce teoretycznej i teorii informacji, takich jak …
4
Czy eta-równoważność funkcji jest zgodna z sekwencją Haskella?
Lemat: Zakładając, że równoważność eta istnieje (\x -> ⊥) = ⊥ :: A -> B. Dowód: ⊥ = (\x -> ⊥ x)przez eta-równoważność i (\x -> ⊥ x) = (\x -> ⊥)redukcję pod lambda. Raport Haskell 2010, rozdział 6.2 określa seqfunkcję na podstawie dwóch równań: seq :: a -> b …
5
Jaki jest limit danych bezstratnej kompresji? (jeśli istnieje taki limit)
Ostatnio miałem do czynienia z algorytmami związanymi z kompresją i zastanawiałem się, który jest najlepszy współczynnik kompresji, jaki można osiągnąć dzięki kompresji danych bezstratnych. Jak dotąd jedynym źródłem, jakie mogłem znaleźć na ten temat, była Wikipedia: Bezstratna kompresja danych cyfrowych, takich jak wideo, filmy cyfrowe i dźwięk, zachowuje wszystkie informacje, …
5
Dlaczego kodowanie Huffmana eliminuje entropię, której nie ma Lempel-Ziv?
Popularny algorytm DEFLATE wykorzystuje kodowanie Huffmana na Lempel-Ziv. Ogólnie rzecz biorąc, jeśli mamy losowe źródło danych (= 1 bit entropii / bit), żadne kodowanie, w tym Huffman, prawdopodobnie nie skompresuje go średnio. Gdyby Lempel-Ziv był „idealny” (do którego zbliża się większość klas źródeł, ponieważ długość dochodzi do nieskończoności), kodowanie postów …
1
Entropia i złożoność obliczeniowa
Są badacze wykazujący, że bit wymazywania musi zużywać energię, czy teraz są jakieś badania dotyczące średniego zużycia energii algorytmu o złożoności obliczeniowej ? Wydaje mi się, że złożoność obliczeniowa F ( n ) jest skorelowana ze średnim zużyciem energii, mam nadzieję, że mogę tu znaleźć odpowiedź.F(n)F(n)F(n)F(n)F(n)F(n)
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.