Алгоритмический подход Колмогорова. Сложность объекта K(y).

Автор темы ph (philip) 
ОбъявленияПоследний пост
ОбъявлениеРаботодателям и кадровым агентствам: Размещение вакансий26.03.2008 03:07
ОбъявлениеЗапущен новый раздел «Задачки и головоломки»29.08.2019 00:42
ОбъявлениеОткрыта свободная публикация вакансий для математиков26.09.2019 16:34
Форумы Список тем Новая тема
28.09.2004 04:05
ph (philip)
Алгоритмический подход Колмогорова. Сложность объекта K(y).
В алгоритмическом подходе опеределения количества информации Колмогорова есть такая формула количества информации: I(x:y) = K(y) - K(y|x). Так вот, если со "сложностью" алгоритма K(y|x) мне вроде бы немного понятно, то со "сложностью объекта y" K(y) неясность полная. Как эту сложность K(y) вычислить? Если кто знает, помогите, плиз.
Все слова в кавычках - от Колмогорова (см. напр. статью: Колмогоров А.Н. Три подхода к опрелению понятия "количество информации".)
Заранее благодарен любой поддержке.

Ответить Цитировать
28.09.2004 11:09
sonte
Колмогоровская сложность
Функция K(x) перечислима сверху, но невычислима, более того, не имеет нетривиальных вычислимых нижних оценок.

Литература:
А.К. Звонкин, Л.А. Левин. Сложность конечных объектов и обоснование теории информации и случайности с помощью теории алгоритмов. Успехи математических наук, т. 25, вып.6, 1970, сс. 85-127.
M. Li, P.M.B. Vitanyi. An Introduction to Kolmogorov Complexity and Its Applications. Springer, 1997.
В.А. Успенский, Н.К. Верещагин, А. Шень. Колмогоровская сложность. (в процессе написания; кусочек лежит на http://lpcs.math.msu.su/~ver/kolm-book/shen-rus.ps.Z)
Ответить Цитировать
29.09.2004 04:55
ph (philip)
Сложность = энтропия = информация
Sonte, большое спасибо за ответ.
Но в связи с ним у меня возникает нехороший вопрос: если К(у) невычислима, то можно ли говорить о вычислении количества информации вообще? Ведь нам для вычислений фактически доступна лишь условная энтропия К(у|х) объекта Y относительно X. Иными словами, можно ли в этом случае говорить, что количество информации I(x:y) численно равно минимальной длине алгоритма "X->Y" (условной энтропии): I(x:y)=K(y|x)? И имеет ли это под собой какое-то строгое обоснование?

Ответить Цитировать
29.09.2004 10:58
В.П.
условная сложность тоже не вычислима
Условная колмогоровская сложность K(y|x) также недоступна для вычисления как и K(y). Можно получать только верхние оценки.
Информация в x об y + сложность построения y, если задано x
даёт сложность y, т.е. I(x:y) +K(y|x)= K(y).
Другое дело, если рассматривается энтропия и условная энтропия. Тогда при заданных условных вероятностях все компаненты аналогичной формулы легко можно вычислить.

Ответить Цитировать
« Следующая тема   Предыдущая тема »
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти