307
Индекс общего обозначения
Общие обозначения:
• := называется детерминированным присвоением
• Если S – множество, то x ← S
обозначает, что x выбирается равномерно из S
• Если A – случайный алгоритм, то y ← A(x) обозначает действующий A на
входе x, с равномерной случайной лентой , и назначающий выход для y. Мы
пишем y := A(x; r), чтобы обозначить действующий A на входе x , использую-
щий случайную ленту r , и
назначающий выход для y
• ٨ обозначает логическое умножение (оператор И (AND))
• V обозначает логическое отрицание (оператор ИЛИ (OR))
• ⊕ обозначает исключающее ИЛИ (оператор XOR); этот оператор может
быть применен к отдельным битам или целым строкам (в последнем случае
оператор XOR действует поразрядно)
• {0, 1}n это множество всех битовых строк длиной n
• {0, 1}≤n то множество всех битовых строк длиной не более n
• {0, 1}* множество
конечных битовых строк
• 0n (соотв., 1n) обозначает строку, составленную из n нулей (соотв., n единиц)
• ||x|| обозначает длину двоичного представления (положительного) целого числа x,
записанного вместе с ведущим битом 1. Обратите внимание, что log x < ||x|| ≤ log x + 1
• |x| обозначает длину двоичной строки x (у которой могут быть ведущие
нули), или абсолютное значение действительного числа x
• O(•), Θ(•), Ω(•), ω(•) см. приложение A.2
• 0x обозначает, что эти числа представлены в шестнадцатеричном коде
• x||y однозначную конкатенацию строк x и y («однозначная» означает, что x
and y могут быть восстановлены из x||y)
• Pr[X] обозначает
вероятность события X
• log x обозначает логарифм x по основанию 2
Достарыңызбен бөлісу: