RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Ближайшие семинары
Календарь семинаров
Список семинаров
Архив по годам
Регистрация семинара

Поиск
RSS
Ближайшие семинары





Для просмотра файлов Вам могут потребоваться








Семинар «Глобус» (записи с 2011 года)
13 сентября 2012 г. 15:40, г. Москва, конференц-зал НМУ (Москва, Большой Власьевский пер., 11)
 


Колмогоровская сложность и асимптотическая граница для кодов, исправляющих ошибки

Ю. И. Манинab

a Northwestern University, Evanston
b Max Planck Institute for Mathematics

Количество просмотров:
Эта страница:355

Аннотация: По множеству всех корректирующих кодов над фиксированным алфавитом из $q$ символов можно построить рекурсивно перечислимое множество рациональных точек в единичном квадрате, координаты на котором суть скорость передачи и относительное минимальное расстояние. Предельные точки этого множества суть все точки под графиком некоторой непрерывной невозрастающей функции, называемой асимптотической границей.
Существование асимптотической границы было доказано докладчиком в 1981 г., однако никаких подходов к её вычислению не существовало, и даже имеется предположение о её невычислимости в смысле конструктивного анализа.
В докладе будет показано, что асимптотическая граница становится вычислимой при наличии оракула, выдающего коды в порядке возрастания их колмогоровской сложности. Более того, естестественная разделяющая функция, использующая сложность, позволяет проинтерпретировать асимптотическую границу как кривую, разделяющую две различные термодинамические фазы кодов.
Доклад основан на совместной работе с М. Марколли (arXiv: 1203.0653).

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2017