Вопросы с тегом «it.information-theory»

Вопросы в теории информации

54
Теория информации используется для доказательства аккуратных комбинаторных утверждений?

Какие ваши любимые примеры, когда теория информации используется, чтобы доказать аккуратное комбинаторное утверждение простым способом? Некоторые примеры, которые я могу придумать, связаны с нижними границами для локально декодируемых кодов, например, в этой статье: предположим, что для двоичных...

44
Колмогоровские приложения сложности в вычислительной сложности

Неформально говоря, колмогоровская сложность строки - это длина самой короткой программы, которая выводит . Мы можем определить понятие «случайная строка», используя ее ( является случайным, если ). Легко видеть, что большинство строк случайные (коротких программ не так много).х х К ( х ) ≥ 0,99 |...

33
Что такое объем информации?

Этот вопрос был задан Жанетт Уинг после ее презентации PCAST по информатике. «С точки зрения физики, есть ли максимальный объем информации, который мы можем иметь?» (Хороший вопрос для теоретического сообщества информатики, так как я думаю, что возникает вопрос «Что такое информация?») За пределами...

28
Эффективно вычислимые варианты колмогоровской сложности

Сложность префикса Колмогорова (т. Е. K(x)K(x)K(x) - это размер минимальной программы с самоограничением, которая выводит ) имеет несколько приятных особенностей:xxx Это соответствует интуиции предоставления строк с шаблонами или структурой меньшей сложности, чем без строк. Это позволяет определить...

27
Хорошие коды декодируются линейными цепями?

Я ищу коды с исправлением ошибок следующего типа: двоичные коды с постоянной скоростью, декодируется из некоторой постоянной доли ошибок декодером, реализуемым в виде логической схемы размера , где N - длина кодирования.O(N)O(N)O(N)NNN Немного предыстории: Шпильман, в линейном время кодируемого и...

21
Насколько хорош код Хаффмана, когда нет больших букв вероятности?

Код Хаффмана для распределения вероятности - это код префикса с минимальной средневзвешенной длиной кодового слова , где - длина го кодового слова. Хорошо известна теорема о том, что средняя длина каждого символа кода Хаффмана находится между и , где - энтропия Шеннона. распределения вероятностей.∑...

19
Есть ли связь между алмазной нормой и расстоянием связанных состояний?

В квантовой теории информации расстояние между двумя квантовыми каналами часто измеряется с использованием алмазной нормы. Существует также ряд способов измерения расстояния между двумя квантовыми состояниями, таких как расстояние следа, точность и т. Д. Изоморфизм Ямиолковского обеспечивает...

15
Информационная сложность алгоритмов запросов?

Информационная сложность была очень полезным инструментом в сложности коммуникации, в основном используемой для снижения сложности коммуникации в распределенных задачах. Есть ли аналог сложности информации для сложности запросов? Существует много параллелей между сложностью запросов и сложностью...

15
Хэши фильтра Блума: больше или больше?

При реализации фильтра Блума традиционный подход требует нескольких независимых хеш-функций. Кирш и Митценмахер показали, что на самом деле вам нужно только два, а остальные можно сгенерировать как линейные комбинации. Мой вопрос: в чем на самом деле разница между двумя хэш-функциями и одной с...

14
Какой предел сжатия данных без потерь? (если такой предел существует)

В последнее время я имел дело с алгоритмами, связанными со сжатием, и мне было интересно, какая наилучшая степень сжатия может быть достигнута при сжатии данных без потерь. До сих пор единственным источником, который я мог найти по этой теме, была Википедия: Сжатие без потерь оцифрованных данных,...

14
Полезность энтропий Реньи?

Большинство из нас знакомы или, по крайней мере, слышали о энтропии Шеннона случайной величины, H(X)=−E[logp(X)]H(X)=−E[log⁡p(X)]H(X) = -\mathbb{E} \bigl[ \log p(X)\bigr] , и обо всех связанных с этим теоретико-информационных мерах, таких как относительная энтропия, взаимная информация и так далее....

14
Является ли eta-эквивалентность для функций совместимой с операцией seke в Haskell?

Лемма: Предполагая, что эта эквивалентность у нас есть (\x -> ⊥) = ⊥ :: A -> B. Доказательство: ⊥ = (\x -> ⊥ x)по eta-эквивалентности и (\x -> ⊥ x) = (\x -> ⊥)по сокращению под лямбду. В отчете Haskell 2010, раздел 6.2, seqфункция определяется двумя уравнениями: seq :: a -> b...

13
Почему кодирование Хаффмана устраняет энтропию, чего не делает Лемпель-Зив?

Популярный алгоритм DEFLATE использует кодирование Хаффмана поверх Lempel-Ziv. В общем, если у нас есть случайный источник данных (= 1 бит энтропии / бит), никакое кодирование, включая Хаффмана, скорее всего не сожмет его в среднем. Если бы Лемпель-Зив был «идеальным» (что подходит для большинства...

12
Результаты канального кодирования с использованием колмогоровской сложности

Обычно энтропия Шеннона используется для доказательства результатов канального кодирования. Даже для результатов разделения канала источника используется энтропия Шеннона. Учитывая эквивалентность между Шенноном (глобальным) и колмогоровским (локальным) понятиями информации, проводилось ли...

12
Энтропия и вычислительная сложность

Есть исследователь, показывающий, что стирающий бит должен потреблять энергию, а сейчас проводится какое-либо исследование среднего потребления энергии алгоритмом с вычислительной сложностью ? Я предполагаю, что вычислительная сложность F ( n ) коррелирует со средним потреблением энергии, надеюсь,...

12
Об энтропии суммы

Ищу ограничение на энтропии суммы двух независимых дискретных случайных величин и . Естественно, Однако применительно к сумме независимых бернуллиевских случайных величин это дает Другими словами, граница увеличивается линейно с при многократном применении. Однако поддерживается для набора размера...

12
Энтропия свертки над гиперкубом

Скажем, у нас есть функция , такая, что ∑ x ∈ Z n 2 f ( x ) 2 = 1 (поэтому мы можем думать о { f ( x ) 2 } x ∈ Z n 2 как о распределении) , Естественно определить энтропию такой функции следующим образом: H ( f ) = - ∑ x ∈ Z n 2 f ( xf:Zn2→Rf:Z2n→Rf:\mathbb{Z}_2^n \to...

11
Связь между вычислительной сложностью и информацией

Я работаю в вычислительной нейробиологической лаборатории, которая количественно оценивает взаимную информацию между парами или группами нейронов. Недавно босс его сместил акцент на измерение «сложности нейронной динамики». Продолжая эту линию исследований, некоторые люди в моей группе,...

11
Различение между

Для заданного квантового состояния выбрано равномерно случайным образом из набора из N смешанных состояний ρ 1 . , , ρ N , какова максимальная средняя вероятность правильного определения A ?ρAρA\rho_ANNNρ1, , , ρNρ1...ρN\rho_1 ... \rho_NAAA Эту проблему можно превратить в проблему различимости двух...

11
Простая (?) Смешная комбинаторная задача!

Пусть мы зафиксируем 0<E<10<E<10 E \}{i | ci≤E}{i | ci≤E}\{ i ~|~ c_i \leq E \} Итак, докажите это или найдите ошибку! надеясь, что это может быть забавная игра для вас! Мотивация вопроса : Предположим, у вас есть случайная величина , типичная мера «сколько случайности» в - это...