Неравенства для колмогоровской сложности и общая информация
Muchnik An.A., Shen A., Romashchenko A., Vereshchagin N.K. Upper semi-lattice of binary strings with the relation x is simple conditional to у. // Preprint DIMACS TR 97−74, Rutgers University, 1997. Чисар И., Кернер Я. Теория информации. Теоремы кодирования для дискретных систем без памяти. // М.: Мир. 1985. Hammer D., Romashchenko A., Shen A., Vereshchagin N. Inequalities for Shannon Entropy and… Читать ещё >
Содержание
- Используемые обозначения
- 1. Р-типичность и Р-случайность
- 2. Неравенства для колмогоровской сложности и шеннонов-ской энтропии
- 3. Полурешетки с отношением условной простоты
- 4. Пары с нематериализуемой взаимной информацией
- 4. 1. Стохастические пары
- 4. 2. Пары ортогональных подпространств
Актуальность темы. Одна из первых работ А. Н. Колмогорова по теории алгоритмической сложности называлась «Три подхода к определению понятия „количество информации“». Двумя из трех рассмотренных подходов были энтропия Шеннона и алгоритмическая (или колмо-горовская) сложность. В этой, а также в нескольких последующих работах ([3, 4]) Колмогоров указывал на связь данных понятий и параллелизм их свойств. Один из простейших примеров параллелизма свойств шенноновской энтропии и колмогоровской сложности — симметричность шенноновской взаимной информации и симметричность взаимной информации по Колмогорову. Другим, нетривиальным примером является аналогичность свойств двух родственных понятий — введенных П. Гачем и Я. Кернером общей информации пары случайных величин и общей информации пары слов [9]. Гач и Кёрнер исследовали свойства общей информации пар случайных величин и пар слов методами теории вероятностей. В ряде других работ [5, 13, 15] свойства общей информации пар слов изучались алгоритмическими методами.
Многие естественные свойства колмогоровской сложности и шенноновской энтропии формулируются с помощью линейных неравенств. Ряд нетривиальных неравенств для колмогоровской сложности, а также их
приложения изучались в [10, 11]. В [16] рассматривалась связь между выразимыми с помощью линейных неравенств свойствами колмогоровской сложности и шенноновской энтропии.
Таким образом, к различным вопросам теории информации разработаны вероятностный и алгоритмический подходы. Многие параллельные понятия из классической и алгоритмической теории информации имеют аналогичные свойства. Изучение данного параллелизма является важной задачей, находящейся на границе двух дисциплин — теории вероятностей и математической логики.
Целью данной работы является изучение классов линейных неравенств, выполняющихся для колмогоровских сложностей произвольных наборов слов и для шенноновских энтропии произвольных случайных величин, а также усиление результатов Гача и Кернера [9] и Ан. А. Мучника [5, 13], касающихся алгоритмического варианта понятия общей информации.
Методы исследования. В работе применяются методы теории алгоритмов и теории вероятностей.
Научная новизна. Все основные результаты работы являются новыми и состоят в следующем:
1) Доказано совпадение классов линейных неравенств, выполняющихся для колмогоровской сложности слов и шенноновской энтропии дискретных случайных величин.
2) Показано, что неравенство Инглетона не выполняется для колмогоровской сложности и шенноновской энтропии.
3) Доказано, что определенные в [15] отношения условной простоты на последовательностях слов задают частичные порядки, являющиеся верхними полурешетками, но не являющиеся нижними полурешетками.
4) Построены два новых класса примеров пар слов, имеющих большую взаимную информацию и нулевую общую информацию. Получен положительный ответ на вопрос Ан. А. Мучника [13] о возможности дополнить любое слово до пары с большой взаимной и нулевой общей информацией.
Приложения. Работа носит теоретический характер. Полученные результаты относятся к теории колмогоровской сложности и могут применяться в классической и алгоритмической теории информации.
Апробация работы. Результаты диссертации докладывались на Научно-исследовательском семинаре по математической логике в МГУ (руководители академик РАН проф. С. М. Адян и проф. В. А. Успенский), а также на Колмогоровском семинаре кафедры математической логики и теории алгоритмов мех.-мат. факультета МГУ (руководители проф. Н. К. Верещагин, д. ф.-м. н. А. Л. Семенов и к. ф.-м. н. А. X. Шень).
Публикации. Основные результаты диссертации опубликованы в работах [15, 16, 17, 18].
Для полноты изложения в диссертации приводятся теоремы 2 и 3, не принадлежащие автору. Данные результаты доказаны Н. К. Верещагиным, А. X. Шенем и Д. Хаммером (и опубликованы в совместной работе [16]). Исследуемая в диссертации формализация отношения условной простоты была предложена А. X. Шенем.
Структура работы. Работа состоит из введения, 4 глав и списка литературы, содержащего 18 наименований. Общий объем диссертации — 88 страниц.
Неравенства для колмогоровской сложности и общая информация (реферат, курсовая, диплом, контрольная)
1. Звонкин А. К., Левин Л. А. Сложность конечных объектов и обоснование понятий информации и случайности с помощью теории алгоритмов. // УМН. 1970. Т. 25, № 6, С. 85−127.
2. Колмогоров А. Н. Три подхода к определению понятия «количество информации». // Проблемы передачи информации, 1965. Т. 1, № 1, С. 3−11.
3. Колмогоров А. Н. К логическим основам теории информации и теории вероятностей. // Проблемы передачи информации. 1969. Т. 5, '№, С. 3−7.
4. Колмогоров А. Н. Комбинаторные основания теории инфориации и исчисления вероятностей. // УМН. 1983. Т. 38, № 4, С. 27−36.
5. Мучник Ан.А. О выделении общей информации двух слов. // Тез. докл. Первого Всемирного Конгресса Общ-ва матем. статист, и теории вероятностей им. Бернулли. М.: Наука. 1986. С. 453.
6. Чисар И., Кернер Я. Теория информации. Теоремы кодирования для дискретных систем без памяти. // М.: Мир. 1985.
7. Шёнфилд Дж. Степени неразрешимости. // М.: Наука. 1977.
8. Ширяев А. Н. Вероятность. // М.: Наука. 1989.
9. Gaes P., Korner J. Common Information is Far Less Then Mutual Information. // Probl. of Control and Inform. Theory. 1973. V. 2, № 2, P. 149−162.
10. Hammer D., Shen A. A Strange Application of Kolmogorov Complexity. // Theory of Computing Systems. 1998. V. 31, P. 1−4.
11. Hammer D. Complexity inequalities. Wissenschaft & Technik Verlag, Berlin, ISBN 3−89 685−479−8, 1998. 143 pp.
12. Ingleton A. W. Representation of matroids. In: Welsh D.J.A., editor. Combinatorial Mathematics and its applications. Academic Press (London), 1971. P. 149−167.
13. Muchnik An.A. On Common Information. // Theoretical Computer Science. 1998. V. 207, P. 319−328.
14. Uspensky V.A. Shen A. Relations between varieties of Kolmogorov complexities. // Mathematical system theory. 1996. V. 29, № 3, P. 271−292.
15. Muchnik An.A., Shen A., Romashchenko A., Vereshchagin N.K. Upper semi-lattice of binary strings with the relation x is simple conditional to у. // Preprint DIMACS TR 97−74, Rutgers University, 1997.
16. Hammer D., Romashchenko A., Shen A., Vereshchagin N. Inequalities for Shannon Entropy and Kolmogorov Complexity. // Journal of Computer and System Sciences. 2000. V. 60, P. 442−464.
17. Ромащенко A.E. Пары слов с нематериализуемой общей информацией. Проблемы передачи информации. 2000. Т. 36, Вып. 1, С. 3−20.
18. Ромащенко А. Е. Полурешетка последовательности слов с отношением условной простоты. // Вестник Московского Университета, 2000. Принято в печать.