# HG changeset patch # User Tobias Gurdan # Date 1366889379 -7200 # Node ID bd943ee06f84a908025325d1f5ba11bd0e0e1c18 # Parent 1a26c2c66bea112b93c4bd093079f6f2a2267ac9# Parent 73037b3dde608aa54345f18e2a840e7917103459 merge heads diff -r 1a26c2c66bea -r bd943ee06f84 .hgignore --- /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 diff -r 1a26c2c66bea -r bd943ee06f84 notes/tex/TU_Muenchen_Logo_Breit.pdf Binary file notes/tex/TU_Muenchen_Logo_Breit.pdf has changed diff -r 1a26c2c66bea -r bd943ee06f84 notes/tex/beamerthemeLEA2.sty --- /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}} diff -r 1a26c2c66bea -r bd943ee06f84 notes/tex/ue01_notes.tex --- /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} diff -r 1a26c2c66bea -r bd943ee06f84 notes/ue01_notes.pdf Binary file notes/ue01_notes.pdf has changed