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
20cs700 [2020-09-03] – [Synopsis] Martin Ziegler20cs700 [2023-03-19] (current) Martin Ziegler
Line 1: Line 1:
-====== Computer Science of Continuous Data: Algorithmic Foundations of Numerics (CS700) ====+====== Computer Science for Continuous Data: Algorithmic Foundations of Numerics (CS700) ====
 ===== Fall 2020 at KAIST's School of Computing ===== ===== Fall 2020 at KAIST's School of Computing =====
  
Line 16: Line 16:
 Language: English (only) \\ Language: English (only) \\
 Final exam: Dec.14~18, take-home \\ Final exam: Dec.14~18, take-home \\
- 
  
 ==== Synopsis ==== ==== Synopsis ====
-**0. Introduction & Motivation** ({{20cs700_.pdf|pdf}},{{20cs700_.ppt|ppt}}): \\+**0. Introduction & Motivation** ({{20cs700_.pdf|pdf}},{{20cs700_.ppt|ppt}},[[https://www.youtube.com/watch?v=EwXPRBiRnE8|video]]): \\
 "Virtues" of Computer Science and Mathematics,  "Virtues" of Computer Science and Mathematics, 
 Abstract Data Types / Structures in Computer Science and Mathematics, Abstract Data Types / Structures in Computer Science and Mathematics,
 IEEE 754 / Floatingpoint Discretization Properties and Reliability, IEEE 754 / Floatingpoint Discretization Properties and Reliability,
 Numerical Folklore and Myths \\ Numerical Folklore and Myths \\
-**I. Recap on discrete Theory of Computation** ({{20cs700a.pdf|pdf}},{{20cs700a.ppt|ppt}}): \\ +**I. Recap on Discrete Computability Theory** ({{20cs700a.pdf|pdf}},{{20cs700a.ppt|ppt}},[[https://www.youtube.com/watch?v=MvAMXQ199Ok|video1]],[[https://www.youtube.com/watch?v=QszQZGujw8w|video2]]): \\ 
-Un-/Computability, Halting Problem, Semi-/Decidability, Reduction, WHILE model of computation, SMN property/Currying, Oracle computation \\ +Un-/Computability, Halting Problem, Semi-/Decidability, Reduction, WHILE model of computation, SMN property/Currying, Oracle computation, Limit Lemma, Arithmetic Hierarchy \\ 
-**II. Computability theory over the Reals**: \\ +**II. Computability theory over the Reals** ({{20cs700b.pdf|pdf}},{{20cs700b.ppt|ppt}},[[https://www.youtube.com/watch?v=NNZw1u97ESA|video]]):  \\ 
-real numbersbinary vs. approximation +a)   Computing Real Numbersthree equivalent notionscounter/examplesoracle-computable reals/limit Lemma ([[https://www.youtube.com/watch?v=3AuYaVmd2k0|video]]) \\ 
-sequenceslimitsrate of convergence +b)  Computing Real Sequences: semi-decidability / strong undecidability of equality, no computable sequence contains all computable reals  ([[https://www.youtube.com/watch?v=iC6dOOltVA8|video]])\\ 
-qualitative stabilitycomputability and continuity +c)  Computing Real Functionsclosure under composition and restriction and sequences, necessarily continuous, computable Weierstrass Theorem ([[https://www.youtube.com/watch?v=wDvlB_XnIzk|video]])\\ 
-real arithmeticjoinmaximumintegral +d+e)  Un/Computability over Real Functions: un/computable Argmin/Root Findingun/computable Derivativeun/computableun/computable Wave Equation  
-root finding, argmaxderivative +([[https://www.youtube.com/watch?v=Qllr1gB2Kbs|video1]][[https://www.youtube.com/watch?v=WvG4I517lKA|video2]]) \\ 
-uncomputable wave equation +f)  Multi-Functions & Enrichment: generalized restriction, fundamental theorem of algebra, fuzzy sign, Archimedian property, linear algebra, analytic functions ([[https://www.youtube.com/watch?v=ZHJcC3MpkHA|video]]) \\ 
-analytic functions, discrete enrichment +g)  Computing Real Operators: encoding continuous functionsuniform computability, encoding compact subsets, Boolean set operations ([[https://youtu.be/zkowLAhAIpQ|video]]) \\ 
-multivaluedness, computability in linear algebra \\ +**III. Computability on Topological Spaces** ({{20cs700c.pdf|pdf}},{{20cs700c.ppt|ppt}}): \\ 
-**III. Computability on T0 spaces**: \\ +a) Basic Spaces: Cantor/Baire, Computing, Cost, Continuity, Compactness 
-C[0;1and computable Weierstrass Theorem +([[http://youtu.be/bV6fc0OxY2U|video]]) \\ 
-encoding compact Euclidean subsets +b) Representations: Definition, Real Examples revisited,  
-computability of function image and preimage +Continuity and Compactness revisited, Realizers 
-theory of encodings (TTE) +of Multi/functions between Represented Spaces, Reduction between 
-Main Theorem: continuity = oracle computability +Representations, Admissible/Standard Representations, Main Theorem
-Henkin-continuity of multivalued 'functions\\ +Sequence Representation 
-IV. Complexity theory over the Reals: \\ +([[http://youtu.be/MCROVpjJqvo|video1]],[[http://youtu.be/8K0Cc8DKYxE|video2]]) \\ 
-quantitative stability and polynomial-time computability +**IV. Recap on Discrete Complexity Theory** ({{20cs700d.pdf|pdf}},{{20cs700d.ppt|ppt}}) \\ 
-maximizing smooth polynomial-time functions is NP-'complete' +a) Computation with cost,  
-hardness of integration, of solving ODEs, and of Poisson's PDE +selected complexity classes, classifying example decision problems, 
-polynomial-time computable analytic functions +comparing decision problems, complexity class picture  
-fixed-parametrized complexity and Gevrey's Hierarchy +([[http://youtu.be/YAFRIWFk0zo|video]]) \\ 
-average-case complexity of real functions \\ +b) complexity class picture, counting complexity class #P, unary complexity classes,  
-V. Imperative programming over the Reals: \\ +parameterized complexity, average-case complexity, various reductions, between functions 
-Semantics of tests +([[http://youtu.be/PscaFPCKya0|video]]) \\ 
-Example: Gaussian Elimination +** V. Complexity theory over the Reals** ({{20cs700e.pdf|pdf}},[[http://youtu.be/f6LInVb4EmM|video]]): \\ 
-Verification in Floyd-Hoare Logic +a) Polytime-computable real numbers, 
-Practical implementation in iRRAM \\ +polytime-computable real functions, 
-VIUniform complexity of operators in Analysis: \\ +quantitative computability ⇒ quantitative continuity, 
-TTE and computational complexity +operations that preserve polytime computability ([[http://youtu.be/LvPi9VAN4t4|video]]) \\ 
-encoding metric spaces of polynomial entropy +b)  
-adversary arguments and exponential entropy +(Strongly) polytime-computable real sequences, 
-encoding function spaces via oracles +polytime analytic function ⇔ polytime Taylor coefficients, 
-Lebesgues decomposition and computational complexity +operations on polytime analytic functions ([[http://youtu.be/C6BhoakURIQ|video]]) \\ 
-2nd-order polynomial complexity theory +c)  
-Weihrauch reductions+Maximizing polytime functions "in NP", 
 +indefinite Riemann integration "in #P", 
 +definite Riemann integration "in #P<sub>1</sub>", 
 +ODESOLVE "in PSPACE" ([[http://youtu.be/6rG0aj408G0|video]]) \\ 
 +d)  
 +Numerical characterizations of Discrete complexity classes: 
 +Parametric maximization is NP-"complete", 
 +in/definite Riemann integration is #P/#P<sub>1</sub>-"complete", 
 +(smooth) ODEs are PSPACE-"complete" 
 +([[http://youtu.be/Gd3fME99DvA|video]]) \\ 
 +e) 
 +Intrinsic Complexity of PDEs: Poisson and Heat Equation  
 +([[http://youtu.be/MPQRY0lbgNA|video]]) \\ 
 +**VI. Complexity on Metric Spaces** \\ 
 +a) Complexity of points, 
 +complexity of functions, 
 +complexity and quantitative continuity, 
 +polynomial admissibility, 
 +polynomial 'Main Theorem', 
 +entropy as quantitative compactness  
 +({{20cs700f.pdf|pdf}},{{20cs700f.ppt|ppt}},[[http://youtu.be/RG8uzsWqZ7s|video]]) \\ 
 +b) Quantitative coding theory of compact metric spaces 
 +({{2020cie.pdf|pdf}},{{2020cie.ppt|ppt}},[[http://youtu.be/107nr4BZN6Q|video1]],[[http://youtu.be/0yHgUz6Ufb8|video2]],[[http://youtu.be/joY3_jqw8As|video3]]) \\ 
 +**VII. Imperative programming over the Reals** ({{20cs700g.pdf|pdf}},{{20cs700g.ppt|ppt}},[[http://youtu.be/3MrnDHX0v_0|video]]): \\ 
 +WHILE Programs over N,R,K=Kleene, 
 +non-extensional integer rounding naive and fast, 
 +exponential function, 
 +trisection for simple root finding, 
 +matrix determinant with multival.pivoting, 
 +Turing-completeness over the Reals \\ 
 +**VIIIReduction between Continuous Problems** ({{20cs700h.pdf|pdf}},{{20cs700h.ppt|ppt}},[[http://youtu.be/SGBCCOlyz2w|video]]): \\ 
 +Computing integer functionALs/operators, generalized polynomial resource bounds, degree of 2nd-order polynomials \\ 
 +** Summary** ({{20cs700z.pdf|pdf}},{{20cs700z.ppt|ppt}},[[http://youtu.be/wee9HQqe3_g|video]]) \\ 
  
 ==== Test questions for self-assessment ==== ==== Test questions for self-assessment ====
Line 86: Line 118:
   * Katrin Tent, Martin Ziegler (Freiburg!): Computable Functions of Reals   * Katrin Tent, Martin Ziegler (Freiburg!): Computable Functions of Reals
   * 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).   * 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).
 +