SoSe 2012 » Algebraic, Topological and Physical Aspects of Computing
Ziegler

Übersicht

Downloads

Aktuelles

03.06.2012	Due to a temporal collision, the exercise session on June 8th is replaced by a lecture on June 5 (Tuesday) at 9h50 in S2|15-401
24.05.2012	On June 1st we have to temporarily reschedule the exercise session from 11:45 to 13:00.

 

Veranstalter

Name	Raum	Tel.
Ziegler, Martin

 

Vorlesung

Tag	Uhrzeit	in Raum
Donnerstags	16:15 - 17:55	S2|15-201

 

Literatur

• Brattka&Ziegler: Computability in Linear Algebra, pp.187-211 in Theoretical Computer Science vol.326
• Real Computation with Least Discrete Advice, http://dx.doi.org/10.1016/j.apal.2011.12.030
• Pauly&Ziegler: Relative Computability and Uniform Continuity of Relations, arXiv:1105.3050
• Ziegler&Koolen: Kolmogorov Complexity Theory over the Reals, Electronic Notes in Theoretical Computer Science vol.221 (2008).
• Brattka,Hertling,Weihrauch: Tutorial on Computable Analysis, www.springerlink.com/index/q8m3614067427312.pdf
• Weihrauch: Computable Analysis
• Morris: Topology without Tears, http://uob-community.ballarat.edu.au/~smorris/topology.htm
• P.Boldi&S.Vigna: "Equality is a Jump", http://dx.doi.org/10.1016/S0304-3975(98)00283-7
• K.Meer&M.Ziegler: "An explicit solution to Post's Problem over the reals", http://dx.doi.org/10.1016/j.jco.2006.09.004
• Blum,Shub,Smale: "On a Theory of Computation and Complexityover the real numbers", projecteuclid.org/euclid.bams/1183555121

 

Übung

Nr.	Zeit	in Raum
1	Freitags, 11:40 - 12:40	S215/201

 

Contents

1. Topological Aspects
   1. Recap on Recursive Analysis
      1. Cauchy computable reals, signed-digit expansions
      2. Computing real functions and relations
      3. Examples: power series, ε-tests
      4. The (sometimes so-called) Main Theorem
      5. Computable Weierstraß Approximation Theorem
      6. Computing closed subsets; union and intersection
      7. Representations
   2. (In-)Computability in Linear Algebra and Geometry
      1. Convex Hull and 2D Point Location
      2. Determinant and rank
      3. Solving systems of linear equations
      4. Diagonalizing symmetric matrices
   3. Uniform Continuity for Multivalued Functions
      1. Hemi, weak and strong continuity
      2. Henkin continuity and the signed-digit relation
      3. A generalized Main Theorem
      4. and its converse
   4. Computing with Discrete Advice
      1. Above examples revisited
      2. Least discrete advice: quantitative and combinatorial aspects of topology
      3. Witnesses of k-wise discontinuity for functions
      4. and for relations
      5. Examples: LLPO and MLPO
      6. Least advice for solving linear equations
      7. Least advice for symmetric matrix diagonalization
      8. Least advice for finding some eigenvector
   5. Revising Computation
      1. finitely many mind-changes
      2. naive Cauchy computation
2. Algebraic Aspects
   1. Recap on the Blum-Shub-Smale Model
      1. Examples: computational geometry, linear algebra, algebraic geometry
      2. Canonical path decomposition, undecidability
      3. Reminder on field extensions and degrees; Lindemann-Weierstraß
   2. Comparison to Computable Analysis
      1. Uncomputable e^x and sqrt, computable Heaviside and decidable graph(sqrt)
      2. A continuous BSS-computable function incomputable in Recursive Analysis
   3. Real Kolmogorov Complexity and Transcendence Degree
      1. Discrete Kolmogorov complexity
   4. NP-Completeness over the Reals
3. Physical Aspects

 

Impressum | Datenschutzerklärung