• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Колмогоровская сложность задачи преобразования слова в два других

ФИО студента: Архипова Александра Рэмовна

Руководитель: Верещагин Николай Константинович

Кампус/факультет: Факультет математики

Программа: Математика (Бакалавриат)

Год защиты: 2016

В этой работе я буду пытаться получить ответ на вопрос, верно ли, что для любых бинарных слов x,y,z существуют слова p и q, такие что $K(pq)-K(pq|x)\approx 0, K(y|x,p)\approx 0, K(z|x,q) \approx 0 $ и при этом длины p и q не сильно превосходят длины описаний y и z соответственно, при известном х. Требование "не сильно превосходят" является существенным - без этого ограничения такие слова очевидно найдутся, например сами слова y и z подойдут под все условия в качестве собственных описаний. По этой причине имеет смысл параметризовать отличие длин p и q от длин описаний y и z, также как и отличие длины pq от длины описания pq. Условия $K(y|x,p)\approx 0, K(z|x,q) \approx 0 $ будут рассматриваться в этой работе как утверждения о существовании функции, по x и p строящей y. При рассмотрении задачи в такой форме, удалось получить некоторые оценки на величины введенных параметров для случаев существования и несуществования слов p и q. Однако для некоторых комбинаций параметров ответ получить не удалось. Для доказательства нижних оценок на параметры будет использоваться игровой метод Мучника. Этот метод позволяет доказывать истинность или ложность достаточно широкого класса утверждений, при помощи построения игры, такой, что существование выигрышной стратегии для одного из игроков эквивалентно истинности доказываемого утверждение, в то время как существование выигрышной стратегии для второго игрока эквивалентно ложности этого утверждения.

Выпускные квалификационные работы (ВКР) в НИУ ВШЭ выполняют все студенты в соответствии с университетским Положением и Правилами, определенными каждой образовательной программой.

Аннотации всех ВКР в обязательном порядке публикуются в свободном доступе на корпоративном портале НИУ ВШЭ.

Полный текст ВКР размещается в свободном доступе на портале НИУ ВШЭ только при наличии согласия студента – автора (правообладателя) работы либо, в случае выполнения работы коллективом студентов, при наличии согласия всех соавторов (правообладателей) работы. ВКР после размещения на портале НИУ ВШЭ приобретает статус электронной публикации.

ВКР являются объектами авторских прав, на их использование распространяются ограничения, предусмотренные законодательством Российской Федерации об интеллектуальной собственности.

В случае использования ВКР, в том числе путем цитирования, указание имени автора и источника заимствования обязательно.

Реестр дипломов НИУ ВШЭ