Programming for Mathematicians

2000
ISBN: 978-3-540-66422-2
Verlag: Springer Berlin Heidelberg

Buch, Englisch, 432 Seiten, Paperback, Format (B × H): 155 mm x 235 mm, Gewicht: 1390 g

Reihe: Universitext

Aimed at teaching mathematics students how to program using their knowledge of mathematics, the entire books emphasis is on "how to think" when programming. Three methods for constructing an algorithm or a program are used: manipulation and enrichment of existing code; use of recurrent sequences; deferral of code writing, in order to deal with one difficulty at a time. Many theorems are mathematically proved and programmed, and the text concludes with an explanation of how a compiler works and how to compile "by hand" little programs. Intended for anyone who thinks mathematically and wants to program and play with mathematics.

Zielgruppe

Research

Autoren/Hrsg.

Seroul, Raymond

Weitere Mitwirkende

O'Shea, D.

Fachgebiete

• Mathematik | Informatik EDV | Informatik Programmierung | Softwareentwicklung Programmierung: Methoden und Allgemeines
• Mathematik | Informatik Mathematik Numerik und Wissenschaftliches Rechnen Angewandte Mathematik, Mathematische Modelle
• Mathematik | Informatik Mathematik Numerik und Wissenschaftliches Rechnen Computeranwendungen in der Mathematik
• Mathematik | Informatik Mathematik Numerik und Wissenschaftliches Rechnen Numerische Mathematik

Inhaltsverzeichnis

1. Programming Proverbs.- 1.1. Above all, no tricks!.- 1.2. Do not chewing gum while climbing stairs.- 1.3. Name that which you still don’t know.- 1.4. Tomorrow, things will be better; the day after, better still.- 1.5. Never execute an order before it is given.- 1.6. Document today to avoid tears tomorrow.- 1.7. Descartes’ Discourse on the Method.- 2. Review of Arithmetic.- 2.1. Euclidean Division.- 2.2. Numeration Systems.- 2.3. Prime Numbers.- 2.3.1. The number of primes smaller than a given real number.- 2.4. The Greatest Common Divisor.- 2.4.1. The Bezout Theorem.- 2.4.2. Gauss’s Lemma.- 2.5. Congruences.- 2.6. The Chinese Remainder Theorem.- 2.7. The Euler phi Function.- 2.8. The Theorems of Fermat and Euler.- 2.9. Wilson’s Theorem.- 2.10. Quadratic Residues.- 2.11. Prime Number and Sum of Two Squares.- 2.12. The Moebius Function.- 2.13. The Fibonacci Numbers.- 2.14. Reasoning by Induction.- 2.15. Solutions of the Exercises.- 3. An Algorithmic Description Language.- 3.1. Identifiers.- 3.2. Arithmetic Expressions.- 3.2.1. Numbers.- 3.2.2. Operations.- 3.2.3. Arrays.- 3.2.4. Function calls and parentheses.- 3.3. Boolean Expressions.- 3.4. Statements and their Syntax.- 3.4.1. Assignments.- 3.4.2. Conditionals.- 3.4.3. For loops.- 3.4.4. While loops.- 3.4.5. Repeat loops.- 3.4.6. Sequences of statements.- 3.4.7. Blocks of statements.- 3.4.8. Complex statements.- 3.4.9. Layout on page and control of syntax.- 3.4.10. To what does the else belong?.- 3.4.11. Semicolons: some classical errors.- 3.5. The Semantics of Statements.- 3.5.1. Assignments.- 3.5.2. Conditionals.- 3.5.3. First translations.- 3.5.4. The boustrophedon order.- 3.5.5. The for loop.- 3.5.6. The while loop.- 3.5.7. The repeat loop.- 3.5.8. Embedded loops.- 3.6. Which Loop to Choose?.- 3.6.1. Choosing a for loop.- 3.6.2. Choosing a while loop.- 3.6.3. Choosing a repeat loop.- 3.6.4. Inspecting entrances and exits.- 3.6.5. Loops with accidents.- 3.6.6. Gaussian elimination.- 3.6.7. How to grab data.- 4. How to Create an Algorithm.- 4.1. The Trace of an Algorithm.- 4.2. First Method: Recycling Known Code.- 4.2.1. Postage stamps.- 4.2.2. How to determine whether a postage is realizable.- 4.2.3. Calculating the threshold value.- 4.3. Second Method: Using Sequences.- 4.3.1. Creation of a simple algorithm.- 4.3.2. The exponential series.- 4.3.3. Decomposition into prime factors.- 4.3.4. The least divisor function.- 4.3.5. Cardinality of an intersection.- 4.3.6. The CORDIC Algorithm.- 4.4. Third Method: Defered Writing.- 4.4.1. Calculating two bizarre functions.- 4.4.2. Storage of the first N prime numbers.- 4.4.3. Last recommendations.- 4.5. How to Prove an Algorithm.- 4.5.1. Crashes.- 4.5.2. Infinite loops.- 4.5.3. Calculating the GCD of two numbers.- 4.5.4. A more complicated example.- 4.5.5. The validity of a result furnished by a loop.- 4.6. Solutions of the Exercises.- 5. Algorithms and Classical Constructions.- 5.1. Exchanging the Contents of Two Variables.- 5.2. Diverse Sums.- 5.2.1. A very important convention.- 5.2.2. Double sums.- 5.2.3. Sums with exceptions.- 5.3. Searching for a Maximum.- 5.4. Solving a Triangular Cramer System.- 5.5. Rapid Calculation of Powers.- 5.6. Calculation of the Fibonacci Numbers.- 5.7. The Notion of a Stack.- 5.8. Linear Traversal of a Finite Set.- 5.9. The Lexicographic Order.- 5.9.1. Words of fixed length.- 5.9.2. Words of variable length.- 5.10. Solutions to the Exercises.- 6. The Pascal Language.- 6.1. Storage of the Usual Objects.- 6.2. Integer Arithmetic in Pascal.- 6.2.1. Storage of integers in Pascal.- 6.3. Arrays in Pascal.- 6.4. Declaration of an Array.- 6.5. Product Sets and Types.- 6.5.1. Product of equal sets.- 6.5.2. Product of unequal sets.- 6.5.3. Composite types.- 6.6. The Role of Constants.- 6.7. Litter.- 6.8. Procedures.- 6.8.1. The declarative part of a procedure.- 6.8.2. Procedure calls.- 6.8.3. Communication of a procedure with the exterior.- 6.9. Visibility of the Variables in a Procedure.- 6.10. Context Effects.- 6.10.1. Functions.- 6.10.2. Procedure or function?.- 6.11. Procedures: What the Program Seems To Do.- 6.11.1. Using the model.- 6.12. Solutions of the Exercises.- 7. How to Write a Program.- 7.1. Inverse of an Order 4 Matrix.- 7.1.1. The problem.- 7.1.2. Theoretical study.- 7.1.3. Writing the program.- 7.1.4. The function det.- 7.1.5. How to type a program.- 7.2. Characteristic Polynomial of a Matrix.- 7.2.1. The program Leverrier.- 7.3. How to Write a Program.- 7.4. A Poorly Written Procedure.- 8. The Integers.- 8.1. The Euclidean Algorithm.- 8.1.1. Complexity of the Euclidean algorithm.- 8.2. The Blankinship Algorithm.- 8.3. Perfect Numbers.- 8.4. The Lowest Divisor Function.- 8.5. The Moebius Function.- 8.6. The Sieve of Eratosthenes.- 8.6.1. Formulation of the algorithm.- 8.6.2. Transforming the algorithm to a program.- 8.7. The Function pi(x).- 8.7.1. Legendre’s formula.- 8.7.2. Implementation of Legendre’s formula.- 8.7.3. Meissel’s formula.- 8.8. Egyptian Fractions.- 8.8.1. The program.- 8.8.2. Numerical results.- 8.9. Operations on Large Integers.- 8.9.1. Addition.- 8.9.2. Subtraction.- 8.9.3. Multiplication.- 8.9.4. Declarations.- 8.9.5. The program.- 8.10. Division in Base b.- 8.10.1. Description of the division algorithm.- 8.10.2. Justification of the division algorithm.- 8.10.3. Effective estimates of integer parts.- 8.10.4. A good division algorithm.- 8.11. Sums of Fibonacci Numbers.- 8.12. Odd Primes as a Sum of Two Squares.- 8.13. Sums of Four Squares.- 8.14. Highly Composite Numbers.- 8.14.1. Several properties of highly composite numbers.- 8.14.2. Practical investigation of highly composite integers.- 8.15. Permutations: Johnson’s’ Algorithm.- 8.15.1. The program Johnson.- 8.16. The Count is Good.- 8.16.1. Syntactic trees.- 9. The Complex Numbers.- 9.1. The Gaussian Integers.- 9.1.1. Euclidean division.- 9.1.2. Irreducibles.- 9.1.3. The program.- 9.2. Bases of Numeration in the Gaussian Integers.- 9.2.1. The modulo beta map.- 9.2.2. How to find an exact system of representatives.- 9.2.3. Numeration system in base beta.- 9.2.4. An algorithm for expression in base beta.- 9.3. Machin Formulas.- 9.3.1. Uniqueness of a Machin formula.- 9.3.2. Proof of Proposition 9.3.1.- 9.3.3. The Todd condition is necessary.- 9.3.4. The Todd condition is sufficient.- 9.3.5. Kern’s algorithm.- 9.3.6. How to get rid of the Arctangent function.- 9.3.7. Examples.- 10. Polynomials.- 10.1. Definitions.- 10.2. Degree of a Polynomial.- 10.3. How to Store a Polynomial.- 10.4. The Conventions we Adopt.- 10.5. Euclidean Division.- 10.6. Evaluation of Polynomials: Horner’s Method.- 10.7. Translation and Composition.- 10.7.1. Change of origin.- 10.7.2. Composing polynomials.- 10.8. Cyclotomic Polynomials.- 10.8.1. First formula.- 10.8.2. Second formula.- 10.9. Lagrange Interpolation.- 10.10. Basis Change.- 10.11. Differentiation and Discrete Taylor Formulas.- 10.11.1. Discrete differentiation.- 10.12. Newton-Girard Formulas.- 10.13. Stable Polynomials.- 10.14. Factoring a Polynomial with Integral Coefficients.- 10.14.1. Why integer (instead of rational) coefficients?.- 10.14.2. Kronecker’s factorization algorithm.- 10.14.3. Use of stable polynomials.- 10.14.4. The program.- 10.14.5. Last remarks.- 11. Matrices.- 11.1. Z-Linear Algebra.- 11.1.1. The bordered matrix trick.- 11.1.2. Generators of a subgroup.- 11.1.3. The Blankinship algorithm.- 11.1.4. Hermite matrices.- 11.1.5. The program Hermite.- 11.1.6. The incomplete basis theorem.- 11.1.7. Finding a basis of a subgroup.- 11.2. Linear Systems with Integral Coefficients.- 11.2.1. Theoretical results.- 11.2.2. The case of a matrix in column echelon form.- 11.2.3. General case.- 11.2.4. Case of a single equation.- 11.3. Exponential of a Matrix: Putzer’s Algorithm.- 11.4. Jordan Reduction.- 11.4.1. Review.- 11.4.2. Reduction of a nilpotent endomorphism.- 11.4.3. The Pitttelkow-Runckel algorithm.- 11.4.4. Justification of the Pittelkow-Runckel algorithm.- 11.4.5. A complete example.- 11.4.6. Programming.- 12. Recursion.- 12.1. Presentation.- 12.1.1. Two simple examples.- 12.1.2. Mutual recursion.- 12.1.3. Arborescence of recursive calls.- 12.1.4. Induction and recursion.- 12.2. The Ackermann function.- 12.3. The Towers of Hanoi.- 12.4. Baguenaudier.- 12.5. The Hofstadter Function.- 12.6. How to Write a Recursive Code.- 12.6.1. Sorting by dichotomy.- 13. Elements of compiler theory.- 13.1. Pseudocode.- 13.1.1. Description of pseudocode.- 13.1.2. How to compile a pseudocode program by hand.- 13.1.3. Translation of a conditional.- 13.1.4. Translation of a loop.- 13.1.5. Function calls.- 13.1.6. A very efficient technique.- 13.1.7. Procedure calls.- 13.1.8. The factorial function.- 13.1.9. The Fibonacci numbers.- 13.1.10. The Hofstadter function.- 13.1.11. The Towers of Hanoi.- 13.2. A Pseudocode Interpreter.- 13.3. How to Analyze an Arithmetic Expression.- 13.3.1. Arithmetic expressions.- 13.3.2. How to recognize an arithmetic expression.- 13.4. How to Evaluate an Arithmetic Expression.- 13.5. How to Compile an Arithmetic Expression.- 13.5.1. Polish notation.- 13.5.2. A Compiler for arithmetic expressions.- References.