раздел математич. логики, уточняющий и изучающий на базе понятий алгоритма и вычислимой функции основные понятия теории информации. А. т. и. стремится обосновать эти понятия без помощи обращения к теории вероятностей и так, чтобы понятия энтропии и количества информации были применимы к индивидуальным объектам. Наряду с этим она порождает и свои собственные проблемы, связанные с изучением энтропии конкретных индивидуальных объектов. Центральным понятием А. т. и. является понятие энтропии индивидуального объекта, называемое сложностью объекта (по Колмогорову). Интуитивно под этим понимается минимальное количество информации, необходимое для восстановления данного объекта. Точное определение понятия сложности индивидуального объекта и на основе этого понятия количества информации в индивидуальном объекте уотносительно индивидуального объекта хбыло дано А. Н. Колмогоровым в 1962-65, что и послужило началом развития А. т. и. Без существенных ограничений общности можно рассматривать только двоичные слова (что в дальнейшем и будет делаться). Под сложностью еловая понимается длина l(р).самого короткого (двоичного) слова р, содержащего всю информацию, необходимую для восстановления хпри помощи к.-л. фиксированного способа декодирования. Точное определение этого понятия следующее. Пусть F(s) - произвольная словарная частично рекурсивная функция. Тогда под сложностью слова хпо Fпонимается: Слово ртакое, что F(р)=х, наз. кодом, или программой, по к-рой Fвосстанавливает слово х. Имеет место теорема: существует частично рекурсивная функция F0 (называемая оптимальной) такая, что для любой частично рекурсивной функции Fвыполняется неравенство: где CF - константа, не зависящая от х. Эта теорема позволяет дать инвариантное (с точностью до аддитивной константы) определение сложности: сложностью К(х).слова хназ. сложность по нек-рой раз и навсегда фиксированной оптимальной частично рекурсивной функции F0. Очевидно, , где С - константа, не зависящая от х. Используя К(х), можно определить также сложность K( х, у).пар слов ( х, у):для этого пары ( х, у).эффективно кодируются в виде одного слова с( х, у), и под сложностью К( х, у).понимается К(с( х, у)). П. Мартином-Лёфом был исследован вопрос о том, как ведет себя сложность начальных кусков бесконечных двоичных последовательностей. Пусть означает начальный кусок последовательностп , составленной из первых пзнаков. Тогда почти все (относительно меры Лебега) бесконечные двоичные последовательности обладают свойствами: а) для бесконечно многих натуральных псправедливо неравенство где с - нек-рая константа; б) для всех натуральных и, больших нек-рого , где - произвольное положительное число (теорема Мартина-Лёфа). С другой стороны, для любой последовательности существует бесконечно много натуральных птаких, что < Понятие сложности используется также при изучении алгоритмич. проблем. Здесь более естественной является так наз. сложность разрешения слова х. Интуитивно под этим понимается минимальное количество информации, к-рую надо иметь, чтобы по каждому числу найти г-й знак слова (длину снова хпри этом можно и не знать). Точнее, под сложностью разрешения слова по частично рекурсивной функции понимается Имеет место теорема: существует частично рекурсивная функция (называемая оптимальной) такая, что для любой другой частично рекурсивной функции Gвыполняется неравенство где - константа, не зависящая от х. Сложностью разрешения слова наз. сложность по нек-рой раз и навсегда фиксированной оптимальной частично рекурсивной функции С 0. Очевидно, <: и Используя , можно для любого множества натуральных чисел Мопределить сложность для п-куска множества М:, где - характеристическая последовательность множества (=1, если , и ,, если ). Алгоритмич. проблемы обычно могут быть представлены в виде проблемы вхождения в нек-рое рекурсивно перечислимое множество М. Если мы фиксируем некрое пи ограничиваемся рассмотрением проблемы вхождения в Мтолько для первых пнатуральных чисел, то мы получаем ограниченную алгоритмическую проблему. Величина интуитивно выражает количество информации, к-рую надо иметь, чтобы можно было решить данную ограниченную проблему. В частности, множество Мрекурсивно тогда и только тогда, когда ограничено сверху нек-рой константой. Из теоремы Мартина-Лёфа следует существование множеств, для к-рых При этом оказывается, что максимально сложные множества уже существуют среди множеств, задаваемых арифметич. предикатами с двумя кванторами. Однако в случае рекурсивно перечислимых множеств имеет место теорема: а) для любого рекурсивно перечислимого множества Ми любого псправедливо неравенство где не зависит от ; б) существует рекурсивно перечислимое множество Мтакое, что для любого имеет место неравенство В то же время существуют такие рекурсивно перечислимые множества М, что при ограничении времени вычислений произвольной общерекурсивной функцией tимеет место оценка не зависит от . В указанных терминах можно дать также характеристику универсальных по нек-рому типу сводимости множеств (см. Универсальное множество):множество Мявляется слабо таблично универсальным тогда и только тогда, когда существует неограниченная общерекурсивная функция такая, что для любого имеет место неравенство
При изучении сложности ограниченных алгоритмич. проблем иногда используются и другие меры сложности, как, напр., минимальная длина изображения нормального алгорифма, решающего данную ограниченную проблему. Но оказывается, что между введенными выше сложностями и аналогами этих сложностей, выраженными через минимальную длину изображения нормального алгорифма (или через минимальное число внутренних состояний машины Тьюринга), существуют асимптотически точные соотношения (см. Алгоритма сложность). При построении А. т. и. вводится еще понятие у с-ловной сложности слова хпри известном упо частично рекурсивной функции : Для этого понятия также имеет место теорема о существовании оптимальной функции , и условная сложность слова хпри известном уопределяется как сложность по век-рой раз и навсегда фиксированной оптимальной функции интуитивно обозначает минимальное количество информации, к-рое необходимо добавить к информации, содержащейся в слове у, чтобы можно было восстановить слово х. Очевидно,. Следующим центральным понятием А. т. и. является понятие количества информации в индивидуальном объекте y относительно индивидуального объекта х: Величину наз. алгоритмическим количеством информации в об Соответственно величины наз. иногда а л-горит ми ческой энтропией хи алгоритмической условной энтропией хпри заданном . Формулы разложения энтропии и коммутативности информации верны в алгоритмич. концепции лишь с точностью до членов порядка O(logH(X,Y): Между алгоритмич. и классич. определениями количества информации (точнее, между сложностью слова по Колмогорову и энтропией распределения частот по Шеннону) существует определенная связь (А. Н. Колмогоров): пусть задано число rи пусть слово хдлины состоит из слов длины г, причем k-e слово длины rвходит в хс частотой , тогда где и при . В общем случае более тесную связь между энтропией и сложностью установить нельзя. Это объясняется тем, что энтропия приспособлена для изучения текстов, не имеющих других закономерностей, кроме частотных. Следовательно, для случайных последовательностей по мере, соответствующей независимым испытаниям, между рассматриваемыми величинами можно установить полную связь; Аналогичный факт имеет место и для произвольного эргодического стационарного случайного процесса. Лит.:[1] Колмогоров А. Н., "Проблемы передачи информации", 1965, т. 1, вып. 1, с. 3-11; [2] его же, "Проблемы передачи информации", 1969, т. 5, вып. 3, с. 3-7; [3] Звонкий А. К., Левин Л. А., "Успехи матем. наук", 1970, т. 25, вып. 6, с. 85-127; [4] Барздинь Я. М., "Докл. АН СССР", 1968, т. 182, № 6, с. 1249-1252; [5] Канович М. И., "Докл. АН СССР", 1970, т. 194, № 3, с. 500-503. Я. М. Барздинь.
Теория — ж. греч. умозренье, умозаключенье; заключенье, вывод из чего-либо, не по явленью на деле, а по выводам своим; противоположное дело, на деле, опыт, практика. не всегда верна;........
Толковый словарь Даля
Теория — теории, ж. (греч. theoria - исследование). 1. учение, являющееся ражением действительности, обобщением практики, человеческого опыта. ..., если она является действительной теорией,........
Толковый словарь Ушакова
Теория Ж. — 1. Обобщение фактов, опыта, знаний, основывающееся на глубоком проникновении в сущность изучаемого явления, вскрывающее его закономерности. 2. Учение о какой-л. области........
Толковый словарь Ефремовой
Выпуск Средства Массовой Информации — – деятельность по организации поиска, получения и производства информации, предназначенной для массового распространения, а также по формированию содержания и оформлению........
Политический словарь
Государственная Поддержка Средств Массовой Информации — – совокупность организационных, организационно-технических, правовых, экономических и иных мер, устанавливаемых государством в целях обеспечения прав граждан на........
Политический словарь
Государственное Средство Массовой Информации — – средство массовой информации, учрежденное органом государственной власти и выпускаемое государственной некоммерческой организацией.
Политический словарь
Дисконтирование Информации Об Объекте Прогнозирования — Уменьшение информативности ретроспективных значений переменной объекта прогнозирования по мере удаления моментов их измерений в прошлое.
Политический словарь
Доступ К Информации — – ознакомление с информацией, ее обработка, в частности копирование, модификация или уничтожение информации; получение субъектом возможности ознакомления с информацией,........
Политический словарь
Злоупотребления Свободой Массовой Информации (при Проведении Агитации) — – злоупотребления свободой массовой информации: агитация, возбуждающая социальную, расовую, национальную ненависть и вражду, призывы к захвату власти, насильственному........
Политический словарь
Издатель Средства Массовой Информации — – юридическое лицо любой формы собственности или физическое лицо, зарегистрированное в качестве индивидуального предпринимателя, действующие на основании свидетельства........
Политический словарь
Исторического Пессимизма Теория — - направление в футурологии международных отношений, которое, в противовес теории технократического оптимизма, исходит из перспективы долгого существования классического........
Политический словарь
Источник Фактографической Информации Об Объекте Прогнозирования — Источник информации об объекте прогнозирования, имеющий своим содержанием фактические данные, необходимые для достижения цели прогноза.
Политический словарь
Источник Экспертной Информации Об Объекте Прогнозирования — Источник информации об объекте прогнозирования, содержащий экспертные оценки, необходимые для достижения цели прогноза.
Политический словарь
Конвергенции Теория — (от лат. convergere - сближаться, сходиться) основана на идее преобладания тенденций объединения элементов в систему над процессами дифференциации, различения и индивидуализации.........
Политический словарь
Мобильности Теория — (от фр. mobile, лат. mobilis - подвижный, способный к быстрому действию) - система идей в социологии и политологии, в которой осмысливаются процессы изменения положения людей........
Политический словарь
Муниципальное Средство Массовой Информации — – средство массовой информации, учрежденное органом (органами) местного самоуправления либо созданными ими организациями и выпускаемое муниципальной некоммерческой организацией.
Политический словарь
Носитель Информации — – физическое лицо, или материальный объект, в том числе физическое поле, в которых информация находит отображение в виде символов, образов, сигналов, технических решений и процессов.
Политический словарь
Общегражданское (общественно-политическое) Средство Массовой Информации — – средство массовой информации, которое ставит своими целями реализацию права граждан на самую разнообразную общественно-политическую информацию, без стремления........
Политический словарь
Олигархизации Политических Партий Теория — - (от греч. oliarchia - власть немногих) - обоснование характерной тенденции в развитии партии: переход от организации демократического типа к жесткому бюрократическому аппарату........
Политический словарь
Организация, Осуществляющая Выпуск Средства Массовой Информации — – коммерческая или некоммерческая организация, являющаяся собственником средства массовой информации или состоящая с ним в договорных отношениях по выпуску средства........
Политический словарь
Партийное Средство Массовой Информации — – средство массовой информации, которое ставит своей целью распространение информации, освещающей проблемы, подходы, идеологию, пропагандистский материал в интересах........
Политический словарь
Политическая Система Индустриально Развитых Стран (теория) — Политическая система представляет собой совокупность лиц, институтов, участвующих в политическом процессе, неформальных и неправительственных факторов, влияющих........
Политический словарь
Политическая Теория — (POLITICAL THEORY) - массив научной мысли, нацеленной на оценку, объяснение и прогнозирование политических феноменов. Одновременно политическая теория представляет собой раздел........
Политический словарь
Полнота Исходной Информации — Степень обеспеченности прогнозирования достоверной исходной информацией.
Политический словарь
Пользователь (потребитель) Информации — – субъект, обращающийся к информационной системе или посреднику за получением необходимой ему информации и пользующийся ею.
Политический словарь
Постиндустриального Общества Теория — - широко применяется в западной политологии и социологии для обозначения современного общества. Концепция индустриального общества разрабатывалась в трудах Р.Дарендорфа........
Политический словарь
Право На Доступ К Информации — – право каждого свободно искать информацию и получать ее от органов государственной власти, иных государственных органов и организаций, органов местного самоуправления,........
Политический словарь
Приведенный Источник Научно-технической Информации Об Объекте Прогнозирования — Источник научно-технической информации об объекте прогнозирования, оцененный по генеральной определительной таблице.
Политический словарь
Продукция Средства Массовой Информации — - тираж или часть тиража отдельного номера периодического печатного издания, отдельный выпуск теле-, радиопередачи или теле-, радиопрограммы, кинохроникальной программы,........
Политический словарь
Свобода Информации — – в конституционном праве понятие, охватывающее целую группу прав и свобод: свободу слова (свободу выражения мнений), свободу печати и иных средств массовой информации,........
Политический словарь
Slovariki 2.0. Знание - сила