Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revisionLast revisionBoth sides next revision | ||
| 18cs493 [2018-07-05] – E-Learning Martin Ziegler | 18cs493 [2018-07-25] – [E-Learning] Martin Ziegler | ||
|---|---|---|---|
| Line 53: | Line 53: | ||
| in E3-1 #3444 | in E3-1 #3444 | ||
| ==== Synopsis ==== | ==== Synopsis ==== | ||
| - | - {{18cs493a.pdf|Introduction and Motivation}} | + | - {{18cs493a.pdf|Introduction and Motivation}} |
| - | - {{18cs493b.pdf|Discrete Computation}}: | + | - {{18cs493b.pdf|Discrete Computation}} |
| * Halting Problem | * Halting Problem | ||
| * Un/ | * Un/ | ||
| Line 61: | Line 61: | ||
| * Complexity classes P, NP, EXP | * Complexity classes P, NP, EXP | ||
| * (Polynomial-time) Reduction | * (Polynomial-time) Reduction | ||
| - | - Computing over the Reals | + | - {{18cs493c.pdf|Computing over the Reals}} ({{18cs493c.ppt|ppt}}) |
| * Computable Real numbers: non/ | * Computable Real numbers: non/ | ||
| * Equality, real sequences and limits | * Equality, real sequences and limits | ||
| * Computing real functions, Effective Weierstrass Theorem | * Computing real functions, Effective Weierstrass Theorem | ||
| * Computational cost, compactness, | * Computational cost, compactness, | ||
| - | * Root finding and uncomputable argmax | + | * Uncomputable derivative |
| - | * Uncomputable derivative/wave equation | + | - {{18cs493d.pdf|Exact Real Computation}} ({{18cs493d.ppt|ppt}}) |
| * Non-extensionality, | * Non-extensionality, | ||
| - | - Real Complexity Theory | ||
| - | * Real arithmetic, join, maximum, integral | ||
| - | * Polynomial-time un/ | ||
| - | * Polynomial-time un/ | ||
| - | * Maximizing smooth functions and P/NP | ||
| - | * Riemann Integration and #P, ODEs and PSPACE | ||
| - | * Complexity Phase Transition and Gevrey' | ||
| - | - Practice of Exact Real Computation | ||
| - | * iRRAM library | ||
| * Semantics of tests and choose() | * Semantics of tests and choose() | ||
| + | * iRRAM library | ||
| * Example Algorithms | * Example Algorithms | ||
| + | - {{18cs493e.pdf|Real Complexity Theory}} ({{18cs493e.ppt|ppt}}) | ||
| + | * Polynomial-time reals | ||
| + | * Polynomial-time functions | ||
| + | * Maximizing smooth functions and P/NP | ||
| + | * Riemann Integration and #P, ODEs and PSPACE | ||
| ==== Reading List ==== | ==== Reading List ==== | ||
| Line 86: | Line 83: | ||
| * Norbert Müller: [[https:// | * Norbert Müller: [[https:// | ||
| * Norbert Müller: [[http:// | * Norbert Müller: [[http:// | ||
| - | * [[http:// | + | |
| ==== Suggested Literature ==== | ==== Suggested Literature ==== | ||
| * Ker-I Ko: Complexity Theory of Real Functions, Birkhäuser (1991). | * Ker-I Ko: Complexity Theory of Real Functions, Birkhäuser (1991). | ||
| Line 95: | Line 92: | ||
| * Akitoshi Kawamura, Florian Steinberg, Martin Ziegler: On the Computational Complexity of the Dirichlet Problem for Poisson' | * Akitoshi Kawamura, Florian Steinberg, Martin Ziegler: On the Computational Complexity of the Dirichlet Problem for Poisson' | ||
| - | E-Learning: | + | ==== E-Learning |
| * [[http:// | * [[http:// | ||
| - | * {{18cs493i.pdf|Homework #1}} consists of four problems to be solved and submitted in English | + | * {{18cs493i.pdf|Homework #1}} consists of four problems to be solved and submitted in English by midnight of July 9 (Monday) |
| + | * {{18cs493ii.pdf|Homework #2}} consists of one large problem to be solved and submitted in English **on paper** in the lecture on July 17 (Tuesday) | ||
| + | * {{18cs493iii.pdf|Homework #3}} consists of two problems. Problem 6 is to be solved and submitted in English **on paper** in the lecture on July 24 (Tuesday). Problem 7 is to be solved and submitted in English via [[mailto: | ||
| + | * {{18cs493exam.pdf|Written Exam}} | ||