\documentclass[a4paper,fleqn,ngerman]{scrartcl}
\usepackage{cmap}
\usepackage[T1]{fontenc}
\usepackage{textcomp}
\usepackage[ngerman]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{wasysym}
\usepackage{dsfont}
\usepackage{booktabs}
\usepackage{color}
\usepackage{units}
\usepackage{eule}
\usepackage[activate]{pdfcprot} % optischer Randausgleich mit pdfLaTeX
\usepackage{graphicx}
\usepackage{calc}
\usepackage[bookmarksnumbered,bookmarksopen]{hyperref}
\hypersetup{
 pdftitle={\"Ubungsblatt 9},
 pdfsubject={Programmierung II, Lenhof},
 pdfauthor={Andreas Glitsch, Jan Hendrik Dithmar, Dirk Heine},
 pdfkeywords={Programmierung II, Lenhof},
 pdfstartview={FitH \hypercalcbp{\paperheight-\topmargin-1in-\headheight-\headsep}}
}
\usepackage{listings}
\lstloadlanguages{Pascal,C++}
\lstset{tabsize=4,language=Pascal,basicstyle=\ttfamily}
\lstset{morekeywords={process,par_begin,par_end,monitor,public,from},
morecomment=[l]{//},
morecomment=[s]{/*}{*/}}
\input{macros}
\setcounter{secnumdepth}{0}
%%\renewcommand*{\sectfont}{\bfseries}
\listfiles
\begin{document}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\titlehead{
  \newlength{\calclengthA}
  \newlength{\calclengthB}
  \settowidth{\calclengthA}{\EULE}
  \setlength{\calclengthB}{\linewidth}
  \addtolength{\calclengthB}{-\calclengthA}
  \addtolength{\calclengthB}{-1em}
  \parbox{\calclengthB}{
    \raggedright
    \scshape{
    Universit\"at des Saarlandes\\
    Fachrichtung 6.2 - Informatik\\
    Sommersemester~2004\\
    Gruppe~Andreas~Augustin ~Do~14-16
    }
  }
  \hfill
  \parbox[b]{\calclengthA}{\EULE}
}
\subject{Programmierung II}
\title{Übungsblatt 9}
\author{Andreas Glitsch 2026130 \and Jan Hendrik Dithmar 2031259 \and Dirk Heine 2030941}
\date{\today}

\maketitle

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
1 & 2 & 3 & 4 & 5 & 6 & $\sum$\\
\hline
& & & & & &\\
\hline
\end{tabular}
\end{center}

\section{Aufgabe 1: Hashfunktion}
Gegeben: $H^{fool} = \{h_{(a,b)} : a,b \in 0...m-1\}$ mit $h_{(a,b)}(x) = ax + \text{b mod m}$.\\
N sei die Anzahl aller Schl\"ussel.\\
Menge M von $\displaystyle \lfloor \frac{N}{m} \rfloor$ Schl\"usseln f\"ur die gilt:\\
$\forall x,y \in M:\forall h_{(a,b)} \in H^{fool} : h_{(a,b)}(x) = h_{(a,b)}(y)$.\\
m prim.\\
\\
Beweis:\\
$h_{(a,b)}(x) = h_{(a,b)}(y) \Rightarrow ax + \text{b mod m} = ay + \text{b mod m}$\\
$\Rightarrow ax + b + tm = ay + b + t'm$\\
$\Rightarrow ax + tm = ay + t'm$\\
$\Rightarrow ax + tm - t'm = ay$\\
$\Rightarrow ax + m(t - t') = ay$\\
$\Rightarrow ax - ay + m(t - t') = 0$\\
$\Rightarrow a(x - y) + m(t - t') = 0$\\
$\Rightarrow a(x - y) \text{ mod m} = 0$\\

\section{Aufgabe 2: L\"oschen eines Elements}

\section{Aufgabe 3: Anwendung Hashfunktion}

\section{Aufgabe 4: Kuckuck-Hashing}
\subsection{i)}
Pseudo-Code f\"ur die insert-Funktion des Kuckuck-hashing:
\begin {verbatim}void insert(item y)
{
  while(true)
  {
    item tmp;
    if(t_1[h_1(y)] != leer)
    {
      tmp = t_1[h_1(y)];
      t_1[h_1(y)] = y;
    }
    else
    {
      t_1[h_1(y)] = y;
      return;
    }
    if(t_2[h_2(tmp)] != leer)
    {
      y = t_2[h_2(tmp)];
      t_2[h_2(tmp)] = tmp;
    }
    else
    {
      t_2[h_2(tmp)] = tmp;
      return;
    }
  }
}
\end{verbatim}

\subsection{ii)}
Die insert-Funktion k\"oennte endlos laufen wenn keine freie Speicherzelle gefunden wird.\\
Dies kann z.B. passieren wenn beide Arrays $t_1$ und $t_2$ voll sind und darauf die %%@
insert-Funktion angewendet wird.\\

\section{Aufgabe 5: Bin\"arer Suchbaum}

\section{Aufgabe 6: Kommutativit\"at}

\end{document}
