🕸️

Diskrete Mathematik: Graphen & Strukturen

60 cards · 🇩🇪 Deutsch

Graphen, Pfade, Bäume und die diskreten Strukturen hinter der Informatik.

logicdiscrete-mathgraphs

Study all 60 cards for free

Flashcards, quizzes, pixel-art games and a daily review that remembers for you.

Study this deck free

Try the first 10 cards

1 / 10
Question

Diskrete Mathematik

Knew itLearning

Tap the card for the answer · swipe right if you knew it, left if not

Already have an account? Sign in

Cards

  1. 1Diskrete Mathematik
    Die Untersuchung mathematischer Strukturen, die grundsätzlich diskret (abzählbar, getrennte Werte) statt kontinuierlich sind, einschließlich ganzer Zahlen, Graphen und logischer Aussagen.
  2. 2Wie unterscheidet sich diskrete Mathematik von kontinuierlicher Mathematik?
    Diskrete Mathematik befasst sich mit abzählbaren, getrennten Objekten (ganze Zahlen, Graphen); kontinuierliche Mathematik befasst sich mit glatten, zusammenhängenden Phänomenen (reelle Zahlen, Analysis, Geometrie).
  3. 3Warum ist diskrete Mathematik wichtig für die Informatik?
    Computer arbeiten in diskreten Schritten und speichern diskrete Bits. Diskrete Mathematik liefert die Grundlagen für Algorithmen, Datenstrukturen, Datenbanken, Kryptografie und theoretische Informatik.
  4. 4Graph in der diskreten Mathematik
    Eine Struktur aus Knoten (Ecken), die durch Kanten verbunden sind. Wird verwendet, um Beziehungen, Netzwerke und Verbindungen darzustellen.
  5. 5gerichteter vs. ungerichteter Graph
    Ungerichtet: Kanten haben keine Richtung (symmetrische Beziehung). Gerichtet (Digraph): Kanten haben eine durch Pfeile angezeigte Richtung (asymmetrische Beziehung).
  6. 6Pfad in einem Graphen
    Eine Folge von Knoten, bei der jedes benachbarte Paar durch eine Kante verbunden ist. Ein einfacher Pfad besucht jeden Knoten höchstens einmal.
  7. 7Zyklus in einem Graphen
    Ein Pfad, der am selben Knoten beginnt und endet. Ein einfacher Zyklus hat außer dem ersten/letzten Knoten keine wiederholten Knoten.
  8. 8Zusammenhängender Graph
    Ein Graph, in dem zwischen jedem Knotenpaar ein Pfad existiert. Keine isolierten Komponenten.
  9. 9Baum in der Graphentheorie
    Ein zusammenhängender, azyklischer (kreisfreier) ungerichteter Graph. Ein Baum mit n Knoten hat genau n-1 Kanten.
  10. 10Spannbaum
    Ein Teilgraph, der alle Knoten des ursprünglichen Graphen enthält und ein Baum ist (zusammenhängend, azyklisch). Wird beim Netzwerkdesign verwendet.
  11. 11Nenne den Vierfarbensatz.
    Jede Landkarte lässt sich mit höchstens vier Farben so färben, dass keine benachbarten Regionen dieselbe Farbe haben. 1976 von Appel und Haken mithilfe von Computern bewiesen.
  12. 12Graphfärbung
    Das Zuweisen von Farben zu Knoten, sodass keine zwei benachbarten Knoten dieselbe Farbe haben. Die chromatische Zahl ist die minimal benötigte Farbanzahl.
  13. 13Vollständiger Graph Kₙ
    Ein Graph, in dem jedes Paar verschiedener Knoten durch eine Kante verbunden ist. Kₙ hat n Knoten und n(n-1)/2 Kanten.
  14. 14Bipartiter Graph
    Ein Graph, dessen Knoten sich in zwei disjunkte Mengen aufteilen lassen, sodass jede Kante einen Knoten der einen Menge mit einem Knoten der anderen verbindet. Keine Kanten innerhalb einer Menge.
  15. 15Eulersche Formel für planare Graphen
    V - E + F = 2, wobei V = Knoten, E = Kanten, F = Flächen (Regionen). Gilt für zusammenhängende planare Graphen.
  16. 16Eulerpfad
    Ein Pfad, der jede Kante genau einmal besucht. Existiert, wenn ein Graph genau 0 oder 2 Knoten mit ungeradem Grad hat.
  17. 17Hamiltonpfad
    Ein Pfad, der jeden Knoten genau einmal besucht. Einen solchen zu finden ist NP-vollständig (rechnerisch schwierig).
  18. 18Kombinatorik
    Die Untersuchung des Zählens, Anordnens und Kombinierens diskreter Objekte. Umfasst Permutationen, Kombinationen und Abzähltechniken.
  19. 19Permutation
    Eine geordnete Anordnung von Objekten. Die Anzahl der Permutationen von n Objekten ist n! = n × (n-1) × ... × 2 × 1.
  20. 20Kombination
    Eine Auswahl von Objekten, bei der die Reihenfolge keine Rolle spielt. Die Anzahl der Möglichkeiten, k Objekte aus n auszuwählen, ist C(n,k) = n!/(k!(n-k)!).
  21. 21Binomialkoeffizient C(n,k)
    Die Anzahl der Möglichkeiten, k Elemente aus n Elementen ohne Berücksichtigung der Reihenfolge auszuwählen. Auch geschrieben als (n über k) oder ₙCₖ.
  22. 22Nenne das Schubfachprinzip.
    Werden n Objekte auf m Behälter verteilt mit n > m, dann enthält mindestens ein Behälter mehr als ein Objekt.
  23. 23Inklusions-Exklusions-Prinzip
    Zum Zählen von Elementen in Vereinigungen von Mengen: |A∪B| = |A| + |B| - |A∩B|. Verallgemeinert sich auf mehr Mengen durch abwechselnde Addition und Subtraktion.
  24. 24Erzeugende Funktion
    Eine formale Potenzreihe, die zur Kodierung von Zahlenfolgen (wie kombinatorischen Anzahlen) verwendet wird. Der Koeffizient von xⁿ liefert das n-te Glied.
  25. 25Pascalsches Dreieck
    Eine dreieckige Anordnung, bei der jede Zahl die Summe der beiden darüberliegenden ist. Zeile n enthält die Binomialkoeffizienten C(n,k) für k=0 bis n.
  26. 26Rekursionsgleichung
    Eine Gleichung, die eine Folge rekursiv in Abhängigkeit von vorherigen Gliedern definiert. Beispiel: Fibonacci Fₙ = Fₙ₋₁ + Fₙ₋₂.
  27. 27Fibonacci-Folge
    F₀=0, F₁=1, Fₙ = Fₙ₋₁ + Fₙ₋₂. Folge: 0, 1, 1, 2, 3, 5, 8, 13, 21, ... Kommt überall in der Natur und der Mathematik vor.
  28. 28Mathematische Logik
    Die Untersuchung formaler Systeme des Schließens, einschließlich Aussagenlogik, Prädikatenlogik und Schlussregeln.
  29. 29Aussage
    Ein deklarativer Satz, der entweder wahr oder falsch ist (aber nicht beides). Beispiel: '5 ist prim' (wahr), '2+2=5' (falsch).
  30. 30Grundlegende logische Junktoren
    UND (∧), ODER (∨), NICHT (¬), IMPLIZIERT (→), GENAU DANN WENN (↔). Werden verwendet, um zusammengesetzte Aussagen aus einfachen zu bilden.

And 30 more cards. Study the whole deck free

More Mathematics decks

See all
Study all 60 cards free