Theoretische Informatik

1.3 Unimodale Arrays

Definition (unimodale Folge)

Eine Zahlenfolge $a_0,\dots,a_{n-1}$ heißt unimodal, wenn es ein $i$ gibt mit $$ a_0 \lt a_1 \lt \dots \lt a_{k-1} \lt a_k \gt a_{k+1} \gt a_{i+2} \gt a_{n-1} \ . $$ Bildlich gesprochen, wenn die Werte $a_i$ erst bis zu einem Maximum ansteigen und danach wieder abfallen. Salopp gesprochen, wenn die Folge ungefähr so aussieht:

Betrachten wir nun das Optimierungsproblem, das Maximum eines unimodalen Arrays $A$ mit $n$ Elementen zu finden. Natürlich können wir dies mit linearer Suche erreichen, müssten dafür im schlimmsten Fall wieder alle $n$ Positionen durchtesten.

Demo

Auf maximize-unimodular-function.html können Sie interaktiv versuchen, das Maximum einer unimodalen Folge mit möglichst wenig Versuchen zu finden.

Theorem (binäre Suche auf unimodalen Arrays)

Sei $A$ ein unimodales Array mit $n$ Elementen. Wir können das Maximum mit höchstens $ 2 \ceil { \log_2(n)}$ Array-Zugriffen finden.

Beweis. Sei $B$ ein Array aus $n-1$ Elementen, definiert als $$ B[i] := A[i] - A[i-1] \ . $$ $B$ misst sozusagen die "Steigung" von $A$. Beachten Sie, dass $B$ nicht notwendigerweise sortiert ist. Allerdings gilt: wenn das Maximum von $A$ bei $A[k]$ liegt, dann ist $B[i]$ negativ für alle $0 \leq i \leq k-1$ und positiv für alle $k \leq i \leq n-2$. Wir suchen also das erste positive Element in $B$ und können dies mittels binärer Suche mit maximal $\ceil{\log_2 n}$ Zugriffen auf das Array $B$ finden.

Ein Problem ist nur, dass wir ja bereits $2 (k-1)$ Zugriffe auf $A$ brauchen, um $B$ überhaupt erst berechnen zu können. Die entscheidende Einsicht ist hier, dass wir $B$ nicht explizit berechnen müssen: nein, erst wenn der Algorithmus den Wert $B[i]$ abfragt, schlagen wir $A[i]$ und $A[i+1]]$ nach und geben $A[i] - A[i+1]$ zurück. Pro $B$-Zugriff benötigen wir also zwei $A$-Zugriffe. $\square$

Demo

Für $n=88$ zum Beispiel würde obiger Algorithmus im schlimmsten Falle $ \ceil { \log_2 (89)} = 7$ Zugriffe tätigen. Ich behaupte, man kann mit maximal 9 Zugriffen das Maximum bestimmen.

Übungsaufgabe

Üben Sie in Paaren die Maximierung unimodaler Arrays als Spiel: Alice stellt fragen der Form Was ist A[i] und Eve antwortet mit einem Wert (zum Beispiel einer reellen Zahl). Eve muss konsistent antworten, d.h., das Sub-Array aus beantworteten Fragen muss selbst unimodal sein.

Alices Ziel ist es, mit möglichst wenig Fragen das Maximum zu finden; Eve will dies hinauszögern. Spielen Sie es zu zweit mit verteilten Rollen. Achten Sie darauf, welche Strategien für Alice und Eve offensichtlich gut bzw. offensichtlich schlecht sind.

Wir können präzise charakterisieren, wieviele Array-Zugriffe man im schlechtesten Fall benötigt, um das Maximum eines unimodalen Arrays des Länge $n$ zu finden. Die exakte Formel ist leider weniger griffig als beispielsweise $ \ceil {\log_2 (n+1)} $. Es lohnt sich, dieses Problem rigoros zu analysieren, erstens weil Sie hier einen mathematischen Beweis in seiner ganzen Pracht sehen werden; zweitens, weil man daran gut demonstrieren kann, wie man in der Praxis "auf mathematische Beweise kommt", sie also findet, auch wenn man anfangs völlig ahnungslos ist. Es ist also ein exzellentes Beweis für mathematische Beweisführung und auch Beweisfindung Ich werde im Verlauf der Analyse wichtige Stationen mathematischer Beweisfindung fettgedruckt hervorheben.

Maximum in einem unimodalen Array finden - Eine genaue Analyse.

Stellen Sie sich vor, Sie beobachten ein das oben beschriebene Spiel zwischen Alice und Eve und pausieren zu einem bestimmten Zeitpunkt. Alice hat also bestimmte Indizes in $\{1,\dots,n\}$ angefragt und Eve hat geantwortet (es wird nun vorteilhaft sein, die Array-Indizes von $1$ bis $n$ laufen zu lassen).

Stellen Sie die richtigen Fragen. In diesem Falle: Egal ob Alice und Eve im bisherigen Verlauf optimal gespielt haben oder nicht, wieviele weitere Zugriffe benötigt Alice, wenn ab jetzt beide optimal spielen?

Sehen Sie insbesondere, dass die gerade gestellte Frage komplexer ist als die, wieviele Zugriffe Alice bei einem Array der Länge $n$ braucht; sie ist komplexer, weil die Antwort eben nicht nur von $n$ abhängt, sondern auch vom bisherigen Spielverlauf. Paradoxerweise werden Fragen oft einfacher zu beantworten, wenn man sie (auf die richtige Weise) verallgemeinert und dadurch scheinbar komplexer macht.

Welche Information brauchen Sie? Zur Beantwortung der oben gestellten Frage brauchen wir als Information die Länge $n$ des Arrays und den bisherigen Spielverlauf. Also zum Beispiel

Warten Sie! Enthält obiges Bild wirklich die gesamte Information, um den Spielverlauf zu rekonstruieren? Nein! Hierfür bräuchten wir die zeitliche Abfolge der Anfragen. Eine vollständige Beschreibung des Spielverlaufs wäre also eine Folge von Indizes $$ i_1, i_2, \dots, i_k \in \{1,\dots,n\} \ , $$ welche die von Alice gestellten Anfragen darstellt, zusammen mit einer Reihe von reellen Zahlen $$ r_1, r_2, \dots, r_k \in \R \ , $$ welche Eves Antworten darstellen, sodass $A[i_1] = r_1, \dots, A[i_k] = r_k$ und die Folge $r_1,\dots,r_k$ selbst unimodal ist.

Das obige Bild stellt dies fast dar, allerdings nur fast, da es die Reihenfolge ignoriert. Müssen wir aber die Reihenfolge überhaupt kennen, um die Frage zu beantworten: Wieviele weitere Zugriffe benötigt Alice, wenn ab jetzt beide optimal spielen? Für die Beantwortung dieser Frage ist die Reihenfolge, in welcher Alice die in der Vergangenheit liegenden Zugriffe getätigt hat, irrelevant. Vergleichen Sie es mit einem Schachspiel:

Tarrasch vs. Euwe, Bad Pistyan (1922). Quelle: Wikipedia

Um zu entscheiden, welcher Zug für Weiß nun optimal ist, ist es irrelevant, wie Tarrasch und Euwe zu dieser Position gelangt sind. Wichtig ist einzig und allein die Position. Daher: ja, das obige Bild mit den roten Balken ist ausreichend, um unsere Frage zu beantworten.

Es ist sogar zuviel Information. Ich behaupte, wichtig sind allein die im unteren Bild stark roten Balken; die blassen können wir ignorieren:

In der Tat: das Maximum liegt sicherlich innerhalb der drei stark roten Balken. Eine optimal spielende Alice wird von nun an nie mehr außerhalb dieses Bereichs auf das Array zugreifen. Wir können also die blass roten Balken vergessen und uns nur die Position und Höhe der stark roten merken:

Im nächsten Schritt wird Alice einen Index zwiscehn $L$ und $L+a+b$ anfragen und die Antwort mit $A[L+a]$ vergleichen. Alice muss sich also nicht nur die Positionen $L, L+a, L+a+b$ merken, sondern auch die Werte des Arrays an diesen Positionen. Für die Beantwortung der Frage Wieviele weitere Zugriffe benötigt Alice? spielen die genauen Werte allerdings keine Rolle! Für einen optimalen Spielverlauf ist nur die Ordnung der Werte entscheidend (also welche größer und welche kleiner sind als andere); da Eve mit reellen Zahlen spielt, kann sie sicherlich immer eine weitere Zahl zwischen zwei gegebenen finden. Wir stellen also fest: um den optimalen weiteren Spielverlauf zu bestimmen, sind die genauen Werte irrelevant; wir müssen nur kennen $L, L+a, L+a+b$ und natürlich wissen, dass $$ A[L] \lt A[L+a] \gt A[L+a+b] $$ gilt. Ja nicht einmal $L$ müssen wir uns merken. Kenntnis der natürlichen Zahlen $a$ und $b$ reicht völlig aus, um die optimale Anzahl weiterer Zugriffe zu bestimmen.

Reduzieren Sie Information! Die Antwort auf die Frage Wieviele weitere Zugriffe benötgit Alice, wenn von nun an beide optimal spielen? hängt nur von den Zahlen $a$ und $b$ ab.

Führen Sie neue Notation ein! Definieren wir $Q(a,b)$ als die Anzahl von weiteren Zugriffen, die Alice benötigt, um das Maximum der unimodalen Funktion zu bestimmen, wenn beide optimal spielen und $A[L] \lt A[L+a] \gt A[L+a+b]$ gilt. Wie oben argumentiert, hängt das nicht von $L$ ab, wir können also $Q(a,b)$ statt $Q(L,a,b)$ schreiben.

Erinnern wir uns an die ursprüngliche Frage: wieviele Zugriffe brauchen wir, um das Maximum eines unimodalen Arrays $A[1\dots n]$ zu finden? In diesem Szenario gibt es kein $a$ und kein $b$, da Alice noch gar keine Fragen gestellt hat. Sei also $k \in \{1,\dots,n\}$ der erste Index, den Alice anfragt. Da per Konvention $A[0] = A[n+1] = \infty$ gilt, haben wir $$ A[0] \lt A[k] \gt A[n+1] $$ und können nun $L := 0, a := k, b := n+1-k$ setzen und wissen, dass Alice von nun an (wenn beide optimal spielen) weitere $Q(k,n+1-k)$ Zugriffe benötigt. Um die Gesamtzahl zu minimieren, muss Alice den Parameter $k$ optimieren und benötigt daher insgesamt $$ 1 + \min_{1 \leq k \leq n} Q(k,n+1-k) $$ Zugriffe. Das $1 + $ beszieht sich auf den ersten Zugriff, den auf den Index $k$. Wenden wir uns nun wieder unserer Funktion $Q(a,b)$ zu und versuchen, sie zu verstehen.

Sammeln Sie einfache Fakten. Was wissen wir über $Q(a,b)$?

Nun, zum Beispiel $Q(1,1) = 0$. Klar: wenn $a=b=1$ und $A[L] \lt A[L+1] \gt A[L+2]$, dann liegt das Maximum des Arrays beim Index $L+1$; keine weiteren Fragen nötig.
Links-Rechts-Symmetrie: $Q(a,b) = Q(b,a)$. Die Komplexität ändert sich nicht, wenn wir Array und angefragte Indizes einfach von rechts nach links umkehren.
Monotonie: $Q(a,b) \leq Q(a+1,b)$. Klar: größere Intervalle können es für Alice nicht einfacher machen.

Spielen Sie selbst! Lassen Sie uns kurz in die Rollen von Alice und Eve schlüpfen. Angenommen, Alice fragt einen Index $L+c$ an mit $c \lt a$:

Eves Antworten fallen in zwei Kategorien. Entweder ist $A[L+c] \gt A[L+a]$ oder $A[L+c] \lt A[L+a]$. Wie soll Eve nun antworten?

Falls $A[L+c] \gt A[L+a]$ gilt, dann können wir von nun an $A[L+a+b]$ vergessen und mit den drei Indizes $L, L+c, L+a$ weiterspielen. Alice benötigt also noch $Q(c, a-c)$ weitere Zugriffe.
Fals $A[L+c] \lt A[L+a]$ gilt, dann können wir $A[L]$ vergessen und mit den Indizes $L+c, L+a, L+a+b$ weiterspielen. Alice benötigt also noch $Q(a-c, b)$ weitere Zugriffe.

Wie sollte Eve also antworten? In jedem so, dass sie das größere von $Q(c, a-c)$ und $Q(a-c, b)$ bekommt. Wegen unseren "einfachen Fakten" Links-Rechts-Symmetrie und Monotonität gilt nun $$ \max ( Q(c,a-c), Q(a-c,b)) = \max (Q(a-c, c), Q(a-c, b)) = Q(a-c, \max(b,c)). $$

In Worten: Alice hat zwei Intervalle mit Längen $a,b$. Durch den Zugriff auf $A[L+c]$ zerlegt Alice das erste Intervall und erhält somit drei Intervalle mit Lägen $c, a-c,b$. Eve kann sich nun entscheiden, ob das Spiel auf den ersten beiden Intervallen fortgesetzt wird, also $c,a-c$ oder auf den letzten beiden, also $a-c,b$. Welche Entscheidung optimal ist, hängt nur davon ab, ob $c$ oder $b$ größer ist. Ein Spielzug lässt sich nun also wie folgt darstellen: Gegeben ein Paar $(a,b)$, zum Beispiel $(11, 4)$, zerlegt Alice die erste Zahl und erhält ein Tripel, zum Beispiel: $ (3, 8, 4)$. Eve kann sich nun für das erste Paar $ (3,8)$ oder das zweite Paar $ (8,4)$ entscheiden und nimmt natürlich das "größere", hier also $ (8,4)$. Als Tabelle:

Alice zerlegt $(11,4)$ in:	Eve wählt als neues Paar:
$(10, 1, 4)$	$(10, 1)$
$(9, 2, 4)$	$(9, 2)$
$(8, 3, 4)$	$(8, 3)$
$(7, 4, 4)$	$(7, 4)$
$(6, 5, 4)$	$(6, 5)$
$(5, 6, 4)$	$(5, 6)$
$(4, 7, 4)$	$(4, 7)$ oder $ (7,4) $, spielt keine Rolle
$(3, 8, 4)$	$(8, 4)$
$(2, 9, 4)$	$(9, 4)$
$(1,10, 4)$	$(10, 4)$

Es sollte klar sein, dass die letzten drei Zeilen für Alice suboptimal sind, da wegen Monotonie $Q(10,4) \geq Q(9,4) \geq Q(8,4) \geq Q(7,4)$ gilt. Alice darf $a$ also in $c + (a-c)$ zerlegen, wie sie will, sollte aber tunlichst $c \geq b$ wählen. Was haben wir aus unserem Beispielzug gelernt?

$$ Q(11,4) = 1 + \min \{ Q(10,1), Q(9,2), Q(8,3), Q(7,4), Q(6,5), Q(5,6), Q(4,7) \} \ . $$

Doch halt! Wir haben etwas vergessen! Alice kann natürlich auch $A[L+a+c]$ anfragen, also das rechte Intervall zerlegen:

Alice zerlegt das rechte Interval und erhält drei Intervalle mit Längen $ (a, c, b-c)$. Welches Paar wählt Eve? Das hängt davon ab, ob $a$ oder $b-c$ größer ist. Führen wir eine Konvention ein: $a \geq b$, das linke Interval ist mindestens so groß wie das rechte; so sieht es auf den Bildern ja auch aus. Dann gilt natürlich auch $b-c \leq b \leq a$ und somit $b-c \leq a$ und $ Q(a,c) \geq Q(b-c, c) = Q(c,b-c$. Eve wählt also das erste Paar: $ (a, c)$.

Ich behaupte, dass dieser Zug von Alice nicht optimal ist. Was, wenn Sie statt $L+a+c$ den Index $L+a-c$ angefragt hätte? Dann hätte sie das Tripel $ (a-c, c, b) $ bekommen und Eve hätte sich zwischen $ (a-c, c)$ und $ (c, b)$ entscheiden müssen. Beide Paare sind für Alice besser kleiner als $a,c$: \begin{align*} Q(a-c,c) & \leq Q(a,c) \tag{Monotonie} \\ Q(c,b) & = Q(b,c) \leq Q(a,c) \tag{Symmetrie, Monotonie und Konvention $a \geq b$} \end{align*} Wir folgern: optimalerweise zerlegt Alice immer das größere der beiden Intervalle. Wir können nun alles zusammenfassen in folgender rekursiver Formel:

\begin{align*} Q(a,b) & = \begin{cases} 0 & \textnormal{ if $a = b= 1$,} \\ 1 + \min_{1 \leq c \leq a-1} Q(a-c, \max (c,b)) & \textnormal { else, if $a \geq b$, } \\ Q(b,a) & \textnormal{else.} \end{cases} \end{align*}

Nochmal in Worten und in einem Beispiel: in jedem Schritt ist es ziemlich offensichtlich, welches der optimale Schritt für Eve ist; wir ersetzen die Spielerin Eve also durch eine starre Regel und haben nun ein Spiel mit nur einer Spielerin: Alice. Es ist also ein Solitaire-Spiel, in welchem Alice in Zahlenpaar $(a,b)$ gegeben hat und auf weitere, kleinere Paare "ziehen" kann, bis sie das Paar $(1,1)$ erreicht hat. Ein Spielverlauf, startend von $(11,4)$, könnte also folgendmaßen aussehen:

$$ (11,4) \stackrel{(5,6,4)}{\longrightarrow} (5,6) \stackrel{(5,1,5)}{\longrightarrow} (5,1) \stackrel{(2,3,1)}{\longrightarrow} (2,3) \stackrel{(2,1,2)}{\longrightarrow} (2,1) \stackrel{(1,1,1)}{\longrightarrow} (1,1) $$ und Alice braucht somit 5 Schritte. Geht es better? Versuchen wir es noch einmal. $$ (11,4) \stackrel{(4,7,4)}{\longrightarrow} (7,4) \stackrel{(4,3,4)}{\longrightarrow} (4,3) \stackrel{(3,1,3)}{\longrightarrow} (3,1) \stackrel{(1,2,1)}{\longrightarrow} (2,1) \stackrel{(1,1,1)}{\longrightarrow} (1,1) $$ Auch wieder 5 Schritte.

Übungsaufgabe Berechnen Sie $Q(a,b)$ per Hand für kleinere Werte von $a,b$, zum Beispiel für $a,b \leq 5$ oder wie weit Sie halt kommen. Verwenden Sie die obige rekursive Formel.

Übungsaufgabe Schreiben Sie ein Elm-Programm (oder Java-Programm), das $Q(a,b)$ rekursiv berechnet. Überprüfen Sie, ob in der Tat $Q(11,4) = 5$ gilt, oder ob es eine Zugreihenfolge gibt, die besser ist als die, die wir oben gefunden haben.

Hinweis. Mit List.range 1 (a-1) erzeugen Sie die Liste [1, 2, ..., a-1]. Mit List.map können Sie dann den Ausdruck $Q(a-c, \max(c,b))$ für jedes $c$ in der Liste berechnen. List.minimum berechnet Ihnen das Minimum einer Liste, gibt allerdings ein Maybe Int zurück (das ist Elm-spezifisch, weil ja die leere Liste kein Minimum hat); in unserem Fall wissen Sie mit Sicherheit, dass die Liste nicht leer ist, dürfen also irgendwas wie Maybe.withDefault verwenden:

Maybe.withDefault 100 (Just 2)                                
2
Maybe.withDefault 100 Nothing                                
100

Lesen Sie erst weiter, wenn Sie die beiden obigen Übungen gemacht haben oder sich ganz sicher sind, dass Sie die nicht machen wollen.

Analyse, Fortsetzung. Da die rekursive Formel $Q(a,b) = 1 + \min_{1 \leq c \leq a-1} Q(a-c, \max (c,b)) $ doch eher kompliziert wirkt und uns nicht direkt eine Lösung einfällt, rechnen wir einfach mal $Q(a,c)$ für kleine Werte aus. Das heißt, wir legen eine Tabelle an, beschriften die Achsen mit $a$ und $b$ und schreiben die Werte von $Q(a,b)$ rein:

Die Werte $Q(a,b)$

Gleiche Werte eingefärbt

Die Ecken der Farbklassen.

Die Ecken einer Farbklasse kommen in Paaren, z.B. $(8,5)$ und $(5,8)$ für die Farbklasse 4. Das ist nicht überraschend, haben wir doch bereits früh die Symmetrie $Q(a,b) = Q(b,a)$ bemerkt. Die Menge $$ \{ (a,b) \ | \ Q(a,b) \leq 4\} \ , $$ also die Menge aller eingefärbten Zellen, schaut aus wie zwei übereinandergelegte Rechtecke, nämlich der Dimensionen $8 \times 5$ und $5 \times 8$. Und in der Tat: Sehen wir uns diese Dimensionen, bzw. die Koordinaten der Eckpunkte genauer an: $$ (1,1), (2,1), (3,2), (5,3), (8,5) $$ Vielleicht "klingelt" es jetzt bei Ihnen. Dies sind die berühmten Fibonacci-Zahlen $$ 0, 1, 1, 2, 3, 5, 8, 13, ... $$ mit dem rekursiven Bildungsgestzt $$ F_n = \begin{cases} 0 & \textnormal{ if $n=0$,}\\ 1 & \textnormal{ if $n=1$,}\\ F_{n-1} + F_{n-2} & \textnormal{ if $n\geq 2$.}\\ \end{cases} $$ Jetzt sind wir bereit für den vorletzten Schritt bei der Suche nach einem Beweis.

Formulieren Sie eine Vermutung. In unserem Falle heißt die Vermutung: die "Ecken" unserer Wertebereiche haben die Koordinaten $ (F_n, F_{n-1})$ bzw. $ (F_{n-1}, F_n)$. Um das mathematisch ganz präzise auszudrücken, müssen wir noch den Zusammenhang zwischen $n$ und dem "Wert" $Q(a,b)$ herausfinden. Zum Beispiel hat die eine Ecke von $ Q(a,b) \leq 4$ die Koordinaten $ (8,5) = (F_6, F_5$. Wir sind nun bereit, eine Vermutung zu formulieren.

Theorem. Sei $a \geq b \geq 1$. Dann gilt $Q(a,b) \leq k$ genau dann, wenn $a \leq F_{k+2}$ und $b \leq F_{k+1}$ ist.

Nun kommt der letzte Schritt bei der Suche nach einem Beweis: der Beweis selbst.

Beweis. Wir einem "genau dann, wenn"-Satz müssen wir immer beide Richtungen beweisen. Meistens ist eine davon einfacher. Wir beginnen mit:

Behauptung 1. Wenn $a \leq F_{k+2}$ und $b \leq F_{k+1}$, dann ist $Q(a,b) \leq k$. In anderen Worten, Alice hat eine Strategie, mit höchstens $k$ Abfragen das Maximum zu finden.

Dies ist die "einfache" Richtung, weil wir hier konkret eine Strategie für Alice angeben können.

Beweis der Behauptung 1. Wir verwenden Induktion über $k$.

Induktionsbasis.Wenn $k=0$ ist, so garantiert die Voraussetzung, dass $a \leq F_2, b\leq 1$. Da $F_2 = F_1 = 1$ und $a, b \geq 1$, so gilt nun $a = b = 1$. In diesem Falle wissen wir bereits, dass $Q(a,b)=0$ gilt. Alice hat das Maximum bereits gefunden: es liegt bei $A[L+1]$.

Induktionsschritt. Sei nun $k \geq 1$. Alice kann das linke Intervall $ \{L, L+1, \dots, L+a\}$ beliebig zerlegen, sagen wir in zwei Intervalle der Längen $F_{k+1}$ und $a-F_{k+1}$. Wir erhalten drei Intervalle der Längen $F_{k+1}, a-F_{k+1}, b$. Da $b \leq F_{k+1}$, ist das erste Paar mindestens so groß wie das zweite; Eve wählt laso $F_{k+1}, a - F_{k+1}$. Für die zweite Koordinate gilt $a - F_{k+1} \leq F_{k+2} - F_{k+1} = F_k$ und somit, wegen Monotonie: $$ Q(F_{k+1}, a - F_{k+1}) \leq Q(F_{k+1}, F_k) \ . $$ Nun wenden wir die Induktionshypothese für $k-1$ statt $k$ an und schlussfolgern, dass $Q(F_{k+1}, F_k) \leq k-1$ gilt. Alice kann das Maximum nun also mit $k-1$ weiteren Zugriffen finden; sie tätigt also insgesamt $k$ Zugriffe.

Behauptung 2. Wenn $Q(a,b) \leq k$ gilt und $a \geq b$, dann ist $a \leq F_{k+2}$ und $b \leq F_{k+1}$.

Dies ist die "schwierigere" Richtung, weil wir hier alle möglichen Züge von Alice berücksichtigen müssen.

Beweis der Behauptung 2. Wir verwenden wiederum Induktion über $k$.

Induktionsbasis.Wenn $k=0$ ist, so ist $Q(a,b) \leq 0$ nach Voraussetzung. Dies gilt ausschließlich für $a = b = 1$ und somit gilt auch $a \leq F_2, b \leq F_1$.

Induktionsschritt. Sei nun $k \geq 1$. Die Herausforderung ist, dass wir nicht wissen, wie Alice das linke Interval zerlegt (wie oben argumentiert, können wir davon ausgehen, dass eine optimal spielende Alice immer das größere Intervall zerlegt). Alice zerlegt das linke Intervall also in zwei Intervalle der Größe $c$ und $a-c$ und erhält das Tripel $c, a-c, b$. Eve wählt nun das schlechtere der Paare $ (c,a-c)$ und $ (a-c, b)$, also jenes, für das $Q$ größer wird. Nach Annehme verwendet Alice insgesamt höchstens $k$ Zugriffe; nach dem Zugriff auf $A[L+c]$ also noch $k-1$ weitere. Dies heißt nun \begin{align} \max ( Q(c, a-c), Q(a-c, b) ) \leq k-1 \ . \label{ineq-unimodal-Q-max} \end{align} Wenn ein Maximum höchstens $k-1$ ist, dann müssen beide Termine höchstens $k-1$ sein. Insbesondere $$ Q(c,a-c) \leq k-1 \ . $$ Wir wollen nun die Induktionshypothese auf $c, a-c$ anwenden. Ein Problem ist, dass wir nicht wissen, ob $c$ oder $a-c$ größer ist. Dennoch: nach Induktionshypothese ist das größere höchstens $F_{k+1}$ und das kleinere höchstens $F_{k}$, also \begin{align*} \min (c, a-c) & \leq F_{k} \max (c, a-c) & \leq F_{k+1} \ . \end{align*} Wenn wir die beiden Ungleichungen addieren, erhalten wir $$ \min (c, a-c) + \max(c, a-c) \leq F_k + F_{k+1} = F_{k+2} \ . $$ Auf der linken Seite addieren wir das Minimum und das Maximum, also einfach beide Werte, und erhalten $a$. Also folgern $a \leq F_{k+2}$, den ersten Teil unserer Behauptung.

Wir ziehen wir nun das zweite Argument aus $ (\ref{ineq-unimodal-Q-max}) $ raus und erhalten $$ Q(a-c, b) \leq k-1 \ . $$ Wir wenden wiederum einen Induktionsschritt an und erhalten $max(a-c, b) \leq F_{k+1}$, woraus sofort $b \leq F_{k+1}$ folgt.

Wir haben nun $a \leq F_{k+2}$ und $b \leq F_{k+1}$, wie verlangt. $\square$

Mit Behauptung 1 und Behauptung 2 haben wir beide Richtungen des "genau dann, wenn"-Satzes gezeigt und beschließen somit den Beweis des Theorems. $\square$

Ein Schlussstein fehlt noch. In dem obigen Theorem betrachten wir das Szenario, dass Alice mit den drei "stark roten" Array-Positionen $L, L+a, L+a+b$ arbeitet. Wie soll Alice allerdings am Anfang verfahren, wenn sie von dem Array $A[1\dots n]$ noch keinen einzigen Index angefragt hat?

Bezeichnen wir mit $a$ den ersten Index, den Alice anfragt. Alice kennt nun also drei Werte: $A[0] = -\infty$ und $A[n+1] = -\infty$ per Konvention und $A[a]$ durch den ersten Zugriff, den sie getätigt hat. Alice verfügt nun also über zwei Intervalle der Längen $a$ und $n+1-a$ und benötigt daher bei optimalem Spiel $Q(a, n+1-a)$ Schritte.

Wie soll Alice nun den ersten Index $a$ wählen? Wenn $n+1$ selbst eine Fibonacci-Zahl $F_{k+2}$ ist, dann könnte sie $a = F_{k+1}$ wählen und danach $$ Q(a, n+1-a) = Q(F_{k+1}, F_{k+2} - F_{k+1}) = Q(F_{k+1}, F_{k}) = k-1 $$ weitere Zugriffe tätigen; wir haben hier das obige Theorem verwendet. Zusammen mit dem ersten Zugriff, den auf $A[a]$, tätigt Alice genau $k$ viele. Daher ergibt sich folgende Vermutung / folgendes Theorem.

Theorem Sei $A$ ein unimodales Array aus $n$ Zahlen und sei $k$ die kleinste natürliche Zahl, für die $n+1 \leq F_{k+2}$ gilt. Dann kann Alice das Maximum von $A$ mit $k$ Zugriffen finden, und dies ist im Worst-Case auch optimal.

Beweis. Dass Alice es kann, haben wir schon (fast) gesehen. Alice fragt $A[F_{k+1}]$ an und erhält somit zwei Intervalle der Längen $F_{k+1}$ und $n+1 - F_{k+1} \leq F_{k+2} - F_{k+1} = F_k$ und kann nun das vorherige Theorem anwenden und insgesamt $k$ Anfragen tätigen.

Um zu zeigen, dass Alice im Worst-Case auch tatsälich $k$ Anfragen benötigt, drehen wir die Dinge um: wir nehmen an, dass es Alice mit $k$ Anfragen schafft und zeigen, dass $n+1 \leq F_{k+2}$ gelten muss. Sei nun $c$ der erste Index, den Alice anfragt. Damit erhält sie zwei Intevalle der Längen $c$ und $n+1-c$. Da wir nicht wissen, ob $c$ oder $n+1-c$ größer ist, führen wir zwei neue Bezeichner ein: $a := \max(c, n+1-c)$ und $b := \min(c, n+1-c)$. Jetzt gilt auf jeden Fall $a \geq b$ und $a + b = n+1$. Da Alice $k-1$ weitere Zugriffe macht, also $Q(a,b) \leq k-1$, gilt nach Theorem $a \leq F_{k+1}, b \leq F_{k}$ und somit $n+1 = a + b \leq F_{k+1} + F_k = F_{k+2}$, wie behauptet. $\square$

Quantitative Analyse

Was heißt das nun quantitativ? Wie verhält sich die optimale Anzahl von Anfragen in Abhängigkeit von $n$? Hierfür müssen wir untersuchen, wie groß $F_{k}$ ist. Beachten Sie, dass "$F_k$ ist groß" gut für Alice ist: sie kann dann auch große unimodale Arrays mit höchstens $k$ Zugriffen maximieren. Ganz Allgemein ist es in der Mathematik unglaublich hilfreich, gewisse Größen "emotional" zu besetzen, also zum Beispiel "großes F_{k} ist gut" oder "großes $Q(a,b)$ ist schlecht" oder "große Intervall-Längen sind schlecht". Wenn Sie "emotional" wissen, was gut ist und was schlecht, dann werden Sie Ungleichungszeichen wie $\geq$ und $\leq$ nicht verwechseln.

Wir müssen also die Größe von $F_k$ abschätzen, im Prinzip eine Formel für $F_k$ entwickeln. Auch hier werde ich wieder extrem detailliert vorgehen und Sie auch an der Beweisfindung teilhaben lassen. Als erstes will ich eine obere Schranke für $F_k$ finden, also argumentieren, dass die Fibonacci-Zahlen nicht allzu schnell wachsen. Als eine erste Beobachtung haben wir $$ F_k = F_{k-1} + F_{k-2} \leq F_{k-1} + F_{k-1} \ , $$ weil $F_{k-2} \leq F_{k-1}$ (warum?). Das heißt also, die Fibonacci-Zahlen wachsen in jedem Schritt um höchstens das doppelte.

Lemma. $F_k \leq 2^k$.

Übungsaufgabe Beweisen Sie das Lemma. Führen Sie möglichst rigoros und detailliert einen induktiven Beweis durch.

"Lemma". $F_k \geq 2^{k/2}$.

Übungsaufgabe (1) "Beweisen" Sie das Lemma mithilfe von Induktion; (2) scheitern Sie, denn das Lemma ist so nicht korrekt; (3) korrigieren Sie das Lemma in sinnvoller Weise; (4) beweisen Sie rigoros die korrigierte Version.

Übungsaufgabe Verallgemeinern Sie. Statt $2$ und $\sqrt{2}$: Was ist die kleinste Zahl $a$, für die Sie $F_k \leq a^k$ beweisen können? Was ist die größte Zahl $a$, für die Sie $F_k \geq a^k$ oder zumindest $F_k \geq C \cdot a^k$ beweisen können?

Spoiler alert. Lesen Sie erst weiter, wenn Sie die letzten drei Übungsaufgaben gelöst haben oder zumindest signifikant Zeit in sie investiert haben.

Manchmal kann es nütztlich sein, mathematische Strenge ein wenig fallen zu lassen und Dinge zu beweisen, die zwar falsch aber eben fast wahr sind. Wir haben weiter oben zum Beispiel Theoreme der Form $F_k \leq a^k$ bzw. $F_k \geq C \cdot a^k$ bewiesen. Können wir $F_k = a^k$ beweisen? Sicherlich nicht, denn die Behauptung $$ \textcolor{red}{\exists a \gt 1 \ \forall k \in \N: \quad F_k = a^k } $$ ist schlicht falsch. Denn angenommen, sie würde gelten, dann hätten wir auch $$ \textcolor{red} {\frac{F_{k+1}}{F_k} = a } \ , $$ das heißt, aufeinanderfolgende Fibonacci-Zahlen müssten immer das gleiche Verhältnis aufweisen, was mit Beispielen wie $ \frac{8}{5} \ne \frac{13}{8}$ einfach zu widerlegen ist. Dennoch: tun wir mal so, als wüssten wir das alles nicht und versuchen, ein entsprechendes Theorem einfach mal zu beweisen.

"Theorem" (falsch) Es gibt ein $a \gt 1$, sodass $F_k = a^k$ für alle $k \in \N$ gilt.

Beweis. Wir beweisen das Theorem durch Induktion über $k$. Sei $k \geq 2$. Dann gilt \begin{align*} F_k & = F_{k-1} + F_{k-2} \tag{Definition der Fibonacci-Zahlen} \\ & = a^{k-1} + a^{k-2} \tag{Induktionshypothese} \\ & \stackrel{!}{=} a^k \ . \end{align*} Die Gleichung $a^{k-1} + a^{k-2} = a^k$ stimmt genau dann, wenn $$ a + 1 = a^2 \ , $$ also $a^2 - a - 1 = 0$. Dies ist eine quadratische Gleichung und besitzt zwei Lösungen: \begin{align*} \phi & = \frac{1 + \sqrt{5}}{2} \approx 1.618 \, \\ \psi & = \frac{1 - \sqrt{5}}{2} \approx -0.618 \ . \\ \end{align*} Welches ist nun das "richtige"? Schauen wir in unser "Theorem": wir suchen ein $a \gt 1$, also ist $\phi$ das "richtige", also $F_k = \phi^k$. $\square$

Das Theorem ist natürlich falsch. Aber wo im Beweis haben wir einen Fehler gemacht?

Übungsaufgabe Finden Sie den Fehler im Beweis.

Ganz klar: wir haben die Induktionsbasis vergessen. Wir hätten zeigen müssen, dass $F_0 = a^0$ und $F_1 = a^1$ gelten, und dies haben wir versäumt. Aber immerhin: die Zahlenfolge $A_0, A_1, A_2, A_3, \dots $ mit $A_k := \phi^k $ besitzt, genau wie die Fibonacci-Folge, die Eigenschaft, dass $A_{k+2} = A_{k+1} + A_k$.

Definition. Eine Zahlenfolge $A_0, A_1, A_2,\dots$ heißt Fibonacci-artig, wenn $A_{k+2} = A_{k+1} + A_k$ für alle $k \in \N$ gilt.

Beispiele für Fibonacci-artige Zahlenfolgen:

$1, \phi, \phi^2, \phi^3, \dots$ für $\phi \approx 1.618$ wie oben;
$1, \psi, \psi^2, \psi^3, \dots$ für $\psi \approx -0.618$ wie oben;
$F_0, F_1, F_2, F_3, \dots$, die Fibonacci-Zahlen selbst;
$0,0, 0, 0, \dots$

Dies sind natürlich nicht alle. Wir können Folgen gliedweise addieren. Definieren wir zum Beispiel eine Folge $A_0, A_1, A_2, \dots,$ mittels $A_k := \phi^k + \psi^k$. Dann gilt

\begin{align*} A_{k+2} & = \phi^{k+2} + \psi^{k+2} \\ & = \phi^{k+1} + \phi^{k} + \psi^{k+1} + \psi^{k} \\ & = A_{k+1} + A_{k} \ . \end{align*}

Voilà, wir bekommen eine neue Fibonacci-artige Folge. Wir können die beiden Anteile $\phi^k$ und $\psi^k$ auch unterschiedlich gewichten:

Übungsaufgabe Für zwei reelle Zahlen $\alpha, \beta \in R$ definieren wir $A_k := \alpha \phi^k + \beta \psi^k$. Zeigen Sie, dass die Folge $A_0, A_1, A_2, \dots $ auch Fibonacci-artig ist.

Was bringt uns dies? Nun ja, wir können jetzt mit den Werten für $\alpha$ und $\beta$ rumspielen und schauen, wie sich die Werte $A_0, A_1$ verändern:

\begin{align*} A_0 & = \alpha + \beta \\ A_1 & = \alpha \phi + \beta \psi \ . \end{align*}

Können wir nun $\alpha, \beta$ so wählen, dass $A_0 = 0$ und $A_1 = 1$ gilt? Wenn ja, dann würde unsere Folge $A_0, A_1,\dots$ die folgenden drei Kriterien erfüllen: $A_0 = 0, A_1 = 1, A_{k+2} = A_{k+1} + A_k$ und somit wäre sie identisch zu den Fibonacci-Zahlen: $A_k = F_k$; wir hätten eine explizite Formel für alle Fibonacci-Zahlen gefunden. Also: wir wollen Zahlen $\alpha,\beta$ mit

\begin{align*} \alpha + \beta & = 0\\ \alpha \phi + \beta \psi & = 1 \ . \end{align*}

Dies ist ein System mit zwei Gleichungen und zwei unbekannten und sollte somit genau eine Lösung haben (außer wenn die beiden Gleichungen linear abhängig sind, was sie aber nicht sind).

Übungsaufgabe Lösen Sie das obige Gleichungssystem (erinnern Sie sich, dass $\phi = \frac{1 + \sqrt{5}}{2} $ und $\psi = \frac{1-\sqrt{5}}{2}$ per Definition).

Wir haben nun also

Theorem. $F_k = \frac{1}{\sqrt{5}} \cdot \pfrac{1+\sqrt{5}}{2}^k - \frac{1}{\sqrt{5}} \cdot \pfrac{1-\sqrt{5}}{2}^k$ .

Beachten Sie, dass der zweiten Summand der Formel mit steigenden $k$ immer kleiner wird (im Absolutbetrag), und somit $$ \left| \frac{1}{\sqrt{5}} \cdot \pfrac{1-\sqrt{5}}{2}^k \right| \leq \frac{1}{\sqrt{5}} \lt 0.45 \ , $$ und somit ist der erste Summand $\frac{1}{\sqrt{5}} \cdot \phi^k$ höchstens $0.45$ von der ganzen Zahl $F_k$ entfernt. Daher gilt auch $F_k \geq \floor {\frac{1}{\sqrt{5}} \cdot \phi^k}$.

Anzahl Zugriffe für Maximierung unimodaler Arrays

Blicken wir zurück auf Theorem 1.13: wenn $n+1 \leq F_{k+2}$ ist, dann reichen $k$ Zugriffe, um in einem unimodalen Array der Länge $n$ das Maximum zu finden. Wenn $n+1 \leq \floor {\frac{1}{\sqrt{5}} \phi^k}$ gilt, dann sicherlich auch, da die rechte Seite ja höchstens $F_{k+2}$ ist. Wir formen nun diese Bedingung weiter um:

\begin{align*} & n+1 \leq \floor {\frac{1}{\sqrt{5}} \phi^k} \\ \Longleftrightarrow & n+1 \leq \frac{1}{\sqrt{5}} \phi^k \tag{da die linke Seite eine ganze Zahl ist}\\ \Longleftrightarrow & \log_2(n+1) \leq - \log_2 (\sqrt{5}) + k \log_2 (\phi) \\ \Longleftrightarrow & k \geq \frac{\log_2 (n+1) + \log_2(5) / 2}{\log_2 \phi} \approx 1.4405 \log_2 n + 1.763 \ . \end{align*}

Zusammenfassend: wir finden das Maximum mit ungefähr $1.4405 \log_2 n$ Zugriffen (plus minus); mit naiver Binärsuche, die in einem Halbierungsschritt $A[m]$ und $A[m+1]$ anfragt, kommen wir auf ungefähr $2 \log_2 n$, was deutlich schlechter ist.

Abschließende Bemerkungen. Mit dem zurückliegenden Kapitel wollte ich zwei Ziele erreichen. Zweitens wollte ich Ihnen anhand des Problems, das Maximum in einem unimodalen Arrays zu finden, illustrieren, wie man durch Abstrahieren, Vereinfachen, Herumprobieren etc. sich langsam vorarbeitet, bis man schlussendlich eine Vermutung formulieren und dann beweisen kann; es war also ein "Crash-Kurs in mathematischer Praxis", wobei "Praxis" nicht heißt, dass es ein im praktischen Leben relevantes Problem wäre, sondern dass es die Praxis mathematischer Arbeit illustriert hat.

Erstens schließlich haben wir in diesem Kapitel das Prinzip der binären Suche kennengelernt, welches Ihnen (unter den richtigen Umständen) erlaubt, Ihr gesuchtes Objekt in (ungefähr) $\log n$ Schritten zu finden, statt in $n$ Schritten, wenn Sie Ihre gesamte Datenmenge durchgehen müssen. Im Allgemeinen funktioniert binäre Suche, wenn Ihre Daten sinnvoll sortiert sind (zum Beispiel alphabetisch in unseren ersten Beispielen). Im nächsten Kapitel beschäftigen wir uns damit, wie man eine Datenmenge (also im Allgemeinen ein Array) sortiert.

Alice zerlegt \((11,4)\) in:	Eve wählt als neues Paar:
\((10, 1, 4)\)	\((10, 1)\)
\((9, 2, 4)\)	\((9, 2)\)
\((8, 3, 4)\)	\((8, 3)\)
\((7, 4, 4)\)	\((7, 4)\)
\((6, 5, 4)\)	\((6, 5)\)
\((5, 6, 4)\)	\((5, 6)\)
\((4, 7, 4)\)	\((4, 7)\) oder \( (7,4) \), spielt keine Rolle
\((3, 8, 4)\)	\((8, 4)\)
\((2, 9, 4)\)	\((9, 4)\)
\((1,10, 4)\)	\((10, 4)\)