От издателей русского перевода 1

О книге "Искусство программирования" 2

От редактора перевода 4

ПРЕДИСЛОВИЕ 5

Предисловие к третьему изданию 11

Процедура чтения книг этой серии 14

ПРИМЕЧАНИЯ К УПРАЖНЕНИЯМ 16

ОСНОВНЫЕ ПОНЯТИЯ 19

1.1. алгоритмы 19

УПРАЖНЕНИЯ 28

1.2. МАТЕМАТИЧЕСКОЕ ВВЕДЕНИЕ 29

1.2.1. Математическая индукция 30

УПРАЖНЕНИЯ 38

1.2.2. Числа, степени и логарифмы 41

УПРАЖНЕНИЯ 46

1.2.3. Суммы и произведения 48

УПРАЖНЕНИЯ (часть 2) 58

1.2.4. Целочисленные функции и элементарная теория чисел 60

УПРАЖНЕНИЯ 63

1.2.5. Перестановки и факториалы 67

1.2.6. Биномиальные коэффициенты 74

УПРАЖНЕНИЯ 92

1.2.7. гармонические числа 97

УПРАЖНЕНИЯ 100

1.2.8. Числа Фибоначчи 101

УПРАЖНЕНИЯ 106

1.2.9. Производящие функции 110

УПРАЖНЕНИЯ 117

1.2.10. Анализ алгоритма 119

УПРАЖНЕНИЯ 128

*1.2.11. Асимптотические представления 130

*1.2.11.1. СИМВОЛ 0. 130

УПРАЖНЕНИЯ 134

*1.2.11.2. Формула суммирования Эйлера. 135

УПРАЖНЕНИЯ 139

*1.2.11.3. Применение асимптотических формул. 140

УПРАЖНЕНИЯ 145

1.3. MIX 148

1.3.1. Описание MIX 158

УПРАЖНЕНИЯ 166

1.3.2. Язык ассемблера компьютера MIX 170

УПРАЖНЕНИЯ (часть 1) 182

УПРАЖНЕНИЯ (часть 2) 183

1.3.3. Применение к перестановкам 190

УПРАЖНЕНИЯ 209

1.4. НЕКОТОРЫЕ ФУНДАМЕНТАЛЬНЫЕ МЕТОДЫ ПРОГРАММИРОВАНИЯ  213

1.4.1. Подпрограммы 213

УПРАЖНЕНИЯ 220

1.4.2. Сопрограммы 221

 УПРАЖНЕНИЯ 228

1.4.3. Программы интерпретаторы 229

1.4.3.1. Имитатор MIX. 231

УПРАЖНЕНИЯ 240

*1.4.3.2. Программы трассировки. 240

1.4.4. ВВОД и ВЫВОД 243

УПРАЖНЕНИЯ 255

1.4.5. История и библиография 258

ГЛАВА 2

ИНФОРМАЦИОННЫЕ СТРУКТУРЫ 262

2.1. ВВЕДЕНИЕ 262

УПРАЖНЕНИЯ 267

2.2. ЛИНЕЙНЫЕ СПИСКИ  268

2.2.1. Стеки, очереди  и деки 268

УПРАЖНЕНИЯ 272

2.2.2. Последовательное распределение 274

УПРАЖНЕНИЯ 282

2.2.3. Связанное распределение 286

УПРАЖНЕНИЯ 301

2.2.4. Циклические списки 306

УПРАЖНЕНИЯ 311

2.2.5. Дважды связанные списки 313

УПРАЖНЕНИЯ 330

2.2.6. Массивы и ортогональные списки 332

УПРАЖНЕНИЯ 339

2.3. ДЕРЕВЬЯ 343

УПРАЖНЕНИЯ 352

2.3.1. Обход бинарных деревьев 353

УПРАЖНЕНИЯ 367

2.3.2. Представление деревьев в виде бинарных деревьев 371

УПРАЖНЕНИЯ 383

2.3.3. Другие представления деревьев 386

УПРАЖНЕНИЯ 397

2.3.4. Основные математические свойства деревьев 401

2.3.4.1. Свободные деревья. 401

УПРАЖНЕНИЯ 408

2.3.4.2. Ориентированные деревья. 411

УПРАЖНЕНИЯ 416

*2.3.4.3. Лемма о бесконечном дереве. 422

УПРАЖНЕНИЯ 424

*2.3.4.4. Перечисление деревьев. 426

УПРАЖНЕНИЯ 436

2.3.4.5. Длина пути. 440

УПРАЖНЕНИЯ 445

*2.3.4.6. История и библиография. 447

УПРАЖНЕНИЯ 449

2.3.5. Списки и "сборка мусора" 450

УПРАЖНЕНИЯ 464

2.4. МНОГОСВЯЗНЫЕ СТРУКТУРЫ 467

УПРАЖНЕНИЯ 476

2.5. ДИНАМИЧЕСКОЕ ВЫДЕЛЕНИЕ ПАМЯТИ 479

А. Резервирование. 479

В. Освобождение. 482

С. "Система двойников". 486

*Е. Метод распределённого подходящего. 495

F. Переполнение. 497

УПРАЖНЕНИЯ 498

2.6. ИСТОРИЯ И БИБЛИОГРАФИЯ  503

ОТВЕТЫ К УПРАЖНЕНИЯМ 512

РАЗДЕЛ 1.2.1 514

РАЗДЕЛ 1.2.2 515

РАЗДЕЛ 1.2.3 517

РАЗДЕЛ 1.2.4 522

РАЗДЕЛ 1.2.5 527

РАЗДЕЛ 1.2.6 530

РАЗДЕЛ 1.2.7 539

РАЗДЕЛ 1.2.8 540

РАЗДЕЛ 1.2.9 544

РАЗДЕЛ 1.2.10 547

РАЗДЕЛ 1.2.11.1 550

РАЗДЕЛ 1.2.11.2 551

РАЗДЕЛ 1.2.11.3 552

РАЗДЕЛ 1.3.1 555

РАЗДЕЛ 1.3.2 559

РАЗДЕЛ 1.3.3 570

РАЗДЕЛ 1.4.1 576

РАЗДЕЛ 1.4.2 577

РАЗДЕЛ 1.4.3.1 578

РАЗДЕЛ 1.4.3.2 579

РАЗДЕЛ 1.4.4 580

РАЗДЕЛ 2.2.1 584

РАЗДЕЛ 2.2.2 589

РАЗДЕЛ 2.2.3 594

РАЗДЕЛ 2.2.4 601

РАЗДЕЛ 2.2.5 603

РАЗДЕЛ 2.2.6 606

РАЗДЕЛ 2.3 611

РАЗДЕЛ 2.3.1 614

РАЗДЕЛ 2.3.2 623

РАЗДЕЛ 2.3.3 627

РАЗДЕЛ 2.3.4.1 630

РАЗДЕЛ 2.3.4.2 632

РАЗДЕЛ 2.3.4.3 639

РАЗДЕЛ 2.3.4.4 641

РАЗДЕЛ 2.3.4.5 648

РАЗДЕЛ 2.3.4.6 650

РАЗДЕЛ 2.3.5 655

РАЗДЕЛ 2.4 659

РАЗДЕЛ 2.5 661

ПРИЛОЖЕНИЕ А

ТАБЛИЦЫ ЗНАЧЕНИЙ НЕКОТОРЫХ КОНСТАНТ  674

ПРИЛОЖЕНИЕ Б

ОСНОВНЫЕ ОБОЗНАЧЕНИЯ 678

Д.Э. Кнут "Искусство программирования" том 1 "Основные алгоритмы. Основные понятия. Информационные структуры."