Семинар 20 октября 2006 года

Пятница, 20 октября, комната 106. Начало в 16:00.

Докладчик: Ю. Лифшиц.

Тема: Утечка информации: марковская модель и алгоритм обнаружения.

Abstract

Рассматривается следующая модель утечки информации (предложена А.О.Слисенко). Дано распределение вероятностей на бесконечных строчках (процессах) в алфавите

. Дано также свойство процессов. Утечкой информации называется случай, когда по проекции процесса на алфавит

апостериорная вероятность выполнения свойства отличается от априорной (ничего не знаем о процессе). В докладе мы считаем, что распределение на бесконечных строчках задано марковским процессом, а свойство распознается автоматом Buchi. Основной результат --- алгоритм, определяющий наличие утечки информации.

Несмотря на такое сложное введение, модель очень понятная и интересная, а основным инструментом алгоритма становятся элементы линейной алгебры (!). Работа выполнена в сотрудничестве с научной группой Daniele Beauquier.