\documentclass[12pt]{article}

\usepackage{ngerman,a4}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{alltt}
\usepackage[latin1]{inputenc}
\usepackage{graphicx}

\thispagestyle{empty}

\title{}
\author{}
\date{}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetC}{\ensuremath{\mathbb{C}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}
\newcommand{\bild}[4]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[width=#1cm]{#2}\\[0.2cm]
			\caption{#3}
			\label{#4}
	\end{figure}
	}

\begin{center}
	{\Huge Theoretische Informatik}
\end{center}
\noindent Rechnen an sich \\[0.5cm]
Was ist \glqq Rechnen\grqq ? \\
Welche Rechenmechanismen gibt es? \\
Kann man \glqq alles\grqq\ \glqq berechnen\grqq ? \\
Wie \glqq teuer\grqq\ ist Rechnen? \\ [0.5cm]

\noindent Rechenmodelle / Rechensituationen \\

\begin{enumerate}
	\item PC \\
	\bild{12}{20102004_modell_1.jpg}{Rechnermodell PC}{modell1} \\
		\noindent Auf bestimmte Eingaben sollen bestimmte Ausgaben erfolgen.
	
	\item AIRBUS \\
		Viele vernetzte Computereinheiten \\
		Eingaben: Steuerungen durch Besatzung, Sensoren (Temperatur, GPS, Luftgeschwindigkeit) \\
		Ausgabe: Info für Besatzung, Aktuatoren

	\item \glqq Einfachste Situation\grqq\ \\
	\bild{12}{20102004_modell_2.jpg}{Rechnermodell \glqq Einfachste Situation\grqq}{modell2} \\
		soll Funktion $F$: Zeichenketten $\to$ Zeichenketten ($\{0;1\}$ JA/NEIN) berechnen \\
		Eingabe: $s$; Ausgabe $F(s)$
\end{enumerate}
Einschub: Zeichenketten
\begin{itemize}
	\item Alphabet $\displaystyle \Sigma$: endliche Menge
	\item String (Zeichenkette) über $\displaystyle \Sigma$: endliche Folge von Elementen von $\displaystyle \Sigma$ z.B.: $v=v_1 v_2 ... v_k; \quad v_i \in \Sigma \quad \forall i$, $|v|=k$ (Länge)
	\item $\displaystyle \Sigma^k$: Menge der Strings der Länge $k$
	\item $\displaystyle \Sigma^0 = \{\varepsilon\}$; $\varepsilon$ ist der leere String
	\item $\displaystyle \Sigma^* = \bigcup_{k \ge 0} \Sigma^k$: Menge aller Strings über $\displaystyle \Sigma$ (mit endl. Länge)
	\item Konkatenation: $\displaystyle u,v \in \Sigma^*; \quad u \in \Sigma^l; v \in \Sigma^k$
		\begin{eqnarray*}
			uv & = & u_1u_2...u_lv_1...v_k \\
			u\varepsilon & = & u \\
			\varepsilon u & = & u
		\end{eqnarray*}
	\item $\displaystyle v \in \Sigma^*; i \in \SetN = \{0,1,...\}$
		\begin{eqnarray*}
			v^0 & = & \varepsilon \\
			v^i & = & v v^{i-1}
		\end{eqnarray*}
	\item $\displaystyle L \subset \Sigma^*$: \glqq Sprache über $\displaystyle \Sigma$\grqq
\end{itemize}
Einschub Ende. \\[0.5cm]
\glqq Maschine definiert Sprache\grqq
$$\{\left. s \in \Sigma^* \right| F(s) = \text{JA}\}$$
Welche Sprachen können von welchen Arten von \glqq Automaten\grqq\ berechnet werden? \\
3 Arten von Automaten: Endlicher Automat, Keller Automat, Turing Maschine
\begin{enumerate}
	\item Endlicher Automat \\
		\bild{12}{20102004_endlicher_automat.jpg}{Endlicher Automat}{endlicher_automat} \\
		endlich viele Steuerungsregeln folgender Form: \\
		Wenn Zustand $= q$ $\AND$ Eingabekopf liest Zeichen $a$ dann
		\begin{enumerate}[1.]
			\item Rücke Eingabekopf um eine Zelle nach rechts
			\item wechsle in Zustand $q'$
		\end{enumerate}
		$Q$: Zustandsmenge \\
		$s \in Q$: Startzustand \\
		$F \subset Q$: Endzustände \\
		Anfangskonfiguration: Maschine ist im Startzustand $s$, Eingabekopf ganz links \\
		Endkonfiguration: Maschine in einem der Endzustände, Eingabekopf ganz rechts \\
		Maschine akzeptiert einen Eingabestring $u$, wenn aus der Startkonfiguration durch wiederholtes Anwenden von Regeln eine Endkonfiguration erreicht (wird) werden kann. \\[0.3cm]
		Bsp.: $\displaystyle \Sigma = \{a,b\}, \quad Q=\{\underbrace{0}_{=s},1,2\}, \quad F=\{2\}$ \\
		\begin{center}
		\begin{tabular}{c|c|c}
			derzeitiger Zustand & gelesenes Zeichen & neuer Zustand \\
			0 & a & 1 \\
			0 & b & 0 \\
			1 & a & 2 \\
			1 & b & 0 \\
			2 & a & 2 \\
			2 & b & 0
		\end{tabular}
		\end{center}
		Beispiel akzeptiert Sprache aller Strings über $\{a,b\}$, die in aa enden. \\
		\begin{center}
		\begin{tabular}{c|c|c}
			derzeitiger Zustand & gelesenes Zeichen & neuer Zustand \\
			$\alpha$: 0 & a & 0 \\
			$\beta$: 0 & b & 0 \\
			$\gamma$: 0 & a & 1 \\
			$\delta$: 1 & a & 2
		\end{tabular}
		\end{center}
		nicht-deterministische Maschine: mehr als eine Regel in gleicher Situation anwendbar
	\item Kellerautomat \\
		\bild{12}{20102004_keller_automat.jpg}{Keller-Automat}{keller_automat} \\
		$Q$: Zustandsmenge \\
		$s \in Q$: Startzustand \\
		$F \subset Q$: Endzustände \\
		Regeln: \\
		Wenn Zustand $= q$ $\AND$ Eingabekopf liest $a$ $\AND$ Arbeitskopf liest $A$, dann
		\begin{enumerate}[1.]
			\item gehe in Zustand $q'$
			\item Bewege Eingabekopf
				\begin{enumerate}[(i)]
					\item rechts
					\item nicht
				\end{enumerate}
			\item Arbeitskopf:
				\begin{enumerate}[(i)]
					\item ersetze $A$ durch $A'$
					\item Kopf nach unten, $A$ gelöscht
					\item Kopf nach oben, schreibe $A'$
				\end{enumerate}
		\end{enumerate}
		Anfangskonfiguration: Zustand $=s$, Eingabekopf ganz links, Arbeitsband: Lesekopf ganz unten, $z$ in unterster Zelle \\
		Endkonfiguration: Maschine in einem der Endzustände. Eingabekopf ganz rechts
		$$\{a^n b^n | n \ge 1\}$$
\end{enumerate}

\end{document}
