Skip to main content
main-content

Über dieses Buch

Algorithmen spielen eine immer wichtigere Rolle in fast allen Bereichen der Mathematik.

Dieses Lehrbuch eignet sich für den Studienbeginn und stellt den klassischen Vorlesungen über Analysis und Lineare Algebra eine dritte mathematische Grundvorlesung zur Seite, die die Autoren in den letzten Jahren mehrfach an der Universität Bonn gehalten haben.

Ziel dieses Buches ist die Vermittlung grundlegender mathematischer Fähigkeiten, besonders 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.

In dieser Neuauflage sind mehr als 150 Übungsaufgaben hinzugefügt worden.

Inhaltsverzeichnis

Frontmatter

Kapitel 1. Einleitung

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.
Stefan Hougardy, Jens Vygen

Kapitel 2. Darstellungen ganzer Zahlen

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^{32}\) verschiedene Zahlen darstellbar. Wir lernen in diesem Kapitel, wie ganze Zahlen gespeichert werden.
Stefan Hougardy, Jens Vygen

Kapitel 3. Rechnen mit ganzen Zahlen

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.
Stefan Hougardy, Jens Vygen

Kapitel 4. Approximative Darstellungen reeller Zahlen

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.
Stefan Hougardy, Jens Vygen

Kapitel 5. Rechnen mit Fehlern

Bei numerischen Berechnungsproblemen muss man immer mit Fehlern rechnen. Wir untersuchen die verschiedenen Fehlerquellen, die Fehlerforpflanzung, numerische Stabilität, Näherungsverfahren und deren Konvergenzgeschwindigkeit.
Stefan Hougardy, Jens Vygen

Kapitel 6. Graphen

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.
Stefan Hougardy, Jens Vygen

Kapitel 7. Einfache Graphenalgorithmen

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.
Stefan Hougardy, Jens Vygen

Kapitel 8. Sortieralgorithmen

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).
Stefan Hougardy, Jens Vygen

Kapitel 9. Optimale Bäume und Wege

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.
Stefan Hougardy, Jens Vygen

Kapitel 10. Matching und Netzwerkflüsse

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.
Stefan Hougardy, Jens Vygen

Kapitel 11. Gauß-Elimination

Wir beschäftigen uns in diesem Kapitel mit der Lösung linearer Gleichungssysteme, insbesondere der Gauß-Elimination. Wir untersuchen das Verhalten bei exakter Rechnung mit rationalen Zahlen sowie beim Rechnen mit Maschinenzahlen.
Stefan Hougardy, Jens Vygen

Backmatter

Weitere Informationen

Premium Partner

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.
Jetzt gratis downloaden!

Bildnachweise