Atjaunināt sīkdatņu piekrišanu

From Mathematics to Generic Programming [Mīkstie vāki]

4.14/5 (261 ratings by Goodreads)
,
  • Formāts: Paperback / softback, 320 pages, height x width x depth: 228x156x17 mm, weight: 436 g
  • Izdošanas datums: 27-Nov-2014
  • Izdevniecība: Addison-Wesley Educational Publishers Inc
  • ISBN-10: 0321942043
  • ISBN-13: 9780321942043
Citas grāmatas par šo tēmu:
  • Mīkstie vāki
  • Cena: 41,05 €
  • Grāmatu piegādes laiks ir 3-4 nedēļas, ja grāmata ir uz vietas izdevniecības noliktavā. Ja izdevējam nepieciešams publicēt jaunu tirāžu, grāmatas piegāde var aizkavēties.
  • Daudzums:
  • Ielikt grozā
  • Piegādes laiks - 4-6 nedēļas
  • Pievienot vēlmju sarakstam
From Mathematics to Generic ProgrammingPalielināt
  • Formāts: Paperback / softback, 320 pages, height x width x depth: 228x156x17 mm, weight: 436 g
  • Izdošanas datums: 27-Nov-2014
  • Izdevniecība: Addison-Wesley Educational Publishers Inc
  • ISBN-10: 0321942043
  • ISBN-13: 9780321942043
Citas grāmatas par šo tēmu:
Permanent link: https://www.kriso.lv/db/9780321942043.html
Keywords:

In this substantive yet accessible book, pioneering software designer Alexander Stepanov and his colleague Daniel Rose illuminate the principles of generic programming and the mathematical concept of abstraction on which it is based, helping you write code that is both simpler and more powerful.

If you’re a reasonably proficient programmer who can think logically, you have all the background you’ll need. Stepanov and Rose introduce the relevant abstract algebra and number theory with exceptional clarity. They carefully explain the problems mathematicians first needed to solve, and then show how these mathematical solutions translate to generic programming and the creation of more effective and elegant code. To demonstrate the crucial role these mathematical principles play in many modern applications, the authors show how to use these results and generalized algorithms to implement a real-world public-key cryptosystem.

As you read this book, you’ll master the thought processes necessary for effective programming and learn how to generalize narrowly conceived algorithms to widen their usefulness without losing efficiency. You’ll also gain deep insight into the value of mathematics to programming–insight that will prove invaluable no matter what programming languages and paradigms you use.

You will learn about

  • How to generalize a four thousand-year-old algorithm, demonstrating indispensable lessons about clarity and efficiency
  • Ancient paradoxes, beautiful theorems, and the productive tension between continuous and discrete
  • A simple algorithm for finding greatest common divisor (GCD) and modern abstractions that build on it
  • Powerful mathematical approaches to abstraction
  • How abstract algebra provides the idea at the heart of generic programming
  • Axioms, proofs, theories, and models: using mathematical techniques to organize knowledge about your algorithms and data structures
  • Surprising subtleties of simple programming tasks and what you can learn from them
  • How practical implementations can exploit theoretical knowledge

Alexander A. Stepanov has been programming since 1972–first in the Soviet Union and, since emigrating in 1977, in the United States. He has programmed operating systems, programming tools, compilers, and libraries. His work on the foundations of programming has been supported by GE, Polytechnic University, Bell Labs, HP, SGI, Adobe, and, since 2009, A9.com, Amazon’s search subsidiary. In 1995, he received theDr. Dobb’s Journal Excellence in Programming Award for the design of the C++ Standard Template Library.

Daniel E. Rose is a research scientist who has held management positions at Apple, AltaVista, Xigo, Yahoo, and A9.com. His research focuses on all aspects of search, ranging from low-level algorithms for index compression to human—computer interaction. Rose led the Apple team that created desktop search for the Mac. He holds a Ph.D. in cognitive science and computer science from the University of California, San Diego, and a B.A. in philosophy from Harvard.

Acknowledgments ix
About the Authors xi
Authors' Note xiii
1 What This Book Is About 1(6)
1.1 Programming and Mathematics
2(1)
1.2 A Historical Perspective
2(1)
1.3 Prerequisites
3(1)
1.4 Roadmap
4(3)
2 The First Algorithm 7(10)
2.1 Egyptian Multiplication
8(3)
2.2 Improving the Algorithm
11(4)
2.3 Thoughts on the
Chapter
15(2)
3 Ancient Greek Number Theory 17(24)
3.1 Geometric Properties of Integers
17(3)
3.2 Sifting Primes
20(3)
3.3 Implementing and Optimizing the Code
23(5)
3.4 Perfect Numbers
28(4)
3.5 The Pythagorean Program
32(2)
3.6 A Fatal Flaw in the Program
34(4)
3.7 Thoughts on the
Chapter
38(3)
4 Euclid's Algorithm 41(22)
4.1 Athens and Alexandria
41(4)
4.2 Euclid's Greatest Common Measure Algorithm
45(5)
4.3 A Millennium without Mathematics
50(1)
4.4 The Strange History of Zero
51(2)
4.5 Remainder and Quotient Algorithms
53(4)
4.6 Sharing the Code
57(2)
4.7 Validating the Algorithm
59(2)
4.8 Thoughts on the
Chapter
61(2)
5 The Emergence of Modern Number Theory 63(22)
5.1 Mersenne Primes and Fermat Primes
63(6)
5.2 Fermat's Little Theorem
69(3)
5.3 Cancellation
72(5)
5.4 Proving Fermat's Little Theorem
77(2)
5.5 Euler's Theorem
79(4)
5.6 Applying Modular Arithmetic
83(1)
5.7 Thoughts on the
Chapter
84(1)
6 Abstraction in Mathematics 85(26)
6.1 Groups
85(4)
6.2 Monoids and Semigroups
89(3)
6.3 Some Theorems about Groups
92(3)
6.4 Subgroups and Cyclic Groups
95(2)
6.5 Lagrange's Theorem
97(5)
6.6 Theories and Models
102(2)
6.7 Examples of Categorical and Non-categorical Theories
104(3)
6.8 Thoughts on the
Chapter
107(4)
7 Deriving a Generic Algorithm 111(18)
7.1 Untangling Algorithm Requirements
111(2)
7.2 Requirements on A
113(3)
7.3 Requirements on N
116(2)
7.4 New Requirements
118(1)
7.5 Turning Multiply into Power
119(2)
7.6 Generalizing the Operation
121(3)
7.7 Computing Fibonacci Numbers
124(3)
7.8 Thoughts on the
Chapter
127(2)
8 More Algebraic Structures 129(26)
8.1 Stevin, Polynomials, and GCD
129(6)
8.2 Gottingen and German Mathematics
135(5)
8.3 Noether and the Birth of Abstract Algebra
140(2)
8.4 Rings
142(3)
8.5 Matrix Multiplication and Semirings
145(2)
8.6 Application: Social Networks and Shortest Paths
147(3)
8.7 Euclidean Domains
150(1)
8.8 Fields and Other Algebraic Structures
151(1)
8.9 Thoughts on the
Chapter
152(3)
9 Organizing Mathematical Knowledge 155(22)
9.1 Proofs
155(4)
9.2 The First Theorem
159(2)
9.3 Euclid and the Axiomatic Method
161(3)
9.4 Alternatives to Euclidean Geometry
164(3)
9.5 Hilbert's Formalist Approach
167(2)
9.6 Peano and His Axioms
169(4)
9.7 Building Arithmetic
173(3)
9.8 Thoughts on the
Chapter
176(1)
10 Fundamental Programming Concepts 177(20)
10.1 Aristotle and Abstraction
177(3)
10.2 Values and Types
180(1)
10.3 Concepts
181(3)
10.4 Iterators
184(1)
10.5 Iterator Categories, Operations, and Traits
185(3)
10.6 Ranges
188(2)
10.7 Linear Search
190(1)
10.8 Binary Search
191(5)
10.9 Thoughts on the
Chapter
196(1)
11 Permutation Algorithms 197(22)
11.1 Permutations and Transpositions
197(4)
11.2 Swapping Ranges
201(3)
11.3 Rotation
204(3)
11.4 Using Cycles
207(5)
11.5 Reverse
212(3)
11.6 Space Complexity
215(1)
11.7 Memory-Adaptive Algorithms
216(1)
11.8 Thoughts on the
Chapter
217(2)
12 Extensions of GCD 219(18)
12.1 Hardware Constraints and a More Efficient Algorithm
219(3)
12.2 Generalizing Stein's Algorithm
222(3)
12.3 Bezout's Identity
225(4)
12.4 Extended GCD
229(5)
12.5 Applications of GCD
234(1)
12.6 Thoughts on the
Chapter
234(3)
13 A Real-World Application 237(12)
13.1 Cryptology
237(3)
13.2 Primality Testing
240(3)
13.3 The Miller-Rabin Test
243(2)
13.4 The RSA Algorithm: How and Why It Works
245(3)
13.5 Thoughts on the
Chapter
248(1)
14 Conclusions 249(2)
Further Reading 251(6)
A Notation 257(4)
B Common Proof Techniques 261(4)
B.1 Proof by Contradiction
261(1)
B.2 Proof by Induction
262(1)
B.3 The Pigeonhole Principle
263(2)
C C++ for Non-C++ Programmers 265(10)
C.1 Template Functions
265(1)
C.2 Concepts
266(1)
C.3 Declaration Syntax and Typed Constants
267(1)
C.4 Function Objects
268(1)
C.5 Preconditions, Postconditions, and Assertions
269(1)
C.6 STL Algorithms and Data Structures
269(1)
C.7 Iterators and Ranges
270(2)
C.8 Type Aliases and Type Functions with using in C++11
272(1)
C.9 Initializer Lists in C++11
272(1)
C.10 Lambda Functions in C++11
272(1)
C.11 A Note about inline
273(2)
Bibliography 275(6)
Index 281
Alexander A. Stepanov studied mathematics at Moscow State University from 1967 to 1972. He has been programming since 1972: first in the Soviet Union and, after emigrating in 1977, in the United States. He has programmed operating systems, programming tools, compilers, and libraries. His work on foundations of programming has been supported by GE, Polytechnic University, Bell Labs, HP, SGI, Adobe, and, since 2009, A9.com, Amazons search technology subsidiary. In 1995 he received the Dr. Dobbs Journal Excellence in Programming Award for the design of the C++ Standard Template Library.

Daniel E. Rose is a research scientist who has held management positions at Apple, AltaVista, Xigo, Yahoo, and A9.com. His research focuses on all aspects of search technology, ranging from low-level algorithms for index compression to humancomputer interaction issues in web search. Rose led the team at Apple that created desktop search for the Macintosh. He holds a Ph.D. in cognitive science and computer science from University of California, San Diego, and a B.A. in philosophy from Harvard University.