SoSe 2013 » Computable Analysis
Ziegler

Übersicht

Downloads

Aktuelles

01.07.2013	Additional lecture on Thursday, July 4, at 3pm
15.06.2013	As 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.2013	In 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.2013	Due to traveling the exercise session originally scheduled for Tuesday (April 30) has to be postponed by one week.
16.04.2013	Lectures 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.2013	The 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

Tag	Uhrzeit	in Raum
Montags	15:20 - 17:00	S2/15-201

 

Literatur

• Klaus Weihrauch: "Computable Analysis" (HeBIS, Wellnitz, Buch Habel, Amazon)
• Ko: "Complexity Theory of Real Functions" (HeBIS, Wellnitz, Buch Habel, Amazon)
• Pour-El & Richards: Computability in Analysis and Physics (HeBIS, Wellnitz, Buch Habel, Amazon)

 

Übung

Nr.	Zeit	in Raum
1	Dienstags, 17h10 - 18h40	S2/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