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
Last revisionBoth sides next revision
18cs493 [2018-07-12] – [Suggested Literature] Martin Ziegler18cs493 [2018-07-25] – [E-Learning] 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}}