Четверг, 13 сентября 2012 г.
15:40, НМУ, конференц-зал
КОЛМОГОРОВСКАЯ СЛОЖНОСТЬ И АСИМПТОТИЧЕСКАЯ ГРАНИЦА ДЛЯ КОДОВ, ИСПРАВЛЯЮЩИХ ОШИБКИ
Лектор - Юрий Иванович Манин (Max-Planck-Institut für Mathematik, Northwestern University)
По множеству всех корректирующих кодов над фиксированным алфавитом из q символов можно построить рекурсивно перечислимое множество рациональных точек в единичном квадрате, координаты на котором суть скорость передачи и относительное минимальное расстояние. Предельные точки этого множества суть все точки под графиком некоторой непрерывной невозрастающей функции, называемой асимптотической границей.
Существование асимптотической границы было доказано докладчиком в 1981 г., однако никаких подходов к её вычислению не существовало, и даже имеется предположение о её невычислимости в смысле конструктивного анализа.
В докладе будет показано, что асимптотическая граница становится вычислимой при наличии оракула, выдающего коды в порядке возрастания их колмогоровской сложности. Более того, естестественная разделяющая функция, использующая сложность, позволяет проинтерпретировать асимптотическую границу как кривую, разделяющую две различные термодинамические фазы кодов.
Доклад основан на совместной работе с М. Марколли (arXiv:1203.0653)
| 06.09.2012 | Петров Леонид Александрович |