Книга написана одним из крупнейших зарубежных специалистов в области программирования, известным советскому читателю по переводам его книг на русский язык (например, «Структурное программирование», «Мир», 1972). Она посвящена фундаментальным вопросам конструирования корректных и изящных программ для ЭВМ. В ней предлагается методика формального вывода программы из математической постановки задачи. При этом прослеживается развитие алгоритмов вплоть до создания программ. Материал излагается в форме остроумных и поучительных задач по программированию.
Книга представляет значительный интерес для широкого круга программистов.
ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА
Программирование богато и многообразно. Ведь кажется нет такой сферы человеческой деятельности, где нельзя было бы с пользой применить вычислительную машину для оценки, информационно-справочного обслуживания, планирования, моделирования и т. п. И это многообразие задач переходит в многообразие программ, которые должны разрабатывать программисты. Они пытаются справиться с этим многообразием, «заключив» его в проблемно-ориентированные языки программирования. Языки вбирают в себя специфические черты конкретных сфер программирования — характерные структуры данных, принципы организации типичных процессов, соответствующую терминологию — и таким образом делают сам процесс программирования более универсальным. Одновременно они освобождают программистов от необходимости детализировать программы до уровня слишком мелких машинных команд и даже от необходимости знать особенности конкретных вычислительных машин. Более того, операционные системы призваны превратить вычислительные машины из предмета постоянного беспокойства в «существа», которые сами заботятся о программисте и готовы оказывать всяческие услуги ему и его программе.
И тем не менее, после того, как любая более или менее сложная задача сформулирована (пусть даже в адекватных и удобных терминах) и машина выбрана (пусть даже в самом деле готовая к всевозможным услугам), каждый программист снова и снова остается один на один со своей собственной задачей: ему нужно составить программу! Выбрать, как именно следует расположить и связать данные в памяти, понять, какая именно последовательность операторов, — способных сделать все что угодно и оттого одновременно и податливых и опасных — выполнит поставленную задачу. И как организовать эти операторы в цикл, который будет с каждым шагом приближать машину к намеченной цели. Выбрать, понять, изобрести, проверить, усомниться и повторить все сначала.
ОГЛАВЛЕНИЕ
Предисловие редактора перевода .................. 5
Предисловие.......... .'................. 8
От автора............................. "
0. Абстракция исполнения.................... 17
1. Роль языков программирования................. 24
2. Состояния и их характеристика................. 27
3. Характеристика семантики................... 34
4. Семантическая характеристика языка программирования . . . '1-5
5. Две теоремы.......................... 62
6. О проектировании правильно завершаемых конструкций..... 66
7. Пересмотренный алгоритм Евклида............... 70
8. Формальное рассмотрение нескольких небольших примеров ... 77
9. Когда недетерминированность ограничена ,........... Ю4
- 10. Размышлений на тему. «Область действия переменных» . . . .111
11. Векторные переменные..................... 131
12. Теорема о линейном просмотре................. 145
13. Задача о следующей перестановке................ 147
14. Задача о голландском национальном флаге........... 151
15. Обновление последовательного файла.............. 1?8
16. Еще раз о задачах слияния................... 165
17. Упражнение, приписываемое Р. У. Хэммингу........ 172
18. Задача поиска по образцу................... 178
19. Представление числа в виде суммы двух квадратов....... 184
20. Задача о наименьшем простом множителе большого числа . . . 187
21. Задача о самых удаленных селениях............. 194
22. Задача о кратчайшем покрывающем дереве........... 199
23. Алгоритм Рема выделения классов эквивалентности....... 208
24. Задача о выпуклой оболочке в трехмерном пространстве .... 217
25. Нахождение максимально сильных компонент в ориентированном графе.............................. 245
26. О руководствах и реализациях................. 256
27. Ретроспективы......................... 265
Цена: 150руб.
