свойство/упорядоченности, 247

связанный список, 205

связная компонента, 88

связный граф, 88

семейство/универсальное, 232

сильно связный граф, 88

симметричная монета, 108

симметричное отношение, 80

симметричность, 33

синглетон, 78

следующий, 198

следующий элемент, 246

сливаемые кучи, 218

слияние упорядоченных массивов, 20

словарь, 197, 246

слово, 101

слово/кодовое, 338

случайная величина, математическое ожидание, 113

случайная величина/дискретная, 112

случайное двоичное дерево

поиска, 256 случайные величины/независимые,

113

случайных чисел генератор, 159

смежная вершина, 87 собственное подмножество, 76

собственный предок, 93 событие, 106

событие/вероятность, 107 событие/достоверное, 106 событие/невозможное, 106 событие/элементарное, 106 события/независимые, 109 события/независимые в совокупности, 109 события/несовместные, 106 события/попарно независимые, 109

события/условно независимые, 111

совместного распределения вероятностей функция, 113

совместные заявки, 331

соотношение рекуррентное, 53

сортировка, 11, 137 сравнением, 170 сортировка/без дополнительной памяти, 12, 138 сортировка/быстрая, 138, 152 сортировка/вставками, 12 сортировка/выбором,19 сортировка/вычерпыванием,

138, 178 сортировка/подсчётом, 138, 173

сортировка/с помощью кучи,

138, 140, 147 сортировка/слиянием, 20, 138 сортировка/устойчивая, 174 сортировка/цифровая, 138,

175

соседняя вершина, 89 сочетания,102

список/двусторонне связанный, 205

список/кольцевой, 205

список/односторонне связанный, 205

список/свободных позиций, 212

список/связанный, 205 список/упорядоченный, 205 среднее время работы, 18 среднее случайное величины,

113 срок, 351

стандартное отклонение, 116 старший коэффициент многочлена, 35 статистика/порядковая, 184 статистики/порядковые,139 стек, 201

стек/пустой, 202 стек/размер, 168 степень вершины, 87, 94 степень вершины/входящая, 87

степень вершины/исходящая, 87

степень многочлена, 35 Стирлинга формула, 38 стоимость, 340 стоимость редактирования, 328

столкновение, 224 сторона многоугольника,321 строго возрастающая (убывающая) функция, 34 строка,101 стягивание, 349 суммирование, 43 суммы правило, 100 сходящийся ряд, 44 сцепление элементов, 225 счётное множество, 78 счётчик/вероятностный, 133 сын, 94 сюръекция, 84

таблица расстановки, 221

Тейлора ряд, 263

теорема/основная о рекуррентных соотношениях, 53, 61

теоретико-множественные операции, 76

точка/максимальной кратности, 297

транзитивное отношение, 80

транзитивность, 33

треугольник Паскаля, 105

триангуляция многоугольника, 322

удаление, 198 удаление элемента, 246 умножение, 231 умножение последовательности матриц, 305

универсальное семейство, 232 универсальное хеширование, 232

универсум, 77 упорядоченная пара, 78 упорядоченности свойство, 247

упорядоченный список, 205 управляемое событиями моделирование, 149 урны, 129

условная вероятность, 109 условно независимые события, 111 успех, 117

устойчивый алгоритм сортировки, 174

факториал, 38

Фибоначчи последовательность, 71

Фибоначчи числа, 39

фиктивный элемент, 207, 275

формальный степенной ряд, 71

формула включений и исключений, 80 формула/Байеса, 110 формула/Стирлинга, 38 функция, 83

функция/асимптотически положительная, 36

функция/булева, 104

функция/квадратичная, 17

функция/линейная, 17

функция/монотонно возрастающая (убывающая), 34

функция/область определения, 83

функция/обратная, 85

функция/ограниченная полилогарифмом, 37

функция/показательная, 36

функция/полиномиально ограниченная, 36

функция/производящая, 71 функция/распределения, 180 функция/распределения вероятностей, 112 функция/расстановки, 221 функция/совместного распределения вероятностей, 113 функция/строго возрастающая (убывающая), 34

Хаффмена код, 341

хвост списка, 205

хвосты биномиального распределения, 123

хеш-значение, 224

хеш-таблица, 224

хеш-функция, 221, 224

хеширование, 221

хеширование-равномерное, 236

хеширование г-универсальное, 244

хеширование/двойное, 238 хеширование/равномерное, 226

хеширование/с открытой адресацией, 235

хеширование/универсальное, 232

целая часть, 35

целое приближение сверху

(снизу), 35 целых чисел множество, 75 цепочки, 224 цикл, 87

цикл/в неориентированном

графе, 88 цикл/простой, 88 цифровая сортировка, 138,

175

цифровые деревья, 261

частично упорядоченное множество, 81

частичный порядок, 81 Чебышёва неравенство, 116 черпак, 178 чёрная высота, 267 числа Фибоначчи, 39, 71 числа/Каталана, 306 число Каталана, 263

шары, 129

шенноновская энтропия, 104 штраф, 351

эквивалентности/класс, 81 эквивалентности/отношение, 81

экспонента, 36 элемент, 75

элемент/максимальный, 82 элементарное событие, 106 энтропия/шенноновская двоичная, 104

ячейка, 221