От математики к обобщенному программированию

От математики  
к обобщенному  
программированию

Александр А. Степанов, Дэниэл Э. Роуз

From Mathematics  
to Generic Programming

Alexander A. Stepanov, Daniel E. Rose

Upper Saddle River, NJ • Boston • Indianapolis • San Francisco
New York • Toronto • Montreal • London • Munich • Paris • Madrid
Capetown • Sydney • Tokyo • Singapore • Mexico City

От математики 
к обобщенному 
программированию

Москва, 2023

Александр А. Степанов, Дэниэл Э. Роуз

2-е издание, электронное

УДК 511+519.6
ББК 22.13+22.18+22.19
С79

С79
Cтепанов, Александр А.
От математики к обобщенному программированию / А. А. Степанов, Д. Роуз ; пер. 
с англ. А. А. Слинкина. — 2-е изд., эл. — 1 файл pdf : 266 с. — Москва : ДМК Пресс, 2023. — 
Систем. требования: Adobe Reader XI либо Adobe Digital Editions 4.5 ; экран 10". — Текст : 
электронный.

ISBN 978-5-89818-306-6

В этой основательной и вместе с тем доступной книге авторы объясняют принципы обобщенного 
программирования и стоящее за ними понятие математической абстракции.
Любой достаточно квалифицированный программист, умеющий логически мыслить, уже обладает 
достаточными знаниями для прочтения этой книги. Авторы на удивление доходчиво сообщают 
необходимые сведения из общей алгебры и теории чисел. Они объясняют, какие проблемы 
должны были разрешить математики, и показывают, как найденные ими решения переводятся на 
язык обобщенного программирования и позволяют создать эффективный и элегантный код.
Читая эту книгу, вы освоите мыслительный процесс, необходимый для правильного программирования, 
и научитесь обобщать найденные для частного алгоритмы с целью расширить область 
их полезного применения без потери эффективности. Вы также постигнете, в чем состоит ценность 
математики для программирования, — и это понимание пригодится вне зависимости от того, на 
каком языке вы пишете и какую парадигму применяете.

УДК 511+519.6 
ББК 22.13+22.18+22.19

Электронное издание на основе печатного издания: От математики к обобщенному программированию / 
А. А. Степанов, Д. Роуз ; пер. с англ. А. А. Слинкина. — Москва : ДМК Пресс, 2016. — 264 с. — ISBN 978-5-
97060-379-6. — Текст : непосредственный.

Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было форме и какими бы 
то ни было средствами без  письменного разрешения владельцев авторских прав.
Материал, изложенный в данной книге, многократно проверен. Но поскольку вероятность технических ошибок все равно 
существует, издательство не может гарантировать абсолютную точность и правильность приводимых сведений. В связи с 
этим издательство не несет ответственности за возможные ошибки, связанные с использованием книги.

В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений, установленных техническими средствами защиты авторских 
прав, правообладатель вправе требовать от нарушителя возмещения убытков или выплаты компенсации.

ISBN 978-5-89818-306-6
© 2015 Pearson Education, Inc.
© Оформление, перевод, ДМК Пресс, 2016

Содержание

Благодарности.......................................................................... 9

Об.авторах............................................................................. 10

От.авторов.............................................................................. 11

Предисловие.автора.к.русскому.изданию.................................... 12

Глава.1..О.чем.эта.книга............................................................ 13
1.1. Программирование и математика ..................................................................................13
1.2. Исторические справки ........................................................................................................14
1.3. Требования к читателю .......................................................................................................15
1.4. План книги ..............................................................................................................................15

Глава.2..Первый.алгоритм......................................................... 17
2.1. Египетское умножение .......................................................................................................18
2.2. Улучшение алгоритма .........................................................................................................21
2.3. Заключительные мысли .....................................................................................................24

Глава.3..Теория.чисел.в.Древней.Греции...................................... 25
3.1. Геометрические свойства целых чисел .........................................................................25
3.2. Просеивание простых чисел .............................................................................................28
3.3. Реализация и оптимизация кода .....................................................................................30
3.4. Совершенные числа .............................................................................................................35
3.5. Пифагорейская программа ...............................................................................................38
3.6. Фатальный изъян в программе .......................................................................................40
3.7. Заключительные мысли .....................................................................................................44

Глава.4..Алгоритм.Евклида........................................................ 45
4.1. Афины и Александрия ........................................................................................................45
4.2. Алгоритм Евклида нахождения наибольшей общей меры ....................................47
4.3. Тысяча лет без математики ...............................................................................................51
4.4. Странная история нуля ......................................................................................................52
4.5. Алгоритмы нахождения частного и остатка ...............................................................54
4.6. Повторное использование кода .......................................................................................57
4.7. Доказательство правильности алгоритма ....................................................................60
4.8. Заключительные мысли .....................................................................................................61

Глава.5..Зарождение.современной.теории.чисел.......................... 62
5.1. Простые числа Мерсенна и Ферма ................................................................................62
5.2. Малая теорема Ферма ........................................................................................................66
5.3. Сокращение ............................................................................................................................69
5.4. Доказательство малой теоремы Ферма ........................................................................72

 Содержание

5.5. Теорема Эйлера .....................................................................................................................74
5.6. Применение арифметики по модулю ............................................................................78
5.7. Заключительные мысли .....................................................................................................79

Глава.6..Абстракция.в.математике.............................................. 80
6.1. Группы ......................................................................................................................................80
6.2. Моноиды и полугруппы .....................................................................................................83
6.3. Некоторые теоремы о группах .........................................................................................86
6.4. Подгруппы и циклические группы ................................................................................88
6.5. Теорема Лагранжа ................................................................................................................90
6.6. Теории и модели ...................................................................................................................94
6.7. Примеры категоричных и некатегоричных теорий ..................................................97
6.8. Заключительные мысли .....................................................................................................99

Глава.7..Вывод.обобщенного.алгоритма.....................................102
7.1. Осмысление требований к алгоритму ........................................................................ 102
7.2. Требования к A ................................................................................................................... 103
7.3. Требования к N ................................................................................................................... 106
7.4. Новые требования ............................................................................................................. 108
7.5. От умножения к возведению в степень ..................................................................... 109
7.6. Обобщение операции ....................................................................................................... 111
7.7. Вычисление чисел Фибоначчи ..................................................................................... 114
7.8. Заключительные мысли .................................................................................................. 117

Глава.8..Еще.об.алгебраических.структурах................................118
8.1. Стевин, полиномы и НОД ............................................................................................. 118
8.2. Геттинген и немецкая математика ............................................................................... 123
8.3. Нётер и рождение общей алгебры ............................................................................... 128
8.4. Кольца ................................................................................................................................... 129
8.5. Умножение матриц и полукольца ................................................................................ 132
8.6. Приложение: социальные сети и кратчайшие пути .............................................. 134
8.7. Евклидовы кольца ............................................................................................................. 136
8.8. Поля и другие алгебраические структуры ................................................................ 137
8.9. Заключительные мысли .................................................................................................. 138

Глава.9..Организация.математических.знаний.............................141
9.1. Доказательства ................................................................................................................... 141
9.2. Первая теорема ................................................................................................................... 144
9.3. Евклид и аксиоматический метод ............................................................................... 147
9.4. Альтернативы евклидовой геометрии ........................................................................ 148
9.5. Формалистический подход Гильберта ....................................................................... 151
9.6. Пеано и его аксиомы ........................................................................................................ 153
9.7. Построение арифметики ................................................................................................. 156
9.8. Заключительные мысли .................................................................................................. 159

Содержание  7

Глава.10..Основные.понятия.программирования..........................160
10.1. Аристотель и абстракции ............................................................................................. 160
10.2. Значения и типы .............................................................................................................. 162
10.3. Концепции ......................................................................................................................... 163
10.4. Итераторы .......................................................................................................................... 166
10.5. Категории, операции и характеристики итераторов .......................................... 167
10.6. Диапазоны ......................................................................................................................... 171
10.7. Линейный поиск .............................................................................................................. 173
10.8. Двоичный поиск .............................................................................................................. 174
10.9. Заключительные мысли ............................................................................................... 178

Глава.11..Алгоритмы.перестановки............................................179
11.1. Перестановки и транспозиции ................................................................................... 179
11.2. Обмен диапазонов........................................................................................................... 182
11.3. Циклическая перестановка .......................................................................................... 185
11.4. Использование циклов .................................................................................................. 188
11.5. Обращение ......................................................................................................................... 192
11.6. Пространственная сложность ..................................................................................... 196
11.7. Алгоритмы, адаптирующиеся к объему памяти ................................................... 197
11.8. Заключительные мысли ............................................................................................... 198

Глава.12..Обобщения.НОД........................................................199
12.1. Аппаратные ограничения и более эффективный алгоритм ............................. 199
12.2. Обобщение алгоритма Штайна .................................................................................. 202
12.3. Теорема Безу ..................................................................................................................... 204
12.4. Расширенный алгоритм Евклида .............................................................................. 208
12.5. Применения НОД ........................................................................................................... 212
12.6. Заключительные мысли ............................................................................................... 213

Глава.13..Реальное.приложение................................................215
13.1. Криптология ..................................................................................................................... 215
13.2. Проверка простоты ......................................................................................................... 217
13.3. Тест Миллера–Рабина ................................................................................................... 220
13.4. Алгоритм RSA: как и почему он работает .............................................................. 222
13.5. Заключительные мысли ............................................................................................... 225

Глава.14..Заключение.............................................................226

Дополнительная.литература.....................................................228

Приложение.А..Обозначения....................................................233

Приложение.В..Стандартные.приемы.доказательства..................236
B.1. Доказательство от противного ..................................................................................... 236
B.2. Доказательство по индукции ........................................................................................ 237

 Введение

B.3. Принцип Дирихле ............................................................................................................ 238

Приложение.С..Язык.С++.для.программистов.на.других.языках......239
C.1. Шаблонные функции ...................................................................................................... 239
C.2. Концепции .......................................................................................................................... 240
C.3. Синтаксис объявлений и типизированные константы ....................................... 241
C.4. Объекты-функции............................................................................................................ 241
C.5. Предусловия, постусловия и утверждения ............................................................. 242
C.6. Алгоритмы и структуры данных STL........................................................................ 243
C.7. Итераторы и диапазоны ................................................................................................. 244
C.8. Использование using для псевдонимов типов и функций типов в C++11 ..... 245
C.9. Списки инициализаторов в C++11 ............................................................................ 246
C.10. Лямбда-функции в C++11 .......................................................................................... 246
C.11. Замечание о ключевом слове inline.......................................................................... 247

Библиография.......................................................................248

Предметный.указатель............................................................252

Благодарности

Мы благодарны всем, кто способствовал появлению этой книги. Руководство 
нашей компании A9.com активно поддерживало проект с самого начала. Билл 
Стейсиор предложил создать курс, легший в основу этой книги, и выбрал тему 
из предложенных нами вариантов. Брайан Пинкертон не только прослушал весь 
курс, но и всячески приветствовал идею превратить его в книгу. Мы благодарим 
также Мэта Маркуса, который вместе с Алексом читал похожий курс в компании 
Adobe в 2004–2005 годах.
На протяжении всего процесса важную роль играли другие члены группы по 
фундаментальным структурам данных и алгоритмам поиска. Анил Ганголли (Anil 
Gangolli) помогал при отборе материала для курса, Райан Эрнст (Ryan Ernst) подготовил 
большую часть инфраструктуры программирования, а Парамжит Оберой 
(Paramjit Oberoi) высказывал ценнейшие замечания на этапе написания книги. 
Нам доставило истинное удовольствие работать с ними, и мы признательны им 
за помощь.
Мы выражаем благодарность редакторам Питеру Гордону (Peter Gordon) и Грэ-
гу Донку (Greg Doench), а также всему коллективу, собравшемуся под крышей 
издательства Addison-Wesley, в том числе главному редактору Джону Фуллеру, 
редактору по производству Мэри Кэсел Уилсон (Mary Kesel Wilson), выпускающему 
редактору Джилл Хоббс (Jill Hobbs), верстальщику и специалисту по LaTeX 
Лори Хьюз (Lori Hughes), за усилия по превращению рукописи в безупреч ную 
книгу.
Наконец, мы хотим поблагодарить наших друзей, семьи и коллег, которые 
прочли  черновые варианты книги и поделились с нами замечаниями, исправлениями, 
предложениями, советами и т. д.: Гас пера Азмана (Gašper Ažman), Джона 
Баннинга (John Banning), Синтию Дворк (Cynthia Dwork), Германа Эпельмана 
(Hernan Epelman), Райана Эрнста (Ryan Ernst), Анила Ганголли (Anil Gangolli), 
Сьюзан Груббер (Susan Gruber), Джона Кальба (Jon Kalb), Роберта Лера (Robert 
Lehr), Дмитрия Лещинера (Dmitry Leshchiner), Тома Лондона (Tom London), 
Марка Манасси (Mark Manasse), Пола Макджонса (Paul McJones), Николаса 
Николова (Nicolas Nicolov), Гора Нишанова (Gor Nishanov), Парамжита Обероя 
(Paramjit Oberoi), Шона Пэрента (Sean Parent), Фернандо Пелличиони (Fernando 
Pelliccioni), Джона Рейзера (John Reiser), Роберта Роуза (Robert Rose), Стефана 
Варгиаса (Stefan Vargyas) и Адама Юнга (Adam Young). Благодаря им книга стала 
намного лучше.

Об авторах

Александр А. Степанов изучал математику в Московском государственном университете 
с 1967 по 1972 год. С 1972 года занимается программированием, сначала 
в Советском Союзе, а затем, после эмиграции в 1977 году, в США. Он принимал 
участие в программировании операционных систем, инструментальных средств 
программирования, компиляторов и библиотек. В работе по основаниям программирования 
ему оказывали поддержку компания Дженерал Электрик, Политехнический 
университет, компании Bell Labs, HP, SGI, Adobe, и – с 2009 года по сей 
день – A9.com, дочерняя компания Amazon, специализирующаяся на технологиях 
поиска. В 1995 году журнал «Dr. Dobb’s Journal» присудил ему премию «За 
выдающиеся заслуги в программировании» за проектирование стандартной библиотеки 
шаблонов C++ (Standard Template Library).
Дэниэл Э. Роуз – ученый-исследователь, занимал руководящие должности 
в компаниях Apple, AltaVista, Xigo, Yahoo и A9.com. Круг его научных интересов 
охватывает технологии поиска, от низкоуров невых алгоритмов сжатия индекса 
до вопросов взаимодействия машины и человека в процессе поиска в веб. Роуз 
руководил в компании Apple группой, разработавшей систему локального поиска 
для компьютера Macintosh. Он обладатель докторской степени по когнитивистике 
и информатике, присужденной Калифорнийским университетом в Сан-Диего, 
а также степени бакалавра по философии, присужденной Гарвардским университетом.

От авторов

Разделение информатики и математики сильно обедняет обе науки. Лекции, положенные 
в основу этой книги, – предпринятая мной попытка показать, что обе 
деятельности – древнюю, восходящую к истокам нашей цивилизации, и самую что 
ни на есть современную – можно соединить.
Мне очень повезло, что мой друг Дэн Роуз, под руководством которого наша 
группа применяла принципы обобщенного программирования к проектированию 
поисковой системы, согласился преобразовать мои довольно бессвязные лекции 
в цельную книгу. Мы оба надеемся, что читателям понравится плод нашей совместной 
работы.
–А. А. С.

Книга, которую вы держите в руках, основана на заметках к курсу лекций «Алгоритмические 
путешествия», прочитанному Алексом Степановым в компании 
A9.com в 2012 году. Но в ходе нашей с Алексом работы по переложению материала 
курса в форму книги мы пришли к выводу, что могли бы поведать более интересную 
историю – об обобщенном программировании и его математических основаниях. 
Это побудило нас существенно изменить организацию книги и исключить 
целый раздел, посвященный теории множеств и математической логике, который 
как-то не укладывался в этот рассказ. Пришлось также добавить и удалить ряд деталей, 
чтобы сделать изложение более связным и доступным читателям, не имеющим 
осно вательной математической подготовки.
Алекс, в отличие от меня, получил математическое образование. Кое в чем мне 
было нелегко разобраться, но приложенные усилия позволили мне понять, что 
нуждается в дополнительном объяснении. Если иногда мы трактуем какие-то вопросы 
не так, как это сделал бы математик, или используем не вполне стандартную 
терминологию, или сознательно упрощаем изложение, то это целиком моя вина.
– Д. Э. Р.

Предисловие автора  
к русскому изданию

Эта книга родилась из курсов, которые я читал в Америке, но корни ее ведут 
к моим русским учителям. О Лобачевском и Пуанкаре я узнал от Эрнеста Борисовича 
Винберга, когда он нам, десятиклассникам второй школы, рассказывал про 
созданную Пуанкаре модель геометрии Лобачевского. Общую алгебру я полюбил, 
слушая лекции Александра Геннадиевича Куроша на мехмате МГУ. Он уверял, 
что «алгебра шлифует головы», и действительно на моей голове есть несколько до 
блеска отшлифованных мест. О теореме Лагранжа, да и вообще о группах я узнал 
от Анны Петровны Мишиной, а про классификацию простых полей – от Юрия 
Ивановича Манина. Пониманием важности истории математики я обязан Владимиру 
Игоревичу Арнольду, а об основаниях арифметики узнал из книги «Теоретическая 
арифметика» его отца, Игоря Владимировича Арнольда.
От моего учителя, Александра Самуиловича Завадье, идет моя любовь к грекам. 
Когда мне было 14 лет, он посоветовал мне читать Платона, особенно порекомендовав «
Пир» в переводе Соломона Конс тантиновича Апта. Спустя 50 лет я по-
прежнему влюблен в Платона и считаю «Пир» сочинением почти божественным.
В Америке я работал с целым рядом замечательных программистов и многому 
от них научился, но моим настоящим учителем программирования был Александр 
Михайлович Гуревич, главный конст руктор управляющей вычислительной 
машины ТА-100. У него я научился необходимости разрабатывать ортогональные 
и минимальные интерфейсы и десятки раз переписывать код, добиваясь красоты 
и оптимальности.
Я с некоторой робостью ожидаю появления этой книги в России, стране моих 
учителей, но надеюсь, что она донесет до молодых программистов хотя бы толику 
того чувства прекрасного, которым одарили меня мои наставники.

Глава 1

О чем эта книга

Невозможно познать мир, не познав математику.

Роджер Бэкон. Большое сочинение

Эта книга о программировании, но она отличается от большинства книг на ту же 
тему. Наряду с алгоритмами и кодом вы найдете в ней математические доказательства 
и исторические сведения о математических открытиях с античных времен до 
наших дней.
Если быть точным, то эта книга посвящена обобщенному программированию, 
подходу, сформировавшемуся в 1980-х годах и ставшему популярным после создания 
библиотеки Standard Template Library (STL) для языка C++ в 1990-х годах. 
Можно дать такое определение.

Определение 1.1. Обобщенным программированием называется подход к программированию, 
в котором упор делается на проектирование таких алгоритмов 
и структур данных, которые работали бы в наиболее общей ситуации без потери 
эффективности.

У тех, кому доводилось использовать STL, возможно, мелькнула мысль: «Как?! 
Вот это и есть обобщенное программирование? А как же шаблоны, характеристики 
итераторов и все прочее?» А это всего лишь языковые средства, обеспечивающие 
поддержку обобщенного программирования. И хотя, безусловно, следует знать, 
как использовать их эффективно, обобщенное программирование как таковое – 
это отношение к программированию, а не конкретный набор средств.
Мы считаем, что такое отношение – стремление писать код самым общим способом – 
должны воспринять все программисты. Компоненты хорошо написанной 
обобщенной программы проще повторно использовать и модифицировать, чем 
компоненты программы, в которой структуры данных, алгоритмы и интерфейсы 
отягощены ненужными предположениями о конкретном применении. Обобщенная 
программа оказывается одновременно проще и эффективнее.

1.1. Программирование и математика

Так откуда же проистекает обобщенное отношение к программированию и как ему 
научиться? Проистекает оно из математики, а точнее, из ее раздела, называемого 
общей алгеброй. Чтобы помочь вам разобраться в этом подходе, мы дадим краткое 
введение в общую алгебру, сосредоточившись на том, как рассуждать об объектах 

 О чем эта книга

в терминах абст рактных свойств операций над ними. Обычно этот предмет изучается 
на математических факультетах университетов, но мы полагаем, что он исключительно 
важен для понимания обобщенного программирования.
Вообще, многие фундаментальные идеи программирования берут начало в математике. 
Знания о том, как эти идеи возникли и развивались, поможет при обдумывании 
проекта программы. Например, «Начала» Евклида, написанные больше 
2000 лет назад, и по сей день остаются одним из лучших примеров построения 
сложной системы из мелких, простых для понимания элементов.
Хотя существо обобщенного программирования – абстрагирование, абстракции – 
не возникают готовыми из ничего. Чтобы понять, как построить нечто общее, 
начать следует с чего-то конкретного. В частности, чтобы выявить подходящие 
абст ракции, необходимо понять особенности конкретной предметной области.
Абстракции, рассматриваемые в общей алгебре, берут начало в конкретных результатах 
одного из самых старых разделов математики – теории чисел. Поэтому 
мы познакомимся с некоторыми ключевыми идеями теории чисел, которая занимается 
свойствами целых чисел и, в особенности делимостью.
Мыслительный процесс, вырабатывающийся при изучении математики, поможет 
вам усовершенствоваться в программировании. Но мы также покажем, что 
иногда и сами математические результаты становятся фундаментом современных 
программных приложений. В частности, в конце книги мы увидим, как некоторые 
результаты такого рода применяются в криптографических протоколах, лежащих 
в основе конфиденциальности в сети и электронной коммерции.
В этой книге мы постоянно переходим от математики к программированию и 
обратно. Важные математические идеи переплетаются с обсуждением как конкретных 
алгоритмов, так и методов обобщенного программирования. Некоторые 
алгоритмы мы упоминаем лишь вскользь, тогда как другие уточняем и обобщаем 
на протяжении всей книги. Две главы посвящены одной лишь математике, а две 
другие – исключительно программированию, но большая часть глав содержит материал, 
относящийся к тому и другому.

1.2. Исторические справки

Нам всегда казалось, что изучение становится проще и интереснее, если материал 
представлен в историческом контексте. Что происходило в описываемое время? 
Кем были участники событий, как они пришли к своим идеям? Была ли работа 
одного человека основана на результатах другого или это была попытка опровержения 
предшествующих результатов? Поэтому, знакомя читателя с математическими 
идеями, мы стараемся рассказывать об их истории и о людях, которые их 
выдвинули. Во многих случаях мы приводим краткие биографии математиков, 
сыгравших главную роль в описываемой истории. Это не исчерпывающие энциклопедические 
статьи, а всего лишь попытка погрузить конкретных людей в исторический 
контекст.
Хотя мы привержены историческому взгляду на вещи, это не означает, что книга 
задумана как история математики или что описанные в ней идеи представлены в