Endliche Strukturen (Mathematik für das Lehramt) (German Edition)

In diesem Band stehen Probleme im Mittelpunkt, die sich zunächst einfach anhören, dann aber eine anspruchsvollere mathematische Bearbeitung verlangen. Sie kommen aus unterschiedlichen Bereichen, doch ist ihnen gemeinsam, dass sie sich auf eine endliche Anzahl von Elementen beziehen. Hierfür werden mathematische Modelle betrachtet und immer wieder die gleichen Fragen gestellt: Hat ein bestimmtes Problem überhaupt eine Lösung? Kann man alle Lösungen systematisch bestimmen? Gibt es dabei einen wirklich effizienten Weg? Das Buch konzentriert sich in fünf Kapiteln auf die grundlegenden algebraischen Strukturen Gruppe, Ring und Körper sowie auf Einblicke in die Galoistheorie, die Codierungstheorie und die Graphentheorie. Am Beispiel endlicher Strukturen wird jeweils aufgezeigt, welche Theorien die Mathematik zur Verfügung stellt, wenn konkrete Fragestellungen wie das Abzählen von Mustern, die Codierung von Nachrichten oder das Aufstellen von Tourenplänen bearbeitet werden sollen. Vorwort 6 Inhaltsverzeichnis 10 1 Grundlagen und Zählprinzipien 12 1.1 Das Induktionsprinzip 14 1.1.1 Das Wohlordnungsaxiom und die Existenz eines kleinsten Elements 15 1.1.2 Beweisen durch vollständige Induktion 16 1.1.3 Induktion und Rekursion 20 1.2 Das Schubfachprinzip 23 1.2.1 Anwendungen des Schubfachprinzips 24 1.2.2 Abbildungen und das Zählen 26 1.2.3 Der Beweis des Schubfachprinzips 30 1.3 Grundprinzipien der Kombinatorik 32 1.3.1 Eine Verallgemeinerung des Schubfachprinzips 32 1.3.2 Permutationen, Variationen, Kombinationen 35 1.3.3 Der Binomische Lehrsatz 41 1.4 Das Inklusions-Exklusions-Prinzip 47 1.4.1 Eine Hinführung zum Inklusions-Exklusions-Prinzip 48 1.4.2 Der Beweis des Inklusions-Exklusions-Prinzips 49 1.4.3 Anwendungen des Inklusions-Exklusions-Prinzips 52 1.5 Übungsaufgaben 59 2 Körper und Polynome 63 2.1 Gruppen, Ringe, Körper 65 2.2 Eigenschaften endlicher Körper 72 2.3 Polynome 82 2.3.1 Rechnen in Polynomringen 83 2.3.2 Primfaktorzerlegung in Polynomringen 86 2.3.3 Ein Weg zur Konstruktion endlicher Körper 98 2.3.4 Noch einmal: Konstruktion endlicher Körper 102 2.4 Automorphismen 106 2.5 Algebraische Zahlen 117 2.6 Übungsaufgaben 121 3 Gruppen und Symmetrien 124 3.1 Der Begriff der Gruppe 126 3.1.1 Gruppen und die Symmetrien des regulären n-Ecks 126 3.1.2 Einfache Eigenschaften von Gruppen und elementare Grundbegriffe 132 3.2 Isomorphie 139 3.2.1 Beispiele isomorpher Gruppen 139 3.2.2 Grundlagen der Bestimmung von Gruppen 142 3.2.3 Faktorgruppen 148 3.3 Permutationen 152 3.3.1 Die symmetrische Gruppe Sn 152 3.3.2 Zyklenzerlegung 154 3.4 Untergruppen der Sn 159 3.5 Operationen von Gruppen auf Mengen 164 3.6 Färbungen 177 3.7 Symmetrien von Polynomen 193 3.8 Übungsaufgaben 205 4 Codierung von Nachrichten 209 4.1 Einführende Beispiele 211 4.2 Fehlererkennung und Fehlerkorrektur 213 4.3 Decodierung 230 4.4 Übungsaufgaben 244 5 Tourenplanung 247 5.1 Grundlegende Eigenschaften von Graphen 250 5.2 Zusammenhängende Graphen 257 5.3 Eulerwege 264 5.3.1 Das Königsberger Brückenproblem 266 5.3.2 Der Algorithmus von Dijkstra 274 5.3.3 Verallgemeinerungen 279 5.4 Der Floyd-Warshall-Algorithmus 281 5.5 Das Müllproblem: Eine Zwischenbilanz 285 5.6 Netzwerke 287 5.7 Der ungarische Algorithmus 297 5.8 Das Müllproblem: Die Bilanz 301 5.9 Ein ungelöstes Problem: P=NP? 303 5.10 Übungsaufgaben 305 6 Lösungen der Übungsaufgaben 308 Literaturverzeichnis 325 Index 326 Der Inhalt wird heute meist unter den etwas vagen Begriff "diskrete Mathematik" gestellt, etwa im Umfang von A. Steger: "Diskrete Strukturen" (ID 33/02). Nach einführenden Abschnitten über Zählverfahren und Beweismethoden sowie über einige algebraische Strukturen folgen Anwendungen auf ausgewählte Fragen zu Symmetrieuntersuchungen, fehlererkennenden Codierungen und an der Praxis orientierten Themen aus der Graphentheorie. Der keineswegs oberflächliche Text ist sehr verständlich und ausführlich, Begriffe und Beweise werden immer anschaulich vorbereitet, dann aber mathematisch streng gefasst. Die gelegentlichen Wiederholungen erleichtern die auswählende Lektüre, führen aber auch zu Längen. Mehr griffige Beispiele hätten belebend gewirkt. Ausführliche Lösungen zu den oft interessanten Aufgaben findet man am Schluss. Der Band ist weitgehend auf der Basis von Schulkenntnissen verständlich, kann also neben Studierenden auch bereits interessierten Schülern zum etwas tieferen Hineinschnuppern in das Fach empfohlen werden. (2 S) Auch wenn die in dem Band behandelten mathematischen Fragen unterschiedlichen Bereichen entstammen, eines ist ihnen gemeinsam: Sie beziehen sich auf eine endliche Anzahl von Elementen. Das Buch konzentriert sich auf die grundlegenden algebraischen Strukturen Gruppe, Ring und Körper und liefert Einblicke in die Galois-, Codierungs- und Graphentheorie. Am Beispiel endlicher Strukturen zeigen die Autoren, welche Theorien auf Problemstellungen wie die Codierung von Nachrichten oder das Aufstellen von Tourenplänen angewendet werden können. Auch wenn die in dem Band behandelten mathematischen Fragen unterschiedlichen Bereichen entstammen, eines ist ihnen gemeinsam: Sie beziehen sich auf eine endliche Anzahl von Elementen. Das Buch konzentriert sich auf die grundlegenden algebraischen Strukturen Gruppe, Ring und Korper und liefert Einblicke in die Galois-, Codierungs-und Graphentheorie. Am Beispiel endlicher Strukturen zeigen die Autoren, welche Theorien auf Problemstellungen wie die Codierung von Nachrichten oder das Aufstellen von Tourenplanen angewendet werden konnen.