Викия

Наука

Алгоритмическая теория информации

22 032статьи на
этой вики
Добавить новую страницу
Обсуждение0 Поделиться

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

В информатике, алгоритмическая теория информации — это область знаний, которая пытается уловить суть сложности используя инструменты из теоретической информатики. Главная идея — это определить сложность (или описательная сложность, Колмогоровская сложность или также сложность Колмогорова-Чейтина) строки как длину кратчайшей программы, которая выводит заданную строку. Строки, которые могут выводиться короткими программами рассматриваются, как не очень сложные. Эта нотация удивительно глубока и может быть использована для постановки и доказательства невозможности некоторых результатов, таким-же образом как это делает теорема Гёделя о неполноте и проблема зависания Тьюринга.

Эта область была разработана Андреем Колмогоровым, Рэем Соломоновым и Грегори Чейтиным в конце 1960-х годов. Существуют несколько вариантов Колмогоровской сложности или алгоритмической информации. Наиболее широко используемая базируется на саморазграничивающих программах и в в основном следует Леониду Левину (1974).

Для формализации данного выше определения сложности определим какие типы программ являются допустимыми. К счастью это не имеет особого значения: как мы увидим позже, любой может выбрать особую нотацию для машины Тьюринга, или программы на языке LISP, или программы на языке Pascal, или в байткоде виртуальной машины Java.

Принцип минимальной длины сообщения (МДС) статистического и индуктивного вывода и машинного обучения был разработан Кристофером Уоллесом и D.M. Boulton в 1968 году. МДС — байесовская вероятность (она включает предыдущие мнения) и информационно-теоретическая. Она имеет желаемые свойства статистической инвариантности (вывод трансформируется с репараметризацией, например, таким-же образом как осуществляется перевод из полярных координат в декартовы), статистическую согласованность (даже для очень сложных проблем, МДС будет сходиться к любой низлежащей модели) и эффективность (модель МДС будет сходиться к любой истинной низлежащей модели так быстро как возможно). Кристофер Уоллес и D.L. Dowe показали формальную связь между МДС и алгоритмической теорией информации (или Колмогоровской сложностью) в 1999 году.

См. также Править

Внешние ссылки Править


  1. Википедия Алгоритмическая теория информации адрес
  2. Викисловарьадрес
  3. Викицитатникадрес
  4. Викиучебникадрес
  5. Викитекаадрес
  6. Викиновостиадрес
  7. Викиверситетадрес
  8. Викигидадрес

Выделить Алгоритмическая теория информации и найти в:

  1. Вокруг света теория информации адрес
  2. Академик теория информации/ru/ru/ адрес
  3. Астронет адрес
  4. Элементы теория информации+&search адрес
  5. Научная Россия теория информации&mode=2&sort=2 адрес
  6. Кругосвет теория информации&results_per_page=10 адрес
  7. Научная Сеть
  8. Традицияадрес
  9. Циклопедияадрес
  10. Викизнаниетеория информации адрес
  1. Google
  2. Bing
  3. Yahoo
  4. Яндекс
  5. Mail.ru
  6. Рамблер
  7. Нигма.РФ
  8. Спутник
  9. Google Scholar
  10. Апорт
  11. Онлайн-переводчик
  12. Архив Интернета
  13. Научно-популярные фильмы на Яндексе
  14. Документальные фильмы
  1. Список ru-вики
  2. Вики-сайты на русском языке
  3. Список крупных русскоязычных википроектов
  4. Каталог wiki-сайтов
  5. Русскоязычные wiki-проекты
  6. Викизнание:Каталог wiki-сайтов
  7. Научно-популярные сайты в Интернете
  8. Лучшие научные сайты на нашем портале
  9. Лучшие научно-популярные сайты
  10. Каталог научно-познавательных сайтов
  11. НАУКА В РУНЕТЕ: каталог научных и научно-популярных сайтов

Комментарии читателей:Править

Викия-сеть

Случайная вики