2004-gre-cs-practice-book.pdf/Q38 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: « == Вопрос: Q38-4c9f66 == <i>Тут вставьте перевод вопроса. Используйте [https://wiki.4intra.net/Help:%D0%A4%D0%BE%D1%80…») |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: Q38-4c9f66 == | == Вопрос: Q38-4c9f66 == | ||
| + | {{38-39 вопрос из теста 2004}} | ||
| − | + | Если ''m'' является составным, какова вероятность того, что в каждом из ''k'' различных вариантов выполнения результат ''A'' будет ''YES''? | |
| − | + | ||
| − | + | ||
| − | + | ||
=== Ответы === | === Ответы === | ||
| − | < | + | * <m>1</m> |
| − | + | * <m>p^k</m> | |
| + | * Правильный ответ: <m>(1-p)^k</m> | ||
| + | * <m>1-p^k</m> | ||
| + | * <m>1-(1-p)^k</m> | ||
| − | + | === Объяснение === | |
| − | + | {{cstest-source|2004-gre-cs-practice-book.pdf|29|38}} | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | Алгоритм с односторонней ошибкой, вероятностная амплификация, <m>(1-p)^k</m>. | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | < | + | |
| − | + | ||
| − | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 07:35, 15 декабря 2024 (UTC)}} | |
| − | + | [[Категория:Вероятностные алгоритмы]] | |
Текущая версия на 07:35, 15 декабря 2024
Вопрос: Q38-4c9f66
Некоторый рандомизированный алгоритм 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-м выполнении , где являются взаимно независимыми
Если m является составным, какова вероятность того, что в каждом из k различных вариантов выполнения результат A будет YES?
Ответы
- Правильный ответ:
Объяснение
Исходники — вопрос 38 на 29 странице книги «2004-gre-cs-practice-book.pdf»
Алгоритм с односторонней ошибкой, вероятностная амплификация, .