nach oben

2016 | Buch

Kapitel lesen Erstes Kapitel lesen

Algorithmische Mathematik

verfasst von: Stefan Hougardy, Jens Vygen

Verlag: Springer Berlin Heidelberg

Buchreihe : Springer-Lehrbuch

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

Dieses Lehrbuch vermittelt grundlegende mathematische Fähigkeiten im Hinblick auf Entwurf und Analyse von Algorithmen, sowie deren Implementierung. Neben einigen fundamentalen Algorithmen (z.B. Sieb des Eratosthenes, Euklidischer Algorithmus, Sortieralgorithmen, Algorithmen auf Graphen, Gauß-Elimination) werden auch elementare Datenstrukturen, graphentheoretische Grundlagen und numerische Fragen behandelt. Zudem werden grundlegende Programmierkenntnisse vermittelt und es wird gezeigt, wie man Algorithmen in C++ implementiert.

Das Buch eignet sich besonders für den Studienbeginn und stellt den klassischen Vorlesungen über Analysis und Lineare Algebra die Algorithmische Mathematik als dritte Grundvorlesung zur Seite. Diese Vorlesung haben die Autoren in den letzten Jahren mehrfach an der Universität Bonn gehalten.

Inhaltsverzeichnis

Frontmatter

1. Einleitung

Zusammenfassung

In diesem Kapitel werden wir einige grundlegende Begriffe einführen und erste Algorithmen vorstellen, analysieren und in C++ implementieren. Zudem werden wir sehen, dass nicht alles berechenbar ist.

Jens Vygen, Stefan Hougardy

2. Darstellungen ganzer Zahlen

Zusammenfassung

Ein Computer speichert alle Informationen mit Bits, die jeweils 0 oder 1 sein können. Ein Byte besteht aus acht Bits. Wir sind anfangs davon ausgegangen, dass wir alle auftretenden natürlichen Zahlen im Datentyp int speichern können. Tatsächlich ist das nicht der Fall. Eine Variable vom Typ int entspricht einer Folge von normalerweise 4 Bytes. Damit sind natürlich nur 2³² verschiedene Zahlen darstellbar. Wir lernen in diesem Kapitel, wie ganze Zahlen gespeichert werden.

Jens Vygen, Stefan Hougardy

3. Rechnen mit ganzen Zahlen

Zusammenfassung

Wir haben in Kap. 1 die Grundrechenarten als elementare Rechenoperationen bezeichnet und angenommen, dass sie in konstanter Zeit durchgeführt werden können. Dies ist oft eine praktische Annahme, die allerdings für beliebig große Zahlen natürlich nicht der Realität entspricht. Wir wollen sehen, wie schnell man tatsächlich mit ganzen Zahlen rechnen kann. Elementare Rechenschritte (im engeren Sinne) sind dabei nur Rechenoperationen und Vergleiche auf ganzen Zahlen beschränkter Größe.

Moderne Computer können Rechenoperationen auf Zahlen mit bis zu 64 Bit in wenigen Taktzyklen durchführen. Für die asymptotische Laufzeit ist dies aber hier irrelevant, da man alles aus Rechenoperationen mit nur einem Bit zusammensetzen kann.

Jens Vygen, Stefan Hougardy

4. Approximative Darstellungen reeller Zahlen

Zusammenfassung

Durch die Kombination der Klassen LargeInt (Programm 2.11) und Fraction (Programm 2.10) – erweitert um die noch fehlenden Operationen – kann man mit rationalen Zahlen rechnen, ohne Rundungsfehler zu machen. Allerdings sind die einzelnen Rechenoperationen vergleichsweise langsam, weil Zähler und Nenner – auch wenn man immer mit dem Euklidischen Algorithmus kürzt – groß werden können.

Wesentlich schneller ist das Rechnen mit Standarddatentypen wie double; allerdings muss man hier Rundungsfehler in Kauf nehmen und kontrollieren.

Komplexe Zahlen lassen sich natürlich (näherungsweise) speichern, indem man (Näherungen von) Real- und Imaginärteil speichert, ähnlich wie man rationale Zahlen als Paare ganzer Zahlen (Zähler und Nenner) darstellen kann. Analog zur Klasse Fraction kann man auch hierfür eine Klasse definieren. Die C++-Standardbibliothek enthält sogar schon einen Typ complex<double>, den man für komplexe Zahlen benutzen kann. Wir beschränken uns im Folgenden der Einfachheit halber auf reelle Zahlen; alles überträgt sich aber natürlich direkt auf komplexe Zahlen.

Jens Vygen, Stefan Hougardy

5. Rechnen mit Fehlern

Zusammenfassung

Bei numerischen Berechnungsproblemen muss man immer mit Fehlern rechnen. Wegen der nur endlich vielen Maschinenzahlen entstehen Fehler nicht nur bei der Eingabe von Daten (zum Beispiel ist die Zahl 0,1 nicht exakt mit endlich vielen Stellen binär darstellbar; vgl. Beispiel 4.2), sondern auch bei den elementaren Rechenoperationen $+$, $-$, $\cdot\,$, $/$. Auch die gewünschte Ausgabe kann eine nicht darstellbare Zahl sein. Man unterscheidet drei Arten von Fehlern:

Jens Vygen, Stefan Hougardy

6. Graphen

Zusammenfassung

Sehr viele diskrete Strukturen können durch Graphen beschrieben werden. Auch in unzähligen Anwendungen tauchen Graphen auf natürliche Weise auf. Daher bilden Graphen die wohl wichtigste Struktur der Diskreten Mathematik.

Jens Vygen, Stefan Hougardy

7. Einfache Graphenalgorithmen

Zusammenfassung

Wir werden nun erste Graphenalgorithmen kennen lernen. Dabei wird es darum gehen, einen Graphen zu „erkunden“ und zum Beispiel festzustellen, welche Knoten von einem bestimmten Ausgangsknoten aus erreichbar sind. Die vorgestellten Algorithmen liefern aber noch weitere Informationen und haben zahlreiche Anwendungen.

Jens Vygen, Stefan Hougardy

8. Sortieralgorithmen

Zusammenfassung

Sehr oft müssen gespeicherte Daten sortiert werden. Hierfür gibt es im Wesentlichen zwei Gründe: zum einen arbeiten bestimmte Algorithmen Objekte in einer bestimmten Reihenfolge ab, zum anderen kann man in einem sortierten Datenbestand mit random access einzelne Objekte viel schneller finden (mit binärer Suche, Algorithmus 5.2).

Jens Vygen, Stefan Hougardy

9. Optimale Bäume und Wege

Zusammenfassung

In der Kombinatorischen Optimierung sucht man in einer endlichen Menge von Objekten mit einer kombinatorischen Struktur ein optimales Element. Die Objekte (d. h., die zulässigen Lösungen) können meist als Teilmengen einer endlichen Grundmenge U repräsentiert werden. Oft ist U die Kantenmenge eines Graphen. Die Objekte können dann z. B. s-t-Wege (für gegebene Knoten s und t) oder aufspannende Bäume sein; diese beiden Fälle werden wir gleich betrachten. Hat man eine Gewichtsfunktion $c\colon U\to{\mathbb{R}}$, so heißt eine zulässige Lösung $X\subseteq U$ optimal, wenn ihr Gewicht (man sagt auch: ihre Kosten) $c(X):=\sum_{u\in X}c(u)$ minimal ist.

Die in Kap. 6 vorgestellte Klasse Graph (Programm 6.29) ist auch für gewichtete Graphen ausgelegt. Die Funktion add_edge hat ein optionales drittes Argument, mit dem das Kantengewicht angegeben werden kann.

Sei G ein Graph mit Kantengewichten $c\colon E(G)\to{\mathbb{R}}$. Für einen Teilgraphen H von G bezeichnen wir mit $c(E(H))=\sum_{e\in E(H)}c(e)$ das Gewicht von H; manchmal spricht man auch von Kosten oder Länge.

Jens Vygen, Stefan Hougardy

10. Matching und Netzwerkflüsse

Zusammenfassung

In diesem Kapitel wollen wir zwei weitere grundlegende kombinatorische Optimierungsprobleme lösen: maximale Matchings in bipartiten Graphen und maximale Flüsse in Netzwerken. Es wird sich herausstellen, dass das erste Problem ein Spezialfall des zweiten ist. Insofern ist nicht überraschend, dass eine grundlegende Technik, augmentierende Wege, bei beiden der Schlüssel zur Lösung ist.

Jens Vygen, Stefan Hougardy

11. Gauß-Elimination

Zusammenfassung

Wir beschäftigen uns in diesem Kapitel mit der Lösung linearer Gleichungssysteme, das heißt Systeme der Form

$$\begin{array}[]{ccccccccc}\alpha_{11}\xi_{1}&+&\alpha_{12}\xi_{2}&+&\ldots&+&\alpha_{1n}\xi_{n}&=&\beta_{1}\\ \vdots&&&&&&\vdots&&\vdots\\ \alpha_{m1}\xi_{1}&+&\alpha_{m2}\xi_{2}&+&\ldots&+&\alpha_{mn}\xi_{n}&=&\beta_{m}\end{array}$$

(oder kurz $Ax=b$), wobei $A=(\alpha_{ij})_{1\leq i\leq m,\,1\leq j\leq n}\in{\mathbb{R}}^{m\times n}$ und $b=(\beta_{1},\ldots,\beta_{m})^{{\scriptscriptstyle\top}}\in{\mathbb{R}}^{m}$ gegeben sind und $x=(\xi_{1},\ldots,\xi_{n})^{{\scriptscriptstyle\top}}\in{\mathbb{R}}^{n}$ gesucht ist. Mit anderen Worten: wir lösen folgendes numerische Berechnungsproblem:

Aus der Linearen Algebra wissen wir, dass dieses Problem eng verwandt dazu ist, den Rang, und im Falle $m=n$ die Determinante und – falls A nichtsingulär ist – die Inverse $A^{-1}$ von A zu berechnen; vgl. die Box Rang und Determinante. Alle diese Probleme löst das Gaußsche Eliminationsverfahren, das wir in diesem Kapitel studieren. Wir haben Problem Ch11.I1.ix1 für reelle Zahlen definiert, aber man kann alles auf beliebige Körper (zum Beispiel $\mathbb{C}$) erweitern, sofern man darin rechnen kann.

Jens Vygen, Stefan Hougardy

Backmatter

Titel: Algorithmische Mathematik
verfasst von: Stefan Hougardy
Jens Vygen
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-662-47014-5
Print ISBN: 978-3-662-47013-8
DOI: https://doi.org/10.1007/978-3-662-47014-5