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
20cs700 [2020-09-09] – [Synopsis] Martin Ziegler20cs700 [2020-12-15] – external edit 127.0.0.1
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 \\ +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)  Advanced Un/Computility of Real Functions: uncomputable Argmin/Root Finding, uncomputable Derivative, uncomputable ODE, uncomputable, Wave Equation, compactness in Real Computation \\ +d+e)  Un/Computability over Real Functions: un/computable Argmin/Root Finding, un/computable Derivative, un/computable, un/computable Wave Equation  
-e)  Multi-Functions & Enrichment: generalized restriction, fundamental theorem of algebra, fuzzy sign, Archimedian property, linear algebra, analytic functions \\ +([[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]]) \\ 
-**III. Computability on T0 spaces**: \\ +g)  Computing Real Operators: encoding continuous functions, uniform computability, encoding compact subsets, Boolean set operations ([[https://youtu.be/zkowLAhAIpQ|video]]) \\ 
-C[0;1] and computable Weierstrass Theorem +**III. Computability on Topological Spaces** ({{20cs700c.pdf|pdf}},{{20cs700c.ppt|ppt}}): \\ 
-encoding compact Euclidean subsets +a) Basic Spaces: Cantor/Baire, Computing, Cost, Continuity, Compactness 
-computability of function image and preimage +([[http://youtu.be/bV6fc0OxY2U|video]]) \\ 
-theory of encodings (TTE) +b) Representations: Definition, Real Examples revisited,  
-Main Theorem: continuity = oracle computability +Continuity and Compactness revisited, Realizers 
-Henkin-continuity of multivalued 'functions' \\ +of Multi/functions between Represented Spaces, Reduction between 
-**IV. Complexity theory over the Reals**: \\ +Representations, Admissible/Standard Representations, Main Theorem, 
-quantitative stability and polynomial-time computability +Sequence Representation 
-maximizing smooth polynomial-time functions is NP-'complete' +([[http://youtu.be/MCROVpjJqvo|video1]],[[http://youtu.be/8K0Cc8DKYxE|video2]]) \\ 
-hardness of integration, of solving ODEs, and of Poisson's PDE +**IV. Recap on Discrete Complexity Theory** ({{20cs700d.pdf|pdf}},{{20cs700d.ppt|ppt}}) \\ 
-polynomial-time computable analytic functions +a) Computation with cost,  
-fixed-parametrized complexity and Gevrey's Hierarchy +selected complexity classes, classifying example decision problems, 
-average-case complexity of real functions \\ +comparing decision problems, complexity class picture  
-**V. Complexity Theory on Compact Metric Spaces** \\ +([[http://youtu.be/YAFRIWFk0zo|video]]) \\ 
-**VI. Imperative programming over the Reals**: \\ +b) complexity class picture, counting complexity class #P, unary complexity classes,  
-Semantics of tests +parameterized complexity, average-case complexity, various reductions, between functions 
-Example: Gaussian Elimination +([[http://youtu.be/PscaFPCKya0|video]]) \\ 
-Verification in Floyd-Hoare Logic +** V. Complexity theory over the Reals** ({{20cs700e.pdf|pdf}},[[http://youtu.be/f6LInVb4EmM|video]]): \\ 
-Practical implementation in iRRAM \\ +a) Polytime-computable real numbers, 
-**VII. Uniform complexity of operators in Analysis**: \\ +polytime-computable real functions, 
-TTE and computational complexity +quantitative computability ⇒ quantitative continuity, 
-encoding metric spaces of polynomial entropy +operations that preserve polytime computability ([[http://youtu.be/LvPi9VAN4t4|video]]) \\ 
-adversary arguments and exponential entropy +b)  
-encoding function spaces via oracles +(Strongly) polytime-computable real sequences, 
-Lebesgues decomposition and computational complexity +polytime analytic function ⇔ polytime Taylor coefficients, 
-2nd-order polynomial complexity theory +operations on polytime analytic functions ([[http://youtu.be/C6BhoakURIQ|video]]) \\ 
-Weihrauch reductions+c)  
 +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 84: 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).
 +