|
|
Семинар «Глобус» (записи с 2011 года)
13 сентября 2012 г. 15:40, г. Москва, конференц-зал НМУ (Москва, Большой Власьевский пер., 11)
|
 |
|
 |
|
|
|
Колмогоровская сложность и асимптотическая граница для кодов, исправляющих ошибки
Ю. И. Манинab
a Northwestern University, Evanston
b Max Planck Institute for Mathematics
|
| Количество просмотров: |
| Эта страница: | 656 |
|
Аннотация:
По множеству всех корректирующих кодов над фиксированным алфавитом из $q$ символов можно построить рекурсивно перечислимое множество рациональных точек в единичном квадрате, координаты на котором суть скорость передачи и относительное минимальное расстояние. Предельные точки этого множества суть все точки под графиком некоторой непрерывной невозрастающей функции, называемой асимптотической границей.
Существование асимптотической границы было доказано докладчиком в 1981 г., однако никаких подходов к её вычислению не существовало, и даже имеется предположение о её невычислимости в смысле конструктивного анализа.
В докладе будет показано, что асимптотическая граница становится вычислимой при наличии оракула, выдающего коды в порядке возрастания их колмогоровской сложности. Более того, естестественная разделяющая функция, использующая сложность, позволяет проинтерпретировать асимптотическую границу как кривую, разделяющую две различные термодинамические фазы кодов.
Доклад основан на совместной работе с М. Марколли (arXiv: 1203.0653).
|
|
Обратная связь: