Kurs:Grundkurs Mathematik (Osnabrück 2018-2019)/Teil I/Vorlesung 15/latex
\setcounter{section}{15}
In dieser Vorlesung besprechen wir, wie sich im Dezimalsystem der Nachfolger, die Größergleichrelation und die Addition darstellen.
\zwischenueberschrift{Der Nachfolger und die Ordnung im Dezimalsystem}
Zuerst bemerken wir, dass das übliche Zählen \zusatzklammer {Einerstelle um $1$ erhöhen und eventuell mit den höheren Ziffern verarbeiten} {} {,} das wir auch in der fünften Vorlesung als eine Zählmöglichkeit erwähnt hatten, korrekt ist. Dies ist eine zwar einfache, aber dennoch durchzuführende Überlegung, da für uns eine Ziffernfolge nicht durch die Reihenfolge im Zählprozess festgelegt ist, sondern über die Interpretation als gemischte Darstellung mit Summen, Produkten und Potenzen.
\inputbemerkung
{}
{
Das Dezimalsystem im Sinne eines Zählsystems, das die
\definitionsverweis {Dedekind-Peano-Axiome}{}{}
erfüllt, hat erstmal nichts mit Summe, Produkt, Potenzen zu tun, sondern ist allein durch die folgende Struktur
\zusatzklammer {Menge mit Zählvorschrift} {} {}
gegeben. Die Elemente sind von der Form
\mathdisp {a_\ell a_{\ell-1} \ldots a_2 a_1 a_0} { , }
also einfach endliche geordnete Tupel von Ziffern
\zusatzklammer {Ziffernfolgen} {} {}
aus der Menge
\mathl{\{0,1,2,3,4,5,6,7,8,9\}}{.} Dabei ist $0$ das Startelement. Der Zählvorgang wird durch den folgenden dezimalen \stichwort {Zähl-Algorithmus} {} beschrieben.
\aufzaehlungdrei{Für einstellige Ziffern $\neq 9$ ist der Nachfolger gemäß der Reihenfolge
\mathl{\{0,1,2,3,4,5,6,7,8,9\}}{} festgelegt
\zusatzklammer {dies ist das \stichwort {kleine Einsnacheins} {}} {} {.}
}{Für beliebige Zahlen im Zehnersystem mit einer letzten Ziffer $\neq 9$ ist der Nachfolger diejenige Ziffernfolge, bei der die letzte Ziffer durch den Nachfolger ersetzt wird und alle anderen Ziffern unverändert übernommen werden.
}{Für beliebige Zahlen im Zehnersystem mit einer Neun als letzter Ziffer sind sämtliche zusammenhängenden Neunen von hinten durch Nullen zu ersetzen und die von hinten erste von $9$ verschiedene Ziffer durch ihren Nachfolger zu ersetzen, die übrigen Ziffern bleiben gleich
\zusatzklammer {wenn die Zahl ausschließlich aus Neunen besteht, ist dies so zu verstehen, dass man sich davor eine $0$ dazudenkt} {} {.}
}
}
\inputfaktbeweis
{Natürliche Zahl/Zehnersystem/Nachfolger/Fakt}
{Lemma}
{}
{
\faktsituation {Das Nachfolgernehmen im
\definitionsverweis {Dezimalsystem}{}{}
\zusatzklammer {gemischtes Dezimaldarstellungssystem} {} {}}
\faktfolgerung {stimmt mit dem Zählvorgang im Sinne von
Bemerkung 15.1
\zusatzklammer {Dezimalzählsystem} {} {}
überein.}
\faktzusatz {}
\faktzusatz {}
}
{
Wir gehen vom Dezimalsystem im Sinne einer gemischten Darstellung
\zusatzklammer {Stellenwertsystem} {} {}
aus und müssen zeigen, dass dort das Nachfolgernehmen, also die Addition mit $1$, die gleiche Wirkungsweise besitzt wie der Zählalgorithmus. Der Nachfolger einer im Dezimalsystem gegebenen natürlichen Zahl
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} {a_0+a_1 10+a_2 10^2 + \cdots + a_{\ell} 10^{\ell}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ist einfach
\mathdisp {{ \left( a_0+1 \right) } +a_1 10+a_2 10^2 + \cdots + a_{\ell} 10^{\ell}} { . }
Aus diesem Ausdruck lässt sich aber noch nicht unmittelbar die Dezimaldarstellung dieser Zahl ablesen, da der Einerkoeffizient nicht unbedingt $\leq 9$ sein muss. Wenn
\mavergleichskette
{\vergleichskette
{a_0
}
{ \leq }{8
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist, so ist
\mavergleichskettedisp
{\vergleichskette
{a_0+1
}
{ \leq} {9
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und die Dezimalentwicklung des Nachfolgers liegt unmittelbar vor. Wenn hingegen
\mavergleichskette
{\vergleichskette
{a_0
}
{ = }{9
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist, so geht es um die Zahl
\mavergleichskettealign
{\vergleichskettealign
{n+1
}
{ =} {(9+1) + a_1 10+a_2 10^2 + \cdots + a_{\ell} 10^{\ell}
}
{ =} { 10+ a_1 10+a_2 10^2 + \cdots + a_{\ell} 10^{\ell}
}
{ =} { (a_1+1) \cdot 10 +a_2 10^2 + \cdots + a_{\ell} 10^{\ell}
}
{ } {
}
}
{}
{}{.}
Erneut gilt, dass bei
\mavergleichskette
{\vergleichskette
{a_1
}
{ \leq }{8
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Dezimalentwicklung vorliegt, bei
\mavergleichskette
{\vergleichskette
{a_1
}
{ = }{9
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
muss man wie zuvor weitermachen. Wenn die hintersten
\zusatzklammer {niedrigststelligen} {} {}
$s$ Ziffern $a_0 , \ldots , a_{s-1}$ gleich $9$ sind und
\mavergleichskettedisp
{\vergleichskette
{a_s
}
{ \neq} {9
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
\zusatzklammer {was den Fall einschließt, dass $n$ genau $s$ Ziffern hat, in welchem Fall $a_s$ als $0$ zu interpretieren ist} {} {,}
so erhält man den Nachfolger, indem man diese $s$ Neunen durch Nullen ersetzt und $a_s$ um $1$ erhöht. Es liegt also die Wirkungsweise des Zählalgorithmus vor.
\inputfaktbeweis
{Natürliche Zahl/Zehnersystem/Potenzabschätzung/Fakt}
{Korollar}
{}
{
\faktsituation {Es sei
\mavergleichskette
{\vergleichskette
{ k
}
{ \in }{ \N_+
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}}
\faktvoraussetzung {Eine natürliche Zahl ist genau dann
\mathl{< 10^{k}}{,}}
\faktfolgerung {wenn sie im Zehnersystem aus maximal $k$ Ziffern besteht.}
\faktzusatz {}
\faktzusatz {}
}
{
Dies folgt aus Lemma 15.2, da es für den Zählprozess klar ist, dass längere Ziffernfolgen größer sind \zusatzklammer {im Zählprozess später dran kommen} {} {.}
\inputfaktbeweis
{Natürliche Zahl/Zehnersystem/Größenvergleich/Fakt}
{Korollar}
{}
{
\faktsituation {Es seien
\mavergleichskettedisp
{\vergleichskette
{m
}
{ =} {a_0+a_1 10+a_2 10^2 + \cdots + a_{k-1}10^{k-1}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} {b_0+b_1 10+b_2 10^2 + \cdots + b_{\ell-1}10^{\ell-1}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
zwei natürliche Zahlen im Zehnersystem
\zusatzklammer {also mit
\mavergleichskettek
{\vergleichskettek
{0
}
{ \leq }{ a_i,b_i
}
{ \leq }{9
}
{ }{
}
{ }{
}
}
{}{}{}} {} {.}}
\faktfolgerung {Dann ist
\mavergleichskettedisp
{\vergleichskette
{m
}
{ >} {n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
genau dann, wenn
\mavergleichskettedisp
{\vergleichskette
{k
}
{ >} { \ell
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
oder wenn
\mavergleichskette
{\vergleichskette
{k
}
{ = }{ \ell
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist und wenn es ein
\mathbed {s} {}
{0 \leq s < k} {}
{} {} {} {,}
derart gibt, dass
\mathdisp {a_{k-1}=b_{k-1} , \ldots , a_{s+1} = b_{s+1}, a_s> b_s} { }
ist.}
\faktzusatz {}
\faktzusatz {}
}
{
Dies folgt aus Lemma 15.2. Vom Zählprozess her ist es klar, dass längere Ziffernfolgen größer sind. Bei gleichlangen Ziffernfolgen und übereinstimmender Anfangssequenz entscheidet die nächste Ziffer, welche Zahl im Zählprozess später dran kommt.
\zwischenueberschrift{Schriftliches Addieren}
Da sich die Addition zweier natürlicher Zahlen aus den Dedekind-Peano-Axiomen ergibt, gibt es in jeder Beschreibung der natürlichen Zahlen genau eine Möglichkeit, zu addieren. Ob diese algorithmisch geschickt oder kompliziert ist, hängt wesentlich von der gewählten Beschreibung ab. Wenn man durch Strichfolgen gegebene Zahlen miteinander addiert, so hängt man einfach die beiden Strichfolgen aneinander. Dies ist auf den ersten Blick ein sehr einfacher Vorgang. Wenn man es aber ernsthaft schriftlich durchführen möchte, so sieht man, dass es extrem mühsam ist, da man jeden Strich der einen Strichfolge einzeln an die andere anhängen muss.
Das schriftliche Addieren zweier natürlicher Zahlen im Zehnersystem ist aus der Schule bekannt. Man schreibt die beiden Zahlen untereinander so, dass die Einerpositionen übereinander stehen und addiert dann die beiden passenden Ziffern
\zusatzklammer {im Sinne des kleinen Einundeins} {} {}
von hinten nach vorne. Wenn das Ergebnis kleiner als $10$ ist, schreibt man diese Zahl hin und rückt nach links. Wenn das Ergebnis größer oder gleich $10$ ist, so schreibt man die Einerziffer dieser Summe an der Stelle hin und hat in der links liegenden Stelle einen zusätzlichen Übertrag von $1$ mitzuberücksichtigen. Dies ist insgesamt ein rekursives Verfahren, das wir kurz festhalten.
\inputverfahren{}
{
Das schriftliche Addieren
\mathl{m+n}{} zweier natürlicher Zahlen, die im Dezimalsystem als
\mathdisp {m= a_0+a_1 10+a_2 10^2 + \cdots + a_{k}10^{k} \text{ und } n= b_0+b_1 10+b_2 10^2 + \cdots + b_{k}10^{k}} { }
gegeben sind
\zusatzklammer {wobei auch vordere Nullen erlaubt sind} {} {,}
funktioniert folgendermaßen. Man berechnet die Dezimalziffern\zusatzfussnote {In der üblichen schriftlichen Durchführung dieses Algorithmus wird diese Indizierung implizit durch die Stellung der Ziffern ausgedrückt} {.} {}
$c_i$ des Ergebnisses und die \stichwort {Überträge} {}
\mathl{d_{i+1}}{}
\zusatzklammer {mit dem Startwert
\mavergleichskettek
{\vergleichskettek
{d_0
}
{ = }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}} {} {}
sukzessive durch
\mavergleichskettedisp
{\vergleichskette
{c_i
}
{ =} { \begin{cases} a_i + b_i +d_i \, , \text{ falls } a_i + b_i +d_i < 10 \, , \\ a_i + b_i +d_i -10 \, , \text{ falls } a_i + b_i +d_i \geq 10 \, , \end{cases}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und\zusatzfussnote {Die Überträge werden mit dem Index derjenigen Stelle versehen, wo sie verarbeitet werden, nicht, wo sie entstehen} {.} {}
\mavergleichskettedisp
{\vergleichskette
{d_{i+1}
}
{ =} { \begin{cases} 0\, , \text{ falls } a_i + b_i +d_i < 10 \, ,\\ 1 \, , \text{ falls } a_i + b_i +d_i \geq 10 \, . \end{cases}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
Die Dezimaldarstellung der Summe
\mathl{m+n}{} ist
\mathl{c_{k+1} c_k \ldots c_2c_1c_0}{}
\zusatzklammer {wobei
\mavergleichskettek
{\vergleichskettek
{c_{k+1}
}
{ = }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
sein kann} {} {.}
Es gilt stets
\mavergleichskettedisp
{\vergleichskette
{ a_i +b_i+d_i
}
{ =} { d_{i+1} 10 +c_i
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}
Warum ist dieser Algorithmus richtig, warum liefert er das korrekte Ergebnis? Die Gewöhnung an dieses Verfahren verleitet dazu, diese Frage nicht ernst zu nehmen bzw. nicht zu verstehen. Das eben beschriebene schriftliche Addieren ist
\betonung{nicht}{} die Definition der Addition, sondern eine algorithmische Ausführung der Addition in einem bestimmten Beschreibungssystem
\zusatzklammer {nämlich dem Dezimalsystem} {} {}
für die natürlichen Zahlen.
Der Ausgangspunkt der Addition der natürlichen Zahlen liegt in der disjunkten Vereinigung von endlichen Mengen, wir haben die Addition über die Nachfolgerabbildung eingeführt und bereits
in Satz 8.14
gezeigt, dass sie mit dem Vereinigungskonzept übereinstimmt. Warum stimmt auch das schriftliche Addieren damit überein? Konkret: Man hat zwei Mengen
\mathkor {} {A} {und} {B} {}
an Äpfeln und bestimmt für beide Mengen ihre Anzahl im Zehnersystem: diese seien
\mathkor {} {m} {und} {n} {.}
Dann schüttet man die Mengen zusammen, erhält die Menge
\mavergleichskette
{\vergleichskette
{C
}
{ = }{A \cup B
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und bestimmt für diese Menge die Anzahl im Zehnersystem: diese sei $k$. Warum kommt, wenn man die Zahlen
\mathkor {} {m} {und} {n} {}
im Zehnersystem schriftlich addiert, ausgerechnet $k$ heraus?
Die beiden Zahlen seien als
\mathkor {} {m= a_r10^r + a_{r-1}10^{r-1} + \cdots + a_210^2+a_1 10 +a_0} {und} {n= b_s10^s + b_{s-1}10^{s-1} + \cdots + b_2 10^2+ b_1 10 +b_0} {}
gegeben, wobei die Ziffern alle zwischen
\mathkor {} {0} {und} {9} {}
seien. Es sei
\mavergleichskette
{\vergleichskette
{r
}
{ \geq }{s
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und wir können sogar annehmen, dass
\mavergleichskette
{\vergleichskette
{r
}
{ = }{s
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist, indem wir fehlende Ziffern in der zweiten Dezimalentwicklung durch Nullen auffüllen. Dann ist
\mavergleichskettedisphandlinks
{\vergleichskettedisphandlinks
{ { \left( a_r10^r + a_{r-1}10^{r-1} + \cdots + a_210^2+a_1 10 +a_0 \right) } + { \left( b_r10^r + b_{r-1}10^{r-1} + \cdots + b_2 10^2+ b_1 10 +b_0 \right) }
}
{ =} { { \left( a_r +b_r \right) } 10^r + { \left( a_{r-1} +b_{r-1} \right) } 10^{r-1} + \cdots + { \left( a_2+b_2 \right) } 10^2+ { \left( a_1 +b_1 \right) } 10 + { \left( a_0 +b_0 \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Dies beruht auf dem Assoziativgesetz der Addition und dem Distributivgesetz. Achtung! Dieses Ergebnis ist nicht in der Dezimaldarstellung, da die vor den Zehnerpotenzen $10^{i}$ stehenden Zahlen
\mathl{a_i+b_i}{} nicht unbedingt kleiner als $10$ sein müssen. Man kann an dieser Stelle
Bemerkung 14.5
anwenden und zu den \anfuehrung{größeren}{} Ziffern nach oben schaufeln. Dies ist aber nicht das Verfahren des schriftlichen Addierens.
\inputfaktbeweis
{Zehnersystem/Schriftliches Addieren/Korrekt/Fakt}
{Satz}
{}
{
\faktsituation {}
\faktfolgerung {Das schriftliche Addieren im Zehnersystem ist korrekt.}
\faktzusatz {}
\faktzusatz {}
}
{
Die beiden Zahlen seien
\mathdisp {m= a_0+a_1 10+a_2 10^2 + \cdots + a_{k}10^{k} \text{ und } n= b_0+b_1 10+b_2 10^2 + \cdots + b_{k}10^{k}} { , }
wobei wir eventuell auch vordere Nullen erlauben. Wir beweisen die Aussage durch Induktion über $k$. Bei
\mavergleichskette
{\vergleichskette
{k
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
handelt es sich um einstellige Zahlen und der Algorithmus ist korrekt. Hierzu macht man eine Fallunterscheidung abhängig davon, ob
\mavergleichskette
{\vergleichskette
{a_0 + b_0
}
{ < }{10
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist oder nicht. Es sei die Aussage nun für beliebige Zahlen, die beide maximal $k+1$ Ziffern haben, bewiesen, und seien zwei maximal $k+2$-stellige Zahlen gegeben. Es ist
\mavergleichskettealignhandlinks
{\vergleichskettealignhandlinks
{ m+n
}
{ =} { \sum_{ i = 0}^{k+1} a_i 10^{i} + \sum_{ i = 0}^{k+1} b_i 10^{i}
}
{ =} { a_{k+1} 10^{k+1} + \sum_{ i = 0}^{k} a_i 10^{i} + b_{k+1} 10^{k+1} + \sum_{ i = 0}^{k} b_i 10^{i}
}
{ =} { { \left( a_{k+1} + b_{k+1} \right) } 10^{k+1} + \underbrace{ \sum_{ i = 0}^{k} a_i 10^{i} }_{ = m'} + \underbrace{ \sum_{ i = 0}^{k} b_i 10^{i} }_{ = n'}
}
{ } {
}
}
{}
{}{.}
Es seien $c_i,d_i$ die durch den für
\mathkor {} {m} {und} {n} {}
in
Verfahren 15.5
beschriebenen Algorithmus festgelegten Zahlen. Die entsprechenden Zahlen für
\mathkor {} {m'} {und} {n'} {}
stimmen damit bis auf eventuell
\mathl{c_{k+1}, c_{k+2}, d_{k+2}}{} überein, da diese nur von den Ziffern bis einschließlich $a_k$ und $b_k$ abhängen. Für
\mathl{m' + n'}{} bezeichnen wir mit
\mathl{c_{k+1}'}{} die entsprechende Ziffer, und zwar ist
\mavergleichskette
{\vergleichskette
{c_{k+1}'
}
{ = }{ d_{k+1}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Nach Induktionsvoraussetzung ist die Summe der beiden hinteren Summanden gleich
\mathdisp {\sum_{ i = 0}^{k} c_i 10^{i} +c_{k+1}' 10^{k+1}} { . }
Die Gesamtsumme ist somit gleich
\mavergleichskettealignhandlinks
{\vergleichskettealignhandlinks
{m+n
}
{ =} { { \left( a_{k+1} + b_{k+1} \right) } 10^{k+1} +c_{k+1}' 10^{k+1} + \sum_{ i = 0}^{k} c_i 10^{i}
}
{ =} { { \left( a_{k+1} + b_{k+1} +c_{k+1}' \right) } 10^{k+1} + \sum_{ i = 0}^{k} c_i 10^{i}
}
{ =} { { \left( a_{k+1} + b_{k+1} + d_{k+1} \right) } 10^{k+1} + \sum_{ i = 0}^{k} c_i 10^{i}
}
{ =} { c_{k+2} 10^{k+2}+ c_{k+1} 10^{k+1} + \sum_{ i = 0}^{k} c_i 10^{i}
}
}
{
\vergleichskettefortsetzungalign
{ =} { \sum_{ i = 0}^{k+2} c_i 10^{i}
}
{ } {
}
{ } {}
{ } {}
}
{}{.}
\inputbeispiel{}
{
Wir erläutern den Induktionsschritt im Beweis zu
Satz 15.6
anhand eines Beispiels. Wir wollen
\mathl{62973+87515}{} berechnen. Im Beweis wird diese Rechnung mit der Rechnung
\mathl{2973+7515}{} in Bezug gesetzt, es wird also die vordere Ziffer weggelassen und die Wirkungsweise des Algorithmus für die beiden Zahlenpaare wird verglichen. Die hinteren Ziffern
\mathl{c_0,c_1,c_2,c_3}{} und die Überträge
\mathl{d_0,d_1,d_2,d_3,d_4}{} stimmen überein
\zusatzklammer {und deshalb werden sie in der Bezeichnung auch nicht unterschieden} {} {.}
Für die kürzere Rechnung ist
\mavergleichskette
{\vergleichskette
{c'_4
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{d'_5
}
{ = }{c'_5
}
{ = }{ 0
}
{ }{
}
{ }{
}
}
{}{}{}
\zusatzklammer {letztere Zahlen kommen gar nicht vor} {} {,}
für die längere Rechnung ist aber
\mavergleichskette
{\vergleichskette
{c_4
}
{ = }{ 5
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
\mavergleichskette
{\vergleichskette
{ d_5
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{c_5
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
Die Korrektheit des schriftlichen Addierens überträgt sich auf die Addition mehrerer Summanden in der Dezimaldarstellung. Man summiert wieder ziffernweise und schreibt die letzte Ziffer der Summe an der entsprechenden Stelle hin, ebenso den Übertrag. Dieser kann jetzt allerdings \zusatzklammer {ab zwölf Summanden} {} {} sogar größergleich $100$ sein, in diesem Fall muss man die Zehnerziffer wie zuvor um eins nach links schreiben und die Hunderterstelle um zwei nach links. Grundsätzlich kann man auch eine Summe mit beliebig vielen Summanden dadurch errechnen, dass man je zwei Summanden zusammenaddiert und somit die Anzahl der Summanden sukzessive verringert, doch ist das viel komplizierter.
\inputbemerkung
{}
{
Unter einem \stichwort {Algorithmus} {} versteht man ein durch bestimmte Regeln festgelegtes \zusatzklammer {deterministisches} {} {} Verfahren, mit dem man in endlich vielen Schritten zu einem Ergebnis kommt. Ein Algorithmus bezieht sich auf eine Menge von möglichen Eingaben \zusatzklammer {Input} {} {} und liefert eine Ausgabe, das Ergebnis \zusatzklammer {Output} {} {.} Ein Algorithmus berechnet den Wert einer Abbildung \zusatzklammer {einschließlich einer Verknüpfung} {} {,} überprüft, ob eine Relation zwischen Elementen vorliegt oder nicht, findet die Lösung zu einer Gleichung. Die Regeln sind präzise Handlungsanweisungen und müssen alle möglichen Fälle abdecken. Ein Algorithmus kann prinzipiell durch eine Maschine durchgeführt werden.
Im Grundkurs werden wir die folgenden Algorithmen behandelt: Schriftliches\zusatzfussnote {Es ist kein Zufall, dass man hier von schriftlich spricht, obwohl es für die Wirkungsweise der Verfahren selbst unerheblich ist, ob sie im Kopf, auf einem Papier oder in einer Maschine durchgeführt werden. Der explizite Einsatz eines Algorithmus lohnt sich erst dann, wenn die Aufgabe eine gewisse Komplexität besitzt, die ohne schriftliche Hilfsmittel das menschliche Speichervermögen übersteigt. Unter \stichwort {halbschriftlichem Rechnen} {} versteht man übrigens Verfahren, bei denen die Rechnungen zwar durch schriftliche Notizen unterstützt werden, aber ohne dass ein Algorithmus systematisch durchlauft wird} {.} {} Zählen\zusatzfussnote {Dieses Zählen kann man auch gut mündlich durchführen} {.} {} \zusatzklammer {Nachfolgernehmen} {} {,} schriftliches Vergleichen, schriftliches Addieren, schriftliches Multiplizieren, schriftliches Subtrahieren, schriftliches Dividieren \zusatzklammer {in einem Stellenwertsystem} {} {,} der euklidische Algorithmus zur Bestimmung des größten gemeinsamen Teilers, das Gaußsche Eliminationsverfahren zur Lösung linearer Gleichungssysteme, das Invertierungsverfahren für Matrizen, das Heron-Verfahren.
Folgende Punkte sind charakteristisch für einen Algorithmus. \aufzaehlungfuenf{Es gibt eine relativ kleine Zahl von Einzelschritten, auf die im Durchlauf des Algorithmus immer wieder Bezug genommen wird. }{Die Einzelschritte verwenden eine endliche Liste von gespeicherten elementaren Teilergebnissen \zusatzklammer {Datenbank} {} {.} }{Es muss irgendwie verbucht werden, auf welche Stelle sich der Einzelschritt bzw. dessen Ergebnis bezieht \zusatzklammer {Nummerierung, Indizierung, Anordnung} {} {.}
}{Die Einzelschritte verwenden Fallunterscheidung, entlang welcher sich das Verfahren verzweigt. }{Es werden Hilfszahlen zwischengespeichert und verwendet. } Beispielsweise werden im Additionsalgorithmus immer wieder zwei einstellige Zahlen miteinander addiert, dabei wird auf das kleine Einsundeins Bezug genommen und die Endziffer dieser Teilrechnung wird an der richtigen Stelle notiert. Die Weiterverarbeitung hängt davon ab, ob diese Einzelsummen kleiner als $10$ oder darüber sind, es werden Überträge notiert.
}
\inputbemerkung
{}
{
Von der Beschreibung eines Algorithmus, d.h. der präzisen Festlegung der einzelnen auszuführenden Rechenschritte, ist die Begrün\-dung für die Korrektheit des Algorithmus zu unterscheiden. Mit Korrektheit meint man, dass der Algorithmus wirklich das leistet, was er verspricht, also dass beispielsweise das schriftliche Additionsverfahren wirklich die beiden Zahlen addiert. Für diesen Nachweis braucht man einen mathematischen Beweis, der sowohl auf die zu berechnende mathematische Struktur \zusatzklammer {die Addition} {} {} als auch auf die Festlegungen des Algorithmus Bezug nimmt.
Ein wichtiger Aspekt bei vielen Algorithmen, der bei einem solchen Beweis hilft, ist ein \stichwort {Invarianzprinzip} {.} Bei einem Algorithmus werden typischerweise mehrere Zwischenergebnisse berechnet und weiterverarbeitet. Insbesondere bei rekursiven Definitionen und bei der maschinellen Durchführung werden Zwischenergebnisse auch überschrieben. Dennoch ist zu jedem Zeitpunkt des Ablaufes die volle Information in einer bestimmten Weise in den Zwischenergebnissen repräsentiert. Wenn man beipielsweise zwei zehnstellige Zahlen schriftlich addiert, und die hinteren fünf Endziffern der Summe und den letzten Übertrag schon berechnet hat, so kann man die hinteren Endziffern der Summanden vergessen. Die Information, was berechnet werden soll, steckt vollständig \zusatzklammer {invariant} {} {} in den vorderen Ziffern der Summanden, den hinteren Ziffern der Summe und dem einen Übertrag drin.
}