Gegenstand der Algorithmischen Mathematik ist die Konstruktion und Analyse effizienter Algorithmen zur Lösung mathematischer Problemstellungen mit Hilfe des Computers. Sie ist damit im Bereich der Angewandten Mathematik anzusiedeln.Ziel dieses Lehrbuchs ist es, Studierenden der Mathematik einen Einblick in unterschiedliche Gebiete der Angewandten Mathematik und in deren algorithmische Aspekte zu geben. Hierbei liegt das Hauptaugenmerk auf Graphentheorie, Numerik und Wahrscheinlichkeitstheorie.
Die einschlägige Lehrbuchliteratur befasst sich zumeist jeweils nur mit einem dieser Gebiete. Im Gegensatz dazu bemüht sich dieses Buch um eine ganzheitliche Darstellung von Graphentheorie, Numerik und Wahrscheinlichkeitstheorie und arbeitet so ihre Gemeinsamkeiten und ihr Zusammenspiel heraus. Gerade die Verschmelzung der unterschiedlichen Gebiete der Angewandten Mathematik gehört zu einer modernen Ausbildung der Mathematik, denn es ist heutzutage unerlässlich, dass ein Numeriker ein grundlegendes Wissen über diskrete Algorithmen besitzt oder ein Stochastiker etwas von numerischer Simulation versteht.
Dieses Buch eignet sich für Studierende, aber auch für alle, die ihr Wissen in Algorithmischer Mathematik auffrischen oder vertiefen wollen.
Author(s): Michael Multerer; Helmut Harbrecht
Edition: 1
Publisher: Springer Spektrum
Year: 2022
Language: German
Pages: 488
City: Berlin, Heidelberg
Tags: Algorithmen;Graphentheorie;Numerik;Stochastik;Probabilistik
Vorwort
Inhaltsverzeichnis
1 Zahlendarstellung im Computer
1.1 Zahlensysteme
1.2 Vorzeichen-Betrag-Darstellung
1.3 Komplementdarstellung
1.4 Festkommadarstellung
1.5 Gleitkommadarstellung
1.6 Genauigkeit der Gleitkommadarstellung
2 Fehleranalyse
2.1 Gleitkommaarithmetik
2.2 Auslöschung
2.3 Vorwärts- und Rückwärtsanalyse
2.4 Kondition und Stabilität
3 Sortieren
3.1 Sortierproblem
3.2 Mergesort
3.3 Quicksort
3.4 Heapsort
3.5 Untere Schranken für das Sortierproblem
4 Graphen
4.1 Grundbegriffe
4.2 Zusammenhang
4.3 Zyklische Graphen
4.4 Bäume
4.5 Graphendurchmusterung
4.6 Starker Zusammenhang
5 Graphenalgorithmen
5.1 Kürzeste-Wege-Probleme
5.2 Netzwerkflussprobleme
5.3 Bipartites Matching
6 Vektoren und Matrizen
6.1 Grundbegriffe
6.2 Vektor- und Matrixnormen
6.3 Dünnbesetzte Matrizen
6.4 Implementierung von Graphen
6.5 Irreduzible Matrizen
7 Lineare Gleichungssysteme
7.1 Kondition linearer Gleichungssysteme
7.2 LR-Zerlegung
7.3 Block-LR-Zerlegung
7.4 LR-Zerlegung mit Spaltenpivotisierung
7.5 LR-Zerlegung mit totaler Pivotisierung
7.6 Cholesky-Zerlegung
8 Matrixapproximationsverfahren
8.1 Singulärwerte
8.2 Adaptive Kreuzapproximation
8.3 Pivotisierte Cholesky-Zerlegung
9 Graphenbasierte Löser
9.1 Motivation
9.2 Cholesky-Zerlegung und Graphen
9.3 Nested Dissection
10 Dreitermrekursion
10.1 Theoretische Grundlagen
10.2 Miller-Algorithmus
10.3 Orthogonalpolynome
10.4 Verfahren der konjugierten Gradienten
11 Wahrscheinlichkeitsräume
11.1 Mengen
11.2 Zufällige Ereignisse
11.3 Rechnen mit zufälligen Ereignissen
11.4 Wahrscheinlichkeitsverteilungen
11.5 Kombinatorik
12 Bedingte Wahrscheinlichkeiten und Unabhängigkeit
12.1 Definition der bedingten Wahrscheinlichkeit
12.2 Multiplikationsregeln
12.3 Stochastische Unabhängigkeit
12.4 Produktexperimente
13 Diskrete Verteilungen
13.1 Zufallsvariablen
13.2 Verteilungsfunktionen
13.3 Erwartungswert
13.4 Varianz
13.5 Schwaches Gesetz der großen Zahlen
13.6 Binomialverteilung
13.7 Poisson-Verteilung
13.8 Hypergeometrische Verteilung
14 Stetige Verteilungen
14.1 Dichtefunktionen
14.2 Erwartungswert und Varianz
14.3 Gleichverteilung
14.4 Exponentialverteilung
14.5 Normalverteilung
15 Stochastische Simulationsverfahren
15.1 Pseudozufallszahlen
15.2 Simulation diskreter Verteilungen
15.3 Verwerfungsmethode
15.4 Inversionsmethode
15.5 Monte-Carlo-Verfahren
16 Markov-Ketten
16.1 Grundlagen
16.2 Simulation von Markov-Ketten
16.3 Irreduzible und aperiodische Markov-Ketten
16.4 Stationäre Verteilungen
16.5 Markov-Ketten-Monte-Carlo-Verfahren
17 Polynominterpolation
17.1 Lagrange-Interpolation
17.2 Neville-Schema
17.3 Newtonsche Interpolationsformel
17.4 Tschebyscheff-Interpolation
18 Trigonometrische Interpolation
18.1 Theoretische Grundlagen
18.2 Schnelle Fourier-Transformation
18.3 Zirkulante Matrizen
19 Splines
19.1 Spline-Räume
19.2 Kubische Splines
19.3 B-Splines
19.4 Interpolationsfehler
20 Wavelet- und Multilevelbasen
20.1 Haar-Transformation
20.2 Haar-Wavelets
20.3 Walsh-Transformation
20.4 Hierarchische Basis
21 Numerische Quadratur
21.1 Trapezregel
21.2 Dünngitter-Quadratur
21.3 Newton-Côtes-Formeln
21.4 Gauß-Quadratur
22 Lineare Ausgleichsprobleme
22.1 Normalengleichungen
22.2 QR-Zerlegung
22.3 Methode der Orthogonalisierung
23 Iterative Lösungsverfahren
23.1 Fixpunktiterationen
23.2 Iterationsverfahren für lineare Gleichungssysteme
23.3 Newton-Verfahren
Literatur
Stichwortverzeichnis
