Мы используем файлы cookies для улучшения работы сайта НИУ ВШЭ и большего удобства его использования. Более подробную информацию об использовании файлов cookies можно найти здесь, наши правила обработки персональных данных – здесь. Продолжая пользоваться сайтом, вы подтверждаете, что были проинформированы об использовании файлов cookies сайтом НИУ ВШЭ и согласны с нашими правилами обработки персональных данных. Вы можете отключить файлы cookies в настройках Вашего браузера.

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

Александр Шень. Сложность определений и сложность вычислений

В докладе предполагается некоторый обзор (в зависимости от интересов аудитории) и более подробный рассказ о колмогоровской сложности

Александр Шень

Институт проблем передачи информации РАН, Москва;
Лаборатория информатики Национального центра научных исследований Франции, Марсель 

30.11.11 в 14-00, аудитория 125, Б. Печерская 25

Доклад на семинаре лаборатории ЛАТАС НИУ ВШЭ

Приглашаются все желающие

 

Сложность определений и сложность вычислений

Термин "сложность" в информатике используется в разных смыслах (не считая бытового - "сложная конструкция"). Можно оценивать время работы алгоритма или используемую им память; комбинацией этих двух мер является схемная сложность (число элементов, необходимых для построения булевой функции). Можно говорить о сложностных классах (полиномиальная иерархия, вероятностные алгоритмы и многое другое). Наконец, можно говорить о сложности определения (задания объектов) - колмогоровской сложности. В докладе предполагается некоторый обзор (в зависимости от интересов аудитории) и более подробный рассказ о колмогоровской сложности (в соответствии со специальностью докладчика)