LERNLEITFADEN · 3 INTERAKTIVE LABORE · ETWA 12 MIN.

Ein gemischtes Kartenspiel liegt fast sicher in einer Reihenfolge, die noch nie jemand in der Hand hatte.

Es gibt 52! Möglichkeiten, ein Kartenspiel anzuordnen: eine 68-stellige Zahl, weit mehr als die Sekunden seit dem Urknall. Diskrete Mathematik befasst sich mit Dingen, die man einzeln zählen kann: Anordnungen, Netzwerke, wahre oder falsche Aussagen. Es ist die Mathematik, auf der Computer tatsächlich laufen.

WIE SCHNELL FAKULTÄTEN WACHSEN
5!120Möglichkeiten, 5 Personen aufzureihen
10!3.628.800Möglichkeiten, 10 Bücher zu ordnen
13!6.227.020.800mehr als die Weltbevölkerung
20!2,43 × 10^18mehr als Sandkörner an allen Stränden (gesch.)
52!8,07 × 10^67Anordnungen eines Kartenspiels

Was ist diskrete Mathematik?

Diskrete Mathematik untersucht Strukturen aus getrennten, abzählbaren Teilen statt aus stetigen Größen: ganze Zahlen, Mengen, logische Aussagen, Graphen (Netze aus Punkten und Verbindungen) und Arten, Anordnungen zu zählen.

Die Analysis fragt, wie sich Dinge stetig ändern; diskrete Mathematik fragt, wie viele, welche und ob es überhaupt möglich ist. Sie liegt Algorithmen, Kryptografie, Datenbanken, Netzwerkrouting und jedem Beweis zugrunde, dass ein Programm korrekt ist.

GraphentheorieNetze aus Punkten und Verbindungen: Karten, soziale Netzwerke, das Web.
KombinatorikAnordnungen und Auswahlen zählen.
LogikWahr/falsch-Denken, Grundlage von Schaltungen und Beweisen.
ZahlentheoriePrimzahlen und Reste: die Mathematik der Verschlüsselung.
LABOR 1 · GRAPHENTHEORIE

Überqueren Sie jede Brücke genau einmal

Klicken Sie auf eine Landmasse, um zu beginnen, dann auf Brücken, um sie zu überqueren. Keine Brücke darf zweimal benutzt werden. 1736 bewies Euler, wann das möglich ist: Ein Weg existiert nur, wenn null oder zwei Landmassen eine ungerade Zahl von Brücken berühren.

NGrad 3SGrad 3IGrad 5EGrad 3
0 / 7Brücken überquert
4Landmassen mit ungeradem Grad
IHR WEGKlicken Sie auf eine Landmasse, um zu beginnen
Diese Karte hat 4 Landmassen mit einer ungeraden Zahl von Brücken. Laut Eulers Regel sind das zu viele. Versuchen Sie es trotzdem!
LABOR 2 · ABZÄHLEN

Zählt die Reihenfolge? Das ändert alles

Wählen Sie k Elemente aus n. Zählt die Reihenfolge (ein Podium, eine PIN), ist das eine Variation. Zählt sie nicht (ein Kartenblatt, ein Ausschuss), ist es eine Kombination: Teilen Sie durch die k! Anordnungen jeder Gruppe.

Gold, Silber und Bronze aus 8 Läufern: 336 Podien, aber nur 56 verschiedene Dreiergruppen von Medaillengewinnern.
REIHENFOLGE ZÄHLT · nPk336n! / (n − k)!
z. B. Auswahl von 3 aus A-D:ABCABDACBACDADBADCBACBAD…
REIHENFOLGE EGAL · nCk56n! / (k! (n − k)!)
z. B. Auswahl von 3 aus A-D:ABCABDACDBCD…
PASCALSCHES DREIECK, ZEILE 8 (nCk FÜR JEDES k)
LABOR 3 · DAS SCHUBFACHPRINZIP

Mehr Tauben als Löcher: Irgendwer muss teilen

Legen Sie n + 1 Dinge in n Kisten, und mindestens eine Kiste bekommt zwei. Das klingt selbstverständlich, beweist aber überraschende Tatsachen. Hier werden Menschen nach Geburtsmonat sortiert: Fügen Sie eine 13. Person hinzu, und ein gemeinsamer Monat ist garantiert.

Jan
Feb
Mär
Apr
Mai
Jun
Jul
Aug
Sep
Okt
Nov
Dez
Fügen Sie Menschen einzeln hinzu. Jeder landet in einem zufälligen Geburtsmonat.

Kernideen auf einen Blick

Eulerweg0 oder 2 Knoten mit ungeradem GradNötig, um jede Kante einmal zu durchlaufen.
HandschlaglemmaΣ deg(v) = 2 × KantenDie Zahl der Knoten mit ungeradem Grad ist also immer gerade.
VariationennPk = n! / (n − k)!Reihenfolge zählt.
KombinationennCk = n! / (k!(n − k)!)Reihenfolge egal.
Schubfachn + 1 Dinge, n Kisten → eine Kiste enthält 2Garantiert eine Kollision.
Implikationp → q ≡ ¬p ∨ qNur falsch, wenn p wahr und q falsch ist.
De Morgan¬(p ∧ q) ≡ ¬p ∨ ¬qDie Verneinung von „und“ ergibt „oder“.
Bäumen Knoten → n − 1 KantenZusammenhängend und ohne Kreise.

Von Euklid zum Internet

um 300 v. Chr.Euklid.Bewies, dass es unendlich viele Primzahlen gibt, und lieferte den Algorithmus für den größten gemeinsamen Teiler.
1654Pascal und Fermat.Briefe über ein Glücksspielproblem begründeten die Wahrscheinlichkeitsrechnung und systematisches Zählen.
1736Eulers Brücken.Sein Königsberg-Beweis gilt als erster Satz der Graphentheorie.
1854Boolesche Algebra.George Boole machte die Logik zur Algebra; 80 Jahre später nutzte Shannon sie zum Entwurf von Schaltungen.
1959Dijkstra-Algorithmus.Kürzeste Wege in einem Graphen, heute in Karten und Netzwerkrouting genutzt.
1976Vierfarbensatz.Bewiesen mit einem Computer, der fast 2.000 Fälle prüfte.

Weiterlesen

Discrete Mathematics and Its ApplicationsKenneth Rosen · das Standardlehrbuch an Universitäten
Mathematics for Computer ScienceLehman, Leighton & Meyer · freier MIT-Text
Concrete MathematicsGraham, Knuth & Patashnik · der tiefgehende Klassiker
Testen Sie sich: 20 Fragen zur diskreten MathematikLeitfaden Algorithmen

Rätsel wie das von Euler sind reines Denken. Messen Sie Ihres.

Unser vollständiger IQ-Test deckt logisches, numerisches, sprachliches und räumliches Denken ab: 60 Fragen, etwa 30 Minuten.

Vollständigen IQ-Test machen