% modusspezifisches: \mode { \usetheme{Warsaw} \setbeamertemplate{navigation symbols}{} %\setbeamercovered{transparent} % ausgeblendete Sachen transparent } \mode
{ %usepackage{fullpage} \usepackage{geometry} \geometry{left=3cm,textwidth=15cm,top=2.3cm,textheight=24.5cm} % textumflossene Bilder: \usepackage{picins} % schoene Programmlistings: \usepackage{listings} \lstset{language=c} \lstset{frame=single} \lstset{captionpos=b} \lstset{commentstyle=\textit} \renewcommand\lstlistingname{Programm} } \usepackage{graphicx} \usepackage[german]{babel} % ? ngerman tut nicht ? \usepackage[latin1]{inputenc} % Umlaute direkt eingeben %\usepackage{times} % nix schoen... %\usepackage{lmodern} %\usepackage[T1]{fontenc} % Oder was auch immer. Zu beachten ist, das Font und Encoding passen % müssen. Falls T1 nicht funktioniert, kann man versuchen, die Zeile % mit fontenc zu löschen. \title{Dynamische Programmierung} \subtitle{Hallo Welt für Fortgeschrittene} % (optional) \author{Frank Blendinger} \institute{\texttt{fb@intoxicatedmind.net}} \date{31.~Mai 2005} \mode { % Dies wird lediglich in den PDF Informationskatalog einfügt. % Kann gut weggelassen werden. \subject{Informatik} % Falls eine Logodatei namens "university-logo-filename.xxx" vorhanden % ist, wobei xxx ein von latex bzw. pdflatex lesbares Graphikformat % ist, so kann man wie folgt ein Logo einfügen: \pgfdeclareimage[height=1.1cm]{fau-logo}{fau} \logo{\pgfuseimage{fau-logo}} } % Folgendes sollte gelöscht werden, wenn man nicht am Anfang jedes % Unterabschnitts die Gliederung nochmal sehen möchte. %\AtBeginSubsection[] %{ % \begin{frame} % \frametitle{Gliederung} % \tableofcontents[currentsection,currentsubsection] % \end{frame} %} % Falls Aufzählungen immer schrittweise gezeigt werden sollen, kann % folgendes Kommando benutzt werden: %\beamerdefaultoverlayspecification{<+->} \begin{document} %==============================================================================% % Titelseite %==============================================================================% \begin{frame} \titlepage \end{frame} \mode
{ \maketitle } %==============================================================================% % Gliederung %==============================================================================% % Unnoetig, wenn \AtBeginSubsection schon die Gliederung anzeigt \mode { \begin{frame}[plain] \frametitle{Gliederung} \tableofcontents % Die Option [pausesections] könnte nützlich sein. \end{frame} } %==============================================================================% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Motivation} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %==============================================================================% \subsection{Was ist Dynamische Programmierung?} %==============================================================================% \begin{frame} \frametitle{Um was geht es?} \begin{definition} \textbf{Dynamische Programmierung (DP)} ist ein algorithmisches Muster, das meist zur L"osung von \alert{Optimierungsproblemen} eingesetzt wird. \end{definition} %\pause \begin{itemize} \item typischer Einsatz: Suche nach einer ein \alert{Maximum oder Minimum} erzielenden Kombination \item nicht eine, sondern die beste aus vielen m"oglichen L"osungen interessiert \mode { \bigskip } \item auch h"aufig gesucht: die \alert{Anzahl aller L"osungen} \\ zu einem Problem \end{itemize} \end{frame} %------------------------------------------------------------------------------% \begin{frame} \frametitle{Wie wird es gemacht?} \begin{itemize} \item \glqq dumme\grqq ~Herangehensweise w"are, alle M"oglichkeiten einfach durchzuprobieren \mode { \bigskip } \item hierbei werden oftmals Teilkombinationen wieder und wieder probiert \mode { \bigskip } \item diesen Aufwand spart man sich beim DP, indem man \alert{Zwischenergebnisse speichert} und auf diese bei Bedarf zur"uckgreift \end{itemize} \end{frame} %==============================================================================% \subsection{Geschichtliches} %==============================================================================% \begin{frame} \frametitle{Wer hat's erfunden?} \mode { \pause \ldots nein, nicht die Schweizer! \texttt{;)} \pause \bigskip \begin{columns}[c] \begin{column}{1.5cm} \includegraphics[height=2.5cm]{bellman.pdf} \end{column} \begin{column}{8cm} \begin{itemize} \item Begriff in den 1940er Jahren vom amerikanischen Mathematiker \textsc{Richard Bellman} (1920--1984) geprägt \item eigentlich ein mathematisches Verfahren, der Begriff \glqq Programmierung\grqq ~bezieht sich auf das Ausf"ullen einer Tabelle mit Zwischenergebnissen \end{itemize} \end{column} \end{columns} } \mode
{ \piccaption{\textsc{R. Bellman}\label{bellman}} \parpic[r]{ \includegraphics[height=3.0cm]{bellman.eps} } Der Begriff wurde in den 1940err Jahren vom amerikanischen Mathematiker \textsc{Richard Bellman} (1920--1984) geprägt. Urspr"unglich beschrieben wird hier ein mathematisches Verfahren, der Begriff \glqq Programmierung\grqq ~bezieht sich auf das Ausf"ullen einer Tabelle mit Zwischenergebnissen. \textsc{Bellman} studierte Mathematik am Brooklyn College und der University of Wisconsin. Er arbeitete im Bereich der theoretischen Physik in Los Alamos. 1946 erhielt er seinen Ph.D. der Universität Princeton. Die Methode der Dynamischen Programmierung entwickelte er im Zusammenhang mit seinen Forschungen auf dem Gebiet der Kontrolltheorie, die sich mit Entscheidungsprozessen besch"aftigt. } \end{frame} %==============================================================================% \subsection{Einf"uhrendes Beispiel: Fibonacci-Zahlen} %==============================================================================% \begin{frame} \frametitle{Alte Bekannte: die Fibonacci-Zahlen} \begin{definition} Fibonacci-Zahlen \newline $fib(1) = fib(2) = 1$ \newline $fib(n) = fib(n-2) + fib(n-1)$ \qquad\qquad $\forall n > 2$ \end{definition} \mode { \bigskip } \texttt{1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \ldots} \mode { \bigskip } \begin{itemize} \item rekursive Implementierung naheliegend \item aber: wie sieht es mit dem \alert{Aufwand} aus? \end{itemize} \end{frame} %------------------------------------------------------------------------------% \begin{frame} \frametitle{Fibonacci rekursiv} Rekursionsbaum f"ur die Berechnung von \texttt{fib(7)}: \begin{center} \mode { \includegraphics[height=4.4cm]{figure_fib1.pdf} } \mode
{ \includegraphics[height=5.5cm]{figure_fib1.eps} } \end{center} \begin{itemize} \item \alert{mehrfache Berechung} von Zwischenergebnissen \item \mode { exponentieller Aufwand: $\mathcal{O}(2^{n})$ \\ (pr"aziser: $\Omega(1.6^{n})$) } \mode
{ Aufwand zur Berechnung ist exponentiell: $\mathcal{O}(2^{n})$ (pr"aziser $\Omega(1.6^{n})$, was aber keine signifikante Verbesserung darstellt) } \end{itemize} \end{frame} %------------------------------------------------------------------------------% \begin{frame} \frametitle{Fibonacci rekursiv - aber diesmal mit Hirn!} \begin{itemize} \item weiterhin Rekursion \item berechnete Fibonacci-Zahlen in Tabelle speichern \item vor Rekursionsabstieg erst Blick in die Tabelle, ob Ergebnis nicht bereits vorliegt \begin{center} \mode { \includegraphics[height=3.2cm]{figure_fib2.pdf} } \mode
{ \includegraphics[height=4.5cm]{figure_fib2.eps} } \end{center} \item Ergebnis: nur noch \alert{linearer Aufwand} $\mathcal{O}(n)$ \end{itemize} \end{frame} %------------------------------------------------------------------------------% \begin{frame}[fragile] \frametitle{Fibonacci rekursiv - aber diesmal mit Hirn!} \begin{semiverbatim} \mode{ \uncover<2->{\alert<2>{long memo[MAX_N];}} \uncover<2->{\alert<3>{memset(memo, UNSET, MAX_N * sizeof(long));}} \uncover<2->{\alert<3,5>{memo[1] = 1; memo[2] = 1;}} \uncover<2->{} \uncover<1->{long \underline{fib}(int n) \{} \uncover<4->{\alert<4>{ if (memo[n] != UNSET) return memo[n];}} \uncover<1-5>{\alert<5>{ if (n == 1 || n == 2) return 1;}} \uncover<7->{\alert<7>{ memo[n] = \underline{fib}(n-1) + \underline{fib}(n-2);}} \uncover<1-7>{\alert<7>{ return \underline{fib}(n-1) + \underline{fib}(n-2);}} \uncover<8->{\alert<8>{ return memo[n];}} \uncover<1->{\}} } \end{semiverbatim} \end{frame} \mode
{ \input{code_fibmemo.tex} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Grundlagen} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %==============================================================================% \subsection{Memoization} %==============================================================================% \begin{frame} \frametitle{Grundlage eines jeden DP-Algorithmus: Memoization} \begin{definition} Unter \textbf{Memoization} versteht man allgemein die \alert{Speicherung der Ergebnisse} einer Funktion, um zu einem sp"ateren Zeitpunkt auf diese zur"uckgreifen zu k"onnen, anstatt sie neu berechnen zu m"ussen. \end{definition} \end{frame} %------------------------------------------------------------------------------% \begin{frame} \frametitle{Memoization: wie implementieren?} \begin{itemize} \item Tabelle je nach Anwendungsfall ein- oder mehrdimensionales Array \mode { \smallskip } \item meist kann (oder muss) die Tabelle mit einer Anzahl von Grundf"allen vorinitialisiert werden \mode { \smallskip } \item Rest der Tabelle wird auf einen speziellen Wert au"serhalb des L"osungsraums gesetzt, der f"ur \glqq noch nicht berechnet\grqq ~steht \mode { \smallskip } \item erste Anweisung bei jedem Funktionsaufruf ist ein Tabellenlookup \begin{itemize} \item \textbf{Wert bereits in Tabelle:}\\ zur"uckliefern \item \textbf{Wert noch nicht in Tabelle:}\\ berechnen, in Tabelle speichern, zur"uckliefern \end{itemize} \end{itemize} \end{frame} %==============================================================================% \subsection{Optimale Teilprobleme} %==============================================================================% \begin{frame} \frametitle{Aus eins mach viele: optimale Teilprobleme} \begin{itemize} \item urspr"ungliches Problem wird in eine \alert{Kombination aus kleineren Teilproblemen} zerlegt \mode { \bigskip } \item Teilprobleme sind ihrerseits optimal \mode { \bigskip } \item im Gegensatz zu Divide-and-Conquer-Algorithmen m"ussen die Teilprobleme nicht unabh"angig voneinander sein \mode { \bigskip } \item wir erhalten eine \alert{Rekursionsgleichung} f"ur das Problem \mode { \bigskip } \item Basisf"alle (z.B. $n=1$) aufstellen \end{itemize} \end{frame} %------------------------------------------------------------------------------% \begin{frame} \frametitle{Schwarze Schafe: "uberlappende Teilprobleme} \begin{itemize} \item bei Berechnung der Teilprobleme kann es zu \alert{"Uberschneidungen} kommen \mode { \bigskip } \item man spricht von sog. \glqq "uberlappenden Teilproblemen\grqq \mode { \bigskip } \item diese werden mittels \alert{Memoization} erschlagen \end{itemize} \mode { \bigskip \bigskip } \textbf{Memoization $+$ Teilprobleme $=$ DP} \end{frame} %==============================================================================% \subsection{Top-down vs. bottom-up} %==============================================================================% \begin{frame} \frametitle{Top-down: vom Problem zur L"osung} \begin{itemize} \item bisher Effizienzgewinn durch Memoization \mode { \bigskip } \item aber noch immer gro"ser \alert{Overhead durch Funktionsaufrufe} insbesondere bei hohen Rekursionstiefen \mode { \bigskip } \item bei extrem gro"sen Eingaben kann sogar der Speicherbedarf problematisch werden -- es drohen \alert{Stack Overflows}! \mode { \bigskip } \item rekursive Berechnung ist ein \textbf{top-down} Ansatz \end{itemize} \end{frame} %------------------------------------------------------------------------------% \begin{frame} \frametitle{Bottom-up: von der L"osung zum Problem} \begin{itemize} \item oft ist es geschickter einen \textbf{bottom-up} Ansatz zu verfolgen \mode { \bigskip } \item hierbei wird die Tabelle sukzessiv mit den Teill"osungen aufgef"ullt \mode { \bigskip } \item am Ende kann im Idealfall die L"osung direkt aus der Tabelle abgelesen werden \mode { \bigskip } \item im Gegensatz zur top-down Variante (Rekursion erweitert um Memoization) ist der bottom-up Ansatz meist nicht so leicht zu finden \mode { \bigskip } \item kann aber nochmals beachtliche \\ Performanzsteigerung zur Folge haben \end{itemize} \end{frame} %==============================================================================% \subsection{Ein weiteres Beispiel: Binomialkoeffizienten} %==============================================================================% \begin{frame} \frametitle{Ein Klassiker der Kombinatorik: Binomialkoeffizienten} \begin{itemize} \item Anzahl der M"oglichkeiten $k$ (numerierte) Bierflaschen aus einem Kasten mit $n$ solcher erfrischenden Getr"anke zu entnehmen \vspace{0.2cm} %\pause \begin{block}{Die L"osung:} $$\binom{n}{k} = \frac{n!}{(n-k)! k!}$$ \end{block} \vspace{0.4cm} %\pause \item gilt nat"urlich auch f"ur vergleichbare, aber weniger aufregende Problemstellungen \end{itemize} \end{frame} %------------------------------------------------------------------------------% \begin{frame}[fragile] % wegen {verbatim} \begin{itemize} \item Wie macht es der gemeine Informatiker? Klar: \alert{rekursiv}! \begin{block}{Rekursionsgleichung} $$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$ \end{block} \item Ein Blick auf das \textsc{Pascal}sche Dreieck offenbart uns, warum das funktioniert: {\small \begin{verbatim} 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 \end{verbatim} } \vspace{0.2cm} In der $(n+1)$-ten Zeile finden wir\\ die Werte $\binom{n}{i}$ f"ur $0 \leq i \leq n$. \end{itemize} \end{frame} %------------------------------------------------------------------------------% \mode
{ Eine genauere Erkl"arung der Rekursionsformel liefert folgende "Uberlegung: Wir betrachten das $n$-te Element. Entweder kommt dieses in einer der $\binom{n}{k}$ Teilmengen mit $k$ Elementen vor oder nicht. In ersterem Fall k"onnen wir die verbleibenden $k-1$ Elemente der Teilmenge aus den "ubrigen $n-1$ Elementen entnehmen. Andernfalls m"ussen wir alle $k$ Elemente aus den $n-1$ Elementen nehmen. Da diese beiden F"alle disjunkt sind, ergibt die Summe beider M"oglichkeiten die gesamte Summe um $k$ aus $n$ zu w"ahlen, also $\binom{n}{k}$. Die Rekursion ben"otigt selbstverst"andlich noch eine Abbruchbedingung. Hierf"ur bedienen wir uns der folgenden beiden Spezialf"alle: \begin{itemize} \item $\binom{n}{0} = 1$. Dies wird sofort einsichtig, wenn man sich vor Augen f"uhrt, dass es lediglich eine M"oglichkeit gibt, 0 Elemente aus einer $n$-elementigen Menge zu entnehmen -- n"amlich die leere Menge. \item $\binom{n}{n} = 1$. Die "Uberlegung erfolgt analog zum vorherigen Fall: Wieviele M"oglichkeiten gibt es, um alle $n$ Elemente aus einer $n$-elementigen Menge zu entnehmen? Genau eine, die Menge selbst. \end{itemize} Der linke Summand der Rekursionsgleichung wird nach $k$ Schritten zu $\binom{n-k}{0}$, der rechte nach $n-k$ Schritten zu $\binom{k}{k}$, womit die Rekursion schlie"slich terminiert. Eine ausf"uhrlichere Erl"auterung zu Binomialkoeffizienten findet sich u.a. in \cite{Skiena2003} sowie in \cite{Cormen1992}. \bigskip } %------------------------------------------------------------------------------% \begin{frame}[fragile] \frametitle{Konstruktion einer bottom-up L"osung} \begin{itemize} \item Um den Binomialkoeffizienten $\binom{n}{m}$ zu berechnen, k"onnen wir also einfach eine Dreiecksmatrix mit einem \textsc{Pascal}schen Dreieck mit $n+1$ Zeilen ausf"ullen. \mode { \bigskip } \item Die \glqq R"ander\grqq ~des Dreiecks, also die Eintr"age \texttt{[0][0]} bis \texttt{[0][n]} sowie \texttt{[0][0]} bis \texttt{[n][n]}, werden mit Einsen initialisiert. \mode { \bigskip } \item Die \glqq Innenfl"ache\grqq ~wird zeilenweise abgelaufen, zur Berechnung kann immer auf zwei bereits besetzte Eintr"age zur"uckgegriffen werden. \mode { \bigskip } \item An Position \texttt{[n][m]} steht schlie"slich der \\ gesuchte Wert. \end{itemize} \end{frame} %------------------------------------------------------------------------------% \begin{frame}[fragile] \frametitle{Optimierungsm"oglichkeit} \begin{itemize} \item keine teueren Funktionsaufrufe n"otig, da Rekursion vermieden wurde \mode { \bigskip } \item aber: einige der berechneten Werte w"aren gar nicht notwendig gewesen \mode { \smallskip } \item f"ur den Wert $x_{i, j}$ sind $x_{i-1, j-1}$ und $x_{i-1, j}$ relevant \mode { \smallskip } \item zur Berechnung von $\binom{n}{m} = x_{n, m}$ werden also keine $x_{i, j}$~mit~$j > m$ gebraucht \mode { \smallskip } \item es reicht daher beim Ausf"ullen der Tabelle in jeder Zeile bis zum $m$-ten Wert zu gehen \end{itemize} \end{frame} %------------------------------------------------------------------------------% % Quelltext \mode
{ \bigskip Das folgende C-Programm zeigt eine Bottom-up-Implementierung zur Berechnung von Binomialkoeffizienten. Die oben genannte Optimierung ist hier noch nicht mit eingebaut -- dies sei dem geneigten Leser zur "Ubung "uberlassen. \smallskip \input{code_bincoeff.tex} } %------------------------------------------------------------------------------% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Praktische Anwendung} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %==============================================================================% \subsection{Entwurf eines DP-Algorithmus} %==============================================================================% \begin{frame} \frametitle{Schritte beim Entwurf eines DP-Algorithmus} Der Entwurf eines DP-Algorithmus erfolgt "ublicherweise in vier Schritten: \mode { \smallskip } \begin{enumerate} \item Struktur einer optimalen L"osung analysieren \mode { \smallskip } \item Rekursionsgleichung f"ur eine optimales L"osung aufstellen \mode { \smallskip } \item wenn m"oglich Umwandlung des top-down Ansatzes in eine bottom-up Variante und Berechung einer optimalen L"osung \mode { \smallskip } \item Rekonstruktion des L"osungsweges zum zuvor bestimmten Ergebnis \end{enumerate} \end{frame} %------------------------------------------------------------------------------% \mode
{ Der letzte Schritt ist nat"urlich nur notwendig, falls nicht (nur) der Wert einer optimalen L"osung interessiert, sondern auch der Weg, der zu diesem Ergebnis gef"uhrt hat, also z.B. eine bestimmte Permutation. Zur leichteren Rekonstruktion merkt man sich h"aufig bei Schritt 3 zus"atzliche Informationen "uber getroffene Entscheidungen. } %==============================================================================% \subsection{Das Rucksackproblem} %==============================================================================% \begin{frame} \frametitle{Ich packe meinen Rucksack, und ich nehme mit \ldots} \frametitle
{Problemstellung} \begin{itemize} \item Rucksack mit der Kapazit"at $c$ \mode { \smallskip } \item $N$ verschiedene Typen von Gegenst"anden (jeweils in unbegrenzter Anzahl) \mode { \smallskip } \item jeder Typ $n$ hat einen spezifischen Wert $v_{n}$ sowie einen Platzbedarf $s_{n}$ \mode { \smallskip } \item wir wollen unseren Rucksack f"ullen \begin{itemize} \item ohne die Kapazit"at $c$ zu "uberschreiten \item dabei den Gesamtwert des Inhalts maximieren \end{itemize} \mode { \bigskip } \item typisches \alert{Optimierungsproblem} \end{itemize} \end{frame} %------------------------------------------------------------------------------% \begin{frame} \frametitle{Beispiel: Einkauf im Supermarkt} \mode
{ \smallskip } \begin{center} \begin{tabular}{llrr} $n$ & Artikel & Platz $s_{n}$ & Wert $v_{n}$ \\ \hline 0 & Bratwurst & 3 & 4 \\ 1 & Bier & 4 & 5 \\ 2 & Cola & 7 & 10 \\ 3 & Chips & 8 & 11 \\ 4 & Melone & 9 & 13 \\ \end{tabular} \end{center} \smallskip Was packen wir in unseren Rucksack der Gr"o"se 17 um sp"ater maximalen Genu"s zu erhalten? \smallskip \begin{itemize} \item ausprobieren undenkbar \item aber: wie dann? \end{itemize} \end{frame} %------------------------------------------------------------------------------% \begin{frame} \frametitle{Entwurf einer L"osung f"ur das Rucksackproblem} \begin{enumerate} \item \textbf{Wie sieht eine optimale L"osung aus?} \end{enumerate} \begin{itemize} \item Liste von $k$ Gegenstandstypen $n$: $$L_{c} = (n_{1}, n_{2}, \ldots , n_{k})$$ (die einzelnen Eintr"age $n_{i}$ m"ussen nicht zwingenderweise paarweise verschieden sein) \bigskip \item maximaler Wert des so gepackten Rucksacks ist die Summe der Werte all seiner Gegenst"ande: $$w_{c} = \sum_{i=1}^k{v_{i}}$$ \end{itemize} \end{frame} %------------------------------------------------------------------------------% \begin{frame} \frametitle{Entwurf einer L"osung f"ur das Rucksackproblem} \begin{enumerate} \setcounter{enumi}{1} \item \textbf{Rekursionsgleichung aufstellen} \end{enumerate} \begin{itemize} \item wir gehen davon aus, dass $L_{c}$ f"ur die Kapazit"at $c$ eine optimale L"osung ist \mode { \bigskip } \item wenn wir nun ein beliebiges Element, sagen wir das letzte, aus der Liste entfernen, so ist die Restliste eine optimale L"osung f"ur die Kapazit"at $c - s_{n_{k}}$ \mode { \bigskip } \item beim Weg zur"uck von der Teill"osung ist eine \alert{Auswahl} zu treffen: f"uge weiteres Element hinzu, so dass \begin{itemize} \mode{ \smallskip } \item die Kapazit"at nach wie vor unter der Gesamtkapazit"at liegt \mode{ \smallskip } \item der erh"ohte Gesamtwert maximal ist \mode{ \smallskip \bigskip } \end{itemize} \end{itemize} \end{frame} %------------------------------------------------------------------------------% \begin{frame}[fragile] \frametitle{Entwurf einer L"osung f"ur das Rucksackproblem} \mode{ Ein funktionierender, rekursiver Ansatz: } \begin{semiverbatim} \mode{int \underline{sack} (int cap) \{ int i, space, max, t; for (i = 0, max = 0; i < N; i++) if ((space = cap - items[i].size) >= 0) if ((t = \underline{sack}(space) + items[i].value) > max) max = t; return max; \} } \end{semiverbatim} \mode
{ \input{code_knapsack_rek.tex} } \mode { \vspace{-0.6cm} } \begin{itemize} \item aber Vorsicht: \alert{\textbf{Finger weg davon!}} \item extrem ineffizient schon bei sehr kleinen Werten! \end{itemize} \end{frame} %------------------------------------------------------------------------------% \begin{frame} \frametitle{Entwurf einer L"osung f"ur das Rucksackproblem} Laufzeiten f"ur die rekursive Implementierung (verwendete Daten waren die f"unf Artikeltypen aus dem Supermarkt-Beispiel): \mode{ \smallskip } \begin{center} \small \begin{tabular}{rr} $c$ & Zeit \\ \hline 100 & 0.9~sec \\ 110 & 4.3~sec \\ 120 & 23~sec \\ 125 & 51~sec \\ 130 & 1~min 57~sec \\ 135 & 4~min 28~sec \\ 140 & 10~min 10~sec \\ 150 & 52~min 48~sec \\ \end{tabular} \end{center} \begin{itemize} \item \alert{exponentielle Laufzeit} \end{itemize} \mode
{ \bigskip } \end{frame} %------------------------------------------------------------------------------% \begin{frame} \frametitle{Entwurf einer L"osung f"ur das Rucksackproblem} \begin{enumerate} \setcounter{enumi}{2} \item \textbf{Umwandeln in top-down DP} \end{enumerate} \mode{ \bigskip } \begin{itemize} \item das muss nat"urlich besser gehen! \mode{ \bigskip } \item wir bauen \alert{Memoization} ein \end{itemize} \end{frame} %------------------------------------------------------------------------------% \begin{frame}[fragile] \frametitle{Entwurf einer L"osung f"ur das Rucksackproblem} \begin{semiverbatim}\mode{int \underline{sack} (int cap) \{ \uncover<1->{ int i, space, max, t;} \uncover<2->{\alert<2>{ if (maxKnown[cap] != UNSET) return maxKnown[cap];}} \uncover<1->{ for (i = 0, max = 0; i < N; i++)} \uncover<1->{ if ((space = cap - items[i].size) >= 0)} \uncover<1->{ if ((t = \underline{sack}(space) + items[i].val) > max) \{} \uncover<1->{ max = t;} \uncover<1->{ \}} \uncover<3->{\alert<3>{ maxKnown[cap] = max;}} \uncover<1->{ return max;} \uncover<1->{\}} } \end{semiverbatim} \mode
{ \vspace{-0.6cm} \input{code_knapsack_dp.tex} } \end{frame} %------------------------------------------------------------------------------% \begin{frame} \frametitle{Entwurf einer L"osung f"ur das Rucksackproblem} Wir werfen erneut einen Blick auf die Laufzeiten (Daten wie gehabt): \mode{ \smallskip } \begin{center} \small \begin{tabular}{rr} $c$ & Zeit \\ \hline 1.000 & 5~ms \\ 50.000 & 20~ms \\ 100.000 & 25~ms \\ 500.000 & 80~ms \\ 1.000.000 & 145~ms \\ \end{tabular} \end{center} \begin{itemize} \item immense \alert{Performanzsteigerung}! \item \alert{lineare Laufzeit} \item notwendige "Anderung umfasste gerade mal \\ zwei Zeilen Code \end{itemize} \mode
{ \smallskip } \end{frame} %------------------------------------------------------------------------------% \begin{frame} \frametitle{Entwurf einer L"osung f"ur das Rucksackproblem} \begin{enumerate} \setcounter{enumi}{3} \item \textbf{Rekonstruktion des L"osungsweges} \end{enumerate} \begin{itemize} \item wenn uns nur der Wert unseres perfekt gef"ullten Rucksacks interessiert, sind wir nun fertig \mode { \bigskip } \item falls auch die Best"uckung von Interesse ist, so muss man sich die gew"ahlten Gegenst"ande merken \end{itemize} \end{frame} %------------------------------------------------------------------------------% \begin{frame} \frametitle{Entwurf einer L"osung f"ur das Rucksackproblem} \mode
{ \smallskip } \begin{itemize} \item bei jedem Schritt kommt ein neuer Gegenstand hinzu, der die verbleibende Kapazit"at verkleinert \mode { \bigskip } \item dieser einmal gew"ahlte Gegenstand bleibt f"ur diesen Schritt fest und wird im weiteren Verlauf nicht mehr ge"andert \mode { \bigskip } \item es gibt also zu jedem Kapazit"atswert, auf den wir auf unserem Weg sto"sen, genau einen eindeutigen Gegenstand \mode { \bigskip } \item wir merken uns daher die Zuordnung Kapazit"at $\rightarrow$ Index des gew"ahlten Gegenstandes in einem Array \texttt{itemKnown} \mode { \bigskip } \end{itemize} \end{frame} %------------------------------------------------------------------------------% \begin{frame} \frametitle{Entwurf einer L"osung f"ur das Rucksackproblem} \mode
{ \smallskip } \begin{itemize} \item bei der Rekonstruktion beginnen wir bei der Gesamtkapazit"at~$c$ \mode { \bigskip } \item der Index unseres ersten Gegenstands befindet sich daher in \texttt{itemKnown[c]} \mode { \bigskip } \item wurde dieser Gegenstand in den Rucksack aufgenommen so verbleibt noch die Kapazit"at \texttt{c~-~itemKnown[c].size} \mode { \bigskip } \item der n"achste Index findet sich also bei \texttt{itemKnown[c~-~itemKnown[c].size]} usw. \end{itemize} \end{frame} %------------------------------------------------------------------------------% \begin{frame}[fragile] \frametitle{Entwurf einer L"osung f"ur das Rucksackproblem} \begin{semiverbatim}\mode{int \underline{sack} (int cap) \{ \uncover<1->{ int i, space, max, }\uncover<2->{\alert<2>{max_i}, }\uncover<1->{t;} \uncover<1->{ if (maxKnown[cap] != UNSET) return maxKnown[cap];} \uncover<1->{ for (i = 0, max = 0; i < N; i++)} \uncover<1->{ if ((space = cap - items[i].size) >= 0)} \uncover<1->{ if ((t = \underline{sack}(space) + items[i].val) > max) \{} \uncover<1->{ max = t; }\uncover<2->{\alert<2>{max_i = i;}} \uncover<1->{ \}} \uncover<1->{ maxKnown[cap] = max; }\uncover<3->{\alert<3>{itemKnown[cap] = items[max_i];}} \uncover<1->{ return max;} \uncover<1->{\}} } \end{semiverbatim} \mode
{ \vspace{-0.6cm} Die Speicherung der gew"ahlten Gegenst"ande wurde in \lstlistingname ~\ref{knapsack_dp} bereits stillschweigend implementiert. Hierzu wurde zus"atzlich das Array \texttt{itemKnown} angelegt (Zeile~5) und nach jeder Auswahl zus"atzlich zum Wert auch der gerade selektierte Gegenstand gespeichert (Zeile~17). } \end{frame} % %==============================================================================% % \subsection{Matrixmultiplikation} % %==============================================================================% % % \begin{frame} % \frametitle{Optimale Reihenfolge bei der Multiplikation von Matrizen} % \frametitle
{Problemstellung} % % \begin{itemize} % \item % gegeben sind $N$ Matrizen $M_{1}$ bis $M_{N}$ % % \mode{ \bigskip } % % \item % weiterhin sind die Werte $p_{0}$ bis $p_{N}$ gegeben, wobei % f"ur die Matrix $M_{i}$ die Anzahl der Zeilen $p_{i-1}$ und die % Anzahl der Spalten $p_{i}$ ist % % \mode{ \bigskip } % % \item % die Matrizen sollen nun miteinander multipliziert werden, wobei % die Reihenfolge gew"ahlt werden soll, bei der die \alert{Anzahl % der Skalarmultiplikationen minimal} ist % \end{itemize} % \end{frame} % % %------------------------------------------------------------------------------% % % \begin{frame} % \frametitle{Optimale Reihenfolge bei der Multiplikation von Matrizen} % % \begin{itemize} % \item % zur Erinnerung: f"ur die Multiplikation zwei Matrizen muss die % Anzahl der Spalten der ersten mit der Anzahl der Spalten der % zweiten Matrix "ubereinstimmen % % \mode{ \bigskip } % % \item % f"ur die Multiplikation einer $p \times r$ Matrix mit einer % $r \times q$ Matrix sind $p \cdot r \cdot q$ % Skalarmultiplikationen notwendig % % \mode{ \bigskip } % % \item % Reihenfolge der Multiplikation entspricht Klammerung % % \mode{ \bigskip } % % \item % Anzahl der M"oglichkeiten ist exponentiell % \end{itemize} % \end{frame} % % %------------------------------------------------------------------------------% % % \begin{frame} % \frametitle{Beschreibung einer L"osung} % % \begin{itemize} % \item % eine optimale Klammerung l"asst sich zerteilen % % \mode{ \bigskip } % % \item % die Kosten der Gesamtl"osung seien % % \item % Kosten der Zerteilung sind % % \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Fazit und Ausblick} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %==============================================================================% \subsection{Zusammenfassung} %==============================================================================% \begin{frame} \frametitle{Wann bietet es sich an, DP einzusetzen?} \begin{itemize} \item Suche nach einem Optimum \mode{ \bigskip } \item jeder Schritt zum Ziel ben"otigt eine Auswahl \mode{ \bigskip } \item optimales Ergebnis l"asst sich in Teilergebnisse aufteilen, die ihrerseits optimal sind \mode{ \bigskip } \item es treten bei der Zerst"uckelung h"aufig "Uberlappungen auf \end{itemize} \end{frame} %==============================================================================% \subsection{Probleme} %==============================================================================% \begin{frame} \frametitle{Wann ist DP kein geeigneter Ansatz?} \begin{itemize} \item wenn die Anzahl der m"oglichen Funktionswerte, die ben"otigt werden, zu gro"s wird \mode { \smallskip } \item Speicherplatz f"ur Zwischenspeicherung (top-down) bzw. Vorausberechnung (bottom-up) dann nicht ausreichend \mode { \smallskip } \item insbesondere dann, wenn reelle Zahlen als Funktionsparameter auftreten \mode { \bigskip } \item \ldots und nat"urlich Finger weg von DP, wenn ein effizienterer L"osungsweg (Formel o."a.) bekannt ist! \texttt{:)} \end{itemize} \end{frame} %==============================================================================% \subsection{Einsatzgebiete} %==============================================================================% \begin{frame} \frametitle{Zum Schluss ein kleiner Blick "uber den Tellerrand} DP wird \textit{nicht nur} f"ur das L"osen von ACM-Aufgaben benutzt. Einsatzgebiete \glqq in freier Wildbahn\grqq ~sind beispielsweise: \mode{ \bigskip } \begin{itemize} \item \textbf{Bioinformatik} \mode{ \smallskip } \begin{itemize} \item Sequenzierung von Genen und Proteinen \mode{ \smallskip } \item sehr "ahnliche Problemstellung wie bei Stringvergleichen \end{itemize} \mode{ \bigskip } \item \textbf{Linguistik} \mode{ \smallskip } \begin{itemize} \item CYK-Algorithmus \end{itemize} \end{itemize} \end{frame} \mode { %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Literatur} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame} \frametitle{Literaturempfehlungen} \begin{thebibliography}{T.~Cormen, et al.} % laengster Eintrag \bibitem{Cormen1992} T.~Cormen et al. \newblock Introduction To Algorithms \newblock {\small MIT Press, 1992} \bibitem{Sedgewick1992} R.~Sedgewick \newblock Algorithmen \newblock {\small Addison-Wesley, 1992} \bibitem{Sedgewick2002} R.~Sedgewick \newblock Algorithmen in C++ \newblock {\small Pearson Studium, 2002} \bibitem{Skiena2003} S.~Skiena, M.~Revilla \newblock Programming Challenges \newblock {\small Springer, 2003} \end{thebibliography} \end{frame} } \mode
{ \begin{thebibliography}{T.~Cormen, et al.} % laengster Eintrag \bibitem{Cormen1992} T.~Cormen et al. \newblock \textit{Introduction To Algorithms}. \newblock MIT Press, 1992. \bibitem{Sedgewick1992} R.~Sedgewick. \newblock \textit{Algorithmen}. \newblock Addison-Wesley, 1992. \bibitem{Sedgewick2002} R.~Sedgewick. \newblock \textit{Algorithmen in C++}. \newblock Pearson Studium, 2002. \bibitem{Skiena2003} S.~Skiena, M.~Revilla. \newblock \textit{Programming Challenges}. \newblock Springer, 2003. \end{thebibliography} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \mode { \begin{frame}[plain] \begin{center} {\Huge That's all, folks!} \end{center} \end{frame} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end{document}