Mathematik für Informatiker

Frontmatter

1. Grundbegriffe der Aussagen- und Prädikatenlogik

Zusammenfassung

In diesem Abschnitt müssen Sie einige logische Begriffe lernen, die jeder Mathematiker und Informatiker als Handwerkszeug braucht. Sie beschreiben gewissermaßen die Regeln, die man einhalten muss, wenn man Mathematik macht. Und sie liefern auch die entscheidenden Werkzeuge für die Abstraktionen, die bei jeder Formalisierung von Prozessen aus der realen Welt im Bereich der Informatik und speziell im Bereich der Programmierung so wichtig sind.

Matthias Schubert

2. Grundbegriffe der Mengenlehre

Zusammenfassung

Mengenlehre gibt es seit den achtziger Jahren des 19. Jahrhunderts. Sie wurde von Georg Cantor begründet. Der Begriffsapparat der Mengenlehre hat sich als so nützlich für die Formulierung von Aussagen in den verschiedensten mathematischen Gebieten erwiesen, dass er sich überall durchgesetzt hat. Für den Informatiker sind Mengen und Teilmengen u.a. im Zusammenhang mit den richtigen Beschreibungen der Wertebereiche für Variable in Programmen und für Attribute in Datensätzen von großer Bedeutung.

Matthias Schubert

3. Natürliche Zahlen

Zusammenfassung

Sie kennen die natürlichen Zahlen, es war von ihnen im vergangenen Kapitel des Öfteren die Rede, es sind die Zahlen 0, 1, 2, 3, 4, 5, … Wir schreiben hier und im Folgenden für die Menge der natürlichen Zahlen immer den Buchstaben N. Dass die 0 dazugehört, ist eine relativ neue Festlegung der Mathematiker. «Früher» ließ man die natürlichen Zahlen bei 1 beginnen. In diesem Buch ist in der Menge der natürlichen Zahlen immer die 0 als Element mit enthalten.

Matthias Schubert

4. Andere Schreibweisen für die natürlichen Zahlen

Zusammenfassung

Informatiker sehen Zahlen oft nicht in der uns gewohnten Darstellung, sondern als Dualzahlen oder auch Hexadezimalzahlen. Ich möchte Ihnen kurz erklären, was es damit auf sich hat.

Matthias Schubert

5. Ganze Zahlen und Rationale Zahlen – Gruppen, Ringe und Körper

Zusammenfassung

Nachdem wir uns im letzten Kapitel mehr mit den Darstellungen von Zahlen als mit den diesen Zahlen innewohnenden Gesetzmäßigkeiten beschäftigt haben, kehren wir nun zu unserem alten Geschäft der Erforschung der Zahlen zurück und schreiben diese wieder brav und getreulich im Dezimalsystem.

Matthias Schubert

6. Äquivalenzrelationen und Äquivalenzklassen

Zusammenfassung

Das, was wir in diesem Kapitel besprechen, spielt in den verschiedensten Situationen eine wichtige Rolle:

• Bei der Zusammenfassung von vielen einzelnen, individuell gestalteten Dingen oder Lebewesen zu Gruppierungen. Beispielsweise beim Ubergang von einzelnen Menschen zu den Stadten, in denen diese Menschen wohnen, von da aus zu den Landern, zu denen diese Stadte gehoren usw.
• Diese Fahigkeit, die Dinge auf der richtigen »Granularitatsebene« zu betrachten und dort mit Attributen zu versehen, ist in der Informatik beim Datendesign fur eine Datenbank oder auch bei jedem Entwurf einer Klassenarchitektur fur ein Programm von groser Bedeutung.
• Und schlieslich handelt es sich hier um ein sehr machtiges mathematisches Konzept. Ich werde Ihnen neben den Informatikanwendungen in diesem Kapitel ein wenig zeigen konnen, wie man aus den naturlichen Zahlen N alle anderen mathematischen Konzepte konstruieren kann. Das betrifft hier vor allem die ganzen Zahlen Z und die rationalen Zahlen Q.
• Zu Anfang werden wir aber noch einmal unser Beispiel fur eine Relation aus dem zweiten Kapitel betrachten, die wir mit Hilfe der Modulo-Funktion definiert haben. Diese Betrachtung ist eine wichtige Grundlage fur unsere spateren Kryptographiekapitel. .
• Den Abschluss dieses Kapitels bildet eine Diskussion des Relationenbegriffs im Bereich der Datenbanken.

Matthias Schubert

7. Endliche Gruppen und Endliche Körper

Zusammenfassung

Wir werden in diesem Kapitel die Restklassen - Mengen Zq genauer untersuchen. Bitte denken Sie daran, dass wir Körperstrukturen brauchen, um Gleichungen lösen zu können, in denen addiert und multipliziert wird. Mit anderen Worten: Wir untersuchen hier, wann wir in Zq rechnen können. Was wir hier an Theorie und Verfahren erarbeiten, spielt in mehreren Anwendungen in der Informatik eine wichtige Rolle.

Matthias Schubert

8. Zahlentheorie und Kryptographie

Zusammenfassung

Allen, die sich für das spannende Gebiet der Verschlüsselungen und Geheimcodes interessieren, sei das Buch »Geheime Botschaften« von Simon Singh eindringlich empfohlen [Singh2]. Ich möchte mich in diesem Kapitel auf die mathematischen Hintergründe eines der wichtigsten Verschlüsselungsverfahren konzentrieren. Wir besprechen die so genannte Public Key Verschlüsselung. Sie hat bei allen sicherheitskritischen Kommunikationsprozessen, die im Internet oder auch über andere Übertragungswege stattfinden, eine enorme Bedeutung. Sie ist also wichtig für die Informatik, aber die Informatik ist auch wichtig für diese Form der Verschlüsselung, denn ihre Durchführung ist ohne Computer gar nicht denkbar.

Matthias Schubert

9. Die reellen Zahlen

Zusammenfassung

Die Anlässe für unsere jeweilige Unzufriedenheit mit den natürlichen Zahlen und mit den ganzen Zahlen waren stets die Unlösbarkeit von einfachen Gleichungen.

Matthias Schubert

10. Die komplexen Zahlen

Zusammenfassung

Seit vielen Kapiteln reden wir über die Lösbarkeit von Gleichungen.

Matthias Schubert

11. Lineare Algebra, ein bisschen Geometrie und normierte Räume

Zusammenfassung

Vektorräume gehören zu den wichtigsten mathematischen Strukturen, die bei der Modellierung von Mengen und den Beziehungen der Elemente untereinander auftreten können.

Matthias Schubert

12. Lineare Gleichungen, Matrizen und Determinanten, Lineare Abbildungen

Zusammenfassung

Matrizen sind die »hauseigenen«, die linearen Abbildungen in Vektorräumen bzw. zwischen Vektorräumen. Sie stehen in unmittelbarer Beziehung zu linearen Gleichungen, die einerseits Matrizen in abgewandelter Form darstellen und andererseits der Schlüssel sind zur Bestimmung des Charakters dieser Abbildungen. Mit ihnen und den daraus hervorgehenden Determinanten wird insbesondere ermittelt, ob Matrizen bijektive Abbildungen darstellen. Durch Gleichungen und Matrizen lassen sich auch Geraden und Ebenen, allgemein: Teilräume von Vektorräumen charakterisieren. Das ist ein Aspekt, den wir schon im vergangenen Kapitel kurz behandelt haben und dessen Verständnis wir hier weiter vorbereiten.

Matthias Schubert

13. Boolesche Algebra

Zusammenfassung

Unsere Betrachtungen zur Booleschen Algebra werden sich diesmal – anders als unsere anderen algebraischen Untersuchungen – nicht mit der Lösbarkeit von Gleichungen beschäftigen sondern mit der mathematischen Beschreibung von logischen Formeln und ihren Wahrheitswerten false und true bzw. 0 und 1. Der Name Boolesche Algebra ist eine Erinnerung an George Boole, einen englischen Mathematiker, der von 1815 – 1864 lebte und der auf diesem Gebiet sehr viele Grundlagen erarbeitet hat. Ein weiterer wichtiger Name in diesem Zusammenhang ist der von Claude Shannon, einem amerikanischen Mathematiker und Ingenieur, der 1938 die faszinierende Tatsache entdeckte, dass es eine so große Ähnlichkeit zwischen der Art, wie Logiker argumentieren und der Art, wie elektronische Maschinen rechnen, gibt, dass die Boolesche Algebra dort sehr wirkungsvoll eingesetzt werden kann.

Matthias Schubert

14. Boolesche Gesetze, Dualitäten und Diagramme

Zusammenfassung

Wir haben im letzten Kapitel ein paar Boolesche Gesetze wiederholt bzw. uns neu überlegt. Ich möchte sie noch einmal in einer Form aufschreiben, in der Sie erkennen können, dass es jedes Gesetz in zwei Formen gibt. Zusätzlich erinnere ich Sie noch an die Distributivgesetze aus Kapitel 1 (Satz 1.12).

Matthias Schubert

15. Leonhard Euler und die 7 Brücken von Königsberg

Zusammenfassung

Die russische Stadt Kaliningrad hieß bis 1945 Königsberg und der Fluss Pregolja, an dem Kaliningrad liegt, hieß zu Königsberger Zeiten die Pregel. Mit der Stadt Königsberg und diesem Fluss verbindet sich ein altes mathematisches Rätsel, das den Anlass zur Entstehung völlig neuer mathematischer Teilgebiete, der Graphentheorie und der Topologie, gab. Alles begann damit, dass der große Mathematiker Leonard Euler im Jahre 1736 dieses Rätsel zur Veranschaulichung eines von ihm gelösten mathematischen Problems benutzte.

Matthias Schubert

16. Bäume

Zusammenfassung

Im vorigen Kapitel haben Sie einen einfachen Algorithmus kennen gelernt, mit dem man in einem gegebenen Graphen Euler-Wege und Zyklen finden kann. Es zeigt sich, dass die moderne Graphentheorie voller Probleme steckt, die man am besten algorithmisch löst. Wir werden dazu einige Beispiele diskutieren, die alle wichtige praktische Anwendungen haben. Wir werden in jedem Falle einen effizienten Algorithmus zur Lösung des jeweiligen Problems angeben, den wir auch programmieren werden, und wir werden mehrere Beispiele für die Anwendung dieser Algorithmen diskutieren.

Matthias Schubert

17. Kürzeste Wege und der Algorithmus von Dijkstra

Zusammenfassung

Wir werden in diesem Kapitel einen Algorithmus beschreiben, mit dem man kürzeste Wege in einem Graphen finden kann und der dem Algorithmus von Prim, mit dem wir den MSB-Graphen gefunden haben, sehr ähnlich ist. Er heißt nach seinem Entdecker Dijkstras Algorithmus. Edsger Dijkstra (geboren 1930) ist ein holländischer Mathematiker und Physiker. Er ist einer der »Gurus« der modernen theoretischen Informatik; er entwickelte die strukturierte Programmierung, die Sprache ALGOL und er hat auch noch viele andere fundamentale Beiträge geleistet. Man sagt, dass er »Dijkstras Algorithmus« einfach als ein Beispiel zur Illustration einer seiner Vorlesungen 1959 erfand.

Matthias Schubert

18. Binärbäume und rekursive Strukturen

Zusammenfassung

Binär-Bäume spielen in der Informatik eine herausgehobene Rolle bei der Navigation in hierarchischen Strukturen, die man entsprechend modelliert. Ich hoffe, dieser Satz ist nicht zu rätselhaft, falls doch, bitte ich Sie, am Ende dieses Kapitels diesen Satz noch einmal zu lesen.

Matthias Schubert

19. Paarungsprobleme und ihre ungarischen Lösungen

Zusammenfassung

Sie haben sicher schon bemerkt, dass sich viele Probleme innerhalb der Informatik mittels Graphen modellieren lassen. Dazu gehört auch das Problem der Bildung von Paaren von Objekten in einem Graphen, in dem die Objekte, die möglicherweise zu Paaren zusammengefasst werden können, durch Kanten miteinander verbunden sind. Diese Kanten repräsentieren meistens Präferenzen, die untereinander kollidieren können. Gerade bei diesem Problem gibt es mannigfache Anwendungen – nicht nur innerhalb sondern auch außerhalb der Informatik.

Matthias Schubert

20. Laufzeiten und Komplexitäten, P und NP

Zusammenfassung

In diesem Kapitel versuche ich, Sie ein wenig auf wichtige Diskussionen in der theoretischen Informatik vorzubereiten. Obwohl es ja in diesem Teil des Buches um Graphen, um Algorithmen, um diskrete Mathematik geht, brauchen wir auf einmal wieder dringend die Hilfe aus der Analysis und ich verweise Sie bei Unsicherheiten in Bezug auf die hier benutzten Begriffe auf das Kapitel mit dem Titel »Was Sie schon immer aus der Analysis wissen wollten, aber nie zu fragen wagten – eine kurze Nachricht von einem unserer wichtigsten Sponsoren« im Anhang dieses Buches.

Matthias Schubert

21. Beschreibende Statistik

Zusammenfassung

Statistik ist die Analyse von Beobachtungen oder Versuchen, die mit oder ohne Einfluss des Zufalls entstanden sind. Inwiefern interessiert einen Informatiker die Auswertung von Versuchen? Spätestens im Bereich des Data Warehousing und des Data Mining, bei dem es beispielsweise darum geht, die Bestimmung von geeigneten Ansprechpartnern für Werbe- oder Mail-Kampagnen auf Grund von Verhaltensmustern zu automatisieren, ist man mit dieser Frage auf einem sehr hohen Niveau konfrontiert. Wir werden auf diese Beispiele zu sprechen kommen, ich starte mit einem Beispiel, das ich aus dem sehr motivierenden Buch »Statistics« von Freedman, Pisani und Purves [Freed] übernommen habe.

Matthias Schubert

22. Grundlagen der Wahrscheinlichkeitsrechnung

Zusammenfassung

Im vorherigen Kapitel ging es um möglichst aussagekräftige und umfassende Auswertungen von Versuchen und Umfragen, die in der Realität bereits stattgefunden haben. In den nächsten Kapiteln wird es darum gehen, möglichst richtige Vorhersagen über den Ausgang von bestimmten Experimenten machen zu können. Wir begeben uns also auf ein scheinbar völlig unmathematisches Terrain: das Gebiet des Blicks in die Zukunft.

Matthias Schubert

23. Diskrete Zufallsvariable

Zusammenfassung

Wir werden in den nächsten beiden Kapiteln Verteilungen von Wahrscheinlichkeiten untersuchen. Wir werden uns fragen: Welche Situationen sind sehr wahrscheinlich, welche weniger wahrscheinlich usw. Um Situationen zu beschreiben, brauchen wir Zufallsvariablen. In diesem Kapitel untersuchen wir im Wesentlichen diskrete Zufallsvariablen, das sind Zufallsvariablen, deren Werte alle nicht zu dicht beieinander liegen.

Matthias Schubert

24. Stetige Zufallsvariable

Zusammenfassung

In diesem Kapitel brauchen wir ein paar Kenntnisse aus der Analysis. Wir werden von stetigen Funktionen reden, werden diese integrieren und werden differenzierbare Funktionen ableiten. Ich hoffe hier, dass Sie die nötigen Kenntnisse dazu aus der Schule mitbringen. Gegebenenfalls verweise ich Sie wieder auf den Anhang zu diesem Buch »Was Sie immer über Analysis wissen wollten, aber nie zu fragen wagten«.

Matthias Schubert

25. Schätzungen

Zusammenfassung

Bitte lesen (überfliegen) Sie noch einmal den einleitenden Abschnitt zum 19. Kapitel. Wir wissen jetzt viel mehr und können dieses Beispiel konkreter verstehen. Wir können an ihm Grundregeln für statistisches Arbeiten beobachten.

Matthias Schubert

26. Tests, Tests, Tests

Zusammenfassung

Die Welt, das Internet1, die wissenschaftlichen Institute – alle sind voller statistischer Tests, mit denen man auf Knopfdruck Hypothesen »überprüfen« kann, die auf der Grundlage von empirischen Daten getroffen wurden. Genau darum wird es in dem Kapitel gehen: Wie kann man mit Hilfe von statistischen Testverfahren, die empirisch erhobene Daten auswerten, Hypothesen untermauern bzw. als unwahrscheinlich ablehnen. Auch auf diese Problematik habe ich versucht, am Anfang des 21. Kapitels vorzubereiten. Sie ist natürlich mit der des vorherigen Kapitels eng verwandt. Wir beginnen mit einem klassischen Beispiel, dem man sofort ansieht, in welchem Land, in welchen Kreisen und in welcher Zeit es ausgedacht wurde.

Matthias Schubert

Backmatter