ОГЛАВЛЕНИЕ ГЛАВА 1. ОСНОВНЫЕ ПОНЯТИЯ 27 1.1. АЛГОРИТМЫ 27 1.2. МАТЕМАТИЧЕСКОЕ ВВЕДЕНИЕ 37 1.2.1. Математическая индукция 38 1.2.2. Числа, степени и логарифмы 49 1.2.3. Суммы и произведения 56 1.2.4. Целочисленные функции и элементарная теория чисел 68 1.2.5. Перестановки и факториалы 75 1.2.6. Биномиальные коэффициенты 82 1.2.7. Гармонические числа 105 1.2.8. Числа Фибоначчи 109 1.2.9. Производящие функции 118 1.2.10.Анализ алгоритма 127 *1.2.11.Асимптотические представления 138 *1.2.11.1. Символ O 138 *1.2.11.2. Формула суммирования Эйлера 143 *1.2.11.3. Применение асимптотических формул 148 1.3. MIX 156 1.3.1. Описание MIX 156 1.3.2. Язык ассемблера компьютера MIX 178 1.3.3. Применение к перестановкам 198 1.4. НЕКОТОРЫЕ ФУНДАМЕНТАЛЬНЫЕ МЕТОДЫ ПРОГРАММИРОВАНИЯ 221 1.4.1. Подпрограммы 221 1.4.2. Сопрограммы 229 1.4.3. Программы-интерпретаторы 237 1.4.3.1. Имитатор MIX 239 *1.4.3.2. Программы трассировки 248 1.4.4. Ввод и вывод 251 1.4.5. История и библиография 266 ГЛАВА 2. ИНФОРМАЦИОННЫЕ СТРУКТУРЫ 271 2.1. ВВЕДЕНИЕ 271 2.2. ЛИНЕЙНЫЕ СПИСКИ 277 2.2.1. Стеки, очереди и деки 277 2.2.2. Последовательное распределение 283 2.2.3. Связанное распределение 295 2.2.4. Циклические списки 315 2.2.5. Дважды связанные списки 322 2.2.6. Массивы и ортогональные списки 341 2.3. ДЕРЕВЬЯ 352 2.3.1. Обход бинарных деревьев 362 2.3.2. Представление деревьев в виде бинарных деревьев 380 2.3.3. Другие представления деревьев 395 2.3.4. Основные математические свойства деревьев 410 2.3.4.1. Свободные деревья 410 2.3.4.2. Ориентированные деревья 420 *2.3.4.3. Лемма о бесконечном дереве 431 *2.3.4.4. Перечисление деревьев 435 2.3.4.5. Длина пути 449 *2.3.4.6. История и библиография 456 2.3.5. Списки и “сборка мусора” 459 2.4. МНОГОСВЯЗНЫЕ СТРУКТУРЫ 476 2.5. ДИНАМИЧЕСКОЕ ВЫДЕЛЕНИЕ ПАМЯТИ 488 2.6. ИСТОРИЯ И БИБЛИОГРАФИЯ 512 ОТВЕТЫ К УПРАЖНЕНИЯМ 521 ПРИЛОЖЕНИЕ A. ТАБЛИЦЫ ЗНАЧЕНИЙ НЕКОТОРЫХ КОНСТАНТ 683 A.1. Основные константы (десятичные) 683 A.2. Основные константы (восьмеричные) 684 A.3. Значения гармонических чисел, чисел Бернулли и чисел Фибоначчи 685 ПРИЛОЖЕНИЕ Б. ОСНОВНЫЕ ОБОЗНАЧЕНИЯ 687 ПРЕДМЕТНО-ИМЕННОЙ УКАЗАТЕЛЬ 692