Слабое определение обнаружения

Можно в некотором роде ослабить определение обнаружения, сохранив полученный выше результат в силе. В частности можно допустить, чтобы алгоритм, претендующий на обнаружение вируса V, возвращал 1 не только на экземплярах этого вируса, но и на некоторых других программах, при условии, что они тоже являются экземплярами (других) вирусов.

Определение 2.4. Будем говорить, что алгоритм A слабо обнаруживает вирус V для любой программы p, A(p) завершает работу и возвращает 1, если p V, и возвращает отличный от 1 результат, если p не является экземпляром никакого вируса. При этом на экземплярах других вирусов алгоритм может возвращать любой результат

Вполне очевидно, что для сконструированного вируса W не существует алгоритма, который мог бы слабо обнаруживать этот вирус, поскольку такой алгоритм будет либо возвращать 1 на программе, которая просто завершает свою работу, либо будет возвращать не 1 для программы, являющейся экземпляром W.


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



double arrow
Сейчас читают про: