Special Topics in Computer Science I (CS493) in Summer 2018: Algorithmic Foundation of Numerics
This course offers a handson introduction to the rigorous foundations of computing with continuous data (real numbers, sequences, functions): from in/computability via complexity to programming practice.
Purpose and Goals
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 objectoriented overloading an abstract data type REAL. In addition, each week will conclude with a theoretical homework assignment.
Administrative
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 selfassessment of mathematical background:
 What does it mean for a sequence to converge?
 What does it mean for a function to be continuous?
 What does it mean for a set to be compact?
 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).
Schedule
 Tue, July 3, 12:1013:00
 Wed, July 4, 12:1013:00
 Thu, July 5, 12:1013:00
 Tue, July 10, 12:1013:00
 Wed, July 11, 12:1013:00
 Thu, July 12, 12:1013:00
 Fri, July 13, 9:0012:00
 Tue, July 17, 12:1013:00
 Wed, July 18, 12:1013:00
 Thu, July 19, 12:1013:00
 Fri, July 20, 9:0012:00
 Tue, July 24, 12:1013:00
 Wed, July 25, 12:1013:00
 Thu, July 26, 12:1013:00
in E31 #3444
Synopsis

 Halting Problem
 Un/Semi/Decidability/Enumerability
 WHILE+ Programs
 Asymptotic Runtime
 Complexity classes P, NP, EXP
 (Polynomialtime) Reduction

 Computable Real numbers: non/equivalent notions
 Equality, real sequences and limits
 Computing real functions, Effective Weierstrass Theorem
 Computational cost, compactness, and continuity
 Uncomputable derivative

 Nonextensionality, discrete enrichment
 Semantics of tests and choose()
 iRRAM library
 Example Algorithms

 Polynomialtime reals
 Polynomialtime functions
 Maximizing smooth functions and P/NP
 Riemann Integration and #P, ODEs and PSPACE
Reading List
 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 BitCosts”, 18th KoreaJapan Joint Workshop on Algorithms and Computation (2015).
 Norbert Müller: The iRRAM: Exact Arithmetic in C++ (2000).
 Norbert Müller: iRRAM C++ Library.
Suggested Literature
 KerI 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 BitComplexity of Numerical Operators on Analytic Functions and Gevrey's Hierarchy, pp.689714 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).
ELearning
 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