\documentclass[a4paper,twoside,12pt]{article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts,amstext}
\usepackage{amsmath}
\usepackage{german}
\usepackage{fullpage}
\usepackage{xspace}
\usepackage{graphicx}

\newcommand{\ZETTELNUMMER}{14}
\newcommand{\ABGABEDATUM}{am 9. Februar~2018 bis 10 Uhr in die 
  jeweiligen Tutorenf\"acher}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Aufgabe \arabic{AUFGNR}]\stepcounter{AUFGNR} #1\hfill\emph{#2}}


\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\half}[1]{\frac{#1}{2}}
\newcommand{\N}{\mathbb{N}}

\renewcommand{\labelenumi}{(\alph{enumi})}


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Aufgabenblatt zur Vorlesung

\smallskip
\noindent
\large
\textbf{Algorithmen, Datenstrukturen und Datenabstraktion}\hfill WS 17/18 \\[0.5ex]
\normalsize
Wolfgang Mulzer, Katharina Klost


\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM\\
Dies ist das letzte Aufgabenblatt.

\vskip 0.5cm
\noindent

\begin{description}
\AUFGABE {Finden von Senken in Graphen} {10 Punkte}

Betrachtet man die Adjazenzmatrixdarstellung eines Graphen $G=(V,E)$, dann
haben viele Algorithmen Laufzeit $\Omega(|V|^{2})$. Es gibt 
aber Ausnahmen: Zeigen Sie, dass die Frage, ob ein gerichteter Graph $G$ eine
\emph{globale Senke} --- einen Knoten vom Ingrad $|V|-1$ und Ausgrad $0$ --- 
hat, in Zeit $O(|V|)$ beantwortet werden kann, selbst wenn man die
Adjazenzmatrixdarstellung von $G$ (die ja selbst schon die Gr\"o\ss{}e
$\Theta(|V|^{2})$ hat) verwendet.
Beweisen Sie Korrektheit und Laufzeit Ihres Algorithmus.


\emph{Hinweis}: Sei $A$ die Adjazenzmatrix von $G$ und 
  $u \neq v \in V$. Was folgt  \"uber $u$ und $v$,
  wenn $A_{uv} = 1$ ist?
  Was, wenn $A_{uv} = 0$ ist?

\AUFGABE{K\"urzeste Wege in DAGs}{10 Punkte}

Sei $G = (V,E)$ ein gewichteter gerichteter azyklischer Graph.
Seien $s,t \in V$. Geben Sie einen Algorithmus, der einen k\"urzesten
Weg von $s$ nach $t$ in Zeit $O(|V|+|E|)$ berechnet. Beweisen Sie die
Korrektheit und die Laufzeit Ihres Algorithmus.

\emph{Hinweis}:
Beachten Sie Aufgabe 3(b) auf dem 13.~\"Ubungszettel und verwenden
Sie dynamisches Programmieren.

\AUFGABE{$A^*$-Suche}{10 Punkte}

Sei $G = (V, E)$ ein gerichteter, gewichteter Graph mit nichtnegativen
Kantengewichten. Seien $t \in V$ und sei 
$h : V \rightarrow \mathbb{R}_0^+$ eine
Funktion mit $h(t) = 0$.
Wir nennen $h$ \emph{konsistent}, falls f\"ur alle Kanten
$e = (u,v) \in E$ gilt:
\[
h(u) \leq h(v) + w_e,
\]
wobei $w_e$ das Gewicht der Kante $e$  bezeichnet.

Zeigen Sie: Wenn $h$ konsistent ist,  dann ist
$h(v) \leq d_G(v, t)$ f\"ur alle $v \in V$. Hierbei 
bezeichnet $d_G(\cdot, \cdot)$ den 
k\"urzeste-Wege-Abstand in $G$. 
Gilt auch die Umkehrung?


\end{description}

\noindent
\emph{Hinweis}:
Bitte formatieren Sie Ihre Abgaben mit \LaTeX\xspace oder einem
vergleichbaren elektronischen Textverarbeitungssystem. Ansonsten droht
der Abzug von bis zu 10\% der erreichbaren Punkte.



\end{document}
