SS 2012 » Algebraic, Topological and Physical Aspects of Computing



03.06.2012Due 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.2012On June 1st we have to temporarily reschedule the exercise session from 11:45 to 13:00.



Name Raum Tel.
Ziegler, Martin



TagUhrzeitin Raum
Donnerstags16:15 - 17:55S2|15-201



  • Brattka&Ziegler: Computability in Linear Algebra, pp.187-211 in Theoretical Computer Science vol.326
  • Real Computation with Least Discrete Advice,
  • 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,
  • Weihrauch: Computable Analysis
  • Morris: Topology without Tears,
  • P.Boldi&S.Vigna: "Equality is a Jump",
  • K.Meer&M.Ziegler: "An explicit solution to Post's Problem over the reals",
  • Blum,Shub,Smale: "On a Theory of Computation and Complexityover the real numbers",



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



  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 ex 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



Achtung: Am 13., 20., 23., und 30. März 2017 entfällt die Sprechstunde des Studienkoordinators.

Ordnungen, Formulare, etc.

Dokumente wie Prüfungsplan-formulare, Studien- und Prüfungspläne oder Modulhandbücher finden Sie im Downloadbereich

Sabine Bartsch
Meike Mühlhäußer
Bettina Plutz

Mi, Do10:30-12:30


Dr. Benjamin Seyfferth





A A A | Print Drucken | Impressum Impressum | Contact Kontakt
    zum Seitenanfangzum Seitenanfang