Parametrisierte uniforme Berechnungskomplexität in Geometrie und Numerik

1. Front Matter

   Pages I-XI

   PDF

2. Einleitung

   • Carsten Rösnick

   Pages 1-7

3. Kontext

   • Carsten Rösnick

   Pages 9-27

4. Darstellungen für Unterklassen abgeschlossener und offener Mengen

   • Carsten Rösnick

   Pages 29-71

5. Berechenbarkeit und Komplexität geometrischer und topologischer Operatoren

   • Carsten Rösnick

   Pages 73-82

6. Höherstufige Komplexität

   • Carsten Rösnick

   Pages 83-88

7. Berechenbarkeit und Komplexität numerischer Operatoren

   • Carsten Rösnick

   Pages 89-124

8. Funktionsinversion

   • Carsten Rösnick

   Pages 125-146

9. Rück- und Ausblick

   • Carsten Rösnick

   Pages 147-151

10. Back Matter

    Pages 153-169

    PDF

Carsten Rösnick legt seiner Arbeit die Frage nach der algorithmischen Komplexität der approximativen Berechnung von Operatoren aus Geometrie, Topologie und Analysis zugrunde. Er betrachtet Operatoren wie Mengendurchschnitt, Projektion, Maximierung, Integration und Funktionsinversion. Der Begriff der Komplexität ist hierbei im rigorosen Sinne von garantierten Laufzeitschranken und asymptotischen Optimalitätsbeweisen zu verstehen. Dazu führt der Autor Kodierungen für Mengen und Funktionen ein und untersucht sie hinsichtlich ihrer (Polynomialzeit-)Äquivalenz, um schließlich in der Bestimmung parametrisierter Komplexitätsschranken für obige Operatoren Verwendung zu finden.

• Berechenbare Analysis
• Kontinuierliche Komplexitätstheorie
• Numerik
• Parametrisierte Berechnungskomplexität
• Theoretische Informatik

• Technische Universität Darmstadt, Darmstadt, Germany

  Carsten Rösnick

Carsten Rösnick studierte Informatik und Mathematik an der Universität Paderborn. Er promovierte als wissenschaftlicher Mitarbeiter an der Technischen Universität Darmstadt in der Arbeitsgruppe Logik des Fachbereichs Mathematik.

Policies and ethics