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

ÜbersichtDownloads

Aktuelles

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.

 

Veranstalter

Name Raum Tel.
Ziegler, Martin

 

Vorlesung

TagUhrzeitin Raum
Donnerstags16:15 - 17:55S2|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.Zeitin Raum
1Freitags, 11:40 - 12:40S215/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 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

 

Aktuelles

Achtung: Am 04.08.2016 und vom 15.08. - 08.09. entfällt die Sprechstunde des Studienkoordinators! In dringenden Fällen wenden Sie sich bitte an das Studienbüro.

Ordnungen, Formulare, etc.

... im Downloadbereich

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

Sprechzeiten:
Mo13:30-15:30
Mi, Do10:30-12:30

studienbuero@mathematik.tu-darmstadt.de

Dr. Benjamin Seyfferth

Sprechzeiten:
Mo13:30-15:00
Do10:30-12:00

studienberatung@mathematik.tu-darmstadt.de

 

 

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