logo资料库

From Mathematics to Generic Programming.pdf

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：2.42M 资料格式：pdf 举报 版权申诉
第1页 / 共311页
第2页 / 共311页
第3页 / 共311页
第4页 / 共311页
第5页 / 共311页
第6页 / 共311页
第7页 / 共311页
第8页 / 共311页
资料共311页，剩余部分请下载后查看
    Cover
    Title
    Copyright
    Contents
    Acknowledgments
    About the Authors
    Authors’ Note
    1. What This Book Is About
    1.1 Programming and Mathematics
    1.2 A Historical Perspective
    1.3 Prerequisites
    1.4 Roadmap
    2. The First Algorithm
    2.1 Egyptian Multiplication
    2.2 Improving the Algorithm
    2.3 Thoughts on the Chapter
    3. Ancient Greek Number Theory
    3.1 Geometric Properties of Integers
    3.2 Sifting Primes
    3.3 Implementing and Optimizing the Code
    3.4 Perfect Numbers
    3.5 The Pythagorean Program
    3.6 A Fatal Flaw in the Program
    3.7 Thoughts on the Chapter
    4. Euclid’s Algorithm
    4.1 Athens and Alexandria
    4.2 Euclid’s Greatest Common Measure Algorithm
    4.3 A Millennium without Mathematics
    4.4 The Strange History of Zero
    4.5 Remainder and Quotient Algorithms
    4.6 Sharing the Code
    4.7 Validating the Algorithm
    4.8 Thoughts on the Chapter
    5. The Emergence of Modern Number Theory
    5.1 Mersenne Primes and Fermat Primes
    5.2 Fermat’s Little Theorem
    5.3 Cancellation
    5.4 Proving Fermat’s Little Theorem
    5.5 Euler’s Theorem
    5.6 Applying Modular Arithmetic
    5.7 Thoughts on the Chapter
    6. Abstraction in Mathematics
    6.1 Groups
    6.2 Monoids and Semigroups
    6.3 Some Theorems about Groups
    6.4 Subgroups and Cyclic Groups
    6.5 Lagrange’s Theorem
    6.6 Theories and Models
    6.7 Examples of Categorical and Non-categorical Theories
    6.8 Thoughts on the Chapter
    7. Deriving a Generic Algorithm
    7.1 Untangling Algorithm Requirements
    7.2 Requirements on A
    7.3 Requirements on N
    7.4 New Requirements
    7.5 Turning Multiply into Power
    7.6 Generalizing the Operation
    7.7 Computing Fibonacci Numbers
    7.8 Thoughts on the Chapter
    8. More Algebraic Structures
    8.1 Stevin, Polynomials, and GCD
    8.2 Göttingen and German Mathematics
    8.3 Noether and the Birth of Abstract Algebra
    8.4 Rings
    8.5 Matrix Multiplication and Semirings
    8.6 Application: Social Networks and Shortest Paths
    8.7 Euclidean Domains
    8.8 Fields and Other Algebraic Structures
    8.9 Thoughts on the Chapter
    9. Organizing Mathematical Knowledge
    9.1 Proofs
    9.2 The First Theorem
    9.3 Euclid and the Axiomatic Method
    9.4 Alternatives to Euclidean Geometry
    9.5 Hilbert’s Formalist Approach
    9.6 Peano and His Axioms
    9.7 Building Arithmetic
    9.8 Thoughts on the Chapter
    10. Fundamental Programming Concepts
    10.1 Aristotle and Abstraction
    10.2 Values and Types
    10.3 Concepts
    10.4 Iterators
    10.5 Iterator Categories, Operations,and Traits
    10.6 Ranges
    10.7 Linear Search
    10.8 Binary Search
    10.9 Thoughts on the Chapter
    11.1 Permutations and Transpositions
    11.2 Swapping Ranges
    11.3 Rotation
    11.4 Using Cycles
    11.5 Reverse
    11.6 Space Complexity
    11.7 Memory-Adaptive Algorithms
    11.8 Thoughts on the Chapter
    12. Extensions of GCD
    12.1 Hardware Constraints anda More Efficient Algorithm
    12.2 Generalizing Stein’s Algorithm
    12.3 Bézout’s Identity
    12.4 Extended GCD
    12.5 Applications of GCD
    12.6 Thoughts on the Chapter
    13.1 Cryptology
    13.2 Primality Testing
    13.3 The Miller-Rabin Test
    13.4 The RSA Algorithm: How and Why It Works
    13.5 Thoughts on the Chapter
    14. Conclusions
    Further Reading
    A. Notation
    B. Common Proof Techniques
    B.1 Proof by Contradiction
    B.2 Proof by Induction
    B.3 The Pigeonhole Principle
    C. C++ for Non-C++ Programmers
    C.1 Template Functions
    C.2 Concepts
    C.3 Declaration Syntaxand Typed Constants
    C.4 Function Objects
    C.5 Preconditions, Postconditions, and Assertions
    C.6 STL Algorithms and Data Structures
    C.7 Iterators and Ranges
    C.8 Type Aliases and Type Functions with using in C++11
    C.9 Initializer Lists in C++11
    C.10 Lambda Functions in C++11
    C.11 A Note about inline
    Bibliography
    A
    B
    C
    D
    E
    F
    G
    H
    I
    K
    L
    M
    P
    R
    S
    V
    W
    Index
    #
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    M
    N
    O
    P
    Q
    R
    S
    T
    U
    V
    W
    Z
    From Mathematics to Generic Programming
    This page intentionally left blank
    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
    Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in this book, and the publisher was aware of a trade- mark claim, the designations have been printed with initial capital letters or in all capitals. e authors and publisher have taken care in the preparation of this book, but make no expressed or implied warranty of any kind and assume no responsibility for errors or omissions. No liability is assumed for incidental or consequential damages in connection with or arising out of the use of the information or programs contained herein. For information about buying this title in bulk quantities, or for special sales opportunities (which may include electronic versions; custom cover designs; and content particular to your business, train- ing goals, marketing focus, or branding interests), please contact our corporate sales department at corpsales@pearsoned.com or (800) 382-3419. For government sales inquiries, please contact governmentsales@pearsoned.com. For questions about sales outside the United States, please contact international@pearsoned.com. Visit us on the Web: informit.com/aw Library of Congress Cataloging-in-Publication Data Stepanov, Alexander A. From mathematics to generic programming / Alexander A. Stepanov, Daniel E. Rose. pages cm Includes bibliographical references and index. ISBN 978-0-321-94204-3 (pbk. : alk. paper) 1. Generic programming (Computer science)—Mathematics. 2. Computer algorithms. I. Rose, Daniel E. II. Title. QA76.6245.S74 2015 005.1'1—dc23 2014034539 Copyright © 2015 Pearson Education, Inc. All rights reserved. Printed in the United States of America. is publication is protected by copy- right, and permission must be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or likewise. To obtain permission to use material from this work, please submit a written request to Pearson Education, Inc., Permissions Department, One Lake Street, Up- per Saddle River, New Jersey 07458, or you may fax your request to (201) 236-3290. Photo credits are listed on page 293. ISBN-13: 978-0-321-94204-3 ISBN-10: 0-321-94204-3 Text printed in the United States on recycled paper at RR Donnelley in Crawfordsville, Indiana. ird printing, August 2015
    Contents Acknowledgments About the Authors Authors’ Note xiii ix xi 1 What This Book Is About 1 2 3 4 1.1 Programming and Mathematics 1.2 A Historical Perspective 2 1.3 Prerequisites 1.4 Roadmap 3 4 2 The First Algorithm 7 2.1 Egyptian Multiplication 2.2 Improving the Algorithm 2.3 Thoughts on the Chapter 8 11 15 20 Ancient Greek Number Theory 17 3.1 Geometric Properties of Integers 3.2 Sifting Primes 3.3 Implementing and Optimizing the Code 3.4 Perfect Numbers 3.5 The Pythagorean Program 3.6 A Fatal Flaw in the Program 3.7 Thoughts on the Chapter 28 32 34 38 17 23 41 Euclid’s Algorithm 41 4.1 Athens and Alexandria 4.2 Euclid’s Greatest Common Measure Algorithm 4.3 A Millennium without Mathematics 4.4 The Strange History of Zero 51 4.5 Remainder and Quotient Algorithms 4.6 Sharing the Code 57 4.7 Validating the Algorithm 4.8 Thoughts on the Chapter 59 61 50 53 45 v
    vi 5 6 7 Contents 63 63 77 The Emergence of Modern Number Theory 5.1 Mersenne Primes and Fermat Primes 5.2 Fermat’s Little Theorem 5.3 Cancellation 5.4 Proving Fermat’s Little Theorem 5.5 Euler’s Theorem 5.6 Applying Modular Arithmetic 5.7 Thoughts on the Chapter 69 72 79 83 84 89 85 85 Abstraction in Mathematics 6.1 Groups 6.2 Monoids and Semigroups 6.3 Some Theorems about Groups 6.4 Subgroups and Cyclic Groups 97 6.5 Lagrange’s Theorem 6.6 Theories and Models 102 6.7 Examples of Categorical and Non-categorical Theories 6.8 Thoughts on the Chapter 92 95 107 104 111 111 Deriving a Generic Algorithm 7.1 Untangling Algorithm Requirements 7.2 Requirements on A 7.3 Requirements on N 7.4 New Requirements 7.5 Turning Multiply into Power 7.6 Generalizing the Operation 7.7 Computing Fibonacci Numbers 7.8 Thoughts on the Chapter 113 116 118 119 121 127 124 8 More Algebraic Structures 135 129 129 8.1 Stevin, Polynomials, and GCD 8.2 Göttingen and German Mathematics 8.3 Noether and the Birth of Abstract Algebra 8.4 Rings 8.5 Matrix Multiplication and Semirings 8.6 Application: Social Networks and Shortest Paths 8.7 Euclidean Domains 8.8 Fields and Other Algebraic Structures 8.9 Thoughts on the Chapter 142 145 150 151 152 140 147 9 Organizing Mathematical Knowledge 9.1 Proofs 9.2 The First Theorem 155 159 155
    Contents vii 9.3 Euclid and the Axiomatic Method 9.4 Alternatives to Euclidean Geometry 9.5 Hilbert’s Formalist Approach 167 9.6 Peano and His Axioms 9.7 Building Arithmetic 9.8 Thoughts on the Chapter 169 173 176 161 164 10 Fundamental Programming Concepts 177 177 10.1 Aristotle and Abstraction 10.2 Values and Types 180 181 10.3 Concepts 10.4 Iterators 184 10.5 Iterator Categories, Operations, and Traits 10.6 Ranges 188 10.7 Linear Search 10.8 Binary Search 10.9 Thoughts on the Chapter 190 191 196 185 11 Permutation Algorithms 197 201 11.1 Permutations and Transpositions 11.2 Swapping Ranges 11.3 Rotation 204 11.4 Using Cycles 11.5 Reverse 11.6 Space Complexity 11.7 Memory-Adaptive Algorithms 11.8 Thoughts on the Chapter 212 215 207 217 197 216 12 Extensions of GCD 219 12.1 Hardware Constraints and a More Efficient Algorithm 12.2 Generalizing Stein’s Algorithm 12.3 Bézout’s Identity 12.4 Extended GCD 12.5 Applications of GCD 12.6 Thoughts on the Chapter 222 225 229 234 234 219 13 A Real-World Application 237 237 13.1 Cryptology 13.2 Primality Testing 13.3 The Miller-Rabin Test 13.4 The RSA Algorithm: How and Why It Works 13.5 Thoughts on the Chapter 240 243 248 245
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料