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-08] – [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, 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 85: 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).
 +