Александр Александрович Степанов , Дэниэл Роуз - От математики к обобщенному программированию

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

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

Alexander A. Stepanov, Daniel E. Rose

From Mathematics
to Generic Programming

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

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

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

Москва, 2015

С79

Степанов Александр А., Роуз Дэниэл Э.
От математики к обобщенному программированию / пер. с англ. А. А. Слинкина. - М.: ДМК Пресс, 2015. - 264 с.: ил.
В этой основательной и вместе с тем доступной книге авторы объясняют принципы обобщенного
программирования и стоящее за ними понятие математической абстракции.
Любой квалифицированный программист, умеющий логически мыслить, уже обладает достаточными знаниями для ее прочтения. Авторы на удивление доходчиво сообщают необходимые
сведения из общей алгебры и теории чисел. Они объясняют, какие проблемы должны были разрешить математики, и показывают, как найденные ими решения переводятся на язык обобщенного
программирования и позволяют создать эффективный и элегантный код.
Читая эту книгу, вы освоите мыслительный процесс, необходимый для правильного программирования, и научитесь обобщать найденные для частной задачи алгоритмы с целью расширить
область их полезного применения без потери эффективности. Вы также постигнете, в чем состоит
ценность математики для программирования, —и это понимание пригодится вне зависимости от
того, на каком языке вы пишете и какую парадигму применяете.

Authorized translation from the English language edition, entitled FROM MATHEMATICS
TO GENERIC PROGRAMMING; ISBN
: by ALEXANDER STEPANOV and
DANIEL ROSE; published by Pearson Education, Inc., publishing as Addison-Wesley Professional.
Copyright© 2015.
All rights reserved. No part of this book may be reproduced or transmitted in any form or by any
means, electronic or mechanical, including photocopying, recording or by any information storage
retrieval system, w ithout permission from Pearson Education, Inc. RUSSIAN language edition
published by DMK PUBLISHERS. Copyright © 2015.
Все права защищены. Любая часть этой книги не может быть воспроизведена в какой
бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав.
Материал, изложенный в данной книге, многократно проверен. Но поскольку вероятность
технических ошибок все равно существует, издательство не может гарантировать абсолютную
точность и правильность приводимых сведений. В связи с этим издательство не несет ответственности за возможные ошибки, связанные с использованием книги.

Copyright © 2015 Pearson Education, Inc.
© Оформление, перевод, ДМК Пресс, 2015

Содержание
Благодарности....................................................

9

Об авторах...................................................................................................... 10
От авторов............... ............................................. ...................................... 11
Предисловие автора к русскому изданию........ ...................................... 12
13
Глава 1. О чем эта книга.................
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
40
3.6. Фатальный изъян в программе................................
3.7. Заключительные мысли.........................................................................................44
Глава 4. Алгоритм Евклида.......................................................................... 45
4.1. Афины и Александрия........................................................................................... 45
4.2. Алгоритм Евклида нахождения наибольшей общей меры............................... 47
4.3. Тысяча лет без математики................................................................................... 51
4.4. Странная история --">