Войти
Логин:
Пароль:
Забыли пароль?
научная деятельность
структура институтаобразовательные проектыпериодические изданиясотрудники институтапресс-центрконтакты
русский | english

Семинар Добрушинской математической лаборатории. 28 ноября, вторник, 16:00, ауд. 307.

 

Семинар Добрушинской математической лаборатории. 28 ноября, вторник, 16:00, ауд. 307. 

Александр Шень (ИППИ): Нормальные последовательности и автоматная сложность. 

Аннотация: Хорошо известно, что нормальные последовательности (те, где любая группа цифр встречается с одинаковой предельной частотой) можно описать как несжимаемые с помощью конечных автоматов. Однако стандартная формулировка критерия такого рода (Becher, Heiber, 2014) не соответствует общей схеме определения несжимаемости в терминах колмогоровской сложности. Этот критерий можно переформулировать, введя понятие автоматной сложности, и тогда классические результаты о нормальных последовательности (сохранение нормальности двоичного числа при умножении на рациональное, эквивалентность разных определений, а также теорема Пятецкого-Шапиро о нормальности последовательности, в которой частоты появления всех блоков не более чем в константу раз превосходят ожидаемые) получают простые и естественные доказательства в терминах конечных автоматов.

Архив прошедших семинаров Добрушинской лаборатории

25.11.2017 | Бланк Михаил Львович
 

 

  © Федеральное государственное бюджетное учреждение науки
Институт проблем передачи информации им. А.А. Харкевича Российской академии наук, 2017
Об институте  |  Контакты  |  Старая версия сайта