SS 2013 » Computable Analysis



01.07.2013Additional lecture on Thursday, July 4, at 3pm
15.06.2013As indicated above, the lecture and/or exercise sessions unfortunately cannot take place
* on Tuesday, July 2
* on Monday, July 8
* on Tuesday, July 9
03.05.2013In order to catch up on, and anticipating futher, cancelled sessions, we will from now on extend the Tuesdays' meetings from 45 to 90 minutes.
28.04.2013Due to traveling the exercise session originally scheduled for Tuesday (April 30) has to be postponed by one week.
16.04.2013Lectures take place Mondays from 3:20pm to 5:00pm in S2/15-201
Exercise classes are Tuesdays from 5:10pm to 5:55pm in S2/15-201, starting April 23rd
20.03.2013The time, date, and place for the rest of this course may be discussed during the first meeting on April 15 at 2:25pm in S1/03-116.



Name Raum Tel.
Ziegler, Martin



TagUhrzeitin Raum
Montags15:20 - 17:00S2/15-201





Nr.Zeitin Raum
1Dienstags, 17h10 - 18h40S2/15-201



  1. Recap on discrete computability:
    1. in-/computability,
    2. equivalence of several notions
    3. Halting problem,
    4. enumerability
    5. Reduction
  2. Computability of real numbers:
    1. equivalence of several notions
    2. Specker sequence,
    3. in-/effective rates of convergence
    4. closure under addition, multiplication etc.
    5. computability of real sequences: uniformity
  3. Real function computability
    1. Computable Weierstrass Theorem
    2. power series
    3. computable join, max, int
    4. uncomputable: argmax, roots, diff
    5. Uncomputable Wave Equation
    6. Multivaluedness and Discrete Advice
  4. Type-2 Theory of Effectivity
    1. Constructing with, and Comparing, Representations
    2. Encoding Functions, Closed, and Open Subsets
    3. Computability in Linear Algebra
  5. Recap on discrete complexity theory:
    1. bit-model of computation
    2. asymptotic runtime/memory
    3. example algorithms: Sieve, Euler Circuit, Edge Cover
    4. SAT, 3SAT, Vertex Cover, Hamilton Ciruit, TSP
    5. polynomial reduction
    6. 4SAT ≤ 3SAT ≤ Vertex Cover
    7. NP-completeness
    8. PSPACE and #P
  6. Real function complexity theory:
    1. polytime computable reals and functions
    2. polynom. continuity, 1/ln(e/x)
    3. nonuniform complexity of MAX and ∫
    4. Laplace/Poisson Equation
  7. Parameterized and Second-Order Complexity
    1. Second-Order Representations
    2. Second-Order Polynomials
    3. Examples
  8. Reductions
  9. iRRAM



Achtung: Vom 23.10.2017 bis 25.10.2017 ist das Studienbüro wegen Semestervorbereitung geschlossen! Die Sprechstunden entfallen!

Ordnungen, Formulare, etc.

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

Sabine Bartsch
Iryna Bysaha
Meike Mühlhäußer
Alexandra Neutsch
Bettina Plutz (in Elternzeit)

Mi, Do10:30-12:30



 Albrun Knof


Die Sprechstunden finden in Raum S2|15 241 statt. Es ist keine Terminvereinbarung notwendig.

Weitere Fragen bitte per Mail an:




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