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-08] – [Synopsis] Martin Ziegler20cs700 [2024-06-23] (current) – YouTube + Handbook 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}},[[https://drive.google.com/file/d/1JQcoCtv6o9Yo3wTGCmTbkt2F8jV_egDm/|video]]): \\+**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}},[[https://drive.google.com/file/d/1yuqN1sJ5GK9-sSrwVSaaYV0TmN-m0kR4/|video1]],[[https://drive.google.com/file/d/1B9dN6RNsuKLfGdmrjjfx6596K3wRVFe7|video2]]): \\+**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, Limit Lemma, Arithmetic Hierarchy \\ 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]]):  \\ 
-a)   Computing Real Numbers: three equivalent notions, counter/examples, oracle-computable reals/limit Lemma \\ +a)   Computing Real Numbers: three equivalent notions, counter/examples, oracle-computable reals/limit Lemma ([[https://www.youtube.com/watch?v=3AuYaVmd2k0|video]]) \\ 
-b)  Computing Real Sequences: semi-decidability / strong undecidability of equality, no computable sequence contains all computable reals  \\ +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]])\\ 
-c)  Computing Real Functions: closure under composition and restriction and sequences, necessarily continuous, computable Weierstrass Theorem, compactness \\ +c)  Computing Real Functions: closure under composition and restriction and sequences, necessarily continuous, computable Weierstrass Theorem ([[https://www.youtube.com/watch?v=wDvlB_XnIzk|video]])\\ 
-d)  Computing Real Functions II: uncomputable root finding, uncomputable derivative, uncomputable Wave Equation \\ +d+e)  Un/Computability over Real Functions: un/computable Argmin/Root Finding, un/computable Derivative, un/computable, un/computable Wave Equation  
-e)   Computing Real Multi-Functions: generalized restriction, fuzzy sign, Archimedian property, Fundamental Theorem of Algebra \\ +([[https://www.youtube.com/watch?v=Qllr1gB2Kbs|video1]], [[https://www.youtube.com/watch?v=WvG4I517lKA|video2]]) \\ 
-f)  Computing Real Operators: encoding continuous functions, encoding compact subsets \\ +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]]) \\ 
-g)   Applications: Analytic functions, discrete enrichment, computability in linear algebra \\   +g)  Computing Real Operators: encoding continuous functions, uniform computability, encoding compact subsets, Boolean set operations ([[https://youtu.be/zkowLAhAIpQ|video]]) \\ 
-**III. Computability on T0 spaces**: \\ +**III. Computability on Topological Spaces** ({{20cs700c.pdf|pdf}},{{20cs700c.ppt|ppt}}): \\ 
-C[0;1] and computable Weierstrass Theorem +a) Basic Spaces: Cantor/Baire, Computing, Cost, Continuity, Compactness 
-encoding compact Euclidean subsets +([[http://youtu.be/bV6fc0OxY2U|video]]) \\ 
-computability of function image and preimage +b) Representations: Definition, Real Examples revisited,  
-theory of encodings (TTE) +Continuity and Compactness revisited, Realizers 
-Main Theorem: continuity = oracle computability +of Multi/functions between Represented Spaces, Reduction between 
-Henkin-continuity of multivalued 'functions' \\ +Representations, Admissible/Standard Representations, Main Theorem, 
-**IV. Complexity theory over the Reals**: \\ +Sequence Representation 
-quantitative stability and polynomial-time computability +([[http://youtu.be/MCROVpjJqvo|video1]],[[http://youtu.be/8K0Cc8DKYxE|video2]]) \\ 
-maximizing smooth polynomial-time functions is NP-'complete' +**IV. Recap on Discrete Complexity Theory** ({{20cs700d.pdf|pdf}},{{20cs700d.ppt|ppt}}) \\ 
-hardness of integration, of solving ODEs, and of Poisson's PDE +a) Computation with cost,  
-polynomial-time computable analytic functions +selected complexity classes, classifying example decision problems, 
-fixed-parametrized complexity and Gevrey's Hierarchy +comparing decision problems, complexity class picture  
-average-case complexity of real functions \\ +([[http://youtu.be/YAFRIWFk0zo|video]]) \\ 
-**V. Complexity Theory on Compact Metric Spaces** \\ +b) complexity class picture, counting complexity class #P, unary complexity classes,  
-**VI. 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, 
-**VII. Uniform 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 \\ 
 +**VIII. Reduction 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 ====
 Mathematical background: Mathematical background:
Line 74: Line 107:
  
 ==== Selected References ==== ==== Selected References ====
 +  * [[https://youtube.com/playlist?list=PLvcvykdwsGNE9HyG46aT6aqCvvJBZgKZh|YouTube]]
   * Klaus Weihrauch: Computable Analysis: An Introduction, Springer (2000).   * Klaus Weihrauch: Computable Analysis: An Introduction, Springer (2000).
   * Ker-I Ko: Complexity Theory of Real Functions, Birkhäuser (1991).   * Ker-I Ko: Complexity Theory of Real Functions, Birkhäuser (1991).
 +  * Vasco Brattka, Peter Hertling (Editors): Handbook of Computability and Complexity in Analysis (2021)
   * Mark Braverman, Stephen Cook: Computing over the Reals: Foundations for Scientific Computing, Notices of the AMS (2006).   * Mark Braverman, Stephen Cook: Computing over the Reals: Foundations for Scientific Computing, Notices of the AMS (2006).
   * Akitoshi Kawamura, Stephen Cook: Complexity Theory for Operators in Analysis, ACM Transactions on Computation Theory 4 (2012).   * Akitoshi Kawamura, Stephen Cook: Complexity Theory for Operators in Analysis, ACM Transactions on Computation Theory 4 (2012).
Line 84: Line 119:
   * M.Schröder, F.Steinberg, M.Ziegler: "Average-Case Bit-Complexity Theory of Real Functions", pp.505-519 in Proc. 6th Int. Conf. on Mathematical Aspects of Computer and Information Sciences (MACIS 2015), Springer LNCS vol.9582 (2016).   * M.Schröder, F.Steinberg, M.Ziegler: "Average-Case Bit-Complexity Theory of Real Functions", pp.505-519 in Proc. 6th Int. Conf. on Mathematical Aspects of Computer and Information Sciences (MACIS 2015), Springer LNCS vol.9582 (2016).
   * 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)