LaTeX-examples/documents/Numerik/Klausur1/Aufgabe2.tex

\section*{Aufgabe 2}
\subsection*{Teilaufgabe a}
\textbf{Aufgabe}
Formulieren Sie einen Algorithmus in Pseudocode zum Lösen des Gleichungssystems
\[Ly = b,\]
wobei $L$ eine invertierbare, untere Dreiecksmatrix ist.

Geben Sie die Formel zur Berechnung von $y_i$ an.

\textbf{Lösung:} TODO! %TODO!

   \begin{algorithm}[H]
        \begin{algorithmic}
        \Require $p \in \mathbb{P}, a \in \mathbb{Z}, p \geq 3$
		\Procedure{CalculateLegendre}{$a$, $p$}
            \If{$a \geq p$ or $a < 0$}\Comment{rule (III)}
				\State \Return $\Call{CalculateLegendre}{a \mod p, p}$ \Comment{now: $a \in [0, \dots, p-1]$}
			\ElsIf{$a == 0$ or $a == 1$}
				\State \Return $a$ \Comment{now: $a \in [2, \dots, p-1]$}
			\ElsIf{$a == 2$} \Comment{rule (VII)}
				\If{$p \equiv \pm 1 \mod 8$}
					\State \Return 1
				\Else
					\State \Return -1
				\EndIf	\Comment{now: $a \in [3, \dots, p-1]$}
			\ElsIf{$a == p-1$} \Comment{rule (VI)}
				\If{$p \equiv 1 \mod 4$}
					\State \Return 1
				\Else
					\State \Return -1
				\EndIf \Comment{now: $a \in [3, \dots, p-2]$}
			\ElsIf{!$\Call{isPrime}{a}$} \Comment{rule (II)}
				\State $p_1, p_2, \dots, p_n \gets \Call{Factorize}{a}$
				\State \Return $\prod_{i=1}^n \Call{CalculateLegendre}{p_i, p}$ 
			\Else \Comment{now: $a \in \mathbb{P}, \sqrt{p-2} \geq a \geq 3$}
				\If{$\frac{p-1}{2} \equiv 0 \mod 2$ or $\frac{a-1}{2} \equiv 0 \mod 2$}
					\State \Return $\Call{CalculateLegendre}{p, a}$
				\Else
					\State \Return $(-1) \cdot \Call{CalculateLegendre}{p, a}$
				\EndIf
			\EndIf
		\EndProcedure
        \end{algorithmic}
    \caption{Calculate Legendre symbol}
    \label{alg:calculateLegendreSymbol}
    \end{algorithm}

\subsection*{Teilaufgabe b}
\subsection*{Teilaufgabe c}