Адрес e-mail:

Колмогоровская сложность (А.С. Милованов, осень 2021)

Лектор - А.С. Милованов

Время и место: понедельник, 17:05-18:30, первое занятие - 13 сентября, http://meet.google.com/fpv-khtf-ofk


Описание
Понятие колмогоровской сложности появилось в 1960-е годы на стыке теории алгоритмов, теории информации и теории вероятностей. Идея А.Н. Колмогорова состояла в том, чтобы измерять количество информации, заключенной в индивидуальных конечных объектах.  Оказалось, что это возможно (хотя лишь с точностью до аддитивной
константы).  Неформальное определение колмогоровской сложности слова x  такое: это минимальная длина программы, которая на пустом входе выдаёт x. (Такое определение зависит от выбора языка программирования, но на самом деле эта зависимость небольшая.) В курсе будут рассказаны основные понятия этой теории (случайность по Мартин-Лёфу, априорная вероятность, и т.д.), а также будут рассказаны некоторые приложения (например, в комбинаторике и теории автоматов). Хотя колмогоровская сложность невычислима, и поэтому не может использоваться на практике непосредственно, она являлась родительницей многих идей теории обучения.

Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

© 2001-2021 Московский физико-технический институт (национальный исследовательский университет)

Противодействие коррупции | Сведения о доходах

Политика обработки персональных данных МФТИ

Техподдержка сайта | API

Использование новостных материалов сайта возможно только при наличии активной ссылки на https://mipt.ru

МФТИ в социальных сетях