Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
18cs493 [2018-07-05] – [Synopsis] Martin Ziegler | 18cs493 [2018-07-25] (current) – written exam 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 ==== | ||
+ | * [[http:// | ||
+ | * {{18cs493i.pdf|Homework #1}} consists of four problems to be solved and submitted in English by midnight of July 9 (Monday) via [[mailto: | ||
+ | * {{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}} on July 25 with 30% bonus points |