% -*- TeX -*- -*- DE -*-

\chapter{Optimierung}
\section{Einführung}
Die Architektur nach von Neumann hat sich als Grundlage für die Rechnerentwicklung bewährt.
Das Prinzip des minimalen Hardware- und Speicher-Aufwands führt zu kostengünstigen Realisierungen.
Mit der fortschreitenden Entwicklung der Halbleiter-Technologien wurde es allerdings möglich,
von diesem Prinzip abzuweichen und die Architektur in Hinblick auf höhere Performanz
zu erweitern.
In diesem Kapitel werden die wichtigsten Ansätze vorgestellt.
%
Ausgangspunkt ist die in Kapitel \ref{c_neumann} beschriebene Grundstruktur.
Wir hatten bei der Diskussion bereits die schwer wiegenden Defizite, die unmittelbar aus
der Architektur resultieren, kennen gelernt.
Die zwei wesentlichen Punkte sind:
\begin{itemize}
    \item Der einheitliche Bus stellt einen Flaschenhals dar.
    \item Bei der Bearbeitung der Befehle wechseln sich Hol- und Ausführungsphasen ab.
    Dadurch sind in der meisten Zeit nur einige Komponenten aktiv.
\end{itemize}
In den folgenden Abschnitten werden verschiedene Ansätze zur Behebung dieser Schwachstellen vorgestellt.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Harvard-Architektur} \index{Harvard-Architektur}
Eine prinzipielle Alternativ besteht in der Auftrennung des Bussystems.
In der Harvard-Architektur werden getrennte Speicherbereiche für Daten und Programme
eingeführt.
Jeder Speicherbereich ist über ein eigenes Bussystem mit der CPU verbunden.
Das Konzept wird vornehmlich bei Digitalen Signalprozessoren (DSP) realisiert. \index{Signalprozessoren}
Diese auf hohe Geschwindigkeit optimierten Prozessoren werden zur Verarbeitung
von Audio- oder Videodaten eingesetzt.
Dabei wird durch die Harvard-Architektur ein schneller Datendurchsatz erzielt.
Mit einer Instruktion kann dann der nächste Befehl und gleichzeitig Daten geladen werden.
Ein Beispiel für den Motorola DSP56300 aus dem Manual\cite{dsp56300_fm} ist:
\begin{verbatim}
mac y0,x1,b     x:(r4)-,x1   y:(r0)+,y0
; Signed Multiply Accumulate b = b + y0 * x1
;               Lade aus Speicherbereich X, Adresse in Register R4
;               nach Register X1, anschließend noch R4 = R4 -1
;                            Aus Bereich Y, Adresse in R0 nach Y0
;                            R0 = R0 +1
\end{verbatim}
Zeitgleich mit einer arithmetischen Operation werden neue Werte aus zwei
verschiedenen Speicherbereichen geladen.
Die Adressierung erfolgt indirekt über Register.
Zusätzlich werden auch die Inhalte dieser Register aktualisiert.
In der arithmetischen Operation werden noch die alten Werte in den Registern verwendet.
Die neu geladenen Werte stehen dann für die nächste Instruktion bereit.

Einen Schritt weiter ging die Firma Analog Devices.
Bei dem 32-Bit Signalprozessoren SHARC\textregistered\
wurde das Konzept noch um einen
zusätzlichen Bus für die Ein- und Ausgabe erweitert.
Dafür wurde die Bezeichnung \emph{Super Harvard Architektur }eingeführt.

% http://www.analog.com/processors/processors/sharc/overview.html
% Super Harvard Architecture
% is designed with an emphasis on balance between the computational core performance,
% large internal dual-ported SRAM, and I/O throughput.
% The architecture is referred to as "super" Harvard because
% it advances the concept of separate data memory and program memory typical of Harvard
% architecture microprocessors by adding an I/O processor and I/O bus.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{DMA} \index{DMA}
In der ursprünglichen von Neumann Architektur werden alle Datentransfers über
die CPU abgewickelt.
Das Prinzip zeigt Bild \ref{f_ohne_dma} am Beispiel eines Transfers von einem
Gerät in den Speicher.
Um einen Wert zu kopieren ist folgender Ablauf notwendig:
\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
\begin{enumerate}
    \item Wert von Quelle in CPU laden.
    \begin{enumerate}
        \item MOV-Befehl laden.
        \item Wert laden.
    \end{enumerate}
    \item Wert von CPU zu Ziel speichern.
    \begin{enumerate}
        \item MOV-Befehl laden.
        \item Wert speichern.
    \end{enumerate}
\end{enumerate}
Wenn man weiterhin bedenkt, dass auch der MOV-Befehl beispielsweise beim 8086 mehrere
Bustransfers für Befehlscode und Adressen bedingt,
wird klar wie aufwändig ein solcher Transfer wird.
Andererseits kommen solche Transfers häufig vor.
In vielen Fällen wird nicht nur ein einzelner Transfer benötigt, sondern
ganze Blöcke sollen kopiert werden.

\begin{figure}[btp]
\begin{center}
\input{ohne_dma.pic}
\caption { \label{f_ohne_dma}  Ablauf beim Datentransfer}
\end{center}
\end{figure}

Eine wesentliche Verbesserung  bietet in solchen Situationen
der \emph{Direct Memory Access} (DMA). \index{Direct Memory Access}
Die Grundidee ist, die Aufgabe des Datentransfers an eine eigene Einheit (DMA-Controller) zu delegieren.
Die CPU muss sich dann nicht mehr selbst um den Transfer kümmern, sondern beauftragt
den (oder einen von mehreren) DMA-Controller.
Sie gibt Quelle, Ziel und Umfang der Daten vor.
Der DMA-Controller führt dann den Transfer selbständig durch und informiert die CPU
nach erfolgreichem Abschluss.
Bild \ref{f_mit_dma} illustriert dieses Konzept.

%
\begin{figure}[btp]
\begin{center}
\input{mit_dma.pic}
\caption { \label{f_mit_dma}  Ablauf beim Datentransfer mit DMA}
\end{center}
\end{figure}
%

Während der DMA-Transfer erfolgt, kann die CPU andere Aufgaben erledigen.
Dafür wird sie auch weiterhin selbst auf den Bus zugreifen.
Durch eine entsprechende Steuerlogik wird dafür gesorgt, dass es dabei
zu keinen Konflikten kommt.
Die Kontrolle behält dabei die CPU.
Sie gibt über ein spezielles Signal den Bus für
den DMA frei.
Dann wird entweder ein einzelner Wert oder ein ganzer Block (\emph{Block mode})
übertragen.
Anschließend erhält die CPU die Kontrolle zurück.

Dieser Vorgang wiederholt sich, bis alle angegebenen Daten transferiert sind.
Die Zählung der Daten übernimmt der DMA-Controller.
Nach Abschluss informiert er -- beispielsweise per Interrupt -- die CPU.

Aus Sicht des Anwenders ist der DMA relativ einfach.
Man muss nur durch entsprechende Befehle an den DMA-Controller den
Vorgang starten.
Alles andere läuft dann automatisch im Hintergrund ab.
Man muss lediglich beachten, dass der Zustand des Zielspeichers während des DMA-Vorgangs
nicht definiert ist.
Würde man während dieser Zeit eine Zelle aus diesem Bereich lesen,
könnte man entweder bereits den neuen  oder noch den alten Wert erhalten,
je nach dem ob der DMA diese Zelle bereits erreicht hat oder nicht.
Das Resultat hängt von den Details im Timing ab.
Daher sollte sinnvollerweise die Anwendung während eines laufenden DMA-Transfers
den Zielspeicher nicht verwenden.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Pipelining} \index{Pipelining}
In Kapitel \ref{c_Zentraleinheit} hatten wir gesehen, wie die Ausführung eines Befehls
in mehreren Phasen abläuft.
Dabei kann man unterscheiden zwischen Phasen mit und ohne Buszugriff.
Nehmen wir als vereinfachtes Modell an, dass ein Befehl nur  zwei Phasen umfasst:
\begin{enumerate}
    \item Holen des Befehls aus dem Hauptspeicher.
    \item Ausführen der Operation innerhalb der CPU.
\end{enumerate}
Dann ergibt sich folgendes Bild für die Abfolge von drei Befehlen:
\begin{center}
\begin{tabular}{|*{7}{p{4em}|}} \hline
   1& 2 & 3 & 4 & 5 & 6 & 7 \\ \hline
   Holen & Ausführen & Holen & \multicolumn{2}{c|}{Ausführen} & Holen & Ausführen \\ \hline
   \multicolumn{2}{p{8em}}{Befehl 1} & \multicolumn{3}{p{12em}}{Befehl 2} & \multicolumn{2}{p{8em}}{Befehl 3} \\
\end{tabular}
\end{center}
%
Der Ablauf zeigt den Wechsel zwischen den beiden Phasen.
In jeder Phase ist aber nur ein Teil des Systems aktiv, oder -- negativ formuliert -- der
andere Teil ist untätig und wartet.
Es bietet sich als Alternative an, die Befehle nicht streng sequentiell sondern überlappend zu bearbeiten.
Man kann die Situation gut mit der Fertigung von z.\,B. Autos vergleichen.
Die Arbeiten am nächsten Auto beginnen nicht erst, wenn ein Auto komplett fertig gestellt ist.
Vielmehr wird der Fertigungsprozess in viele einzelne Schritte unterteilt.
Sobald ein Schritt abgeschlossen ist, wird das entsprechende Auto einen Schritt weiter
gegeben und das nächste rückt nach.
Zu jedem Zeitpunkt befinden sich mehrere Autos in der Fertigungskette.
Sie durchlaufen den Prozess in Form eines Fließbandes.

Übertragen auf die Befehlsverarbeitung werden die Instruktionen ebenfalls durch
ein Fließband oder einen Schlauch (engl. \emph{Pipeline}) geschoben.
Aus dem obigen Beispiel wird dann folgender Ablauf:
\begin{center}
\begin{tabular}{|*{7}{p{4em}|}} \hline
   1& 2 & 3 & 4 & 5 & 6 & 7 \\ \hline %\cline{1-2}
   Holen & Ausführen                 &  \multicolumn{5}{c}{} \\ \cline{1-2}
   \multicolumn{2}{p{8em}}{Befehl 1} &  \multicolumn{5}{c}{} \\ \cline{2-4}
   \multicolumn{1}{c|}{} & Holen & \multicolumn{2}{c|}{Ausführen} &  \multicolumn{3}{c}{}  \\ \cline{2-4}
   \multicolumn{1}{c}{}  & \multicolumn{3}{p{12em}}{Befehl 2}          &  \multicolumn{3}{c}{}  \\ \cline{3-5}
   \multicolumn{2}{c|}{} & Holen & \emph{Warten} & Ausführen  &  \multicolumn{2}{c}{}  \\ \cline{3-5}
   \multicolumn{2}{c}{}  & \multicolumn{5}{l}{Befehl 3}            \\
\end{tabular}
\end{center}
Während der erste Befehl noch intern ausgeführt wird, kann bereits der zweite Befehl
aus dem Speicher geholt werden.
Bei dem zweiten Befehl dauert die Ausführung länger als das Holen des dritten Befehls.
Der dritte Befehl kann dementsprechend erst nach einem Wartetakt weiter geschoben werden.

Dieses Prinzip wird als \emph{Pipelining} oder Fließband-Prinzip bezeichnet. \index{Fließband-Prinzip}
In dem Beispiel verkürzt sich die Verarbeitungszeit für drei Befehle um 2 Einheiten.
Demgegenüber steht ein gewisser Mehraufwand, um die parallele Verarbeitung der einzelnen
Stufen zu ermöglichen.
Insbesondere werden zusätzliche Register benötigt, um die in den einzelnen Stufen benötigten
Werte getrennt zu halten.

Wie groß die Ersparnis tatsächlich wird, hängt von den einzelnen Verarbeitungszeiten
und der Struktur der Befehle ab.
Lassen sich mehr Verarbeitungsstufen separieren, ist ein größerer Gewinn durch
die gleichzeitige Bearbeitung aufeinander folgender Befehle erzielen.
Der größte Gewinn wird erzielt, wenn die Pipeline permanent gefüllt ist.
Dann sind alle Einheiten gleichzeitig aktiv und der Durchsatz wird maximal.
Am Ende jeder Pipeline-Phase ist ein Befehl fertig ausgeführt.

Dieser optimale Betrieb lässt sich nicht mehr aufrecht erhalten, sobald Abhängigkeiten
zwischen den Befehlen zu berücksichtigen sind.
Besonders problematisch sind Sprünge.
Von welcher Adresse der nächste Befehle zu holen ist, steht erst nach Analyse des
Sprungbefehls fest.
Daher kann die nächste Instruktion erst mit einer Verzögerung geladen werden.

Ohne besondere Maßnahmen würden in der Zwischenzeit die nächsten Befehle in
der linearen Folge geladen und mit ihrer Ausführung begonnen werden.
Die Bearbeitung dieser "`falschen"' Befehle ist abzubrechen.
Außerdem müssen gegebenenfalls bereits vorgenommene Veränderungen an Registern o.\,ä.
zurück genommen werden.
Um diesen Mehraufwand zu vermeiden, kann man nach jedem Sprungbefehl entsprechend
viele Instruktionen einfügen, die keine weiteren Auswirkungen haben.
Die meisten Assembler kennen für derartige Zwecke eine Instruktion NOP (\emph{No Operation}).

Noch schwieriger ist die Situation bei bedingten Sprüngen.
Hier dauert es oft noch länger bis entschieden ist, ob der Sprung ausgeführt werden soll oder
nicht.
Moderne Prozessoren verwenden ausgeklügelte Strategie für solche Fälle.
Eine Möglichkeit ist,
die Wahrscheinlichkeit für den Sprung abzuschätzen (\emph{Branch prediction}). \index{Branch prediction}
Eine plausible Annahme ist, dass das gleiche Ergebnis wie bei dem letzten Durchgang
eintrifft.
Damit liegt man z.\,B. bei Zählschleifen immer außer beim letzten Durchgang richtig.
In der Mehrzahl der Fälle kann daher die Ausführung nahtlos fortgesetzt werden.
Wurde der falsche Pfad gewählt, müssen die angefangenen Operationen abgebrochen und
eventuelle Veränderungen rückgängig gemacht werden.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Cache-Speicher} \index{Cache-Speicher}
\subsection{Funktionsweise}
Mit zunehmender Geschwindigkeit moderner Prozessoren erweist sich immer mehr der
Speicherzugriff als bestimmend für die erzielbare Leistungsfähigkeit.
Sehr schnelle Speicherbausteine sind teuer.
Gleichzeitig benötigen Betriebssystem und Anwendungen immer mehr Speicherkapazität.
Preisgünstigere Speicherbausteine benötigen länger für einen Zugriff als die CPU für die Anforderung.
Nach einer Leseanforderung muss die CPU eine gewisse Zeit auf das Ergebnis warten.
Anstatt weiter zu arbeiten, fügt sie Wartezyklen (\emph{wait states}) ein.

Einen Ausweg bietet die Einführung eines so genannten Cache-Speichers (Cache, engl. geheimes Lager).
Ausgangspunkt ist die Beobachtung, dass in der Regel auf bestimmte Speicherzellen viel
häufiger zugegriffen wird als auf andere.
Ein typisches Beispiel sind Schleifen.
In dem Programmfragment
\begin{verbatim}
for( i=0; i<anzahlAktien; i++ ) {
    depotWert += aktie[i].wert;
}
\end{verbatim}
wird einerseits der Programmcode für jeden Schleifendurchgang wiederholt.
Andererseits werden immer wieder die Variablen \texttt{i}, \texttt{anzahlAktien} und \texttt{depotWert}
verwendet.
Wenn man diese Befehlscodes und Daten in einem schnellen Zwischenspeicher legt,
kann die Ausführung weitgehend von dem langsameren Zugriff auf den Hauptspeicher abgekoppelt werden.
Bild \ref{f_cache} illustriert diese Idee.

%
\begin{figure}[btp]
\begin{center}
\input{cache.pic}
\caption { \label{f_cache}  Schneller Cache-Speicher zwischen Hauptspeicher und CPU}
\end{center}
\end{figure}
%

Das Konzept lässt sich leicht an Alltagssituationen erläutern.
Wenn man ein Buch zur Arbeit benötigt, wird man es nicht nach jedem Nachschlagen zurück
in das Regal stellen.
Vielmehr wird man es griffbereit auf den Schreibtisch legen.
Im Laufe der Zeit wird sich ein kleiner Stapel von aktuell verwendeten Büchern auf dem
Schreibtisch aufbauen.
Erst wenn dort der Platz nicht mehr ausreicht, werden Bücher wieder zurück ins Regal gestellt.

\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
Wieder bezogen auf einen Rechner gestaltet sich ein Lesezugriff wie folgt:
\begin{itemize}
    \item Es wird geprüft, ob von der entsprechenden Zelle bereits eine Kopie im Cache vorliegt.
    \item Wenn ja (\emph{Cache hit}), wird diese Kopie verwendet.
    \item Wenn nein (\emph{Cache miss}), muss der Wert vom Hauptspeicher geholt werden.
    Gleichzeitig wird eine Kopie für die weitere Arbeit in den Cache gelegt.
\end{itemize}
Sofern die Anzahl der Treffer im Cache groß ist, ergibt sich ein deutlicher Gewinn
an Performanz.
Wie hoch der Gewinn tatsächlich ausfällt, hängt von der Anwendung ab.

\subsection{Cache-Organisation}
Bei dem ersten Lesezugriff auf eine Zelle, wird sie in den Cache aufgenommen.
Dabei genügt es nicht, den Inhalt zu zu kopieren.
Vielmehr muss auch die Adresse vermerkt werden.
Ein Eintrag oder eine Zeile im Cache hat dann die Form
\begin{center}
\begin{tabular}{|c|c|} \hline
  Adresse & Wert \\ \hline
\end{tabular}
\end{center}
In der Praxis benötigt man noch weiter Bits, um z.\,B. die Gültigkeit der Daten anzuzeigen.
Festzustellen, ob eine Adresse bereits im Cache liegt, ist in diesem einfachen
Konzept recht aufwändig.
Da eine Zelle in ein beliebige Zeile des Caches liegen kann,
sind alle Zeilen im Cache auf diese Adresse hin zu vergleichen.

Einfacher ist die Situation, wenn man anhand der ursprünglichen Adresse auf den
Speicherplatz im Cache schließen kann.
Diese Art von Speicher, bei denen eine Verbindung zwischen Adresse und Inhalt besteht,
nennt man Assoziativ-Speicher. \index{Assoziativ-Speicher}
Betrachten wir als Beispiel folgende Situation:
\begin{itemize}
    \item Der Hauptspeicher ist 64 k groß (16-Bit Adressen).
    \item Der Cache-Speicher hat 256 Zeilen (8-Bit Adressen).
\end{itemize}
Eine einfache Strategie ist, die letzten 8 Bit der Speicheradresse als Index für
den Cache zu verwenden.
Angenommen die Speicherzelle $4f3e$ im Hauptspeicher ist zum ersten Mal angesprochen.
Dann wird davon das zweite Byte $3e$ oder $62_{10}$ abgetrennt und als Zeilenindex für den Cache verwendet.
In diese Zeile wird Adresse und Werte eingetragen.
Es ist allerdings nicht erforderlich, die komplette Adresse abzulegen.
Vielmehr liegt der zweite Teil bereits durch die Zeilennummer fest.
Es genügt also, das erste Byte zu vermerken.
Damit erhält man die Darstellung:
\begin{center}
\begin{tabular}{lc}
  62. (3e.) Zeile &
  \begin{tabular}{|c|c|} \hline
  Rest der Adresse:  $4f$ & Wert \\ \hline
  \end{tabular} \\
\end{tabular}
\end{center}
Um umgekehrt festzustellen, ob die Adresse $4f3e$ bereits im Cache liegt,
muss man nur nachschauen, ob in der $3e$. Zeile der Adressteil $4f$ steht
und die Zeile als gültig markiert ist.

Mit diesem Prinzip kann der Zugriff einfach realisiert werden.
Der Nachteil ist, dass es nur eine mögliche Ablagestelle für eine
Adresse gibt.
Entsprechend viele Adressen teilen sich diese eine Zeile.
In unserem Beispiel würde auch die Adresse $b23e$ in die gleiche Zeile gehören.
Dazu müsste der alte Eintrag für $4f3e$ überschrieben werden.
Auch wenn im Cache noch andere freie Zeilen sind,
kann keine andere Zeile genutzt werden.
Unter ungünstigen Umständen kann eine schlechte Auslastung des Cache-Speichers resultieren.
In der Praxis benutzt man daher Anordnungen, bei denen für eine gegebene Adresse
zwei oder vier  Ablagestellen in Frage kommen.
Derartige Speicher werden dementsprechend als 2-fach oder 4-fach assoziativ bezeichnet.
Sie bieten einen guten Kompromiss zwischen Vergleichsaufwand und guter Auslastung.

Wenn alle Ablageplätze belegt sind, muss einer der alten Werte überschrieben werden.
Eine häufig verwendete Strategie besteht darin, den am längsten nicht mehr benutzen
Wert zu verdrängen (\emph{Least-Recently-Used} LRU).
Dazu werden entsprechende Zähler in den Cache integriert, um die Zugriffsstatistik zu erfassen.

%Konsistenz

\subsection{Realisierungen}
Je nach Lage des Cache-Speichers unterscheidet man.
\begin{itemize}
    \item Level 1 (L1): Der Cache ist in den Prozessor integriert.
    \item Level 2 (L2): Der Cache befindet sich in einem eigenen Baustein,
    der über eine schnelle Verbindung an den Prozessor angeschlossen ist.
\end{itemize}
Neben diesen beiden Hauptklassen werden auch die Bezeichnungen Level 0 bei Entkopplung der
Komponenten innerhalb der CPU und Level 3 bei Systemen mit mehreren Prozessoren
verwendet.
Weiterhin werden oft getrennte Cache-Speicher für Programme und Daten verwendet.

% Allgemeine Verwendung
Caching ist ein sehr wirksames Verfahren, um Zugriffe zu beschleunigen.
Daher findet es auf verschiedensten Ebenen Anwendung.
Durch einen vorgeschalteten  Cache-Speicher werden Daten von der Festplatte
schneller verfügbar.
Das  HyperText Transport Protocol (HTTP) unterstützt das Caching von Web-Seiten.
Dabei werden z.\,B. auf dem lokalen Rechner Kopien der zuletzt besuchten Seiten abgelegt.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{RISC-Rechner} \index{RISC-Rechner}
Der 8086 ist ein Beispiel für einen Prozessor mit einem recht umfangreichen Befehlssatz.
Sein Befehlssatz umfasst sowohl vergleichsweise einfache Operationen (\texttt{INC AX}) als auch
komplexe Operationen (z.\,B. \texttt{LOOP}-Befehl).
Die aufwändigen Befehle werden intern durch eine Folge von Mikrobefehlen realisiert.
Ein derartiger Befehlssatz bedingt unterschiedliche Längen und Ausführungszeiten
für die verschiedenen Befehle.

Mit der zunehmenden Integration wuchs der Befehlsatz immer mehr an.
Andererseits musste man feststellen, dass ein so mächtiger Befehlssatz
kaum vollständig ausgenutzt wurde.
Untersuchungen ergaben:
\begin{itemize}
    \item 80\% der Zeit wird mit 20\% der Befehlen ausgefüllt.
    \item 90\% aller Befehle sind Load/Store oder einfache ALU-Befehle.
\end{itemize}
Komplexe Befehle kommen demnach relativ selten vor und ihr Beitrag zur Ausführungszeit
ist relativ gering.
Dabei spielt sicherlich auch eine Rolle, dass weder ein Programmierer noch ein
Compiler Befehlsätze mit teilweise mehr als 400 verschiedenen Instruktionen
optimal benutzen kann.

Ausgehend von diesen Überlegungen entstand das Konzept der \emph{Reduced Instruction Set Computer} (RISC)
als Gegenentwurf zu den \emph{Complex Instruction Set Computer} (CISC). \index{CISC}
Wie der Name sagt, wird bei diesem Ansatz ein kleiner Befehlsvorrat verwendet.
Gleichzeitig sollen die Befehle möglichst einfach gestaltet sein.
Durch diese Beschränkungen ist eine Vereinheitlichung
im Befehlsformat möglich,
so dass die Dekodierung der Befehle erleichtert wird.
Weiterhin können die Befehle direkt als Schaltungen realisiert werden.
Die Notwendigkeit von Mikroprogrammen entfällt.
Im einzelnen gelten für RISC-Architekturen folgende Punkte.
\begin{itemize}
    \item Speicherzugriffe sind nur über LOAD und STORE Befehle möglich.
    Die ALU-Befehle können nur auf Register arbeiten.
    Soll ein Wert im Speicher verändert werden, so muss er zunächst in ein Register
    geladen werden. Dann kann er verändert und anschließend wieder in den Speicher
    zurück geschrieben werden.
    Ein CISC-Befehl wie \texttt{INC [200]} muss in drei RISC -Befehle aufgeteilt werden.
    \item RISC-Prozessoren haben viele Register.
    Da die Bearbeitung von Werten im Speicher aufwändig ist, sind viele Register
    zur internen Zwischenspeicherung sinnvoll.
    Üblich sind 50 bis 200 Register.
    \item Die Befehle haben ein einheitliches Format (gleiche Länge, gleicher Aufbau).
    Damit ist die Dekodierung einfach.
    \item Durch den überschaubaren und einheitlichen Befehlssatz ist eine Pipeline mit
    mehreren Stufen (z.\,B. Sun Sparc 4 Stufen) möglich. \index{Pipeline}
    Wird in jedem Zeittakt ein Befehl in der Pipeline fertig, so bezeichnet man
    den Prozessor als skalar.
    Pro Zeittakt wird dann ein Befehl ausgeführt, unabhängig davon wie lange die
    Bearbeitung in der Pipeline dauert.
\end{itemize}
In der RISC-Architektur wird das Fehlen von einigen leistungsfähigen Befehlen oder
Adressierverfahren durch die schnelle Ausführung und viele interne Register kompensiert.
Um die Leistungsfähigkeit voll auszuschöpfen,
muss ein Compiler diese Eigenschaften berücksichtigen.
Beispielsweise ist es oft möglich, durch geschicktes Umordnen von Anweisungen
Konflikte in der Bearbeitung der Pipeline zu vermeiden oder zumindest zu verringern.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Parallele Strukturen}
Die Ausführungsgeschwindigkeit eines Rechners lässt sich nicht beliebig steigern.
Bei allen Fortschritte der Halbleitertechnik mit beeindruckenden Steigerungen
der Taktraten existieren doch grundsätzliche, physikalische Grenzen.
Außerdem sind Systeme, die an der Grenze des zur Zeit gerade machbaren liegen,
erfahrungsgemäß sehr teuer.
Als Alternative bietet es sich an, anstelle einer sehr aufwändigen Einheit mehrere
einfache Einheiten parallel zu schalten.

Wenn es gelingt, ohne übermäßigen Verwaltungsaufwand die Arbeit auf mehrere Prozessoren zu verteilen,
so ist eine preisgünstige Lösung möglich.
Der Gewinn durch Parallelisierung hängt sehr stark von der Aufgabe ab.
Viele rechenintensive Probleme lassen sich gut in unabhängig voneinander zu bearbeitenden
Teilprobleme aufteilen.
Allerdings gibt es stets eine Grenze für diese Aufteilung.
Gerne wird folgendes Beispiel aus dem Alltagsleben benutzt, um diese
Problematik zu veranschaulichen:
\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
\begin{itemize}
    \item Ein Maurer braucht 8 Stunden für eine Wand.
    \item Zwei Maurer brauchen 4 Stunden für die selbe Wand.
    \item Wie lange brauchen 100 Maurer für die gleiche Wand?
\end{itemize}
Der Idealfall, dass $N$ Einheiten die Aufgabe in der Zeit $T/N$ erledigen,
wird nur selten erreicht.
Wie hoch die Leistungssteigerung (\emph{Speedup}) ausfällt, hängt vom Problem
und der Lösungsstrategie ab.
Häufig sind für sequentielle und parallele Bearbeitung jeweils unterschiedliche
Lösungswege optimal.

Die Parallelisierung kann auf verschiedenen Ebenen erfolgen.
Auf oberster Ebene werden vollständige Rechner parallel betrieben.
Mit diesem Ansatz wurden beispielsweise durch koordinieren Einsatz vieler, über
das Internet verbundener Rechner einige Verschlüsselungsverfahren geknackt.
Ein anderes Beispiel ist die Suche nach außerirdischen Signalen in Aufnahmen
von Radioteleskopen.
Im Projekt SETI\symbol{64}home (SETI steht für \emph{Search for Extraterrestrial Intelligence}) \index{SETI}
kann jeder Anwender auf seinem Rechner sonst nicht benötigte Rechenleistung für die Suche bereit stellen
\cite{setihome}.

Auf der untersten Ebene sind in einem Prozessor mehrere parallel arbeitende Einheiten integriert.
Im einfachsten Fall führen diese Einheiten alle die gleiche Operation an mehreren Daten aus.
Typische Anwendungen findet man in der Bildbearbeitung,
wenn die gleiche Operation (z.\,B. Umwandlung von Farbwerten in Graustufen) auf
alle Punkte eines Bildes angewendet werden soll.
Allgemein lassen sich Verfahren, bei denen  Vektoren oder Matrizen verwendet werden,
leicht aufteilen.
%
\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
Die Parallelität kann räumlich oder zeitlich sein.
Je nachdem unterscheidet man:
\begin{itemize}
    \item Feldrechner: \index{Feldrechner}
    viele gleichartige Einheiten führen gleichzeitig eine Instruktion
    auf unterschiedlichen Daten aus.
    Die  Einheiten können von unterschiedlicher Komplexität sein (vollständige Prozessoren oder
    spezialisierte Schaltungen)
    und über eigenen Speicher verfügen.
    \item Vektorrechner: \index{Vektorrechner}
    eine Einheit ist für die mehrfache, schnelle Ausführung der gleichen
    Operation ausgelegt.
    Dazu dient eine spezielle Pipeline-Struktur. \index{Pipeline}
    Bei langen Vektoren sind nach dem Füllen der Pipeline alle Stufen gleichmäßig
    ausgelastet.
\end{itemize}

Komplexer ist die Situation, wenn mehrere Einheiten jeweils eigene Befehle ausführen.
Die einzelnen Befehle sind dann zu einem sehr langen Befehlsword
(\emph{very long instruction word} VLIW) zusammen gefasst. \index{VLIW}
Aus diesem Befehlswort entnimmt jede Einheit ihre Instruktion und Information über Operanden.

Diese Anordnung ist theoretisch sehr leistungsfähig.
Mit $N$ parallelen Einheiten können $N$ voneinander unabhängige Befehle angestoßen werden.
Das Problem liegt in der Aufteilung der Arbeit.
Einerseits sollen möglichst viele Einheiten gleichzeitig aktiv sein.
Andererseits muss sichergestellt sein, dass es zu keinen Konflikten
bezüglich Ablauf oder Daten kommt.
In dieser Allgemeinheit wird der Compiler vor eine schwierige Aufgabe gestellt.
Daher findet man in der Praxis nur vereinfachte Versionen dieses Konzeptes.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Klassifikation von Rechnern}
Eine systematische Einteilung von Rechnern in Bezug auf Parallelität stammt von M. J. Flynn
\cite{flynn}. \index{Flynn, M. J.}
Er unterscheidet (Tabelle \ref{t_flynn}):
\begin{itemize}
    \item SISD \emph{Single Instruction, Single Data}: \index{SISD}
    Der klassische von-Neumann Rechner.
    Zu einem Zeitpunkt wird eine Instruktion ausgeführt, die auf einem Datenwert
    oder einem zusammen gehörenden Satz von Datenwerten
    (z.\,B. zwei Eingangswerte, ein Ausgangswerte)
    wirken.
    \item SIMD \emph{Single Instruction, Multiple Data}: \index{SIMD}
    Die gleiche Instruktion wird auf mehrere Datensätzen angewandt.
    Zu dieser Gruppe gehören Feld- und Vektorrechner.
    \item MISD \emph{Multiple Instructions, Single Data}: \index{MISD}
    Keine sinnvolle Kombination.
    Hierbei würden mehrere Instruktionen gleichzeitig auf einen Datensatz angewandt.
    \item MIMD \emph{Multiple Instructions, Multiple Data}: \index{MIMD}
    Allgemeinster Fall mit unterschiedlichen Befehlen für unterschiedliche Datensätze.
    Realisierungen sind Multiprozessorsysteme.
\end{itemize}

\begin{table}
  \centering
  \caption{\label{t_flynn}Klassifikation nach Flynn}
  \begin{tabular}{|c|c|c|}\hline
                       & Ein Befehl & Mehrere Befehle \\ \hline
    Ein Datenwert      & SISD & MISD \\ \hline
    Mehrere Datenwerte & SIMD & MIMD \\ \hline
  \end{tabular}
\end{table}

In der Praxis sind die Grenzen zwischen den Kategorien fließend.
Ähnliches gilt für die Unterscheidung zwischen RISC und CISC.
Der Trend ist, das Beste aus verschiedenen Konzepten zu kombinieren.
% -*- TeX -*- -*- DE -*-

\chapter{Der Intel 8086 Prozessor}
\section{Einführung}
In diesem Kapitel werden wir am Beispiel des Prozessors Intel 8086 eine Architektur im Detail
kennen lernen.
Dieser Prozessor wurde 1978 von Intel eingeführt.
Er besteht aus etwa 30000 Transistoren und arbeitet mit Taktfrequenzen von 5 bis 10 MHz.
Der Prozessor ist aufgrund seiner Überschaubarkeit gut geeignet, um grundlegende Prinzipien
zu veranschaulichen.
Gleichzeitig ist er Teil der IA-32 Intel Architektur \cite{ia32_v1, ia32_v2},
und damit ein Vorläufer der modernen Prozessoren der Pentium-Gruppe.

Als praktische Beispiele werden kleine Programme dienen.
Zur Entwicklung und Ausführung der Programm wird das Programm Emu8086
(www.emu8086.com) eingesetzt.
Dieses Programm bietet eine komplette Entwicklungsumgebung mit Assembler,
Simulator (Software Emulator) und Debugger.
Der Assembler übersetzt Programme, die in der zugehörigen Assembler-Sprache geschrieben sind,
in ausführbaren Maschinencode.

Der Simulator ist die software-mäßige Nachbildung des Prozessors.
Es handelt sich so zu sagen um einen virtuellen Prozessor mit all seinen Komponenten.
In dem Simulator können Programme ausgeführt werden und darüber hinaus
Ein- und Ausgabe mit virtuellen Geräten
ausgetauscht werden.
Zur gezielten Fehlersuche dient ein eingebauter Debugger.
Damit können beispielsweise Programme beim Eintreten von vordefinierten Ereignissen (Break points)
angehalten werden.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Register}
Der 8086 verfügt über 8 allgemeine Register:
\begin{itemize}
    \item AX - Accumulator register (unterteilt in AH und AL)
    \item BX - Base address register (unterteilt in BH und BL)
    \item CX - Count register (unterteilt in CH und CL)
    \item DX - Data register (unterteilt in DH und DL)
    \item SI - Source Index register
    \item DI - Destination Index register
    \item BP - Base Pointer
    \item SP - Stack Pointer
\end{itemize}
Die vier 16 Bit Register AX bis DX können in je zwei 8 Bit breiten Teilen
angesprochen werden (H wie High und L wie Low).
Ist beispielsweise der Wert von CX 0xe45f, so hat CH den Wert 0xe4 und CL den Wert 0x5f.
Eine Änderung in einem der Teilregister betrifft genauso das gesamte Register.
Löscht man CH, so hätte in dem Beispiel CX anschließend den Wert 0x005f.
Wie die Namen zeigen, sind die 8 Register jeweils für bestimmte Zwecke vorgesehen.
Welche Verwendung im einzelnen durch entsprechende Befehle unterstützt wird,
werden wir später im Detail sehen.
Allerdings ist man relativ frei in der Nutzung.
Zur erweiterten Adressierung stehen vier Segmentregister zu Verfügung:
\begin{itemize}
    \item CS Code Segment
    \item DS Daten Segment
    \item ES Extra Segment
    \item SS Stack Segment
\end{itemize}
% jetzt schon Adressierung ?
Die Adressierung wird später im Abschnitt \ref{s_Speicheradressierung} im Detail beschrieben.
Schließlich gibt es noch zwei Spezialregister:
\begin{itemize}
    \item IP - Instruction Pointer
    \item Flags Register
\end{itemize}
IP weist auf den aktuellen Befehl.
Das Flags Register enthält Statusinformationen und wird daher auch als Statusregister bezeichnet.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Erstes Beispiel}
Das folgende Programm lädt zunächst zwei Zahlen in die beiden Register AX und BX.
Dazu wird der MOV-Befehl\footnote{Groß- und Kleinschreibung spielen bei dem Assembler keine Rolle.
Die Schreibweisen MOV und mov sind gleichwertig} verwendet.
Der erste Operand bezeichnet das Ziel, der zweite enthält direkt den Zahlenwert.
Zahlenwerte  können in der Assemblersprache in verschiedenen Systemen angegeben werden.
Die Endungen b, o und h kennzeichnen Werte als Binär-, Oktal- oder Hexadezimalzahl.
Im Programm werden dann beide Registerinhalte mit dem Befehl ADD addiert.
Das Ergebnis $322_{10}$ oder $142_{16}$ steht dann in AX.

Die Befehlszeilen bestehen jeweils aus dem Befehlswort (Mnemonic) und den eventuellen Operanden.
Ein Semikolon markiert den Rest der Zeile als Kommentar.
Neben den eigentlichen Assemblerbefehlen können Direktiven an den Assembler eingefügt werden.
Entsprechende Anweisungen beginnen mit dem \verb!#!-Zeichen.
%
\begin{verbatim}
#make_COM#

; COM file is loaded at CS:0100h
ORG 100h    ; Programm an Adresse 100h beginnen

mov AX,67   ; Kommentare beginnen mit ;
mov BX,0ffh ; Hex-Konstanten werden mit h gekennzeichnet und
            ; müssen mit einer Ziffer beginnen
add AX,BX   ; AX = AX + BX
ret         ; Ende des Programms
\end{verbatim}
%
Das Beispiel ist als COM-Typ angelegt.
Dies ist eine einfache Form von ausführbaren Programmen.
Mit der Anweisung \texttt{ORG} (\emph{origin}, engl. Ursprung) wird die Anfangsadresse des Programms festgelegt.
Bei Programmen vom Typ COM sind die ersten $100_{16}$ Zellen für Systeminformationen
reserviert.

Der Assembler generiert aus diesem Programm die entsprechenden Binärdarstellung.
Dieser Code muss dann noch in den Hauptspeicher geladen werden.
Dann kann die Ausführung ab der Startadresse beginnen.
Der Simulator ersetzt für Testzwecke eine realen Maschine.
Im Speicher liegt das Programm in folgender Form vor:
%
\begin{center}
\begin{tabular}{*{9}{|c}||l|} \hline
100 & 101 & 102 & 103 & 104 & 105 & 106 & 107 & 108 & Adresse \\ \hline
b8  &  43 & 00  & bb  & ff  & 00  & 03  & c3  & c3  & Maschinencode \\ \hline
\multicolumn{3}{|c}{mov AX,67}  & \multicolumn{3}{|c}{mov BX,0ffh}
    & \multicolumn{2}{|c|}{add AX,BX} & ret  & Befehl        \\ \hline
\end{tabular}
\end{center}
%
Die beiden MOV-Befehle benötigen jeweils nur ein Byte Maschinencode.
Dabei enthält dieses Byte bereits die Information über das Ziel-Register.
In den beiden darauf folgenden Bytes steht der Zahlenwert, wobei das niedrigwertige Byte zuerst kommt.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Befehle}
In diesem Abschnitt wird der Befehlssatz des 8086 vorgestellt.
Zunächst werden die wesentlichen Befehlsarten erläutert.
Anschließend werden einige Befehle im Detail untersucht.
Intel unterscheidet zwischen folgenden 6 Befehlsarten:
\begin{enumerate}
    \item Transportbefehle:
    Befehle, mit denen Werte zwischen verschiedenen Einheiten kopiert werden können.
    Dazu gehört der wahrscheinlich am häufigsten verwendete Befehl MOV,  PUSH und POP
    für den Stack sowie IN und OUT für periphere Ein- und Ausgabe.
    \item Arithmetische Befehle:
    Die Grundoperationen für ganzzahlige Operanden ADD, SUB, MUL und DIV und weitere
    Befehle wie INC, DEC, NEG, $\ldots$.
    \item Logische Befehle:
    Bitoperatoren AND, OR, XOR, NOT sowie diverse Shift-Operatoren.
    \item Verarbeitung von Zeichenketten (Strings):
    Einige Befehle zur Bearbeitung von Zeichenketten.
    Die Befehle verwenden die beiden Register SI und DI zur vereinfachten Adressierung
    aufeinander folgender Zeichen (Bytes).
    \item Sprungbefehle:
    Sprünge innerhalb eines Moduls, entweder unbedingt (JMP) oder nur falls
    eine bestimmte Bedingung erfüllt ist (z.\,B. JNZ jump not zero).
    Weiterhin gehören zu dieser Gruppe Befehle zum Aufruf eines Unterprogramms (CALL)
    und zur Rückkehr (RET).
    \item Prozessorkontrolle:
    Befehle zum Setzen und Löschen von Bits im Statusregister (STC set carry flag, CLC clear carry flag)
    und allgemeine Anweisung wie HLT zum Anhalten des Prozessors.
\end{enumerate}


%\subsection{Arithmetische Befehle}
\subsection{Addition}
Der typische Vertreter der arithmetischen Befehle ist der Befehl ADD zur Addition.
Der Befehl enthält zwei Operanden und das Ergebnis überschreibt den ersten Operanden.
Für die Operanden sind folgende Kombinationen möglich:
\begin{center}
\begin{tabular}{ll}
Register & Speicher \\
Speicher & Register \\
Register & Register \\
Speicher & Konstante \\
Register & Konstante \\
\end{tabular}
\end{center}
Einer der Operanden kann eine Speicherzelle sein.
Speicherzellen können in der Form [\emph{Adresse}] angegeben werden.
Die Anweisung
\begin{verbatim}
add [107h],2    ; Addiere 2 zu Speicherzelle 107h
\end{verbatim}
addiert den Wert 2 zu dem Inhalt der Speicherzelle mit der Adresse $107_{16}$.
Jedoch ist es bei dem 8086 nicht möglich, zwei Speicherzellen direkt zu addieren.
Vielmehr muss zunächst einer der Werte in ein Register geladen werden.
Die Register können sowohl in voller als auch halber Breite benutzt werden.
Dabei müssen allerdings die Operanden gleiche Größe haben.
Dementsprechend wird die Addition mit 8 oder 16 Bit ausgeführt.
\begin{beispiel} Beispiele für Addition:
\begin{verbatim}
add ax,-1      ; Register und Konstante
add ah,bl      ; zwei Halbregister
;  add al,bx  Halb- und Ganzregister geht nicht!
\end{verbatim}
\end{beispiel}
Mit der Ausführung werden im Statusregister die betroffenen Bits gesetzt oder gelöscht.
Im wesentlichen werden eingetragen:
\begin{center}
\begin{tabular}{ll}
Carry Flag    & Übertrag \\
Overflow Flag & Überlauf \\
Zero Flag     & Ergebnis gleich 0 \\
Sign Flag     & Vorzeichen des Resultats \\
\end{tabular}
\end{center}


\begin{uebung} Addition von Halbregistern:
Welcher Wert wird nach folgendem Programm im Register AX stehen?
\begin{verbatim}
mov ax,0103h
add ah,al
\end{verbatim}
\end{uebung}


\subsection{Multiplikation und Division}
Die Befehle für vorzeichenlose Multiplikation und Division sind  MUL und DIV.
Die Varianten IMUL und IDIV berücksichtigen die Vorzeichen.
In Abschnitt \ref{ss_zahlenbereich} hatten wir gesehen, dass für die Multiplikation
im allgemeinen zusätzlicher Platz für das Ergebnis benötigt wird.
Gleichzeitig sind Multiplikation und Division besonders aufwändige Operationen.
Daher nehmen die Befehle eine gewisse Sonderstellung ein.

Anders als etwa bei ADD wird ein Operand stets aus dem Akkumulator genommen.
Als zweiter Operand ist ein Register oder eine Speicherzelle möglich.
Konstanten können nicht direkt verwendet werden.
Der genaue Ablauf hängt von der Größe des zweiten Operanden ab.
Handelt es sich um einen 8 Bit Wert, so wird er mit AL multipliziert und das Ergebnis
in AX geschrieben.
Sowohl AH und AL sind daran beteiligt.
Selbst wenn das Resultat in AL passt, wird AH trotzdem gelöscht.
%
\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
\begin{beispiel} Multiplikation mit 8 Bit Wert\\
Nach
\begin{verbatim}
mov al,3
mov bl,2
mul bl         ; AX = AL * BL
\end{verbatim}
enthält AX den Wert $6$, ein eventueller Wert in AH geht verloren.
\end{beispiel}
Bei einem 16 Bit großen Operanden wird mit dem gesamten AX multipliziert.
Der obere Teil das 32 Bit Resultats wird in DX abgelegt.
%
\begin{beispiel} Multiplikation mit 16 Bit Wert\\
\begin{verbatim}
mov ax,4000
mul ax         ; AX quadrieren
\end{verbatim}
Ergibt in AX $2400_{16}$ und in DX $00F4_{16}$, insgesamt also $00F42400_{16}$ entsprechend
$16000000_{10}$
\end{beispiel}
%
Die Division verläuft umgekehrt.
Bei einem 8 Bit Operanden wird AX durch diesen Wert dividiert.
Das Resultat kommt in AL.
Zusätzlich wird der verbleibende Rest (AX \% Operand) in AH geschrieben.
%
\begin{beispiel} Division durch 8 Bit Wert\\
Nach
\begin{verbatim}
mov ax,17
mov bl,5
div bl
\end{verbatim}
führt zu AL=3 (17/5) und AH=2 (17\%5).
\end{beispiel}
Die Division bei 16 Bit Operanden verwendet wiederum AX und DX als Ausgangswert und
berechnet DX:AX/Operand.
Das Ergebnis steht anschließend in AX, der Rest in DX.
Falls das Ergebnis der Division zu groß für das Zielregister AX ist,
so wird dies als Fehler signalisiert.
Den dabei benutzen Interrupt-Mechanismus werden wir in Abschnitt \ref{s_interrupt}
kennen lernen.


\subsection{Sprungbefehle}
Häufig ist es notwendig, vom linearen Programmablauf abzuweichen.
So sind Pro\-gramm\-ab\-schnitte mehrfach zu durchlaufen
oder in Abhängigkeit von Zwischenergebnissen soll zu unterschiedlichen
Fortsetzungen verzweigt werden.
In modernen Hochsprachen stehen dafür entsprechende übersichtliche Konstruktionen
wie if ... then ... else oder while ... zur Verfügung.
Damit sind Sprungbefehle nicht mehr notwendig und sollten - sofern die Sprachen sie
überhaupt noch anbieten - vermieden werden.

Anders ist die Situation auf Assembler-Ebene.
Der Prozessor kennt im wesentlichen nur Sprungbefehle.
Die Umsetzung der Konstruktionen der Hochsprache in Sprünge übernimmt ein Compiler.
Bei der Programmierung in Assembler ist der Programmierer gefordert, die Ablaufsteuerung durch entsprechende
Sprungbefehle selbst zu  realisieren.

Der 8086 verfügt über mehrere Sprungbefehle sowie einen speziellen Befehl zur einfachen
Implementierung von Zählschleifen.
Mit dem absoluten Sprungbefehl JMP wird die Ausführung an der angegebenen Adresse fortgesetzt.
Die Adressen können als Absolutwerte oder -- gekennzeichnet durch ein \verb!$! vor der Zahl -- relativ zur
momentanen Adresse angegeben werden.
Um die Eingabe der Adressen zu vereinfachen, unterstützt der Assembler Sprungmarken (Label).
Eine solche Marke wird in der Form \emph{Name:} vor einer Anweisung eingetragen.
Bei JMP \emph{Name} ersetzt der Assembler den Namen durch die Adresse.
\begin{beispiel} Sprungbefehl\\
\begin{verbatim}
l1: mov cx,10    ; Sprungmarke l1
    inc ax
again:
    add ax,cx    ; Sprungmarke again
    ...          ; weiterer Code
    jmp again
    ...
    jmp l1
    ...
    jmp $-10     ; um zehn Adressen zurück springen
\end{verbatim}
\end{beispiel}

Bei bedingten Sprüngen wird die entsprechende Bedingung geprüft, und nur wenn
sie erfüllt ist, erfolgt der Sprung.
Ansonsten folgt die nächste Anweisung in der linearen Abfolge.
Die Bedingungsprüfung beruht auf dem Statusregister.
Bei der Ausführung des Sprungbefehls wird der Wert des entsprechenden Flags geprüft.
So erfolgt der Sprung JZ (jump if zero), wenn das Zero Flag gesetzt ist.
Das bedeutet aber, dass zuvor das Statusregister entsprechend gesetzt werden musste.
Daher muss unmittelbar vorher eine entsprechende Operation ausgeführt werden.
Die Abfolge ist demnach
\begin{center}
Operation $\to$ Statusregister wird gesetzt $\to$ Bedingung prüfen $\to$ Sprung
\end{center}
In den meisten Fällen ist ohnehin ein Befehl notwendig, dessen Auswirkung
dann getestet werden kann.
Ansonsten kann der Befehl CMP verwendet werden.
Er vergleicht zwei Operanden indem er die Differenz bildet.
Das Statusregister wird entsprechend gesetzt, aber das Resultat nirgends abgelegt.
Zwischen dem relevanten Befehl und dem Sprung können "`neutrale"' Befehle,
die die entsprechenden Statusbits nicht beeinflussen, eingefügt werden.

Die bedingten Sprünge testen auf die verschiedensten Bedingungen und berücksichtigen
dabei teilweise auch mehr als nur ein Statusbit.
So erfolgt JGE (jump if greater or equal) wenn das Zero Flag gesetzt ist oder
das Sign Flag auf positiv steht.
Von den Befehle ist auch die negierte Form JNxxx wie z.\,B. JNZ (jump if not zero) verfügbar.
Das folgende Beispiel zeigt die Verwendung eines bedingten Sprung zur
Programmierung einer Schleife, in der Zahlen aufaddiert werden.
Das Register BX übernimmt die Rolle des Zählers.
%
\begin{beispiel} Addition der Zahlen $10,9,\ldots,1$\\
\begin{verbatim}
    mov bx,10     ; Zähler nach BX
    mov ax,0      ; vorsorglich AX löschen
l:  add ax,bx     ; Aufsummieren
    dec bx        ; Herunterzählen
    jnz l         ; noch nicht 0 ?
\end{verbatim}
\end{beispiel}
Solange der Befehl \texttt{DEC BX} noch nicht 0 ergibt, wird durch den Sprung die nächste
Addition ausgeführt.
Am Ende steht die Summe $55_{10}$ bzw. $37_{16}$ im Akkumulator AX.
Da diese Art von Schleifen häufig vorkommt, gibt es dafür einen eigenen Befehl LOOP.
Dabei wird das Register CX (Count register) eingesetzt.
Zu Beginn wird die gewünschte Anzahl von Wiederholung in CX geschrieben.
Dann führt der LOOP-Befehle folgende Aktionen aus:
\begin{itemize}
    \item Er dekrementiert CX: CX = CX - 1
    \item Falls CX ungleich 0 ist, springt er an die angegebene Stelle.
\end{itemize}
Aus dem Beispiel wird mit dieser Vereinfachung:
\begin{beispiel} Addition der Zahlen $10,9,\ldots,1$ mittels LOOP Befehl\\
\begin{verbatim}
    mov cx,10    ; Zähler muss nach CX
    mov ax,0     ; vorsorglich AX löschen
l1: add ax,cx    ; Aufsummieren
    loop l1
\end{verbatim}
\end{beispiel}
Ähnlich wie bei dem Befehl MUL bedingt die Vereinfachung eine Festlegung.
Der Zähler steht immer in CX und in jeder Iteration wird er um den Wert 1 erniedrigt.
Damit lassen sich ein Großteil der vorkommenden Schleifen effizient realisieren.
Lediglich in Spezialfällen -- z.\,B. mit einem Inkrement ungleich 1 -- ist eine
aufwändigere Lösung erforderlich.

\begin{uebung} Verkehrsampel\\
\label{ueb:Verkehrsampel}
Mit dem Befehl OUT \emph{Port},AX wird der Wert in AX in den I/O-Port mit der
angegebenen Nummer geschrieben.
Damit können externe Geräte (Device) angesprochen werden.
Unter der Portnummer 4 wird im Simulator eine Steuerung für 4 Verkehrsampeln angesprochen.
Über die einzelnen Bits können die Farben geschaltet werden (0 aus, 1 ein).
Es gilt:
\begin{itemize}
    \item Bit 0,1,2 für Grün, Gelb, Rot bei Ampel 1
    \item Bit 3,4,5 für Grün, Gelb, Rot bei Ampel 2
    \item Bit 6,7,8 für Grün, Gelb, Rot bei Ampel 3
    \item Bit 9,10,11 für Grün, Gelb, Rot bei Ampel 4
\end{itemize}
\begin{enumerate}
    \item Schreiben Sie ein Programm, das alle Kombinationen durchläuft.
    \item In einer zweiten Variante sollen alle Lampen einzeln getestet werden.
    (Hinweis: der Befehl SHL Register,Konstante schiebt den Inhalt eines Registers
    um die angegebene Anzahl von Stellen nach links).
    \item Implementieren Sie einen realistischen Ablauf, bei dem z.\,B. die Ampeln 1 und 3 sowie
    2 und 4 jeweils den gleichen Zustand haben.
\end{enumerate}
\end{uebung}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Speicheradressierung}
\label{s_Speicheradressierung}
\subsection{Adressbereich}
Der 8086 verwendet eine Wortbreite von 16 Bit.
Damit lassen sich $2^{16}=65536=64k$ Adressen ansprechen.
Um den Bereich zu vergrößern, werden die Adressen aus zwei 16 Bit Werten
gebildet.
Dazu werden die Segmentregister CS, DS, ES und SS verwendet. \index{Segmentregister}
Eine vollständige Adresse besteht dann aus der Segmentadresse und dem
so genannten Offset.
Mit den vier Segmentregister sind vier einzelne Bereiche vorgegeben.
Im einzelnen sind dies wie die Namen der Register anzeigen
\begin{itemize}
    \item Programmcode (CS)
    \item Daten (DS)
    \item Stack (SS)
    \item Extra (2.Datensegment) (ES)
\end{itemize}
Für die tatsächliche Lage dieser Segmente gibt es keine zwingenden Vorgaben.
Sie können überlappen oder komplett getrennt voneinander liegen.
Bei Programmen vom Typ COM liegen alle vier Segmente übereinander.

Intern wird bei jedem Speicherzugriff das zueinander passende Paar von
Segmentregister und Adressregister
verknüpft.
Die Adresse eines Befehls wird beispielsweise aus den Werten in den Registern CS und IP
gebildet.
Im Laufe der Zeit wurden zwei verschiedene Strategien zur Berechnung verwendet.
Zunächst wurde unter dem Betriebssystem DOS der Real-Mode eingesetzt. \index{Real-Mode}
Das modernere Verfahren ist der Protected-Mode. \index{Protected-Mode}

\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
Im  Real-Mode wird aus den beiden 16 Bit Werten eine 20 Bit große Adresse berechnet,
so dass sich insgesamt ein Adressbereich von $2^{20}=1M$ ergibt.
Die Vorschrift dazu ist einfach:
\begin{itemize}
    \item Segmentadresse: Segmentregister wird mit $16$ ($10_{16}$) multipliziert.
    Dies entspricht einer Verschiebung um 4 Stellen nach links.
    \item Gesamtadresse: Segmentadresse + Offset
\end{itemize}
Man schreibt dies in der Form \emph{Segmentregister}:\emph{Adressregister}.
Die Adressberechnung läuft automatisch ab.
Beispielsweise wird beim Laden des nächsten Befehls der Wert in IP mit dem Wert
in CS verknüpft.
%
% ToDo: Hier noch grafische Darstellung einfügen
%
\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
\begin{beispiel} Adressberechnung in Real-Mode\\
Sei CS=2F53h und  IP=2E95h.
Dann berechnet sich für CS:IP oder 2F53:2E95 die Adresse wie folgt:
\begin{itemize}
    \item Segmentadresse: $2F53h * 10h = 2F530h$
    \item Gesamtadresse:  $2F530h + 2E95h = 323C5h$
\end{itemize}
Als tatsächliche Adresse wird der Wert CS:IP=$323C5h$ genommen.
\end{beispiel}
Solange man innerhalb eines Segments bleibt, braucht man lediglich zu Beginn des Programms
einmal die Segmentregister zu laden. \index{Segmentregister}
Das Programm verhält sich dann so, als ob nur 64k Speicher vorhanden wären.
Mit diesem Konzept können auch leicht mehrere Programme gleichzeitig im Speicher gehalten werden.
Das System muss dann lediglich die jeweiligen Segmentadressen verwalten.

Die Segmentgrenzen lassen sich in Schritten von 16 verschieben.
Dies erlaubt bei knappem Speicherplatz eine sehr feine Aufteilung praktisch ohne Lücken.
Allerdings leidet die Transparenz, da die Zuordnung nicht eindeutig ist.
Mehrere Kombinationen von Segmentadresse und Offset führen zu einer gegebenen 20 Bit Adresse.
So könnte in unserem Beispiel die Adresse $323C5h$ auch durch $2F54$:$2E85h$ angesprochen werden.

Im Protected-Mode (ab 80286 verfügbar) werden die Werte in den \index{Protected-Mode}
Segmentregistern nicht mehr direkt zur Adressgenerierung
herangezogen, sondern stellen Selektoren dar.
Ein solcher Selektor bezeichnet einen Index in einer
Deskriptortabelle.
Der Deskriptor wiederum enthält dann u.a. die Basisadresse und die Größe eines Segmentes.
In dem Deskriptor sind außerdem Zugriffsrechte festgelegt.
Damit ist es als Beispiel möglich, das Programmsegment als "`read-only"' zu markieren
und damit gegen unbeabsichtigte Veränderungen zu schützen.

\begin{uebung} Adressberechnung in Real-Mode\\
Geben Sie mindestens zwei verschiedene Kombinationen von
Segmentadresse und Offset an, über die im Real-Mode
die Adresse $4a36fh$ erreicht werden kann.
\end{uebung}

\subsection{Adressierungsmöglichkeiten}
Wesentlich für die Programmierung sind die Möglichkeiten,
Speicherzellen anzusprechen.
In diesem Abschnitt werden die verschiedenen Arten der Adressierung des 8086 vorgestellt.

\subsubsection{Registeradressierung}
Besonders einfach ist die Adressierung, wenn die zu verarbeitenden Daten in Registern stehen.
Dann wird im Befehl direkt der Name der Register angegeben.
Je nach Bedarf kann ein volles Register mit 16 Bit oder ein Halbregister mit 8 Bit spezifiziert werden.
Die Operation erfolgt dann in der entsprechenden Bitbreite.
Man spricht dann von Wort- und Byteoperationen.
\begin{beispiel} Registeradressierung\\
\begin{verbatim}
    mov bx,ax    ; Wortoperation
    mov al,bh    ; Byteoperation
    inc cx       ; Wortoperation
\end{verbatim}
\end{beispiel}


\subsubsection{Unmittelbare Adressierung}
Bei Befehlen mit zwei Operanden kann einer davon eine Konstante sein.
Der Wert ist dann im Befehl enthalten und steht im Speicher nach dem Maschinencode für den Befehl.
\begin{beispiel} Unmittelbare Adressierung\\
\begin{verbatim}
    mov bx,655
    add al,'a'
\end{verbatim}
\end{beispiel}
Zwei Anmerkungen:
\begin{enumerate}
    \item Eine Konstante kann kein Ziel sein.
    \item Eine Konstante ist nicht gegen Veränderungen geschützt.
    Es ist durchaus möglich, die entsprechende Speicherzelle zu verändern.
\end{enumerate}

\subsubsection{Direkte Adressierung}
Die Adresse im Speicher kann direkt als Konstante angegeben werden.
Zur Unterscheidung werden die Adressen in eckige Klammern gesetzt.
Die Zählung beruht auf Bytes.
Bei einer Wortoperation sind dann die beiden aufeinander folgenden Zellen betroffen.
\begin{beispiel} Direkte  Adressierung\\
\begin{verbatim}
    mov bx,[2000]  ; Inhalt von 2000 und 2001 nach BX
    add [2efh],bl  ; Inhalt von BL nach 2EFh
\end{verbatim}
\end{beispiel}


\subsubsection{Indirekte Adressierung}
Häufig ist es erforderlich, die Adressen variabel zu halten.
Bei der Verarbeitung von Feldern oder Zeichenketten ist es beispielsweise
erforderlich, ausgehend von einer Anfangsadresse eine ganze Reihe von Zellen
nacheinander zu bearbeiten.
Für derartige Anwendung besteht die Möglichkeit der indirekten Adressierung.
Hierbei befindet sich die Adresse, die verwendet werden soll, selbst in einem Register.
Im Befehl schreibt man den Namen des Registers in eckigen Klammern.
Die Anweisungen
\begin{verbatim}
    mov bx,200
    add ax,[bx]  ; AX + Inhalt von 200
\end{verbatim}
verwenden BX zur indirekten Adressierung.
Zunächst wird mit einem MOV-Befehl die Adresse nach BX kopiert.
Bei der Addition wird dann nicht etwa der Inhalt von BX (in diesem Fall 200) zu
AX addiert, sondern BX wird als Verweis oder Zeiger verwendet.
Dieser Zeiger deutet auf die Speicherzelle 200.
Von dort wird der zweite Wert für die Addition geholt.
Das Beispiel entspricht demnach der Anweisung
\begin{verbatim}
    add al,[200]  ; AL + Inhalt von 200
\end{verbatim}
Der Vorteil der indirekten Adressierung zeigt sich erst, wenn mit der Adresse selbst
gerechnet werden soll.
Die folgende Erweiterung des obigen Codes bildet die Summe aus den Werten in 10 aufeinander folgenden Adressen:
\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
\begin{verbatim}
    mov bx,200
    mov cx,10
l:
    add al,[bx]  ; AL + Inhalt von 200,201,...
    inc bx
    loop l
\end{verbatim}
Hier wird zunächst die Anfangsadresse geladen.
Nach jeder Addition wird die Adresse erhöht.
Veränderungen an BX bewirken, dass der Zeiger anschließend auf eine andere
Speicherzelle zeigt.

Der Mechanismus der indirekten Adressierung über Index oder Zeiger
wird immer dann verwendet, wenn ein flexibler Zugriff erforderlich ist.
Ein Anwendungsfeld ist die Verarbeitung von Feldern von Speicherzellen
sei es als Zeichenketten oder als Vektoren oder Matrizen von Werten.
Auch die Übergabe größerer Objekte an Funktionen erfolgt über einen
Verweis auf die Speicherposition.

Implizit verwenden auch höhere Programmiersprachen diesen Mechanismus.
Die Zeiger in C sind eine direkte Umsetzung.
Die Sprache C erlaubt es, Zeiger auf Speicherstellen zu setzen und mit den
Adressen zu rechnen (Zeigerarithmetik).
Damit kann sehr effizienter Code geschrieben werden.

Allerdings ist der direkte Einsatz von Zeigern sehr fehlerträchtig.
Ein Fehler in der Adressberechnung kann dazu führen, dass vollkommen falsche
Zellen benutzt und eventuell geändert werden.
Derartige Fehler führen zu schwer nachvollziehbaren Seiteneffekten.
Aus diesem Grund ist bei vielen Sprachen keine direkte Manipulation
von Zeigern möglich.
So verzichteten die Designer der Sprache Java darauf, die Zeiger aus C zu übernehmen.
Intern finden allerdings viele Zugriffe über Verweise (Referenzen)
statt.
Die Adressberechnung wird vom Compiler eingefügt.
Es ist aber trotzdem für den Anwender wichtig, den Unterschied
zwischen einem direkten Zugriff auf ein Objekt und dem indirekten Zugriff
über eine Referenz zu kennen.

Die indirekte Adressierung bedingt einen zusätzlichen Aufwand bei der Ausführung.
Zunächst muss der Inhalt des Indexregisters geholt werden und dann erfolgt der
Zugriff auf die Speicherzelle mit dieser Adresse.
Daher ist im 8086 diese Möglichkeit auf die vier Register BX, SI, DI und BP beschränkt.

\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
\begin{beispiel} Indirekte  Adressierung\\
\begin{verbatim}
    mov bx,[si]
    add [bx],bl
    inc [di]
\end{verbatim}
\end{beispiel}


\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
\subsubsection{Erweiterte indirekte Adressierung}
Die Zeiger der indirekte Adressierung können beim Einsatz noch auf mehrere Arten erweitert werden.
Zunächst ist es möglich, eine konstante Verschiebung (Displacement) zu verwenden. \index{Displacement}
Dieser Wert \texttt{D} wird in der Form \verb![Reg]+D! angegeben.
Die gleichwertigen Formen \verb![Reg+D]!, \verb![D+Reg]! und \verb!D+[Reg]! sind ebenfalls erlaubt.
Bei der Befehlsausführung werden die Adresse im Register und die Verschiebung addiert.
Die Summe bezeichnet dann die Zelle, die tatsächlich verwendet werden soll.
Je nach Anwendung kann man  die Gesamtadresse in zwei Arten interpretieren:
\begin{enumerate}
    \item variable Basisadresse plus einer konstanten Verschiebung
    \item konstante Basisadresse plus einer variablen Verschiebung
\end{enumerate}
%
\begin{beispiel} Indirekte  Adressierung mit Displacement\\
Kopieren eines Speicherinhaltes in zweite Zelle mit dem Abstand 10:
\begin{verbatim}
    mov si,200
    mov bx,[si]       ; hole Wert von Adresse 200 nach BX
    mov [si]+9,bx     ; Kopiere Wert aus BX nach 209
\end{verbatim}
\end{beispiel}
%
\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
Weiterhin kann die Adresse als Summe über zwei Register gebildet werden.
Damit können sowohl Basis als auch Verschiebung flexibel gehalten werden.
%
\begin{beispiel} Indirekte  Adressierung mit zwei Registern \\
Kopieren eines Feldes mit 10 Bytes:
\begin{verbatim}
    mov bx,130      ; Adresse von Quelle
    mov bp,140      ; Adresse von Ziel
    mov si,10       ; Anzahl der Bytes
loop:
    mov al,[bx+si]  ; ein Byte holen
    mov [bp+si],al  ; und wieder schreiben
    dec si          ; herunter zählen
    jnz loop
\end{verbatim}
\end{beispiel}
%
Schließlich ist es noch möglich, zwei Register plus einer konstanten Verschiebung
zu verwenden.
%
\begin{beispiel} Indirekte  Adressierung mit zwei Registern und Displacement\\
\begin{verbatim}
mov cl,[bx+si]+5   ; Adresse: Inhalt von BX + Inhalt von SI + 5
mov cl,[bx+si+5]   ; kann man auch so schreiben
mov cl,[bx][si]+5  ; auch erlaubt
                   ; weitere Möglichkeiten siehe Handbücher
\end{verbatim}
\end{beispiel}
%
Allerdings sind dabei nicht alle Kombinationen der vier Register erlaubt.
Die möglichen Kombinationen zeigt folgende Darstellung:
\begin{center}
\begin{tabular}{|c|c|c|}
BX & SI & \\
   & \hphantom{BX}   & Displacement \\
BP & DI & \\
\end{tabular}
\end{center}
Die Regel dazu ist, dass aus jeder Spalte ein Wert gewählt werden kann.
Also ist beispielsweise BP+SI+Displacement möglich.
Andere Kombinationen wie BX+BP werden vom Assembler als Fehler abgelehnt.


\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
\begin{uebung} \label{ue_cga} Speicheradressierung\\
Ab der Adresse B8000 liegt der Speicher für das CGA-Display (Color Graphics Adapter). \index{CGA-Display}
Für jedes Zeichen des Bildschirms sind zwei Bytes reserviert:
Der ASCII-Code des Zeichens und die Festlegung der Farben.
\begin{enumerate}
    \item Schreiben Sie ein Programm, das alle ASCII-Zeichen ausgibt.
    \item Geben Sie mehrere Zeichen nebeneinander aus.
    \item Variieren Sie die Farbinformation.
\end{enumerate}
\end{uebung}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
\section{Variablen}
Im Assembler ist es möglich, Speicherplatz zu reservieren, mit einem Startwert zu füllen
und mit einem symbolischen Namen zu versehen.
Es stehen dazu zwei Befehle zur Verfügung:
\begin{enumerate}
    \item DB (Define Byte): Reserviert Bytes
    \item DW (Define Word): Reserviert Wörter (je 16 Bit)
\end{enumerate}
Die Syntax ist
\begin{center}
name DB|DW werte
\end{center}
%
Über den Namen kann später auf den Speicherplatz zugegriffen werden.
Ein einfaches Beispiel dazu:
\begin{beispiel} Variablen\\
\begin{verbatim}
    mov al,x       ; lade Inhalt von x nach AL
    ret
x   db    2        ; Variable x, 1 Byte groß, Anfangswert 2
\end{verbatim}
\end{beispiel}
%
Mit dem Befehl DB wird Speicherplatz reserviert.
Der Speicherplatz schließt sich direkt an den letzten Befehl an.
In dem Beispiel wurde er hinter die letzte Anweisung RET gesetzt.
Dies ist zwar sinnvoll, aber keineswegs zwingend notwendig.
Variablen und Programm können beliebig gemischt werden.
Syntaktisch ist auch die Folge
\begin{verbatim}
    mov al,x       ; lade Inhalt von x nach AL
x   db    2        ; Variable mitten im Programm
    ret
\end{verbatim}
korrekt.
Der Assembler wird einfach hinter der MOV-Anweisung ein Byte mit dem Wert 2 einfügen.
Bei der Programmausführung würde dies als Befehl interpretiert werden.
Die CPU würde die 2 als Maschinencode lesen, eventuell weitere Operanden holen
und den Befehl ausführen.
Es liegt in der Verantwortung des Anwenders dafür zu sorgen, dass Programm und Daten
klar getrennt bleiben.

Über den Namen x kann im Programm die Speicherzelle angesprochen werden.
Der Assembler verwaltet die Variablennamen und ersetzt sie im Code durch die
tatsächlichen Adressen.
Die Variablen erleichtern die Programmierung.
Aber im späteren ausführbaren Code sind sie verschwunden.

\begin{beispiel} Variablendefinitionen\\
\begin{verbatim}
feld  dw 2,3,4,5    ; Ein Feld mit 4 Werten
text  db 'Hallo',0  ; 5 Zeichen plus abschließende Null
      db 6fh        ; anonyme Variablen sind auch möglich
f5    db 4 dup(5)   ; mit n dup(x) werden n Kopien von x angelegt
ex    db 4+5*7      ; Ausdrücke werden vom Assembler berechnet
\end{verbatim}
\end{beispiel}

Letztlich sind die Variablen nur eine symbolische Darstellung einer Speicheradresse.
Es ist keinerlei Typ- oder Größeninformation mit ihnen verbunden.
Daher können sie genauso wie konstante Adressen verwendet werden.
Insbesondere können sie mit den Indexregistern für indirekte Adressierung kombiniert werden.

\begin{beispiel} Verwendung von Variablen\\
\begin{verbatim}
    inc x+5        ; Inhalt von (Adresse von x) + 5 erhöhen
    mov al,x[di]   ; Inhalt von (Adresse von x) + (Inhalt von DI) laden
    mov al,[di]+x  ; das selbe in anderer Schreibweise
\end{verbatim}
\end{beispiel}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Unterprogramme}
Wesentlich für die Programmierung größerer Projekte ist die Aufteilung in kleinere,
überschaubare Einheiten.
Sinnvollerweise ist eine solche Einheit für eine konkrete, in sich abgeschlossen Aufgabe
zuständig.
Sie erhält Werte, führt die entsprechende Aufgabe aus und gibt das Resultat zurück.

Je nach Programmiersprache heißen die entsprechenden Einheiten Funktionen, Prozeduren oder Methoden.
Allgemein kann man von Unterprogrammen sprechen.
Der Ablauf ist folgender:
\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
\begin{itemize}
    \item Das Hauptprogramm unterbricht die weitere Ausführung.
    \item Es ruft das Unterprogramm auf und spezifiziert die Eingangswerte (Argumente, Parameter).
    \item Das Unterprogramm führt seine Aufgabe aus.
    \item Das Unterprogramm meldet das Ergebnis (Rückgabewert) und
    gibt die Kontrolle an das Hauptprogramm zurück.
    \item Das Hauptprogramm setzt die weitere Ausführung fort.
\end{itemize}
\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
Ein Unterprogramm selbst kann weitere Unterprogramme aufrufen, eventuell sogar eine
weitere Instanz von sich selbst (Rekursion).
Bei der Umsetzung dieses Konzeptes stellen sich die Fragen:
\begin{itemize}
    \item Wie übergibt das Hauptprogramm die Kontrolle an das Unterprogramm?
    \item Wie kann nach Ende des Unterprogramms das Hauptprogramm fortgesetzt werden?
    \item Wie erfolgt die Übergabe von Werten?
\end{itemize}
Der Aufruf eines Unterprogramms bedeutet, dass die Ausführung mit der entsprechenden
Anweisung weiter geführt wird.
Intern muss dazu der Programmzähler auf die Anfangsadresse gesetzt werden.
Dies könnte durch einen Sprungbefehl geschehen.
Allerdings fehlt nach einem Sprung die Möglichkeit der Rückkehr.
Irgendwo muss also noch vermerkt werden, wo es nach Ende des Unterprogramms weiter gehen
soll.
Hier kommt der Stack ins Spiel.
Beim Aufruf eines Unterprogramms (Befehl CALL) wird die Adresse des nächsten Befehls im Hauptprogramm auf den
Stack gelegt.
Dann beginnt die Ausführung des Unterprogramms.
Das Ende des Unterprogramms ist durch einen Befehl RET (Return) markiert.
Mit dem Erreichen dieses Befehls wird die Adresse vom Stack geholt und die Ausführung dort fortgesetzt.

Welchen Vorteil bietet nun gerade der Stack zum Speichern der Adresse?
Betrachten wir dazu den Ablauf bei einer Verkettung von Unterprogrammaufrufen.
\begin{center}
\begin{tabular}{|p{18em}|p{3.5em}|} \hline
  Aktion & Stack \\ \hline \hline
  Hauptprogramm legt Rückkehradresse AHa auf Stack und ruft U1 auf &
  \rule[0mm]{0mm}{3.5ex} \begin{tabular}{|c|} \hline
   AHa \\ \hline
  \end{tabular}
  \\ \hline
  U1 legt Rückkehradresse AU1 auf Stack und ruft U2 auf &
  \rule[0mm]{0mm}{4.5ex}
  \begin{tabular}{|c|} \hline
   AU1 \\ \hline
   AHa \\ \hline
  \end{tabular}
  \\ \hline
  U2 legt Rückkehradresse AU2 auf Stack und ruft U3 auf &
  \rule[-4.8ex]{0mm}{10.5ex}
  \begin{tabular}{|c|} \hline
   AU2 \\ \hline
   AU1 \\ \hline
   AHa \\ \hline
  \end{tabular}
  \\ \hline
  U3 endet und nimmt Rückkehradresse AU2 vom Stack  &
  \rule[0mm]{0mm}{4.5ex}
  \begin{tabular}{|c|} \hline
   AU1 \\ \hline
   AHa \\ \hline
  \end{tabular}
  \\ \hline
  U2 endet und nimmt Rückkehradresse AU1 vom Stack  &
  \rule[0mm]{0mm}{3.5ex} \begin{tabular}{|c|} \hline
   AHa \\ \hline
  \end{tabular}
  \\ \hline
  U1 endet und nimmt Rückkehradresse AHa vom Stack  &
  \rule[0mm]{0mm}{3.5ex} \begin{tabular}{|c|} \hline
   \hphantom{AHa} \\ \hline
  \end{tabular}
  \\ \hline
\end{tabular}
\end{center}
Bei jedem weiteren Aufruf wird die Rücksprungadresse über die bereits abgespeicherten gelegt.
Am Ende eines Unterprogramms wird
die zuletzt abgelegt Adresse wieder entnommen.
Durch die Last In First Out Eigenschaft des Stacks werden die Adressen automatisch in
der passenden Reihenfolge abgelegt und entnommen.
Mit jedem weiteren Unterprogrammaufruf wächst der Stack um eine Adresse.
Umgekehrt schrumpft er bei einem Rücksprung wieder um eine Adresse.

Damit ist im wesentlichen auch schon die Realisierung von Unterprogrammen im Assembler beschrieben.
Unterprogramme selbst werden im Programmcode mit \emph{Name} PROC eingeleitet
und  mit \emph{Name} ENDP beendet.
Der dabei angegebene Name wird dann beim Aufruf CALL Name verwendet.

\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
\begin{beispiel} Unterprogramm\\
\begin{verbatim}
    MOV    AL,7
    CALL   u1      ; Aufruf
    RET

u1  PROC           ; Beginn des Unterprogramms
    ADD    AL,3    ; AL=AL+3
    RET            ; Rücksprung
u1  ENDP           ; Ende des Unterprogramms
\end{verbatim}
\end{beispiel}

\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
Es existiert kein Mechanismus, der die Übergabe von Werten zwischen Haupt- und Unterprogramm
automatisch übernimmt.
Vielmehr beruht die Übergabe auf "`Verabredungen"'.
Eine Möglichkeit ist, Register für die Übergabe zu benutzen.
So könnte die Festlegung für ein Unterprogramm sein:
\begin{itemize}
    \item Argument 1 steht in AX, Argument 2 steht in BX
    \item Ergebnis steht in CX
\end{itemize}
Der folgende Code zeigt den Ablauf am Beispiel eines Unterprogramms zur Bestimmung
des Maximums aus zwei Zahlen.
\begin{beispiel} Unterprogramm max\\
\begin{verbatim}
    MOV    AX,34     ; Argumente laden
    MOV    BX,22
    CALL   max       ; Aufruf
                     ; Resultat steht in CX
    RET

max PROC           ; Beginn des Unterprogramms
;  max erwartet zwei Werte in AX und BX, bestimmt das Maximum
;  und speichert das Ergebnis in CX
    CMP AX,BX      ; Werte vergleichen
    JLE fall2      ; BX <= AX ?
    MOV CX,AX      ; max = AX
    RET
fall2:
    MOV CX,BX      ; max = BX
    RET            ; Rücksprung
max ENDP           ; Ende des Unterprogramms
\end{verbatim}
\end{beispiel}

Wenn ein Unterprogramm  Register benutzt, werden die darin enthaltenen Werte überschrieben.
Ein Hauptprogramm kann daher nicht ohne weiteres davon ausgehen, dass nach der
Ausführung eines Unterprogramms alle Register noch ihre alten Inhalte enthalten.
Wenn die ursprünglichen  Werte anschließend weiter benötigt werden, so müssen
sie zu Beginn des Unterprogramms geeignet gespeichert und am Ende wieder geladen werden.
Dazu sind zwei Strategien möglich:
\begin{itemize}
    \item Die Verantwortung liegt beim Hauptprogramm.
    Es kümmert sich darum, dass Register mit wichtigem Inhalt gerettet und nach
    Rücksprung wieder gesetzt werden.
    \item Die Verantwortung liegt beim Unterprogramm.
    Das Unterprogramm speichert alle Register, die es verändert wird, ab und
    lädt sie vor dem Rücksprung wieder.
\end{itemize}
Beide Vorgehensweise haben Vor- und Nachteile.
Am einfachsten und übersichtlichsten ist es wohl, wenn das Unterprogramm alle Register,
die es verändern wird, vorsorglich sichert.
Allerdings entsteht dadurch ein häufig unnötiger Mehraufwand, indem Register kopiert werden,
die vom Hauptprogramm gar nicht verwendet werden.

Als Zwischenspeicher bietet sich wieder der Stack an.
Das Unterprogramm kann in diesem Fall zu Beginn mittels PUSH-Operationen die
betroffenen Register retten.
Am Ende werden sie über POP-Operationen wieder geladen.
Der Vorteil des Stacks erweist sich bei verschachtelten, mehrfachen Aufrufen.
Mehrere Kopien der Register liegen dann in unterschiedlicher Tiefe im Stack.
Hätte man demgegenüber einen festen Bereich als Zwischenspeicher festgelegt, so
würden die Werte bei jedem weiteren Aufruf überschrieben.
Mit dem gleichen Argument sollte ein Unterprogramm benötigten Speicherplatz für temporäre Variablen
ebenfalls in dem Stack anlegen.


\section{Interrupt}
\label{s_interrupt}
Eine spezielle Art von Unterprogrammen stellen Interrupts (engl. Unterbrechungen) dar.
Sie werden über einen eigenen Befehl INT \emph{Nummer} aufgerufen.
Der Wert von Nummer liegt zwischen 0 und 255, so dass 256 verschiedene Interrupts möglich sind.
Zusätzlich werden Untergruppen von Interrupts durch den Wert in AH spezifiziert.
Insgesamt ergeben sich damit $256 \cdot 256$ verschiedene Interrupts.
Andere Register (vornehmlich AL) dienen zur Übergabe von Parametern und Resultaten.
Interrupts stellen vor allem Schnittstelle zum System dar.
Über spezielle Interrupts können Geräte wie Bildschirm, Tastatur oder Festplatten
angesprochen werden.

\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
\begin{beispiel} Ausgabe der Zeichenfolge \emph{FB} über Interrupt 10H/0E.\\
\begin{verbatim}
MOV    AH, 0Eh    ; sub-function festlegen
                  ; AH wird durch Interrupt nicht verändert

MOV    AL, 'F'
INT    10h        ; Ausgabe

MOV    AL, 'B'
INT    10h        ; Ausgabe
\end{verbatim}
\end{beispiel}

\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
\begin{beispiel} Interrupt zum Lesen von Tastatur.\\
\begin{verbatim}
l:
mov ah,0
int 16h     ; Interrupt um 1 Zeichen von Tastatur zu lesen
mov bl,al   ; Ergebnis (Zeichen) steht in AL, nach BL kopieren
jmp l       ; Endlos-Schleife
\end{verbatim}
\end{beispiel}

\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
\begin{beispiel} Einfügen von einer Wartezeit von einer Sekunde.\\
\begin{verbatim}
; Interrupt 15 / AH=86h ist eine Wartefunktion. In den kombinierten
; Registern CX und DX wird die Anzahl von Mikrosekunden spezifiziert.
; 1 Sekunde entspricht 1 Million Mikrosekunden
; also nach CX:DX 1000000 bzw. F4240h
MOV     CX, 0Fh      ; oberer 16 Bit
MOV     DX, 4240h    ; untere 16 Bit
MOV     AH, 86h
INT     15h
\end{verbatim}
\end{beispiel}

\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}

Wo der Code zu den einzelnen Interrupts zu finden ist, ist in einer Tabelle (Interrupt table) festgelegt.
Im Prinzip wird bei einem Aufruf \texttt{INT \emph{n}} die n-te Zeile dieser Tabelle verwendet, um die Startadresse
des Unterprogramms (Interrupt Service Routine) auszuwählen.
Interrupts sind eine  einfache und standardisierte Form von Unterprogrammen.
Sie sind daher besonders geeignet, um Systemfunktionen zu implementieren.
Diese Funktionen brauchen dann nur einmal in den Speicher geladen zu werden.
Jedes Programm hat über den Interruptmechanismus Zugriff auf sie.

Neben den beschriebenen Aufruf durch Programme (Software-Interrupts) können Interrupts
auch durch die Hardware ausgelöst werden (Hardware-Interrupts).
Verschiedenste Ereignisse innerhalb oder außerhalb der CPU können Ursache für Hardware-Interrupts sein.
Einige Möglichkeiten sind:
%\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
\begin{itemize}
    \item Fehler bei arithmetischen Operationen (z.\,B. Divisionsergebnis passt nicht in Zielregister).
    \item Der Anwender betätigt eine Taste.
    \item Die Netzwerkkarte meldet den Empfang eines Paketes.
    \item Die Versorgungsspannung fällt aus.
\end{itemize}
Die meisten dieser Fälle können zu beliebigen Zeiten auftreten.
Das gerade laufende Programm wird dann unterbrochen und über die Nummer des Interrupts die
zugehörige Service Routine ausgeführt.
Die Routine endet mit dem Befehl IRET und das angehaltene Programm läuft weiter.

Anders als ein normales Unterprogramm ist ein Interrupt nicht vorhersehbar.
Beispielsweise könnte ein Interrupt unmittelbar vor einem bedingten Sprung erfolgen.
Daher ist es notwendig, dass am Ende des Interrupts auch das Statusregister wieder auf
den ursprünglichen Wert gesetzt wird.
Dazu wird bei einer Interrupt Service Routine beim Aufruf zusätzlich das
Statusregister auf den Stack gelegt und am Ende wieder von dort geholt.

Die Ursachen für einen Interrupt können von unterschiedlicher Dringlichkeit sein.
Auf einen Netzausfall beispielsweise muss sehr viel schneller reagiert werden, als auf einem Tastendruck.
Aus diesem Grund werden Interrupts mit einer Priorität versehen.
Interrupts mit einer höheren Priorität unterbrechen solche mit niedrigerer Priorität.
Die Behandlung der  Interrupts übernimmt ein spezieller Interrupt-Controller.
Er entlastet die CPU von der Behandlung der verschiedenen Interrupts (Interrupt Request IRQ).
Weiterhin bietet er die Möglichkeit, einzelne Interrupts frei zu geben oder zu unterdrücken (maskieren).
Die sehr wichtigen Interrupts sind allerdings davon ausgenommen.
Sie können nicht per Programm unterdrückt werden (nicht maskierbare Interrupts).

Die Reaktionszeit auf einen Interrupt bestimmt die Echtzeitfähigkeit eines Systems.
Systeme, bei denen Echtzeitfähigkeit eine wichtige Rolle spielt, sind dementsprechend
für eine schnelle Bearbeitung von Interrupts ausgelegt.
Für den Prozessor in einem Handy als Beispiel ist es wichtig, dass die Sprachdaten
schnell genug abgeholt, bearbeitet und wieder ausgegeben werden.


\section{Vom C-Programm zum Assemblercode}
Nur in seltenen Fällen wird eine Anwendung direkt in der Assembler-Sprache geschrieben.
Vielmehr wird in der Regel eine Hochsprache verwendet.
Die Sprache selbst ist idealerweise unabhängig von dem Zielsystem.
Für die Umsetzung des Programmcodes in Assembler beziehungsweise Maschinencode ist
der Compiler zuständig.

Im Normalfall läuft diese Umsetzung vollautomatisch ab.
Über entsprechende Optionen kann der entstehende Assemblercode und Maschinencode
ausgegeben werden.
Betrachten wir als Beispiel das folgende, kurze C-Programm.
\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
\begin{verbatim}
void ausgabe( short a, short b ) {
    printf( "%d %d", a, b );
}

short main(short argc, char* argv[])
{
    short a=2, b=5, i;

    for( i=0; i<10; i++ ) a += b;

    ausgabe( a, b );

    return 0;
}
\end{verbatim}
\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
Mit der Option \texttt{/FAs} erzeugt der Compiler von Microsoft Visual C++ eine Datei mit der Endung \texttt{.asm},
die sowohl den C-Code als auch die generierten Assemblerbefehle enthält.
Als Konfiguration wurde \emph{Debug} gewählt.
Anders als in der Konfiguration \emph{Release} wird der Code nicht allzu stark durch
Optimierungen verändert.
Der Teil \texttt{main} wird dann in folgenden Code für einen Pentium-Prozessor
übersetzt\footnote{Der Assemblercode ist etwas vereinfacht wiedergegeben.
Der Zusatz \texttt{e} vor den Registernamen bezieht sich auf die auf 32 Bit erweiterten Register}:
\begin{verbatim}
_TEXT   SEGMENT
_a$ = -4
_b$ = -8
_i$ = -12
_main   PROC NEAR     ; Beginn der Prozedur main

; 11   : {
    push    ebp       ; Register auf Stack retten
    mov ebp, esp
    sub esp, 76
    push    ebx
    push    esi
    push    edi
...  ; ********* hier sind einige Befehle ausgelassen *********

; 12   :    short a=2, b=5, i;
    mov  _a$[ebp], 2
    mov  _b$[ebp], 5

; 14   :    for( i=0; i<10; i++ ) a += b;
    mov _i$[ebp], 0              ; Initialisierung i = 0
    jmp $L538
$L539:
    mov ax, _i$[ebp]             ; Hochzählen
    add ax, 1
    mov _i$[ebp], ax
$L538:
    movsx   ecx, _i$[ebp]
    cmp ecx, 10                 ; Abbruchbedingung
    jge  $L540
    mov dx, _a$[ebp]            ; Schleifenkern
    add dx, _b$[ebp]
    mov _a$[ebp], dx
    jmp  $L539
$L540:

; 16   :    ausgabe( a, b );
    mov ax, _b$[ebp]
    push    eax
    mov cx, _a$[ebp]
    push    ecx
    call    ?ausgabe@@YAXFF@Z           ; ausgabe
...  ; ********* hier sind einige Befehle ausgelassen *********
_main   ENDP
\end{verbatim}
Im Assemblercode findet man die Struktur des C-Programms gut wieder.
Zur Übergabe der beiden Argumente an die Funktion \texttt{ausgabe} wird der Stack verwendet.
Die Zählschleife wird mit mehreren Sprüngen realisiert, wobei die Sprungmarken fortlaufend
nummeriert werden.
Die Umsetzung ist allerdings nicht optimal.
Insbesondere das ständige Transferieren der Werte zwischen Hauptspeicher und Registern
bedeutet einen vermeidbaren Mehraufwand.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{"Ubungen}
\begin{uebung} Anweisungen \\
Welche der folgenden Move-Anweisungen sind nicht erlaubt? Geben Sie jeweils eine kurze Begründung.
\begin{verbatim}
mov ax,123
mov ax,[256]
mov ax,bh
mov 345,ax
mov ax,ax
mov ah,bl
\end{verbatim}
\end{uebung}

\begin{uebung}
In manchen Assembler-Programmen findet man die Anweisung XOR für ein exklusives Oder
mit identischen Operanden, also
XOR AX,AX oder XOR DS,DS.
Was bewirkt dieser Befehl?
Welche Gründe könnten dafür sprechen, diesen "`Trick"' einzusetzen?
\end{uebung}

\begin{uebung} \label{ue_ampel} Ampel \\
Erweitern Sie unser Programm für die Ampelsteuerung zu einem realistischen Ablauf.
Die Dauer der einzelnen Phasen soll durch Warteschleifen realisiert werden.
Um den Ablauf flexibel zu gestalten, sollen diese Zeiten in Variablen gespeichert werden.
\end{uebung}

\begin{uebung} Fibonacci-Zahlen \\ \index{Fibonacci-Zahlen}
Die Fibonacci\footnote{Leonardo Pisano genannt Fibonacci, italienischer Mathematiker, ca. 1170-1250}-Zahlen
sind  durch die Startbedingung $i_1 = 1$, $i_2 = 1$
und die Rekursion $i_n = i_{n-2} +  i_{n-1}$ definiert.
Damit gilt
\begin{eqnarray*}
  i_3 &=& i_1 + i_2 = 1 + 1 = 2 \\
  i_4 &=& i_2 + i_3 = 1 + 2 = 3 \\
  i_5 &=& i_3 + i_4 = 2 + 3 = 5 \\
  i_6 &=& i_4 + i_5 = 3 + 5 = 8 \\
\end{eqnarray*}
und so weiter.
Schreiben Sie ein Assembler-Programm, das ausgehend von den Startwerten 1,1  weitere
Fibonacci-Zahlen berechnet.
\end{uebung}

\begin{uebung} \label{ue:sort} Sortier-Algorithmus \\
Implementieren Sie einen Algorithmus, um ein Feld mit  Werten zu sortieren.
\end{uebung}

\begin{uebung} Wurm \\
Realisieren Sie einen "`Wurm"', d.\,h. ein Programm, das sich selbst ständig
im Speicher kopiert.
\end{uebung}
% -*- TeX -*- -*- DE -*-

\chapter{Aussagelogik}
\label{c:aussagelogik}
\section{Aussagen}
Ein Aussage ist ein Satz, dem eindeutig ein Wahrheitswert
zugeordnet werden kann.
%
\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
\begin{quote}
"`Eine Aussage ist ein sprachliches Gebilde, von dem es sinnvoll
ist, zu sagen, es sei wahr oder falsch."'
(Aristoteles, griechischer Gelehrter, 384-322 v. Chr.)
\end{quote}
%
\begin{beispiel}Einige Aussagen: \\
"`Es regnet"' \\
"`5+7=13"'
\end{beispiel}
%
\begin{uebung}
Welche Sätze sind keine Aussagen? Können Sie Beispiele angeben?.
\end{uebung}
%
Eine formale Definition ist:
\begin{center}
\fbox{
\parbox{0.7\textwidth}{
Für eine Aussage A ist W(A) der Wahrheitswert mit \newline
\begin{tabular}{lll}
W(A) $:=$   &  wahr,       & falls Aussage A zutrifft \\
            &  falsch,     & falls Aussage A nicht zutrifft \\
\end{tabular}
}
}
\end{center}
%
Mehrere Einzelaussagen können zu einer neuen Aussage verknüpft werden,
für die sich wiederum ein Wahrheitswert bestimmen lässt.
%
\begin{uebung} Tour de France:\\
Wenn Eric Zabel bei den Zielwertungen die meisten Punkte sammelt, bekommt er dafür das grüne Trikot.
Führt er allerdings auch in der Gesamtwertung, so trägt er das gelbe Trikot.
Das grüne Trikot geht dann an den zweiten der
Punktwertung\footnote{Es gibt noch eine weitere Möglichkeit. Welche?}.
Wie sieht eine entsprechende Wahrheitstabelle aus? \\
Aussage A1: Eric Zabel ist der Punktbeste \\
Aussage A2: Eric Zabel ist der gesamt Führende \\
Aussage A3: Eric Zabel trägt das grüne Trikot \\
\begin{center}
\begin{tabular}{|c|c||c|} \hline
W(A1)  &  W(A2) &  W(A3) \\   \hline \hline
falsch & falsch & \\   \hline
falsch & wahr   & \\   \hline
wahr   & falsch & \\   \hline
wahr   & wahr   & \\   \hline
\end{tabular}
\end{center}
%
\end{uebung}
Die Verknüpfung kann wie im Beispiel in einer so genannten Wahrheitstabelle dargestellt werden.
Dabei trägt man alle möglichen Kombinationen der Einzelaussagen und
das jeweilige Resultat in einer Tabelle ein.
Ein Beispiel ist die UND-Verknüpfung.
Sie besagt, dass die Gesamtaussage nur dann wahr ist, wenn jede Einzelaussage zutrifft.
\begin{beispiel} UND-Verknüpfung \\
Zwei ist eine gerade Zahl UND drei ist eine ungerade Zahl
\end{beispiel}
Die Wahrheitstabelle (auch Wertetabelle genannt) für UND mit zwei Einzelaussagen
hat folgendes Aussehen:
\begin{center}
\begin{tabular}{|c|c||c|} \hline
W(A1)  &  W(A2) & W( A1 UND A2) \\   \hline \hline
falsch & falsch & falsch \\    \hline
falsch & wahr   & falsch \\   \hline
wahr   & falsch & falsch \\   \hline
wahr   & wahr   & wahr   \\   \hline
\end{tabular}
\end{center}
%
\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
Vereinfachung der Schreibweise: \\
wahr wird durch 1 ausgedrückt (w, true) \\
falsch wird durch 0 ausgedrückt (f, false) \\
Wahrheitstabelle (Wertetabelle):
\begin{center}
\begin{tabular}{|c|c||c|} \hline
W(A1) &  W(A2) &  W( A1 UND A2 ) \\   \hline \hline
0  & 0 &  0 \\    \hline
0  & 1 &  0 \\    \hline
1  & 0 &  0 \\    \hline
1  & 1 &  1 \\    \hline
\end{tabular}
\end{center}
%
Dies ist die UND-Verknüpfung (Konjunktion, AND), eine so genannte logische Operation.
Man schreibt dafür:\\
\begin{center}
W( A1 und A2 ) = W(A1) $\cdot$ W(A2) \\
\end{center}
Andere Schreibweisen sind : W(A1)  $\cap$ W(A2) und  W(A1)  $\wedge$ W(A2).
Die logischen Konstanten sind 0 und 1.
Eine logische Variable steht für ein Element aus der Menge $\{0,1\}$,
die Zuordnung heißt Belegung der Variablen
(Beispiel: $a = 0$).


\section{Grundverknüpfungen}
\label{s:boole_grundop}
Folgende Grundverknüpfungen zwischen logischen Variablen (und Konstanten) sind gebräuchlich:\\
%
Negation (NICHT, NOT): $\neg a$, $\overline{a}$       sprich: nicht $a$
\[
\begin{array}{|c||c|} \hline
a &  \overline{a} \\ \hline \hline
0 & 1 \\ \hline
1 & 0 \\ \hline
\end{array}
\]
%
Konjunktion (UND, AND, Logisches Produkt):  $a \cdot b$ sprich: $a$ und $b$\\
Eine UND-Verknüpfung von 2 Variablen ergibt nur dann eine 1, wenn alle 2 Variablen gleich 1 sind.
(Reihenschaltung von 2 Schaltern)
\[
\begin{array}{|c|c||c|} \hline
a & b & a \cdot b \\ \hline \hline
0 & 0 & 0 \\ \hline
0 & 1 & 0 \\ \hline
1 & 0 & 0 \\ \hline
1 & 1 & 1 \\ \hline
\end{array}
\]
(Hinweis: Ähnlichkeit mit Zahlenmultiplikation) \\
%
Disjunktion (ODER, OR, Logische Summe):  $a + b$  sprich: $a$ oder $b$ \\
Eine ODER-Verknüpfung von 2 Variablen ergibt dann eine 1, wenn eine Variable oder beide Variablen gleich 1 sind.
(Andere Schreibweisen: W(A1)  $\cup$ W(A2) und  W(A1)  $\vee$ W(A2))
\[
\begin{array}{|c|c||c|} \hline
a & b & a + b \\ \hline \hline
0 & 0 & 0 \\ \hline
0 & 1 & 1 \\ \hline
1 & 0 & 1 \\ \hline
1 & 1 & 1 \\ \hline
\end{array}
\]
%
Antivalenz (EXOR, exklusives ODER)       $a \oplus b$       sprich: entweder $a$ oder $b$ \\
Wahr wenn nur eine der beiden Variablen wahr ist (nicht aber beide).
\[
\begin{array}{|c|c||c|} \hline
a & b & a \oplus b \\ \hline \hline
0 & 0 & 0 \\ \hline
0 & 1 & 1 \\ \hline
1 & 0 & 1 \\ \hline
1 & 1 & 0 \\ \hline
\end{array}
\]
Peircefunktion (NOR)            sprich: weder a noch b \\
(entspricht negiertem ODER)
\[
\begin{array}{|c|c||c|} \hline
a & b & \overline{a + b}\\ \hline \hline
0 & 0 & 1 \\ \hline
0 & 1 & 0 \\ \hline
1 & 0 & 0 \\ \hline
1 & 1 & 0 \\ \hline
\end{array}
\]
%
Shefferfunktion (NAND)          sprich: nicht beide a und b \\
(entspricht negiertem UND)
\[
\begin{array}{|c|c||c|} \hline
a & b & \overline{a \cdot b} \\ \hline \hline
0 & 0 & 1 \\ \hline
0 & 1 & 1 \\ \hline
1 & 0 & 1 \\ \hline
1 & 1 & 0 \\ \hline
\end{array}
\]

\section{Ausdrücke}
Verknüpfungen mit mehr als zwei Variablen oder Konstanten lassen sich mit den oben
eingeführten Operationen darstellen.
Eine solche Verknüpfung von endlich vielen Konstanten und logischen Variablen
mittels Grundverknüpfungen heißt Ausdruck.
Ausdrücke, in denen nur die Operationen Negation, UND und ODER verwendet werden,
nennt man Boolesche Ausdrücke
(George Boole, engl. Mathematiker 1815-1864, gilt als Begründer der mathematischen Logik).
\index{Boole, George}

Die Reihenfolge, in der die Operatoren angewendet werden,
wird wie beim Rechnen mit Zahlen durch Vorrangregeln ("`Punktrechnung vor Strichrechnung"') und Klammern bestimmt.
Es gilt insbesondere:
\begin{itemize}
    \item Gleichrangige Operationen werden  von links nach rechts berechnet
    \item geklammerte Verknüpfungen   haben Vorrang vor
    \item Negation                    hat Vorrang vor
    \item Konjunktion (UND)           hat Vorrang vor
    \item Disjunktion (ODER)
\end{itemize}
%
Negation wird oft durch Überstreichung dargestellt,
die dann einfach auf mehrere Variablen oder Konstanten erweitert werden kann.
Oft wird das Zeichen für die Boolsche Multiplikation weggelassen ($a \cdot b$  wird zu  $a b$ )
Ein Ausdruck wird durch Angabe der Wertetabelle vollständig beschrieben:
\begin{uebung} Ergänzen Sie die Wertetabelle für den Ausdruck
$a \cdot b + a \cdot \overline{c}$.
\[
\begin{array}{|c|c|c||c|c|c||c|} \hline
a & b & c & a \cdot b & \overline{c} & a \cdot \overline{c} & a \cdot b + a \cdot \overline{c}\\ \hline
0 & 0 & 0 & & & & \\ \hline
0 & 0 & 1 & & & &  \\ \hline
  &   &   & & & &  \\ \hline
  &   &   & & & &  \\ \hline
  &   &   & & & &  \\ \hline
  &   &   & & & &  \\ \hline
  &   &   & & & &  \\ \hline
  &   &   & & & &  \\ \hline
\end{array}
\]
\end{uebung}


\section{Umformungen}
Verschiedene Ausdrücke können äquivalent sein,
d.\,h. bei gleicher Belegung der gemeinsamen Variablen nehmen sie gleiche Wahrheitswerte an.
Man schreibt dann $a = b$.
Es gibt in der Regel viele verschiedene Möglichkeiten, einen Zusammenhang zu formulieren.
%
\begin{beispiel}
\[
a \cdot ( b + \overline{b} ) = a \cdot ( c + \overline{c} )
\]
\end{beispiel}
\begin{uebung} Beweisen Sie durch Ausfüllen der Wahrheitstabelle diese Beziehung.
\[
\begin{array}{|c|c|c||c|c|} \hline
a & b & c & a \cdot ( b + \overline{b} ) & a \cdot ( c + \overline{c} ) \\ \hline \hline
0 & 0 & 0 & & \\ \hline
0 & 0 & 1 & & \\ \hline
0 & 1 & 0 & & \\ \hline
0 & 1 & 1 & & \\ \hline
1 & 0 & 0 & & \\ \hline
1 & 0 & 1 & & \\ \hline
1 & 1 & 0 & & \\ \hline
1 & 1 & 1 & & \\ \hline
\end{array}
\]
\end{uebung}
%
Für die Umformung gelten folgende Gesetze: \\
%
Negation der Negation
\[
\overline{\overline{a}} = a
\]
Kommutativgesetze
\begin{eqnarray*}
  a \cdot b &=& b \cdot a \\
  a + b &=& b + a
\end{eqnarray*}
%
Assoziativgesetze
\begin{eqnarray*}
    a \cdot ( b \cdot c ) &=& ( a \cdot b ) \cdot c \\
    a + ( b + c )    &=& ( a + b ) + c
\end{eqnarray*}
%
Distributivgesetze
\begin{eqnarray*}
     a \cdot ( b + c ) &=& ( a \cdot b ) + ( a \cdot c ) \\
     a + ( b \cdot c ) &=& ( a + b ) \cdot ( a + c )
\end{eqnarray*}
%
Idempotenzgesetze
\begin{eqnarray*}
       a \cdot a &=& a \\
       a + a &=& a
\end{eqnarray*}
%
Komplementgesetze
\begin{eqnarray*}
   a \cdot \overline{a} &=& 0 \\
   a + \overline{a}     &=& 1 \\
\end{eqnarray*}
%
0-1 Gesetze
\begin{eqnarray*}
              a \cdot 1 &=& a  \\
              a \cdot 0 &=& 0  \\
              a + 1     &=& 1  \\
              a + 0     &=& a
\end{eqnarray*}
%
Absorptionsgesetze
\begin{eqnarray*}
     a \cdot ( a + b ) &=& a \\
     a + ( a \cdot b ) &=& a \\
     ( a \cdot b ) + ( a \cdot  \overline{b} ) &=& a \\
     ( a +  \overline{b} ) \cdot b &=& a \cdot b \\
     ( a  \cdot  \overline{b} ) + b &=& a + b \\
     ( a + b ) \cdot ( a +  \overline{b} ) &=& a \\
\end{eqnarray*}
%
De Morgansche\footnote{Augustus De Morgan, englischer Mathematiker, 1806-1871} Regel
\begin{eqnarray*}
\overline{( a \cdot b )} &=&  \overline{a} + \overline{b} \\
\overline{( a + b )}     &=& \overline{a} \cdot \overline{b} \\
\end{eqnarray*}
%

\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
\begin{beispiel}
Wir betrachten ein Fahrrad. Sei \\
$a$ : Vorderreifen platt  \\
$b$ : Hinterreifen platt  \\
dann gilt für die Aussage $c$ : "`Fahrrad fährt"':\\
$c =  \overline{a} \cdot  \overline{b}$\\
( der Vorderreifen ist NICHT platt UND der Hinterreifen ist NICHT platt ) \\
oder \\
$\overline{c} = a + b$    \\      ( Fahrrad fährt NICHT wenn Vorderreifen platt ODER Hinterreifen platt ) \\
beziehungsweise \\
$c =  \overline{ a + b }$  \\
( Fahrrad fährt wenn NICHT ( Vorderreifen platt ODER Hinterreifen platt ),
(2. Morgansche Regel) \\
%
Der Beweis der Umformungsregeln kann jeweils durch Umformen oder  Aufstellen der Wertetabellen erfolgen.
\end{beispiel}
%
\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
\begin{beispiel}
2. Distributivgesetze  $ a + ( b \cdot c ) = ( a + b ) \cdot ( a + c )$ \\
\[
( a + b ) \cdot ( a + c ) = a \cdot a + a \cdot c + b \cdot a + b \cdot c       \mbox{(Ausmultiplizieren)}
\]
mit  $a \cdot a = a  = a \cdot 1$  erhält man
\begin{eqnarray*}
  a \cdot 1 + a \cdot c + b \cdot a + b \cdot c  &=&  \\
  a \cdot (1 + c + b ) + b \cdot c &=& \mbox{(Ausklammern)} \\
  a \cdot 1 + b \cdot c &=& \\
   &=& a  + b \cdot c\\
\end{eqnarray*}
\end{beispiel}
%
Häufig benutzte "`Tricks"':
\begin{itemize}
    \item $a  = a \cdot 1$  um dann anschließend $a$ ausklammern zu können
    \item $( 1 + a + b + c + d )   = 1$
    \item $0 \cdot a \cdot b \cdot c     =  0$
\end{itemize}
%
\begin{uebung}
5. Absorptionsgesetz    $(a  \cdot  \overline{b} ) + b = a + b$
\[
\begin{array}{|c|c||c||c|c|} \hline
a &  b  &  (a  \cdot  \overline{b} ) & (a  \cdot  \overline{b} ) + b & a + b \\ \hline \hline
0 &  0  & & & \\ \hline
0 &  1  & & & \\ \hline
1 &  0  & & & \\ \hline
1 &  1  & & & \\ \hline
\end{array}
\]
\end{uebung}
\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}

\section{Boolesche Funktionen}
Eine Boolesche (oder logische) Funktion ist eine Zuordnung zwischen
der Belegung der Variablen und den Wahrheitswerten 0 und 1
(analog zur Funktionenlehre wie etwa $f(x) = \sin( x )$ ).
%
\begin{definition}
Boolesche Funktion \\
Eine $n$-stellige (vollständig definierte) Boolesche Funktion $f$ wird definiert durch
die Abbildung
\[
f: \{0,1\}^n \to \{0,1\},
\]
\end{definition}
wobei $\{0,1\}^n$  die $n$-fache Kreuzmenge oder das $n$-fache kartesische Produkt der Menge $\{0,1\}$,
also die Menge aller $n$-Tupel $(a_1, a_2, \ldots, a_n)$ mit
$a_i \in \{0,1\}$ für alle $i = 1, \ldots, n$ ist.
Mit anderen Worten: jeder mögliche Kombination von $n$ binären Werten wird ein
ebenfalls binärer Funktionswert zugewiesen.
Die Funktion kann als logischer Ausdruck oder in Form einer $2^n$-zeiligen Wertetabelle angegeben werden.

Es ist offensichtlich, wie man aus einer gegebenen Funktion die Wertetabelle aufbauen kann.
Häufig stellt sich aber das umgekehrte Problem:
Die Wertetabelle ist vorgegeben und dazu soll ein Ausdruck gefunden werden.
Damit stellt sich die Frage:
Wie kommt man von einer Wertetabelle zu einem logischen Ausdruck?

Ein Verfahren basiert auf den so genannten Mintermen. \index{Minterm}
Minterme sind Terme die nur für genau einen Eingangstupel den Wert 1 ergeben.
Dies wird erreicht, indem alle Argumente mittels UND verknüpft werden,
wobei Argumente mit dem Wert 0 negiert werden.
\begin{beispiel} Minterm für $n = 4$ \\
Zu dem Eingang  0 0 1 1  gehört der Minterm   $\overline{a_1} \cdot \overline{a_2} \cdot a_3 \cdot a_4$.
Dieser Ausdruck ist für den Eingangstupel  wahr und für alle anderen Tupel falsch.
\end{beispiel}
%
Für $n=3$ erhält man folgende Tabelle (wieder mit den Bezeichnungen $a$, $b$ und $c$ für
die Eingangsvariablen):
\[
\begin{array}{|c|c|c||c|} \hline
a & b & c & \mathrm{Minterme} = 1 \\ \hline \hline
0 & 0 & 0 & \overline{a}  \overline{b}  \overline{c} \\ \hline
0 & 0 & 1 & \overline{a}  \overline{b}  c \\ \hline
0 & 1 & 0 & \overline{a}  b  \overline{c} \\ \hline
0 & 1 & 1 & \overline{a}  b  c \\ \hline
1 & 0 & 0 & a  \overline{b}  \overline{c} \\ \hline
1 & 0 & 1 & a  \overline{b}  c \\ \hline
1 & 1 & 0 & a  b  \overline{c} \\ \hline
1 & 1 & 1 & a  b  c \\ \hline
\end{array}
\]
Damit kann man für eine gegebene Wertetabelle die Funktion $x$ in der disjunktiven Normalform (DNF)
als ODER-Verknüpfung aller Minterme angeben. \index{disjunktiven Normalform }
%
\begin{beispiel}
Wertetabelle
\[
\begin{array}{|c|c|c||c|c|} \hline
a & b & c & x & \mathrm{Minterm} \\ \hline \hline
0 & 0 & 0 & 0 & \\ \hline
0 & 0 & 1 & 0 & \\ \hline
0 & 1 & 0 & 0 & \\ \hline
0 & 1 & 1 & 1 & \overline{a}  b  c \\ \hline
1 & 0 & 0 & 1 & a  \overline{b}  \overline{c} \\ \hline
1 & 0 & 1 & 0 & \\ \hline
1 & 1 & 0 & 0 & \\ \hline
1 & 1 & 1 & 1 & a  b  c \\ \hline
\end{array}
\]
Die zugehörige disjunktiven Normalform lautet:
\[x = \overline{a}  b  c   +  a  \overline{b}  \overline{c}  + a  b  c\]
\end{beispiel}
%
Die alternative Darstellung beruht auf den
Maxtermen: Termen die nur für genau einen Eingangstupel den Wert 0 ergeben. \index{Maxterm}
Dazu werden alle Argumente ODER verknüpft, wobei Argumente mit dem Wert 1 negiert werden.
Beispielsweise gehört zu dem Eingang 0 0 1  der Maxterm   $a + b  + \overline{c}$
Die konjunktiven Normalform (KNF) wird nach der folgenden Vorschrift konstruiert:
Für jede Zeile mit x = 0 wird der Maxwert gebildet,
anschließend werden alle Maxterme mit UND verknüpft.
\index{konjunktive Normalform}

\begin{beispiel}
Wertetabelle
\[
\begin{array}{|c|c|c||c|c|} \hline
a & b & c & x & \mathrm{Maxterm}  \\ \hline \hline
0 & 0 & 0 & 0 & a + b + c \\ \hline
0 & 0 & 1 & 0 & a + b + \overline{c} \\ \hline
0 & 1 & 0 & 0 & a + \overline{b} + c \\ \hline
0 & 1 & 1 & 1 & \\ \hline
1 & 0 & 0 & 1 & \\ \hline
1 & 0 & 1 & 0 & \overline{a} + b + \overline{c} \\ \hline
1 & 1 & 0 & 0 & \overline{a} + \overline{b} + c \\ \hline
1 & 1 & 1 & 1 & \\ \hline
\end{array}
\]
Die zugehörige konjunktive Normalform lautet:
\[x =  (a + b + c) (a + b + \overline{c}) (a + \overline{b} + c)
(\overline{a} + b + \overline{c}) (\overline{a} + \overline{b} + c)\]
\end{beispiel}
%
Die Betrachtungen zeigen, dass man aus einer beliebigen Wertetabelle stets eine Normalform ableiten kann
Anschaulich ist damit gezeigt, dass die Operationen (NICHT, UND, ODER) vollständig sind,
d.\,h. jede Boolesche Funktion kann unter Verwendung dieser drei Operationen dargestellt werden.
Weiterhin können gemäß der De Morganschen Regel UND und ODER ineinander überführt werden.
Damit bilden sowohl (NICHT, UND) als auch (NICHT, ODER) bereits ein vollständiges System.
%
\begin{uebung}
Für welche Sonderfälle gibt es entweder nur disjunktive oder konjunktive Normalforme?
\end{uebung}
\begin{uebung}
Zeigen Sie für (NAND) oder (NOR), dass die Operation alleine ein vollständiges System bildet.
\end{uebung}


\section{Vereinfachung von Schaltfunktionen}
Bei der technischen Umsetzung von logischen Funktionen spricht man von Schaltfunktionen.
Die logischen Operationen werden dann durch entsprechende Schaltungen realisiert.

Die Minimierung (Vereinfachung) von Schaltfunktionen hat für die Informationsverarbeitung große Bedeutung.
Bei der Realisierung von Schaltfunktionen mit Gatterbausteinen sucht man einen minimalen
Booleschen Ausdruck für die gegebene Funktion.
Diese Vorgehensweise führt zu kostengünstigen Schaltungen,
da die Kosten von der Komplexität des Booleschen Ausdrucks abhängen.
Ziel der Minimierungsverfahren ist es, Schaltfunktionen mit möglichst geringen Kosten (Aufwand) zu realisieren.
Dazu werden redundante Terme und Variablen entfernt.
Für die Vereinfachung von Schaltfunktionen können verschiedene Verfahren verwendet werden:
\begin{itemize}
    \item Anwendung der Axiome und Rechenregeln der Boolschen Algebra
    \item Graphische Verfahren, zum Beispiel das Minimierungsverfahren mittels Karnaugh-Veitch-Diagrammen
    (KV-Diagrammen).
    Ein Applet zu KV-Diagrammen wurde in der Studienarbeit \cite{meyer_kvd} entwickelt
    (http://tech-www.informatik.uni-hamburg.de/applets/kvd/).
    \item Tabellarische Verfahren, zum Beispiel das Minimierungsverfahren nach  Quine-McCluskey
\end{itemize}
%
Für den praktischen Einsatz müssen allerdings auch technische Randbedingungen berücksichtigt werden.
So kann es beispielsweise vorteilhaft sein, nur bestimmte Typen von Operationen zu verwenden.
Früher wurden Schaltungen aus einzelnen ICs aufgebaut.
Dann stellt sich das besondere Optimierungsproblem, möglichst wenige ICs zu verwenden.
Ein übliches IC enthält z.\,B. 4 NAND Elemente.
Das Optimierungsproblem besteht dann darin, die Elemente in den ICs möglichst gut auszunutzen.
In diesem Fall ist beispielsweise eine Realisierung mit 4 NAND Elementen günstiger
als eine mit einem NAND und einem NOR Element.

\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}

\section{"Ubungen}
\begin{uebung} Wertetabelle\\
Erstellen Sie die Wertetabelle für den Ausdruck
\[a \cdot \overline{b} + \overline{a} \cdot b   + b \cdot \overline{c} \]
(Es können mehr Spalten als benötigt vorhanden sein.\\
Schreibweise: $\cdot$ für UND,  $+$ für ODER)
\[
\begin{array}{*{3}{|p{2em}}||*{6}{p{2em}|}} \hline
a & b & c & & & & & & \\ \hline \hline
  &   &   & & & & & & \\ \hline
  &   &   & & & & & & \\ \hline
  &   &   & & & & & & \\ \hline
  &   &   & & & & & & \\ \hline
  &   &   & & & & & & \\ \hline
  &   &   & & & & & & \\ \hline
  &   &   & & & & & & \\ \hline
  &   &   & & & & & & \\ \hline
\end{array}
\]
\end{uebung}

\begin{uebung}
\label{ue:aktien}
Verkaufsentscheidung \\
Ein Anleger kauft Aktien der XYZ AG.
Er wählt folgende Strategie:
Falls sich XYZ schlechter als der DAX entwickelt, wird die Aktie verkauft,
sobald sich der Kurs um mehr als 10\% von dem Einkaufswert entfernt hat.
Ansonsten - wenn sich XYZ gleich gut oder besser als der DAX entwickelt - wird sie verkaufen,
wenn der Wert des gesamten Depots (inklusive anderer Aktien) unter 3 Millionen Euro fällt.
\begin{itemize}
    \item Welches sind die relevanten Einzelaussagen?
    Stellen Sie eine Wahrheitstabelle für die Verkaufsentscheidung auf.
    \item Geben sie die zugehörige disjunktive Normalform an.
    \item Welche Vereinfachungen bieten sich an?
\end{itemize}
\end{uebung}

\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}

\begin{uebung} \label{ue:kraftwerke}
Kraftwerküberwachung \\
Ihre Firma betreibt 3 Kraftwerke, die jeweils eine Leistung  von 10000 kW liefern.
Jede Stunde werden die aktuellen Leistungsdaten gemeldet.
Um den ordnungsgemäßen Betrieb zu überwachen, betrachten Sie zwei Kriterien:
\begin{enumerate}
    \item Steigt in mindestens einem Kraftwerk die Leistung über 11000 kW?
    \item Fällt bei mindestens zwei Kraftwerken die Leistung unter 9900 kW?
\end{enumerate}
Erstellen Sie für jedes der beiden Kriterien eine Wahrheitstabelle.
Verwenden Sie dazu im ersten Fall die Aussagen $L_i > 11000 kW$
und im zweiten Fall $L_i < 9900 kW$ wobei $L_i$ die Leistung im Kraftwerk $i$ bezeichnet.

\begin{center}
\mbox{
1.
\begin{tabular}{*{3}{|p{2em}}||*{1}{p{2em}|}} \hline
$L_1$ & $L_2$ & $L_3$ & Alarm  \\ \hline \hline
  &   &   &  \\ \hline
  &   &   &  \\ \hline
  &   &   &  \\ \hline
  &   &   &  \\ \hline
  &   &   &  \\ \hline
  &   &   &  \\ \hline
  &   &   &  \\ \hline
  &   &   &  \\ \hline
\end{tabular}
}
\mbox{
2.
\begin{tabular}{*{3}{|p{2em}}||*{1}{p{2em}|}} \hline
$L_1$ & $L_2$ & $L_3$ & Alarm  \\ \hline \hline
  &   &   &  \\ \hline
  &   &   &  \\ \hline
  &   &   &  \\ \hline
  &   &   &  \\ \hline
  &   &   &  \\ \hline
  &   &   &  \\ \hline
  &   &   &  \\ \hline
  &   &   &  \\ \hline
\end{tabular}
}
\end{center}
\end{uebung}
% -*- TeX -*- -*- DE -*-

\chapter{Endliche Automaten und regul"are Grammatiken}

\section{Regul"are Ausdr"ucke}
Suchen und Ersetzen sind häufige Aufgaben. 
Entweder möchte man selbst im Editor oder in der Textverarbeitung ein Muster 
suchen oder durch ein anderes ersetzen oder Programme sollen diese Aufgabe automatisch ausführen.
Ein weiteres Anwendungsfeld sind Plausibiltätsprüfungen. 
So kann man beispielsweise in eines Eingabemaske testen, 
ob die Werte bestimmten Vorgaben entsprechen. 
Beispielsweise soll das Feld für die Postleitzahl  genau 5 Ziffern enthalten 
(sofern man nur Adressen innerhalb Deutschlands betrachtet). 
Häufig reicht es dabei nicht aus, einen festen Text zu verwenden. 
Vielmehr sollen kompliziertere Muster behandelt werden.  
Einige Beispiele sind:
\begin{itemize}
    \item Suche nach allen Datumsangaben in einem Text
    \item Ersetzen des Dezimalpunktes durch ein Komma (oder umgekehrt)
    \item Prüfen, ob eine Zeile eine plausible Anschrift enthält (also Straße, Hausnummer, Postleitzahl, Stadt)
    \item Suchen nach allen C-Dateien, die im Namen den Begriff \emph{Euro} enthalten
\end{itemize}    
Für solche Fälle unterstützen viele Programmiersprachen 
und Editoren  reguläre Ausdrücke (regular expressions).    
Wir verwenden als Beispiel die Sprache Perl \cite{wall_perl}.
Damit lässt sich folgendes Testprogramm zur Suche nach Mustern in Dateien schreiben: 
\begin{verbatim}
# Programm fbgrep.pl
# Kopiere erstes Argument in Variable $search
$search = shift;

# jetzt Schleife ueber alle angegebenen Dateien
while (<>) {
  if(  /$search/ ){
    # Zeile gefunden, Muster steht jetzt in $&
    print "<$&>:: $_";
  }
}
\end{verbatim}
Das Programm erhält beim Aufruf als ersten Parameter das Suchmuster und anschließend eine 
Liste von Dateinamen. 
Mit dem Befehl \texttt{shift} wird das erste Element des Feldes mit Aufrufparametern in 
die Variable \verb!$search! kopiert.
Die anschließende Schleife mit der Konstruktion \verb!<>! läuft dann über alle Zeilen aller 
angebenen Dateien. 
Bei einem Treffer wird das Muster (steht in der Variablen \verb!$&!) 
sowie die Zeile (Variable \verb!$_!) ausgegeben.
\begin{beispiel} Einfache Suche\\
Der Befehl 
\begin{verbatim}
fbgrep.pl "Neumann" skript.txt
\end{verbatim}
findet alle Zeile mit dem Text \emph{Neumann} in der Datei \texttt{skript.txt}.
\end{beispiel}
Wie das Beispiel zeigt, werden Buchstaben als normaler Suchtext behandelt. 
Das gleiche gilt für Ziffern und einen Teil der Sonderzeichen. 

Die anderen Sonderzeichen haben eine besondere Bedeutung. 
So steht der Punkt für irgendein Zeichen.
Das Muster \texttt{a.b} deckt damit Folgen in der Art \emph{aAb}, \emph{axb}, \emph{a2b}, u. s. w. ab. 
Mehrere Punkte stehen für mehrere Zeichen. 
Mit \texttt{.....berg} findet man \emph{Friedberg}, aber auch 
\emph{Godesberg}, \emph{eidelberg} oder gar \emph{\_Goldberg} und \emph{p-n-Überg}.
Mit den beiden Zeichen \verb!^! und \verb!$! kann man Zeilenanfang und Zeilenende angeben. 
So sucht \verb!^...$! nach allen Zeilen, die genau drei Zeichen enthalten.

Mehrere Alternativen werden durch ein \verb!|!-Zeichen getrennt. 
So kann man mit \texttt{berg|stadt}  gleichzeitig nach \texttt{berg} und \texttt{stadt} suchen.
Kompliziertere Ausdrücke werden durch runde Klammern gegliedert.
Beispielsweise bedeutet \texttt{(A|B)..(berg|stadt)} alle Muster mit:
\begin{itemize}
    \item \texttt{A} oder \texttt{B} am Anfang
    \item dann zwei beliebige Zeichen
    \item \texttt{berg} oder \texttt{stadt} am Ende
    \item Beispiele: Arlberg, Bamberg
\end{itemize}    
Anstelle von \texttt{(A|B)} kann man kürzer \texttt{[AB]} schreiben. 
Allgemein kann man mehrere alternative Zeichen als so genannte Zeichenklasse in 
eckigen Klammern angeben. 
Dann werden an dieser Stelle alle aufgeführten Zeichen akzeptiert. 
In diesem Fall haben die allermeisten Sonderzeichen keine besondere Bedeutung, 
sondern werden wie normale Zeichen behandelt. 
Ausnahmen sind das Minus- und das \verb!^!-Zeichen.
Mit dem Minuszeichen werden Bereiche spezifiziert. 
Beispielsweise umfasst  \verb![a-h]! alle Buchstaben von \texttt{a} bis \texttt{h}. 
Ein vorangestelltes \verb!^!-Zeichen kehrt die Bedeutung um.
\begin{beispiel} Zeichenklassen\\
\begin{itemize}
    \item \verb![Ff]! groß oder klein F
    \item \verb![a-z]! irgendein Kleinbuchstabe
    \item \verb![A-Za-z]! ein Buchstabe
    \item \verb![0-9]! eine Ziffer (entspricht \verb![0123456789]!)
    \item \verb![^ijkxyz]! alles außer den aufgeführten Buchstaben
    \item \verb![^0-9]! keine Ziffer 
    \item \verb+[^ .,;!?]+ kein Leerzeichen und kein Satzzeichen
\end{itemize}    
\end{beispiel} 
Für häufig benutzte Klassen sind in Perl eigene Zeichen definiert. 
So bezeichnet beispielsweise \verb!\d! die Klasse aller Ziffern 
und  \verb!\w! alle alphanumerischen Zeichen (Ziffern und Buchstaben).
Die Umkehrung wird durch einen Großbuchstaben dargestellt: 
\verb!\D! sind alle Zeichen außer Ziffern und \verb!\W! umfasst alle Sonderzeichen.

\begin{table}
  \centering
  \caption{Metazeichen}\label{t:metazeichen}
\begin{tabular}{|l|l|} \hline
    \verb!.! &    Irgendein Zeichen \\ \hline
    \verb!|! &    Auswahl \\ \hline
    \verb![]! &   Zeichenklasse \\ \hline
    \verb!^!  &    Zeilenanfang \\ \hline
    \verb!$!  &    Zeilenende \\ \hline
    \verb!()! &   Gruppe \\ \hline
    \verb!\!  &    Danach wird das nächste Zeichen als normaler Text verwendet \\ \hline
\end{tabular}
\end{table}

Häufig möchte man Wiederholungen von Teilen des Suchmusters spezifizieren.  
In Tabelle \ref{t:mehrfach} sind die verschiedenen Möglichkeiten dazu zusammen gestellt. 
Allgemein wird mit der Form \verb!{n,m}! angegeben, dass ein Muster mindestens n-mal
und  höchstens m-mal auftreten darf. 
Mit \verb!e{2,3}! sind  zwei oder drei Wiederholungen des Buchstaben \texttt{e} beschrieben. 
Die Kombination \verb!.*! steht als Platzhalter für eine beliebige Folge von Zeichen 
einschließlich einer leeren Folge. 

\begin{table}
  \centering
  \caption{Wiederholungszeichen}\label{t:mehrfach}
\begin{tabular}{|l|l|} \hline
    \verb!*!    &    beliebig oft oder gar nicht \\ \hline
    \verb!+!    &    mindestens 1-mal \\ \hline
    \verb!?!    &    1-mal oder gar nicht \\ \hline
    \verb!{n}!  &    genau n-mal \\ \hline
    \verb!{n,}! &    mindestens n-mal \\ \hline
    \verb!{n,m}! &   mindestens n-mal, höchstens m-mal \\ \hline
\end{tabular}
\end{table}

\begin{beispiel} Wiederholungen\\
\begin{itemize}
    \item \verb!^[0-9]+$!   alle Zeilen, die nur Ziffern enthalten
    \item \verb![aeiou]{5}! alle Muster mit genau 5 aufeinander folgenden Vokalen (z. B. \emph{Treueeid})
    \item \verb!a\w*b\w*c\w*d\w*! Wörter, die die Buchstaben a, b, c und d in dieser Reihenfolge enthalten
%    \item \verb!! 
\end{itemize}    
\end{beispiel} 

\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
\begin{uebung} Reguläre Ausdrücke\\
Welche Muster werden durch folgende reguläre Ausdrücke beschrieben:
\begin{enumerate}
    \item \verb![a-zA-Z_][a-zA-Z_0-9]*!
    \item \verb![+-]?[0-9]+!
    \item \verb![a-zA-Z.]*\@[a-zA-Z.]*!
    \item \verb![a-h]{4}!
\end{enumerate}    
\end{uebung}


\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
\begin{uebung} Reguläre Ausdrücke\\
Geben Sie für folgende Suchaufgaben reguläre Ausdrücke an:
\begin{enumerate}
    \item Folgen von zwei oder mehr Leerzeichen
    \item Wörter mit mehr als 25 Buchstaben      %  [A-Za-z][a-z]{25,}
    \item Alle achtstelligen Binärzahlen
    \item Integerkonstanten in der Sprache C in oktaler oder hexadezimaler Schreibweise  
    \item Alle Jahreszahlen von 1980 bis 2099              % "19[89][0-9]|20[0-9][0-9]" 
    \item Zeitangaben in der Form \emph{Stunden:Minuten}
    \item Zeilen, die mit \verb!<h1! oder \verb!<h2! beginnen
    \item Ausdrücke, die mit \verb!<a! beginnen und mit  \verb!a>! enden
\end{enumerate}    
\end{uebung}


\section{Endliche Automaten}
Nach diesen Betrachtungen stellt sich die Frage, 
wie   reguläre Ausdrücke effizient ausgewertet werden können?
Mit anderen Worten: wie kann geprüft werden, ob eine gegebene Folge von Zeichen 
zu einen regulären Ausdruck gehört?
Hier helfen endliche Automaten.
Wir betrachten dazu den zu prüfenden Text als eine Folge von einzelnen Zeichen. 

Der Automat besteht aus einer endlichen Anzahl von Zuständen,
die durch Übergänge untereinander verbunden sind. 
Zu Beginn der Verarbeitung befindet sich der Automat in dem Startzustand. 
Dann wird das erste Zeichen gelesen. 
In Abhängigkeit von diesem Zeichen geht der Automat in einen anderen 
Zustand über. 
Dieser Vorgang wird für jedes weitere eingegebene Zeichen wiederholt. 
Die Analyse wird abgebrochen, wenn ein Zeichen auftritt, für das im aktuellen 
Zustand kein weiterer Übergang vorgesehen ist. 
Ist das Ende der Eingabefolge erreicht, so wird noch geprüft, ob ein 
als mögliches Ende markierter Zustand erreicht wurde. 
In diesem Fall gilt die Folge als akzeptiert. 

\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
Der einfache Automat in Bild \ref{f:end_berg} prüft auf das Wort \texttt{berg}.
Die Zustände sind als Kreise dargestellt. 
An den Übergangspfeilen steht jeweils, welches Zeichen dazu gehört.
Endzustände werden durch einen doppelten Kreis hervorgehoben.

\begin{figure}
\begin{center}
\parbox{0.7\textwidth}{
\entrymodifiers={++[o][F-]}
\xymatrix @-1pc {
*\txt{start} \ar[r]
& S_0 \ar[r]^b
& S_1 \ar[r]^e
& S_2 \ar[r]^r
& S_3 \ar[r]^g
&*++[o][F=]{S_4}
}
}
\end{center}
\caption{Automat für Suche nach \texttt{berg}}\label{f:end_berg}
\end{figure}



Im Startzustand $S_0$ ist nur die Eingabe $b$ vorgesehen.
Dann erfolgt der Übergang zu dem Zustand $S_1$. 
Ansonsten wird die Analyse bereits hier als gescheitert abgebrochen. 
Entsprechend wird in $S_1$ nur $e$ erkannt.
Dieser Vorgang wird für 4 Eingabezeichen durchgeführt. 
Bei Übereinstimmung befindet sich der Automat dann im Zustand $S_3$ -- 
dem einzigen erlaubten Endzustand. 


\begin{uebung} Wie kann der Automat erweitert werden, so dass er auch \texttt{burg} akzeptiert?
\end{uebung}


\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
Ein etwas komplizierteres Beispiel ist der folgende Automat 
für die Darstellung von ganzen Zahlen mit optionalem Vorzeichen: \\
\begin{center}
\parbox{0.7\textwidth}{
\entrymodifiers={++}
\xymatrix @-1pc {
& 
& *++[o][F-]{S_1} \ar[rrd]^{1-9}
\\
*\txt{start} \ar[r]
& *++[o][F-]{S_0} \ar[rrr]^{1-9} \ar[ru]^+ \ar[rd]_{-}
& 
&
& *++[o][F=]{S_3} \ar@(ul,ur)[]^{0-9}
\\
& 
& *++[o][F-]{S_2} \ar[rru]_{1-9}
}
}
\end{center}

\noindent
Bei der Analyse der Folge \texttt{+342} ergibt sich folgender Ablauf:
\begin{center}
\begin{tabular}{c|c} 
  Zustand & Eingabe \\ \hline
  $S_0$   &  +  \\
  $S_1$   &  3  \\
  $S_3$   &  4  \\
  $S_3$   &  2  \\
  $S_3$   &  \emph{Ende}  \\
\end{tabular}
\end{center}
Der Automat befindet sich nach der Verarbeitung der Eingangsfolge in einem Enzustand.
Damit ist die Eingabe akzeptiert.

\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
Definition Automat:\\
\begin{center}
\fbox{
\parbox{0.7\textwidth}{
Gegeben sei eine Eingabemenge $E$, 
eine Zustandsmenge $Z$, ein Anfangszustand $z_a \in Z$, 
eine Menge von Endzuständen $F \subseteq Z$ und eine Abbildung 
$f: E \times Z \to Z$. 
Dann bildet das 5-Tupel ($E$, $Z$, $z_a$, $f$, $F$) einen Automaten A. 
Für endliche $E$ und $Z$ ist $A$ ein endlicher Automat.
} }
\end{center}
%
Die Abbildung $f: E \times Z \to Z$, die für jede Kombination von Zustand und Eingangswert 
den Folgezustand festlegt, kann übersichtlich als Matrix geschrieben werden. 

\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
\begin{beispiel} Zahlen\\
\begin{itemize}
    \item $E = \{+, -, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$
    \item $Z = \{S_0, S_1, S_2, S_3\}$
    \item $z_a = S_0$ 
    \item $F= \{S_3\}$ 
\item Abbildung $f$:
\[
\begin{array}{|c||c|c|c|c|} \hline
              & S_0 & S_1 & S_2 & S_3  \\ \hline \hline
  +           & S_1 &     &     &        \\ \hline
  -           & S_2 &     &     &        \\ \hline
  0           &     &     &     & S_3  \\ \hline
  1-9         & S_3 & S_3 & S_3 & S_3  \\ \hline
\end{array}
\]
\end{itemize}    
\end{beispiel} 



\begin{beispiel} Kaffeeautomat: \\
Der folgende Automat akzeptiert alle Zahlungen mit 10, 20 und 30 Cent Münzen,
die zum Endbetrag von 60 Cent führen. 
\begin{center}
\parbox{0.7\textwidth}{
\entrymodifiers={++}
\xymatrix @-1pc {
& 
& 
& 
& *++[o][F-]{20} \ar[rr]^{20} \ar[rd]^{10} 
& 
& *++[o][F-]{40} \ar@/^/[rrrd]^{20} \ar[rd]^{10} 
& 
\\
*\txt{start} \ar[r] 
& *++[o][F-]{0} \ar@/^/[rrru]^{20} \ar[rr]^{10}  \ar@(dr,dl)[0,6]_{50}
& 
& *++[o][F-]{10} \ar[ru]^{10} \ar[rr]^{20} \ar@(dr,dl)[0,6]_{50}
& 
& *++[o][F-]{30} \ar[ru]^{10} \ar[rr]^{20}
& 
& *++[o][F-]{50} \ar[rr]^{10} 
&
& *++[o][F=]{60}
}
}
\end{center}
\end{beispiel} 

\begin{uebung}
\label{ue:kaffee}
Geben Sie für den Kaffeeautomaten die Abbildung $f$ in Matrixform an. 
\end{uebung}

\begin{uebung}
\label{ue:fsm_c}
Implementieren Sie in C einen endlichen Automaten zur Erkennung von Zahlen. 
Lesen Sie jeweils die nächste Zahl mit \texttt{getch} ein.  
Verwenden Sie eine Variable zum Speichern des aktuellen Zustandes. 
Die verschiedenen Zustände sollen dann als 
case-Marken einer switch-Auswahl auf dieser Variablen realisiert werden.
\end{uebung}

\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}

\begin{center}
\fbox{
\parbox{0.7\textwidth}{
Reguläre Ausdrücke und endliche Automaten  sind äquivalent. 
Zu jedem regulären Ausdruck existiert ein endlicher Automaten,
der genau die beschriebenen Muster akzeptiert.  
Umgekehrt lässt sich für jeden endlichen Automaten ein gleichwertiger
regulärer Ausdruck angeben. 
} }
\end{center}
%

\subsection{$\varepsilon$-"Ubergänge}
\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
In vielen Fällen sind Übergänge nützlich, 
bei denen kein Eingangssymbol gelesen wird. 
Man bezeichnet solche Übergänge als $\varepsilon$-Übergänge.
Ein entsprechender Automat für die Darstellung von ganzen Zahlen mit optionalem Vorzeichen 
hat folgende Form: \\
\begin{center}
\parbox{0.7\textwidth}{
\entrymodifiers={++}
\xymatrix @-1pc {
& 
& *++[o][F-]{1} \ar[rd]^{\varepsilon}
\\
*\txt{start} \ar[r]
& *++[o][F-]{0} \ar[rr]^{\varepsilon} \ar[ru]^+ \ar[rd]_{-}
& 
& *++[o][F-]{3} \ar[rr]^{1-9}
& 
& *++[o][F=]{4} \ar@(ul,ur)[]^{0-9}
\\
& 
& *++[o][F-]{2} \ar[ru]_{\varepsilon}
}
}
\end{center}

Die $\varepsilon$-Übergänge vereinfachen den Aufbau der Automaten. 
Sie sind aber keine wirkliche Erweiterung der Möglichkeiten. 
Man kann zeigen, dass sich jeder Automat mit $\varepsilon$-Übergängen
in einen gleichwertigen Automat ohne derartige Übergänge umformen lässt. 

\subsection{Endliche Maschinen}
Fügt man zu einem Automaten eine Ausgabe hinzu, so erhält man eine Maschine.
Man unterscheidet:
\begin{itemize}
    \item Moore-Maschine:  Ausgabe erfolgt im Zustand
    \item Mealy-Maschine: Ausgabe erfolgt bei Übergängen
\end{itemize}    
%
Wir betrachten als Beispiel eine Moore-Maschine zur Addition von Binärzahlen. 
\begin{itemize}
    \item Eingang: die Werte der beiden Zahlen an einer Stelle.
     $E = \{00, 01, 10, 11\}$
    \item Ergebnis der jeweiligen Addition unter 
    Berücksichtigung eines eventuellen Übertrags.
\end{itemize}    
Beispiel:
\[
\begin{array}{|c|c|c|c|c|c|c|c|c|}  \hline
                  & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 1  \\ \hline
                  & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1  \\ \hline
\mbox{\"Ubertrag} &   &   &   & 1 & 1 &   & 1 &    \\ \hline \hline
                  & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 0  \\ \hline
  \end{array}
\]
\begin{itemize}
    \item Eingangsfolge: $11, 00, 11, 11, 00, 10, 10, 01 $ \\
    \item Ausgangsfolge: $0, 1, 0, 1, 1, 1, 1, 1$ 
\end{itemize}    
%
Wir verwenden dabei folgende Notation: $S_n^x$ ist der Zustand $n$ mit der Ausgabe $x$.
Dabei bezeichnet $S_n^{\varepsilon}$ einen Zustand ohne Ausgabe. 
\begin{center}
\parbox{0.7\textwidth}{
\entrymodifiers={++}
\xymatrix @-1pc {
& *++[o][F-]{S_1^0} \ar@/_/[d]_{\varepsilon}
&
&
&
&
& *++[o][F-]{S_5^1} \ar@/^/[ld]^{\varepsilon}
\\
*\txt{start} \ar[r]
& *++[o][F-]{S_0^{\varepsilon}} \ar@/_/[u]_{00} \ar@/^/[d]^{01,10}  \ar[rr]^{11} 
&
& *++[o][F-]{S_3^0} \ar[rr]^{\varepsilon} 
&
& *++[o][F-]{S_4^{\varepsilon}} \ar@/^/[dllll]^{00}  \ar@/^/[ru]^{11}   \ar@/^/[rd]^{01,10}  
\\
& *++[o][F-]{S_2^1} \ar@/^/[u]^{\varepsilon}
&
&
&
&
& *++[o][F-]{S_6^0} \ar@/^/[lu]^{\varepsilon}
}
}
\end{center}
Für das Beispiel ergibt sich folgende Zustandsfolge: 
\[
S_0, S_3, S_4, S_2, S_0, S_3, S_4, S_5, S_4, S_2, S_0, S_2, S_0, S_2, S_0, S_2, S_0
\]




\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
\section{Grammatiken}
Ausgangspunkt unserer Betrachtungen ist ein Vorrat von Buchstaben.
Für die Menge der Buchstaben führen wir die Bezeichnung $\Sigma$ gemäß
\begin{equation}
    \Sigma = \{a, b, c, \ldots, n\}
\end{equation}
ein.
Aus diesen Buchstaben werden Wörter gebildet.
Ein einfaches Beispiel ist die Menge mit nur zwei Elementen
%
\begin{equation}
    \Sigma_d = \{0, 1\}
\end{equation}
%
Indem man die beiden Buchstaben aneinander reiht, lassen sich mit diesem Vokabular
alle möglichen Binärzahlen darstellen:
\begin{equation}
\begin{array}{l}
  0 \\
  1 \\
  01 \\
  10 \\
  001 \\
  \ldots \\
\end{array}
\end{equation}
Alle diese Folgen oder Wörter zusammen bilden wiederum eine Menge, die als $\Sigma^+$ bezeichnet wird.
Nimmt man noch die leere Folge $\varepsilon$ hinzu, so erhält man die Menge $\Sigma^*$
(Kleene-Stern-Produkt, benannt nach Stephen C.\ Kleene, 1909-1998). \index{Kleene,  Stephen C.}
Diese unendlich große Menge enthält alle möglichen Folgen.
Jede Einschränkung der Abfolge wählt eine Teilmenge von $\Sigma^*$ aus.
Ein Beispiel ist die Menge $B$ der Bytes, das heißt alle Folgen von 8 Symbolen aus unserer Menge $\Sigma_d$:
%
\begin{equation}
    \begin{array}{ccccc}
      B & = & \{ & 00000000 & \\
        &   &    & 10000000 & \\
        &   &    & \ldots   & \} \\
    \end{array}
\end{equation}
%
Eine solche Menge von Wörtern definiert eine Sprache.
Weitere Beispiele sind die Bytes mit gerader Parität oder die Sprache
%
\begin{equation}
      B_n = \{ 0^n \; 1^n \}
\end{equation}
%
mit jeweils zwei gleich langen Blöcken von Nullen und Einsen.
Die Schreibweise $a^n$ ist ein Abkürzung für $n$ aufeinander folgende Buchstaben $a$.

In den allermeisten Fällen ist die vollständige Aufzählung aller Wörter einer Sprache
nicht praktikabel.
Gesucht sind daher andere Möglichkeiten, die Sprache zu beschreiben.
Noam Chomsky \index{Chomsky, Noam}(amerikanischer Linguist, geb. 1928) entwickelte das Konzept der
generativen Grammatiken. \index{generative Grammatik}
Dabei beschreibt für eine Sprache ein Regelwerk, wie alle möglichen Wörter konstruiert werden können.
Die verschiedenen Typen von Grammatiken wurden von ihm nach der Komplexität der Regeln klassifizieren.

Eine Grammatik ist eine gut geeignete Darstellungsform, um Folgen zu generieren.
Für die umgekehrte Fragestellung, ob eine gegebene Folge von der Grammatik abgedeckt ist,
ist diese Darstellung weniger nutzbar.
Eine solche Prüfung lässt sich sehr viel einfacher mit Automaten durchführen.
Es erweist sich, dass für die von Chomsky eingeführte Hierarchie von Grammatiken eine
Äquivalenz zu einer Hierarchie von Automaten besteht.
Für jede Grammatik lässt sich ein entsprechender Automat konstruieren, der nur die
von dieser Grammatik erzeugten Folgen akzeptiert.
Welcher Typ von Automat dazu im Einzelfall notwendig ist, hängt von der Einordnung der Grammatik
in die Hierarchie ab.


\subsection{Produktionsregeln und Ableitungsbäume}
Eine Grammatik enthält eine Reihe von Produktionsregeln. \index{Produktionsregel}
Die Regeln haben die Form
%
\begin{equation}
    l \rightarrow r
\end{equation}
%
mit der Bedeutung "`der Ausdruck $l$ auf der linken Seite wird durch $r$ ersetzt"'.
Eine solche Regel ist
%
\[
    negZahl \rightarrow - \; Betrag
\]
%
d.h. eine negative Zahl wird durch das Vorzeichen $-$ und den Betrag gebildet.
In diesem Fall ist $-$ ein Symbol aus der Eingangsmenge. 
Da bei einem solchen Symbol keine weitere Regel mehr anzuwenden ist, wird es als 
Terminalsymbol bezeichnet. \index{Terminalsymbol}
Das Symbole \emph{Betrag} dagegen ist eine  Kategorie, die
durch Anwendung von Produktionsregeln weiter aufgelöst wird.
Daher wird dieser Typ von Symbolen
als Nichtterminalsymbolen oder einfach Nichtterminals bezeichnet. \index{Nichtterminalsymbol}
Die Nichtterminals und die Regeln können wieder als Mengen betrachtet werden.
Dann ist eine Grammatik $G$ bestimmt durch die drei Mengen $\Sigma$, $N$  und $P$ für die
Terminals, Nichtterminals und Produktionsregeln.
Zusätzlich benötigt man noch einen Startpunkt $S$ für die Anwendung der Regeln.
Zusammenfassend gilt dann
\begin{equation}
\label{e_gramm}
    G = (\Sigma, N, P, S)
\end{equation}
Mit $L(G)$ bezeichnet man dann die durch die Grammatik definierte Sprache. 
Betrachten wir das einfache Beispiel in Tabelle \ref{t_eg}.
Die Grammatik beschreibt, wie aus den Symbolen $\{+, -, 0, 1\}$ positive 
und negative ganze Binärzahlen gebildet werden. 
Ausgangspunkt für die Produktionsregeln ist das Nichtterminalsymbol $W$ (Wert).
Darauf können zwei Regeln angewandt werden:

\begin{table}
  \centering
  \caption{\label{t_eg}Einfache Grammatik}
\begin{tabular}{|l|l|} \hline
  $\Sigma$ & $+$, $-$, $0$, $1$  \\   \hline
  $N$ &   $W \; B \; Z \; V$ \\   \hline
  $P$ &   $W   \to B$  \\
    &   $W   \to V \; B$ \\
    &   $B   \to Z $\\
    &   $B   \to Z \; B $\\
    &   $Z   \to 0 $\\
    &   $Z   \to 1 $\\
    &   $V   \to - $\\
    &   $V   \to + $\\ \hline
  $S$ &   $W$  \\   \hline
\end{tabular}
\end{table}

\[
W \to V B 
\]
und
\[
W \to B 
\]
Der Wert besteht entweder aus Vorzeichen plus Betrag oder nur einem Betrag.
Wählen wir die erste Alternative.
Auch für $V$ stehen zwei Regeln zur Verfügung.
Das Vorzeichen kann  $+$ oder $-$ sein. 
Der Betrag wird als Folge von Ziffern gebildet. 
Durch wiederholte Anwendung der Regel $B   \to Z \; B $ können beliebig lange 
Wörter erzeugt werden. 

Der Ableitungsprozess endet, wenn der Ausdruck nur noch Terminals enthält.
Jedes so generierte Wort gehört zur Grammatik.
Im allgemeinen ist nicht garantiert, dass jede Ableitung zu einem legalen Ergebnis führt.
Es können bei der Ableitung Nichtterminals übrig bleiben, für die keine passenden Regeln spezifiziert sind.
Der Ableitungsprozess lässt sich als Baum darstellen. 
Das Startsymbol bildet die Wurzel.
Die Nichtterminals sind die Knoten und die Terminals schließlich sind die Blätter. 
Als Beispiel erhält man aus der Folge $+10$ folgenden Baum:

\leaf{+}
\branch{1}{V}
\leaf{1}
\branch{1}{Z}
\leaf{0}
\branch{1}{Z}
\branch{1}{B}
\branch{2}{B}
\branch{2}{W}
\branch{1}{S}
\begin{center}
\tree
\end{center}


Die Definition \ref{e_gramm} gilt für alle Grammatiken der Chomsky Hierarchie.
Die einzelnen Typen unterscheiden sich in den Einschränkungen für die Produktionsregeln.

\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
\begin{uebung} Anschrift-Grammatik\\
Wie sieht eine Grammatik aus, mit der man den Aufbau von Anschriften aus Name, Vorname, Straße, etc. 
beschreibt? 
\end{uebung}

\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
\begin{uebung} Radio-Grammatik\\
\begin{enumerate}
    \item Geben Sie 3 Sätze an, die mit der folgenden regulären Grammatik generiert werden können.
    \item Zeichnen Sie für einen der Beispielssätze den Ableitungsbaum.
    \item Erweitern Sie die Grammatik so,
    dass optional Sätze auch mit dem Wort \emph{Bitte} eingeleitet werden können.
    \item Wie sieht der zugehörige endliche Automat aus?
\end{enumerate}
\end{uebung}
\begin{center}
\begin{tabular}{|l|l|} \hline
  $\Sigma$ & $Radio$, $CD$, $ein$, $aus$, \emph{nächstes}, $Lied$, \emph{Stück}  \\   \hline
  N &   BEFEHL, SCHALTEN, LIED, GERÄT \\   \hline
  P
    &   BEFEHL  $\to$ GERÄT    \\
    &   BEFEHL  $\to$ GERÄT SCHALTEN  \\
    &   BEFEHL  $\to$ \emph{nächstes} LIED \\
    &   GERÄT   $\to$ $CD$    \\
    &   GERÄT   $\to$ $Radio$ \\
    &   LIED    $\to$ $Lied$  \\
    &   LIED    $\to$ \emph{Stück}  \\
    &   SCHALTEN   $\to ein $\\
    &   SCHALTEN   $\to aus $\\ \hline
  S &   BEFEHL  \\   \hline
\end{tabular}
\end{center}

\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
\subsection{Einseitig lineare Grammatiken} \index{Einseitig lineare Grammatiken}
Die einfachsten Grammatiken - Typ 3 - sind dadurch gekennzeichnet, dass die
Ableitungen nur in eine Richtung erfolgen.
Alle Regeln haben bei einer rechts-linearen Grammatik die Form
\begin{eqnarray}\label{e_typ3}
    A &\to& w \\
    A &\to&  w B  \nonumber
\end{eqnarray}
mit $A,B \in N$ und $w \in \Sigma^*$.
In jeder Regel steht auf der linken Seite ein Nichtterminal und auf der rechten Seite
entweder ein Ausdruck mit Terminals alleine oder ein solcher Ausdruck gefolgt von einem Nichtterminal.
Zu jeder derartigen Grammatik existiert ein endlicher Automat, der die
mit der Grammatik verträglichen Folgen akzeptiert.
Die möglichen Folgen sind damit auch durch reguläre Ausdrücke beschrieben 
und man spricht daher auch von regulären Sprachen. \index{reguläre Sprachen}
Äquivalent zu den rechts-linearen Grammatiken sind die links-linearen Grammatiken,
bei denen die zweite Grundform der Regeln $A \to B w$ ist.
  

\subsection{Möglichkeiten und Grenzen endlicher Automaten und regulärer Sprachen}
Reale Rechner kann man als endliche Automaten interpretieren. 
Zu einem Zeitpunkt befindet sich der Rechner in einem bestimmten Zustand, 
charakterisiert durch die Inhalte in all seinen Speicherzellen und Registern.
Indem der nächste Befehl ausgeführt wird, ändern sich einige Inhalte. 
Die neuen Inhalte bestimmen wiederum den Folgezustand.  

\begin{uebung}
Betrachten Sie einen Rechner mit 256 MByte Speicher. 
Dieser Rechner soll als endlicher Automat modelliert werden. 
Wie viele Zustände werden dazu benötigt?
\end{uebung}

\ifthenelse{\equal{\meinmodus}{folien}}{\newpage}{}
Von großer Bedeutung ist das Wortproblem: \index{Wortproblem}
\begin{itemize}
    \item Kann man für eine gegebene Symbolfolge entscheiden, 
    ob sie ein Wort der regulären Grammatik ist? 
    Formal ausgedrückt: gilt für eine Folge $w \in \Sigma^*$ 
    und eine Grammatik $G$ $w \in L(G)$ oder  $w \not\in L(G)$?
\end{itemize}    
Anwendungen dazu sind:
\begin{itemize}
    \item Erfüllt ein Text die Suchabfrage?
    \item Ist ein Programm syntaktisch korrekt?
\end{itemize}    
Diese Frage ist entscheidend für die praktische Verwendbarkeit. 
Eine Sprache, bei der nicht entscheidbar ist, ob eine Symbolfolge dazu gehört oder 
nicht, ist als Programmiersprache ungeeignet, da man keinen Compiler dazu 
konstruieren kann. 
Glücklicherweise ist bei regulären Grammatiken das Wortproblem entscheidbar.
Es kann in der Tat für jede beliebige Symbolfolge entschieden werden, 
ob sie zu entsprechenden Sprache $L(G)$ gehört oder nicht.
Darüber hinaus lässt sich auch eine Aussage über den dazu notwendigen Rechenaufwand treffen. 

Typische Aussagen über die Komplexität haben die Form $O( f(N) )$, wobei $N$
die Anzahl der zu verarbeitenden Werte bezeichnet.
Der Ausdruck $O(f(N))$ besagt, dass die Komplexität proportional ist zu einer Funktion $f(N)$.
Mit anderen Worten,
es gibt zwei Konstanten $a$ und $b$, so dass für die Anzahl der Rechenschritte 
die Formel
\begin{equation}\label{e_o}
     a \cdot f(N) + b
\end{equation}
gilt.
Bei einem Algorithmus mit $O(N)$ etwa steigt der Aufwand proportional zu Anzahl der Daten.
Demgegenüber würde bei einem Algorithmus mit $O(N^2)$  der Aufwand quadratisch ansteigen.

Das Wortproblem bei regulären Grammatiken hat die Komplexität $O(N)$, wobei $N$ die 
Länge der Symbolfolge bezeichnet. 
Mit wachsender Länge nimmt der Aufwand proportional zu. 
Dies ist ein sehr erfreuliches Ergebnis.
Probleme mit $O(N)$ sind gut lösbar.
Selbst bei langen Eingangsfolgen -- beispielsweise ein Programm mit vielen tausend
Zeilen -- ist der Compiler in überschaubarer Zeit fertig.  
 

Begrenzt wird die Darstellungsmöglichkeit der endlichen Automaten  durch das fehlende Gedächtnis.
Ein endlicher Automat verfügt über keinen expliziten Speicher.
Die Information liegt lediglich im aktuellen Zustand.
In Folge dieser Beschränkung sind Ausdrücke, die eine Information über die
bisherige Folge verwenden, im allgemeinen nicht abgedeckt.

Ein Musterbeispiel ist die Menge von Ausdrücken $\{a^nbc^n\}$, bei der
die Symbole $a$ und $c$  genau gleich oft auftreten.
Sofern es für $n$ keine Beschränkung gibt, kann man keinen endlichen Automaten konstruieren,
der diese Bedingung prüft. 
Es gibt keine Möglichkeit, die Anzahl der gesehenen Zeichen $a$ zu speichern. 
In der Grammatik liegt die Beschränkung im einseitigen Wachstum der Regeln. 
Die eigentlich benötigt Regel in der Art $A \to a B c$ widerspricht dem Konstruktionsprinzip von 
einseitig linearen Grammatiken.

Beispiele für derartige Fälle in Programmiersprachen sind Ausdrücke mit Klammern.
Setzt man für $a$ $($ und für $c$ $)$, so hat erhält man die Form $\{(^nb)^n\}$.
Es wird also verlangt, dass  für jede öffnende Klammer
wieder eine schließende Klammer gesetzt ist.
Ohne Begrenzung von $n$ lässt sich eine solche Sprache nicht durch eine reguläre Grammatik beschreiben.
 
 

\begin{uebung} \label{ue:bauer} Logische Knobelei \\
Man kann die Methoden der Aussagelogik auch zur Lösung von Knobelaufgaben einsetzen.
Dazu zerlegt man die Aufgabe in einfache Aussagen.
Die verschiedenen Kombinationen und ihre Bewertung
werden in einer Wahrheitstabelle zusammen gestellt.
Durch ein solches systematisches Vorgehen lässt sich ein  kompliziertes Problem
leichter lösen.

Betrachten Sie als Beispiel folgende Aufgabe:
In einem alten Rätsel kommt ein Bauer mit Gans, Hund und einem Sack Korn an einen Fluss.
In dem Fährboot kann er jeweils nur einen Teil mitnehmen.
Aber er darf niemals Gans und Hund oder Gans und Korn zusammen unbeaufsichtigt lassen
(und schon gar nicht alle drei).
Wie kann er das Problem lösen?
\begin{itemize}
    \item Betrachten Sie die 4 Aussagen A1:\emph{Bauer am linken Ufer}, A2:\emph{Gans am linken Ufer},
    A3:\emph{Hund am linken Ufer} und A4:\emph{Korn am linken Ufer}.
    A1 WAHR besagt dann, dass der Bauer am linken Ufer ist während er im Fall FALSCH
    sich auf der rechten Seite befindet.
    Die Anfangssituation ist WAHR WAHR WAHR WAHR oder kurz geschrieben 1111.
    \item Stellen Sie die Wahrheitstabelle für die erlaubten Kombinationen auf.
    \item Teilen Sie die legalen Kombinationen in zwei Gruppen gemäß der Position des Bauerns
    (linkes oder rechtes Ufer).
    \item Ein Überfahrt ist jetzt ein Übergang zwischen zwei Kombinationen in den beiden Gruppen.
    Dabei darf sich nur maximal eine Position ändern.
    \item Verfolgen Sie ausgehend von der Anfangssituation 1111 die möglichen Abfolgen
    bis zum Ziel 0000.
\end{itemize}
\end{uebung}
This is e-TeX, Version 3.141592-2.1 (MiKTeX 2.4) (preloaded format=latex 2000.11.28)  4 SEP 2007 14:49
entering extended mode
**skript.ltx
(skript.ltx
LaTeX2e <2001/06/01>
Babel <v3.7m> and hyphenation patterns for english, french, german, ngerman, du
mylang, nohyphenation, loaded.
(C:\texmf\tex\latex\base\book.cls
Document Class: book 2001/04/21 v1.4e Standard LaTeX document class
(C:\texmf\tex\latex\base\bk12.clo
File: bk12.clo 2001/04/21 v1.4e Standard LaTeX file (size option)
)
\c@part=\count79
\c@chapter=\count80
\c@section=\count81
\c@subsection=\count82
\c@subsubsection=\count83
\c@paragraph=\count84
\c@subparagraph=\count85
\c@figure=\count86
\c@table=\count87
\abovecaptionskip=\skip41
\belowcaptionskip=\skip42
\bibindent=\dimen102
) (C:\texmf\tex\latex\german\german.sty
v2.5e 1998-07-08
Package: german 1998/07/08 v2.5e Support for writing german texts (br)
\grmnU@D=\dimen103
german -- \language number for Austrian undefined, default 2 used.
) (C:\texmf\tex\latex\germbib\bibgerm.sty
Package: bibgerm 2000/08/18 v0.1 Support for mixed language bibliographies

** Macros for german `BibTeX'ing added to Style Option `german' 20 Apr 1993 **
** idea and languages `german' and `USenglish' implemented by M. Wallmeier **
** Modified for LaTeX 2e and german.sty 2.5b by A. Scherer 1 Nov 1995 **
** Modified for ngerman.sty and babel.sty by H. Harders 21 August 2000 **)
(C:\texmf\tex\latex\base\fontenc.sty
Package: fontenc 2001/06/05 v1.94 Standard LaTeX package
 (C:\texmf\tex\latex\base\t1enc.def
File: t1enc.def 2001/06/05 v1.94 Standard LaTeX file
LaTeX Font Info:    Redeclaring font encoding T1 on input line 38.
))
(C:\texmf\tex\latex\base\inputenc.sty
Package: inputenc 2001/07/10 v0.99a Input encoding file 
 (C:\texmf\tex\latex\base\ansinew.def
File: ansinew.def 2001/07/10 v0.99a Input encoding file 
))
(C:\texmf\tex\latex\eepic\epic.sty
Enhancements to Picture Environment. Version 1.2 - Released June 1, 1986
\@@multicnt=\count88
\d@lta=\count89
\@delta=\dimen104
\@@delta=\dimen105
\@gridcnt=\count90
\@joinkind=\count91
\@dotgap=\dimen106
\@ddotgap=\dimen107
\@x@diff=\count92
\@y@diff=\count93
\x@diff=\dimen108
\y@diff=\dimen109
\@dotbox=\box26
\num@segments=\count94
\num@segmentsi=\count95
\@datafile=\read1
) (C:\texmf\tex\latex\eepic\eepic.sty
Extension to Epic and LaTeX. Version 1.1e - Released Dec 21, 1999
\@gphlinewidth=\count96
\@eepictcnt=\count97
\@tempdimc=\dimen110
\maxovaldiam=\dimen111
\@filltype=\box27
) (C:\texmf\tex\latex\base\ifthen.sty
Package: ifthen 2001/05/26 v1.1c Standard LaTeX ifthen package (DPC)
) (C:\texmf\tex\latex\graphics\epsfig.sty
Package: epsfig 1999/02/16 v1.7a (e)psfig emulation (SPQR)

(C:\texmf\tex\latex\graphics\graphicx.sty
Package: graphicx 1999/02/16 v1.0f Enhanced LaTeX Graphics (DPC,SPQR)

(C:\texmf\tex\latex\graphics\keyval.sty
Package: keyval 1999/03/16 v1.13 key=value parser (DPC)
\KV@toks@=\toks14
)
(C:\texmf\tex\latex\graphics\graphics.sty
Package: graphics 2001/07/07 v1.0n Standard LaTeX Graphics (DPC,SPQR)
 (C:\texmf\tex\latex\graphics\trig.sty
Package: trig 1999/03/16 v1.09 sin cos tan (DPC)
) (C:\texmf\tex\latex\00miktex\graphics.cfg
File: graphics.cfg 2003/03/12 v1.1 MiKTeX 'graphics' configuration
)
Package graphics Info: Driver file: dvips.def on input line 80.

(C:\texmf\tex\latex\graphics\dvips.def
File: dvips.def 1999/02/16 v3.0i Driver-dependant file (DPC,SPQR)
))
\Gin@req@height=\dimen112
\Gin@req@width=\dimen113
)
\epsfxsize=\dimen114
\epsfysize=\dimen115
) (C:\texmf\tex\latex\base\makeidx.sty
Package: makeidx 2000/03/29 v1.0m Standard LaTeX package
) (C:\texmf\tex\latex\ntgclass\a4.sty
Package: a4 1999/03/03 v1.2f A4 based page layout
) (C:\texmf\tex\generic\xypic\xy.sty
(C:\texmf\tex\generic\xypic\xy.tex Bootstrap'ing: catcodes, docmode,
(C:\texmf\tex\generic\xypic\xyrecat.tex)
(C:\texmf\tex\generic\xypic\xyidioms.tex)

 Xy-pic version 3.7 <1999/02/16>
 Copyright (c) 1991-1998 by Kristoffer H. Rose <krisrose@ens-lyon.fr>
 Xy-pic is free software: see the User's Guide for details.

Loading kernel: messages; fonts; allocations: state,
\X@c=\dimen116
\Y@c=\dimen117
\U@c=\dimen118
\D@c=\dimen119
\L@c=\dimen120
\R@c=\dimen121
\Edge@c=\toks15
\X@p=\dimen122
\Y@p=\dimen123
\U@p=\dimen124
\D@p=\dimen125
\L@p=\dimen126
\R@p=\dimen127
\Edge@p=\toks16
\X@origin=\dimen128
\Y@origin=\dimen129
\X@xbase=\dimen130
\Y@xbase=\dimen131
\X@ybase=\dimen132
\Y@ybase=\dimen133
\X@min=\dimen134
\Y@min=\dimen135
\X@max=\dimen136
\Y@max=\dimen137
\lastobjectbox@=\box28
\zerodotbox@=\box29
\almostz@=\dimen138
 direction,
\d@X=\dimen139
\d@Y=\dimen140
\K@=\count98
\KK@=\count99
\Direction=\count100
\K@dXdY=\dimen141
\K@dYdX=\dimen142
\xyread@=\read2
\xywrite@=\write3
\csp@=\count101
\quotPTK@=\dimen143

utility macros; pictures: \xy, positions,
\swaptoks@@=\toks17
\connectobjectbox@@=\box30
 objects,
\styletoks@=\toks18
 decorations;
kernel objects: directionals, circles, text; options; algorithms: directions,
edges, connections;  Xy-pic loaded)
Package: xy 1999/02/16 Xy-pic version 3.7
 (C:\texmf\tex\generic\xypic\xycurve.tex
 Xy-pic option: Curve and Spline extension v.3.7 curve,
\crv@cnt@=\count102
\crvpts@=\toks19
\splinebox@=\box31
\splineval@=\dimen144
\splinedepth@=\dimen145
\splinetol@=\dimen146
\splinelength@=\dimen147
 circles,
\L@=\dimen148
 loaded))
(C:\texmf\tex\generic\xypic\xypic.sty (C:\texmf\tex\generic\xypic\xy.sty
(C:\texmf\tex\generic\xypic\xy.tex not reloaded)

LaTeX Warning: You have requested package `xypic',
               but the package provides `xy'.

Package: xy 1999/02/16 Xy-pic version 3.7
) (C:\texmf\tex\generic\xypic\xyv2.tex
 Xy-pic option: Version 2 Compatibility v.3.4

Xy-pic Warning: `\stop' redefined.

(C:\texmf\tex\generic\xypic\xyframe.tex
 Xy-pic option: Frame and Bracket extension v.3.7 loaded)
(C:\texmf\tex\generic\xypic\xymatrix.tex  Xy-pic option: Matrix feature v.3.4
\Row=\count103
\Col=\count104
\queue@=\toks20
\queue@@=\toks21
\qcount@=\count105
\qcount@@=\count106
\matrixsize@=\count107

loaded) (C:\texmf\tex\generic\xypic\xyarrow.tex
 Xy-pic option: Arrow and Path feature v.3.5 path, \ar, loaded) loaded))
(C:\texmf\tex\latex\qobitree\QobiTree.tex
\c@treecount=\count108
\c@branchcount=\count109
\parentbox=\box32
\treebox=\box33
\treeboxone=\box34
\treeboxtwo=\box35
\treeboxthree=\box36
\treeboxfour=\box37
\treeboxfive=\box38
\treeboxsix=\box39
\treeboxseven=\box40
\treeboxeight=\box41
\treeboxnine=\box42
\treeboxten=\box43
\treeboxeleven=\box44
\treeboxtwelve=\box45
\treeboxthirteen=\box46
\treeboxfourteen=\box47
\treeboxfifteen=\box48
\treeboxsixteen=\box49
\treeboxseventeen=\box50
\treeboxeighteen=\box51
\treeboxnineteen=\box52
\treeboxtwenty=\box53
\treeoffsetone=\skip43
\treeoffsettwo=\skip44
\treeoffsetthree=\skip45
\treeoffsetfour=\skip46
\treeoffsetfive=\skip47
\treeoffsetsix=\skip48
\treeoffsetseven=\skip49
\treeoffseteight=\skip50
\treeoffsetnine=\skip51
\treeoffsetten=\skip52
\treeoffseteleven=\skip53
\treeoffsettwelve=\skip54
\treeoffsetthirteen=\skip55
\treeoffsetfourteen=\skip56
\treeoffsetfifteen=\skip57
\treeoffsetsixteen=\skip58
\treeoffsetseventeen=\skip59
\treeoffseteighteen=\skip60
\treeoffsetnineteen=\skip61
\treeoffsettwenty=\skip62
\treeshiftone=\skip63
\treeshifttwo=\skip64
\treeshiftthree=\skip65
\treeshiftfour=\skip66
\treeshiftfive=\skip67
\treeshiftsix=\skip68
\treeshiftseven=\skip69
\treeshifteight=\skip70
\treeshiftnine=\skip71
\treeshiftten=\skip72
\treeshifteleven=\skip73
\treeshifttwelve=\skip74
\treeshiftthirteen=\skip75
\treeshiftfourteen=\skip76
\treeshiftfifteen=\skip77
\treeshiftsixteen=\skip78
\treeshiftseventeen=\skip79
\treeshifteighteen=\skip80
\treeshiftnineteen=\skip81
\treeshifttwenty=\skip82
\treewidthone=\skip83
\treewidthtwo=\skip84
\treewidththree=\skip85
\treewidthfour=\skip86
\treewidthfive=\skip87
\treewidthsix=\skip88
\treewidthseven=\skip89
\treewidtheight=\skip90
\treewidthnine=\skip91
\treewidthten=\skip92
\treewidtheleven=\skip93
\treewidthtwelve=\skip94
\treewidththirteen=\skip95
\treewidthfourteen=\skip96
\treewidthfifteen=\skip97
\treewidthsixteen=\skip98
\treewidthseventeen=\skip99
\treewidtheighteen=\skip100
\treewidthnineteen=\skip101
\treewidthtwenty=\skip102
\daughteroffsetone=\skip103
\daughteroffsettwo=\skip104
\daughteroffsetthree=\skip105
\daughteroffsetfour=\skip106
\branchwidthone=\skip107
\branchwidthtwo=\skip108
\branchwidththree=\skip109
\branchwidthfour=\skip110
\parentoffset=\skip111
\treeoffset=\skip112
\daughteroffset=\skip113
\branchwidth=\skip114
\parentwidth=\skip115
\treewidth=\skip116
)
\@indexfile=\write4

Writing index file skript.idx
(skript.aux (gnuplot/log.aux) (gnuplot/h.aux) (trans.aux) (last.aux)
(gnuplot/modulo.aux)

LaTeX Warning: Label `ue_rtt' multiply defined.

)
LaTeX Font Info:    Checking defaults for OML/cmm/m/it on input line 23.
LaTeX Font Info:    ... okay on input line 23.
LaTeX Font Info:    Checking defaults for T1/cmr/m/n on input line 23.
LaTeX Font Info:    ... okay on input line 23.
LaTeX Font Info:    Checking defaults for OT1/cmr/m/n on input line 23.
LaTeX Font Info:    ... okay on input line 23.
LaTeX Font Info:    Checking defaults for OMS/cmsy/m/n on input line 23.
LaTeX Font Info:    ... okay on input line 23.
LaTeX Font Info:    Checking defaults for OMX/cmex/m/n on input line 23.
LaTeX Font Info:    ... okay on input line 23.
LaTeX Font Info:    Checking defaults for U/cmr/m/n on input line 23.
LaTeX Font Info:    ... okay on input line 23.


bibgerm.sty: (n)german.sty 2.5b detected

(kapitel.ltx
LaTeX Font Info:    External font `cmex10' loaded for size
(Font)              <14.4> on input line 15.
LaTeX Font Info:    External font `cmex10' loaded for size
(Font)              <7> on input line 15.
 [1



]
LaTeX Font Info:    External font `cmex10' loaded for size
(Font)              <12> on input line 19.
LaTeX Font Info:    External font `cmex10' loaded for size
(Font)              <8> on input line 19.
LaTeX Font Info:    External font `cmex10' loaded for size
(Font)              <6> on input line 19.

Underfull \vbox (badness 10000) has occurred while \output is active []

 [2]
\c@uebung=\count110
\c@beispiel=\count111
\c@definition=\count112

(vorwort.ltx) [3] [4

] (skript.toc [5] [6] [7] [8] [9] [10])
\tf@toc=\write5
 [11] [12

]
(geschichte.ltx
Kapitel 1.
[1

]
File: bilder/lochstreifen.eps Graphic file (type eps)
 <bilder/lochstreifen.eps>
File: bilder/lochkarte.eps Graphic file (type eps)
 <bilder/lochkarte.eps> [2] [3]
Underfull \vbox (badness 6220) has occurred while \output is active []

 [4]
Overfull \hbox (1.15762pt too wide) in paragraph at lines 157--166
[][]\T1/cmr/m/n/12 Die 1945/46 fer-tig-ge-stell-te ENIAC (\T1/cmr/m/it/12 Elec-
tro-nic Nu-me-ri-cal In-te-gra-tor And Com-
 []

LaTeX Font Info:    External font `cmex10' loaded for size
(Font)              <5> on input line 179.
[5] [6]
LaTeX Font Info:    Try loading font information for OMS+cmr on input line 223.

 (C:\texmf\tex\latex\base\omscmr.fd
File: omscmr.fd 1999/05/25 v2.5h Standard LaTeX font definitions
)
LaTeX Font Info:    Font shape `OMS/cmr/m/n' in size <12> not available
(Font)              Font shape `OMS/cmsy/m/n' tried instead on input line 223.

Overfull \hbox (1.90173pt too wide) in paragraph at lines 244--254
\T1/cmr/m/n/12 Stan-dar-dan-wen-dun-gen (Text-ver-ar-bei-tung, Ta-bel-len-kal-k
u-la-ti-on, Gra-phik, etc.) an-
 []

[7]) (physik.ltx [8]
Kapitel 2.
[9

] [10]
File: bilder/si.eps Graphic file (type eps)
 <bilder/si.eps>
File: bilder/si-as.eps Graphic file (type eps)
 <bilder/si-as.eps> [11]
File: bilder/pn.eps Graphic file (type eps)
 <bilder/pn.eps>
File: bilder/pn-sperr.eps Graphic file (type eps)

<bilder/pn-sperr.eps> [12]
File: bilder/pn-durch.eps Graphic file (type eps)
 <bilder/pn-durch.eps> [13]
File: bilder/transistor.eps Graphic file (type eps)
 <bilder/transistor.eps>
[14] [15] (inverter.pic) (nand.pic)
Underfull \vbox (badness 2318) has occurred while \output is active []

 [16]
(nor.pic) [17]) (vonneumann.ltx [18]
Kapitel 3.
[19

] (neumann.pic) [20]) (boole.ltx [21] [22

]
Kapitel 4.

Underfull \hbox (badness 10000) in paragraph at lines 41--50

 []

[23]
Underfull \hbox (badness 10000) in paragraph at lines 96--98

 []

[24]
Underfull \vbox (badness 2213) has occurred while \output is active []

 [25]
[26] [27] [28]
Underfull \hbox (badness 10000) in paragraph at lines 334--335

 []

[29] [30] [31]
Overfull \hbox (32.7303pt too wide) in paragraph at lines 497--501
[][]\T1/cmr/m/n/12 Graphische Ver-fah-ren, zum Bei-spiel das Mi-ni-mie-rungs-ve
r-fah-ren mit-tels Karnaugh-
 []


Overfull \hbox (24.01295pt too wide) in paragraph at lines 497--501
\T1/cmr/m/n/12 wur-de in der Stu-di-en-ar-beit [[]] ent-wickelt (http://tech-ww
w.informatik.uni-
 []


Overfull \hbox (10.72594pt too wide) in paragraph at lines 501--502
[][]\T1/cmr/m/n/12 Tabellarische Ver-fah-ren, zum Bei-spiel das Mi-ni-mie-rungs
-ver-fah-ren nach Quine-
 []

[32]
LaTeX Font Info:    Font shape `OMS/cmr/m/it' in size <12> not available
(Font)              Font shape `OMS/cmsy/m/n' tried instead on input line 546.

Overfull \hbox (7.97026pt too wide) in paragraph at lines 582--582
[]\T1/cmr/m/it/12 Alarm| 
 []


Overfull \hbox (7.97026pt too wide) in paragraph at lines 596--596
[]\T1/cmr/m/it/12 Alarm| 
 []

[33]) (../../inf1_pt/skript/zahlen.ltx [34]
Kapitel 5.
[35

]
Overfull \hbox (4.72003pt too wide) in alignment at lines 80--85
 [][][] []
 []

[36] [37] [38]
Overfull \hbox (0.21616pt too wide) in paragraph at lines 206--214
[]\T1/cmr/m/n/12 Während man bei der Po-tenz-me-tho-de zu-nächst die höchst-wer
-ti-ge Zif-fer be-stimmt,
 []

[39] [40] [41]) (zahlen_rechnen.ltx [42]
Overfull \hbox (6.44235pt too wide) in paragraph at lines 67--74
[][]\T1/cmr/m/n/12 Bild 5.1[] zeigt einen Auf-bau zur Ad-di-ti-on 4-stelliger B
i-n-är-zah-len. In der niedrieg-
 []

File: bilder/addierer.eps Graphic file (type eps)
<bilder/addierer.eps> [43] [44]
LaTeX Font Info:    Try loading font information for T1+cmtt on input line 161.

 (C:\texmf\tex\latex\base\t1cmtt.fd
File: t1cmtt.fd 1999/05/25 v2.5h Standard LaTeX font definitions
)
(integer_kreis.pic) [45]) (float_zahlen.ltx [46] [47] [48] [49]
Overfull \hbox (12.15903pt too wide) in paragraph at lines 208--215
\T1/cmr/m/n/12 chen Schal-tungs-auf-wand. Frü-her wur-den da-für spe-zi-el-le B
au-stein als Co-Prozessoren
 []

[50] [51] [52] [53]) (zeichen.ltx [54]
Kapitel 6.
[55

] [56] [57]

LaTeX Warning: Reference `t:utf' on page 58 undefined on input line 146.

) (it.ltx [58]
Kapitel 7.
[59

] [60] [61] [62] (gnuplot/log.tex
\plotpoint=\box54
) [63] [64


] (gnuplot/h.tex) [65] [66


]
File: bilder/up.eps Graphic file (type eps)

<bilder/up.eps>
File: bilder/up.eps Graphic file (type eps)
 <bilder/up.eps>
File: bilder/up.eps Graphic file (type eps)
 <bilder/up.eps>
File: bilder/up.eps Graphic file (type eps)
 <bilder/up.eps>
File: bilder/up.eps Graphic file (type eps)

<bilder/up.eps>
File: bilder/down.eps Graphic file (type eps)
 <bilder/down.eps>
File: bilder/up.eps Graphic file (type eps)
 <bilder/up.eps>
File: bilder/down.eps Graphic file (type eps)
 <bilder/down.eps>
File: bilder/up.eps Graphic file (type eps)

<bilder/up.eps> [67] [68]
Overfull \hbox (19.01158pt too wide) in paragraph at lines 496--500
[]\T1/cmr/m/n/12 In vie-len Fäl-len tre-ten die Zei-chen nicht ver-ein-zelt auf
. So sind bei ei-nem Schwarzweiÿ-
 []

[69]
File: bilder/springer.eps Graphic file (type eps)
 <bilder/springer.eps>
File: bilder/PICT0004.eps Graphic file (type eps)
 <bilder/PICT0004.eps>
Underfull \hbox (badness 10000) in paragraph at lines 540--547

 []

) (cpu.ltx [70]
Kapitel 8.
[71

] (alu.pic) (alu_3r.pic) [72] (alu_2r.pic) [73] [74] (alu_2r_zu.pic)
[75] [76] [77] [78] [79]) (i8086.ltx [80]
Kapitel 9.

Overfull \hbox (7.65189pt too wide) in paragraph at lines 14--21
\T1/cmr/m/n/12 und Aus-füh-rung der Pro-gramm wird das Pro-gramm Emu8086 (www.e
mu8086.com)
 []

[81

] [82] [83] [84]
Underfull \hbox (badness 10000) in paragraph at lines 241--242

 []

[85] [86]
Underfull \hbox (badness 10000) in paragraph at lines 297--298

 []

[87]
Underfull \hbox (badness 10000) in paragraph at lines 341--342

 []


Underfull \hbox (badness 10000) in paragraph at lines 362--363

 []

[88] [89] [90]
Underfull \hbox (badness 10000) in paragraph at lines 498--499

 []


Underfull \hbox (badness 10000) in paragraph at lines 510--511

 []


Underfull \hbox (badness 10000) in paragraph at lines 528--529

 []

[91] [92]
Underfull \hbox (badness 10000) in paragraph at lines 609--610

 []

[93]
Underfull \hbox (badness 10000) in paragraph at lines 662--663

 []

[94]
Underfull \hbox (badness 10000) in paragraph at lines 715--716

 []


Underfull \hbox (badness 10000) in paragraph at lines 748--749

 []

[95]
Underfull \hbox (badness 10000) in paragraph at lines 763--764

 []


Overfull \hbox (26.3792pt too wide) in paragraph at lines 768--768
[]    \T1/cmtt/m/n/12 mov al,x[di]   ; Inhalt von (Adresse von x) + (Inhalt von
 DI) laden[] 
 []

[96]
Underfull \hbox (badness 4954) in paragraph at lines 820--820
[][]\T1/cmr/m/n/12 Hauptprogramm legt Rück-kehr-adres-se
 []

[97]
Underfull \hbox (badness 10000) in paragraph at lines 873--874

 []


Underfull \hbox (badness 10000) in paragraph at lines 898--899

 []

[98] [99]
Underfull \hbox (badness 10000) in paragraph at lines 965--966

 []


Underfull \hbox (badness 10000) in paragraph at lines 979--980

 []


Underfull \hbox (badness 10000) in paragraph at lines 990--991

 []


Overfull \hbox (1.68523pt too wide) in paragraph at lines 1000--1000
[][]\T1/cmtt/m/n/12 ; Interrupt 15 / AH=86h ist eine Wartefunktion. In den komb
inierten[] 
 []


Overfull \hbox (14.03221pt too wide) in paragraph at lines 1000--1000
[]\T1/cmtt/m/n/12 ; Registern CX und DX wird die Anzahl von Mikrosekunden spezi
fiziert.[] 
 []

[100] [101] [102] [103]
Overfull \hbox (0.47295pt too wide) in paragraph at lines 1159--1164
[][]\T1/cmr/m/it/12 In man-chen Assembler-Programmen fin-det man die An-wei-sun
g XOR
 []

) (schichten.ltx [104]
Kapitel 10.
[105

] [106] [107]) (optimierung.ltx [108]
Kapitel 11.
[109

] (ohne_dma.pic) (mit_dma.pic) [110] [111]
Overfull \hbox (5.93466pt too wide) in paragraph at lines 162--162
[]\T1/cmr/m/n/12 Ausführen| 
 []


Overfull \hbox (5.93466pt too wide) in paragraph at lines 162--162
[]\T1/cmr/m/n/12 Ausführen| 
 []


Overfull \hbox (0.98091pt too wide) in paragraph at lines 160--165
 [][] 
 []

[112]
Overfull \hbox (5.93466pt too wide) in paragraph at lines 185--185
[]\T1/cmr/m/n/12 Ausführen| 
 []


Overfull \hbox (5.93466pt too wide) in paragraph at lines 189--189
[]\T1/cmr/m/n/12 Ausführen| 
 []


Overfull \hbox (0.98091pt too wide) in paragraph at lines 183--192
 [][] 
 []

[113]
Overfull \hbox (1.07986pt too wide) in paragraph at lines 246--253
[]\T1/cmr/m/n/12 Mit zu-neh-men-der Ge-schwin-dig-keit mo-der-ner Pro-zes-so-re
n er-weist sich im-mer mehr
 []

(cache.pic) [114] [115] [116] [117] [118] [119]) (familien.ltx [120]
Kapitel 12.

Overfull \hbox (4.09554pt too wide) in paragraph at lines 18--21
[][]\T1/cmr/m/n/12 Arbeitsplatzrechner (Work-sta-ti-on): [][] an-spruchs-vol-le
 Ein-satz-ge-bie-te wie CAD,
 []

[121

]
Overfull \hbox (33.93427pt too wide) in paragraph at lines 58--62
[][]\T1/cmr/m/n/12 Pentium II: MMX-Befehlserweiterungen (\T1/cmr/m/it/12 Mul-ti
 Me-dia Ex-ten-si-on\T1/cmr/m/n/12 ) für Multimedia-
 []


Overfull \hbox (1.23949pt too wide) in paragraph at lines 58--62
\T1/cmr/m/n/12 Anwendungen: Gleich-zei-ti-ge Be-ar-bei-tung nach dem SIMD-Schem
a von meh-
 []

[122] (trans.tex)
Underfull \vbox (badness 1454) has occurred while \output is active []

 [123


])
(speicher.ltx [124]
Kapitel 13.

Underfull \hbox (badness 1275) in paragraph at lines 23--23
[][]\T1/cmr/m/n/12 Backup-Medien (Bän-
 []


Underfull \hbox (badness 10000) in paragraph at lines 24--24
[][]\T1/cmr/m/n/12 Wechselmedien (CD,
 []


Underfull \hbox (badness 5345) in paragraph at lines 24--24
\T1/cmr/m/n/12 Dis-ket-te, Flash-Card,
 []

[125

] [126] [127]
Overfull \hbox (4.90382pt too wide) in paragraph at lines 150--154
[][]\T1/cmr/m/n/12 Eine Wei-ter-ent-wick-lung mit noch hö-he-ren Über-
 []

(floppy.pic) [128]
Underfull \vbox (badness 6252) has occurred while \output is active []

 [129]
[130] [131] [132]) (../../netzwerke/skript/grundlagen.ltx [133] [134

]
Kapitel 14.
[135] (bits.pic) [136] [137] (roehre.pic) [138] [139] [140] [141] (topo_pp.pic)
(topo_stern.pic) (topo_baum.pic) [142] (topo_ring.pic) (topo_bus.pic) [143]
(herr_a.pic) [144] [145] [146] [147] [148] [149]
Overfull \hbox (20.69994pt too wide) in paragraph at lines 731--734
[]\T1/cmr/m/it/12 (Namen der Windows-Versionen). In-for-mie-ren Sie sich an Han
d der Hilfe-Funktionen
 []


Overfull \hbox (48.95421pt too wide) in paragraph at lines 761--763
[]\T1/cmr/m/it/12 Hinweis: Für einen bes-se-ren Ab-lauf soll-te der \T1/cmtt/m/
it/12 InputStream \T1/cmr/m/it/12 in einen \T1/cmtt/m/it/12 BufferedInputStream

 []

) (../../netzwerke/skript/r2r.ltx
\hoehevond=\skip117
 [150]
Kapitel 15.

Overfull \hbox (0.51608pt too wide) in paragraph at lines 17--25
[][]\T1/cmr/m/n/12 Bei ei-ner elek-tri-schen Lei-tung wer-den die bei-den Zu-st
än-de bei-spiels-wei-se durch
 []

(digitale_bits_01.pic) [151

] (digitale_bits_allg.pic)
Underfull \vbox (badness 6961) has occurred while \output is active []

 [152]
Overfull \hbox (12.77701pt too wide) in paragraph at lines 108--113
\T1/cmr/m/n/12 dann von Rah-men oder Fra-mes. Da-bei un-ter-schei-det man zwi-s
chen Byte-orientierten
 []

[153] [154]
Overfull \hbox (3.17517pt too wide) in paragraph at lines 225--230
\T1/cmr/m/n/12 zu ver-wech-seln-den In-for-ma-tio-nen wie Kon-to-num-mer, Kredi
tkarten-Nummern oder
 []

[155] [156] [157] [158]
Underfull \vbox (badness 7344) has occurred while \output is active []

 [159]
(arq_1.pic) (arq_2.pic) [160] (arq_3.pic) [161] (sliding_w.pic) [162] [163]
Overfull \hbox (15.4249pt too wide) in paragraph at lines 683--693
[][]\T1/cmr/m/it/12 Das nach-fol-gen-de C-Programm si-mu-liert einen Ka-nal mit
 Bit-Fehlern.
 []

[164] [165] [166]) (../../netzwerke/skript/lan.ltx [167] [168

]
Kapitel 16.

Overfull \hbox (17.82019pt too wide) in paragraph at lines 40--42
[]\T1/cmr/m/n/12 gebildet. So be-zeich-net 10BA-SE5 ei-ne Va-ri-an-te mit 10Mbi
t/s Basisband-Übertragung
 []

[169]
Underfull \hbox (badness 10000) in paragraph at lines 45--54

 []

[170] [171]
\tlmaximale=\skip118

Underfull \hbox (badness 10000) in paragraph at lines 197--197
[][]\T1/cmr/m/n/12 Dickes Ko-axi-al-ka-bel
 []


Underfull \hbox (badness 10000) in paragraph at lines 198--198
[][]\T1/cmr/m/n/12 Dünnes Ko-axi-al-ka-bel
 []


Underfull \hbox (badness 10000) in paragraph at lines 199--199
[]\T1/cmr/m/n/12 Punkt--zu--Punkt Ver-bin-
 []


Overfull \hbox (8.53691pt too wide) in paragraph at lines 194--202
 [][][] 
 []

[172]
Underfull \vbox (badness 10000) has occurred while \output is active []

 [173]
(topo_ring.pic) [174] [175] (wlan.pic) [176] [177] [178]
Overfull \hbox (16.42781pt too wide) in paragraph at lines 517--523
\T1/cmr/m/n/12 fi-gu-ra-tio-nen (z.B. Mono-Master, Multi-Master, Master-Slave).
 Ein Token-
 []


Overfull \hbox (1.1941pt too wide) in paragraph at lines 523--528
\T1/cmr/m/n/12 Viel-fach-zu-griffs-ver-fah-ren und Prio-ri-täts-re-geln. CAN wi
rd auch zur Ver-
 []


Overfull \hbox (2.84097pt too wide) in paragraph at lines 540--543
[][]\T1/cmr/m/n/12 Local Ope-ra-ting Net-work LON: auch LONWORKS[] ge-nannt ist
 eben-
 []

[179]) (../../netzwerke/skript/ip.ltx [180]
Kapitel 17.

Overfull \hbox (6.99525pt too wide) in paragraph at lines 24--32
[]\T1/cmr/m/n/12 Grundlage des In-ter-nets ist IP -- das In-ter-net Pro-to-koll
. IP bein-hal-tet die Adressver-
 []


Overfull \hbox (24.42413pt too wide) in paragraph at lines 36--41
\T1/cmr/m/n/12 man die Adres-sen als 4 durch Punk-te ge-trenn-te De-zi-mal-zah-
len, al-so z.B. 120.56.222.94,
 []

[181

] [182]
Overfull \hbox (34.34398pt too wide) in paragraph at lines 118--127
[][]\T1/cmr/m/n/12 Eine an-de-re Ver-fei-ne-rung des Adressraums er-reicht man 
durch Subnetz-Adressierung.
 []


Overfull \hbox (11.65497pt too wide) in paragraph at lines 138--142
[][]\T1/cmr/m/n/12 Der Netz-werk-teil ei-ner Adres-se lässt sich leicht durch b
it-wei-se UND-Verknüpfung
 []


Underfull \hbox (badness 10000) in paragraph at lines 138--142

 []

[183]
Underfull \hbox (badness 10000) in paragraph at lines 143--151

 []


Overfull \hbox (26.3792pt too wide) in paragraph at lines 188--188
[]  \T1/cmtt/m/n/12 Beschreibung. . . . . . . . . . . : Accton EN2242 Series Mi
niPCI Fast[] 
 []


Overfull \hbox (20.2057pt too wide) in paragraph at lines 188--188
[]  \T1/cmtt/m/n/12 Lease erhalten. . . . . . . . . . : Dienstag, 22. Juni 2004
 14:21:28[] 
 []


Overfull \hbox (20.2057pt too wide) in paragraph at lines 188--188
[]  \T1/cmtt/m/n/12 Lease läuft ab. . . . . . . . . . : Dienstag, 22. Juni 2004
 14:31:28[] 
 []


Underfull \vbox (badness 10000) has occurred while \output is active []

 [184]
[185] [186]
Overfull \hbox (0.1648pt too wide) in paragraph at lines 291--296
\T1/cmr/m/n/12 ei-ne Zu-ord-nungs-ta-bel-le mit IP-Adressen und Ethernet-Adress
en, die ARP-Tabelle
 []

[187]
Overfull \hbox (1.68523pt too wide) in paragraph at lines 370--370
[]    \T1/cmtt/m/n/12 Pakete: Gesendet = 4, Empfangen = 4, Verloren = 0 (0% Ver
lust),[] 
 []

[188] (netz_graph.pic) [189]
Overfull \hbox (8.6266pt too wide) in paragraph at lines 438--447
\T1/cmr/m/n/12 und ex-ter-nem (in-ter-do-main) Rou-ting. Die Vor-ge-hens-wei-se
 bei Intradomain-Routing
 []


LaTeX Warning: `h' float specifier changed to `ht'.

[190]

LaTeX Warning: `h' float specifier changed to `ht'.


LaTeX Warning: `h' float specifier changed to `ht'.

[191] [192]
Overfull \hbox (17.63689pt too wide) in paragraph at lines 602--609
\T1/cmr/m/n/12 ge-währ-lei-sten. Die An-sprü-che sind da-bei we-sent-lich ge-ri
n-ger als bei dem Intradomain-
 []

[193] [194]
Overfull \hbox (7.90596pt too wide) in paragraph at lines 691--709
[][]\T1/cmr/m/n/12 Technische The-men wer-den in spe-zi-el-len Grup-pen be-han-
delt. All-ge-mei-ne grund-
 []

[195]) (../../netzwerke/skript/tcp.ltx [196]
Kapitel 18.
[197

]

LaTeX Warning: Reference `cha_rpc' on page 198 undefined on input line 46.


Overfull \hbox (15.39038pt too wide) in paragraph at lines 44--47
\T1/cmr/m/n/12 über IP dar-stel-len. Im spä-te-ren Ka-pi-tel [] wird ein Bei-sp
iel für ein Anfrage/Antwort-
 []

[198] [199]
Overfull \hbox (22.3731pt too wide) in paragraph at lines 178--181
[][]\T1/cmr/m/n/12 Die An-wen-dung wünscht aus-drück-lich den so-for-ti-gen Ver
-sand (Push-Operation).
 []

[200] [201] [202] [203] (last.tex) [204] [205


])
(../../netzwerke/skript/anwendungen.ltx [206]
Kapitel 19.
[207

]
Overfull \hbox (2.006pt too wide) in paragraph at lines 72--76
\T1/cmr/m/n/12 spe-zi-fi-ziert. []Ein sol-cher URL ist []\T1/cmtt/m/n/12 http:/
/www.fh-friedberg.de/index.html\T1/cmr/m/n/12 . Der
 []


Overfull \hbox (9.371pt too wide) in paragraph at lines 77--78
[][]\T1/cmr/m/n/12 Der Cli-ent ex-tra-hiert aus dem URL den Kno-ten-na-men []\T
1/cmtt/m/n/12 www.fh-friedberg.de
 []

[208] [209] [210]
Overfull \hbox (26.93198pt too wide) in paragraph at lines 184--190
[][]\T1/cmr/m/n/12 Der zwei-te Teil hat bei HTTP die all-ge-mei-ne Form \T1/cmr
/m/it/12 //user:password@host:port/pfad\T1/cmr/m/n/12 .
 []

[211] [212]
Overfull \hbox (2.16974pt too wide) in paragraph at lines 301--308
[][]\T1/cmr/m/n/12 Aus Si-cher-heits-grün-den kön-nen JavaScript-Programme und 
Ja-va Ap-p-lets nicht
 []


Underfull \vbox (badness 10000) has occurred while \output is active []

 [213]
[214]
Overfull \hbox (14.03221pt too wide) in paragraph at lines 408--408
[]\T1/cmtt/m/n/12 553 sorry, that domain isn't in my list of allowed rcpthosts 
(#5.7.1)[] 
 []

[215]
Overfull \hbox (6.67274pt too wide) in paragraph at lines 458--460
[][]\T1/cmr/m/n/12 Definition von In-halt-s-ty-pen und -untertypen; Zwei Bei-sp
ie-le sind: []\T1/cmtt/m/n/12 image/gif\T1/cmr/m/n/12 ,
 []

[216] [217]
Overfull \hbox (74.02722pt too wide) in paragraph at lines 563--573
[]\T1/cmr/m/n/12 Newsgroups fin-det man über spe-zi-el-le Such-dien-ste wie z.B
. fin-do-lin (http://www.findolin.com/).
 []

[218] [219] [220] [221] [222] [223] [224]

LaTeX Warning: Reference `s_socket_ueb' on page 225 undefined on input line 901
.

) (../../netzwerke/skript/java.ltx [225] [226

]
Kapitel 20.
[227] [228]
Overfull \hbox (3.90143pt too wide) in paragraph at lines 131--136
[]\T1/cmr/m/n/12 Der be-schrie-ben Client-Socket ver-wen-det ei-ne stro-m-ori-e
n-tier-te Ver-bin-dung (TCP).
 []

[229] [230] [231] [232] [233] [234] [235] [236])
(../../netzwerke/skript/sicherheit.ltx [237] [238

]
Kapitel 21.
(firewall.pic) [239] [240] [241] [242] [243] [244] [245] [246]
(gnuplot/modulo.tex) [247


] [248] [249]

LaTeX Warning: Reference `c_rsa' on page 250 undefined on input line 560.


LaTeX Warning: Reference `c_rsa' on page 250 undefined on input line 566.

[250] [251]) (einheiten.ltx [252]
Anhang A.
) (aufgaben.ltx [253

] [254

]
Anhang B.
[255] [256] [257] [258] [259]) (loesungen.ltx [260]
Anhang C.

Overfull \hbox (8.80617pt too wide) in paragraph at lines 51--51
[]\T1/cmr/m/n/12 Alarm| 
 []


Overfull \hbox (8.80617pt too wide) in paragraph at lines 65--65
[]\T1/cmr/m/n/12 Alarm| 
 []


Underfull \vbox (badness 1142) has occurred while \output is active []

 [261

]
[262] [263] [264]
Underfull \hbox (badness 10000) in paragraph at lines 206--209

 []


Overfull \hbox (1.68523pt too wide) in paragraph at lines 221--221
[]    \T1/cmtt/m/n/12 mov ax,0b800h      ; zunaechst Segmentadresse fuer Daten 
setzen[] 
 []

[265]
Overfull \hbox (1.68523pt too wide) in paragraph at lines 293--293
[]     \T1/cmtt/m/n/12 db 0ffh,0ffh,0ffh        ; Markierung zur besseren Darst
ellung[] 
 []


Underfull \hbox (badness 10000) in paragraph at lines 296--298

 []

[266]) (glossar.ltx [267] [268

]
Anhang D.
[269] [270] [271]
Overfull \hbox (23.47856pt too wide) in paragraph at lines 120--121
[][]\T1/cmr/m/n/12 Maximum Seg-ment Si-ze. Die ma-xi-ma-le Grö-ÿe ei-nes TCP-Se
gments. 
 []

[272] [273] [274]
Overfull \hbox (1.40479pt too wide) in paragraph at lines 187--188
[][]\T1/cmr/m/n/12 Token Ro-ta-ti-on Ti-me. Die Um-lauf-zeit für den To-ken bei
 Token-
 []


Overfull \hbox (2.69327pt too wide) in paragraph at lines 201--202
[][]\T1/cmr/m/n/12 Virtual Chan-nel Iden-ti-fier. Ken-nung für vir-tu-el-len AT
M-Kanal. 
 []

[275]) (skript.bbl [276]
Underfull \hbox (badness 10000) in paragraph at lines 66--70
[][]\T1/cmr/m/n/12 Daniel Kar-ren-berg, Ge-rard Ross, Paul Wil-son, and
 []


Underfull \hbox (badness 10000) in paragraph at lines 66--70
\T1/cmr/m/n/12 Les-lie No-bi-le.  De-ve-lop-ment of the re-gio-nal in-ter-
 []


Underfull \hbox (badness 10000) in paragraph at lines 66--70
\T1/cmr/m/n/12 net re-gi-stry sy-stem.  \T1/cmr/m/it/12 The In-ter-net Pro-to-c
ol Jour-nal,
 []


Overfull \hbox (17.05637pt too wide) in paragraph at lines 66--70
[]\T1/cmtt/m/n/12 www.cisco.com/warp/public/759/ipj_4-4/ipj_4-4_regional.html\T
1/cmr/m/n/12 ,
 []

[277

] [278])) (skript.ind [279] [280

]
Overfull \hbox (8.57834pt too wide) in paragraph at lines 163--164
[][]\T1/cmr/m/n/12 Internet Con-trol Mes-sa-ge Pro-to-col, 188 
 []


Overfull \hbox (3.51848pt too wide) in paragraph at lines 164--165
[][]\T1/cmr/m/n/12 Internet Cor-po-ra-ti-on for As-si-gned Na-
 []

[281]
Overfull \hbox (0.61632pt too wide) in paragraph at lines 217--218
[][]\T1/cmr/m/n/12 Manufacturing Au-to-ma-ti-on Pro-to-col,
 []


Overfull \hbox (10.83185pt too wide) in paragraph at lines 230--231
[][]\T1/cmr/m/n/12 Monoalphabetisch Ver-schlüs-se-lung, 243 
 []

[282]
Overfull \hbox (0.55106pt too wide) in paragraph at lines 292--293
[][]\T1/cmr/m/n/12 Reverse Ad-dress Re-so-lu-ti-on Pro-to-col,
 []


Overfull \hbox (9.26567pt too wide) in paragraph at lines 372--373
[][]\T1/cmr/m/n/12 Verzögerung--Bandbreite--Produkt, 139 
 []

[283] [284

]) (skript.aux (gnuplot/log.aux) (gnuplot/h.aux) (trans.aux)
(last.aux) (gnuplot/modulo.aux))

LaTeX Warning: There were undefined references.


LaTeX Warning: There were multiply-defined labels.

 ) 
Here is how much of TeX's memory you used:
 4636 strings out of 95933
 48345 string characters out of 1195656
 196330 words of memory out of 1136394
 6863 multiletter control sequences out of 35000
 21897 words of font info for 51 fonts, out of 500000 for 1000
 14 hyphenation exceptions out of 607
 32i,15n,22p,259b,332s stack positions out of 1500i,500n,5000p,200000b,32768s

Output written on skript.dvi (296 pages, 1181208 bytes).