speichernausdrucken.tex

\section{Ein erstes C Programm}

Ein wichtiger Schritt hin zu einem Programm ist die Formulierung des
Verfahrens für die Lösung eines Problems als Algorithmus.
\begin{myblock}{Definition: Algorithmus}
Ein \textbf{Algorithmus} ist eine präzise Vorschrift, um aus vorgegebenen
Eingaben in endlich vielen Schritten eine bestimmte Ausgabe zu
ermitteln.
\end{myblock}

Hat man dies geschafft, so muss der Algorithmus in die jeweilige Programmiersprache, hier also C, umgesetzt werden.
Betrachten wir als Beispiel folgendes Problem:
Wir haben Daten $x_0, x_1,\ldots,x_{n-1}$ von einem Datentyp für den wir eine Operation größer-gleich (oder kleiner-gleich) und kleiner (größer) definiert haben.
Man beachte, dass wir ab jetzt bei der Indizierung der C Konvention folgen und von $0$ bis $n-1$ indizieren.
Die Aufgabe ist nun eine Permutation $\sigma(i)$, $i=0,...,n-1$ zu finden, so dass
\[
x_{\sigma(0)}\ \leq\ x_{\sigma(1)}\ \leq\ \ldots\ \leq\ x_{\sigma(n-1)}
\]
gilt.

Ein einfacher Algorithmus, um dieses Problem zu lösen heißt \emph{Einfügesortieren}.
Er kann in folgen Schritten formuliert werden:
\begin{enumerate}
\item Wir starten mit zwei Listen, eine sortierte S und eine unsortierte U\\
  Am Anfang besteht U aus der zu sortierenden Liste und S ist leer.
\item Nun verschieben wir jeweils das erste Element aus U nach S.
  Wir fügen das Element dabei so in S ein, dass S immer sortiert ist.
 \item Wir wiederholen 2. so oft, bis U leer ist.
\end{enumerate}
Wahrscheinlich ist jedem klar, dass diese Vorschrift in $n$ Schritten das gewünschte Ergebnis liefern wird.
Leider wird der Computer bzw. der C-Compiler den Algorithmus so nicht verstehen.
Deswegen werden wir den Algorithmus jetzt in C übersetzen.

\subsection{Daten- und Speichertypen}

Bevor wir die C-Datentypen vorstellen, ist es hilfreich zu verstehen, wie Daten auf einem Rechner gespeichert werden.
Speicher, egal ob Hauptspeicher oder Festplatte benutzt als kleinste Speicherzelle ein Element das entweder den Zustand 0 oder 1 annehmen kann.
Ein solches Element nennt man Bit.
Das heißt mit einem Bit kann man genau zwei Zustände darstellen.
Fasst man 8 Bits zu einem Byte zusammen, so kann man $2^8=256$ Zustände darstellen.
Größere Speicherbereiche nennt man
\begin{itemize}
\item Byte:  1~Byte, $2^{8 }$ Zustände
\item Word:  2~Byte, $2^{16}$ Zustände
\item Dword: 4~Byte, $2^{32}$ Zustände
\item Qword: 8~Byte, $2^{64}$ Zustände
\end{itemize}
Beispielsweise kann Text in einer Datei im ASCII Format gespeichert. 
Das bedeutet, dass jedes Zeichen genau ein Byte in Anspruch nimmt.
Damit kann aber im ASCII Format lediglich ein Zeichenumfang von $256$ Zeichen dargestellt werden.

Die verschiedenen Speichertypen haben zwei wichtigen Eigenschaften:
\begin{itemize}
\item Die totale Größe
\item Die Zugriffszeit
\end{itemize}
Typischerweise ist die Zugriffszeit länger, wenn die totale Größe des Speichermediums größer ist.
Zum Beispiel ist Hauptspeicher ungefähr $10.000$ mal schneller zu erreichen als eine Festplatte, aber 50 mal langsamer zu erreichen als die Register einer CPU.
Die Register bestehen aber nur aus wenigen Kilobytes, der Hauptspeicher aus einigen Gigabyte, und die Festplatte heutzutage aus einigen Terabyte.
Für uns ist hier aber lediglich der Unterschied Festplattenspeicher und Hauptspeicher von Bedeutung, da die Register vom Compiler angesteuert werden.

\subsection{Maschinenzahlen}

Auf einem Rechner ist lediglich eine Teilmenge $\mathcal{M}$ der
reellen Zahlen darstellbar. Nach IEEE Standard wird eine Fließkomma
Zahl wie folgt dargestellt:
\begin{equation}
x = \mathrm{sign}(x)\cdot a\cdot E^{e-k}
\end{equation}
wobei $E\in \mathbb{N}, E>1$ die Basis ist (meist $E=2$), $k\in
\mathbb{N}$ die 
Genauigkeit und $e$ im Exponentenbereich
$e_\mathrm{min}<e<e_\mathrm{max}$ liegt mit
$e_\mathrm{min},e_\mathrm{max}\in \mathbb{Z}$. Die Mantisse $a\in
\mathbb{N}_0$ ist 
definiert als
\begin{equation}
a = a_1 E^{k-1} + a_2 E^{k-2} + ... + a_k E^0\,,
\end{equation}
wobei $k$ die Mantissenlänge darstellt und $a_i$ die Ziffern im
entsprechenden Zahlensystem sind. Auf modernen Rechnern ist
üblicherweise $a_i\in\{0,1\}$ im Dualsystem mit Basis $E=2$.

Bei der Abbildung der reellen Zahlen auf die Menge der Maschinenzahlen
muss fast immer eine Rundungsoperation vorgenommen werden. Dabei geht
Information verloren, eine Rückabbildung ist nicht eindeutig möglich.

\begin{myexampleblock}{Zahlendarstellung}
  \begin{enumerate}
    \item Die Abbildung der Zahl $0{,}1$ im Dezimalsystem auf das
    Dualsystem $0{,}1_{10} = 0{,}0001\,1001\,1001\,1001\ldots_2$ ist ein unendlicher
    periodischer Dualbruch und damit mit endlicher Stellenzahl nicht
    exakt darstellbar.
  \item beim Addieren zweier $k$-stelliger Zahlen entsteht im
    Allgemeinen eine $k+1$ stellige Zahl. Überschreitet bei einem
    solchen Schritt $k+1$ die maximal verfügbare Stellenzahl, so kommt
    es zu einem sogenannten Überlauf (Englisch: \emph{overflow}), der
    zum Fehlschlagen eines Verfahrens führt.
  \end{enumerate}
\end{myexampleblock}
Als Maschinengenauigkeit bezeichnet man die größte reelle Zahl
$\delta_M$ für die der Rechner
\begin{equation}
1 + \delta_M = 1
\end{equation}
liefert. Für die Abbildung der reellen Zahlen auf Maschinenzahlen gilt
dann notwendigerweise
\begin{equation}
-\delta_M \leq \delta x\leq \delta_M\,.
\end{equation}


\subsection{C Quelltext für den Algorithmus Einfügesortieren}

Daten werden im C Quelltext durch sogenannte Variablen repräsentiert. 
Auf Variablen können wir Operation ausführen, oder sie an Funktionen übergeben.
Zunächst stellen wir jetzt vor, wie man Variablen deklariert, ihnen einen Wert zuweist und wie man sie beispielsweise auf dem Monitor ausgeben kann.
C kennt beispielsweise Datentypen für ganze Zahlen und für reelle Zahlen.
Beispiele sind \texttt{int} für ganze und \texttt{float} für reelle Zahlen.
Diese sind in verschiedenen Längen verfügbar.
Verschiedene Längen erlauben die Darstellung verschiedener Zahlenbereiche.

\subsubsection{Ein erstes C-Programm}

Ein C-Programm ist ein Stück Text, der entsprechend den Sprachregeln von C formuliert sein muss.
Es besteht im Allgemeinen aus Deklarationen, Anweisungen, Kontrollstrukturen und Kommentaren.
Das vielleicht einfachste C-Programm hat folgende Form:
\begin{lstlisting}{Ein erstes C-Programm}
int main()
{
  // dies ist ein Kommentar
  /*
    Dies ist ein mehrzeiliger Kommentar
  */
  return (0);
}
\end{lstlisting}
An Hand dieses einfachen Programms können wir schon einiges über die C Sprachregeln lernen.
Jedes Programm in C muss die Funktion \texttt{main} definieren. 
Die von uns gerade definiert Funktion \texttt{main} hat eine ganze Zahl (\texttt{int}) als Rückgabewert.
Da der geklammerte Bereich direkt nach \texttt{main} leer ist, bekommt die Funktion keine Parameter übergeben.
Schlüsselwörter, hier \texttt{int} und \texttt{main} werden durch ein oder mehrere Leerzeichen getrennt.
Mit den geschweiften Klammern wird ein Abschnitt oder Block definiert, in diesem Fall der Block der Funktion.
Die beiden Schrägstriche \texttt{//} lassen den Compiler alles danach folgende bis zum Zeilenende als Kommentar interpretieren.
Wir empfehlen, nicht die mehrzeiligen Kommentare \texttt{/* */} zu verwenden.
Der Grund dafür ist, dass wenn man einen mehrzeiligen Bereich auskommentiert, der schon einen mehrzeiligen Kommentar enthält, dann endet der Kommentarbereich beim ersten \texttt{*/}, und man bekommt eine Fehlermeldung.

Die Funktion \texttt{return} beendet die Abarbeitung der Funktion und gibt einen Wert an die aufrufende Funktion zurück.
Jede Funktion sollte immer explizit \texttt{return} aufrufen, auch wenn es keinen Rückgabewert gibt.
Jede Deklaration oder Anweisung, in diesem Fall der Aufruf von \texttt{return}, muss mit einem Semikolon \texttt{;} abgeschlossen werden.
Deklarationen oder Anweisungen sind nicht an Zeilen gebunden und können über mehrere Zeilen verteilt werden. 
Leere Zeilen werden vom Compiler nicht beachtet.
Groß- und Kleinschreibung sind wichtig, \texttt{Foo} und \texttt{foo} sind also unterschiedlich.
Da auch Leerzeichen am Zeilenanfang beliebig sind, werden Zeilen normalerweise eingerückt.
Das erhöht die Lesbarkeit des Quelltextes.
Gute Editoren stellen Einrückungs Schemas zur Verfügung.

Wie übersetzt man nun dieses Programm?
Wir zeigen dies hier beispielhaft für Linux und den GNU C Compiler \texttt{gcc}.
Angenommen, obiger Quelltext ist in einer Datei \texttt{main.c} im momentanen Arbeitsverzeichnis gespeichert.
Dann kann man die Datei mit folgendem Aufruf auf der Kommandozeile übersetzen:

\vspace*{0.5cm}
\begin{verb}
>$  gcc -std=c99 -Wall -pedantic main.c -o main.exe
\end{verb}
\vspace*{0.5cm}

\noindent Das in Maschinencode übersetzte Programm kann man dann mit

\vspace*{0.5cm}
\begin{verb}
>$  ./main.exe
\end{verb}
\vspace*{0.5cm}

\noindent von der Kommandozeile aus ausgeführt werden. 
In obigem Aufruf des GNU Compilers sind nicht alle Kommandozeilenparameter strickt notwendig.
Die Parameter \texttt{-Wall -pedantic} sorgen dafür, dass der Compiler möglichst viele Warnungen ausgibt und alle möglichen Probleme im Quelltext auch mitteilt.
Wir denken, dass es gerade für Anfänger sehr wichtig ist, Quelltext so sauber wie möglich zu schreiben.
Deshalb möchten wir dringend dazu auffordern, diese Compiler Parameter zu benutzen.
Der Parameter \texttt{-std=c99} sorgt dafür, dass der \texttt{gcc} den C99 Standard verwendet.
Aller Quelltext in diesem Dokument ist für diesen Standard geschrieben und übersetzt nicht für ältere Standards.

Eine Alternative zum \texttt{gcc} ist der \texttt{clang} Compiler.
Er hat einen ganz ähnlichen Aufruf

\vspace*{0.5cm}
\begin{verb}
>$  clang -std=c99 -Wall -pedantic main.c -o main.exe
\end{verb}
\vspace*{0.5cm}

\texttt{clang} und \texttt{gcc} sind beide freie Software.
Ihre Installation unter Linux ist sehr leicht, aber auch unter Windows kann man, mit einigem Aufwand, wenn man unbedingt möchte beide installieren.

Bisher tut unser erstes Programm noch nichts, außer Null zurückgeben. 
Wir können es um eine Ausgabe auf den Bildschirm erweitern:
\begin{lstlisting}{Programm Hallo Welt}
#include <stdio.h>

int main()
{
  // Ausgabe auf dem Bildschirm
  printf("Hallo Welt\n");
  return (0);
}
\end{lstlisting}
Es sind zwei Dinge dazugekommen:
Erstens haben wir eine sogenannte Header-Datei, in diesem Fall \texttt{stdio.h} eingebunden.
Das ist nötig, damit der C-Compiler die Funktion \texttt{printf} kennt.
Zweitens ist der Aufruf von \texttt{printf} hinzugekommen.
Die Funktion \texttt{printf} gibt in diesem Fall den String \glqq Hallo Welt\grqq\ auf dem Standard Ausgabegerät aus, was normalerweise die Kommandozeile selbst ist, wenn das Programm von der Kommandozeile aufgerufen wird. 
Wir werden die Funktion \texttt{printf} später noch im Detail diskutieren.
In diesem Beispiel kopiert \texttt{printf} die Zeichenkette unverändert zum standard output.
\verb|\n| erzeugt einen Zeilenumbruch.
Wieder wird der Aufruf von \texttt{printf} mit einem Semikolon \texttt{;} abgeschlossen.
Man beachte, dass \texttt{return} die Klammern um den Rückgabewert nicht benötigt, es ginge also auch \texttt{return 0;}.

Der Rückgabewert von \texttt{main} kann übrigens an der Kommandozeile wie folgt abgefragt werden

\vspace*{0.5cm}
\begin{verbatim}
>$  ./main.exe
>$  echo $?
0
\end{verbatim}
\vspace*{0.5cm}

Man kann der Funktion \texttt{main} auch Parameter übergeben.
Wie, werden wir später sehen.