RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Скоро в журнале
Архив
Импакт-фактор
Правила для авторов
Лицензионный договор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Труды МИАН:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Тр. МИАН, 2011, том 274, страницы 103–118 (Mi tm3316)  

Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)

О совместной условной сложности (энтропии)

Н. К. Верещагинa, Ан. А. Мучник

a Кафедра математической логики и теории алгоритмов, Механико-математический факультет, Московский государственный университет им. М. В. Ломоносова, Москва, Россия

Аннотация: Колмогоровская сложность слова $b$ при известном $a$ определяется как минимальная длина программы, перерабатывающей $a$ в $b$. Мы обобщаем это понятие на четверки слов $a,b,c,d$: их совместной условной сложностью $K((a\to c)\land(b\to d))$ называется минимальная длина программы, перерабатывающей $a$ в $c$, а $b$ в $d$. В работе доказано, что совместная условная сложность не выражается через обычные условные и безусловные сложности. Вопрос о существовании задачи о переработке информации, сложность которой не выражается через обычные условные и безусловные сложности, был поставлен А. Шенем на одном из заседаний Колмогоровского семинара в МГУ в 1994 г. Наш результат дает положительный ответ на этот вопрос. Кроме того, мы доказываем аналогичные утверждения и для классической шенноновской энтропии. Мы приводим два различных доказательства обоих результатов – “эффективное” и “квазиэффективное”. В заключение мы приводим квазиэффективное доказательство усиленного варианта известного результата о существовании слов с невыделяемой общей информацией. Ранее было известно только неэффективное доказательство этого утверждения.

Полный текст: PDF файл (242 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Proceedings of the Steklov Institute of Mathematics, 2011, 274, 90–104

Реферативные базы данных:

Тип публикации: Статья
УДК: 510.5
Поступило в июне 2011 г.

Образец цитирования: Н. К. Верещагин, Ан. А. Мучник, “О совместной условной сложности (энтропии)”, Алгоритмические вопросы алгебры и логики, Сборник статей. К 80-летию со дня рождения академика Сергея Ивановича Адяна, Тр. МИАН, 274, МАИК «Наука/Интерпериодика», М., 2011, 103–118; Proc. Steklov Inst. Math., 274 (2011), 90–104

Цитирование в формате AMSBIB
\RBibitem{VerMuc11}
\by Н.~К.~Верещагин, Ан.~А.~Мучник
\paper О совместной условной сложности (энтропии)
\inbook Алгоритмические вопросы алгебры и логики
\bookinfo Сборник статей. К~80-летию со дня рождения академика Сергея Ивановича Адяна
\serial Тр. МИАН
\yr 2011
\vol 274
\pages 103--118
\publ МАИК «Наука/Интерпериодика»
\publaddr М.
\mathnet{http://mi.mathnet.ru/tm3316}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2962936}
\elib{http://elibrary.ru/item.asp?id=16766474}
\transl
\jour Proc. Steklov Inst. Math.
\yr 2011
\vol 274
\pages 90--104
\crossref{https://doi.org/10.1134/S008154381106006X}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000295983200005}
\elib{http://elibrary.ru/item.asp?id=23965217}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84912009353}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/tm3316
  • http://mi.mathnet.ru/rus/tm/v274/p103

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. Ewert W., Dembski W.A., Marks Ii R.J., “Measuring Meaningful Information in Images: Algorithmic Specified Complexity”, IET Comput. Vis., 9:6 (2015), 884–894  crossref  isi  elib
    2. Lukas L., Plevny M., “Using entropy for quantitative measurement of operational complexity of supplier-customer system: case studies”, Cent. Europ. J. Oper. Res., 24:2, SI (2016), 371–387  crossref  mathscinet  zmath  isi  elib  scopus
    3. Lukas L., Hofman J., “Operational Complexity of Supplier-Customer Systems Measured by Entropy-Case Studies”, Entropy, 18:4 (2016), UNSP 137  crossref  mathscinet  isi  elib  scopus
  • Труды Математического института им. В. А. Стеклова Proceedings of the Steklov Institute of Mathematics
    Просмотров:
    Эта страница:293
    Полный текст:20
    Литература:46
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019