Elementare Kombinatorik für die Informatik

Abzählungen, Differenzengleichungen, diskretes Differenzieren und Integrieren

verfasst von: Kurt-Ulrich Witt

Verlag: Springer Fachmedien Wiesbaden

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

Einloggen, um Zugang zu erhalten

Über dieses Buch

Auf wie viele Arten und Weisen können die Elemente einer Menge einer anderen zugeordnet werden? Wie viele Möglichkeiten gibt es, aus einer Menge eine bestimmte Anzahl von Elementen auszuwählen? Wie können Summen berechnet werden? Wie können Rekursionsgleichungen aufgelöst werden? Das sind Fragestellungen, die in vielen Bereichen der Informatik gelöst werden müssen. Das Buch gibt eine Einführung in Konzepte, Methoden und Verfahren der Diskreten Mathematik, insbesondere der Kombinatorik, mit denen solche Fragestellungen behandelt werden können. Wegen seiner didaktischen Elemente wie Vorgabe von Lernzielen, Zusammenfassungen, Marginalien und einer Vielzahl von Übungen mit Musterlösungen eignet sich das Buch nicht nur als Begleitlektüre zu entsprechenden Informatik- und Mathematik-Lehrveranstaltungen, sondern insbesondere auch zum Selbststudium.

Inhaltsverzeichnis

Frontmatter

1. Einleitung

Zusammenfassung

Kombinatorische Überlegungen kennen wir aus dem täglichen Leben: Wie viele Möglichkeiten gibt es, sechs Zahlen aus 49 zu ziehen? Wie viele Möglichkeiten gibt es, eine Anzahl von Personen an einer Anzahl von Tischen gewisser Größe zu platzieren? Wie oft klingen Gläser, wenn n Personen anstoßen? Im Kern geht es um die Frage, wie viele Möglichkeiten es gibt, aus einer endlichen Menge Teilmengen einer bestimmten Größe auszuwählen. Dabei ist es von Bedeutung, ob bei der Auswahl der Elemente die Reihenfolge der Auswahl eine Rolle spielt oder ob Elemente mehrfach oder nur einmal ausgewählt werden können. Auch in der Informatik ist es oft erforderlich, kombinatorische Überlegungen anzustellen: Wie viele Verbindungen einer bestimmten Länge gibt es in einem Rechnernetz? Wie viele Operationen führt ein Programm bei der Eingabe einer bestimmten Größe durch? Auf wie viele Arten kann eine Menge von Programmen auf einer Menge von Prozessoren ausgeführt werden?

Kurt-Ulrich Witt

2. Permutationen und Kombinationen

Zusammenfassung

In diesem Kapitel beschäftigen wir uns mit der Auswahl von Teilmengen von endlichen Mengen, dabei insbesondere mit der Frage, wie viele Möglichkeiten es prinzipiell gibt, solche Auswahlen zu treffen. Dabei unterscheiden wir bei der Auswahl, ob Elemente nur einmal oder wiederholt ausgewählt werden können und ob die Reihenfolge der Auswahl eine Rolle spielt.

Kurt-Ulrich Witt

3. Partitionen

Zusammenfassung

Im vorigen Kapitel haben wir uns mit der Auswahl und dem Abzählen von Teilmengen einer gegebenen Menge beschäftigt und dabei unterschieden zwischen geordneten und ungeordneten Auswahlen sowie zwischen Auswahlen mit und ohne Wiederholung. Am Ende des Kapitels haben wir bereits einen Zusammenhang zwischen ungeordnetem Auswählen mit Wiederholung und einer gewissen Art von Zerlegung einer Zahl in Summanden einer bestimmten Anzahl gesehen. In diesem Kapitel werden solche Zahlpartitionen detailliert betrachten. Des Weiteren betrachten wir gleichermaßen Mengenpartitonen sowie die Anzahl von Abbildungen, die zwischen zwei endlichen Mengen möglich sind, wenn diese Abbildungen bestimmte Eigenschaften erfüllen.

Kurt-Ulrich Witt

4. Abzählmethoden und das Urnenmodell

Zusammenfassung

Wir haben bereits im ersten Kapitel bei der Bestimmung der Anzahl von Permutationen und Kombinationen mit und ohne Wiederholung bestimmte Grundannahmen gemacht. So sind wir z.B. davon ausgegangen, dass endliche Mengen, deren Elemente man eineindeutig einander zuordnen kann, die gleiche Anzahl von Elementen besitzen, und dass die Gesamtzahl der Verinigung von disjunkten endlichen Mengen gleich der Summe der Elementanzahlen dieser Mengen ist. In diesem Kapitel werden die grundlegenden Abzählmethoden dargestellt. Des Weiteren wird das Urnenmodell vorgestellt, welches der Veranschaulichung von Auswahl- und Abzählmethoden gilt.

Kurt-Ulrich Witt

5. Erzeugende Funktionen

Zusammenfassung

Aus Gleichung (1.24) wissen wir, dass sich die Funktion (1+z)ⁿ als Polynom darstellen lässt:

$$ (1 + z)^{n} = \sum^{n}_{k=0} \binom{n}{k} z^{k} $$

(4.1)

Der Koeffizient von z ^k ist dabei K(n, k) = ( _k ⁿ ), die Anzahl der k-Kombinationen einer n-elementigen Menge. Die Polynomdarstellung (4.1) der Funktion f(z) = (1+z)ⁿ enthält also eine kombinatorische Information: Wir können diese Funktion als eine erzeugende Funktion für die Zahlen K(n, k) betrachten. Dieses Kapitel gibt eine Einführung in erzeugende Funktionen.

Kurt-Ulrich Witt

6. Lineare Differenzengleichungen

Zusammenfassung

In der Informatik werden oft die Glieder einer Folge a ₀, a ₁, a ₂, ... oder die Werte f(0), f(1), f(2), ... einer Funktion f : ℕ₀ → ℝ rekursiv definiert, d.h. es werden Anfangswerte der Folge bzw. der Funktion angegeben und die weiteren Werte werden dann als Funktion bereits berechneter Werte bestimmt. Ein bekanntes Beispiel ist die Fakultätsfunktion ! : ℕ₀ → ℕ₀ definiert durch

$$ n! = \begin{cases} 1, & \text{falls } n = 0 \\ n \cdot (n-1)!, & \text{falls } n \geq 1 \end{cases} $$

(5.1)

Es ergibt sich für $ n \geq 1: n! = \prod_{k=1}^{n} k $ als Produkt der Zahlen von 1 bis n.

Kurt-Ulrich Witt

7. Diskretes Differenzieren und Integrieren

Zusammenfassung

Konzepte und Methoden der Differentiation und Integration stetiger Funktionen können auf diskrete Funktionen übertragen werden. Analog definierte Operatoren zeigen dabei analoge Eigenschaften. Anwendungen dieser Operatoren führen z.B. zur geschlossenen Darstellung von Summen von Potenzen und Summen von Faktoriellen. Wir werden sehen, dass dabei die Stirlingzahlen erster und zweiter Art eine wichtige Rolle spielen.

Kurt-Ulrich Witt

Backmatter

Titel: Elementare Kombinatorik für die Informatik
verfasst von: Kurt-Ulrich Witt
Verlag: Springer Fachmedien Wiesbaden
Electronic ISBN: 978-3-658-00994-6
Print ISBN: 978-3-658-00993-9
DOI: https://doi.org/10.1007/978-3-658-00994-6