Центральный Дом Знаний - Алгоритмическая теория информации

Информационный центр "Центральный Дом Знаний"

Заказать учебную работу! Жми!



ЖМИ: ТУТ ТЫСЯЧИ КУРСОВЫХ РАБОТ ДЛЯ ТЕБЯ

      cendomzn@yandex.ru  

Наш опрос

Как Вы планируете отдохнуть летом?
Всего ответов: 922

Онлайн всего: 1
Гостей: 1
Пользователей: 0


Форма входа

Логин:
Пароль:

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

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

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

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

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

Loading

Календарь

«  Март 2024  »
ПнВтСрЧтПтСбВс
    123
45678910
11121314151617
18192021222324
25262728293031

Архив записей

Друзья сайта

  • Заказать курсовую работу!
  • Выполнение любых чертежей
  • Новый фриланс 24