Mercurial > 13ss.theoinf

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/.hgignore	Thu Apr 25 13:29:39 2013 +0200
@@ -0,0 +1,21 @@
+syntax: glob
+
+# Compiled files (they should be added by-hand)
+*.dvi
+*.pdf
+
+# TeX files
+*.aux
+*.bbl
+*.blg
+*.brf
+*.log
+*.out
+*.synctex.gz
+*.thm
+*.toc
+*.nav
+*.snm
+
+# Swap files
+*.swp
Binary file notes/tex/TU_Muenchen_Logo_Breit.pdf has changed
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/notes/tex/beamerthemeLEA2.sty	Thu Apr 25 13:29:39 2013 +0200
@@ -0,0 +1,60 @@
+\ProvidesPackage{beamerthemeLEA2}
+
+\xdefinecolor{tumblue}     {RGB}{  0,101,189}
+\xdefinecolor{tumgreen}    {RGB}{162,173,  0}
+\xdefinecolor{tumred}      {RGB}{229, 52, 24}
+\xdefinecolor{tumivory}    {RGB}{218,215,203}
+\xdefinecolor{tumorange}   {RGB}{227,114, 34}
+\xdefinecolor{tumlightblue}{RGB}{152,198,234}
+
+%% shadow, font, color, outer, inner
+%% normal text, alerted text, example text, structure
+
+\useoutertheme{split}
+
+\setbeamercolor{normal text}{fg=black,bg=white}
+\setbeamercolor{alerted text}{fg=tumred,bg=white}
+\setbeamercolor{example text}{fg=tumgreen,bg=white}
+\setbeamercolor{structure}{fg=tumblue,bg=white}
+\setbeamercolor{titlelike}{fg=tumblue}
+\setbeamercolor{subtitle}{fg=black}
+\setbeamerfont{title}{series=\bfseries}
+
+\setbeamertemplate{sections/subsections in toc}[square]
+\setbeamertemplate{items}[square]
+\setbeamertemplate{navigation symbols}[only frame symbol]
+
+\setbeamertemplate{blocks}[default]
+
+\setbeamercolor{block title}        {use=normal text, fg=black,bg=tumlightblue}
+\setbeamercolor{block title alerted}{use=alerted text,fg=white,bg=alerted text.fg}
+\setbeamercolor{block title example}{use=example text,fg=white,bg=example text.fg}
+
+\setbeamercolor{block body}        {parent=normal text,use=block title,        bg=block title.bg!25!bg}
+\setbeamercolor{block body alerted}{parent=normal text,use=block title alerted,bg=block title.bg!25!bg}
+\setbeamercolor{block body example}{parent=normal text,use=block title example,bg=block title example.bg!15!bg}
+
+\pgfdeclareimage[height=5mm]{uni}{TU_Muenchen_Logo_Breit}
+\logo{\pgfuseimage{uni}}
+
+\defbeamertemplate*{footline}{infolines theme}{%
+    \hspace*{2ex}\raisebox{1.5ex}[-1.5ex]{%
+    \tiny\insertframenumber{}/\inserttotalframenumber \hspace{5mm} \insertnavigation{0.8\paperwidth}}%
+}
+
+\setbeamertemplate{frametitle}{
+    \begin{beamercolorbox}[wd=80mm,leftskip=0mm]{frametitle}
+        \usebeamerfont*{frametitle}
+        \insertframetitle\hfill\parbox{10mm}{\vspace{-2mm}\insertlogo}\hspace{-2mm}
+    \end{beamercolorbox}
+    \vspace{-3mm}\textcolor{tumblue}{\noindent\rule{\textwidth}{0.4px}}
+}
+% hier kein Logo
+\setbeamertemplate{sidebar right}{\vfill\vskip2pt\llap{\usebeamertemplate***{navigation symbols}\hskip1mm}\vskip2pt}
+
+\setbeamertemplate{headline}{}
+
+\setbeamercovered{transparent}
+
+% escapeinside= removed for utf8 compatibility
+\lstset{numbers=left, numberstyle=\tiny, numbersep=5pt, basicstyle=\small, backgroundcolor=\color{tumlightblue}}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/notes/tex/ue01_notes.tex	Thu Apr 25 13:29:39 2013 +0200
@@ -0,0 +1,250 @@
+\documentclass[compress, german, t]{beamer}
+
+\usepackage[ngerman,english]{babel}
+\uselanguage{German}
+\languagepath{German}
+
+\usepackage[T1]{fontenc}
+\usepackage[utf8]{inputenc}
+
+\usepackage{helvet}
+\usepackage{url}
+\usepackage{listings}
+\usepackage{xcolor}
+\usepackage{tikz}
+\usepackage{pgfplots}
+\usetikzlibrary{automata}
+\usetikzlibrary{calc}
+\usetikzlibrary{shapes.geometric}
+\usepackage{tabu}
+
+\usepackage{beamerthemeLEA2}
+
+\newcommand{\N}       {\mathbb{N}}          % natürliche Zahlen
+\newcommand{\Z}       {\mathbb{Z}}          % ganze Zahlen
+\newcommand{\R}       {\mathbb{R}}          % reelle Zahlen
+\newcommand{\Prob}    {\mathrm{P}}          % Wahrscheinlichkeit
+\newcommand{\Oh}      {\mathcal{O}}         % O-Notation (Landau-Symbole)
+\newcommand{\mycite}[1]{\textcolor{tumgreen}{[#1]}}
+
+\tikzstyle{every edge} = [draw,very thick,->,>=latex]
+\tikzstyle{every state} = [circle,thick,draw,fill=tumblue!10]
+
+\title{Übung 1}
+\subtitle{Theoretische Informatik Sommersemester 2013}
+\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
+
+\begin{document}
+
+\begin{frame}
+    \titlepage
+\end{frame}
+
+\begin{frame}
+    \frametitle{Organisatorisches}
+
+    \begin{itemize}
+        \item Mail: \href{mailto:tutor@zfix.org}{tutor@zfix.org}
+        \item Web: \href{tutor.zfix.org}{tutor.zfix.org}
+            \vfill
+        \item Wann?
+            \begin{itemize}
+                \item Dienstag 10-12h 00.08.038
+                \item Dienstag 12-14h 00.08.038
+            \end{itemize}
+        \item Übungsablauf, Aufgabentypen
+        \item Hausaufgaben
+            \begin{itemize}
+                \item Abgabe am Montag 14h, \alert{allein}
+                \item Rückgabe in der \alert{richtigen} Übung
+                \item Notenbonus für 40\% der Punkte, 40\% in der zweiten Hälfte
+            \end{itemize}
+        \item Klausur
+            \begin{itemize}
+                \item Endterm: Mi 31.07. 11.30-14h
+                \item Wiederholung: Do 26.09. 11-13.30h
+            \end{itemize}
+    \end{itemize}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Was ist Theoinf?}
+
+    Aus der VL
+    \vspace{1em}
+
+    \begin{itemize}
+        \item Automatentheorie
+            \begin{itemize}
+                \item Rechner mit endlichem oder kellerartigem Speicher
+            \end{itemize}
+            \vspace{0.5em}
+        \item Grammatiken
+            \begin{itemize}
+                \item Syntax von Programmiersprachen
+            \end{itemize}
+            \vspace{0.5em}
+        \item Berechenbarkeitstheorie
+            \begin{itemize}
+                \item Untersuchung der Grenzen, was Rechner prinzipiell können
+            \end{itemize}
+            \vspace{0.5em}
+        \item Komplexitätstheorie
+            \begin{itemize}
+                \item Untersuchung der Grenzen, was Rechner mit begrenzten Ressourcen können
+            \end{itemize}
+    \end{itemize}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Grundlegendes}
+
+    \begin{definition}
+        \begin{itemize}
+            \item Ein \alert{Alphabet} $\Sigma$ ist eine endliche Menge.
+            \item Ein \alert{Wort} über $\Sigma$ ist eine endliche Folge von Zeichen.
+            \item Eine Teilmenge $L \subseteq \Sigma^*$ ist eine \alert{formale Sprache}
+        \end{itemize}
+    \end{definition}
+
+    \vfill
+
+    \begin{definition}[Operationen auf Sprachen]
+        \begin{itemize}
+            \item $\alert{AB} = \left\{ uv \mid u \in A \wedge v \in B \right\}$
+            \item $\alert{A^n} = \left\{w_1 \ldots w_n \mid w_1 \ldots w_n \in A \right\}$,\qquad $A^0 = \{\epsilon\}$
+            \item $\alert{A^*} = \bigcup_{n \in \N_0} A^n$
+        \end{itemize}
+    \end{definition}
+\end{frame}
+
+\begin{frame}
+    \frametitle{DFA}
+
+    \begin{definition}[Deterministischer endlicher Automat]
+        Ein \alert{DFA} ist ein Tupel $M = (Q, \Sigma, \delta, q_0, F)$ aus einer/einem
+        \begin{itemize}
+            \item endlichen Menge von \alert{Zuständen} $Q$
+            \item endlichen \alert{Eingabealphabet} $\Sigma$
+            \item totalen \alert{Übergangsfunktion} $\delta : Q \times \Sigma \mapsto Q$
+            \item \alert{Startzustand} $q_0 \in Q$
+            \item Menge von \alert{Endzuständen} $F \subseteq Q$
+        \end{itemize}
+    \end{definition}
+
+    \vfill
+    \pause
+
+    \begin{center}
+        \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=]
+            \node[state, initial] (q0) {$q_0$};
+            \node[state, accepting] (q1) [right of = q0] {$q_1$};
+            \node[state] (q2) [right of = q1] {$q_2$};
+
+            \draw[->] (q0) edge [loop above] node {0} (q0);
+            \draw[->] (q2) edge [loop above] node {1} (q2);
+            \draw[->] (q0) edge [bend left] node {1} (q1);
+            \draw[->] (q1) edge [bend left] node {1} (q0);
+            \draw[->] (q1) edge [bend left] node {0} (q2);
+            \draw[->] (q2) edge [bend left] node {0} (q1);
+        \end{tikzpicture}
+    \end{center}
+\end{frame}
+
+\begin{frame}
+    \frametitle{NFA}
+    \begin{definition}[Nicht-Deterministischer endlicher Automat]
+        Ein \alert{NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit
+        \begin{itemize}
+            \item $Q, \Sigma, q_0, F$ wie ein DFA
+            \item \alert{Übergangsfunktion} $\delta : Q \times \Sigma \mapsto P(Q)$
+        \end{itemize}
+    \end{definition}
+
+    \vfill
+    \pause
+
+    \begin{center}
+        \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=]
+            \node[state, initial] (q0) {$q_0$};
+            \node[state, accepting] (q1) [right of = q0] {$q_1$};
+
+            \draw[->] (q0) edge [loop above] node {0,1} (q0);
+            \draw[->] (q0) edge node {1} (q1);
+        \end{tikzpicture}
+    \end{center}
+\end{frame}
+
+\begin{frame}
+    \frametitle{$\epsilon$-NFA}
+    \begin{definition}[NFA mit $\epsilon$-Übergängen]
+        Ein \alert{$\epsilon$-NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit
+        \begin{itemize}
+            \item $Q, \Sigma, q_0, F$ wie ein DFA
+            \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \mapsto P(Q)$
+        \end{itemize}
+    \end{definition}
+
+    \vfill
+    \pause
+
+    \begin{center}
+        \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=30, initial text=]
+            \node[state] (q1) {$q_1$};
+            \node[state, initial] (q0) [left of = q1] {$q_0$};
+            \node[state, accepting] (q2) [right of = q1] {$q_2$};
+
+            \draw[->] (q0) edge [red] node {$\epsilon$} (q1);
+            \draw[->] (q1) edge [loop above] node {0,1} (q1);
+            \draw[->] (q1) edge node {1} (q2);
+            \draw[->] (q0) edge [bend right, red] node {$\epsilon$} (q2);
+        \end{tikzpicture}
+    \end{center}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Automaten}
+    \begin{block}{Übergangsfunktionen}
+        Die Automaten $A = (Q, \Sigma, \delta, q_0, F)$ unterscheiden sich nur durch ihre Übergangsfunktionen.
+
+        \begin{description}
+            \item[DFA] $\delta : Q \times \Sigma \mapsto Q$
+            \item[NFA] $\delta : Q \times \Sigma \mapsto \alert{P(Q)}$
+            \item[$\epsilon$-NFA] $\delta : Q \times \alert{\left( \Sigma \cup \{\epsilon\} \right)} \mapsto \alert{P(Q)}$
+        \end{description}
+    \end{block}
+
+    \vfill
+
+    \begin{theorem}
+        \alert{DFA}, \alert{NFA} und \alert{$\epsilon$-NFA} sind gleich mächtig und lassen sich ineinander umwandeln.
+    \end{theorem}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Tutoraufgabe 3}
+
+    \begin{center}
+        \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=]
+            \node[state, initial] (q0) {$q_0$};
+            \node[state, accepting] (q1) [above right of = q0] {$q_1$};
+            \node[state] (q2) [right of = q1] {$q_2$};
+            \node[state] (q3) [below right of = q0] {$q_3$};
+            \node[state] (q4) [right of = q3] {$q_4$};
+
+            \draw[->] (q0) edge node {0} (q1);
+            \draw[->] (q0) edge node {1} (q3);
+
+            \draw[->] (q1) edge [loop above] node {0} (q1);
+            \draw[->] (q2) edge [loop right] node {1} (q2);
+            \draw[->] (q4) edge [loop right] node {0} (q4);
+
+            \draw[->] (q1) edge [bend left] node {1} (q2);
+            \draw[->] (q2) edge [bend left] node {0} (q1);
+            \draw[->] (q3) edge [bend left] node {0,1} (q4);
+            \draw[->] (q4) edge [bend left] node {1} (q3);
+        \end{tikzpicture}
+    \end{center}
+\end{frame}
+
+\end{document}
Binary file notes/ue01_notes.pdf has changed