Неравенства для колмогоровской сложности и общая информация тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

Используемые обозначения.

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