nach oben

2007 | Buch

Kapitel lesen Erstes Kapitel lesen

Mathematik für Informatiker

Band 1: Diskrete Mathematik und Lineare Algebra

verfasst von: Gerald Teschl, Susanne Teschl

Verlag: Springer Berlin Heidelberg

Buchreihe : eXamen.press

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

Einloggen, um Zugang zu erhalten

Über dieses Buch

In diesem Lehrbuch werden die mathematischen Grundlagen exakt und dennoch anschaulich und gut nachvollziehbar vermittelt. Sie werden durchgehend anhand zahlreicher Musterbeispiele illustriert, durch Anwendungen in der Informatik motiviert und durch historische Hintergründe oder Ausblicke in angrenzende Themengebiete aufgelockert.

Am Ende jedes Kapitels befinden sich Kontrollfragen, die das Verständnis testen und typische Fehler bzw. Missverständnisse ausräumen. Zusätzlich helfen zahlreiche Aufwärmübungen (mit vollständigem Lösungsweg) und weiterführende Übungsaufgaben das Erlernte zu festigen und praxisrelevant umzusetzen. Dieses Lehrbuch ist daher auch sehr gut zum Selbststudium geeignet.

Ergänzend wird in eigenen Abschnitten das Computeralgebrasystem Mathematica vorgestellt und eingesetzt, wodurch der Lehrstoff visualisiert und somit das Verständnis erleichtert werden kann.

Inhaltsverzeichnis

Frontmatter

Grundlagen

1. Logik und Mengen

Auszug

Die Logik ist ein wichtiges Hilfsmittel in der Informatik. Sie wird beim Entwurf von Programmen gebraucht oder um die Korrektheit von Algorithmen zu verifizieren. Sie hilft bei der Beantwortung von Fragen wie „Hat die Switch-Anweisung wohl nichts übersehen?“ oder „Arbeitet der Algorithmus wohl in allen Spezialfällen so, wie ich es möchte?“. Die Logik ist notwendig, um Anforderungen eindeutig und widerspruchsfrei zu formulieren. Was ist zum Beispiel die Verneinung von „Jeder Benutzer hat ein Passwort“? Es gibt in der Umgangssprache verschiedene Möglichkeiten, die nach den Regeln der Logik richtige Verneinung ist aber eindeutig: „Es gibt mindestens einen Benutzer, der kein Passwort hat“. (Nicht nur) für Informatiker ist logisch-analytisches Denkvermögen eine wichtige Anforderung, und daher steht die Logik auch am Anfang unseres Weges.

2. Zahlenmengen und Zahlensysteme

Auszug

In diesem Abschnitt werden Ihnen einige vertraute Begriffe begegnen. Wir beginnen mit den natürlichen Zahlen. Sie haben sich historisch einerseits aus der Notwendigkeit zu zählen („Kardinalzahlen“) und andererseits aus dem Bedürfnis zu ordnen („Ordinalzahlen“) entwickelt:

Diskrete Mathematik

3. Elementare Begriffe der Zahlentheorie

Auszug

Erinnern Sie sich an die Division mit Rest aus Satz 2.47: Wenn a ∈ ℤ und m ∈ ℕ, so kann man a in der Form a = q · m + r schreiben, wobei q und r aus ∔ eindeutig bestimmt sind durch die Festlegung 0 ≤ r < m. Diese Zahl r heißt Rest der Division und man verwendet dafür auch die Schreibweise r = a mod m. Beispiel: 17 mod 5 = 2, in Worten: „Der Rest der Division von 17 durch 5 ist 2“ oder kurz „17 modulo 5 ist 2“.

4. Polynomringe und endliche Körper

Auszug

Erinnern Sie sich an die Definition eines Körpers in Abschnitt 3.2. Das ist eine Menge $ \mathbb{K} $ gemeinsam mit zwei Verknüpfungen, Addition und Multiplikation genannt, die bestimmte Eigenschaften erfüllen. Insbesondere gibt es für jedes Element a des Körpers ein inverses Element −a bezüglich der Addition und für jedes a ≠ 0 ein Inverses a⁻¹ bezüglich der Multiplikation. Paradebeispiele für Körper mit unendlich vielen Elementen sind ℚ, ℝ oder ℂ.

5. Relationen und Funktionen

Auszug

Relationen sind ein mathematisches Hilfsmittel, um Beziehungen zwischen einzelnen Objekten zu beschreiben. Sie werden zum Beispiel in relationalen Datenbanken und in der theoretischen Informatik (z. B. formale Sprachen) verwendet.

6. Folgen und Reihen

Auszug

Wir haben in Kapitel 2 gesehen, dass wir durch gezieltes Probieren die Zahl √2 beliebig genau durch rationale Zahlen annähern können. Ein effizientes Verfahren hat der griechische Mathematiker Heron im 1. Jh. n. Chr. angegeben: Man beginnt mit einem Näherungswert a₁, etwa a₁ = 2, und wählt einen zweiten Wert b₁ = 2/a₁ = 1, sodass das Rechteck mit den Seiten a₁ und b₁ die Fläche a₁b₁ = 2 hat. Hätten wir den richtigen Wert (nämlich √2) gewählt, so hätten wir ein Quadrat erhalten. So ist aber die eine Seite zu lang und die andere zu kurz. Einen besseren Näherungswert erhalten wir, indem wir den Mittelwert $ a_2 = \tfrac{{a_1 + b_1 }} {2} = \tfrac{1} {2}\left( {a_1 + \tfrac{2} {{a_1 }}} \right) = 1.5 $ wählen. Der nächste Näherungswert wird in gleicher Weise aus dem zweiten Näherungswert berechnet: $ a_3 = \tfrac{1} {2}\left( {a_2 + \tfrac{2} {{a_2 }}} \right) = 1.416666... $ In diesem Sinn geht es weiter:

$$ \begin{gathered} a_4 = \frac{1} {2}(a_3 + \frac{2} {{a_3 }}) = 1.414215... \hfill \\ a_5 = \frac{1} {2}(a_4 + \frac{2} {{a_4 }}) = 1.414213... \hfill \\ \end{gathered} $$

Man erhält eine Folge a₁, a₂, a₃, a₄, a₅, . . . von Näherungswerten. Es kann gezeigt werden, dass dadurch √2 in jeder gewünschten Genauigkeit angenähert werden kann.

7. Kombinatorik

Auszug

Die Kombinatorik untersucht die verschiedenen Möglichkeiten, Objekte anzuordnen bzw. auszuw ählen. Sie ist im 17. Jahrhundert durch Fragestellungen begründet worden, die durch Glücksspiele aufgekommen sind. Viele Abzählprobleme können formuliert werden, indem man geordnete oder ungeordnete Auswahlen von Objekten trifft, die Permutationen bzw. Kombinationen genannt werden. Man kann die Kombinatorik daher auch als die „Kunst des Zählens“ bezeichnen. Sie hilft bei der Beantwortung von Fragen wie: „Wie viele verschiedene Passwörter gibt es, wenn ein Passwort aus mindestens sechs und höchstens acht Zeichen bestehen kann, und wenn davon mindestens eines eine Ziffer sein muss?“ oder „Wie viele Rechenschritte benötigt ein Algorithmus?“ Auch für die Bestimmung von Wahrscheinlichkeiten sind Abzählverfahren unentbehrlich: Die Frage „Wie groß ist die Wahrscheinlichkeit, im Lotto „6 aus 45“ sechs Richtige zu haben?“ führt auf die Frage, wie viele Möglichkeiten es gibt, 6 Zahlen aus 45 auszuwählen.

8. Rekursionen und Wachstum von Algorithmen

Auszug

Viele Abzählprobleme können nicht direkt mithilfe der Methoden gelöst werden, die wir im Kapitel 7 kennen gelernt haben. Ein Beispiel für ein solches Problem ist: Wie viele Möglichkeiten gibt es, Bitfolgen der Länge n zu bilden, die keine aufeinander folgenden 1 enthalten? Wenn wir zum Beispiel n = 3 setzen, dann können wir die erlaubten Bitfolgen leicht anschreiben: 000, 100, 010, 001, 101; es gibt also fünf derartige Folgen. Wie viele gibt es aber zum Beispiel für n = 8 oder n = 12? Es wäre praktisch, eine Formel für allgemeines _n zu haben. Wenn wir mit a_n die Anzahl der erlaubten Bitfolgen der Länge _n bezeichnen, dann werden wir in diesem Kapitel sehen, dass a_n+1 = a_n + a_n−1 ist. Wir können also die gesuchte Anzahl mithilfe einer Rekursion ausdrücken. Mithilfe der Anfangsbedingungen a₁ = 2 und a₂ = 3 können wir a₃ = a₂ + a₁ = 5 berechnen, und weiter a₄ = a₃ + a₂ = 8 usw. Es ist sogar möglich, ein nicht-rekursives Bildungsgesetz a_n = f(n) zu finden. Wir erhalten es durch Lösung der Rekursion.

Lineare Algebra

9. Vektorräume

Auszug

Größen wie Geschwindigkeit, Kraft, usw. sind dadurch gekennzeichnet, dass sie nicht nur einen Betrag, sondern auch eine Richtung haben. Sie können durch Pfeile veranschaulicht werden. Man nennt solche Größen auch vektorielle Größen, im Unterschied zu so genannten skalaren Größen, wie etwa einer Temperatur, die durch eine einzige reelle Zahl (einen Skalar) angegeben werden kann. Ein Vektor bzw. die Lage eines Punktes kann im dreidimensionalen Raum durch drei reelle Zahlen, ein 3-Tupel, beschrieben werden (Koordinaten). Die Geometrie des ℝ³ ist unter anderem für Anwendungen in der Computergrafik von großer Bedeutung. Es ist aber sinnvoll, auch 4-Tupel, 5-Tupel, usw., also allgemein n-Tupel zu betrachten: So kann man zum Beispiel den Tagesumsatz von 12 Filialen in einem 12-Tupel zusammenfassen. Um den Wochenumsatz der 12 Filialen zu erhalten, muss man die 12-Tupel koordinatenweise addieren. Um die Mehrwertsteuer zu erhalten, muss man jede Koordinate mit 0.2 (20% Mehrwertsteuer) multiplizieren. Es ist also sinnvoll, allgemein n-Tupel zu betrachten und dafür Rechenoperationen zu definieren. Für 2- oder 3-Tupel lassen sich diese Operationen auch geometrisch veranschaulichen. Für allgemeine n-Tupel ist das nicht möglich, trotzdem ist die geometrische Anschauung für den Spezialfall n = 2 oder n = 3 oft der Schlüssel zur Lösung komplizierter Probleme.

10. Matrizen und Lineare Abbildungen

Auszug

In den meisten Programmiersprachen steht der Datentyp array (engl. für Feld, Anordnung) zur Verfügung. In einem array können mehrere gleichartige Elemente zusammengefasst werden, auf die mithilfe von Indizes zugegriffen wird. Hat jedes Element einen Index, so entspricht der array einem Vektor; wird jedes Element durch zwei Indizes angegeben wird, so führt uns das auf den mathematischen Begriff einer Matrix.

11. Lineare Gleichungen

Auszug

Definition 11.1 Ein lineares Gleichungssystem aus m Gleichungen mit n Unbekannten x₁, x₂, ..., x_n hat die Form

$$ \begin{gathered} a_{11} x_1 + a_{12} x_2 + \cdots + a_{1n} x_n = b_1 \hfill \\ a_{21} x_1 + a_{22} x_2 + \cdots + a_{2n} x_n = b_2 \hfill \\ \vdots \hfill \\ a_{m1} x_1 + a_{m2} x_2 + \cdots + a_{mn} x_n = b_m \hfill \\ \end{gathered} $$

Dabei sind die a_ij und b_i gegebene Zahlen eines beliebigen Körpers $ \mathbb{K} $ . Die a_ij heißen die Koeffizienten des Gleichungssystems. Sind alle b_i gleich null, so heißt das Gleichungssystem homogen, andernfalls inhomogen. Man spricht auch kurz von einem linearen (m, n)- (bzw. m × n) Gleichungssystem über dem Körper $ \mathbb{K} $ .

12. Lineare Optimierung

Auszug

In vielen Problemen der Praxis werden Lösungen gesucht, die bestimmten Einschränkungen genügen. Diese Einschränkungen können oft durch lineare Ungleichungen beschrieben werden.

13. Skalarprodukt und Orthogonalität

Auszug

Wir haben bisher die Addition zweier Vektoren und die Multiplikation eines Vektors mit einem Skalar definiert. Wir wollen nun als Nächstes eine Multiplikation zweier Vektoren einführen, die viele praktische Anwendungen hat: Das Skalarprodukt oder auch innere Produkt 〈a, b〉 zweier Vektoren a = (a₁, a₂, . . . , a_n) und b = (b₁, b₂, . . . , b_n) im ℝⁿ ist definiert als

$$ \left\langle {a,b} \right\rangle = a^T b = \sum\limits_{j = 1}^n {a_j b_j = a_1 b_1 + a_2 b_2 + \cdots + a_n b_n .} $$

14. Eigenwerte und Eigenvektoren

Auszug

Wir haben eine Menge von n linear unabhängigen Vektoren u₁, . . . , u_n ∈ ℝⁿ (oder ℂⁿ) als Basis bezeichnet, da sich jeder Vektor x ∈ ℝⁿ als Linearkombination

$$ x = \sum\limits_{n = 1}^n {y_j u_j } $$

schreiben lässt. Betrachten wir diese Basisvektoren als fix gegeben, so kann der Vektor x sowohl durch seine Koordinaten x₁, . . . , x_n bezüglich der Standardbasis e₁, . . . , e_n, wie auch durch seine Koordinaten y₁, . . . , y_n bezüglich der neuen Basis u₁, . . . , u_n beschrieben werden. Wenn wir die Basisvektoren u_j als Spalten einer Matrix U = (u₁ u₂ . . . u_n) auffassen, dann können wir damit leicht zwischen den verschiedenen Koordinaten hin und her rechnen: x = Uy, y = U^-1x.

Graphentheorie

15. Grundlagen der Graphentheorie

Auszug

Graphen werden in vielen Anwendungsgebieten, wie zum Beispiel Informations- und Kommunikationstechnologien, Routenplanung oder Projektplanung eingesetzt. Sie helfen bei der Beantwortung von Fragen wie: Auf welchem Weg können Nachrichten im Internet möglichst effizient vom Sender zum Empfänger geleitet werden? Wo sollen neue Straßen gebaut werden, um den Verkehrsfluss zu verbessern oder um Wegstrecken zu minimieren? Welche Fahrtroute ist optimal, um möglichst schnell von einem Startort zu einem Zielort zu gelangen? In welcher Reihenfolge soll ein Roboter Löcher in Platinen bohren, sodass er möglichst wenig Zeit pro Platine braucht? Die zunehmende Bedeutung der Graphen kommt vor allem daher, dass sehr komplexe Probleme modelliert und mithilfe von Algorithmen gelöst werden können, die in der Graphentheorie entwickelt wurden.

16. Bäume und kürzeste Wege

Auszug

Bäume gehören zu den wichtigsten Typen von Graphen. Sie sind grundlegende Bausteine für alle Graphen. Darüber hinaus sind sie gut geeignet zur Darstellung von Strukturen bzw. Abläufen (z. B. Suchen, Sortieren).

17. Flüsse in Netzwerken und Matchings

Auszug

Graphen werden oft zur Modellierung von Transportproblemen verwendet. Transportiert wird zum Beispiel Wasser oder Öl in einem Leitungsnetz. Allgemeiner können wir aber auch von einem Fluss von Information, Emails, Anrufen durch ein Kommunikationsnetz, von Menschen im öffentlichen Verkehrsnetz, von PKWs oder Warenlieferungen durch ein Straßennetz, usw. sprechen.

Backmatter

Titel: Mathematik für Informatiker
verfasst von: Gerald Teschl
Susanne Teschl
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-540-70825-4
Print ISBN: 978-3-540-70824-7
DOI: https://doi.org/10.1007/978-3-540-70825-4

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

Grundlagen

1. Logik und Mengen

2. Zahlenmengen und Zahlensysteme

Diskrete Mathematik

3. Elementare Begriffe der Zahlentheorie

4. Polynomringe und endliche Körper

5. Relationen und Funktionen

6. Folgen und Reihen

7. Kombinatorik

8. Rekursionen und Wachstum von Algorithmen

Lineare Algebra

9. Vektorräume

10. Matrizen und Lineare Abbildungen

11. Lineare Gleichungen

12. Lineare Optimierung

13. Skalarprodukt und Orthogonalität

14. Eigenwerte und Eigenvektoren

Graphentheorie

15. Grundlagen der Graphentheorie

16. Bäume und kürzeste Wege

17. Flüsse in Netzwerken und Matchings

Backmatter

Premium Partner