С большой вероятностью - With high probability
В математика, событие, которое происходит с большой вероятностью (часто сокращается до w.h.p. или же WHP) - такое, вероятность которого зависит от некоторого числа п и переходит в 1 как п стремится к бесконечности, т.е. его можно сделать как можно ближе к 1, сделав п достаточно большой.
Приложения
Термин WHP особенно используется в Информатика, при анализе вероятностные алгоритмы. Например, рассмотрим некоторый вероятностный алгоритм на графе с п узлы. Если вероятность того, что алгоритм вернет правильный ответ, равна , тогда, когда количество узлов очень велико, алгоритм верен с вероятностью, очень близкой к 1. Этот факт кратко выражается в том, что алгоритм является правильным WHP.
Вот несколько примеров использования этого термина:
- Тест на простоту Миллера – Рабина: вероятностный алгоритм проверки того, является ли данное число п простое или составное. Если п составной, тест обнаружит п как составной WHP. Есть небольшая вероятность, что нам не повезло и тест подумает, что п простое. Но вероятность ошибки может быть уменьшена до бесконечности, если выполнить тест много раз с разными рандомизациями.
- Алгоритм Фрейвальдса: рандомизированный алгоритм проверки умножения матриц. Он работает быстрее, чем детерминированные алгоритмы WHP.
- Treap: рандомизированное двоичное дерево поиска. Его высота - логарифмическая WHP. Дерево слияния это связанная структура данных.
- Онлайн коды: рандомизированные коды, которые позволяют пользователю восстановить исходное сообщение WHP.
- BQP: сложный класс задач, для которых существуют квантовые алгоритмы с полиномиальным временем, которые являются правильными WHP.
- Наверное, примерно правильное обучение: Процесс машинного обучения, в котором изученная функция имеет низкий уровень ошибки обобщения WHP.
- Протоколы сплетен: а протокол связи используется в распределенные системы надежно доставлять сообщения во весь кластер, используя постоянный объем сетевых ресурсов на каждом узле и гарантируя отсутствие единой точки отказа.
Смотрите также
Рекомендации
- Métivier, Y .; Робсон, Дж. М .; Saheb-Djahromi, N .; Земмари, А. (2010). «Рандомизированный распределенный алгоритм MIS оптимальной битовой сложности». Распределенных вычислений. 23 (5–6): 331. Дои:10.1007 / s00446-010-0121-5.
- «Принципы распределенных вычислений (лекция 7)» (PDF). ETH Цюрих. Получено 21 февраля 2015.
Этот Информатика статья - это заглушка. Вы можете помочь Википедии расширяя это. |