Algorithmische Mathematik I · Algorithmische Mathematik I 22. Januar 2018 (14:19) 1 Mathematische Grundlagen 1.1 Mathematische Grundbegri e Wir werden die folgenden Begri e benutzen:

Algorithmische Mathematik I

Gennadiy Averkov

IMO | FMA | OvGU Magdeburg

22. Januar 2018

A[1]

A[2]

A[4] A[5]

A[3]

A[6] A[7]

1

Algorithmische Mathematik I 22. Januar 2018 (14:19)

Inhaltsverzeichnis

1 Mathematische Grundlagen 5

1.1 Mathematische Grundbegriffe . . . . . . . . . . . . . . . . . . . . . . 5

1.2 Summen und Produkte . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.3 Pradikate und Quantoren . . . . . . . . . . . . . . . . . . . . . . . . 6

1.4 Widerspruchsbeweis . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.5 Vollstandige Induktion . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.6 Asymptotische Notation . . . . . . . . . . . . . . . . . . . . . . . . . 7

2 Grundlagen zu Algorithmen und Programmierung 8

2.1 Stellenwertsysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.2 Rechenprobleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.3 Einige Grundkonzepte imperativer Programmierung . . . . . . . . . 11

2.4 Prozeduren, Parameterubergabe und Rekursion . . . . . . . . . . . . 12

2.5 Konstruktion neuer Datentypen . . . . . . . . . . . . . . . . . . . . . 14

2.6 Random Access Machine . . . . . . . . . . . . . . . . . . . . . . . . . 15

3 Sortierproblem 16

3.1 Sortieren durch Einfugen . . . . . . . . . . . . . . . . . . . . . . . . . 16

3.2 Sortieren durch Mischen . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.3 Die Datenstruktur Heap und der Heap-Sort . . . . . . . . . . . . . . 24

3.4 Prioritatsschlangen auf der Basis von Heaps . . . . . . . . . . . . . . 30

3.5 Untere Schranken an die Laufzeit von Sortieralgorithmen . . . . . . 32

3.6 Countingsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3.7 RadixSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

3.8 QuickSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

4 Verkettete Datenstrukturen 38

4.1 Stack, Schlange und Deque als Arrays . . . . . . . . . . . . . . . . . 38

4.2 Stack und Schlange als einfach verkettete Listen . . . . . . . . . . . 39

4.3 Deque als eine doppelt verkette Liste . . . . . . . . . . . . . . . . . . 40

4.4 Zeiger-basierte binare Baume . . . . . . . . . . . . . . . . . . . . . . 41

5 Berechnungen mit reellen Zahlen 41

5.1 Darstellung reeller Zahlen in einem Stellenwertsystem . . . . . . . . 41

5.2 Rundungsfehler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

2


5.3 Fehler der Gleitkommazahlenarithmetik . . . . . . . . . . . . . . . . 42

5.4 Verfahrensfehler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

5.5 Datenfehler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

5.6 Modellierungsfehler . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

3


Einleitung

Organisation: Schein fur 50 % der Ubungsaufgaben (2er Gruppen) und Program-mierprojekt (3er Gruppen). In der Vorlesung: Theorie. In den Ubungen: Diskussionder Aufgaben + Einfuhrung in C++ (fur absolute Anfanger, nur Basics).

Die in der Vorlesung formulierten Aufgaben konnen entweder in den Ubungsblatterndran kommen oder als Aufgaben zum Selbstlernen benutzt werden.

In dem Kurs geht es um die Algorithmen und Mathematik.

Mogliches Muster:

Problem/Objekt aus der Praxis → mathematisches Modell → mathematischeTheorie dazu → Algorithmische Theorie.

Beispiel dazu: Euklidische Steiner-Baume. Im Fall von drei Ecken eines gleichseitigenDreiecks. Im Fall von vier Ecken eines Quadrats. Eigenschaften der Steiner-Punkte.Wie konsturiert man die Euklidische Steinerbaume.

Ein weiteres Beispiel: Bestimmung der Kusszahl. Eine mathematische Aufgabe. Un-tere Schranken in konkretem Dimensions konnen unter anderem mit Hilfe des Com-puters ausgerechnet werden. Somit beweist man Theoreme mit Hilfe vom Computer.Hier benutzt man Algorithmen/Computer als Hilfsmittel zur Losung mathemati-scher Probleme (wird immer ofter gemacht). Heutzutage hat fast jede mathemati-sche Theorie eine algorithmische ‘Ecke’. In vielen Theorien spielen die Algorithmeneine zentrale Rolle (Numerik, Optimierung, Algebra, Graphentheorie usw. usw.).

4


1 Mathematische Grundlagen

1.1 Mathematische Grundbegriffe

Wir werden die folgenden Begriffe benutzen: Aussage, Menge, Abbildung, Tupel, Re-lation und die zugehorigen Operationen und Standardbezeichnungen. Das alles wirdauch in den anderen Kursen (lineare Algebra und Analysis) ausfuhrlich diskutiert.Falls man im Laufe der Vorlesung Fragen dazu hat, bitte melden!

Inklusion von Mengen wird in diesem Kurs als ⊆ (in manchen Quellen verwendetman auch ⊂).

Sei X eine Menge. Dann ist die Potenzmenge von X die Menge aller Teilmengenvon X. Bezeichnung: 2X , Formal: 2X := A : A ⊆ X, Anmerkung: hat X genau nElemente, so hat 2X genau 2n Elemente (wird spater genauer diskutiert).

Zahlenmengen:

N := 1, 2, 3, . . .

N0 := 0, 1, 2, . . .

Z := 0, 1,−1, 2,−2, . . .

Q := pq : p ∈ Z, q ∈ N

R reelle Zahlen

In der Mathematik verwendet steht := fur ‘wird definiert als’. D.h., links steht einneues Symbol bzw. eine neue Bezeichnung und rechts die Bedeutung davon.

N ⊆ N0 ⊆ Z ⊆ Q ⊆ R ⊆ C

In manchen Quellen wird N als N = 0, 1, 2, . . . definiert.

1.2 Summen und Produkte

Die Anzahl der Elemente in einer Menge X (Kardinalitat von X genannt) wird als|X| bezeichnet. Man setzt die Kardinalitat von ∅ gleich 0.

Sei X eine nichtleere endliche Menge. Dann kann X als X = x1, . . . , xn dargestelltwerden mit xi 6= xj ⇔ i 6= j fur alle i, j ∈ 1, . . . , n.Fur eine Abbildung f : X → R definiert man

•∑x∈X

f(x) := f(x1) + . . .+ f(xn)

•∏x∈X

f(x) := f(x1) · . . . · f(xn)

Im Fall X = ∅ definiert man fur f : X → R und∑x∈X

f(x) = 0 und∏x∈X

f(x) = 1.∑,∏

sind wohldefiniert (ohne Beweis).

5


1.3 Pradikate und Quantoren

Sei X Menge. Dann heißt P : X → falsch,wahr Pradikat auf X. Etwa P : N →falsch,wahr, P (k) :=

”k(k + 1) ist durch 3 teilbar fur alle k ∈ N”.

Durch ein Pradikat P : X → falsch,wahr kann man die Menge x ∈ X : P (x)definieren.

∀ x ∈ X : P (x) fur ein Pradikat P auf eine Menge X steht fur die Aussage”die

Bedingung P (x) gilt fur alle x ∈ X“. ∀ heißt das Allgemeinheitsquantor (Bedeutung:fur ∀lle).

∃ x ∈ X : P (x) bezeichnet die Aussage”die Bedingung P (x) gilt fur ein x ∈ X“. ∃

heißt Existenzquantor (Bedeutung: es ∃xistiert).

1.4 Widerspruchsbeweis

Wir wollen nun ein paar nutzliche Beweistechniken diskutieren. Eine davon ist derWiderspruchsbeweis. Am besten lasst sich der Beweis an einem Beispiel diskutieren.

Wir zeigen durch einen Widerspruch, dass unendliche viele Primzahlen gibt. An-genommen, die Anzahl der Primzahlen ware endlich. Seien dann p1, . . . , pn mitn ∈ N alle Primzahlen (mit p1 = 2, p2 = 3, p4 = 5 usw. ). Wir betrachten die Zahlk = 1 +

∏ni=1 pi. Die Zahl k besitzt eine Primfaktorzerlegung und daher auch einen

Primfaktor p. Da p1, . . . , pn alle Primzahlen sind, ist p = pj fur ein j ∈ 1, . . . , n.Die Zahl pj teilt k nach der Konstruktion und sie teilt auch das Produkt

∏ni=1 pi, weil

pj in diesem Produkt vorkommt. Somit teilt pj auch die Differenz k −∏n

i=1 pi = 1.Dies ist ein Widerspruch, weil 1 keine Teiler außer sich selbst besitzt.

1.5 Vollstandige Induktion

Vollstandige Induktion ist eine weitere Beweistechnik, die sehr oft in der diskretenund algorithmischen Mathematik verwendet wird.

Sei P ein Pradikat auf N. Dann sind die folgenden Bedingungen aquivalent:

(i) P (n) gilt fur alle n ∈ N.

(ii) P (1) gilt, und fur alle n ∈ N gilt: P (n)⇒ P (n+ 1).

Es gibt mehrere offensichtliche Variationen zu dieser Aquivalenz. Verifizierung vonP (1) heißt Induktionsanfang, Verifizierung der Implikation P (n) ⇒ P (n + 1) heißtInduktionsschritt.

Beispiel 1.1. Als Beispiel, zeigen wir

n∑i=1

i =n(n+ 1)

2(1.1)

fur alle n ∈ N. Die Formel (1.1) ist wahr fur n = 1, denn links so wie rechts hatman in diesem Fall die eins.

6


Sei n ∈ N eine Zahl, fur welche (1.1) wahr ist (Diese Annahme nennt man dieInduktionsvoraussetzung). Nun zeigen wir, dass (1.1) mit n+ 1 an der Stelle von ngilt. Man hat

n+1∑i=1

i = n+ 1 +n∑

i=1

iInd.V or.

= n+ 1 +n(n+ 1)

2=

(n+ 1)(n+ 2)

2

Nach der Induktionsvoraussetzung gilt 1 + · · ·+ (n+ 1) = (1 + · · ·+ n) + (n+ 1) =n(n+1)

2 + (n+ 1). Durch das Ausklammern von n+ 1 erhalten wir n(n+1)2 + n+ 1 =

(n+1)(n+2)2 .

Mit Hilfe der vollstandigen Induktion kann man neben den Gleichungen auch Un-gleichungen und auch verschiedene andere Aussagen beweisen.

Aufgabe 1.2. In der Analysis werden Sie zeigen, dass fur alle x1, . . . , xk ≥ 0 (k ∈N) die Ungleichung (

k∏i=1

xi

)1/k

≤ 1

k

k∑i=1

xi

erfullt ist. Die linke Seite heißt das geometrische Mittel und die rechte Seite dasarithmetische Mittel. Zeigen Sie diese Ungleichung, im Fall, dass k eine Zweierpo-tenz k = 2n (n ∈ N), mit Hilfe der vollstandigen Induktion uber n.

Aufgabe 1.3. Sei X endliche Menge und sei

2X := Y : Y ⊆ X .

Zeigen Sie |2X | = 2|X| durch Induktion uber |X|. Hinweis: in diesem Fall kann mandie Induktion mit |X| = 0 beginnen.

1.6 Asymptotische Notation

Bei der Analyse von Algorithmen redet man oft von der Großenordnung von Funk-tionen. Daher verwendet man sehr gerne die sogenannte asymptotische Notation.Seien f, g : N→ R Funktionen.

Man schreibt f(n) = O(g(n)), fur n → ∞, wenn eine Konstante c > 0 und einn0 ∈ N existiert derart, dass |f(n)| ≤ c|g(n)| fur alle n ≥ n0 gilt. Die Bezeich-nung f(n) = O(g(n)) steht fur f(n) hat die Großenordnung hochstens g(n) bisauf eine mutliplikative Konstante. Die Schreibweise f(n) = O(g(n)) ist streng ge-nommen nicht ganz korrekt, in der Literatur aber sehr verbreitet. Die KorrekteSchrebweise ware f(n) ∈ O(g(n)) (d.h., f(n) ist liegt in der Menge aller Funktionender Großenordnung hochstens O(g(n))). In der Literatur verwendet man namlichoft O(g(n)) als eine Schreibweise fur eine anonyme Funktion der Großenordnunghochstens g(n). In diesem Kurs spielen die Betrage in der Definition von O(g(n)) inder Regel keine Rolle, weil man fast ausschließlich nichnegative Funktionen disku-tiert.

Man schreibt f(n) = Ω(g(n)), fur n → ∞, wenn eine konstante c > 0 und einn0 ∈ N existieren derart, dass |f(n)| ≥ c|g(n)| fur alle n ≥ n0 gilt. In diesem Fall:Großenordnung mindestens g(n), bis auf multiplikative Konstanten.

7


Man schreibt f(n) = Θ(g(n)) wenn f(n) = O(g(n)) und f(n) = Ω(g(n)) gilt (also:Großenordnung genau g(n) bis auf multiplikativen Konstanten).

Beispiel 1.4. Sei f(n) :=√

2n+ 5−10. Man hat f(n) = Θ(√n), fur n→∞, denn

einerseits hat man√

2n+ 5−10 ≤√

2n+ 5 ≤√

7n =√

7√n fur alle n ∈ N, woraus

f(n) = O(√n) folgt. Andererseits hat man

√2n+ 5− 10 ≥

√n− 10 ≥ 1

2

√n fur alle

n ≥ 400, woraus f(n) = Ω(√n) folgt.

Aufgabe 1.5. Sind die folgenden asymptotischen Abschatzungen richtig: n! = O(nn),nn = Ω(n!), n! = O(2n), nn = O(n!)?

2 Grundlagen zu Algorithmen und Programmierung

2.1 Stellenwertsysteme

Im Computer werden alle Daten mit 0 und 1 dargestellt. Es ist klar, dass manalle Daten mit ganzen Zahlen darstellen kann (denn man kann Symbole mit ganzenZahlen nummerieren). Um als zu verstehen, wie man die Daten mit 0 und 1 darstellt,muss vor allem geklart werden, wie man die ganzen Zahlen mit 0 und 1 darstellt.Dafur werden wir die Stellenwertsysteme einfuhren.

In der Informatik benutzt man meistens die Stellenwertsystem zu den Basen b ∈2, 8, 10, 16

Aufgabe 2.1. Zeigen Sie Folgendes. Sei b ∈ N, b ≥ 2. Dann besitzt jede Zahl z ∈ Z,≥ 0 eine eindeutige Darstellung als

z =k∑

i=0

zibi (2.1)

mit k ∈ N0 und zi ∈ 0, . . . , b− 1 und zk 6= 0 fur z 6= 0.

Die Zahlen z0, . . . , zk heißen die Stellen von z im Stellenwertsystem zur Basis b, undwir schreiben in diesem Fall

zk · · · z0 (zur Basis b) = z.

Hier heißt z0 die niedrigste Stelle und zk die hochste Stelle. Die Zahl z heißt k-stellige Zahl im Stellenwertsystem zur Basis b. Bei negativen ganzen Zahlen geht dieDarstellung zur Basis b genau so (mit Vorzeichen).

Beispiel 2.2. Schriftliche Addition, Subtratktion, Multiplikation und Division zueiner beliebigen Basis b geht genau wie zur Basis b = 10. Etwa

Addition zur Basis 2:

1 0 1+ 1 1

1 0 0 0

Bemerkung 2.3. Konvertierung von Basis b zur Basis 10. Direkt nach (2.1) oderdas sogenannte Horner-Schema, das einem ermoglicht, die Anzahl der Multiplika-tionen zu sparen: Fur k = 2,

z2b2 + z1b+ z0 = b(bz2 + z1) + z0,

8


fur k = 3z3b

3 + z2b2 + z1b+ z0 = b (b (bz3 + z2)︸︷︷︸

1. Runde

+z1)

︸︷︷︸2. Runde

+z0.

︸︷︷︸3. Runde

usw.

Beispiel 2.4. Die Konvertierung von der Basis 10 zu einer anderen Basis gehtdurch die iterative Division mit Rest. Konvertieren wir die Zahl 46 in das Systemzur Basis 3. Man hat

46 = 15 · 3 + 1 = (5 · 3 + 0) · 3 + 1 = 5 · 32 + 0 · 3 + 1

= (1 · 3 + 2) · 32 + 0 · 3 + 1

= 1 · 33 + 2 · 32 + 0 · 31 + 1 · 30

Das heißt:46 (zur Basis 10) = 1201 (zur Basis 3).

Beispiel 2.5. Die Basis 10 benutzen Menschen, die Basis 2 die Computer, und dieBasis 16 die Menschen, die maschinennah mit Computern arbeiten. Die Konvertie-rung zwischen der Basis 2 und der Basis 16 einfach ist, weil 16 eine Potenz von2 ist. Die Basis 16 ermoglicht aber eine kompaktere Darstellung von Zahlen. DieZiffern des 16er System (auch Hexadezimal-System genannt) sind die 16 Symbo-le 0, . . . , 9, A,B,C,D,E, F . Wir konnen diese Ziffern als Zahlen im Dezimalsystemoder Binarsystem darstellen:

Hexadezimal Dezimal Binar0 0 00001 1 00012 2 00103 3 00114 4 01005 5 01016 6 01107 7 01118 8 10009 9 1001A 10 1010B 11 1011C 12 1100D 13 1101E 14 1110F 15 1111

Hier ist A zur Basis 16 gleich der 10 zur unserer Standardbasis 10, usw. und F zurBasis 16 ist gleich der 15 zur Basis 10. Die Zahl BEE im Hexadezimal-System kannins Binarsystem konvertiert werden, indem man jede Ziffer durch ihre Binardarstellungersetzt.

BEE (im Hexadezimalsystem) = 1011 1110 1110(im Binarsystem).

9


Um sich zu vergewissern, dass das tatsachlich stimmt, kann man sich uberlegen, wasdiese Gleichheit im Dezimalsystem bedeutet:

(23 + 21 + 20)︸︷︷︸B

162 + (23 + 22 + 21)︸︷︷︸E

161 + (23 + 22 + 21)︸︷︷︸E

160

=211 + 29 + 28 + 27 + 26 + 25 + 23 + 22 + 21

Um zu sehen, wie man im Computer Daten mit 0 und 1 darstellt kann unter Linuxden hexdump-Befehl benutzen:

echo "aaabbbb" | hexdump -C

Ausgabe:

00000000 61 61 61 62 62 62 62 0a |aaabbbb.|

00000008

Hier ist 61 die hexadecimale Unicode-Kodierung des Buchstaben a, 62 die hexa-dezimale Unicode-Kodierung des Buchstaben b und 0a die hexadezimale Unicode-Kodierung von ‘neue Zeile’.

Aufgabe 2.6. Bei rationalen Zahlen, geht die Berechnung der Dezimaldarstellungzur Basis b genau so wie im Dezimalsystem. Berechnen Sie die Dezimaldarstellungvon 1/2, 1/3, 1/4, 1/5 und 1/6 im Binarsystem.

Bemerkung 2.7. Wenn man im Computer nicht-negative ganze Zahlen in einem n-Bit-Register speichert, so gehen im Fall eines arithmetischen Uberlaufs die hoherenStellen verloren. Zum Beispiel gilt

11111110 + 00000010 = 100000000

zur Basis 2. (Im Dezimalsystem: 254 + 2 = 256). Wenn man diese Berechnung ineinem 8-Bit-Register ausfuhrt ist das Resultat gleich 0. D.h. in einem n-bit Registerwerden die arithmetischen Operationen modulo 2n durchgefuhrt.

2.2 Rechenprobleme

Die Rechenprobleme sind Eingabe-Ruckgabe-Relationen. Etwa beschreit die Relation(a, p) ∈ N2 : p ist Primfaktor von a

.

zwischen zwei naturlichen Zahlen das Rechenproblem ‘bestimme einen Primfaktorder gegebenen naturlichen Zahl’. Das zugrundeliegende Rechenproblem algorith-misch zu losen heißt, einen Algorithmus zu entwickeln, der zu jeder moglichenEingabe eine passende Ruckgabe bestimmt oder feststellt, dass es keine passendeRuckgabe existiert.

In unserem Beispiel ist fur die Eingabe a = 10, die Zahl p = 2 eine passendeRuckgabe. Die Zahl p = 5 passt auch, denn 5 ist ebenfalls ein Primfaktor von 10.Fur a = 1 hat man keine passende Ruckgabe: so musste in der Losungsalgorithmusmit einer Meldung terminieren, dass es keine passende Ruckgabe gibt.

10


Die Berechnung einer Abbildung/Funktion f : X → Y ist ein Spezialfall. In diesemFall ist f(x) die eindeutige Ruckgabe fur die Eingabe x ∈ X. Zum Beispiel konnenwir das Problem der der Potenz als die Funktion f : N2 → N mit f(a, p) := ap. MitWorten: fur gegebene a, p ∈ N soll ap algorithmisch berechnet werden.

Ein weiterer Spezialfall ist die Uberprufung einer Eigenschaft. Solche Probleme nenntman Entscheidungsprobleme. Sie konnen als Berechnung einer Funktion f : X →0, 1 interpretiert werden. Etwa: f : N→ 0, 1mit f(n) = 1, wenn n eine Primzahlist, und f(n) = 0 sonst. Mit Worten: es soll uberpruft werden, ob eine gegebenenaturliche Zahl n eine Primzahl ist.

2.3 Einige Grundkonzepte imperativer Programmierung

Um die Programmierung unabhangig von einer konkreten Programmiersprache zudiskutieren, benutzten wir den sogenannten Pseudocode. Pseudocode ist eine Co-deskizze, die ein wie ein Computerprogramm aussieht, in der man aber auch beiBedarf Worte benutzen kann. Mit Pseudocode kann man Algorithmen beschreiben,ohne auf die technischen Details der Programmierung einzugehen.

Eine Programm-Variable ist ein Behalter fur Werte bzw. Daten. Der Wert der Varia-blen kann durch eine Zuweisung festgelegt werden. Man betrachte z.B. die folgendenzwei Zeilen.

1: x := 52: x := 2 · x+ 4

Hier wird in der ersten Zeile einer Variablen x der Wert 5 zugewiesen. Als := Be-zeichnen wir in unserem Pseudocode die Zuweisung. In der zweiten Zeile wird derVariablen x ein neuer Wert zugewiesen, wobei man sich bei der Zuweisung in derrechten Seite auf den aktuellen Wert bezieht.

Um mit die Variablen und Daten zu bearbeiten benutzt man die Kontrollbefehle wieif-then, if-then-else (Verzweigung) und while and for (Schleifen).

Hier ein Code, der die Werte der Variablen x und y vertauscht, wenn am Anfangx > y gilt:

1: if x > y :2: t := x3: x := y4: y := t5: end

D.h. die drei Zuweisungen werden genau dann ausgefuhrt wenn beim Erreichen derZeile 1 des Codes die Bedingung x > y gilt. Die Variable t ist eine Zusatzvariable,die beim Vertauschen benutzt wird.

If-then-else ist analog aufgebaut. Im else-Teil stehen die Befehle, die ausgefuhrtwerden, wenn die gegebene Bedingung nicht erfullt ist.

Ein Array A der Lange n ist eine Liste aus n Variablen, wobei die Variablen mit auf-einanderfolgenden ganzen Zahlen indexiert sind. In den allermeisten meisten Spra-chen einschließlich C und C++ werden die Arrays ab 0 indexiert. Bei Indexierung

11


ab 1 (die wir im Pseudocode dieser Vorlesung benutzen) ist ein Array A der Langen aus den Variablen A[1], . . . , A[n] zusammengesetzt, auf welche man durch die An-gabe des Index i zugreifen kann. Die Variable A[i] heißt die i-te Komponente, oderdas i-te Element des Arrays A. Die Anzahl der Komponente eines Arrays A wird alsLange[A] bezeichnet.

Wir illustrieren einen andere Kontrollstruktur, die for-Schleife, indem wir zeigen,wie man damit die Summe aller Elemente eines n-elementigen Arrays bestimmenkann.

1: s := 02: for i := 1, . . . ,Lange[A] :3: S := S +A[i]4: end

Eine while-Schleife ist eine Kontrollestruktur die aus dem Rumpf und der Bedingungder Schleife besteht, wobei die Befehle des Rumpfs der Schleife iterativ ausgefuhrtwerden, solange die Bedingung der Schleife erfullt ist. In der while-Schliefe stehtdie Bedingung vor dem Rumpf. In manchen Programmiersprachen hat man auchschleifen, bei denen die Bedingung nach dem Rumpf steht (repeat-until -Schleifen).

Hier ein Beispiel, wie man die Komponenten ein Array mit Hilfe einer while-Schleifeumkehren kann:

1: i := 12: j := Lange[A]3: while i < j :4: A[i] und A[j] vertauschen5: i := i+ 1 B Zum nachsten i6: j := j − 1 B Zum nachsten j7: end

2.4 Prozeduren, Parameterubergabe und Rekursion

Prozedur (Funktion, Unterprogramm) ist ein Code innerhalb eines Programms miteigener Eingabe.

Stellen wir uns vor, wir mussen zur Losung einer Rechenaufgabe immer wiedertesten, ob x ∈ [p, q] fur gegebene p, q, x ∈ Z gilt. In diesem Fall lohnt es sich,eine sogenannte Prozedur anzulegen, welche genau diesen Test durchfuhrt. (AndereNamen: Programm-Funktion, Unterprogramm):

b = Ist-zwischen(x, p, q)

if p ≤ x ≤ q oder q ≤ x ≤ q :b = Wahr

endb = Falsch

Die Variablen x, p, q heißen Eingabeparameter der Prozedur und die Variable b istdie Ruckgabe-Variable. In vielen modernen Programmiersprachen benutzt man fur

12


die Ruckgabe keinen Variablennamen sondern den Befehl return. Das sieht dann soaus:

Ist-zwischen(x, p, q)

if p ≤ x ≤ q oder q ≤ x ≤ q :return Wahr

endreturn Falsch

Durch ein return wird die Prozedur mit dem vorgegeben Wert beendet.

Man kann auch Prozeduren ohne Ruckgabe betrachten. In C++ sind es die Funk-tionen mit dem Ruckgabetyp void.

In manchen Sprachen (wie z.B. in C++) stehen mehrere Arten der Parameterubergabezur Verfugung, wie z.B. Ubergabe durch Kopie und die Ubergabe durch Referenz.Wenn z.B. im vorigen Pseudocode x, p und q durch Kopie ubergeben werden, so ent-stehen bei jedem Aufruf der Prozedur die drei Variablen x, p und q, welche dann ent-sprechend initialisiert werden. Etwa, bei der Ausfuhrung von Ist-zwischen(a, b, c)mit x = a, y = b, z = c.

Bei der Ubergabe durch Referenz, ist der Eingabeparameter lediglich ein weitererName fur eine Variable, die bereits existiert. Ich illustriere das am Bespiel vomVertauschen:

void vertauschen ( i n t& x , i n t& y ) i n t t=x ;x=y ;y=t ;

i n t main ( )

i n t a=2,b=3;vertauschen ( a , b ) ;r e turn 0 ;

Damit die Werte a und b in der main-Funktion vertauscht werden, mussen die Ein-gabeparameter x und y Referenzvariablen sein. In diesem Fall sind x und y zweiteNamen fur a bzw. b. Die Variable t ist eine lokale Variable der Funktion vertau-schen. Sie entsteht bei jeder Ausfuhrung von vertauschen und verschwindet nachder Terminierung dieser Funktion.

13


p := Potenz(a, n)

if n = 0 :p := 1

else if n gerade :q := Potenz(a, n/2)p := q2

else:q := Potenz(a, (n− 1)/2)p := pq2.

end

Diese rekursive Umsetzung ist in vielen Situationen besser als die nicht-rekursiveiterative Umsetzung mit O(n) Iterationen.

Es kann uberpruft werden, dass alles was man rekursiv umsetzt auch ohne Rekursion,etwa mit Schleifen und Arrays, umsetzen kann. Dies gilt auch fUr das Potenzierenoben. Die rekursiven Umsetzungen sind aber manchmal leichter zu verstehen bzw.eleganter.

Prozeduren, die sich selbst aufrufen, heißen rekursive. Hier ein Beispiel einer Proze-dur, welche an fur a ∈ Z und n ∈ N0 ausrechnet.

2.5 Konstruktion neuer Datentypen

Zur Konstruktion neuer/eigener Datentypen stehen in hoheren Programmierspra-chen verschiedene Mittel und Bibliotheken zur Verfugung. Wir diskutieren hier keineAbstraktionsmechanismen (wie OOP oder Templates), sondern mehr die Maschine-nebene.

Was man verwenden kann ist: Arrays/Listen, Strukturen und Zeiger.

Strings sind z.B. im wesentlichen Listen von Zeichen. Genau so konnen auch Filesals Listen von Zeichen interpretiert werden.

Strukturen ermoglichen Daten verschiedener Datentypen in einem ‘Packchen’ zuvereinigen. Zum Beispiel. Ein Datentype auto kann durch Modell, Kennzeichen, Ki-lometerstand, und andere sogenannte Attribute definiert werden. Ein farbiger Punktauf der Ebene durch drei Attribute, x-Komponente, y-Komponente und Farbe. Usw.

Zeiger sind Adresse-Variablen. D.h., eine Zeiger-Variable speichert die Adresse einesOrts (einer anderen Variablen) in Speicher. Zeiger konnen in verschiedenster Situa-tionen benutzt werden (insb. um verkettete Datenstrukturen zu implementieren).Fur Zeiger hat man zwei Grundoperationen: Adresse von einem Objekt, und Ob-jekt unter gegebener Adresse. In vielen Programmiersprachen haben die komplexenObjekte das Zeigerverhalten (etwa, Arrays in Python).

Im folgenden werden wir Algorithmen mit Pseudocode beschreiben (‘unverbindli-cher Code’, selbsterklarend). Unsere Vereinbarung: bei Parameterubergabe werdenArrays durch Referenz ubergeben, einfache Datentypen durch Kopie).

14


2.6 Random Access Machine

Random Access Machine (kurz RAM ), oder auf deutsch, Maschine mit wahlfreiemZugriff, wird unsere Idealisierung des realen Rechners sein. Die Analyse und Ent-wicklung von Algorithmen in diesem Kurs wird im Rahmen der RAM durchgefuhrt.

Wir nehmen an, die Zellen unserer Maschine konnen ganze Zahlen beliebiger Großespeichern (d.h. die Bit-Große der Speicherzellen ist unendlich). Die Speichergroße(d.h,. die Anzahl der Speicherzellen) ist ebenfalls unbeschrankt (d.h., unendlich).Wir konnen alle anderen Datentypen auf der Basis der ganzen Zahlen umsetzen.

genannt. Wir brauchen eine mathematische Abstraktion fur einen realen Rechner.Dies ist die Random Access Machine. Sie kann rein formal eingefuhrt werden. Ichfinde es besser, wenn wir zunachst eine etwas informelle Beschreibung benutzen,durch welche wir festlegen welche Datentypen, Operationen und Kontrollstrukturenfur uns elementar sind.

Als Grundoperationen erlauben wir

• Zuweisung (fur ganzzahligen Datentyp),

• Addition von ganzzahligen Variablen,

• Multiplikation einer ganzzahligen Variablen mit einer Konstante,

• Ganzzahlige Division einer ganzzahligen Variablen durch eine Konstante,

• Zugriff zu Speicherzellen durch Index,

• Vergleichsoperationen <,≤,=,≥, > 0,

• Kontrollstrukturen if-then-else, while, for.

Unsere Algorithmen werden als Pseudocode formuliert und ihre Analyse wird imRahmen dieses Modells durchgefuhrt. Fur Pseudocode legen wir fest, dass stan-dardmaßig in Prozeduren alle einfachen Datentypen durch Kopie und alle komplexenDatentypen (Arrays usw.) durch Referenz ubergeben werden.

Wir lassen Multiplikation von zwei ganzzahligen Variablen ist in unserem Modellkeine Grundoperationen. Denn, wenn das eine Grundoperationen ware, so hatte derfolgende Psuedocode die Laufzeit O(n):

x := 2for i = 1, . . . , n :x := x2

end

Der Pseudocode wurde als 22n in der Zeit O(n) berechnen. Die Zahl 22n hat 2n + 1Binarstellen. Wir wurden also eine Zahl exponentieller Bitgroße in linearer Zeit be-rechnen. Weil das zu unrealistisch ist, schließen wir Multiplikation beliebiger ganzerZahlen als Grundoperation aus.

15


3 Sortierproblem

Das Sortierproblem ist das Problem, in einem gegebenen Array A einer beliebigenLange n ∈ N0, die Komponenten so zu vertauschen, dass nach dem Vertauschendie Bedingung A[1] ≤ . . . ≤ A[n] erfullt ist. Wir argumentieren auf Arrays mitganzzahligen Komponenten. Die prasentierten Algorithmen konnen aber auch furArrays mit allgemeineren Inhalten verwendet werden.

3.1 Sortieren durch Einfugen

Wir beginnen mit dem Sortieren durch Einfugen (engl. Insertion Sort). Ist A einArray der Lange n, so konnen wir Auch Teilarrays A[i . . j] von fur 1 ≤ i ≤ j ≤ nbetrachten. Das Teilarray A[i . . j] ist das Teil von A mit den Komponenten A[k] furi ≤ k ≤ j.Die Idee von Sortieren durch Einfugen ist ein sortiertes Teilarray iterativ wachsenzu lassen:

· · · · · ·︸︷︷︸schon sortiert

· · · · · ·︸︷︷︸nicht bearbeitet

einfugen−−−−−→ · · · · · ·︸︷︷︸sortiert

· · · · · ·︸︷︷︸nicht bearbeitet

Das (eine der Komponenten des nichtsortierten Teilarrays) wird in das bereitssortierte Teil solange aufgenommen bis das nicht bearbeitete Teil leer wird.

Wir wissen also, wie die außere Schleife aussieht:

Sortieren-durch-Einfugen(A)

for i = 2, . . . ,Lange[A] :B A[1 . . i− 1] schon sortiertB TODO: A[1 . . i] sortieren

end

Hier eine schematische Darstellung:

· · · · · ·︸︷︷︸schon sortiert

i · · · · · ·︸︷︷︸nicht bearbeitet

Nun konnen wir das eigentliche Einfugen in der inneren Schleife umsetzen:

16


Sortieren-durch-Einfugen(A)

1: for i := 2, . . . ,Lange[A] :2: B A[1 . . i− 1] ist sortiert3: x := A[i] B wird eingefugt4: j := i B A[j] ‘frei’5: B Schleife: Steht links vor freien Position was großeres als x?6: while j > 1 und A[j − 1] > x :7: B Wir andern die freie Position (wie bei 15-Puzzle)8: A[j] := A[j − 1]9: j := j − 1

10: end11: A[j] := x B Position fur x gefunden12: end

Eine schematische Darstellung:

· · ·︸︷︷︸≤x

· · · · · ·︸︷︷︸>x

noch nichtverschoben

j

· · ·i︸︷︷︸

>xschon

verschoben

· · · · · ·︸︷︷︸noch nichtbearbeitet

Bemerkung 3.1. Die und-Operation in der While-Schleife ist in den Program-miersprachen in der regele eine sogenannte trage Operation. In diesem Fall heißtes: ist j > 1 nicht erfullt, so kennt man, dass der Ausdruck als Falsch ausgewertetwird. In diesem Fall wird A[j − 1] > x nicht ausgewertet. Wenn man bei j ≤ 1, dieOperation A[j−1] > x auswerten wurde, so hatte (je nach der Programmiersprache)einen Laufzeitfehler.

Bemerkung 3.2. Sortieren durch Einfugen terminiert. In der inneren Schleife wirdj in jeder Iteration verkleinert, sodass jede Ausfuhrung der Inneren schleife end-lich viele Iterationen macht.Die außere Schleife macht offensichtlich nicht mehr lasLange[A] Iterationen.

Theorem 3.3 (Korrektheit des Sortierens durch Einfugen). Sortieren durch Einfugenlost das Sortierproblem.

Beweis. Bei den Arrays A der Lange hochstens 1, macht die außere Schleife keineeinzige Iteration, sodass A gar nicht verandert wird. Der Algorithmus arbeitet alsokorrekt auf Arrays der Lange hochstens 1.

Hat A eine großere Lange, so gilt in der ersten Iteration (mit i = 2) offensichtlichdie Bedingung, dass A[1 . . i− 1] sortiert ist. Das heißt, wenn am Ende der außerenSchleife das Teilarray A[1 . . i] sortiert wird, so funktioniert das gesamte Verfahrenkorrekt. Denn so behalt man wahrend der gesamten Ausfuhrung die Bedingung,dass A[1 . . i − 1] zur Beginn der außeren Schleife sortiert ist, sodass am Ende derAusfuhrung das gesamte Array sortiert wird.

Es bleibt zu zeigen, dass jede Iteration der außeren Schleife das Array A[1. .i] sortiert.Das Element A[i] wird in der Variablen x aufgehoben, sodass A[i] uberschriebenwerden kann. Die innere Schleife ist so aufgebaut, dass man das Teilarray vonA[1. .i−

17


1] aus den Elementen, die echt großer als x sind iterativ um eine Position nach rechtsverschiebt (mit dem rechten Element beginnend). Die Bedingung, dass die PositionA[j] ‘frei’ ist, Beim Beginn jeder Iteration der inneren Schleife ist die KomponenteA[j] ‘frei’, das heißt, wenn man das aufgehobene Element x in A[j] kopieren wurde,enthielte das Array A alle seinen ursprunglichen Elemente.

Eine Aussage, die an einer Stelle des Algorithmus immer erfullt ist, heißt Invariante.Insbesondere Spricht man von Schleifeninvarianten.

Die Laufzeit ist die Anzahl der Elementaroperationen/Grundoperationen (vgl. unse-re Definition der Random Access Machine), die ein Algorithmus bei der Ausfuhrungauf einer gegebenen Eingabe durchfuhrt.

Die Worst-Case-Laufzeit ist die maximale Laufzeit auf einer gegebenen Menge derEingaben.

Der Speicheraufwand ist die Anzahl der Speicherzellen, die ein Algorithmus nebender Speicherung der Eingabe zusatzlich benotigt (beachte, unsere Random AccessMachine hatte den ganzzahligen Datentype als Grundlage)

Theorem 3.4 (Zur Effizienz des Sortierens durch Einfugen). Die Worst-Case-Laufzeit des Sortierens durch Einfugen auf Arrays der Lange n ist Θ(n2). Der Spei-cheraufwand ist Θ(1).

Beweis. Der Speicheraufwand ist offensichtlich Θ(1), da man lediglich drei zusatzlicheVariablen i, j und x benutzt.

Wir zeigen, dass die Laufzeit auf jedem Array der Lange n ≥ 1 hochstens quadratischist. Zur Ausfuhrung einer Iteration der außeren Schleife braucht man hochstens cnElementaroperationen fur eine Konstante c > 0 (da die innere Schleife nicht mehrals n Iterationen macht). Die außere Schleife macht nicht mehr als n Iterationen,sodass die Gesamtlaufzeit aller Iteration nicht hoher als cn2 ist. Es folgt, dass dieLaufzeit des Sortierens durch Einfugen auf eine Array der Lange n gleich O(n2) ist.

Es bleibt zu zeigen, dass die Laufzeit auf manchen Arrays der Lange n gleich Ω(n2)ist. Angenommen, n ≥ 1 und A ist ein absteigend sortiertes Array mit n unterschied-lichen Elementen, etwa A = [n, . . . , 1]. Dann macht fur jedes i ∈ 2, . . . , n die innereSchleife genau i− 1 Iterationen. Da man in jeder inneren Iteration mindestens eineElementaroperation durchfuhrt, ist die Gesamtlaufzeit mindestens

n∑i=2

(i− 1) =n−1∑k=1

k =(n− 1)n

2= Ω(n).

Bemerkung 3.5. Man macht asymptotische und keine exakten Abschatzungen derLaufzeit macht man aus dem folgenden Grund, weil man analysieren will, weil mansich hauptsachlich fur die Großenordnung der Laufzeit fur genugend große Einga-ben interessiert. Bei einer exakteren Abschatzung musste man den Rechner genauer‘festlegen’ (das will man allerdings nicht).

18


3.2 Sortieren durch Mischen

Die Idee ist, zwei rekursiv sortierte moglichst gleichlange Teilarrays zu einem sor-tierten Array zu mischen:

· · · · · ·︸︷︷︸rekursivsortiert

· · · · · ·︸︷︷︸rekursivsortiert

mischen−−−−−→ · · · · · ·︸︷︷︸sortiert

Wir definieren x abgerundet und x aufgerundet fur x ∈ R:

bxc := max z ∈ Z : z ≤ x , dxe := min z ∈ Z : x ≤ z .

Das Sortieren durch Mischen ist sehr einfach aufgebaut:

Sortieren-durch-Mischen(A)

1: if Lange[A] > 1 :2: m := bLange[A]/2c B Mitte des Arrays3: A[1 . . m] in einem neuen Array L aufheben.4: A[m+ 1 . . Lange[A]] in einem neuen Array R aufheben.5: Sortieren-durch-Mischen(L)6: Sortieren-durch-Mischen(R)7: Mischen(A,L,R) B sortierte L und R wirden in das A gemischt8: B Bemerkung: hier werden L und R aufgelost9: end

Beim Mischen wird A sukzessiv mit Inhalten von L und R gefullt. Die Arrays L sowieR werden gleichzeitig von links nach rechts gescannt, die jeweils kleinere Kompo-nenten wird in A aufgenommen:

19


Mischen(A,L,R)

1: a := 1, l := 1, r := 1 B Laufindizes fur jeden der drei Arrays2: B Los!3: while l ≤ Lange[L] und r ≤ Lange[R] :4: if L[l] ≤ R[r] :5: A[a] := L[l]6: a := a+ 1, l := l + 17: else:8: A[a] := R[r]9: a := a+ 1, r := r + 1

10: end11: end12: B Nun einen der beiden Reste aus L bzw. R in A kopieren13: while l ≤ Lange[L] :14: A[a] := L[l]15: a := a+ 1, l := l + 116: end17: while r ≤ Lange[R] :18: A[a] := R[r]19: a := a+ 1, r := r + 120: end

Hier die schematische Darstellung der Hauptphase von Mischen (Initialisierung unddie While-Schleife in den Zeilen 1–11):

L · · · · · ·︸︷︷︸schon

kopiert

l · · · · · ·︸︷︷︸noch nicht

kopiert

mischen−−−−−→ A · · · · · ·︸︷︷︸schongefullt

a · · · · · ·︸︷︷︸noch nicht

gefullt

R · · · · · ·︸︷︷︸schon

kopiert

r · · · · · ·︸︷︷︸noch nicht

kopiert

Invarianten der Hauptphase sind:

• Ist x schon kopiert und y noch nicht kopiert so gilt x ≤ y.

• Alle kopierten Komponenten befinden sich im gefullten Teil von A in eineraufsteigend sortierten Reihenfolge.

Zur Endlichkeit:

• Sortieren durch Mischen terminiert auf Arrays der Lange hochstens 1.

• Ist die Lange des Arrays n ≥ 2, so macht das Verfahren zwei rekursive Aufrufeauf Arrays der Lange hochstens n− 1 und einen Aufruf von Mischen.

20


• Das heißt, unter der Voraussetzung, dass das Mischen terminiert, kann dieEndlichkeit des Sortierens durch Mischen per Induktion nach n gezeigt werden.

• Mischen terminiert, da sich in jeder Iteration jeder Schleife der Index l oderder Index r erhoht wird und die Abbruchbedingungen von der Große von lund r abhangen.

Lemma 3.6 (Die Laufzeit, die Korrektheit und der Speicheraufwand von Mischen).Mischen erfullt die folgenden Bedingungen:

(a) Das Verfahren ist korrekt: gilt Lange[A] = Lange[L] + Lange[R], so werdendie Komponenten aufsteigend sortierter Arrays L und R in das Array A in eineraufsteigend sortierten Reihenfolge gemischt.

(b) Die Laufzeit fur jedes Array A der Lange n ist Θ(n).

(c) Der Speicheraufwand ist Θ(1).

Beweis. Die Aussagen uber den Speicheraufwand sind klar.

Zur Korrektheit: das Element aus L oder R, welches in das R aktuell kopiert wirdist nicht großer als die Elemente die zu einem spateren Zeitpunkt kopiert werden,denn unter den beiden aktuellen Elementen von L und R wahlt man das Kleinere.Jedes Element von L und R wird in einem Zeitpunkt der Ausfuhrung in A kopiert.

Zur Laufzeit: In jeder Iteration wird entweder ein Element von L oder ein Elementvon R abgearbeitet. Das heißt, die Gesamtanzahl der Iteration von allen drei Schlei-fen ist genau Lange[L] + Lange[R] = n. Pro Iteration macht man mindestens eineElementoperation und hochstens konstant viele Elementaroperationen. Die Laufzeitist daher Θ(n).

Bevor wir die Effizienz vom Sortieren durch Mischen sauber analysieren, uberlegenwir informell, was die Laufzeit von Sortieren durch Mischen sein konnte. Am bestenbetrachten wir zuerst Arrays deren Langer eine Zweirpotenz ist. Wir vereinfachendan, die Laufzeit T (n) ware eine Funktion in n (das ist nicht ganz richtig, abereigentlich fast richtig). Nun hat man T (2k) = 2T (2k−1) + a2k, wenn die Laufzeitvon Mischen eine Funktion in der Lange von A ware (wie gesagt, nicht ganz richtig,aber fast richtig). Hierbei ist a > 0 eine Konstante. Diese rekursive Relation kannman nun immer wieder verwenden

T (2k) = 2T (2k−1) + a2k

= 22T (2k−2) + a2k + a2k

= 23T (2k−3) + a2k + a2k + a2k

= · · ·= 2kT (1) + a2k + · · ·+ a2k︸︷︷︸

k

= 2kT (1) + ak2k

= Θ(k2k).

21


Wenn wir nun keine Zweierpotenzen betrachten und k = log n benutzen, so erhaltenwir Θ(n log n). Dieser informeller Beweis kann in einen formal korrekten Beweiskonvertiert werden.

Theorem 3.7 (Uber Sortieren durch Mischen). Fur das Sortieren durch Mischengilt:

(a) Das Verfahren lost das Sortierproblem.

(b) Die Laufzeit auf allen Arrays der Lange n ist Θ(n log n).

(c) Der Speicheraufwand auf allen Arrays der Lange n ist Θ(n).

Beweis. Korrektheit: Wir zeigen die Korrektheit durch Induktion uber n ∈ N0. FurArrays der Große hochstens eins andert das Verfahren das Array A nicht und ar-beitet somit korrekt. Sei n ≥ 2 und sei das Verfahren korrekt auf Arrays der Langehochstens n−1. Auf Arrays der Lange n macht Sortieren durch Mischen zwei rekur-sive Aufrufe des Sortierens durch Mischen mit Arrays der Lange hochstens dn/2e,wobei fur n ≥ 2 der Wert dn/2e nicht hoher als n − 1 ist. Nach der Induktionsvor-aussetzung sortieren die rekursiven Aufrufe die beiden Teilarrays. Die Korrektheitfur Arrays der Lange n folgt nun aus der Korrektheit des Mischens.

Laufzeit: Wir zeigen, dass die Laufzeit O(n log n) ist. Wir wahlen im Folgenden eineKonstante c > 0, fur welche die folgende Aussage durch Induktion gezeigt werdenkann: Die Laufzeit vom Sortieren durch Mischen auf Arrays der Lange n ≥ 2 isthochstens cn log n. Damit diese Aussage fur 2 ≤ n ≤ 3 wahr wird, reicht es c eineobere Schranke an die Laufzeit fur Arrays der Lange 2 und 3 zu wahlen. Sei n ≥ 4 undsei die Laufzeit des Sortierens durch Mischen auf Arrays der Lange k ∈ 2, . . . , n−1hochstens ck log k. Wir zeigen nun, dass die Laufzeit vom Sortieren durch Mischenauf Arrays der Lange n hochstens cn log n ist, wenn die Konstante c > 0 passendfixiert ist.

Das Sortieren durch Mischen besteht aus zwei rekursiven Aufrufe auf Arrays derLange bn/2c und dn/2e, einem Aufruf von Mischen (mit der linearen Laufzeit in n)und dem Kopieren der Teilen von A in die Arrays L (mit der linearen Laufzeit in n).Mit der Verwendung der Induktionsvoraussetzung ergibt sich die obere Schranke

T := c bn/2c log bn/2c︸︷︷︸Sortieren von L

+c dn/2e log dn/2e︸︷︷︸Sortieren von R

+ an︸︷︷︸Kopieren und Mischen

an die Gesamtlaufzeit, wobei a > 0 eine Konstante ist. (Hier und im Folgendenbezeichnet log ohne Angabe der Basis den Logarithmus zur Basis 2.) Es sei be-merkt, dass die Induktionsvoraussetzung tatsachlich anwendbar ist, weil fur n ≥ 4die Ungleichungen

2 ≤ n

2≤ bn/2c ≤ dn/2e ≤ n+ 1

2≤ n− 1

erfullt sind und somit die beiden Werte bn/2c und dn/2e im Bereich 2, . . . , n− 1liegen.

Die Terme unter den Logarithmen konnen wir mit Hilfe von Ungleichungen

dn/2e ≤ dn/2e ≤ n+ 1

2≤ 3n

4

22


abschatzen. So ergibt sich die Schranke:

T ≤ c(bn/2c+ dn/2e) log(3n/4) + an

= cn log(3n/4) + an

= cn(log n− log(4/3)) + an

= cn log n+ (a− c log(4/3))n.

Nun gilt die Abschatzung T ≤ cn log n wenn wir c groß genug fixieren, sodass dieBedingung c log(4/3) ≥ a erfullt ist.

Auf eine ahnliche Weise kann auch die untere Schranke Ω(n log n) auf Arrays derLange n gezeigt werden.

Speicheraufwand: Wir zeigen, dass der Speicheraufwand O(n) ist. Wir mussen alsozeigen, dass fur eine Konstante c > 0 der Speicheraufwand auf Arrays der Langen ≥ 2 hochstens cn ist. Das wird durch Induktion uber n gezeigt. Fur n = 2 reichtes, c genugend groß zu wahlen. Sei n ≥ 3 und sei der Speicheraufwand fur Arraysder Lange k ∈ 2, . . . , n − 1 hochstens ck. Fur ein beliebiges Array der Lange nergibt sich die obere Schranke

S := c dn/2e︸︷︷︸rekursive Aufrufe

auf L und R

+ an︸︷︷︸Kopieren in L und R

an den Speicheraufwand, wobei hier a > 0 eine Konstante ist. In dieser Abschatzungscheint der Speicheraufwand von Mischen ignoriert zu sein. Mischen hat einen Kon-stanten Speicheraufwand. Wenn wir also a genugend groß wahlen, konnen wir durchden Term an den Aufwand von Mischen mitberucksichtigen. Die Erklarung, warumman im Gegenteil zur Analyse der Laufzeit nur einen Term fur die beiden rekursivenAufrufe hat ist die Folgende. Wenn der erste rekursive Aufruf terminiert hat, gibter den von ihm benutzten Speicher wieder frei; dieser Speicher kann anschließendbeim zweiten rekursiven Aufruf benutzt werden.

Wir schatzen dn/2e durch

dn/2e ≤ (n+ 1)/2 ≤ 3n/4

ab und erhaltenS ≤ (3c/4 + a)n.

Somit hat man S ≤ cn, wenn c ≥ 4a gilt. Wir wahlen also in diesem Beweis c großgenug, sodass c ≥ 4a gilt.

Die untere Schranke Ω(n) an den Speicheraufwand auf allen Arrays der Lange nkann analog gezeigt werden.

Aufgabe 3.8. Zeigen Sie, dass das Sortieren durch Mischen auf allen Arrays derLange n die Laufzeit Ω(n log n) hat.

Aufgabe 3.9. Zeigen Sie, dass das Sortieren durch Mischen auf allen Arrays derLange der Lange n den Speicheraufwand Ω(n) hat.

Der Unterschied der Worst-Case-Laufzeiten Θ(n2) und Θ(n log n) macht sich beider Vergroßerung der Array-Lange n sehr schnell bemerkbar. Das asymptotischeVerhalten von n log n ist viel ‘ahnlicher’ zum Verhalten von n als zum Verhalten vonn2. Salopp kann man das Verhalten n log n als ‘beinah linear’ beschreiben.

23


Bemerkung 3.10 (Anwendungen der Sortierverfahren). Sortierverfahren haben di-verse Anwendungen.

1. Wenn die Datensatze sortiert sind, so kann man unter den Datensatzen vielschneller suchen. Die Suche nach einem Element mit einem gegebenen Wertx kann in einem Sortierten Array in der Worst-Case-Laufzeit Θ(log n) durch-gefuhrt werden. Im Gegenteil wurde eine solche Suche in einem unsortiertenArray die Worst-Case-Laufzeit Θ(n) haben.

2. Verschiedene Algorithmen benutzen Sortierverfahren als Hilfsmittel (etwa ei-nige Algorithmen zur Berechnung der konvexen Hulle in der Dimension zwei).

3. Durch das Sortieren kann man die Vielfachheiten der Elemente der Arrayszahlen. Die Vielfachheit ist die Angabe, wie oft das Element im Array vor-kommt.

4. Durch das Sortieren kann man ein Array mit potenziellen Wiederholungen vonWerten zu einem Array ohne Wiederholungen der Werte konvertieren.

3.3 Die Datenstruktur Heap und der Heap-Sort

Man spricht von einer Datenstruktur, wenn man die vorhandenen Daten auf einebesondere Weise organisiert, und eine Reihe aus aus Prozeduren fur diese Daten zurVerfugung stellt, die ein ‘Team’ bilden, d.h., die Prozeduren ‘helfen sich’ gegenseitigbzw. erganzen sich auf eine naturliche Weise. Das Team aus Prozeduren, die zurVerfugung stehen, nennt man ein Interface. In der Regel hat man Prozeduren zumAblesen, zur Anderung und zum Loschen verschiedener Datensatze.

In diesem Abschnitt wird die Datenstruktur Heap eingefuhrt. Diese Datenstrukturist recht nutzlich, und wir werde sie im Teil 2 dieses Kurs als Hilfsmittel bei einemAlgorithmus zur Berechnung der kurzesten Wege in einem Graphen verwenden.

Der Heap-Sort ist im Wesentlichen ein Nebenprodukt bei der Umsetzung der Da-tenstruktur Heap. Der Heap-Sort besteht aus zwei Phasen:

ArrayPhase 1 (Erzeugung des Heaps)−−−−−−−−−−−−−−−−−−−→ Heap

Phase 2 (Auflosung des Heaps)−−−−−−−−−−−−−−−−−−−→ sortiertes Array.

Der Heap-Sort hat asymptotisch die gleiche Worst-Case-Laufzeit wie das Sortierendurch Einfugen und einen besseren Speicheraufwand.

In diesem Abschnitt betrachten wir Arrays A, welche neben dem Attribut Lange[A]noch ein weiteres zusatzliches Attribut Große[A] mit 0 ≤ Große[A] ≤ Lange[A]haben. Somit wird das Array in zwei Teile aufgeteilt: A[1 . . Große[A]] und derPuffer A[Große[A] + 1 . . Lange[A]].

Die Komponenten A[i] mit 1 ≤ i ≤ Große[A] werden als Knoten eines sogenanntengeordneten Baums interpretiert, indem man fur die Komponenten A[i] die Vater-Kind Relation einfuhrt. Bei Große[A] = 0 ist der Baum leer. Ansonsten heißt A[1]die Wurzel des Baums. Fur 2 ≤ i ≤ Große[A] heißt A[bi/2c] der Vater des KontenA[i].

Im folgenden Bild sind die Vater-Kind-Relationen im Fall von Große[A] = 8 dar-gestellt:

24


A[1]

A[2]

A[4]

A[8]

A[5]

A[3]

A[6] A[7]

Wenn also 1 ≤ i ≤ Große[A] gilt, so ist die Komponente A[2i] das linke Kind vonA[i], falls 2i ≤ Große[A] gilt, und die Komponente A[2i+ 1] das rechte Kind vonA[i], falls 2i+ 1 ≤ Große[A]. Man kann also Knoten ohne Kinder, Knoten nur mitdem linken Kind und Knoten mit zwei Kindern haben.

Wir werden die folgenden einfachen Prozeduren benutzen:

v = Vater(i)

1: v := bi/2ck = Linkes-Kind(i)

1: k := 2i

k = Rechtes-Kind(i)

1: k := 2i+ 1

Der Nachfahre eines Knotens ist rekursiv als ein Kind oder ein Nachfahre eines Kindsdefiniert. Der Vorfahre eines Knotens ist rekursiv als der Vater oder ein Vorfahredes Vaters definiert.

Gilt fur einen Konten A[i], 2t ≤ i < 2t+1 und i ≤ Große[A], so heißt t die Tiefevon A[i]. Die Wurzel befindet sich somit in der Tiefe 0, die Knoten A[2] und A[3](falls vorhanden) in der Tiefe 1 usw. Ein Pfad der Lange t ist eine Folge v0, . . . , vt,bei der vi Vater von vi+1 fur alle 0 ≤ i < t gilt. Hier ein Beispiel, in dem man einPfad und die Angabe der Tiefen sieht:

Tiefe 0

Tiefe 1

Tiefe 2

Tiefe 3

A[1]

A[2]

A[4]

A[8]

A[5]

A[3]

A[6] A[7]

Ein Max-Heap, ist ein Array A mit Große[A] ≤ Lange[A], fur das die sogenannteMax-Heap-Eigenschaft

A[Vater(i)] ≥ A[i]

fur alle i = 2, . . . ,Große[A] erfullt ist. Analog werden auch Min-Heap durch dieMin-Heap-Eigenschaft eingefuhrt. Wenn man von einem Heap redet, so meint maneinen Max- oder einen Min-Heap. Ob man Max- oder Min-Heaps diskutiert ist ziem-lich egal. In diesem Abschnitt werden wir die Max-Heaps diskutieren. Hier ein Bei-spiel eines Max-Heaps der Große 8:

25


A[1] = 21

A[2] = 14

A[4] = 8

A[8] = 2

A[5] = 7

A[3] = 10

A[6] = 9 A[7] = 3

Heaps kann man als rekursive Datenstrukturen auffassen, weil jeder Knoten desHeaps als Wurzel eines Teilheaps interpretiert werden kann. In diesem Beilspiel istder Teilheap mit der Wurzel A[2] farblich hinterlegt:

A[1] = 21

A[2] = 14

A[4] = 8

A[8] = 2

A[5] = 7

A[3] = 10

A[6] = 9 A[7] = 3

Die Hohe eines Heaps ist die maximale Tiefe der Knoten des Heaps plus eins. DerHeap aus dem vorigen Bild hat zum Beispiel die Hohe 3. Des weiteren definierenwir die Hohe eines Heapknotens als die Hohe seines Teilheaps. Der Knoten A[2] ausdem vorigen Bild hat die Hohe 2.

In der folgenden Prozedur wird fur einen gegebenen Index i ∈ 1, . . . ,Große[A]unter den Indizes aus

i,Linkes-Kind(i),Rechtes-Kind(i) ∩ 1, . . . ,Große[A]

ein Index g mit dem Großten Wert von A[g] gewahlt.

g := Großter-von-drei-Knoten(A, i)

1: l := Linkes-Kind(i)2: r := Rechtes-Kind(i)3: g := i4: if l ≤ Große[A] und A[l] > A[i] :5: g := l6: end7: if r ≤ Große[A] und A[r] > A[g] :8: g := r9: end

Wir setzen nun die wichtigste Prozedur der Datenstruktur Heap um, die man in derRegel Heapify nennt. Als Eingabe erhalt man einen Index i ∈ 1, . . . ,Große[A].Unter der Voraussetzung, dass fur der linke und rechte Teilbaume von A[i] bereits

26


Heaps sind, wird der Teilbaum mit der Wurzel A[i] durch das Vertauschen der Werteseiner Knoten zu einem Heap konvertiert.

Max-Heapify(A, i)

1: g := Großter-von-drei-Knoten(A, i)2: while g 6= i :3: Vertausche A[i] und A[g]4: i := g5: g := Großter-von-drei-Knoten(A, i)6: end

Beispiel 3.11. Wir betrachten das folgende A mit Große[A] = 10:

A[1] = 16

A[2] = 4 A[3] = 10

A[4] = 14 A[5] = 7 A[6] = 9 A[7] = 3

A[8] = 2 A[9] = 8 A[10] = 1

Bei der Ausfuhrung von Max-Heapify(A, 2) werden in der ersten Iteration A[2]und A[4] vertauscht:

A[1] = 16

A[2] = 14 A[3] = 10

A[4] = 4 A[5] = 7 A[6] = 9 A[7] = 3A[8] = 2

A[9] = 8 A[10] = 1

und in der zweiten Iteration A[4] und A[9]:

A[1] = 16

A[2] = 14 A[3] = 10

A[4] = 8 A[5] = 7A[6] = 9 A[7] = 3 A[8] = 2

A[9] = 4 A[10] = 1

Somit wird die Heapeigenschaft fur den Teilbaum mit der Wurzel A[2] erstellt.

Theorem 3.12 (Korrektheit von Heapify). Max-Heapify arbeitet korrekt (d.h.,laut der Beschreibung oben).

Beweis. Die Korrektheit von Max-Heapify kann per Induktion nach der AnzahlN der Elemente in dem Baum mit Wurzel i bewiesen werden. Ist N = 1, so arbeteit

27


Max-Heapify offensichtlich korrekt. Agenommen, Max-Heapify arbeitet korrektfur Teilbaume der Große hochstens N mit N ∈ N. Sei A und i so, dass der Teilbaummit Wurzel i Große N+1 hat. Die Funktion Großter-von-drei-Knoten arbeitetoffensichtlich Korrekt, d.h. A[g] das Maximum von A[i], A[Linkes-Kind(i)] undA[Rechtes-Kind(i)]. Der Umtausch in Zeile 3 von Max-Heapify erstellt die Heap-Eigenschaft bezuglich i und den Kindern von i. Die Heap-Eigenschaft fur Baume,deren Wurzel die Kinder von i sind, folgt aus der Induktionsvoraussetzung.

Theorem 3.13 (Laufzeit von Heapify). Sei 1 ≤ i ≤ Große[A]. Seien der linke undrechte Teilbaume des Knotens A[i]. Die Worst-Case-Laufzeit von Max-Heapify(A, i)fur Knoten A[i] der Hohe h ist Θ(h).

Beweis. Die Laufzeiten vom Vertauschen von zwei Knoten und dem Aufruf vonGroßter-von-drei-Knoten(A, i) sind Θ(1). Die Anzahl der Iterationen ist of-fensichtlich nicht Hoher als h, weil zu jedem Zeitpunkt der Ausfuhrung A[i] einNachfahre des Knotens, fur welchen der Max-Heapify aufgerufen wurde. Ist derWert von A[i] echt kleiner als der Wert aller Nachfahren von A[i], so macht dasVerfahren genau h Iterationen.

Nun konnen wir mit Hilfe von Max-Heapify die erste Phase vom Heapsort umset-zen. In der folgenden Prozedur Max-Heap-erzeugen wird aus einem Array mitn Komponenten durch das Vertauschen der Elemente ein Max-Heap mit n Kno-ten erstellt. Zur Umsetzung: Es wird uber alle Knoten, die Kinder haben, in derRuckwartsrichtung iteriert und fur jeden Knoten solchen Knoten Max-Heapifyaufgerufen.

Max-Heap-erzeugen(A)

1: Große[A] := Lange[A]2: for i := Vater(Große[A]), . . . , 1 mit Schritt −1 :3: B Hier: Teilbaume aller Knoten mit Indizes großer als i bereits Max-Heaps4: Max-Heapify(A, i) B Nun ist Teilbaum mit Wurzel A[i] dran!5: end

Beispiel 3.14. Wir verfolgen die Ausfuhrung von Max-Heapify am folgendenBeispiel. Sei A := [4, 1, 3, 2, 16, 9, 10, 14, 8, 7] und Große[A] := 10. Wir illustrierendie Arbeit von Max-Heap-erzeugen(A) an dem gegebenen A.

• A[5] und A[10] werden nicht vertauscht.

• A[4] und A[8] werden vertauscht.

• A[3] und A[7] werden vertauscht.

• A[2] und A[5], A[5] und A[10] werden vertauscht.

• A[1] und A[2], A[2] und A[4], A[4] und A[9] werden vertauscht.

Theorem 3.15. Max-Heap-erzeugen arbeitet korrekt.

28


Beweis. Wir setzen n := Große[A] = Lange[A]. Ein Knoten mit Index i ∈ [n]hat keine Kinder wenn 2i und 2i + 1 echt großer als n ist. Die Bedingung 2i ≤n charakterisiert somit die Indizes der Knoten mit Kindern. Somit ist bn/2c =Vater(n) der großte Index eines Knotens mit Kindern.

Wir sehen also, dass in der ersten Iteration Teilbaume aller Knoten mit Indizesgroßer als i Heaps sind, weil diese Teilbaume nur aus ihrem Wurzelknoten bestehen.Da wir in jeder Iteration Max-Heapify fur den aktuellen Knoten A[i] ausfuhren,bleibt diese Bedingung in jeder Iteration erhalten, sodass man in letzter Iterationnach dem Aufruf von Max-Heapify fur den Knoten A[1] die Heap-Eigenschaft fur alleKnoten erstellen. Es sei noch bemerkt, dass die Rahmenbedingungen fur den Aufrufvon Max-Heapify fur den Knoten A[i] erfullt sind, da zu jeder Zeit der Ausfuhrungder linke und der rechte Teilbaum des Knotens A[i] bereits Heaps sind.

Die Hohe eines geordneten Baums mit n Knoten ist O(log n). Somit ergibt sich dieobere Schranke O(n log n) an die Laufzeit von Max-Heap-erzeugen auf Arraysder Lange n. Es stellt sich heraus, dass diese obere Schranke nicht optimal ist. Eineexakte Asymptotik wird in Theorem 3.17 angegeben.

Die Laufzeit von Max-Heap-erzeugen ist O(n log n) mit n := Lange[A].

Lemma 3.16. Sei A Heap der Große n ∈ N. Dann ist blog nc+ 1 die Hohe von Aund, fur 1 ≤ h ≤ blog nc+ 1, besitzt A hochstens

⌊n

2h−1

⌋der Hohe h.

Beweis. Die Hohe ist als die maximale Tiefe von Heapknoten plus 1 definiert. Seit ∈ N0. Ein Knoten i mit 2t ≤ i < 2t+1 befindet sich in der Tiefe t. Wir sind alsoauf der Suche nach t mit 2t ≤ n < 2t+1. Dieses t ist genau blog nc. Wir haben alsogezeigt, dass blog nc+ 1 die Hohe von A ist.

Wenn wir einen Knoten i ∈ [n] fixieren, so befindet sich A[i] in der Tiefe 0 des Teil-baums mit Wurzel A[i]. Der Knoten A[2i] befindet sich in der Tiefe 1 des Teilbaumsmit der Wurzel A[i] usw. Wir sehen also, dass die maximale Tiefe der Knoten desTeilbaums mit Wurzel A[i] als nichtnegativer ganzzahliger Wert t mit der Eigen-schaft 2ti ≤ n < 2t+1i beschrieben werden kann. Somit ist die Hohe des Teilbaumsmit Wurzel A[i] als h ∈ N mit 2h−1i ≤ n < i2h definiert. Die Knoten A[i] derTeilbaume der Hohe h sind also durch die Bedingung n

2h< i ≤ n

2h−1 charakterisiert.

Wir sehen also, dass man hochstens⌊

n2h−1

⌋postive ganzzahlige Werte i hat, welche

die beiden Schranken erfullen.

Anhand des vorigen Lemmas bestimmen wir die exakte Asymptotik von Max-Heap-erzeugen:

Theorem 3.17. Die Laufzeit von Max-Heap-erzeugen auf allen Arrays der Langen ist Θ(n).

Beweis. Die Laufzeit betragt Ω(n), weil Max-Heap-erzeugen uber alle Knoten,die Kinder besitzen, iteriert, und die Anzahl dieser Knoten bn/2c = Ω(n) ist.

Wir zeigen die obere Schranke O(n) an die Laufzeit von Max-Heap-erzeugen.Wir fixieren eine Konstante c > 0 derart, dass die Laufzeit von Max-heapify aufeinem Knoten der Hohe h hochstens ch ist. Nun lasst sich mit Hilfe von Lemma 3.16eine obere Schranke an die Gesamtlaufzeit aller Ausfuhrungen von Max-Heapify

29


innerhalb von Max-Heap-erzeugen berechnen. In Abhangigkeit von der Hohender Knoten setzt sich die obere Schranke folgedermaßen zusammen:

blognc+1∑h=1

⌊ n

2h−1

⌋︸︷︷︸

obere SchrankeAnz. Knoten

Hohe h

(ch)︸︷︷︸Laufzeit pro

KnotenHohe h

≤ cnblognc+1∑

h=1

h

2h−1≤ cn

∞∑h=1

h2−h+1

︸︷︷︸<∞

.

Heapsort(A)

1: Max-Heap-erzeugen(A)2: for i = Lange[A], . . . , 2 mit Schritt −1 :3: B Hier: Elemente des Puffers sind Aufsteigend sortiert und nicht kleiner als

die Elemente des aktiven Bereichs.4: vertauschen(A[1], A[i])5: Große[A] := Große[A]− 16: Max-Heapify(A, 1)7: end

Theorem 3.18. Der Heapsort arbeitet korrekt. Seine Laufzeit auf Arrays derLange n ist O(n log n).

Beweis. Die Korrektheit folgt direkt. Die Laufzeit ergibt sich aus den Abschatzungender Laufzeit von Max-Heap-erzeugen und Max-Heapify.

Beispiel 3.19. Arbeitsweise von Heapsort auf dem Heap A := [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]mit der Große 10 illustrieren. . .

3.4 Prioritatsschlangen auf der Basis von Heaps

Die Priortitatsschlange ist ein Behalter fur endlich viele Werte, fur welche die fol-genden Operationen zu Verfugung stehen.

• einfugen(S, x) - ein neues Element x einfugen.

• Maximum(S) - Ruckgabe von Maximum.

• Maximum-entfernen(S) - entfernt ein maximales Element von S und gibtdieses zuruck.

Anwendungen von Prioritatsschlangen:

• Zeitplanung (engl.: scheduling) von Jobs auf einem Rechner.

• Ereignisgetriebene Simulatoren.

30


Prioritatsschlangen auf der Basis von Heaps:

m = Heap-Maximum(A)

1: m := A[1]

m = Heap-Maximum-entfernen(A)

1: m := A[1]2: A[1] := A[Große[A]]3: Große[A] := Große[A]− 14: Max-Heapify(A)

Heap-Schlußel-Vergroßern(A, i, x)

Assumption: A ist Heap; 1 ≤ i ≤ Große[A]; x ≥ A[i].Result: Der Wert von A[i] wird gleich x gesetzt; Heap-Eigeschaft wird neu erstellt.1: A[i] := x2: while i > 1 und A[Vater(i)] < A[i] :3: vertauschen(A[i], A[Vater(i)])4: i := Vater(i)5: end

Neues Element einfugen:

Max-Heap-einfugen(A, x)

Assumption: A ist Heap.Result: das Element x wird in A eingefugt, sodass A ein Heap bleibt.1: Große[A] := Große[A] + 12: A[Große[A]] := −∞3: Heap-Schlußel-Vergroßern(A,Große[A], x)

Element entfernen:

Heap-entfernen(A, i)

Assumption: A ist Heap, der das Element A[i] besitzt.Result: Das Element A[i] wird aus A enfernet, sodass A ein Heap bleibt.1: x := A[Große[A]]2: Große[A] := Große[A]− 13: if x > A[i] :4: Heap-Schlussel-vergrossern(A, x, i)5: else:6: A[i] := x7: Heapify(A, i)8: end

Direkte Implementierung von Prioritatsschlangen auf der Basis von Arrays mit se-quentieller Suche ist viel inneffizienter:

31


Worst-Case-Laufzeiten von Prioritatschlangen:Arrays mit sequentieller Suche vs. Heap-basierte Umsetzung

Sequentielle Suche Heap-basiert

Maximum Θ(n) Θ(1)Maximum entfernen Θ(n) Θ(log n)einfugen Θ(1) Θ(log n)entfernen Θ(n) Θ(log n)Schlussel verandern Θ(1) Θ(log n)

Worst-Case-Operation Θ(n) Θ(log n)

3.5 Untere Schranken an die Laufzeit von Sortieralgorithmen

Theorem 3.20. Man betrachte einen Algorithmus zur Bestimmung der aufstei-genden Reihenfolge der Elemente eines gegebenen Arrays, welcher die aufsteigendeReihenfolge ausschließlich durch das Vergleichen der Komponenten mit Hilfe von ≤bestimmt. Das heißt, der Algorithmus:

• greift auf das gegebene Array A der Lange n ∈ N ausschließlich mit Hilfe derVergleichsoperationen A[i] ≤ A[j] fur i, j ∈ 1, . . . , n zu.

• berechnet eine Permutation i1, . . . , in der Indizes 1, . . . , n mit der EigenschaftA[i1] ≤ · · · ≤ A[in].

Dann macht ein solcher Algorithmus Ω(n log n) Vergleiche A[i] ≤ A[j] mit i, j ∈1, . . . , n der Komponenten des Eingabearrays A.

Beweis. Bei der Ausfuhrung des Algorithmus erstellen wir eine ‘Log-Datei’ auf diefolgende Weise. Bei jedem Vergleich A[i] ≤ A[j] wird das Resultat des Vergleichs zurLOG-Datei hinzugefugt (etwa: 1, wenn das Resultat des Vergleichs wahr war und0 sonst). Sei nun k die maximale Anzahl der Vergleiche vom Typ A[i] ≤ A[j] beider Ausfuhrung des Algorithmus auf Arrays der Lange n. Somit ist der Inhalt derLog-Datei am Ende der Ausfuhrung ein 0, 1-String der Lange hochstens k. AufArrays der Lange n gib es also hochstens

20 + · · ·+ 2k

mogliche Inhalte der Log-Datei. Diese Zahl ist hochstens 2k+1. Die Berechnete Per-mutation ist durch den Inhalt der Log-Datei eindeutig bestimmt, d.h., die Ruckgabeist eindeutig durch die Resultate der Vergleiche bestimmt, weil der Algorithmuszum Eingabearray A keine anderen Informationen hat außer den Informationen, diedurch Vergleiche A[i] ≤ A[j] gewonnen wurden.

Fur n paarweise verschiedene ganzzahlige Werte x1 < . . . < xn hat man n! Moglichkeitendiese Werte in einem Array der Lange n aufzuheben. Die Ruckgaben (Permutatio-nen) fur all diese n! Arrays sind paarweise verschieden. Es folgt also, dass die Anzahlder Log-Dateien bei der Ausfuhrung auf Arrays der Langen n mindestens n! seinmuss. Es ergibt sich die Ungleichung

2k+1 ≥ n!

welche man als k ≥ log(n!)−1 umformulieren kann. Das ergibt die Behauptung.

32


Aufgabe 3.21. Zeigen Sie log(n!)− 1 = Ω(n log n).

Beweis.

log 1 + log 2 + · · ·+ log n− 1 =n∑

i=3

log i

Fur die dn/2e Elemente mit n−dn/2e+ 1 ≤ i ≤ n gilt log(i) ≥ log(n−dn/2e+ 1) ≥log(n−(n+1)/2+1) ≥ log(n/2). Somit ist die Summe mindestens dn/2e log(n/2) ≥12n log(n/2). Man hat log(n/2) = log(n)− 1 ≥ 1

2 log(n) bei n ≥ 4. Somit ergibt sichdie Abschatzung 1

4n log n.

3.6 Countingsort

Wenn man uber Zusatzinformation uber die Natur der Komponenten eines Arraysverfugt, so kann man unter Umstanden das Array schneller als in der Zeit O(n log n)sortieren.

Die Eingabe der Prozeduren dieses Abschnitts besteht aus einer naturlichen Zahl kund einem Array A, dessen alle Komponenten zu 1, . . . , k gehoren. Ist k nicht allzugroß im Vergleich zur Lange von A, so kann man den sogenannten CountingSortverwenden.

Wir beginnen mit der folgenden Prozedur, die fur jedes Element x ∈ 1, . . . , k zahlt,wie oft x im Array A vorkommt.

Z = Werte-zahlen(A, k)

1: Ein neues, mit Nullen gefulltes Array Z der Lange k einfuhren2: for j = 1, . . . ,Lange[A] :3: Z[A[j]] := Z[A[j]] + 14: end

Die folgende Prozedur ist analog zur Verteilungsfunktion aus der Wahrscheinlich-keitstheorie (Elemente der Wahrscheinlichkeitstheorie hatten Sie zum Teil in derSchule, noch viel mehr lernen Sie im dritten Semester). Fur jedes i ∈ 1, . . . , kzahlt die Prozedur die Anzahl der Elemente in A im Bereich 1, . . . , i (d.h., dieElemente die nicht großer als i sind).

Z = Verteilungsfunktion(A, k)

1: Z := Werte-zahlen(A, k)2: for i := 2, . . . , k :3: B Hier: Z[i− 1] ist die Anzahl der Elemente in 1, . . . , i− 14: B Z[i] die Anzahl der Elemente mit dem Wert i5: Z[i] := Z[i] + Z[i− 1]6: end

Beim Countingsort bleibt der Eingabearray A unverandert. Man generiert statt-dessen ein Ausgabearray B, in welchem die Elemente von A in einer aufsteigendsortierten Reihenfolge enthalten sind.

33


Die Idee ist, dass man durch die Verteilungsfunktion berechnet hat, unter wel-cher Position welche Komponente von A in der sortierten Version von A stehensoll.

B = CountingSort(A, k)

1: Z := Verteilungsfunktion(A, k)2: Ein neues Array B der gleichen Lange wie A einfuhren3: for j := Lange[A], . . . , 1 mit Schritt −1 :4: x := A[j] B In dieser Iteration schreiben wir x in B5: B[Z[x]] := x B Der Wert x wird in die Position Z[x] des Ruckgabe-Arrays

geschrieben6: Z[x] := Z[x] − 1 B Wenn der Wert x in einer spateren Iteration noch mal

kommt . . .7: end

Ein Sortieralgorithmus heißt stabil, wenn dieser Algorithmus die relative Reihen-folge der Elemente mit dem gleichen Wert nicht andert. Etwa, wenn ein stabilerSortieralgorithmus ein Array aus Punkten in Z2 nach der ersten x-Koordinate sor-tiert und das Array zwei Komponenten A[i] = (x, y) und A[j] = (x, y′) mit i < jhat, bei denen die x-Koordinate gleich ist, so steht auch nach dem Sortieren (x, y)vor (x, y′).

CountingSort ist stabil, wobei die Stabilitat durch das Iterieren uberA in Ruckwarts-richtung sichergestellt wird.

Theorem 3.22. Die Laufzeit von Countingsort auf Arrays der Lange n mit Ele-menten aus 1, . . . , k ist Θ(n+ k).

Die Laufzeit ist Θ(n) fur k = O(n).

Beispiel 3.23. Countingsort fur A = [2, 5, 4, 1, 2, 4, 1, 4] und k = 1. Werte-zahlenerstellt das Array [2, 2, 0, 3, 1]. Die ‘Verteilungsfunktion’ ist somit [2, 4, 4, 7, 8]. Dar-auf basierend konnen nun die Werte belegt werden. Man weiß, die 5 geht in diePosition 8. Die erste 4, die wir entdecken (beim Ruckwartsiterieren) in die Position7, die nachste vier in die Position 6 usw.

3.7 RadixSort

Angenommen, A ist ein Array aus nichtnegativen ganzen Zahlen, die zu einer gege-benen Basis d ≥ 2 dargestellt sind und hochstens k ∈ N Stellen haben. Die Stellensind mit Zahlen von 0 bis d− 1 indexiert, wobei wir als die 0-te Stelle die niedrigsteStelle bezeichnen. Mit Hilfe von CountingSort konnen wir das Array A wie obenfolgendermaßen sortieren:

RadixSort(A, d, k)

1: for i = 0, . . . , d− 1 :2: Die Elemente von A nach der i-ten Stelle mit Hilfe von CountingSort sor-

tieren.3: end

34


Beispiel 3.24. Beispiel zu RadixSort: [329, 459, 657, 839, 436, 720, 355]...

Theorem 3.25. RadixSort arbeitet korrekt.

Beweis. Per Induktion nach der Anzahl der Stellen, mit der Verwendung der Stabi-litat von CountingSort.

Theorem 3.26. Die Laufzeit von RadixSort auf einem n-elementigen Array derd-stelligen Zahlen im Stellenwersystem mit Basis k ist Θ(d(n+ k)) (unter der Vor-aussetzung, dass jede Zahl direkt durch Ihre Stellen gegeben ist – etwa, als Array derStellen).

3.8 QuickSort

Beim QuickSort beschaftigen wir uns mit dem Teilarray A[q . . r] eines Arrays Amit 1 ≤ p ≤ q ≤ Lange[A]. Die Aufgabe des QuickSort ist dieses Teilarray zusortieren. Durch die Angabe von q = 1 und r = Lange[A] kann man dann dasgesamte Array A sortieren. Der QuickSort ist rekursive aufgebaut. Sein Herzstuckist die Prozedur Partition. In Partition werden die komponenten eines TeilarraysA[p . . q] in Abhangigkeit vom Wert x = A[q] vertauscht. Die Komponenten die nichtgroßer als x sind sollen dabei links von x stehen und die Komponenten, die nichtkleiner als x, sind rechts von x. Die Ruckgabe von Partition ist die Position vonx nach dem

QuickSort(A, p, r)

1: if p < r :2: q := Partition(A, p, r)3: Quicksort(A, p, q − 1)4: Quicksort(A, q + 1, r)5: end

Solange Partition korrekt arbeitet, arbeitet auch Quicksort korrekt; der Beweisist Analog zum Beweis der Richtigkeit von Sortieren-durch-Mischen.

Die Arbeitsweise der folgenden Umsetzung von Partition kann in entarteten Fallenetwas verwirrend sein. Die Arbeitsweise kann etwas klarer werden, wenn man sichvorstellt, als ob man zwischen der aufeinanderfolgenden Komponenten ‘Trennstel-len’ hatte, wobei die Trennstelle zwischen A[k − 1] und A[k] mit k nummeriert ist.Wahrend des Iterieren sind also die Komponenten zwischen den Trennstellen p− 1und i. Die Partitionierung ist so aufgebaut, dass ein Index j iterativ wachst, und injeder Iteration die Elemente zwischen den Trennstellen p und i und j nicht großerals x wahrend die Elemente zwischen den Trennstellen i und j nicht kleiner als xsind.

35


q = Partition(A, p, r)

1: x := A[r]2: i := p3: for j := p, . . . , r − 1 :4: if A[j] ≤ x :5: A[i+ 1] und A[j] vertauschen6: i := i+ 17: end8: end9: A[i+ 1] und A[r] vertauschen

10: q := i+ 1

Theorem 3.27. Partition arbeitet korrekt. Die Laufzeit auf allen Teilarrays derLange n ist Θ(n). Die Anzahl der Vergleiche der Komponenten des Teilarrays istn− 1.

Beweis. Die Korrektheit basiert auf den oben erwahnten Schleifen-Invarianten. Dieanderen Behauptung sind ziemlich einfach.

Wir weisen darauf hin, dass unterschiedliche Umsetzungen der Partitionierung (mitahnlichen Eigenschaften) existieren. Es stellt sich heraus, dass unsere Variante QuckSortauf manchen Arrays recht langsam ist (quadratisch in der Lange des Arrays). An-dererseits werden wir nun sehen, dass QuickSort in einem ‘generischen Durch-schnittsfall’ recht schnell ist.

Das Element, mit dem bei einer Partitionierung alle anderen Elemente verglichenwerden nennt man das Pivot-Element.

Wir werden die folgende Ungleichung benutzen:

Aufgabe 3.28. Zeigen Sie fur alle n ∈ N mit n ≥ 2:

n−1∑k=1

k log2 k ≤1

2n2 log2 n−

1

8n2

36


Beweis.

n−1∑k=1

k log2 k ≤dn2 e−1∑k=1

k log2 k +

n−1∑k=dn2 e

k log2 k

≤ log2

n

2

dn2 e−1∑k=1

k + log2 n

n−1∑k=dn2 e

k

= (log2 n− 1)

dn2 e−1∑k=1

k + log2 n

n−1∑k=dn2 e

k

= log2 n

n−1∑k=1

k −dn2 e−1∑k=1

k

=1

2n(n− 1) log2 n−

1

2

(⌈n2

⌉− 1)⌈n

2

⌉≤ 1

2n(n− 1) log2 n−

1

2

(n2− 1) n

2

=1

2n2 log2 n−

1

2n log2 n−

1

8n2 +

n

4

≤ 1

2n2 log2 n−

1

8n2.

Theorem 3.29. Wir betrachten die Umsetzung von QuickSort mit der Parti-tionierung, welche die relative Reihenfolge der Elemente die kleiner als das Pivot-Element nicht andert und die relative Reihenfolge der Elemente die großer als dasPivot-Element ebenfalls nicht andert. Wir fixieren ganze Zahlen x1 < x2 < x3 < . . .und betrachten, fur jedes n ∈ N, die durchschnittliche Laufzeit T (n) von QuickSortden n! Belegungen eines Arrays der Lange n mit den Werten x1, . . . , xn. Dann gilt:T (n) = O(n log n).

Beweis. Man fixiere k mitA[n] = xk. Wahrend der Ausfuhrung von Quicksort(A, 1, n)wird Quicksort rekursiv auf Teilarrays der Lange k − 1 und n− 1− k aufgerufen.Fur 1/n-tel aller mit x1, . . . , xn gefullten Arrays A gilt A[n] = xk. Daher gilt:

T (n) ≤ 1

n

n∑k=1

(T (k − 1)︸︷︷︸rek. Aufruf

links

+T (n− k)︸︷︷︸rek. Aufruf

rechts

) + cn︸︷︷︸Laufzeit der

Partitionierung

=2

n

n−1∑k=0

T (k − 1) + cn

≤ 2

n

n−1∑k=2

T (k − 1) + dn

wobei hier c und d positive Konstante mit c ≤ d sind.

37


Wir zeigen per Induktion nach n, dass es a > 0 existieren mit T (n) ≤ an log n furalle n ≥ 2. Die Behauptung gilt offensichtlich fur n = 2, falls a > 0 groß genug ist.Sei n ≥ 2 und es gelte T (k) ≤ ak log k fur alle k = 2, ..., n− 1. Dann gilt:

T (n) ≤ 2

n

n−1∑k=2

T (k) + dn

≤ 2

n

n−1∑k=1

ak log2 k + dn

=2a

n

n∑k=2

k log2 k + dn

Aus Lemma 3.28 folgt

T (n) ≤ 2a

n

(1

2n2 log n− 1

8n2

)+ dn

= an log2 n−a

4n+ dn

≤ an log n,

falls a groß genug gewahlt wird, sodass a ≥ 4d gilt.

Um die Situation zu vermeiden, dass Quicksort auf gewissen entarteten Arrays lang-sam wird, kann man die randomisierte Version von QuickSort benutzen. Bei dieserwird das Pivot-Elemente durch zufallige (gleichmaßig verteilte) Wahl einer Kompo-nente des zugrundeliegenden Arrays fixiert. Es kann gezeigt werden, dass die ran-domisierte Version jedes gegebene Array mit n paarweise verschiedenen Elementein der erwarteten Zeit O(n log n) sortiert. Der randomisierte QuickSort ist in derPraxis sehr beliebt

Bemerkung 3.30. Endrekursion (engl.: Tail recursion) ist, wenn ein rekursiverAufruf der letzte Aufruf der rekursiven Funktion ist. Dieser Aufruf kann durch eineiterative Struktur ersetzt werden.

4 Verkettete Datenstrukturen

Diese kleine Kapitel hat zwei Ziele. Das Hauptziel ist verkette Datenstrukturen zudiskutieren. Nebenbei werden wir aber auch sehr einfache aber auch sehr nutzlicheDatenstrukturen Stack und Schlange einfuhren, welche wir auch einige Algorithmendes zweiten Teils des Kurses als Hilfsmittel benutzen werden.

4.1 Stack, Schlange und Deque als Arrays

In diesem Abschnitt verwenden wir die Indexierung der Arrays ab 0, weil fur dieUmsetzung der Deques bequemer ist.

38


Ein Stack (auch ein Stapel genannt) ist eine Liste mit Einschrankung der Zugriffs-liste. Man kann das letzte Element der Liste mit der Operation Pop entfernen undzuruckgeben und ein gegebenes Element als letztes Element zur Liste hinzufugen.Auf der Basis eines Arrays A kann ein Stack mit der Verwendung eines Zusatzat-tributs Top[A] umgesetzt werden. Hierbei ist Top[A] die Position fur ein neuesElement der Liste. Beim Pop fuhrt man also Top[A] = Top[A] − 1 aus uns gibtdann das Element A[Top[A]] zuruck. Der Wert Top[A] ist genau die Anzahl derElemente auf dem Stack. Bei Top[A] hat man somit einen Stack-Unterlauf-Fehler.Die Operation Push fur ein Element x ist ebenfalls sehr einfach umsetzbar. Wirmachen die Zuweisung A[Top[A]] = x und erhohen dann Top[A] um eins. WennTop[A] = Lange[A] gilt, ist unser Stack voll, weil bei unserer Array-basierten Um-setzung ein Stack hochstens Lange[A] Elemente speichern kann. Ist der Stack voll,so wurde eine weitere Push-Operation zu einem Stack-Uberlauf-Fehler fuhren.

Eine Schlange (auf Englisch, queue) ist eine Liste mit der folgenden Einschrankungder Zugriffsrechte. Man kann das erste Element der Liste mit einer Operation Dequeaus der Liste entfernen und zuruckgeben, und ein gegebenes Element x zum Endeder Liste durch die Operation Enqueue hinzufugen. Wir prasentieren eine Array-basierte Umsetzung der Schlange, die auf der Vorstellung beruht, dass die Elementedes Arrays A ein ‘Kreis bilden’; die Elemente A[0], . . . , A[Lange[A] − 1] kommenhintereinander in diesem Kreis und nach A[Lange[A]− 1] kommt wieder A[0]. DieElemente der Schlange sollen nun hintereinander folgende Elemente dieses Krei-ses Sein. Wir fuhren ein Attribut Kopf[A] ein, durch welches wir die Position desersten Elements (des sogenannten Kopfs der Schlange) merken und ein AttributGroße[A], durch welches wir die Anzahl der Element in der Schlange merken. Beimdeque[A] setzt man x := A[Kopf[A]], setzt anschließend Kopf[A] := (Kopf[A] +1) mod Lange[A] und gibt dann x zuruck. Ist zum Beginn der Ausfuhrung vondeque die Schlange leer, so hat man naturlich einen Unterlauf. Die Berechnung mo-dulo die Lange ist notig, weil die Elemente sich ‘im Kreis befinden’. Beim Enqueuefur ein gegebenes Element x hat man bei Große[A] = Lange[A] naturlich einenUnterlauf. Ansonsten enthalt i := (Kopf[A] + Große[A]) mod Lange[A] die Posi-tion fur das neue Element x. Man macht also fur dieses i die Zuweisung A[i] = xund erhoht anschließend Große[A] um eins.

Eine Deque (Englische Abkurzung fur double-ended queue) ist eine Mischung ausStack und Schlange. Es ist eine Liste, bei der man eine neues Element vorne sowiehinten hinzufugen kann (mit Pushleft und Pushright) und das erste sowie letzteElement hinzufugen kann (mit Popleft und Popright). Array-basierend kanneine Dequeue analog zu Schlangen umgesetzt werden. Die Operation Popleft istgenau dequeue und Pushright ist genau enqueue. Nun kann sich relativ leichtuberlegen, wie man die beiden anderen Operationen umsetzt.

4.2 Stack und Schlange als einfach verkettete Listen

Ich erinnere kurz daran, dass die Zeiger Variablen sind, die Adressen enthalten. Istz ein Zeiger auf ein Objekt so bezeichnen wir als Objekt z das Objekt. Wenn nunObjekt[z] ein Attribut Attr hat, so schreiben wir die kurze Schreibweise Attr[z]an der Stelle Attr[Objekt[z]]. Ist x ein Objekt, so bezeichnen wir als Addr[x]die Adresse von x. Mit Hilfe von Zeigern arbeitet man mit dem sogenannten dyna-

39


mischen Speicher. Fur den Dynamischen Speicher hat man zwei Grundoperationen:Speicher fur ein Objekt reservieren. Die Ruckgabe dieser Operation ist die Adressedes neu erzeugten Objekts. Erganzend dazu hat man die Operation, mit der mandas Objekte unter gegebener Adresse loscht und den von diesem Objekt reserviertenSpeicher wieder freigibt.

Adressen verwendet man oft implizit oder explizit beim Aufbau neuer Datentypenund Umsetzung von Algorithmen. Wir bemerken dabei, dass ein Index i einer Ar-raykomponente ist die Adresse dieser Komponente innerhalb des Arrays. Wenn wiralso in einem Algorithmus Komponenten-Indizes eines Arrays fuhren, benutzten wirim Wesentlichen auch Adressen.

Wir fuhren in diesem Abschnitt auf Zeigern basierend die sogenannten einfach ver-ketteten Listen ein, wobei wir mit einfach verketteten Listen nun Stacks und Schlan-gen umsetzten. Die einfachen verketteten Listen setzten sich aus den sogenanntenKnoten zusammen, wobei jeder Knoten k ein Element der Liste enthalt (wir nen-nen dieses Element Wert[k]) und einen Zeiger Nachf[k] auf einen Nachbarn. EinNullzeiger wird als 0 bezeichnet, es ist ein Zeiger ins nichts.

Bei einem Stack auf der Basis von einfach verketteten Listen ist der Stack durch einenZeiger T auf seinen ‘obersten’ Knoten gegeben. Ist der Stack leer so gilt T = 0. IstT 6= 0, so ist Nachf[T ] der zeiger auf den zweit-obersten Knoten usw. Wenn maneine neues Element x hinzufugen mochte, so kann man einen Knoten erzeugen undeiner Variablen k die Adresse dieses Knoten speichern. Dann setzt man Wert[k] :=x und fugt den neuen Knoten zum Stack folgendermaßen hinzu. Nach links[k] := Tist der Nachfolger von Objekt[k] der aktuell oberste Knoten. Mit T := k zeigt dannT auf den neu erzeugten Knoten, der die oberste Position im Stack aufnimmt.

Die Pop-Operation wird folgendermaßen umgesetzt. Man fuhrt eine Zeiger-Variablek ein und setzt k := T . Somit zeigt nun k auf den obersten Knoten des Stacks.Durch L := nachf[L] wird Objekt[k] aus dem Stack entfernt. Anschließend kannman durch x := Wert[k] den unter der Adresse k gespeicherten Wert abrufen unddann den Knoten Objekt[k] loschen (d.h., den fur den Knoten reservierten Speicherwieder freigeben).

Zur Umsetzung von Schlange mit Hilfe einfach verketteten Listen braucht man zweiZeiger: einen Zeiger E auf den ersten Knoten der Schlange und einen Zeiger A auf denletzten Knoten der Schlange. Hierbei ist nachf[A] der Zeiger auf den zweiten Knotender Schlange, usw. und nachf[E] = 0. Die Operation enque fur eine neues Element(falls das Element bereits im Knoten aufgehoben hat, auf welchen ein Zeiger k zeigt)geht durch nachf[E] := k und E := nachf[E]. Es sei darauf hingewiesen, dass manam Anfang nachf[k] := 0 setzten muss. Bei deque fuhrt man einen neuen Zeigerk ein setzt man k := A, um den Zugriff auf den aktuellen ersten Knoten nicht zuverlieren, versetzt dann durch A := nachf[A] den Zeiger vom ersten auf den zweitenKnoten. Anschließend kann der Wert x := Wert[k] abgerufen und zuruckgegebensowie der Knoten unter der Adresse k geloscht werden.

4.3 Deque als eine doppelt verkette Liste

Fur eine effiziente Umsetzung von Deque als verkettete Datenstruktur braucht mandoppelt verkettete Listen. Bei doppelt verketteten Listen ‘merkt’ ein Knoten k der

40


Liste zwei Nachbarn: den Nachfolger nachf[k] und den Vorganger vorg[k]. Beieiner zyklischen Reihung, in der erste Knoten Nachfolger des letzten Knoten undder erste Knoten der Vorganger des ersten Knoten ist, reicht es einen Zeiger A aufden Anfangsknoten (also den ersten Knoten) zu fuhren.

Nun kann man sich uberlegen, wie man die beiden Push-Operationen (von linksund rechts) sowie die Pop-Operationen (von links und rechts) umsetzt. Durch diedoppelte Verkettung und die beidseitige Verlinkung des Anfangs- und Endknotenskann man auf den Anfangs- sowie Endknoten in der Zeit O(1) zugreifen. Dadurch istdie effiziente Umsetzung der vier benotigten Operationen ziemlich unproblematisch.

4.4 Zeiger-basierte binare Baume

5 Berechnungen mit reellen Zahlen

In diesem ganz kurzen Kapitel wollen wir in wenigen Worten auf Berechnungen mitreellen Zahlen eingehen. Viel detaillierter wird diese Thematik in den numerischenVorlesungen (insb. in der Einfuhrung in die Numerik im 4. Semester) diskutiert. DasKapitel basiert auf Kapiteln 4 und 5 des Buchs von Vygen und Hougardi.

5.1 Darstellung reeller Zahlen in einem Stellenwertsystem

Theorem 5.1. Sei b ≥ 2 naturliche Zahl. Dann besitzt jede reelle Zahl x 6= 0 eineeindeutige Darstellung

x = σ · bE ·∞∑i=0

zib−i (5.1)

mit:

• σ ∈ −1, 1,

• E ∈ Z,

• zi ∈ 0, . . . , b− 1 fur alle i ∈ N0.

• z0 6= 0,

• zi 6= b− 1 fur unendlich viele i ∈ N0.

Die Darstellung (5.1) heißt die normalisierte Darstellung von x im Stellenwertsystemzur Basis b. Wenn fur ein m ∈ N man zi = 0 fur alle i ≥ m hat, so heißt xdie m-stellige normalisierte Gleitkommazahl zur Basis b. Die Summe

∑∞i=0 zib

−i =∑m−1i=0 zib

−i heißt die Mantisse von x.

Die im Rechner benutzten Datentypen fur Gleitkommazahlen sind durch die Vorgabevon b, m und eines Berecheis Emin, . . . , Emax definiert. Beim IEEE-Standard istdouble durch b = 2,m = 53 und E ∈ −1022, . . . , 1023 definiert.

41


Beispiel 5.2.

1

3= (0,01)2,

8,1 = (1000,00011)2.

Man kann also 13 sowie 8,1 nur annahernd als eine m-stellige Gleitkommazahl zur

Basis 2 darstellen (beachte: b = 2 ist die Standardbasis im Computer).

5.2 Rundungsfehler

Seien a, a′ ∈ R. Der Wert |a′−a| heißt der absolute Fehler der Naherung des Wertes

a mit dem Wert a′. Gilt a 6= 0, so heißt∣∣∣a′−aa

∣∣∣ der relative Fehler der Naherung von

a mit a′.

Fur eine nichtleere endliche Menge F positiver reeller Zahlen. Wir nennen den Wert

g := supx∈[minF,maxF ]

infy∈F

∣∣∣∣y − xx∣∣∣∣

die Genauigkeit der Zahlen F .

Theorem 5.3. Ist b ∈ N mit b ≥ 2, m ∈ N und Emin < Emax so ist die Genauigkeitvon

F =

bE

m−1∑i=0

zib−i : z0 ∈ 1, . . . , b− 1, z1, . . . , zm−1 ∈ 0, . . . , b− 1, E ∈ Emin, . . . , Emax

gleich 11+2bm−1 .

Der Wert aus dem vorigen Theorem heißt die Maschinengenauigkeit.

5.3 Fehler der Gleitkommazahlenarithmetik

Die Besonderheit der Gleichkommazahlen ist, dass die Gleitkommazahlen-Operationennicht genau, sondern mit einem Fehler ausgefuhrt werden. Am Beispiel mit b = 10erklaren: 1, 0,004 und 0,006 bei Mantisse aus 3 Ziffern.

Erstaunlicherweise haben manche Rechenverfahren, die in exakter Arithmetik aquivalentsind (sie berechnen das Gleiche mit ahnlicher Laufzeit usw). sehr unterschiedlicheGenauigkeit in Gleitkomma-Arithmetik. Wenn wir etwa Werte x1 ≥ . . . ≥ xn ≥ 0aufsummieren wollen, so liefert uns die Formel x1 + · · · + xn (vom ersten Ele-ment beginnend aufsummieren) im Allgemeinen ein anderes Ergebnis als die Formelxn + · · ·+ x1 (vom letzten Element beginnend aufsummieren), wenn wir die Werteals Gleitkommazahlen speichern.

5.4 Verfahrensfehler

Ein Verfahrensfehler ist ein Fehler eines Naherungsverfahrens zur Berechnung einerFunktion bzgl. exakter reellen Arithmetik. Etwa wir berechnen annahernd

√x fur po-

sitive reelle Werte x im Bereich [1, 2] mit dem Verfahren y0 = x und yi := 1yi−1

+yi−1

42


fur i = 1, 2, 3. Hierbei ist der Wert y3 die Ruckgabe. Nun kann man sich uberlegen,was der maximale (absoluter bzw. relativer) Fehler dieses Naherungsverfahrens ist,unter der Voraussetzung, dass die arithmetischen Operationen exakt ausgefuhrt wer-den. Dies ist dann der Verfahrensfehler.

5.5 Datenfehler

Nicht-mathematisch. Bei realen Berechnungen ist die Eingabe in den meisten Situa-tion bereits ungenau. Z.B., die Eingabe, die aus Experimenten stammt.

5.6 Modellierungsfehler

Das mathematisches Modell fur gegebene Situation (etwa in der physikalischen Welt)ist ebenfalls eine annahernde Beschreibung der zugrundeliegenden Situation. Durchdie Ungenauigkeit der Modellierung entstehen somit weitere Fehler.

43

Documents

Algorithmische Mathematik I · Algorithmische Mathematik I 22. Januar 2018 (14:19) 1 Mathematische Grundlagen 1.1 Mathematische Grundbegri e Wir werden die folgenden Begri e benutzen: