Аннотация:
Как защитить авторские права на информацию, передаваемую (или продаваемую) «широковещательно», т.е. сразу многим пользователям одновременно, так, чтобы если какая-то коалиция из недобросовестных пользователей (называемых «пиратами») решила перепродать эту информацию (например,
фильм), то автор смог бы однозначно определить хотя бы одного «пирата»? Эта задача, которая может быть
сформулирована математически (что мы и сделаем), оказывается близкой к разным комбинаторным задачам, возникавшим в прошлом веке. Наиболее известная из этих задач – это задача Эрдеша о максимальном числе подмножеств конечного множества таких, что никакое подмножество не покрывается t другими подмножествами. Или вот такая задача – чему равно максимальное число строк в троичной матрице из n столбцов такой, что для любых трех строк найдется столбец, в котором эти строки различны. Я расскажу про известные результаты и открытые вопросы.
|
