Наверх

Джон Бентли  2-е издание, 1999 (Rus)
Жемчужины программирования

Содержание
Предисловие

О книге
Программы
Читателям первого издания
Благодарности к первому изданию
Благодарности ко второму изданию
От издательства


Часть 1. Предварительные сведения

ГЛАВА 1. КАК РАСКОЛОТЬ ОРЕШЕК
1.1. Дружеский разговор
1.2. Точная постановка задачи
1.3. Разработка программы
1.4. Набросок решения
1.5. Основные принципы
1.6. Задачи
1.7. Дополнительная литература

ГЛАВА 2. АГА!  АЛГОРИТМЫ
2.1. Три задачи
2.2. Вездесущий двоичный поиск
2.3. Мощь элементарного
2.4. Соберем все вместе: сортировка
2.5. Принципы
      Сортировка
      Двоичный поиск
      Сигнатуры
      Постановка задачи
      Перспективы для программиста
2.6. Задачи
2.7. Дополнительная литература
2.8. Реализация поиска анаграмм

ГЛАВА 3. ПРОГРАММЫ И СТРУКТУРЫ ДАННЫХ
3.1. Программа обработки результатов опроса
3.2. Обработка шаблонных писем
3.3. Примеры
      Меню
      Сообщения об ошибках
      Функции для работы с датами
      Анализ слов
3.4. Структурирование данных
3.5. Обработка специальных данных
      Гипертекст
      Пары "имя-значение"
      Таблицы (spreadsheets)
      Базы данных
      Специальные языки
3.6. Принципы
      Повторяющиеся действия выполняйте над массивами
      Инкапсулируйте сложные структуры
      Используйте самые совершенные средства везде, где это возможно
      Данные должны определять структуру программы
3.7. Задачи
3.8. Дополнительная литература

ГЛАВА 4. КАК ПИСАТЬ ПРАВИЛЬНЫЕ ПРОГРАММЫ
4.1. Двоичный поиск бросает вызов
4.2. Пишем программу
4.3. Понимание программы
4.4. Принципы
      Утверждения
      Последовательное выполнение
      Ветвление
      Циклы
      Функции
4.5. Смысл верификации программ
4.6. Задачи
4.7. Дополнительная литература

ГЛАВА 5. НЕМНОГО ПРОГРАММИРОВАНИЯ
5.1. От псевдокода к С
5.2. Тестовая программа
5.3. Искусство вставки утверждений
5.4. Автоматизация тестирования
5.5. Время выполнения
5.6. Окончательная программа
5.7. Принципы
      Тестовые программы
      Кодирование
      Тестирование
      Отладка
      Время работы
5.8. Задачи
5.9. Дополнительная литература
5.10. Отладка


Часть 2. Производительность

ГЛАВА 6. ПРОИЗВОДИТЕЛЬНОСТЬ В ПЕРСПЕКТИВЕ
6.1. Пример
      Алгоритмы и структуры данных
      Оптимизация алгоритма
      Реорганизация структуры данных
      Оптимизация кода
      Аппаратура
6.2. Уровни разработки
      Постановка задачи
      Структуризация системы
      Алгоритмы и структуры данных
      Оптимизация кода
      Системное программное обеспечение
      Аппаратное обеспечение
6.3. Принципы
      Если нужно ускорить систему незначительно
      Если нужно существенно ускорить работу
6.4. Задачи
6.5. Дополнительная литература

ГЛАВА 7. ПРЕДВАРИТЕЛЬНЫЕ ОЦЕНКИ
7.1. Основы мастерства
      Два ответа лучше, чем один
      Быстрые проверки
      Правила большого пальца
      Практика
7.2. Оценка производительности
7.3. Запас прочности
7.4. Закон Литтла
7.5. Принципы
7.6. Задачи
7.7. Дополнительная литература
7.8. Быстрые вычисления в повседневной жизни (дополнение)

ГЛАВА 8. МЕТОДЫ РАЗРАБОТКИ АЛГОРИТМОВ
8.1. Задача и простой алгоритм
8.2. Два квадратичных алгоритма
8.3. Алгоритм "разделяй и властвуй"
8.4. Сканирующий алгоритм
8.5. И что это значит?
8.6. Принципы
      Сохранение данных во избежание повторных вычислений
      Предварительная обработка данных и помещение их в структуры
      Алгоритмы "разделяй и властвуй"
      Сканирующие алгоритмы
      Кумулятивные суммы
      Нижняя граница
8.7. Задачи
8.8. Дополнительная литература

ГЛАВА 9. ОПТИМИЗАЦИЯ ПРОГРАММ
9.1. Типичная история
9.2. Первая помощь: примеры
      Деление с остатком
      Функции, макросы и встраиваемый код
      Последовательный поиск
      Вычисление расстояний на сфере
9.3. Оптимизируем двоичный поиск
9.4. Принципы
      Важность эффективности
      Средства измерения
      Уровни разработки
      Когда вместо ускорения получается замедление
      Графическая программа Ван Вайка
      Деление с остатком
      Функции, макросы и встраиваемый код
      Последовательный поиск
      Вычисление расстояний на сфере
      Двоичный поиск
9.5. Задачи
9.6. Дополнительная литература

ГЛАВА 10. ЭКОНОМИЯ ПАМЯТИ
10.1. Ключ к успеху - простота
10.2. Пример
10.3. Размещение данных в памяти
      Не храните то, что можно вычислить
      Разреженные структуры данных
      Сжатие данных
      Политика выделения памяти
      Сборка мусора
10.4. Методы уменьшения размера кода
      Определение функции
      Интерпретаторы
      Перевод на машинный код
10.5. Принципы
      "Стоимость" памяти
      Эффективное уменьшение объема
      Измерение объемов памяти
      Компромиссы
      Работа с окружением
      Использование подходящих средств
10.6. Задачи
10.7. Дополнительная литература
10.8. Пример эффективного сжатия


Часть 3. Программный продукт

ГЛАВА 11. СОРТИРОВКА

11.1. Сортировка вставкой
11.2. Простая быстрая сортировка
12 Содержание
11.3. Улучшенные быстрые сортировки
11.4. Принципы
      Библиотечная функция qsort
      Сортировка вставкой
      Случай больших п
11.5. Задачи
11.6. Дополнительная литература

ГЛАВА 12. ЗАДАЧА О ВЫБОРКЕ
12.1. Задача
12.2. Одно из решений
12.3. Пространство разработки
12.4. Принципы
      Понимание предложенной задачи
      Постановка абстрактной задачи
      Исследование пространства разработки
      Реализация одного из решений
      Оглядывайтесь назад
12.5. Задачи
12.6. Дополнительная литература

ГЛАВА 13. ПОИСК
13.1. Интерфейс
13.2. Линейные структуры
13.3. Двоичное дерево поиска
13.4. Структуры для целых чисел
13.5. Принципы
      Важность библиотек
      Важность памяти
      Методы оптимизации программ
13.6. Задачи
13.7. Дополнительная литература
13.8. Примеры поиска

ГЛАВА 14. КУЧИ
14.1. Структура данных
14.2. Две важные функции
14.3. Очереди с приоритетом
14.4. Алгоритм сортировки
14.5. Принципы
      Эффективность
      Правильность
      Абстракция
      Абстрагирование процедур
      Абстрактные типы данных
14.6. Задачи
14.7. Дополнительная литература

ГЛАВА 15. ЖЕМЧУЖНАЯ СТРОКА
15.1. Слова
15.2. Фразы
15.3. Порождение текста
15.4. Принципы
      Задачи со строками
      Структуры данных для хранения строк
      Хеширование
      Сбалансированные деревья
      Массивы остатков
      Библиотеки или "самодельные" компоненты?
15.5. Задачи
15.6. Дополнительная литература

Эпилог к первому изданию
Эпилог ко второму изданию


Приложения
Приложение 1. Каталог алгоритмов
      Сортировка
      Поиск
      Прочие алгоритмы на множествах
      Алгоритмы на строках
      Алгоритмы с векторами и матрицами
      Случайные объекты
      Численные алгоритмы
Приложение 2
. Умеете ли вы делать оценки?
Приложение 3. Модель стоимости времени и памяти
Приложение 4. Правила оптимизации программ
      Жертвуем памятью ради скорости
      Жертвуем скоростью ради памяти
      Циклы
      Логические правила
      Составление процедур
      Составление выражений
Приложение 5. Классы C++
      Подсказки к некоторым задачам

Решения избранных задач
Решения к главе 1
Решения к главе 2
Решения к главе 3
Решения к главе 4
Решения к главе 5
Решения к главе 6
Решения к главе 7
Решения к главе 8
Решения к главе 9
Решения к главе 10
Решения к главе 11
Решения к главе 12
Решения к главе 13
Решения к главе 14
Решения к главе 15

Алфавитный указатель