Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- ПРЕДПОЛОЖЕНИЕ A.3
- ОПРЕДЕЛЕНИЕ A.5
- Основы теории вероятности
| ТЕОРЕМА A.1 (Теорема биномиального разложения) Пусть x, y – дей-
ствительные целые числа n – положительное целое. Тогда ПРЕДПОЛОЖЕНИЕ A.2 Для всех x ≥ 1 справедливо, что (1 − 1/x)x ≤ e−1. ПРЕДПОЛОЖЕНИЕ A.3 Для всех x справедливо, что 1 − x ≤ e−x. ПРЕДПОЛОЖЕНИЕ A.4 Для всех x при 0 ≤ x ≤ 1 справедливо, что Асимптотическая запись Мы используем стандартную запись для выражения асимптотического пове- дения функций. ОПРЕДЕЛЕНИЕ A.5 Пусть f (n), g(n) будут функциями из неотрицатель- ных целых чисел , для неотрицательных действительных чисел. Тогда: • f (n) = O(g(n)) означает, что существуют положительные целые числа c и nr, такие что для всех n > nr справедливо, что f (n) ≤ c • g(n). • f (n) = Ω(g(n)) означает, что существуют положительные целые числа c и nr, такие, что для всех n > nr справедливо, что f (n) ≥ c • g(n). • f (n) = Θ(g(n)) означает, что существуют положительные целые числа c1, c2 и nr такие, что для всех n > nr справедливо, что c1 • g(n) ≤ f (n) ≤ c2 • g(n). • f (n) = o(g(n)) означает, что limn→∞ g(n) = 0. • f (n) = ω(g(n)) означает, что limn→∞ g(n) = ∞. Пример A.6 Пусть f (n) = n4 + 3n + 500. Тогда: • f (n) = O(n4). 311 • f (n) = O(n5). На самом деле, f (n) = o(n5). • f (n) = Ω(n3 log n). Фактически, f (n) = ω(n3 log n). • f (n) = Θ(n4). ♦ Основы теории вероятности Мы предполагаем, что читатель знаком с основами теории вероятности на уровне, который рассматривается в типичном университетском курсе по дис- кретной математике. Здесь мы просто напомним читателю о некоторых обозна- чениях и основных фактах. If E – это событие, то E¯ обозначает дополнение этого события; т.е., E¯ – это событие, которое E не происходит. По определению, Pr[E] = 1 − Pr[E¯]. Если E1 и E2 являются событиями, то E1 ^ E2 обозначает их конъюнкцию; т.е., E1 ^ E2 является таким событием, что происходит как E1, так и E2 . По определе- нию, Pr[E1 v E2] ≤ Pr[E1]. События E1 и E2 называются независимыми, если Pr[E1v E2] = Pr[E1] • Pr[E2]. Если E1 и E2 – события, то E1 v E2 обозначает логическое сложение (дизъ- юнкцию) E1 и E2; то есть, E1 v E2 – такое событие, при котором происходит или E1 или E2. Из определения следует, что Pr[E1 v E2] ≥ Pr[E1]. Граница объедине- ния часто является очень полезной верхней границей этой величины. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|