Шаблон:38-39 вопрос из теста 2004

Ссылки сюда (2) →

Некоторый рандомизированный алгоритм A предназначен для определения, является ли данное положительное целое число n простым, путем генерации случайной битовой строки r и, основываясь на значениях n и r, путем вывода либо Yes (n является простым), либо No (n является составным)

Выполнение алгоритма А гарантирует следующее

• Если n — простое число, то результатом A всегда будет Yes
• Если n является составным, то существует вероятность p > 0, такое что результатом A будет No с вероятностью p и Yes с вероятностью 1 — p

На входе m алгоритм A выполняется k раз (k > 0) и генерирует случайную строку при i-м выполнении , где являются взаимно независимыми

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.