Allgemeines: Wir haben etliche Fragen zusammengestellt, die sich chronologisch durch die Vorlesung im WS03/04 ziehen. Beachtet bitte, dass wir in der Prüfung auch konkrete Instanzen verwenden werden, statt ganz allgemein zu fragen. Zum Beispiel: Wie würden Sie diesen Ausdruck auswerten? Wie klein ist der Fehler hier?
Und: Diese Liste hat natürlich keinen Anspruch auf Vollständigkeit!!!! Die Übungen gehören ebenfalls zum Prüfungsstoff.
Bei sehr gut verlaufenden Prüfungen werden wir am Ende zwei relativ schwere Fragen aus dem Stoff der Vorlesung/Übungen stellen. Zumindest eine davon sollte zufriedenstellend beantwortet werden, um eine 1.0 Benotung zu rechtfertigen.

1. Einführung

• Was bezeichnen wir als Geometric Computation?
• Welche wesentlichen Fragen sind bei geometrischen Algorithmen zu beantworten? Welche Probleme können dabei auftreten?
• Nennen Sie ein paar Beispiele für geometrische Algorithmen und die dazugehörigen Probleme.
• Was bezeichnen wir formal als Robustheit und Stabilität?

2. Floating Point Arithmetic

• Was ist im Standard IEEE 754 festgelegt und wofür braucht man solche Standards überhaupt? Erläutern Sie die Bestandteile der folgenden Floating Point Zahl nach IEEE 754.
• Wie ist das single-precision Format definiert?
• Nennen Sie Alternativen zur Floating Point Arithmetik. Was sind die konkreten Nachteile dieser Alternativen?
• Warum kann mit Floating Point Arithmetik niemals genau gerechnet werden? Ist die folgende Rechnung mit Floating Point Arithmetik exakt ausführbar? Geben Sie eine Berechung an, die mit Floating Point Arithmetik nicht exakt durchgeführt werden kann.
• Was ist mit der Bezeichnung ULP gemeint, nennen Sie ein Beispiel!
• Wo liegen die Probleme bei der Konvertierung von Dezimal- zu Binärzahlen und zurück?
• Geben Sie ein Beispiel dafür an, dass für die Konvertierung einer Binärzahl im single-precision Modus zur nächstgelegenen (Round to Nearest) Dezimalzahl mindestens eine 9-stellige Signifikante vorgesehen werden sollte.
• Was ist ein Maschinen-Epsilon?
• Nennen Sie Beispiele für absolute und relative Fehler. In welchem Bereichen können diese Fehler liegen?
• Welche der beiden folgenden äquivalenten Formeln würden Sie verwenden? Geben Sie eine Begründung an!
• Wie würden Sie die p,q-Formel auswerten. Begründung?
• Wozu verwendet man ein Guard-Digit?
• Erläutern Sie, was Round-to-Nearest bedeutet!
• Welche Schlüsse ziehen wir aus der Betrachtung von Floating Point Arithmetik für die Implementierung geometrischer Algorithmen?

3. Geometrische Primitiven

• Nennen und erläutern Sie die wesentlichen geometrischen Primitiven. Geben Sie konkret den Halbebenentest der folgenden drei Punkte als Determinante an.
• Geben Sie allgemein den OrientationTest für beliebige Dimensionen als Determinante an.
• Geben Sie ein Beispiel für die Verwendung einer geometrischen Primitive innerhalb eines geometrischen Algorithmus an.
• Geben Sie die induktive Definition des OrientationTests für beliebige Dimensionen und die dazugehörige geometrische Bedeutung an.
• Worauf lässt sich der InCircleTest zurückführen? Beweis!

4. Adaptive Verfahren

• Was ist die Grundidee eines adaptiven Verfahrens?
• Geben Sie ein Beispiel für eine Expansion an. Welche Idee steckt im Allgemeinen hinter den Expansionen?
• Warum betrachten wir in erster Linie nicht-überlappende Expansionen?
• Was verstehen wir unter Exakter Rundung? Welche Probleme treten dabei im Allgemeinen auf?
• Erklären Sie den Algorithmus zur Bestimmung einer Expansion mittels einer Addition. Wie sieht das Ergebnis aus und welche Bedeutung hat dieses Ergebnis?
• Warum ist es wichtig, dass wir mit Binären Zahlen arbeiten? Ist das eine Einschränkung für uns?
• Führen Sie TwoSum an mit den folgenden Zahlen durch.
• Wenn der Rundungsfehler durch unsere Mantissenlänge dargestellt werden kann, was gilt dann für den Betrag des Fehlers? Beweis?
• Erklären Sie die Algorithmen GrowExpansion und ExpansionSum. Was ist die Grundvoraussetzung zur korrekten Arbeit mit Expansionen?
• Erklären Sie die Ergebnisse von TwoProdukt, ExpansionDiff, ScaleExpansion und Compress.
• Bauen Sie ein effizientes Auswertungsschema für den folgenden arithmetischen Ausdruck mit Expansionen auf.
• Erläutern Sie die Unterschiede der Designmethoden I und II anhand eines einfachen arithmetischen Ausdrucks und schätzen Sie den Berechnungsaufwand bis zu einer bestimmten Genauigkeit ab.
• Beweisen Sie, dass die Fehlerabschätzungen der obigen Designmethoden stimmt.
• Was verstehen wir unter Inkrementelle Adaptivität im Zusammenhang mit Expansionen?
• Was verstehen wir unter Lazy Arithmetik? Welche Voraussetzungen müssen dafür erfüllt sein?
• Welchen Ausdruck beschreibt der folgende ExpressionTree? Wie kann man schnell geeignete Grenzen des Intervalls finden?
• Wie führt man die Intervall-Arithmetik mit Lazy Numbers durch? Zeigen Sie, dass die folgende Intervallabschätzung korrekt ist.
• Werten Sie den folgenden Ausdruck aus. Welche Auswertung interessiert uns bei geometrischen Algorithmen im Wesentlichen?
• Welche Vorteile und welche Nachteile können Sie über die Lazy Arithmetik aufzeigen.

5. Exakte Arithmetik

• Was verstehen wir unter Exakter Arithmetik und warum ist diese so wichtig für die geometrischen Algorithmen?
• Beschreiben Sie formal den zusätzlichen Aufwand bei der Verwendung von Integer oder Rationaler Arithmetik gegenüber Floating Point Arithmetik.
• Wie unterschiedlich sind die Laufzeiten bei folgendem arithmetischem Ausdruck a) bei Floating Point Arithmetik b) bei Integer Arithmetik?
• Warum reichen BigInteger und auch BigRationals eigentlich doch nicht aus?
• Was verstehen wir unter Bitkomplexität und wie hoch ist diese beispielsweise beim OrientationTest in 3D?
• Wie lässt sich die Bitkomplexität bei Rationaler Arithmetik eindämmen?
• Was sind algebraische Zahlen und wie kann man mit diesen Zahlen rechnen?
• Geben Sie sie Resultante der folgenden Polynome an.
• Rechnen Sie für zwei gegebene algebraische Zahlen die Summe aus.

6. Unpräzise Kalkulationen

• Definieren Sie formal die Begriffe Robustheit und Stabilität und geben Sie Beispiele dafür an. Definieren Sie den Begriff des Geometrischen Problems.
• Wozu wird ein \alpha-Pseudocircle verwendet?
• Geben Sie Beispiele für \epsilon-Arithmetiken an.
• Erläutern Sie die in der Vorlesung vorgestellten Approximationsprädikate für den OrientationTest und den InCircleTest. a) Formal b) Geometrisch.
• Was ist ein \epsilon-Arithmetik Test bezüglich Approximationsprädikate? Geben Sie ein Beispiel an.
• Erläutern Sie die natürliche Fehlerschranke zur Stabilität bei Algorithmen, die Polynome mit Grad k zur Auswertung von Primitiven unter \epsilon Arithmetik verwenden.
• Erklären Sie die Begriffe \mu(a,b,c) und \mu(a,b,c,d). Erklären Sie das Prädikat T(a,b,c).
• Skizzieren Sie den Beweis, dass der TriangleTest korrekt arbeitet.
• Geben Sie den Algorithmus zur Brerechnung der approximativen konvexen Hülle an.
• Zeigen Sie: \mu(a,b,c,d)=\Phi_c(d,a)-\Phi_c(a,b).
• Was berechnet der InCircleTest mit \epsilon-Arithmetik genau?
• Skizzieren Sie den Algorithmus zur Bestimmung der approximativen Delaunay Triangulation und schätzen Sie die Laufzeit ab.

7. Bestehende Systeme für Geometric Computation

• Nennen Sie die bestehenden Systeme und die Hauptmethode der Auswertung der Primitiven.
• Welche der beschriebenen Methoden erscheint Ihnen am sinnvollsten? Begründung!
• Skizzieren Sie kurz den Standardaufbau eines Systems.
• Welche Eigenschaften sollte ein System haben?