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
Next revisionBoth sides next revision
20cs700 [2020-09-03] – [Synopsis] Martin Ziegler20cs700 [2020-09-17] – [Synopsis] Martin Ziegler
Line 19: Line 19:
  
 ==== Synopsis ==== ==== Synopsis ====
-0. Introduction & Motivation ({{20cs700_.pdf|pdf}},{{20cs700_.ppt|ppt}}): \\+**0. Introduction & Motivation** ({{20cs700_.pdf|pdf}},{{20cs700_.ppt|ppt}},[[https://drive.google.com/file/d/1JQcoCtv6o9Yo3wTGCmTbkt2F8jV_egDm/|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 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]]): \\ 
-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**:  \\ 
-real numbers: binary vs. approximation +a)   Computing Real Numbers: three equivalent notions, counter/examples, oracle-computable reals/limit Lemma ([[https://drive.google.com/file/d/1goACIp9v1Lva1m7tUx8E7_bS2xawIfUT|video]]) \\ 
-sequences, limits, rate of convergence +b)  Computing Real Sequences: semi-decidability / strong undecidability of equality, no computable sequence contains all computable reals  ([[https://drive.google.com/file/d/14TqLkBtmdQy5A-bLUDb0juOAmQKxcW-j|video]])\\ 
-qualitative stability: computability and continuity +c)  Computing Real Functions: closure under composition and restriction and sequences, necessarily continuous, computable Weierstrass Theorem ([[https://drive.google.com/file/d/1bD4sUmWErYefwmnXKibD08s04XPTDW6W|video]])\\ 
-real arithmetic, join, maximum, integral +d)  Advanced Un/Computility of Real Functions: uncomputable Argmin/Root Finding, uncomputable Derivative, uncomputable ODE, uncomputable, Wave Equation, compactness in Real Computation \\ 
-root finding, argmax, derivative +e)  Multi-Functions & Enrichment: generalized restriction, fundamental theorem of algebra, fuzzy sign, Archimedian property, linear algebra, analytic functions \\ 
-uncomputable wave equation +f)  Computing Real Operators: encoding continuous functions, encoding compact subsets \\ 
-analytic functions, discrete enrichment +**III. Computability on T0 spaces**: \\
-multivaluedness, computability in linear algebra \\ +
-III. Computability on separable metric spaces: \\+
 C[0;1] and computable Weierstrass Theorem C[0;1] and computable Weierstrass Theorem
 encoding compact Euclidean subsets encoding compact Euclidean subsets
Line 42: Line 40:
 Main Theorem: continuity = oracle computability Main Theorem: continuity = oracle computability
 Henkin-continuity of multivalued 'functions' \\ Henkin-continuity of multivalued 'functions' \\
-IV. Complexity theory over the Reals: \\+**IV. Complexity theory over the Reals**: \\
 quantitative stability and polynomial-time computability quantitative stability and polynomial-time computability
 maximizing smooth polynomial-time functions is NP-'complete' maximizing smooth polynomial-time functions is NP-'complete'
Line 49: Line 47:
 fixed-parametrized complexity and Gevrey's Hierarchy fixed-parametrized complexity and Gevrey's Hierarchy
 average-case complexity of real functions \\ average-case complexity of real functions \\
-V. Imperative programming over the Reals: \\+**V. Complexity Theory on Compact Metric Spaces** \\ 
 +**VI. Imperative programming over the Reals**: \\
 Semantics of tests Semantics of tests
 Example: Gaussian Elimination Example: Gaussian Elimination
 Verification in Floyd-Hoare Logic Verification in Floyd-Hoare Logic
 Practical implementation in iRRAM \\ Practical implementation in iRRAM \\
-VI. Uniform complexity of operators in Analysis: \\+**VII. Uniform complexity of operators in Analysis**: \\
 TTE and computational complexity TTE and computational complexity
 encoding metric spaces of polynomial entropy encoding metric spaces of polynomial entropy
Line 62: Line 61:
 2nd-order polynomial complexity theory 2nd-order polynomial complexity theory
 Weihrauch reductions Weihrauch reductions
- 
 ==== Test questions for self-assessment ==== ==== Test questions for self-assessment ====
 Mathematical background: Mathematical background: