Шаблон:38-39 вопрос из теста 2004 — различия между версиями
Материал из DISCOPAL
Akazikov (обсуждение | вклад) (Новая страница: «Определенный рандомизированный алгоритм ''A'' предназначен для определения того, являетс…») |
Akazikov (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | + | Некоторый рандомизированный алгоритм ''A'' предназначен для определения, является ли данное положительное целое число ''n'' простым, путем генерации случайной битовой строки ''r'' и, основываясь на значениях ''n'' и ''r'', путем вывода либо ''Yes'' (''n'' является простым), либо ''No'' (''n'' является составным) | |
Выполнение алгоритма ''А'' гарантирует следующее | Выполнение алгоритма ''А'' гарантирует следующее | ||
* Если ''n'' — простое число, то результатом ''A'' всегда будет ''Yes'' | * Если ''n'' — простое число, то результатом ''A'' всегда будет ''Yes'' | ||
| − | * Если ''n'' является составным, то существует вероятность ''p > 0'', | + | * Если ''n'' является составным, то существует вероятность ''p > 0'', такое что результатом ''A'' будет ''No'' с вероятностью ''p'' и ''Yes'' с вероятностью ''1 — p'' |
На входе ''m'' алгоритм ''A'' выполняется ''k'' раз (''k > 0'') и генерирует случайную строку <m>r_i</m> при ''i''-м выполнении <m>i \le i \le k</m>, где <m>r_1, r_2, ..., r_k</m> являются взаимно независимыми | На входе ''m'' алгоритм ''A'' выполняется ''k'' раз (''k > 0'') и генерирует случайную строку <m>r_i</m> при ''i''-м выполнении <m>i \le i \le k</m>, где <m>r_1, r_2, ..., r_k</m> являются взаимно независимыми | ||
Текущая версия на 12:44, 16 ноября 2024
Некоторый рандомизированный алгоритм 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-м выполнении , где являются взаимно независимыми