Übersicht der Themen

  • Logik

    • Boolesche Aussagenlogik (+ Syntax, Wertetabelle)
    • Boolesche Gesetze (semantische Äquivalenzen)
    • (Kanonische) Disjunktive Normalform (DNF), (Kanonische) Konjunktive Normalform (KNF)
    • Resolutionskalkül

    Mengen

    • Mengen und Operationen auf Mengen
    • Darstellung, Urbild
    • Abstraktionsprinzip (Gleichheit, Mächtigkeit, Komplement)
    • Teilmenge, Obermenge
    • Venn-Diagramme
    • Potenzmenge
    • Kartesisches Produkt
    • Binäre Relation (Grafisch, Matrix)
      • Reflexivität, Symmetrie, Transitivität
    • Äquivalenzrelation / -klassen
    • Totale Ordnung / Halbordnung, lexikographische Ordnung
    • Hasse-Diagramme
    • Poset: minimales, maximales Element, Supremum (kleinste obere Schranke), Infimum (größte untere Schranke)
    • Scheduling, gerichtete Zyklen, topologisches Sortieren (Funktionen / Abbildungen)
    • surjektiv, injektiv, bijektiv
    • Abzählbarkeit, Cantorsche Diagonilisierungsmethode)

    Beweise

    • Direkter Beweis
    • Widerspruchsbeweis
    • Schubfachprinzip
    • Vollständige Induktion
    • Strukturelle Induktion

    Kombinatorik

    • Abzählbarkeit
    • Gleichheitsregel, Summenregel, Produktregel
    • Permutationen
    • Inklusion, Exklusion
    • Binomialkoeffizienten
    • Bijektion
    • Mengenpartitionen, Zahlpartitionen (geordnet, ungeordnet)
    • Zählkoeffizienten
    • Rekursion

    Wahrscheinlichkeit

    • elementare Eigenschaften
    • Baumdiagramme
    • bedingte Wahrscheinlichkeit
    • Unabhängigkeit
    • Zufallsvariable
    • Erwartungswert (Linearität), Varianz
    • totale Wahrscheinlichkeit
    • spezielle Verteilungen (Binomialverteilung, geometrische Verteilung, Bernoulli)
    • Harmonische Zahlen

    Graphen

    • Graph, Knoten, Kanten
    • ungerichtet, gerichtet
    • Adjazenzmatrix
    • Untergraph (induziert)
    • Isomorphie
    • bipartiter Graph
    • Wege, Kreise
    • Baum
    • zusammenhängend
    • Aufspannender Baum