Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
18cs493 [2018-07-12] – [Synopsis] Martin Ziegler18cs493 [2018-07-25] (current) – written exam Martin Ziegler
Line 1: Line 1:
 + ====== 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.
 +
 +==== 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 object-oriented overloading
 +an abstract data type REAL. In addition, each week will conclude
 +with a theoretical homework assignment.
 +==== Administrative ===
 +Lecturer: [[mailto:CS493@theoryofcomputation.asia|Martin Ziegler]]
 +
 +Language: English only 
 +
 +Prerequisites: Introduction to Computer Science, Discrete Mathematics, Calculus I, C++, root on some Linux computer
 +
 +Teaching Assistant: [[mailto:klimdhn@kaist.ac.kr|Donghyun Lim]]
 +
 +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/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: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
 +==== Synopsis ====
 +  - {{18cs493a.pdf|Introduction and Motivation}} ({{18cs493a.ppt|ppt}})
 +  - {{18cs493b.pdf|Discrete Computation}} ({{18cs493b.ppt|ppt}}): 
 +    * Halting Problem
 +    * Un/Semi/Decidability/Enumerability 
 +    * 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/equivalent notions
 +     * Equality, real sequences and limits
 +     * Computing real functions, Effective Weierstrass Theorem
 +     * Computational cost, compactness, and continuity
 +     * Uncomputable derivative
 +  - {{18cs493d.pdf|Exact Real Computation}} ({{18cs493d.ppt|ppt}})
 +     * Non-extensionality, discrete enrichment
 +     * 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: "[[http://theoryofcomputation.asia/survey3.pdf|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: [[https://doi.org/10.1007/3-540-45335-0_14|The iRRAM: Exact Arithmetic in C++]] (2000).
 +  * Norbert Müller: [[http://www.informatik.uni-trier.de/iRRAM/|iRRAM C++ Library]].
 +
 +==== Suggested Literature ====
 +  * 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).
 +
 +==== E-Learning ====
 +  * [[http://klms.kaist.ac.kr/|KLMS]]
 +  * {{18cs493i.pdf|Homework #1}} consists of four problems to be solved and submitted in English by midnight of July 9 (Monday) via [[mailto:cs493@theoryofcomputation.asia|email]].
 +  * {{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:cs493@theoryofcomputation.asia|email]] before the lecture on July 24 (Tuesday).
 +  * {{18cs493exam.pdf|Written Exam}} on July 25 with 30% bonus points