SoSe 2013 » Computable Analysis
Ziegler

ÜbersichtDownloads

Aktuelles

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.

 

Veranstalter

Name Raum Tel.
Ziegler, Martin

 

Vorlesung

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

 

Literatur

 

Übung

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

 

Contents

  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

 

Impressum | Datenschutzerklärung