\documentstyle[A4,12pt,german]{article} \newcommand{\bD}{\hbox{\bf D}} \newcommand{\N}{\hbox{\bf N}} \newcommand{\cA}{\hbox{$\cal A$}} \begin{document} \begin{center} {Probleme, Algorithmen, Komplexit"at:\\ Einige grundlegende Begriffe.} \end{center} \begin{enumerate} \item Beispiele zum Einstieg Um eine konkrete Anschauung von den in der "Uberschrift genannten Begriffen zu erhalten, ist es zweckm"a"sig, beispielhaft einige praktisch relevante Probleme zusammenzustellen, wie sie im Rahmen der Vorlesung\footnote{ Nat"urlich k"onnen bei weitem nicht alle genannten im Rahmen dieser Vorlesung angesprochen werden. Es geht ja auch mehr um den Typus von Problemen.} behandelt werden sollen. \begin{itemize} \item Probleme mit (nat"urlichen) Zahlen \begin{itemize} \item Addition, Multiplikation, Exponentiation von nat"urlichen Zahlen, \item Division mit Rest ({\em div, mod}) \item Berechnung des gr"o"sten gemeinsamen Teilers zweier (oder mehrerer) nat"urlicher Zahlen \item Testen auf Primheit \item Faktorisierung \end{itemize} \item Probleme mit Polynomen \begin{itemize} \item Auswertung \item Addition, Multiplikation von Polynomen \item Polynomdivision mit Rest \item Test auf Irreduzibilit"at \item Faktorisierung \end{itemize} \item Probleme mit Matrizen \begin{itemize} \item Multiplikation von Matrizen \item Berechnung der Inversen \item Berechnung von Determinanten \item L"osung von linearen Gleichungssystemen \item Lineare Optimierung (reell, ganzzahlig) \end{itemize} \item Probleme mit Listen \begin{itemize} \item Maximumsuche in einer Liste von Zahlen \item Element in Liste finden \item Sortieren einer Liste von Zahlen \end{itemize} \item Probleme mit (Di)Graphen (vgl. Algorithmik II) \begin{itemize} \item Topologisches Sortieren \item Spannenden Baum finden bzw. deren Anzahl bestimmen \item K"urzeste Wege, Flu"sprobleme \item Eulerschen Weg, Hamiltonschen Kreis finden bzw. deren Anzahl bestimmmen \item Maximale Clique finden \item F"arbungszahl bestimmen \end{itemize} \item Probleme mit Formeln und Termen \begin{itemize} \item Aussagenlogische, arithmetische Formel auswerten \item AL-Formel in Normalform (DNF, KNF) transformieren \item AL-Formel auf Erf"ullbarkeit testen \item Transformation von Termen in Normalform (Reduktionsysteme) \item Formales Differenzieren \end{itemize} \end{itemize} \item Probleme und Problemgr\"o"se Die Spezifikation eines algorithmischen {\em Problems} ist gegeben durch eine Funktion \[ F :\bD \rightarrow \bD' \] oder eine (linkstotale) Relation \[ F \subseteq \bD \times \bD' \] wobei \bD\ und $\bD'$ Datenbereiche ({\em domains}) sind. Die zu einem domain \bD\ geh\"orenden Objekte, die {\em Daten}, haben eine {\em Gr\"osse}, d.h. es ist eine Funktion \[ \hbox{\it size} : \bD \rightarrow \N : d \mapsto |d| \] gegeben. Mit $\bD_n = \{ d \in \bD; |d| = n\}$ wird die Menge der Daten der Gr\"osse $n$ bezeichnet. \item Diskussion der Gr\"o"se anhand der Beispiele \begin{itemize} \item Nat"urliche Zahlen: Elemente $n \in {\bf N}$ werden meist in Basis-$b$-Darstellung vorliegen, also \[ n = n_0 + n_1 \, b + n_2 \, b^2 + \cdots + n_k b^k ~~\mbox{\rm mit}~~ 0 \leq n_i < b~~(0 \leq j \leq k) \] Im Zusammenhang mit dem Chinesischen Restesatz k"onnen auch modulare Zahldarstellungen von Interesse sein. Als Gr"o"se einer nat"urlichen Zahl $n$ nimmt man in der Regel die Anzahl der bit, die man braucht, um die Zahl in Basis-2-Darstellung aufzuschreiben, also $\lceil \log_2 n \rceil$. \item Polynome Als Ma"s f"ur die Gr"o"se eines Polynoms nimmt man meist den {\em Grad} des Polynoms, also i.w. die Anzahl der Koeffizienten. In Sonderf"allen ist die Anzahl der von Null verschiedenen Koeffizienten relevant. Diese Unterscheidung entspricht zwei verschiedenen Darstellungen von Polynomen im Rechner: {\em dense} und {\em sparse}. Die Wahl der Darstellung hat auf die Arithmetik einen wesentlichen Einflu"s. Die Gr"o"se der Koeffizienten eines Polynoms wird oft unber"ucksichtigt gelassen, geht dann also in die Messung mit 1 ein. F"ur manche Situationen ist das vertretbar (z.B. Polynome "uber endlichen Koeffizientenbereichen), in andern F"allen ist das unrealistisch (nat"urlich insbesondere dann, wenn die Koeffizienten selbst wieder Polynome sind, also in der Situation von multivariablen Polynomen. Hier ist "ubrigens auch die Frage {\em dense} vs. {\em sparse} kritisch). \item Matrizen Die Situation ist "ahnlich wie bei Polynomen, wobei als relevanter Parameter einer $(n \times n)$-Matrix oft $n$ (und nicht etwa $n^2$) angesehen wird. Speziell bei Optimierungsproblemen orientiert man sich auch an der ``wahren'' Gr"o"se einer Matrix, also der bit-Gr"o"se, genommen "uber alle Eintr"age der Matrix. \item Listen H"aufig ist die L"ange einer Liste der relevante Parameter, d.h. die Gr"o"se der Listenelemente wird als ``konstant'' (=1) angesehen. Je nach der Natur der Listeneintr"age kann das, wie bei Matrizen und Polynomen, ein problematischer Standpunkt sein. \item Graphen F"ur die algorithmische Behandlung ist wichtig, in welcher Form ein Graph $G = (V,E)$ vorliegt, ob als Adjazenzmatrix oder Adjazenzliste. Oft gen"ugt die Knotenzahl $\sharp V$ als Ma"s f"ur die Gr"o"se, gelegentlich mu"s man aber auch die Kantenzahl $\sharp E$ mit ins Spiel bringen. \item Terme und Formeln Da solchen Objekten meist eine Baumstruktur zugrunde liegt, orientiert man sich an den Ma"sen f"ur Graphen. Die Beschriftung kann aber eine Rolle spielen (z.B. Anzahl der verschiedenen Variablen) \end{itemize} \item Korrektheit Ein (deterministischer) Algorithmus \cA\ l\"ost das durch die Spezifikation \[ F : \bD \rightarrow \bD'~~ \hbox{bzw}~~ F \subseteq \bD \times \bD' \] gegebene Problem, wenn er diese Funktion $F$ (bzw. Relation $F$) realisiert, d.h. wenn \[ \forall d \in \bD : \cA (d) = F(d)~~\hbox{bzw}~~ \forall d \in \bD : (d,\cA (d)) \in F \] gilt. Hierbei bezeichnet $\cA(d)$ das Resultat der Ausf"uhrung des Algorithmus \cA\ auf dem input-Datum $d \in \bD$. (In diesem Rahmen treten keine Terminationsprobleme auf. Es interessieren vorwiegend Situationen, wo Termination ohnehin gesichert ist). \bigskip \item Kosten eines Algorithmus Ist \cA\ ein Algorithmus, der ein gegebenes Problem $F$ l"ost, so interessieren neben dieser Eigenschaft der Korrektheit auch der ``Aufwand'' f"ur seine Ausf"uhrung. ein Mass f\"ur die {\em Kosten}. Diese sollen erfa"st werden durch eine Funktion \[ c^{\cA} : \bD \rightarrow \N : d \mapsto c^{\cA}(d) \] die die Kosten der Ausf\"uhrung von \cA\ auf $d \in D$ beschreibt. Unter den ``Kosten'' hat man sich dabei, je nach der Natur des Problems und des Algorithmus, solche Gr"ossen wie \begin{itemize} \item Rechenzeit, \item Speicherbedarf, \item Anzahl der Zugriffe auf externen Speicher, \item Gr\"o"se des Resultats usw. \end{itemize} oder Kombinationen aus solchen Gr\"ossen vorzustellen. Dabei wird in der Regel von Implementierungsdetails, Hardwaregegebenheiten usw. abstrahiert und es wird nur auf die {\em wesentlichen Operationen} Bezug genommen. Das kann dann sein: \begin{itemize} \item Anzahl der bit-Operationen \item Anzahl der Vergleichsoperationen \item Anzahl der Zuweisungsoperationen \item Anzahl der arithmetischen Operationen \end{itemize} wobei der jeweilige Algorithmus oft mit Hilfe eines Pseudocodes beschrieben sein wird. \item Der {\em worst-case} Ansatz Als die {\em worst-case}-Komplexit\"at des Algorithmus \cA\ bezeichnet man die Funktion \[ c_{\max}^{\cA} : \N \rightarrow \N : n \mapsto\max \{ c^{\cA}(d); d \in \bD_n \} \] (Entsprechend kann man auch die {\em best-case}-Komplexit\"at des Algorithmus \cA\ \[ c_{\min}^{\cA} : \N \rightarrow \N : n \mapsto \min \{ c^{\cA}(d); d \in \bD_n \} \] definieren. Dies ist aber in der Regel nicht so sehr von Interesse.) Was einen an der Komplexit\"atsfunktion $n \mapsto c_{\max}^{\cA}(n)$ interessiert, ist das Verhalten in Anh\"angigkeit von $n$ f\"ur grosse Werte von $n$. Bei sorgf\"altiger Abstraktion von dem realen Laufzeitverhalten (einer konkreten Implementierung eines Algorithmus in einer konkreten Programmiersprache f\"ur eine konkrete Maschine) zu einer Registrierung der wesentlichen Operationen zeigen reale und abstrahierende Komplexit\"at das gleiche asymptotische Verhalten, wachsen also beispielsweise als Funktionen mit dem gleichen polynomialen Grad - wenn sich die Komplexit\"at \"uberhaupt polynomial verh\"alt. Dies rechtfertigt die vergr\"obernde Vorgehensweise, die oft zugunsten mathematischer Praktikabilit\"at gew\"ahlt werden muss. Eine gel\"aufige, grobe Unterscheidung sagt, dass ein Algorithmus \cA\ f\"ur akzeptabel gehalten, als {\em effizient} klassifiziert wird, wenn diese Funktion $n \mapsto c_{\max}^{\cA}(n)$ {\em polynomial} w\"achst. Bei schnellerem, also insbesondere bei {\em exponentiellem} Wachstum dieser Funktion spricht man dann von einem {\em ineffizenten} Algorithmus. Gegen diese Unterscheidung lassen sich durchaus Argumente aus {\em praktischer} Sicht vorbringen: ein polynomiales Wachstum vom Grad drei, vier, f\"unf etwa kann schon bei bescheidenen Problemgr\"ossen in unpraktikable Bereiche f\"uhren. Zudem kann f\"ur Probleme realistischer Gr\"o"se ein Algorithmus mit exponentieller Komplexit\"at durchaus ein besseres Verhalten zeigen als ein Algorithmus, der sich polynomial verh\"alt, wo dieser prinzipielle Vorteil aber erst in Gr\"ossenordnungen zum Tragen kommt, die ohnehin ausserhalb aller Realit\"at liegen. Die Konkurrenz zwischen dem bew\"ahrten (aber im worst-case eben doch exponentiellen) Simplex-Algorithmus f\"ur die lineare Optimierung und dem polynomialen Algorithmus von Khachian illustriert das.\footnote{Eine \"ahnlich Aussage muss man auch im Bereich polynomialer Algorithmen machen, siehe die Bemerkungen zur Komplexit"at der Matrixmultiplikation in Abschnitt 12.} Ein wichtiges {\em theoretisches} Argument daf\"ur, die Unterscheidung zwischen Effizienz und Nicht-Effizienz mit ``polynomial'' bzw. ``nicht-polynomial'' zu identifizieren, liegt darin, dass diese Unterscheidung ausserordentlich robust gegen die jeweiligen spezifischen Details bei der Wahl des Komplexit\"atsma"ses, des Maschinenmodells und der Implementierung ist. Insbesondere f\"uhren in dieser Hinsicht Turing-Maschinen mit ihren bit-Operationen und RAMs mit ihrer Modellierung realistischer Rechner zur gleichen Unterscheidung. Als einfache Beispiele zur Berechnung der {\em worst-case} Komplexit"at eines Algorithmus siehe etwa {\em maxfind} (mit seinen Varianten) und {\em insertionsort}. \item {\em Average-case} Komplexit"at Die worst-case Komplexit\"at $c_{\max}^{\cA}$ eines Algorithmus gibt meistens nur ein sehr grobes Bild von dem quantitativen Verhalten eines Algorithmus. Aus praktischer Sicht ist man oft eher daran interessiert, wie sich ein Algorithmus f\"ur eingegebenes Problem bei einem {\em typischen} input der Gr\"osse $n$ verh\"alt. Man hat es also mit der Frage nach den Charakteristika einer Wahrscheinlichkeitsverteilung, also etwa dem Mittelwert (Erwartungswert) und der Streuung (Varianz), zu tun. \begin{itemize} \item Stochastischer Ansatz. Man setzt voraus, dass f\"ur jedes $n \in \N$ auf den Daten $\bD_n$ der Gr\"osse $n$ eine Wahrscheinlichkeitsverteilung $\mu_n$ gegeben ist, insgesamt also eine Familie $(\mu_n)_{n \geq 0}$, die das ``zuf"allige'' Auftreten der inputs beschreibt. Die Komplexit\"atsfunktion $c^{\cA} : \bD_n \rightarrow \N$ ist also als Zufallsvariable aufzufassen, f\"ur deren Verteilung (oder Verteilungsfunktion) man sich interessiert. Diese explizit zu berechnen und etwa Grenzverteilungen f\"ur $n \rightarrow \infty$ zu berechnen, ist nur in wenigen F\"allen m\"oglich. Realistischer ist die Frage nach den wichtigen Kenngr\"ossen dieser Verteilungen, also Erwartungswert und Varianz (und evtl. h\"ohere Momente). Es interessiert also \[ c_{\rm aver,\mu}^{\cA}(n) := {\bf E}_{\mu_n}(c^{\cA}) = \int_{\bD_n} c^{\cA}(d)~ d\mu_n \] was man, wegen der diskreten Natur der Werte der Kostenfunktion, auch als \begin{eqnarray*} c_{\rm aver,\mu}^{\cA}(n) & = &\sum_{k \geq 0} k \cdot \mu_n( d \in \bD ; c^{\cA} (d) = k ) \\ &=& \sum_{k \geq 1}\mu_n( d \in \bD ; c^{\cA} (d) \geq k ) \end{eqnarray*} schreiben kann. F\"ur die Varianz gelten die entsprechenden Formeln. Auch dieser Ansatz st"o"st in aller Regel auf un\"uberwindliche Schwierigkeiten: man hat aus der Problemstellung nur unzureichende Hinweise darauf, mit welcher Verteilungsfamilie $(\mu_n)_{n \in \N}$ man rechnen soll. Selbst wenn man sich hier festlegt, kommt man, ausser in wenigen gel\"aufigen F\"allen (wie Gleichverteilung, Normal\-verteilung, Exponential\-verteil\-ung usw.), kaum je zu exakten Resultaten. Hat man keinen Grund zu einer speziellen Annahme \"uber die Verteilung, so zieht man sich \"ublicherweise auf die Gleichverteilung zur\"uck. Ist dann auch noch der Datenbereich $\bD_n$ f\"ur jedes $n$ endlich, so reduziert sich die Berechnung der mittleren Komplexit\"at des Algorithmus \cA\ auf ein kombinatorisches Z\"ahlproblem: \begin{eqnarray*} c_{\rm aver}^{\cA}(n) & = &{1 \over \sharp \bD_n} \sum_{k \geq 0}k \cdot \sharp \{ d \in \bD_n ; c^{\cA}(d) = k \} \\ & = & {1 \over \sharp \bD_n} \sum_{k \geq 1}\sharp \{ d \in \bD_n ; c^{\cA}(d) \geq k \} \end{eqnarray*} Diese Reduktion auf eine kombinatorische Situation hat den Vorteil, da"s man bekannte kombinatorische Techniken, insbesondere die Technik der erzeugenden Funktionen, zu Hilfe nehmen kann, um solche Z\"ahlprobleme zu l\"osen. Oft kann man auch (unter der Annahme der Gleichverteilung) von einer kontinuierlichen Situation zu einer diskreten, kombinatorischen Situation \"ubergehen, ohne Information zu verlieren. Dies soll gleich an einem wichtigen Beispiel erl\"autert werden. \end{itemize} Vorher aber noch der Hinweis auf die Berechnungen der {\em average-case} Komplexit"at von {\em maxfind} (mit Anzahl der Zuweisungsoperationen als relevantem Kostenma"s --- was auf das Studium des Parameters {\em lrm} = Anzahl der Links-Rechts-Maxima f"ur Listen bzw. Permutationen f"uhrt) und auf das Studium von {\em insertionsort} (wo der Parameter {\em inv} = Anzahl der Inversionen einer Liste bzw. Permutation die interessante Rolle spielt). \item Beispiel: Sortieren von Listen Bei manchen Sortierproblemen wird angenommen, da"s die Datenmenge $\bD_n$ aus allen Listen $L = L[1..n]$ der L\"ange $n$ besteht, wobei die Listenelemente $L[i]$ unabh\"angig und gleichverteilt aus der Menge $[0,1]$ der reellen Zahlen zwischen $0$ und $1$ genommen sind. Bei vielen Sortieralgorithmen interessiert man sich nur f\"ur die Anzahl der Vergleichs\-operationen, die zum Sortieren der Liste erforderlich sind. Andere ``wesentliche'' Operationen sollen im Algorithmus nicht vorkommen oder deren Kosten (z.B bei Vertauschungen) sollen von den betroffenen Argumenten unabh\"angig sein. In dieser Situation kommt es also nur auf die relative Ordnung der Listenelemente $L[1] ,\ldots, L[n]$ untereinander an - nicht auf die tats\"achlichen Werte. Man kann sich dann, wie im Zusammenhang mit dem Algorithmus {\em insertionsort} ausgef"uhrt, auf die kombinatorische Situation zur"uckziehen, da"s man als inputs der L"ange $n$ alle Permutationen $\sigma \in S_n$ in Betracht zieht, mit der Gleichverteilung $\mu_n$ als Input-Verteilung, die jedem $\sigma$ die Wahrscheinlichkeit $1/n!$ gibt.\footnote{ Das Kuriose an dieser Situation ist, da"s man in diesem Szenario das Ergebnis eines Sortiervorganges schon vor dessen Ausf"uhrung kennt, man also eigentlich garnicht sortieren m"usste --- aber es ist ja nicht die sortierte Liste, die uns interessiert, sondern der Aufwand zur Konstruktion derselben.} In diesem Kontext liefern dann Parameter wie ``Anzahl der Links-Rechts-Maxima'', ``Anzahl der Inversionen'', ``Anzahl der Zyklen'' von Permutationen die f"ur das Laufzeitverhalten relevanten Statistiken. Diese sind in der mathematischen Literatur gr"undlich studiert worden, teils lange bevor Komplexit"atsanalysen daf"ur eine Motivation darstellten. Man kann sich oft, nicht immer, klassischer Methoden und Resultate bedienen. In vielen F"allen haben aber auch die Bed"urfnisse der Komplexit"atsanalyse zu neuen mathematischen Fragestellungen und Methoden gef"uhrt. \item Wachstumsordnungen Es gelingt nur in relativ seltenen F"allen, f"ur die Komplexit"atsfunktionen \begin{eqnarray*} c_{max}^{\cA} ~:~\N \rightarrow \N ~:~ n \mapsto c_{max}^{\cA}(n) \\ c_{aver}^{\cA} ~:~\N \rightarrow \N ~:~ n \mapsto c_{aver}^{\cA}(n) \end{eqnarray*} eines Algorithmus \cA\ eine {\em explizite} Darstellung, etwa in Art einer ``geschlossenen'' Formel f"ur $c_{max}^{\cA}(n)$ bzw $c_{aver}^{\cA}(n)$, zu finden. Meist ist dies aber auch garnicht das Wesentliche, sondern man interessiert sich f"ur die {\em Tendenz}, also das {\em Wachstumsverhalten} (bei wachsendem $n$) dieser Funktionen. Dies ist auch insofern berechtigt, als man bei den Untersuchungen von unwesentlichen ``Implementierungsdetails'' ohnehin absehen muss, die sich in den Kompexit"atsfunktionen unangenehm komplizierend bemerkbar machen w"urden, ohne den ``Trend'' zu beeinflussen. Die Mathematik, insbesondere die asymptotische Analysis, hat ein Arsenal von Begriffen und Methoden entwickelt, um mit Fragen des Wachstumsverhaltens umzugehen, insbesondere Funktionen nach ihrem Wachstumsverhalten zu vergleichen und zu klassifizieren. Von elementaren Aspekten, etwa dem korrekten Umgang mit der $O,o,\Omega,\Theta,\sim$-Notation wird noch die Rede sein. \item Komplexit\"at eines Problems Jedes algorithmisch l"osbare Problem l"a"st viele verschiedene Algorithmen zu seiner L"osung zu. Deren Komplexit"atsverhalten kann sehr unterschiedlich sein. Um verschiedene Algorithmen f"ur ein Problem fair miteinander zu vergleichen, mu"s man nat"urlich sorgf"altig darauf achten, da"s gleiche Rahmenbedingungen hinsichtlich Datenstrukturierung und Kostenparametern gegeben sind. Man spricht dann auch von einem {\em Modell}, das solche Aspekte kodifiziert --- dieser Begriff ist durchaus enger als der Begriff eines {\em Problems}. Diese Unterscheidung soll an dieser Stelle nicht weiterverfolgt werden, sondern f"ur den momentanen Gebrauch soll der Begriff des Problems alle Aspekte mitumfassen, die f"ur einen fairen Vergleich von Algorithmen relevant sind. Man kann dann von der {\em worst-case-Komplexit"at eines Problems} $F$ in folgendem Sinne sprechen: \[ c_{max}^{F} ~:~ \N \rightarrow \N ~:~ n \mapsto \min_{\cA} c_{max}^{\cA}(n) \] Es handelt sich also um ein Ma"s f"ur den algorithmischen Mindestaufwand (im Bezug auf eine spezifische Kostenfunktionen), den {\em jeder} Algorithmus zur L"osung des Problems ben"otigt. Die Fairness-Bedingungen erfordern dabei, da"s alle zur Konkurrenz bei der Minimum-Bildung zugelassenen Algorithmen, abgesehen von der f"ur uns banalen Forderung nach der Korrektheit) mit den gleichen Datenstrukturen umgehen m"ussen und den gleichen Kostenma"sen unterliegen. Die {\em averagce-case-Komplexit"at} eines Problems kann man analog definieren. Die exakte Bestimmung von {\em Problemkomplexit"aten} ist, von relativ wenigen Ausnahmen abgesehen, noch nicht gelungen. Es handelt sich um eine in aller Regel au"serordentlich schwierige Aufgabe (Quantifizierung "uber eine uns weitgehend unbekannte Menge von Objekten: alle Algorithmen \ldots) und bislang mu"s man sich auch bei relativ ``allt"aglichen'' Problemen mit schw"acherer Information zufrieden geben: \begin{itemize} \item Gelingt es, aus der Natur der Problems $F$ heraus eine Funktion $g~:~\N \rightarrow \N\ $ anzugeben, f"ur die \[ \forall n \in \N~:~ g(n) \leq c_{max}^{F}(n) \] gilt, so nennt man $g$ eine {\em untere Schranke} f"ur die Problemkomplexit"at. \item Die Komplexit"atsfunktion $n \mapsto c_{max}^{\cA}$ f"ur jeden konkreten Algorithmus \cA , der das Problem $F$ l"ost, ist eine {\em obere Schranke} f"ur die Funktion $c_{max}^{F}$: \[ \forall n \in \N~:~ c_{max}^{F}(n) \leq c_{max}^{\cA}(n) \] \item Hat man einen Algorithmus \cA\ gefunden, dessen Komplexit"at $c_{max}^{\cA}$ mit einer unteren Schranke $g$ \"ubereinstimmt, so hat man nat"urlich den Idealfall $c_{max}^{F} = c_{max}^{\cA}$, und man spricht von einem {\em optimalen} Algorithmus. \end{itemize} \item Relativierungen Angesichts der oft hoffnungslosen Schwierigkeiten, Komplexit"aten von konkreten Algorithmen exakt zu berechnen, geschweige denn Problemkomplexit"aten zu bestimmen (und seien es auch nur realistische untere Schranken), verwendet man die Begriffe {\em untere Schranke}, {\em obere Schranke}, {\em optimaler Algorithmus} h"aufig auch im Sinne der Wachstumsordnungen der Funktionen, spricht also z.B. von {\em asymptotisch optimalen} Algorithmen. \item Beispiele: \begin{itemize} \item Maximumsuche in einer Liste (und Verwandtes) Betrachten wir Algorithmen, die in Listen von Zahlen (oder Elementen einer total geordneten Menge) das maximale Element finden, und betrachten wir die Anzahl der paarweisen Vergleiche als relevantes Kostenma"s, so ist klar, da"s bei Listenl"ange $n$ mindestens $n-1$ Vergleiche n"otig sind --- jedes Element mu"s ja mindestens einmal in einen Vergleich einbezogen werden. Also ist $g(n) = n-1$ eine untere Schranke f"ur die Problemkomplexit"at. Andererseits gibt es Algorithmen wie {\em maxfind} und {\em maxturnier} (vgl Aufgabe 1 der "Ubungen), die tats"achlich mit $n-1$ Vergleichen bei Listenl"ange $n$ auskommen. {\em maxfind} und {\em maxturnier} sind also {\em optimale} Algorithmen f"ur das Problem der Maximumsuche unter dem Kostenma"s der Anzahl Vergleichsoperationen. Ganz entsprechend kann man zu dem Problem, das {\em zweitgr"o"ste} Element in einer Liste zu finden (Aufgabe 2), feststellen: \begin{itemize} \item $n+ \lceil \log n \rceil -2$ Vergleichsoperationen bei Listenl"ange $n$ sind notwendig (nicht in der Vorlesung bewiesen, siehe Literatur, zB. {\sc Baase}) \item Es gibt Algorithmen, die mit dieser Zahl von Vergleichsoperationen auskommen. \end{itemize} oder bei dem Problem, zugleich Maximum und Minimum in einer Liste zu finden (Aufgabe 5 der "Ubungen): \begin{itemize} \item $\lceil{3 n\over 2}\rceil-2$ Vergleichsoperationen bei Listenl"ange $n$ sind notwendig (nicht in der Vorlesung bewiesen, siehe Literatur, z.B. {\sc Aigner}) \item Es gibt Algorithmen, die mit dieser Zahl von Vergleichsoperationen auskommen. \end{itemize} \item Sortieren einer Liste Es wird sich zeigen, da"s jeder Algorithmus, der Listen der L"ange $n$ auf der Basis von paarweisen Vergleichen sortiert, im {\em worst case} mindestens $\log_2(n!)$ Vergleichsoperationen ben"otigt. Die Funktion $n \mapsto \lceil \log_2(n!) \rceil$ ist also eine untere Schranke, die man allerdings meist etwas abschw"acht, um handlichere Aussagen zu haben. Aus $n! > (n/e)^n$ folgt, da"s auch die Funktion $n \mapsto n \, \log_2 n - n \log_2 e$ eine untere Schranke ist. Jedes Sortierverfahren, das im {\em worst-case} mit $O(n \log_2 n)$ Vergleichen auskommt, bezeichnet man als {\em asymptotisch optimal}. Die bekannten Algorithmen {\em heapsort} und {\em merge sort} sind solche asymptotisch optimalen Verfahren im worst-case. Quicksort (naiv) hat asymptotisch quadratische Komplexit"at, ist also nicht optimal im worst-case, wohl aber im average-case. \item Multiplikation von ganzen Zahlen, Polynomen, Matrizen Diese ``Alltagsprobleme'' stellen die Komplexit"atsanalyse immer noch vor gro"se R"atsel, was die ``wahren'' unteren Schranken betrifft. \begin{itemize} \item Die Schulmethode zur Multiplikation von nat"urlichen Zahlen mit jeweils $n$ Ziffern in Basis-$b$-Darstellung erfordert $O(n^2)$ Multiplikationen im Ziffernbereich, dazu $O(n)$ Additionen (wobei "Ubertragseffekte zu ber"ucksichtigen sind). Mit der {\sc Karatsuba}-Idee (1962) kann man diese obere Schranke auf $O(n^{\log_2 3})=O(n^{1.56\ldots})$ dr"ucken. Die beste derzeit bekannte Methode, der auf der Idee der Fourier-Transformation basierende Algorithmus von {\sc Sch"onhage} und {\sc Strassen} (1971), ist ein $O(n \, \log n \ \log \log n)$ Verfahren, das sich aber erst bei Problemgr"ossen $n > 10^6$ als den anderen Verfahren "uberlegen erweist. Was die {\em untere Schranke} f"ur diese Problem betrifft, so hat man trivialerweise eine lineare Funktion, da man jede Ziffer der zu multiplizierenden Zahlen einmal ins Spiel bringen muss. Das ist aber auch alles, was man bislang mit Bestimmtheit sagen kann. \item F"ur die Multiplikation von Polynomen ist die Situation "ahnlich: von den $O(n^2)$ Multiplikationen im Koeffizientenbereich, die das ``Schulverfahren'' zur Multiplikation zweier Polynome $n$-ten Grades ben"otigt, "uber das $O(n^{\log_2 3})=O(n^{1.585\ldots})$ Verfahren von {\sc Karatsuba} geht der Weg bis zu dem $O(n \, \log n)$ Verfahren mit Hilfe der schnellen Fourier-Transformation. Auch hier ist die ``wahre'' Problemkomplexit"at noch unbekannt. \item Bei der Matrixmultiplikation kennt man die ``Schulmethode'', bei der man zur Multiplikation von zwei $(n \times n)$-Matrizen einen Aufwand von $O(n^3)$ Multiplikationen im Koeffizientenbereich ben"otigt. {\sc Strassen} hat 1969 gezeigt, da"s man zwei $(2 \times 2)$-Matrizen mit lediglich 7 (statt 8~!) Multiplikationen im Koeffizientenbereich multiplizieren kann: die rekursive Verwendung dieser Idee \`a la {\sc Karatsuba} f"uhrt auf einen $O( n^{\log_2 7} ) = O(n^{2.807\ldots})$ Multiplikationsalgorithmus. Diese bei ihrer Entdeckung als "uberraschend empfundene Tatsache hat eine enorme Aktivit"at auf dem Gebiet der Algorithmik der Matrixmultiplikation ausgel"ost, die bis heute anh"alt. Man kennt heute Algorithmen mit einem asymptotischen Verhalten von $O(n^{2.375\ldots})$ f"ur die Anzahl der Multiplikationen im Koeffizientenbereich --- im Gegensatz zu der {\sc Strassen}-Methode, die bereits in Gr"o"senordnungen um $n=20$ interessant wird, sind diese ``Algorithmen'' aber rein ``theoretischer'' Natur in dem Sinne, da"s ihre asymptotische "Uberlegenheit erst bei astronomischen Problemgr"o"sen zum Tragen kommt. \end{itemize} \end{itemize} \end{enumerate} \end{document}