ersteschritte.tex

\section{Ein erstes \texttt{C} Programm}

Ein wichtiger Schritt hin zu einem Programm ist die Formulierung des Verfahrens für die Lösung eines Problems als Algorithmus.\index{Algorithmus}
\begin{mydefinitionblock}{Definition: Algorithmus}
Ein \textbf{Algorithmus} ist eine präzise Vorschrift, um aus vorgegebenen
Eingaben in endlich vielen Schritten eine bestimmte Ausgabe zu
ermitteln.
\end{mydefinitionblock}
Hat man dies geschafft, so muss der Algorithmus in die jeweilige Programmiersprache, hier also \texttt{C}, umgesetzt werden.
Betrachten wir als Beispiel folgendes Problem:
Nehmen wir an wir betrachten Daten
\[
x_0, x_1,\ldots,x_{n-1}
\]
von einem bestimmten Datentyp, für den wir eine Operation größer-gleich (oder kleiner-gleich) und kleiner (oder größer) definiert haben.
Man beachte, dass wir ab jetzt bei der Indizierung der \texttt{C} Konvention folgen und von $0$ bis $n-1$ indizieren.
Die Aufgabe ist eine Permutation $\sigma(i)$, $i=0,...,n-1$ zu finden, so dass wir folgende \emph{sortierte} Liste 
\[
x_{\sigma(0)}\ \leq\ x_{\sigma(1)}\ \leq\ \ldots\ \leq\ x_{\sigma(n-1)}
\]
von Daten erhalten.

Ein einfacher Algorithmus, um dieses Problem zu lösen heißt \emph{Einfügesortieren}.\index{Algorithmus!Einfügesortieren}
Er kann in folgen Schritten formuliert werden:
\begin{enumerate}
\item Beginne mit zwei Listen, einer sortierten Liste $S$ und einer unsortierten $U$.\\
  Am Anfang besteht $U$ aus der zu sortierenden Liste und $S$ ist leer.
\item Verschiebe das jeweils erste Element aus $U$ nach $S$.
  Füge das Element dabei so in $S$ ein, dass $S$ immer sortiert ist.
 \item Wiederhole 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 \texttt{C}-Compiler den Algorithmus so nicht verstehen.
Deswegen werden wir den Algorithmus jetzt in \texttt{C} übersetzen.
Dafür führen wir zunächst Datentypen in \texttt{C} ein, damit wir die Liste $\{x_i\}$ auf dem Rechner darstellen können. 
Anschließend führen wir sogenannte Kontrollstrukturen ein, um obigen Algorithmus abbilden zu können.

\subsection{Daten- und Speichertypen}

Bevor wir \texttt{C}-Datentypen vorstellen, ist es hilfreich zu verstehen, wie Daten allgemeine 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\index{bit}\index{byte}\index{word}
\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 (\enquote{\emph{double-word}})
\item Qword: 8~Byte, $2^{64}$ Zustände (\enquote{\emph{quad-word}})
\end{itemize}
Beispielsweise kann Text in einer Datei im ASCII Format gespeichert werden. \index{ASCII Format}
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 invers proportional zur totalen Größe des Speichermediums.
Zum Beispiel ist Hauptspeicher ungefähr $10.000$ mal schneller zu erreichen, als eine Festplatte, aber 50 mal langsamer 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 im Normalfall 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ßkommazahl wie folgt dargestellt:\index{Fließkommazahl}
\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\index{Mantisse}
\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{myalertblock}{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 numerischer Verfahren führen kann. Dies ist jedoch
    hauptsächlich bei ganzzahligen Datentypen von Relevanz.
  \item die bei der Fließkommadarstellung inhärente Rundung führt dazu, dass 
    ein gegebener Algorithmus Ergebnisse nur bis zu einer bestimmten Genauigkeit
    berechnen kann. Man spricht hierbei von \emph{Rundungsfehlern}.
    Es ist Vorsicht geboten: bei manchen numerischen Verfahren kann dies dazu führen,
    dass unzureichend genaue oder gar völlig falsche Ergebnisse berechnet werden.
    
  \end{enumerate}
\end{myalertblock}
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}
wobei $\delta x$ den Zahlenbereich angibt, der zu $0$ ausgewertet wird.

\subsection{\texttt{C} Quelltext}

Daten werden im \texttt{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.
\texttt{C} kennt 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 Größen verfügbar, also mit verschiedener Anzahl an bits.
Verschiedene bit-Anzahl erlaubt die Darstellung verschiedener Zahlenbereiche.

\subsubsection{Ein erstes \texttt{C}-Programm}

Ein \texttt{C}-Programm ist ein Textstück, das entsprechend den Sprachregeln von \texttt{C} formuliert sein muss.
Es besteht im Allgemeinen aus Deklarationen, Anweisungen, Kontrollstrukturen und Kommentaren.
Das vielleicht einfachste \texttt{C}-Programm hat folgende Form:
\begin{lstlisting}[caption={Ein erstes \texttt{C}-Programm}, belowcaptionskip=0.3em]
int main()
{
  // dies ist ein Kommentar
  /*
    Dies ist ein mehrzeiliger Kommentar
  */
  return 0; // Rueckgabe 0
}
\end{lstlisting}
An Hand dieses einfachen Programms können wir schon einiges über die \texttt{C} Sprachregeln lernen.
Jedes Programm in \texttt{C} muss die Funktion \texttt{main} genau einmal definieren. 
Die \texttt{main} Funktion ist auch der Startpunkt für jedes \texttt{C} Programm.
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 voneinander 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 \texttt{main} und gibt einen Wert an die aufrufende Funktion zurück.
Jede Funktion sollte (muss aber nicht) 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 Schemata zur Verfügung.

Soweit die Erklärung für das erste Programm.
Wie übersetzt man nun dieses Programm?
Mit Übersetzen bezeichnet man den Schritt, in dem der \texttt{C} Quelltext in sogenannten Maschinentext übersetzt wird.
Maschinentext kann dann direkt von einem Rechner interpretiert werden.
Wir zeigen das Übersetzen beispielhaft für Linux und den GNU \texttt{C} Compiler \texttt{gcc}.\index{\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 Maschinentext ü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 strikt 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 notwendigerweise für ältere Standards.

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

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

\noindent\texttt{clang} und \texttt{gcc} sind beide freie Software.
Ihre Installation unter Linux ist sehr leicht, aber auch unter Windows kann man beide -- mit einigem Aufwand -- ebenfalls installieren.

Bisher tut unser erstes Programm noch nichts, außer Null zurückgeben. 
Wir können es um eine Ausgabe auf den Bildschirm erweitern:

% minipage to avoid page break in this short bit of code
\begin{minipage}{\linewidth}
\begin{lstlisting}[caption={Programm Hallo Welt}, belowcaptionskip=0.3em]
#include <stdio.h>

int main()
{
  // Ausgabe auf dem Bildschirm
  printf("Hallo Welt\n");
  return 0;
}
\end{lstlisting}
\end{minipage}

Es sind zwei Dinge dazugekommen:
Erstens haben wir eine sogenannte Header-Datei, in diesem Fall \texttt{stdio.h} eingebunden.\index{\texttt{stdio.h}}
Das ist nötig, damit der \texttt{C}-Compiler die Funktion \texttt{printf} kennt.\index{\texttt{printf}}
Denn \texttt{printf} ist nicht Teil der \texttt{C} Sprache, es ist in einer sogenannten Bibliothek definiert. 
Mit der Einbindung der Header-Datei wird die Funktion dem Compiler bekannt gemacht.
Dies werden wir später noch genauer erörtern.

Zweitens ist der Aufruf von \texttt{printf} (\emph{print formatted}) hinzugekommen.
Die Funktion \texttt{printf} gibt in diesem Fall die Zeichenkette (den \emph{string}) \enquote{Hallo Welt} auf dem Standard Ausgabegerät aus, was normalerweise die Kommandozeile selbst ist, wenn das Programm von der Kommandozeile aufgerufen wird. 
Auch die Funktion \texttt{printf} werden wir später noch im Detail diskutieren.
In diesem Beispiel kopiert \texttt{printf} die Zeichenkette unverändert zur standard Ausgabe, also wahrscheinlich auf die Konsole.
\verb|\n| erzeugt einen Zeilenumbruch.
Wieder wird der Aufruf von \texttt{printf} mit einem Semikolon \texttt{;} abgeschlossen.
Man beachte, dass \texttt{return} keine Klammern um den Rückgabewert benötigt.
\texttt{return} stellt keinen Funktionsaufruf dar.


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

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

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