Special Topics in Computer Science I (CS493) in Summer 2018: Algorithmic Foundation of Numerics

This course offers a hands-on introduction to the rigorous foundations of computing with continuous data (real numbers, sequences, functions): from in/computability via complexity to programming practice.

We emphasize the difference between a recipe/heuristic and an algorithm. You will be reminded of aspects from the classical (i.e. discrete) Theory of Computation, from computability to complexity. We then apply it to numerical problems, yielding a rigorous perspective on the (i) computability, (ii) complexity, and (iii) semantics of: real tests, root finding, differentiation, maximization, integration, ODE and PDE solving. The course culminates in a programming assignment in iRRAM: a C++ library providing via object-oriented overloading an abstract data type REAL. In addition, each week will conclude with a theoretical homework assignment.

Lecturer: Martin Ziegler

Language: English only

Prerequisites: Introduction to Computer Science, Discrete Mathematics, Calculus I, C++, root on some Linux computer

Teaching Assistant: Donghyun Lim

Test questions for self-assessment of mathematical background:

1. What does it mean for a sequence to converge?
2. What does it mean for a function to be continuous?
3. What does it mean for a set to be compact?
4. Why is every continuous function on a compact domain uniformly continuous?

Grading: 10% attendance, 50% homework/programming assignments, 40% final exam

There will be 3 small homework/programming assignments throughout July and a final exam on July 25+26 (two parts).

• Tue, July 3, 12:10-13:00
• Wed, July 4, 12:10-13:00
• Thu, July 5, 12:10-13:00
• Tue, July 10, 12:10-13:00
• Wed, July 11, 12:10-13:00
• Thu, July 12, 12:10-13:00
• Fri, July 13, 9:00-12:00
• Tue, July 17, 12:10-13:00
• Wed, July 18, 12:10-13:00
• Thu, July 19, 12:10-13:00
• Fri, July 20, 9:00-12:00
• Tue, July 24, 12:10-13:00
• Wed, July 25, 12:10-13:00
• Thu, July 26, 12:10-13:00

in E3-1 #3444

1. Introduction and Motivation (ppt)
2. Discrete Computation (ppt):
   • Halting Problem
   • Un/Semi/Decidability/Enumerability
   • WHILE+ Programs
   • Asymptotic Runtime
   • Complexity classes P, NP, EXP
   • (Polynomial-time) Reduction
3. Computing over the Reals (ppt)
   • Computable Real numbers: non/equivalent notions
   • Equality, real sequences and limits
   • Computing real functions, Effective Weierstrass Theorem
   • Computational cost, compactness, and continuity
   • Uncomputable derivative
4. Exact Real Computation (ppt)
   • Non-extensionality, discrete enrichment
   • Semantics of tests and choose()
   • iRRAM library
   • Example Algorithms
5. Real Complexity Theory (ppt)
   • Polynomial-time reals
   • Polynomial-time functions
   • Maximizing smooth functions and P/NP
   • Riemann Integration and #P, ODEs and PSPACE

• Mark Braverman, Stephen Cook: Computing over the Reals: Foundations for Scientific Computing, Notices of the AMS (2006).
• A. Kawamura, M. Ziegler: “Invitation to Real Complexity Theory: Algorithmic Foundations to Reliable Numerics with Bit-Costs”, 18th Korea-Japan Joint Workshop on Algorithms and Computation (2015).
• Norbert Müller: The iRRAM: Exact Arithmetic in C++ (2000).
• Norbert Müller: iRRAM C++ Library.

• Ker-I Ko: Complexity Theory of Real Functions, Birkhäuser (1991).
• Klaus Weihrauch: Computable Analysis: An Introduction, Springer (2000).
• Akitoshi Kawamura, Stephen Cook: Complexity Theory for Operators in Analysis, ACM Transactions on Computation Theory 4 (2012).
• Akitoshi Kawamura, Hiroyuki Ota, Carsten Rösnick, Martin Ziegler: Computational Complexity of Smooth Differential Equations, Logical Methods in Computer Science (2014).
• Akitoshi Kawamura, Norbert Müller, Carsten Rösnick, Martin Ziegler: Computational Benefit of Smoothness: Parameterized Bit-Complexity of Numerical Operators on Analytic Functions and Gevrey's Hierarchy, pp.689-714 in the Journal of Complexity vol.31:5 (2015).
• Akitoshi Kawamura, Florian Steinberg, Martin Ziegler: On the Computational Complexity of the Dirichlet Problem for Poisson's Equation, Mathematical Structures in Computer Science (2017).

• KLMS
• Homework #1 consists of four problems to be solved and submitted in English by midnight of July 9 (Monday) via email.
• Homework #2 consists of one large problem to be solved and submitted in English on paper in the lecture on July 17 (Tuesday)
• Homework #3 consists of two problems. Problem 6 is to be solved and submitted in English on paper in the lecture on July 24 (Tuesday). Problem 7 is to be solved and submitted in English via email before the lecture on July 24 (Tuesday).
• Written Exam on July 25 with 30% bonus points