Краткое содержание
Предисловие 15
Часть 1. Предварительные сведения 19
Глава 1. Как расколоть орешек 21
Глава 2. Ага! Алгоритмы 29
Глава 3. Программы и структуры данных 41
Глава 4. Как писать правильные программы 53
Глава 5. Немного программирования 65
Часть 2. Производительность 79
Глава 6. Производительность в перспективе 81
Глава 7. Предварительные оценки 89
Глава 8. Методы разработки алгоритмов 99
Глава 9. Оптимизация программ 109
Глава 10. Экономия памяти 123
Часть 3. Программный продукт 139
Глава 11. Сортировка 141
Глава 12. Задача о выборке 153
Глава 13. Поиск 161
Глава 14. Кучи 177
Глава 15. Жемчужная строка 191
Эпилог к первому изданию 205
Эпилог ко второму изданию 207
Приложения 209
Приложение 1. Каталог алгоритмов 211
Приложение 2. Умеете ли вы делать оценки? 217
Приложение 3. Модель стоимости времени и памяти 219
Приложение 4. Правила оптимизации программ 223
Приложение 5. Классы C++ 229
Подсказки к некоторым задачам 233
Решения избранных задач 238
Алфавитный указатель 265
Содержание
Предисловие 15
О книге 15
Программы 16
Читателям первого издания 17
Благодарности к первому изданию 17
Благодарности ко второму изданию 18
От издательства 18
Часть 1. Предварительные сведения 19
Глава 1. Как расколоть орешек 21
1.1. Дружеский разговор 21
1.2. Точная постановка задачи 22
1.3. Разработка программы 23
1.4. Набросок решения 24
1.5. Основные принципы 25
1.6. Задачи 2G
1.7. Дополнительная литература 28
Глава 2. Ага! Алгоритмы 29
2.1. Три задачи 29
2.2. Вездесущий двоичный поиск 30
2.3. Мощь элементарного 32
2.4. Соберем все вместе: сортировка 34
2.5. Принципы 35
Сортировка 35
Двоичный поиск 35
Сигнатуры 35
Постановка задачи 36
Перспективы для программиста 36
2.6. Задачи 36
2.7. Дополнительная литература 38
2.8. Реализация поиска анаграмм 38
Глава 3. Программы и структуры данных 41
3.1. Про1рамма обработки результаюи опроса 41
3.2. Обработка шаблонных писем 43
3.3. Примеры 45
Меню 45
Сообщения об ошибках 46
Функции для работы с датами 46
Анализ слов 46
3.4. Структурирование данных 47
3.5. Обработка специальных данных 47
Гипертекст 47
Пары «имя-значение» 48
Таблицы (spreadsheets) 48
Базы данных 48
Специальные языки 49
3.6. Принципы 49
Повторяющиеся действия выполняйте над массивами 50
Инкапсулируйте сложные структуры 50
Используйте самые совершенные средства везде, где это возможно.. 50 Данные должны определять структуру программы 50
3.7. Задачи 50
3.8. Дополнительная литература 52
Глава 4. Как писать правильные программы 53
4.1. Двоичный поиск бросает вызов 53
4.2. Пишем программу 54
4.3. Понимание программы 56
4.4. Принципы 59
Утверждения 59
Последовательное выполнение 59
Ветвление 59
Циклы 60
Функции 60
4.5. Смысл верификации программ 60
4.6. Задачи 61
4.7. Дополнительная литература 64
Глава 5. Немного программирования 65
5.1. От псевдокода к С 65
5.2. Тестовая программа 67
5.3. Искусство вставки утверждений 69
5.4. Автоматизация тестирования 70
5.5. Время выполнения 72
5.6. Окончательная программа 73
5.7. Принципы 74
Тестовые программы 74
Кодирование 74
Тестирование 74
Отладка 75
Время работы 75
5.8. Задачи 75
5.9. Дополнительная литература 76
5.10. Отладка 77
Часть 2. Производительность 79
Глава 6. Производительность в перспективе 81
6.1. Пример 81
Алгоритмы и структуры данных 82
Оптимизация алгоритма 83
Реорганизация структуры данных 83
Оптимизация кода 83
Аппаратура 83
6.2. Уровни разработки 84
Постановка задачи 84
Структуризация системы 85
Алгоритмы и структуры данных 85
Оптимизация кода 85
Системное программное обеспеченно 85
Аппаратное обеспечение 86
6.3. Принципы 86
Если нужно ускорить систему незначительно 86
Если нужно сушест пенно ускорить работу 86
6.4. Задачи 87
6.5. Дополнительная лик*ра1ура 88
Глава 7. Предварительные оценки 89
7.1. Основы мастерства 90
Два ответа лучик*, чем один 90
Быстрые проверки 90
Правила большого пальца 91
Практика 92
7.2. Оценка производительности 92
7.3. Запас прочности 94
7.4. Закон Литтла 95
7.5. Принципы 96
7.0. Задачи 96
7.7. Дополнительная литература 97
7.8. Быстрые вычисления в повседневной жизни (дополнение) 98
Глава 8. Методы разработки алгоритмов 99
8.1. Задача и простой алгоритм 99
8.2. Два квадратичных алгоритма 100
8.3. Алгоритм «разделяй и властвуй» 101
8.4. Сканирующий алгоритм 103
8 5. И что это значит? 104
8.6. Принципы 105
Сохранение данных во избежание повтрпых вычислений 106
Предваршельная обработка данных и помещение их в структуры . 106
Алгоритмы «разделяй и властвуй» 106
Сканирующие алгоритмы 106
Кумулятивные суммы 106
Нижняя граница 107
8.7. Задачи 107
8.8. Дополнительная литература 108
Глава 9. Оптимизация программ 109
9.1. \ ппнчная история 109
9.2. Первая помощь: примеры 111
Деление с остатком 1 11
Функции, макросы и встраиваемый код 111
Последовательный поиск 112
Вычисление расстояний на сфере 114
9.3. On I импзируем двоичный поиск 115
9.4. Принципы 118
Важность эффективности 118
Средства измерения 118
Уровни разработки 119
Когда вместо ускорения получается замедление 119
Графическая программа Ван Банка 119
Деление с ос'гатком 119
Функции, макросы и встраиваемый код 119
П о с л е д о в а те л ь и ы й 11 о и с к 120
Вычисление расстоянии на сфере 120
Двоичный поиск 120
9.5. Задачи 120
9.6. Дополнительная литература 122
Глава 10. Экономия памяти 123
10.1. Ключ к успеху — простота 123
10.2. Приме]) 124
10.3. Размещение данных в памяти 128
Не храпите то, что можно вычислить 128
Разреженные структуры данных 128
Сжатие данных 129
Политика выделения памяти 130
Сборка мусора 130
10.4. Методы уменьшения размера кода 131
Определение функции 132
Интерпретаторы 132
11 ере вод па м а пи 11 и Iы й код 133
10.5. Принципы 133
«Стоимость» памяти 133
Эффективное уменьшение объема 134
Измерение объемов памяти 134
Компромиссы 134
Работа с окружением 135
Использование подходящих среда в 135
10.6. Задачи 135
10.7. Дополнительная литература 136
10.8. Пример эффективного сжашя 137
Часть 3. Программный продукт 139
Глава 11. Сортировка 141
11.1. Сортиройка вставкой 141
11.2. Простая быстрая сортировка 143
11.3. Улучшенные быстрые сортировки 146
11.4. Принципы 149
Библиотечная функция qsort 149
Сортировка встав ко ii 150
Случай больших п 150
11.5. Задачи 150
1 1.6. Дополнительная литература 151
Глава 12. Задача о выборке 153
12.1. Задача 153
12.2. Одно из решении 154
12.3. Пространство разработки 155
12.4. Принципы 158
Понимание предложенной задачи 158
Постановка абстрактной задачи 158
Исследование пространства разработки 158
Реализация одного из решений 158
Оглядывайтесь назад 158
12.5. Задачи 159
12.6. Дополнительная литература 160
Глава 13. Поиск 161
13.1. Интерфейс 161
13.2. Линейные структуры 163
13.3. Двоичное дерево поиска 167
13.4. Структуры для целых чисел 169
13.5. Принципы 171
Важность библhoick 172
Важпост ь памят и 172
Методы оптимизации программ 172
13.6. Задачи 172
13.7 Дополнительная лшература 173
13.8. Примеры поиска 174
Глава 14. Кучи 177
14.1. Структура данных 177
14.2. Две важные функции 179
14.3. Очереди с приоритетом 182
14.4. Алгортм сортировки 185
14.5. Прппцппы 188
Эффективность 188
Правильность 188
Абстракция 188
Абстрагирование процедур 188
Абстрактные типы данных 188
14.6. Задачи 189
14.7. Дополнительная литература 190
Глава 15. Жемчужная строка 191
15.1. Слона 191
15.2. Фразы 195
15.3. Порождение текста 197
15.4. Принципы 202
Задачи со строками 202
Структуры данных для хранения строк 202
Хеширование 202
Сбалансированные деревья 202
Массивы остатков 202
Библиотеки или «самодельные» компоненты? 202
15.5. Задачи 203
15.6. Дополнительная литература 204
Эпилог к первому изданию 205
Эпилог ко второму изданию 207
Приложения 209
Приложение 1. Каталог алгоритмов 211
Сортировка 211
Поиск 213
Прочие алгоритмы на множествах 214
Алгоритмы па строках 215
Алгоритмы с векторами и матрицами 215
Случайные объекты 215
Численные алгоритмы 216
Приложение 2. Умеете ли вы делать оценки? 217
Приложение 3. Модель стоимости времени и памяти 219
Приложение 4. Правила оптимизации программ 223
Жертвуем памятью ради скорости 223
Жертвуем скоростью ради памяти 224
Циклы 224
Логические правила 225
Составление процедур 226
Сосга в л е и и е в ы раже и и и 227
Приложение 5. Классы C++ 229
Подсказки к некоторым задачам 233
Решения избранных задач 238
Решения к главе 1 238
Решения к главе 2 241
Решения к главе 3 244
Решения к главе 4 246
Решения к главе 5 246
Решения к главе 6 247
Решения к главе 7 248
Решения к главе 8 249
Решения к глаие 9 251
Решения к главе 10 253
Решения к главе1 11 254
Решения к главе 12 257
Решения к главе 13 258
Решения к главе 14 261
Решения к главе 15 263
Алфавитный указатель 265
Опубликовал Kest
April 16 2013 15:07:07 ·
0 Комментариев ·
3467 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
