# HG changeset patch # User Markus Kaiser # Date 1366668480 -7200 # Node ID 95b88347f4655c6ec759486561b75f3640d1abe2 # Parent 594b9dd142e74dd8d2717b4242e6532aa560b9b0 ue01 notes diff -r 594b9dd142e7 -r 95b88347f465 notes/tex/TU_Muenchen_Logo_Breit.pdf Binary file notes/tex/TU_Muenchen_Logo_Breit.pdf has changed diff -r 594b9dd142e7 -r 95b88347f465 notes/tex/beamerthemeLEA2.sty --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/notes/tex/beamerthemeLEA2.sty Tue Apr 23 00:08:00 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}} diff -r 594b9dd142e7 -r 95b88347f465 notes/tex/ue01_notes.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/notes/tex/ue01_notes.tex Tue Apr 23 00:08:00 2013 +0200 @@ -0,0 +1,224 @@ +\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{\inter} {\cap} % Schnittmenge +\newcommand{\union} {\cup} % Vereinigung +\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{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} diff -r 594b9dd142e7 -r 95b88347f465 notes/ue01_notes.pdf Binary file notes/ue01_notes.pdf has changed