Skip to main content
main-content

Über dieses Buch

Vor 50 Jahren gab es den Begriff ,,Diskrete Mathematik" nicht, und er ist auch heu­ te im deutschen Sprachraum keineswegs gebräuchlich. Vorlesungen dazu werden nicht überall und schon gar nicht mit einem einheitlichen Themenkatalog angebo­ ten (im Gegensatz zum Beispiel zu den USA, wo sie seit langem einen festen Platz haben). Die Mathematiker verstehen unter Diskreter Mathematik meist Kombina­ torik oder Graphentheorie, die Informatiker Diskrete Strukturen oder Boolesche Algebren. Das Hauptanliegen dieses Buches ist daher, solch einen Themenkatalog zu präsentieren, der alle Grundlagen für ein weiterführendes Studium enthält. Die Diskrete Mathematik beschäftigt sich vor allem mit endlichen Mengen. Was kann man in endlichen Mengen studieren? Als allererstes kann man sie abzählen, dies ist das klassische Thema der Kombinatorik - in Teil I werden wir die wichtig­ sten Ideen und Methoden zur Abzählung kennenlernen. Auf endlichen Mengen ist je nach Aufgabenstellung meist eine einfache Struktur in Form von Relationen gegeben, von denen die anwendungsreichsten die Graphen sind. Diese Aspekte fas­ sen wir in Teil II unter dem Titel Graphen und Algorithmen zusammen. Und schließlich existiert auf endlichen Mengen oft eine algebraische Struktur (oder man kann eine solche auf natürliche Weise erklären). Algebraische Systeme sind der Inhalt von Teil III.

Inhaltsverzeichnis

Frontmatter

Abzählung

Frontmatter

1. Grundlagen

Zusammenfassung
Wir wollen einige fundamentale Regeln zusammenfassen, auf denen alle Abzählung basiert. Die ersten beiden Regeln (die so einsichtig sind, dass sie nicht bewiesen werden müssen) beruhen auf einer Klassifikation der Elemente der abzuzählenden Menge.
Martin Aigner

2. Summation

Zusammenfassung
Viele Abzählprobleme reduzieren sich auf die Auswertung von Summen, und umgekehrt lassen sich Zählkoeffizienten oft als eine Summe darstellen. Einige der Standardmethoden, wie man Summen berechnet, wollen wir nun kennenlernen.
Martin Aigner

3. Erzeugende Funktionen

Zusammenfassung
Wir kommen nun zur dritten und weitaus anwendungsreichsten Methode der Zähltheorie. Wir fassen die gesuchten Zählkoeffizienten a 0, a 1, a 2,... als Koeffizienten einer Potenzreihe Σn≥0 a n z n auf. Mit diesen Potenzreihen können wir rechnen, das heißt wir operieren mit den Koeffizienten als Ganzes Wir werden sehen, dass sich manche bisher unzugänglichen Probleme erstaunlich leicht bewältigen lassen.
Martin Aigner

4. Abzählung von Mustern

Zusammenfassung
Viele Abzählprobleme sind von ganz anderer Art als wir sie bisher kennengelernt haben − sie sind durch Symmetrien auf der zugrundeliegenden Struktur bestimmt. Wie man an solche Fragen herangeht, wollen wir uns in diesem Kapitel überlegen.
Martin Aigner

5. Asymptotische Analyse

Zusammenfassung
Wir haben in den vorangegangenen Abschnitten eine Reihe von Methoden kennengelernt, wie man eine Zählfunktion f (n) in den Griff bekommt. Summationen, Rekursionen, erzeugende Funktionen. Was tun, wenn keine dieser Methoden zum Ziel führt? Dann werden wir versuchen, f (n) nach oben und unten abzuschätzen, um wenigstens eine ungefähre Vorstellung von der Größenordnung von f (n) zu bekommen.
Martin Aigner

Graphen und Algorithmen

Frontmatter

6. Graphen

Zusammenfassung
Ein Graph G = (E, K) besteht aus einer (endlichen) Eckenmenge E und einer Menge \( K\subseteq (_{2}^{E}) \) von Paaren {u, v}, uv, genannt Kanten.
Martin Aigner

7. Bäume

Zusammenfassung
Die Theorie der Bäume wurde ursprünglich aus dem Studium der Kohlenwasserstoffverbindungen und anderer Isomere entwickelt.
Martin Aigner

8. Matchings und Netzwerke

Zusammenfassung
Erinnern wir uns an das Job-Zuordnungsproblem. Gegeben ist eine Menge S = {P 1,...,P n } von Personen und eine Menge T = {J 1,...,J n }von Jobs. Wir setzen P i J i K,falls P i für den Job J i geeignet ist. Wir wollen nun eine Zuordnung P i J ϕ(i) finden, so dass jede Person P i einen geeigneten Job J ϕ(i) findet. Wann ist dies möglich? Allgemein werden wir Gewichte auf den Kanten P i J i haben (die wir z. B. als Eignungskoeffizienten interpretieren können), und die Zuordnung soll optimal (= maximal groß) werden.
Martin Aigner

9. Suchen und Sortieren

Zusammenfassung
Eine Variante des folgenden Spieles kennt wahrscheinlich jeder. Jemand verlässt den Raum. Die übrigen Spieler einigen sich auf einen gewissen Begriff. Nach der Rückkehr sucht der ausgewählte Spieler nach dem Begriff, indem er Fragen stellt, die nur ja/nein Antworten erlauben. Errät er den gesuchten Begriff mit höchstens 20 Fragen, so hat er gewonnen.
Martin Aigner

10. Allgemeine Optimierungsmethoden

Zusammenfassung
In den bisherigen Abschnitten von Teil II haben wir eine Reihe von Algorithmen für wichtige Probleme, wie das Job-Zuordnungsproblem oder das Traveling Salesman Problem, kennengelernt und dabei die grundlegenden Fragen diskutiert, die beim Entwurf und der Analyse von Algorithmen auftauchen: Wie beschreiben wir die Algorithmen? Welche Datenstrukturen sollen wir verwenden? Wie schnell ist der Algorithmus? Gibt es überhaupt effiziente Algorithmen?
Martin Aigner

Algebraische Systeme

Frontmatter

11. Boolesche Algebren

Zusammenfassung
Wir studieren die Menge B(n) = {0, 1}n. Die Elemente von B(n) sind also Folgen oder Vektoren x = (x 1 ,..., x n ) von 0’en und 1’en der Länge n, oder 0, 1-Wörter der Länge n. Zunächst ist das einfach eine Menge, aber wir können nun B(n) auf mehrfache Weise interpretieren, auf B(n) verschiedene Strukturen erklären, und das macht die Sache erst interessant. Mit x, y, z... bezeichnen wir stets Elemente aus B(n), mit x, y, z,... einzelne Koordinaten.
Martin Aigner

12. Modulare Arithmetik

Zusammenfassung
Kongruenzen gehören zu den wichtigsten Methoden, die uns zur Behandlung von zahlentheoretischen Fragen zur Verfügung stehen. Wir setzen eine gewisse Vertrautheit voraus, wollen aber alle wichtigen Begriffe zusammenstellen.
Martin Aigner

13. Codierung

Zusammenfassung
Eine besondere interessante Anwendung unserer algebraischen Strukturen ergibt sich bei der sicheren Übertragung von Nachrichten. Bevor wir dies besprechen, wollen wir einige Überlegungen anstellen, wie die Übermittlung von Nachrichten vor sich geht. Zunächst einmal: Wie bilden wir Nachrichten? Die übliche Form sind gesprochene oder geschriebene Wörter. Wenn wir etwas in den Computer eingeben wollen, so drücken wir auf eine Taste, und die Übertragung geschieht mittels der durch die Hardware vorgegebenen mechanischen oder elektrischen Impulse. Telefon, Morseapparat, Telegraph, Funken usf., das alles sind Methoden der Kommunikation.
Martin Aigner

14. Kryptographie

Zusammenfassung
Wir wenden uns nun dem zweiten Aspekt der Kanalcodierung zu — Geheimhaltung von Nachrichten. Man codiere (oder verschlüssele) einen Text T in der Form c(T) Zu c gibt es eine Abbildung d, die wir wiederum Decodierung nennen, so dass d(c(T)) = T gilt. C = c(T) heißt das Kryptogramm (oder Geheimtext). Unsere Aufgabe besteht darin, das Kryptogramm so zu entwerfen, dass es von niemandem (außer dem Empfänger) entschlüsselt werden kann. Der Fehleraspekt spielt hier keine Rolle, wir nehmen an, dass eine Sendung stets fehlerfrei beim Empfänger ankommt.
Martin Aigner

15. Lineare Optimierung

Zusammenfassung
Dieses letzte Kapitel geht etwas über den Rahmen einer Einführung in die Dis­krete Mathematik hinaus. Es geht tiefer in die zugrundeliegende mathematische Struktur und ist daher in der notwendigerweise knappen Darstellung theoretischer als die bisherigen Kapitel. Lineare Optimierung ist aber heute ein derart wichtiges Gebiet mit einer unübersehbaren Fülle von Anwendungen, vor allem für diskrete Probleme (aber nicht nur dort), dass die wesentlichen Ideen und Methoden je­dem „diskreten“ Mathematiker geläufig sein sollten. Im folgenden werden nur die grundlegenden Resultate vorgestellt, für ein weiterführendes Studium sei auf die Literatur verwiesen.
Martin Aigner

Backmatter

Weitere Informationen