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

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






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


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

Ю. И. Манинab

a Northwestern University, Evanston
b Max Planck Institute for Mathematics

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

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

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