Шаблон:38-39 вопрос из теста 2004
Материал из DISCOPAL
Определенный рандомизированный алгоритм 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-м выполнении , где являются взаимно независимыми
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.