|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Сложность конечных объектов и обоснование понятий информации и случайности с помощью теории алгоритмовстатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК- Авторы: Звонкин Александр Калманович, Левин Леонид Анатольевич
- Журнал: Успехи математических наук
- Том: 25
- Номер: 6
- Год издания: 1970
- Издательство: ФГБУ "Издательство "Наука"
- Местоположение издательства: Москва
- Первая страница: 85
- Последняя страница: 127
- Аннотация: В 1964 г. А. Н. Колмогоров ввел понятие сложности конечного объекта (например, слова в некотором алфавите). Сложность он определял как минимальное число двоичных знаков, содержащих всю информацию о задаваемом объекте, достаточную для его восстановления (декодирования). Это определение существенно зависит от метода декодирования, однако с помощью общей теории алгоритмов А. Н. Колмогорову удалось дать инвариантное (универсальное) определение сложности. Близкие понятия рассматривались Р. Дж. Соломоновым (США) и А. А. Марковым. На базе понятия сложности А. Н. Колмогоров дал определение количества информации в конечных объектах и понятия случайной последовательности (уточненное потом в работах П. Мартин-Лёфа). Впоследствии этот круг вопросов быстро развивался. В частности, интересное развитие получили идеи А. А. Маркова о применении понятия сложности для изучения количественных вопросов теории алгоритмов. Настоящая статья представляет собой обзор основных результатов, связанных со всем изложенным.
- Добавил в систему: Золин Евгений Евгеньевич