Искусство программирования. Том 1. Основные алгоритмы. 3-е издание. Дональд Э. Кнут

Первый том серии книг Искусство программирования начинается с описания основных понятий и методов программирования. Затем автор сосредотачивается на рассмотрении информационных структур — представлении информации внутри компьютера, структурных связях между элементами данных и о способам эффективной работы с ними. Для методов имитации, символьных вычислений, числовых методов, методов разработки программного обеспечения даны примеры элементарных приложений. По сравнению с предыдущим изданием, добавлены десятки простых, но в то же время очень важных алгоритмов. В соответствии с современными направлениями исследований был существенно переработан также раздел математического введения.

Содержание

Предисловие Предисловия к книге Искусство программирования, том 1. Основные алгоритмы 

Введение Введение к книге Искусство программирования, том 1. Основные алгоритмы  

Глава 1. ОСНОВНЫЕ ПОНЯТИЯ 

1.1. АЛГОРИТМЫ 

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

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

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

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

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

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

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

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

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

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

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

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

*1.2.11.1. Символ O 

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

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

1.3. MIX 

1.3.1. Описание MIX 

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

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

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

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

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

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

1.4.3.1. Имитатор MIX 

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

1.4.4. Ввод и вывод 

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

Глава 2. ИНФОРМАЦИОННЫЕ СТРУКТУРЫ 

2.1. ВВЕДЕНИЕ 

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

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

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

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

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

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

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

2.3. ДЕРЕВЬЯ 

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

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

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

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

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

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

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

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

2.3.4.5. Длина пути 

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

2.3.5. Списки и “сборка мусора” 

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

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

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

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

ПРИЛОЖЕНИЕ A. ТАБЛИЦЫ ЗНАЧЕНИЙ НЕКОТОРЫХ КОНСТАНТ 

A.1. Основные константы (десятичные) 

A.2. Основные константы (восьмеричные) 

A.3. Значения гармонических чисел, чисел Бернулли и чисел Фибоначчи 

ПРИЛОЖЕНИЕ Б. ОСНОВНЫЕ ОБОЗНАЧЕНИЯ