Skip to content
Snippets Groups Projects
Select Git revision
  • 083ccbe05e4dcd859812f8e9d4392def73a50b63
  • main default
  • keycloak-deprecate
  • remove-jwt-easy
  • ci-update
  • v0.1.15
  • v0.1.14
  • v0.1.13
  • v0.1.12
  • v0.1.11
  • v0.1.10
  • v0.1.9
  • v0.1.8
  • v0.1.7
  • v0.1.6
  • v0.1.5
  • v0.1.4
  • v0.1.3
  • v0.1.2
  • v0.1.1
  • v0.1.0
21 results

DummyUserProvider.php

Blame
    • Reiter, Christoph's avatar
      3faa7dd5
      Switch to the OIDC discover protocol for the provider config · 3faa7dd5
      Reiter, Christoph authored
      The goal is to support every OIDC server that implements the discover
      protocol (Keycloak for example). This allows us to fetch all the required
      information at runtime without the user having to keep the settings
      in sync with the used server. The config and public keys are cached for
      one hour.
      
      While in theory this works with non-keycloak it isn't tested yet, and we
      still need keycloak specific settings for the API docs auth because we only
      support keycloak with our frontend web components which we inject into the
      openapi docs.
      
      Fixes #3
      3faa7dd5
      History
      Switch to the OIDC discover protocol for the provider config
      Reiter, Christoph authored
      The goal is to support every OIDC server that implements the discover
      protocol (Keycloak for example). This allows us to fetch all the required
      information at runtime without the user having to keep the settings
      in sync with the used server. The config and public keys are cached for
      one hour.
      
      While in theory this works with non-keycloak it isn't tested yet, and we
      still need keycloak specific settings for the API docs auth because we only
      support keycloak with our frontend web components which we inject into the
      openapi docs.
      
      Fixes #3
    202_quicksort.tex 14.86 KiB
    \section{Quicksort}
    Quicksort ist einer der meist verwendeten Sortieralgorithmen. Die Idee ist wieder das divide-et-impera-Prinzip,
    der Kern des Algorithmus ist die Zerlegung des Arrays, die sogenannte Partition.
    
    \subsection{Partition}
    Für eine Partition eines Arrays $\mathcal{A}$ wählen wir zuerst ein Pivotelement $p$. Nun sortieren wir das Array so,
    dass links von $p$ nur Elemente stehen, die kleiner als $p$ sind, rechts nur Elemente, die größer sind.
    Vorerst nehmen wir als Pivotelement einfach das letzte Arrayelement.
    
    \noindent Die Funktion $\texttt{swap}(a,b)$ im folgenden Pseudocode tauscht hierbei die Werte von $a$ und~$b$.
    
    \begin{algorithm}[H]
      \SetNlSty{texttt}{[}{]}
      \caption{\texttt{partition}($\mathcal{A}$)}
      \KwIn{An unsorted array $\mathcal{A}$ of lenght $n$} 
      \KwOut{The partition of $\mathcal{A}$ wrt. the pivot $p$ and its index $k$}
      $p \leftarrow \mathcal{A}[n-1]$ \;
      $i \leftarrow -1$ \;
      \For{$j \leftarrow 0$ \KwTo $n-2$}{
        \If{$\mathcal{A}[j] ≤ p$}{
          $\texttt{swap}(\mathcal{A}[i+1], \mathcal{A}[j])$ \;
          $i \leftarrow i + 1$ \;
        }
      }
      $\texttt{swap}(\mathcal{A}[i+1], \mathcal{A}[n-1])$ \;
      $i \leftarrow i + 1$ \;
      \KwRet $(\mathcal{A}, i)$
    \end{algorithm}
    
    \subsubsection{Korrektheitsüberlegungen:}
    Was passiert hier? Das Pivotelement $p$ ist das letzte Element von $\mathcal{A}$, siehe Zeile [1].
    Wie oben erwähnt, partionieren wir das Array in
    Elemente, welche kleiner oder gleich $p$ sind, sowie die Elemente, welche größer als $p$ sind.
    Das Pivotelement $p$ dient erstmal nur zum Vergleichen ([4]), bleibt aber
    ansonsten außen vor, bis es in Zeile [7] an seine endgültige Position getauscht wird. 
    
    Die endgültige Position von $p$ wird von dem Index $i$ bestimmt. Dabei erfüllt $i$ zu jedem Zeitpunkt die Bedingung,
    dass alles, was sich links von $i$ befindet ($i$ eingeschlossen), stets kleiner oder gleich $p$ ist (Zeile [4] und [5])! Unter
    den Elementen, die bereits mit $p$ verglichen wurden (siehe Laufindex $j$) nimmt $i$ dabei den maximalen Wert ein (Nach
    Ausführung von Zeile [6], bzw Zeile [8]). Zu beachten ist außerdem, dass durch das rechtzeitige Addieren von $i+1$ nie ein
    Arrayzugriff an undefinierter Stelle geschieht([5]), selbst wenn $i$ mit $-1$ initialisiert wurde([2]).
    
    Als letztes muss nur noch die Rolle des Laufindex $j$ geklärt werden. Definiert in Zeile [3] startet $j$ beim ersten Element
    und geht bis zum vorletzten (also exklusiv $p$). Da pro Schleifendurchgang $i$ um maximal eins inkrementiert werden
    kann, ist $j$ also stets größergleich $i$. Dabei zeigt $j$ an, welche Elemente des Arrays bereits mit $p$ verglichen
    wurden. 
    Findet $j$ mit Zeile $[4]$ ein Element, welches kleiner ist als $p$, wird dieses in den von $i$ markierten Bereich
    vertauscht([5]). Dabei wird eine Sortierung innerhalb einer Partition zwar vielleicht zerstört, aber das ist für die
    Korrektheit des Algorithmus nicht relevant. 
    
    Man kann also feststellen: Das Array ist stets in vier (möglicherweise leere) Teilbereiche unterteilt. Der
    Speicherort von $p$ (Anfangs $n-1$), die noch nicht verglichenen Elemente $j < \text{ index } ≤ n-2$, die kleiner als
    $p$ eingestuften Elemente $0 ≤ \text{ index } ≤ i$ und die als größer als $p$ eingestuften Elemente $i < \text{ index }
    ≤ j$.
    
    Da ein Schleifendurchlauf die Schleifeninvarianten (also der Programmzustand exakt vor dem Inkrementieren von $j$)
    \begin{itemize}
      \item Elemente mit Index $x$, wobei $x ≤ i$, sind kleiner oder gleich $p$, 
      \item Elemente mit Index $x$, wobei $i < x$ und $x ≤ j$, sind größer $p$,
      \item Elemente mit Index $x$, wobei $j < x$, sind noch nicht überprüft,
    \end{itemize}
    erhält, aber die Anzahl der nicht überprüften Elemente pro Schleifendurchlauf um eins schrumpft, terminiert der
    Algorithmus. Mit Zeile [7] wird am Ende noch $p$ an seinen richtigen Platz verschoben, damit eine korrekte Partition
    zurückgegeben werden kann.
    
    %TODO: Bild von partition analog zu Cormen, Figure 7.1
    
    \subsubsection{Laufzeit:}
    Die Schleife in Zeile [3] bis [6] hat an sich eine Laufzeit in $\mathcal{O}(1)$, wird aber $\mathcal{O}(n)$ mal
    aufgerufen. Dadurch ergibt sich, dass die Laufzeit von $T_{\text{p}} = T_\texttt{partition}(\mathcal{A})$ in $\Theta(n)$
    liegt, wobei $n = \texttt{len}(\mathcal{A})$. Es gibt keinen asmyptotischen Unterschied zwischen best/worst-case.
    
    
    \subsection{Quicksort}
    Auf der Basis von $\texttt{partition}$ kann der Sortieralgorithmus $\texttt{quicksort}$ konstruiert werden.
    
    \begin{algorithm}[H]
      \SetNlSty{texttt}{[}{]}
      \caption{\texttt{quicksort}($\mathcal{A}$)}
      \KwIn{An unsorted array $\mathcal{A}$ of length $n$} 
      \KwOut{The same array $\mathcal{A}$, but sorted}
      \eIf{$n > 1$}{
        $(\mathcal{A}, k) \leftarrow \texttt{partition}(\mathcal{A})$ \;
        \KwRet $\texttt{concat}(\texttt{quicksort}(\mathcal{A}[0, \dots, k-1]), [A[k]], \texttt{quicksort}(\mathcal{A}[k+1,
          \dots, n-1])$ \;
      }{
        \KwRet $\mathcal{A}$
      }
    \end{algorithm}
    
    Die Funktion $\texttt{concat}$ ist hierbei eine $\mathcal{O}(1)$-Operation, da sie vom Compiler wegoptimiert werden
    kann. Aber auch als $\mathcal{O}(n)$-Operation wäre sie asymptotisch irrelevant, da $\texttt{partition}$ bereits
    $\mathcal{O}(n)$ Zeit braucht. Sollten wir Arrays auf Grenzen wie $[0,-1]$ aufrufen, so ist damit das leere Array
    gemeint.
    
    \subsubsection{Korrektheitsüberlegungen:}
    Die Korrektheit von $\texttt{quicksort}$ ist schneller einsehbar als die von $\texttt{partition}$. Ist die
    Paritionseigenschaft bezüglich des Pivotelements in Position $k$ erfüllt, so haben wir links und rechts davon echt
    kleinere Unterarrays, welche durch Rekursion sortiert werden (der Basisfall von einem Element ist trivial sortiert). Der
    Algorithmus $\texttt{quicksort}$ terminiert als spätestens nach $n$ rekursiven Aufrufen und arbeitet dabei korrekt.
    
    \subsubsection{Laufzeit:}
    Die allgemeine Rekursionsgleichung für $T_{\text{qs}} = T_{\texttt{quicksort}}$ lautet
    \[
      T_{\text{qs}}(n) = T_{\text{qs}}(m) + T_{\text{qs}}(n-m-1) + T_p(n) + f(n), \text{ wobei } f \in \mathcal{O}(1).
    \]
    Dabei verschwindet $f$ völlig unter $T_p \in \mathcal{O}(n)$.
    Der Parameter $m \in \{0,\dots,n-1\}$ beschreibt dabei die Position des Pivotelements. Die Laufzeit des Algorithmus
    hängt nun stark von $m$ ab:
    
    \paragraph{Best case}
    Im besten Fall treffen wir mit dem Pivotelement $p$ genau den Median von $\mathcal{A}$. Dann haben wir durch $m \simeq
    \frac{n}{2}$ pro Rekursionsschritt eine balancierte Aufteilung des Rekursionsbaums, die Rekursionsgleichung wird zu 
    \[
      T_{\text{qs}}(n) = 2T_{\text{qs}}\left( \frac{n}{2} \right) + T_p(n).
    \]
    Nach dem Hauptsatz der Laufzeitfunktionen ist mit $a=2, b=2$, $f \in \mathcal{O}(n)$ die Laufzeit im best-case damit in
    $\mathcal{O}(n \log n)$.
    
    \paragraph{Worst case}
    Im schlechtesten Fall teilen wir das Array sehr ungünstig: Das Pivotelement ist immer das Maximum oder das Minimum,
    unser Array wird also aufgeteilt in ein $n-1$ großes Array, $m=1$ in jedem Rekursionsschritt.
    Damit haben wir keinen echten Bruchteil pro Rekursionsschritt und das Master-Theorem lässt sich nicht anwenden. Also
    rechnen wir per Hand:
    \begin{align*}
      T_{\text{qs}}(n) & = T_{\text{qs}}(1) + T_{\text{qs}}(n-1) + T_\text{p}(n) \\
      &= 2T_{\text{qs}}(1) + T_{\text{qs}}(n-2) + T_\text{p}(n-1) + T_\text{p}(n) \\
      &= 3T_{\text{qs}}(1) + T_{\text{qs}}(n-3) + T_\text{p}(n-2) + T_\text{p}(n-1) + T_\text{p}(n) \\
      &\qquad \qquad \vdots \\
      &= \underbrace{n T_{\text{qs}}(1)}_{\text{$\in Θ(n)$}}  
      +\underbrace{\sum_{i=1}^n T_\text{p}(i)}_{\text{$\in Θ(n^2)?$}} \\
    \end{align*}
    Dabei gibt uns die Eulersche Summenformel $\sum_{i=1}^n i = \frac{n^2 - n}{2} \in \mathcal{O}(n^2)$ einen Hinweis, in welcher
    Aufwandsklasse der Summenterm liegen könnte. Wir fomalisieren jetzt also die Idee, dass wir $T_{\text{p}}(n)$ durch $c_2 n$ von
    oben und $c_1 n$ von unten abschätzen können, sobald die $n$ groß genug werden.
    
    Betrachten wir also $\sum_{i=1}^k T_\text{p}(i)$. Mit $T_\text{p} \in Θ(n)$ wissen wir, dass $n_0,c_1,c_2$ existieren, sodass
    $c_1 n' ≤ T_\text{p}(n') ≤ c_2 n'$ für alle $n' > n_0$. Dieses $n_0$ ist aber fix, d.h. für ein groß genuges $k$ (und
    $k$ soll später gegen unendlich gehen) betrachten wir also $\sum_{i=n_0}^k T_p(i)$. Hier gilt:
    \[
      \underbrace{c_1 \sum_{i=n_0}^k i}_{\text{$\in Ω(k^2)$}} 
      ≤ \sum_{i=n_0}^k T_p(i) ≤
      \underbrace{c_2 \sum_{i=n_0}^k i}_{\text{$\in \mathcal{O}(k^2)$}}
    \]
    wie uns die Eulersche Summenformel verrät.
    Mit einer beidseitigen Abschätzung haben wir hier also obige Vermutung bewiesen.
    
    
    
    Wir würden nun gerne noch eine average-case Analyse durchführen. Bei einer Gleichverteilung des Inputs ergibt sich
    nämlich auch eine average-case Aufwand von $T_{\text{qs}}^{\text{avg}} \in \mathcal{O}(n \log n)$. Allerdings benötigt eine
    average-case Analyse Annahmen über die Verteilung des Inputs.
    
    Wir analysieren daher eine stark verwandte Variante, den randomisierten Quicksort.
    
    \subsection{Randomisierter Quicksort}
    Grundidee des randomisierten Quicksort Algorithmus ist es, nicht mehr ein fixes Pivotelement in der Partition zu wählen
    (wie bei uns das erste Element), sondern ein zufälliges. Dadurch kann man eine gute
    \emph{durchschnittliche} Performance erreichen. 
    
    Das Wort \emph{durchschnittlich} bekommt hier aber eine andere andere Bedeutung
    als in der average-case-Analyse! In der average-case-Analyse betrachtet man die durchschnittliche Laufzeit über alle
    möglichen Inputs (gewichtet mit der Wahrscheinlichkeit des entsprechenden Inputs), hier hingegen betrachtet man die
    durchschnittliche Laufzeit \emph{über die verschiedenen zufälligen Läufe des nichtdeterministischen Algorithmus}
    (gewichtet nach Wahrscheinlichkeit des entsprechenden Durchlaufs).
    
    Definieren wir zuerst die randomisierte Partition:
    
    \begin{algorithm}[H]
      \SetNlSty{texttt}{[}{]}
      \caption{\texttt{randomized\_partition}($\mathcal{A}$)}
      \KwIn{An unsorted array $\mathcal{A}$ of length $n$} 
      \KwOut{The partition of $\mathcal{A}$ wrt. the randomized pivot $p$ and its post-partitioning-index $k$}
      $i \leftarrow \texttt{random\_uniform}(n-1)$ \;
      $\texttt{swap}(\mathcal{A}[0], \mathcal{A}[i])$ \;
      \KwRet $\texttt{partition}(\mathcal{A})$
    \end{algorithm}
    
    Neu ist also nur das Vertauschen des ersten Elements von $\mathcal{A}$ mit einem durch $\texttt{random\_uniform}$
    zufällig (gleichverteilt) gewählten Elements des Arrays, der Rest ist wie bei $\texttt{partition}$.
    Dabei hat $\texttt{random\_partition}$ die gleichbleibende Laufzeit $T_{\text{rp}} \in Θ(n)$ mit $n =
    \texttt{len}(\mathcal{A})$. Es ist auch nicht schwer einzusehen, das hier $n_0 = 2$ gewählt werden kann.
    
    Der Algorithmus $\texttt{randomized\_quicksort}$ hat dabei genau den gleichen Pseudocode wie $\texttt{quicksort}$, nur
    dass $\texttt{randomized\_partition}$ statt $\texttt{partition}$ in Zeile $[2]$ gerufen wird. Die Laufzeit von
    $\texttt{randomized\_quicksort}$ mit Input der Länge $n$ bezeichnen wir mit $T_{\text{rqs}}(n)$. Wir werden nun zeigen,
    dass $T_{\text{rqs}} \in \mathcal{O}(n \log n)$ liegt.
    
    
    \subsubsection{Herleitung der average case Laufzeit von \texttt{randomized\_quicksort}:} Für die erwartete Laufzeit gilt
    \begin{displaymath}
      T_{\text{rqs}}(n) = \sum_{k=1}^{n-1} P(k) \left( T_{\text{rqs}}(k) + T_{\text{rqs}}(n-k-1) + T_{\text{rp}}(n) \right),
    \end{displaymath}
    wobei $P(k)$ die Wahrscheinlichkeit ist, dass $\texttt{randomized\_partition}(\mathcal{A})$ den Index $k$ liefert.
    Wir nehmen mit $k \in \{0,\dots, n-1\}$ eine Gleichverteilung $P(k) = \frac{1}{n}$ an.
    % TODO: Mehr Details
    \begin{align*}
      T_{\text{rqs}} 
      &= \sum_{k=0}^{n-1} \left( \frac{1}{n} \left( T_{\text{rqs}}(k) + T_{\text{rqs}}(n-k-1) + T_{\text{rp}}(n) \right) \right) \\
      &= \frac{n}{n} T_{\text{rp}}(n) +  \frac{1}{n} \sum_{k=0}^{n-1}  T_{\text{rqs}}(k) + T_{\text{rqs}}(n-k-1) \\
      &= T_\text{rp}(n) + \frac{2}{n} \sum_{k=0}^{n-1} T_{\text{rqs}}(k) \\
      &≤ T_\text{rp}(n) + d + \frac{2}{n} \sum_{k=2}^{n-1} T_{\text{rqs}}(k).
    \end{align*}
    Wobei $d := 2T_\text{rqs}(0) + 2T_\text{rqs}(1) ≤ \frac{2}{n} (T_\text{rqs}(0) + T_\text{rqs}(1))$ ist für $n ≥ 1$.
    
    Wir zeigen nun vermöge einer vollständigen Induktion, dass mit $c = \max\{T_{\text{rq}}(2) + d, 8(d+c_{\text{rp}})\}$ gilt: 
    \[
      T_{\text{rqs}}(n) ≤ c \cdot n \log_2 n \text{ für alle } n ≥ 2.
    \]
    
    Hierbei ist $c_{\text{rp}}$ die Konstante mit welcher $T_\text{rp}(n) ≤ c_{\text{rp}} n$ gilt. Streng genommen
    gilt das erst ab irgendeinem $n_0$, aber den Aspekt vernachlässigen wir hier, um die Beweisstruktur etwas
    übersichtlicher zu gestalten. Es ist bei \texttt{randomized\_partition} aber auch leicht ersichtlich, dass $n_0 = 2$
    gewählt werden kann. 
    
    Induktionsanfang $n=2$: 
    \begin{align*}
      T_{\text{rqs}}(2) 
      &≤ d + T_{\text{rp}}(2) \\
      &≤ c n \log_2 2 
    \end{align*}
    Für $c = \max(T_{\text{rqs}}(1) + T_{\text{rp}}(2), 8 c_{\text{rp}}) \geq T_{\text{rqs}}(1) + T_{\text{rp}}(2)$ ist die
    Abschätzung definitiv erfüllt.
    
    Induktionsschritt $n-1 \mapsto n$: Zu zeigen ist, dass mit mit der Aussage wahr für alle $n \in \{2, \dots, n-1\}$ gilt:
    $T_{\text{rqs}}(n) ≤ c n \log_2 n$. Wir rechnen:
    \begin{align*}
      T_{\text{rqs}}(n) 
      &≤ T_{\text{rp}}(n) + d + \frac{2}{n} \sum_{k=2}^{n-1} T_{\text{rqs}}(k) \\
      &\overset{{\scriptscriptstyle \text{IV}}}{≤} T_{\text{rp}}(n) + d \frac{2c}{n} \sum_{k=2}^{n-1} \cdot k \log_2 k \\
      &\overset{\scriptscriptstyle (*)}{≤} T_{\text{rp}}(n) + d + \frac{2c}{n} \left( (\log_2 n) \left( \frac{n(n-1)}{2} \right) - \frac{\frac{n}{2}(\frac{n}{2}-1)}{2} \right) \\
      &= c(n-1) \log_2 n - c \left(\frac{n}{4} - \frac{1}{2} \right) + T_{\text{rp}}(n) + d \\
      &\overset{\scriptscriptstyle (**)}{≤} c \cdot n \log_2 n.
    \end{align*}
    Betrachten wir zuerst $(**)$ genauer: Das gilt genau dann, wenn 
    \[
      T_\text{rp}(n) + d ≤ c \left( \frac{n}{4} - \frac{1}{2} \right) + \log_2 n.
    \]
    Mit $n ≥ 2$ ist $\log_2 n > \frac{1}{2}$ und $T_\text{rp}(n)$ lässt sich nach Annahme von oben durch $c_\text{rp} n$
    abschätzen.
    Damit vereinfacht sich die Ungleichung auf 
    \[
      4(c_\text{rp} n + d) ≤ c n,
    \]
    was mit obigen $c$ ab $n ≥ 2$ erfüllt ist.
    
    Jetzt gilt es nurnoch, die in Schritt $(*)$ getroffene Abschätzung der Summe $\sum_{k=1}^{n-1} k \log_2 k$ zu beweisen:
    \begin{align*}
      \sum_{k=2}^{n-2} k \log_2 k 
      &≤ \sum_{k=1}^{n-1} k \log_2 k \\
      &= \sum_{k=1}^{\ceil*{\frac{n}{2}}-1} k \underbrace{\log_2 k}_{≤ \log_2 \frac{n}{2}} + \sum_{k=\ceil*{\frac{n}{2}}}^{n-1} k \underbrace{\log_2 k}_{≤ \log_2 n} \\
      &≤ \sum_{k=1}^{\ceil*{\frac{n}{2}}-1} k (\log_2 n - 1) + \sum_{k=\ceil*{\frac{n}{2}}}^{n-1} k \log_2 n \\
      &= \log_2 n \sum_{k=1}^{\ceil*{\frac{n}{2}}-1} k - \sum_{k=1}^{\ceil*{\frac{n}{2}}-1} k + \log_2 n \sum_{k = \ceil*{\frac{n}{2}}}^{n-1} k \\
      &= \log_2 n \underbrace{\sum_{k=1}^{n-1} k}_{= \frac{n(n-1)}{2}} - \underbrace{\sum_{k=1}^{\ceil*{\frac{n}{2}}-1} k}_{\geq \frac{\frac{n}{2}(\frac{n}{2}-1)}{2}} \\
      &≤ (\log_2 n) \left( \frac{n(n-1)}{2} \right) - \frac{\frac{n}{2}(\frac{n}{2}-1)}{2}
    \end{align*}
    
    
    Unsere vollständige Induktion ist damit bewiesen, und wir haben gezeigt, dass die durchschnittliche Laufzeit von $\texttt{randomized\_quicksort}$ in
    $\mathcal{O}(n \log n)$ liegt.