Начала программирования

Александр Степанов, Пол Мак-Джонс

В настоящей книге применяется дедуктивный подход к программированию, основанный на объединении программ с абстрактными математическими теориями, которые обеспечивают их работу.

Представлены вместе описания этих теорий, алгоритмы, записанные с точки зрения этих теорий, а также теоремы и леммы, описывающие их свойства. Реализация алгоритмов на реальном языке программирования является центральной темой книги.

Эта книга предназначена для тех, кто стремится глубже понять суть программирования, будь то профессиональные программисты или ученые и инженеры, для которых программирование составляет важную часть их профессиональной деятельности. Книга предназначена для чтения от начала и до конца. Читатели смогут достичь понимания материала, только изучая код, доказывая леммы и выполняя упражнения.

«В книге содержатся одни из наиболее замечательных образцов кода, с которыми я когда-либо сталкивался.» - Бьярне Страуструп, разработчик языка C++

Краткое содержание книги

В главе 1 приведено описание значений, объектов, типов, процедур и концепций. Главы 2–5 посвящены алгоритмам на алгебраических структурах, таких как полугруппы и полностью упорядоченные множества. В главах 6–11 описываются алгоритмы на абстрактных представлениях памяти. В главе 12 рассматриваются объекты, содержащие другие объекты. В послесловии представлены общие размышления о подходе, изложенном в книге.

«Как известно, инженеры-механики, строители и электрики в своей работе опираются на надежные математические основания. С другой стороны, инженеры-программисты часто практикуют свое ремесло, не имея или почти не имея представления о том, на каком математическом фундаменте зиждется то, чем они занимаются. А потом мы не можем понять, почему программное обеспечение печально известно тем, что поставляется с опозданием и содержит много ошибок, тогда как другие инженеры обычно сдают в эксплуатацию готовые мосты, автомобили, электрические приборы и пр. своевременно и с незначительными дефектами. Настоящая книга призвана устранить это неравенство. Члены моего коллектива, занимающиеся сложными разработками в компании Adobe, после прохождения курса по материалам книги получили чрезвычайно положительную отдачу от вложенных усилий. На первый взгляд книга может показаться весьма специализированной, предназначенной только для теоретиков в области компьютерных наук, но в действительности она должна быть обязательно изучена всеми инженерами-программистами, которые ставят перед собой серьезные задачи».

- Мартин Ньюэлл, заслуженный исследователь Adobe: «Я счастлив видеть, что содержимое курса Алекса, разработку которого я настоятельно поддерживал как технический директор Silicon Graphics, теперь доступно для всех программистов в этой изящной небольшой книге».

- Форест Баскетт, главный партнер, New Enterprise Associates

«Терпение и организационный опыт Пола помогли создать на базе математического подхода Алекса четко структурированное произведение, а это - впечатляющий подвиг!»

- Роберт В. Тэйлор, основатель Xerox PARC SCL и DEC Systems Research Center

Издательство: Вильямс, 2011 г.

ISBN 978-5-8459-1708-9, 978-0-321-63537-2

Количество страниц: 272.

Содержание книги «Начала программирования»:

10 Предисловие
15 Глава 1. Вводные определения
- 15 1.1 Категории идей: сущность, вид, род
- 16 1.2 Значения
- 18 1.3 Объекты
- 20 1.4 Процедуры
- 22 1.5 Регулярные типы
- 23 1.6 Регулярные процедуры
- 25 1.7 Концепции
- 29 1.8 Резюме
31 Глава 2. Преобразования и их орбиты
- 31 2.1 Преобразования
- 34 2.2 Орбиты
- 36 2.3 Точка столкновения
- 42 2.4 Измерение размеров орбиты
- 43 2.5 Действия
- 44 2.6 Резюме
45 Глава 3. Ассоциативные операции
- 45 3.1 Ассоциативность
- 47 3.2 Вычисление степеней
- 49 3.3 Преобразования программ
- 53 3.4 Процедуры для специального случая
- 56 3.5 Параметризация алгоритмов
- 57 3.6 Линейные рекуррентные соотношения
- 60 3.7 Процедуры накопления
- 60 3.8 Резюме
63 Глава 4. Линейные упорядочения
- 63 4.1 Классификация отношений
- 65 4.2 Полные и слабые упорядочения
- 66 4.3 Выбор порядка
- 74 4.4 Естественное полное упорядочение
- 75 4.5 Семейства производных процедур
- 75 4.6 Расширение процедур выбора порядка
- 76 4.7 Резюме
77 Глава 5. Упорядоченные алгебраические структуры
- 77 5.1 Основные алгебраические структуры
- 82 5.2 Упорядоченные алгебраические структуры
- 83 5.3 Остаток
- 86 5.4 Наибольший общий делитель
- 89 5.5 Обобщение НОД
- 91 5.6 Алгоритм gcd по Штейну
- 92 5.7 Частное
- 93 5.8 Частное и остаток для отрицательных величин
- 95 5.9 Концепции и их модели
- 97 5.10 Компьютерные целочисленные типы
- 98 5.11 Резюме
99 Глава 6. Итераторы
- 99 6.1 Читаемость
- 101 6.2 Итераторы
- 102 6.3 Интервалы
- 105 6.4 Читаемые интервалы
- 112 6.5 Увеличение интервалов
- 114 6.6 Прямые итераторы
- 119 6.7 Индексированные итераторы
- 119 6.8 Двунаправленные итераторы
- 121 6.9 Итераторы с произвольным доступом
- 122 6.10 Резюме
125 Глава 7. Координатные структуры
- 125 7.1 Бифуркатные координаты
- 129 7.2 Двунаправленные бифуркатные координаты
- 133 7.3 Координатные структуры
- 134 7.4 Изоморфизм, эквивалентность и упорядочение
- 140 7.5 Резюме
141 Глава 8. Координаты с изменяемыми последователями
- 141 8.1 Связанные итераторы
- 142 8.2 Переупорядочение связей
- 148 8.3 Области применения переупорядочений связей
- 151 8.4 Связанные бифуркатные координаты
- 155 8.5 Резюме
157 Глава 9. Копирование
- 157 9.1 Записываемость
- 159 9.2 Копирование с учетом позиции
- 165 9.3 Копирование на основе предиката
- 171 9.4 Взаимная перестановка интервалов
- 174 9.5 Резюме
177 Глава 10. Переупорядочения
- 177 10.1 Перестановки
- 180 10.2 Переупорядочения
- 182 10.3 Алгоритмы обращения
- 185 10.4 Алгоритмы вращения
- 192 10.5 Выбор алгоритма
- 196 10.6 Резюме
197 Глава 11. Разбиение и слияние
- 197 11.1 Разбиение
- 203 11.2 Сбалансированное приведение
- 207 11.3 Слияние
- 212 11.4 Резюме
213 Глава 12. Составные объекты
- 213 12.1 Простые составные объекты
- 220 12.2 Динамические последовательности
- 227 12.3 Основополагающий тип
- 230 12.4 Резюме
231 Послесловие
235 Глава А. Математическая система обозначений
237 Глава В. Язык программирования
- 237 8.1 Определение языка
- 244 8.2 Макросы и характеристические структуры
246 Литература
250 Предметный указатель