Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Алгоритмічна теорія інформації



Алгоритмічна теорія інформації - це область інформатики, яка намагається вловити суть складності, використовуючи інструменти з теоретичної інформатики. Головна ідея - це визначити складність (або описову складність, колмогоровскую складність, складність Колмогорова-Хайтіна) рядки як довжину найкоротшої програми, яка виводить задану рядок. Рядки, які можуть виводитися короткими програмами, розглядаються як не дуже складні. Ця нотація дивно глибока і може бути використана для постановки і докази неможливості деяких результатів таким же чином, як це робить теорема Геделя про неповноту і проблема зависання Тьюринга.

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

Для формалізації даного вище визначення складності визначимо, які типи програм є допустимими. Це не має особливого значення: як ми побачимо пізніше, будь-хто може вибрати особливу нотацію для машини Тьюринга, або програми на мові LISP, або програми на мові Pascal, або в байткод віртуальної машини Java.

Принцип мінімальної довжини повідомлення (МДС) статистичного та індуктивного виводу і машинного навчання був розроблений Крістофером Уоллесом (англ.) і DM Boulton в 1968. МДС - Байєсова ймовірність (вона включає попередні думки) та інформаційно-теоретична. Вона має бажані властивості статистичної інваріантності (висновок трансформується з репараметрізаціей, наприклад, таким-же чином як здійснюється переклад з полярних координат в Декартові), статистичну узгодженість (навіть для дуже складних проблем МДС буде сходитися до будь низлежащего моделі) і ефективність (модель МДС буде сходитися до кожної справжньої низлежащего моделі так швидко, як можливо). Крістофер Уоллес і DL Dowe показали формальний зв'язок між МДС та алгоритмічної теорією інформації (або колмогоровской складністю) в 1999.


Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Теорія інформації
Нат (теорія інформації)
Алгоритмічна розв'язність
Цілісність інформації
Розкриття інформації
Надмірність інформації
Кодування інформації
Асиметричність інформації
Свобода інформації
© Усі права захищені
написати до нас