Неравенства для колмогоровской сложности и общая информация

ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

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. Принято в печать.

Показать весь текст

Заполнить форму текущей работой

Другие работы

Позитронная спектроскопия В2-соединений титана и сплавов системы In-Tl, испытывающих термоупругие мартенситные превращения

Проблема устойчивости фаз в металлических сплавах является одной из центральных в физике конденсированного состояния. Особый интерес представляют исследования физической природы и механизмов термоупругих мар-тенситных превращений (МП) в сплавах, обладающих практически важным эффектом памяти формы. Аномальное поведение электронных и решеточных свойств в области температур, предшествующих МП в этих…

Диссертация