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-01] – [Synopsis] Martin Ziegler20cs700 [2020-09-17] – [Synopsis] Martin Ziegler
Line 19: Line 19:
  
 ==== Synopsis ==== ==== Synopsis ====
-0. Introduction \\ +**0. Introduction & Motivation** ({{20cs700_.pdf|pdf}},{{20cs700_.ppt|ppt}},[[https://drive.google.com/file/d/1JQcoCtv6o9Yo3wTGCmTbkt2F8jV_egDm/|video]]): \\ 
-I. Recap on discrete Theory of Computation: \\ +"Virtues" of Computer Science and Mathematics,  
-un-/computability, Halting Problem +Abstract Data Types / Structures in Computer Science and Mathematics, 
-asymptotic runtime and memory +IEEE 754 / Floatingpoint Discretization Properties and Reliability, 
-machine models: unit-cost vs. bit-cost +Numerical Folklore and Myths \\ 
-complexity classes LOGSPACE, P, NP1, NP, #P, PSPACE, EXP +**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]]): \\ 
-reductions and completeness, parameterized complexity +Un-/Computability, Halting Problem, Semi-/Decidability, Reduction, WHILE model of computation, SMN property/Currying, Oracle computation, Limit Lemma, Arithmetic Hierarchy \\ 
-oracle computation \\ +**II. Computability theory over the Reals**:  \\ 
-II. Computability theory over the Reals: \\ +a)   Computing Real Numbers: three equivalent notions, counter/examples, oracle-computable reals/limit Lemma ([[https://drive.google.com/file/d/1goACIp9v1Lva1m7tUx8E7_bS2xawIfUT|video]]) \\ 
-real numbers: binary vs. approximation +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]])\\ 
-sequences, limits, rate of convergence +c)  Computing Real Functions: closure under composition and restriction and sequences, necessarily continuous, computable Weierstrass Theorem ([[https://drive.google.com/file/d/1bD4sUmWErYefwmnXKibD08s04XPTDW6W|video]])\\ 
-qualitative stability: computability and continuity +d)  Advanced Un/Computility of Real Functions: uncomputable Argmin/Root Finding, uncomputable Derivative, uncomputable ODE, uncomputable, Wave Equation, compactness in Real Computation \\ 
-real arithmetic, join, maximum, integral +e)  Multi-Functions & Enrichment: generalized restriction, fundamental theorem of algebra, fuzzy sign, Archimedian property, linear algebra, analytic functions \\ 
-root finding, argmax, derivative +f)  Computing Real Operators: encoding continuous functions, encoding compact subsets \\ 
-uncomputable wave equation +**III. Computability on T0 spaces**: \\
-analytic functions, discrete enrichment +
-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 43: 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 50: 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 63: 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: