LaTeX-examples/documents/klausurvorbereitung-gbi/gbi-klausurvorbereitung.tex

\documentclass[a4paper,12pt]{article}
\usepackage{amssymb} % needed for math
\usepackage{amsmath} % needed for math
\usepackage[utf8]{inputenc} % this is needed for umlauts
\usepackage[ngerman]{babel} % this is needed for umlauts
\usepackage[T1]{fontenc}    % this is needed for correct output of umlauts in pdf
\usepackage[margin=2.5cm]{geometry} %layout
\usepackage{fancyhdr}  % needed for the footer
\usepackage{lastpage}  % needed for the footer
\usepackage{hyperref}  % links im text
\usepackage{wasysym}  % farbige Tabellenzellen

\newcommand{\Nachname}{Thoma}
\newcommand{\Vorname}{Martin}

\hypersetup{
  pdfauthor   = {\Vorname~\Nachname},
  pdfkeywords = {\Vorname~\Nachname, GBI, Klausur},
  pdftitle    = {Klausurvorbereitung für GBI im WS 2011 / 2012}
}

\begin{document}

\title{Klausurvorbereitung für GBI im WS 2011 / 2012}
\author{\Vorname~\Nachname}

\section{Definitionen}
Definiere folgendes Formal korrekt:

\begin{enumerate}
  \item ${\cal O}(f(n))$,  $\Omega(f(n))$,  $\Theta(f(n))$
  \item Das Master-Theorem
  \item $L^*, L^+$
\end{enumerate}

\section{Aussagenlogik}
Finde möglichst einfache Aussagenlogische Formeln C, D, E in Abhängigkeit von A
und B für folgende Tabelle:
\begin{table}[h]
	\begin{tabular}{| c | c  || c | c | c |}
	\hline
	\textbf{A} & \textbf{B} & C & D & E\\
	\hline
	\hline
	0 & 0 & 0 & 1 & 0\\
	\hline
	0 & 1 & 1 & 1 & 1\\
	\hline
	1 & 0 & 1 & 0 & 0\\
	\hline
	1 & 1 & 1 & 0 & 0\\
	\hline
	\end{tabular}
\end{table}

\section{Master-Theorem}
Wenden Sie, falls möglich, das Master-Theorem auf folgende Funktionen an. Jede
Funktion hat $\mathbb{N}_0$ als Definitions- und Zielmenge.\footnote{An dieser Stelle sollte man Frage 5.20 beantworten.}
\begin{enumerate}
  \item $f(n) := 2 \cdot 5 + 3 f(\frac{n}{2})$
  \item $g(n) := 2 \cdot 5 - 3 g(\frac{n}{2})$
  \item $h(n) := h(\frac{n}{3}) + 1$
  \item $i(n) := 9 \cdot i(\frac{n}{3}) + n^2$
  \item $j(n) := 8 \cdot j(\frac{n}{3}) + n^2$
  \item $k(n) := 8 \cdot k(\frac{n}{3}) + \frac{1}{2} n^2$
  \item $l(n) := 8 \cdot l(\frac{n}{9}) + 1/n$
  \item $m(n) := 2 \cdot m(\frac{n}{2}) + n log(n)$ \footnote{\href{http://www.cits.rub.de/imperia/md/content/may/dima08/26_erzeugende.pdf}{Folie 310}, LEHRSTUHL KRYPTOLOGIE und IT-SICHERHEIT der Uni Bochum}
\end{enumerate}

\pagebreak

\section{Formale Sprachen}
Sei $\Sigma = \{a, b, c\}$

\subsection{Dies und das}
\begin{enumerate}
  \item Wieviele Sprachen gibt es über $\Sigma^*$?
  \item Wie viele endliche Sprachen gibt es über $\Sigma^*$?
  \item Wie viele Wörter hat die Sprache $L = \{w \in \Sigma^* |~~|w| \leq 2\}$?
\end{enumerate}

\subsection{Palindrome}
Sei L die Sprache der Palindrome. Ein Palindrom ist ein Wort, das von links nach
rechts gelesen genauso aussieht, wie von rechts nach links gelesen.

Beispiele:
\begin{itemize}
  \item Anna
  \item Die Liebe ist Sieger; stets rege ist sie bei Leid.
  \item Rentner
\end{itemize}

Aufgaben:
\begin{enumerate}
  \item Beschreiben Sie L als Menge
  \item Geben Sie eine Grammatik G an, sodass gilt: L = L(G).
  \item Geben Sie, falls möglich, einen Endlichen Automaten an, der L erkennt. Falls das nicht möglich ist, begründen Sie warum.
  \item Geben Sie, falls möglich, eine Ableitung von \glqq abcba\grqq{} an. Falls das nicht möglich ist, begründen Sie warum.
  \item Geben Sie, falls möglich, einen/den Ableitungsbaum zu \glqq abcba\grqq{} an. Falls das nicht möglich ist, begründen Sie warum.
  \item Geben Sie, falls möglich, einen regulären Ausdruck zu L an, sodass $L = \langle R \rangle $. Falls das nicht möglich ist, begründen Sie warum.
\end{enumerate}

\pagebreak

\section{Wahr oder Falsch}
\begin{table}[h]
	\begin{tabular}{| c | p{12 cm}  | c | c |}
	\hline
	\textbf{\#} & \textbf{Frage} & \textbf{Wahr} & \textbf{Falsch} \\
	\hline
	\hline
	1 & Alle Sprachen sind regulär.           &  \Square &  \Square \\
	\hline
	2 & Alle endlichen Sprachen sind regulär. &  \Square &  \Square \\
	\hline
	3 & Alle regulären Sprachen sind endlich. &  \Square &  \Square \\
	\hline
	4 & Es gibt unentscheidbare Probleme.     &  \Square &  \Square \\
	\hline
	5 & Es gibt Probleminstanzen unentscheidbarer Probleme, die entscheidbar sind.     &  \Square &  \Square \\
	\hline
	6 & Die Busy-Beaver-Funktion bb(n) wächst schneller als jede berechenbare Funktion. &  \Square &  \Square \\
	\hline
	7 & Es gibt keine Funktion $f(n)$, für die gilt: $f(n) \notin {\cal O}(n^n)$ &  \Square &  \Square \\
	\hline
	8 & Es gibt keine berechenbare Funktion $f(n)$, für die gilt: \newline $f(n) \notin {\cal O}(n^n)$ &  \Square &  \Square \\
	\hline
	9 & Eine Turingmaschine erkennt genau die Kontextfreien Sprachen. &  \Square &  \Square \\
	\hline
	10 & Es gibt zu jeder Sprache L eine Grammatik G, sodass L = L(G).  &  \Square &  \Square \\
	\hline
	11 & Es gibt zu jeder regulären Sprache L eine Grammatik G, \newline sodass L = L(G). &  \Square &  \Square \\
	\hline
	12 & Es gibt zu jeder kontextfreien Sprache L eine Grammatik G, \newline sodass L = L(G). &  \Square &  \Square \\
	\hline
	13 & ${\cal O}(f(n)) \cap \Omega(f(n)) = \Theta(f(n))$   &  \Square &  \Square \\
	\hline
	14 & 1 Mebibyte = $2^{20}$ Byte &  \Square &  \Square \\
	\hline
	15 & 1 Megabyte = $2^6$ Byte   &  \Square &  \Square \\
	\hline
	16 & $L = \{w\} \Rightarrow \forall n \in \mathbb{N}_0: L^n = \{w^n\} $ &  \Square &  \Square \\
	\hline
	17 & $L = \{w\} \Rightarrow \exists n \in \mathbb{N}_0: L^n = \{w^n\} $ &  \Square &  \Square \\
	\hline
	18 & $L = \{w\} \Rightarrow \exists n, m \in \mathbb{N}_0: n \neq m \land L^n = \{w^n\} \land L^m = \{w^m\}$ &  \Square &  \Square \\
	\hline
	19 & Sei $G(V, E)$ ein Graph und $n = |V|$. Dann existiert eine obere Schranke in Abhängigkeit von $n$ für $|E|$ &  \Square &  \Square \\
	\hline
	20 & Sei $f: \mathbb{N}_0 \rightarrow \mathbb{N}_0$ eine Funktion und $\varepsilon, a, b > 0$. Dann gilt entweder \newline
$f \in {\cal O}(n^{log_b a - \varepsilon})$ oder \newline
$f \in \Theta(n^{log_b a})$ oder \newline
$f \in \Omega(n^{log_b a + \varepsilon})$ &  \Square &  \Square \\
	\hline
	\end{tabular}
\end{table}





\end{document}