Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revisionLast revisionBoth sides next revision | ||
| 20cs700 [2020-09-01] – [Synopsis] Martin Ziegler | 20cs700 [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 \\ | + | **0. Introduction |
| - | I. Recap on discrete | + | " |
| - | 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 Computability |
| - | reductions and completeness, | + | Un-/Computability, Halting Problem, Semi-/ |
| - | oracle computation | + | **II. Computability theory over the Reals** ({{20cs700b.pdf|pdf}}, |
| - | II. Computability theory over the Reals: \\ | + | a) |
| - | real numbers: binary vs. approximation | + | b) Computing Real Sequences: semi-decidability / strong undecidability |
| - | sequences, limits, rate of convergence | + | c) Computing Real Functions: closure under composition |
| - | qualitative stability: computability | + | d+e) Un/ |
| - | real arithmetic, join, maximum, integral | + | ([[https:// |
| - | root finding, argmax, derivative | + | f) Multi-Functions & Enrichment: generalized restriction, |
| - | uncomputable wave equation | + | g) Computing Real Operators: encoding continuous functions, uniform |
| - | analytic functions, discrete enrichment | + | **III. Computability on Topological Spaces** ({{20cs700c.pdf|pdf}}, |
| - | multivaluedness, computability | + | a) Basic Spaces: Cantor/ |
| - | III. Computability on separable metric spaces: \\ | + | ([[http:// |
| - | C[0;1] and computable Weierstrass Theorem | + | b) Representations: |
| - | encoding compact Euclidean subsets | + | Continuity |
| - | computability of function image and preimage | + | of Multi/ |
| - | theory | + | Representations, |
| - | Main Theorem: | + | Sequence Representation |
| - | Henkin-continuity of multivalued 'functions' | + | ([[http:// |
| - | IV. Complexity theory over the Reals: \\ | + | **IV. Recap on Discrete Complexity Theory** ({{20cs700d.pdf|pdf}}, |
| - | quantitative stability and polynomial-time computability | + | a) Computation with cost, |
| - | maximizing smooth polynomial-time functions is NP-'complete' | + | selected complexity classes, classifying example decision problems, |
| - | hardness of integration, | + | comparing decision problems, complexity class picture |
| - | polynomial-time computable analytic | + | ([[http:// |
| - | fixed-parametrized | + | b) complexity class picture, counting complexity class #P, unary complexity classes, |
| - | average-case complexity | + | parameterized complexity, average-case complexity, various reductions, between |
| - | V. Imperative programming over the Reals: \\ | + | ([[http:// |
| - | Semantics of tests | + | ** V. Complexity theory over the Reals** ({{20cs700e.pdf|pdf}}, |
| - | Example: Gaussian Elimination | + | a) Polytime-computable real numbers, |
| - | Verification in Floyd-Hoare Logic | + | polytime-computable real functions, |
| - | Practical implementation in iRRAM \\ | + | quantitative |
| - | VI. Uniform complexity of operators in Analysis: \\ | + | operations that preserve polytime computability ([[http:// |
| - | TTE and computational complexity | + | b) |
| - | encoding metric spaces of polynomial | + | (Strongly) polytime-computable real sequences, |
| - | adversary arguments and exponential entropy | + | polytime analytic function ⇔ polytime Taylor coefficients, |
| - | encoding function spaces via oracles | + | operations on polytime analytic |
| - | Lebesgues decomposition and computational complexity | + | c) |
| - | 2nd-order | + | Maximizing polytime functions "in NP", |
| - | Weihrauch reductions | + | indefinite Riemann integration "in #P", |
| + | definite Riemann integration "in # | ||
| + | ODESOLVE "in PSPACE" | ||
| + | d) | ||
| + | Numerical characterizations of Discrete complexity classes: | ||
| + | Parametric maximization | ||
| + | in/definite Riemann | ||
| + | (smooth) | ||
| + | ([[http:// | ||
| + | e) | ||
| + | Intrinsic Complexity | ||
| + | ([[http:// | ||
| + | **VI. Complexity on Metric Spaces** \\ | ||
| + | a) Complexity of points, | ||
| + | complexity of functions, | ||
| + | complexity and quantitative continuity, | ||
| + | polynomial admissibility, | ||
| + | polynomial | ||
| + | entropy as quantitative compactness | ||
| + | ({{20cs700f.pdf|pdf}}, | ||
| + | b) Quantitative coding theory | ||
| + | ({{2020cie.pdf|pdf}}, | ||
| + | **VII. Imperative programming over the Reals** ({{20cs700g.pdf|pdf}}, | ||
| + | WHILE Programs over N, | ||
| + | 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}}, | ||
| + | Computing integer functionALs/ | ||
| + | ** Summary** ({{20cs700z.pdf|pdf}}, | ||
| ==== Test questions for self-assessment ==== | ==== Test questions for self-assessment ==== | ||
| Line 87: | Line 118: | ||
| * Katrin Tent, Martin Ziegler (Freiburg!): | * Katrin Tent, Martin Ziegler (Freiburg!): | ||
| * A. Kawamura, M. Ziegler: " | * A. Kawamura, M. Ziegler: " | ||
| + | |||