Pytania w teorii informacji
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...
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?”)...
Złożoność prefiksu Kołmogorowa (tj. to rozmiar minimalnego programu do rozgraniczania, który generuje x ), ma kilka fajnych cech:K(x)K(x)K(x)xxx Odpowiada to intuicji nadawania łańcuchom z wzorami lub struktury mniejszej złożoności niż łańcuchy bez. To pozwala nam na zdefiniowanie warunkowego...
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...
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...
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ść...
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...
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...
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...
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 -> b seq ⊥ b =...
Większość z nas zna - lub przynajmniej słyszała - entropię Shannona zmiennej losowej, H(X)=−E[logp(X)]H(X)=−E[logp(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...
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...
Szukam oprawionego na entropii H(X+Y)H(X+Y)H(X+Y) sumy dwóch niezależnych dyskretnych zmiennych losowych i . Oczywiście, Jednak zastosowane do sumy niezależnych zmiennych losowych Bernoulliego , daje to Innymi słowy, granica rośnie liniowo z przy wielokrotnym stosowaniu. Jednak jest obsługiwany...
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źć...
Zwykle do udowodnienia wyników kodowania kanału używana jest entropia Shannona. Nawet w przypadku wyników separacji kanałów źródłowych stosowana jest entropia shannon. Biorąc pod uwagę równoważność między Shannonem (globalnym) a Kołmogorowskim (lokalnym) pojęciem informacji, czy przeprowadzono...
Pracuję w obliczeniowym laboratorium neuronauki, które ocenia ilościowo wzajemną informację między parami lub grupami neuronów. Ostatnio szef skupił się na pomiarze „złożoności dynamiki neuronowej”. Prowadząc tę linię badań, niektórzy ludzie w mojej grupie wydają się utożsamiać „kompleks” z „ma...
Biorąc pod uwagę stan kwantowy wybrany losowo równomiernie ze zbioru N stanów mieszanych ρ 1 . . . ρ N , jakie jest maksymalne średnie prawdopodobieństwo prawidłowej identyfikacji A ?ρAρA\rho_ANNNρ1.. . ρN.ρ1...ρN.\rho_1 ... \rho_NZAZAA Problem ten można przekształcić w problem odróżnialności...
Pozwólmy naprawić 0<E<10<E<10 E \}{i | ci≤E}{i | ci≤E}\{ i ~|~ c_i \leq E \} Udowodnij to lub znajdź błąd! mając nadzieję, że może to być dla ciebie zabawna gra! Motywacja pytania : Załóżmy, że masz losową zmienną , typową miarą „ile losowości” jest w jest...
W artykule Na temat dwóch problemów teorii informacji Erdõs i Rényi wyznaczają dolne granice minimalnej liczby ważeń, które należy zrobić, aby określić liczbę fałszywych monet w zestawie monet.nnn Bardziej formalnie: Fałszywe monety mają mniejszą wagę niż właściwe monety; znane są wagi i...
Chcę zacząć uczyć się o kodowaniu sieci: http://en.wikipedia.org/wiki/Network_coding Czy znasz jakieś dobre ankiety (np. Z ankiet i samouczków IEEE) na powyższe tematy. Znalazłem kilka kursów uniwersyteckich w Google, ale chciałbym uzyskać rekomendacje od osób, które już czytają i znają dobre...