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

Материал из DISCOPAL
Версия от 15:25, 13 ноября 2024; Akazikov (обсуждение | вклад) (Новая страница: «Определенный рандомизированный алгоритм ''A'' предназначен для определения того, являетс…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Определенный рандомизированный алгоритм 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-м выполнении , где являются взаимно независимыми

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

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

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