Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
18cs493 [2018-07-12] – [Suggested Literature] Martin Ziegler | 18cs493 [2018-07-25] (current) – written exam Martin Ziegler | ||
---|---|---|---|
Line 1: | Line 1: | ||
+ | | ||
+ | This course offers a hands-on introduction to the rigorous foundations | ||
+ | of computing with continuous data (real numbers, sequences, functions): | ||
+ | from in/ | ||
+ | |||
+ | ==== Purpose and Goals ==== | ||
+ | We emphasize the difference between a recipe/ | ||
+ | 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, | ||
+ | real tests, root finding, differentiation, | ||
+ | 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. | ||
+ | ==== Administrative === | ||
+ | Lecturer: [[mailto: | ||
+ | |||
+ | Language: English only | ||
+ | |||
+ | Prerequisites: | ||
+ | |||
+ | Teaching Assistant: [[mailto: | ||
+ | |||
+ | Test questions for self-assessment 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/ | ||
+ | |||
+ | There will be 3 small homework/ | ||
+ | and a final exam on July 25+26 (two parts). | ||
+ | ==== Schedule ==== | ||
+ | * 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: | ||
+ | in E3-1 #3444 | ||
+ | ==== Synopsis ==== | ||
+ | - {{18cs493a.pdf|Introduction and Motivation}} ({{18cs493a.ppt|ppt}}) | ||
+ | - {{18cs493b.pdf|Discrete Computation}} ({{18cs493b.ppt|ppt}}): | ||
+ | * Halting Problem | ||
+ | * Un/ | ||
+ | * WHILE+ Programs | ||
+ | * Asymptotic Runtime | ||
+ | * Complexity classes P, NP, EXP | ||
+ | * (Polynomial-time) Reduction | ||
+ | - {{18cs493c.pdf|Computing over the Reals}} ({{18cs493c.ppt|ppt}}) | ||
+ | * Computable Real numbers: non/ | ||
+ | * Equality, real sequences and limits | ||
+ | * Computing real functions, Effective Weierstrass Theorem | ||
+ | * Computational cost, compactness, | ||
+ | * Uncomputable derivative | ||
+ | - {{18cs493d.pdf|Exact Real Computation}} ({{18cs493d.ppt|ppt}}) | ||
+ | * Non-extensionality, | ||
+ | * Semantics of tests and choose() | ||
+ | * iRRAM library | ||
+ | * Example Algorithms | ||
+ | - {{18cs493e.pdf|Real Complexity Theory}} ({{18cs493e.ppt|ppt}}) | ||
+ | * Polynomial-time reals | ||
+ | * Polynomial-time 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: " | ||
+ | * Norbert Müller: [[https:// | ||
+ | * Norbert Müller: [[http:// | ||
+ | |||
+ | ==== Suggested Literature ==== | ||
+ | * Ker-I Ko: Complexity Theory of Real Functions, Birkhäuser (1991). | ||
+ | * Klaus Weihrauch: Computable Analysis: An Introduction, | ||
+ | * 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' | ||
+ | * Akitoshi Kawamura, Florian Steinberg, Martin Ziegler: On the Computational Complexity of the Dirichlet Problem for Poisson' | ||
+ | |||
+ | ==== E-Learning ==== | ||
+ | * [[http:// | ||
+ | * {{18cs493i.pdf|Homework #1}} consists of four problems to be solved and submitted in English by midnight of July 9 (Monday) via [[mailto: | ||
+ | * {{18cs493ii.pdf|Homework #2}} consists of one large problem to be solved and submitted in English **on paper** in the lecture on July 17 (Tuesday) | ||
+ | * {{18cs493iii.pdf|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 [[mailto: | ||
+ | * {{18cs493exam.pdf|Written Exam}} on July 25 with 30% bonus points |