Elements of Programming / Начала программирования
Год издания: 2011
Автор: Alexander Stepanov, Paul McJones / Александр Степанов, Пол Мак-Джоунс
Переводчик: Константин Птицын
Жанр или тематика: Программирование, математические основы
Издательство: ООО "И. Д. Вильямс"
ISBN: 978–5–8459–1708–9
Язык: Русский
Формат: PDF
Качество: Издательский макет или текст (eBook)
Интерактивное оглавление: Да
Количество страниц: 272
Описание: В настоящей книге применяется дедуктивный подход к программированию, основанный на объединении программ с абстрактными математическими теориями, которые обеспечивают их работу. Представлены вместе описания этих теорий, алгоритмы, записанные с точки зрения этих теорий, а также теоремы и леммы, описывающие их свойства. Реализация алгоритмов на реальном языке программирования является центральной темой книги. Эта книга предназначена для тех, кто стремится глубже понять суть программирования, будь то профессиональные программисты или ученые и инженеры, для которых программирование составляет важную часть их профессиональной деятельности. Книга предназначена для чтения от начала и до конца. Читатели смогут достичь понимания материала, только изучая код, доказывая леммы и выполняя упражнения.
"В книге содержатся одни из наиболее замечательных образцов кода, с которыми я когда-либо сталкивался."
- Бьярне Страуструп, разработчик языка C++
Краткое содержание книги:
В главе 1 приведено описание значений, объектов, типов, процедур и концепций.
Главы 2–5 посвящены алгоритмам на алгебраических структурах, таких как полугруппы и полностью упорядоченные множества.
В главах 6–11 описываются алгоритмы на абстрактных представлениях памяти.
В главе 12 рассматриваются объекты, содержащие другие объекты.
В послесловии представлены общие размышения о подходе, изложенном в книге.
Отзывы о книге
"Как известно, инженеры-механики, строители и электрики в своей работе опираются на надежные математические основания.
С другой стороны, инженеры-программисты часто практикуют свое ремесло, не имея или почти не имея представления о том, на каком математическом фундаменте зиждется то, чем они занимаются. А потом мы не можем понять, почему программное обеспечение печально известно тем, что поставляется с опозданием и содержит много ошибок, тогда как другие инженеры обычно сдают в эксплуатацию готовые мосты, автомобили, электрические приборы и пр. своевременно и с незначительными дефектами. Настоящая книга призвана устранить это неравенство. Члены моего коллектива, занимающиеся сложными разработками в компании Adobe, после прохождения курса по материалам книги получили чрезвычайно положительную отдачу от вложенных усилий. На первый взгляд книга может показаться весьма специализированной, предназначенной только для теоретиков в области компьютерных наук, но в действительности она должна быть обязательно изучена всеми инженерами-программистами, которые ставят перед собой серьезные задачи".
- Мартин Ньюэлл, заслуженный исследователь Adobe
"Я счастлив видеть, что содержимое курса Алекса, разработку которого я настоятельно поддерживал как технический директор Silicon Graphics, теперь доступно для всех программистов в этой изящной небольшой книге".
- Форест Баскетт, главный партнер, New Enterprise Associates
"Терпение и организационный опыт Пола помогли создать на базе математического подхода Алекса четко структурированное произведение, а это - впечатляющий подвиг!"
- Роберт В. Тэйлор, основатель Xerox PARC SCL и DEC Systems Research Center
Об авторах
Александр Степанов изучал математику в Московском государственном университете с 1967 по 1972 гг. Он работает в области программирования с 1972 года: сначала в Советском Союзе, а после эмиграции в 1977 году в Соединенных Штатах. Он занимался программированием операционных систем, инструментов программирования, компиляторов и библиотек. Его работа над началами программирования поддерживалась General Electric, Политехническим институтом Бруклина, AT&T, HP, SGI, и, с 2002 года, — Adobe. В 1995 году он получил премию "Excellence in Programming" (от Dr. Dobb's Journal) за проект стандартной библиотеки шаблонов C++.
Пол Мак-Джоунс изучал прикладную математику в Калифорнийском университете, Беркли, с 1967 до 1971 гг. С 1967 года он занимался программированием в областях операционных систем, сред программирования, систем обработки транзакций и приложений для промышленных предприятий и потребительского рынка. Он работал в Калифорнийском университете, IBM, Xerox, Tandem, DEC, и, с 2003 года, — в Adobe. В 1982 году он и его соавторы получили премию "ACM Programming Systems and Languages Paper" за статью "Диспетчер по восстановлению системы управления базами данных System R".
Оглавление
Предисловие
└─── Об авторах
Глава 1. Вводные определения
├─── 1.1. Категории идей: сущность, вид, род
├─── 1.2. Значения
├─── 1.3. Объекты
├─── 1.4. Процедуры
├─── 1.5. Регулярные типы
├─── 1.6. Регулярные процедуры
├─── 1.7. Концепции
└─── 1.8. Резюме
Глава 2. Преобразования и их орбиты
├─── 2.1. Преобразования
├─── 2.2. Орбиты
├─── 2.3. Точка столкновения
├─── 2.4. Измерение размеров орбиты
├─── 2.5. Действия
└─── 2.6. Резюме
Глава 3. Ассоциативные операции
├─── 3.1. Ассоциативность
├─── 3.2. Вычисление степеней
├─── 3.3. Преобразования программ
├─── 3.4. Процедуры для специального случая
├─── 3.5. Параметризация алгоритмов
├─── 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. Алгоритм gcd по Штейну
├─── 5.7. Частное
├─── 5.8. Частное и остаток для отрицательных величин
├─── 5.9. Концепции и их модели
├─── 5.10. Компьютерные целочисленные типы
└─── 5.11. Резюме
Глава 6. Итераторы
├─── 6.1. Читаемость
├─── 6.2. Итераторы
├─── 6.3. Интервалы
├─── 6.4. Читаемые интервалы
├─── 6.5. Увеличение интервалов
├─── 6.6. Прямые итераторы
├─── 6.7. Индексированные итераторы
├─── 6.8. Двунаправленные итераторы
├─── 6.9. Итераторы с произвольным доступом
└─── 6.10. Резюме
Глава 7. Координатные структуры
├─── 7.1. Бифуркатные координаты
├─── 7.2. Двунаправленные бифуркатные координаты
├─── 7.3. Координатные структуры
├─── 7.4. Изоморфизм, эквивалентность и упорядочение
└─── 7.5. Резюме
Глава 8. Координаты с изменяемыми последователями
├─── 8.1. Связанные итераторы
├─── 8.2. Переупорядочение связей
├─── 8.3. Области применения переупорядочений связей
├─── 8.4. Связанные бифуркатные координаты
└─── 8.5. Резюме
Глава 9. Копирование
├─── 9.1. Записываемость
├─── 9.2. Копирование с учетом позиции
├─── 9.3. Копирование на основе предиката
├─── 9.4. Взаимная перестановка интервалов
└─── 9.5. Резюме
Глава 10. Переупорядочения
├─── 10.1. Перестановки
├─── 10.2. Переупорядочения
├─── 10.3. Алгоритмы обращения
├─── 10.4. Алгоритмы вращения
├─── 10.5. Выбор алгоритма
└─── 10.6. Резюме
Глава 11. Разбиение и слияние
├─── 11.1. Разбиение
├─── 11.2. Сбалансированное приведение
├─── 11.3. Слияние
└─── 11.4. Резюме
Глава 12. Составные объекты
├─── 12.1. Простые составные объекты
├─── 12.2. Динамические последовательности
├─── 12.3. Основополагающий тип
└─── 12.4. Резюме
Послесловие
├─── Регулярность
├─── Концепции
├─── Алгоритмы и их интерфейсы
├─── Методы программирования
├─── Значения указателей
└─── Резюме
Приложение A. Математическая система обозначений
Приложение B. Язык программирования
├─── B.1. Определение языка
├─────── Система обозначений синтаксиса
├─────── Лексические соглашения
├─────── Основные типы
├─────── Выражения
├─────── Перечисления
├─────── Структуры
├─────── Процедуры
├─────── Инструкции
├─────── Шаблоны
├─────── Встроенные средства
├─── B.2. Макросы и характеристические структуры
├─────── Ограничения шаблонов
├─────── Встроенные средства
└─────── Функции типа
Литература
Предметный указатель
