В этой основательной и вместе с тем доступной книге проектировщик новаторского программного обеспечения Александр Степанов и его коллега Дэниэл Роуз объясняют принципы обобщенного программирования и стоящее за ними понятие математической абстракции. Понимание этих принципов поможет вам писать код одновременно более простой и более эффективный. Любой достаточно квалифицированный программист, умеющий логически мыслить, уже обладает достаточными знаниями для прочтения этой книги. Авторы на удивление доходчиво сообщают необходимые сведения из общей алгебры и теории чисел. Они подробно объясняют, какие проблемы должны были сначала разрешить математики, в затем показывают, как найденные ими решения переводятся на язык обобщенного программирования и позволяют создать эффективный и элегантный код. Для демонстрации важнейшей роли математических оснований во многих современных приложениях авторы показывают, как полученные результаты и обобщенные алгоритмы можно применить в практически используемой криптосистеме с открытым ключом. Читая эту книгу, вы освоите мыслительный процесс, необходимый для эффективного программирования, и научитесь обобщать найденные для частного алгоритмы с целью расширить область их полезного применения без потери эффективности. Вы также постигнете, в чем состоит ценность математики для программирования, - и это понимание пригодится вне зависимости от того, на каком языке вы пишете и какую парадигму применяете. Александр А. Степанов занимается программированием с 1972 года, сначала в Советском Союзе, а затем, после эмиграции в 1977 году, в США. Он принимал участие в программировании операционных систем, инструментальных средств программирования, компиляторов и библиотек. В работе по основаниям программирования ему оказывали поддержку компания Дженерал Электрик, Политехнический университет, компании BellLabs, HP, SGI, Adobe, и - с 2009 года по сей день - A9.com, дочерняя компания Amazon, специализирующаяся на технологиях поиска. В 1995 году журнал "Dr. Dobb'sJournal" присудил ему премию "За выдающиеся заслуги в программировании" за проектирование стандартной библиотеки шаблонов C++ (StandardTemplateLibrary). Дэниэл Э. Роуз - ученый-исследователь, занимал руководящие должности в компаниях Apple, AltaVista, Xigo, Yahoo и A9.com. Круг его научных интересов охватывает технологии поиска, от низкоуровневых алгоритмов сжатия индекса до вопросов взаимодействия машины и человека в процессе поиска в веб. Роуз руководил в компании Apple группой, разработавшей систему локального поиска для компьютера Macintosh. Он обладатель докторской степени по когнитивистике и информатике, присужденной Калифорнийским университетом в Сан-Диего, а также степени бакалавра по философии, присужденной Гарвардским университетом. - Античные парадоксы, красивые теоремы, единство и противоположность непрерывного и дискретного - Действенные математические подходы к абстрагированию - Общая алгебра как источник идей обобщенного программирования - Аксиомы, доказательства, теории и модели: применение математических методов для организации знаний об алгоритмах и структурах данных - Удивительные тонкости, скрывающиеся в простых программистских задачах, и какие уроки можно из них извлечь - Как теоретические знания помогают практической реализации

Благодарности
Об авторах
От авторов
Предисловие автора к русскому
изданию
Глава 1. О чем эта
книга
1. 1. Программирование и
математика
1.2. Исторические
справки
1.3. Требования к
читателю
1.4. План
книги
Глава 2. Первый
алгоритм
2.1. Египетское
умножение
2.2. Улучшение
алгоритма
1.3. Заключительные
мысли
Глава 3. Теория чисел в Древней
Греции
3.1. Геометрические свойства целых
чисел
3.2. Просеивание простых
чисел
3.3. Реализация и оптимизация
кода
3.4. Совершенные
числа
3.5. Пифагорейская
программа
3.6. Фатальный изъян в
программе
3.7. Заключительные
мысли
Глава 4. Алгоритм
Евклида
4.1. Афины и
Александрия
4.2. Алгоритм Евклида нахождения наибольшей
общей меры
4.3. Тысяча лет без
математики
4.4. Странная история
нуля
4.5. Алгоритмы нахождения частного и
остатка
4.6. Повторное использование
кода
4.7. Доказательство правильности
алгоритма
4.8. Заключительные
мысли
Глава 5. Зарождение современной теории чисел
5.1. Простые числа Мерсенна и
Ферма
5.2. Малая теорема Ферма
5.3. Сокращение
5.4. Доказательство малой теоремы Ферма
5.5. Теорема Эйлера
5.6. Применение арифметики по
модулю""!"
5.7. Заключительные мысли
Глава 6. Абстракция в математике
6.1. Группы
6.2. Моноиды и
полугруппы
6.3. Некоторые теоремы о
группах
6.4. Подгруппы и циклические
группы
6.5. Теорема
Лагранжа
6.6. Теории и
модели
6.7. Примеры категоричных и некатегоричиых
теорий
6.8. Заключительные
мысли
Глава 7. Вывод обобщенного алгоритма
7.1. Осмысление требований к
алгоритму.
7.2. Требования к А
7.3. Требования к N
7.4. Новые требования
7.5. От умножения к возведению в
степень
7.6. Обобщение
операции
7.7. Вычисление чисел
Фибоначчи
7.8. Заключительные
мысли
Глава 8. Еще об алгебраических структурах
8.1. Стевин, полиномы и
ПОД
8.2. Геттинген и немецкая
математика
8.3. Нётер и рождение общей
алгебры
8.4. Кольца
8.5. Умножение матриц и
полукольца
8.6. Приложение: социальные сети и кратчайшие
пути
8.7. Евклидовы кольца
8.8. Поля и другие алгебраические
структуры
8.9. Заключительные
мысли
Глава 9. Организация математических знаний.
9.1. Доказательства
9.2. Первая теорема
9.3. Евклид и аксиоматический метод
9.4. Альтернативы евклидовой
геометрии
9.5. Формалистический подход
Гильберта
9.6. Пеано и его аксиомы
9.7. Построение арифметики
9.8. Заключительные мысли
10. Основные понятия программирования
10.1. Аристотель и
абстракции
10.2. Значения и
типы
10.3. Концепции
10 4. Итераторы
10 5 Категории, операции и характеристики
итераторов
10.6. Диапазоны
10.7. Линейный
поиск
10.8. Двоичный
поиск
10.9. Заключительные
мысли
Глава 11. Алгоритмы
перестановки
11.1. Перестановки и
транспозиции
11.2. Обмен
диапазонов
11.3. Циклическая
перестановка
11.4. Использование
циклов
11.5. Обращение
11.6. Пространственная
сложность
11.7. Алгоритмы, адаптирующиеся к объему
памяти
11.8. Заключительные
мысли
Глава 12. Обобщения
НОД
12.1. Аппаратные ограничения и более
эффективный алгоритм
12.2. Обобщение алгоритма
Штайна
12.3. Теорема
Безу
12.4. Расширенный алгоритм
Евклида
12.5. Применения
НОД
12.6. Заключительные
мысли
Глава 13. Реальное
приложение
13.1. Криптология
13.2. Проверка
простоты
13.3. Тест
Миллера-Рабина
13.4. Алгоритм RSA: как и почему он
работает
13.5. Заключительные мысли
Глава 14.
Заключение
Дополнительная
литература
Приложение А
Обозначения
Приложение В. Стандартные приемы
доказательства
Доказательство от
противного
Доказательство по индукции
В.З. Принцип Дирихле
Приложение С. Язык C++ для программистов на
других языках
С. 1. Шаблонные
функции
С.2. Концепции
С.З. Синтаксис объявлений и типизированные
константы
С.4. Объекты-функции
С.5. Предусловия, постусловия и
утверждения
Сб. Алгоритмы и структуры данных
STL
С.7. Итераторы и
диапазоны
С.8. Использование using для псевдонимов типов и
функций типов в С++11
С.9. Списки инициализаторов в
С++11
С.10. Лямбда-функции в
С++11
СИ. Замечание о ключевом слове
inline
Библиография
Предметный указатель