\documentclass[unbewertet]{agisuebung}

\date{03.~Dezember 2024}
%\newcommand{\deadlineDate}{Mittwoch, 06.~November 2024, 12:15~Uhr}
\newcommand{\exerciseNum}{2}
\usepackage{multicol}
\DeclareMathOperator{\preorder}{preorder}
\DeclareMathOperator{\inorder}{inorder}
\DeclareMathOperator{\postorder}{postorder} 
\DeclareMathOperator{\CH}{CH}

% # # # # # # # # # # # # # # # # # # # # # # # # # #
\begin{document} %  # # # # # # # # # # # # # # # # #
% # # # # # # # # # # # # # # # # # # # # # # # # # #


% ### aufgabe
\begin{aufgabe}[Methode der kleinsten Quadrate] % ------------------------------------------------
In dieser Übung implementieren Sie die Methode der linearen kleinsten Quadrate, wie sie in den Vorlesungen beschrieben wurde.  
Insbesondere soll ihr Programm allgemeine Instanzen des Höhenmessproblems ("`Beispiel 2"') lösen.  
Verwenden Sie eine imperative Programmiersprache wie C(++/\#), Java oder Python, nicht ein Computer-Algebrasystem wie Mathematica.  
Für die Matrizenoperationen (Multiplikationen, Inversionen, Lösung eines Systems $Ax = b$, \ldots) können Sie Bibliotheken wie \texttt{Jama} oder \texttt{Eigen} verwenden, jedoch keine Methoden, die direkt eine "`Lösung der kleinsten Quadrate"' liefern.  

Wir interessieren uns für die Höhen von $n$ Punkten: einem Punkt $P_1$ und weiteren $n-1$ Punkten.  
Wir definieren das Koordinatensystem, indem wir die Höhe von $P_1$ auf 0 setzen, das heißt $h_1 = 0$.  
Nun möchten wir die anderen Höhen basierend auf einer Liste von Höhendifferenzmessungen schätzen.  
Wir nehmen an, dass die Messungen Fehler enthalten können, diese Fehler jedoch statistisch unabhängig sind.

\subsection*{Eingabe}

Ihr Programm sollte die folgende Eingabe (über den Standard-Stream wie \texttt{cin}, \texttt{System.in} oder \texttt{input}) akzeptieren.  
Auf der ersten Zeile steht eine einzelne ganze Zahl $n > 1$, die Anzahl der Punkte.  
In der zweiten Zeile steht eine einzelne ganze Zahl $m \ge 1$, die Anzahl der Messungen.  
Danach folgen $m$ Zeilen, von denen jede die folgenden vier Zahlen enthält, getrennt durch Leerzeichen:  

\begin{itemize}
	\item Den Index $i$ des Punktes, \emph{von dem} die Messung stammt.  
	\item Den Index $j$ des Punktes, \emph{zu dem} die Messung durchgeführt wurde.  
	\item Den Wert der Messung, d. h. eine Messung von $h_j - h_i$.  
\end{itemize}

Das Beispiel aus den Vorlesungsfolien würde wie folgt dargestellt:

\begin{center}
\begin{tabular}{|l|}
\hline
\verb!4 !\\
\verb!5 !\\
\verb!1    2    4.1    !\\
\verb!2    3    -7     !\\
\verb!3    4    1.1    !\\
\verb!4    1    1.2    !\\
\verb!4    2    5.4    !\\
\hline
\end{tabular}
\end{center}

\begin{teilaufgabe}
\item Ihr Programm sollte Folgendes ausgeben:  
Eine Schätzung der Höhen $h_2, \ldots, h_n$ nach der Methode der kleinsten Quadrate sowie die "`korrigierten Messungen"'.  

\item Wir möchten nun Genauigkeiten der Messungen bestimmen. 

Starten Sie mit einem bekannten Satz von Höhen.  
Dies impliziert eine vollständige, konsistente Menge von Messungen.  
Ihr Programm aus Teil (a) sollte die korrekten Höhen daraus berechnen können. 

Fügen Sie automatisch Rauschen zu den Messungen hinzu (z. B. einen unabhängig normalverteilten Fehler für jede Messung).
Wie gut kann Ihr Programm die Höhen nun schätzen?  

\item Wir können die Basisvarianzen des Rauschens wie folgt schätzen. Bei $n$ Messungen und $u$ Unbekannten gibt $\sigma_0^2=\frac{v^T v}{n-u}$ die \emph{Basisvarianz} an. Die Varianzen der einzelnen Höhen erlangt man von der Diagonalen der Matrix $\sigma_0^2\cdot(A^T A)^{-1}$.

Für das Beispiel aus der Vorlesung erhalten wir

\[v^T v = \begin{pmatrix}0.1 & 0.2 & 0.2 & 0.1 & 0.1\end{pmatrix} \cdot \begin{pmatrix}0.1 \\ 0.2 \\ 0.2 \\ 0.1 \\ 0.1\end{pmatrix} = 3\cdot 0.1^2 + 2 \cdot 0.2^2 = 0.11 m^2\]

\[\sigma_0^2 = \frac{v^T v}{n - u} = \frac{0.11 m^2}{5-3} = 0.055m^2\]

\[\sigma_0^2\cdot (A^T A)^{-1}= 0.055m^2 \cdot \begin{pmatrix}0.625 & 0.500 & 0.375\\ 0.500 & 1.000 & 0.500\\ 0.375 & 0.500 & 0.625 \end{pmatrix} = \begin{pmatrix}0.0344 & 0.0275 & 0.0206\\ 0.0275& 0.0550 & 0.0275\\ 0.30206 & 0.0275 & 0.0344 \end{pmatrix} m^2.\]

Und damit 
\[\sigma_{h_2}=\sigma_{h_4}=\sqrt{0.0344 m^2}=0.185m\]
\[\sigma_{h_3}=\sqrt{0.0550 m^2}=0.235m\].

Wie gut schätzt das Programm die Basisvarianz Ihrer Messungen? (Sie kennen die Varianz, da Sie das Rauschen selbst hinzugefügt haben.)  

Wie beeinflussen die Varianzen und die Menge der Messungen die Qualität der Lösung?  
\end{teilaufgabe}
\end{aufgabe}

\begin{aufgabe}[Kartenbeschriftungen]
Für jeden Punkt einer gegebenen Menge $P$ sei dessen rechteckiges Label gegeben.
Sei nun $ts(P)$ die maximale Anzahl der gelabelten Punkte im \emph{top slider model}.
Analog seinen $op(P)$ und $tp(P)$ für das \emph{one position} bzw. \emph{two position model} definiert (jeweils auf der oberen Seite). Wir gehen davon aus, dass alle Rechtecke Höhe 1 haben.
\begin{teilaufgabe}
 \item Wie hoch kann das Verhältnis $\frac{ts(P)}{tp(P)}$ werden, wenn alle Rechtecke 
	\begin{itemize}
		\item Quadrate sind?
		\item gleich lange Rechtecke sind?
		\item beliebige Rechtecke sind?
	\end{itemize}
 \item Wie hoch kann das Verhältnis $\frac{tp(P)}{op(P)}$ werden, wenn alle Rechtecke 
	\begin{itemize}
		\item Quadrate sind?
		\item gleich lange Rechtecke sind?
		\item beliebige Rechtecke sind?
	\end{itemize}
\end{teilaufgabe}
\end{aufgabe}


% # # # # # # # # # # # # # # # # # # # # # # # # # #
\end{document} %  # # # # # # # # # # # # # # # # # #
% # # # # # # # # # # # # # # # # # # # # # # # # # #