SS 2011 » Reelle Komplexität
Ziegler

ÜbersichtBeiträge

Aktuelles

03.03.2011Vorbesprechung am 11.4.2011 um 14h25 im S2|02-A313.
Der erste Vortrag findet statt am 2.5.2011 um 14h25 im S2|02-A313

 

Veranstalter

Name Raum Tel.
Ziegler, Martin

 

Vorlesung

TagUhrzeitin Raum
Montags14:25 - 16:05S2|02-A313

 

Literatur

  • L. Blum, F. Cucker, M. Shub and S. Smale, Complexity and Real Computation, Springer (1998) (HeBIS, Wellnitz, Buch Habel, Amazon)
  • L. Blum, M. Shub, S. Smale, “On a Theory of Computation Over the Real Numbers; NP Completeness, Recursive Functions and Universal Machines,” FOCS; 88; Bulletin of the AMS, Vol. 21:1 pp.1-46 (1989, projecteuclid.org/euclid.bams/1183555121
  • Ker-I Ko: "Complexity Theory of Real Functions", Springer (1991) (HeBIS, Wellnitz, Buch Habel, Amazon)
  • Klaus Weihrauch: "Computable analysis", Springer (2000) (HeBIS, Wellnitz, Buch Habel, Amazon)
  • Ker-I Ko, Harvey Friedman: Computational Complexity of Real Functions. Theor. Comput. Sci. 20: 323-352 (1982) (HeBIS)
  • Brattka, Hertling, Weihrauch: "A Tutorial on Computable Analysis", http://www.springerlink.com/content/q8m3614067427312/

 

Kooperation

gemeinsam mit PD Dr. Ulrike Brandt vom Fachbereich Informatik

 

Einleitung

Sicher haben Sie schon vom Milleniumsproblem "P versus NP" gehört; vielleicht auch vom verwandten "NP versus PSPACE". Hierbei geht es um die Beziehungen zwischen Komplexitätsklassen diskreter Rechenaufgaben, d.h. über natürlichen Zahlen bzw. endlichen Binärfolgen.

Für das Rechnen mit reellen Zahlen gibt es zwei diametrale Algorithmen-Konzepte:

  1. als Programm über den arithmetischen Operationen und Vergleichen: wohlgemerkt exakt
  2. durch Approximation mit Brüchen (d.h. Zähler und Nenner natürliche Zahlen) bis auf vorgebbaren Absolutfehler
Hier tauchen die Konzepte P und NP  in überraschender Weise wieder auf und erklären, warum manche numerischen Aufgaben so viel Rechenaufwand aufwerfen.

 

Themenliste und Termine

  1. Grundlagen struktureller diskreter Komplexitätstheorie I (deterministische und nichtdeterministische Turingmaschinen, Asymptotik, polynomielle Laufzeit und Speicherplatz) : Schwagenscheidt, 2.5.
  2. Grundlagen struktureller diskreter Komplexitätstheorie II (Reduktion, NP- und PSPACE-vollständige Probleme) : Bitterlich, 9.5.

  3. Berechenbarkeit und Komplexität reeller Zahlen (mehrere äquivalente Definitionen, Eigenschaften, Gegen-/Beispiele) : Wietschel 16.5.
  4. Berechenbarkeit reeller Funktionen auf [0,1] (Definition, Hauptsatz, effektiver Weierstraß, Beispiele) : Franz 23.5.
  5. Komplexität reeller Zahlen und Funktionen (sinnlose und sinnvolle Definition, Beispiele) : Neeb 30.5.
  6. Komplexität des Maximums einer polynomialzeitberechenbaren Funktion : Thies 6.6.
  7. Komplexität des Integrals einer polynomialzeitberechenbaren Funktion

  8. BSS-Rechenmodell: Motivation, Definition, Beispielalgorithmen : Chebotar 20.6.
  9. Pfadzerlegung, unberechenbare reelle Funktionen : Sokoli 27.6. im S2|15-201
  10. Komplexitätsklasse NP über Ringen {0,1}, ℕ, ℝ, ℂ: Deiseroth 4.7.
  11. P-versus-NP über ℝ und ℂ, Entscheidbarkeit von NP: Schwagenscheidt 11.7.
  12. Komplexität und Quantenlogik: Ziegler 18.7.

     

Aktuelles

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)

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

studienbuero(at)mathematik.tu-darmstadt.de

Studienberatung

 Albrun Knof

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

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

Weitere Fragen bitte per Mail an:

studienberatung(at)mathematik.tu-darmstadt.de

 

 

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