16 Жемчужины творчества программистов: Пер. с англ. - М.: Радио и связь, 1990. - 224с.: ил.
ISBN S-256-00704-1.
В книге американского автора на различных примерах из практики программирования показано, как хорошее понимание особенностей поставленной задачи позволяет найти оптимальное по быстродействию, объему требуемой памяти, легкости модификации решения. Наряду с конкретными примерами даны общие рекомендации по составлению оптимальных алгоритмов и программ. Рассмотрение построено по следующему принципу: постановка задачи, пример традиционного решения и объяснение его недостатков, углубленный анализ задачи и найденное в результате этого лучшее решение, изложение ряда принципов грамотного программирования.
Для программистов.
ОГЛАВЛЕНИЕ
Предисловие...................................................... 8
ЧАСТЬ I.Введение................................................ 11
Глава 1. Как расколоть орешек....................................... И
Л. Дружеский разговор........................................, . 12
.2. Точная формулировка задачи.................................... 13
.3. Разработка программы......................................... 13
.4. Набросок решения............................................ 15
.5. Основные принципы.......................................... 16
.6. Задачи.................................................... 17
.7. Литература для дополнительного чтения............................ 20
Глава 2. Ага! Алгоритмы........................................... 21
2.1. Три задачи.................................................. 21
2.2. Вездесущий двоичный поиск.................................... 22
2.3. Сила примитивов............................................. 24
2.4. Соберем все вместе (сортировка)................................. 26
2.5. Основные принципы.......................................... 27
2.6. Задачи.................................................... 29
2.7. Литература для вспомогательного чтения........................... 31
2.8. Реализация программы для анаграмм (дополнение).................... 31
Глава 3. Программы, работающие со структурами данных................... 34
3.1. Программа обработки результатов обследования...................... 34
3.2. формирование писем.......................................... 37
3.3. Примеры................................................... 41
3.4. Большая по объему программа................................... *3
3.5. Основные принципы.......................................... 45
3.6. Задачи.................................................... 46
3.7. Литература для дополнительного чтения............................ *
ЛЛ
Глава 4. Написание программ, не содержащих ошибок..................... *"
4.1. Двоичный поиск "бросает вызов"................................. *'
4.2. Написание программы...............................•......... *
4.3. Разбор программы............................................ I*
4.4. Реализация программы........................................ ^
4,5- Основные принципы.......................................... ~?
4.5. Зачем нужна верификация программ.............................. ™
с
4.7. Задачи.................................................... 62
4.8. Литература для дополнительного чтения............................ 65
4.9. Верификация программ при их "промышленном производстве * (дополнен ие) 65
ЧАСТЬ II. Эффективность.......................................... 68
Глава 5. Производительность в перспективе.............................. 69
5.1. Разбор примера.............................................. 69
5.2. Этапы разработки............................................. 72
5.3. Основные принципы.......................................... 74
5.4. Задачи.................................................... 75
5.5. Литература для дополнительного чтения............................ 76
Глава 6. Предварительные оценки.................................... 77
6.1. Основные навыки............................................ 78
6.2. Быстрые вычисления при разработке компьютерных систем.............. 80
6.3. "Запас прочности"............................................ 81
6.4. Разбор примера.............................................. 83
6.5. Основные принципы.......................................... 85
6.6. Задачи.................................................... 85
6.7. Литература для дополнительного чтения............................ 86
6.8. Быстрые вычисления в повседневной жизни (дополнение)............... 87
Глава 7. Методы разработки алгоритмов................................ 88
7.1. Задача и простой алгоритм ее решения............................. 89
7.2. Два квадратичных алгоритма.................................... 90
7.3. Алгоритм "разделяй и властвуй".................................. 92
7.4. Сканирующий алгоритм........................................ 94
7.5. Проверка на практике......................................... 95
7.6. Основные принципы,.......................................... 97
7.7. Задачи..................................................... 99
7.8. Литература для дополнительного чтения............................ 100
7.9. Влияние алгоритмов на качество программ (дополнение)................ 101
Глава 8. Оптимизация программы..................................... 103
8.1. Типичная история............................................ 103
8.2. Первая помощь.............................................. 104
8.3. "Основное лечение" — двоичный поиск............................. 108
8.4. Основные принципы........................................... 113
8.5. Задачи..................................................... 115
8.6. Литература для дополнительного чтения ........................... 117
8.7. Оптимизация программ на Коболе, используемых федеральным правительст-
вом (дополнение)............................................ 117
Глава 9. Сокращение объема памяти................................... 118
9.1. Простота — это ключ к успеху.................................... 119
9.2. Память для хранения данных.................................... 120
9.3. Сокращение количества команд.................................. 125
9.4. Основные принципы........................................... 127
9.5. Задачи..................................................... 129
9.6. Литература для дополнительного чтения............................ 130
9.7. Два примера большого сокращения памяти (дополнение)................ 130
6
ЧАСТЬ III. Программный продукт.................................... 133
Глава 10. Сортировка.............................................. 133
10.1. Сортировка методом вставок. Алгоритм порядка О (N )................ 134
10.2. Быстрая сортировка — алгоритм порядка О (N logN)................... 136
10.3. Основные принципы.......................................... 142
10.4. Задачи.................................................... 143
10.5. Литература для дополнительного чтения........................... 146
Глава 11. Поиск.................................................. 146
11.1. Задача.................................................... 146
11.2. Одно из решений............................................ 148
11.3. Пространство решений........................................ 149
11.4. Основные принципы.......................................... 154
11.5. Задачи.................................................... 155
11.6. Литература для дополнительного чтения........................... 157
Глава 12. Пирамиды.............................................. 157
12.1. Структуры данных........................................... 158
12.2. Две важные подпрограммы.................................... 160
12.3. Очереди с приоритетами....................................... 164
12.4. Алгоритм сортировки.. ........................................ 166
12.5. Основные принципы.......................................... 169
12.6. Задачи.................................................... 170
12.7. Литература для дополнительного чтения........................... 173
Глава 13. Программа проверки правописания............................ 173
13.1. Простая программа........................................... 173
13.2. Пространство возможных решений............................... 175
13.3. Программа с тонкостями....................................... 179
13.4. Основные принципы.......................................... 183
13.5. Задачи.................................................... 184
13.6. Литература для дополнительного чтения........................... 185
13.7. Почему проверка правописания — трудная задача (дополнение).......... 186
ЭПИЛОГ......................................................... 187
Приложение. Каталог алгоритмов.................................... 189
Сортировка.................................................... 1'"
Поиск........................................................ 192
Другие алгоритмы для работы с множествами........................... 1'3
Алгоритмы для векторов и матриц................................... "*
Случайные объекты.............................................. 194
Другие алгоритмы............................................... ^
Подсказки для некоторых задач........................................ 194
Решения некоторых задач............................................ 19
Цена: 100руб.
